Discuss manifoldness, co-incident faces edges etc
On 2019-11-13 22:17, nop head wrote:
Why does is it a contradiction?
The statement "There is no explicit topology but it is preserved."
contradicts itself because you cannot preserve something that does not
exist.
Carsten Arnholm
On Thu, Nov 14, 2019, at 10:32 AM, arnholm@arnholm.org wrote:
Attempting to automatically repair the kind of self intersection you
describe, i.e. two faces intersecting will give "interesting" results.
If you split the two faces into say 4 triangles it implies creating a
4-manifold edge... so an automatic repair attempt of such issues is
mostly self defeating.
Thanks for correcting me on that.
Actually, the repair would result in a 2-manifold mesh if topology information is part of the mesh, because the repair would create duplicated vertexes in the vertex list. This would fix a self-intersection problem for the purposes of running a CGAL operation; it would allow a boolean operation to succeed. Keep in mind that CGAL uses the Nef Polyhedron representation for boolean operations, and two polyhedra that meet at an edge is representable as a Nef Polyhedron. As long as the automatic repair process produces something that we can convert into a Nef Polyhedron without losing topology information, then it works.
However, if you discard the topology information (eg, when exporting to STL), then you end up with a 4-manifold edge, and the figure-8 mesh isn't 2-manifold, and isn't printable. That's the part I wasn't clear on when I wrote the earlier post.
On 2019-11-14 16:46, Doug Moen wrote:
On Thu, Nov 14, 2019, at 10:32 AM, arnholm@arnholm.org wrote:
Attempting to automatically repair the kind of self intersection you
describe, i.e. two faces intersecting will give "interesting" results.
If you split the two faces into say 4 triangles it implies creating a
4-manifold edge... so an automatic repair attempt of such issues is
mostly self defeating.
Thanks for correcting me on that.
Actually, the repair would result in a 2-manifold mesh if topology
information is part of the mesh, because the repair would create
duplicated vertexes in the vertex list.
I cannot see how this can be true. If the self intersection happens
because a 2-manifold body (with full topology representation) somehow
folds in on itself and creating overlapping volumes, the face splitting
will 4-manifold edges in all cases. The only way to avoid that is if you
could device a scheme where the volume overlap could be eliminated by
deleting faces that was inside the volume, i.e some kind of boolean
union with itself. That however, is a challenging task.
So I maintain that self intersection is a symptom of some other problem
that needs to be fixed. Trying to fix it by attacking the symptom is
likely not leading to a desirable result in most cases.
Carsten Arnholm
Following up on Carsten's comment, the self-intersection repair algorithm that I conceived of, which works by splitting faces, isn't suitable for STL/polygon soup meshes, because the resulting mesh may not be manifold. The results aren't manifold for the figure-8 extrusion, they are manifold for the swept epicycle.
My algorithm does work for CGAL and 3MF, in the technical sense of creating a valid 2-manifold mesh. However, the resulting mesh might not be printable because my algorithm can potentially produce separate regions of the model that join at knife edges, which might be very weak or even fall apart during printing.
I found an alternative self-intersection repair algorithm online. This one focuses a particular class of local self-intersections, where the model contains a thin surface, and some triangles on one side of the surface project through to the other side, creating self intersection. This is quite different from the swept epicycle model we discussed earlier. This algorithm uses "edge hammering" and "face lifting" to fix the problem and give the surface more thickness, which changes the shape of the model, and potentially makes it more 3D printable. https://imr.sandia.gov/papers/imr18/Yamakawa.pdf
On Thu, Nov 14, 2019, at 3:46 PM, Doug Moen wrote:
On Thu, Nov 14, 2019, at 10:32 AM, arnholm@arnholm.org wrote:
Attempting to automatically repair the kind of self intersection you
describe, i.e. two faces intersecting will give "interesting" results.
If you split the two faces into say 4 triangles it implies creating a
4-manifold edge... so an automatic repair attempt of such issues is
mostly self defeating.
Thanks for correcting me on that.
Actually, the repair would result in a 2-manifold mesh if topology
information is part of the mesh, because the repair would create
duplicated vertexes in the vertex list. This would fix a
self-intersection problem for the purposes of running a CGAL operation;
it would allow a boolean operation to succeed. Keep in mind that CGAL
uses the Nef Polyhedron representation for boolean operations, and two
polyhedra that meet at an edge is representable as a Nef Polyhedron. As
long as the automatic repair process produces something that we can
convert into a Nef Polyhedron without losing topology information, then
it works.
However, if you discard the topology information (eg, when exporting to
STL), then you end up with a 4-manifold edge, and the figure-8 mesh
isn't 2-manifold, and isn't printable. That's the part I wasn't clear
on when I wrote the earlier post.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
I found a boolean mesh library, an alternative to CGAL or Carve, with some incredible properties.
It is very robust. Unlike CGAL or Carve, the input can contain self-intersections. The input is not generally required to be manifold, although there is still the restriction of no open boundaries or non-manifold “flaps”, and consistent orientation.
The algorithm is based on CGAL exact arithmetic, but they have a method for converting the output to floating point without introducing self intersections.
The performance is very good: on average 7x faster than CGAL, competitive with Carve (about 12% slower). The performance gets much better if you combine many meshes using a single operation. They found one case where unioning 10 objects took a few seconds with their code, and a few weeks with CGAL.
And it is open source, part of libIGL.
https://github.com/libigl/libigl/blob/master/include/igl/copyleft/cgal/mesh_boolean.h
If the libigl boolean operators are this good, why aren't we using them? There's no reference to libigl in the github issues or pull requests. In Feb 2018, on the forum, Marius said he had talked to the author, and: "I’ve been wanting to test that out, but haven’t managed to free up enough time to clean up our interfacing with CGAL to something that makes it clean to test out various libraries.. ".
To summarize things on my end, my goals in this thread are:
- Support models containing polyhedra that touch at a vertex or an edge.
- Support import of valid 3MF files (without getting a CGAL error).
- Support export of valid 3MF files (with correct topology information included, unlike today)
My current suggestions are:
- Change the PolySet structure to contain topology info.
- Check imported meshes for bad topology[*] (not manifold, not correctly oriented, holes).
If a problem is found, print a warning message and flag the mesh as non-manifold.
Perform the same check on polyhedron() and polygon() output. - Use the libigl boolean operators, instead of CGAL.
- Add a
repair_self_intersections()module, based on libigl.
[*] Note, the "bad topology" check is relative to the topology information (vertex IDs), not the vertex coordinates. This distinction makes no difference for STL or polygon soup, but it does make a difference when importing file formats that support topology information, such as OBJ and 3MF. With the latter file formats, it is possible to encode two cubes touching on an edge as a 2-manifold shape.
These changes will improve OpenSCAD:
- Far more forgiving of bad meshes on import.
- Booleans are much faster. 7x faster on average, much bigger speedups are possible when you union a large number of complex shapes.
- Far less likely to export a bad mesh.
Based on a test of 10,000 shapes from Thingiverse, only 18% of the meshes are damaged enough that the libigl booleans won't work. The number is close to 50% for CGAL and Carve.
On 11/14/2019 5:39 AM, Ronaldo Persiano wrote:
How a self-intersection could be repaired? Before figuring a process
out to do it I need to understand what outcome the process should
have. What would be the repair of the linear_extrusion of a single
polygon tracking the figure of an 8?
If one can address the manifold question, the answer seems like the same
answer that is used in 2D drawing programs. Try it: draw a closed
figure 8, and then fill it. The "inside" of the figure is the inside of
the two loops, as a human would expect. The linear extrusion of that
then seems straightforward. (Again, ignoring the manifold question.)
(I tried Corel Draw and Inkscape.)
On 11/14/2019 7:32 AM, arnholm@arnholm.org wrote:
I think self-intersections are almost always a sign of something else
gone wrong, it is typically a body that overlaps itself and and not a
result of a boolean operation. A self-overlapping volume is physically
impossible. There are lots of ways to use bodies that are not
2-manifold, but a self overlapping volume seems like an obvious mistake.
Is it?
Consider the 2D case. I'm drawing with a paintbrush, and so I'm drawing
areas, not lines. I draw a figure-8. It's self-intersecting, but it's
clearly not impossible. The two parts of the stroke are unioned.
If we view the 3D equivalent as painting in 3D with a 3D brush, the
result doesn't seem impossible at all.
If we were drawing with voxels, I suspect that the question wouldn't
even arise.
A figure of 8 is only a self intersecting mesh if you create it by sweeping
a 2D shape. If you create it by unioning two rings the mesh will not
contain any self intersections. To avoid the problem with sweep you can
sweep sections that don't self intersect and union them. The problem of
repairing a completely general a self intersection mesh is the exactly the
same complexity as union because that is what union does. It computes the
boundary of two intersecting meshes, removing the internal faces.
The fact that 3MF says the positive fill rule should be used creates a sort
of Boolean XOR and is exactly the problem I had when printing somebody
else's design. Skeinforge used the positive fill rule but Cura at the time
printed the union.
"there is no explicit topology but it is preserved."contradicts itself
because you cannot preserve something that does not exist.
No it doesn't because any manifold has some topology. If the manifold can
be stored in an STL file and reconstructed properly it still has the same
topology. That will be true as long as there are no shared edges. So
although the topology is not explicitly stored it can be reconstructed from
a polygon soup. I.e. you can pair up the edges and make a data structure
that explicitly connects them.
On Thu, 14 Nov 2019 at 18:43, Jordan Brown openscad@jordan.maileater.net
wrote:
On 11/14/2019 7:32 AM, arnholm@arnholm.org wrote:
I think self-intersections are almost always a sign of something else gone
wrong, it is typically a body that overlaps itself and and not a result of
a boolean operation. A self-overlapping volume is physically impossible.
There are lots of ways to use bodies that are not 2-manifold, but a self
overlapping volume seems like an obvious mistake.
Is it?
Consider the 2D case. I'm drawing with a paintbrush, and so I'm drawing
areas, not lines. I draw a figure-8. It's self-intersecting, but it's
clearly not impossible. The two parts of the stroke are unioned.
If we view the 3D equivalent as painting in 3D with a 3D brush, the result
doesn't seem impossible at all.
If we were drawing with voxels, I suspect that the question wouldn't even
arise.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 14.11.2019 19:42, Jordan Brown wrote:
On 11/14/2019 7:32 AM, arnholm@arnholm.org wrote:
I think self-intersections are almost always a sign of something else
gone wrong, it is typically a body that overlaps itself and and not a
result of a boolean operation. A self-overlapping volume is physically
impossible. There are lots of ways to use bodies that are not
2-manifold, but a self overlapping volume seems like an obvious mistake.
Is it?
Consider the 2D case. I'm drawing with a paintbrush, and so I'm drawing
areas, not lines. I draw a figure-8. It's self-intersecting, but it's
clearly not impossible. The two parts of the stroke are unioned.
So if you changed paintbrush colour along the way, what would the colour
of the intersecting area be?
What I was thinking of was the case in 3D where the topology is well
defined and closed, but where the geometry (i.e. the coordinates) are
such that some vertices fall within the volume of another part of the
body. What I meant it by physically impossible was if you took a steel
rod and bent it such that it would overlap itself. You cannot have two
instances of material occupying the same volume even though you can
formulate it with a polyhedron.
Your paintbrush example is kind of equivalent.
Carsten Arnholm