Line on Line Collision

[voidSkipper]

I've built quite a decent ragdoll engine, but I'm stumped as to how to solve collisions between the lines (or constraints) that join points (for instance, one ragdoll colliding with another). I was able to work out on paper how to find the point of intersection of two lines, then modify the velocities of the penetrating point so as to remove it within one update, but I couldn't get it to translate into flash.

In short, can someone explain to me how to, in flash
-Find the point of intersection between two line segments (line segments defined as {a.x, a.y, b.x, b.y}
-Find the component vectors required to move the two lines apart

Thanks in advance (:

[newblack]

you can treat a line as a rectangle with no area and use the separating axis theorem to detect/resolve collisions. this would essentially double the number of collision queries you'd have to perform (once up the length of the segment and another back down), but could be worth it as SAT offers a generalized solution for a lot of collision.

i'm happy to help if you decide to go this route.

[voidSkipper]

I was not planning to make this that complicated, but if you're willing to teach, I'm willing to learn.

[ozmic66]

Instead of using a rectangle with no area, you can actually just use a polygon defined by only 2 vertices with the SAT algo

[voidSkipper]

Would someone please explain SAT to me?

[ozmic66]

Check these out

Great visuals:
http://www.harveycartel.org/metanet/...tutorialA.html

In depth explanation:
http://www.geometrictools.com/Docume...ratingAxes.pdf

[newblack]

from the links provided by ozmic66 you should have an idea of what SAT is- here's an implementation (not testing anything, so let me know) based on how i've used SAT.

i'm making the following assumptions which i can clarify/explain/provide source if necessary:
1. you have a Vector datatype with
a. public x & y properties
b. a method called 'dot' that returns the dot product of 2 vectors
c. a 'normalize' method which normalizes the Vector
d. a 'getDifference' method which returns the difference between the 2 vectors
e. a 'getProduct' method which scales a Vector by a Number
f. a 'negate' method which scales the Vector by -1

2. the line datatype has 2 public properties, a and b (both Vectors)

so- we have a CollisionDetector datatype with 4 properties, and a constructor that defines the lines to check for collision:

//lines your checking for collision
public var line1:Line;
public var line2:Line;
//how far they've penetrated (smallest incident)
public var penetrationDepth:Number;
//the axis to translate the lines out of contact
public var normal:Vector;

public function CollisionDetector( line1:Line, line2:Line )
{
   this.line1 = line1;
   this.line2 = line2;
} 

so you want to treat each line as if it has 2 edges. the CollisionDetector datatype then implements a hasCollision method. it will return true if there's a collision and false otherwise. we construct the algorithm to terminate as soon as we find there isn't a collision. i've marked in the code the process you need to repeat for each edge rather than type it all out (start loop and end loop). if this is confusing or you need help defining the edge normals, i'm happy to help.

public function hasCollision() : Boolean
{
   //we evaluate each penetration, finding the smallest 
   //any valid candidate will be negative and greater than Number.NEGATIVE_INFINITY
   penetrationDepth = Number.NEGATIVE_INFINITY;

   //start loop here- iterate over each edge normal (4)

   //edgeNormal is the Vector perpindicular or 'normal' to the edge in
   //question. this variable would be defined 4 times in the loop (unless
   //a separating axis is found)
   var edgeNormal:Vector = new Vector( -( line1.b.y - line1.a.y ), line1.b.x - line1.a.x );
   edgeNormal.normalize();

   //project each vertex of line1 onto the edgeNormal
   var proj1a:Number = edgeNormal.dot( line1.a );
   var proj1b:Number = edgeNormal.dot( line1.b );
   //find the mins and maxes
   var min1:Number = Math.min( proj1a, proj1b );
   var max1:Number = Math.max( proj1a, proj1b );
   
   //project each vertex of line2 onto the edgeNormal
   var proj2a:Number = edgeNormal.dot( line2.a );
   var proj2b:Number = edgeNormal.dot( line2.b );
   //find the mins and maxes
   var min2:Number = Math.min( proj2a, proj2b );
   var max2:Number = Math.max( proj2a, proj2b );

   //now we have a 1 dimensional overlap query- find the distance
   var dist:Number = min1 < min2 ? min2 - max1 : min1 - max2;
   //if the distance between their 1D projections is greater than zero
   //then they do not intersect
   if( dist > 0 ) return false; //separating axis found- exit algorithm

   //just because the projections overlap doesn't mean it's the best
   //axis with which to resolve the collision- we want to find the smallest
   if( dist > penetrationDepth )
   {
      //it is the smallest distance needed to resolve the lines' 
      //interpenetration so update penetrationDepth and normal
      penetrationDepth = dist;
      normal = edgeNormal;
   }

   //end loop here- if we haven't exited the algorithm, there is no
   //separating axis and the lines intersect
   return true;
} 

Now for resolving the collision let's look at how we would use the CollisionDetector:

var detector:CollisionDetector = new CollisionDetector( line1, line2 );
if( detector.hasCollision() )
{
   //first we need to decide how the bodies sit in regard to the found normal
   //we can assign a position to the line by averaging its vertices:
   var line1Pos:Vector = new Vector( ( line1.a.x + line1.b.x ) / 2, ( line1.a.y + line1.b.y ) / 2;
   var line2Pos:Vector = new Vector( ( line2.a.x + line2.b.x ) / 2, ( line2.a.y + line2.b.y ) / 2;

   //find line2's position relative to 1
   var diff:Vector = line1Pos.getDifference( line2Pos );
   if( diff.dot( detector.normal ) < 0 ) detector.normal.negate();
   
   //the vector we'll actually use to resolve interpenetration
   var resolution:Vector = detector.normal.getProduct( detector.penetrationDepth );

   //each line shares the same translation out of collision (0.5)
   //this could be changed to handle different masses
   line1.a.x -= resolution.x * 0.5;
   line1.a.y -= resolution.y * 0.5;
   line1.b.x -= resolution.x * 0.5;
   line1.b.y -= resolution.y * 0.5;

   line2.a.x += resolution.x * 0.5;
   line2.a.y += resolution.y * 0.5;
   line2.b.x += resolution.x * 0.5;
   line2.b.y += resolution.y * 0.5;
} 

ok- i hope that gets you started. it's late and all this is off the top of my head so i can't say this is the best explanation... but i'm happy to help with any issues this brings up.

Instead of using a rectangle with no area, you can actually just use a polygon defined by only 2 vertices with the SAT algo

yes, same thing i was saying; just trying to offer a visualization.

[ozmic66]

Nice explanation Newblack.
It's always great to see this kind of effort in responses on this forum.

[voidSkipper]

Yes, thankyou very much indeed. I'll have to spend a while reading over all that.