A fast 3D collision detection algorithm

This is novel indeed! What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost? Either way, narrow phase gets extremely unwieldy when down to the triangle level. Easy for simple shapes but if you throw 1M vertices at it vs 1M vertices you’re going to have a bad time.

Any optimization to cut down on ray tests or clip is going to be a win.

Most likely this can be preceded by testing branches of some spatial hierarchy datastructure, 1 million squared is a lot to compute no matter the algorithm

Without optimizations of the vertices buffer, correct, it’s a 1T loop. But we can work on faces and normals so that reduces it by a factor of 3. We can octree it further as well spatially but…

There’s a really clever trick Unreal does with their decimation algorithm to produce collision shapes if you need to. I believe it requires a bake step (pre-compute offline).

I’d be fine with a bake step for this.

Do you mean non-convex shapes? You can do a convex decomposition and then test all pairs. Usually games accelerate this with a BVH.

Usually you have a render model and a physical model which is a degenerate version of the viewed object, with some objects tailored for picking up, or allowing objects to pass through a curved handle, etc.

I would assume using this algorithm wouldn't necessarily change that creation pipeline.

> Do we assume a spherical bounds and just eat the cost?

We pick the bounding volume that is most suitable to the use case. The cost of non-spherical bounding volumes is often not that severe when compared to purely spherical ones.

https://docs.bepuphysics.com/PerformanceTips.html#shape-opti...

Edit: I just noticed the doc references this issue:

https://github.com/bepu/bepuphysics2/issues/63

Seems related to the article.

I’m trying to find a way to NOT have hull models included in my games. Saving players potentially GBs of disk space.

Constructing Bvh’s on the fly from the high fidelity models we use. Without incurring a performance penalty like we are. So we can improve collision detection instead of clipping due to low res hull models.

The OP’s source code builds a Bvh but it still does so in a way that we’re able to clog it with 34M vertices. Sadly, we’re still going to have to explode geometry and rebuild a hierarchy in order to iterate over collisions fast. I do like the approach OP took but we both suffer from the same issues.

Yeah triangle-triangle is really dependent on number of triangles.

I noticed that issue is 6 years old, what’s the current state?