1//////////////////////////////////////////////////////////////////////
2// LibFile: beziers.scad
3// Bezier curves and surfaces are way to represent smooth curves and smoothly curving
4// surfaces with a set of control points. The curve or surface is defined by
5// the control points, but usually only passes through the first and last control point (the endpoints).
6// This file provides some
7// aids to constructing the control points, and highly optimized functions for
8// computing the Bezier curves and surfaces given by the control points,
9// Includes:
10// include <BOSL2/std.scad>
11// include <BOSL2/beziers.scad>
12// FileGroup: Advanced Modeling
13// FileSummary: Bezier curves and surfaces.
14//////////////////////////////////////////////////////////////////////
15
16// Terminology:
17// Path = A series of points joined by straight line segements.
18// Bezier Curve = A polynomial curve defined by a list of control points. The curve starts at the first control point and ends at the last one. The other control points define the shape of the curve and they are often *NOT* on the curve
19// Control Point = A point that influences the shape of the Bezier curve.
20// Degree = The degree of the polynomial used to make the bezier curve. A bezier curve of degree N will have N+1 control points. Most beziers are cubic (degree 3). The higher the degree, the more the curve can wiggle.
21// Bezier Parameter = A parameter, usually `u` below, that ranges from 0 to 1 to trace out the bezier curve. When `u=0` you get the first control point and when `u=1` you get the last control point. Intermediate points are traced out *non-uniformly*.
22// Bezier Path = A list of bezier control points corresponding to a series of Bezier curves that connect together, end to end. Because they connect, the endpoints are shared between control points and are not repeated, so a degree 3 bezier path representing two bezier curves will have seven entries to represent two sets of four control points. **NOTE:** A "bezier path" is *NOT* a standard path
23// Bezier Patch = A two-dimensional arrangement of Bezier control points that generate a bounded curved Bezier surface. A Bezier patch is a (N+1) by (M+1) grid of control points, which defines surface with four edges (in the non-degenerate case).
24// Bezier Surface = A surface defined by a list of one or more bezier patches.
25// Spline Steps = The number of straight-line segments used to approximate a Bezier curve. The more spline steps, the better the approximation to the curve, but the slower it will be to generate. This plays a role analogous to `$fn` for circles. Usually defaults to 16.
26
27
28// Section: Bezier Curves
29
30// Function: bezier_points()
31// Synopsis: Computes one or more specified points along a bezier curve.
32// SynTags: Path
33// Topics: Bezier Curves
34// See Also: bezier_curve(), bezier_curvature(), bezier_tangent(), bezier_derivative(), bezier_points()
35// Usage:
36// pt = bezier_points(bezier, u);
37// ptlist = bezier_points(bezier, RANGE);
38// ptlist = bezier_points(bezier, LIST);
39// Description:
40// Computes points on a bezier curve with control points specified by `bezier` at parameter values
41// specified by `u`, which can be a scalar or a list. The value `u=0` gives the first endpoint; `u=1` gives the final endpoint,
42// and intermediate values of `u` fill in the curve in a non-uniform fashion. This function uses an optimized method which
43// is best when `u` is a long list and the bezier degree is 10 or less. The degree of the bezier
44// curve is `len(bezier)-1`.
45// Arguments:
46// bezier = The list of endpoints and control points for this bezier curve.
47// u = Parameter values for evaluating the curve, given as a single value, a list or a range.
48// Example(2D): Quadratic (Degree 2) Bezier.
49// bez = [[0,0], [30,30], [80,0]];
50// debug_bezier(bez, N=len(bez)-1);
51// translate(bezier_points(bez, 0.3)) color("red") sphere(1);
52// Example(2D): Cubic (Degree 3) Bezier
53// bez = [[0,0], [5,35], [60,-25], [80,0]];
54// debug_bezier(bez, N=len(bez)-1);
55// translate(bezier_points(bez, 0.4)) color("red") sphere(1);
56// Example(2D): Degree 4 Bezier.
57// bez = [[0,0], [5,15], [40,20], [60,-15], [80,0]];
58// debug_bezier(bez, N=len(bez)-1);
59// translate(bezier_points(bez, 0.8)) color("red") sphere(1);
60// Example(2D): Giving a List of `u`
61// bez = [[0,0], [5,35], [60,-25], [80,0]];
62// debug_bezier(bez, N=len(bez)-1);
63// pts = bezier_points(bez, [0, 0.2, 0.3, 0.7, 0.8, 1]);
64// rainbow(pts) move($item) sphere(1.5, $fn=12);
65// Example(2D): Giving a Range of `u`
66// bez = [[0,0], [5,35], [60,-25], [80,0]];
67// debug_bezier(bez, N=len(bez)-1);
68// pts = bezier_points(bez, [0:0.2:1]);
69// rainbow(pts) move($item) sphere(1.5, $fn=12);
70
71// Ugly but speed optimized code for computing bezier curves using the matrix representation
72// See https://pomax.github.io/bezierinfo/#matrix for explanation.
73//
74// All of the loop unrolling makes and the use of the matrix lookup table make a big difference
75// in the speed of execution. For orders 10 and below this code is 10-20 times faster than
76// the recursive code using the de Casteljau method depending on the bezier order and the
77// number of points evaluated in one call (more points is faster). For orders 11 and above without the
78// lookup table or hard coded powers list the code is about twice as fast as the recursive method.
79// Note that everything I tried to simplify or tidy this code made is slower, sometimes a lot slower.
80function bezier_points(curve, u) =
81 is_num(u) ? bezier_points(curve,[u])[0] :
82 let(
83 N = len(curve)-1,
84 M = _bezier_matrix(N)*curve
85 )
86 N==0 ? [for(uval=u)[1]*M] :
87 N==1 ? [for(uval=u)[1, uval]*M] :
88 N==2 ? [for(uval=u)[1, uval, uval^2]*M] :
89 N==3 ? [for(uval=u)[1, uval, uval^2, uval^3]*M] :
90 N==4 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4]*M] :
91 N==5 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5]*M] :
92 N==6 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5,uval^6]*M] :
93 N==7 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5,uval^6, uval^7]*M] :
94 N==8 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5,uval^6, uval^7, uval^8]*M] :
95 N==9 ? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5,uval^6, uval^7, uval^8, uval^9]*M] :
96 N==10? [for(uval=u)[1, uval, uval^2, uval^3, uval^4, uval^5,uval^6, uval^7, uval^8, uval^9, uval^10]*M] :
97 /* N>=11 */ [for(uval=u)[for (i=[0:1:N]) uval^i]*M];
98
99
100// Not public.
101function _signed_pascals_triangle(N,tri=[[-1]]) =
102 len(tri)==N+1 ? tri :
103 let(last=tri[len(tri)-1])
104 _signed_pascals_triangle(N,concat(tri,[[-1, for(i=[0:1:len(tri)-2]) (i%2==1?-1:1)*(abs(last[i])+abs(last[i+1])),len(last)%2==0? -1:1]]));
105
106
107// Not public.
108function _compute_bezier_matrix(N) =
109 let(tri = _signed_pascals_triangle(N))
110 [for(i=[0:N]) concat(tri[N][i]*tri[i], repeat(0,N-i))];
111
112
113// The bezier matrix, which is related to Pascal's triangle, enables nonrecursive computation
114// of bezier points. This method is much faster than the recursive de Casteljau method
115// in OpenScad, but we have to precompute the matrices to reap the full benefit.
116
117// Not public.
118_bezier_matrix_table = [
119 [[1]],
120 [[ 1, 0],
121 [-1, 1]],
122 [[1, 0, 0],
123 [-2, 2, 0],
124 [1, -2, 1]],
125 [[ 1, 0, 0, 0],
126 [-3, 3, 0, 0],
127 [ 3,-6, 3, 0],
128 [-1, 3,-3, 1]],
129 [[ 1, 0, 0, 0, 0],
130 [-4, 4, 0, 0, 0],
131 [ 6,-12, 6, 0, 0],
132 [-4, 12,-12, 4, 0],
133 [ 1, -4, 6,-4, 1]],
134 [[ 1, 0, 0, 0, 0, 0],
135 [ -5, 5, 0, 0, 0, 0],
136 [ 10,-20, 10, 0, 0, 0],
137 [-10, 30,-30, 10, 0, 0],
138 [ 5,-20, 30,-20, 5, 0],
139 [ -1, 5,-10, 10,-5, 1]],
140 [[ 1, 0, 0, 0, 0, 0, 0],
141 [ -6, 6, 0, 0, 0, 0, 0],
142 [ 15,-30, 15, 0, 0, 0, 0],
143 [-20, 60,-60, 20, 0, 0, 0],
144 [ 15,-60, 90,-60, 15, 0, 0],
145 [ -6, 30,-60, 60,-30, 6, 0],
146 [ 1, -6, 15,-20, 15,-6, 1]],
147 [[ 1, 0, 0, 0, 0, 0, 0, 0],
148 [ -7, 7, 0, 0, 0, 0, 0, 0],
149 [ 21, -42, 21, 0, 0, 0, 0, 0],
150 [-35, 105,-105, 35, 0, 0, 0, 0],
151 [ 35,-140, 210,-140, 35, 0, 0, 0],
152 [-21, 105,-210, 210,-105, 21, 0, 0],
153 [ 7, -42, 105,-140, 105,-42, 7, 0],
154 [ -1, 7, -21, 35, -35, 21,-7, 1]],
155 [[ 1, 0, 0, 0, 0, 0, 0, 0, 0],
156 [ -8, 8, 0, 0, 0, 0, 0, 0, 0],
157 [ 28, -56, 28, 0, 0, 0, 0, 0, 0],
158 [-56, 168,-168, 56, 0, 0, 0, 0, 0],
159 [ 70,-280, 420,-280, 70, 0, 0, 0, 0],
160 [-56, 280,-560, 560,-280, 56, 0, 0, 0],
161 [ 28,-168, 420,-560, 420,-168, 28, 0, 0],
162 [ -8, 56,-168, 280,-280, 168,-56, 8, 0],
163 [ 1, -8, 28, -56, 70, -56, 28,-8, 1]],
164 [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [-9, 9, 0, 0, 0, 0, 0, 0, 0, 0], [36, -72, 36, 0, 0, 0, 0, 0, 0, 0], [-84, 252, -252, 84, 0, 0, 0, 0, 0, 0],
165 [126, -504, 756, -504, 126, 0, 0, 0, 0, 0], [-126, 630, -1260, 1260, -630, 126, 0, 0, 0, 0], [84, -504, 1260, -1680, 1260, -504, 84, 0, 0, 0],
166 [-36, 252, -756, 1260, -1260, 756, -252, 36, 0, 0], [9, -72, 252, -504, 630, -504, 252, -72, 9, 0], [-1, 9, -36, 84, -126, 126, -84, 36, -9, 1]],
167 [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [-10, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0], [45, -90, 45, 0, 0, 0, 0, 0, 0, 0, 0], [-120, 360, -360, 120, 0, 0, 0, 0, 0, 0, 0],
168 [210, -840, 1260, -840, 210, 0, 0, 0, 0, 0, 0], [-252, 1260, -2520, 2520, -1260, 252, 0, 0, 0, 0, 0],
169 [210, -1260, 3150, -4200, 3150, -1260, 210, 0, 0, 0, 0], [-120, 840, -2520, 4200, -4200, 2520, -840, 120, 0, 0, 0],
170 [45, -360, 1260, -2520, 3150, -2520, 1260, -360, 45, 0, 0], [-10, 90, -360, 840, -1260, 1260, -840, 360, -90, 10, 0],
171 [1, -10, 45, -120, 210, -252, 210, -120, 45, -10, 1]]
172];
173
174
175// Not public.
176function _bezier_matrix(N) =
177 N>10 ? _compute_bezier_matrix(N) :
178 _bezier_matrix_table[N];
179
180
181// Function: bezier_curve()
182// Synopsis: Computes a specified number of points on a bezier curve.
183// SynTags: Path
184// Topics: Bezier Curves
185// See Also: bezier_curve(), bezier_curvature(), bezier_tangent(), bezier_derivative(), bezier_points()
186// Usage:
187// path = bezier_curve(bezier, [splinesteps], [endpoint]);
188// Description:
189// Takes a list of bezier control points and generates splinesteps segments (splinesteps+1 points)
190// along the bezier curve they define.
191// Points start at the first control point and are sampled uniformly along the bezier parameter.
192// The endpoints of the output will be *exactly* equal to the first and last bezier control points
193// when endpoint is true. If endpoint is false the sampling stops one step before the final point
194// of the bezier curve, but you still get the same number of (more tightly spaced) points.
195// The distance between the points will *not* be equidistant.
196// The degree of the bezier curve is one less than the number of points in `curve`.
197// Arguments:
198// bezier = The list of control points that define the Bezier curve.
199// splinesteps = The number of segments to create on the bezier curve. Default: 16
200// endpoint = if false then exclude the endpoint. Default: True
201// Example(2D): Quadratic (Degree 2) Bezier.
202// bez = [[0,0], [30,30], [80,0]];
203// move_copies(bezier_curve(bez, 8)) sphere(r=1.5, $fn=12);
204// debug_bezier(bez, N=len(bez)-1);
205// Example(2D): Cubic (Degree 3) Bezier
206// bez = [[0,0], [5,35], [60,-25], [80,0]];
207// move_copies(bezier_curve(bez, 8)) sphere(r=1.5, $fn=12);
208// debug_bezier(bez, N=len(bez)-1);
209// Example(2D): Degree 4 Bezier.
210// bez = [[0,0], [5,15], [40,20], [60,-15], [80,0]];
211// move_copies(bezier_curve(bez, 8)) sphere(r=1.5, $fn=12);
212// debug_bezier(bez, N=len(bez)-1);
213function bezier_curve(bezier,splinesteps=16,endpoint=true) =
214 bezier_points(bezier, lerpn(0,1,splinesteps+1,endpoint));
215
216
217// Function: bezier_derivative()
218// Synopsis: Evaluates the derivative of the bezier curve at the given point or points.
219// Topics: Bezier Curves
220// See Also: bezier_curvature(), bezier_tangent(), bezier_points()
221// Usage:
222// deriv = bezier_derivative(bezier, u, [order]);
223// derivs = bezier_derivative(bezier, LIST, [order]);
224// derivs = bezier_derivative(bezier, RANGE, [order]);
225// Description:
226// Evaluates the derivative of the bezier curve at the given parameter value or values, `u`. The `order` gives the order of the derivative.
227// The degree of the bezier curve is one less than the number of points in `bezier`.
228// Arguments:
229// bezier = The list of control points that define the Bezier curve.
230// u = Parameter values for evaluating the curve, given as a single value, a list or a range.
231// order = The order of the derivative to return. Default: 1 (for the first derivative)
232function bezier_derivative(bezier, u, order=1) =
233 assert(is_int(order) && order>=0)
234 order==0? bezier_points(bezier, u) : let(
235 N = len(bezier) - 1,
236 dpts = N * deltas(bezier)
237 ) order==1? bezier_points(dpts, u) :
238 bezier_derivative(dpts, u, order-1);
239
240
241
242// Function: bezier_tangent()
243// Synopsis: Calculates unit tangent vectors along the bezier curve at one or more given positions.
244// Topics: Bezier Curves
245// See Also: bezier_curvature(), bezier_derivative(), bezier_points()
246// Usage:
247// tanvec = bezier_tangent(bezier, u);
248// tanvecs = bezier_tangent(bezier, LIST);
249// tanvecs = bezier_tangent(bezier, RANGE);
250// Description:
251// Returns the unit tangent vector at the given parameter values on a bezier curve with control points `bezier`.
252// Arguments:
253// bezier = The list of control points that define the Bezier curve.
254// u = Parameter values for evaluating the curve, given as a single value, a list or a range.
255function bezier_tangent(bezier, u) =
256 let(
257 res = bezier_derivative(bezier, u)
258 ) is_vector(res)? unit(res) :
259 [for (v=res) unit(v)];
260
261
262
263// Function: bezier_curvature()
264// Synopsis: Returns the curvature at one or more given positions along a bezier curve.
265// Topics: Bezier Curves
266// See Also: bezier_tangent(), bezier_derivative(), bezier_points()
267// Usage:
268// crv = bezier_curvature(curve, u);
269// crvlist = bezier_curvature(curve, LIST);
270// crvlist = bezier_curvature(curve, RANGE);
271// Description:
272// Returns the curvature value for the given parameters `u` on the bezier curve with control points `bezier`.
273// The curvature is the inverse of the radius of the tangent circle at the given point.
274// Thus, the tighter the curve, the larger the curvature value. Curvature will be 0 for
275// a position with no curvature, since 1/0 is not a number.
276// Arguments:
277// bezier = The list of control points that define the Bezier curve.
278// u = Parameter values for evaluating the curve, given as a single value, a list or a range.
279function bezier_curvature(bezier, u) =
280 is_num(u) ? bezier_curvature(bezier,[u])[0] :
281 let(
282 d1 = bezier_derivative(bezier, u, 1),
283 d2 = bezier_derivative(bezier, u, 2)
284 ) [
285 for(i=idx(d1))
286 sqrt(
287 sqr(norm(d1[i])*norm(d2[i])) -
288 sqr(d1[i]*d2[i])
289 ) / pow(norm(d1[i]),3)
290 ];
291
292
293
294// Function: bezier_closest_point()
295// Synopsis: Finds the closest position on a bezier curve to a given point.
296// Topics: Bezier Curves
297// See Also: bezier_points()
298// Usage:
299// u = bezier_closest_point(bezier, pt, [max_err]);
300// Description:
301// Finds the closest part of the given bezier curve to point `pt`.
302// The degree of the curve, N, is one less than the number of points in `curve`.
303// Returns `u` for the closest position on the bezier curve to the given point `pt`.
304// Arguments:
305// bezier = The list of control points that define the Bezier curve.
306// pt = The point to find the closest curve point to.
307// max_err = The maximum allowed error when approximating the closest approach.
308// Example(2D):
309// pt = [40,15];
310// bez = [[0,0], [20,40], [60,-25], [80,0]];
311// u = bezier_closest_point(bez, pt);
312// debug_bezier(bez, N=len(bez)-1);
313// color("red") translate(pt) sphere(r=1);
314// color("blue") translate(bezier_points(bez,u)) sphere(r=1);
315function bezier_closest_point(bezier, pt, max_err=0.01, u=0, end_u=1) =
316 let(
317 steps = len(bezier)*3,
318 uvals = [u, for (i=[0:1:steps]) (end_u-u)*(i/steps)+u, end_u],
319 path = bezier_points(bezier,uvals),
320 minima_ranges = [
321 for (i = [1:1:len(uvals)-2]) let(
322 d1 = norm(path[i-1]-pt),
323 d2 = norm(path[i ]-pt),
324 d3 = norm(path[i+1]-pt)
325 ) if (d2<=d1 && d2<=d3) [uvals[i-1],uvals[i+1]]
326 ]
327 ) len(minima_ranges)>1? (
328 let(
329 min_us = [
330 for (minima = minima_ranges)
331 bezier_closest_point(bezier, pt, max_err=max_err, u=minima.x, end_u=minima.y)
332 ],
333 dists = [for (v=min_us) norm(bezier_points(bezier,v)-pt)],
334 min_i = min_index(dists)
335 ) min_us[min_i]
336 ) : let(
337 minima = minima_ranges[0],
338 pp = bezier_points(bezier, minima),
339 err = norm(pp[1]-pp[0])
340 ) err<max_err? mean(minima) :
341 bezier_closest_point(bezier, pt, max_err=max_err, u=minima[0], end_u=minima[1]);
342
343
344// Function: bezier_length()
345// Synopsis: Approximate the length of part of a bezier curve.
346// Topics: Bezier Curves
347// See Also: bezier_points()
348// Usage:
349// pathlen = bezier_length(bezier, [start_u], [end_u], [max_deflect]);
350// Description:
351// Approximates the length of the portion of the bezier curve between start_u and end_u.
352// Arguments:
353// bezier = The list of control points that define the Bezier curve.
354// start_u = The Bezier parameter to start measuring measuring from. Between 0 and 1.
355// end_u = The Bezier parameter to end measuring at. Between 0 and 1. Greater than start_u.
356// max_deflect = The largest amount of deflection from the true curve to allow for approximation.
357// Example:
358// bez = [[0,0], [5,35], [60,-25], [80,0]];
359// echo(bezier_length(bez));
360function bezier_length(bezier, start_u=0, end_u=1, max_deflect=0.01) =
361 let(
362 segs = len(bezier) * 2,
363 uvals = lerpn(start_u, end_u, segs+1),
364 path = bezier_points(bezier,uvals),
365 defl = max([
366 for (i=idx(path,e=-3)) let(
367 mp = (path[i] + path[i+2]) / 2
368 ) norm(path[i+1] - mp)
369 ]),
370 mid_u = lerp(start_u, end_u, 0.5)
371 )
372 defl <= max_deflect? path_length(path) :
373 sum([
374 for (i=[0:1:segs-1]) let(
375 su = lerp(start_u, end_u, i/segs),
376 eu = lerp(start_u, end_u, (i+1)/segs)
377 ) bezier_length(bezier, su, eu, max_deflect)
378 ]);
379
380
381
382// Function: bezier_line_intersection()
383// Synopsis: Calculates where a bezier curve intersects a line.
384// Topics: Bezier Curves, Geometry, Intersection
385// See Also: bezier_points(), bezier_length(), bezier_closest_point()
386// Usage:
387// u = bezier_line_intersection(bezier, line);
388// Description:
389// Finds the intersection points of the 2D Bezier curve with control points `bezier` and the given line, specified as a pair of points.
390// Returns the intersection as a list of `u` values for the Bezier.
391// Arguments:
392// bezier = The list of control points that define a 2D Bezier curve.
393// line = a list of two distinct 2d points defining a line
394function bezier_line_intersection(bezier, line) =
395 assert(is_path(bezier,2), "The input ´bezier´ must be a 2d bezier")
396 assert(_valid_line(line,2), "The input `line` is not a valid 2d line")
397 let(
398 a = _bezier_matrix(len(bezier)-1)*bezier, // bezier algebraic coeffs.
399 n = [-line[1].y+line[0].y, line[1].x-line[0].x], // line normal
400 q = [for(i=[len(a)-1:-1:1]) a[i]*n, (a[0]-line[0])*n] // bezier SDF to line
401 )
402 [for(u=real_roots(q)) if (u>=0 && u<=1) u];
403
404
405
406
407// Section: Bezier Path Functions
408// To contruct more complicated curves you can connect a sequence of Bezier curves end to end.
409// A Bezier path is a flattened list of control points that, along with the degree, represents such a sequence of bezier curves where all of the curves have the same degree.
410// A Bezier path looks like a regular path, since it is just a list of points, but it is not a regular path. Use {{bezpath_curve()}} to convert a Bezier path to a regular path.
411// We interpret a degree N Bezier path as groups of N+1 control points that
412// share endpoints, so they overlap by one point. So if you have an order 3 bezier path `[p0,p1,p2,p3,p4,p5,p6]` then the first
413// Bezier curve control point set is `[p0,p1,p2,p3]` and the second one is `[p3,p4,p5,p6]`. The endpoint, `p3`, is shared between the control point sets.
414// The Bezier degree, which must be known to interpret the Bezier path, defaults to 3.
415
416
417// Function: bezpath_points()
418// Synopsis: Computes one or more specified points along a bezier path.
419// SynTags: Path
420// Topics: Bezier Paths
421// See Also: bezier_points(), bezier_curve()
422// Usage:
423// pt = bezpath_points(bezpath, curveind, u, [N]);
424// ptlist = bezpath_points(bezpath, curveind, LIST, [N]);
425// path = bezpath_points(bezpath, curveind, RANGE, [N]);
426// Description:
427// Extracts from the Bezier path `bezpath` the control points for the Bezier curve whose index is `curveind` and
428// computes the point or points on the corresponding Bezier curve specified by `u`. If `curveind` is zero you
429// get the first curve. The number of curves is `(len(bezpath)-1)/N` so the maximum index is that number minus one.
430// Arguments:
431// bezpath = A Bezier path path to approximate.
432// curveind = Curve number along the path.
433// u = Parameter values for evaluating the curve, given as a single value, a list or a range.
434// N = The degree of the Bezier path curves. Default: 3
435function bezpath_points(bezpath, curveind, u, N=3) =
436 bezier_points(select(bezpath,curveind*N,(curveind+1)*N), u);
437
438
439// Function: bezpath_curve()
440// Synopsis: Converts bezier path into a path of points.
441// SynTags: Path
442// Topics: Bezier Paths
443// See Also: bezier_points(), bezier_curve(), bezpath_points()
444// Usage:
445// path = bezpath_curve(bezpath, [splinesteps], [N], [endpoint])
446// Description:
447// Computes a number of uniformly distributed points along a bezier path.
448// Arguments:
449// bezpath = A bezier path to approximate.
450// splinesteps = Number of straight lines to split each bezier curve into. default=16
451// N = The degree of the bezier curves. Cubic beziers have N=3. Default: 3
452// endpoint = If true, include the very last point of the bezier path. Default: true
453// Example(2D):
454// bez = [
455// [0,0], [-5,30],
456// [20,60], [50,50], [110,30],
457// [60,25], [70,0], [80,-25],
458// [80,-50], [50,-50]
459// ];
460// debug_bezier(bez, N=3, width=2);
461function bezpath_curve(bezpath, splinesteps=16, N=3, endpoint=true) =
462 assert(is_path(bezpath))
463 assert(is_int(N))
464 assert(is_int(splinesteps) && splinesteps>0)
465 assert(len(bezpath)%N == 1, str("A degree ",N," bezier path should have a multiple of ",N," points in it, plus 1."))
466 let(
467 segs = (len(bezpath)-1) / N,
468 step = 1 / splinesteps
469 ) [
470 for (seg = [0:1:segs-1])
471 each bezier_points(select(bezpath, seg*N, (seg+1)*N), [0:step:1-step/2]),
472 if (endpoint) last(bezpath)
473 ];
474
475
476// Function: bezpath_closest_point()
477// Synopsis: Finds the closest point on a bezier path to a given point.
478// Topics: Bezier Paths
479// See Also: bezpath_points(), bezpath_curve(), bezier_points(), bezier_curve(), bezier_closest_point()
480// Usage:
481// res = bezpath_closest_point(bezpath, pt, [N], [max_err]);
482// Description:
483// Finds an approximation to the closest part of the given bezier path to point `pt`.
484// Returns [segnum, u] for the closest position on the bezier path to the given point `pt`.
485// Arguments:
486// bezpath = A bezier path to approximate.
487// pt = The point to find the closest curve point to.
488// N = The degree of the bezier curves. Cubic beziers have N=3. Default: 3
489// max_err = The maximum allowed error when approximating the closest approach.
490// Example(2D):
491// pt = [100,0];
492// bez = [[0,0], [20,40], [60,-25], [80,0],
493// [100,25], [140,25], [160,0]];
494// pos = bezpath_closest_point(bez, pt);
495// xy = bezpath_points(bez,pos[0],pos[1]);
496// debug_bezier(bez, N=3);
497// color("red") translate(pt) sphere(r=1);
498// color("blue") translate(xy) sphere(r=1);
499function bezpath_closest_point(bezpath, pt, N=3, max_err=0.01, seg=0, min_seg=undef, min_u=undef, min_dist=undef) =
500 assert(is_vector(pt))
501 assert(is_int(N))
502 assert(is_num(max_err))
503 assert(len(bezpath)%N == 1, str("A degree ",N," bezier path shound have a multiple of ",N," points in it, plus 1."))
504 let(curve = select(bezpath,seg*N,(seg+1)*N))
505 (seg*N+1 >= len(bezpath))? (
506 let(curve = select(bezpath, min_seg*N, (min_seg+1)*N))
507 [min_seg, bezier_closest_point(curve, pt, max_err=max_err)]
508 ) : (
509 let(
510 curve = select(bezpath,seg*N,(seg+1)*N),
511 u = bezier_closest_point(curve, pt, max_err=0.05),
512 dist = norm(bezier_points(curve, u)-pt),
513 mseg = (min_dist==undef || dist<min_dist)? seg : min_seg,
514 mdist = (min_dist==undef || dist<min_dist)? dist : min_dist,
515 mu = (min_dist==undef || dist<min_dist)? u : min_u
516 )
517 bezpath_closest_point(bezpath, pt, N, max_err, seg+1, mseg, mu, mdist)
518 );
519
520
521
522// Function: bezpath_length()
523// Synopsis: Approximate the length of a bezier path.
524// Topics: Bezier Paths
525// See Also: bezier_points(), bezier_curve(), bezier_length()
526// Usage:
527// plen = bezpath_length(path, [N], [max_deflect]);
528// Description:
529// Approximates the length of the bezier path.
530// Arguments:
531// path = A bezier path to approximate.
532// N = The degree of the bezier curves. Cubic beziers have N=3. Default: 3
533// max_deflect = The largest amount of deflection from the true curve to allow for approximation.
534function bezpath_length(bezpath, N=3, max_deflect=0.001) =
535 assert(is_int(N))
536 assert(is_num(max_deflect))
537 assert(len(bezpath)%N == 1, str("A degree ",N," bezier path shound have a multiple of ",N," points in it, plus 1."))
538 sum([
539 for (seg=[0:1:(len(bezpath)-1)/N-1]) (
540 bezier_length(
541 select(bezpath, seg*N, (seg+1)*N),
542 max_deflect=max_deflect
543 )
544 )
545 ]);
546
547
548
549// Function: path_to_bezpath()
550// Synopsis: Generates a bezier path that passes through all points in a given linear path.
551// SynTags: Path
552// Topics: Bezier Paths, Rounding
553// See Also: path_tangents()
554// Usage:
555// bezpath = path_to_bezpath(path, [closed], [tangents], [uniform], [size=]|[relsize=]);
556// Description:
557// Given a 2d or 3d input path and optional list of tangent vectors, computes a cubic (degree 3) bezier
558// path that passes through every point on the input path and matches the tangent vectors. If you do
559// not supply the tangent it will be computed using `path_tangents()`. If the path is closed specify this
560// by setting `closed=true`. The size or relsize parameter determines how far the curve can deviate from
561// the input path. In the case where the curve has a single hump, the size specifies the exact distance
562// between the specified path and the bezier. If you give relsize then it is relative to the segment
563// length (e.g. 0.05 means 5% of the segment length). In 2d when the bezier curve makes an S-curve
564// the size parameter specifies the sum of the deviations of the two peaks of the curve. In 3-space
565// the bezier curve may have three extrema: two maxima and one minimum. In this case the size specifies
566// the sum of the maxima minus the minimum. If you do not supply the tangents then they are computed
567// using `path_tangents()` with `uniform=false` by default. Tangents computed on non-uniform data tend
568// to display overshoots. See `smooth_path()` for examples.
569// Arguments:
570// path = 2D or 3D point list or 1-region that the curve must pass through
571// closed = true if the curve is closed . Default: false
572// tangents = tangents constraining curve direction at each point
573// uniform = set to true to compute tangents with uniform=true. Default: false
574// ---
575// size = absolute size specification for the curve, a number or vector
576// relsize = relative size specification for the curve, a number or vector. Default: 0.1.
577function path_to_bezpath(path, closed, tangents, uniform=false, size, relsize) =
578 is_1region(path) ? path_to_bezpath(path[0], default(closed,true), tangents, uniform, size, relsize) :
579 let(closed=default(closed,false))
580 assert(is_bool(closed))
581 assert(is_bool(uniform))
582 assert(num_defined([size,relsize])<=1, "Can't define both size and relsize")
583 assert(is_path(path,[2,3]),"Input path is not a valid 2d or 3d path")
584 assert(is_undef(tangents) || is_path(tangents,[2,3]),"Tangents must be a 2d or 3d path")
585 assert(is_undef(tangents) || len(path)==len(tangents), "Input tangents must be the same length as the input path")
586 let(
587 curvesize = first_defined([size,relsize,0.1]),
588 relative = is_undef(size),
589 lastpt = len(path) - (closed?0:1)
590 )
591 assert(is_num(curvesize) || len(curvesize)==lastpt, str("Size or relsize must have length ",lastpt))
592 let(
593 sizevect = is_num(curvesize) ? repeat(curvesize, lastpt) : curvesize,
594 tangents = is_def(tangents) ? [for(t=tangents) let(n=norm(t)) assert(!approx(n,0),"Zero tangent vector") t/n] :
595 path_tangents(path, uniform=uniform, closed=closed)
596 )
597 assert(min(sizevect)>0, "Size and relsize must be greater than zero")
598 [
599 for(i=[0:1:lastpt-1])
600 let(
601 first = path[i],
602 second = select(path,i+1),
603 seglength = norm(second-first),
604 dummy = assert(seglength>0, str("Path segment has zero length from index ",i," to ",i+1)),
605 segdir = (second-first)/seglength,
606 tangent1 = tangents[i],
607 tangent2 = -select(tangents,i+1), // Need this to point backwards, in direction of the curve
608 parallel = abs(tangent1*segdir) + abs(tangent2*segdir), // Total component of tangents parallel to the segment
609 Lmax = seglength/parallel, // May be infinity
610 size = relative ? sizevect[i]*seglength : sizevect[i],
611 normal1 = tangent1-(tangent1*segdir)*segdir, // Components of the tangents orthogonal to the segment
612 normal2 = tangent2-(tangent2*segdir)*segdir,
613 p = [ [-3 ,6,-3 ], // polynomial in power form
614 [ 7,-9, 2 ],
615 [-5, 3, 0 ],
616 [ 1, 0, 0 ] ]*[normal1*normal1, normal1*normal2, normal2*normal2],
617 uextreme = approx(norm(p),0) ? []
618 : [for(root = real_roots(p)) if (root>0 && root<1) root],
619 distlist = [for(d=bezier_points([normal1*0, normal1, normal2, normal2*0], uextreme)) norm(d)],
620 scale = len(distlist)==0 ? 0 :
621 len(distlist)==1 ? distlist[0]
622 : sum(distlist) - 2*min(distlist),
623 Ldesired = size/scale, // This will be infinity when the polynomial is zero
624 L = min(Lmax, Ldesired)
625 )
626 each [
627 first,
628 first + L*tangent1,
629 second + L*tangent2
630 ],
631 select(path,lastpt)
632 ];
633
634
635
636
637// Function: bezpath_close_to_axis()
638// Synopsis: Closes a 2D bezier path to the specified axis.
639// SynTags: Path
640// Topics: Bezier Paths
641// See Also: bezpath_offset()
642// Usage:
643// bezpath = bezpath_close_to_axis(bezpath, [axis], [N]);
644// Description:
645// Takes a 2D bezier path and closes it to the specified axis.
646// Arguments:
647// bezpath = The 2D bezier path to close to the axis.
648// axis = The axis to close to, "X", or "Y". Default: "X"
649// N = The degree of the bezier curves. Cubic beziers have N=3. Default: 3
650// Example(2D):
651// bez = [[50,30], [40,10], [10,50], [0,30],
652// [-10, 10], [-30,10], [-50,20]];
653// closed = bezpath_close_to_axis(bez);
654// debug_bezier(closed);
655// Example(2D):
656// bez = [[30,50], [10,40], [50,10], [30,0],
657// [10, -10], [10,-30], [20,-50]];
658// closed = bezpath_close_to_axis(bez, axis="Y");
659// debug_bezier(closed);
660function bezpath_close_to_axis(bezpath, axis="X", N=3) =
661 assert(is_path(bezpath,2), "bezpath_close_to_axis() can only work on 2D bezier paths.")
662 assert(is_int(N))
663 assert(len(bezpath)%N == 1, str("A degree ",N," bezier path shound have a multiple of ",N," points in it, plus 1."))
664 let(
665 sp = bezpath[0],
666 ep = last(bezpath)
667 ) (axis=="X")? concat(
668 lerpn([sp.x,0], sp, N, false),
669 list_head(bezpath),
670 lerpn(ep, [ep.x,0], N, false),
671 lerpn([ep.x,0], [sp.x,0], N+1)
672 ) : (axis=="Y")? concat(
673 lerpn([0,sp.y], sp, N, false),
674 list_head(bezpath),
675 lerpn(ep, [0,ep.y], N, false),
676 lerpn([0,ep.y], [0,sp.y], N+1)
677 ) : (
678 assert(in_list(axis, ["X","Y"]))
679 );
680
681
682// Function: bezpath_offset()
683// Synopsis: Forms a closed bezier path loop with a translated and reversed copy of itself.
684// SynTags: Path
685// Topics: Bezier Paths
686// See Also: bezpath_close_to_axis()
687// Usage:
688// bezpath = bezpath_offset(offset, bezier, [N]);
689// Description:
690// Takes a 2D bezier path and closes it with a matching reversed path that is offset by the given `offset` [X,Y] distance.
691// Arguments:
692// offset = Amount to offset second path by.
693// bezier = The 2D bezier path.
694// N = The degree of the bezier curves. Cubic beziers have N=3. Default: 3
695// Example(2D):
696// bez = [[50,30], [40,10], [10,50], [0,30], [-10, 10], [-30,10], [-50,20]];
697// closed = bezpath_offset([0,-5], bez);
698// debug_bezier(closed);
699// Example(2D):
700// bez = [[30,50], [10,40], [50,10], [30,0], [10, -10], [10,-30], [20,-50]];
701// closed = bezpath_offset([-5,0], bez);
702// debug_bezier(closed);
703function bezpath_offset(offset, bezier, N=3) =
704 assert(is_vector(offset,2))
705 assert(is_path(bezier,2), "bezpath_offset() can only work on 2D bezier paths.")
706 assert(is_int(N))
707 assert(len(bezier)%N == 1, str("A degree ",N," bezier path shound have a multiple of ",N," points in it, plus 1."))
708 let(
709 backbez = reverse([ for (pt = bezier) pt+offset ]),
710 bezend = len(bezier)-1
711 ) concat(
712 list_head(bezier),
713 lerpn(bezier[bezend], backbez[0], N, false),
714 list_head(backbez),
715 lerpn(backbez[bezend], bezier[0], N+1)
716 );
717
718
719
720// Section: Cubic Bezier Path Construction
721
722// Function: bez_begin()
723// Synopsis: Calculates starting bezier path control points.
724// Topics: Bezier Paths
725// See Also: bez_tang(), bez_joint(), bez_end()
726// Usage:
727// pts = bez_begin(pt, a, r, [p=]);
728// pts = bez_begin(pt, VECTOR, [r], [p=]);
729// Description:
730// This is used to create the first endpoint and control point of a cubic bezier path.
731// Arguments:
732// pt = The starting endpoint for the bezier path.
733// a = If given a scalar, specifies the theta (XY plane) angle in degrees from X+. If given a vector, specifies the direction and possibly distance of the first control point.
734// r = Specifies the distance of the control point from the endpoint `pt`.
735// ---
736// p = If given, specifies the number of degrees away from the Z+ axis.
737// Example(2D): 2D Bezier Path by Angle
738// bezpath = flatten([
739// bez_begin([-50, 0], 45,20),
740// bez_tang ([ 0, 0],-135,20),
741// bez_joint([ 20,-25], 135, 90, 10, 15),
742// bez_end ([ 50, 0], -90,20),
743// ]);
744// debug_bezier(bezpath);
745// Example(2D): 2D Bezier Path by Vector
746// bezpath = flatten([
747// bez_begin([-50,0],[0,-20]),
748// bez_tang ([-10,0],[0,-20]),
749// bez_joint([ 20,-25], [-10,10], [0,15]),
750// bez_end ([ 50,0],[0, 20]),
751// ]);
752// debug_bezier(bezpath);
753// Example(2D): 2D Bezier Path by Vector and Distance
754// bezpath = flatten([
755// bez_begin([-30,0],FWD, 30),
756// bez_tang ([ 0,0],FWD, 30),
757// bez_joint([ 20,-25], 135, 90, 10, 15),
758// bez_end ([ 30,0],BACK,30),
759// ]);
760// debug_bezier(bezpath);
761// Example(3D,FlatSpin,VPD=200): 3D Bezier Path by Angle
762// bezpath = flatten([
763// bez_begin([-30,0,0],90,20,p=135),
764// bez_tang ([ 0,0,0],-90,20,p=135),
765// bez_joint([20,-25,0], 135, 90, 15, 10, p1=135, p2=45),
766// bez_end ([ 30,0,0],-90,20,p=45),
767// ]);
768// debug_bezier(bezpath);
769// Example(3D,FlatSpin,VPD=225): 3D Bezier Path by Vector
770// bezpath = flatten([
771// bez_begin([-30,0,0],[0,-20, 20]),
772// bez_tang ([ 0,0,0],[0,-20,-20]),
773// bez_joint([20,-25,0],[0,10,-10],[0,15,15]),
774// bez_end ([ 30,0,0],[0,-20,-20]),
775// ]);
776// debug_bezier(bezpath);
777// Example(3D,FlatSpin,VPD=225): 3D Bezier Path by Vector and Distance
778// bezpath = flatten([
779// bez_begin([-30,0,0],FWD, 20),
780// bez_tang ([ 0,0,0],DOWN,20),
781// bez_joint([20,-25,0],LEFT,DOWN,r1=20,r2=15),
782// bez_end ([ 30,0,0],DOWN,20),
783// ]);
784// debug_bezier(bezpath);
785function bez_begin(pt,a,r,p) =
786 assert(is_finite(r) || is_vector(a))
787 assert(len(pt)==3 || is_undef(p))
788 is_vector(a)? [pt, pt+(is_undef(r)? a : r*unit(a))] :
789 is_finite(a)? [pt, pt+spherical_to_xyz(r,a,default(p,90))] :
790 assert(false, "Bad arguments.");
791
792
793// Function: bez_tang()
794// Synopsis: Calculates control points for a smooth bezier path joint.
795// Topics: Bezier Paths
796// See Also: bez_begin(), bez_joint(), bez_end()
797// Usage:
798// pts = bez_tang(pt, a, r1, r2, [p=]);
799// pts = bez_tang(pt, VECTOR, [r1], [r2], [p=]);
800// Description:
801// This creates a smooth joint in a cubic bezier path. It creates three points, being the
802// approaching control point, the fixed bezier control point, and the departing control
803// point. The two control points will be collinear with the fixed point, making for a
804// smooth bezier curve at the fixed point. See {{bez_begin()}} for examples.
805// Arguments:
806// pt = The fixed point for the bezier path.
807// a = If given a scalar, specifies the theta (XY plane) angle in degrees from X+. If given a vector, specifies the direction and possibly distance of the departing control point.
808// r1 = Specifies the distance of the approching control point from the fixed point. Overrides the distance component of the vector if `a` contains a vector.
809// r2 = Specifies the distance of the departing control point from the fixed point. Overrides the distance component of the vector if `a` contains a vector. If `r1` is given and `r2` is not, uses the value of `r1` for `r2`.
810// ---
811// p = If given, specifies the number of degrees away from the Z+ axis.
812function bez_tang(pt,a,r1,r2,p) =
813 assert(is_finite(r1) || is_vector(a))
814 assert(len(pt)==3 || is_undef(p))
815 let(
816 r1 = is_num(r1)? r1 : norm(a),
817 r2 = default(r2,r1),
818 p = default(p, 90)
819 )
820 is_vector(a)? [pt-r1*unit(a), pt, pt+r2*unit(a)] :
821 is_finite(a)? [
822 pt-spherical_to_xyz(r1,a,p),
823 pt,
824 pt+spherical_to_xyz(r2,a,p)
825 ] :
826 assert(false, "Bad arguments.");
827
828
829// Function: bez_joint()
830// Synopsis: Calculates control points for a disjointed corner bezier path joint.
831// Topics: Bezier Paths
832// See Also: bez_begin(), bez_tang(), bez_end()
833// Usage:
834// pts = bez_joint(pt, a1, a2, r1, r2, [p1=], [p2=]);
835// pts = bez_joint(pt, VEC1, VEC2, [r1=], [r2=], [p1=], [p2=]);
836// Description:
837// This creates a disjoint corner joint in a cubic bezier path. It creates three points, being
838// the aproaching control point, the fixed bezier control point, and the departing control point.
839// The two control points can be directed in different arbitrary directions from the fixed bezier
840// point. See {{bez_begin()}} for examples.
841// Arguments:
842// pt = The fixed point for the bezier path.
843// a1 = If given a scalar, specifies the theta (XY plane) angle in degrees from X+. If given a vector, specifies the direction and possibly distance of the approaching control point.
844// a2 = If given a scalar, specifies the theta (XY plane) angle in degrees from X+. If given a vector, specifies the direction and possibly distance of the departing control point.
845// r1 = Specifies the distance of the approching control point from the fixed point. Overrides the distance component of the vector if `a1` contains a vector.
846// r2 = Specifies the distance of the departing control point from the fixed point. Overrides the distance component of the vector if `a2` contains a vector.
847// ---
848// p1 = If given, specifies the number of degrees away from the Z+ axis of the approaching control point.
849// p2 = If given, specifies the number of degrees away from the Z+ axis of the departing control point.
850function bez_joint(pt,a1,a2,r1,r2,p1,p2) =
851 assert(is_finite(r1) || is_vector(a1))
852 assert(is_finite(r2) || is_vector(a2))
853 assert(len(pt)==3 || (is_undef(p1) && is_undef(p2)))
854 let(
855 r1 = is_num(r1)? r1 : norm(a1),
856 r2 = is_num(r2)? r2 : norm(a2),
857 p1 = default(p1, 90),
858 p2 = default(p2, 90)
859 ) [
860 if (is_vector(a1)) (pt+r1*unit(a1))
861 else if (is_finite(a1)) (pt+spherical_to_xyz(r1,a1,p1))
862 else assert(false, "Bad Arguments"),
863 pt,
864 if (is_vector(a2)) (pt+r2*unit(a2))
865 else if (is_finite(a2)) (pt+spherical_to_xyz(r2,a2,p2))
866 else assert(false, "Bad Arguments")
867 ];
868
869
870// Function: bez_end()
871// Synopsis: Calculates ending bezier path control points.
872// Topics: Bezier Paths
873// See Also: bez_tang(), bez_joint(), bez_end()
874// Usage:
875// pts = bez_end(pt, a, r, [p=]);
876// pts = bez_end(pt, VECTOR, [r], [p=]);
877// Description:
878// This is used to create the approaching control point, and the endpoint of a cubic bezier path.
879// See {{bez_begin()}} for examples.
880// Arguments:
881// pt = The starting endpoint for the bezier path.
882// a = If given a scalar, specifies the theta (XY plane) angle in degrees from X+. If given a vector, specifies the direction and possibly distance of the first control point.
883// r = Specifies the distance of the control point from the endpoint `pt`.
884// p = If given, specifies the number of degrees away from the Z+ axis.
885function bez_end(pt,a,r,p) =
886 assert(is_finite(r) || is_vector(a))
887 assert(len(pt)==3 || is_undef(p))
888 is_vector(a)? [pt+(is_undef(r)? a : r*unit(a)), pt] :
889 is_finite(a)? [pt+spherical_to_xyz(r,a,default(p,90)), pt] :
890 assert(false, "Bad arguments.");
891
892
893
894// Section: Bezier Surfaces
895
896
897// Function: is_bezier_patch()
898// Synopsis: Returns true if the given item is a bezier patch.
899// Topics: Bezier Patches, Type Checking
900// Usage:
901// bool = is_bezier_patch(x);
902// Description:
903// Returns true if the given item is a bezier patch. (a 2D array of 3D points.)
904// Arguments:
905// x = The value to check the type of.
906function is_bezier_patch(x) =
907 is_list(x) && is_list(x[0]) && is_vector(x[0][0]) && len(x[0]) == len(x[len(x)-1]);
908
909
910// Function: bezier_patch_flat()
911// Synopsis: Creates a flat bezier patch.
912// Topics: Bezier Patches
913// See Also: bezier_patch_points()
914// Usage:
915// patch = bezier_patch_flat(size, [N=], [spin=], [orient=], [trans=]);
916// Description:
917// Returns a flat rectangular bezier patch of degree `N`, centered on the XY plane.
918// Arguments:
919// size = scalar or 2-vector giving the X and Y dimensions of the patch.
920// ---
921// N = Degree of the patch to generate. Since this is flat, a degree of 1 should usually be sufficient. Default: 1
922// orient = A direction vector. Point the patch normal in this direction.
923// spin = Spin angle to apply to the patch
924// trans = Amount to translate patch, after orient and spin.
925// Example(3D):
926// patch = bezier_patch_flat(size=[100,100]);
927// debug_bezier_patches([patch], size=1, showcps=true);
928function bezier_patch_flat(size, N=1, spin=0, orient=UP, trans=[0,0,0]) =
929 assert(N>0)
930 let(size = force_list(size,2))
931 assert(is_vector(size,2))
932 let(
933 patch = [
934 for (x=[0:1:N]) [
935 for (y=[0:1:N])
936 v_mul(point3d(size), [x/N-0.5, 0.5-y/N, 0])
937 ]
938 ],
939 m = move(trans) * rot(a=spin, from=UP, to=orient)
940 ) [for (row=patch) apply(m, row)];
941
942
943
944// Function: bezier_patch_reverse()
945// Synopsis: Reverses the orientation of a bezier patch.
946// Topics: Bezier Patches
947// See Also: bezier_patch_points(), bezier_patch_flat()
948// Usage:
949// rpatch = bezier_patch_reverse(patch);
950// Description:
951// Reverses the patch, so that the faces generated from it are flipped back to front.
952// Arguments:
953// patch = The patch to reverse.
954function bezier_patch_reverse(patch) =
955 [for (row=patch) reverse(row)];
956
957
958// Function: bezier_patch_points()
959// Synopsis: Computes one or more specified points across a bezier surface patch.
960// Topics: Bezier Patches
961// See Also: bezier_patch_normals(), bezier_points(), bezier_curve(), bezpath_curve()
962// Usage:
963// pt = bezier_patch_points(patch, u, v);
964// ptgrid = bezier_patch_points(patch, LIST, LIST);
965// ptgrid = bezier_patch_points(patch, RANGE, RANGE);
966// Description:
967// Sample a bezier patch on a listed point set. The bezier patch must be a rectangular array of
968// points, and it will be sampled at all the (u,v) pairs that you specify. If you give u and v
969// as single numbers you'll get a single point back. If you give u and v as lists or ranges you'll
970// get a 2d rectangular array of points. If one but not both of u and v is a list or range then you'll
971// get a list of points.
972// Arguments:
973// patch = The 2D array of control points for a Bezier patch.
974// u = The bezier u parameter (inner list of patch). Generally between 0 and 1. Can be a list, range or value.
975// v = The bezier v parameter (outer list of patch). Generally between 0 and 1. Can be a list, range or value.
976// Example(3D):
977// patch = [
978// [[-50, 50, 0], [-16, 50, 20], [ 16, 50, 20], [50, 50, 0]],
979// [[-50, 16, 20], [-16, 16, 40], [ 16, 16, 40], [50, 16, 20]],
980// [[-50,-16, 20], [-16,-16, 40], [ 16,-16, 40], [50,-16, 20]],
981// [[-50,-50, 0], [-16,-50, 20], [ 16,-50, 20], [50,-50, 0]]
982// ];
983// debug_bezier_patches(patches=[patch], size=1, showcps=true);
984// pt = bezier_patch_points(patch, 0.6, 0.75);
985// translate(pt) color("magenta") sphere(d=3, $fn=12);
986// Example(3D): Getting Multiple Points at Once
987// patch = [
988// [[-50, 50, 0], [-16, 50, 20], [ 16, 50, 20], [50, 50, 0]],
989// [[-50, 16, 20], [-16, 16, 40], [ 16, 16, 40], [50, 16, 20]],
990// [[-50,-16, 20], [-16,-16, 40], [ 16,-16, 40], [50,-16, 20]],
991// [[-50,-50, 0], [-16,-50, 20], [ 16,-50, 20], [50,-50, 0]]
992// ];
993// debug_bezier_patches(patches=[patch], size=1, showcps=true);
994// pts = bezier_patch_points(patch, [0:0.2:1], [0:0.2:1]);
995// for (row=pts) move_copies(row) color("magenta") sphere(d=3, $fn=12);
996function bezier_patch_points(patch, u, v) =
997 assert(is_range(u) || is_vector(u) || is_finite(u), "Input u is invalid")
998 assert(is_range(v) || is_vector(v) || is_finite(v), "Input v is invalid")
999 !is_num(u) && !is_num(v) ?
1000 let(
1001 vbezes = [for (i = idx(patch[0])) bezier_points(column(patch,i), u)]
1002 )
1003 [for (i = idx(vbezes[0])) bezier_points(column(vbezes,i), v)]
1004 : is_num(u) && is_num(v)? bezier_points([for (bez = patch) bezier_points(bez, v)], u)
1005 : is_num(u) ? bezier_patch_points(patch,force_list(u),v)[0]
1006 : column(bezier_patch_points(patch,u,force_list(v)),0);
1007
1008
1009
1010
1011function _bezier_rectangle(patch, splinesteps=16, style="default") =
1012 let(
1013 uvals = lerpn(0,1,splinesteps.x+1),
1014 vvals = lerpn(1,0,splinesteps.y+1),
1015 pts = bezier_patch_points(patch, uvals, vvals)
1016 )
1017 vnf_vertex_array(pts, style=style, reverse=false);
1018
1019
1020// Function: bezier_vnf()
1021// Synopsis: Generates a (probably non-manifold) VNF for one or more bezier surface patches.
1022// SynTags: VNF
1023// Topics: Bezier Patches
1024// See Also: bezier_patch_points(), bezier_patch_flat()
1025// Usage:
1026// vnf = bezier_vnf(patches, [splinesteps], [style]);
1027// Description:
1028// Convert a patch or list of patches into the corresponding Bezier surface, representing the
1029// result as a [VNF structure](vnf.scad). The `splinesteps` argument specifies the sampling grid of
1030// the surface for each patch by specifying the number of segments on the borders of the surface.
1031// It can be a scalar, which gives a uniform grid, or
1032// it can be [USTEPS, VSTEPS], which gives difference spacing in the U and V parameters.
1033// Note that the surface you produce may be disconnected and is not necessarily a valid manifold in OpenSCAD.
1034// You must also ensure that the patches mate exactly along their edges, or the VNF will be invalid.
1035// Arguments:
1036// patches = The bezier patch or list of bezier patches to convert into a vnf.
1037// splinesteps = Number of segments on the border of the bezier surface. You can specify [USTEPS,VSTEPS]. Default: 16
1038// style = The style of subdividing the quads into faces. Valid options are "default", "alt", "min_edge", "quincunx", "convex" and "concave". See {{vnf_vertex_array()}}. Default: "default"
1039// Example(3D):
1040// patch = [
1041// // u=0,v=0 u=1,v=0
1042// [[-50,-50, 0], [-16,-50, 20], [ 16,-50, -20], [50,-50, 0]],
1043// [[-50,-16, 20], [-16,-16, 20], [ 16,-16, -20], [50,-16, 20]],
1044// [[-50, 16, 20], [-16, 16, -20], [ 16, 16, 20], [50, 16, 20]],
1045// [[-50, 50, 0], [-16, 50, -20], [ 16, 50, 20], [50, 50, 0]],
1046// // u=0,v=1 u=1,v=1
1047// ];
1048// vnf = bezier_vnf(patch, splinesteps=16);
1049// vnf_polyhedron(vnf);
1050// Example(3D,FlatSpin,VPD=444): Combining multiple patches
1051// patch = 100*[
1052// // u=0,v=0 u=1,v=0
1053// [[0, 0,0], [1/3, 0, 0], [2/3, 0, 0], [1, 0,0]],
1054// [[0,1/3,0], [1/3,1/3,1/3], [2/3,1/3,1/3], [1,1/3,0]],
1055// [[0,2/3,0], [1/3,2/3,1/3], [2/3,2/3,1/3], [1,2/3,0]],
1056// [[0, 1,0], [1/3, 1, 0], [2/3, 1, 0], [1, 1,0]],
1057// // u=0,v=1 u=1,v=1
1058// ];
1059// fpatch = bezier_patch_flat([100,100]);
1060// tpatch = translate([-50,-50,50], patch);
1061// flatpatch = translate([0,0,50], fpatch);
1062// vnf = bezier_vnf([
1063// tpatch,
1064// xrot(90, tpatch),
1065// xrot(-90, tpatch),
1066// xrot(180, tpatch),
1067// yrot(90, flatpatch),
1068// yrot(-90, tpatch)]);
1069// vnf_polyhedron(vnf);
1070// Example(3D):
1071// patch1 = [
1072// [[18,18,0], [33, 0, 0], [ 67, 0, 0], [ 82, 18,0]],
1073// [[ 0,40,0], [ 0, 0,100], [100, 0, 20], [100, 40,0]],
1074// [[ 0,60,0], [ 0,100,100], [100,100, 20], [100, 60,0]],
1075// [[18,82,0], [33,100, 0], [ 67,100, 0], [ 82, 82,0]],
1076// ];
1077// patch2 = [
1078// [[18,82,0], [33,100, 0], [ 67,100, 0], [ 82, 82,0]],
1079// [[ 0,60,0], [ 0,100,-50], [100,100,-50], [100, 60,0]],
1080// [[ 0,40,0], [ 0, 0,-50], [100, 0,-50], [100, 40,0]],
1081// [[18,18,0], [33, 0, 0], [ 67, 0, 0], [ 82, 18,0]],
1082// ];
1083// vnf = bezier_vnf(patches=[patch1, patch2], splinesteps=16);
1084// vnf_polyhedron(vnf);
1085// Example(3D): Connecting Patches with asymmetric splinesteps. Note it is fastest to join all the VNFs at once, which happens in vnf_polyhedron, rather than generating intermediate joined partial surfaces.
1086// steps = 8;
1087// edge_patch = [
1088// // u=0, v=0 u=1,v=0
1089// [[-60, 0,-40], [0, 0,-40], [60, 0,-40]],
1090// [[-60, 0, 0], [0, 0, 0], [60, 0, 0]],
1091// [[-60,40, 0], [0,40, 0], [60,40, 0]],
1092// // u=0, v=1 u=1,v=1
1093// ];
1094// corner_patch = [
1095// // u=0, v=0 u=1,v=0
1096// [[ 0, 40,-40], [ 0, 0,-40], [40, 0,-40]],
1097// [[ 0, 40, 0], [ 0, 0, 0], [40, 0, 0]],
1098// [[40, 40, 0], [40, 40, 0], [40, 40, 0]],
1099// // u=0, v=1 u=1,v=1
1100// ];
1101// face_patch = bezier_patch_flat([120,120],orient=LEFT);
1102// edges = [
1103// for (axrot=[[0,0,0],[0,90,0],[0,0,90]], xang=[-90:90:180])
1104// bezier_vnf(
1105// splinesteps=[steps,1],
1106// rot(a=axrot,
1107// p=rot(a=[xang,0,0],
1108// p=translate(v=[0,-100,100],p=edge_patch)
1109// )
1110// )
1111// )
1112// ];
1113// corners = [
1114// for (xang=[0,180], zang=[-90:90:180])
1115// bezier_vnf(
1116// splinesteps=steps,
1117// rot(a=[xang,0,zang],
1118// p=translate(v=[-100,-100,100],p=corner_patch)
1119// )
1120// )
1121// ];
1122// faces = [
1123// for (axrot=[[0,0,0],[0,90,0],[0,0,90]], zang=[0,180])
1124// bezier_vnf(
1125// splinesteps=1,
1126// rot(a=axrot,
1127// p=zrot(zang,move([-100,0,0], face_patch))
1128// )
1129// )
1130// ];
1131// vnf_polyhedron(concat(edges,corners,faces));
1132function bezier_vnf(patches=[], splinesteps=16, style="default") =
1133 assert(is_num(splinesteps) || is_vector(splinesteps,2))
1134 assert(all_positive(splinesteps))
1135 let(splinesteps = force_list(splinesteps,2))
1136 is_bezier_patch(patches)? _bezier_rectangle(patches, splinesteps=splinesteps,style=style)
1137 : assert(is_list(patches),"Invalid patch list")
1138 vnf_join(
1139 [
1140 for (patch=patches)
1141 is_bezier_patch(patch)? _bezier_rectangle(patch, splinesteps=splinesteps,style=style)
1142 : assert(false,"Invalid patch list")
1143 ]
1144 );
1145
1146
1147
1148// Function: bezier_vnf_degenerate_patch()
1149// Synopsis: Generates a VNF for a degenerate bezier surface patch.
1150// SynTags: VNF
1151// Topics: Bezier Patches
1152// See Also: bezier_patch_points(), bezier_patch_flat(), bezier_vnf()
1153// Usage:
1154// vnf = bezier_vnf_degenerate_patch(patch, [splinesteps], [reverse]);
1155// vnf_edges = bezier_vnf_degenerate_patch(patch, [splinesteps], [reverse], return_edges=true);
1156// Description:
1157// Returns a VNF for a degenerate rectangular bezier patch where some of the corners of the patch are
1158// equal. If the resulting patch has no faces then returns an empty VNF. Note that due to the degeneracy,
1159// the shape of the surface can be triangular even though the underlying patch is a rectangle.
1160// If you specify return_edges then the return is a list whose first element is the vnf and whose second
1161// element lists the edges in the order [left, right, top, bottom], where each list is a list of the actual
1162// point values, but possibly only a single point if that edge is degenerate.
1163// The method checks for various types of degeneracy and uses a triangular or partly triangular array of sample points.
1164// See examples below for the types of degeneracy detected and how the patch is sampled for those cases.
1165// Note that splinesteps is the same for both directions of the patch, so it cannot be an array.
1166// Arguments:
1167// patch = Patch to process
1168// splinesteps = Number of segments to produce on each side. Default: 16
1169// reverse = reverse direction of faces. Default: false
1170// return_edges = if true return the points on the four edges: [left, right, top, bottom]. Default: false
1171// Example(3D,NoAxes): This quartic patch is degenerate at one corner, where a row of control points are equal. Processing this degenerate patch normally produces excess triangles near the degenerate point.
1172// splinesteps=8;
1173// patch=[
1174// repeat([-12.5, 12.5, 15],5),
1175// [[-6.25, 11.25, 15], [-6.25, 8.75, 15], [-6.25, 6.25, 15], [-8.75, 6.25, 15], [-11.25, 6.25, 15]],
1176// [[0, 10, 15], [0, 5, 15], [0, 0, 15], [-5, 0, 15], [-10, 0, 15]],
1177// [[0, 10, 8.75], [0, 5, 8.75], [0, 0, 8.75], [-5, 0, 8.75], [-10, 0, 8.75]],
1178// [[0, 10, 2.5], [0, 5, 2.5], [0, 0, 2.5], [-5, 0, 2.5], [-10, 0, 2.5]]
1179// ];
1180// vnf_wireframe((bezier_vnf(patch, splinesteps)),width=0.1);
1181// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1182// Example(3D,NoAxes): With bezier_vnf_degenerate_patch the degenerate point does not have excess triangles. The top half of the patch decreases the number of sampled points by 2 for each row.
1183// splinesteps=8;
1184// patch=[
1185// repeat([-12.5, 12.5, 15],5),
1186// [[-6.25, 11.25, 15], [-6.25, 8.75, 15], [-6.25, 6.25, 15], [-8.75, 6.25, 15], [-11.25, 6.25, 15]],
1187// [[0, 10, 15], [0, 5, 15], [0, 0, 15], [-5, 0, 15], [-10, 0, 15]],
1188// [[0, 10, 8.75], [0, 5, 8.75], [0, 0, 8.75], [-5, 0, 8.75], [-10, 0, 8.75]],
1189// [[0, 10, 2.5], [0, 5, 2.5], [0, 0, 2.5], [-5, 0, 2.5], [-10, 0, 2.5]]
1190// ];
1191// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1192// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1193// Example(3D,NoAxes): With splinesteps odd you get one "odd" row where the point count decreases by 1 instead of 2. You may prefer even values for splinesteps to avoid this.
1194// splinesteps=7;
1195// patch=[
1196// repeat([-12.5, 12.5, 15],5),
1197// [[-6.25, 11.25, 15], [-6.25, 8.75, 15], [-6.25, 6.25, 15], [-8.75, 6.25, 15], [-11.25, 6.25, 15]],
1198// [[0, 10, 15], [0, 5, 15], [0, 0, 15], [-5, 0, 15], [-10, 0, 15]],
1199// [[0, 10, 8.75], [0, 5, 8.75], [0, 0, 8.75], [-5, 0, 8.75], [-10, 0, 8.75]],
1200// [[0, 10, 2.5], [0, 5, 2.5], [0, 0, 2.5], [-5, 0, 2.5], [-10, 0, 2.5]]
1201// ];
1202// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1203// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1204// Example(3D,NoAxes): A more extreme degeneracy occurs when the top half of a patch is degenerate to a line. (For odd length patches the middle row must be degenerate to trigger this style.) In this case the number of points in each row decreases by 1 for every row. It doesn't matter of splinesteps is odd or even.
1205// splinesteps=8;
1206// patch = [[[10, 0, 0], [10, -10.4, 0], [10, -20.8, 0], [1.876, -14.30, 0], [-6.24, -7.8, 0]],
1207// [[5, 0, 0], [5, -5.2, 0], [5, -10.4, 0], [0.938, -7.15, 0], [-3.12, -3.9, 0]],
1208// repeat([0,0,0],5),
1209// repeat([0,0,5],5),
1210// repeat([0,0,10],5)
1211// ];
1212// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1213// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1214// Example(3D,NoScales): Here is a degenerate cubic patch.
1215// splinesteps=8;
1216// patch = [ [ [-20,0,0], [-10,0,0],[0,10,0],[0,20,0] ],
1217// [ [-20,0,10], [-10,0,10],[0,10,10],[0,20,10]],
1218// [ [-10,0,20], [-5,0,20], [0,5,20], [0,10,20]],
1219// repeat([0,0,30],4)
1220// ];
1221// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1222// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1223// Example(3D,NoScales): A more extreme degenerate cubic patch, where two rows are equal.
1224// splinesteps=8;
1225// patch = [ [ [-20,0,0], [-10,0,0],[0,10,0],[0,20,0] ],
1226// [ [-20,0,10], [-10,0,10],[0,10,10],[0,20,10] ],
1227// repeat([-10,10,20],4),
1228// repeat([-10,10,30],4)
1229// ];
1230// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1231// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1232// Example(3D,NoScales): Quadratic patch degenerate at the right side:
1233// splinesteps=8;
1234// patch = [[[0, -10, 0],[10, -5, 0],[20, 0, 0]],
1235// [[0, 0, 0], [10, 0, 0], [20, 0, 0]],
1236// [[0, 0, 10], [10, 0, 5], [20, 0, 0]]];
1237// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1238// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1239// Example(3D,NoAxes): Cubic patch degenerate at both ends. In this case the point count changes by 2 at every row.
1240// splinesteps=8;
1241// patch = [
1242// repeat([10,-10,0],4),
1243// [ [-20,0,0], [-1,0,0],[0,10,0],[0,20,0] ],
1244// [ [-20,0,10], [-10,0,10],[0,10,10],[0,20,10] ],
1245// repeat([-10,10,20],4),
1246// ];
1247// vnf_wireframe(bezier_vnf_degenerate_patch(patch, splinesteps),width=0.1);
1248// color("red")move_copies(flatten(patch)) sphere(r=0.3,$fn=9);
1249function bezier_vnf_degenerate_patch(patch, splinesteps=16, reverse=false, return_edges=false) =
1250 !return_edges ? bezier_vnf_degenerate_patch(patch, splinesteps, reverse, true)[0] :
1251 assert(is_bezier_patch(patch), "Input is not a Bezier patch")
1252 assert(is_int(splinesteps) && splinesteps>0, "splinesteps must be a positive integer")
1253 let(
1254 row_degen = [for(row=patch) all_equal(row)],
1255 col_degen = [for(col=transpose(patch)) all_equal(col)],
1256 top_degen = row_degen[0],
1257 bot_degen = last(row_degen),
1258 left_degen = col_degen[0],
1259 right_degen = last(col_degen),
1260 samplepts = lerpn(0,1,splinesteps+1)
1261 )
1262 all(row_degen) && all(col_degen) ? // fully degenerate case
1263 [EMPTY_VNF, repeat([patch[0][0]],4)] :
1264 all(row_degen) ? // degenerate to a line (top to bottom)
1265 let(pts = bezier_points(column(patch,0), samplepts))
1266 [EMPTY_VNF, [pts,pts,[pts[0]],[last(pts)]]] :
1267 all(col_degen) ? // degenerate to a line (left to right)
1268 let(pts = bezier_points(patch[0], samplepts))
1269 [EMPTY_VNF, [[pts[0]], [last(pts)], pts, pts]] :
1270 !top_degen && !bot_degen && !left_degen && !right_degen ? // non-degenerate case
1271 let(pts = bezier_patch_points(patch, samplepts, samplepts))
1272 [
1273 vnf_vertex_array(pts, reverse=!reverse),
1274 [column(pts,0), column(pts,len(pts)-1), pts[0], last(pts)]
1275 ] :
1276 top_degen && bot_degen ?
1277 let(
1278 rowcount = [
1279 each list([3:2:splinesteps]),
1280 if (splinesteps%2==0) splinesteps+1,
1281 each reverse(list([3:2:splinesteps]))
1282 ],
1283 bpatch = [for(i=[0:1:len(patch[0])-1]) bezier_points(column(patch,i), samplepts)],
1284 pts = [
1285 [bpatch[0][0]],
1286 for(j=[0:splinesteps-2]) bezier_points(column(bpatch,j+1), lerpn(0,1,rowcount[j])),
1287 [last(bpatch[0])]
1288 ],
1289 vnf = vnf_tri_array(pts, reverse=!reverse)
1290 ) [
1291 vnf,
1292 [
1293 column(pts,0),
1294 [for(row=pts) last(row)],
1295 pts[0],
1296 last(pts),
1297 ]
1298 ] :
1299 bot_degen ? // only bottom is degenerate
1300 let(
1301 result = bezier_vnf_degenerate_patch(reverse(patch), splinesteps=splinesteps, reverse=!reverse, return_edges=true)
1302 )
1303 [
1304 result[0],
1305 [reverse(result[1][0]), reverse(result[1][1]), (result[1][3]), (result[1][2])]
1306 ] :
1307 top_degen ? // only top is degenerate
1308 let(
1309 full_degen = len(patch)>=4 && all(select(row_degen,1,ceil(len(patch)/2-1))),
1310 rowmax = full_degen ? count(splinesteps+1) :
1311 [for(j=[0:splinesteps]) j<=splinesteps/2 ? 2*j : splinesteps],
1312 bpatch = [for(i=[0:1:len(patch[0])-1]) bezier_points(column(patch,i), samplepts)],
1313 pts = [
1314 [bpatch[0][0]],
1315 for(j=[1:splinesteps]) bezier_points(column(bpatch,j), lerpn(0,1,rowmax[j]+1))
1316 ],
1317 vnf = vnf_tri_array(pts, reverse=!reverse)
1318 ) [
1319 vnf,
1320 [
1321 column(pts,0),
1322 [for(row=pts) last(row)],
1323 pts[0],
1324 last(pts),
1325 ]
1326 ] :
1327 // must have left or right degeneracy, so transpose and recurse
1328 let(
1329 result = bezier_vnf_degenerate_patch(transpose(patch), splinesteps=splinesteps, reverse=!reverse, return_edges=true)
1330 )
1331 [result[0],
1332 select(result[1],[2,3,0,1])
1333 ];
1334
1335
1336// Function: bezier_patch_normals()
1337// Synopsis: Computes surface normals for one or more places on a bezier surface patch.
1338// Topics: Bezier Patches
1339// See Also: bezier_patch_points(), bezier_points(), bezier_curve(), bezpath_curve()
1340// Usage:
1341// n = bezier_patch_normals(patch, u, v);
1342// ngrid = bezier_patch_normals(patch, LIST, LIST);
1343// ngrid = bezier_patch_normals(patch, RANGE, RANGE);
1344// Description:
1345// Compute the unit normal vector to a bezier patch at the listed point set. The bezier patch must be a rectangular array of
1346// points, and the normal will be computed at all the (u,v) pairs that you specify. If you give u and v
1347// as single numbers you'll get a single point back. If you give u and v as lists or ranges you'll
1348// get a 2d rectangular array of points. If one but not both of u and v is a list or range then you'll
1349// get a list of points.
1350// .
1351// This function works by computing the cross product of the tangents. In some degenerate cases the one of the tangents
1352// can be zero, so the normal vector does not exist. In this case, undef is returned. Another degenerate case
1353// occurs when the tangents are parallel, or nearly parallel. In this case you will get a unit vector returned but it will not
1354// be the correct normal vector. This can happen if you use a degenerate patch, or if you give two of the edges of your patch a smooth "corner"
1355// so that the u and v directions are parallel at the corner.
1356// Arguments:
1357// patch = The 2D array of control points for a Bezier patch.
1358// u = The bezier u parameter (inner list of patch). Generally between 0 and 1. Can be a list, range or value.
1359// v = The bezier v parameter (outer list of patch). Generally between 0 and 1. Can be a list, range or value.
1360// Example(3D,Med,VPR=[71.1,0,155.9],VPD=292.705,VPT=[20.4724,38.7273,22.7683],NoAxes): Normal vectors on a patch
1361// patch = [
1362// // u=0,v=0 u=1,v=0
1363// [[-50,-50, 0], [-16,-50, 20], [ 16,-50, -20], [50,-50, 0]],
1364// [[-50,-16, 40], [-16,-16, 20], [ 16,-16, -20], [50,-16, 70]],
1365// [[-50, 16, 20], [-16, 16, -20], [ 16, 37, 20], [70, 16, 20]],
1366// [[-50, 50, 0], [73, 50, -40], [ 16, 50, 20], [50, 50, 0]],
1367// // u=0,v=1 u=1,v=1
1368// ];
1369// vnf_polyhedron(bezier_vnf(patch,splinesteps=30));
1370// uv = lerpn(0,1,12);
1371// pts = bezier_patch_points(patch, uv, uv);
1372// normals = bezier_patch_normals(patch, uv, uv);
1373// for(i=idx(uv),j=idx(uv)){
1374// stroke([pts[i][j],pts[i][j]-6*normals[i][j]], width=0.5,
1375// endcap1="dot",endcap2="arrow2",color="blue");
1376// }
1377// Example(3D,NoAxes,Med,VPR=[72.5,0,288.9],VPD=192.044,VPT=[51.6089,48.118,5.89088]): This example gives invalid normal vectors at the four corners of the patch where the u and v directions are parallel. You can see how the line of triangulation is approaching parallel at the edge, and the invalid vectors in red point in a completely incorrect direction.
1378// patch = [
1379// [[18,18,0], [33, 0, 0], [ 67, 0, 0], [ 82, 18,0]],
1380// [[ 0,40,0], [ 0, 0,100], [100, 0, 20], [100, 40,0]],
1381// [[ 0,60,0], [ 0,100,100], [100,100, 20], [100, 60,0]],
1382// [[18,82,0], [33,100, 0], [ 67,100, 0], [ 82, 82,0]],
1383// ];
1384// vnf_polyhedron(bezier_vnf(patch,splinesteps=30));
1385// uv = lerpn(0,1,7);
1386// pts = bezier_patch_points(patch, uv, uv);
1387// normals = bezier_patch_normals(patch, uv, uv);
1388// for(i=idx(uv),j=idx(uv)){
1389// color=((uv[i]==0 || uv[i]==1) && (uv[j]==0 || uv[j]==1))
1390// ? "red" : "blue";
1391// stroke([pts[i][j],pts[i][j]-8*normals[i][j]], width=0.5,
1392// endcap1="dot",endcap2="arrow2",color=color);
1393// }
1394// Example(3D,Med,NoAxes,VPR=[56.4,0,71.9],VPD=66.9616,VPT=[10.2954,1.33721,19.4484]): This degenerate patch has normals everywhere, but computational of the normal fails at the point of degeneracy, the top corner.
1395// patch=[
1396// repeat([-12.5, 12.5, 15],5),
1397// [[-6.25, 11.25, 15], [-6.25, 8.75, 15], [-6.25, 6.25, 15], [-8.75, 6.25, 15], [-11.25, 6.25, 15]],
1398// [[0, 10, 15], [0, 5, 15], [0, 0, 15], [-5, 0, 15], [-10, 0, 15]],
1399// [[0, 10, 8.75], [0, 5, 8.75], [0, 0, 8.75], [-5, 0, 8.75], [-10, 0, 8.75]],
1400// [[0, 10, 2.5], [0, 5, 2.5], [0, 0, 2.5], [-5, 0, 2.5], [-10, 0, 2.5]]
1401// ];
1402// vnf_polyhedron(bezier_vnf(patch, 32));
1403// uv = lerpn(0,1,8);
1404// pts = bezier_patch_points(patch, uv, uv);
1405// normals = bezier_patch_normals(patch, uv, uv);
1406// for(i=idx(uv),j=idx(uv)){
1407// if (is_def(normals[i][j]))
1408// stroke([pts[i][j],pts[i][j]-2*normals[i][j]], width=0.1,
1409// endcap1="dot",endcap2="arrow2",color="blue");
1410// }
1411// Example(3D,Med,NoAxes,VPR=[48,0,23.6],VPD=32.0275,VPT=[-0.145727,-0.0532125,1.74224]): This example has a singularities where the tangent lines don't exist, so the normal will be undef at those points.
1412// pts1 = [ [-5,0,0], [5,0,5], [-5,0,5], [5,0,0] ];
1413// pts2 = [ [0,-5,0], [0,5,5], [0,-5,5], [0,5,0] ];
1414// patch = [for(i=[0:3])
1415// [for(j=[0:3]) pts1[i]+pts2[j] ] ];
1416// vnf_polyhedron(bezier_vnf(patch, 163));
1417// uv = [0,.1,.2,.3,.7,.8,.9,1];//lerpn(0,1,8);
1418// pts = bezier_patch_points(patch, uv, uv);
1419// normals = bezier_patch_normals(patch, uv, uv);
1420// for(i=idx(uv),j=idx(uv))
1421// stroke([pts[i][j],pts[i][j]+2*normals[i][j]], width=0.08,
1422// endcap1="dot",endcap2="arrow2",color="blue");
1423
1424function bezier_patch_normals(patch, u, v) =
1425 assert(is_range(u) || is_vector(u) || is_finite(u), "Input u is invalid")
1426 assert(is_range(v) || is_vector(v) || is_finite(v), "Input v is invalid")
1427 !is_num(u) && !is_num(v) ?
1428 let(
1429 vbezes = [for (i = idx(patch[0])) bezier_points(column(patch,i), u)],
1430 dvbezes = [for (i = idx(patch[0])) bezier_derivative(column(patch,i), u)],
1431 v_tangent = [for (i = idx(vbezes[0])) bezier_derivative(column(vbezes,i), v)],
1432 u_tangent = [for (i = idx(vbezes[0])) bezier_points(column(dvbezes,i), v)]
1433 )
1434 [for(i=idx(u_tangent)) [for(j=idx(u_tangent[0])) unit(cross(u_tangent[i][j],v_tangent[i][j]),undef)]]
1435 : is_num(u) && is_num(v)?
1436 let(
1437 du = bezier_derivative([for (bez = patch) bezier_points(bez, v)], u),
1438 dv = bezier_points([for (bez = patch) bezier_derivative(bez, v)], u)
1439 )
1440 unit(cross(du,dv),undef)
1441 : is_num(u) ? bezier_patch_normals(patch,force_list(u),v)[0]
1442 : column(bezier_patch_normals(patch,u,force_list(v)),0);
1443
1444
1445
1446// Section: Debugging Beziers
1447
1448
1449// Module: debug_bezier()
1450// Synopsis: Shows a bezier path and it's associated control points.
1451// SynTags: Geom
1452// Topics: Bezier Paths, Debugging
1453// See Also: bezpath_curve()
1454// Usage:
1455// debug_bezier(bez, [size], [N=]);
1456// Description:
1457// Renders 2D or 3D bezier paths and their associated control points.
1458// Useful for debugging bezier paths.
1459// Arguments:
1460// bez = the array of points in the bezier.
1461// size = diameter of the lines drawn.
1462// ---
1463// N = Mark the first and every Nth vertex after in a different color and shape.
1464// Example(2D):
1465// bez = [
1466// [-10, 0], [-15, -5],
1467// [ -5, -10], [ 0, -10], [ 5, -10],
1468// [ 14, -5], [ 15, 0], [16, 5],
1469// [ 5, 10], [ 0, 10]
1470// ];
1471// debug_bezier(bez, N=3, width=0.5);
1472module debug_bezier(bezpath, width=1, N=3) {
1473 no_children($children);
1474 check =
1475 assert(is_path(bezpath),"bezpath must be a path")
1476 assert(is_int(N) && N>0, "N must be a positive integer")
1477 assert(len(bezpath)%N == 1, str("A degree ",N," bezier path shound have a multiple of ",N," points in it, plus 1."));
1478 $fn=8;
1479 stroke(bezpath_curve(bezpath, N=N), width=width, color="cyan");
1480 color("green")
1481 if (N!=3)
1482 stroke(bezpath, width=width);
1483 else
1484 for(i=[1:3:len(bezpath)]) stroke(select(bezpath,max(0,i-2), min(len(bezpath)-1,i)), width=width);
1485 twodim = len(bezpath[0])==2;
1486 color("red") move_copies(bezpath)
1487 if ($idx % N !=0)
1488 if (twodim){
1489 rect([width/2, width*3]);
1490 rect([width*3, width/2]);
1491 } else {
1492 zcyl(d=width/2, h=width*3);
1493 xcyl(d=width/2, h=width*3);
1494 ycyl(d=width/2, h=width*3);
1495 }
1496 color("blue") move_copies(bezpath)
1497 if ($idx % N ==0)
1498 if (twodim) circle(d=width*2.25); else sphere(d=width*2.25);
1499 if (twodim) color("red") move_copies(bezpath)
1500 if ($idx % N !=0) circle(d=width/2);
1501}
1502
1503
1504// Module: debug_bezier_patches()
1505// Synopsis: Shows a bezier surface patch and its associated control points.
1506// SynTags: Geom
1507// Topics: Bezier Patches, Debugging
1508// See Also: bezier_patch_points(), bezier_patch_flat(), bezier_vnf()
1509// Usage:
1510// debug_bezier_patches(patches, [size=], [splinesteps=], [showcps=], [showdots=], [showpatch=], [convexity=], [style=]);
1511// Description:
1512// Shows the surface, and optionally, control points of a list of bezier patches.
1513// Arguments:
1514// patches = A list of rectangular bezier patches.
1515// ---
1516// splinesteps = Number of segments to divide each bezier curve into. Default: 16
1517// showcps = If true, show the controlpoints as well as the surface. Default: true.
1518// showdots = If true, shows the calculated surface vertices. Default: false.
1519// showpatch = If true, shows the surface faces. Default: true.
1520// size = Size to show control points and lines.
1521// style = The style of subdividing the quads into faces. Valid options are "default", "alt", and "quincunx".
1522// convexity = Max number of times a line could intersect a wall of the shape.
1523// Example:
1524// patch1 = [
1525// [[15,15,0], [33, 0, 0], [ 67, 0, 0], [ 85, 15,0]],
1526// [[ 0,33,0], [33, 33, 50], [ 67, 33, 50], [100, 33,0]],
1527// [[ 0,67,0], [33, 67, 50], [ 67, 67, 50], [100, 67,0]],
1528// [[15,85,0], [33,100, 0], [ 67,100, 0], [ 85, 85,0]],
1529// ];
1530// patch2 = [
1531// [[15,85,0], [33,100, 0], [ 67,100, 0], [ 85, 85,0]],
1532// [[ 0,67,0], [33, 67,-50], [ 67, 67,-50], [100, 67,0]],
1533// [[ 0,33,0], [33, 33,-50], [ 67, 33,-50], [100, 33,0]],
1534// [[15,15,0], [33, 0, 0], [ 67, 0, 0], [ 85, 15,0]],
1535// ];
1536// debug_bezier_patches(patches=[patch1, patch2], splinesteps=8, showcps=true);
1537module debug_bezier_patches(patches=[], size, splinesteps=16, showcps=true, showdots=false, showpatch=true, convexity=10, style="default")
1538{
1539 no_children($children);
1540 assert(is_undef(size)||is_num(size));
1541 assert(is_int(splinesteps) && splinesteps>0);
1542 assert(is_list(patches) && all([for (patch=patches) is_bezier_patch(patch)]));
1543 assert(is_bool(showcps));
1544 assert(is_bool(showdots));
1545 assert(is_bool(showpatch));
1546 assert(is_int(convexity) && convexity>0);
1547 for (patch = patches) {
1548 size = is_num(size)? size :
1549 let( bounds = pointlist_bounds(flatten(patch)) )
1550 max(bounds[1]-bounds[0])*0.01;
1551 if (showcps) {
1552 move_copies(flatten(patch)) color("red") sphere(d=size*2);
1553 color("cyan")
1554 for (i=[0:1:len(patch)-1], j=[0:1:len(patch[i])-1]) {
1555 if (i<len(patch)-1) extrude_from_to(patch[i][j], patch[i+1][j]) circle(d=size);
1556 if (j<len(patch[i])-1) extrude_from_to(patch[i][j], patch[i][j+1]) circle(d=size);
1557 }
1558 }
1559 if (showpatch || showdots){
1560 vnf = bezier_vnf(patch, splinesteps=splinesteps, style=style);
1561 if (showpatch) vnf_polyhedron(vnf, convexity=convexity);
1562 if (showdots) color("blue") move_copies(vnf[0]) sphere(d=size);
1563 }
1564 }
1565}
1566
1567
1568// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap