BUG: minkowski() fills holes when used with 2D polygons

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

BUG: minkowski() fills holes when used with 2D polygons

Triffid Hunter

// using 2c273159 - Wed Apr 4 01:46:50 2012 +0200 - Missing NULL check on some normalization corner cases. Fixes #95


module object_with_holes() {

  difference() {

    square([20, 20], center=true);

    circle(r=5);

  }

}


// does not work (fills in hole)

linear_extrude(height=1)

minkowski() {

  #object_with_holes();

  circle(r=1);

}


// works as expected

translate([25, 0, 0])

minkowski() {

  linear_extrude(height=1)

    #object_with_holes();

  cylinder(r=1, h=0.01);

}


Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kitwallace
I'm using version 2013.06  and this bug is still there.  It would be useful to see it fixed because it stops me using adding thickness -inside- a path using the technique of differencing the shape from an large enclosing square, applying minkowski and finally intersecting with the original shape to get a perimeter (Minkowski applied to the outside of the shape yields a different external profile)  see http://kitwallace.tumblr.com/post/71983202646/the-savoy-vase  for context.
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
Hi,

The challenge of changing this is that lots of existing models might be dependant on minkowski filling holes, so I’m not sure we should change it, even when the underlying bug has been found and fixed.

Btw., your savoy vase can be modeled in a simpler, and much faster way (requires OpenSCAD 2013.06):

https://gist.github.com/kintel/8245291

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kitwallace
I suppose both buggy and bugless modes of Minkowski could be supported if bug exploitation is common.  I at least would find a bugless mode useful.

Btw many thanks Marius for your improvements to my Savoy vase code - I've added to the documentation in the wiki on the scale parameter which is a very welcome addition.

https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/2D_to_3D_Extrusion

-Chris
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

Oskar
In reply to this post by kintel
Chris: There is another workaround for 2D Minkowski of complex polygons that I have used before. Evaluate via 3D Minkowski:

Instead of:

        minkowski() {
                circle(r=d);
                child();
        }

Do

        projection(cut=true) minkowski() {
                cylinder(r=d);
                linear_extrude(center=true) child();
        }

The problem is that with complex polygons, the computation times quickly becomes excessive!

So I implemented* the code required for the 2D Minkowski to work with complex polygons and the computation times for the examples at https://github.com/OskarLinde/scad-utils went (in a debug build with $fn=64) from 13 minutes to 6 seconds. It really takes the Minkowski operator into the realm of usability for more complex 2D polygons.

kintel wrote
The challenge of changing this is that lots of existing models might be dependant on minkowski filling holes, so I’m not sure we should change it, even when the underlying bug has been found and fixed.
Marius, while I agree with the general philosophy of not breaking existing projects, this is a case where we have a mathematical operator (Minkowski) producing incorrect results for a large set of inputs. That behavior would be surprising to anyone encountering it and people (ab)using it would surely realize that they are relying on unintended behavior.

Apart from being mathematically incorrect, the current behavior is also asymmetric with the 3D case.

Best,

Oskar

*) It entailed implementing a decomposition of a complex polygon (CGAL::Nef_polyhedron_2) into a small set of simple polygons (CGAL::Polygon_2), and code to properly handle the conversion from CGAL::Polygon_with_holes_2 back to CGAL::Nef_polyhedron_2. Please let me know if you would be interested in a patch, in which case I would clean it up a bit and add some regression tests.
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
On Jan 7, 2014, at 19:06 PM, Oskar <[hidden email]> wrote:
>
> So I implemented* the code required for the 2D Minkowski to work with
> complex polygons and the computation times for the examples at
> https://github.com/OskarLinde/scad-utils
> <https://github.com/OskarLinde/scad-utils>   went (in a debug build with
> $fn=64) from 13 minutes to 6 seconds. It really takes the Minkowski operator
> into the realm of usability for more complex 2D polygons.
>
Actually, I’m in the process of porting 2D minkowski away from CGAL altogether.
See e.g. https://github.com/openscad/openscad/blob/issue527/src/GeometryEvaluator.cc

When I wrote that, I was of the impression that CGAL was correct in filling the holes, while I realize now that this might not be the case after all.

-> I think it makes sense to change this behavior to allow holes and let them be preserved during a 2D minkowski.

I’ll make the necessary changes and see where that gets us.

Btw., could you post the 2D example you mentioned, so I can do a corresponding test against my new code?

Cheers,

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

Oskar
kintel wrote
Actually, I’m in the process of porting 2D minkowski away from CGAL altogether.
See e.g. https://github.com/openscad/openscad/blob/issue527/src/GeometryEvaluator.cc
That sounds great if it gives a significant speed up. Have you actually found the 2D CSG operations in CGAL to be a performance bottle neck though? How much does the CSG operations cost compared to converting back and forth to Nef for example?

kintel wrote
-> I think it makes sense to change this behavior to allow holes and let them be preserved during a 2D minkowski.
>
Definitely. It also means that operations such offset/inset/shell etc are implementable with good performance using nothing more than CSG+minkowski.


kintel wrote
Btw., could you post the 2D example you mentioned, so I can do a corresponding test against my new code?
I've attached a test example that with a correct 2D CGAL::minkowski takes about 3 s:

PolySets in cache: 0
PolySet cache size in bytes: 0
CGAL Polyhedrons in cache: 110
CGAL cache size in bytes: 2235304
   Top level object is a 2D object:
   Empty:          no
   Plane:          no
   Vertices:      532
   Halfedges:    1064
   Edges:         532
   Faces:          26
   FaceCycles:     50
   ConnComp:       25
Total rendering time: 0 hours, 0 minutes, 3 seconds
Rendering finished.


mintest.scad

The result:

Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
On Jan 7, 2014, at 20:52 PM, Oskar <[hidden email]> wrote:

> Have you actually
> found the 2D CSG operations in CGAL to be a performance bottle neck though?
> How much does the CSG operations cost compared to converting back and forth
> to Nef for example?
>
2D minkowski isn’t really that slow. My motivation for refactoring is to make geometry generation more flexible, so we won’t have to use Nef polyhedrons all the time.

> Definitely. It also means that operations such offset/inset/shell etc are
> implementable with good performance using nothing more than CSG+minkowski.
>
Yes, we’re planning to add a native module for this as well.

> I've attached a test example

Thanks! This actually crashes master, so I’ve got some work to do..
I’ll post my results when I’ve got any.

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
In reply to this post by Oskar
On Jan 7, 2014, at 19:06 PM, Oskar <[hidden email]> wrote:
>
> *) It entailed implementing a decomposition of a complex polygon
> (CGAL::Nef_polyhedron_2) into a small set of simple polygons
> (CGAL::Polygon_2), and code to properly handle the conversion from
> CGAL::Polygon_with_holes_2 back to CGAL::Nef_polyhedron_2. Please let me
> know if you would be interested in a patch, in which case I would clean it
> up a bit and add some regression tests.
>
I looked a bit at doing this using ClipperLib’s minkowski sum, but it looks like it requires the first path to be a polyline and doesn’t understand holes.

Perhaps it makes sense to do this in CGAL after all, and I’d be interested in your patch.

The OpenSCAD code for doing this has changed a bit, and we kicked out 2D Nef polyhedrons from the core data structures.
This is the utility function for doing 2D minkowski right now:
https://github.com/openscad/openscad/blob/issue527/src/GeometryEvaluator.cc#L221

I understand that it might be a bit of work to redo this for the issue527 branch, but if you post your code somewhere, I might be able to massage it in there..
Also, if this is done cleanly, I’m sure RapCAD could use the code as well :)

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

Maurice van Peursem
In reply to this post by kitwallace
Thanks for that. I think it is also possible to have a different
scale-factor in the X and Y direction, maybe you could add this to
the documentation?

Maurice


>I suppose both buggy and bugless modes of Minkowski could be supported if bug
>exploitation is common.  I at least would find a bugless mode useful.
>
>Btw many thanks Marius for your improvements to my Savoy vase code - I've
>added to the documentation in the wiki on the scale parameter which is a
>very welcome addition.
>
>https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/2D_to_3D_Extrusion
>
>-Chris
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kitwallace
Hi Maurice

Do you know what the parameter names are - I've tried a few guesses but no luck

Chris


On Fri, Jan 10, 2014 at 11:55 AM, Maurice van Peursem [via OpenSCAD] <[hidden email]> wrote:
Thanks for that. I think it is also possible to have a different
scale-factor in the X and Y direction, maybe you could add this to
the documentation?

Maurice


>I suppose both buggy and bugless modes of Minkowski could be supported if bug
>exploitation is common.  I at least would find a bugless mode useful.
>
>Btw many thanks Marius for your improvements to my Savoy vase code - I've
>added to the documentation in the wiki on the scale parameter which is a
>very welcome addition.
>
>https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/2D_to_3D_Extrusion
>
>-Chris
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566



If you reply to this email, your message will be added to the discussion below:
http://forum.openscad.org/BUG-minkowski-fills-holes-when-used-with-2D-polygons-tp2797p6449.html
To unsubscribe from BUG: minkowski() fills holes when used with 2D polygons, click here.
NAML

Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator

On Jan 10, 2014, at 07:00 AM, kitwallace <[hidden email]> wrote:

> Hi Maurice
>
> Do you know what the parameter names are - I've tried a few guesses but no
> luck

scale can be a vector. See:
o  https://github.com/openscad/openscad/issues/273
o https://github.com/openscad/openscad/blob/master/testdata/scad/features/linear_extrude-scale-zero-tests.scad

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

Oskar
In reply to this post by kintel
Hi Marius,

kintel wrote
On Jan 7, 2014, at 19:06 PM, Oskar <[hidden email]> wrote:
>
> *) It entailed implementing a decomposition of a complex polygon
> (CGAL::Nef_polyhedron_2) into a small set of simple polygons
> (CGAL::Polygon_2), and code to properly handle the conversion from
> CGAL::Polygon_with_holes_2 back to CGAL::Nef_polyhedron_2. Please let me
> know if you would be interested in a patch, in which case I would clean it
> up a bit and add some regression tests.
>
I looked a bit at doing this using ClipperLib’s minkowski sum, but it looks like it requires the first path to be a polyline and doesn’t understand holes.

Perhaps it makes sense to do this in CGAL after all, and I’d be interested in your patch.

The OpenSCAD code for doing this has changed a bit, and we kicked out 2D Nef polyhedrons from the core data structures.
This is the utility function for doing 2D minkowski right now:
https://github.com/openscad/openscad/blob/issue527/src/GeometryEvaluator.cc#L221

I understand that it might be a bit of work to redo this for the issue527 branch, but if you post your code somewhere, I might be able to massage it in there..
I had a quick look at the issue527 code and it will be quite straight forward to port my CGAL::minkowski patch to this branch. I have one question though: Looking at the code, the new Polygon2d class represents a polygon as a set of outlines (that may be either positive or negative). What kind of restrictions/constraints can I expect these polygons to have. I.e.:

* Can outlines be self-intersecting? (complex polygons)
* Can outlines intersect other outlines within the same polygon?
* Can outline edges be touching?
* Can outline vertices be touching?
* Can one Polygon2D contain more than one disjoint shape? (union() { square(1); translate([2,0]) square(1); })
* Are unbounded polygons supported (for example, the outer outline is negative, meaning that everything outside is part of the polygon)?
* Are we guaranteed that a negative outline is contained inside a positive outlines, and further, that any positive outline is either contained inside a negative outline or being a outer boundary?
* Is winding-order consistent with positiveness, or can these be arbitrary?
* Is it a simple "polygon with holes" model. I.e one single positive outline with zero or more negative holes (where all holes are non-intersecting and the positive outline is simple)?
* Are the outlines ordered in any way? (E.g. a inner outline always comes after its immediate surrounding outer outline)

Best regards,

Oskar
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
On Jan 10, 2014, at 13:51 PM, Oskar <[hidden email]> wrote:

> […] the new Polygon2d class […]. What kind of
> restrictions/constraints can I expect these polygons to have. I.e.:
>
First of all, Polygon2d is used to store a what both DxfData and CGAL_polyhedron_2 used to store.

Polygon2d’s are used both for user input and for result of processing. After being processed they’ll typically be sanitized (see isSanitized()).

For non-sanitized Polygon2d’s anything goes, but the end result is dependent on how sanitizing works.
Sanitizing is typically done using ClipperLib (http://www.angusj.com/delphi/clipper.php)

For sanitized polygons, you should be able to trust the following:

> * Can outlines be self-intersecting? (complex polygons)
No

> * Can outlines intersect other outlines within the same polygon?
No

> * Can outline edges be touching?
No

> * Can outline vertices be touching?
Yes (I think so): Two outlines can share a vertex (e.g. two positive outlines or two negative outlines)

> * Can one Polygon2D contain more than one disjoint shape? (union() {
> square(1); translate([2,0]) square(1); })

Yes: There can be more than one top-level positive outline.

> * Are unbounded polygons supported (for example, the outer outline is
> negative, meaning that everything outside is part of the polygon)?
No

> * Are we guaranteed that a negative outline is contained inside a positive
> outlines, and further, that any positive outline is either contained inside
> a negative outline or being a outer boundary?
Yes

> * Is winding-order consistent with positiveness, or can these be arbitrary?
They are consistent

> * Is it a simple "polygon with holes" model. I.e one single positive outline
> with zero or more negative holes (where all holes are non-intersecting and
> the positive outline is simple)?
Should be clear from the above.

> * Are the outlines ordered in any way? (E.g. a inner outline always comes
> after its immediate surrounding outer outline)
I’m not sure. We use an external library (ClipperLib) to do calculations. I don’t know/remember if this is guaranteed.

Also note that we don’t (yet) support open polylines. This may change in the future and may require further refactoring of Polygon2d.

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

Oskar
Thank you Marius, very useful information!

Instead of porting my CGAL Minkowski patch, I (hopefully) managed to implement the correct behavior on top of Clipper's MinkowskiSum. Please review https://github.com/openscad/openscad/pull/601

Best regards,

Oskar
Reply | Threaded
Open this post in threaded view
|

Re: BUG: minkowski() fills holes when used with 2D polygons

kintel
Administrator
On Jan 12, 2014, at 10:32 AM, Oskar <[hidden email]> wrote:
>
> Instead of porting my CGAL Minkowski patch, I (hopefully) managed to
> implement the correct behavior on top of Clipper's MinkowskiSum. Please
> review https://github.com/openscad/openscad/pull/601
>
Nice - thx!
I merged it with a minor change avoiding the extra sanitization step in the end.

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566