cacb 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? > > What is missing in this thinking? > ... I wanted to do 'wrap text on surface' stuff. To make that work involves a plastic transform, which, in OPENscad is only possible if you manipulate the points as data. https://gist.github.com/NateTG/b350378c56f436d3996a2107f7cba965 -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Ronaldo
Ronaldo wrote
> I agree that earcut method may generate very bad triangles, almost > degenerated. That is one reason I would look for something else. I don't > know how the sweep line algorithms work but remind that for our > application > in mind we can't add new vertices to any polygonal. You don't have to add vertices. If you're sweeping "left to right" then it will cut at every vertex that is "convex to the right." It's basically this: https://en.wikipedia.org/wiki/Polygon_triangulation#Monotone_Polygon_Triangulation -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Ronaldo
On 2019-01-21 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 built-in 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:N-1]) 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 2019-01-22 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 one-liner, 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/Polygon-stuffs). 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:
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 _______________________________________________ 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 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 ear-cut method for simple polygons at the paper beginning, he does not discuss the necessary changes in the method to deal with FSPs. The conventional ear-cut method does not works directly with FSP. Analysing my implementation of the ear-cut 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 ear-cut 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 ear-cut 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 ear-cut 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 |
Hmm, I would expect your example to have a key hole representation similar to
this image: <http://forum.openscad.org/file/t887/FSP.png> So no additional vertices are introduced. When the earcut travels now along the "outline" of the FSP, it will have to ignore the vertices of an edge when it analyzes a triangle containing its fake counterpart - or (just a thought) it might relax a ">=" condition into a ">=" condition (or vice versa) and thus allow for simple polygons with shared vertices. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Parkinbot wrote Hmm, I would expect your example to have a key hole representation similar to 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 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 |
Ronaldo wrote:
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 ear-cut triangulation. Here is my previous sweep example working now directly with the FSP generated by polyHoles.
_______________________________________________ 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:N-1]) 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 |
Sorry my fault, the inner polygon needs reversed orientation of course.
function FSP(out, in) = [for(i=out) i, out[0], for(i=[len(in)-1:-1:0]) in[i], in[0], out[0]]; Yeah, it works!!!! Great! Sometimes it is a long journey to find out that everything was already there. <http://forum.openscad.org/file/t887/fsp_poly.png> -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Don't be lazy and run a code with a full legal polyhedron! A quarta, 27/02/2019, 16:14, Parkinbot <[hidden email]> escreveu: Sorry my fault, the inner polygon needs reversed orientation of course. _______________________________________________ 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:N-1]) 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 |
Of course, one can omit the union test, do F6 and export a proper STL. After
import Boolean operations will work. import("FSP.stl"); cube(1); So it is CGAL that is playing unfair. Haven't we had this result already near thread start? @Hans: It might be not a big thing to feed CGAL with a fully tesselated version of a polyhedron. -- 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 .
In reply to this post by Ronaldo
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 x-value in each inner polygon and puts them into a list A. 2. selects the polygon n with minimal x-value 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 x-values and indices let(ibestP = minX(minXlist)) // get index of best polygon (i.e. with lowest x-value) 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]) // x-val 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 minX-values, 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:N-1]) 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 |
Free forum by Nabble | Edit this page |