 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Hi,
when I recently started working with (natural) splines I was somewhat
disappointed to see that the generated points weren't evenly spaced.
This is not a problem when modeling a garden hose, where the constituting
spheres should be packed close to get a smooth surface, but it cab be a bit of
a nuisance when placing a series of disjunct objects along the spline's path.
So I tried to get my objects evenly spaced. Here's the idea:
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. In the array you store the
accumulated distances. So the n-th entry holds the path length from start to
point n.
When the array is filled you also know the total path length L, suppose L equals
12.34. Now find in the array the partials lengths of 12.34 / 100, 2 * 12.34 /
100, 3 * 12.34 / 100, etc.
Store the indices of those values in a new array, a lookup table
which translates between a position on the spline and the parameter POV-Ray's
spline function wants to give you the point at that position.
That's it. Questions, comments, ideas, constructive criticism and alternate
solutions are welcome.
My suggestion is to add this functionality to spline in a future version of
POV-Ray.
Code below is just a quick-and-dirty test program, no optimization, no nothing.
Steven
***** Code starts here **************************************************
/******************************************************************************
/
/ Evenly spaced points on spline
/
/ Steven Van Hulle
/ POV-Ray v3.6
/ 2008-04-11
/
******************************************************************************/
#include "colors.inc"
#include "transforms.inc"
#default { finish{ ambient 0.7 } }
background { Gray85 }
light_source { <-30, 30, -30> color White }
camera {
location <0.0, 1, -5.0>
direction 3.0*z
right x * image_width / image_height
look_at <0.0, 0.7, 0.0>
}
#macro Sqr(n) n*n #end
#macro Distance(A, B) sqrt(Sqr(A.x - B.x) + Sqr(A.y - B.y) + Sqr(A.z - B.z))
#end
#declare Path_Spline = spline {
natural_spline
-0.25, <-2, 0, 0>
0.00, <-1, 0, 0>
0.25, <-0.15, 0.5, 0>
0.50, < 0, 1.5, 0>
0.75, < 0.75, 0.5, 0>
1.00, < 1, 0, 0>
1.25, < 2, 0, 0>
};
#declare Path_Spline2 = spline {
natural_spline
-0.25, <-2.1, 0, 0>
0.00, <-1.1, 0, 0>
0.25, <-0.25, 0.5, 0>
0.50, <-0.1, 1.5, 0>
0.75, < 0.65, 0.5, 0>
1.00, < 0.9, 0, 0>
1.25, < 1.9, 0, 0>
};
#declare npoints = 100;
#declare resol = 100;
#declare dist = array[npoints * resol + 1];
#declare points = array[npoints + 1];
#declare dist[0] = 0;
#declare prevpt = Path_Spline(0);
#local ii = 1;
#while (ii <= npoints * resol)
#declare newpt = Path_Spline(ii/(npoints * resol));
#declare dist[ii] = dist[ii-1] + Distance(prevpt, newpt);;
#declare prevpt = newpt;
#declare ii = ii + 1;
#end
#local Ltot = dist[npoints * resol];
#declare points[0] = 0;
#local p = 1;
#local jj = 0;
#while (p <= npoints)
#declare targetval = Ltot * p / npoints;
#while ((dist[jj] < targetval) & (jj < npoints * resol))
#declare jj = jj + 1;
#end
#declare points[p] = jj;
sphere {Path_Spline(jj/(npoints * resol)), 0.005 pigment{Blue}}
#declare p = p + 1;
#end
// show common spline
#local C = 0;
#while (C <= 1)
sphere{Path_Spline2(C),0.005 pigment {Red}}
#local C=C+0.01;
#end
text {
ttf "arial.ttf" "POV-Ray spline"
.001, 0 pigment { Red } scale 0.05 translate <-1, 1.4, 0>
}
text {
ttf "arial.ttf" "Evenly spaced spline"
.001, 0 pigment { Blue } scale 0.05 translate <-1, 1.33, 0>
}
***** Code ends here ****************************************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp <war### [at] tag povrayorg> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
47ff5d1b@news.povray.org...
>
> POV-Ray doesn't offer internally any such approximation feature. If you
> need it, you'll have to create the necessary SDL code yourself.
>
I think it is implemented in Chris Colefax's spline macros
http://www.geocities.com/ccolefax/spline/index.html
Marc
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Among other things, stevenvh saw fit to write:
> Hi,
> when I recently started working with (natural) splines I was somewhat
> disappointed to see that the generated points weren't evenly spaced.
> This is not a problem when modeling a garden hose, where the constituting
> spheres should be packed close to get a smooth surface, but it cab be a
> bit of a nuisance when placing a series of disjunct objects along the
> spline's path. So I tried to get my objects evenly spaced. Here's the
> idea:
This article may be interesting
http://www.cs.uiowa.edu/~kearney/pubs/CurvesAndSurfacesArcLength.pdf
I recently applied this idea for representing the reaction path of a
chemical reaction (in multidimensional space, though).
--
light_source{9+9*x,1}camera{orthographic look_at(1-y)/4angle 30location
9/4-z*4}light_source{-9*z,1}union{box{.9-z.1+x clipped_by{plane{2+y-4*x
0}}}box{z-y-.1.1+z}box{-.1.1+x}box{.1z-.1}pigment{rgb<.8.2,1>}}//Jellby
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote in message <47ff5d1b@news.povray.org>:
> 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).
I think there is something missing in your solution. As far as I know, the
arc length on a spline is not something we can get in closed form. In fact,
that is exactly the cause of the problem in the first place.
Therefore, to compute how much the guessed point if off the desired point,
it is necessary to integrate from the beginning of the curve (or the last
known point). In that case, a simple, linear method is more efficient.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
// calculate the length of a spline
#macro Len_Spline(Espl begin_at stop_at num)
#local c = 1/num;
#local V1 = Espl(begin_at);
#local result = 0;
#while (c <= 1)
#local V2 = Espl( c*(stop_at - begin_at) + begin_at);
#local result = result + vlength(V2-V1);
#local V1 = V2;
#local c = c + 1/num;
#end
(result)
#end
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Tim Attwood" wrote in message <4802861b@news.povray.org>:
> #local result = result + vlength(V2-V1);
In the particular case of a spline, we know the derivative vector at any
point. I suspect it would be more accurate to use its length rather than the
distance between two consecutive points.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> #local result = result + vlength(V2-V1);
>
> In the particular case of a spline, we know the derivative vector at any
> point. I suspect it would be more accurate to use its length rather than
> the
> distance between two consecutive points.
I don't follow, maybe you could explain that?
I've read through a book on topology a while back and it
seemed very dense to me, isn't a derivative vector a
derivative in respect to a vector field? A vector field
being a mapping from R^n to R^n? I think in this case
a spline is a mapping from R to R^3, doesn't that
rule out some of this sort of math? Remember that
we don't know the type of spline here either.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood napsal(a):
>>> #local result = result + vlength(V2-V1);
>> In the particular case of a spline, we know the derivative vector at any
>> point. I suspect it would be more accurate to use its length rather than
>> the
>> distance between two consecutive points.
>
> I don't follow, maybe you could explain that?
> I've read through a book on topology a while back and it
> seemed very dense to me, isn't a derivative vector a
> derivative in respect to a vector field? A vector field
> being a mapping from R^n to R^n? I think in this case
> a spline is a mapping from R to R^3, doesn't that
> rule out some of this sort of math? Remember that
> we don't know the type of spline here either.
>
>
A derivative is always with respect to a scalar and any vector is
differentiable. An operator over R^n -> R^n is a divergence (nabla dot).
R^3 -> R^3 has a rotation (nabla cross) aditionally.
R^n -> R (a scalar field) has a gradient (nabla; vector of derivations
along axes).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
