Errors during repeated minkowski and difference

[xaqrox]

So I have this object (it's going to be a speaker mount):

// hullshelf.scad
$fn=12;

thx=20;

width=177-thx;
depth=205-thx;
height=width;

center=[0, 0, 0];

i=[1,-1];
vertices = [for (x=i, y=i, z=i) [x*width, y*depth, z*height]/2];

// Vertex labels
*for (vertex=[0:len(vertices)-1])
  translate(vertices[vertex]*1.5)
    rotate([90, 0, 0]) linear_extrude(5)
      text(str(vertex), size=30, valign="center", halign="center");

pairs = [
  // top
  [0, 6],
  [2, 4],
  // back
  [0, 5],
  [1, 4],
  // front
  [1, 6],
  [2, 5],
  // inside
  [0, center],
  [4, center],
];

function getVertex(point)=is_num(point) ? vertices[point] : point;

module capsule(points, radius)
  hull()
    for (point=points)
      translate(getVertex(point))
        sphere(radius);

module lattice()
  for(pair=pairs)
    capsule(pair, thx/2);

lattice();

Inspired by Irev-Dev/Round-Anything, I want to "fillet" or "round" the sharp boundaries of where the capsule hulls intersect each other. So I'm trying this double-minkowski-then-difference thing.

difference() {
  cube(500, center=true);
  minkowski() {
    difference() {
      cube(500, center=true);
      minkowski() {
        lattice();
        sphere(d=thx);
      }
    }
    sphere(d=thx);
  }
}

When I attempt to preview this, after about 8 minutes I get the following error:

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e->incident_sface() != SFace_const_handle() File: /Users/kintel/code/OpenSCAD/libraries/install/include/CGAL/Nef_S2/SM_const_decorator.h Line: 330

Through process of elimination, I find this happens during the second (outer) minkowski. I imagine something about the complex convexity of this model just totally stumps OpenSCAD, but I don't have the background in the math or the software implementation to identify precisely what limitation I am coming up against.

So, I tried some experiments...

If I just do one "face" (the "top", for example) of this model at $fn=8, it works:

Nice! But if I bump it to $fn=12, I get a different error:

ERROR: CGAL error in CGALUtils::applyBinaryOperator UNKNOWN: CGAL ERROR: assertion violation! Expr: sf_old->mark() File: /Users/kintel/code/OpenSCAD/libraries/install/include/CGAL/Convex_decomposition_3/SM_walls.h Line: 569

With a couple primitive cylinders at $fn=12 instead, we get beautiful success:

// Instead of "lattice();" in the previous snippet.
for(a=[0, 90])
  rotate([0, a, 0])
     cylinder(d=thx, h=100, center=true);

This also works with a 45deg rotation:

But not at 30deg:

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e_below != SHalfedge_handle() File: /Users/kintel/code/OpenSCAD/libraries/install/include/CGAL/Nef_3/SNC_FM_decorator.h Line: 427

Or 60deg:

ERROR: CGAL error in CGAL_Nef_polyhedron3(): CGAL ERROR: assertion violation! Expr: e->incident_sface() != SFace_const_handle() File: /Users/kintel/code/OpenSCAD/libraries/install/include/CGAL/Nef_S2/SM_const_decorator.h Line: 330

It does work with this thing:

for(a=[0:90:270])
  rotate([0, a, 0])
    translate([50, 0, 0])
      cylinder(d=thx, h=200, center=true);

But not this thing:

for(a=[0:120:240])
  rotate([0, a, 0])
    translate([30, 0, 0])
      cylinder(d=thx, h=200, center=true);

So am I just coming up against an inherent limitation in OpenSCAD? Or CGAL? Or is there a better way to model this? Or is there another program that I could model this in...?

--- Want to back this issue? **[Post a bounty on it!](https://app.bountysource.com/issues/94552730-errors-during-repeated-minkowski-and-difference?utm_campaign=plugin&utm_content=tracker%2F52063&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://app.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F52063&utm_medium=issues&utm_source=github).

[MichaelAtOz]

So am I just coming up against an inherent limitation in OpenSCAD? Or CGAL? Or is there a better way to model this? Or is there another program that I could model this in...?

Sorry it took so long to respond. Next time show (at least a final) single code snippet with the problem - I was jumping around all your variants...then getting distracted and starting again \:\

For others to reproduce (remove the !), it gets a CGAL assertion violation:

$fn=12;

thx=20;
long=100;
cubl=200;

difference() {
  cube(cubl, center=true);
  minkowski() {
    difference() {
      cube(cubl, center=true);
       minkowski() {
        // Instead of "lattice();" in the previous snippet.
        !for(a=[0, 30])  // 90 works
          rotate([0, a, 0])
             cylinder(d=thx, h=long, center=true);        
        sphere(d=thx);
      }
    }
    sphere(d=thx);
  }
}

ERROR: CGAL error in CGAL_... is failure of object integrity when CGAL is processing the various stages of its calculations, something internally 'must' match, but doesn't. Like Expr: e_below != SHalfedge_handle() says the edge below (whatever that is) should match the edge in the halfedge it is also dealing with.

Ideally OpenSCAD should pass valid geometry to CGAL. Most such errors are from poorly formed import()ed STLs, or badly built polygons/polyhedrons. Once those are eliminated, it gets messy.

Valid geometry must be manifold (discussion), and have no self-intersections (see diagrams).

When you operate on 'curved' objects, the lines making the edges can sometimes end up aligned (or a common point). These are non manifold. Also some floating point operations can move a point slightly, such that it turns into a self-intersection.

For various reasons this shows its face at inopportune times...

With the ! in the code above, you can see for example, the point in the middle, shared. It may be that, or some other line; intersecting cylinder()s tend to be common problems. Or the first minkowski() difference() may introduce another 'point of contention'.

Until someone smarter than me works out a better way internally, I find when this happens you have to jiggle(TM) the model. As you found, sometimes just fiddling with $fn will make it go away, other times you may need to nudge an object by 0.01 or so.

With intersecting cylinder()s, I have found rotate()ing them in Z moves the points they join at enough. With the code below, this has unaligned points. Close-up of the middle.

$fn=12;

thx=20;
long=100;
cubl=200;
angles=[0, 30];

difference() {
  cube(cubl, center=true);
  minkowski() {
    difference() {
      cube(cubl, center=true);
       minkowski() {
        // Instead of "lattice();" in the previous snippet.
        !for(i=[0,len(angles)-1])  // 90 works
          rotate([0, angles[i], i*3.14159])
             cylinder(d=thx, h=long, center=true);        
        sphere(d=thx);
      }
    }
    sphere(d=thx);
  }
}

Note you don't always have to be that convoluted, but a simple rotate() in the original code, rotated both so the points still aligned.

I haven't tried with your lattice, but I suspect a jiggle(TM) or two to your cylinder()s will do wonders.

[MichaelAtOz]

Oops, that rotate had side effects. Try

        for(i=[0,len(angles)-1])  // 90 works
          rotate([0, angles[i], 0])
            rotate([0,0,i*3.14159])
             cylinder(d=thx, h=long, center=true);        

That too 30 minutes to render, so your lattice will be looong.

There are other fillet approaches, but they don't work with for() as they need children().

[kintel]

Status as of 2024-03-24: This is still an issue, both with CGAL and Manifold

[kintel]

Status as of 2024-09-19: This seems to work fine with Manifold now. Still broken with CGAL.