
123456

On 20190121 21:59, Ronaldo Persiano wrote:
> < [hidden email]> wrote:
>
>> Why this long and complex discussion when you can use 2D booleans 
>> i.e.
>> subtract the holes from the main rectangle and simply extrude that?
>
> The main goal now is to sweep a polygon with holes along a polygonal
> line using fast polyhedron.
Maybe achieving something similar to this then?
https://gist.github.com/arnholm/931bba4633ca344a3ffe0698b945395f> This avoid slower boolean operations. As
> Parkinbot pointed before, we might instead sweep the polygon border
> and subtract the sweeping of each hole in a slower process.
Ok, but this should not really take a lot of processing time with any of
the possible approaches. The example above, which take a "high level
approach" instead of constructing a complex polyhedron manually, was
processed with https://github.com/arnholm/xcsg in less than 0.15 sec.
The 2d booleans are not slow in OpenSCAD, a builtin sweep is missing
though.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Carsten,
being able to extrude a 2D object (with holes) along a fancy path in
extension of linear_extrude would be a nice to have (without having to
install angelscript :) ), but the discussed approach is even more
ambitious. Just read the thread from start.
The multi hole sweep will allow each polygon to morph along the path, like
shown in the following example code that "extrudes" a CW screw with a CCW
hole:
< http://forum.openscad.org/file/t887/CWCCW.png>
use <Naca_sweep.scad>
difference()
{
sweep(gendat(circle(100, N=4), 1));
sweep(gendat(circle(60, N=4), .5));
}
function gendat(P, dir=1) =
[for (i=[45:45]) Tz_(i, Rz_(dir*i, vec3D(P)))];
function circle(r, N) = [for(i=[0:N1]) let(w=360/N*i) r*[cos(w), sin(w)]];

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20190122 13:36, Parkinbot wrote:
> Carsten,
>
> being able to extrude a 2D object (with holes) along a fancy path in
> extension of linear_extrude would be a nice to have (without having to
> install angelscript :) ),
You don't need angelscript to do it. The xcsg application knows nothing
about angelscript, it only relates to the specification of the wiki at
https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
alternative front end.
> but the discussed approach is even more
> ambitious. Just read the thread from start.
> The multi hole sweep will allow each polygon to morph along the path,
> like
> shown in the following example code that "extrudes" a CW screw with a
> CCW
> hole:
> < http://forum.openscad.org/file/t887/CWCCW.png>
Ok, that was the part I was missing then, thanks. I agree that is more
ambitious.
Talking about morphing, I have tried that (with holes also)
https://github.com/arnholm/xcsg/wiki/transform_extrude , but not in
combination with a general sweep path.
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


cacb wrote
> You don't need angelscript to do it. The xcsg application knows nothing
> about angelscript, it only relates to the specification of the wiki at
> https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
> alternative front end.
thanks for the hint. I always wanted to find out how to use MATLAB as a
frontend. Hope I'll soon find time to dig deeper into this interesting
approach.
cacb wrote
> Talking about morphing,
OK, this is a trivial linear interpolation and more or less a oneliner, if
you have arithmetics operating over point lists.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


After a big good struggle, I have finally devised a way to do a partition of a polygon with holes in parts which are simple polygons. It does not find the best partition in the number parts but the partition is limited to m+1 polygons where m is the number of holes. The OpenSCAD codes of the method, some tests cases of it and of the sweep of polygon with holes may be found in my github repository ( https://github.com/RonaldoCMP/Polygonstuffs). Here I will present and discuss some cases.
The following image shows the best and worst cases of the method.
As the method is biased from left to right and right to left, it is impossible for it to find a bipartition when the holes are distributed verticaly. The number of parts in the worst case is m+1.
The worst case for any method (the problem worst case) may be seen bellow.
This example is based on a case devised by Parkinbot and shows that for some cases there is no smaller partition than one with m+1 parts.
To evaluate the time spent by the method I run the next case with many sizes of the matrix of holes and square refinements.
In this example I could change the size of the hole matrix and the number of vertices in all square edges. In my machine, without square refinements, the method spent negligible time to get a partition of 49 holes (4*50 vertices), 3s for 100 holes and 13s for 200 holes. With 25 holes and square refinements, it spent 3s with 1600 vertices (16 per edge) and 9s with 3200 vertices. So, it is very efficient for practical applications.
Now, a real application case: sweeping a polygon with holes with just one polyhedron call. The shape to be swept is the following, already processed by the method:
Sweeping this polygon along a spiral curve with proper code led to:
This image is a render of the sweep with a cube subtracted from it to show it is CGAL palatable. The model was built by "lazy unioning" 6 pieces which are not manifolds: the two caps, the outer sweep without caps and the 3 hole sweeps without caps. Each of those parts is output by a code that generates a polyhedron data format [points, faces]. The lazy union module just "stitches" the incoming polyhedron data together. I have updated my sweep library in github including a module lazyUnion(), the module that produced the image.
To get an idea of how that model was produced I show bellow an excerpt of its main code:
outer = circ(r=50,n=24); // the outer border mH = cxydistr(25, 4, 3, revert(circ(12,24))); // hole borders // build the polygon for the face with holes holedFacePDat = polyHolePartition(outer, mH, true); path = spiral(200,80,270,24); tpath = construct_transform_path(path); // sweep the outer face and the holes without caps souter = sweep_polyhedron(outer, tpath, caps=false); shole0 = sweep_polyhedron(mH[0], tpath, caps=false); shole1 = sweep_polyhedron(mH[1], tpath, caps=false); shole2 = sweep_polyhedron(mH[2], tpath, caps=false); // transform holedFacePDat to put the holed caps in proper place begCap = tranfPdata(tpath[0], holedFacePDat) ; endCap = tranfPdata(tpath[lpath1], holedFacePDat, inv=true) ; // join evething in one polyhedron lazyUnion([souter,begCap,endCap, shole0, shole1, shole2]); translate([160,50,0]) cube([60,60,150]);
Note that polyHolePartition is able to output the partition in one of two formats depending on its third argument value: a simple list of the partition polygons (the default) or that partition in polyhedron data format, that is a list of vertices followed by a list of faces.
Finally, the image of that sweep with edges on reveals an irony. After all the work to get a reasonable partition of the polygon with holes, the alternate construction of OpenSCAD triangulates the sweep shape because it is not planar after have been geometric transformed to its place! Em ter, 22 de jan de 2019 às 14:43, Parkinbot < [hidden email]> escreveu: cacb wrote
> You don't need angelscript to do it. The xcsg application knows nothing
> about angelscript, it only relates to the specification of the wiki at
> https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
> alternative front end.
thanks for the hint. I always wanted to find out how to use MATLAB as a
frontend. Hope I'll soon find time to dig deeper into this interesting
approach.
cacb wrote
> Talking about morphing,
OK, this is a trivial linear interpolation and more or less a oneliner, if
you have arithmetics operating over point lists.

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


Ronaldo,
congrats, it looks like you had a hard time and did a great piece of work.
Without having been able to study and accompany your solution path in
greater detail (I'm currently fully booked and completely out of time) I
think it can work the way you describe it, and the implementation of such an
algorithm in OpenSCAD is a piece of art of its own.
However, I still have the vague hope one could get along with a simple
earcut and a keyhole representation running from the outer polygon over each
of the holes and back to the outer polygon  without dissecting any hole and
WITHOUT even partitioning the polygon once. Your remark
Ronaldo wrote
> The polyHoles() code implements the David Eberly method of bridging a
> polygon with (any number of) holes in order to apply his earcut
> triangulation method to the resulting (almost) simple polygon. The
> polygon polyHoles() returns has no holes but is not really a simple
> polygon: some edges of it are traveled twice as you traverse its full
> cycle.
has raised this hope, a more or less vague gut feeling. As I understand the
keyhole representation this algorithm generates, it is a means to construct
a fake polygon without a hole from a polygon with holes. As you already
suspected "changing some constraints in the earcut method" might lead to a
much less demanding solution.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Parkinbot wrote: However, I still have the vague hope one could get along with a simple
earcut and a keyhole representation running from the outer polygon over each
of the holes and back to the outer polygon  without dissecting any hole and
WITHOUT even partitioning the polygon once. Your remark
Well, that was the goal of David Eberly's paper. It describes an algorithm to transform a polygon with holes in a fake simple polygon without holes (I liked this name) . I have implemented a version of this algorithm in my polyHoles.scad code which is now uploaded in my github repository in its last version. The fake simple polygon (FSP) it generates has some edges which are traveled twice when the all the border of the FSP is traveled. So, it is not a simple polygon. However, although Eberly describes a version of the earcut method for simple polygons at the paper beginning, he does not discuss the necessary changes in the method to deal with FSPs. The conventional earcut method does not works directly with FSP. Analysing my implementation of the earcut method, I saw that the check for an ear should be relaxed to allow other vertices on the ear border. And it seems to work for FSP with that relaxed conditions.
I have made a comparison between the relaxed earcut method and the polygon partition one. An image of the one result is bellow.
We have here a polygon with 4 holes with 4 additional vertices inserted in every original edge. From left to right, we have the partition of the polygon made by polyHolePartition, the earcut triangulation of the FSP, and the FSP itself. The partition has 4 parts which are simple polygon, the triangulation has 106 triangles and the FSP just one polygon. All solutions have 108 vertices. So the number of parts involved, although reasonable in the partition case, is very large with the triangulation solution. Besides, many triangles are very thin, almost degenerate, like the ones just bellow the two holes at southwest. This may be a cause of troubles in the render of sweeps. A run time comparison is even more strikingly against triangulation. Although the implementation of the earcut method is much simpler than the implementation of the polyHolePartition, the triangulation method is much more inefficient and spent a lot more time than the partition method when the number of vertices grows.
To tell you the truth, I don't like the solution of the partition method (and even less the triangilation). I would prefer far more the FSP generated by polyHoles. The only reason I developed the implementation of the partition method is that FSP faces are not acceptable by polyhedrons in render, although it is acceptable by polygon() and its linear_extrude(). So, my hope is that some day OpenSCAD could deal with polyhedron faces with the same generality it deals in polygon(). Then, polyHolePartition and triangulation of faces will be history.
The irony I mentioned in the end of my last message is that anything we do a partition of a polygon with holes in simple polygons to turn it palatable to CGAL, the system will discard it and make its own triangulation of the face.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Sorry, I have not made myself clear. The additional vertices where introduced to the polygons *before* calling any process in order to evaluate the effect of the number of vertices. You may think that all polygons are circle. My functions do not add any vertices to the input polygons.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Ronaldo wrote
> Sorry, I have not made myself clear. The additional vertices where
> introduced to the polygons *before* calling any process in order to
> evaluate the effect of the number of vertices.
Ok, but this relativates the following statement:
Ronaldo wrote
> Besides, many triangles are very thin, almost degenerate, like the ones
> just bellow the two holes at southwest. This may be a cause of troubles in
> the render of sweeps.
and isn't that outcome a general problem of earcut?
Ronaldo wrote
> which is now uploaded in my github repository in its last version.
I'll download and test it in the next days.
Ronaldo wrote
> The irony I mentioned in the end of my last message is that anything we do
> a partition of a polygon with holes in simple polygons to turn it
> palatable to CGAL, the system will discard it and make its own
> triangulation of the face.
Yeah, the main irony is indeed that OpenSCAD already has the capability to
triangulate polygons with holes, but it cannot be accessed from user space.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Parkinbot, wrote: Yeah, the main irony is indeed that OpenSCAD already has the capability to
triangulate polygons with holes, but it cannot be accessed from user space.
I don't know if it is capable of dealing directly with polygons with holes because there is no way to specify it except by boolean differences or by FSP. And I don't care to access it directly. I would be glad that faces with holes for polyhedron could be accepted in FSP format the same way they are accepted by polygon() once we don't have any way to define polyhedron faces by boolean differences.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I would be glad that faces with holes for polyhedron could be accepted in FSP format the same way they are accepted by polygon() once we don't have any way to define polyhedron faces by boolean differences.
I was wrong! I have checked again and the primitive polyhedron is able to deal with FSP ! There was a bug in my previous tests. So, we don't need to do any partition, either by triangulation or polyHolePartition, to a FSP and the only additional function needed to sweep polygons with holes is polyHoles which is lighter than polyHolePartition() and much more efficient than earcut triangulation.
Here is my previous sweep example working now directly with the FSP generated by polyHoles.
use <sweep.scad> // this is my sweep version with sweep_polyhedron() and lazyUnion() outer = circ(r=50,n=24); // the outer border mH = circ_distrib(25, 4, 3, revert(circ(12,24))); // holes borders // build the FSP for the face with holes FSP = polyHoles(outer, mH); // express it in a pdata format FSP_PDat = [ FSP, [[for(i=[0:len(FSP)1]) i]] ]; path = spiral(200,80,270,24); // the sweep path transforms ptrans = construct_transform_path(path); // sweep the outer face and the holes without caps // sweep_polyhedron function generates the pdata of the sweep souter = sweep_polyhedron(outer, ptrans, caps=false); shole0 = sweep_polyhedron(mH[0], ptrans, caps=false); shole1 = sweep_polyhedron(mH[1], ptrans, caps=false); shole2 = sweep_polyhedron(mH[2], ptrans, caps=false); // transform FSP_PDat to put the holed caps in proper place begCap = tranfPdata(ptrans[0], FSP_PDat) ; endCap = tranfPdata(ptrans[len(ptrans)1], FSP_PDat, rev=true) ; // join evething in one polyhedron lazyUnion([souter, begCap, endCap, shole0, shole1, shole2]); translate([160,50,0]) cube([60,60,150]); function spiral(r,h,ang,n) = [for(i=to_(n)) [r*cos(i*ang/n), r*sin(i*ang/n),i*h/n] ]; function circ(r,n,a=360) = [for(i=to_(n)) r*[cos(i*a/n), sin(i*a/n),0] ]; function T_(p,lp) = [for(pi=lp) pi+p ]; function circ_distrib(r,n,m,lp) = [for(i=to_(m)) rotz(i*360/n, T_([0,r,0],lp) ) ]; function tranfPdata(transf, pdata, rev=false) = [ transform(transf, pdata[0]), pdata[1] ] : [ transform(transf, pdata[0]), [for(f=pdata[1]) revert(f) ] ]; let( T = [ [cos(a), sin(a), 0],[sin(a),cos(a),0],[0,0,1] ] ) lp[0][0]==undef? T*lp :[ for(pi=lp) T*pi ] ; function revert(l) = !(len(l)>0)? [] : [ for(i=[len(l)1:1:0]) l[i] ]; function to_(n) = [0:n1]; function transform(m, list) = [for (p=list)let( q = m*concat(p,[1]) ) [q.x,q.y,q.z]/q[3]];
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Ronaldo wrote
> I was wrong! I have checked again and the primitive polyhedron is able to
> deal with FSP !
I tried to verify with OpenSCAD RC2, remembering that I had already checked
it when the thread started. I would say: polyhedron() does not interpret an
FSP. Or do you use another representation?
< http://forum.openscad.org/file/t887/FSP_polyhedron.png>
This is my code:
o = circle(r=100, z=100);
i = circle(r=10, z=100);
fsp = FSP(o,i);
color("red") polygon(vec2(fsp));
polyhedron(fsp, [Rg(2*len(fsp))]);
// line(fsp, color = "green");
function circle(r=10, N=3, z=0) = [for(i=[0:N]) let(a=360/N*i) r*[cos(a),
sin(a),z/r]];
function vec2(P) = [for(p=P) [p[0], p[1]]];
function Rg(N) = [for(i=[0:N1]) i];
function FSP(out, in) = [for(i=out) i, out[0], for(i=in) i, in[0], out[0]];

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Ronaldo wrote
> Don't be lazy and run a code with a full legal polyhedron!
You are right, better always do a full test. The following code is well with
F5/F12, but doesn't render properly with F6, when a cube is unioned.
o = circle(r=100, z=0);
i = circle(r=10, z=0);
o1 = circle(r=100, z=100);
i1 = circle(r=10, z=100);
P = concat(o, i, o1, i1);
F = [0, 3, 5, 4, 3, 0, 1, 2, 0]; // FSP lower
F1 = [6,8,7,6,9,10,11, 9,6]; // FSP upper
A = [[1,0,6], [1, 6, 7], [0, 2, 8], [0, 8, 6], [2, 1, 8], [1, 7, 8]]; //
inner
B = [[3,4,10], [3,10,9],[4, 11, 10], [4,5,11], [5, 3, 9], [5,9,11]]; //
outer
polyhedron(P, concat([F1, F], A, B));
cube(1);
function circle(r=10, N=3, z=0) = [for(i=[0:N1]) let(a=360/N*i) r*[cos(a),
sin(a),z/r]];

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


This post was updated on .
It's generally not lazyness but lack of time. I found time today to read the
paper more properly (a bit bony in its formalizm). After that I implemented
a FSP function, doing the same what your polyHoles does. Sorry to reinvent
the wheel, but it is so hard for me to read foreign code (you may call me a
code autist).
My code
1. finds the points B_i with minimal xvalue in each inner polygon and puts
them into a list A.
2. selects the polygon n with minimal xvalue from the list A, uses the
point B_n as bridge and excludes polygon n from the list A.
3. finds the nearest point with smaller x value in the outer polygon with
respect to the bridge
4. composes a new outer polygon using the bridge
5. does recursion until list A is empty.
Note that I don't check if polygons are simple. Here is the code and a full
blown use case with four inner polygons:
< http://forum.openscad.org/file/t887/fsp_FSP.png>
// full example of FSP
o = circle(r=100, N=4);
i0 = T([41, 25, 0], circle(r=20, N=3));
i1 = T([40, 15, 0], circle(r=20, N=3));
i2 = T([45, 10, 0], circle(r=20, N=3));
i3 = T([0, 0, 0], circle(r=20, N=3));
X = FSP(o, [i0, i1, i2, i3]);
polygon(X);
line(X);
// outer: polygon, inner: list of polygons
function FSP(outer, inner, minXlist=undef) =
let(minXlist = minXlist?minXlist:MinXList(inner)) // all bridge point
xvalues and indices
let(ibestP = minX(minXlist)) // get index of best polygon (i.e. with
lowest xvalue)
let(bestinner = inner[minXlist[ibestP][2]]) // polygon to be bridged
let(minXlist_ = excludeElem(minXlist, ibestP)) // exclude best polygon from
bridge point list
let(validx = minXlist[ibestP]) // xval and its index in best polygon
let(ibest = validx[1]) // index of bridge point in polygon
let(ibestinner = validx[2]) // index of polygon in inner list
let(bridge = inner[ibestinner][ibest]) // bridge point in polygon to be
bridged
let(obest = Nearest(outer, bridge)) // index of nearest point with <=x value
in outer polygon
let(N=len(bestinner))
let(fsp = [for(i=[0:obest]) outer[i], // outer polygon with bridge to inner
for(i=[ibest+N:1:ibest]) bestinner[i%N],
for(i=[obest:len(outer)]) outer[i%len(outer)]])
let(ret = minXlist_==[]?fsp:FSP(fsp, inner, minXlist_)) // recursion until
minXlist empty
ret;
// P is polygon list. Returns list of minXvalues, their indices and polygon
index
function MinXList(P) = [for(p=[0:len(P)1]) let(m = minX(P[p])) [P[p][m][0],
m, p]];
// index of element with smallest value in first component (x value)
function minX(P) = let(N=len(P))
[for(i=1, min=0; i<N+1; min=P[i][0]<P[min][0]?i:min, i=i+1) if(i==N)
min][0];
// exclude element with idx from list
function excludeElem(list, idx) = [for(i=[0:len(list)1]) if(i!=idx)
list[i]];
// get index of nearest point smaller x value in P wrt p
function Nearest(P, p) = let(N=len(P))
[for(i=1, min=0, val=0, val_=0; i<N+1;
min=P[i][0]<=p[0] && norm(P[i]p)<norm(P[min]p)?i:min, i=i+1)
if(i==N) min][0];
// translate polygon P
function T(x, P) = [for(p=P) p+x];
// circle polygon
function circle(r=10,N=3)=[for(i=[0:N1]) let(a=360/N*i) r*[cos(a),sin(a)]];
module line(P, r=1, color="red")
color(color)for(p=[0:len(P)1])
hull()
{
translate(P[p]) sphere(r);
translate(P[(p+1)%len(P)]) sphere(r);
}

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

123456
