Seperating Axis, Rotated Rectangles...

[xup878]

ok i've had a little time to work on this but i'm stuck...
the green lines are the axis for testing the collisions... i haven;t put em colliding for clarity...



see here that i can detect the collisions for a rectangle when it is on any of the corner points...



but what do i do when it won't be hiting the edges?? as u can see here the collision is about to take place, but its not even close...

should i change the axis i am testing on?

Metanet i know u know ur stuff, please help! i can't find anything on the net about rotated rectangles using seperating axis!!
diagrams of what axis to test and when are all i need really...
i just don't know when i should be testing what axis?? and how to detect when to swap axis? should i be using vornoi regions again?

[ant512]

There are a few of ways I can think of to do this. The first might not be possible in Flash, but it works in Java (so I suspect it might be possible in Flash MX 2004):

- Create two GeneralPath objects from the two rectangles;
- Create an Area object from the two GeneralPath objects.

If the Area object is not false, the two GeneralPath objects intersect, so you know that there is a collision:

code:

---

if (areaObject) {

    collision = true;

} else {

    collision = false;

}

---

The second way, which is much more intensive, is to treat each side of the rectangles as a separate line. Work out the equation of the lines, and check for intersects between every line of rectangle A with every line of rectangle B within the boundaries described by the rectangle.

This requires:

- Calculation of 8 line equations;
- Calculation of 16 line intersection points.

Finally, you could attempt to use the shape-based hitTest method, but as that only deals with single co-ordinate collisions, you'd have to loop through a subset of co-ordinates within one of the rectangles to check - every five pixels, for example. Again, this is very intensive.

There's probably a better way of approaching this, though - I'll be interested to see what everyone else comes up with.

[xup878]

Originally posted by ant512
There's probably a better way of approaching this, though - I'll be interested to see what everyone else comes up with.

yeh i know all about the line intersect etc ways...

i'm only interested in the seperating axis theory.... it is actually the fastest, i think...
i'm just one step away, and i can't figure out the last hurdle... which axis do i test against for which situations...
circles vs rectangles was so much easier...

[DancingOctopus]

I'd create 4 MC's inside each rectangle, localtoglobal their position then shape flag col det each against each rectangle. If you did an initial bounding box col det before the more accurate method, it shouldn't be too much strain on the CPU.

[ant512]

I've had a quick look on Google for this method - it's a work of genius. Have a look at this page, as it includes little Flash demos of each stage in the algorithm:

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

Note the correct spelling of "separating" - this might help you find the answers you're after!

[metanet]

hi,
i'm sorry if i'm not understanding the problem, but it appears to me (from your diagrams) that you're only testing 2 axes.

for 2 boxes, which _each_ have 2 axes to test, you need to test 4 axes in total. so, in the bottom pic, it's true that the boxes are almost colliding if you only test using the left box's axes, but if you use the right box you'll see that they're still quite seperated.

also, you're drawing the projected size of the boxes; if done properly, you should be calculating the "halfsize" and not the full size. but you might be doing the halfsize then fooling with it to get a nice display, who knows -- one problem we found was that writing code to DO the sepaxis test and writing code to DISPLAY the results are two different things. if you do the former correctly there will be almost nothing worth drawing. but to do the latter properly you have to perform all kinds of extra math, which essentially defeats the speed (though it's good for testing, as you've shown). this is why we didn't release the source to the diagrams, because they are useless as collision code.

anyway, you seem to be on the right track.

raigan

[xup878]

ah of course i should be testing the second boxes axis as well... whoops

ok so i should be testing on the axis as well like this???


drawn in real quick

yeah the way it looks is for display purposes only
i'm using halfsizes normally... i too have different code for the collision test and the drawing... dunno if u remember my circle v rotated rectangle demo?

[metanet]

hey,
i guess that was it -- i do remember the rotated rects, i recognized the little control squares in your pic

raigan