Sorting Collisions
Author
Well, ive just about got my collision dectection system done, thanks to a wonderful tutorial by oliii (sorry if i spelled it wrong) which i have taken a little farther, and anyways, i realized something, because my collision system will move an object forward in time to the point of its collision with another object (if its velocity will move it that far), it will need to detect collision with the nearest objects first, and so i need to have some way to sort collisions by i guess... distance, but we all know sqrt is fairly expensive, and i dont wanna do that every frame if at all possible, is there any method for sorting objects taht eliminates this? or someone tell me "theres nothing you can do about that, sure some collisions will miss, but theres nothing you can do about that", or worst of all, no one knows what im talking about because my system is crazy :-P
anyways, if anyone understands my dilema and can lend me a thought, thatd be great, thanks
-Dan
Being someone who's had to do this for a couple of different projects, the easiest way is to not deal with it in terms of distance, but time. When the collision tests are done determine the associated time that the collision occurs at, in the range (0:1]. Where time 0 is the start of the frame (where nothing should be colliding) and 1 is position along the velocity that the object ends up at the end of the frame. (the parenthesis on the zero means that the range includes all the number down to zero, but not zero itself) This way, you sort all the collisions by time, resolve the collision at the earliest time and then do it all over again.
--Russell--
Don't usually post, so you can shoot me an email at: magforceseven@exilecafe.net if you have any other questions.
--Russell--
Don't usually post, so you can shoot me an email at: magforceseven@exilecafe.net if you have any other questions.
Well, you shouldn't worry about the speed of a few clock cycles before implementing something.
But if it's very important that you avoid sqrt() at all costs, note that you don't need the exact distance between 2 things.
Assuming x and y are positive, and x > y:
sqrt(x) > sqrt(y)
So when you're sorting by distance, you don't need the exact distance, so don't take a sqrt() operation. It'll still sort okay.
But if it's very important that you avoid sqrt() at all costs, note that you don't need the exact distance between 2 things.
Assuming x and y are positive, and x > y:
sqrt(x) > sqrt(y)
So when you're sorting by distance, you don't need the exact distance, so don't take a sqrt() operation. It'll still sort okay.
Author
Hrm alright, thanks for the time tip :-D, and thanks for the no sqrt tip too, well i guess sure it works that if x > y then sqrt(x) > sqrt(y), but does it necessarily work the other way? (at this point it doesnt really matter anymore since im going to use the time based approach, but im still curious)
thanks both
-Dan
thanks both
-Dan
I have to agree, time will be a better measure for sorting. I tried with displacements, it's not a good idea. You still have to be careful with the overlaps (time = 0).
That should be a new part in the tutorials actually.
I'd tried this.
1) Find the earliest collisions for all objects.
2) Sort objects by time of collision.
3) Apply impulse to first colliding objects
4) Re-calcualte collisions with objects that previously collided with these two objects.
5) goto 2, until no collisions left.
Not sure how overlaps work in this. YOu have to be careful because they can introduce an infinite loop.
That should be a new part in the tutorials actually.
I'd tried this.
1) Find the earliest collisions for all objects.
2) Sort objects by time of collision.
3) Apply impulse to first colliding objects
4) Re-calcualte collisions with objects that previously collided with these two objects.
5) goto 2, until no collisions left.
Not sure how overlaps work in this. YOu have to be careful because they can introduce an infinite loop.
If you want to compare distance then you do length(vec u) > length(vec v).
length(a) = sqrt(a.x^2 + a.y^2 + a.z^2)
Now you should be able to see that you can remove the sqrt when comparing distances. Calculating the time for the collision is better.
length(a) = sqrt(a.x^2 + a.y^2 + a.z^2)
Now you should be able to see that you can remove the sqrt when comparing distances. Calculating the time for the collision is better.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
