the best way to do collision detection

[ghettotek]

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.

[DoG]

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

[Feanor]

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]

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.

[Mark Levin]

"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]

Can you say calculus!! 12x^4 = 48x^3!!!!

[OneSadCookie]

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

[Mars_999]

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

[inio]

just to clarify, we're all talking about:

http://www.inio.org/~inio/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:

http://www.inio.org/~inio/incorrect_expression.gif

has nothing to do with calculus.

[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:

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.

[inio]

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.

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?

[OneSadCookie]

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

¾œǟɚ˦ζЖאكฏ༃ᄒᡴẘὭ‱ⁿ₪№Ↄ↩∢⌦⓰╪▓◈♨❦⤵⦾⫨⻭⽔⿸〄ぷプㄍㅹ㆕ㇿ㈯㌫㐱乞ꀎ꒲걍論 שּׁﭻ﹅﹡ﻬ｟�����

[DoG]

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

[willThimbleby]

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]

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>

[Mark Levin]

Originally posted by Feanor

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.


I meant the operative word there to be "consider". I don't mind if he considers it and then decides I'm totally wrong :P

And besides, having some source lying around that's proven to work for the same task can be an invaluable learning tool even if it's not used directly in the program in question.

[willThimbleby]

Originally posted by Feanor
... 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.

Noted in that case if you want to learn more about it, which is very worth while even if you end up using someone elses code, as you will have an idea of how it works.

Have a look at these:

http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.flipcode.com/tutorials/tut_collision.shtml

There as some good bits here as well, although they concentrate on the physics.

http://www.d6.com/users/checker/dynamics.htm

Actual collision detection is usually tied very much to the pyhsics engine you use. If you want actual algorithms to tell if something is hit then I can give you them, but to handle physics and proper responses is harder.

[Mars_999]

Originally posted by inio

has nothing to do with calculus. [/B]

How is that? It's a derivative. Calculus is the instantaneous rate of change or am I wrong. Intergration and derivatives are calculus. I dont' remember intergration anymore due to way to many rules. I do know this 2x^3 derivative is 6x. Thats why I put 12x^4 = 48x^3 if you remember the power rule that is correct. Drop the exponent and multiply and subtract one from the exponent. That's a part of calculus. Unless Calculus has changed.

[Feanor]

Originally posted by Mars_999
How is that? It's a derivative. Calculus is the instantaneous rate of change or am I wrong. Intergration and derivatives are calculus. I dont' remember intergration anymore due to way to many rules. I do know this 2x^3 derivative is 6x. Thats why I put 12x^4 = 48x^3 if you remember the power rule that is correct. Drop the exponent and multiply and subtract one from the exponent. That's a part of calculus. Unless Calculus has changed.

You didn't include the derivate symbol, so all you wrote was an equality formula consisting of two equations in one unknown, NOT a derivate solution. While the derivate of 12x^4 may be 48x^3 (and no one is arguing that), you have to say "d/dx..." to have a technically correct expression. We all knew what you meant, but some people are afraid you will fail calculus, or maybe that you will corrupt naive readers of the board with your fast and loose short hand. :p

Are we far enough off topic yet?:wacko: Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool(TM)? Am I being an fascist moderator? Is there life on other planets? :???:

[Mars_999]

Originally posted by Feanor
You didn't include the derivate symbol, so all you wrote was an equality formula consisting of two equations in one unknown, NOT a derivate solution. While the derivate of 12x^4 may be 48x^3 (and no one is arguing that), you have to say "d/dx..." to have a technically correct expression. We all knew what you meant, but some people are afraid you will fail calculus, or maybe that you will corrupt naive readers of the board with your fast and loose short hand. :p

Are we far enough off topic yet?:wacko: Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool(TM)? Am I being an fascist moderator? Is there life on other planets? :???:

Ok, I see now. Yes thats my bad. Sorry I was just starting to wondering if my calculus was right? dy/dx =. My prof was anal about using = then your result when we did calculus. So now I am a rebel!! I did get an A in all my math though. Muahahha:wow: :D

What I was getting at with calculus is why couldn't you use the derivative to find the point your looking for? Oh, I think it just hit me that might lead to differential equations? Or am I lost? I never took D.E. just for the record!

[Feanor]

Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic.

[inio]

Originally posted by Feanor
Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic. Calculus becomes useful when you want to determine if moving objects could intersect. For example, given two spheres centers, velocities, accelerations, and radii, you can use calculus to find the time(s) when they will be nearest each other, and from that determine if they could intersect at any time between two given instants.

[DoG]

Knowledge of higher maths is very useful, latest when you have to optimze code. Often, it really helps to write out the math and do simplifications/rearrangements that way, rather than doing it in the code, where you might not even see what you have to do.

Discrete math, linear algebra, differential calculus, tensor math, etc, can all be useful, but they are a work of the devil. :wacko:

You actually don't need calculus to determine when two things intersect, its linear algebra, if I am not mistaken. In code, you don't use calculus, really, since calculus is mostly theory. You might use it when designing code, though.

Anyhow, I always wondered why I had to take 4 semesters of math. 90% of it I can't remember, but those rest 10% come in handy at times. It can impress people if you can prove that 1+1=2 with about 10 pages of theorems :p . And being fussy about math, a teacher once zeroed a math exam because I wrote an = sign instead of an arrow in a place.

- D.G

[Mars_999]

Originally posted by Feanor
Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic.

Calculus deal with any equations. Linear or ^2 or ^3 really doesnt' matter. I was thinking about the detection of two objects and their times and velocities as was stated by Inio. But in games I guess people could care less about accuracy, because calculus is going to be accurate as it gets. I just thought that using calculus would be fast because you could derive a equation that would work for your world and use that equation instead of all these spheres, planes and everything else you can think of. But to tell you the truth I haven't had Calculus in a long time now and its to rusty for me to use anymore but if your good at it you could use it to do some powerful calculations instead of using trig all the time.

[Feanor]

Right, that's what I meant by "predictive collision detection" -- predicting collisions by extrapolating current velocities. The only time this is used is when objects are moving very fast, and there is a possibility that they could travel through another object between frames of animation. I still am having trouble determining the particular application of calculus methods, although I can see that for accelerating objects, rates of change would be involved. inio is the math whiz around here; maybe he has some idea.

I can see linear algebra being useful for solving two equations in two unknowns in order to see if paths interesect in space. I cannot at the moment see how to put time into it, in order to avoid false positives for paths that intersect but disjointly in time. I am sure that someone has put a solution out somewhere.