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.

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?

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

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?

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

Many thanks, now i got it :)