Grid causes degenerate meshes #203

ijackson opened this Issue Oct 3, 2012 · 13 comments

5 participants


I have a file which produces this error:

add_vertex_to_facet(): input error: disconnected facet complexes at vertex 224:
involved facets are: 11394 11166 10938 10710 10482 10254 10026 9798 9570 9342 9114 8886 8658 8430 8202 7974 7746 7518 7290 7062 6834 6606 6378 6150 5922 5694 5466 5238 5010 4782 4554 4326 4098 3870 3642 3414 3186 2958 2730 2502 2274 2046 1818 1590 1362 1134 906 678 450 222 (closed cycle) and.
CGAL error in CGAL_Build_PolySet: CGAL ERROR: assertion violation!
Expr: check_protocoll == 0
File: /usr/include/CGAL/Polyhedron_incremental_builder_3.h
Line: 199

To reproduce, process the attached file "pawn.scad" with "openscad -o t.stl pawn.scad" on Debian wheezy (openscad 2011.12-3, libcgal9 4.0-4).

(Hmm, I can't see how to attach the file. I will try to do that after I submit this issue. If I fail I will post a url for it instead.)


There doesn't seem to be a way to attach a file to a bug report. (omg wtf?) So here is a url for the file:;a=blob_plain;f=pawn.scad;hb=openscad-bug-2012-10-03


I have found that this diff (which reduces the resolution of some of the extrusions etc.) works as a workaround.

diff --git a/pawn.scad b/pawn.scad
index 6f1bf99..bbcb2b3 100644
--- a/pawn.scad
+++ b/pawn.scad
@@ -34,8 +34,8 @@ echo("height", htotal);

d = 0.01;


module SegmentBasisSquare(zmin, zmax, xmin){
translate([xmin, zmin-d]) square([-xmin+d, zmax-zmin+d*2]);

openscad member

It looks like this is caused by us giving CGAL a self-intersecting/collapsed mesh in CGAL_Build_PolySet in This is again caused by trying to snap vertices to a fine grid. This grid trick is the cause of a number of issues and needs to be refactored. Since so much relies on it, it's a bit of a scary job (i.e. wait until after the next release).


Technically removing the grid I think is quite simple. Have a look how I build a primitive in RapCAD using CGAL's incremental builder. In the operator() function of CGALBuilder I add all the points to a simple list and then use indexOf to find the index. Behind the scenes its doing an exact double comparison, so two points at almost exactly the same place are still recorded as two separate indexes. Initially I thought that using indexOf would be slow, and I tried using hash tables to improve performance. But in reality there didn't seem to be any considerable performance impact compared to what CGAL then has to do. I measured it as being a lot quicker than what's going on in grid.h by putting some timing code in both.

Obviously implementing it is only the first part of the story for OpenSCAD. Making sure it doesn't break anything is going to be the tough part.

openscad member

what is 'exact double'?


Basically I am just trying to distinguish the difference between what grid.h does where it rounds up doubles to the nearest value as defined by GRID_FINE or GRID_COARSE or smth. Whereas comparing doubles inside the lists indexOf implementation uses

bool compare(double a, double b) { return a==b; }

Actually I have just remembered, its not using doubles at all its a list of CGAL:Point3, that in turn uses Gmpq FeildType numbers behind the scenes so its really comparing multiple precision floating points, in that part of the code. However there is a doubles comparison going on in the appendVertex method of CGALPrimitive, behind the scenes of the contains function.


It used to work more like I originally described in this revision. Its been re factored quite a lot since then. It does a comparison of Point as defined here

openscad member

I thought gmpq is rationals?


Yes, Its what OpenSCAD is using for the CGAL Arithmetic

openscad member

This was fixed a while ago. Note that rotate_extrude() requires the 2D object to have only positive X coordinates, otherwise, the resulting object will be an inside-out volume.

@kintel kintel closed this Jan 22, 2015

requires the 2D object to have only positive X coordinates


The 2D shape needs to be either completely on the positive or negative side of the X axis.


Also, is it completely positive, what about zero?

(for the wiki)

openscad member

The latter is technically allowed, but the geometry will be inside-out (which we should fix)
The object is allowed to touch the X axis but not cross it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment