POV-Ray : Newsgroups : povray.general : Help with "programmatically" determining intersection Server Time
31 Oct 2024 19:30:59 EDT (-0400)
  Help with "programmatically" determining intersection (Message 1 to 8 of 8)  
From: Bald Eagle
Subject: Help with "programmatically" determining intersection
Date: 16 Mar 2016 23:10:00
Message: <web.56ea1f7e7eb839c15e7df57c0@news.povray.org>
I have 2 involute curves that I'm "plotting" with spheres as I increase theta in
the following manner:

#declare Z1 = Base * (sin(theta) - theta*cos(theta));
#declare Z2 = -Base * (sin(theta) - theta*cos(theta));  // Opposite side of
involute tooth
sphere{ <X, T1, Z1>, T1 pigment {Blue} rotate -y*Tooth1*AngularSpacing}
sphere{ <X, T1, Z2>, T1 pigment {Blue} rotate -y*Tooth2*AngularSpacing}

Since I'm using a loop to increase theta in discrete increments, I can't test if
the 2 points are coincident because I might have already skipped over the place
where they would be.

I could probably devise a practical method of skipping over this problem and
obtaining the end result, but I'd like to learn how to best handle this issue
and have that one extra coding skill to employ in the future.

I've tried testing to see if the difference of the z components is below a
certain value:

#declare NegInvolute = transform {rotate <0, -AngularSpacing, 0>};
#declare NI_Point = vtransform (<X, T1, Z2>, NegInvolute);
#if ( abs(Z1) - abs(NI_Point.z) < 0.1)
but that seems to highlight every point leading up to the intersection, and if I
witch the position of the terms in the difference, I get all of the points after
the intersection - and it doesn't seem like it as close to or including the
actual intersection point as I'd expect.   And it seems kind of clumsy and
inelegant.

What's the best way to go about determining the intersection of intermittently
plotted curves?


Post a reply to this message

From: Le Forgeron
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 03:07:17
Message: <56ea57a5$1@news.povray.org>
Le 17/03/2016 04:07, Bald Eagle a écrit :
> #declare Z1 = Base * (sin(theta) - theta*cos(theta));
> #declare Z2 = -Base * (sin(theta) - theta*cos(theta));

you are trying to solve Z1 = Z2, i.e. Z1-Z2 = 0

Base * (sin(theta) - theta*cos(theta)) + Base * (sin(theta) - 
theta*cos(theta)) = 0

2 * Base * (sin(theta) - theta*cos(theta)) = 0

Base is constant, not interesting.

Remains (sin(theta) - theta*cos(theta)) = 0

sin(theta) = theta*cos(theta)

Obvious (as in math) first solution is theta = 0.

Then you can use the Internet

http://www.wolframalpha.com/input/?i=sin+x+-+x+cos+x+%3D+0

x ~~ -14.0661939128315...

x ~~ ±10.9041216594289...

x ~~ ±7.72525183693771...

x ~~ ±4.49340945790906...

x = 0

At least 8 intersections, but only one if you restrict yourself to -pi , 
+pi.

Back to your original problem: you should detect the change of sign of 
Z1-Z2, not its small absolute value. You need a memory of the sign at 
the previous point, and compare with the new sign for the new point.

And possibly handling a 3 states sign: <0, ==0, >0

You crossed the intersection when going from <0 to >0 or vice-versa
You found the intersection when new sign == 0


Post a reply to this message

From: scott
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 04:20:26
Message: <56ea68ca$1@news.povray.org>
On 17/03/2016 07:07, Le_Forgeron wrote:
> Le 17/03/2016 04:07, Bald Eagle a écrit :
>> #declare Z1 = Base * (sin(theta) - theta*cos(theta));
>> #declare Z2 = -Base * (sin(theta) - theta*cos(theta));
>
> you are trying to solve Z1 = Z2, i.e. Z1-Z2 = 0

Wait... the two spheres are rotated different amounts:

sphere{ <X, T1, Z1>, T1 pigment {Blue} rotate -y*Tooth1*AngularSpacing}
sphere{ <X, T1, Z2>, T1 pigment {Blue} rotate -y*Tooth2*AngularSpacing}


Post a reply to this message

From: Bald Eagle
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 10:15:00
Message: <web.56eabacf4c69d6165e7df57c0@news.povray.org>
scott <sco### [at] scottcom> wrote:


> Wait... the two spheres are rotated different amounts:
>
> sphere{ <X, T1, Z1>, T1 pigment {Blue} rotate -y*Tooth1*AngularSpacing}
> sphere{ <X, T1, Z2>, T1 pigment {Blue} rotate -y*Tooth2*AngularSpacing}

Correct.   Because if you plot the involutes, one curves up, and the other
curves down.  I already (after 40 minutes worth of trigonometric algebra)
established where they cross the base circle, and then after some more searching
and some luck, did the same with the addendum circle.

The second sphere gets rotated by Tooth2, which is just Tooth1+0.5.  Therefore
it gets rotated above/past the other involute and so as it curls own and the
first involute curls up, they will eventually intersect.   As Jerome pointed
out, since these are "transcendental functions" - they will have an infinite
number of intersections, but I'm only interested at the first (at the moment
;).

I do think that his suggestion of "tracking" the curves and determining the
intersection from a change of sign will work - but that looks more "practical"
than mathematical and elegant.   But maybe that's the reality of how it's done.
 I'll play with it some and see where I get, but that could take all day
again...


Post a reply to this message

From: scott
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 11:16:31
Message: <56eaca4f$1@news.povray.org>
> Correct.   Because if you plot the involutes, one curves up, and the other
> curves down.  I already (after 40 minutes worth of trigonometric algebra)
> established where they cross the base circle, and then after some more searching
> and some luck, did the same with the addendum circle.

I'm surprised this is not documented/solved somewhere else already. 
You're surely not the only one wanting to design gears. Saying that 
though, most CAD software will automatically do CSG on the intersecting 
teeth, so you wouldn't need to worry so much where the exact point was, 
so long as you went past it for each tooth.

> The second sphere gets rotated by Tooth2, which is just Tooth1+0.5.  Therefore
> it gets rotated above/past the other involute and so as it curls own and the
> first involute curls up, they will eventually intersect.   As Jerome pointed
> out, since these are "transcendental functions" - they will have an infinite
> number of intersections, but I'm only interested at the first (at the moment
> ;).
>
> I do think that his suggestion of "tracking" the curves and determining the
> intersection from a change of sign will work -

I don't think that will work because your curves are moving in 2 
dimensions. What you'd need to do is check if the line between the 
current point and the previous point of curve 1 *crosses* the line 
between the current point and the previous point of curve 2.

> but that looks more "practical"
> than mathematical and elegant.   But maybe that's the reality of how it's done.
>   I'll play with it some and see where I get, but that could take all day
> again...

I prefer the "practical" approach, because it will work with (almost) 
any function or formula with little modification. The mathematical 
approach, whilst neat, needs recalculating every time you tweak the 
curve, and just may not be possible to do in some situations (or more 
likely, is beyond my skill to do the algebra!).


Post a reply to this message

From: Bald Eagle
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 12:10:01
Message: <web.56ead5c84c69d6165e7df57c0@news.povray.org>
scott <sco### [at] scottcom> wrote:

> I'm surprised this is not documented/solved somewhere else already.
> You're surely not the only one wanting to design gears.

Yes and no.   "documented / solved" - yes, surely.  Freely available on the web
and not buried in a math or engineering textbook - harder to find.

I mean, check this out:
http://mathhelpforum.com/geometry/136011-circle-involute-solving-y-any-given-x.html

"It follows from the given equations for x and y that  x^2+y^2 = a^2(1+t^2)."

Right.   After you do:


Equations for an involute
 x = a(cosq + qsinq)
 y = a(sinq - qcosq)

Equation for a circle
x2 + y2 = r2

When the involute intersects the circle, the evaluated equations are equal

a2(cosq + qsinq)2 +  a2(sinq - qcosq)2 = r2

a2(cos2q + 2qcosqsinq + q2sin2q)  +  a2(sin2q + 2qcosqsinq - q2cos2q)2  = r2

a2(cos2q + 2qcosqsinq + q2sin2q + sin2q - 2qcosqsinq + q2cos2q)2  = r2

a2(cos2q + q2sin2q + sin2q + q2cos2q)2  = r2

a2(cos2q + q2sin2q + sin2q + q2(1 - sin2q))2  = r2

a2(cos2q + q2sin2q + sin2q + q2 - q2sin2q)2  = r2

a2(cos2q + sin2q + q2)2  = r2

a2(1 - sin2q + sin2q + q2)2  = r2

a2(1 + q2)2  = r2      (1 + q2)2  = r2 / a2

a sqrt [(1 + q2)]  = r     1 + q2  = sqrt [ r2 / a2 ]







(The 2's are all superscripted...)



> I don't think that will work because your curves are moving in 2
> dimensions. What you'd need to do is check if the line between the
> current point and the previous point of curve 1 *crosses* the line
> between the current point and the previous point of curve 2.

I read that 5 times and finally got ya.
That _sounds_ good - but:  HOW do we do that "checking"?

Curves moving in 2 dimensions doesn't seem like a big deal - that's 99% of what
most HS math / geometry is anyway, right?  "Find the intersection of 2 lines..."
   These lines just happen to be curves.  So long as theta < 2pi, there ought to
only be one intersection.

I'm leaning towards the mathematical approach, since then I can test for values
of x or z or theta or something else rather than a cluster of error-prone code.




At this point, it looks like the determination of the curves crossing the
Outside Circle doesn't work either.
http://web.mit.edu/harishm/www/papers/involuteEWC.pdf
Page 4, equation 11.

I overlay the involute trace with yellow if theta is _greater_ than that
calculated value, and the beginning of the yellow is OFF.

I'll post an image in binaries, and code in the event that you'd like to play
along on this one  :)


Post a reply to this message

From: Le Forgeron
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 12:49:19
Message: <56eae00f@news.povray.org>
Le 17/03/2016 17:05, Bald Eagle a écrit :
> 
> 
>> > I don't think that will work because your curves are moving in 2
>> > dimensions. What you'd need to do is check if the line between the
>> > current point and the previous point of curve 1 *crosses* the line
>> > between the current point and the previous point of curve 2.
> I read that 5 times and finally got ya.
> That _sounds_ good - but:  HOW do we do that "checking"?

if you have 2 pair of points, making 2 segments (forget for the time being a curve
between the points),
you can check if the segments intersect with a bit of math (ah, again).

1. the points of second segment must be on each side of the line defined by the first
segment.

( a simple matter of having the line equation ax+by+c = 0 for that line, then the sign
of ax+by+c for the P3 and P4 must be opposite, aka
 f(P3) * f(P4) < 0

you can also check if P3 or P4 is on the line : f(P3) * f(P4) == 0
)

2. repeat previous check by swapping the pairs.

3. if both previous checks are successful, you have asserted that each segment cut the
line of the other pair.
The demonstration that with such situation the two segments do intersect each other,
is not too complex (some would state obvious,
but obvious in math might need a few pages).

Whatever, you have your above check.

Hardest part: from 2 distinct points, compute the 3 coefficients of the equation of
their line.


Post a reply to this message

From: clipka
Subject: Re: Help with "programmatically" determining intersection
Date: 17 Mar 2016 17:20:50
Message: <56eb1fb2$1@news.povray.org>
Am 17.03.2016 um 15:10 schrieb Bald Eagle:

> I do think that his suggestion of "tracking" the curves and determining the
> intersection from a change of sign will work - but that looks more "practical"
> than mathematical and elegant.   But maybe that's the reality of how it's done.

That's numerical mathematics for you.

The so-called bisection method is a well-accepted approach to solve
equations numerical when an analytical approach is not feasible, and has
been around for centuries.


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.