Difference of valid objects not valid. Why?

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

Difference of valid objects not valid. Why?

adrianv
I wrote a routine to make round-edged holes in cylindrical shells.  For
example:

<http://forum.openscad.org/file/t2477/ehole.png>

It seems to work a lot of the time.  The above example renders without a
hitch.  But I have a mystery that sometimes I get a CGAL error.   What I
don't understand is that if I render the mask (the thing that I cut away to
make the hole) then CGAL issues no error and everything appears OK.  (The
mask is a union of two objects and I have also got a cube in there for good
measure, so CGAL is activated.)   The case I was really interested in was to
create a slot in a cylinder, so here is the mask, which renders OK:

<http://forum.openscad.org/file/t2477/hmask.png>

No CGAL error yet.  But when I difference it from the cylindrical shell as
follows, I get a CGAL error below.  I wonder about the "non coplanar faces".
I didn't think my model had any such thing.  

Rendering Polygon Mesh using CGAL...
PolySet has nonplanar faces. Attempting alternate construction
ERROR: CGAL error in CGALUtils::applyBinaryOperator difference: CGAL ERROR:
assertion violation! Expr: itl != it->second.end() File:
/mxe/usr/x86_64-w64-mingw32.static.posix/include/CGAL/Nef_3/SNC_external_structure.h
Line: 1152
Geometries in cache: 19
Geometry cache size in bytes: 2719400
CGAL Polyhedrons in cache: 3
CGAL cache size in bytes: 43133288
Total rendering time: 0 hours, 1 minutes, 52 seconds
Top level object is a 3D object:
Simple: yes
Vertices: 264
Halfedges: 792
Edges: 396
Halffacets: 272
Facets: 136
Volumes: 3
Rendering finished.

Preview looks like this:

<http://forum.openscad.org/file/t2477/cslot.png>

So why can I take two valid objects, take their difference and the result is
invalid?   Under what circumstances can this occur?  


Code that produces the examples:

include<BOSL2/std.scad>
include<BOSL2/skin.scad>

$fn=64;//4;//128;

function cylhole(r, path, offset=0) =
    [for(point=path)
cylindrical_to_xyz(concat([r+offset],xscale(360/(2*PI*r),p=point)))];

// r is center radius of cylindrical shell, thickness is shell thickness,
path is path for hole to cut (2d)
module cylholemask(r,thickness,path)
{
  cutout = cylhole(r,path);
  cutout_tangent = path_tangents(cutout);
  cutout_normal = [for(i=idx(cutout)) cross(cutout_tangent[i], [cutout[i].x,
cutout[i].y,0])];
  minangle = min(subindex(path,0))*360/(2*PI*r);
  maxangle = max(subindex(path,0))*360/(2*PI*r);

  innerplane1 = plane_from_points(
               [(r-thickness/2)*[cos(minangle), sin(minangle),0],
                (r-thickness/2)*[cos(minangle), sin(minangle),1],
                (r-thickness/2)*[cos(maxangle), sin(maxangle),0]]);
  outerplane = concat(select(innerplane1,0,2), [r+thickness]);
  innerplane = concat(select(innerplane1,0,2), [innerplane1[3]-thickness]);

  farpts = scale([1.1,1.1,1],p=cutout);

  inner = [for(i=idx(cutout)) plane_line_intersection(innerplane,
[farpts[i],cutout[i]])];
  outer = [for(i=idx(cutout)) plane_line_intersection(outerplane,
[farpts[i],cutout[i]])];

  skin([inner, outer], slices=0,convexity=10);
  path_sweep((cmask(thickness/2)), cutout, closed=true, method="manual",
normal=cutout_normal);
}  

function cmask(r) =
   let(eps=0.1)
   fwd(r+.01,p=
   [
    [r+eps,0],
    each arc(r=r, angle=[0, 180]),
    [-r-eps,0],
    [-r-eps, r+eps],
    [r+eps, r+eps]
   ]);

slot=reverse(turtle(["move",4,"arcleft", .5, "move", 5, "arcright", 1,
"arcleft", .5,180, "move", 3+4,
                "arcleft", .5, 180, "arcright", 1, "move", 5,
"arcleft",.5]));

difference(){
  up(1.25)cyl(r=10.5, h=10);
  up(1.25)cyl(r=9.5, h=11);
  cylholemask(10,1.05, subdivide_path(simplify_path(slot),475,exact=false));
// This fails
//  cylholemask(10, 1.05, apply(xscale(3),circle(r=3, $fn=128)));    // This
works
}

right(75)cube([1,1,1]);










--
Sent from: http://forum.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: Difference of valid objects not valid. Why?

cacb
On 2020-05-14 16:45, adrianv wrote:
> Rendering Polygon Mesh using CGAL...
> PolySet has nonplanar faces. Attempting alternate construction
> ERROR: CGAL error in CGALUtils::applyBinaryOperator difference: CGAL
> ERROR:

Looks like you have non-triangular faces, since it is impossible to have
nonplanar triangles. Try exporting the parts to e.g. STL or other format
that requires triangles.

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: Difference of valid objects not valid. Why?

nophead
The fact it converts to PolySet and back can corrupt valid CGAL geometry because it goes from CGAL rationals to double with a snap to a grid. You simply can't have vertices that are so close they merge when snapped.

On Thu, 14 May 2020 at 16:17, <[hidden email]> wrote:
On 2020-05-14 16:45, adrianv wrote:
> Rendering Polygon Mesh using CGAL...
> PolySet has nonplanar faces. Attempting alternate construction
> ERROR: CGAL error in CGALUtils::applyBinaryOperator difference: CGAL
> ERROR:

Looks like you have non-triangular faces, since it is impossible to have
nonplanar triangles. Try exporting the parts to e.g. STL or other format
that requires triangles.

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: Difference of valid objects not valid. Why?

Ronaldo
In reply to this post by adrianv


But I have a mystery that sometimes I get a CGAL error.   What I
don't understand is that if I render the mask (the thing that I cut away to
make the hole) then CGAL issues no error and everything appears OK.  (The
mask is a union of two objects and I have also got a cube in there for good
measure, so CGAL is activated.)  

Some non-manifold objects boolean operated with a cube may render without any issue depending where the cube is: 

v = [ [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,11,10] ];

f = [ [0,1,2,3], [1,0,4,5], [2,1,5,6], [3,2,6,7], [0,3,7,4],
      [7,8,6,5,4], [6,8,7]  ];

union(){
  polyhedron(v, f);
  //translate([5,11,10])
  cube(3,center=true);
}


That will render fine although the polyhedron is not a manifold. Add the translation and CGAL complains.

In a boolean operation, CGAL only needs to make local changes. If everything is nice there, it concludes its task without looking elsewhere.

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

Re: Difference of valid objects not valid. Why?

adrianv
The problem of CGAL objecting to my model doesn't seem to be specifically
correlated to the non-coplanar faces that it notes.  I changed the model a
bit and that went away.  I also tried explicitly triangulating the only
faces that aren't triangles.   (Note that these faces were constructed by
intersecting lines with a plane, so they can't be non-coplanar.)  None of
this fixed anything.

It seems like the issue of rounding gets raised repeatedly as an explanation
for CGAL errors, generally in situations where it is not relevant.  I did
finally encounter this, so it does actually happen.   It happens in one of
my models when points are closer together in my model than 1.3e-6.  The
model above has a modest spacing of facets and shouldn't have any points so
close together.  (And yes, if I increase the points to larger than 1.3e-6,
like say 1.4e-6 then the CGAL error in that case vanishes.)  

I'm kind of puzzled about when/how CGAL decides to examine my shape, though.
I tried unioning my mask shape with a cube and got the CGAL error.  But my
mask shape is already the union of two shapes that overlap each other.  Why
doesn't this trigger a CGAL evaluation and the error?  Why do I have to
separately union with a cube to get the error?  In any case, this produces a
better explanation of what is going wrong: something is somehow amiss with
the polyhedron that defines my roundover.   The other shape (which cuts the
hole) doesn't seem to produce the error when unioned with a cube.  



--
Sent from: http://forum.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: Difference of valid objects not valid. Why?

nophead
CGAL works fine with close vertices, so if the result of a union or difference yields close vertices it will give a correct result in its nef polyhedron form. OpenSCAD then converts it to is own PolySet format which is a polygon soup, like STL is a triangle soup. It also truncates to doubles and snaps to a grid, so it breaks the topology. If it then converts it back to a nef polyhedron and passes it back to CGAL which will throw an exception.

On Fri, 15 May 2020 at 01:39, adrianv <[hidden email]> wrote:
The problem of CGAL objecting to my model doesn't seem to be specifically
correlated to the non-coplanar faces that it notes.  I changed the model a
bit and that went away.  I also tried explicitly triangulating the only
faces that aren't triangles.   (Note that these faces were constructed by
intersecting lines with a plane, so they can't be non-coplanar.)  None of
this fixed anything.

It seems like the issue of rounding gets raised repeatedly as an explanation
for CGAL errors, generally in situations where it is not relevant.  I did
finally encounter this, so it does actually happen.   It happens in one of
my models when points are closer together in my model than 1.3e-6.  The
model above has a modest spacing of facets and shouldn't have any points so
close together.  (And yes, if I increase the points to larger than 1.3e-6,
like say 1.4e-6 then the CGAL error in that case vanishes.) 

I'm kind of puzzled about when/how CGAL decides to examine my shape, though.
I tried unioning my mask shape with a cube and got the CGAL error.  But my
mask shape is already the union of two shapes that overlap each other.  Why
doesn't this trigger a CGAL evaluation and the error?  Why do I have to
separately union with a cube to get the error?  In any case, this produces a
better explanation of what is going wrong: something is somehow amiss with
the polyhedron that defines my roundover.   The other shape (which cuts the
hole) doesn't seem to produce the error when unioned with a cube. 



--
Sent from: http://forum.openscad.org/

_______________________________________________
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: Difference of valid objects not valid. Why?

RobWLakes
So what I think is happening here is that if the CGAL can produce pixels, just like .STL produces filament, then job done?
Cheers, RobW

On 15 May 2020 6:44:34 pm AEST, nop head <[hidden email]> wrote:
CGAL works fine with close vertices, so if the result of a union or difference yields close vertices it will give a correct result in its nef polyhedron form. OpenSCAD then converts it to is own PolySet format which is a polygon soup, like STL is a triangle soup. It also truncates to doubles and snaps to a grid, so it breaks the topology. If it then converts it back to a nef polyhedron and passes it back to CGAL which will throw an exception.

On Fri, 15 May 2020 at 01:39, adrianv <[hidden email]> wrote:
The problem of CGAL objecting to my model doesn't seem to be specifically
correlated to the non-coplanar faces that it notes.  I changed the model a
bit and that went away.  I also tried explicitly triangulating the only
faces that aren't triangles.   (Note that these faces were constructed by
intersecting lines with a plane, so they can't be non-coplanar.)  None of
this fixed anything.

It seems like the issue of rounding gets raised repeatedly as an explanation
for CGAL errors, generally in situations where it is not relevant.  I did
finally encounter this, so it does actually happen.   It happens in one of
my models when points are closer together in my model than 1.3e-6.  The
model above has a modest spacing of facets and shouldn't have any points so
close together.  (And yes, if I increase the points to larger than 1.3e-6,
like say 1.4e-6 then the CGAL error in that case vanishes.) 

I'm kind of puzzled about when/how CGAL decides to examine my shape, though.
I tried unioning my mask shape with a cube and got the CGAL error.  But my
mask shape is already the union of two shapes that overlap each other.  Why
doesn't this trigger a CGAL evaluation and the error?  Why do I have to
separately union with a cube to get the error?  In any case, this produces a
better explanation of what is going wrong: something is somehow amiss with
the polyhedron that defines my roundover.   The other shape (which cuts the
hole) doesn't seem to produce the error when unioned with a cube. 



--
Sent from: http://forum.openscad.org/

_______________________________________________
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
Rob W
Lake Tyers Beach,
Victoria, Australia