Hi,
The last few days I have been experimenting with some code to detect and "heal" problems in polyhedra (yes I know there are several such tools out there already, but I want some more control). In the process, I manually created a test polyhedron in OpenSCAD with a couple of deliberate mistakes, to see what would happen. Here is my code (warning, buggy polyhedron!): union() { polyhedron( points=[ [1,1,1] ,[1,1,1] ,[1,0,1] ,[1,1,1] ,[1,1,1] ,[0,1,1] ,[1,1,1] ,[1,1,1] ,[1,1,1] ,[1,1,1] ], faces=[ [2,1,0] ,[3,2,0] ,[6,3,0] ,[1,5,0] ,[5,6,0] ,[4,7,1] ,[3,4,2] ,[8,4,3] ,[6,8,3] ,[9,7,4] ,[8,9,4] ,[7,6,5] ,[9,8,6] ,[7,9,6] ] ); }; The points with 0 in X or Y are the deliberate buggy points. The faces near those points are not all topologically connected with each other, although it is not immediately obvious from the code. All the faces are oriented properly, but one of the top faces skip those points with zero coordinates, so it isn't really a properly closed polyhedron. The surprise is that OpenSCAD does not complain or give any warning that there is a problem with such a polyhedron and will silently export an STL with the exact same problem. However if you try AMF export there is a hard crash (2015.03, Win7). I wonder why such problems not detected/reported in OpenSCAD? A related question is: Why does F6 apparently not fail, but the STL is still invalid? After running my healing code on the above polyhedron, the result expressed in OpenSCAD syntax becomes: union() { polyhedron( points=[ [1,1,1] ,[1,1,1] ,[1,0,1] ,[1,1,1] ,[1,1,1] ,[0,1,1] ,[1,1,1] ,[1,1,1] ,[1,1,1] ,[1,1,1] ], faces=[ [2,1,0] ,[3,2,0] ,[6,3,0] ,[1,5,0] ,[5,6,0] ,[2,5,1] ,[3,4,2] ,[7,5,2] ,[4,7,2] ,[8,4,3] ,[6,8,3] ,[9,7,4] ,[8,9,4] ,[7,6,5] ,[9,8,6] ,[7,9,6] ] ); }; I.e. one of the top faces has been replaced by 3 new faces to make it a valid polyhedron. Now OpenSCAD exports a valid STL and also does no longer crash on AMF export, but exports a valid AMF as would be expected. Any thoughts on this? Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
It's a bug. There are probably multiple issues open. Like this one:
The consensus seems to be that we should report problems, and automatically repair the mesh when feasible.
On Friday, 2 December 2016, Carsten Arnholm <[hidden email]> wrote: Hi, _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
On 02. des. 2016 21:53, doug moen wrote:
> It's a bug. There are probably multiple issues open. Like this one: > > https://github.com/openscad/openscad/issues/1864 > > The consensus seems to be that we should report problems, and > automatically repair the mesh when feasible. Thanks for the confirmation. Yes, checking for manifoldness and zero area triangles would catch most issues. However, the problem isn't limited to the case of import from external files as this case shows. Reporting such issues should be a requirement I think. Automatic repair sounds good but may generate its own issues. As mentioned, F6 does not complain so there must be something going on already. The funny thing is that the STL output is according to the buggy input. Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by doug.moen
How do you detect the problem with your code? Do you convert the polyhedron data to some other data structure to find it?
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by cacb
> On Dec 2, 2016, at 17:19, Carsten Arnholm <[hidden email]> wrote:
> > As mentioned, F6 does not complain so there must be something going on already. The funny thing is that the STL output is according to the buggy input. > If you try to union with another object, it will complain. The AMF crash shouldn’t happen. I believe that’s a separate new bug. There are multiple issues related to this, .e.g: o Correctness analysis o Error reporting, error visualization o Mesh repair o Snaprounding of exact polyhedrons I’m working on some of these: https://github.com/openscad/openscad/issues/1580 The rabbit hole goes pretty deep though. If you have good ideas on how to heal polyhedra, either on input or after snaprounding, I’d be interested. Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by Ronaldo
On 03. des. 2016 00:01, Ronaldo Persiano wrote:
> How do you detect the problem with your code? Do you convert the > polyhedron data to some other data structure to find it? Yes, you need intermediate data structures in addition to the polyhedron. The basics are rather simple though. Below is a C++ snippet showing one way to detect nonmanifold edges (m_poly is a 'polyhedron3d' much like the OpenSCAD polyhedron): // perform edge use count std::map<size_t,size_t> edge_count; size_t nface = m_poly>face_size(); for(size_t iface=0; iface<nface; iface++) { const polyhedron3d::pface& face = m_poly>face(iface); size_t nedge = face.size(); size_t last_edge = nedge1; for(size_t iedge=0; iedge<nedge; iedge++) { size_t iv0 = face[iedge]; size_t iv1 = (iedge<last_edge)? face[iedge+1] : face[0]; size_t edge_id = std::min(iv0,iv1)*1000000 + std::max(iv0,iv1); edge_count[edge_id]++; } } This will detect edges with problems, as any edge with a count different from 2 is nonmanifold. This is the basics for detection, fixing takes a bit more. Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by kintel
On 03. des. 2016 02:54, Marius Kintel wrote:
> If you try to union with another object, it will complain. > The AMF crash shouldn’t happen. I believe that’s a separate new bug. Indeed, it must be somehow related to the buggy polyhedron, but it seems to be an independent bug causing crash. The buggy polyhedron can be represented as AMF just like it can be written to STL. > There are multiple issues related to this, .e.g: > o Correctness analysis Essentially this boils down to manifoldness and face area checking. Speaking of which, importing from AMF would make manifoldness checking easier since it already has explicit topology. > o Error reporting, error visualization Have a look at KISSlicer, it classifies and visualizes nonmanifold edges. > o Mesh repair Somewhat harder. It needs to be iterative in my experience. When you fix one problem, another is revealed that was originally not directly observable. If all goes well, a few iterations later you end up with no more problems. Things to fix are duplicate vertices, nonmanifold edges of various kinds and faces requiring subdivision (as in the example I showed). > o Snaprounding of exact polyhedrons I am not sure exactly what this refers to, but perhaps it relates to coordinate representation in CGAL and matching duplicate vertices. As I am not using CGAL in my code I have an independent vertex matching scheme which essentially is creating 'vertex clusters', i.e. finding all groups of vertices within a specified coordinate tolerance of each other. Average coordinates are computed for the clusters and a new 'cluster vertex' is created to replace all the others. Originally I did this to fix individual vertex duplication errors in a connected polyhedron, but it also works to reconnect a totally disconnected (all edges are free edges) polyhedron created from naive reading of STL (example below). Again, importing from AMF would make it faster, easier and safer. > I’m working on some of these: https://github.com/openscad/openscad/issues/1580 > The rabbit hole goes pretty deep though. Yes, I agree that if you dig into the real issues it goes deep. It should be mentioned that the above 'clustering' technique creates interesting side effects such as topologically collapsed faces or other variants of zero area faces (to be discarded). Sometimes also duplicate backtoback nonzero area faces result, where removing one of the duplicate faces causes new nonmanifold edges to reveal themselves etc. With some luck, after a few iterations things settle down into a consistent polyhedron, or alternatively the whole polyhedron unravels down to nothing :) > If you have good ideas on how to heal polyhedra, either on input or after snaprounding, I’d be interested. Se the code snippet I posted and the above comments. In the reference you gave https://github.com/openscad/openscad/issues/1580 there is talk about 'edge flipping' to fix zero area faces. This seems to imply you have explicit edge representation. If you don't, i.e. faces defined only by vertex references, then it is trivial: You can just discard zero area faces, even in a connected polyhedron. I looked at one of the regression cases, i.e. https://github.com/openscad/openscad/commit/08154b19215254c5f60f17af3dd8fdd30d41462b OpenSCAD creating "issue1580backtoback2.stl" I tried running this through my experimental code: >polyfix issue1580backtoback2.stl Parameters: input_file = issue1580backtoback2.stl polyhedron 0, tol=0.01, maxiter=50 iteration 0: vertices=36 faces=12 warning: nonmanifold edges: uc(1)=36 merged 27 vertices, removed 0 collapsed faces split 2 faces total changes=29 no warnings iteration 1: vertices=9 faces=14 total changes=0 no warnings Writing: issue1580backtoback2_polyfix.amf polyhedron 0: vertices=9 faces=14 : no warnings So it succeeds. The resulting polyhedron in OpenSCAD syntax becomes polyhedron( points=[ [2,0,0] ,[2,4,0] ,[0,0,0] ,[0,1,0] ,[0,2,1] ,[0,2,0] ,[0,4,0] ,[2,0,0] ,[2,4,0] ], faces=[ [4,1,0] ,[3,2,0] ,[1,3,0] ,[2,4,0] ,[5,3,1] ,[6,5,1] ,[4,6,1] ,[7,4,2] ,[3,7,2] ,[5,7,3] ,[8,6,4] ,[7,8,4] ,[8,7,5] ,[6,8,5] ] ); So I think one observation is that healing using a simpler datastructure makes healing simpler... Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

Hi Carsten,
1) Manifoldness While a locally manifold topology is a requirement for most usecases, the challenges arise when a manifold topology needs to be supported by multiple different vertices having the same position in space. Two examples: o Two cubes touching in one edge o A concave polygon mesh touching itself in one edge These examples are common results of snaprounding (topological changes after converting from a rational number type to float). They are valid intermediate results in a CSG tree, and they're explicitly supported in e.g. 3MF. The information for building such a mesh is missing when we e.g. read from a polygon soup like STL, and we currently don’t have a way of reconstructing it when snaprounding from CGAL. You can modify your check by testing that all edges have an even count, but the healing algorithms is probably going to suffer from this new, more complex topology. (I plan to find some better terminology for some of the cases we’re discussing.) 2) Mesh Repair Iterative mesh repair is a hard problem, but it’s probably possible to design good heuristics to solve most cases. I got this recommended: "VertexRounding a ThreeDimensional Polyhedral Subdivision” by Steven Fortune: https://link.springer.com/article/10.1007/PL00009480 > https://github.com/openscad/openscad/issues/1580 > there is talk about 'edge flipping' to fix zero area faces. This seems to imply you have explicit edge representation. If you don't, i.e. faces defined only by vertex references, then it is trivial: You can just discard zero area faces, even in a connected polyhedron. > I build a halfedge structure (using CGAL’s Polyhedron_3 class) from one of our internal representations (polygon soup or indexed polygon mesh) and perform analysis and repair on that structure (unfortunately with the same manifold requirements as you’re using) When I say “zero area triangles” I’m not referring to degenerate triangles where two vertices collapse. I’m talking about triangles connecting 3 collinear vertices. These have zero area, no normal, infinite aspect ratio but are necessary for mesh connectivity so they cannot be removed. There are ways of fixing these, e.g. through edge flips or triangle splits, but as you allude to this is not trivial in the general case. > >polyfix issue1580backtoback2.stl > So it succeeds. > So I think one observation is that healing using a simpler datastructure makes healing simpler... > I have much more degenerate test cases than that one :) I’d be interested in your face split algorithm. Are you planning on making your work available as a free software library or code snippet? Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
I don't believe that polyhedron repair is possible. The set of nonmanifold topologies are much broader that the manifold ones. And to find a manifold that meet most the adjacencies of a nonmanifold is an illdefined problem. Take the following case as an example:
We have one edge with 3 incident faces and 5 edges with just one incidence. That 5 edges doesn't form a cycle and are not eligible as the border of a missing face. Three faces (f1, f4 and the right one) meet in an edge. They are candidates to be removed. The most problematic one may be f1. If it is removed, f5 is a candidate to be inserted as a missing face. On the other hand, if we remove f4, the addition of f2 and f3 solves the repair. Now, uncomment face f2. Who will be the candidates to be removed? We may remove f2 and f1 and add f5 or remove f4 and add f3. Which one is best? Comment and/or uncomment the lines with faces f1 to f5 will generate a handful of ambiguous cases. 
In reply to this post by kintel
Hello Marius,
On 03. des. 2016 16:27, Marius Kintel wrote: > While a locally manifold topology is a requirement > for most usecases, the challenges arise when a manifold topology > needs to be supported by multiple different vertices having the > same position in space. I assume by this you mean there is no selfintersection in the sense that there are overlapping volumes, but only vertices "touching". If there are multiple vertices in the same location and no inherent problem with the topology (usecount etc.), then there really is no reason to fix anything because the model is topologically ok. However, I think when we talk about healing, we refer to a subset of cases where the model is supposed to be usable in further boolean operations, and thus it needs to be manifold and unambiguous. Then it is much harder. > o Two cubes touching in one edge This could be considered topologically ok, it is just not manifold. If this topology was the result of a union of two cubes, you might want to call it a bug since you expect/require manifold results. Under this requirement I think the intersection between the two should be a volume or at least common (subset of a) face, and with only a touching edge you might want to keep two independent topologies but with matching coordinates. Perhaps difficult with software relying heavily on coordinate analysis, I realise that. > The information for building such a mesh is missing when we e.g. > read from a polygon soup like STL, and we currently don’t have a > way of reconstructing it when snaprounding from CGAL. From STL, you can only make a guess, and the guess may be wrong. > You can modify your check by testing that all edges have an even > count, but the healing algorithms is probably going to suffer from > this new, more complex topology. It is not easy to know if a use count of. e.g 4 is a model bug or a case like you explained. I have a complex case reporting use count=4 for some cases and it isn't obvious why at this point. > I build a halfedge structure (using CGAL’s Polyhedron_3 class) > from one of our internal representations (polygon soup or indexed > polygon mesh) and perform analysis and repair on that structure > (unfortunately with the same manifold requirements as you’re using) You have to make some assumptions, and the reasonable assumptions have the side effect that they are not always valid. Healing is a compromise that can be useful, but should not be "standard". > When I say “zero area triangles” I’m not referring to degenerate > triangles where two vertices collapse. I’m talking about triangles > connecting 3 collinear vertices. These have zero area, no normal, > infinite aspect ratio Yes, I understood that. Collapsed triangles are easy, but for the case of 3 nonintersecting collinear vertices, you have to check for the projection distance of the "middle vertex" down to the line defined by the 2 others, or alternatively compute the 3d polygon area explicitly for example along the lines of http://thebuildingcoder.typepad.com/blog/2008/12/3dpolygonareas.html > but are necessary for mesh connectivity so > they cannot be removed. I believe they are only necessary *because* you are using a halfedge (I call it 'coedge') datastructure. If all you have is triangles with 3 vertex references this problem goes away. Consider 2 triangles connected by one edge. Assume a vertex on that edge is merged with one of its neighbours, implying that one triangle collapses. You can then discard it, because the other triangle takes its place automatically. No other data structure exists that may be compromised. > There are ways of fixing these, e.g. through edge flips or > triangle splits, but as you allude to this is not trivial in > the general case. I have not seen the need for edge flips yet. > I have much more degenerate test cases than that one :) Ok, I guess my code will fail on some of them... if there is an index of those cases it could be of interest to try. > I’d be interested in your face split algorithm. > Are you planning on making your work available as a > free software library or code snippet? It might happen, but I am prototyping this using things I cannot release. Removing the proprietary pieces can be done though, I just have not done it. However, let me give you an idea of the algorithm. It is all based on faces referring to vertices only. Even edges do not exist explicitly, only by means of the end vertices and the face loop (3 vertex indices). First, it identifies the free edges (use_count=1) in the model and keeps the end vertices with it std::map<id_edge,std::pair<id_vertex,id_vertex>> free_edges; (perhaps using edges with use_count!=2 would be more general) In this process, a record is kept of the face referring to a free edge std::map<id_edge,id_face> edge_faces; For each free edge there may be a number of other vertices touching it (test with projection distance and edge parameter value to make sure it is on the edge). I use a map to sort the found intersections in increasing parameter order <0.0,1.0> per edge being split. Each split also carries an id of the vertex causing the split. std::map<id_edge,std::map<double,id_vertex>> edge_splits; To actually split the faces, traverse edge_splits, and look up which faces to split via edge_faces. To split a face, find the "top vertex" of the face, the one opposite the edge being split. Then simply remesh the triangle as a fan of new triangles, all referring to the top vertex and vertices from edge ends and/or edge_splits. Finally remove the split face and mark it as done so you don't try to split it again in this iteration. This means some split points can remain untreated in the current iteration. This happens for faces with more than one edge with splits. Iterate the whole thing until no more faces require splitting. Carstem Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by Ronaldo
> On Dec 3, 2016, at 14:25, Ronaldo <[hidden email]> wrote:
> > I don't believe that polyhedron repair is possible. The set of nonmanifold > topologies are much broader that the manifold ones. And to find a manifold > that meet most the adjacencies of a nonmanifold is an illdefined problem. I think we can constrain the allowed input to be locally manifold, but where multiple topologically different vertices can have the same position in space, as I suggested in my previous email in this thread. Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by cacb
> On Dec 3, 2016, at 15:29, Carsten Arnholm <[hidden email]> wrote:
> > Ok, I guess my code will fail on some of them... if there is an index of those cases it could be of interest to try. > Not yet, but I’ll start categorizing more failing tests and list them under the appropriate github issue. As a start, it would be interesting if you could handle the 8 test cases listed here: https://github.com/openscad/openscad/issues/1580 They all cause zero area triangles on export from OpenSCAD today. > However, let me give you an idea of the algorithm. By first glance it looks like your algorithm is equivalent to iteratively performing edge flips, except you handle all vertexedge intersections per split operation, instead of just one. I’ll take a closer look later. Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by Ronaldo
On 03. des. 2016 20:25, Ronaldo wrote:
> I don't believe that polyhedron repair is possible. Well, it is possible under certain assumptions, most importantly when a model can be interpreted as manifold, using coordinate matching, and a couple of other techniques. In 3d printing, most models are (or should be) manifolds, so it is a reasonable assumption to work from when attempting to 'heal' But the healing algorithms are not able to read your mind, so to turn your example into a usable manifold (if that is your goal), you need to edit it. Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by kintel
On 03. des. 2016 22:00, Marius Kintel wrote:
> As a start, it would be interesting if you could handle the 8 test cases listed here: > https://github.com/openscad/openscad/issues/1580 > > They all cause zero area triangles on export from OpenSCAD today. Not sure I understood which exact 8 cases that is, but I tried these: issue1580backtoback.stl result: no warnings issue1580backtoback2.stl result: no warnings issue1580zeroareatriangle.stl result: no warnings issue945e.stl result: no warnings issue945f.stl result: no warnings issue1803.stl result: no warnings adns2610_dev_circuit_inv_ascii.stl result: no warnings (ascii) issue1876.stl result: no warnings See attached file with more info. In short, all appears to end with no warning, and using simple visualisation of the resulting AMF file seems to confirm they are all ok. issue1876.stl was an interesting case of having also a duplicated face, it was handled ok. > By first glance it looks like your algorithm is equivalent to > iteratively performing edge flips, except you handle all vertexedge > intersections per split operation, instead of just one. > I’ll take a closer look later. Yes it is true all edge splits are done done at once for any given edge. From the above tests, my scheme seems to work, but I guess there are more complex problems Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org OpenSCAD_test_cases.txt (5K) Download Attachment 
Administrator

> On Dec 3, 2016, at 17:51, Carsten Arnholm <[hidden email]> wrote:
> > Not sure I understood which exact 8 cases that is, but I tried these: > Cool, looks like you’re a good step ahead of me in terms of success rate. > From the above tests, my scheme seems to work, but I guess there are more complex problems > There are more complex ones, but they’re all based on original bug reports which I haven’t properly organized yet. Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Free forum by Nabble  Edit this page 