Hallo Pico People,
Loving it here. First post!
So i'm working on a 2D physics based collision engine.
...Imagine a whole bunch of polygons flying around, wrapped in AABBs (axis aligned bounding boxes)...
And I was wondering if this was a legit/efficient way to check if Two Edges/Line-Segments Intersect.
1. Treat them as AABBs and check if those overlap, is so keep the "resulting mini rectangle".
2. Treat them as Linear-Functions (infinite strait lines) and check if they are parallel, if NOT determine the resulting "point of intersection"
3. check if the "point of intersection" is inside the "resulting mini rectangle".
--return that point, otherwise abort
--do segments intersect? if so where? function segments(a,b) local r=overlap(to_rect(a), to_rect(b)) if(not r)return false local pt=intersection(a,b) if(not pt)return false if(in_rect(pt,r))return pt return false end
Lets assume the sub-functions (which I haven't included) are squeaky clean, its more about the idea...
Have to say it works a charm at the moment, even on weird concave polygons. But I could be going mad.
Any tips? Would it be easier on the CPU to use dot/cross product stuff? Am I missing something?
ps. here's a drawing
Have a look at Christer Ericson real-time collision detection book.
Or complete set of intersection algorithms: http://www.realtimerendering.com/intersections.html
Thanks freds72 :-> great resource!
EDIT: The Ray/Ray bit at the end seems to be the case, but it uses unit vectors and magnitudes which are costly (right?) if your sifting through tons of segment comparisons...
found a really good check for parallelism to kill the instance and save loads of tokens:
-> vectors are parallel if (vax)(vby)==(vbx)(vay), though that might not be uni-directional... haven't checked yet. (never happens with floats anyway)
EDIT:it is unidirectional (as in doesn't matter which was they go)
I use normals and dot products after narrowing it down with AABBs.
I hadn't thought of using the rectangle intersection to check if the intersection falls inside the line segment. Seems like a good trick.
Normals and DPs have the advantage that you don't have to check for parallel lines. You're essentially calculating how far on either side of the first line the start and end of the second line are. If both values are positive or both values are negative then the line segments don't intersect, which handles the parallel case plus some other cases as well. Plus you can use them to calculate the line-line intersection.
Here's a basic example.
I use a 2D vector metatable, as it makes the vector equations easier to read IMO.
I would still use AABBs first though. It's a cheap test and quickly discards a lot of cases. It may even help avoid numeric overflow cases, by only considering segments that are close to each other.
[Please log in to post a comment]