Improve Godot Engine's boolean operator engine (CSG) with elalish/manifold

[fire]

• Restore normals and tangents
• Postpone running a profiler and see if there's easy bottlenecks
• Write a Godot Engine proposal
• Generating CSG nodes is slow on a full character mesh added to a box
• Can start providing test cases that crash the godot engine patched with manifold
• Remove exceptions from elalish/manifold ?
• Propose idea
• Ask for comments
• Investigate code details
• Tech lead of Godot Engine is ok with requiring manifold geometry inputs for CSG
• Remove requiring Cuda Developer Kit to build.
• Check performance latency of mesh generation (per frame? per second? per minute?)
• Blocked on removal of boost dependency
• The results of boolean operations look great. No gaps.
• Restore UV coordinates
• Restore materials

[elalish]

That would be awesome! Technically it should be possible to build Thrust with the C++ backend without using nvcc (from the CUDA toolkit) since Thrust is just a C++ header library. However, I haven't tried it yet. I'd like to migrate from Thrust to C++17 parallel algorithms partially to simplify the code and make it run in parallel on more than just CUDA GPUs, but also to make standard compiler chains work better.

Are you interested in helping to try some of these options?

[fire]

Can you briefly describe a guide?

1. where inputting manifold meshes
2. apply union, intersect and merge
3. output another mesh?

[elalish]

I think this test and the following one demonstrate all of that: https://github.com/elalish/manifold/blob/master/test/mesh_test.cpp#L698

And of course the docs: https://elalish.github.io/manifold/classmanifold_1_1_manifold.html

[fire]

Is it difficult to disable assimp?

[elalish]

Assimp is only linked for building meshIO. It's separated for exactly this reason; I figured most users would use their own input/output code.

[Calinou]

To give some context on Godot's CSG usage, Godot features CSG nodes (with both primitive and user-supplied custom meshes) that can be used to block out levels. CSG nodes can also have one or more material slots configured (and assigned on a per-face basis), which are preserved by the CSG algorithm and can be assigned by the user. The documentation can be found here.

Custom code had to be written for this back in 2018, since CSG libraries available at that time were generally GPL-licensed. (Godot is MIT-licensed and therefore needs to avoid (L)GPL-licensed components.)

This custom code is relatively small, but it also suffers from many bugs, especially with coplanar faces:

• CSG box and sphere subtract displays cracking from missing triangle  godotengine/godot#41140
• CSG flicker / missing triangles / holes in the geometry at certain translations godotengine/godot#43755
• Holes in CSG meshes with coplanar faces and engine freeze when moving them godotengine/godot#58637

Mesh generation performance is good enough for static level design, but performing real-time changes should be avoided to prevent stuttering during gameplay. (That said, I doubt any CSG library can be fast enough to guarantee that mesh generation happens in < 16 milliseconds with typical low-poly game meshes. Moving mesh generation to a separate thread is probably a good idea.)

[x] Tech lead of Godot Engine is ok with requiring manifold geometry inputs for CSG

For reference, the current custom CSG implementation already has this as a requirement:

Any mesh can be used for CSG, this makes it easier to implement some types of custom shapes.
Even multiple materials will be properly supported.¹ There are some restrictions for geometry, though:

• It must be closed
• It must not self-intersect
• Is must not contain internal faces
• Every edge must connect to only two other faces

—Godot gets CSG support

In parallel, we'd like to rework the CSG editor for better usability, but this can be done separately from the underlying mesh generation algorithm.

Footnotes

1. Multiple materials per CSG node are already supported since Godot 3.1. ↩

[fire]

@elalish Can you remove boost graph dependency?

https://github.com/haasdo95/graphlite was the closest I can find.

[fire]

I was able to extract https://github.com/V-Sekai/godot/tree/csg-manifold [does not compile] and did a build system trick to enable .cu, but the boost dependency was too much after the 8th Boost folder...

[elalish]

Interesting, I'm still relatively new to the world of C++ libraries and didn't imagine Boost would be a big problem dependency-wise. I'm only using it for a connected components algorithm - figured better not to reinvent the wheel. Still, that's a generic algorithm and I'm sure it's available elsewhere, or we could just write our own. Thoughts?

[fire]

Can you evaluate https://github.com/haasdo95/graphlite? I wasn't able to find many substitutes.

What operations are you using?

[elalish]

All I use is connected_components (in two places):

manifold/manifold/src/impl.cu

Line 427 in 3e92f47

boost::connected_components(graph, components.data());

graphlite doesn't technically include it, but it basically has it sketched out here: https://github.com/haasdo95/graphlite/blob/dde08e41c75b5fe42f7e3e0c6b02c4883b23155f/src/graph_lite/serialize.h#L156

Shouldn't be too hard to switch over. I like the idea of keeping my dependencies light.

[fire]

Can you do an estimate how difficult the work is, and if you need help?

[elalish]

Shouldn't be more than a few hours, ideally. However, I'm leaving on vacation tomorrow for the rest of the week. If you want to take a stab at it, you're welcome to. Otherwise I'll take a look next week.

As far as taking a dependency on graphlite, should I just copy in graph_lite.h and note the git hash it's from? I can't think of a better way at the moment...

[fire]

I'm swamped with pending work. I can't promise anything.

It'll mostly like be next week.

Regarding dependencies, Godot Engine has a readme and a licenses document.

[fire]

Here's my thoughts on the two Material Case.

1. mesh 1 mat 1 and mesh 2 mat 2 need to be converted to mesh 1 mat 3 and mesh 2 mat 3
2. mat 3 uses xatlas to combine or a simple algorithm that uses double the uv space. (like 4x)
3. Use manifold on the mesh 1 and mesh 2.

[elalish]

Yeah, pretty much. You can do steps 1 and 2 after 3 (which means you can do it after many boolean operations and just deal with the UV coords that are left if you want). This is what the MeshRelation is for.

[elalish]

I've got a WIP #92 to change the graph dependency.

[fire]

Debugging winding order and conventions.

Do you have an example cube with the positions and the triangle vertex indices?

[elalish]

CCW. Manifold cube = Manifold::Cube(); should give you what you need, yeah?

[fire]

If I used the meshes from the manifold library I was able to do csg operations, but still working on the mesh import. It crashes on non-manifoldness.

[ksuprynowicz]

Works perfectly now :)

[fire]

Some fun shapes.

[elalish]

Nice work! So @fire, if this is working, does that mean the Boost dependency is okay, or you still need that removed?

[Calinou]

So @fire, if this is working, does that mean the Boost dependency is okay, or you still need that removed?

The Boost dependency still needs to be removed if this is to be integrated in Godot core. We can't integrate such a massive dependency in Godot's repository (as we include the source of all dependencies within https://github.com/godotengine/godot). Small binary size and fast build times are important to us, so we had to make this decision.

[fire]

I posted the changes I used here #93.

Here's a Godot Engine master patched branch https://github.com/V-Sekai/godot/tree/csg-manifold-03.

[fire]

Notes:

1. Generating CSG nodes is slow on a full character mesh added to a box, but did not run a profiler
2. Can start providing test cases that crash the godot engine patched with manifold
3. Can we remove exceptions from elalish/manifold ?
4. The results of boolean operations look great. No gaps.

[Calinou]

Can we remove exceptions from elalish/manifold ?

To clarify, we want Godot to remain buildable without exceptions, so they need to be disableable at build-time. It's fine to keep exception code for those who want it, but it needs to be optional.

[fire]

logs_28140.zip

7_Compilation (armv7).txt

Here are the logs that fail on exceptions.

[fire]

Posting my test godot project so I can clean up my desktop.

CSG Game Project.zip

[elalish]

You can see for yourself that our tests are passing, perhaps you can write a test to catch the problem you're having?

[elalish]

@fire Any more information you can give me on this? I see you're now restoring materials, which presumably means you're now using MeshGL? For anything with discontinuous vertex properties, you'll need the mergeFromVert and mergeToVert vectors to maintain the manifoldness. Next I'm planning to build a helper to auto-generate those for a MeshGL based on tolerance welding, but that'll always be a heuristic process. Any examples you can give of what's giving you difficulty would help in my design of that.

[fire]

I am currently trying to release Godot Engine 4.0 so things have been hectic. Sorry for the lack of communication.

[fire]

Some interesting new development. https://github.com/SarahWeiii/CoACD was able to turn arbitrary meshes into a manifold meshes.

Not sure how, but something to do with openvdb.

Useful for supporting arbitrary meshes as input

[elalish]

@fire Yeah, I have quite a bit of familiarity with algorithms to make meshes manifold - I managed Microsoft's relationship with Netfabb when we were integrating their watertighting algorithms into our software. If you want to do it generically (like they did) you need a lot of heuristics and there's no avoiding having some very surprising results occasionally.

This library isn't about heuristics, but reliability. That said, I would like to help with meshes that are at least attempting to be manifold to get over the hump. I'm considering a function like enum MeshGL::Merge(float precision) that would generate the mergeFromVertex and mergeToVertex vectors by welding verts on open edges that are separated by less than precision. It would return a status of either AlreadyManifold, NowManifold, or NotManifold. This would make imported models with properties much easier to deal with.

However, it would help my development greatly if you could supply some example models that you were expecting to work and reported as NotManifold, so I can test this flow.

[yetigit]

@fire did a thing here https://github.com/yetigit/force-manifold

that uses just the openvdb part without the convex hull decomposition (which is still quality stuff); basically this is raymarching looking meshes being generated, guaranteeing that the mesh is a manifold. however often times the resolution is high

LEFT is the result RIGHT is the input

[elalish]

Thanks for sharing! Yeah, voxels are a reliable way to get manifoldness, though of course they kill the efficiency of a mesh. I'm almost done with my Merge function - curious how frequently it'll help.

[fire]

I decided to try for fun today and after vendoring thrust, glm, nanobind, quickhull subrepos I hit a roadblock with thrust requiring cuda..

I think I will have a hard time convincing the other Godot Engine maintainers that adding all these libraries is worth the load.

[pca006132]

but thrust doesn't require cuda? you can try to supply the thrust directory into manifold by setting FETCHCONTENT_SOURCE_DIR_THRUST. It should work. We are building it without cuda in the CI.

[fire]

I posted an updated branch to https://github.com/V-Sekai/godot/tree/vsk-csg-4.3.

Note that the default csg shapes aren't manifold so they tend to disappear on use in a csg tree.

Edited:

Something about the indexed meshes requirement breaks the vertex attributes if I try to add more.

[elalish]

Something about the indexed meshes requirement breaks the vertex attributes if I try to add more.

Happy to help if you can give a little more detail. When you have discontinuous vertex properties, you'll need the mergeFromVert and MergeToVert vectors in MeshGL to tell it how to stitch them to make a manifold. Alternately, you can use MeshGL.Merge() to generate these automatically, fixing gaps up to precision wide.

[fire]

Merge() helped significantly.

https://github.com/V-Sekai/godot/blob/549b24ca9b5fcd5be5b9b3c1923cb21816ba0e7c/modules/csg/csg_shape.cpp#L190

Now I am stuck on associating ??? ReservedIDs with each csg shape's Vector<Ref<Materials>> because each shape has it's own material index and it's unique to the vector of materials.

The above is a blender monkey and a mesh.

Edited:

Use the branch due to bugfixes.

[fire]

This is regular Godot Engine CSG for comparison to Manifold CSG

[elalish]

Looks like great progress!

Now I am stuck on associating ??? ReservedIDs with each csg shape's Vector<Ref> because each shape has it's own material index and it's unique to the vector of materials.

Yes, that's exactly what they're for. I like to make a map of originalID to Material (or material index). If each Manifold you create for input has a single material, you can just use manifold.OriginalID() to get the new entry for the map. If it has multiple materials, then you'll want to organize the triangles into runs of consistent material (like draw calls) and call Manifold::ReserveIDs() to get however many you need and put them in the meshGL.runOriginalID vector.

Does that make sense?

[fire]

The task would be to convert TypedArray<Face> into runs of single materials from its current mixed materials. Then something.

The face struct looks like:

struct CSGBrush {
	struct Face {
		Vector3 vertices[3];
		Vector2 uvs[3];
		AABB aabb; // We calculate this directly.
		bool smooth = false;
		bool invert = false;
		int material = 0;
	};
	// ...
};

Then the task gets fuzzy after that.

[elalish]

Yes, so just sort your vector of faces by material. Then find the indices of that vector where the material changes. These values become meshGL.runIndex. Then get a sequence of originalIDs with int first = Manifold::ReserveIDs(numMaterials);. Make a mapping between these originalIDs and your materials. Then fill meshGL.runOriginalID with the ID that maps to your material for each sorted run.

When you get a MeshGL result after operations, the triangles are already sorted into these runs of consistent ID that you can use your map to return to material. Does that make sense?

[fire]

@elalish I gave up trying to learn the manifold runs api.

I treat each material as a separate manifold surface and hacked them together as csg booleans unions where the single material is the id of the mesh.

Multiple materials!

[hrgdavor]

Yes, that's exactly what they're for. I like to make a map of originalID to Material (or material index). If each Manifold you create for input has a single material, you can just use manifold.OriginalID() to get the new entry for the map. If it has multiple materials, then you'll want to organize the triangles into runs of consistent material (like draw calls) and call Manifold::ReserveIDs() to get however many you need and put them in the meshGL.runOriginalID vector.

Does that make sense?

That sound like a great basis for a tutorial, with demo code. I guess it looks trivial to @elalish , but my brain hurts reading that paragraph :) .

[elalish]

That sound like a great basis for a tutorial, with demo code. I guess it looks trivial to @elalish , but my brain hurts reading that paragraph :) .

Yes, fair feedback - I have some sample code in JS, but it's complicated by other things. Okay, I'll take it upon myself to make a tutorial for this. Does anyone have a preference as far as language? I usually default to JS, since it's pretty easy to read and commonly-known.

And @fire, in fact Merge() is compatible with custom triangle runs, and probably makes them a lot easier to use.

[pca006132]

I think TS would be a bit better: We have type support, so it may be better to show how to use those types. One can read it as JS by removing all the type annotations.

[fire]

I have no preference.

[hrgdavor]

if JS/TS is being weighted I vote for TS, I think it would be better suited for the mentioned demo.

I do not code backend in JS, I only do frontend. On front I enjoy the freedom away from TS chains, but I am grateful for all the great tooling TS popularity brought, and ppl doing more typings via TS/jsdoc, ....

[elalish]

Okay, I updated our basic Three.js interop example to demonstrate the use of runOriginalID for material mapping, along with Merge(), and it's all in TS now with proper source mapping. Please take a look at https://manifoldcad.org/three and in dev tools open three.ts to see all the code and comments.

I merged it quickly to make sure it deployed properly - seems to be all good. If anything is still unclear, please add a review to the merged PR above and I'll be happy to do a follow-on.