the best way to do collision detection
right now im using the basic pointradius 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 ObjC.
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
 D.G
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?
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?
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.
"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.
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: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: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^n1 So 3x^2 = 6x
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.
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 GrayHat
Bring Alistair Cooke's America to DVD!
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 xz grid, so you can find the triangle(s) over which the object is positioned based on its x and z coordinates, 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 axisaligned 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 pointplane vertical distance. When you're done, subtract the height value from the y value of the object.
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 xz grid, so you can find the triangle(s) over which the object is positioned based on its x and z coordinates, 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 axisaligned 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 pointplane vertical distance. When you're done, subtract the height value from the y value of the object.
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 antialiased 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 GrayHat
Bring Alistair Cooke's America to DVD!
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 commandshifte to "entityize", replacing nonascii characters with the appropriate entities. Email me if you want it or the source...
¾œǟɚ˦ζЖאكฏ༃ᄒᡴẘὭ‱ⁿ₪№Ↄ↩∢⌦⓰╪▓◈♨❦⤵⦾⫨⻭⽔⿸〄ぷプㄍㅹ㆕ㇿ㈯㌫㐱乞ꀎ꒲걍論שּׁﭻ﹅﹡ﻬ｟�����
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 commandshifte to "entityize", replacing nonascii characters with the appropriate entities. Email me if you want it or the source...
¾œǟɚ˦ζЖאكฏ༃ᄒᡴẘὭ‱ⁿ₪№Ↄ↩∢⌦⓰╪▓◈♨❦⤵⦾⫨⻭⽔⿸〄ぷプㄍㅹ㆕ㇿ㈯㌫㐱乞ꀎ꒲걍論שּׁﭻ﹅﹡ﻬ｟�����
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
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
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.
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:Originally posted by willThimbleby... 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.
I'd suggest if you want to do more that the first item then use some one elses code.
<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>
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
2D Pixel Collision Detection using OCCLUSION  Elphaba  0  4,146 
Jun 8, 2009 06:30 AM Last Post: Elphaba 

Hierarchy, gluProject and collision detection  lemtoo  3  6,309 
Nov 30, 2007 09:26 AM Last Post: lemtoo 

multilevel collision detection  alert  0  2,421 
Apr 7, 2005 10:27 AM Last Post: alert 

Quad CollisionDetection  Duane  5  7,169 
Jan 18, 2005 01:42 PM Last Post: Duane 

Collision detection problems  CarbonX  6  5,027 
Sep 5, 2004 01:08 PM Last Post: Tasnu Arakun 