Re: [OpenSCAD] Vertex arrays?
What a great explanation! I wish content like this was embedded as
comments in the source code!!
Jon
On 1/29/2016 5:06 AM, David Eccles (gringer) wrote:
OpenSCAD, like Prolog, is a declarative language. In Prolog, rules return
true or false, whereas in OpenSCAD, modules return a 3D object. It takes a
bit of mind twisting to get into the swing of declarative programming, but
I've learnt to stop worrying and love the recursion.
As an example, my path extrusion script generates a polyhedron formed by
translating and rotating a polygon along a path in three-dimensional space.
Here's a double helix, created as a polyhedron with about 180 defined
points. Modifying the number of slices of 't' for the point and path
function can result in this quite quickly exceeding 1000 points without any
change in code:
use <path_extrude.scad>;
pi=3.14159;
for(shift = [0, 360/15]){
myPoints = [ for(t = [0:72:359]) [cos(t),sin(t)] ];
myPath = [ for(t = [0:10:359]) [
(10+1.212pisin(5t))cos(t+shift),
(10+1.212pisin(5t))sin(t+shift),
1.212picos(5*t)
] ];
path_extrude(points=myPoints, path=myPath, merge=true);
}
I've included an image with an 18-point circle and 180-point path for
demonstration.
http://forum.openscad.org/file/n15969/pathextrude_double_helix_3240.png
The backend of the path_extrude function is 4kb of code, which is fairly
lightweight when compared to things that it can replace. It uses list
comprehensions to simplify the code, but I can achieve the same thing by
defining a function to generate recursive vectors (see my EllerSCAD maze
generator for an example of that). I use a recursive function to first
generate the point array:
module path_extrude(points, path, pos=0, merge=false, trimEnds=false,
extruded=[]){
if((len(points) > 0) && (len(path) > 0)){
if(len(extruded) >= (len(path))){
// extrusion is finished, so construct the object
//echo(extruded);
makeExtrudedPoly(extruded, merge=merge, trimEnds=trimEnds);
} else {
// generate points from rotating polygon
if(merge || (pos < (len(path) - 1))){
if((pos == 0) && (!merge)) {
newPts = myRotate(rToS(path[1] - path[0]),
points);
path_extrude(points=points, path=path, pos=pos+1,
merge=merge, trimEnds=trimEnds,
extruded=concat(extruded, [add(newPts,path[pos])]));
} else {
newPts = myRotate(rToS(path[(pos+1) % len(path)]
- path[(pos+len(path)-1) % len(path)]),
points);
path_extrude(points=points, path=path, pos=pos+1,
merge=merge, trimEnds=trimEnds,
extruded=concat(extruded, [add(newPts,path[pos])]));
}
} else {
newPts = myRotate(rToS(path[pos] - path[pos-1]),
points);
path_extrude(points=points, path=path, pos=pos+1,
merge=merge, trimEnds=trimEnds,
extruded=concat(extruded, [add(newPts,path[pos])]));
}
}
}
}
And then another recursive function to generate the polyhedron definition
using the point array. Because each polygon unit has the same number of
points at each position in the 3D path, I can define the joining
quadrilaterals (not necessarily planar) without too much effort:
module makeExtrudedPoly(ex, merge=false, trimEnds=false){
ps = flatten(ex);
pp = len(ex[1]); // points in one polygon
tp = len(ex[1]) * len(ex); // total number of points
if(!merge && !trimEnds){
polyhedron(points=ps, faces=concat(
[[for (i = [pp-1 : -1 : 0]) i]],
[[for (i = [tp-pp : 1 : tp-1]) i]],
[for (pt=[0:(len(ex)-2)])
for(i = [0:pp-1]) phFace(pp,tp,i,ptpp)],
[])
);
} else if(trimEnds) {
polyhedron(points=ps, faces=concat(
[[for (i = [pp2-1 : -1 : pp]) i]],
[[for (i = [tp-pp2 : 1 : tp-pp-1]) i]],
[for (pt=[1:(len(ex)-3)])
for(i = [0:pp-1]) phFace(pp,tp,i,ptpp)]));
} else {
polyhedron(points=ps, faces=
[for (pt=[0:(len(ex)-1)])
for(i = [0:pp-1]) phFace(pp,tp,i,pt*pp)]);
}
}
Hopefully you can see that the majority of the code is spent dealing with
corner cases (i.e. what to do at the ends of the path), rather than the
bread and butter of the algorithm. The remainder of the code is made up from
helper functions to make the code a bit more succinct. OpenSCAD can do a lot
of this stuff natively, but only on actual objects (as far as I can tell)
and not on numerical matrices:
// rotation matrix implementation
// OpenSCAD seems to do this slightly different from Wikipedia
// c.f. https://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations
function rot2Mat(rotVec, axis) =
(len(rotVec) == 2) ?
rot2Mat([rotVec[0], rotVec[1], 0], axis) :
(axis == "x") ?
[[1, 0, 0],
[0, cos(rotVec[0]), sin(rotVec[0])],
[0, sin(rotVec[0]), -cos(rotVec[0])]] :
(axis == "y") ?
[[ cos(rotVec[1]), 0, sin(rotVec[1])],
[ 0, 1, 0],
[-sin(rotVec[1]), 0, cos(rotVec[1])]] :
(axis == "z") ?
[[ cos(rotVec[2]), sin(rotVec[2]), 0],
[-sin(rotVec[2]), cos(rotVec[2]), 0],
[0, 0, 1]] : undef;
// convert point to 3D by setting Z to zero (if not present)
function c3D(tPoints) =
(len(tPoints[0]) < 3) ?
tPoints * [[1,0,0],[0,1,0]] :
tPoints;
// rotate [2D] points using a specificed XYZ rotation vector
function myRotate(rotation, points) =
c3D(points) * rot2Mat(rotation, "x")
* rot2Mat(rotation, "y")
* rot2Mat(rotation, "z");
// Determine spherical rotation for cartesian coordinates
function rToS(pt) =
[-acos((pt[2]) / norm(pt)),
0,
-atan2(pt[0],pt[1])];
// Generate a line between two points in 3D space [only used for debugging
this code]
module line3D(p1,p2){
translate((p1+p2)/2)
rotate(rToS(p1-p2))
cylinder(r=1, h=norm(p1-p2), center = true, $fn = 3);
}
// Flattens an array down one level (removing the enclosing array)
function flatten(pointArray, done=0, res=[]) =
(done == len(pointArray)) ?
res :
flatten(pointArray=pointArray, done=done+1,
res=concat(res,pointArray[done]));
// Creates a polyhedron face
function phFace(pp, tp, base, add=0) =
[base + add, (base+1) % pp + add,
(((base+1) % pp) + pp + add) % tp, (base + pp + add) % tp];
function add(vecArg, scArg, res=[]) =
(len(res) >= len(vecArg)) ?
res :
add(vecArg, scArg, res=concat(res,[vecArg[len(res)]+scArg]));
The code is a little slow, but I don't yet have any need to optimise it
further because it is sufficiently fast for the things I have been using it
for. See it in action here:
http://www.thingiverse.com/thing:186660
--
View this message in context: http://forum.openscad.org/Vertex-arrays-tp15876p15969.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
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2016.0.7357 / Virus Database: 4522/11507 - Release Date: 01/28/16