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.
Quote this message in a reply
DoG
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 Blink

- D.G
Quote this message in a reply
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?
Quote this message in a reply
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.
Quote this message in a reply
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.
Quote this message in a reply
Mars_999
Unregistered
 
Post: #6
Can you say calculus!! 12x^4 = 48x^3!!!!
Quote this message in a reply
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...

∂∕∂x 12x⁴ = 48x³

12x⁴ = 48x³ ⇔ x = 4
Quote this message in a reply
Mars_999
Unregistered
 
Post: #8
Quote:Originally posted by OneSadCookie
I'm glad I didn't do calculus where you learnt it...

∂∕∂x 12x⁴ = 48x³

12x⁴ = 48x³ ⇔ x = 4


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

[Image: stupid_derivative.gif]

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:

[Image: incorrect_expression.gif]

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!
Quote this message in a reply
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. LOL

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.
Quote this message in a reply
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. LOL


"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!
Quote this message in a reply
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 Blush

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...

¾œǟɚ˦ζЖאكฏ༃ᄒᡴẘὭ‱ⁿ₪№Ↄ↩∢⌦⓰╪▓◈♨❦⤵⦾⫨⻭⽔⿸〄ぷプㄍㅹ㆕ㇿ㈯㌫㐱乞ꀎ꒲걍論שּׁﭻ﹅﹡ﻬ⦅�����
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #13
Back to topic...

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
Quote this message in a reply
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.
Quote this message in a reply
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. Smile

<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>
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  2D Pixel Collision Detection using OCCLUSION Elphaba 0 3,369 Jun 8, 2009 06:30 AM
Last Post: Elphaba
  Hierarchy, gluProject and collision detection lemtoo 3 4,729 Nov 30, 2007 09:26 AM
Last Post: lemtoo
  multi-level collision detection alert 0 1,776 Apr 7, 2005 10:27 AM
Last Post: alert
  Quad Collision-Detection Duane 5 5,366 Jan 18, 2005 01:42 PM
Last Post: Duane
  Collision detection problems CarbonX 6 3,827 Sep 5, 2004 01:08 PM
Last Post: Tasnu Arakun