3D Theory - Collision Detection

http://www.euclideanspace.com/threed/animation/collisiondetect/index.htm

by octopus • 15 years ago

37 9 15 years ago

rflrob• 15 years ago

> For example if we have 'n' objects then the first object could collide with n-1 objects (since we don't check if an object has collided with itself) the second object could collide with (n-2) additional objects not counting the possible collisions we have already counted. If we keep going like this we get the number of possible collisions is: (n-1) * (n-2) * (n-3) ... 1 This is equivalent to n! / 2! * (n-2)!

Seems to me like it should be more like the handshake problem, which comes out to n * (n-1)/2. n^2 is still bad, but not nearly as bad as n!.

revolvingcur• 15 years ago

Yeah, that analysis is egregiously wrong: the terms should be summed instead of multiplied. The correct complexity is O(n^2).

IvoDankolov• 15 years ago

Actually, n! / (2! * (n-2)!) comes out exactly at n * (n-1)/2. It's just one form of the general formula for combinations.

However, multiplying the possible situations is, of course, wrong. A case of a wrong explanation of the final result I'd imagine (permutations instead of combinations),

newobj2• 15 years ago

Hrmm. For some reason whenever graphics/game programming related articles get posted on HN, the quality seems to be ridiculously low. For example, no discussion of discrete vs. continuous, temporal coherence, sweep and prune, separating axis, etc. I think even if you assume this article was written in 1998 it still strikes me as a bit behind the times. The fact that this article has 15 points at the moment is disturbing...

Entlin• 15 years ago

Why don't you post a better article?

jgh-• 15 years ago

Why doesn't Octopus just stop posting horrible articles and whenever people point out how horrible the articles are, why don't other stop telling them to post something better?

In other words, STFU GTFO.

newobj2• 15 years ago

Because I haven't been involved in game development professionally since 2002. Even though my knowledge is now 9 years out of date, I know that this article is low quality.

Jach• 15 years ago

That's a sign you should submit better articles or write them yourself (then submit). If you have a bunch of links handy why not post them here as well?

When I learned about sweep and prune I was amazed at how simple and obvious it should have been, but I don't recall the first books I read on game programming ever mentioning it, I'd hope a book dedicated to collision detection topics would but I don't own one.

chipsy• 15 years ago

The quality of most such articles really is extremely low. Apart from a few books from experts like the Ericson "Real-Time Collision Detection," and the codebase for open source engines, public knowledge about this stuff is basically missing from the Web.

At least these days there are good books. Ten years ago, AFAIK, your best options for the cutting-edge concepts were GDC session notes and academic papers.

3D Theory - Collision Detection

Related Stories