Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Pierre Terdiman, posted on October 09, 2000

Image Description, by Pierre Terdiman

Collision fun in cube hell :

This is a little demo of my collision detection library, called Z-Collide. First of all, I guess the pic will get reduced, and you may not see what's going on here. So have a look at the original screenshot:

The upper left image contains 10000 cubes ready to be tested against the collision detection module, down to the triangle level, and including closest points computation while we're at it. No fear.

The upper right image shows 4096 of them in the worst possible scenario: randomly placed within a unit cube, colliding in all possible ways. The profiler keeps track of what happens at various levels and reports the number of cycles it takes to do the job.

The lower left (pretty confused) image shows the same kind of situation, with AABBs (Axis-Aligned Bounding Boxes) turned on. Green boxes are not colliding. Yellow boxes are colliding, not the actual cubes. Red boxes are colliding, and the cubes within as well.

The last image focus on a single pair. A white segment is drawn between two user-selected cubes, reporting their closest points, exact distance, and the contact manifold (Point-Point, Edge-Edge, Point-Face, etc). That contact manifold is very important for collision response, when the collision detection library is used as the heart of a rigid body simulator.

You can download the demo:
The included readme file contains some more technical information.

On my Celeron 500 / GeForce / W98, it runs at 60~80 fps for 1024 cubes (which would need one million intersection tests with a naive O(n^2) way). Needless to say, the framerate drops for 10000 cubes (2~10 fps).

Of course, the lib works for arbitrary models, not just for cubes :)



Image of the Day Gallery


Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
Isaack Rasmussen

October 09, 2000, 02:43 PM

Damn nice Pierre!

Do you have a fast colisiondetection routine, or is it your culling scheme that is just quite effective? For it seems as it is damn fast.

I guess that one day, I'm probably gonna bug you... pleading you to tell me how you are doing it.

Nice, nice,



October 09, 2000, 03:06 PM

How does your profiler work? Do you make some call to the profiler inside each function (or before each function call) to tell it that it is being executed now?



October 09, 2000, 05:57 PM

Very nifty. What do the percentages tell you that the profiler produces? I noticed they add up to more than 100%.



October 09, 2000, 06:38 PM

for simple FOV, do you use the fact that your FOV is 90 degrees?
or it's not?

Because if it's 90 degrees simpler check can be made.

and wrong me for the bad english,

Pierre Terdiman

October 09, 2000, 06:39 PM

This is a demo of a collision detection library, so yes, I hope that part is fast :) The culling is actually quite slow (not too much, but I didn't particularly try to optimize it).

The profiler works like rdtsc since that's just a rdtsc wrapper. Call it once before, call it once after, it keeps track of the number of elapsed cycles, the recursion level, etc.

They add up to more than 100% because the percentages of a given recursion level (the indented texts) sum to 100% as well, i.e. they're relative to the previous level. For example:

Collisions (50%)
Sweep&Prune (40%)
Exact collisions (60%)

Here the collisions take (50%) of the total time, and the sweep&prune takes 40% of those 50%. The whole collision-time is divided between the two subtotals.

Sorry, hope it's a bit clearer :)


Pierre Terdiman

October 09, 2000, 06:41 PM

Hi Malkia,
No I don't use anything special for a 90 degrees FOV... See, that's a collision detection demo, not really a culling demo :)

And anyway you can change the FOV with the up & down arrows, so it wouldn't be terribly useful.

Graham Gibbons

October 09, 2000, 07:02 PM

I'm having a little problem with your demo. If I click on any of the cubes the program performs an illegal operation. I think it might be that I have a Voodoo running in 16 bit but I dunno. lala well I wanna see it so help me out here.


October 09, 2000, 08:05 PM


Looks pretty okay :)

Just wondering what your collision-detection order is..

Do you keep a collision-list for each axis ?
(register in- and out-going collisions for each axis, and only process those that collide in all three ?)

do you first check for axis-aligned bounding boxes, then for oriented, then..?

does your collision-scheme require a specific volume-description
(ie. BSP/octree/whatever for the final poly-poly-detection ?) - or is it generalized in some abstract volume-class ?

and finally - collision-detection is one thing... but are you planning for correct physics / collision-handling after you've detected the collisions..?
(The latter seems more important to me than the actual collision-detection itself :))




October 10, 2000, 02:23 AM

Looks nice, but how about using bounding-spheres, so you have to calculate lesser coordinates, only the center and the radius instead of every side of the bounding-boxes. Give it a try, its much faster!

Pierre Terdiman

October 10, 2000, 03:02 AM

Err... I'm afraid I have no idea what could be wrong with Voodoo cards, I don't have one for testing, and they have some severe limitations, so it could be just anything... That's very weird anyway, since clicking on a cube doesn't do any nasty things. I guess that's a real bug.... :(

Did you look at the readme file? The collision order is a standard broad-then-narrow phase order. I don't use 3 lists since (as noted by David Baraff) that's just slower than a single one. So I use a single one, but the sorting axis can be different from one frame to another. I check for AABB, then for exact collisions using either an OBB tree (useless for a single cube), either a separating vector algorithm, either GJK. Hence you need some specific volume description indeed, but the actual data depends on the collision method: an OBB tree or the list of valencies of the mesh.

Of course the next part of the story (physics, etc) is planned as well, that's why I'm speaking about the contact manifold in the image description. But the collision actually is, most of the time, the weakest part of the physics-chain. (as reported by many many papers related to rigib body simulation) ...sure, it does not mean resting contacts are a piece of cake nonetheless...

I support bounding spheres as well, certainly. But in that particular sample, a sphere is a pretty bad BV, of course. Generally speaking anyway, you can do a lot of great things just using spheres, and for many games that's just the way to go: cheap, fast, efficient, reliable.



October 10, 2000, 04:37 AM

Ahhh, the famous collision hell :) These look more colourful than the screenshots you posted to the [algorithms] list. I was very impressed with this. Once you add some cool physics (would love to see the cubes gravitating towards something and bumping into each other)

By the way, I think tabulating your profiler output would be a very cool way to go. This would visually clarify the information a bit. Although, it does sound too much like a programming principles lecture :)

Pierre Terdiman

October 10, 2000, 05:46 AM

Yeah, I'm working on it:)
The profiler output actually *is* tabulated, but not enough apparently...

This thread contains 12 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.