 Classic List Threaded 31 messages 12
Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

Open this post in threaded view
|

 I agree that Boolean operations, offset e minkovski of objects defined by points has its own interested. However, my point when I started this thread was the inefficiency of the projection() operator. I consider brute force to approach the projection by simply joining polygons by Boolean union. Something better would be expected but it seems that is the way OpenSCAD does projection as you can see by this small example:\$fn=400;tw=180;sc=0.01;projection()union(){  linear_extrude(20,twist=tw,scale=sc)    circle(30);   mirror([0,0,1])     linear_extrude(20,twist=tw,scale=sc)      circle(30);}It took more than 7 min. in my computer to find a circle with 400 vertices at the end. Even with tw=0 and sc=0.8, it required 8 sec.I think the union of polygons is one of the worst strategy to projection despite its conceptual simplicity. The border of the projection of a polyhedron is contained in the projection of its vertical silhouette edges namely and loosely those edges whose adjacent faces are one facing upward and the other, downward. Usually the set of silhouette edges is a small fraction of the total number. After finding the silhouette edges and projecting them a sweep algorithm may be used to connect the segments and define a polygon. To those that may be interested, here is a reference: It is not an easy task to implement in OpenSCAD language but it would be far easier and faster than polygon union. Anyway, I am not interested here in native language implementations of projection but to have a faster built-in one. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 Thank you Carsten for spending your time to check my example, showing the Boolean operation is the main culprit for the long running time. Your analysis almost makes me complacent with the projection() low performance. But at the end, I have decided to investigate what makes it stuck.As a test case, I took a torus knot generated by sweeping a circle. To simplify I have chosen a knot (3,2) which has only 4 areas of projection overlapping (see attached image). My test main code was simply:// geometric datan = 20;  // section discretizationm = 40 ;  // path discretizationd = 20;   // section radiusR = 400;  // knot major radiusr = 150;  // knot minor radiusp  = 3;q  = 2;to = true; echo(p=p, q=q);echo(n=n, m=m);if(to) {  echo("only knot");  sweep(sections(p,q,n,m,d));}else{  echo("knot projection");  projection()   sweep(sections(p,q,n,m,d));}where sections() generates m circular sections with n points each along a (3,2) knot path. The full code I have used in my tests is attached. Note that the circular sections have a radius d very small compared to the torus major radius. I have ran three cases with 20000 vertices and I got these time results:                        just the knot           knot projection   n =  50, m = 400           6 sec                    12 secn = 100, m = 200           6 sec                    16 secn = 500, m =  40           6 sec                  2 min 45 secWhat makes the last projection so slow? The last one is the case whose projected polygon has the least number of vertices, estimated as something near 2*m = 80 point. The reason might be the number of triangles that have intersection after the projection. My second image shows the detail of one of those intersections in wireframe view for n=6 and m=40. With n=500, more than 2000 triangles overlap at each of the 4 intersections. The third image shows the detail of the same knot intersections in wireframe view for n=6 and m=200 and it seems that much more triangles overlap when m is increased. So, the number of overlapping triangles doesn't seem to be the reason for a long run time of the projection. Two additional tests have shown the puzzle complexity: with 25000 points (n=500, m=50) the projection required 2 min and 2 sec and with n=500 and m=80 (40000 vertices) the projection time was nearly the same: 2 min and 43 sec..The torus knot seems to be easy to project by silhouette computation followed by the sweep line algorithm: it may have a lot of silhouette segments but a few intersections between them. A much harder case for that algorithm would be a linear_extrusion of a circle with a cleverly chosen twist and a scale a slightly less than 1.OpenSCAD projection() performance is still a mystery. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org torus_knot_3_2_top.PNG (70K) Download Attachment torus_knot_3_2_top_wireframe_6x40.PNG (30K) Download Attachment torus_knot_3_2_top_wireframe_6x200.PNG (43K) Download Attachment Sweep_Knot.scad (1K) Download Attachment