2D Collision Engine - Performance Test

Performance Tuning
#1

Hello,

So I’ve seen many users struggling about collisions or faster implementation of it. And i’ve also seen that almost everyone creates a custom engine that best suits their need. So i came up with the idea of providing a fast collision api, so every time people write their engine they can skip this part of the process, but it also provides support for many other things like Curves, Line, Segment, handles rotation, any polygons, circles, rectangle… Which allows you to do raytracing, or draw from the shape i created by getiing a list of points and many other things.

I’m still working on it. Yet i have implemented Line, Segment, Circle, Rectangle, Polygon, RegularPolygon (optimized polygon), Vector, Point and also a FastMath class that i built with the code that i found here ( mainly Riven’s code so thank you ). Only detects collision for now. Almost everyting is documented.

So here’s the link to the lib : https://www.dropbox.com/s/d8692tv9rw3alhe/leSpace2D.jar?dl=0 ( Source code is included, i implemented SAT from another thread which i can’t find back haha)

Then what’s the problem ? Hum i have a really decent processor i7 - 4 cores and i’d like to know the speed of the algorithm on your computer.

Here’s a link to the test class i used : http://pastebin.com/0f5cELmu

Here’s my output using Circle (longer to create but faster for collisions) ( Intersection calls : 12.5 x 10^8; Contains call : 25 x 10^8 ):


USING 50 000 ENTITIES
[INSTANCIATION] Done in 409 ms.
[INTERSECTION] Done in 8 892 ms. With 212 587 696 shape(s) intersection.
[CONTAINS] Done in 24 641 ms. With 35 814 199 shape(s) inside over shapes.

Here’s my output using Rectangle : ( Intersection calls : 12.5 x 10^8; Contains call : 25 x 10^8 )


USING 50 000 ENTITIES
[INSTANCIATION] Done in 14 ms.
[INTERSECTION] Done in 132 767 ms. With 895 420 123 shape(s) intersection.
[CONTAINS] Done in 129 783 ms. With 172 029 124 shape(s) inside over shapes.
#2

So i’ve found some workaround to speed up the rectangles intersection check by about 8%. To do this i’ve simply created a new method for my shapes to project them on one of their edge.

But any idea about any workaround to do not check all points of a convex polygon to project it on a specified line ?

Or any idea on the fastest implementation about simply projecting a polygon onto a specified point ?
I am currently iterating through all the points. May be i should cache their projection ?

[EDIT]
Caching as i’m talking improves performance by 30% for rectangles, but apparently i got some issue as it appears to only detect 3x10^8 intersections instead of the standard 8x10^8.

Note : i’m asking about projection because it represents half the time of the execution time of my method.

#3

Writing general collision libraries is certainly tempting, but it’s kind of a deep rabbit hole. For one thing, collision detection problems are often highly context-dependent, and bespoke implementations can sometimes exploit context in a way that generic solutions can’t. Also, numerical issues can make implementing robust collision code difficult, and it’s really easy to miss corner cases even if you know what you’re doing. I’m sure you already know all that, but I guess I’m just saying it’s all pretty non-trivial.

Anyway, I looked through the code a bit and was wondering, is the ‘Polygon’ class supposed to be convex-only? Or is it intended to represent non-convex polygons as well?

Also, can you clarify what you mean by projecting a polygon onto a specified point?

#4

Yes you’re right. But if i share the source code with it then you can take the part that’s interesting for you or/and adapt it.

Also you should be aware that i difference points and vectors.

Currently the ‘Polygon’ class is for convex polygons only. I’ll have to implement one with an Origin Point and vectors describing it, if this is the other implementation that you thought of ?

So i have a normalized direction vector of a line, ( we only need the direction vector as 2 parrallel lines would give the same result in our case), and a list of points representing a convex polygon. What i mean by projecting it is the orthogonal projection of a polygon on a line.

( Wikipedia link with illustrations: https://en.wikibooks.org/wiki/Linear_Algebra/Orthogonal_Projection_Onto_a_Line I currently )

[EDIT]
I found the issue with caching which was really stupid. And it’s even faster.

#5

Sure, I understand that. I was just asking because you mentioned projecting the polygon onto a point, but maybe you meant line.

[quote]Currently the ‘Polygon’ class is for convex polygons only.
[/quote]
Ok, I’ll just mention one thing I noticed. Although I haven’t examined it carefully, it looks like your contains() function for polygons uses some form of the generalized ‘edge crossing’ algorithm for point-polygon containment. Is that correct? If so, it seems like for convex polygons you’d want to instead use a simple hyperplane test (that is, check to see if the point is ‘inside’ all the bounding hyperplanes for the polygon), as that’s likely to be simpler and more robust.

Also, are you sure this loop:


        for (int index = vertexes.size() - 1; index-- > 0;)
        {
            final Point cur = getVertex(index);
            final Point next = getVertex(index + 1);

Is correct? It seems like this would always miss one of the polygon edges.

#6

That iss what i meant.

That’s correct, to check if a point is inside a polygon i use the winding number algorithm. Thank you for pointing this solution, i’ve not yet studied hyperplane so i’ll learn about it.

Thanks for pointing this out, i already fixed some missing edges in ‘for’ loops but i forgot those in the ‘Polygon’ class, which i have fixed now. The lib is up to date now.