## the best way to do collision detection

ghettotek
Unregistered

Post: #1
right now im using the basic point-radius method of defining bounding spheres for collision detection. im only doing this because i havent had time to study all there is on more efficient collision detection methods. i was just wondering: iyho, what is the best way to do collision detection? i just need something basic (not too basic, like the method im using), but fast and reliable and relatively easy to implement with Obj-C.
Moderator
Posts: 869
Joined: 2003.01
Post: #2
You might want to try some space partitioning method like binary space trees or octrees to speed up things. Or be a little more specific about what you are looking for

- D.G
Feanor
Unregistered

Post: #3
This topic is probably too complicated for this forum. The few people (not me) who have implemented collision detection might be able to argue its fine points, but I doubt one could describe a strategy in much detail to beginners. I have read a couple of papers on Gamasutra and the like.

There are two main types of collision detection (not counting mathematical intersection tests, of which there are many). One is to check for intersections regularly, and the other is to do what I call predictive, where to calculate paths of moving objects and test those paths (or volumes around those paths) for intersection. It is slow to check two moving paths, and np to check n moving paths.

DoooG's point, if I interpret right, is that you can't do efficient intersection testing until you figure which possibly intersecting objects are close to each other in the first place. That is why you want space partitioning. Fortunately, space partitioning has other uses, like visibility determination, and I believe that you should be able to use similar data structures to accomplish both tasks.

Managing a space partition is a complex job. I am working on something that will need to do this, so I hope to do some more reading and write some test code over the next few months.

ghettotek, what sort of environments are you objects in? Rooms, terrains, or outer space? Something unique? A combination?
ghettotek
Unregistered

Post: #4
i dont know what exactly it is im going to be using in my scene, i guess im just trying to make a demo for myself for further reference on how to do all these things. i was looking more into the type of collision detection involved with terrain (or something like that), keeping objects moving along the faces of the terrain, and things of that sort.
Member
Posts: 177
Joined: 2002.08
Post: #5
"How do I do collision detection?" depends far too much on how you are storing and describing the shapes you want to collide, as has been said.

If you really are early in the design stage and really don't want to deal with the math, you should consider finding a free collision framework you could drop in and design the rest of the physics around.

In general, collision detection is much easier if you can express your objects mathematically (sphere, point/ray, infinite plane, etc) rather than a collection of arbitrary bounded polygons, and as Doog said you should do everything possible to avoid having to check the entire world.
Mars_999
Unregistered

Post: #6
Can you say calculus!! 12x^4 = 48x^3!!!!
Luminary
Posts: 5,143
Joined: 2002.04
Post: #7
Quote:Originally posted by Mars_999
Can you say calculus!! 12x^4 = 48x^3!!!!

I'm glad I didn't do calculus where you learnt it...

&#x2202;&#x2215;&#x2202;x 12x&#x2074; = 48x&#x00b3;

12x&#x2074; = 48x&#x00b3; &#x21d4; x = 4
Mars_999
Unregistered

Post: #8
I'm glad I didn't do calculus where you learnt it...

&#x2202;&#x2215;&#x2202;x 12x&#x2074; = 48x&#x00b3;

12x&#x2074; = 48x&#x00b3; &#x21d4; x = 4

???? You don't understand derivatives? Thats the power rule. dy/dx = nx^n-1 So 3x^2 = 6x
Member
Posts: 145
Joined: 2002.06
Post: #9
just to clarify, we're all talking about:

right? (there's only one variable in play so it's not a partial derivative ala OSC's notation.) Because Mars 666's original expression:

has nothing to do with calculus.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Feanor
Unregistered

Post: #10
Why did OSC use the partial derivate symbols? Does it work out the same if there is only one variable? I failed those, man, and have to find time to go back and learn them properly. I'm a logic guy. Numerical methods are so messy, with their approximations, but I want to know them better. My Calculus II prof was too nice to look at, and I did not pay enough attention. And, having a nice accent, she said FACtorial in a distracting way.

inio, you went to a lot of trouble to make a point? Or do you have some cool program that does math that you can print to PDF or something with? Anyway, give the guy a break, I knew what he was talking about, even if he wrote it wrong. This isn't a test, is it?

On with collision detection. Who is recommending using a library? Mark Levin. ghettotek wants to learn some new ideas. You could at least word it differently: "You might consider ... ", but why not be encouraging? That's what iDevGames is about.

If you are just testing an object on terrain (assuming we have terrain and objects working fine), you can probably avoid a visibility graph (like a quadtree) and just do some standard geometry. Most terrains use a uniform x-z grid, so you can find the triangle(s) over which the object is positioned based on its x and z co-ordinates, and either its bounding shape or or its lowest y value. Either way, on steep slopes it will either end up looking like it is floating above the surface, or partly under it. I recommend not using a bounding sphere in this case, but something with a flat bottom, like a box or cylinder, or just a point.

Once you find the triangle(s), you should be able to just intersect either one or some set of points (e.g.: the lower corners of an axis-aligned bounding box) with the planes of those triangles. Create a height variable, initialized to a high number. Subtract the y value of the plane directly under one point from the y value of the point. If it is less than the height variable, reset the height variable to the new value. Do that for each point-plane vertical distance. When you're done, subtract the height value from the y value of the object.
Member
Posts: 145
Joined: 2002.06
Post: #11
Quote:Originally posted by Feanor
Why did OSC use the partial derivate symbols? Does it work out the same if there is only one variable? I failed those, man, and have to find time to go back and learn them properly. I'm a logic guy. Numerical methods are so messy, with their approximations, but I want to know them better. My Calculus II prof was too nice to look at, and I did not pay enough attention. And, having a nice accent, she said FACtorial in a distracting way.

"partial derivative" are just a fancy name for treating the other variables as constants. The slightly different symbols just are a reminder.

Quote:inio, you went to a lot of trouble to make a point? Or do you have some cool program that does math that you can print to PDF or something with?

MS Office V.x Equation Editor, copy and pasted into photoshop (creates really nice HUGE anti-aliased text when pasted into photoshop), with my standard drop shadow filter applied and a quick transparent save to web. (I have macros set up specifically for preparing images for posting to this forum, with it's background color). I'm more impressed by OSC's Unicode stuff. How'd you do that?

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Luminary
Posts: 5,143
Joined: 2002.04
Post: #12
The partial derivative symbols were simply ignorance on my part (oops); I never did very advanced calculus. I think someone might have mentioned once that there was such a thing as a partial derivative

As for the unicode, I just used the Jaguar character palette (from the keyboard menu, turn it on in System Preferences) to find the characters. The character palette tells you the unicode hex value, so you can enter the XML hexadecimal entities (&#x****; ) by hand, but I have a little service I wrote which maps command-shift-e to "entityize", replacing non-ascii characters with the appropriate entities. Email me if you want it or the source...

&#x00be;&#x0153;&#x01df;&#x025a;&#x02e6;&#x03b6;&#x0416;&#x05d0;&#x0643;&#x0e0f;&#x0f03;&#x1112;&#x1874;&#x1e98;&#x1f6d;&#x2031;&#x207f;&#x20aa;&#x2116;&#x2183;&#x21a9;&#x2222;&#x2326;&#x24f0;&#x256a;&#x2593;&#x25c8;&#x2668;&#x2766;&#x2935;&#x29be;&#x2ae8;&#x2eed;&#x2f54;&#x2ff8;&#x3004;&#x3077;&#x30d7;&#x310d;&#x3179;&#x3195;&#x31ff;&#x322f;&#x332b;&#x3431;&#x4e5e;&#xa00e;&#xa4b2;&#xac4d;&#xf941;&#xfb2c;&#xfb7b;&#xfe45;&#xfe61;&#xfeec;&#xff5f;&#xfffd;&#xd840;&#xdc0b;&#xd87e;&#xdc2c;
Moderator
Posts: 869
Joined: 2003.01
Post: #13

As far as I can tell, the collision detection ghettotek is looking for is of the discrete type, just evaluating current positions of the objects in a scene, not considering their paths. In this case, you have split the problem into space partitioning, mesh partitioning, and eventually triangle to triangle intersections, which are easiest done as triangle/edge intersections, imo.

Furthermore, you might want to think about if you need to evaluate the exact collision point and surface normals, or just if two objects collided. The first you would need an a physics collision, where you want to calculate some kind of collision response, the second you would use for things like visibility determination, ray casting for the AI, view culling, etc.

If you only want to improve the bounding sphere method, you need to look for an algorithm which makes a the bounding sphere a tighter fit, or even an optimal fit.

Also, in case you haven't yet, make a bounding tree for successively smaller groups of triangles, as a first step towards space partitioning.

OT again: I am trying to write some documentation with TeX, does anyone know how to do nice code typesetting with it?

/ D.G
Member
Posts: 78
Joined: 2002.06
Post: #14
Collision detection is:
not too hard, for points and fixed planes
hard for solid objects that can rotate
very very hard for all different shapes in a moving environment
impossible to do well for all situations

I'd suggest if you want to do more that the first item then use some one elses code. I'd use ODE http://opende.sourceforge.net/ you build callbacks for when collisions happen, it's fairly well designed. It can't do any shaped bodies, but it can do cuboids and a few others. Takes a while to get the hang of it. There are also a few others http://opende.sourceforge.net/junk.html. There are also a few just plain collision detection engines lying around in places but they are usually extremly complicated.
Feanor
Unregistered

Post: #15
Quote:Originally posted by willThimbleby
I'd suggest if you want to do more that the first item then use some one elses code.
... except that said he wanted to know more about how to do it. He can't learn very much by employing someone else to do it for him. Links duly noted, however.

<offtopic>OSC, that's a use for the Character Palette I hadn't thought of. Kind of tedious, though. Also, all the cool old school Mac option characters aren't available, since they aren't unicode compliant or something, although they were all useful in a way the bullets and such in unicode are not.</offtopic>