the best way to do collision detection
Quote: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
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.
Quote: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.
Quote: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.
Quote: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.
Are we far enough off topic yet? Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool™? Am I being an fascist moderator? Is there life on other planets?
Quote: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.
Are we far enough off topic yet? Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool™? 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
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!
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.
Quote:Originally posted by FeanorCalculus 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.
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.
"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!
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.
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 . 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
Discrete math, linear algebra, differential calculus, tensor math, etc, can all be useful, but they are a work of the devil.
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 . 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
Quote: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.
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.
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.
Predictive collision detection is a matter of calculating the x and y coordinates of the objects as a function of time (t), then using that to find the distance between pairs of objects as a function of time: sqrt( [x1(t)  x2(t)]^2 + [y1(t)  y2(t)]^2 ). You want to set that equal to the sum of the radii of the objects = r1+r2. It greatly simplifies things to just square both sides and get rid of the radical: [x1(t)  x2(t)]^2 + [y1(t)  y2(t)]^2 = (r1+r2)^2
Then you "just" solve for 't'. This is much easier said than done because after combining like terms and all that the equation turns out to be somewhere between a 3rd to 5th order polynominal, depending on whether the objects are accelerating or not. So you've got to find formulas for solving cubic/quartic/quintic (3,4,5thorder) equations, and implement those. I hope you like working w/complex numbers.
In the end you may get up to 5 points of intersection. The only one you really should be concerned about is the lowest 't' value past the current time. anything before that has already happened, the one right after that is after the objects "pass thru" eachother, which is exactly what you're going to prevent them from doing, and the remaining ones aren't going to happen because the collision will change the trajectories of the objects. More often than not there won't be any future intersection points because the two objects aren't going to collide.
You always want to take the first collision over all pairs, because that collision is going to change the trajectories and thus possibly affect future collisions. This also means that you'll have to recalculate after each collision. (And whenever an object makes a course adjustment.)
A nice optimization is realizing that you don't have to recalculate ALL pairs  you really only have to do about 2N recalculations, rather than NxN, but that's a whole 'nother topic that I'll leave for the ambitious to work out on their own.
Frankly, I think predictive collision detection can be much faster than other methods, depending on the application. The main difficulty is solving for t and keeping track off all the predictions and recalculations you have to do. There are formulas out there to solve for t for up to secondorder position equations (x = a+bt+ct^2), but if your position equations are any more complex than that, you'll want to consider approximating or using a different method altogether. This method certainly has it's advantages, and a secondorder equation is perfect for a truetophysics space game (neglecting gravity). I'm using it. Hence I'm able to explain it.
Then you "just" solve for 't'. This is much easier said than done because after combining like terms and all that the equation turns out to be somewhere between a 3rd to 5th order polynominal, depending on whether the objects are accelerating or not. So you've got to find formulas for solving cubic/quartic/quintic (3,4,5thorder) equations, and implement those. I hope you like working w/complex numbers.
In the end you may get up to 5 points of intersection. The only one you really should be concerned about is the lowest 't' value past the current time. anything before that has already happened, the one right after that is after the objects "pass thru" eachother, which is exactly what you're going to prevent them from doing, and the remaining ones aren't going to happen because the collision will change the trajectories of the objects. More often than not there won't be any future intersection points because the two objects aren't going to collide.
You always want to take the first collision over all pairs, because that collision is going to change the trajectories and thus possibly affect future collisions. This also means that you'll have to recalculate after each collision. (And whenever an object makes a course adjustment.)
A nice optimization is realizing that you don't have to recalculate ALL pairs  you really only have to do about 2N recalculations, rather than NxN, but that's a whole 'nother topic that I'll leave for the ambitious to work out on their own.
Frankly, I think predictive collision detection can be much faster than other methods, depending on the application. The main difficulty is solving for t and keeping track off all the predictions and recalculations you have to do. There are formulas out there to solve for t for up to secondorder position equations (x = a+bt+ct^2), but if your position equations are any more complex than that, you'll want to consider approximating or using a different method altogether. This method certainly has it's advantages, and a secondorder equation is perfect for a truetophysics space game (neglecting gravity). I'm using it. Hence I'm able to explain it.
Nice input on the subject, but this thread is over six years old! I guess it's still relevant, but talk about raising the dead...
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
2D Pixel Collision Detection using OCCLUSION  Elphaba  0  3,738 
Jun 8, 2009 06:30 AM Last Post: Elphaba 

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

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

Quad CollisionDetection  Duane  5  6,071 
Jan 18, 2005 01:42 PM Last Post: Duane 

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