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

Dan Shriver tabbydan at gmail.com
Thu Nov 14 07:36:16 EST 2019


Ideally I'd like to see some way to fix manifold issues.

For instance, I like to play with epicycles and the like.  Unfortunately,
these shapes, while aesthetically pleasing tend to do a lot of intersecting
loops etc.  The end result is they are unprintable.

On Thursday, November 14, 2019, Doug Moen <doug at moens.org> wrote:

> 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/0ef469d6/attachment.html>


More information about the Discuss mailing list