Add Boolean Operations on Meshes

[snailtomatoes]

What problem does this solve or what need does it fill?

Adding boolean operations should enable for an ergonomic foundation for constructive geometry

What solution would you like?

Meshes should have a function, similar in usage as merge(), like so:

base_mesh.intersection(operand_mesh);
base_mesh.union(operand_mesh);
base_mesh.subtraction(operand_mesh;
base_mesh.XOR(operand_mesh);

• union or subtraction should consume operand_mesh modifyng base_mesh inplace.
• intersection and XOR should consume both meshes to return an array or list of resulting meshes.

What alternative(s) have you considered?

Boolean operations are resource intesive and a solution that's not going to be closely integrated in the current mesh handling would degrade performance even further.
In addition having tried to do so by myself anyway it's a feature too big to tackle by myself at the moment.

[alice-i-cecile]

I expect that this would be best tackled as a working group, but IMO this is desirable and within scope :)

[ethereumdegen]

I would be pleased to help with this -- i really want to see this happen .

Here is a related talk I found. I think we could make a crate for this named "bevy_csg' or something and its responsibility would be these meshing operations. But also it could allow one to spawn an editable object in a bevy world with tools to edit it .

https://www.youtube.com/watch?v=Iqmg4gblreo

Also maybe structs for the lib could be laid out like this ?? (naive)

https://github.com/ethereumdegen/degen_csg/blob/main/src/csg.rs

an MVP really only needs cuboids to start with as that would solve 99% of level-block-out applications. Maybe cylinders too. But i agree the hardest part is going to be the boolean operations on mesh vertices/faces. If we had that, CSG wouldnt be that hard to build on top.

Btw watch that youtube video starting at 10 minutes. That kind of helps it click

[ethereumdegen]

I think the most simple naive implementation is to build a fn that can take a cuboid and subtract another cuboid.

Basically what you have to do is think in terms of faces. You need to remove certain faces from the base mesh and add faces from the applying mesh.

The tricky part is you kind of need to do a loopcut tool operation on the base mesh by using the planes of the applying mesh. Im sure having some intermediate data format (not just vertices and indices) will be extremely helpful here .

However the more i read about this the more people say how complex it can get and to use existing libraries. Of course many exist in cpp

here is a rust one that is unfinished https://github.com/carlmartus/rscsg

and another https://github.com/dima634/baby_shark

[mockersf]

CSG is very nice, but it's not general mesh boolean ops

The idea with CSG is that you start with base objects that you know how to define mathematically

It's also implemented in https://noumenal.app with Bevy

[ethereumdegen]

Yeah but that is closed source so entirely useless
yes its confusing there are many terms so we need to work through that as well. In any case csg uses those operations

[mintlu8]

union or subtraction should consume operand_mesh modifyng base_mesh inplace.

Just want to point out there is no need to consume the mesh, taking a reference is just as performant.

[HackerFoo]

union or subtraction should consume operand_mesh modifyng base_mesh inplace.

Just want to point out there is no need to consume the mesh, taking a reference is just as performant.

No, it's not, because you'll end up doing a lot of cloning, assuming the mesh is first converted to some sort of spatial tree. Unless you mean a mutable reference, which is essentially the same thing, but much harder to manage in this case.

[HackerFoo]

Yeah but that is closed source so entirely useless yes its confusing there are many terms so we need to work through that as well. In any case csg uses those operations

It can't hurt to have someone around who has been researching and working on this problem for a long time. But for the same reason, I'm not willing to just hand my work over, and it's unlikely anyone else would be able to contribute in any meaningful way without spending nearly as much time studying the underlying algorithms. I don't mind sharing references that I've used, and I track other algorithms and implementations.

I suggest using an existing robust implementation such as elalish's Manifold; he has spent a long time working on his implementation as well. Unless there is someone with the background needed and willing to do this kind of work.

[RCC-CCN]

I agree, I'd like to add to the resources InteractiveAndRobustMeshBooleans.
It's an university project in C++ with many caveats but the general step used seems to be straightforward, implementation on the other hand can be confusing.

[mintlu8]

union or subtraction should consume operand_mesh modifyng base_mesh inplace.

Just want to point out there is no need to consume the mesh, taking a reference is just as performant.

No, it's not, because you'll end up doing a lot of cloning, assuming the mesh is first converted to some sort of spatial tree. Unless you mean a mutable reference, which is essentially the same thing, but much harder to manage in this case.

I meant the right hand side mesh if there's any misunderstanding.

fn union(self, rhs: &Mesh) // or &mut self ?

It is because data are already in Vecs in both meshes. There's no way to merge vecs in rust.

[bugsweeper]

I don't think we should use another project written in C++ (I don't hate C++, I was C++ developer), I like that Bevy built in Rust and FFI usage will make it dirty.

This task is not so complex if we divide it to a set of simple tasks (I put here list of naive task list. It based on expectation that mesh is complete and has not gaps. Resulting mesh should also be complete with no gaps):

• Determine whether the point is inside of the mesh. This can be done by simply set axis (for example Z) through the point and find the most close to the point triangles crossing this axis from two sides. If projections of triangles normal on axis look outside of point, the point is inside, if opposite then point is outside, if normal's projection has same direction, then mesh has gaps and axis hit that gap. The third most rare state of point is being on the surface of another mesh, in this case the most close triangle will contain that point.
• When we have mesh with marked point relative to other mesh, we can make desicions triangle-wise. If all points of triangle have same state (all inside for example) and all sides of triangle don't cross any other triangle, then this triangle could be dropped (if it is inside the mesh and we make mesh union, or it outside and we make mesh intersection or substraction) or can be added to the new mesh otherwise (point list of triangle should be reversed to change normal direction in case of substraction, or xor)
• The most complex case if triangles are crossing each other, then we should divide triangle into parts so each of them would have simple borders to other. Each triangle subdivide into up to three triangles by each intersection (we should reserve enought memory).

Operation is heavy indeed. I think it could be nice job for compute shader.

[bugsweeper]

The difference between union, substraction, xor and intersection - which side of each mesh do we choose inside or outside relative to another mesh.
PS: this is very important feature for sculpting or games with desctructions

[bugsweeper]

The other intresting question is: what color should new surface have (only union have no new surface, other operations have cut place, every point of which should have some color or UV coordinate for texture). Should this operations take extra parameter (closure?) which would make such decision? Because for sculpting there is bad decision to leave with new surface (copied from knife surface) the color of knife. For example game Fruit Ninja cuts fruits like watermelon which could be one color (green) outside but very different color inside (red) and this is very new color, not the color from old fruit mesh or katana mesh.

[superdump]

As a note, bevy aims to be able to manage assets on web as well as native. That doesn’t mean that C++ dependencies can’t be used, but bear in mind that they will not be available on web and will likely have to be behind a feature flag as they can’t be considered core functionality given they are not available everywhere. Or something like that. I don’t know if we maintainers have explicitly defined that policy anywhere but the cross-platform support and web asset handling support is clear.

[RCC-CCN]

Just to clarify, my suggestion was not to include a C++ library as an external dependency but as a possibile reference that being C++ would need a substantial effort to transpose code/concepts.

[HackerFoo]

It might be possible to include Manifold as a dependency for WASM builds:

• https://github.com/rafaelbeckel/test-c-rust-wasm
• Align with the "C" ABI rustwasm/wasm-bindgen#3454
• https://github.com/elalish/manifold/blob/master/README.md#wasm

[pca006132]

I have some experience optimizing mesh boolean performance, here are my opinions on some of the points mentioned above:

I think the most simple naive implementation is to build a fn that can take a cuboid and subtract another cuboid.

That is a voxel-based approach, which can work. This approach impose limits on the precision of the input that you can work with, as the number of voxels will quickly blow-up as you increase precision, and the artifacts can be fairly noticeable.
Also, it can be hard to map texture back to the result.

---

Just want to point out there is no need to consume the mesh, taking a reference is just as performant.

No, it's not, because you'll end up doing a lot of cloning, assuming the mesh is first converted to some sort of spatial tree. Unless you mean a mutable reference, which is essentially the same thing, but much harder to manage in this case.

From my experience, cloning the mesh is not that slow comparing to the actual boolean operation. It is practically impossible to do the computation in-place, so you need allocation anyway. The resulting mesh will usually be quite different from the input, so the input buffer usually can't be reused.

Using references will allow you to do some optimization on the csg tree (DAG), enables sharing without expensive cloning, etc. We wrote some general tips here: https://github.com/elalish/manifold/wiki/Performance-Considerations

There may be use cases where you want to modify part of the mesh, but it is hard to make an algorithm that just mutate a part of the mesh that is changed, at least manifold is not able to do that for now (and no one is asking us to do that).

---

This task is not so complex if we divide it to a set of simple tasks (I put here list of naive task list. It based on expectation that mesh is complete and has not gaps. Resulting mesh should also be complete with no gaps):

Probably not that simple, you can also have self-intersection or invalid topology and things will become really complicated, see https://github.com/elalish/manifold/wiki/Manifold-Library

Also, mesh boolean and triangulation are full of corner cases which can be tricky to handle correctly. It took years for manifold to get to the current state, and there are still known issues. Performance is also a difficult subject, it will not be very useful if boolean operation on simple things take hours to complete (e.g. openscad is well-known for this previously when input is complicated).

---

Operation is heavy indeed. I think it could be nice job for compute shader.

This will be very hard because you are often memory-bound (host to device transfers). manifold used to have CUDA backend for some algorithms, but we later ditched it because proper CPU implementation is faster.