polyhedron() cannot do "faces with holes" currently as far as i know.

However there is a work-around. It is called the Keyhole Polygon...

Basically you take any polygon with a single hole... and pretend you
slice a knife down from the outside of the polygon, straight down, until
you cut into the hole. What you end up with is a single polygon without
any holes. Here is a picture

https://sozvyezdami.files.wordpress.com/2013/04/11.png?w=640

The caveat that the new edges you create by cutting will be coincident
with each other.... and the 'points' or 'nodes' of those new edges will
also be coincident, which can be a problem for some polygon processing
algorithms. However it appears to work on your basic example in
OpenSCAD. Here is your code rewritten to have two 'keyhole' polygons on
top and bottom.

pts =  [[0, 0, 0], [6, 0, 0], [6, 5, 0], [0, 5, 0], [2, 1, 0], [5, 2,
0],
[3, 4, 0], [0, 0, 3], [6, 0, 3], [6, 5, 3], [0, 5, 3], [2, 1, 3], [5, 2,
3], [3, 4, 3]];

faces1= [[0, 7, 8, 1], [1, 8, 9, 2], [2, 9, 10, 3], [3, 10, 7, 0],
[4, 5,12, 11], [5, 6, 13, 12], [6, 4, 11, 13],
[0, 1, 2, 3, 4, 6, 5, 4, 3],
[10, 9, 8, 7, 11, 12, 13, 11, 7]];
polyhedron( points = pts, faces = faces1  );

Also i had to re-order some of the vertices, as viewable in
'View/ThrownTogether' mode within OpenSCAD to make sure there were no
naughty purples. Hope this helps!

-don bright
hmbright@fastmail.fm

Hi Don, interesting approach. I seem to read similar one when reading
Computer Geometry or something a while back, but can't recall what it's for.

This approach seems to simplify the problem significantly. The
re-arrangement of points is not a big issue.

On the other hand, for my application, it might bring up other problems.
What I show in this thread is an extremely simplified example. The actual
tube in my lib could be a complicated one with random curving, etc. To make
a holed surface on the end of a long tube with this approach, the entire
tube will have to be sliced apart.

I also intend to use a holed surface as the merging face when cylinder of
different sides (in polyhedron) linked together. That is, to merge two
polyhedria. It will then be a budding, but not hole-punching/cutting,
process.

Anyway, thx for the idea. I believe it'd turn out useful in the future
development of my lib.

$  Runsun Pan, PhD

$ -- libs: doctest , faces ( git ), offliner ( git );

tips: hash( 1 , 2 ), sweep , var

$ -- Linux Mint 17.1 Rebecca x64  + OpenSCAD 2015.03.15/2015.04.01.nightly

--
View this message in context: http://forum.openscad.org/Polyhedron-tube-with-irregular-sides-is-it-possible-tp13813p13839.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

Regarding "faces with hole", following up the "keyhole polygon" solution
described by dob bright 3 yrs ago (which is also presented as an "
alternative face description
https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/The_OpenSCAD_Language#Alternate_Face_Descriptions
" in the official document ).I found that it could even be used to make a
polyhedron cube with multiple holes, like this:
pts = [[0, 0, 0], [0, 4, 0], [3, 5, 0], [2, 0, 0], [0, 0, 2], [0, 4, 2], [3,
5, 2], [2, 0, 2], [1, 0.5, 0], [0.4, 1.2, 0], [0.5, 2.1, 0], [2, 1.5, 0],
[1, 0.5, 2], [0.4, 1.2, 2], [0.5, 2.1, 2], [2, 1.5, 2], [1.5, 2.5, 0], [0.5,
3.5, 0], [2, 3.5, 0], [1.5, 2.5, 2], [0.5, 3.5, 2], [2, 3.5, 2]];faces =
[[4, 5, 6, 7, 4, 15, 14, 13, 12, 15, 4, 21, 20, 19, 21], [3, 2, 1, 0, 3, 8,
9, 10, 11, 8, 3, 16, 17, 18, 16], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6],
[3, 0, 4, 7], [9, 8, 12, 13], [10, 9, 13, 14], [11, 10, 14, 15], [8, 11, 15,
12], [17, 16, 19, 20], [18, 17, 20, 21], [16, 18, 21,
19]];polyhedron(pts,faces);
http://forum.openscad.org/file/t602/20181209_runsun_multi_hole_surface_1.png
In this case, the top face uses pts[4] as the starting point to cut into the
two holes:
[ 4, 5, 6, 7, 4, 15, 14, 13, 12, 15, 4, 21, 20, 19, 21]
as shown in this figure:
http://forum.openscad.org/file/t602/20181209_runsun_multi_hole_surface_2.png
What surprises me is that the 2 cut lines, 4~15 and 4~21,  go across the
entire holes.Is this normal?

It seems that this approach works in more holes, too:
pts = [[0, 0, 0], [0, 4, 0], [3, 5, 0], [2, 0, 0], [0, 0, 1], [0, 4, 1], [3,
5, 1], [2, 0, 1], [1, 0.5, 0], [0.4, 1.2, 0], [2, 1.5, 0], [1, 0.5, 1],
[0.4, 1.2, 1], [2, 1.5, 1], [0.5, 1.8, 0], [0.5, 2.1, 0], [1.8, 2.2, 0],
[1.5, 2, 0], [0.5, 1.8, 1], [0.5, 2.1, 1], [1.8, 2.2, 1], [1.5, 2, 1], [1,
2.75, 0], [0.5, 3.5, 0], [2, 3.5, 0], [1, 2.75, 1], [0.5, 3.5, 1], [2, 3.5,
1]];faces = [[4, 5, 6, 7, 4, 13, 12, 11, 13, 4, 21, 20, 19, 18, 21, 4, 27,
26, 25, 27], [3, 2, 1, 0, 3, 8, 9, 10, 8, 3, 14, 15, 16, 17, 14, 3, 22, 23,
24, 22], [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 4, 7], [9, 8, 11,
12], [10, 9, 12, 13], [8, 10, 13, 11], [15, 14, 18, 19], [16, 15, 19, 20],
[17, 16, 20, 21], [14, 17, 21, 18], [23, 22, 25, 26], [24, 23, 26, 27], [22,
24, 27, 25]];polyhedron(pts,faces);
http://forum.openscad.org/file/t602/20181209_runsun_multi_hole_surface_3.png
The top face:
[ 4, 5, 6, 7, 4, 13, 12, 11, 13, 4, 21, 20, 19, 18, 21, 4, 27, 26, 25, 27]
I'd like to know what you experts think about this.

$  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets

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

Very interesting stuff. Thanks for digging out this hack!
I immediately wanted this for sweep();

A sweep with a "close" attribute doing a single hole without difference() is
already nothing new - you sweep up and down.

sweep([circle(10, 0), circle(10, 20), circle(7, 20), circle(7, 0)], close =
true);
function circle(r=10, z = 0, N=10) = [for(i=[0:N-1]) [rcos(360/Ni),
rsin(360/Ni), z]];

I guess this approach will allow to implement a sweep() allowing for as many
holes as one likes.
I'll have to add a new interface parameter to my sweep() that lets one
supply a list of polygons describing the holes. The first and last face need
the hack, the rest is more or less straight forward.

Being able to sweep objects with multiple holes can speed up rendering of a
lot of stuff. I'm looking forward to have it.

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

Oh, how stupid I didn't check this little detail :-( . My first approach was
to use a polygon with the same point sequence, but that didn't work, because
my sweep() currently also puts vertical walls along the kerfs. So if CGAL
would cooperate, one could easily implement sweep() to omit those walls.

http://forum.openscad.org/file/t887/sweepwithholes.png

use <Naca_sweep.scad>
a = circle(30, 0, 10, -1);
b = circle(6, 0, 100, 1);

q = prepsweep([a, each forN_(b, 17)]);
sweep([q, Tz_(10, q)]);

function prepsweep(P) = [each P[0], each for(p=[1:len(P)-1]) each [P[p],
[P[p][0]], [P[0][len(P[0])-1]]]];
function forN_(P, r=0, N=6) = [for(i=[0:N-1]) T_(rsin(360/Ni),
rcos(360/Ni), 0, P)];
function circle(r=10, z = 0, N=10, dir=1) = [for(i=[0:N-1])
[rcos(dir360/Ni), rsin(dir360/Ni), z]];

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

A multi-hole sweep can be also implemented straight forward and does not need
this hack. It has to provide its own triangulation of the first and last
faces with holes and just can't rely on CGAL to do it. CGAL gets slow
anyway, when it starts with "trying alternative construction". The rest is
just building the walls like a vectorized sweep.

The new call will be something like:

sweep(outerpolygon_sequence=a, listofholes_sequence=b)

As soon as I find time, I'm gonna try it.

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

You could just use clockwise-counterclockwise to identify holes.

I did write a triangulation thing for bending text, though there's probably
a better way.

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

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

Thx for the check, nophead. Wondering how OpenSCAD allows it to render
correctly when it's stand-alone.

$  Runsun Pan, PhD $ libs: scadx , doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), editor of choice: CudaText  ( OpenSCAD lexer ); $ Tips ; $ Snippets

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

A triangulation like earcut with holes will be cumbersome to implement in
OpenSCAD. However a fast and viable solution for implementing the multi-hole
sweep is to use a vectorized lazy union sweep for the holes and difference
the result from the sweep of the outer polygon. For export one will have to
use a Boolean operation to do a CGAL check anyway.

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

Since the following code is accepted by CGAL

pts =  [[0, 0], [6, 0], [6, 5], [0, 5], [0, 0], [2, 1], [5, 2], [3, 4], [2,
1]];
linear_extrude(2)
polygon(pts);
cube(1);

and obviously uses triangulation

http://forum.openscad.org/file/t887/hole.png

it shouldn't be too difficult to provide a built-in triangulate2D() function
that uses clipper and returns a [verts, triags] list.

vertsfaceslist = triangulate2D(pts);  // builtin call using clipper
returning a [verts, triags] list
// ... use vertsfaceslist

the prototype could be:

function triangulate2D(polygon, z=undef) = ...

If provided z would add the given value as z coordinate to the verts (vec3
conversion) for intended polyhedron usage. Doesn't this sound like a nice
feature request?

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

Sorry nophead,

I meant that I can see that F5 tessellates a polygon with holes for use with
linear_extrude and we could use the underlying functionality to provide a
function that tesselates a 2D polygon given as list.

Btw, I see a F5 tesselation but not a F6 tesselation for

sphere(10);

Maybe OpenSCAD just doesn't display it?

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

Ronaldo had noticed it some time ago that CGAL changes tesselation on its own
will.

I created a cube by means of sweep(). So I am sure that it is tesselated in
triags. See how it is displayed by F6 with a unit cube unioned.
http://forum.openscad.org/file/t887/sweep.png

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

Clearly, CGAL is only called when a Boolean operation is present. Thus the
polyset to nef_polyhreda conversion is not necessary for primitives like a
polyhedron and can't be displayed.
When CGAL is called, it seems to try to reduce faces.

Nevertheless there is a tesselation of polygon with holes for F5 and this
one could be exposed to the user.

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

If there is a tesselation, a sweep with more than one hole can be
implemented. Wasn't this at least part the aim?

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

see what happens to an almost planar face created by an rotate_extrude.
http://forum.openscad.org/file/t887/rot.png

rotate_extrude(angle = 160)
{
translate([10, 0])
difference()
{
square(10, center = true);
square(5, center = true);
}
}
cube(1);

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

And another interesting observation:

The iron law to do a sweep() is: Avoid (self) intersection of faces at any
cost. This doesn't seem to apply for intersecting bending faces. While F12
announces a failure, CGAL seems to happily digest it:

use <Naca_sweep.scad>
sweep([circle(), Tz_(5, circle(phi = 180))]);
function circle(r = 10, N=100, z=3, phi=0) =
[for(i=[0:N-1])  [rsin(360/Ni), rcos(360/Ni), zcos(360/Ni*2+phi)]];
cube(1);

http://forum.openscad.org/file/t887/sweep.png

Will this open the path for a representation that lets us ignore (self)
intersections?

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

I can export it to STL and import it again without any problems.

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

it is even getting wierder and wierder:

http://forum.openscad.org/file/t887/sweep.png

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

Ronaldo

you are right, changing the representation is a typical interface task and
can be easily done within sweep() and transparent to the user.
Collect the first and last faces of the outer manifold and the holes, find
the right polyHoles-polygon to represent it and then use earcut. The rest is
a vectorized sweep.
I haven't had time to play with your algorithm more extensively as I am
short of time being on travel until Sunday. Can you post the current version
of your earcut()? Don't find mine anymore.

I would propose the following interface to keep the "affine" state as long
as possible - and allow for the lazy union of multihole sweeps:

module sweepMH(manifolds)
{
prepdata = sweepMH(manifolds);
polyhedron(prepdata[0], prepdata[1]);
}

function sweepMH(manifolds) =
let(firstface = earcut(polyHole(manifolds)))
let(lastface = earcut(polyHole(manifolds, last=true))
...

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

Parkinbot,

Find attached my last version of the polygon triangulation. I have reviewed
it converting recursions to iterations with C-like for in order to escape
the cycles early as possible. This version of the ear method is adapted to
polygons with two-way bridges. I have also a simple polygon check but it
rejects polygons with bridges. To accept polygon with bridges in that check
requires a whole new set of cumbersome tests. I don't like my
implementation of the check that resort to quick sort to make it somewhat
more efficient but if you want to try it, let me know. Another function
that you may consider, that is included in the same file of the simple
polygon test, is the plane fitting and projection to "flatten" almost
planar 3D polygons converting it in a 2D polygon before the triangulation
is called.

Both polygon triangulation and polygon with holes bridging methods fail if
they receive a non valid input. Without a proper validity check their use
is a blind fly.

It is possible to manipulate the initial runsun model in such way the
polyhedron is acceptable by CGAL and faces with hole do not need to be
triangulated. If enough well placed bridges are added (the number of holes
plus one) a polygon with holes is split in two polygons meeting at the
bridges. The following example, based on the runsun model, illustrates the
principle.

pts = [[0, 0, 0], [0, 4, 0], [3, 5, 0], [2, 0, 0],
[0, 0, 2], [0, 4, 2], [3, 5, 2], [2, 0, 2],
[1, 0.5, 0], [0.4, 1.2, 0], [0.5, 2.1, 0], [2, 1.5, 0],
[1, 0.5, 2], [0.4, 1.2, 2], [0.5, 2.1, 2], [2, 1.5, 2],
[1.5, 2.5, 0], [0.5, 3.5, 0], [2, 3.5, 0],
[1.5, 2.5, 2], [0.5, 3.5, 2], [2, 3.5, 2]];

faces = [[7, 4, 5, 6, 21, 20, 19, 14, 13, 12],  // top blue
[7, 12, 15, 14, 19, 21, 6],            // top red
[3, 2, 18, 16, 10, 11],                // bottom red
[2, 1, 0, 3, 11, 8, 9, 10, 16, 17, 18], // bottom blue
[0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6],
[3, 0, 4, 7], [9, 8, 12, 13], [10, 9, 13, 14],
[11, 10, 14, 15], [8, 11, 15, 12], [17, 16, 19, 20],
[18, 17, 20, 21], [16, 18, 21, 19]];

The following image of the polyhedron(pts, faces) enhances the top and
bottom partition:

[image: polyWithHoles.PNG]

Intentionally the top and bottom partitions are differents. Note that each
of the faces with holes has 3 bridges that are common to the two polygons
of the partition.

I guess the method I coded to find the bridges is O(m) where m is the
number of holes which is lot better than the triangulation methods. The
original method finds m bridges for m holes in the polygon. It may be
changed to find an additional bridge that split the face in two. I am
working on this now.

The image bellow shows the render of difference between the polyhedron and
a cube.

[image: polyRendered.PNG]

Correction: my guess of the order of the bridging method was wrong; I meant
O(n.m) for m holes and n total number of vertices.

Ronaldo

first, thanks for the earcut. It works well.

I am also thrilled by your solution to decompose a face with holes into two
(or more?) faces without holes. This is definitely a good approach for
implementing a multihole sweep. Does your algorithm find such a
decomposition for an unlimited number of holes?

As I understand it, the proposed function sweepMH() will now be something
like:

function sweepMH(manifolds) =
let(firstfaces = decompose(polyHole(manifolds)))
let(lastfaces = decompose(polyHole(manifolds, last=true))
...

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

Parkinbot,

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. I call those
edges as (two-way) bridges. As CGAL doesn't like polyhedron faces with the
kind of polygons polyHoles produces, my proposal is to write an algorithm
based on the Eberly's one to partition a simple polygon with holes in
(really) simple polygons without holes.

In my last few messages, I have made a set of very naive conjectures about
this problem and its solving algorithm: 1) it is possible to partition the
original polygon with holes in exactly two parts, 2) this partition is done
by m+1 bridges and 3) the order of the solving method would be O(m.n) where
m is the number of holes and n is the total number of vertices. Those
conjectures  are in fact true for convex polygons with convex holes.

For convex holes but non-convex polygons, the number of necessary bridges
may be 2.m and the partition may have m+1 parts. For non-convex holes,
things become very wild! I don't have a guess for the number of parts in
the partition but the number of bridges may increase to something like 2^m
and the complexity grows to O( (2^m).n). Still, my expectancy is that this
approach would be better than triangulation.

I am still working on the method I have in mind to partition a polygon with
many holes in simple polygons without holes. To have a flavor of what would
result in a non-convex case consider the following image:

[image: Poly2holes.PNG]

The red bridges have been obtained by a direct application of
polyHoles(outer,mH). The yellow bridges result from the application of
polyHoles(-outer, -mH). Four bridges partition the original polygon in 3
parts. However, it is possible to partition it in 2 parts with just 3
bridges.

Parkinbot,

The ear-cut triangulation method I have attached before is good only for
the kind of polygons polyHoles generates. It may lead to wrong results
(like degenerated triangles) when an additional vertex is added to some
bridge. So I think it is risky to use it in any other cases. To have a
proper ear-cut triangulation method that works for proper simple polygons
the function isCCW should have the following definition:

function isCCW(a, b, c) = CCW(a,b,c) >= 0 ;

Ronaldo,
I intuitively unterstand the separation algorithm as follows:

Be P the point set of the outer polygon and I = {P1, P2 ...} the points sets
of the holes.

1. find first bridge between P and I: calculate all point distances between
   P and I and select the hole P_ containing the point closest to O to build
   the brigde. Remove P_ from I and get I_
2. find bridge from hole P_ to closest hole in I_: exclude the ingoing
   bridge point from P_, set P_ as P and I_ as I.
3. if I is not empty go to step 1.

selecting always the shortest distance to build a brige, guarantees that no
other polygon can be cut. Thus we have all bridges exept the last.

The problem: I don't see, why we should be able to find a bridge to the
outer polygon again and I doubt that such a bridge will always exist.

See this example:

P = [[0,0],  [10,0], [10,10], [0,10]];
Q1 = [[2,7.8], [1,7.8], [1,1],  [9,1], [9,9], [1,9], [1,8], [8,8], [8,2],
[2,2], ];
Q2 = [[4,3],  [3,4], [3,3]];

linear_extrude(.1, convexity = 9)
difference()
{
polygon(P);
polygon(Q1);
polygon(Q2);
}

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

Parkinbot,

polyHoles doesn't try to find a bridge between each hole and the polygon
boundary. Some bridges may connect two holes.
It operates as following:

a) find the hole having the rightmost vertex among all hole vertices;
b) project this vertex to the right to a point in the polygon border;
c) find a vertex of the polygon "near" the projection point whose
connection to the hole vertex of a) is a bridge;
d) redefine the polygon using that bridge and the hole of a) ;
e) remove the hole of a) from the list of holes;
f) recur with the redefined polygon and the updated list of holes.

So, in your example, there would be a bridge from the squared hole to the
polygon border and another one between the two holes.

In the algorithm schema above, item c) is a bit more complex than described.

David Eberly's explanation of the algorithm is very clear and easy to
follow.

Ronaldo,

this is exactly what I meant and what I tried to express:
Go from the outer polygon to nearest hole, then from this hole to the
nearest unbridged hole and so on until you reach the last unbridged hole.
To get a full separation into two facets, you have to add a final bridge
from last hole to the outer polygon. And this is not always possible.

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

We agree. A bipartition with m+1 bridges is assured when the main polygon
and the holes are convex. But, for very intricate geometry of m holes, the
number of parts and number of bridges seem to grow exponentially with m.

In the picture bellow, the main polygon border is white. There are 3 holes,
filled by the colors green, red and blue. One possible set of bridges to
subdivide the polygon in simple polygons are represented in yellow.

[image: spiraledHoles.PNG]

The polygon partition has 6 parts. It is possible to add a fourth spiraled
hole squeezed between all previous holes that will require to double the
number of bridges and will produce the double of parts in the partition.
And so on...