CGAL assertion failure when differencing moderate complexity models

[dmopalmer]

A difference of a 5k polygon model with itself (shifted) leads to an assertion error. A simpler (1k polygons) model does not. Larger models also cause the assertion.

Tarball is at https://dl.dropboxusercontent.com/u/9855476/difference_test.tgz

CGAL error in CGAL_Nef_polyhedron's difference operator: CGAL ERROR: assertion violation! Expr: itl != it->second.end()

(All models were generated (by quadratic edge decimation) using meshlab from the Venus of Willendorf model at turbosquid. This is a paleolithic sculpture of a nude woman, so NSFW if your work involves knapping flint spear points.)

---

module thing()
{   // 5k model causes assertion failure.    1K model no problem
     import("venus_5k.stl",convexity=10);
//  import("venus_1k.stl",convexity=10);
}

module diff()
{
    difference()
    {
        child(0);
        translate([1,0,0]) child(0);
    }
}

render() diff() thing();

Versions: OpenScad 2013.05.25 binary distribution (also seen on 2013.1 installed using MacPorts) on Mac OSX 10.8.4.

[donbright]

thanks for the bug report.

do you happen to have a url for your decimated stl ?

or maybe a sequence of commands in meshlab that can generate them?

i assume the model is here

http://www.turbosquid.com/3d-models/venus-willendorf-3d-model/424895

thanks again

[dmopalmer]

Tarball is now in a dropbox link in the edited bug report.

The original URL is, as you said, http://www.turbosquid.com/3d-models/venus-willendorf-3d-model/424895 In Meshlab: Filters->Remeshing etc.->Quadric edge collapse decimation-> Target number of faces=5000 preserve normal preserve topolgy (rest as default)

with the result exported as an STL gives somethign which shows the problem.

[kintel]

A difference between two objects can cause the result to be non-manifold. In this case, it looks like that's exactly what happens. This is a pretty hard limitation of the underlying geometry library we use (CGAL).

[dmopalmer]

As I understand it, the difference of two well-behaved polyhedra should be a finite number of well-behaved polyhedra, except in the case where vertices, edges, or faces are aligned (to within the accuracy of the data structure, or close enough to cause trouble).

Is that what is happening here, and would it make sense to try a bunch of different offsets to find one where nothing aligns and causes trouble, or is that unlikely to fix things? (In my specific use case, making a hollow shell out of an object for purposes of 3d printing, I am fine with shifting things around a hundred microns or so to avoid degeneracies. I don't know what tolerance is used by CGAL.)

[kintel]

A difference between two manifold polyhedra might not be manifold. I'd say they're still "well behaved", but the mathematics would say non-manifold, which, unfortunately is the limitation we're working within.

As an illustration, consider this - the result of the difference of the two tetris pieces is not manifold, but would be with minor justifications of the translation:

module tetris() {
  cube(10);
  translate([10,0,-10]) cube([10,10,30]);
}

difference() {
  tetris();
  translate([10,0,0]) tetris();
}

[kintel]

PS. The tolerance of CGAL is virtually infinite, but OpenSCAD tries to limit resolution to something more limited, which might cause issues in itself. Fixing that is on the TODO list..

[dmopalmer]

The tetris case has aligned edges and vertices. When I take the Venus model, there is no reason to expect that any given vertex, edge or face is aligned with one from the same model translated by [1,0,0], although it could happen by chance.

But I have tried translations of [1.01,0.02,0.03], [1.0123456,0.02829384,0.03517], [1.123456,0.2829384,0.3517], etc, which should not all have accidental alignments.

[kintel]

dmopalmer: My suspicion is that you accidentally get a non-manifold results and that's why CGAL complains. It's very hard to see though, from that model. Perhaps it would be possible to gradually cut away stuff from it to get a smaller example. Once we can clearly identify what's going on, things will be more clear (plus that we'll have a good testcase for the future :) )

[kintel]

@dmopalmer Have you seen any similar behaviour on smaller models? I still think that the problem is related to geometric features and not the size of the model. It's a lot of work to slim down the model to a minimal test case..

[dmopalmer]

I haven't tried to slim it down. I was intending to get to the point where I could run in a debugger and set a breakpoint at the assert, but I never got the total build system to the right state.

[kintel]

I don't think a debugger would help in this case - IMO, the underlying code is too complex to figure out the cause without seeing the geometric context.

[dmopalmer]

Using a debugger to print out the details of the particular facets causing the problem (is a facet degenerate? parallel to a an axis? high-aspect-ratio? Is it the same facet causing problems each time? does it occur at a magic number?) would help.

If not, then just getting the location of the facet will help to simplify the model to only the troublesome facets.

[kintel]

True enough :) If you need help to build, please get in touch. I'm hoping to get OpenSCAD to a point where building it shouldn't be the showstopper..

[kintel]

To clarify: It looks like subtracting two well-formed, valid and simple manifold objects in CGAL triggers the mentioned assertion. This sounds like a bug in CGAL.

CGAL error: assertion violation!
Expression : itl != it->second.end()
File       : /Users/kintel/code/OpenSCAD/openscad/../libraries/install/include/CGAL/Nef_3/SNC_external_structure.h
Line       : 1102

[thehans]

Original links are broken, unable to reproduce. Please re-open or create new issue if models which reproduce the issue can be provided. Closing