CSG box and sphere subtract displays cracking from missing triangle

[goatchurchprime]

Godot version:
3.2.2.stable

OS/device including version:
Windows10

Issue description:
CSG subtraction of a SphereMesh from a CubeMesh given in the attached scene is missing a triangle.

The crack does not go away when I turn off backface culling, so I think the triangle is being discarded rather than inverted. The too-close points should instead be pulled closed.

Steps to reproduce:
Cubemesh size = Vector3( 0.1, 0.1, 0.2 )
Spheremesh size = radius 0.1, height 0.2, radial_segments 12, rings 12 at position Vector3(-0.0544916, 0, -0.0286622 )

Minimal reproduction project:
csgmesh_cracked.zip

[goatchurchprime]

Simpler example involving 3 boxes
handright_cracked2.zip

[Calinou]

cc @madmiraal

[madmiraal]

First, it's worth noting that these missing triangles would probably not be visible from the camera in the game. The missing triangles are noticeable in the two examples, because the viewport is zoomed in on small shapes that have dimensions of only around 0.1.

To avoid creating unnecessary triangles, triangles that have a dimension less than the CSGShape Snap are not created. The default (and minimum) CSGShape Snap is 0.001. So in the examples, a triangle of less than 1/100th the width of the shape is not created. The problem is, different snapping decisions being made on adjacent triangles as the shapes are being created.

Using the simpler example above with just the first two boxes, you can see how the faces of the original (red) box have been snapped differently, which results in the gap being visible in the green box:

This happens when the diagonal is longer than the snapping distance, and the perpendicular distances are less than the snapping distance.

What's missing is the merging of the vertices of the final shape. As suggested in the OP:

The too-close points should instead be pulled closed.

[goatchurchprime]

The cracks show up pretty clearly in my game, even in the shadows. Units are in metres for VR use, and those models are the size of my hands. I am also getting shards, the opposite of cracks, poking out of my surfaces,

The use of epsilon values (the "snap" value here) in commercial CADCAM software is the source of many bugs that can never be fixed. The problem is that is_equal_approx() is not a transitive relation (a approx b, and b approx c does not always mean a approx c), while many of the algorithms assume that it is and crash. Sometimes their code will rerun functions multiple times with slightly different values of this epsilon until one doesn't crash.

Mesh-based CSG is much harder to get right than it looks because there are an unbelievable number of special cases that you won't know until they show up as bugs years later. Using voxels can be a worthwhile approximation.

In my opinion this is a definitely domain of a specialist third-party library, like zlib or jpeg compression. It's not an important enough part of this project to be worth debugging to the bitter end.

The place I've used a lot of this type of CSG is OpenSCAD, which depends on http://opencsg.org/ which is GPL, so is a problem.

The other place where these functions are available is CGAL, like here:
https://doc.cgal.org/latest/Polygon_mesh_processing/group__PMP__intersection__grp.html
This can be licensed under LGPL. However, I've looked through the godot thirdparty directory and there's nothing there with that license, so that's probably a problem too.

Has anyone looked hard for an MIT version of these algorithms? Maybe the godot code could spun off as a thirdparty mesh algorithm where it will be easier to debug. The problem with bugs when it is part of this bigger system is that when they are quite hard to fix there's always a sense of: Is this worth it when we can usually find a way to work around it in this case.

[Zireael07]

@goatchurchprime: Yes, Godot devs did look for a CSG library that would be compatible with Godot's license, and IIRC found none (OpenSCAD and CGAL were both proposed)

[TheSHEEEP]

I basically have a similar problem in my prototyping.

The idea was to utilize CSG for procedural content generation, as frankly, it is just so obvious it should be used for that. It's so easy to use and construct procedural levels with it, even supporting different materials.
As simple as building with Lego - compared to the nightmare it would be to do the same with the SurfaceTool and setting all vertices, indices, etc. manually.

But there are just way too many bugs (no doubt stemming from various special cases).
You can get rid of some of them by decreasing the snap value - but that also seems to increase the time used for mesh creation, making it not very suitable for procedural generation at runtime any more.

In the end, I think we just have to face the reality that CSGShape is not fully suitable for production and never will be.
You could lament the choice of only allowing MIT in the licenses, but it is what it is.
The real question is: What to use instead? If the only answer is SurfaceTool, Godot has a real problem when it comes to procedural mesh generation.

[fire]

@goatchurchprime I had trouble integrating manifold, but it is Godot Engine MIT license compatible.

elalish/manifold#91

Perhaps others can assist.

[fire]

Testing a new promising mysterious library.