Am 09.05.2017 um 19:08 schrieb Thorsten Froehlich:
> clipka <ano### [at] anonymousorg> wrote:
>> Am 09.05.2017 um 14:14 schrieb William F Pokorny:
>>
>>> The great news is Christoph fixed ALL the sphere_sweep auto-bounding
>>> issues I have in hand in beta 6! The auto-bounding issue has dogged
>>> sphere_sweeps from day one with this object.
>>
>> In a certain sense I cheated: Rather than trying to come up with a
>> formula to compute the minimum and maximum coordinates of a sphere sweep
>> based on a Catmull-Rom spline (the thing POV-Ray calls `cubic_spline`),
>> I just searched the Internerds for a formula to translate a Catmull-Rom
>> spline into a (temporary) equivalent Bezier spline, and then exploiting
>> the neat property that a Bezier spline can never "overshoot" its control
>> points.
> 
> IIIRC that is actually the only solution because afaik one cannot compute the
> convex hull of a Catmull-Rom spline.

We don't need the convex hull; we just need to identify the minimum and
maximum for any given coordinate.

Like any 3rd order polynomial splines, at their heart Catmull-Rom
splines boil down to piecewise cubic functions with vector coefficients
and a "time-like" parameter. As such, we can consider each dimension
separately, i.e. we can treat the thing as a set of piecewise 3rd order
polynomials, one for each dimension.

For each polynomial we can identify the local minima and maxima by
looking for the roots of the first derivative. We're already computing
the coefficients of the base function anyway, so computing the
coefficients of the first derivative should be a piece of cake. We can
then test those roots for falling inside the relevant interval.

Cobbling together all the local minima and maxima of all the pieces, we
can then determine the smallest local minimum and largest local maximum.

Finally, we can throw the endpoints into the mix, to deal with cases
where the absolute minimum or maximum is not a local one, but rather at
a border of a piece.


That would be the algorithm for an infinitesimally thin spline. A sphere
sweep is a bit more complicated, but if I'm not mistaken we would
actually just have to examine the sum / difference of the location
function and the radius function (instead of the pure location function)
for the local maxima and minima, respectively. And since we're dealing
with polynomials, that's just a matter of adding / subtracting the
coefficients.

Post a reply to this message