This is a quite interesting problem.  I have an idea, but I haven't
tested it so I don't know how well it would work.  Once you have a
spline of the right length, you can use Peter Popov's method to place
the points equally along it, so the problem, as you said, is finding a
spline of the correct length.  My idea is that you could take your
starting spline and calculate its total length (using an approximating
sum).  Then take how this sum compares to the desired length, you could
then move the control points toward or away from the line connecting the
endpoints of the spline and repeat the process until the spline has a
length that is close enough to what you want.  The advantage of this
method is that you can change exactly how the control points are moved
to get an effect more like what you are looking for.

Post a reply to this message

On Tue, 28 Dec 1999 23:33:16 +0100, "Rune" <run### [at] inamecom>
wrote:

>However, I'm not sure what the difference is between this:
>
>>Do this until no force is greater than a certain threshold value
>
>...and this:
>
>>or even better, the standard deviation of the forces
>>falls below a certain level (i.e. the spline is equistressed).

The difference is that if you have too many points, the forces between
them may be great but still equal, which would force the first
algorithm into an infinite loop, while the second (which looks at the
deviation) will stop seeing that all forces are virtually equal.

>But I guess that's not so important anyway. I get the basic idea.

For once I was able to make a clear point :)

>Greetings,
>
>Rune


Peter Popov
pet### [at] usanet
ICQ: 15002700

Post a reply to this message

Rune <run### [at] inamecom> wrote:
> I'm trying to make a long neck-like thing. I must be able
> to set the point where the neck starts and ends. Also the
> normal of the neck in these two points. ("normal" is
> probably not the right word. "Vector" or "direction" is
> probably better, but I'll just use "normal" here) I also
> want to control the length of the neck and the number of
> "links" or segments it is made of. ( The length of each
> "link" would then be [length-of-neck] / [number-of-links] )
[snip]
> I have succeeded in making the points having the right
> distance to each other:
>
> A force is applied to each point. If the point is closer to
> it's neighbor than the desired length then it is pushed
> away from it. If the point is further away the neighbor
> than the desired length then it is pulled closer to it.
> This calculation is done to each sphere with each of each
> sphere's two neighbors. The difference between the old
> and the new position is multiplied with a small value (*1),
> then stored in a temporary array. When the calculations are
> done to each sphere, the changes are applied. Then it
> starts all over and over again a certain number of times (*2).
>
> This makes the point have the right distance to each other,
> but nothing prevents the "neck" from bending so
> unfortunately the points arrange themselves in a zig-zag
> pattern.
>
> I need help with making some forces that makes the "neck"
> bend as little as possible, i.e. make the distribution of
> the bending even, that way making the curve smooth.
> (look in "ikn.inc" line 45.)

To avoid confusion I think it helps to use the word 'tangent' when you're
talking about a vector tangential to the curve, particularly as 'normal' has
particular meanings in POV-Ray (and, of course, in any discussions about
mathematical curves and surfaces).

Now, given the example you posted to .binaries and your description of your
goal I would say the method you're using (inverse kinematics) is quite
suitable.  To avoid kinking perhaps you could apply an extra constraint to
each link which checks the angle it forms with the links around it, eg.
given three sphere centres (P1, P2, and P3) you could calculate the cosine
of the angle using:

   vdot (vnormalize (P2 - P1), vnormalize (P3 - P2))

To stop the kinking you want this to be as close as possible to -1 (the
cosine of 180 degrees), so in addition to being pulled by the endpoints and
tangents and being forced to be separated by a certain distance, the spheres
also try to form a straight line (or as close as possible given the other
constraints).

Post a reply to this message

Kevin Wampler wrote:

> This is a quite interesting problem.  I have an idea, but I haven't
> tested it so I don't know how well it would work.  Once you have a
> spline of the right length, you can use Peter Popov's method to place
> the points equally along it, so the problem, as you said, is finding a
> spline of the correct length.  My idea is that you could take your
> starting spline and calculate its total length (using an approximating
> sum).  Then take how this sum compares to the desired length, you could
> then move the control points toward or away from the line connecting the
> endpoints of the spline and repeat the process until the spline has a
> length that is close enough to what you want.  The advantage of this
> method is that you can change exactly how the control points are moved
> to get an effect more like what you are looking for.

Come to think of it, you could probably get even better results by
translating each control perpendicularly away from the line connecting the
two control points on either side of it instead of away from the endpoints
of the spline

Post a reply to this message

Wasn't it Rune who wrote:
>Mike Williams wrote:
>>Wasn't it Rune who wrote:
>
>>>I'm trying to make a long neck-like thing. I must be able
>>>to set the point where the neck starts and ends. Also the
>>>normal of the neck in these two points. ("normal" is
>>>probably not the right word. "Vector" or "direction" is
>>>probably better, but I'll just use "normal" here) I also
>>>want to control the length of the neck and the number of
>>>"links" or segments it is made of. ( The length of each
>>>"link" would then be [length-of-neck] / [number-of-links] )
>
>>Unfortunately, also, there's nothing that restrains the first and last
>>links to remain oriented along the specified vector, and the "pull" from
>>the other links causes them to be drawn noticeably off line. (I guess
>>that if you tweak the code to restrain the first and last link, then
>>you'd get a kink at link 2 and link n-1.)
>
>Yes, that's a problem.
>
>>I also guess that the curve to which this converges is actually the same
>>shape as a spline, but with equidistant points. You say that a spline
>>doesn't give you a very realistic neck bend, but I reckon that that's
>>the shape you'll end up with if you ever get this working.
>
>OK, I'll drop my original idea about adding forces to points in a spline.
>
>
>Instead I'll calculate the spline with the right total length and then try
>to use Peter Popov's method to figure equidistant points.
>
>However, I don't know yet how to calculate the spline with the right total
>length.
>
>>It's fairly easy to calculate the spline with the right total
>>length (performing a binary chop on the value I just tweaked above),
>
>Could you explain this in greater detail?

I'll post some code that does this to povray.binaries.scene-files.



-- 
Mike Williams #
Gentleman of Leisure

Post a reply to this message

Mike Williams wrote:
>Wasn't it Rune who wrote:
>>Mike Williams wrote:
>>>It's fairly easy to calculate the spline with the right total
>>>length (performing a binary chop on the value I just tweaked above),
>>
>>Could you explain this in greater detail?
>
>I'll post some code that does this to povray.binaries.scene-files.

Thanks a lot Mike!

It works very well and quick too!

Only, I found it was even quicker if you change line 36 to line 40 from
this:

  #if (_ikn_len > ikn_length)
    #declare _ikn_m = _ikn_m * 0.5;  // if spline too long, reduce end
vectors
  #else
    #declare _ikn_m = _ikn_m * 1.5;  // if spline too long, increase end
vectors
  #end

to this:

  #declare _ikn_m = _ikn_m*(ikn_length/_ikn_len);

Then you can easily go down to 0.01% precision and then it's still quicker.

I'll use your method to find the right spline and then Peter Popov's to
equalize the points. :-)

Greetings,

Rune

---
Updated December 22: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Thanks for the reply Kevin!

Mike Williams posted some code in povray.binaries.scene-files that does
about what you describes. It works very well and now I'm going to use it
together with Peter's so that the points get equalized too. :-)

Greetings,

Rune

---
Updated December 22: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Chris Colefax wrote:
>To avoid confusion I think it helps to use the word 'tangent' when you're
>talking about a vector tangential to the curve

Tangent, yes that's the word. I couldn't remember it.

>Now, given the example you posted to .binaries and your description of your
>goal I would say the method you're using (inverse kinematics) is quite
>suitable.

I'll use Mike Williams' + Peter Popov's methods, but now with your
suggestion I'll give my original idea another try as well. I'll then see
which works best.

>To avoid kinking perhaps you could apply an extra constraint to
>each link which checks the angle it forms with the links around it, eg.
>given three sphere centres (P1, P2, and P3) you could calculate the cosine
>of the angle using:
>
>   vdot (vnormalize (P2 - P1), vnormalize (P3 - P2))
>
>To stop the kinking you want this to be as close as possible to -1 (the
>cosine of 180 degrees), so in addition to being pulled by the endpoints and
>tangents and being forced to be separated by a certain distance, the
spheres
>also try to form a straight line (or as close as possible given the other
>constraints).

I understand you so far, i.e. how to find out how much the curve is bended
on a given point.
However, to me the problem is how to straighten out the curve. I mean, I can
see that I want to get the cosine of the angle as close as possible to -1,
but it is how to accomplish this that is the problem.

Has you any ideas as to how to accomplish it?

Greetings,

Rune

---
Updated December 22: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Peter Popov wrote:
>On Tue, 28 Dec 1999 23:33:16 +0100, "Rune" <run### [at] inamecom>
>wrote:
>
>>However, I'm not sure what the difference is between this:
>>
>>>Do this until no force is greater than a certain threshold value
>>
>>...and this:
>>
>>>or even better, the standard deviation of the forces
>>>falls below a certain level (i.e. the spline is equistressed).
>
>The difference is that if you have too many points, the forces between
>them may be great but still equal, which would force the first
>algorithm into an infinite loop, while the second (which looks at the
>deviation) will stop seeing that all forces are virtually equal.

Thanks, I get it now. :-)

I've tested your method and it seems to work fine. I still need to optimize
it though. So far I've just looped the code a certain number of times, but I
want to optimize it so it stops automatically when no more calculations are
needed, like you described.

Greetings,

Rune

---
Updated December 22: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

Rune <run### [at] inamecom> wrote:
> I'll use Mike Williams' + Peter Popov's methods, but now with your
> suggestion I'll give my original idea another try as well. I'll then see
> which works best.

As I mentioned in the previous thread (Optimised curves) cubic splines will
not give you the circular curves you posted in .images, although you may
find you prefer cubic splines anyway!

> I understand you so far, i.e. how to find out how much the curve is bended
> on a given point.
> However, to me the problem is how to straighten out the curve. I mean, I
can
> see that I want to get the cosine of the angle as close as possible to -1,
> but it is how to accomplish this that is the problem.
>
> Has you any ideas as to how to accomplish it?

One way might be to move the third point closer to the line that is formed
by the first and second points, eg. given P1, P2, and P3 (the point to be
moved):

   P3 = P3*W1 + (P2 + P2 - P1)*W2;

Here W1 and W2 are the weights you are giving to the current point versus
the point that would be if there was no bending at all.   They should add to
1, and you could determine the weights using a function of the previously
calculated cosine (C), eg:

   W1 = (1 - C)/2;
   W2 = 1 - W1;

Here a cosine of -1 (180 degrees) gives full weighting to the current point
and zero weighting to the desired point (which are actually one and the same
so the weights don't matter).  A cosine of 1 (0 degrees) gives the
opposite - full weighting to the desired point and none to the current point
(in effect flipping the current point around 180 degrees).  In between, the
closer the cosine is to -1 (180 degrees) the less the point is moved, eg. a
cosine of 0 (90 degrees) gives equal weighting to each point so the new
point is about 45 degrees from the desired point.  Adjusting the way the
weights are calculated will obviously affect the 'unkinking' of the links.

Post a reply to this message