Empathy List Archives

RP

Ronaldo Persiano

Fri, Feb 21, 2020 12:06 AM

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?

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?

P

Parkinbot

Fri, Feb 21, 2020 10:40 AM

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/

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/

P

Parkinbot

Fri, Feb 21, 2020 11:57 AM

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/

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/

A

arnholm@arnholm.org

Fri, Feb 21, 2020 12:25 PM

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

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

P

Parkinbot

Fri, Feb 21, 2020 2:24 PM

sounds like it is O(n²), because of the the union?

--
Sent from: http://forum.openscad.org/

sounds like it is O(n²), because of the the union? -- Sent from: http://forum.openscad.org/

NH

nop head

Fri, Feb 21, 2020 2:26 PM

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 rudolf@digitaldocument.de wrote:

sounds like it is O(n²), because of the the union?

--
Sent from: http://forum.openscad.org/

OpenSCAD mailing list
Discuss@lists.openscad.org
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 <rudolf@digitaldocument.de> wrote: > sounds like it is O(n²), because of the the union? > > > > -- > Sent from: http://forum.openscad.org/ > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

A

arnholm@arnholm.org

Fri, Feb 21, 2020 2:34 PM

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

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

P

Parkinbot

Fri, Feb 21, 2020 2:54 PM

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/

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/

RP

Ronaldo Persiano

Fri, Feb 21, 2020 4:57 PM

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?

> > 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?

P

Parkinbot

Fri, Feb 21, 2020 6:23 PM

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/

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/

discuss@lists.openscad.org

About projection()