cacb wrote

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/

Ronaldo wrote

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/

On 2019-01-21 21:59, Ronaldo Persiano wrote:

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

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

On 2019-01-22 13:36, Parkinbot 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.

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

cacb wrote

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

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/

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.

[image: 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.

[image: 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.

[image: 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:

[image: SweepPolygon.PNG]

Sweeping this polygon along a spiral curve with proper code led to:

[image: 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.
[image: 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 rudolf@digitaldocument.de
escreveu:

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

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/

Parkinbot wrote:

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.

[image: 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.