1//////////////////////////////////////////////////////////////////////
2// LibFile: paths.scad
3// Polylines, polygons and paths.
4// To use, add the following lines to the beginning of your file:
5// ```
6// include <BOSL/constants.scad>
7// use <BOSL/paths.scad>
8// ```
9//////////////////////////////////////////////////////////////////////
10
11/*
12BSD 2-Clause License
13
14Copyright (c) 2017, Revar Desmera
15All rights reserved.
16
17Redistribution and use in source and binary forms, with or without
18modification, are permitted provided that the following conditions are met:
19
20* Redistributions of source code must retain the above copyright notice, this
21 list of conditions and the following disclaimer.
22
23* Redistributions in binary form must reproduce the above copyright notice,
24 this list of conditions and the following disclaimer in the documentation
25 and/or other materials provided with the distribution.
26
27THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
28AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
30DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
31FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
33SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
34CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
35OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37*/
38
39
40include <constants.scad>
41use <transforms.scad>
42use <math.scad>
43use <quaternions.scad>
44use <triangulation.scad>
45
46
47// Section: Functions
48
49
50// Function: simplify2d_path()
51// Description:
52// Takes a 2D polyline and removes unnecessary collinear points.
53// Usage:
54// simplify2d_path(path, [eps])
55// Arguments:
56// path = A list of 2D path points.
57// eps = Largest angle delta between segments to count as colinear. Default: 1e-6
58function simplify2d_path(path, eps=1e-6) = simplify_path(path, eps=eps);
59
60
61// Function: simplify3d_path()
62// Description:
63// Takes a 3D polyline and removes unnecessary collinear points.
64// Usage:
65// simplify3d_path(path, [eps])
66// Arguments:
67// path = A list of 3D path points.
68// eps = Largest angle delta between segments to count as colinear. Default: 1e-6
69function simplify3d_path(path, eps=1e-6) = simplify_path(path, eps=eps);
70
71
72// Function: path_length()
73// Usage:
74// path3d_length(path)
75// Description:
76// Returns the length of the path.
77// Arguments:
78// path = The list of points of the path to measure.
79// Example:
80// path = [[0,0], [5,35], [60,-25], [80,0]];
81// echo(path_length(path));
82function path_length(path) =
83 len(path)<2? 0 :
84 sum([for (i = [0:len(path)-2]) norm(path[i+1]-path[i])]);
85
86
87// Function: path2d_regular_ngon()
88// Description:
89// Returns a 2D open counter-clockwise path of the vertices of a regular polygon of `n` sides.
90// Usage:
91// path2d_regular_ngon(n, r|d, [cp], [scale]);
92// Arguments:
93// n = Number of polygon sides.
94// r = Radius of regular polygon.
95// d = Radius of regular polygon.
96// cp = Centerpoint of regular polygon. Default: `[0,0]`
97// scale = [X,Y] scaling factors for each axis. Default: `[1,1]`
98// Example(2D):
99// trace_polyline(path2d_regular_ngon(n=12, r=50), N=1, showpts=true);
100function path2d_regular_ngon(n=6, r=undef, d=undef, cp=[0,0], scale=[1,1]) =
101 let(
102 rr=get_radius(r=r, d=d, dflt=100)
103 ) [
104 for (i=[0:n-1])
105 rr * [cos(i*360/n)*scale.x, sin(i*360/n)*scale.y] + cp
106 ];
107
108
109// Function: path3d_spiral()
110// Description:
111// Returns a 3D spiral path.
112// Usage:
113// path3d_spiral(turns, h, n, r|d, [cp], [scale]);
114// Arguments:
115// h = Height of spiral.
116// turns = Number of turns in spiral.
117// n = Number of spiral sides.
118// r = Radius of spiral.
119// d = Radius of spiral.
120// cp = Centerpoint of spiral. Default: `[0,0]`
121// scale = [X,Y] scaling factors for each axis. Default: `[1,1]`
122// Example(3D):
123// trace_polyline(path3d_spiral(turns=2.5, h=100, n=24, r=50), N=1, showpts=true);
124function path3d_spiral(turns=3, h=100, n=12, r=undef, d=undef, cp=[0,0], scale=[1,1]) = let(
125 rr=get_radius(r=r, d=d, dflt=100),
126 cnt=floor(turns*n),
127 dz=h/cnt
128 ) [
129 for (i=[0:cnt]) [
130 rr * cos(i*360/n) * scale.x + cp.x,
131 rr * sin(i*360/n) * scale.y + cp.y,
132 i*dz
133 ]
134 ];
135
136
137// Function: points_along_path3d()
138// Usage:
139// points_along_path3d(polyline, path);
140// Description:
141// Calculates the vertices needed to create a `polyhedron()` of the
142// extrusion of `polyline` along `path`. The closed 2D path shold be
143// centered on the XY plane. The 2D path is extruded perpendicularly
144// along the 3D path. Produces a list of 3D vertices. Vertex count
145// is `len(polyline)*len(path)`. Gives all the reoriented vertices
146// for `polyline` at the first point in `path`, then for the second,
147// and so on.
148// Arguments:
149// polyline = A closed list of 2D path points.
150// path = A list of 3D path points.
151function points_along_path3d(
152 polyline, // The 2D polyline to drag along the 3D path.
153 path, // The 3D polyline path to follow.
154 q=Q_Ident(), // Used in recursion
155 n=0 // Used in recursion
156) = let(
157 end = len(path)-1,
158 v1 = (n == 0)? [0, 0, 1] : normalize(path[n]-path[n-1]),
159 v2 = (n == end)? normalize(path[n]-path[n-1]) : normalize(path[n+1]-path[n]),
160 crs = cross(v1, v2),
161 axis = norm(crs) <= 0.001? [0, 0, 1] : crs,
162 ang = vector_angle(v1, v2),
163 hang = ang * (n==0? 1.0 : 0.5),
164 hrot = Quat(axis, hang),
165 arot = Quat(axis, ang),
166 roth = Q_Mul(hrot, q),
167 rotm = Q_Mul(arot, q)
168) concat(
169 [for (i = [0:len(polyline)-1]) Q_Rot_Vector(point3d(polyline[i]),roth) + path[n]],
170 (n == end)? [] : points_along_path3d(polyline, path, rotm, n+1)
171);
172
173
174
175// Section: 2D Modules
176
177
178// Module: modulated_circle()
179// Description:
180// Creates a 2D polygon circle, modulated by one or more superimposed sine waves.
181// Arguments:
182// r = radius of the base circle.
183// sines = array of [amplitude, frequency] pairs, where the frequency is the number of times the cycle repeats around the circle.
184// Example(2D):
185// modulated_circle(r=40, sines=[[3, 11], [1, 31]], $fn=6);
186module modulated_circle(r=40, sines=[10])
187{
188 freqs = len(sines)>0? [for (i=sines) i[1]] : [5];
189 points = [
190 for (a = [0 : (360/segs(r)/max(freqs)) : 360])
191 let(nr=r+sum_of_sines(a,sines)) [nr*cos(a), nr*sin(a)]
192 ];
193 polygon(points);
194}
195
196
197// Section: 3D Modules
198
199
200// Module: extrude_from_to()
201// Description:
202// Extrudes a 2D shape between the points pt1 and pt2. Takes as children a set of 2D shapes to extrude.
203// Arguments:
204// pt1 = starting point of extrusion.
205// pt2 = ending point of extrusion.
206// convexity = max number of times a line could intersect a wall of the 2D shape being extruded.
207// twist = number of degrees to twist the 2D shape over the entire extrusion length.
208// scale = scale multiplier for end of extrusion compared the start.
209// slices = Number of slices along the extrusion to break the extrusion into. Useful for refining `twist` extrusions.
210// Example(FlatSpin):
211// extrude_from_to([0,0,0], [10,20,30], convexity=4, twist=360, scale=3.0, slices=40) {
212// xspread(3) circle(3, $fn=32);
213// }
214module extrude_from_to(pt1, pt2, convexity=undef, twist=undef, scale=undef, slices=undef) {
215 rtp = xyz_to_spherical(pt2-pt1);
216 translate(pt1) {
217 rotate([0, rtp[2], rtp[1]]) {
218 linear_extrude(height=rtp[0], convexity=convexity, center=false, slices=slices, twist=twist, scale=scale) {
219 children();
220 }
221 }
222 }
223}
224
225
226
227// Module: extrude_2d_hollow()
228// Description:
229// Similar to linear_extrude(), except the result is a hollow shell.
230// Arguments:
231// wall = thickness of shell wall.
232// height = height of extrusion.
233// twist = degrees of twist, from bottom to top.
234// slices = how many slices to use when making extrusion.
235// Example:
236// extrude_2d_hollow(wall=2, height=100, twist=90, slices=50)
237// circle(r=40, $fn=6);
238module extrude_2d_hollow(wall=2, height=50, twist=90, slices=60, center=undef, orient=ORIENT_Z, align=V_UP)
239{
240 orient_and_align([0,0,height], orient, align, center) {
241 linear_extrude(height=height, twist=twist, slices=slices, center=true) {
242 difference() {
243 children();
244 offset(r=-wall) {
245 children();
246 }
247 }
248 }
249 }
250}
251
252
253// Module: extrude_2dpath_along_spiral()
254// Description:
255// Takes a closed 2D polyline path, centered on the XY plane, and
256// extrudes it along a 3D spiral path of a given radius, height and twist.
257// Arguments:
258// polyline = Array of points of a polyline path, to be extruded.
259// h = height of the spiral to extrude along.
260// r = radius of the spiral to extrude along.
261// twist = number of degrees of rotation to spiral up along height.
262// Example:
263// poly = [[-10,0], [-3,-5], [3,-5], [10,0], [0,-30]];
264// extrude_2dpath_along_spiral(poly, h=200, r=50, twist=1080, $fn=36);
265module extrude_2dpath_along_spiral(polyline, h, r, twist=360, center=undef, orient=ORIENT_Z, align=V_CENTER) {
266 pline_count = len(polyline);
267 steps = ceil(segs(r)*(twist/360));
268
269 poly_points = [
270 for (
271 p = [0:steps]
272 ) let (
273 a = twist * (p/steps),
274 dx = r*cos(a),
275 dy = r*sin(a),
276 dz = h * (p/steps),
277 pts = matrix4_apply(
278 polyline, [
279 matrix4_xrot(90),
280 matrix4_zrot(a),
281 matrix4_translate([dx, dy, dz])
282 ]
283 )
284 ) for (pt = pts) pt
285 ];
286
287 poly_faces = concat(
288 [[for (b = [0:pline_count-1]) b]],
289 [
290 for (
291 p = [0:steps-1],
292 b = [0:pline_count-1],
293 i = [0:1]
294 ) let (
295 b2 = (b == pline_count-1)? 0 : b+1,
296 p0 = p * pline_count + b,
297 p1 = p * pline_count + b2,
298 p2 = (p+1) * pline_count + b2,
299 p3 = (p+1) * pline_count + b,
300 pt = (i==0)? [p0, p2, p1] : [p0, p3, p2]
301 ) pt
302 ],
303 [[for (b = [pline_count-1:-1:0]) b+(steps)*pline_count]]
304 );
305
306 tri_faces = triangulate_faces(poly_points, poly_faces);
307 orient_and_align([r,r,h], orient, align, center) {
308 polyhedron(points=poly_points, faces=tri_faces, convexity=10);
309 }
310}
311
312
313// Module: extrude_2dpath_along_3dpath()
314// Description:
315// Takes a closed 2D path `polyline`, centered on the XY plane, and extrudes it perpendicularly along a 3D path `path`, forming a solid.
316// Arguments:
317// polyline = Array of points of a polyline path, to be extruded.
318// path = Array of points of a polyline path, to extrude along.
319// ang = Angle in degrees to rotate 2D polyline before extrusion.
320// convexity = max number of surfaces any single ray could pass through.
321// Example(FlatSpin):
322// shape = [[0,-10], [5,-3], [5,3], [0,10], [30,0]];
323// path = concat(
324// [for (a=[30:30:180]) [50*cos(a)+50, 50*sin(a), 20*sin(a)]],
325// [for (a=[330:-30:180]) [50*cos(a)-50, 50*sin(a), 20*sin(a)]]
326// );
327// extrude_2dpath_along_3dpath(shape, path, ang=140);
328module extrude_2dpath_along_3dpath(polyline, path, ang=0, convexity=10) {
329 pline_count = len(polyline);
330 path_count = len(path);
331
332 polyline = rotate_points2d(path2d(polyline), ang);
333 poly_points = points_along_path3d(polyline, path);
334
335 poly_faces = concat(
336 [[for (b = [0:pline_count-1]) b]],
337 [
338 for (
339 p = [0:path_count-2],
340 b = [0:pline_count-1],
341 i = [0:1]
342 ) let (
343 b2 = (b == pline_count-1)? 0 : b+1,
344 p0 = p * pline_count + b,
345 p1 = p * pline_count + b2,
346 p2 = (p+1) * pline_count + b2,
347 p3 = (p+1) * pline_count + b,
348 pt = (i==0)? [p0, p2, p1] : [p0, p3, p2]
349 ) pt
350 ],
351 [[for (b = [pline_count-1:-1:0]) b+(path_count-1)*pline_count]]
352 );
353
354 tri_faces = triangulate_faces(poly_points, poly_faces);
355 polyhedron(points=poly_points, faces=tri_faces, convexity=convexity);
356}
357
358
359
360// Module: extrude_2d_shapes_along_3dpath()
361// Description:
362// Extrudes 2D children along a 3D polyline path. This may be slow.
363// Arguments:
364// path = array of points for the bezier path to extrude along.
365// convexity = maximum number of walls a ran can pass through.
366// clipsize = increase if artifacts are left. Default: 1000
367// Example(FlatSpin):
368// path = [ [0, 0, 0], [33, 33, 33], [66, 33, 40], [100, 0, 0], [150,0,0] ];
369// extrude_2d_shapes_along_3dpath(path) circle(r=10, $fn=6);
370module extrude_2d_shapes_along_3dpath(path, convexity=10, clipsize=100) {
371 function polyquats(path, q=Q_Ident(), v=[0,0,1], i=0) = let(
372 v2 = path[i+1] - path[i],
373 ang = vector_angle(v,v2),
374 axis = ang>0.001? normalize(cross(v,v2)) : [0,0,1],
375 newq = Q_Mul(Quat(axis, ang), q),
376 dist = norm(v2)
377 ) i < (len(path)-2)?
378 concat([[dist, newq, ang]], polyquats(path, newq, v2, i+1)) :
379 [[dist, newq, ang]];
380
381 epsilon = 0.0001; // Make segments ever so slightly too long so they overlap.
382 ptcount = len(path);
383 pquats = polyquats(path);
384 for (i = [0 : ptcount-2]) {
385 pt1 = path[i];
386 pt2 = path[i+1];
387 dist = pquats[i][0];
388 q = pquats[i][1];
389 difference() {
390 translate(pt1) {
391 Qrot(q) {
392 down(clipsize/2/2) {
393 linear_extrude(height=dist+clipsize/2, convexity=convexity) {
394 children();
395 }
396 }
397 }
398 }
399 translate(pt1) {
400 hq = (i > 0)? Q_Slerp(q, pquats[i-1][1], 0.5) : q;
401 Qrot(hq) down(clipsize/2+epsilon) cube(clipsize, center=true);
402 }
403 translate(pt2) {
404 hq = (i < ptcount-2)? Q_Slerp(q, pquats[i+1][1], 0.5) : q;
405 Qrot(hq) up(clipsize/2+epsilon) cube(clipsize, center=true);
406 }
407 }
408 }
409}
410
411
412// Module: trace_polyline()
413// Description:
414// Renders lines between each point of a polyline path.
415// Can also optionally show the individual vertex points.
416// Arguments:
417// pline = The array of points in the polyline.
418// showpts = If true, draw vertices and control points.
419// N = Mark the first and every Nth vertex after in a different color and shape.
420// size = Diameter of the lines drawn.
421// color = Color to draw the lines (but not vertices) in.
422// Example(FlatSpin):
423// polyline = [for (a=[0:30:210]) 10*[cos(a), sin(a), sin(a)]];
424// trace_polyline(polyline, showpts=true, size=0.5, color="lightgreen");
425module trace_polyline(pline, N=1, showpts=false, size=1, color="yellow") {
426 if (showpts) {
427 for (i = [0:len(pline)-1]) {
428 translate(pline[i]) {
429 if (i%N == 0) {
430 color("blue") sphere(d=size*2.5, $fn=8);
431 } else {
432 color("red") {
433 cylinder(d=size/2, h=size*3, center=true, $fn=8);
434 xrot(90) cylinder(d=size/2, h=size*3, center=true, $fn=8);
435 yrot(90) cylinder(d=size/2, h=size*3, center=true, $fn=8);
436 }
437 }
438 }
439 }
440 }
441 for (i = [0:len(pline)-2]) {
442 if (N!=3 || (i%N) != 1) {
443 color(color) extrude_from_to(pline[i], pline[i+1]) circle(d=size/2);
444 }
445 }
446}
447
448
449// Module: debug_polygon()
450// Description: A drop-in replacement for `polygon()` that renders and labels the path points.
451// Arguments:
452// points = The array of 2D polygon vertices.
453// paths = The path connections between the vertices.
454// convexity = The max number of walls a ray can pass through the given polygon paths.
455// Example(2D):
456// debug_polygon(
457// points=concat(
458// path2d_regular_ngon(r=10, n=8),
459// path2d_regular_ngon(r=8, n=8)
460// ),
461// paths=[
462// [for (i=[0:7]) i],
463// [for (i=[15:-1:8]) i]
464// ]
465// );
466module debug_polygon(points, paths=undef, convexity=2, size=1)
467{
468 pths = (!is_def(paths))? [for (i=[0:len(points)-1]) i] : is_scalar(paths[0])? [paths] : paths;
469 echo(points=points);
470 echo(paths=paths);
471 linear_extrude(height=0.01, convexity=convexity, center=true) {
472 polygon(points=points, paths=paths, convexity=convexity);
473 }
474 for (i = [0:len(points)-1]) {
475 color("red") {
476 up(0.2) {
477 translate(points[i]) {
478 linear_extrude(height=0.1, convexity=10, center=true) {
479 text(text=str(i), size=size, halign="center", valign="center");
480 }
481 }
482 }
483 }
484 }
485 for (j = [0:len(paths)-1]) {
486 path = paths[j];
487 translate(points[path[0]]) {
488 color("cyan") up(0.1) cylinder(d=size*1.5, h=0.01, center=false, $fn=12);
489 }
490 translate(points[path[len(path)-1]]) {
491 color("pink") up(0.11) cylinder(d=size*1.5, h=0.01, center=false, $fn=4);
492 }
493 for (i = [0:len(path)-1]) {
494 midpt = (points[path[i]] + points[path[(i+1)%len(path)]])/2;
495 color("blue") {
496 up(0.2) {
497 translate(midpt) {
498 linear_extrude(height=0.1, convexity=10, center=true) {
499 text(text=str(chr(65+j),i), size=size/2, halign="center", valign="center");
500 }
501 }
502 }
503 }
504 }
505 }
506}
507
508
509
510// vim: noexpandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap