[OpenSCAD] Discuss manifoldness, co-incident faces edges etc

Doug Moen doug at moens.org
Thu Nov 14 07:03:37 EST 2019

On Thu, Nov 14, 2019, at 2:47 AM, nop head wrote:
> It isn't only during STL export that this goes wrong. A lot of OpenSCAD operations use a PolySet representation, which is a polygon soup of doubles. Whenever it converts from CGAL rationals to PolySet doubles is can cause self intersections and degenerate triangles. Any of these will give a CGAL exception if they get converted back to NefPolyhedra to do another CSG operation. This is the source of endless CGAL exceptions that people report. To avoid them the geometry has be manifold and free of self-intersections even after its vertices are snapped to a grid and or truncated. So you have to avoid close vertices as well.

This is fixable, at least partly. We need to change the PolySet representation to include a vertex table, which contains the topology information.

When we convert a Nef Polyhedron to a Polyset, the algorithm is:
 1) Using the CGAL representation of coordinates (rational numbers), construct the vertex table. Two vertexes which have the same coordinates as rational numbers will have the same vertex ID.
 2) Once the vertex table is constructed and vertex IDs are assigned, then we convert rational numbers to floating point. At this stage, errors may be introduced. For example, two distinct vertexes that are very close together might merge into one due to floating point imprecision. But these vertexes will still have different vertex IDs, so the topology is preserved.

At this point, we can export the Polyset as a 3MF file (or as any file format that has a vertex table), and the topology will be correct. In the case of 3MF, if the topology is valid then the mesh is valid for 3D printing. There is still a problem with CGAL, but I'll address that.

When we import a 3MF file, we can test if it has correct topology (test that it is manifold). For example, we could use CMeshObject::`IsManifoldAndOriented`() from lib3mf, a library we already link to. The documentation says this operation is fast. If the mesh is not manifold, then it is badly damaged: according to the 3MF standard, it isn't 3D printable. CGAL operations won't work: I think the conversion to a Nef Polyhedron will just fail. We could issue an error message, or we could print a warning and set a not_manifold flag on the PolySet object, to be consulted if a CGAL operation fails.

I would like to change the polyhedron() operator, to perform the same fast validation test on the output (is it manifold). We print a warning if the polyhedron isn't manifold, and set a flag. Maybe there is more we can do. The polyhedron() arguments include a vertex table, so we preserve that vertex table in the PolySet.

When we import a 3MF file, the mesh may be self-intersecting. This is legal, according to the 3MF standard. A mesh that is manifold but self intersecting should be 3D printable, according to the standard. But CGAL operations may fail, if the self intersection occurs in the neighbourhood of where CGAL needs to split faces. CGAL 5.0 throws a specific exception when it detects self-intersection, which we can catch and handle.

In order to conform to the 3MF standard, OpenSCAD is required to be robust in the presence of self-intersection. CGAL boolean operations don't support this, however, and I so far haven't found a competing mesh library whose boolean operations support this. Such a library probably doesn't exist. That means we need to repair the self-intersections in order for CGAL to succeed.

CGAL 5 has a function for detecting self-intersection: CGAL::Polygon_mesh_processing::does_self_intersect(). CGAL 5 has a suite of mesh repair functions, but the documentation for these functions does not mention repairing self-intersection. However, libigl has a CGAL-compatible API for repairing self intersections (include/igl/copyleft/cgal/SelfIntersectMesh.h). Maybe we can use it?

> So in a lot of cases there is no "topology information" to preserve. Whenever you do F6 and don't get the "simple:" report then the final result is a PolySet, but even if the final result is a CGAL NefPolyhedron PolySets might have been use for intermediate results.
> So I don't think the problem is fixable for 3MF export without changing PolySet to contain topology and also fix all the places that truncate or snap to grid to fix the topology, which is hard. If one only needs to design manifold geometry without self intersections then PolySets don't need to store topology but the truncation problem sill needs to be fixed.

I don't really understand the rationale for "the places that truncate or snap to grid to fix the topology". It sounds like a bad idea? We should be using alternate methods? But I don't know.

My approach is not to repair the topology, if at all possible, because there's no good way to do that. Instead, we should always try to maintain valid topology (by storing a vertex table in PolySet). The result of a CGAL operation will always contain valid topology. 3MF files are required to contain valid topology, even if the vertex values are off and there is self-intersection. Whenever we import a mesh or evaluate a polyhedron() or polygon() call, we should test for valid topology and complain loudly if the topology is bad. If a CGAL operation fails on a mesh or polygon due to bad topology, then we report an error that mentions bad topology. Maybe we can experiment with the CGAL functions for repairing topology and see if they help?

 We should definitely repair self intersections. I don't think that starting from polygon soup and snapping to a grid is a valid way to repair self intersections. I think that self-intersection repair should use topology information (the vertex table) as a starting point. That way we don't have to guess what the topology should be, we know. The libigl self-intersection repair algorithm DOES use a vertex table for the input mesh. This gives me hope that we could be using more robust/effective methods for dealing with defective meshes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscad.org/pipermail/discuss_lists.openscad.org/attachments/20191114/c81b7076/attachment.html>

More information about the Discuss mailing list