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

nop head nop.head at gmail.com
Thu Nov 14 07:45:16 EST 2019


Not sure why you say they are unprintable. If you give the curve some width
it becomes something you can print. It has intersecting loops but that
doesn't mean it has a self intersecting mesh.

On Thu, 14 Nov 2019 at 12:37, Dan Shriver <tabbydan at gmail.com> wrote:

> 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.
>>
> _______________________________________________
> OpenSCAD mailing list
> Discuss at lists.openscad.org
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscad.org/pipermail/discuss_lists.openscad.org/attachments/20191114/41c70dc3/attachment.html>


More information about the Discuss mailing list