// 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); } 
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/thesavoyvase for context.

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 
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 
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/scadutils 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. 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. 
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/scadutils > <https://github.com/OskarLinde/scadutils> 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 
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? Definitely. It also means that operations such offset/inset/shell etc are implementable with good performance using nothing more than CSG+minkowski. 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: 
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 
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 
In reply to this post by kitwallace
Thanks for that. I think it is also possible to have a different
scalefactor 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 
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 
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_extrudescalezerotests.scad Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://rocklinux.net/mailman/listinfo/openscad http://openscad.org  https://flattr.com/thing/121566 
In reply to this post by kintel
Hi Marius,
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 selfintersecting? (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 windingorder 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 nonintersecting 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 
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 nonsanitized 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 selfintersecting? (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 toplevel 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 windingorder 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 nonintersecting 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 
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 
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 
Free forum by Nabble  Edit this page 