Why is this not an error?

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Why is this not an error?

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

doug.moen
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,

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



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

Ronaldo
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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

kintel
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 Snap-rounding 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 snap-rounding, I’d be interested.

 -Marius


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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 = nedge-1;
       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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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, non-manifold edges
of various kinds and faces requiring subdivision (as in the example I
showed).

> o Snap-rounding 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 re-connect 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
back-to-back non-zero area faces result, where removing one of the
duplicate faces causes new non-manifold 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 snap-rounding, 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 "issue1580-back-to-back2.stl"

I tried running this through my experimental code:

 >polyfix issue1580-back-to-back2.stl

Parameters:
   input_file = issue1580-back-to-back2.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: issue1580-back-to-back2_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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

kintel
Administrator
Hi Carsten,

1) Manifoldness

While a locally manifold topology is a requirement for most use-cases, 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 snap-rounding (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 snap-rounding 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: "Vertex-Rounding a Three-Dimensional 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 issue1580-back-to-back2.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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

Ronaldo
I don't believe that polyhedron repair is possible. The set of non-manifold topologies are much broader that the manifold ones. And to find a manifold that meet most the adjacencies of a non-manifold is an ill-defined problem. Take the following case as an example:
p = [ [0,0, 0],[10,0, 0],[10,10, 0],[0,10, 0],
      [0,0,10],[10,0,10],[10,10,10],[0,10,10],
      [5,5,10], // top baricenter
      [5,5, 0]  // bottom baricenter
    ];
f = [
        [0,4,5,1]    // left
      , [2,6,7,3]    // right
      , [0,3,7,4]    // back
      , [4,7,6,8,5]  // top
      , [0,1,9,2,3]  // bottom
      , [1,5,6,2]    // f1 front
//      , [1,2,9],     // f2 bottom
//      , [6,5,8]      // f3 top
      , [1,5,8,9]    // f4 internal
//      , [8,6,2,9]    // f5 internal
    ];
polyhedron(p,f);
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.
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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 use-cases, 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 self-intersection 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 (use-count 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 snap-rounding 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 non-intersecting 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/3d-polygon-areas.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 re-mesh 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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

kintel
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 non-manifold
> topologies are much broader that the manifold ones. And to find a manifold
> that meet most the adjacencies of a non-manifold is an ill-defined 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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

kintel
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 vertex-edge 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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

cacb
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:


issue1580-back-to-back.stl       result: no warnings
issue1580-back-to-back2.stl      result: no warnings
issue1580-zero-area-triangle.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 vertex-edge
 > 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
Reply | Threaded
Open this post in threaded view
|

Re: Why is this not an error?

kintel
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