BooleanOperation 'union' results in overlapping triangles which is an error

[R7President]

After performing a BooleanOperation "union" on 2 cubes, the resulting stl file is not correct, which results in overlapping triangles errors.
Overlapping triangles can cause other code to behave oddly. In particular slicer programs if the stl output is sent to a 3d printer. Different slicers respond to this error differently.

In the attached jpg, the blue arrows are pointing at triangles that have at least 1 side that has another vertex superimposed on top of the line, but not on a vertex.
To make these correct the indicated triangles need to be replaced with 2 triangles where the extra line is from the overlapping vertex to the vertex opposite it on the labelled big triangle.
I added the dashed line to show what is required.

I believe the fix has to be in csg.js in the function JSM.BooleanOperation
although possibly it needs to be fixed in JSM.ClipPolygonWithBSPTree

but I do not understand this code enough to suggest a solution.

[R7President]

Note that this is only a problem for compatibility with other programs such as 3D printer slicers, or exporting to other editors. If you want to limit the usefulness of JSModeler only to visual displays in the browser then this is not an issue.

It seems to me like the BSP algorithm is fundamentally flawed and a re-write will be required. (I think issue 2 is the most important).

1. comparing all polygons in one shape to those of another will fall apart when more complex shapes are used such as an STL import, or even a sphere with a lot of triangles.

• suggest that instead you limit it to comparing only those polygons whose bounding box overlaps with the original polygon.

2. By breaking the original polygon up into sub-polygons you will miss the error cases described in the picture because although the plane intersects the original polygon it will not intersect the sub-polygons so the resulting split will be dependent on what order the split is done.

Suggested algorithm:
use the existing algorithm to break up the polygon into frontPolygons and backPolygons, then merge all of the frontPolygons that share sides (and all of the backPolygons that share sides) note that there might be more than one of each, but the normal case is one of each. I think this is a small change to csg.js in BooleanOperation/ClipNodePolygonsWithTree, after ClipPolygonWithBSPTree.

just a random comment:
There seems to be a fundamental problem with all 3d graphics libraries that define a triangle with 3 floating point XYZ vertexes: to see if 2 triangles share a vertex you must do a floating point equal test of each of the XYZ numbers. If you make even a small difference in how you calculate a new vertex for two adjacent triangles then the equal test will fail (due to a difference in the 10th decimal point). I think it would be better to have an array of vertexes and then to define a triangle just use 3 integers one for each vertex of the triangle (which is an index into the array of vertexes). This makes it much easier to see if two triangles share the same vertex. (a simple integer compare).

[kovacsv]

Thank you for the report. I know about the limitations of the BSP tree algorithm. It's in an experimental stage, and sometimes it fails, because it can create really small triangles and even overlapping ones.
I know a rewrite would be great to achieve better results, but unfortunately I don't think I'll have time for that. Any contribution is welcome if you feel you could help.