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:
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: 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 
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 
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 
On 20200221 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 XYplane 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 
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 
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? _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
In reply to this post by Parkinbot
On 20200221 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 reallife 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 
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 
OK, its easy if you have all Boolean operations available. @nophead, my 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:
The results are astonishing. For a nonconvex 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 
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 
In reply to this post by Ronaldo
That sentence is a nonsense. 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 
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 
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 
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 
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 selfintersection 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 mostoutside to most inside. You now have the result region.  Revar
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
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 
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 _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Wow... adding a set of functions like that would be fantastic
Sent from my iPhone On Feb 23, 2020, at 3:04 PM, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Administrator

In reply to this post by nophead
nophead 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. Hasn't someone done that, OpenSCAD modules etc rewritten in userland? Found it! https://github.com/thehans/FunctionalOpenSCAD  Admin  email* me if you need anything, or if I've done something stupid... * click on my MichaelAtOz label, there is a link to email me. Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.  Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Admin  email* me if you need anything, or if I've done something stupid...
* click on my MichaelAtOz label, there is a link to email me. Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above. 
In reply to this post by nophead
I would love to see builtin functions for `union()`, `difference()`, `intersection()`, and `offset()` too. That last one is far harder to implement correctly than the boolean ops. Clipperlib would be far faster and it’s already been debugged. While we’re at it, functional `hull()` would be nice, too. RevarBat On Feb 23, 2020, at 3:04 PM, nop head <[hidden email]> wrote:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org 
Free forum by Nabble  Edit this page 