Menu
▾
▴
gdalgorithms-list
|
From: metanet s. <met...@ya...> - 2006-03-11 21:51:22
|
hi, Hopefully someone can point me towards some good references/theory.. moving-segment tests came up in the context of Carmageddon a while ago (I think), but searching the archives hasn't turned anything up. My current "ad-hoc" algorithm is: given linesegment with endpoints A,B and endpoint velocities vA,vB, and point C with velocity vC: 1) find the velocity V of C relative to segment A->B** 2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V) **for step (1), I find the point on A->B closest to C, and use the parametric description of this point to blend vA and vB together to generate a single velocity for the segment (which is subtracted from vC to get C's velocity from A-B's frame of reference). Step 1 seems very approximate/hacky, since you can use any combination of current or future positions, each of which will give you a different result: -point on A->B closest to C -point on A->B closest to (C+vC) -point on (A+vA)->(B+vB) closest to C -point on (A+vA)->(B+vB) closest to (C+vC) ..there's no obvious "best"/most correct combination, which seems to indicate that the "real" solution to this problem is probably not so neat or linear, involving root finding or closest-point-of-approach calculation. Anyway, any tips, suggestions or references would be great, I'd really like to know of any more accurate (or at least less spontaneously-invented) approached. I should mention that I only need a boolean result, no time/point of intersection. thanks, raigan --------------------------------- Enrich your life at Yahoo! Canada Finance |
|
From: Robert D. <bli...@go...> - 2006-03-13 11:52:02
|
The velocity of C with respect to AB is time dependent, because the closest point on the line is also time dependent. (Note that the surface swept by the line AB can be curved or flat, and even if it is flat it still doesn't guarantee a linear solution) Just to add to the fun, you have to consider the case when the closest point on the line is one of the end points, which changes everything. I would suggest that the most reliable way to do this would be to stick with your "closest point" approach, use that to find an instantaneous answer to the relative velocity and then move forward to a point in time that is only part way towards the potential collision point. Then you can re-evaluate the closest point and the relative velocity, and try again. I would imagine in most cases you only need to know if collision in a certain (short) time frame is going to happen, in which case the vast majority of cases would probably get a quick out because there is no chance of collision in that time frame. The remainder would just need a few iterations to convince you that collision was inevitable - if you get to the point where you are only millimetres from collision then treating it as if it has happened is probably quite safe. Cheers Robert _____ From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software Sent: 11 March 2006 21:51 To: gda...@li... Subject: [Algorithms] Moving Segment vs Moving Point Intersection (2D) hi, Hopefully someone can point me towards some good references/theory.. moving-segment tests came up in the context of Carmageddon a while ago (I think), but searching the archives hasn't turned anything up. My current "ad-hoc" algorithm is: given linesegment with endpoints A,B and endpoint velocities vA,vB, and point C with velocity vC: 1) find the velocity V of C relative to segment A->B** 2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V) **for step (1), I find the point on A->B closest to C, and use the parametric description of this point to blend vA and vB together to generate a single velocity for the segment (which is subtracted from vC to get C's velocity from A-B's frame of reference). Step 1 seems very approximate/hacky, since you can use any combination of current or future positions, each of which will give you a different result: -point on A->B closest to C -point on A->B closest to (C+vC) -point on (A+vA)->(B+vB) closest to C -point on (A+vA)->(B+vB) closest to (C+vC) ..there's no obvious "best"/most correct combination, which seems to indicate that the "real" solution to this problem is probably not so neat or linear, involving root finding or closest-point-of-approach calculation. Anyway, any tips, suggestions or references would be great, I'd really like to know of any more accurate (or at least less spontaneously-invented) approached. I should mention that I only need a boolean result, no time/point of intersection. thanks, raigan _____ Enrich your life at <http://finance.yahoo.ca> Yahoo! Canada Finance |
|
From: Laurent A. <lau...@su...> - 2006-03-13 15:10:44
|
I certainly missed something here, because it looks quite easy to me, =
with
this approximation:
Your moving segment will describe, between two frames, either a 4 sided
convex polygon, either two triangles (4 sided concave polygon). Your =
moving
point will describe a segment.
You test quite easily if you=92re in case 1 (quad), or in case 2 (two
triangles), and then perform a quad / segment collision test, or two
triangles / segment test.
=20
This will approximate to a per frame / linear velocity, but you can =
solve it
easily, and if you have a decent frame rate, it works well.
Then you can upgrade to a better test with parametric equation only on =
the
point, and keep the case 1 / case 2 tests for the moving segment.
=20
At least, it=92s easy to implement and works straightforward. It depends =
how
you actually intend to use the results =85
=20
Laurent
=20
_____ =20
De : gda...@li...
[mailto:gda...@li...] De la part de =
Robert
Dibley
Envoy=E9 : lundi 13 mars 2006 12:52
=C0 : gda...@li...
Objet : RE: [Algorithms] Moving Segment vs Moving Point Intersection =
(2D)
=20
The velocity of C with respect to AB is time dependent, because the =
closest
point on the line is also time dependent.
(Note that the surface swept by the line AB can be curved or flat, and =
even
if it is flat it still doesn=92t guarantee a linear solution)
=20
Just to add to the fun, you have to consider the case when the closest =
point
on the line is one of the end points, which changes everything.
=20
I would suggest that the most reliable way to do this would be to stick =
with
your =93closest point=94 approach, use that to find an instantaneous =
answer to
the relative velocity and then move forward to a point in time that is =
only
part way towards the potential collision point. Then you can =
re-evaluate
the closest point and the relative velocity, and try again.
I would imagine in most cases you only need to know if collision in a
certain (short) time frame is going to happen, in which case the vast
majority of cases would probably get a quick out because there is no =
chance
of collision in that time frame. The remainder would just need a few
iterations to convince you that collision was inevitable =96 if you get =
to the
point where you are only millimetres from collision then treating it as =
if
it has happened is probably quite safe.
=20
Cheers
=20
Robert
=20
=20
_____ =20
From: gda...@li...
[mailto:gda...@li...] On Behalf Of =
metanet
software
Sent: 11 March 2006 21:51
To: gda...@li...
Subject: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
=20
hi,
Hopefully someone can point me towards some good references/theory..
moving-segment tests came up in the context of Carmageddon a while ago =
(I
think), but searching the archives hasn't turned anything up.
My current "ad-hoc" algorithm is:
given linesegment with endpoints A,B and endpoint velocities vA,vB, and
point C with velocity vC:
1) find the velocity V of C relative to segment A->B**
2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V)
**for step (1), I find the point on A->B closest to C, and use the
parametric description of this point to blend vA and vB together to =
generate
a single velocity for the segment (which is subtracted from vC to get =
C's
velocity from A-B's frame of reference).
Step 1 seems very approximate/hacky, since you can use any combination =
of
current or future positions, each of which will give you a different =
result:
-point on A->B closest to C
-point on A->B closest to (C+vC)
-point on (A+vA)->(B+vB) closest to C
-point on (A+vA)->(B+vB) closest to (C+vC)
..there's no obvious "best"/most correct combination, which seems to
indicate that the "real" solution to this problem is probably not so =
neat or
linear, involving root finding or closest-point-of-approach calculation.
Anyway, any tips, suggestions or references would be great, I'd really =
like
to know of any more accurate (or at least less spontaneously-invented)
approached.
I should mention that I only need a boolean result, no time/point of
intersection.
thanks,
raigan
_____ =20
Enrich your life at <http://finance.yahoo.ca> Yahoo! Canada Finance
|
|
From: Robert D. <bli...@go...> - 2006-03-13 15:47:47
|
Sorry, I didn=92t notice the (2D) in the subject =96 I was thinking in =
3D.
Oops.
=20
=20
_____ =20
From: gda...@li...
[mailto:gda...@li...] On Behalf Of =
Laurent
Auneau
Sent: 13 March 2006 15:11
To: gda...@li...
Subject: RE: [Algorithms] Moving Segment vs Moving Point Intersection =
(2D)
=20
I certainly missed something here, because it looks quite easy to me, =
with
this approximation:
Your moving segment will describe, between two frames, either a 4 sided
convex polygon, either two triangles (4 sided concave polygon). Your =
moving
point will describe a segment.
You test quite easily if you=92re in case 1 (quad), or in case 2 (two
triangles), and then perform a quad / segment collision test, or two
triangles / segment test.
=20
This will approximate to a per frame / linear velocity, but you can =
solve it
easily, and if you have a decent frame rate, it works well.
Then you can upgrade to a better test with parametric equation only on =
the
point, and keep the case 1 / case 2 tests for the moving segment.
=20
At least, it=92s easy to implement and works straightforward. It depends =
how
you actually intend to use the results =85
=20
Laurent
=20
_____ =20
De : gda...@li...
[mailto:gda...@li...] De la part de =
Robert
Dibley
Envoy=E9 : lundi 13 mars 2006 12:52
=C0 : gda...@li...
Objet : RE: [Algorithms] Moving Segment vs Moving Point Intersection =
(2D)
=20
The velocity of C with respect to AB is time dependent, because the =
closest
point on the line is also time dependent.
(Note that the surface swept by the line AB can be curved or flat, and =
even
if it is flat it still doesn=92t guarantee a linear solution)
=20
Just to add to the fun, you have to consider the case when the closest =
point
on the line is one of the end points, which changes everything.
=20
I would suggest that the most reliable way to do this would be to stick =
with
your =93closest point=94 approach, use that to find an instantaneous =
answer to
the relative velocity and then move forward to a point in time that is =
only
part way towards the potential collision point. Then you can =
re-evaluate
the closest point and the relative velocity, and try again.
I would imagine in most cases you only need to know if collision in a
certain (short) time frame is going to happen, in which case the vast
majority of cases would probably get a quick out because there is no =
chance
of collision in that time frame. The remainder would just need a few
iterations to convince you that collision was inevitable =96 if you get =
to the
point where you are only millimetres from collision then treating it as =
if
it has happened is probably quite safe.
=20
Cheers
=20
Robert
=20
=20
_____ =20
From: gda...@li...
[mailto:gda...@li...] On Behalf Of =
metanet
software
Sent: 11 March 2006 21:51
To: gda...@li...
Subject: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
=20
hi,
Hopefully someone can point me towards some good references/theory..
moving-segment tests came up in the context of Carmageddon a while ago =
(I
think), but searching the archives hasn't turned anything up.
My current "ad-hoc" algorithm is:
given linesegment with endpoints A,B and endpoint velocities vA,vB, and
point C with velocity vC:
1) find the velocity V of C relative to segment A->B**
2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V)
**for step (1), I find the point on A->B closest to C, and use the
parametric description of this point to blend vA and vB together to =
generate
a single velocity for the segment (which is subtracted from vC to get =
C's
velocity from A-B's frame of reference).
Step 1 seems very approximate/hacky, since you can use any combination =
of
current or future positions, each of which will give you a different =
result:
-point on A->B closest to C
-point on A->B closest to (C+vC)
-point on (A+vA)->(B+vB) closest to C
-point on (A+vA)->(B+vB) closest to (C+vC)
..there's no obvious "best"/most correct combination, which seems to
indicate that the "real" solution to this problem is probably not so =
neat or
linear, involving root finding or closest-point-of-approach calculation.
Anyway, any tips, suggestions or references would be great, I'd really =
like
to know of any more accurate (or at least less spontaneously-invented)
approached.
I should mention that I only need a boolean result, no time/point of
intersection.
thanks,
raigan
_____ =20
Enrich your life at <http://finance.yahoo.ca> Yahoo! Canada Finance
|
|
From: metanet s. <met...@ya...> - 2006-03-13 15:52:49
|
hi,
thanks to everyone who answered; i got this working yesterday, using the "decompose into triangles" approach.
it feels a bit hacky, since it says "if the paths of motion of the two objects overlap, then the objects collide".. which is far from true.
however, it's working well, and it doesn't look wrong -- i suspect because the more obvious bad-looking cases are high-velocity, making things hard to notice accurately ;)
raigan
Laurent Auneau <lau...@su...> wrote: v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} st1\:*{behavior:url(#default#ieooui) } I certainly missed something here, because it looks quite easy to me, with this approximation:
Your moving segment will describe, between two frames, either a 4 sided convex polygon, either two triangles (4 sided concave polygon). Your moving point will describe a segment.
You test quite easily if youre in case 1 (quad), or in case 2 (two triangles), and then perform a quad / segment collision test, or two triangles / segment test.
This will approximate to a per frame / linear velocity, but you can solve it easily, and if you have a decent frame rate, it works well.
Then you can upgrade to a better test with parametric equation only on the point, and keep the case 1 / case 2 tests for the moving segment.
At least, its easy to implement and works straightforward. It depends how you actually intend to use the results
Laurent
---------------------------------
De : gda...@li... [mailto:gda...@li...] De la part de Robert Dibley
Envoyé : lundi 13 mars 2006 12:52
À : gda...@li...
Objet : RE: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
The velocity of C with respect to AB is time dependent, because the closest point on the line is also time dependent.
(Note that the surface swept by the line AB can be curved or flat, and even if it is flat it still doesnt guarantee a linear solution)
Just to add to the fun, you have to consider the case when the closest point on the line is one of the end points, which changes everything.
I would suggest that the most reliable way to do this would be to stick with your closest point approach, use that to find an instantaneous answer to the relative velocity and then move forward to a point in time that is only part way towards the potential collision point. Then you can re-evaluate the closest point and the relative velocity, and try again.
I would imagine in most cases you only need to know if collision in a certain (short) time frame is going to happen, in which case the vast majority of cases would probably get a quick out because there is no chance of collision in that time frame. The remainder would just need a few iterations to convince you that collision was inevitable if you get to the point where you are only millimetres from collision then treating it as if it has happened is probably quite safe.
Cheers
Robert
---------------------------------
From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software
Sent: 11 March 2006 21:51
To: gda...@li...
Subject: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
hi,
Hopefully someone can point me towards some good references/theory.. moving-segment tests came up in the context of Carmageddon a while ago (I think), but searching the archives hasn't turned anything up.
My current "ad-hoc" algorithm is:
given linesegment with endpoints A,B and endpoint velocities vA,vB, and point C with velocity vC:
1) find the velocity V of C relative to segment A->B**
2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V)
**for step (1), I find the point on A->B closest to C, and use the parametric description of this point to blend vA and vB together to generate a single velocity for the segment (which is subtracted from vC to get C's velocity from A-B's frame of reference).
Step 1 seems very approximate/hacky, since you can use any combination of current or future positions, each of which will give you a different result:
-point on A->B closest to C
-point on A->B closest to (C+vC)
-point on (A+vA)->(B+vB) closest to C
-point on (A+vA)->(B+vB) closest to (C+vC)
..there's no obvious "best"/most correct combination, which seems to indicate that the "real" solution to this problem is probably not so neat or linear, involving root finding or closest-point-of-approach calculation.
Anyway, any tips, suggestions or references would be great, I'd really like to know of any more accurate (or at least less spontaneously-invented) approached.
I should mention that I only need a boolean result, no time/point of intersection.
thanks,
raigan
---------------------------------
Enrich your life at Yahoo! Canada Finance
---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos |
|
From: <chr...@pl...> - 2006-03-13 18:35:23
|
> given linesegment with endpoints A,B and endpoint velocities vA,vB, > and point C with velocity vC [determine if intersection occurs] > > I should mention that I only need a boolean result, no time/point of > intersection. In that you're working in 2D and are only interested in the boolean result, this is pretty easy (3D or non-boolean results would make it much more complicated). As others noted, the movement of segment AB will form a (possibly concave or self-intersecting) quad in the plane. However, rather than testing the moving point against this quad, the right approach is to work in the space of the moving point C. C then becomes stationary and we turn the problem into that of determining if C lies inside the quad Q determined by the four points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. To correctly determine containment in Q you would have to determine which of three cases you have: 1. Q is convex 2. Q is concave 3. Q is self-intersecting The first case is straightforward. C lies inside Q if C is consistently to the left or right of all segments Q1Q2, Q2Q3, Q3Q4, and Q4Q1. The second case corresponds to Q being a dart (Star Trek badge). Split Q on the diagonal to form two triangles and test C for containment in either triangle. For the third case, compute the point where the quad self- intersects and form two triangles extending from that point and test C for containment in the triangles. Christer Ericson http://realtimecollisiondetection.net/ |
|
From: metanet s. <met...@ya...> - 2006-03-14 01:51:20
|
hey. thanks! this is great: a real/accurate solution, instead of "perfectly provided the movement of each point is vert small".. _and_ i can reuse all the decompose-quad-into-triangles code from my (horribly approximate) lineseg-vs-quad test ;) i can't believe i tried it the other way around (testing the moving point from the point of view of a static lineseg) and not this way. doh! raigan chr...@pl... wrote: > given linesegment with endpoints A,B and endpoint velocities vA,vB, > and point C with velocity vC [determine if intersection occurs] > > I should mention that I only need a boolean result, no time/point of > intersection. In that you're working in 2D and are only interested in the boolean result, this is pretty easy (3D or non-boolean results would make it much more complicated). As others noted, the movement of segment AB will form a (possibly concave or self-intersecting) quad in the plane. However, rather than testing the moving point against this quad, the right approach is to work in the space of the moving point C. C then becomes stationary and we turn the problem into that of determining if C lies inside the quad Q determined by the four points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. To correctly determine containment in Q you would have to determine which of three cases you have: 1. Q is convex 2. Q is concave 3. Q is self-intersecting The first case is straightforward. C lies inside Q if C is consistently to the left or right of all segments Q1Q2, Q2Q3, Q3Q4, and Q4Q1. The second case corresponds to Q being a dart (Star Trek badge). Split Q on the diagonal to form two triangles and test C for containment in either triangle. For the third case, compute the point where the quad self- intersects and form two triangles extending from that point and test C for containment in the triangles. Christer Ericson http://realtimecollisiondetection.net/ ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 --------------------------------- Enrich your life at Yahoo! Canada Finance |
|
From: metanet s. <met...@ya...> - 2006-03-31 18:25:14
|
It turns out that determining the _time_ of collision would be very useful; I've tried to figure this out in a few ways, however I always end up with one too many unknowns (or one too few equations). I suppose this is what Christer meant by "much more complicated" ;) If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must exist a unique line L which passes through C and which intersects the lines L1 = Q1 + t(Q4-Q1) and L2 = Q2 + t(Q3-Q2) at the same value of t. It seems like there should be a very straightforward solution, since there can only be a single direction for L which intersects L1 and L2 at the same t parameter, however.. I haven't managed to find it. Substituting the parametric description of the intersection points and rearranging always seems to produce an equation of the form x + y + xy = 0.. which can't be solved without another equation. Of course, it's also possible that I made some mistakes while rearranging things.. A related problem is finding the point of intersection; once we know the time of intersection t it is trivial to determine the point of intersection (at time t, C is colinear with the segment, so it's easy to find the parametric/barycentric coord of C in terms of the segment endpoints). Similarly, given this parametric coord, it would be trivial to determine the time of intersection. However, I know neither. Does anyone have any suggestions on how to approach this problem? It seems irritatingly simple. thanks for your time, raigan chr...@pl... wrote: > given linesegment with endpoints A,B and endpoint velocities vA,vB, > and point C with velocity vC [determine if intersection occurs] > > I should mention that I only need a boolean result, no time/point of > intersection. In that you're working in 2D and are only interested in the boolean result, this is pretty easy (3D or non-boolean results would make it much more complicated). As others noted, the movement of segment AB will form a (possibly concave or self-intersecting) quad in the plane. However, rather than testing the moving point against this quad, the right approach is to work in the space of the moving point C. C then becomes stationary and we turn the problem into that of determining if C lies inside the quad Q determined by the four points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. To correctly determine containment in Q you would have to determine which of three cases you have: 1. Q is convex 2. Q is concave 3. Q is self-intersecting The first case is straightforward. C lies inside Q if C is consistently to the left or right of all segments Q1Q2, Q2Q3, Q3Q4, and Q4Q1. The second case corresponds to Q being a dart (Star Trek badge). Split Q on the diagonal to form two triangles and test C for containment in either triangle. For the third case, compute the point where the quad self- intersects and form two triangles extending from that point and test C for containment in the triangles. Christer Ericson http://realtimecollisiondetection.net/ ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 --------------------------------- Share your photos with the people who matter at Yahoo! Canada Photos |
|
From: Jonathan B. <jo...@nu...> - 2006-03-31 19:46:11
|
This is pretty simple... There are 2 tricks to simplify it. The first is, (assuming that things are moving linearly inside a timestep), consider the point to be stationary, and just subtract its velocity from the endpoints of the segment. This simplifies the equations. The second is, instead of trying to test against the line segment, you test against the whole line. The point can only cross the line once during the timestep (due to linearity). So if it crosses, then you find the crossing point, and then determine whether that was inside the segment or outside (which is easy). Let's call the endpoints of the line A and B. They are really functions of t i.e. A(t) and B(t) but to keep the equations simple we will omit that.... The point you are testing is p. When p crosses the line, (p - A) dot (B - A)perp = 0. [Here dot is the 2d dot product and perp is the 2D operator that rotates the vector 90 degrees, i.e. Vperp = (-Vy, Vx)]. The perp and the dot can be combined, so this is just: (p - A) perp_dot (B - A) = 0. So you just want to solve the equation above for t (which remember is implicit in the A and B). This is pretty trivial but the exact detail depends on your game. [I'm not sure if you are testing a point against, say, a rotating square or what.] Suppose this segment is some piece of an n-gon and you know the positions of A and B both at the beginning and end of the timestep. So we will call them A0 and A1 = A0 + delta A, similarly for B. Then A(t) = A0 + t delta A And you just plug that in for A and B in the equation above and solve it. So you get: (p - A0 - t delta A) perp_dot (B0 - A0 + t(delta B - delta A)) = 0 which is pretty easy to solve, and there you go. If you have any questions about this feel free to drop me an email... this is maybe not the most lucid explanation. metanet software wrote: > > It turns out that determining the _time_ of collision would be very > useful; I've tried to figure this out in a few ways, however I always > end up with one too many unknowns (or one too few equations). I > suppose this is what Christer meant by "much more complicated" ;) > > > If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must > exist a unique line L which passes through C and which intersects the > lines L1 = Q1 + t(Q4-Q1) and L2 = Q2 + t(Q3-Q2) at the same value of t. > > It seems like there should be a very straightforward solution, since > there can only be a single direction for L which intersects L1 and L2 > at the same t parameter, however.. I haven't managed to find it. > Substituting the parametric description of the intersection points and > rearranging always seems to produce an equation of the form x + y + xy > = 0.. which can't be solved without another equation. Of course, it's > also possible that I made some mistakes while rearranging things.. > > > A related problem is finding the point of intersection; once we know > the time of intersection t it is trivial to determine the point of > intersection (at time t, C is colinear with the segment, so it's easy > to find the parametric/barycentric coord of C in terms of the segment > endpoints). Similarly, given this parametric coord, it would be > trivial to determine the time of intersection. However, I know neither. > > Does anyone have any suggestions on how to approach this problem? It > seems irritatingly simple. > > thanks for your time, > raigan > > > */chr...@pl.../* wrote: > > > > > given linesegment with endpoints A,B and endpoint velocities vA,vB, > > and point C with velocity vC [determine if intersection occurs] > > > > I should mention that I only need a boolean result, no time/point of > > intersection. > > In that you're working in 2D and are only interested in the boolean > result, this is pretty easy (3D or non-boolean results would make > it much more complicated). > > As others noted, the movement of segment AB will form a (possibly > concave or self-intersecting) quad in the plane. However, rather > than testing the moving point against this quad, the right approach > is to work in the space of the moving point C. > > C then becomes stationary and we turn the problem into that of > determining if C lies inside the quad Q determined by the four > points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. > > To correctly determine containment in Q you would have to determine > which of three cases you have: > > 1. Q is convex > 2. Q is concave > 3. Q is self-intersecting > > The first case is straightforward. C lies inside Q if C is > consistently to the left or right of all segments Q1Q2, Q2Q3, > Q3Q4, and Q4Q1. > > The second case corresponds to Q being a dart (Star Trek badge). > Split Q on the diagonal to form two triangles and test C for > containment in either triangle. > > For the third case, compute the point where the quad self- > intersects and form two triangles extending from that point and > test C for containment in the triangles. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > > ------------------------------------------------------- > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > ------------------------------------------------------------------------ > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca> |
|
From: Jonathan B. <jo...@nu...> - 2006-03-31 19:46:30
|
This is pretty simple... There are 2 tricks to simplify it. The first is, (assuming that things are moving linearly inside a timestep), consider the point to be stationary, and just subtract its velocity from the endpoints of the segment. This simplifies the equations. The second is, instead of trying to test against the line segment, you test against the whole line. The point can only cross the line once during the timestep (due to linearity). So if it crosses, then you find the crossing point, and then determine whether that was inside the segment or outside (which is easy). Let's call the endpoints of the line A and B. They are really functions of t i.e. A(t) and B(t) but to keep the equations simple we will omit that.... The point you are testing is p. When p crosses the line, (p - A) dot (B - A)perp = 0. [Here dot is the 2d dot product and perp is the 2D operator that rotates the vector 90 degrees, i.e. Vperp = (-Vy, Vx)]. The perp and the dot can be combined, so this is just: (p - A) perp_dot (B - A) = 0. So you just want to solve the equation above for t (which remember is implicit in the A and B). This is pretty trivial but the exact detail depends on your game. [I'm not sure if you are testing a point against, say, a rotating square or what.] Suppose this segment is some piece of an n-gon and you know the positions of A and B both at the beginning and end of the timestep. So we will call them A0 and A1 = A0 + delta A, similarly for B. Then A(t) = A0 + t delta A And you just plug that in for A and B in the equation above and solve it. So you get: (p - A0 - t delta A) perp_dot (B0 - A0 + t(delta B - delta A)) = 0 which is pretty easy to solve, and there you go. If you have any questions about this feel free to drop me an email... this is maybe not the most lucid explanation. metanet software wrote: > > It turns out that determining the _time_ of collision would be very > useful; I've tried to figure this out in a few ways, however I always > end up with one too many unknowns (or one too few equations). I > suppose this is what Christer meant by "much more complicated" ;) > > > If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must > exist a unique line L which passes through C and which intersects the > lines L1 = Q1 + t(Q4-Q1) and L2 = Q2 + t(Q3-Q2) at the same value of t. > > It seems like there should be a very straightforward solution, since > there can only be a single direction for L which intersects L1 and L2 > at the same t parameter, however.. I haven't managed to find it. > Substituting the parametric description of the intersection points and > rearranging always seems to produce an equation of the form x + y + xy > = 0.. which can't be solved without another equation. Of course, it's > also possible that I made some mistakes while rearranging things.. > > > A related problem is finding the point of intersection; once we know > the time of intersection t it is trivial to determine the point of > intersection (at time t, C is colinear with the segment, so it's easy > to find the parametric/barycentric coord of C in terms of the segment > endpoints). Similarly, given this parametric coord, it would be > trivial to determine the time of intersection. However, I know neither. > > Does anyone have any suggestions on how to approach this problem? It > seems irritatingly simple. > > thanks for your time, > raigan > > > */chr...@pl.../* wrote: > > > > > given linesegment with endpoints A,B and endpoint velocities vA,vB, > > and point C with velocity vC [determine if intersection occurs] > > > > I should mention that I only need a boolean result, no time/point of > > intersection. > > In that you're working in 2D and are only interested in the boolean > result, this is pretty easy (3D or non-boolean results would make > it much more complicated). > > As others noted, the movement of segment AB will form a (possibly > concave or self-intersecting) quad in the plane. However, rather > than testing the moving point against this quad, the right approach > is to work in the space of the moving point C. > > C then becomes stationary and we turn the problem into that of > determining if C lies inside the quad Q determined by the four > points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. > > To correctly determine containment in Q you would have to determine > which of three cases you have: > > 1. Q is convex > 2. Q is concave > 3. Q is self-intersecting > > The first case is straightforward. C lies inside Q if C is > consistently to the left or right of all segments Q1Q2, Q2Q3, > Q3Q4, and Q4Q1. > > The second case corresponds to Q being a dart (Star Trek badge). > Split Q on the diagonal to form two triangles and test C for > containment in either triangle. > > For the third case, compute the point where the quad self- > intersects and form two triangles extending from that point and > test C for containment in the triangles. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > > ------------------------------------------------------- > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > ------------------------------------------------------------------------ > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca> |
|
From: Jonathan B. <jo...@nu...> - 2006-03-31 19:57:10
|
Jonathan Blow wrote: > > The first is, (assuming that things are moving linearly inside a > timestep), consider the point to be stationary, and just subtract its > velocity from the endpoints of the segment. This simplifies the > equations. As I look at the final equation, I realize you don't even need to bother with this, so ignore that part. You can just have a p(t) in the final equation I put down, and expand that into p0 + t delta p, and the equation is still just as easy to solve. Sorry about the extra confusion. So the only trick is testing against the full line, not just the segment. |
|
From: Dave M. <da...@ra...> - 2006-04-01 16:38:32
|
Jonathan Blow wrote: > test against the whole line. The point can only cross the line once > during the timestep (due to linearity). So if it crosses, then you find Small niggle: you get a quadratic equation in t not a linear one, right? There are cases where you get 2 crossings. |
|
From: Nils P. <n.p...@cu...> - 2006-04-01 18:22:24
|
Dave Moore wrote: > > Small niggle: you get a quadratic equation in t not a linear one, > right? There are cases where you get 2 crossings. Yes, but you're usually interested in the intersection that happends earliest. It's save to discard the greater one. Nils |
|
From: metanet s. <met...@ya...> - 2006-04-02 18:09:16
|
hi, just in case anyone else is going to use this -- you actually can't naively discard the later intersection, because the quadratic gives you the intersection times of the _infinite_ line with the point. if you're interested in the segment-vs-point intersections (as i was), you have look at both roots to see if either represents an intersection with the lineseg; sometimes the earlier intersection is outside the lineseg, while the later one is in/on the lineseg. raigan Nils Pipenbrinck <n.p...@cu...> wrote: Dave Moore wrote: > > Small niggle: you get a quadratic equation in t not a linear one, > right? There are cases where you get 2 crossings. Yes, but you're usually interested in the intersection that happends earliest. It's save to discard the greater one. Nils ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 --------------------------------- Share your photos with the people who matter at Yahoo! Canada Photos |
|
From: Jonathan B. <jo...@nu...> - 2006-04-02 22:34:07
|
Right. Of course. I vow that next time I post something to gdalgorithms I am going to actually look at the equation and think about it. metanet software wrote: > hi, > just in case anyone else is going to use this -- you actually can't > naively discard the later intersection, because the quadratic gives > you the intersection times of the _infinite_ line with the point. > > if you're interested in the segment-vs-point intersections (as i was), > you have look at both roots to see if either represents an > intersection with the lineseg; sometimes the earlier intersection is > outside the lineseg, while the later one is in/on the lineseg. > > raigan > > > */Nils Pipenbrinck <n.p...@cu...>/* wrote: > > Dave Moore wrote: > > > > > Small niggle: you get a quadratic equation in t not a linear one, > > right? There are cases where you get 2 crossings. > > > Yes, but you're usually interested in the intersection that happends > earliest. It's save to discard the greater one. > > Nils > > > > > > > ------------------------------------------------------- > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > ------------------------------------------------------------------------ > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca> |
|
From: Robert D. <bli...@go...> - 2006-04-03 23:34:40
|
How about taking the other view of this - instead of looking for the moving line segment which hits your point, look for the point on your line segment which will hit your point. So you are looking for t such that: (C - (A + t(B-A))) cross (Av + t(Bv-Av)) = 0 ( Oh, I'm assuming you have already subtracted the velocity of C from everything, since that makes everything much easier ) So now you convert the above into a quadratic equation, find the solution(s) If they are <0 or >1 then they are outside the segment so ignore If not, then test for (Av + t(Bv-Av)) = 0 since this also gives the appearance of success when in fact it should fail. So long as that is not the case, then you are left with a known t which gives you a straight line which is known to pass through the point C, and so you can find the time of impact with a simple linear equation. You can probably do this last bit with a dot product too, since you don't need to do real collision at this point - you know it must pass through the point (barring fp inaccuracy) so just find : (C - (A + t(B-A))) dot (Av + t(Bv-Av)) _____________________________ (Av + t(Bv-Av)) dot (Av + t(Bv-Av)) To give the fraction of time along the line that you need to travel. I'll leave the long winded expansion to quadratic for you to work out :-) Regards Robert _____ From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software Sent: 02 April 2006 19:09 To: gda...@li... Subject: Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D) hi, just in case anyone else is going to use this -- you actually can't naively discard the later intersection, because the quadratic gives you the intersection times of the _infinite_ line with the point. if you're interested in the segment-vs-point intersections (as i was), you have look at both roots to see if either represents an intersection with the lineseg; sometimes the earlier intersection is outside the lineseg, while the later one is in/on the lineseg. raigan Nils Pipenbrinck <n.p...@cu...> wrote: Dave Moore wrote: > > Small niggle: you get a quadratic equation in t not a linear one, > right? There are cases where you get 2 crossings. Yes, but you're usually interested in the intersection that happends earliest. It's save to discard the greater one. Nils ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 _____ Share your photos with the people who matter at <http://photos.yahoo.ca> Yahoo! Canada Photos |
|
From: metanet s. <met...@ya...> - 2006-04-04 02:25:16
|
hi,
weird, i'd never considered this, but it's seeming to make sense -- it's sort of the complement of the method jonathan suggested -- either way you solve a quadratic, which gives you a line containing the solution (the solution being the collision point at the time of collision).
the line either will either describe the movement of the collision point on the over the time interval [0,1] -- your suggestion, or the time of collision with the lineseg (which is an interval) -- jonathan's suggestion.
either way you can find the solution point by finding the intersection of the point's movement and the line which is known to contain the solution.
raigan
p.s - @ jonathan: you pretty much gave me the perfect working solution -- there was just a single tiny non-obvious caveat!! i think you're being hard on yourself ;)
Robert Dibley <bli...@go...> wrote: v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} st1\:*{behavior:url(#default#ieooui) } How about taking the other view of this â instead of looking for the moving line segment which hits your point, look for the point on your line segment which will hit your point.
So you are looking for t such that:
(C - (A + t(B-A))) cross (Av + t(Bv-Av)) = 0
( Oh, Iâm assuming you have already subtracted the velocity of C from everything, since that makes everything much easier )
So now you convert the above into a quadratic equation, find the solution(s)
If they are <0 or >1 then they are outside the segment so ignore
If not, then test for (Av + t(Bv-Av)) = 0 since this also gives the appearance of success when in fact it should fail.
So long as that is not the case, then you are left with a known t which gives you a straight line which is known to pass through the point C, and so you can find the time of impact with a simple linear equation.
You can probably do this last bit with a dot product too, since you donât need to do real collision at this point â you know it must pass through the point (barring fp inaccuracy) so just find :
(C - (A + t(B-A))) dot (Av + t(Bv-Av))
_____________________________
(Av + t(Bv-Av)) dot (Av + t(Bv-Av))
To give the fraction of time along the line that you need to travel.
Iâll leave the long winded expansion to quadratic for you to work out J
Regards
Robert
---------------------------------
From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software
Sent: 02 April 2006 19:09
To: gda...@li...
Subject: Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
hi,
just in case anyone else is going to use this -- you actually can't naively discard the later intersection, because the quadratic gives you the intersection times of the _infinite_ line with the point.
if you're interested in the segment-vs-point intersections (as i was), you have look at both roots to see if either represents an intersection with the lineseg; sometimes the earlier intersection is outside the lineseg, while the later one is in/on the lineseg.
raigan
Nils Pipenbrinck <n.p...@cu...> wrote:
Dave Moore wrote:
>
> Small niggle: you get a quadratic equation in t not a linear one,
> right? There are cases where you get 2 crossings.
Yes, but you're usually interested in the intersection that happends
earliest. It's save to discard the greater one.
Nils
-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos
---------------------------------
Make Yahoo! Canada your Homepage Yahoo! Canada Homepage |
|
From: Robert D. <bli...@go...> - 2006-04-04 08:44:58
|
Yes, the one advantage of mine is that the initial solution (of the = quadratic) tells you if you are off the ends of the line segment = immediately, which I=E2=80=99m guessing will save you some work = =E2=80=93 not a lot though :-) =20 Incidentally, I don=E2=80=99t know if you have thought about this at = all, but your line segment is changing length when you do this sort of = thing. So if for example you really had a piece of wire spinning, it would have = constant length, and each point on the wire would cover a curve. Without modelling this, you will get cases where a point is missed = because you are using straight line segments. Whether that is a great concern or not is of course up to you =E2=80=93 = but if you have a fast spinning wire, then perhaps it should be. =20 Robert =20 _____ =20 From: gda...@li... = [mailto:gda...@li...] On Behalf Of = metanet software Sent: 04 April 2006 03:25 To: gda...@li... Subject: RE: [Algorithms] Moving Segment vs Moving Point Intersection = (2D) =20 hi, weird, i'd never considered this, but it's seeming to make sense -- it's = sort of the complement of the method jonathan suggested -- either way = you solve a quadratic, which gives you a line containing the solution = (the solution being the collision point at the time of collision).=20 the line either will either describe the movement of the collision point = on the over the time interval [0,1] -- your suggestion, or the time of = collision with the lineseg (which is an interval) -- jonathan's = suggestion.=20 either way you can find the solution point by finding the intersection = of the point's movement and the line which is known to contain the = solution. raigan p.s - @ jonathan: you pretty much gave me the perfect working solution = -- there was just a single tiny non-obvious caveat!! i think you're = being hard on yourself ;) Robert Dibley <bli...@go...> wrote: How about taking the other view of this =C3=A2=E2=82=AC=E2=80=9C instead = of looking for the moving line segment which hits your point, look for = the point on your line segment which will hit your point. =20 So you are looking for t such that: =20 (C - (A + t(B-A))) cross (Av + t(Bv-Av)) =3D 0 =20 ( Oh, I=C3=A2=E2=82=AC=E2=84=A2m assuming you have already subtracted = the velocity of C from everything, since that makes everything much = easier ) =20 So now you convert the above into a quadratic equation, find the = solution(s) If they are <0 or >1 then they are outside the segment so ignore If not, then test for (Av + t(Bv-Av)) =3D 0 since this also gives the = appearance of success when in fact it should fail. So long as that is not the case, then you are left with a known t which = gives you a straight line which is known to pass through the point C, = and so you can find the time of impact with a simple linear equation. =20 You can probably do this last bit with a dot product too, since you = don=C3=A2=E2=82=AC=E2=84=A2t need to do real collision at this point = =C3=A2=E2=82=AC=E2=80=9C you know it must pass through the point = (barring fp inaccuracy) so just find : =20 (C - (A + t(B-A))) dot (Av + t(Bv-Av))=20 _____________________________ =20 (Av + t(Bv-Av)) dot (Av + t(Bv-Av)) =20 To give the fraction of time along the line that you need to travel. =20 I=C3=A2=E2=82=AC=E2=84=A2ll leave the long winded expansion to quadratic = for you to work out :-) =20 Regards =20 Robert =20 =20 _____ =20 From: gda...@li... = [mailto:gda...@li...] On Behalf Of = metanet software Sent: 02 April 2006 19:09 To: gda...@li... Subject: Re: [Algorithms] Moving Segment vs Moving Point Intersection = (2D) =20 hi, just in case anyone else is going to use this -- you actually can't = naively discard the later intersection, because the quadratic gives you = the intersection times of the _infinite_ line with the point. =20 if you're interested in the segment-vs-point intersections (as i was), = you have look at both roots to see if either represents an intersection = with the lineseg; sometimes the earlier intersection is outside the = lineseg, while the later one is in/on the lineseg. raigan Nils Pipenbrinck <n.p...@cu...> wrote: Dave Moore wrote: > > Small niggle: you get a quadratic equation in t not a linear one,=20 > right? There are cases where you get 2 crossings. Yes, but you're usually interested in the intersection that happends=20 earliest. It's save to discard the greater one. Nils ------------------------------------------------------- This SF.Net email is sponsored by xPML, a groundbreaking scripting = language that extends applications into web and mobile media. Attend the live = webcast and join the prime developer group breaking into this new coding = territory! http://sel.as-us.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =20 _____ =20 Share your photos with the people who matter at = <http://photos.yahoo.ca> Yahoo! Canada Photos =20 _____ =20 Make Yahoo! Canada your Homepage <http://ca.yahoo.com/bin/set> Yahoo! = Canada Homepage=20 |
|
From: metanet s. <met...@ya...> - 2006-04-04 16:28:55
|
hi,
it's actually not a problem, as the wire is allowed to change lengths/compress/stretch. "wire" may be a bit misleading, i just wanted to distinguish it from the standard rope-as-chain-of-particles ;)
raigan
Robert Dibley <bli...@go...> wrote: v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} st1\:*{behavior:url(#default#ieooui) } Yes, the one advantage of mine is that the initial solution (of the quadratic) tells you if you are off the ends of the line segment immediately, which Iâm guessing will save you some work â not a lot though J
Incidentally, I donât know if you have thought about this at all, but your line segment is changing length when you do this sort of thing.
So if for example you really had a piece of wire spinning, it would have constant length, and each point on the wire would cover a curve.
Without modelling this, you will get cases where a point is missed because you are using straight line segments.
Whether that is a great concern or not is of course up to you â but if you have a fast spinning wire, then perhaps it should be.
Robert
---------------------------------
From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software
Sent: 04 April 2006 03:25
To: gda...@li...
Subject: RE: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
hi,
weird, i'd never considered this, but it's seeming to make sense -- it's sort of the complement of the method jonathan suggested -- either way you solve a quadratic, which gives you a line containing the solution (the solution being the collision point at the time of collision).
the line either will either describe the movement of the collision point on the over the time interval [0,1] -- your suggestion, or the time of collision with the lineseg (which is an interval) -- jonathan's suggestion.
either way you can find the solution point by finding the intersection of the point's movement and the line which is known to contain the solution.
raigan
p.s - @ jonathan: you pretty much gave me the perfect working solution -- there was just a single tiny non-obvious caveat!! i think you're being hard on yourself ;)
Robert Dibley <bli...@go...> wrote:
How about taking the other view of this ââ¬â instead of looking for the moving line segment which hits your point, look for the point on your line segment which will hit your point.
So you are looking for t such that:
(C - (A + t(B-A))) cross (Av + t(Bv-Av)) = 0
( Oh, Iââ¬â¢m assuming you have already subtracted the velocity of C from everything, since that makes everything much easier )
So now you convert the above into a quadratic equation, find the solution(s)
If they are <0 or >1 then they are outside the segment so ignore
If not, then test for (Av + t(Bv-Av)) = 0 since this also gives the appearance of success when in fact it should fail.
So long as that is not the case, then you are left with a known t which gives you a straight line which is known to pass through the point C, and so you can find the time of impact with a simple linear equation.
You can probably do this last bit with a dot product too, since you donââ¬â¢t need to do real collision at this point ââ¬â you know it must pass through the point (barring fp inaccuracy) so just find :
(C - (A + t(B-A))) dot (Av + t(Bv-Av))
_____________________________
(Av + t(Bv-Av)) dot (Av + t(Bv-Av))
To give the fraction of time along the line that you need to travel.
Iââ¬â¢ll leave the long winded expansion to quadratic for you to work out J
Regards
Robert
---------------------------------
From: gda...@li... [mailto:gda...@li...] On Behalf Of metanet software
Sent: 02 April 2006 19:09
To: gda...@li...
Subject: Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
hi,
just in case anyone else is going to use this -- you actually can't naively discard the later intersection, because the quadratic gives you the intersection times of the _infinite_ line with the point.
if you're interested in the segment-vs-point intersections (as i was), you have look at both roots to see if either represents an intersection with the lineseg; sometimes the earlier intersection is outside the lineseg, while the later one is in/on the lineseg.
raigan
Nils Pipenbrinck <n.p...@cu...> wrote:
Dave Moore wrote:
>
> Small niggle: you get a quadratic equation in t not a linear one,
> right? There are cases where you get 2 crossings.
Yes, but you're usually interested in the intersection that happends
earliest. It's save to discard the greater one.
Nils
-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188
---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos
---------------------------------
Make Yahoo! Canada your Homepage Yahoo! Canada Homepage
---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos |
|
From: Jonathan B. <jo...@nu...> - 2006-04-01 19:07:37
|
Yes, he actually pointed this out in a different email... it's one of those things where I saw it was a quadratic equation in the back of my head when I posted to gdalgorithms, but just didn't want to think about it. Indeed you can have two intersections, due to the way the points are moving (I came up with a test case for that that's clear and obvious), so yeah, you just take the earliest (non-negative) answer. Dave Moore wrote: > Jonathan Blow wrote: >> test against the whole line. The point can only cross the line once >> during the timestep (due to linearity). So if it crosses, then you find > > Small niggle: you get a quadratic equation in t not a linear one, > right? There are cases where you get 2 crossings. > > > ------------------------------------------------------- > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the live > webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X