2d Collision Detection With Rotating Rectangles... anyone?

[keeling]

I had been using an offset method of drawing with the rotation done every cycle..... very slow! This was the next thing I was going to tackle once I started to understand collision detection but I got side-tracked. That and I hadn't thought about it because the machine's speed was masking it. I guess I will look at that next.

And yes, simple circle-circle CD works well enough to get 'close enough' for a more serious detection to take place.

[marzecTM]

point in polygon testing is the way to go and gives you a perfect result. it goes like this given that you only want to intersect convex polys:

you have your list of vertices ( points ) of the rectangle in 2d

Code:

p1---------p2
    ^                   |
    |                    |
    |                    |
    p4<---------- p3

as you can see the points have to be given in clockwise or counterclockwise order. if you store them in an array you can't have points(0) being p1 and points(2) being p2 for example.

you now can calculate the line segments between adjacend points that is the segment p1 to p2, p2 to p3, p3 to p4 and p4 to p1. if you have a look at the ascii art obove you see they form a circle. now let's take the segment p2 to p3

Code:

p2
            | \
            |   \
            v    v
           p3   p

i also drew a point p here which is the point in question. i also created a new segment from p2 to p. we now have to vectors. with our the following friendly formula we now can check on which side of the segment p2 to p3 point p lies.

(p.y - p2.y)*( p3.x * p2.x) - ( p.x - p2.y )*(p3.y * p2.y )

looks like a dirty hybrid of a dot and crossproduct doesn't it? i won't derive that formula here. basically it gives you this:

+ if the result is < 0 then the point is on the right site of the linesegment

+ if the result > 0 then the point is on the left site of the line segment

+ if the result = 0 then the point is on the line segment

now have a look at the first figure again. the line segments are arranged in a circular order. all you have to do is to calculate the value of the above formula for all line segments for the point in question and check wheter the sign of them is the same for every result which boils down to this pseudo code.

Code:

dim points( 0 to NUM_POINTS ) as Point
dim p as Point
dim is_in_poly as integer

dim side as single
enum Side
   LEFT_SIDE
   RIGHT_SIDE
   ON_LINE
end enum

is_in_poly = -1
for i = 0 to NUM_POINTS

   if( i = 0 ) then
      tmp = ( p.y - points(i).y )*( points(i+1).x * points(i).x) - ( p.x - points(i).x ) * ( points(i+1).y -points(i )
      if( tmp < 0 ) then site = RIGHT_SIDE
      if( tmp > 0 ) then site = LEFT_SIDE
      if( tmp = 0 ) then is_in_poly = -1: exit for
   else if i = NUM_POINTS then
      tmp = ( p.y - points(i).y )*( points(0).x -  points(i).x) - ( p.x - points(i).x ) * ( points(0).y -points(i )
      if( tmp < 0 ) then tmp = RIGHT_SIDE
      if( tmp > 0 ) then tmp = LEFT_SIDE
      if( tmp = 0 ) then is_in_poly = -1: exit for
      if( tmp <> side ) then is_in_poly = 0: exit for
   else
            tmp = ( p.y - points(i).y )*( points(i+1).x * points(i).x) - ( p.x - points(i).x ) * ( points(i+1).y -points(i )
      if( tmp < 0 ) then tmp = RIGHT_SIDE
      if( tmp > 0 ) then tmp = LEFT_SIDE
      if( tmp = 0 ) then is_in_poly = -1: exit for
      if( tmp <> side ) then is_in_poly = 0: exit for
   end if
next i

if is_in_poly then
   print "point is in poly
else
   print "point is not in poly"
end if

this code might or might not work and can be written by far smaller. but it's more clear that way. so this will tell you wheter a point lies within an n-sided convex polygon. to collide one poly with another you only have to check wheter one of the second polygons points lies in the other polygon and you have perfect pixel collision.

hope that works.

[wallace]

going back to the first post. Lots of programmers place objects in circles and do collision that way. Hell even Halo's vehicles (2001) were placed inside spheres. No one has come up with a perfect collision detection system, even the Havok physics engine can't handle really small or really fast moving objects.

[wallace]

better yet, use an array of circles. It would be easier in OOP, but have each rectangle have a smaller rectangle associated with it that rotates with it. Have four circles that have there centres on the corners of the smaller rectangle. Make them big enough that they reach the corner of the rectangle and all of the edges

[1000101]

If you're dealing with any arbitrary shape, just use simple line interestion.

Define a set of lines which corrispond to the outside edge of your objects and then do line interection, clean, fast, simple.

[marzecTM]

did anybody even boughter to read my post? to summarzie for the lazy: perfect collision detection in 2d between convex n-polys

[keeling]

As I started with the Vector Manipulations for this I came across a thread that had already done this on a different board. Why re-invent the wheel? I have checked this through a wide range of lines and have no problems with it yet. Someone else what to check this?

Code:

#define NO_INTERSECTION        -1
#define INTERSECTION            0
#define CO_LINEAR                1

Type Point2d
   x as Double
   y as Double
end type
Type Line2d
   p1 as point2d
   p2 as point2d
end type
  

const FALSE = 0
const TRUE = NOT FALSE

Function LineIntersection2d(ByRef Line1 as Line2d, _
                            ByRef Line2 as Line2d, _
                            ByRef Intersection2d as Point2d = 0) as Byte
   'a FB translation of code posted by Graham Goring at
   'http://forums.indiegamer.com/showthread.php?t=861
    dim x as double
   dim y as double
   dim a1 as double
   dim b1 as double
   dim c1 as double
   dim a2 as double
   dim b2 as double
   dim c2 as double
   dim r1 as double
   dim r2 as double
   dim r3 as double
   dim r4 as double
   dim denom as double
   dim offset as double
   dim num as double

    a1 = Line1.p2.y - Line1.p1.y
    b1 = Line1.p1.x - Line1.p2.x 'Vector from start to end of line, except mirrored.
    c1 = (Line1.p2.x * Line1.p1.y) - (Line1.p1.x * Line1.p2.y)

    r3 = (a1 * Line2.p1.x) + (b1 * Line2.p1.y) + c1
    r4 = (a1 * Line2.p2.x) + (b1 * Line2.p2.y) + c1
    
    if ( ( r3 <> 0 ) AND (r4 <> 0 ) ) Then
        if (SGN(r3) = SGN(r4)) then
             LineIntersection2d = NO_INTERSECTION
         exit function
      end if
   end if

   a2 = Line2.p2.y - Line2.p1.y
   b2 = Line2.p1.x - Line2.p2.x
   c2 = (Line2.p2.x * Line2.p1.y) - (Line2.p1.x * Line2.p2.y)

   r1 = (a2 * Line1.p1.x) + (b2 * Line1.p1.y) + c2
   r2 = (a2 * Line1.p2.x) + (b2 * Line1.p2.y) + c2

    if ( ( r1 <> 0 ) AND (r2 <> 0 ) ) Then
        if (SGN(r1) = SGN(r2)) then
            LineIntersection2d = NO_INTERSECTION
         exit function
      end if
   end if


    denom = (a1 * b2) - (a2 * b1)

   if (denom = 0) then
      LineIntersection2d = CO_LINEAR
      exit function
   end if
    

    'If we are here then the line segments intersect
   'so, compute intersection point

    if (denom < 0) then
        offset = -denom / 2
    else
        offset = denom / 2
   end if

    num = (b1 * c2) - (b2 * c1)
    
    if (num < 0) then
        x = (num - offset) / denom
    else
        x = (num + offset) / denom
    end if
    
    num = (a2 * c1) - (a1 * c2)
    
    if (num < 0) then
        y = (num - offset) / denom
    else
        y = (num + offset) / denom
   end if
    
    Intersection2d.x = x
    Intersection2d.y = y
        
    LineIntersection2d =  INTERSECTION
end function

[keeling]

@shiftLynx

As you'll most likely notice, this is very similar to what you had. This has the added bonus of telling you where the lines intersect. If one was only interested in collision, you could early out at the approb. comment.