manifold
manifold copied to clipboard
elalish
Improve Godot Engine's boolean operator engine (CSG) with `elalish/manifold`
- [x] Restore normals and tangents
- [x] Postpone running a profiler and see if there's easy bottlenecks
- [x] Write a Godot Engine proposal
- [x] Generating CSG nodes is slow on a full character mesh added to a box
- [x] Can start providing test cases that crash the godot engine patched with manifold
- [x] Remove exceptions from elalish/manifold ?
- [x] Propose idea
- [x] Ask for comments
- [x] Investigate code details
- [x] Tech lead of Godot Engine is ok with requiring manifold geometry inputs for CSG
- [x] Remove requiring Cuda Developer Kit to build.
- [x] Check performance latency of mesh generation (per frame? per second? per minute?)
- [x] Blocked on removal of boost dependency
- [x] The results of boolean operations look great. No gaps.
- [x] Restore UV coordinates
- [x] Restore materials
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?
Can you briefly describe a guide?
- where inputting manifold meshes
- apply union, intersect and merge
- output another mesh?
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
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.
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:
- https://github.com/godotengine/godot/issues/41140
- https://github.com/godotengine/godot/issues/43755
- https://github.com/godotengine/godot/issues/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.[^1] 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
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.
[^1]: Multiple materials per CSG node are already supported since Godot 3.1.
@elalish Can you remove boost graph dependency?
https://github.com/haasdo95/graphlite was the closest I can find.
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...
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?
Can you evaluate https://github.com/haasdo95/graphlite? I wasn't able to find many substitutes.
What operations are you using?
All I use is connected_components (in two places): https://github.com/elalish/manifold/blob/3e92f47c89b48aa384c41f27e2c7b1a63194c1c5/manifold/src/impl.cu#L427
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.
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...
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.
Here's my thoughts on the two Material Case.
- mesh 1 mat 1 and mesh 2 mat 2 need to be converted to mesh 1 mat 3 and mesh 2 mat 3
- mat 3 uses xatlas to combine or a simple algorithm that uses double the uv space. (like 4x)
- Use manifold on the mesh 1 and mesh 2.
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.
Debugging winding order and conventions.
Do you have an example cube with the positions and the triangle vertex indices?
CCW. Manifold cube = Manifold::Cube(); should give you what you need, yeah?
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.
Nice work! So @fire, if this is working, does that mean the Boost dependency is okay, or you still need that removed?
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.
I posted the changes I used here https://github.com/elalish/manifold/pull/93.
Here's a Godot Engine master patched branch https://github.com/V-Sekai/godot/tree/csg-manifold-03.
Notes:
- Generating CSG nodes is slow on a full character mesh added to a box, but did not run a profiler
- Can start providing test cases that crash the godot engine patched with manifold
- Can we remove exceptions from
elalish/manifold? - The results of boolean operations look great. No gaps.
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.
Here are the logs that fail on exceptions.
Posting my test godot project so I can clean up my desktop.
When you say remove exceptions, what exactly do you mean? Are you hoping for old-school error return codes or something?