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

[fire]

• [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

[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:

• 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

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

[^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): 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.

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

[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]

When you say remove exceptions, what exactly do you mean? Are you hoping for old-school error return codes or something?

[fire]

Something like this documentation. https://docs.godotengine.org/en/stable/development/cpp/common_engine_methods_and_macros.html#error-macros

Also the exceptions must be physically removed from the code (like ifdefs) because it's checked by the c++ compiler and not godot engine.

[elalish]

I still don't quite understand what you mean; are you specifically talking about how non-manifold input produces an exception? I suppose that could generate an empty mesh instead? I also have assertions that will throw, the idea being it's better to catch an exception and stop gracefully than to crash. Perhaps you can make a PR to change one or two so I can see what you're thinking of replacing them with?

[fire]

Let's say you're simulating a game world.

1. It's better that manifold returns a valid result like the original two meshes not joined, than a crash that stops the entire simulation for like a 100 people.
2. The other use case is that Android bans exceptions according to the github actions. Not sure about the details.
3. For debugging time I can make test case that would crash because the new code I'm working is buggy with dividing meshes (the boost rewrite) and restarting the editor slows my iteration times.

You can achieve returning a valid result both by exceptions and error codes. Error codes and exceptions are a tool.

The problem I had was defining was what valid results can be returned after a boolean merge error that creates an invalid manifold..

Edited:

An empty mesh is obvious and it handles the boolean intersection case.

[elalish]

Okay, then I think this library throwing exceptions isn't really the problem (I want to notify people when operations didn't or can't work). You'll just need to try/catch them to handle them properly. It sounds like you're alright with requiring manifold input, so I guess you won't hit that exception? If a Boolean operation fails for some reason, you could fall back to using Compose, which will put the meshes together but without any intersecting.

And then there's obviously something the MS compiler doesn't like, so we'll have to debug and fix that.

[fire]

I would like to enable the Android platform, but it requires probably a define for the code that throws so that c++ compiler doesn't see it.

There may also be an exception disable on c++ compiler but I'm not sure what that entails.

[Calinou]

You'll just need to try/catch them to handle them properly.

Unfortunately, this can't be done if the code is built without support for exceptions. Old-school error codes are the only solution here. I know they're not as convenient, but they're far more universal – including for users of third-party language bindings.

It's fairly common for C++ libraries to support building without exceptions, as many users will not even consider a library if it requires building with exceptions. Some exotic platforms and compilers do not support any form of exceptions. For instance, this was a problem on WebAssembly for a long time. Even if this is no longer a problem on some platforms, exceptions can have a significant cost on performance and binary size depending on how well the compiler implements exceptions.

The further step for universal usage would be to use plain C instead of C++ for libraries, but I won't go that far here :slightly_smiling_face:

[elalish]

@Calinou Thank you for the explanation, that's very helpful! I've never written with error codes, so if someone wants to take a stab at ifdeffing one of the current exceptions to show how you'd handle it, that would be very helpful. Obviously we could just remove them all, but then it'll crash instead of throw, which seems worse?

Anyway, this library is already using C++17 and lots of modern style. I want to eventually move forward onto the latest C++ parallel algorithms, which certainly isn't supported by all the old compilers, but I think is the right move for clean GPU and multi-core parallelized code.

[elalish]

I was reading up on this and found an interesting SO question with several good responses. Seems like most of the no-exceptions camp folks also avoid the standard library containers. That seems pretty extreme, but they do mention games specifically. Is that how Godot works?

[ksuprynowicz]

Maybe exceptions could be inside #ifdef ? Then it would be possible to disable them.

[Calinou]

I was reading up on this and found an interesting SO question with several good responses. Seems like most of the no-exceptions camp folks also avoid the standard library containers. That seems pretty extreme, but they do mention games specifically. Is that how Godot works?

Godot itself doesn't use STL containers, but we still build with STL enabled to allow linking against libraries that use it. You can keep using STL on your end :slightly_smiling_face:

[elalish]

Thanks! I have this little ALWAYS_ASSERT function I use to wrap my exceptions, so it should be a simple place to #ifdef everything. There are a few other exceptions sprinkled around, but I'd be happy to convert those to use this wrapper if someone would demonstrate how these should be disabled.

[fire]

Can we define what are good results for failure?

Here's some

1. for boolean add. returning the originals is a ok result
2. for boolean subtract. empty mesh?
3. for boolean intersect empty mesh?
4. for manifold input failure returning the empty mesh is ok
5. for manifold output error returning the empty mesh is ok

[elalish]

Good idea, but does this mean you want me to catch any possible failures and recover from them gracefully, and all without using exceptions? Or can I use exceptions internally so long as I catch them all? After all, my STL containers can still throw. My Boolean failures are basically asserts; compiling them out entirely seems reasonable. It really shouldn't fail unless something is broken (which apparently happens when compiled by MS), and in that case it's just as likely something I'm not asserting will seg-fault anyway.

The main API-level exception is around pre-conditions like input manifoldness, which agreed, we could just make it return an empty Manifold instead.

[fire]

Makes sense. I'll try to type what I can, but starting to get busy.

[fire]

I tried patching csg. What's a good way for me to send you the error cases? They trigger when I drag the csg shapes in godot engine.

[elalish]

Wow, are you running a full boolean per frame? I kind of figured that would be more of a mouse-up operation. Ideally you could save the current state of the manifold inputs, dump them out as GLB or OBJ or something and verify they have the same behavior in a tiny C++ script. If the models aren't copyrighted, you could even add them as a test case in mesh_test.

However, before you go too far, what compiler are you using? If it's MS, then there's already #86, which indicates there's a definite problem that I won't be able to debug without a Windows machine. Do you repro that? Because I can't with gcc.

[fire]

I'm using llvm-mingw which are neither of your tested choices :D. I can also send you instructions to use the github actions build versions of godot engine.

[elalish]

Sure, widening my github actions testing sounds like a good place to start. With llvm-mingw, does the whole manifold test suite pass for you locally at least? If there are any failures, please list them here.

[fire]

It was a bit of a pain. I can show you my godot manifold branch, but wasn't able to get the manifold working on cmake. (win)

[Calinou]

Wow, are you running a full boolean per frame? I kind of figured that would be more of a mouse-up operation.

This is done to allow for quick visual output, but I agree we should move this to a debounce timer eventually (defaulting to 0.1 seconds or so). This debounce timer would probably need to be made configurable somewhere in a global place, as there are always people who will try to use CSG in real-time in their projects (even if it's usually a bad idea).

Running CSG operations on a separate thread could also help, but it adds a lot of complexity.

Edit: Proposal opened: https://github.com/godotengine/godot-proposals/issues/4448