Add Boolean Operations on `Mesh`es

snailtomatoes commented 2 weeks ago

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 commented 2 weeks ago

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

ethereumdegen commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 1 week ago

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 commented 6 days ago

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 commented 6 days ago

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 commented 6 days ago

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.

bevyengine / bevy