Polyhedron tube with irregular sides -- is it possible ?

classic Classic list List threaded Threaded
112 messages Options
123456
Reply | Threaded
Open this post in threaded view
|

Re: Polyhedron tube with irregular sides -- is it possible ?

NateTG
cacb wrote
> ...
> Why this long and complex discussion when you can use 2D booleans - i.e.
> subtract the holes from the main rectangle and simply extrude that?
>
> What is missing in this thinking?
> ...

I wanted to do 'wrap text on surface' stuff.  To make that work involves a
plastic transform, which, in OPENscad is only possible if you manipulate the
points as data.

https://gist.github.com/NateTG/b350378c56f436d3996a2107f7cba965



--
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: Polyhedron tube with irregular sides -- is it possible ?

NateTG
In reply to this post by Ronaldo
Ronaldo wrote
> I agree that earcut method may generate very bad triangles, almost
> degenerated. That is one reason I would look for something else. I don't
> know how the sweep line algorithms work but remind that for our
> application
> in mind we can't add new vertices to any polygonal.

You don't have to add vertices.  If you're sweeping "left to right" then it
will cut at every vertex that is "convex to the right."

It's basically this:

https://en.wikipedia.org/wiki/Polygon_triangulation#Monotone_Polygon_Triangulation



--
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: Polyhedron tube with irregular sides -- is it possible ?

cacb
In reply to this post by Ronaldo
On 2019-01-21 21:59, Ronaldo Persiano wrote:
> <[hidden email]> wrote:
>
>> Why this long and complex discussion when you can use 2D booleans -
>> i.e.
>> subtract the holes from the main rectangle and simply extrude that?
>
> The main goal now is to sweep a polygon with holes along a polygonal
> line using fast polyhedron.

Maybe achieving something similar to this then?
https://gist.github.com/arnholm/931bba4633ca344a3ffe0698b945395f

> This avoid slower boolean operations. As
> Parkinbot pointed before, we might instead sweep the polygon border
> and subtract the sweeping of each hole in a slower process.

Ok, but this should not really take a lot of processing time with any of
the possible approaches. The example above, which take a "high level
approach" instead of constructing a complex polyhedron manually, was
processed with https://github.com/arnholm/xcsg in less than 0.15 sec.

The 2d booleans are not slow in OpenSCAD, a built-in sweep is missing
though.

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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Carsten,

being able to extrude a 2D object (with holes) along a fancy path in
extension of linear_extrude would be a nice to have (without having to
install angelscript :-) ), but the discussed approach is even more
ambitious. Just read the thread from start.

The multi hole sweep will allow each polygon to morph along the path, like
shown in the following example code that "extrudes" a CW screw with a CCW
hole:

<http://forum.openscad.org/file/t887/CWCCW.png>

use <Naca_sweep.scad>
difference()
{
  sweep(gendat(circle(100, N=4), 1));
  sweep(gendat(circle(60, N=4), -.5));
}

function gendat(P, dir=1) =
[for (i=[-45:45]) Tz_(i, Rz_(dir*i, vec3D(P)))];

function circle(r, N) = [for(i=[0:N-1]) let(w=-360/N*i) r*[cos(w), sin(w)]];



--
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: Polyhedron tube with irregular sides -- is it possible ?

cacb
On 2019-01-22 13:36, Parkinbot wrote:
> Carsten,
>
> being able to extrude a 2D object (with holes) along a fancy path in
> extension of linear_extrude would be a nice to have (without having to
> install angelscript :-) ),

You don't need angelscript to do it. The xcsg application knows nothing
about angelscript, it only relates to the specification of the wiki at
https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
alternative front end.

> but the discussed approach is even more
> ambitious. Just read the thread from start.
> The multi hole sweep will allow each polygon to morph along the path,
> like
> shown in the following example code that "extrudes" a CW screw with a
> CCW
> hole:
> <http://forum.openscad.org/file/t887/CWCCW.png>

Ok, that was the part I was missing then, thanks. I agree that is more
ambitious.

Talking about morphing, I have tried that (with holes also)
https://github.com/arnholm/xcsg/wiki/transform_extrude , but not in
combination with a general sweep path.

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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
cacb wrote
> You don't need angelscript to do it. The xcsg application knows nothing
> about angelscript, it only relates to the specification of the wiki at
> https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
> alternative front end.

thanks for the hint. I always wanted to find out how to use MATLAB as a
frontend. Hope I'll soon find time to dig deeper into this interesting
approach.  


cacb wrote
> Talking about morphing,

OK, this is a trivial linear interpolation and more or less a one-liner, if
you have arithmetics operating over point lists.



--
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: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
After a big good struggle, I have finally devised a way to do a partition of a polygon with holes in parts which are simple polygons. It does not find the best partition in the number parts but the partition is limited to m+1 polygons where m is the number of holes. The OpenSCAD codes of the method, some tests cases of it and of the sweep of polygon with holes may be found in my github repository (https://github.com/RonaldoCMP/Polygon-stuffs). Here I will present and discuss some cases.

The following image shows the best and worst cases of the method.

polyHolePartition_TheBestAndWorst.PNG
As the method is biased from left to right and right to left, it is impossible for it to find a bipartition when the holes are distributed verticaly. The number of parts in the worst case is m+1.

The worst case for any method (the problem worst case) may be seen bellow.
polyHolePartition_TheWorstProblem.PNG
This example is based on a case devised by Parkinbot and shows that for some cases there is no smaller partition than one with m+1 parts.

To evaluate the time spent by the method I run the next case with many sizes of the matrix of holes and square refinements.

SquareArranje.PNG
In this example I could change the size of the hole matrix and the number of vertices in all square edges. In my machine, without square refinements, the method spent negligible time to get a partition of 49 holes (4*50 vertices), 3s for 100 holes and 13s for 200 holes. With 25 holes and square refinements, it spent 3s with 1600 vertices (16 per edge) and 9s with 3200 vertices. So, it is very efficient for practical applications.

Now, a real application case: sweeping a polygon with holes with just one polyhedron call. The shape to be swept is the following, already processed by the method:
SweepPolygon.PNG
Sweeping this polygon along a spiral curve with proper code led to:
sweep_polyHoles_1.PNG
This image is a render of the sweep with a cube subtracted from it to show it is CGAL palatable. The model was built by "lazy unioning" 6 pieces which are not manifolds: the two caps, the outer sweep without caps and the 3 hole sweeps without caps. Each of those parts is output by a code that generates a polyhedron data format [points, faces]. The lazy union module just "stitches" the incoming polyhedron data together. I have updated my sweep library in github including a module lazyUnion(), the module that produced the image.

To get an idea of how that model was produced I show bellow an excerpt of its main code:

// the face with holes
outer = circ(r=50,n=24); // the outer border 
mH    = cxydistr(25, 4, 3, revert(circ(12,24))); // hole borders
// build the polygon for the face with holes
holedFacePDat = polyHolePartition(outer, mH, true);
// main path
path = spiral(200,80,270,24);
// the path transforms
tpath = construct_transform_path(path);
// sweep the outer face and the holes without caps
souter = sweep_polyhedron(outer, tpath, caps=false);
shole0 = sweep_polyhedron(mH[0], tpath, caps=false);
shole1 = sweep_polyhedron(mH[1], tpath, caps=false);
shole2 = sweep_polyhedron(mH[2], tpath, caps=false);
// transform holedFacePDat to put the holed caps in proper place
lpath = len(tpath);
begCap   = tranfPdata(tpath[0], holedFacePDat) ;
endCap   = tranfPdata(tpath[lpath-1], holedFacePDat, inv=true) ;
// join evething in one polyhedron
difference() {
  lazyUnion([souter,begCap,endCap, shole0, shole1, shole2]);
  translate([-160,50,0]) cube([60,60,150]);
}

Note that polyHolePartition is able to output the partition in one of two formats depending on its third argument value: a simple list of the partition polygons (the default) or that partition in polyhedron data format, that is a list of vertices followed by a list of faces.

Finally, the image of that sweep with edges on reveals an irony.
SweepPolygonEdges.PNG
After all the work to get a reasonable partition of the polygon with holes, the alternate construction of OpenSCAD triangulates the sweep shape because it is not planar after have been geometric transformed to its place! 

Em ter, 22 de jan de 2019 às 14:43, Parkinbot <[hidden email]> escreveu:
cacb wrote
> You don't need angelscript to do it. The xcsg application knows nothing
> about angelscript, it only relates to the specification of the wiki at
> https://github.com/arnholm/xcsg/wiki . In theory, OpenSCAD could be an
> alternative front end.

thanks for the hint. I always wanted to find out how to use MATLAB as a
frontend. Hope I'll soon find time to dig deeper into this interesting
approach. 


cacb wrote
> Talking about morphing,

OK, this is a trivial linear interpolation and more or less a one-liner, if
you have arithmetics operating over point lists.



--
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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo,

congrats, it looks like you had a hard time and did a great piece of work.
Without having been able to study and accompany your solution path in
greater detail (I'm currently fully booked and completely out of time) I
think it can work the way you describe it, and the implementation of such an
algorithm in OpenSCAD is a piece of art of its own.

However, I still have the vague hope one could get along with a simple
earcut and a keyhole representation running from the outer polygon over each
of the holes and back to the outer polygon - without dissecting any hole and
WITHOUT even partitioning the polygon once. Your remark


Ronaldo wrote
> The polyHoles() code implements the David Eberly method of bridging a
> polygon with (any number of) holes in order to apply his earcut
> triangulation method  to the resulting (almost) simple polygon. The
> polygon polyHoles() returns has no holes but is not really a simple
> polygon: some edges of it are traveled twice as you traverse its full
> cycle.

has raised this hope, a more or less vague gut feeling. As I understand the
keyhole representation this algorithm generates, it is a means to construct
a fake polygon without a hole from a polygon with holes. As you already
suspected "changing some constraints in the earcut method" might lead to a
much less demanding solution.






--
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: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Parkinbot wrote: 
However, I still have the vague hope one could get along with a simple
earcut and a keyhole representation running from the outer polygon over each
of the holes and back to the outer polygon - without dissecting any hole and
WITHOUT even partitioning the polygon once. Your remark

Well, that was the goal of David Eberly's paper. It describes an algorithm to transform a polygon with holes in a fake simple polygon without holes (I liked this name) . I have implemented a version of this algorithm in my polyHoles.scad code which is now uploaded in my github repository in its last version. The fake simple polygon (FSP) it generates has some edges which are traveled twice when the all the border of the FSP is traveled. So, it is not a simple polygon. However, although Eberly describes a version of the ear-cut method for simple polygons at the paper beginning, he does not  discuss the necessary changes in the method to deal with FSPs. The conventional ear-cut method does not works directly with FSP. Analysing my implementation of the ear-cut method, I saw that the check for an ear should be relaxed to allow other vertices on the ear border. And it seems to work for FSP with that relaxed conditions.

I have made a comparison between the relaxed ear-cut method and the polygon partition one. An image of the one result is bellow.
polyComparison.PNG
We have here a polygon with 4 holes with 4 additional vertices inserted in every original edge. From left to right, we have the partition of the polygon made by polyHolePartition, the ear-cut triangulation of the FSP, and the FSP itself. The partition has 4 parts which are simple polygon, the triangulation has 106 triangles and the FSP just one polygon. All solutions have 108 vertices. So the number of parts involved, although reasonable in the partition case, is very large with the triangulation solution. Besides, many triangles are very thin, almost degenerate, like the ones just bellow the two holes at southwest. This may be a cause of troubles in the render of sweeps.
 
A run time comparison is even more strikingly against triangulation. Although the implementation of the ear-cut method is much simpler than the implementation of the polyHolePartition, the triangulation method is much more inefficient and spent a lot more time than the partition method when the number of vertices grows.

To tell you the truth, I don't like the solution of the partition method (and even less the triangilation). I would prefer far more the FSP generated by polyHoles. The only reason I developed the implementation of the partition method is that FSP faces are not acceptable by polyhedrons in render, although it is acceptable by polygon() and its linear_extrude(). So, my hope is that some day OpenSCAD could deal with polyhedron faces with the same generality it deals in polygon(). Then, polyHolePartition and triangulation of faces will be history.

The irony I mentioned in the end of my last message is that anything we do a partition of a polygon with holes in simple polygons to turn it palatable to CGAL, the system will discard it and make its own triangulation of the face. 


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

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Hmm, I would expect your example to have a key hole representation similar to
this image:
<http://forum.openscad.org/file/t887/FSP.png>
So no additional vertices are introduced. When the earcut travels now along
the "outline" of the FSP, it will have to ignore the vertices of an edge
when it analyzes a triangle containing its fake counterpart - or (just a
thought) it might relax a ">=" condition into a ">=" condition (or vice
versa) and thus allow for simple polygons with shared vertices.





--
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: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo

 Parkinbot wrote
Hmm, I would expect your example to have a key hole representation similar to
this image:
<http://forum.openscad.org/file/t887/FSP.png>
So no additional vertices are introduced. 

Sorry, I have not made myself clear. The additional vertices where introduced to the polygons *before* calling any process in order to evaluate the effect of the number of vertices. You may think that all polygons are circle. My functions do not add any vertices to the input polygons.

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

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo wrote
> Sorry, I have not made myself clear. The additional vertices where
> introduced to the polygons *before* calling any process in order to
> evaluate the effect of the number of vertices.

Ok, but this relativates the following statement:


Ronaldo wrote
> Besides, many triangles are very thin, almost degenerate, like the ones
> just bellow the two holes at southwest. This may be a cause of troubles in
> the render of sweeps.

and isn't that outcome a general problem of earcut?


Ronaldo wrote
> which is now uploaded in my github repository in its last version.

I'll download and test it in the next days.


Ronaldo wrote
> The irony I mentioned in the end of my last message is that anything we do
> a partition of a polygon with holes in simple polygons to turn it
> palatable to CGAL, the system will discard it and make its own
> triangulation of the face.

Yeah, the main irony is indeed that OpenSCAD already has the capability to
triangulate polygons with holes, but it cannot be accessed from user space.





--
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: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Parkinbot, wrote:
Yeah, the main irony is indeed that OpenSCAD already has the capability to
triangulate polygons with holes, but it cannot be accessed from user space.

I don't know if it is capable of dealing directly with polygons with holes because there is no way to specify it except by boolean differences or by FSP. And I don't care to access it directly. I would be glad that faces with holes for polyhedron could be accepted in FSP format the same way they are accepted by polygon() once we don't have any way to define polyhedron faces by boolean differences.

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

Re: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Ronaldo wrote:
 I would be glad that faces with holes for polyhedron could be accepted in FSP format the same way they are accepted by polygon() once we don't have any way to define polyhedron faces by boolean differences.

I was wrong! I have checked again and the primitive polyhedron is able to deal with FSP ! There was a bug in my previous tests. So, we don't need to do any partition, either by triangulation or polyHolePartition, to a FSP and the only additional function needed to sweep polygons with holes is polyHoles which is lighter than polyHolePartition() and much more efficient than ear-cut triangulation.

Here is my previous sweep example working now directly with the FSP generated by polyHoles.

use <polyHoles.scad>
use <sweep.scad> // this is my sweep version with sweep_polyhedron() and lazyUnion()

// the face with holes
outer = circ(r=50,n=24); // the outer border 
mH    = circ_distrib(25, 4, 3, revert(circ(12,24))); // holes borders

// build the FSP for the face with holes
FSP = polyHoles(outer, mH);
// express it in a pdata format
FSP_PDat = [ FSP, [[for(i=[0:len(FSP)-1]) i]] ];
// The sweep
// main path
path = spiral(200,80,270,24);
// the sweep path transforms
ptrans = construct_transform_path(path);
// sweep the outer face and the holes without caps
// sweep_polyhedron function generates the pdata of the sweep
souter = sweep_polyhedron(outer, ptrans, caps=false);
shole0 = sweep_polyhedron(mH[0], ptrans, caps=false);
shole1 = sweep_polyhedron(mH[1], ptrans, caps=false);
shole2 = sweep_polyhedron(mH[2], ptrans, caps=false);
// transform FSP_PDat to put the holed caps in proper place
begCap   = tranfPdata(ptrans[0], FSP_PDat) ;
endCap   = tranfPdata(ptrans[len(ptrans)-1], FSP_PDat, rev=true) ;
// join evething in one polyhedron
difference() {
  lazyUnion([souter, begCap, endCap, shole0, shole1, shole2]);
  translate([-160,50,0]) cube([60,60,150]);
}

// helper funtions
function spiral(r,h,ang,n) =
  [for(i=to_(n)) [r*cos(i*ang/n), r*sin(i*ang/n),i*h/n] ];
function circ(r,n,a=360) = [for(i=to_(n)) r*[cos(i*a/n), sin(i*a/n),0] ];
function T_(p,lp) = [for(pi=lp) pi+p ];
function circ_distrib(r,n,m,lp) =  [for(i=to_(m)) rotz(i*360/n, T_([0,r,0],lp) ) ];
function tranfPdata(transf, pdata, rev=false) = 
  ! rev ?
    [ transform(transf, pdata[0]), pdata[1] ] :
    [ transform(transf, pdata[0]), [for(f=pdata[1]) revert(f) ] ];
function rotz(a,lp) =
  let( T = [ [cos(a), sin(a), 0],[-sin(a),cos(a),0],[0,0,1] ] )
  lp[0][0]==undef? T*lp :[ for(pi=lp) T*pi ] ;
function revert(l) = !(len(l)>0)? [] : [ for(i=[len(l)-1:-1:0]) l[i] ];
function to_(n) = [0:n-1];
function transform(m, list) = 
  [for (p=list)let( q = m*concat(p,[1]) ) [q.x,q.y,q.z]/q[3]];




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

Re: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo wrote
> I was wrong! I have checked again and the primitive polyhedron is able to
> deal with FSP !

I tried to verify with OpenSCAD RC2, remembering that I had already checked
it when the thread started. I would say: polyhedron() does not interpret an
FSP. Or do you use another representation?

<http://forum.openscad.org/file/t887/FSP_polyhedron.png>

This is my code:  

o = circle(r=100, z=100);
i = circle(r=10, z=100);
fsp = FSP(o,i);

color("red") polygon(vec2(fsp));
polyhedron(fsp, [Rg(2*len(fsp))]);

// line(fsp, color = "green");

function circle(r=10, N=3, z=0) = [for(i=[0:N]) let(a=360/N*i) r*[cos(a),
sin(a),z/r]];
function vec2(P) = [for(p=P) [p[0], p[1]]];
function Rg(N) = [for(i=[0:N-1]) i];
function FSP(out, in) = [for(i=out) i, out[0], for(i=in) i, in[0], out[0]];
 



--
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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Sorry my fault, the inner polygon needs reversed orientation of course.

function FSP(out, in) = [for(i=out) i, out[0], for(i=[len(in)-1:-1:0])
in[i], in[0], out[0]];


Yeah, it works!!!! Great!
Sometimes it is a long journey to find out that everything was already
there.

<http://forum.openscad.org/file/t887/fsp_poly.png>



--
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: Polyhedron tube with irregular sides -- is it possible ?

Ronaldo
Don't be lazy and run a code with a full legal polyhedron!

A quarta, 27/02/2019, 16:14, Parkinbot <[hidden email]> escreveu:
Sorry my fault, the inner polygon needs reversed orientation of course.

function FSP(out, in) = [for(i=out) i, out[0], for(i=[len(in)-1:-1:0])
in[i], in[0], out[0]];


Yeah, it works!!!! Great!
Sometimes it is a long journey to find out that everything was already
there.

<http://forum.openscad.org/file/t887/fsp_poly.png>



--
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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Ronaldo wrote
> Don't be lazy and run a code with a full legal polyhedron!

You are right, better always do a full test. The following code is well with
F5/F12, but doesn't render properly with F6, when a cube is unioned.  

o = circle(r=100, z=0);
i = circle(r=10, z=0);
o1 = circle(r=100, z=100);
i1 = circle(r=10, z=100);

P = concat(o, i, o1, i1);

F = [0, 3, 5, 4, 3, 0, 1, 2, 0];  // FSP lower
F1 = [6,8,7,6,9,10,11, 9,6];      // FSP upper
A = [[1,0,6], [1, 6, 7], [0, 2, 8], [0, 8, 6], [2, 1, 8], [1, 7, 8]]; //
inner
B = [[3,4,10], [3,10,9],[4, 11, 10], [4,5,11], [5, 3, 9], [5,9,11]]; //
outer

polyhedron(P, concat([F1, F], A, B));

cube(1);

function circle(r=10, N=3, z=0) = [for(i=[0:N-1]) let(a=360/N*i) r*[cos(a),
sin(a),z/r]];




--
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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
Of course, one can omit the union test, do F6 and export a proper STL. After
import Boolean operations will work.

import("FSP.stl");
cube(1);

So it is CGAL that is playing unfair. Haven't we had this result already
near thread start?

@Hans: It might be not a big thing to feed CGAL with a fully tesselated
version of a polyhedron.







--
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: Polyhedron tube with irregular sides -- is it possible ?

Parkinbot
This post was updated on .
In reply to this post by Ronaldo
It's generally not lazyness but lack of time. I found time today to read the
paper more properly (a bit bony in its formalizm). After that I implemented
a FSP function, doing the same what your polyHoles does. Sorry to reinvent
the wheel, but it is so hard for me to read foreign code (you may call me a
code autist).

My code
1. finds the points B_i with minimal x-value in each inner polygon and puts
them into a list A.
2. selects the polygon n with minimal x-value from the list A, uses the
point B_n as bridge and excludes polygon n from the list A.
3. finds the nearest point with smaller x value in the outer polygon with
respect to the bridge
4. composes a new outer polygon using the bridge
5. does recursion until list A is empty.

Note that I don't check if polygons are simple. Here is the code and a full
blown use case with four inner polygons:

<http://forum.openscad.org/file/t887/fsp_FSP.png

// full example of FSP

o = circle(r=100, N=4);
i0 = T([-41, 25, 0], circle(r=20, N=3));
i1 = T([-40, -15, 0], circle(r=20, N=3));
i2 = T([45, -10, 0], circle(r=20, N=3));
i3 = T([0, 0, 0], circle(r=20, N=3));


X = FSP(o, [i0, i1, i2, i3]);

polygon(X);
line(X);


// outer: polygon, inner: list of polygons
function FSP(outer, inner, minXlist=undef) =
let(minXlist  = minXlist?minXlist:MinXList(inner)) // all bridge point
x-values and indices
let(ibestP    = minX(minXlist)) // get index of best polygon (i.e. with
lowest x-value)
let(bestinner = inner[minXlist[ibestP][2]]) // polygon to be bridged
let(minXlist_ = excludeElem(minXlist, ibestP)) // exclude best polygon from
bridge point list
let(validx = minXlist[ibestP]) // x-val and its index in best polygon
let(ibest = validx[1]) // index of bridge point in polygon
let(ibestinner = validx[2]) // index of polygon in inner list
let(bridge = inner[ibestinner][ibest]) // bridge point in polygon to be
bridged
let(obest = Nearest(outer, bridge)) // index of nearest point with <=x value
in outer polygon
let(N=len(bestinner))
let(fsp = [for(i=[0:obest]) outer[i],  // outer polygon with bridge to inner
           for(i=[ibest+N:-1:ibest]) bestinner[i%N],
           for(i=[obest:len(outer)]) outer[i%len(outer)]])
let(ret = minXlist_==[]?fsp:FSP(fsp, inner, minXlist_)) // recursion until
minXlist empty
ret;

// P is polygon list. Returns list of minX-values, their indices and polygon
index
function MinXList(P) = [for(p=[0:len(P)-1]) let(m = minX(P[p])) [P[p][m][0],
m, p]];
 
// index of element with smallest value in first component (x value)
function minX(P) = let(N=len(P))
[for(i=1, min=0; i<N+1; min=P[i][0]<P[min][0]?i:min, i=i+1) if(i==N)
min][0];

// exclude element with idx from list
function excludeElem(list, idx) = [for(i=[0:len(list)-1]) if(i!=idx)
list[i]];  

// get index of nearest point smaller x value in P wrt p
function Nearest(P, p) = let(N=len(P))
[for(i=1, min=0, val=0, val_=0; i<N+1;
    min=P[i][0]<=p[0] && norm(P[i]-p)<norm(P[min]-p)?i:min, i=i+1)
 if(i==N) min][0];


// translate polygon P
function T(x, P) = [for(p=P) p+x];  

// circle polygon
function circle(r=10,N=3)=[for(i=[0:N-1]) let(a=360/N*i) r*[cos(a),sin(a)]];
 
module line(P, r=1, color="red")
color(color)for(p=[0:len(P)-1])
  hull()
  {
    translate(P[p]) sphere(r);
    translate(P[(p+1)%len(P)]) sphere(r);
  }




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

_______________________________________________
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
123456