Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[updated1]The Killer 2D Collision Detection Algorithms
#1
So a while after I posted this thread, I came about doing the killer collision detection algorithm(s). Stopped working on it for a while, but now I am back at it again. The plan is to do a complete set of algorithms that can check whether:
1-An n-sided polygon intersects an n-sided  polygon.
2-An n-sided polygon intersects an ellipse.
3-An ellipse intersects an ellipse.
4-A point is inside an ellipse or an n-sided polygon.

-Doing a fast implementation of #1 would be quite challenging, but not as challenging as #2 or #3.
-#4 can be done quite easily using the ray-casting algorithm.
-#2 and #3 are the hardest to implement, I believe, but since #2 would be more practical, I chose to start with it.

#2 An n-sided polygon intersecting with an ellipse:
For simplicity, lets assume the n-sided polygon is a rectangle, and that the ellipse is moving 4 pixel/frame on the x-axis (to the right), and 4 pixel/frame in the y-axis (downward). I could think of 3 scenarios this could happen:
[Image: s2q576b.png]

Before we tackle this, lets review our facts on ellipses.
[Image: Ch6-11.gif]
An ellipse is basically a stretched circle with 2 "radii". The x-radius is noted by the variable a, and the y-radius is noted by the variable b. The equation of an ellipse with a center at the origin is:
(x^2)/(a^2) + (y^2)/(b^2) = 1
Where a point (x, y) lying inside this ellipse will satisfy the equality:
(x^2)/(a^2) + (y^2)/(b^2) < 1

Using this fact, scenario #1 can be detected fairly easily by checking if one of the polygon's vertices lies inside the ellipse.

Scenario #2 can be checked for by checking if one of the polygon's sides intersects with the ellipse. The expression can be solved by equating the equation of the ellipse and the equation of the side line, which comes in the form of y=mx+c:
[Image: 8gkly6w.png]
Solving for x and y simultaneously will yield the 2 intersecting points between the line and the ellipse, if they intersect that is.

(1)y=mx+c
(2)(x^2)/(a^2) + (y^2)/(b^2) = 1

-Plug (1) into (2):
[Image: g5qJ8zC.png]

-Expanding (for a while) yields:
[Image: NzrjKXG.png]

-Taking common factor yields the following quadratic equation:
[Image: pLgcM7g.png]

-We solve for x using the quadratic formula by substituting:
[Image: mtOaDJf.png]
[Image: mnpSBBz.png]
[Image: RFAF3mu.png]
In:
[Image: 1rosBkj.png]
To get:
[Image: qKBFA5x.png]
Where a is the x-radius, b is the y-radius, m is the gradient of the line and c is the y-intercept of the line.
One decisive value we need to check before we solve for x is the value of the discriminant, [Image: DKFGPTb.png]:
If [Image: DKFGPTb.png], then this would mean that the line doesn't intersect the ellipse at all.
If [Image: QRUUOed.png], then this would mean that the line only touches the ellipse at one point; acts as a tangent. I wouldn't consider that intersecting myself.
If [Image: 1hym99w.png], then this would mean that the line does intersect with the ellipse in 2 points.


In case it's the latter, then you can solve for x to find the points of intersection. The 2 resulting values of x can be plugged into the line equation, y=mx+c, to find the 2 corresponding values of y for the points.

Finally, since your side is actually a segment of the line, you will need to see if its interval intersects with the ellipse, and this can be done by simply checking if any of the intersection points' x or y coordinates lies between either the line segment's x, y coordinates respectively.

You might've figured out that an m value of either 0 or INFINITY (a horizontal or a vertical line) can greatly simplify the calculation. Of course, this is to be added when implementing the algorithm at last.


Scenario #3 can be said to be true if:
1-The center of the ellipse lies inside the polygon (which would require algorithm #4).
2-Scenario #2 is not happening.


By implementing the above, it was really easy to create a hit/hurt box system (since it simply relies on whether the 2 boxes intersect or not). The real challenge is getting such shapes to work for things like platforming and obstacles where resolving the positions of the intersecting geometries would be required.


#4 A point inside an n-sided polygon or an ellipse:
A point inside an ellipse:
A point is inside an ellipse simply if it satisfies the expression:
[Image: zBAfd8N.png]

A point inside an n-sided polygon:
The ray casting algorithm offers a very simple and a cheap (computing time wise) way of finding out whether a point is inside a polygon or not. Basically, the algorithm says that if a ray (a forever going line) emerging from a point P(x,y) intersects with a polygon an odd number of times, then P lies inside the boundaries of that polygon. If the number of intersections the ray makes is even, then the point P lies outside the polygon:
[Image: 7XqRX1U.png]
This should work with a ray of any angle, but we chose to have it go downwards to simplify the intersection checks. The equation of the ray going downwards would simply be: [Image: HKDctGa.png]; where x1 is the x-coordinate of the point P(x1, y1).

In order to check if the sides of the n-sided polygon intersects with the ray, we simply equate the ray equation with every side's line equation:
(1)[Image: HKDctGa.png]
(2)[Image: 8YrFCgY.png]

-We plug (1) into (2)
[Image: BqaeuIF.png]
Where x1 is the x-coordinate of the point, m is the gradient of the side's line, c is its y-axis-intercept/x-offset value and y is the y-coordinate of the point where the ray and the side's line intercept.

After getting y, we check for the following:
1-If y is greater than y1; the intersection happens beyond the point, the direction where the ray goes.
2-If y lies in the interval ]y2, y3[ ; where y2 is the y-coordinate of the side's line segment's high end, and y3 is the y-coordinate of the side's line segment's low end: [Image: 7xnQlDc.png]

If 1 and 2 are true, then we increment the intersections counter. Whether the counter at the end contains an even or an odd number decides if the point is inside or outside the n-sided polygon (odd = inside; even = outside).

There is still two exception we've not gotten around yet:
1-The side's line being parallel to our line; having and m value of INFINITY.
We can solve this problem by simply skipping a side which difference between its two ends' x-coordinates is 0.
2-The ray cutting straight on a vertex in the following manner:
[Image: A5kQIaQ.png]


Thread still in progress. I plan to release the actual implementation when I get it working perfectly at optimal speed.
[Image: signature.png]
A-Engine: A new beat em up game engine inspired by LF2. Coming soon

A-Engine Dev Blog - Update #8: Timeout

Reply
Thanks given by:
#2
Unless I missed something, you aren't accounting for rotation which would further complicate your formula. If I were you I would just convert the ellipse to n-sided polygons and be done with it.

On a more helpful note, a quick google found this paper: http://www.dtic.mil/dtic/tr/fulltext/u2/a199654.pdf which looks quite interesting.
[Image: doty7Xn.gif]

10 ʏᴇᴀʀs sɪɴᴄᴇ ɪʀᴄ ɢᴏᴏᴅ.ɪ ᴡᴀʟᴋ ᴛʜʀᴏᴜɢʜ ᴛʜᴇ ᴇᴍᴘᴛʏ sᴛʀᴇᴇᴛs ᴛʀʏɪɴɢ ᴛᴏ ᴛʜɪɴᴋ ᴏғ sᴏᴍᴇᴛʜɪɴɢ ᴇʟsᴇ ʙᴜᴛ ᴍʏ ᴘᴀᴛʜ ᴀʟᴡᴀʏs ʟᴇᴀᴅs ᴛᴏ ᴛʜᴇ ɪʀᴄ. ɪ sᴛᴀʀᴇ ᴀᴛ ᴛʜᴇ sᴄʀᴇᴇɴ ғᴏʀ ʜᴏᴜʀs ᴀɴᴅ ᴛʀʏ ᴛᴏ sᴜᴍᴍᴏɴ ᴛʜᴇ ɢᴏᴏᴅ ɪʀᴄ. ɪ ᴡᴀᴛᴄʜ ᴏᴛʜᴇʀ ɪʀᴄ ᴄʜᴀɴɴᴇʟs ʙᴜᴛ ɪᴛ ɪs ɴᴏ ɢᴏᴏᴅ. ɪ ᴘᴇsᴛᴇʀ ᴢᴏʀᴛ ᴀɴᴅ ᴛʀʏ ᴛᴏ ʀᴇsɪsᴛ ʜɪs sᴇxɪɴᴇss ʙᴜᴛ ɪᴛ ɪs ᴀʟʟ ᴍᴇᴀɴɪɴɢʟᴇss. ᴛʜᴇ ᴇɴᴅ ɪs ɴᴇᴀʀ.ɪ ᴛʜᴇɴ ᴜsᴜᴀʟʟʏ ʀᴇᴀᴅ sᴏᴍᴇ ᴏʟᴅ ɪʀᴄ ʟᴏɢs ᴀɴᴅ ᴄʀʏ ᴍʏsᴇʟғ ᴛᴏ sʟᴇᴇᴘ.


Reply
Thanks given by: A-Man
#3
I've accounted for the transformations on the ellipse actually (tried it, and it worked!) on an earlier implementation. What we do is we have the function reverse the translation, rotation and shearing the transformed ellipse back to its standard form in the origin. After that, we simply apply these inverse transformations on everything else (which are lines; so no harm) accordingly. This problem would reappear though with the ellipseXellipse implementation, and this solution would not work. I guess I am just going to have to get the extended ellipse equation in the calculation :\. Didn't try implementing it yet, but I can't see a reason for why it won't work.

And thanks for the document! Will give it a read right away.
[Image: signature.png]
A-Engine: A new beat em up game engine inspired by LF2. Coming soon

A-Engine Dev Blog - Update #8: Timeout

Reply
Thanks given by:




Users browsing this thread: 1 Guest(s)