4

This is what I am currently doing:

Creating 4 axis that are perpendicular to 4 edges of 2 rectangles. Since they are rectangles I do not need to generate an axis (normal) per edge.

I then loop over my 4 axes.

So for each axis: I get the projection of every corner of a rectangle on to the axis. There are 2 lists (arrays) containing those projections. One for each rectangle. I then get the dot product of each projection and the axis. This returns a scalar value that can be used to to determine the min and max.

Now the 2 lists contain scalars and not vectors. I sort the lists so I can easily select the min and max values. If the min of box B >= the max of box A OR the max of box B <= the min of box A then there is no collision on that axis and no collision between the objects.

At this point the function finishes and the loop breaks.

If those conditions are never met for all the axis then we have a collision

I hope this was the correct way of doing it.

The python code itself can be found here http://pastebin.com/vNFP3mAb

Also: http://www.gamedev.net/page/reference/index.html/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604

The problem i was having is that the code above does not work. It always detects a a collision even where there is not a collision. What i typed out is exactly what the code is doing. If I am missing any steps or just not understanding how SAT works please let me know.

Bruk Habtu
  • 115
  • 2
  • 8
  • 7
    What's the question? –  May 16 '11 at 06:02
  • For more general convex polygons we would consider potential axes of separation that are *parallel* to the edges of both polygons, but since you are specifically dealing with rectangles, it is equivalent in that case to ask for axes perpendicular (or normal) to the edges. – hardmath May 16 '11 at 09:26
  • The problem i was having is that the code above does not work. It always detects a a collision even where there is not a collision. Sorry for not being as clear. I will edit what i wrote so that it is more clear. – Bruk Habtu May 16 '11 at 17:15
  • 1
    @hardmath. The separating line will be parallel to the edges. The separating axis is the direction vector you project the point onto for testing and is perpendicular to the edges of the polygons. In 3d the separating axis is perpendicular to the faces (i.e. it is a face normal) or the cross product of an edge from each object - again perpendicular to the edges. – phkahler May 16 '11 at 19:12
  • @phkahler: You are right, the separating "hyperplane" corresponds to a normal direction, and the latter "axis" makes sense as the target of projection. The equation of the "hyperplane" can be understood as dotting the direction vector with a vector of unknowns giving some constant, the "normal form" of the equation if properly normalized. – hardmath May 17 '11 at 01:06

2 Answers2

5

In general it is necessary to carry out the steps outlined in the Question to determine if the rectangles "collide" (intersect), noting as the OP does that we can break (with a conclusion of non-intersection) as soon as a separating axis is found.

There are a couple of simple ways to "optimize" in the sense of providing chances for earlier exits. The practical value of these depends on the distribution of rectangles being checked, but both are easily incorporated in the existing framework.

(1) Bounding Circle Check

One quick way to prove non-intersection is by showing the bounding circles of the two rectangles do not intersect. The bounding circle of a rectangle shares its center, the midpoint of either diagonal, and has diameter equal to the length of either diagonal. If the distance between the two centers exceeds the sum of the two circles' radii, then the circles do not intersect. Thus the rectangles also cannot intersect. If the purpose was to find an axis of separation, we haven't accomplished that yet. However if we only want to know if the rectangles "collide", this allows an early exit.

(2) Vertex of one rectangle inside the other

The projection of a vertex of one rectangle on axes parallel to the other rectangle's edges provides enough information to detect when that vertex is inside the other rectangle. This check is especially easy when the latter rectangle has been translated and unrotated to the origin (with edges parallel to the ordinary axes). If it happens that a vertex of one rectangle is inside the other, the rectangles obviously intersect. Of course this is a sufficient condition for intersection, not a necessary one. But it allows for an early exit with a conclusion of intersection (and of course without finding an axis of separation because none will exist).

hardmath
  • 8,753
  • 2
  • 37
  • 65
3

I see two things wrong. First, the projection should simply be the dot product of a vertex with the axis. What you're doing is way too complicated. Second, the way you get your axis is incorrect. You write:

Axis1 = [  -(A_TR[0] - A_TL[0]),
             A_TR[1] - A_TL[1] ]

Where it should read:

Axis1 = [  -(A_TR[1] - A_TL[1]),
             A_TR[0] - A_TL[0] ]

The difference is coordinates does give you a vector, but to get the perpendicular you need to exchange the x and y values and negate one of them.

Hope that helps.

EDIT Found another bug

In this code:

if not ( B_Scalars[0] <= A_Scalars[3] or B_Scalars[3] >= A_Scalars[0] ):
            #no overlap so no collision
            return 0

That should read:

if not ( B_Scalars[3] <= A_Scalars[0] or A_Scalars[3] <= B_Scalars[0] ):

Sort gives you a list increasing in value. So [1,2,3,4] and [10,11,12,13] do not overlap because the minimum of the later is greater than the maximum of the former. The second comparison is for when the input sets are swapped.

phkahler
  • 5,687
  • 1
  • 23
  • 31
  • Thanks for the response phkahler. Once I have the corners projected on to the axis it is a matter of finding the 2 corners (per rectangle) that are the farthest in either direction? This can be done my measuring the length between the 2 coordinates. I think I understand how this works now. I will post my solution when I get it working. – Bruk Habtu May 16 '11 at 20:47
  • Along the lines of things "way too complicated", I'm uncomfortable with the way rectangle are being represented. There's nothing explicit representing the angle of rotation of a rectangle. Instead the representation appears to be that of a general quadrilateral, i.e. four points that are simply labelled "top left", "top right", etc. The resulting eight coordinates are too general, so you have to rely on the code that populates them to get them consistent. A more restrictive representation (center, width, height, angle of rotation) could enforce that a rotated rectangle is being defined. – hardmath May 17 '11 at 01:51
  • @hardmath: yes I agree this is a general quadrilateral, but his implementation of SAT also compute an axis for all 4 side, so it should work so long as they are convex. – phkahler May 17 '11 at 18:41
  • @ Bruk Habtu: You still want to look for the min and max values like you're doing. Don't worry that the dot products are signed or that no specific vertex is at zero - it's all relative. – phkahler May 17 '11 at 18:42
  • @phkahler I followed your advice. But the code still detects objects as colliding even when they are no where near eachother. Once I had the projections of all the corners I checked to see whic were the min and max by checking the length between each point. I'm sure its something small that I am missing. http://pastebin.com/7yGWF5AG – Bruk Habtu May 19 '11 at 21:53
  • @Bruk Habtu: found another bug in your min/max testing. See update. – phkahler May 24 '11 at 16:29