3 ms·

The link seems to be the overview (with nifty demo) - the actual article is here: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detecti

The link seems to be the overview (with nifty demo) - the actual article is here: https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection https://developer.mozilla.org/en-US/docs/Games/Techniques/3D... I've been playing around with 3D for a while, and have found that collision detection is the (relatively) easy bit: it's collision resolution that messes me up!

talloaktrees 11y ago
Yes, you're exactly right. Resolution is the tricky part. I made a simple FPS game engine using Java + libgdx (https://github.com/jrenner/gdx-proto https://github.com/jrenner/gdx-proto), and it leveraged the bullet physics library for collision detection, but handling collision resolution myself. Even simple things like getting an object to to slide along a wall as it collides with it at an angle can be tricky.
- JupiterMoon 11y ago
  If you're already using bullet why not use if for collision resolution as well? Or if you want to manually change things try using ODE as this is more amiable towards doing so.
maccard 11y ago
Even detecting collisions accurately isn't easy. This is only between primitives (spheres and boxes). Detecting collisions between convex hulls (and more difficultly non-convex shapes) is quite difficult.
- chaosemer 11y ago
  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

talloaktrees 11y ago

Yes, you're exactly right. Resolution is the tricky part. I made a simple FPS game engine using Java + libgdx (https://github.com/jrenner/gdx-proto https://github.com/jrenner/gdx-proto), and it leveraged the bullet physics library for collision detection, but handling collision resolution myself. Even simple things like getting an object to to slide along a wall as it collides with it at an angle can be tricky.

JupiterMoon 11y ago
If you're already using bullet why not use if for collision resolution as well? Or if you want to manually change things try using ODE as this is more amiable towards doing so.

maccard 11y ago

Even detecting collisions accurately isn't easy. This is only between primitives (spheres and boxes). Detecting collisions between convex hulls (and more difficultly non-convex shapes) is quite difficult.

chaosemer 11y ago
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