Sign in to follow this  
adras

3D collision detection

Recommended Posts

http://www.gamasutra.com/features/20000210/lander_01.htm For those who are not registered:
Quote:
A better strategy is to divide the polygon into quadrants centered on the test point, as in Figure 4. Start at the first vertex in the polygon and set a counter to 0. Anytime an edge crosses from one quadrant to the next, add one to the counter if it crosses clockwise around the test point and subtract one if it crosses counter-clockwise. If the edge crosses diagonally across two quadrants, you need to determine which side of the test point it crossed, and then either add or subtract 2. Try it yourself on Figure 4. Start at vertex 1. Add 1 when edge 3-4 crosses from quadrant I to II, and subtract it again with edge 4-5. When you reach the last edge (11-1), you should have 4. When using the routine, if the counter is equal to 4 or –4, the test point is inside the polygon. You can see the code for this routine in Listing 1. Figure4
Well this is just perfect for me i think. But unfortunately i don't understand the following sentence:
Quote:
If the edge crosses diagonally across two quadrants, you need to determine which side of the test point it crossed, and then either add or subtract 2
determine which side? what is he talking about? left, right, up, down, diagonal? when do i have to add 2 and when to subtract 2? Are there any other easy ways for 3D collision detection that are 100% accurate?

Share this post


Link to post
Share on other sites
Hi Adras,

All they mean by:
If the edge crosses diagonally across two quadrants, you need to determine which side of the test point it crossed, and then either add or subtract 2

is that instead of an edge just crossing one quadrant boundry there could be a case where a polygons edge crosses 2 quadrant boundries from start to finish (like a longer version of edge 6-7 in the example might). Anyway when this happens you have to determine if it's a clockwise or counter clockwise move and then add or subtract 2 since you crossed 2 quadrants. There is no case for more than 2 quadrants since a straight line (an edge) couldn't pass through 3 quadrants.

Hope this helps

Share this post


Link to post
Share on other sites
Thanks for your quick reply!
And thats exactly my question how do i determine if its a clockwise or counterclockwise move when crossing 2 quadrants?

Share this post


Link to post
Share on other sites
The way the edges move through the quadrant boundries determines if they are clockwise or counter-clockwise with respect to the test point. So if an edge starts in quadrant I and moves to quadrant II, then you have a clockwise move. The same goes for quadrant II to quadrant III, or if you move to a higher quadrant you move clockwise (when you get to quadrant IV just wrap around to quadrant I). The counter clockwise moves work the opposite way by moving to lower quadrants.

The case where you cross over 2 quadrants works just the same except you have an extra quadrant. You would have something like a line starting in quadrant I crossing into quadrant II (clockwise since II is higher than I) and then it continues to move into quadrant III (still clockwise since III is higher than II) so you would add 2 since the edge made 2 clockwise moves. A single edge passing through 2 quadrant boundries will either be 2 clockwise moves or 2 counter-clockwise moves, but never 1 of each like a counter-clockwise to a clockwise.

Hope thats more clear

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this