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".
-->otherwise abort

2. Treat them as Linear-Functions (infinite strait lines) and check if they are parallel, if NOT determine the resulting "point of intersection"
--otherwise abort

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?

Luv, Phume

ps. here's a drawing

P#82711 2020-10-08 18:34 ( Edited 2020-10-08 19:58)

1

Have a look at Christer Ericson real-time collision detection book.
Or complete set of intersection algorithms: http://www.realtimerendering.com/intersections.html

P#82717 2020-10-08 19:05

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)

cheers!

EDIT:it is unidirectional (as in doesn't matter which was they go)

P#82718 2020-10-08 19:19 ( Edited 2020-10-09 22:02)
1

Pbly the most complete/fastest physic engine on pico:
https://github.com/jamesedge/pico8-physics
There is a lot more for collision detection than just checking ray/ray intersection !

P#82729 2020-10-09 06:02
1

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.

P#82735 2020-10-09 10:48

Hi Mot,

your approach might be a good step after my AABB check, though the AABB might be overkill.

Would you mind sharing an example snippet?

ps. for parallel lines the code i posted in the comment above seems solid, pretty elegant :->

P#82749 2020-10-09 22:04 ( Edited 2020-10-09 22:05)
1

Here's a basic example.
I use a 2D vector metatable, as it makes the vector equations easier to read IMO.

Cart #mot_linesegintersect-0 | 2020-10-10 | Code ▽ | License: CC4-BY-NC-SA
1

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.

P#82770 2020-10-10 12:12

@Mot. Wow thanks!

Yeah I'm using Vector Metatables too, totally agree. no worries.

Might use this instead now because I'm using chains of points as lines to refine the initial AABB collision, where most will AABB positive as lines anyway.

Cheers!

P#82783 2020-10-10 20:25