About projection()

classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

About projection()

Ronaldo
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

nophead
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

cacb
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Ronaldo
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Ronaldo
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

adrianv
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

RevarBat
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

RevarBat
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.

- Revar




On Feb 22, 2020, at 3:59 AM, Parkinbot <[hidden email]> wrote:

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


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

nophead
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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

boxcarmib
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:


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
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

MichaelAtOz
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 user-land?
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.
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

RevarBat
In reply to this post by nophead
I would love to see built-in 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:


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
12