Warp <war### [at] tagpovrayorg> wrote:
> stevenvh <nomail@nomail> wrote:
> > when I recently started working with (natural) splines I was somewhat
> > disappointed to see that the generated points weren't evenly spaced.
>
>   That's a normal property of splines.
>
>   If you calculate points along a spline at evenly-spaced time values,
> the distance between these points depend on the geometry of the spline
> (the distance between control points and the spline curvature). This is
> the fastest way of calculating points along a spline (and in many cases
> even the desired thing because it produces smooth and natural-looking
> "acceleration" and "deceleration", and other non-linear effects).
>
>   Calculating evenly-spaced points in a spline is a hard problem.
> The easiest (although perhaps not the absolute fastest) solution to
> it is to approximate by adaptive sampling. This means that the next
> point in the spline is searched by first calculating one point at
> a "guessed" distance, then refine that "guess" and calculate another
> point, and so on, all the time approaching the actual point (which will
> never be actually reached, but the end result will be quite close to it).
>
>   POV-Ray doesn't offer internally any such approximation feature. If you
> need it, you'll have to create the necessary SDL code yourself.
>
> > Suppose you want to place 100 objects evenly along the spline's path.
> > You create an array of 10000 elements, say a few orders of magnitude more than
> > the number of points you're interested in. Calculate 10000 points on the
> > spline, and the distance from the previous point.
>
>   That's a much slower approach than the adaptive sampling. It also wastes
> a lot of memory.
>
> --
>                                                           - Warp

Can you actually apply adaptive sampling here? Do you have code for it, or an
elaborated algorithm?
POV-Ray's spline returns a point somewhere on the spline, but if you go for the
next point, there's no way to know the distance between the two. The only thing
you know is that the function is monotonic, i.e. that if a<b<c then MySpline(b)
will be between MySpline(a) and MySpline(c) on the curve. That's it.
By calculating a large number of points close to each other I can approximate
the curve between two adjacent points by a straight line.

I was also worried about speed, but on my PC it takes just a few hundred ms
extra, and I can afford the extra 200KB too :-)

Steven

Post a reply to this message