collision detection - need advice
Hello
It is a broad and yet very complex subject, at least for me, when I simply google it. I would benefit from anyone who could simplify or just give some good insights which path would be the best option for me.
I have thousands of 3D rotated rectangular bodies (rectangular cuboids), typical dimensions L 10 W 8 H 2. I need a very efficient check if they intersect each other. So far I was using the simple one approximating such cuboid to the sphere, which, unfortunately, is too limited.
Any insights would be very helpful, and I would appreciate them.
P.S. so far the Separating Axis Theorem looks the most viable option. Am I right?
It is a broad and yet very complex subject, at least for me, when I simply google it. I would benefit from anyone who could simplify or just give some good insights which path would be the best option for me.
I have thousands of 3D rotated rectangular bodies (rectangular cuboids), typical dimensions L 10 W 8 H 2. I need a very efficient check if they intersect each other. So far I was using the simple one approximating such cuboid to the sphere, which, unfortunately, is too limited.
Any insights would be very helpful, and I would appreciate them.
P.S. so far the Separating Axis Theorem looks the most viable option. Am I right?
Last edited on
These kinds of problems often benefit from a cheap, simple check that gets you close -- "maybe these 2 things intersect" and the more advanced algorithm can be used only if the objects are potentially collided. Your current check could be sped up perhaps (eg take off the square roots if you left them in) to make a list of candidates for the advanced approach. The vast majority of your objects are likely far enough away from each other that you can say 'not intersected' for very little cost.
Start with a coarse check on the min-max x,y,z coordinates of the pair of cuboids. This will RULE OUT most pairs very quickly.
If intersection remains a possibility then they will intersect if any one of the eight vertices of cube B is inside A. Whether a point is inside cuboid A may be ascertained by creating a local coordinate system from three edges meeting at one corner of A and projecting the point to be tested onto that coordinate system.
If intersection remains a possibility then they will intersect if any one of the eight vertices of cube B is inside A. Whether a point is inside cuboid A may be ascertained by creating a local coordinate system from three edges meeting at one corner of A and projecting the point to be tested onto that coordinate system.
Are there any constraints as to where these cuboids can go? Use any constraints to your advantage.
But in general, you want some sort of divide-and-conquer approach, because you know that only rectangles close together could possibly intersect.
https://gamedev.stackexchange.com/questions/161814/how-to-optimize-collisions
https://www.quora.com/How-is-collision-in-game-development-of-thousands-maybe-millions-of-objects-are-managed-by-a-map
But in general, you want some sort of divide-and-conquer approach, because you know that only rectangles close together could possibly intersect.
https://gamedev.stackexchange.com/questions/161814/how-to-optimize-collisions
https://www.quora.com/How-is-collision-in-game-development-of-thousands-maybe-millions-of-objects-are-managed-by-a-map
Topic archived. No new replies allowed.