31 messages
12
Open this post in threaded view
|

 I found today that multmatrix() accepts singular matrix: good stuff!. So, it is able to do projections either in 2D or 1D; however the system interpret its result as a 3D object and we can't mix it with lower dimension objects. On the other hand, it is geometrically a lower dimension object.I have devised the following strategy to compute a legal projection using multmatrix:module project() {  projection()    hull()       multmatrix( [ [1,0,0,0], [0,1,0,0],[0,0,0,0]])         children();}It uses the operator projection() but on a "solid" with much lower number of vertices. To compare project() with projection(), I have run the following two codes one at a time:project() sphere(10, \$fn=1000);projection() sphere(10, \$fn=1000); The former runs in 4 sec ; the later, in 4 min and 55 sec !!!What projection() does to take so long? _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 nice approach. But not very fruitful. It doesn't digest previous CGAL trips: project() {   translate([10,0,0])sphere(10, \$fn=100);   translate([-10,0,0])sphere(10, \$fn=100); } Anyway, it looks more like the convex hull of a projection. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 This thread is a good opportunity to get more insight into how projections are calculated for a mesh. In detail, how do algorithms that calculate projection() and projection(cut = z) look like? Say, on the basis of an affine triangulation that can be fed into polyhedron(). Therefore we have a triangle and a vertex list to start with. Any suggestions? -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 On 2020-02-21 12:57, Parkinbot wrote: > In detail, how do algorithms that calculate projection() and > projection(cut > = z) look like? As for projection(), it can be done the way I did it. Any 3d primitive or boolean result is essentially a 3d mesh of triangles. Projecting to XY-plane means to traverse all triangles of the mesh. For each triangle you drop the z coordinates to get a 2d triangle. Some of the 2d triangles will be collapsed (zero area) or will have opposite winding order, these should be dropped. For the rest perform 2d union to compute the final projection polygon(s). Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

Open this post in threaded view
|

 2D unions are fast. It is because projection() uses CGAL and anything in CGAL is unbelievably slow.On Fri, 21 Feb 2020 at 14:25, Parkinbot <[hidden email]> wrote:sounds like it is O(n²), because of the the union? -- 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
Open this post in threaded view
|

 In reply to this post by Parkinbot On 2020-02-21 15:24, Parkinbot wrote: > sounds like it is O(n²), because of the the union? I guess so, but 2d union is really fast so it isn't a real-life problem that you notice. I have not even bothered to run it in threads. Carsten Arnholm _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 In reply to this post by Parkinbot OK, its easy if you have all Boolean operations available. @nophead, my question was directed to affine representations in user space. So cacb's solution would imply that we have to implement a 2D union operation in order to do a projection in user space. Parkinbot wrote > Say, on the basis of an affine triangulation that can be fed into > polyhedron(). Therefore we have a triangle and a vertex list to start > with. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 OK, its easy if you have all Boolean operations available. @nophead, my question was directed to affine representations in user space. So cacb's solution would imply that we have to implement a 2D union operation in order to do a projection in user space. I did it for polyhedron data [v,f]. If union is the trouble (although it is a union of interior disjoint sets), I use divide and conquer in a recursive module and so the unions are of just two polygons at a time.Here is the code:module project(v,f) {   v = [for(vi=vf[0]) [vi.x,vi.y]];  f = [for(f=vf[1]) // discard downward faces         if( cross(v[f[1]]-v[f[0]],v[f[2]]-v[f[0]]) > 0 ) f];  _project(v,f);}module _project(v,f) {  if(len(f)<2)    polygon([for(iv=f[0]) v[iv]]);  else if(len(f)==2)     union() { polygon([for(iv=f[0]) v[iv]]); polygon([for(iv=f[1]) v[iv]]); }  else {    m = floor(len(f)/2);    union() {      _project(v, [for(i=[0:m]) f[i]]);      _project(v, [for(i=[m+1:len(f)-1]) f[i]]);      }    }}The results are astonishing. For a non-convex polyhedron with 40000 faces, project() rendered in 7 sec and projection() in 13 sec. For low face counts, projection() seems to work faster then project() but its running time grows faster with the number of faces (perhaps O(n^2)) while project() seems to be almost linear in the range I did my tests.Wait! The polyhedron was generated by a code and its faces (quads) are in an order such that each face is followed and preceded by neighbor faces. When I scramble the face order, project() runs much more slowly and projection() wins easily the race.The point is: it is possible to get a faster projection if neighboring information is considered and faces joined with neighbor faces first. What is the cost of finding neighboring information?  _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 Ronaldo, I see your point. The "quicksort strategy" of project() seems very efficient from a heuristical point of view. At least your algorithm is really fast, when I feed it some representation (with 40004 points and 80008 faces) generated by my sweep() function. And much faster than a projection() of the result of the sweep() module fed with the same representation.   This is my test code: y = gendat();   // 3 sec x = sweep(y);  // 1 sec function gendat() =   [for(i=[0:10000])     Rz(i, T(i/10, i/10, i/10, circle(100, N=3)))]; project(x);  4sec // projection()sweep(y); 100 sec Your results show that the implemention of 2D union can be enhanced a lot. Otherwise also module _project(v,f)   for(fi=f)       polygon(v,[fi]); would do. But, again, in order to use union, you have to use polygon() forcing you to leave user's "holy" land of affine representation...   -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 In reply to this post by Ronaldo When I scramble the face order, project() runs much more slowly and projection() wins easily the race.That sentence is a non-sense. I meant that "I shuffled the face order". Sorry about that. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 In reply to this post by Parkinbot Revar has written a union() that operates on point lists and produces point lists as output.  I don't know how fast it is, though.  It's in BOSL2.   Parkinbot wrote > But, again, in order to use union, you have to use polygon() forcing you > to > leave user's "holy" land of affine representation... > >   -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 Not very fast, and not free of bugs yet. Really wish I could call a union function built in that would let clipperlib do the actual work far faster. -Revar > On Feb 21, 2020, at 5:06 PM, adrianv <[hidden email]> wrote: > > ﻿Revar has written a union() that operates on point lists and produces point > lists as output.  I don't know how fast it is, though.  It's in BOSL2.   > > > Parkinbot wrote >> But, again, in order to use union, you have to use polygon() forcing you >> to >> leave user's "holy" land of affine representation... >> >> > > > > > > -- > 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
Open this post in threaded view
|

 Interesting. Can you give a rough outline of the algorithm your function uses? RevarBat wrote > Not very fast, and not free of bugs yet. Really wish I could call a union > function built in that would let clipperlib do the actual work far faster. > > -Revar -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 Roughly, boolean 2D geometry works as follows:First, we have the concept of a `region`, which is a list of closed paths.  You are inside a region if you can draw a line from that point out to an arbitrarily distant outside point and you cross an odd number of the region paths.A boolean operation like a union, difference, or intersection can be performed upon more than two regions at a time, but you can simplify them all to being successive operations on only two regions at a time. All boolean operations use a similar method to calculate:1) Split each region's paths up into path segments where they cross the paths of the other region.2) Tag each path segment of one region as being inside, outside, or coincident with the edge of the other region. Coincident segments come in two varieties, shared and unshared.  If a point infinitesimally to one side of the middle of the segment is inside both regions, then it is shared.  If it is only inside one, then it is unshared. This tagging is done for both regions separately.3) Filter the tagged path segments for the specific operation: (See image below.)    a) union() needs the outside and shared segments from the first region, and the outside segments from the other.    b) difference() needs the outside and unshared segments from the first region, and the inside segments from the other.    c) intersection() needs the inside and unshared segments from the first region, and the inside segments from the other.4) Assemble all of the filtered segments from both regions into closed paths. There's some fiddly bits here where you assure the shortest closed paths by checking for path self-intersection as you assemble it, and put the trailing bits back into the segments pool.5) Calculate how many other paths that each resultant path is inside of.6) Sort the paths from most-outside to most inside. You now have the result region.- RevarOn Feb 22, 2020, at 3:59 AM, Parkinbot <[hidden email]> wrote:Interesting. Can you give a rough outline of the algorithm your functionuses? RevarBat wroteNot very fast, and not free of bugs yet. Really wish I could call a unionfunction built in that would let clipperlib do the actual work far faster. -Revar--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
Open this post in threaded view
|

 Thanks. Looks more or less like expected. A clever subdivision algo for this can be found in: http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdfThe whole operation is claimed to be O(n+k)log(n) with n denoting the total number of involved edges and k  the edge intersections. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

 Perhaps add a set of functions to OpenSCAD with the same names as the boolean ops that take geometry as lists and return new lists. That would allow everything to be done in user land harnessing clipper.On Sun, 23 Feb 2020 at 22:57, Parkinbot <[hidden email]> wrote:Thanks. Looks more or less like expected. A clever subdivision algo for this can be found in: http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdf The whole operation is claimed to be O(n+k)log(n) with n denoting the total number of involved edges and k  the edge intersections. -- 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
Open this post in threaded view
|

 Wow... adding a set of functions like that would be fantastic Sent from my iPhoneOn Feb 23, 2020, at 3:04 PM, nop head <[hidden email]> wrote:﻿Perhaps add a set of functions to OpenSCAD with the same names as the boolean ops that take geometry as lists and return new lists. That would allow everything to be done in user land harnessing clipper.On Sun, 23 Feb 2020 at 22:57, Parkinbot <[hidden email]> wrote:Thanks. Looks more or less like expected. A clever subdivision algo for this can be found in: http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdf The whole operation is claimed to be O(n+k)log(n) with n denoting the total number of involved edges and k  the edge intersections. -- 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_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|