Poly->Poly Collision Challenge

[jdarling]

Its been a long time since we have seen any challenges on this board, so I figured what the hell time for another one. The goal is simple, given 2D arrays of points that represent polygons (could be convex or concave) tell if they collide or not.

Method prototype:
[code=delphi]
type
TColPoint = packed record
x, y : single;
end;
function colPoly(const o1x, o1y, o2x, o2y : single; const pts1, pts2 : array of TColPoint) : boolean; inline;
begin
end;
[/code]

Notes:
o1x, o1y - World position of poly 1
o2x, o2y - World position of poly 2
pts1 - Points array for poly 1
pts2 - Points array for poly 2
* Don't assume that pts[length(pts)-1] is the same as pts[0] it may or may not be

Rules:
1) Only use existing FPC/Lazarus/Delphi libraries that ship with the compilers (Math, SysUtils, etc... though they shouldn't be needed)
2) Don't submit someone elses work

UPDATE:
Ok, a quick test harness and a (very bad) example are posted at: http://www.eonclash.com/PGD/testpoly.zip

[User137]

Is this a competition or lookout for hints/code?
You propably aim to find a function fast enough for realtime game? I can think of at least 2 solutions:

Common for both solutions at first:
- Rectangular check for min/max of both polygons, see if their bounding rectangles collide. This will speed up the program by eliminating distant ones.

1) Check line-line intersection for each edge in both polygons. Accurate but you need extra measures to check if other polygon is inside.

2) Virtual pixel map. You can "draw" both polygons (filled can be trickier unless you use something ready like propably slow TBitmap) on a 2 dimensional array and stop "drawing" on first pixel that overlaps. The bigger the resolution the slower it gets but the rougher the bordering areas are.

[jdarling]

It seems like every now and again we see a common question come up around the boards. Over the years (as I said its been a while) we have had little code snipit competitions (no real winners) and I thought this would be a good one. The solution I provided will work and works fairly quickly. So, its just a little bit of fun more than anything.

Collision detection always comes up in games, circle->circle, circle->segment, point->poly, and segment->poly (thus circle to poly) are fairly simple to implement in an extremely fast routine. Poly->Poly both convex and concave on the other hand takes some serious thought and math (in many cases). So, what better

The "best" solution I've seen (and one I've implemented myself if you look around) is tracing one shape onto another shape (can be pre-calculated) and then using distance to see if there is a collision. Its extremely fast and accurate, has the added advantage of being able to easily be modified for use over time shifts too . But its WAY outside the scope of this.

- Jeremy

[Ingemar]

I think this is a thread that was worth a better destiny than dying after three posts.

The topic of collision detection is complex with several levels and different possibilities depending on context. Like, do we know the result of the previous collision test between the two shapes? There is SAT (which I would call "separating planes"), there is GJK, you can do straight polygon/polyhedra intersection, and you can demand the shapes to be convex or not.

Was this supposed to be 2D only? Isn't that to aim a bit low? OTOH, as a "challenge" the 3D case is a bit complex.

[code_glitch]

With some of my latest experimentation I could 'cheat':

1) Using a FBO, set output to texture A and draw the first object
2) Again with a FBO, set the output to texture B and draw the second object (your poly)
3) Blend the two with difference blending - given the right colours, you get a pattern of where they overlap if they overlap at all.
4) Scan for the pattern and voila - pixel perfect collision detection with openGL Hardware acceleration.

Its 'cheating' in this forum but in my mind should work - my main problem is getting the FBOs to work correctly with blending (almost done 100% accurately) and finding a fast way to scan for said overlap colour (which is why I am reading through a 600 ofdd page book on OpenGL) Just my 2 pence on this problem...

[Ingemar]

Its 'cheating' in this forum but in my mind should work - my main problem is getting the FBOs to work correctly with blending (almost done 100% accurately) and finding a fast way to scan for said overlap colour (which is why I am reading through a 600 ofdd page book on OpenGL) Just my 2 pence on this problem...

Is it cheating, really? I would call it image-based collision detection. Not bad for 2D collision detection, except that the scanning of the image for the result isn't so easy to do on the GPU.

[code_glitch]

@Ingemar:

isn't so easy to do on the GPU.

And that would be the challenge in this method. And it is cheating in the sense that it is in the physics and advanced math forum and my implementation shamefully uses Prometheus code in areas where I am too lazy to go back into OpenGl (although it could just use gl)...

@Phibermon:
Or if you broke up the collision detection into segmens and scanned those for even a single pixel you could use that to get 'pixel perfect' to the nearest group of pixels depending on hardware

And with a velocity variable, you'd be all set to go as to where the collision is from with some simple math from the near centre of the colision pixel group - of course that would use up a lot of cycles but would yield an accurate result.

[User137]

Instead of GPU you can also draw the collision test polygons in TCanvas, for example of a TBitmap. You can still draw them on GPU to for the looks but like said, it's propably not fast to read the results from it. And if you draw to GPU they need to be convex.

Overall, unless the polygons consist of hundreds of vertices, the math way will propably be more efficient.

edit: For the math way, if it's ruled that polygon must be convex, then isn't the only scenario such that at least 1 vertex must always be inside other polygon? I recall reading of doing this test with just dot product.

[Lazarus68]

Seems to me that because the computer only uses ones and zeros the fastest way to detect a collision would be to filter the polygons with XOR but I'm kind of a newbie on pascal programming, I used to program a bit of assembler on the commodore 64.

Oh, hello everybody.