Advances in approximate convex decomposition, or how to get better physics models.

[animats]

Second Life has much trouble with bad physics models. The system for generating them automatically during mesh upload is not that great. It's a hard problem.

There's been recent research work on solving that. Google seems to be funding work in the field, partly because they need this for Google Earth.

New papers, both from 2022:

• "CvxNet: Learnable Convex Decomposition". Uses machine learning. Some big names in the author list. Difficult paper to understand. Claims better results than other approaches.
• "Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search"  More traditional geometric approach. Not too complicated. Open source code on Github.

Looks like there's been considerable progress. The big advance is doing approximate convex decomposition, where it's OK if there's a little overlap between the parts. If you go for exact decomposition, as Havok does, the joints get complicated. For collision purposes, a little overlap is not a problem.

The second paper has some useful pictures.

The input is a single mesh, and the output is multiple convex (no inward dents) meshes, shown in different colors. Convex meshes are suitable for SL's collision system. (Convex hull intersections are fast to compute. See "GJK algorithm" for the theory. That's what everybody serious, including Havok, uses.)

This approach seems to get the classic hard cases right. The Havok decomposition has a hard time with simple cases such as a house with four walls, let alone one with a door and windows. This system seems to do better.

Harder cases, with the accuracy turned down. This looks promising. If you turn the accuracy way down, something reasonable still comes out. That's what we need.

Of course, these are the author's test cases. Anyone want to build the code and run some models through it? The program takes .obj format, so if you have it in Blender, you can try it with this program.

SL viewers that upload content send this info as a "Physics Convex Block". Currently, Havok code in the viewer generates those, but a new approach could be substituted.

[AmeliaJ08]

If this actually works I can imagine many creators jumping for joy right now!

[Adamburp Adamczyk]

I agree whole fartedly.

[Henri Beauchamp]

Since Havok is not Open Source, the Cool VL Viewer is using HACD (the oldest version from 2011, since the newer one does not perform as good): amusingly, the results are actually much better than Havok's despite the lack of a ”simplification” step...

[animats]

First try of this convex decomposition program. This is the frame from one of my escalators. (No steps; those are a separate part.)

• On the right, the original.
• In the middle, the default reduction to convex hulls. This resulted in 24 hulls. Would be an OK physics model.
• On the left, forced down to 8 hulls. Except for that bump at the top left, which would get avatars stuck on the escalator, it's fine. 8 was too small.

Looks OK so far. Its choices on where to cut are reasonable. Try it yourself. I used the Python 3 version, listed under PyPi here.

Creators, please try some of your own models and post the results. Thanks.

[Wulfie Reanimator]

How does the result work in practice if you upload it to SL? Is the physics cost more or less than the original escalators? (Or about the same?)

Edited August 20, 2023 by Wulfie Reanimator

[animats]

We have a problem. Original model of simple building on right. Generated convex decomposition on left.

This isn't good. Three walls and the floor were already convex, and they were subdivided, for no good reason.

Bug report submitted.

[animats]

Some progress. Turns out that the input must be subdivided into triangles, not polygons, but the program doesn't check for that.

On the right, the original. Center, convex hulls with default settings. On the left, asked for more precision.

It tends to shrink holes unless the precision is turned up to max. Then it generates too many hulls. Adjacent hull merging does not seem to be working properly. Tends to round sharp edges and generate unnecessary triangles, which would run up the SL physics cost. The developer is looking into this.

It's promising, but it needs a better clean-up phase. Too early to say if this is a viable solution for SL.

[animats]

A bit more progress.

Finally, a good convex hull decomposition. 10 hulls. Even if the window is slightly off.

This was made by:

• Create model in Blender.
• Clean it up until it's a valid manifold. Watertight solid, all normals correct. Blender has a "Manifold" checker that can tell you if your model is watertight, but it doesn't fix it for you.
• Triangulate. Must be triangles, not polygons.
• Export to .obj format.

• ./coacd -i work/house1atriang.obj -o house1atriangphy5b.obj -pm off -md 7 -t 0.02

Takes about 3 seconds.

• Import new .obj file back into Blender.

The program is rather brittle academic software. If you don't triangulate the input, the output is terrible, but you don't get any error messages. The program is supposed to be able to cope with non-manifold geometry, but that feature rounds square corners and messes things up. "-pm off" turns that off.

So the theory is coming along, but the code needs some work. I'll try some harder cases soon. I've tried my escalator frame, and it's not bad except for parts that are not a valid manifold. Have to fix those and try again.

Probably the most useful form of this for now would be as a Blender plug-in to help make SL physics models. It's not ready to be part of the uploader. Nice to see advances in the technology, though.

Edited August 31, 2023 by animats

[animats]

Github link: https://github.com/SarahWeiii/CoACD