RE: [Algorithms] Moving Segment vs Moving Point Intersection (2D)

[metanet s. <met...@ya...>]

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  you’re 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, it’s 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  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 Yahoo! Canada Finance
    
    
    

		
---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos