Hacker News Reader

Comment by mrspeaker | Hacker News Reader

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...

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!

View on HN

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), 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.

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.

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.

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

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.)

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

Reply on news.ycombinator.com