3 ms·
I used to work on collision detection in the 1990s. You can do convex collision detection in O(sqrt(m)+sqrt(n)) the first time, and close to O(1) if the objects
by Animats 7y ago
I used to work on collision detection in the 1990s. You can do convex collision detection in O(sqrt(m)+sqrt(n)) the first time, and close to O(1) if the objects just moved a little and you have the result from the previous time. See the GJK algorithm. It's basically hill-climbing to find the closest points.
The author glosses over many real-world problems. Some algorithms work badly in 32-bit floating point because they depend on small differences between large numbers. (I ran into that in the days before everybody had good 64-bit FPUs.) Convex meshes should not be triangulated, because that results in coplanar faces, and hill-climbing can get stuck on the wrong face. It's necessary to clean up convex objects a bit - require a minimum break angle of one or two degrees at each edge to make sure that they're strictly convex, not just non-concave. The author writes "One important class of objects are convex polytopes, which have the property that between any pair of points in the shape the straight line segment connecting them is also contained in the shape." That's a necessary property, but not a sufficient one; it allows coplanar faces.
Broad phase collision detection usually involves three lists of the bounding boxes of the objects, ordered by X, Y, and Z. Only if there's overlap in all three axes do you need to do the narrow-phase test. The author writes "Using output sensitive analysis, there is also a lower bound of O(n log(n) + k) (for comparison based algorithms) by reduction to the element uniqueness problem." That's also the lower bound for sorting by comparison, of course. But that's a price you only pay at cold start, when you initially sort all your objects. Thereafter, you update the ordered lists as the objects move, which, if most things are not moving at high speed, is cheap.
Large-area collision detection, for big MMOs, has an even coarser phase of binning by large areas. Just divide the world into squares and only look at your square and the neighboring squares. This parallelizes nicely.
- djmips 7y agoPeople are still using 32 bit floats in games and it's not something that has been solved by good 64-bit FPUs.
- johtela 7y ago> Broad phase collision detection usually involves three lists of the bounding boxes of the objects, ordered by X, Y, and Z. Exactly. You first want to limit the set of objects that might collide as far as possible. A three-level interval tree [1] works great for finding overlapping bounding boxes. You need a three-level nested interval tree where the 1st level covers the x-direction, 2nd y-direction, 3rd z-direction. It also pays off to make sure that the interval trees are balanced. You can turn the interval tree into red black tree [2], for example, by adding the color flag in the interval node. Then you can balance the tree using rotations when inserting or deleting. [1]: https://en.wikipedia.org/wiki/Interval_tree https://en.wikipedia.org/wiki/Interval_tree [2]: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
- w0utert 7y agoOne thing that has crossed my mind a few times when dealing with bounding box tests (for non-interactive purposes by the way, but that's besides the point) is whether it would be worth using oriented bounding boxes instead of axis-aligned bounding boxes. The idea would be to fit an efficient bounding box to my object-space meshes once, and then use the mesh transform on each bounding box before the tests. This obviously takes computation type (to do the transform, and because the bounding box test will be a lot more expensive compared to an AABB), but the number of false positives would be way lower for certain shapes. In which scenario's would you think this could be worth it?
- gentleman11 7y agoIs this a good resource for how to efficiently do raycast collision detection? I might need to write a little script in the next month or so