Rework CSG algorithms to be more reliable

[mrjustaguy]

Describe the project you are working on

Procedural Mesh Generation

Describe the problem or limitation you are having in your project

Current Godot CSG Algorithm has issues with properly determining where 2 triangles intersect, as if the triangle is too small it causes crackling issues (https://github.com/godotengine/godot/issues/43755 and https://github.com/godotengine/godot/issues/41140 for reference)

Describe the feature / enhancement and how it helps to overcome the problem or limitation

by reworking CSG, Such issues can be mitigated/eliminated. Here's how:

1. Separation of Intersected Triangles and Non-intersected Triangles (algorithms are Multi-thread Friendly)
2. Splitting the Intersected Child Triangles (depending on operation, and where the parent and child triangles are facing, delete triangle(s) on one side of the parent's triangle plane that the child triangle is intersecting) - Note: Could be done by splitting a triangle with every plane into 3 separate triangles and removing 1 or 2 depending on where they are and what operation is needed, and adding the leftover triangle(s) to a dictionary with the key being the original triangle id, and the values being sets of 3 vertices, and then after all the cuts are done, run an algorithm to remove overlapping parts of all those triangles, same algorithm can be used for parent triangles
3. Fill Child Triangles that have connections to what remains of the cut down Intersected Child Triangles - Note: Mesh Vertices/Edges/Faces aren't connected, so would have to generate vertex/edge/face indexes
4. Erase the necessary Parent Triangle Parts Based on the Intersections (see note after 2. step)
5. Merge all the constructed triangles and if not done yet get UV data, Normals, generate collisions etc...

Note - The Algorithm Below is more or less what I stated here, just rephrased to be more code-like

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Algorithm: 1.0 Get Intersecting Faces/Triangles 1.1 Get Faces Without Intersections (note: 1.0 and 1.1 are stored as 2 different categories of faces) 2.0 Split Intersecting Child Triangles Based on Operation (Keep only those that are: Above Parent Triangle in Union, Below Parent Triangle in Subtraction (and invert Faces), Below Parent Triangle in Intersection (without inverting Faces)) (Note: By Above I mean Visible Face, Below I mean Not Visible Face Sides) 3.0 Add Non-Intersected Faces that share an Edge with 2 newly split Leftover Triangles (or generate new ones, as there are 3 verts (1 shared, and 2, one for each edge of the Leftover Triangles) 4.0 Discard Non-Intersected Faces that don't have a connection to the Properly Split Leftover Triangles 5.0 Cut out Parent Face Properly (Keep only those that are: Above Child Triangle (original) in Union, Above Child Triangle (original) in Subtraction, Below Child Triangle in Intersection) 7.0 Construct/Merge the final Mesh

Example Project in GDScript (WIP - Triangle Splitting 90% done (There is a special case that causes the Triangle splitting code to to miss cutting some triangles, or has an unwanted triangle that is intersecting a mesh face and triangle finalization hasn't been started)): CSG.zip (UPDATED 09/02/2021, 9:55 pm CET(GMT+1)) Mesh Separation.zip (This needs to be merged with the CSG code, and used for separating the non-intersected parts of the meshes, after which last task is cutting intersected triangles and PoC is done)

If this enhancement will not be used often, can it be worked around with a few lines of script?

No

However https://github.com/godotengine/godot-proposals/issues/892 could potentially get the current CSG bugs to be Far less common & far less visible as the main issue is the Snap.. the smaller it can be, the less cases where the bugs show up and are noticable - however how effective that will be in reality is unclear right now.

Is there a reason why this should be core and not an add-on in the asset library?

CSG is Core, It makes sense to have it Functional in Core instead of having a Broken (Possibly on a fundamental level even) Core and a Functional Addon.

Notes:

1. I'd Work on re-Implementing/fixing CSG in Godot myself, However I'm not proficient enough with C++ to do so.
2. There are some Special Cases that need to be checked with the 1st Intersection checking stage, which I've worked around in the Project example, which could probably be done a lot better. I've Rewritten the example, it'll be cutting faces in a separate pass after all the intersection points are gathered, and then it'll just Draw out the polygons that are to be deleted/kept (depending on operation) - this method is used for both child and parent triangles
3. The Project is WIP and Will be Updated Periodically as I get past milestones (Triangle Spliting, Cutting unwanted triangles out of the mesh, etc..) Abandoned due to technical issues with mesh separation, latest version is posted above if you care to try and figure out what I could not. - Figured out Mesh Separation, however properly drawing out triangles is the issue now, in fact it's the last hurdle to a functional Reliable CSG
4. Probably Best Wait for the Whole Proof of Concept Project to be Finished (if it ever does) and use it as Base for the rework.
5. In the unlikely case that someone works on the Prototype and makes progress on it, please comment what you have and where you are stuck, as I'll still be following this closely and might be of some help.

[mrjustaguy]

Closing in favor of #2271 which would be much simpler to implement (as it's just adding check & clean up functionality) and would probably deal with a lot of the CSG issues this aimed to deal with.

[mrjustaguy]

Note: sth like https://github.com/goostengine/goost/pull/39 Could be used to cut polygons out of triangles, would only need to convert the triangle and polygon vertex coords from 3d to 2d which is a fairly simple transformation, do the cut to get the proper triangle cutout and transform it back