Well, I would like to ask this, because it seems there are smart people here (david for instance) that could tell what they think and know.
Is there a good a priori Box to Box collision detection?
I am doing the most naive box to box collision detection, that is, checking when each of its vertics hit the other box and when each of one's box edges hit each of the other box's edge.
Its pretty slow, but I can manage with it.
I thought of some optimiztaions for it, but they take too long to just try, and they are not always optimizing as I thought they would.
I also havnt found any good resources on box to box a priori collision detection.
So I would appreciate if it is possible.
Box to Box Collision detection
My first thought for your problem would be to start with bounding sphere collision. That is, create the smallest possible spheres around each box, and check if the distance between the centers of the spheres is greater than the sum of their radii. If so, they cannot intersect, and you are done. Otherwise, we have to do more tests.
Next, you can check if any of the points of one box are inside the other box. If so, they are intersecting. If not, we have to go on.
Finally, you can check if any of the edges of one box intersect the faces of the other box. If so, they are intersecting, and if not, they are not. Either way, you are done.
Checking collision between every box in the scene is an O(n^2) algorithm, so no matter what you do, it will start to bog down very quickly as you add more boxes. If there are going to be a lot of boxes then you probably ought to look into some kind of scenegraphing, such as octrees. This is a useful site for most kinds of basic collision detection geometry.
Next, you can check if any of the points of one box are inside the other box. If so, they are intersecting. If not, we have to go on.
Finally, you can check if any of the edges of one box intersect the faces of the other box. If so, they are intersecting, and if not, they are not. Either way, you are done.
Checking collision between every box in the scene is an O(n^2) algorithm, so no matter what you do, it will start to bog down very quickly as you add more boxes. If there are going to be a lot of boxes then you probably ought to look into some kind of scenegraphing, such as octrees. This is a useful site for most kinds of basic collision detection geometry.
Thank you, I am sorry if it is too much bothering for you.
What I am doing is a priori collision test, not a post one.
In a priori test, the two boxes do not intersect yet, and the test calculates the exact time it would take the two boxes to meet each other in some point.
So there is also the dimension of time in a priori test, unlike a post test in which you only check for intersection.
I do a priori test because I dont know how to make fast object not to leap over standing objects because of the very fast speed and because of the post test rather then priori test. And also because the hit location is more accurate.
I just thought you might know of resources on a box to box priori test, because I can rarely find anything about priori tests in the net.
Maybe I am not looking good enough.
Thank you again.
What I am doing is a priori collision test, not a post one.
In a priori test, the two boxes do not intersect yet, and the test calculates the exact time it would take the two boxes to meet each other in some point.
So there is also the dimension of time in a priori test, unlike a post test in which you only check for intersection.
I do a priori test because I dont know how to make fast object not to leap over standing objects because of the very fast speed and because of the post test rather then priori test. And also because the hit location is more accurate.
I just thought you might know of resources on a box to box priori test, because I can rarely find anything about priori tests in the net.
Maybe I am not looking good enough.
Thank you again.
Why don't you just use finer timesteps? I don't think there is really any other robust way to do this in real time. When I need a really precise hit location I just recursively check smaller timesteps. I.e. if the boxes are intersecting at 1 second, but not at 0 seconds, then they collided at some point in-between. So then I check if they were intersecting at 0.5 seconds. If they were, then they collided between 0.5 and 1 seconds. Then I check 0.75... and so on. You can keep doing this as many times as you want to get as much precision as you want.
A priori tests only really make sense if one thing is going much faster than the other, like a box and a wall, or a bullet and ... anything. In these cases you can just extrude the object through space, so the box would become sort of a doubled box, and the bullet becomes a line.
In almost all cases, high-frequency intersection tests make the most sense.
A priori tests only really make sense if one thing is going much faster than the other, like a box and a wall, or a bullet and ... anything. In these cases you can just extrude the object through space, so the box would become sort of a doubled box, and the bullet becomes a line.
In almost all cases, high-frequency intersection tests make the most sense.