Simple polygon triangulation
My vote is in favor. OpenSCAD is a bit more than geometry and topology. In
animation for instance, to produce in an easy way good animated sequences we
need to make state machines and record events.
I know this is not the object of the language, but why not extend it to
facilitate and stimulate creativity. Most of users are not MScs or Phds
searching for the optimal way to produce great geometrical creations. Of
course this aspect is important as it is related with the main goal of the
language. However the popularity of the language in which users have a
fundamental role would be augmented if some new language tools could
facilitate their expression. As an example, some contributors offer great
libraries that most of us can't use because the most common of us don't
understand it and in it's majority, documentation is scarse. OpenSCAD is
becoming more popular and one of it's strengths is the easy way one can
express some creativity at its own level of knowledge.
jpmendes
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16892.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
You don't need state to produce animation sequences. I once designed an
animation system that had to synchronise across lots of adjacent machines
that were connected to their left and right neighbours. From that they
could decide where they were and in the row, how long the row was and the
most left one passed a time variable up stream. From that any arbitrary
animation sequence were run. You simply have to divide down the time
variable to work out what state you are in if your animation has states.
If you want to write in a procedural language why not use the Python
binding, or the C++ binding, or Angel script, etc.
On 1 April 2016 at 20:10, jpmendes jpmendes54@gmail.com wrote:
My vote is in favor. OpenSCAD is a bit more than geometry and topology. In
animation for instance, to produce in an easy way good animated sequences
we
need to make state machines and record events.
I know this is not the object of the language, but why not extend it to
facilitate and stimulate creativity. Most of users are not MScs or Phds
searching for the optimal way to produce great geometrical creations. Of
course this aspect is important as it is related with the main goal of the
language. However the popularity of the language in which users have a
fundamental role would be augmented if some new language tools could
facilitate their expression. As an example, some contributors offer great
libraries that most of us can't use because the most common of us don't
understand it and in it's majority, documentation is scarse. OpenSCAD is
becoming more popular and one of it's strengths is the easy way one can
express some creativity at its own level of knowledge.
jpmendes
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16892.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Although strictly not necessary it helps a lot. Specially if we want to keep
track of object mutual interference. Maybe a mathematician can describe a
path for objects interfering with each other and predict the time for the
occurrences, but it is much simpler to record those events. As this is an
off topic let's stop for now. Thanks for the suggestion I will think more
about it.
jpmendes
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16897.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I think I have a full functional implementation of a O(n^3) ear-cutting
method to triangulate 2D simple polygon. I addopted the data structure
Parkinbot suggested to output the triangles as lists of the indices in the
array of vertices. The code is relatively simple:
// ************* 2D triangulation of a polygon ********************
// triangulate the 2D polygon lp
function triangulate(lp) = triangs(build_data(lp));
function triangs(lsp) = // traiangulate structured 2D polygon
len(lsp) <= 3 ?
[ [ind(lsp[0]), ind(lsp[1]), ind(lsp[2])] ]:
let( ear = any_ear(lsp), l = len(lsp) )
ear== undef? [] : // case S is a non-simple polygon
concat( [ [ ind(lsp[(ear+l-1)%l]), ind(lsp[ear]), ind(lsp[(ear+1)%l])
] ],
triangs(exclude_vertex(ear, lsp)) );
// small data structure to preserve original indexing of points
function build_data(lp) = [ for(i=[0:len(lp)-1]) [ i, lp[i] ] ];
function ind(sp) = sp[0];
function vtx(sp) = sp[1];
function exclude_vertex(k,lsp) =
concat( k<=0? []: [for(i=[0 :k-1]) lsp[i] ] ,
k>=len(lsp)-1? []: [for(i=[k+1:len(lsp)-1]) lsp[i] ] );
// find the index of the best ear according to inner angle criterium
function any_ear(lsp) =
let( l = len(lsp) )
[ for(j=[0:l-1]) if( is_ear(j, lsp) ) j ] [0];
// false if vtx(lsp[k1]) not convex or
// any other point of lsp is inside the triangle
function is_ear(k1,lsp) =
let( l = len(lsp), k0 = (k1+l-1)%l, k2 = (k1+1)%l )
!is_left(vtx(lsp[k1]), vtx(lsp[k0]), vtx(lsp[k2])) // vtx(lsp[k1]) is
convex
&& void( [ for(i=[0:l-1]) // and other vertices are outside
if( (i!=k0) && (i!=k1) && (i!=k2) &&
is_left(vtx(lsp[k0]), vtx(lsp[k1]), vtx(lsp[i])) &&
is_left(vtx(lsp[k1]), vtx(lsp[k2]), vtx(lsp[i])) &&
is_left(vtx(lsp[k2]), vtx(lsp[k0]), vtx(lsp[i]))) 1 ]
) ;
// true if vtx(sp3) is at left or is colinear to the vector
vtx(sp2)-vtx(sp1)
function is_left(a, b, c) =
(b[0] - a[0])(c[1] - a[1]) - (b[1] - a[1])(c[0] - a[0]) <= 0 ;
function void(lst) = len(lst)==0 ;
For almost planar closed polygonals in the 3D space, I do a plane fitting to
the vertices, project them into the plane and define a local 2D coordinate
system before the triangulation. This process is entirely independent of the
triangulation above:
// ******* plane fitting and projection ***************
function project_poly(lp3D) =
let( leigen = least_square_transform_3(lp3D),
pm = leigen[0], // mean point
eigenv = leigen[1], // eigenvectors
projection = [ eigenv[0], eigenv[1] ], // projection transform
lproj2D = [ for(i=[0:len(lp3D)-1]) projection*(lp3D[i]-pm) ] )
is_CCW(lproj2D) ?
lproj2D*[ [-1,0],[0,1] ] :
lproj2D;
// check whether the orientation induced by projection is CCW
function is_CCW(lp) =
let( bd = bounds(lp),
im = index_min(bd) ) // the index of the smaller index in bd
( bd[im] <= bd[(im+1)%4] )
&& ( bd[(im+1)%4] <= bd[(im+2)%4] )
&& ( bd[(im+2)%4] <= bd[(im+3)%4] ) ;
// indices of extreme points of p
function bounds(lp) =
let( indminX = index_min( lp*[ 1, 0]), indmaxX = index_min( lp*[-1,
0]),
indminY = index_min( lp*[ 0, 1]), indmaxY = index_min( lp*[
0,-1]) )
[ indminX, indminY, indmaxX, indmaxY ]; // this order is essential
// the index of the smaller value in the list l
function index_min(l) = let( minv = min(l) )
[ for(i=[0:len(l)-1]) if ( l[i] == minv ) i ][0];
As you can see, the CCW orientation of the vertices is ensured by a well
chosen projection. The data fitting relies on the
least_square_transform_3(). That function returns the three pairs of
eigenvalue/eigenvector of the covariance matrix of the points. As those
functions may be used by other applications, I kept them in a file with
other linear algebra stuffs. This file may be retrived bellow:
linear_algebra.scad
http://forum.openscad.org/file/n16898/linear_algebra.scad
To improve the time complexity of the method for triangulation of the simple
polygon, we need to find an ear in constant time. There is solutions to that
but it requires more sophisticated data structure. I will not do it now, may
be later. Now I will return to the application that demanded the
triangulation.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16898.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo, if you are interested, this is my implementation of the subdivision
algorithm.
This time I combined cycle and split to avoid an extra copy.
I works as expected, but not on all generated polygons. I suspect, now is
not the generator, but the algorithm freaking out on rare occasions. Don't
have the time, to find out the reason, without a debugging facility. I
testet the predicates and functions and gave some test code for them.
Maybe four eyes see more than two ...
N = 19;
p = randpolyg(N); // too easy to be perfect
q = triag_div(p);
for (i=[0:len(q)-1]) color([i,i,i]/(N)) polygon(q[i]); translate([0,
0,-1]) polygon(p);
// testing of the subfunctions
echo(is_left([0,0], [1,1], [2,3])); // true
echo(is_left([0,0], [1,1], [3,1])); // false
echo(is_in([[0,0], [1,1], [4,3]], [2,2])); // false
echo(is_in([[0,0], [1,1], [4,3]], [1.1,1])); // true
echo(split([1,2,3,4])); // [[1, 2, 3], [3, 4, 1]]
echo(split([1,2,3,4], 1)); //+cycle [[2, 3, 4], [4, 1, 2]]
echo(split([1,2,3,4,5])); // [[1, 2, 3], [3, 4, 5, 1]]
echo(split([1,2,3,4,5, 6])); // [[1, 2, 3, 4], [4, 5, 6, 1]]
// generate a randomized CW polygon
function randpolyg(N=10) = [for (i=[0:360/N:359.9])
let (rnd = rands(5,10,2)) [rnd[0]*sin(i), rnd[1]*cos(i)]];
// the main algorithm
function triag_div(S, cycle=0) =
len(S)==3? [S]:
let(A = split(S, cycle))
is_division(A) ?
concat(
triag_div(A[0]),
triag_div(A[1]))
:triag_div(S, cycle+1);
// split a polygon in the middle after cycling
function split(S, cycle=0) = let (n=len(S), cut=floor(n/2))
[[for(i=[0:cut]) S[(i+cycle)%n]], [for(i=[cut:n]) S[(i+cycle)%n]]];
// true, if all points of first set outside of second set
// and all points of second set outside of first set
function is_division(A) =
let (res1 = [for(i=[1:len(A[0])-2]) if(is_in(A[1], A[0][i])) 1])
let (res2 = [for(i=[1:len(A[1])-2]) if(is_in(A[0], A[1][i])) 1])
res1==[] && res2==[];
// true if p is in A
function is_in(A, p) = let(n=len(A)) let(res =
[for(i=[0:n-1]) if(is_left(A[i], A[(i+1)%n], p)) 1])
res==[];
// true if c is left of a--->b
function is_left(a, b, c) =
(b[0] - a[0])(c[1] - a[1]) - (b[1] - a[1])(c[0] - a[0]) > 0;
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16900.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Thank you, Parkinbot. Your code looks nice. I will comment it tomorrow.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16909.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Parkinbot, please try your subdivision algorithm with this polygon
N = 19;
pre_seed = 5528; //-1; // if pre_seed <0 a random seed is generated
seed = pre_seed<0 ? floor(rands(0,10000,1)[0]): pre_seed;
echo(seed=seed);
// generate a randomized CW polygon
function randpolyg(N=10) = let( rnd = rands(5,10,2N+1,seed) )
[for (i=[0:360/N:359.9]) [rnd[2iN/360]sin(i), rnd[2iN/360+1]*cos(i)]];
p = randpolyg(N); // too easy to be perfect
2016-04-02 15:27 GMT-03:00 Ronaldo rcmpersiano@gmail.com:
Thank you, Parkinbot. Your code looks nice. I will comment it tomorrow.
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16909.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
This is not my area, but maybe you guys interested in tessellation can take
a look at "Wings 3D" sources. Wings 3D is written in Erlang also a
functional language, perhaps some algorithms maybe easily adapted to
OpenSCAD by some experienced developer. I downloaded the sources just for
curiosity and the code seems to be well structured. A specific module on
tessellation exists with some interesting comments. BTW Synwrite has a
lexter for Erlang.
jpmendes
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16917.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Meanwhile I know, what is problem. The code's logic is fine, but the
is_division() predicate is too weak. It can fail on certain non-convex
partitions. I think I'll have to give it new try.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16918.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I have noticed that. Besides, your main algoritm assumes that, for any
simple polygon, there is a diagonal from some p[i] to p[i+floor(n/2)] for
some i. This is not true in general.
2016-04-02 20:05 GMT-03:00 Parkinbot rudolf@parkinbot.com:
Meanwhile I know, what is problem. The code's logic is fine, but the
is_division() predicate is too weak. It can fail on certain non-convex
partitions. I think I'll have to give it new try.
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16918.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org