On 13.11.2019 21:39, nop head wrote:

This statement contradicts itself.

The obvious suggestion is to fix that for file formats with explicit
topology.

Carsten Arnholm

Why does is it a contradiction? A polygon mesh represents geometry and by
finding which facets share edges it is unambiguous, so the topology of the
geometry is preserved as long as it is manifold. For non manifold geometry
you need a more complex data structure because edges can no longer be
paired up unambiguously.

On Wed, 13 Nov 2019 at 21:01, Carsten Arnholm arnholm@arnholm.org wrote:

Another way of putting it is CGAL has a much more complex data structure
that has explicit topology. It can created that unambiguously from a
polygon soup without any guesswork but only if it is manifold.

On Wed, 13 Nov 2019 at 21:17, nop head nop.head@gmail.com wrote:

On Wed, Nov 13, 2019, at 8:05 PM, nop head wrote:

Not true. STL is ambiguous even if it is 2-manifold, because it can still contain self-intersections. Self intersecting STLs are interpreted differently by different slicers. You mentioned this yourself in a previous message:

Just to be clear, the 2-manifold property doesn't say anything about whether a mesh is self intersecting or not.

OpenSCAD can export self-intersecting STL just by intersecting some shapes that are themselves free of defects. And you don't get a warning when this happens. Nobody seems to know how to fix this. So STL files exported by OpenSCAD may be ambiguous.

3MF does not suffer from the same problem. 3MF meshes are required to be 2-manifold (the 2-manifold property applies to vertex IDs, not vertex values, as I explained earlier). However, 3MF meshes are allowed to have self-intersections, because lots of different mesh generation programs (not just OpenSCAD) produce self-intersecting meshes, and nobody knows how to fix this. 3MF works around this problem by mandating a specific algorithm that slicers must follow to interpret self-intersecting meshes. As a result, 3MF meshes are portable: they are guaranteed by the standard to print the same way on all slicers.

There's more. OpenSCAD polygon-soup meshes can change from being manifold (in the CGAL data structure) to non-manifold during STL export, due to the conversion of exact rational numbers in the CGAL data to approximate floating point in the STL output. Two vertices that are distinct in the CGAL data can become equal in the STL output, and that's enough to make the mesh non-manifold. And we don't know how to fix this.

This problem is fixable for 3MF export. All we need to do is preserve the "topology information" (the vertex table) when we convert CGAL data to 3MF data. The 2-manifold property that is defined on vertex IDs in the vertex table is not affected by conversion of exact rationals to floating point. What can happen is that two vertexes with distinct IDs and distinct coordinates can become modified by conversion to floating point, so that the coordinates are the same. But the vertex IDs are still distinct. And this situation is permitted by the 3MF standard, so the mesh remains valid.

In conclusion, STL export is inherently broken and cannot be fixed. However, 3MF export can be made to work correctly, if we modify OpenSCAD to preserve and maintain 3MF topology information.

On 11/12/2019 6:25 PM, MichaelAtOz wrote:

I suspect that we're up to at least six variations of geometric
peculiarities that cause beginners problems:

• Shared vertices or edges (or maybe faces)
• Z-fighting with zero-thickness results from difference (and
  intersection?  and shared faces of different colors?)
• Self-intersection
• Polyhedra with winding errors
• Blatantly malformed polyhedra (missing faces, et cetera)
• The "convexity" parameter

I suspect that the answers to each are completely independent of one
another.  I suspect also that the class of "malformed polyhedra" might
well be very diverse.

Unfortunately, I have no idea.  At least in a sense I expect them to all
be solvable because, to paraphrase Justice Stewart
https://en.wikipedia.org/wiki/I_know_it_when_I_see_it, I know the
right answer when I see the scenario.

But that doesn't mean that they are practically solvable.  They might
require expertise that is not available, or impractical amounts of work,
or impractical amounts of computation.

The only one that I have a hint on is "convexity"; setting it to 10
seems to fix all of my convexity problems and doesn't seem to noticeably
impact display times.  I can make some guesses on blatantly malformed
polyhedra, but I'm not sure.  (And I expect that my guesses wouldn't
catch all cases.)

With respect to the manifold-ness question, and in particular whether
it's useful and meaningful to represent objects with shared vertices or
shared edges... I think I've said all that I have to say and am
repeating myself, so I'll try to shut up.

On 11/13/2019 9:39 AM, Max Bond wrote:

OK, I know I just said I'd shut up, but this is a specific question to
which I have a specific (example) answer.  This is not concocted; it's
real.  The intent is to produce something visually similar to a shingled
roof.  It basically makes a checkerboard where all of the black squares
are slightly raised.  (Because the shingle thickness is down around the
vertical resolution of the printer, trying to represent the actual slant
of the shingles wouldn't work.)

inch = 1;
foot = 12*inch;
layer=0.3;
epsilon=0.1;

module roof(w,l,t,shinglew,shinglel, shinglet) {
    cube([w,l,t]);
    translate([0,0,t]) {
        for (iy=[0:1:floor(l/shinglel)-1]) {
            for (ix=[iy%2:2:floor(w/shinglew)-1]) {
                translate([ix*shinglew, iy*shinglel, 0]) cube([shinglew-epsilon, shinglel-epsilon, shinglet]);
            }
        }
    }
}

roof(w=8*foot, l=4*foot, t=0.6*inch, shinglew=6*inch, shinglel=4*inch, shinglet=layer);

The rendering ends up with optical illusions that make the shape unclear
from most directions, but this one is pretty good:

Here's what it looks like in plastic (pardon the poor focus):

Why is this a problem?

Note that I couldn't use the obvious solution; I had to inject
"-epsilon" so that the raised rectangles wouldn't touch at the corners. 
I don't remember whether I remembered to do that when I constructed it,
or if I had to run into an OpenSCAD non-manifold-ness complaint and then
add them... but I shouldn't have had to add them.

And (OK, repeating myself a bit) I don't care in the slightest what the
slicer does with those intersections, whether it considers the
rectangles to have separate perimeters or not.  The corners should be
awfully close to one another, and whether that means slightly separated,
or slightly overlapping, or precisely touching is not important.

(Half of the time I say that the slicer should color between the
lines, which means that "square" convex corners will always be round and
the corners will not touch, and half the time I say that no matter how
thin the object is, it should still be represented in the plastic, even
if that means coloring outside the lines, and so a zero-thickness
intersection gets a single minimal extrusion across it.  Either answer
would be reasonable and understandable.)

Now, note:  I'm talking about the input 3D solids and the output
plastic.  I'm not talking about the mesh in the middle; that's an
implementation detail that I shouldn't have to care about.  I accept
that a "polygon soup" representation might be ambiguous.  (I'm not sure
I've seen one yet, but I'm willing to accept it on faith.)  It might
well be that solving this problem would require fundamental changes to
OpenSCAD and the slicers.

I had another real-project case that ran into the same problem, but it
was more complex.  Basically, it was equivalent to having an inset
square with a raised circle in it, where (to the accuracy of my
measurements) the diameter of the circle was equal to the length of the
edge of the square.  I had to fudge them a bit to get them to be different.

whether a mesh is self intersecting or not.

Sorry I thought self intersection is not manifold because it creates zero
thickness sections. If it is then all I have said is correct if you change
non-manifold to non-manifold and not self intersecting.

"topology information" (the vertex table) when we convert CGAL data to 3MF
data.

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.

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.

On Thu, 14 Nov 2019 at 03:41, Jordan Brown openscad@jordan.maileater.net
wrote:

Also polygon soups can describe self intersecting geometry in general. What
they can't do is handle meshes with shared edges. These are like
singularities where the shape goes from 3 dimensions to 2. As long as each
edge of a facet has a unique partner running in the opposite direction you
can stitch them all together in an unambiguous way. However I don't think
CGAL allows self intersections even without shared edges.

On Thu, 14 Nov 2019 at 07:47, nop head nop.head@gmail.com wrote:

On Thu, Nov 14, 2019, at 2:47 AM, nop head wrote:

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?

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.

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@moens.org wrote: