Gilbert-Johnson-Keerthi algorithm demo (2D)

WIP games, tools & toy projects Archived Projects
#1

I have been working on a 2D implementation of the GJK collision algorithm, and I now have an applet put together to demonstrate it. The applet can be found here. Let me know what you think. If you could share what sort of performance you are getting, that would be great. I will post the source code soon, once I get it cleaned up a bit.

Just as a note, the collision detection is intentionally naive (every object tested against every other object). This was to make it easier to stress the simulation.

#2

Nice!

I get around 250 objects before the object update time gets almost 95% and the fps goes down to 10. 280 objects give 2 fps and 99% update time.

#3

Ya, that’s around the point where the performance breaks down for my PC as well. 250 objects is roughly 3,100,000 collision checks / sec or about 31,000 per frame. Once I add in some broad phase collision detection, this should be fine for most games of moderate complexity or less. I need to try out some caching. If the last point of the simplex (for non-intersecting objects) is saved, you can start from there on the next iteration. This would allow you to eliminate most non-intersections in one iteration instead of two. It would also be very easy to multi-thread this because each check is independent of the others.

#4

Do you have any plans to add the Expanding Polytope Algorithm to the collision detection for interpenetrating objects?

#5

Yes. I would like to expand this enough so that it can be used for physics simulation where it’s useful to have a bit more information. I haven’t done enough research into EPA to implement that part yet, so it will have to wait.

#6

Are there any good tutorials or articles about this algorithm, since I have never heard of it before?

#7

There is a good video at the top of this page http://mollyrocket.com/forums/viewtopic.php?t=245. It discusses GJK in the 3D case where there is a greater benefit to using it. This page http://physics2d.com/content/gjk-algorithm has a good tutorial as well.

The GJK algorithm is commonly used for 3D collision detection. It is not used as often for 2D because SAT is about the same speed and less complicated. That’s not to say there is no benefits to GJK for 2D. My favorite thing is that you can test any two shapes you define a support function for. The collision detection algorithm doesn’t need to know anything else about the shapes or how they are stored.

#8

Minor correction: any two convex shapes, but you can decompose most complicated concave shapes into convex approximations, which is good enough for physics engines.

#9

Yes, the algorithm is intended for only convex shapes. If you correctly create your support function, it will actual define the shape of the tightest convex hull regardless of whether or not the shape itself is convex. Sort of an unusual property, but it could actually be useful for some situations.

There are some other interesting things that I am looking into. It may be possible that for a shape that is offset and rotated, to not actual need to transform the shape at all. For an offset shape you just add the offset to the returned support point, rather than offsetting all the points first. I am not entirely sure, but for a rotated shape you may be able to rotate the direction vector before asking for the support, then unrotate the returned point. Combining these two means you would never need to actually transform a polygon for example. This would be a big plus and would also open the opportunity to make some form of hashed support look-up for polygons because the geometry would be static. I am still working through some of this, but it seems like there is a lot more potential for optimization.

#10

I can get 260 objects at 60fps, but drops fast. But I see it only uses a single core so its only uses about ~15% of my cpu.

#11

I get 40fps with 300 objects - very sharp ramp there between managing and too much to handle.

Intel Core i5 650 @ 3.2 ghz (quad cpu)

#12

It is interesting how quickly the performance collapses. There is probably something else going on other than the CPU load. Maybe the memory bandwidth becomes the bottleneck or something with the JVM. I’m not going to bother digging to deep into this because with a good broad phase, it all becomes kind of irrelevant.

#13

Really nice! Can you really create custom shape easily and it will work ‘‘out of the box’’ with the physic engine? I wonder if it’s more flexible than other physics engine. Sometimes I feel kind of restrain by the physic engine so that I need to change all my code to match with it while I thought it would be nice if you could match the physics engine code to your game. Anyway that’s probably just me.

Btw, I keep 100 fps and 100 ups up to 300 objects. After that it drop.

#14

This is only collision detection right now, but one of the nice things about GJK is you just need to implement the support function to use any shape. From a code perspective, there is a Collidable interface with the getSupport function. Any two shapes implementing that can be tested for collisions. Once I add some real physics to this, a rigid body would contain a list of Collidables that define its area. It would then be strait forward to add a new shape such as a capped rectangle or ellipse or whatever. So in answer to your question, yes it would be easy to add a new shape. Changing other aspects of the physics would as usual be more difficult.

#15

For concave shapes, you can just divide them into convex pieces and test each one!

#16

Oh I thought there was already a bit more than just collision detection from your demo. You not only detect but react to the collision too. What information do you get when you have a collision to help you decide how to react to that collision?

#17

I am just maintaining the velocities. I add an vector pointing to the center of the screen to each object’s velocity, and if two objects are intersecting I push their velocities apart. Basic rigid body physics is the easy part. I already have a class for that, just didn’t use that here for some reason. The hard part of physics is satisfying constraints.

#18

I can only go to 150 shapes before the fps drops. I had 800 shapes @ 3 fps though…