A Flash Developer Resource Site

Results 1 to 9 of 9

Thread: Line on Line Collision

  1. #1
    Junior Member
    Join Date
    Sep 2007
    Posts
    6

    Line on Line Collision

    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 (:

  2. #2
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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.

  3. #3
    Junior Member
    Join Date
    Sep 2007
    Posts
    6
    I was not planning to make this that complicated, but if you're willing to teach, I'm willing to learn.

  4. #4
    Senior Member ozmic66's Avatar
    Join Date
    Oct 2005
    Posts
    472
    Instead of using a rectangle with no area, you can actually just use a polygon defined by only 2 vertices with the SAT algo
    Last edited by ozmic66; 09-26-2007 at 01:44 PM.
    Pixelwave Flash-based iPhone framework
    iPhone Games: Flyloop | Freedom Run

    Twitter: Oztune

  5. #5
    Junior Member
    Join Date
    Sep 2007
    Posts
    6
    Would someone please explain SAT to me?

  6. #6
    Senior Member ozmic66's Avatar
    Join Date
    Oct 2005
    Posts
    472
    Pixelwave Flash-based iPhone framework
    iPhone Games: Flyloop | Freedom Run

    Twitter: Oztune

  7. #7
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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:
    PHP Code:
    //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 
    CollisionDetectorline1:Lineline2: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.

    PHP Code:
    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.line1.a.), line1.b.line1.a.);
       
    edgeNormal.normalize();

       
    //project each vertex of line1 onto the edgeNormal
       
    var proj1a:Number edgeNormal.dotline1.);
       var 
    proj1b:Number edgeNormal.dotline1.);
       
    //find the mins and maxes
       
    var min1:Number Math.minproj1aproj1b );
       var 
    max1:Number Math.maxproj1aproj1b );
       
       
    //project each vertex of line2 onto the edgeNormal
       
    var proj2a:Number edgeNormal.dotline2.);
       var 
    proj2b:Number edgeNormal.dotline2.);
       
    //find the mins and maxes
       
    var min2:Number Math.minproj2aproj2b );
       var 
    max2:Number Math.maxproj2aproj2b );

       
    //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 ) 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:
    PHP Code:
    var detector:CollisionDetector = new CollisionDetectorline1line2 );
    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.line1.b.) / 2, ( line1.a.line1.b.) / 2;
       var 
    line2Pos:Vector = new Vector( ( line2.a.line2.b.) / 2, ( line2.a.line2.b.) / 2;

       
    //find line2's position relative to 1
       
    var diff:Vector line1Pos.getDifferenceline2Pos );
       if( 
    diff.dotdetector.normal ) < detector.normal.negate();
       
       
    //the vector we'll actually use to resolve interpenetration
       
    var resolution:Vector detector.normal.getProductdetector.penetrationDepth );

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

       
    line2.a.+= resolution.0.5;
       
    line2.a.+= resolution.0.5;
       
    line2.b.+= resolution.0.5;
       
    line2.b.+= resolution.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.
    Quote Originally Posted by 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
    yes, same thing i was saying; just trying to offer a visualization.
    Last edited by newblack; 09-28-2007 at 03:05 AM.

  8. #8
    Senior Member ozmic66's Avatar
    Join Date
    Oct 2005
    Posts
    472
    Nice explanation Newblack.
    It's always great to see this kind of effort in responses on this forum.
    Pixelwave Flash-based iPhone framework
    iPhone Games: Flyloop | Freedom Run

    Twitter: Oztune

  9. #9
    Junior Member
    Join Date
    Sep 2007
    Posts
    6
    Yes, thankyou very much indeed. I'll have to spend a while reading over all that.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center