4 ms·

Detecting collisions between two convex hulls isn't that hard, but it is slow-ish. The Separating Axis Theorem (or its more general and WAY COOLER SOUNDING Hyp

Detecting collisions between two convex hulls isn't that hard, but it is slow-ish. The Separating Axis Theorem (or its more general and WAY COOLER SOUNDING Hyperplane Separation Theorem) lets you do a dot-product per face and if they all come out positive, there's no collision. https://en.wikipedia.org/wiki/Hyperplane_separation_theorem https://en.wikipedia.org/wiki/Hyperplane_separation_theorem

Animats 11y ago
Convex collision detection is very fast with incremental GJK. When the axis-aligned bounding boxes for two objects intersect, you create an object pair and start GJK for the pair. It walks along the edges and faces of the polyhedra to find the shortest distance. This is O(log N) on the number of vertices. On the next frame, you rerun GJK starting from the previous result, and if the objects haven't moved much, look at 0 or 1 new edges, vertices, or faces. So the incremental approach is nearly constant time after the startup. Doing a dot-product for every face pair is O(N^2). Bad for large N. If you do this right, convex hulls with a few hundred faces are no problem. When constructing convex hulls for this, you can use a tool like QHull. Tell it that you want at least some minimal angle such as 1 degree at each edge. This will eliminate many near-coplanar faces. Also, it's better to use polygonal faces than triangular faces. With triangles, a rectangular face has two coplanar faces, and GJK will toggle between them, making resting object jiggle. (Basic annoyance of polyhedra and roundoff: if you tesselate, you get coplanar faces; if you use polygon faces, they're not perfectly flat.)
snaily 11y ago
There's something about multidimensional geometry and great theorem names. I bring you the ham sandwich theorem: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Ham_sandwich_theorem

Animats 11y ago

Convex collision detection is very fast with incremental GJK. When the axis-aligned bounding boxes for two objects intersect, you create an object pair and start GJK for the pair. It walks along the edges and faces of the polyhedra to find the shortest distance. This is O(log N) on the number of vertices. On the next frame, you rerun GJK starting from the previous result, and if the objects haven't moved much, look at 0 or 1 new edges, vertices, or faces. So the incremental approach is nearly constant time after the startup. Doing a dot-product for every face pair is O(N^2). Bad for large N. If you do this right, convex hulls with a few hundred faces are no problem. When constructing convex hulls for this, you can use a tool like QHull. Tell it that you want at least some minimal angle such as 1 degree at each edge. This will eliminate many near-coplanar faces. Also, it's better to use polygonal faces than triangular faces. With triangles, a rectangular face has two coplanar faces, and GJK will toggle between them, making resting object jiggle. (Basic annoyance of polyhedra and roundoff: if you tesselate, you get coplanar faces; if you use polygon faces, they're not perfectly flat.)

snaily 11y ago

There's something about multidimensional geometry and great theorem names. I bring you the ham sandwich theorem: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Ham_sandwich_theorem