1//////////////////////////////////////////////////////////////////////
2// LibFile: vnf.scad
3// The Vertices'N'Faces structure (VNF) holds the data used by polyhedron() to construct objects: a vertex
4// list and a list of faces. This library makes it easier to construct polyhedra by providing
5// functions to construct, merge, and modify VNF data, while avoiding common pitfalls such as
6// reversed faces. It can find faults in your polyhedrons. Note that this file is for low level manipulation
7// of lists of vertices and faces: it can perform some simple transformations on VNF structures
8// but cannot perform boolean operations on the polyhedrons represented by VNFs.
9// Includes:
10// include <BOSL2/std.scad>
11// FileGroup: Advanced Modeling
12// FileSummary: Vertices 'n' Faces structure. Makes polyhedron() easier to use.
13// FileFootnotes: STD=Included in std.scad
14//////////////////////////////////////////////////////////////////////
15
16
17// Section: Creating Polyhedrons with VNF Structures
18// VNF stands for "Vertices'N'Faces". VNF structures are 2-item lists, `[VERTICES,FACES]` where the
19// first item is a list of vertex points, and the second is a list of face indices into the vertex
20// list. Each VNF is self contained, with face indices referring only to its own vertex list.
21// You can construct a `polyhedron()` in parts by describing each part in a self-contained VNF, then
22// merge the various VNFs to get the completed polyhedron vertex list and faces.
23
24/// Constant: EMPTY_VNF
25/// Description:
26/// The empty VNF data structure. Equal to `[[],[]]`.
27EMPTY_VNF = [[],[]]; // The standard empty VNF with no vertices or faces.
28
29
30// Function: vnf_vertex_array()
31// Synopsis: Returns a VNF structure from a rectangular vertex list.
32// SynTags: VNF
33// Topics: VNF Generators, Lists
34// See Also: vnf_tri_array(), vnf_join(), vnf_from_polygons(), vnf_from_region()
35// Usage:
36// vnf = vnf_vertex_array(points, [caps=], [cap1=], [cap2=], [style=], [reverse=], [col_wrap=], [row_wrap=], [triangulate=]);
37// Description:
38// Creates a VNF structure from a rectangular vertex list, by dividing the vertices into columns and rows,
39// adding faces to tile the surface. You can optionally have faces added to wrap the last column
40// back to the first column, or wrap the last row to the first. Endcaps can be added to either
41// the first and/or last rows. The style parameter determines how the quadrilaterals are divided into
42// triangles. The default style is an arbitrary, systematic subdivision in the same direction. The "alt" style
43// is the uniform subdivision in the other (alternate) direction. The "min_edge" style picks the shorter edge to
44// subdivide for each quadrilateral, so the division may not be uniform across the shape. The "quincunx" style
45// adds a vertex in the center of each quadrilateral and creates four triangles, and the "convex" and "concave" styles
46// chooses the locally convex/concave subdivision. Degenerate faces
47// are not included in the output, but if this results in unused vertices they will still appear in the output.
48// Arguments:
49// points = A list of vertices to divide into columns and rows.
50// ---
51// caps = If true, add endcap faces to the first AND last rows.
52// cap1 = If true, add an endcap face to the first row.
53// cap2 = If true, add an endcap face to the last row.
54// col_wrap = If true, add faces to connect the last column to the first.
55// row_wrap = If true, add faces to connect the last row to the first.
56// reverse = If true, reverse all face normals.
57// style = The style of subdividing the quads into faces. Valid options are "default", "alt", "min_edge", "min_area", "quincunx", "convex" and "concave".
58// triangulate = If true, triangulates endcaps to resolve possible CGAL issues. This can be an expensive operation if the endcaps are complex. Default: false
59// Example(3D):
60// vnf = vnf_vertex_array(
61// points=[
62// for (h = [0:5:180-EPSILON]) [
63// for (t = [0:5:360-EPSILON])
64// cylindrical_to_xyz(100 + 12 * cos((h/2 + t)*6), t, h)
65// ]
66// ],
67// col_wrap=true, caps=true, reverse=true, style="alt"
68// );
69// vnf_polyhedron(vnf);
70// Example(3D): Both `col_wrap` and `row_wrap` are true to make a torus.
71// vnf = vnf_vertex_array(
72// points=[
73// for (a=[0:5:360-EPSILON])
74// apply(
75// zrot(a) * right(30) * xrot(90),
76// path3d(circle(d=20))
77// )
78// ],
79// col_wrap=true, row_wrap=true, reverse=true
80// );
81// vnf_polyhedron(vnf);
82// Example(3D): Möbius Strip. Note that `row_wrap` is not used, and the first and last profile copies are the same.
83// vnf = vnf_vertex_array(
84// points=[
85// for (a=[0:5:360]) apply(
86// zrot(a) * right(30) * xrot(90) * zrot(a/2+60),
87// path3d(square([1,10], center=true))
88// )
89// ],
90// col_wrap=true, reverse=true
91// );
92// vnf_polyhedron(vnf);
93// Example(3D): Assembling a Polyhedron from Multiple Parts
94// wall_points = [
95// for (a = [-90:2:90]) apply(
96// up(a) * scale([1-0.1*cos(a*6),1-0.1*cos((a+90)*6),1]),
97// path3d(circle(d=100))
98// )
99// ];
100// cap = [
101// for (a = [0:0.01:1+EPSILON]) apply(
102// up(90-5*sin(a*360*2)) * scale([a,a,1]),
103// wall_points[0]
104// )
105// ];
106// cap1 = [for (p=cap) down(90, p=zscale(-1, p=p))];
107// cap2 = [for (p=cap) up(90, p=p)];
108// vnf1 = vnf_vertex_array(points=wall_points, col_wrap=true);
109// vnf2 = vnf_vertex_array(points=cap1, col_wrap=true);
110// vnf3 = vnf_vertex_array(points=cap2, col_wrap=true, reverse=true);
111// vnf_polyhedron([vnf1, vnf2, vnf3]);
112// Example(3D): Building a Multi-Stage Cylindrical Ramp
113// include <BOSL2/rounding.scad>
114// major_r = 50;
115// groove_profile = [
116// [-10,0], each arc(points=[[-7,0],[0,-3],[7,0]]), [10,0]
117// ];
118// ramp_profile = [ [-10,25], [90,25], [180,5], [190,5] ];
119// rgroove = apply(right(major_r) * xrot(90), path3d(groove_profile));
120// rprofile = round_corners(ramp_profile, radius=20, closed=false, $fn=72);
121// vnf = vnf_vertex_array([
122// for (a = [ramp_profile[0].x : 1 : last(ramp_profile).x]) let(
123// z = lookup(a,rprofile),
124// m = zrot(a) * up(z)
125// )
126// apply(m, [ [rgroove[0].x,0,-z], each rgroove, [last(rgroove).x,0,-z] ])
127// ], caps=true, col_wrap=true, reverse=true);
128// vnf_polyhedron(vnf, convexity=8);
129function vnf_vertex_array(
130 points,
131 caps, cap1, cap2,
132 col_wrap=false,
133 row_wrap=false,
134 reverse=false,
135 style="default",
136 triangulate = false
137) =
138 assert(!(any([caps,cap1,cap2]) && !col_wrap), "col_wrap must be true if caps are requested")
139 assert(!(any([caps,cap1,cap2]) && row_wrap), "Cannot combine caps with row_wrap")
140 assert(in_list(style,["default","alt","quincunx", "convex","concave", "min_edge","min_area"]))
141 assert(is_matrix(points[0], n=3),"Point array has the wrong shape or points are not 3d")
142 assert(is_consistent(points), "Non-rectangular or invalid point array")
143 assert(is_bool(triangulate))
144 let(
145 pts = flatten(points),
146 pcnt = len(pts),
147 rows = len(points),
148 cols = len(points[0])
149 )
150 rows<=1 || cols<=1 ? EMPTY_VNF :
151 let(
152 cap1 = first_defined([cap1,caps,false]),
153 cap2 = first_defined([cap2,caps,false]),
154 colcnt = cols - (col_wrap?0:1),
155 rowcnt = rows - (row_wrap?0:1),
156 verts = [
157 each pts,
158 if (style=="quincunx")
159 for (r = [0:1:rowcnt-1], c = [0:1:colcnt-1])
160 let(
161 i1 = ((r+0)%rows)*cols + ((c+0)%cols),
162 i2 = ((r+1)%rows)*cols + ((c+0)%cols),
163 i3 = ((r+1)%rows)*cols + ((c+1)%cols),
164 i4 = ((r+0)%rows)*cols + ((c+1)%cols)
165 )
166 mean([pts[i1], pts[i2], pts[i3], pts[i4]])
167 ],
168 allfaces = [
169 if (cap1) count(cols,reverse=!reverse),
170 if (cap2) count(cols,(rows-1)*cols, reverse=reverse),
171 for (r = [0:1:rowcnt-1], c=[0:1:colcnt-1])
172 each
173 let(
174 i1 = ((r+0)%rows)*cols + ((c+0)%cols),
175 i2 = ((r+1)%rows)*cols + ((c+0)%cols),
176 i3 = ((r+1)%rows)*cols + ((c+1)%cols),
177 i4 = ((r+0)%rows)*cols + ((c+1)%cols),
178 faces =
179 style=="quincunx"?
180 let(i5 = pcnt + r*colcnt + c)
181 [[i1,i5,i2],[i2,i5,i3],[i3,i5,i4],[i4,i5,i1]]
182 : style=="alt"?
183 [[i1,i4,i2],[i2,i4,i3]]
184 : style=="min_area"?
185 let(
186 area42 = norm(cross(pts[i2]-pts[i1], pts[i4]-pts[i1]))+norm(cross(pts[i4]-pts[i3], pts[i2]-pts[i3])),
187 area13 = norm(cross(pts[i1]-pts[i4], pts[i3]-pts[i4]))+norm(cross(pts[i3]-pts[i2], pts[i1]-pts[i2])),
188 minarea_edge = area42 < area13 + EPSILON
189 ? [[i1,i4,i2],[i2,i4,i3]]
190 : [[i1,i3,i2],[i1,i4,i3]]
191 )
192 minarea_edge
193 : style=="min_edge"?
194 let(
195 d42=norm(pts[i4]-pts[i2]),
196 d13=norm(pts[i1]-pts[i3]),
197 shortedge = d42<d13+EPSILON
198 ? [[i1,i4,i2],[i2,i4,i3]]
199 : [[i1,i3,i2],[i1,i4,i3]]
200 )
201 shortedge
202 : style=="convex"?
203 let( // Find normal for 3 of the points. Is the other point above or below?
204 n = (reverse?-1:1)*cross(pts[i2]-pts[i1],pts[i3]-pts[i1]),
205 convexfaces = n==0
206 ? [[i1,i4,i3]]
207 : n*pts[i4] > n*pts[i1]
208 ? [[i1,i4,i2],[i2,i4,i3]]
209 : [[i1,i3,i2],[i1,i4,i3]]
210 )
211 convexfaces
212 : style=="concave"?
213 let( // Find normal for 3 of the points. Is the other point above or below?
214 n = (reverse?-1:1)*cross(pts[i2]-pts[i1],pts[i3]-pts[i1]),
215 concavefaces = n==0
216 ? [[i1,i4,i3]]
217 : n*pts[i4] <= n*pts[i1]
218 ? [[i1,i4,i2],[i2,i4,i3]]
219 : [[i1,i3,i2],[i1,i4,i3]]
220 )
221 concavefaces
222 : [[i1,i3,i2],[i1,i4,i3]],
223 // remove degenerate faces
224 culled_faces= [for(face=faces)
225 if (norm(cross(verts[face[1]]-verts[face[0]],
226 verts[face[2]]-verts[face[0]]))>EPSILON)
227 face
228 ],
229 rfaces = reverse? [for (face=culled_faces) reverse(face)] : culled_faces
230 )
231 rfaces,
232 ],
233 vnf = [verts, allfaces]
234 ) triangulate? vnf_triangulate(vnf) : vnf;
235
236
237// Function: vnf_tri_array()
238// Synopsis: Returns a VNF from an array of points.
239// SynTags: VNF
240// Topics: VNF Generators, Lists
241// See Also: vnf_vertex_array(), vnf_join(), vnf_from_polygons(), vnf_from_region()
242// Usage:
243// vnf = vnf_tri_array(points, [row_wrap], [reverse])
244// Description:
245// Produces a VNF from an array of points where each row length can differ from the adjacent rows by up to 2 in length. This enables
246// the construction of triangular VNF patches. The resulting VNF can be wrapped along the rows by setting `row_wrap` to true.
247// You cannot wrap columns: if you need to do that you'll need to merge two VNF arrays that share edges. Degenerate faces
248// are not included in the output, but if this results in unused vertices they will still appear in the output.
249// Arguments:
250// points = List of point lists for each row
251// row_wrap = If true then add faces connecting the first row and last row. These rows must differ by at most 2 in length.
252// reverse = Set this to reverse the direction of the faces
253// Example(3D,NoAxes): Each row has one more point than the preceeding one.
254// pts = [for(y=[1:1:10]) [for(x=[0:y-1]) [x,y,y]]];
255// vnf = vnf_tri_array(pts);
256// vnf_wireframe(vnf,width=0.1);
257// color("red")move_copies(flatten(pts)) sphere(r=.15,$fn=9);
258// Example(3D,NoAxes): Each row has two more points than the preceeding one.
259// pts = [for(y=[0:2:10]) [for(x=[-y/2:y/2]) [x,y,y]]];
260// vnf = vnf_tri_array(pts);
261// vnf_wireframe(vnf,width=0.1);
262// color("red")move_copies(flatten(pts)) sphere(r=.15,$fn=9);
263// Example(3D): Merging two VNFs to construct a cone with one point length change between rows.
264// pts1 = [for(z=[0:10]) path3d(arc(3+z,r=z/2+1, angle=[0,180]),10-z)];
265// pts2 = [for(z=[0:10]) path3d(arc(3+z,r=z/2+1, angle=[180,360]),10-z)];
266// vnf = vnf_join([vnf_tri_array(pts1),
267// vnf_tri_array(pts2)]);
268// color("green")vnf_wireframe(vnf,width=0.1);
269// vnf_polyhedron(vnf);
270// Example(3D): Cone with length change two between rows
271// pts1 = [for(z=[0:1:10]) path3d(arc(3+2*z,r=z/2+1, angle=[0,180]),10-z)];
272// pts2 = [for(z=[0:1:10]) path3d(arc(3+2*z,r=z/2+1, angle=[180,360]),10-z)];
273// vnf = vnf_join([vnf_tri_array(pts1),
274// vnf_tri_array(pts2)]);
275// color("green")vnf_wireframe(vnf,width=0.1);
276// vnf_polyhedron(vnf);
277// Example(3D,NoAxes): Point count can change irregularly
278// lens = [10,9,7,5,6,8,8,10];
279// pts = [for(y=idx(lens)) lerpn([-lens[y],y,y],[lens[y],y,y],lens[y])];
280// vnf = vnf_tri_array(pts);
281// vnf_wireframe(vnf,width=0.1);
282// color("red")move_copies(flatten(pts)) sphere(r=.15,$fn=9);
283function vnf_tri_array(points, row_wrap=false, reverse=false) =
284 let(
285 lens = [for(row=points) len(row)],
286 rowstarts = [0,each cumsum(lens)],
287 faces =
288 [for(i=[0:1:len(points) - 1 - (row_wrap ? 0 : 1)]) each
289 let(
290 rowstart = rowstarts[i],
291 nextrow = select(rowstarts,i+1),
292 delta = select(lens,i+1)-lens[i]
293 )
294 delta == 0 ?
295 [for(j=[0:1:lens[i]-2]) reverse ? [j+rowstart+1, j+rowstart, j+nextrow] : [j+rowstart, j+rowstart+1, j+nextrow],
296 for(j=[0:1:lens[i]-2]) reverse ? [j+rowstart+1, j+nextrow, j+nextrow+1] : [j+rowstart+1, j+nextrow+1, j+nextrow]] :
297 delta == 1 ?
298 [for(j=[0:1:lens[i]-2]) reverse ? [j+rowstart+1, j+rowstart, j+nextrow+1] : [j+rowstart, j+rowstart+1, j+nextrow+1],
299 for(j=[0:1:lens[i]-1]) reverse ? [j+rowstart, j+nextrow, j+nextrow+1] : [j+rowstart, j+nextrow+1, j+nextrow]] :
300 delta == -1 ?
301 [for(j=[0:1:lens[i]-3]) reverse ? [j+rowstart+1, j+nextrow, j+nextrow+1]: [j+rowstart+1, j+nextrow+1, j+nextrow],
302 for(j=[0:1:lens[i]-2]) reverse ? [j+rowstart+1, j+rowstart, j+nextrow] : [j+rowstart, j+rowstart+1, j+nextrow]] :
303 let(count = floor((lens[i]-1)/2))
304 delta == 2 ?
305 [
306 for(j=[0:1:count-1]) reverse ? [j+rowstart+1, j+rowstart, j+nextrow+1] : [j+rowstart, j+rowstart+1, j+nextrow+1], // top triangles left
307 for(j=[count:1:lens[i]-2]) reverse ? [j+rowstart+1, j+rowstart, j+nextrow+2] : [j+rowstart, j+rowstart+1, j+nextrow+2], // top triangles right
308 for(j=[0:1:count]) reverse ? [j+rowstart, j+nextrow, j+nextrow+1] : [j+rowstart, j+nextrow+1, j+nextrow], // bot triangles left
309 for(j=[count+1:1:select(lens,i+1)-2]) reverse ? [j+rowstart-1, j+nextrow, j+nextrow+1] : [j+rowstart-1, j+nextrow+1, j+nextrow], // bot triangles right
310 ] :
311 delta == -2 ?
312 [
313 for(j=[0:1:count-2]) reverse ? [j+nextrow, j+nextrow+1, j+rowstart+1] : [j+nextrow, j+rowstart+1, j+nextrow+1],
314 for(j=[count-1:1:lens[i]-4]) reverse ? [j+nextrow,j+nextrow+1,j+rowstart+2] : [j+nextrow,j+rowstart+2, j+nextrow+1],
315 for(j=[0:1:count-1]) reverse ? [j+nextrow, j+rowstart+1, j+rowstart] : [j+nextrow, j+rowstart, j+rowstart+1],
316 for(j=[count:1:select(lens,i+1)]) reverse ? [ j+nextrow-1, j+rowstart+1, j+rowstart]: [ j+nextrow-1, j+rowstart, j+rowstart+1],
317 ] :
318 assert(false,str("Unsupported row length difference of ",delta, " between row ",i," and ",(i+1)%len(points)))
319 ],
320 verts = flatten(points),
321 culled_faces=
322 [for(face=faces)
323 if (norm(verts[face[0]]-verts[face[1]])>EPSILON &&
324 norm(verts[face[1]]-verts[face[2]])>EPSILON &&
325 norm(verts[face[2]]-verts[face[0]])>EPSILON)
326 face
327 ]
328 )
329 [flatten(points), culled_faces];
330
331
332
333// Function: vnf_join()
334// Synopsis: Returns a single VNF structure from a list of VNF structures.
335// SynTags: VNF
336// Topics: VNF Generators, Lists
337// See Also: vnf_tri_array(), vnf_vertex_array(), vnf_from_polygons(), vnf_from_region()
338// Usage:
339// vnf = vnf_join([VNF, VNF, VNF, ...]);
340// Description:
341// Given a list of VNF structures, merges them all into a single VNF structure.
342// Combines all the points of the input VNFs and labels the faces appropriately.
343// All the points in the input VNFs will appear in the output, even if they are
344// duplicates of each other. It is valid to repeat points in a VNF, but if you
345// with to remove the duplicates that will occur along joined edges, use {{vnf_merge_points()}}.
346// .
347// Note that this is a tool for manipulating polyhedron data. It is for
348// building up a full polyhedron from partial polyhedra.
349// It is *not* a union operator for VNFs. The VNFs to be joined must not intersect each other,
350// except at edges, or the result will be an invalid polyhedron. Similarly the
351// result must not have any other illegal polyhedron characteristics, such as creating
352// more than two faces sharing the same edge.
353// If you want a valid result it is your responsibility to ensure that the polyhedron
354// has no holes, no intersecting faces or edges, and obeys all the requirements
355// that CGAL expects.
356// .
357// For example, if you combine two pyramids to try to make an octahedron, the result will
358// be invalid because of the two internal faces created by the pyramid bases. A valid
359// use would be to build a cube missing one face and a pyramid missing its base and
360// then join them into a cube with a point.
361// Arguments:
362// vnfs = a list of the VNFs to joint into one VNF.
363// Example(3D,VPR=[60,0,26],VPD=55,VPT=[5.6,-5.3,9.8]): Here is a VNF where the top face is missing. It is not a valid polyhedron like this, but we can use it as a building block to make a polyhedron.
364// bottom = vnf_vertex_array([path3d(rect(8)), path3d(rect(5),4)],col_wrap=true,cap1=true);
365// vnf_polyhedron(bottom);
366// Example(3D,VPR=[60,0,26],VPD=55,VPT=[5.6,-5.3,9.8]): Here is a VNF that also has a missing face.
367// triangle = yrot(-90,path3d(regular_ngon(n=3,side=5,anchor=LEFT)));
368// top = up(4,vnf_vertex_array([list_set(right(2.5,triangle),0,[0,0,7]),
369// right(6,triangle)
370// ], col_wrap=true, cap2=true));
371// vnf_polyhedron(zrot(90,top));
372// Example(3D,VPR=[60,0,26],VPD=55,VPT=[5.6,-5.3,9.8]): Using vnf_join combines the two VNFs into a single VNF. Note that they share an edge. But the result still isn't closed, so it is not yet a valid polyhedron.
373// bottom = vnf_vertex_array([path3d(rect(8)), path3d(rect(5),4)],col_wrap=true,cap1=true);
374// triangle = yrot(-90,path3d(regular_ngon(n=3,side=5,anchor=LEFT)));
375// top = up(4,vnf_vertex_array([list_set(right(2.5,triangle),0,[0,0,7]),
376// right(6,triangle)
377// ], col_wrap=true, cap2=true));
378// full = vnf_join([bottom,zrot(90,top)]);
379// vnf_polyhedron(full);
380// Example(3D,VPR=[60,0,26],VPD=55,VPT=[5.6,-5.3,9.8]): If we add enough pieces, and the pieces are all consistent with each other, then we can arrive at a valid polyhedron like this one. To be valid you need to meet all the CGAL requirements: every edge has exactly two faces, all faces are in clockwise order, no intersections of edges.
381// bottom = vnf_vertex_array([path3d(rect(8)), path3d(rect(5),4)],col_wrap=true,cap1=true);
382// triangle = yrot(-90,path3d(regular_ngon(n=3,side=5,anchor=LEFT)));
383// top = up(4,vnf_vertex_array([list_set(right(2.5,triangle),0,[0,0,7]),
384// right(6,triangle)
385// ], col_wrap=true, cap2=true));
386// full = vnf_join([bottom,
387// for(theta=[0:90:359]) zrot(theta,top)
388// ]);
389// vnf_polyhedron(full);
390// Example(3D): The vnf_join function is not a union operator for polyhedra. If any faces intersect, like they do in this example where we combine the faces of two cubes, the result is invalid and will give rise to CGAL errors when you add more objects into the model.
391// cube1 = cube(5);
392// cube2 = move([2,2,2],cube1);
393// badvnf = vnf_join([cube1,cube2]);
394// vnf_polyhedron(badvnf);
395// right(2.5)up(3)color("red")
396// text3d("Invalid",size=1,anchor=CENTER,
397// orient=FRONT,h=.1);
398function vnf_join(vnfs) =
399 assert(is_vnf_list(vnfs) , "Input must be a list of VNFs")
400 len(vnfs)==1 ? vnfs[0]
401 :
402 let (
403 offs = cumsum([ 0, for (vnf = vnfs) len(vnf[0]) ]),
404 verts = [for (vnf=vnfs) each vnf[0]],
405 faces =
406 [ for (i = idx(vnfs))
407 let( faces = vnfs[i][1] )
408 for (face = faces)
409 if ( len(face) >= 3 )
410 [ for (j = face)
411 assert( j>=0 && j<len(vnfs[i][0]),
412 str("VNF number ", i, " has a face indexing an nonexistent vertex") )
413 offs[i] + j ]
414 ]
415 )
416 [verts,faces];
417
418
419
420// Function: vnf_from_polygons()
421// Synopsis: Returns a VNF from a list of 3D polygons.
422// SynTags: VNF
423// Topics: VNF Generators, Lists
424// See Also: vnf_tri_array(), vnf_join(), vnf_vertex_array(), vnf_from_region()
425// Usage:
426// vnf = vnf_from_polygons(polygons, [eps]);
427// Description:
428// Given a list of 3D polygons, produces a VNF containing those polygons.
429// It is up to the caller to make sure that the points are in the correct order to make the face
430// normals point outwards. No checking for duplicate vertices is done. If you want to
431// remove duplicate vertices use {{vnf_merge_points()}}. Polygons with zero area are discarded from the face list by default.
432// If you give non-coplanar faces an error is displayed. These checks increase run time by about 2x for triangular polygons, but
433// about 10x for pentagons; the checks can be disabled by setting fast=true.
434// Arguments:
435// polygons = The list of 3D polygons to turn into a VNF
436// fast = Set to true to skip area and coplanarity checks for increased speed. Default: false
437// eps = Polygons with area small than this are discarded. Default: EPSILON
438function vnf_from_polygons(polygons,fast=false,eps=EPSILON) =
439 assert(is_list(polygons) && is_path(polygons[0]),"Input should be a list of polygons")
440 let(
441 offs = cumsum([0, for(p=polygons) len(p)]),
442 faces = [for(i=idx(polygons))
443 let(
444 area=fast ? 1 : polygon_area(polygons[i]),
445 dummy=assert(is_def(area) || is_collinear(polygons[i],eps=eps),str("Polygon ", i, " is not coplanar"))
446 )
447 if (is_def(area) && area > eps)
448 [for (j=idx(polygons[i])) offs[i]+j]
449 ]
450 )
451 [flatten(polygons), faces];
452
453
454
455
456function _path_path_closest_vertices(path1,path2) =
457 let(
458 dists = [for (i=idx(path1)) let(j=closest_point(path1[i],path2)) [j,norm(path2[j]-path1[i])]],
459 i1 = min_index(column(dists,1)),
460 i2 = dists[i1][0]
461 ) [dists[i1][1], i1, i2];
462
463
464function _join_paths_at_vertices(path1,path2,v1,v2) =
465 let(
466 repeat_start = !approx(path1[v1],path2[v2]),
467 path1 = clockwise_polygon(list_rotate(path1,v1)),
468 path2 = ccw_polygon(list_rotate(path2,v2))
469 )
470 [
471 each path1,
472 if (repeat_start) path1[0],
473 each path2,
474 if (repeat_start) path2[0],
475 ];
476
477
478/// Internal Function: _cleave_connected_region(region, eps)
479/// Description:
480/// Given a region that is connected and has its outer border in region[0],
481/// produces a overlapping connected path to join internal holes to
482/// the outer border without adding points. Output is a single non-simple polygon.
483/// Requirements:
484/// It expects that all region paths be simple closed paths, with region[0] CW and
485/// the other paths CCW and encircled by region[0]. The input region paths are also
486/// supposed to be disjoint except for common vertices and common edges but with
487/// no crossings. It may return `undef` if these conditions are not met.
488/// This function implements an extension of the algorithm discussed in:
489/// https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
490function _cleave_connected_region(region, eps=EPSILON) =
491 len(region)==1 ? region[0] :
492 let(
493 outer = deduplicate(region[0]), //
494 holes = [for(i=[1:1:len(region)-1]) // deduplication possibly unneeded
495 deduplicate( region[i] ) ], //
496 extridx = [for(li=holes) max_index(column(li,0)) ],
497 // the right extreme vertex for each hole sorted by decreasing x values
498 extremes = sort( [for(i=idx(holes)) [ i, extridx[i], -holes[i][extridx[i]].x] ], idx=2 )
499 )
500 _polyHoles(outer, holes, extremes, eps, 0);
501
502
503// connect the hole paths one at a time to the outer path.
504// 'extremes' is the list of the right extreme vertex of each hole sorted by decreasing abscissas
505// see: _cleave_connected_region(region, eps)
506function _polyHoles(outer, holes, extremes, eps=EPSILON, n=0) =
507 let(
508 extr = extremes[n], //
509 hole = holes[extr[0]], // hole path to bridge to the outer path
510 ipt = extr[1], // index of the hole point with maximum abscissa
511 brdg = _bridge(hole[ipt], outer, eps) // the index of a point in outer to bridge hole[ipt] to
512 )
513 brdg == undef ? undef :
514 let(
515 l = len(outer),
516 lh = len(hole),
517 // the new outer polygon bridging the hole to the old outer
518 npoly =
519 approx(outer[brdg], hole[ipt], eps)
520 ? [ for(i=[brdg: 1: brdg+l]) outer[i%l] ,
521 for(i=[ipt+1: 1: ipt+lh-1]) hole[i%lh] ]
522 : [ for(i=[brdg: 1: brdg+l]) outer[i%l] ,
523 for(i=[ipt: 1: ipt+lh]) hole[i%lh] ]
524 )
525 n==len(holes)-1 ? npoly :
526 _polyHoles(npoly, holes, extremes, eps, n+1);
527
528// find a point in outer to be connected to pt in the interior of outer
529// by a segment that not cross or touch any non adjacente edge of outer.
530// return the index of a vertex in the outer path where the bridge should end
531// see _polyHoles(outer, holes, extremes, eps)
532function _bridge(pt, outer,eps) =
533 // find the intersection of a ray from pt to the right
534 // with the boundary of the outer cycle
535 let(
536 l = len(outer),
537 crxs =
538 let( edges = pair(outer,wrap=true) )
539 [for( i = idx(edges) )
540 let( edge = edges[i] )
541 // consider just descending outer edges at right of pt crossing ordinate pt.y
542 if( (edge[0].y > pt.y) //+eps)
543 && (edge[1].y <= pt.y)
544 && _is_at_left(pt, [edge[1], edge[0]], eps) )
545 [ i,
546 // the point of edge with ordinate pt.y
547 abs(pt.y-edge[1].y)<eps ? edge[1] :
548 let( u = (pt-edge[1]).y / (edge[0]-edge[1]).y )
549 (1-u)*edge[1] + u*edge[0]
550 ]
551 ]
552 )
553 crxs == [] ? undef :
554 let(
555 // the intersection point of the nearest edge to pt with minimum slope
556 minX = min([for(p=crxs) p[1].x]),
557 crxcand = [for(crx=crxs) if(crx[1].x < minX+eps) crx ], // nearest edges
558 nearest = min_index([for(crx=crxcand)
559 (outer[crx[0]].x - pt.x) / (outer[crx[0]].y - pt.y) ]), // minimum slope
560 proj = crxcand[nearest],
561 vert0 = outer[proj[0]], // the two vertices of the nearest crossing edge
562 vert1 = outer[(proj[0]+1)%l],
563 isect = proj[1] // the intersection point
564 )
565 norm(pt-vert1) < eps ? (proj[0]+1)%l : // if pt touches an outer vertex, return its index
566 // as vert0.y > pt.y then pt!=vert0
567 norm(pt-isect) < eps ? undef : // if pt touches the middle of an outer edge -> error
568 let(
569 // the edge [vert0, vert1] necessarily satisfies vert0.y > vert1.y
570 // indices of candidates to an outer bridge point
571 cand =
572 (vert0.x > pt.x)
573 ? [ proj[0],
574 // select reflex vertices inside of the triangle [pt, vert0, isect]
575 for(i=idx(outer))
576 if( _tri_class(select(outer,i-1,i+1),eps) <= 0
577 && _pt_in_tri(outer[i], [pt, vert0, isect], eps)>=0 )
578 i
579 ]
580 : [ (proj[0]+1)%l,
581 // select reflex vertices inside of the triangle [pt, isect, vert1]
582 for(i=idx(outer))
583 if( _tri_class(select(outer,i-1,i+1),eps) <= 0
584 && _pt_in_tri(outer[i], [pt, isect, vert1], eps)>=0 )
585 i
586 ],
587 // choose the candidate outer[i] such that the line [pt, outer[i]] has minimum slope
588 // among those with minimum slope choose the nearest to pt
589 slopes = [for(i=cand) 1-abs(outer[i].x-pt.x)/norm(outer[i]-pt) ],
590 min_slp = min(slopes),
591 cand2 = [for(i=idx(cand)) if(slopes[i]<=min_slp+eps) cand[i] ],
592 nearest = min_index([for(i=cand2) norm(pt-outer[i]) ])
593 )
594 cand2[nearest];
595
596
597// Function: vnf_from_region()
598// Synopsis: Returns a 3D VNF given a 2D region.
599// SynTags: VNF
600// Topics: VNF Generators, Lists
601// See Also: vnf_vertex_array(), vnf_tri_array(), vnf_join(), vnf_from_polygons()
602// Usage:
603// vnf = vnf_from_region(region, [transform], [reverse]);
604// Description:
605// Given a (two-dimensional) region, applies the given transformation matrix to it and makes a (three-dimensional) triangulated VNF of
606// faces for that region, reversed if desired.
607// Arguments:
608// region = The region to convert to a vnf.
609// transform = If given, a transformation matrix to apply to the faces generated from the region. Default: No transformation applied.
610// reverse = If true, reverse the normals of the faces generated from the region. An untransformed region will have face normals pointing `UP`. Default: false
611// Example(3D):
612// region = [square([20,10],center=true),
613// right(5,square(4,center=true)),
614// left(5,square(6,center=true))];
615// vnf = vnf_from_region(region);
616// color("gray")down(.125)
617// linear_extrude(height=.125)region(region);
618// vnf_wireframe(vnf,width=.25);
619function vnf_from_region(region, transform, reverse=false) =
620 let (
621 region = [for (path = region) deduplicate(path, closed=true)],
622 regions = region_parts(force_region(region)),
623 vnfs =
624 [
625 for (rgn = regions)
626 let(
627 cleaved = path3d(_cleave_connected_region(rgn))
628 )
629 assert( cleaved, "The region is invalid")
630 let(
631 face = is_undef(transform)? cleaved : apply(transform,cleaved),
632 faceidxs = reverse? [for (i=[len(face)-1:-1:0]) i] : [for (i=[0:1:len(face)-1]) i]
633 ) [face, [faceidxs]]
634 ],
635 outvnf = vnf_join(vnfs)
636 )
637 vnf_triangulate(outvnf);
638
639
640
641// Section: VNF Testing and Access
642
643
644// Function: is_vnf()
645// Synopsis: Returns true given a VNF-like structure.
646// Topics: VNF Manipulation
647// See Also: is_vnf_list(), vnf_vertices(), vnf_faces()
648// Usage:
649// bool = is_vnf(x);
650// Description:
651// Returns true if the given value looks like a VNF structure.
652function is_vnf(x) =
653 is_list(x) &&
654 len(x)==2 &&
655 is_list(x[0]) &&
656 is_list(x[1]) &&
657 (x[0]==[] || (len(x[0])>=3 && is_vector(x[0][0],3))) &&
658 (x[1]==[] || is_vector(x[1][0]));
659
660
661// Function: is_vnf_list()
662// Synopsis: Returns true given a list of VNF-like structures.
663// Topics: VNF Manipulation
664// See Also: is_vnf(), vnf_vertices(), vnf_faces()
665//
666// Description: Returns true if the given value looks passingly like a list of VNF structures.
667function is_vnf_list(x) = is_list(x) && all([for (v=x) is_vnf(v)]);
668
669
670// Function: vnf_vertices()
671// Synopsis: Returns the list of vertex points from a VNF.
672// Topics: VNF Manipulation
673// See Also: is_vnf(), is_vnf_list(), vnf_faces()
674// Description: Given a VNF structure, returns the list of vertex points.
675function vnf_vertices(vnf) = vnf[0];
676
677
678// Function: vnf_faces()
679// Synopsis: Returns the list of faces from a VNF.
680// Topics: VNF Manipulation
681// See Also: is_vnf(), is_vnf_list(), vnf_vertices()
682// Description: Given a VNF structure, returns the list of faces, where each face is a list of indices into the VNF vertex list.
683function vnf_faces(vnf) = vnf[1];
684
685
686
687// Section: Altering the VNF Internals
688
689
690// Function: vnf_reverse_faces()
691// Synopsis: Reverses the faces of a VNF.
692// SynTags: VNF
693// Topics: VNF Manipulation
694// See Also: vnf_quantize(), vnf_merge_points(), vnf_drop_unused_points(), vnf_triangulate(), vnf_slice(), vnf_unify_faces()
695// Usage:
696// rvnf = vnf_reverse_faces(vnf);
697// Description:
698// Reverses the orientation of all the faces in the given VNF.
699function vnf_reverse_faces(vnf) =
700 [vnf[0], [for (face=vnf[1]) reverse(face)]];
701
702
703// Function: vnf_quantize()
704// Synopsis: Quantizes the vertex coordinates of a VNF.
705// SynTags: VNF
706// Topics: VNF Manipulation
707// See Also: vnf_reverse_faces(), vnf_merge_points(), vnf_drop_unused_points(), vnf_triangulate(), vnf_slice()
708// Usage:
709// vnf2 = vnf_quantize(vnf,[q]);
710// Description:
711// Quantizes the vertex coordinates of the VNF to the given quanta `q`.
712// Arguments:
713// vnf = The VNF to quantize.
714// q = The quanta to quantize the VNF coordinates to.
715function vnf_quantize(vnf,q=pow(2,-12)) =
716 [[for (pt = vnf[0]) quant(pt,q)], vnf[1]];
717
718
719
720// Function: vnf_merge_points()
721// Synopsis: Consolidates duplicate vertices of a VNF.
722// SynTags: VNF
723// Topics: VNF Manipulation
724// See Also: vnf_reverse_faces(), vnf_quantize(), vnf_drop_unused_points(), vnf_triangulate(), vnf_slice(), vnf_unify_faces()
725// Usage:
726// new_vnf = vnf_merge_points(vnf, [eps]);
727// Description:
728// Given a VNF, consolidates all duplicate vertices with a tolerance `eps`, relabeling the faces as necessary,
729// and eliminating any face with fewer than 3 vertices. Unreferenced vertices of the input VNF are not dropped.
730// To remove such vertices uses {{vnf_drop_unused_points()}}.
731// Arguments:
732// vnf = a VNF to consolidate
733// eps = the tolerance in finding duplicates. Default: EPSILON
734function vnf_merge_points(vnf,eps=EPSILON) =
735 let(
736 verts = vnf[0],
737 dedup = vector_search(verts,eps,verts), // collect vertex duplicates
738 map = [for(i=idx(verts)) min(dedup[i]) ], // remap duplic vertices
739 offset = cumsum([for(i=idx(verts)) map[i]==i ? 0 : 1 ]), // remaping face vertex offsets
740 map2 = list(idx(verts))-offset, // map old vertex indices to new indices
741 nverts = [for(i=idx(verts)) if(map[i]==i) verts[i] ], // this doesn't eliminate unreferenced vertices
742 nfaces =
743 [ for(face=vnf[1])
744 let(
745 nface = [ for(vi=face) map2[map[vi]] ],
746 dface = [for (i=idx(nface))
747 if( nface[i]!=nface[(i+1)%len(nface)])
748 nface[i] ]
749 )
750 if(len(dface) >= 3) dface
751 ]
752 )
753 [nverts, nfaces];
754
755
756// Function: vnf_drop_unused_points()
757// Synopsis: Removes unreferenced vertices from a VNF.
758// SynTags: VNF
759// Topics: VNF Manipulation
760// See Also: vnf_reverse_faces(), vnf_quantize(), vnf_merge_points(), vnf_triangulate(), vnf_slice(), vnf_unify_faces()
761// Usage:
762// clean_vnf = vnf_drop_unused_points(vnf);
763// Description:
764// Remove all unreferenced vertices from a VNF. Note that in most
765// cases unreferenced vertices cause no harm, and this function may
766// be slow on large VNFs.
767function vnf_drop_unused_points(vnf) =
768 let(
769 flat = flatten(vnf[1]),
770 ind = _link_indicator(flat,0,len(vnf[0])-1),
771 verts = [for(i=idx(vnf[0])) if(ind[i]==1) vnf[0][i] ],
772 map = cumsum(ind)
773 )
774 [ verts, [for(face=vnf[1]) [for(v=face) map[v]-1 ] ] ];
775
776function _link_indicator(l,imin,imax) =
777 len(l) == 0 ? repeat(imax-imin+1,0) :
778 imax-imin<100 || len(l)<400 ? [for(si=search(list([imin:1:imax]),l,1)) si!=[] ? 1: 0 ] :
779 let(
780 pivot = floor((imax+imin)/2),
781 lesser = [ for(li=l) if( li< pivot) li ],
782 greater = [ for(li=l) if( li> pivot) li ]
783 )
784 concat( _link_indicator(lesser ,imin,pivot-1),
785 search(pivot,l,1) ? 1 : 0 ,
786 _link_indicator(greater,pivot+1,imax) ) ;
787
788// Function: vnf_triangulate()
789// Synopsis: Triangulates the faces of a VNF.
790// SynTags: VNF
791// Topics: VNF Manipulation
792// See Also: vnf_reverse_faces(), vnf_quantize(), vnf_merge_points(), vnf_drop_unused_points(), vnf_slice(), vnf_unify_faces()
793// Usage:
794// vnf2 = vnf_triangulate(vnf);
795// Description:
796// Triangulates faces in the VNF that have more than 3 vertices.
797// Arguments:
798// vnf = VNF to triangulate
799// Example(3D):
800// include <BOSL2/polyhedra.scad>
801// vnf = zrot(33,regular_polyhedron_info("vnf", "dodecahedron", side=12));
802// vnf_polyhedron(vnf);
803// triangulated = vnf_triangulate(vnf);
804// color("red")vnf_wireframe(triangulated,width=.3);
805function vnf_triangulate(vnf) =
806 let(
807 verts = vnf[0],
808 faces = [for (face=vnf[1])
809 each (len(face)==3 ? [face] :
810 let( tris = polygon_triangulate(verts, face) )
811 assert( tris!=undef, "Some `vnf` face cannot be triangulated.")
812 tris ) ]
813 )
814 [verts, faces];
815
816
817
818// Function: vnf_unify_faces()
819// Synopsis: Remove triangulation from VNF, returning a copy with full faces
820// SynTags: VNF
821// Topics: VNF Manipulation
822// See Also: vnf_reverse_faces(), vnf_quantize(), vnf_merge_points(), vnf_triangulate(), vnf_slice()
823// Usage:
824// newvnf = vnf_unify_faces(vnf);
825// Description:
826// When a VNF has been triangulated, the polygons that form the true faces have been chopped up into
827// triangles. This can create problems for algorithms that operate on the VNF itself, where you might
828// want to be able to identify the true faces. This function merges together the triangles that
829// form those true faces, turning a VNF where each true face is represented by a single entry
830// in the faces list of the VNF. This function requires that the true faces have no internal vertices.
831// This will always be true for a triangulated VNF, but might fail for a VNF with some other
832// face partition. If internal vertices are present, the output will include backtracking paths from
833// the boundary to all of those vertices.
834// Arguments:
835// vnf = vnf whose faces you want to unify
836// Example(3D,Med,NoAxes): Original prism on the left is triangulated. On the right, the result of unifying the faces.
837// $fn=16;
838// poly = linear_sweep(hexagon(side=10),h=35);
839// vnf = vnf_unify_faces(poly);
840// vnf_wireframe(poly);
841// color([0,1,1,.70])vnf_polyhedron(poly);
842// right(25){
843// vnf_wireframe(vnf);
844// color([0,1,1,.70])vnf_polyhedron(vnf);
845// }
846
847function vnf_unify_faces(vnf) =
848 let(
849 faces = vnf[1],
850 edges = [for(i=idx(faces), edge=pair(faces[i],wrap=true))
851 [[min(edge),max(edge)],i]],
852 normals = [for(face=faces) polygon_normal(select(vnf[0],face))],
853 facelist = count(faces), //[for(i=[1:1:len(faces)-1]) i],
854 newfaces = _detri_combine_faces(edges,faces,normals,facelist,0)
855 )
856 [vnf[0],newfaces];
857
858
859function _detri_combine_faces(edgelist,faces,normals,facelist,curface) =
860 curface==len(faces)? select(faces,facelist)
861 : !in_list(curface,facelist) ? _detri_combine_faces(edgelist,faces,normals,facelist,curface+1)
862 :
863 let(
864 thisface=faces[curface],
865 neighbors = [for(i=idx(thisface))
866 let(
867 edgepair = search([sort(select(thisface,i,i+1))],edgelist,0)[0],
868 choices = select(edgelist,edgepair),
869 good_choice=[for(choice=choices)
870 if (choice[1]!=curface && in_list(choice[1],facelist) && normals[choice[1]]*normals[curface]>1-EPSILON)
871 choice],
872 d=assert(len(good_choice)<=1)
873 )
874 len(good_choice)==1 ? good_choice[0][1] : -1
875 ],
876 // Check for duplicates in the neighbor list so we don't add them twice
877 dups = search([for(n=neighbors) if (n>=0) n], neighbors,0),
878 goodind = column(dups,0),
879 newface = [for(i=idx(thisface))
880 each
881 !in_list(i,goodind) ? [thisface[i]]
882 :
883 let(
884 ind = search(select(thisface,i,i+1), faces[neighbors[i]])
885 )
886 select(faces[neighbors[i]],ind[0],ind[1]-1)
887 ],
888 usedfaces = [for(n=neighbors) if (n>=0) n],
889 faces = list_set(faces,curface,newface),
890 facelist = list_remove_values(facelist,usedfaces)
891 )
892 _detri_combine_faces(edgelist,faces,normals,facelist,len(usedfaces)==0?curface+1:curface);
893
894
895
896function _vnf_sort_vertices(vnf, idx=[2,1,0]) =
897 let(
898 verts = vnf[0],
899 faces = vnf[1],
900 vidx = sortidx(verts, idx=idx),
901 rvidx = sortidx(vidx),
902 sorted_vnf = [
903 [ for (i = vidx) verts[i] ],
904 [ for (face = faces) [ for (i = face) rvidx[i] ] ],
905 ]
906 ) sorted_vnf;
907
908
909
910
911// Function: vnf_slice()
912// Synopsis: Slice the faces of a VNF along an axis.
913// SynTags: VNF
914// Topics: VNF Manipulation
915// See Also: vnf_reverse_faces(), vnf_quantize(), vnf_merge_points(), vnf_drop_unused_points(), vnf_triangulate()
916// Usage:
917// sliced = vnf_slice(vnf, dir, cuts);
918// Description:
919// Slice the faces of a VNF along a specified axis direction at a given list of cut points.
920// The cut points can appear in any order. You can use this to refine the faces of a VNF before
921// applying a nonlinear transformation to its vertex set.
922// Arguments:
923// vnf = VNF to slice
924// dir = normal direction to the slices, either "X", "Y" or "Z"
925// cuts = X, Y or Z values where cuts occur
926// Example(3D):
927// include <BOSL2/polyhedra.scad>
928// vnf = regular_polyhedron_info("vnf", "dodecahedron", side=12);
929// vnf_polyhedron(vnf);
930// sliced = vnf_slice(vnf, "X", [-6,-1,10]);
931// color("red")vnf_wireframe(sliced,width=.3);
932function vnf_slice(vnf,dir,cuts) =
933 let(
934 // Code below seems to be unnecessary
935 //cuts = [for (cut=cuts) _shift_cut_plane(vnf,dir,cut)],
936 vert = vnf[0],
937 faces = [for(face=vnf[1]) select(vert,face)],
938 poly_list = _slice_3dpolygons(faces, dir, cuts)
939 )
940 vnf_merge_points(vnf_from_polygons(poly_list));
941
942
943function _shift_cut_plane(vnf,dir,cut,off=0.001) =
944 let(
945 I = ident(3),
946 dir_ind = ord(dir)-ord("X"),
947 verts = vnf[0],
948 on_cut = [for (x = verts * I[dir_ind]) if(approx(x,cut,eps=1e-4)) 1] != []
949 ) !on_cut? cut :
950 _shift_cut_plane(vnf,dir,cut+off);
951
952
953function _split_polygon_at_x(poly, x) =
954 let(
955 xs = column(poly,0)
956 ) (min(xs) >= x || max(xs) <= x)? [poly] :
957 let(
958 poly2 = [
959 for (p = pair(poly,true)) each [
960 p[0],
961 if(
962 (p[0].x < x && p[1].x > x) ||
963 (p[1].x < x && p[0].x > x)
964 ) let(
965 u = (x - p[0].x) / (p[1].x - p[0].x)
966 ) [
967 x, // Important for later exact match tests
968 u*(p[1].y-p[0].y)+p[0].y
969 ]
970 ]
971 ],
972 out1 = [for (p = poly2) if(p.x <= x) p],
973 out2 = [for (p = poly2) if(p.x >= x) p],
974 out3 = [
975 if (len(out1)>=3) each split_path_at_self_crossings(out1),
976 if (len(out2)>=3) each split_path_at_self_crossings(out2),
977 ],
978 out = [for (p=out3) if (len(p) > 2) list_unwrap(p)]
979 ) out;
980
981
982function _split_2dpolygons_at_each_x(polys, xs, _i=0) =
983 _i>=len(xs)? polys :
984 _split_2dpolygons_at_each_x(
985 [
986 for (poly = polys)
987 each _split_polygon_at_x(poly, xs[_i])
988 ], xs, _i=_i+1
989 );
990
991/// Internal Function: _slice_3dpolygons()
992/// Usage:
993/// splitpolys = _slice_3dpolygons(polys, dir, cuts);
994/// Topics: Geometry, Polygons, Intersections
995/// Description:
996/// Given a list of 3D polygons, a choice of X, Y, or Z, and a cut list, `cuts`, splits all of the polygons where they cross
997/// X/Y/Z at any value given in cuts.
998/// Arguments:
999/// polys = A list of 3D polygons to split.
1000/// dir_ind = slice direction, 0=X, 1=Y, or 2=Z
1001/// cuts = A list of scalar values for locating the cuts
1002function _slice_3dpolygons(polys, dir, cuts) =
1003 assert( [for (poly=polys) if (!is_path(poly,3)) 1] == [], "Expects list of 3D paths.")
1004 assert( is_vector(cuts), "The split list must be a vector.")
1005 assert( in_list(dir, ["X", "Y", "Z"]))
1006 let(
1007 I = ident(3),
1008 dir_ind = ord(dir)-ord("X")
1009 )
1010 flatten([
1011 for (poly = polys)
1012 if (polygon_area(poly)>EPSILON) // Discard zero area polygons
1013 let(
1014 plane = plane_from_polygon(poly,1e-4))
1015 assert(plane,"Found non-coplanar face.")
1016 let(
1017 normal = point3d(plane),
1018 pnormal = normal - (normal*I[dir_ind])*I[dir_ind]
1019 )
1020 approx(pnormal,[0,0,0]) ? [poly] // Polygons parallel to cut plane just pass through
1021 : let(
1022 pind = max_index(v_abs(pnormal)), // project along this direction
1023 otherind = 3-pind-dir_ind, // keep dir_ind and this direction
1024 keep = [I[dir_ind], I[otherind]], // dir ind becomes the x dir
1025 poly2d = poly*transpose(keep), // project to 2d, putting selected direction in the X position
1026 poly_list = [for(p=_split_2dpolygons_at_each_x([poly2d], cuts))
1027 let(
1028 a = p*keep, // unproject, but pind dimension data is missing
1029 ofs = outer_product((repeat(plane[3], len(a))-a*normal)/plane[pind],I[pind])
1030 )
1031 a+ofs] // ofs computes the missing pind dimension data and adds it back in
1032 )
1033 poly_list
1034 ]);
1035
1036
1037
1038
1039
1040// Section: Turning a VNF into geometry
1041
1042
1043// Module: vnf_polyhedron()
1044// Synopsis: Returns a polyhedron from a VNF or list of VNFs.
1045// SynTags: Geom
1046// Topics: VNF Manipulation
1047// See Also: vnf_wireframe()
1048// Usage:
1049// vnf_polyhedron(vnf) [ATTACHMENTS];
1050// vnf_polyhedron([VNF, VNF, VNF, ...]) [ATTACHMENTS];
1051// Description:
1052// Given a VNF structure, or a list of VNF structures, creates a polyhedron from them.
1053// Arguments:
1054// vnf = A VNF structure, or list of VNF structures.
1055// convexity = Max number of times a line could intersect a wall of the shape.
1056// cp = Centerpoint for determining intersection anchors or centering the shape. Determintes the base of the anchor vector. Can be "centroid", "mean", "box" or a 3D point. Default: "centroid"
1057// anchor = Translate so anchor point is at origin (0,0,0). See [anchor](attachments.scad#subsection-anchor). Default: `"origin"`
1058// spin = Rotate this many degrees around the Z axis after anchor. See [spin](attachments.scad#subsection-spin). Default: `0`
1059// orient = Vector to rotate top towards, after spin. See [orient](attachments.scad#subsection-orient). Default: `UP`
1060// atype = Select "hull" or "intersect" anchor type. Default: "hull"
1061// Anchor Types:
1062// "hull" = Anchors to the virtual convex hull of the shape.
1063// "intersect" = Anchors to the surface of the shape.
1064// Extra Anchors:
1065// "origin" = Anchor at the origin, oriented UP.
1066module vnf_polyhedron(vnf, convexity=2, cp="centroid", anchor="origin", spin=0, orient=UP, atype="hull") {
1067 vnf = is_vnf_list(vnf)? vnf_join(vnf) : vnf;
1068 assert(in_list(atype, _ANCHOR_TYPES), "Anchor type must be \"hull\" or \"intersect\"");
1069 attachable(anchor,spin,orient, vnf=vnf, extent=atype=="hull", cp=cp) {
1070 polyhedron(vnf[0], vnf[1], convexity=convexity);
1071 children();
1072 }
1073}
1074
1075
1076// Module: vnf_wireframe()
1077// Synopsis: Creates a wireframe model from a VNF.
1078// SynTags: VNF
1079// Topics: VNF Manipulation
1080// See Also: vnf_polyhedron()
1081// Usage:
1082// vnf_wireframe(vnf, [width]);
1083// Description:
1084// Given a VNF, creates a wire frame ball-and-stick model of the polyhedron with a cylinder for
1085// each edge and a sphere at each vertex. The width parameter specifies the width of the sticks
1086// that form the wire frame and the diameter of the balls.
1087// Arguments:
1088// vnf = A vnf structure
1089// width = width of the cylinders forming the wire frame. Default: 1
1090// Example:
1091// $fn=32;
1092// ball = sphere(r=20, $fn=6);
1093// vnf_wireframe(ball,width=1);
1094// Example:
1095// include <BOSL2/polyhedra.scad>
1096// $fn=32;
1097// cube_oct = regular_polyhedron_info("vnf",
1098// name="cuboctahedron", or=20);
1099// vnf_wireframe(cube_oct);
1100// Example: The spheres at the vertex are imperfect at aligning with the cylinders, so especially at low $fn things look prety ugly. This is normal.
1101// include <BOSL2/polyhedra.scad>
1102// $fn=8;
1103// octahedron = regular_polyhedron_info("vnf",
1104// name="octahedron", or=20);
1105// vnf_wireframe(octahedron,width=5);
1106module vnf_wireframe(vnf, width=1)
1107{
1108 no_children($children);
1109 vertex = vnf[0];
1110 edges = unique([for (face=vnf[1], i=idx(face))
1111 sort([face[i], select(face,i+1)])
1112 ]);
1113 attachable()
1114 {
1115 union(){
1116 for (e=edges) extrude_from_to(vertex[e[0]],vertex[e[1]]) circle(d=width);
1117 // Identify vertices actually used and draw them
1118 vertused = search(count(len(vertex)), flatten(edges), 1);
1119 for(i=idx(vertex)) if(vertused[i]!=[]) move(vertex[i]) sphere(d=width);
1120 }
1121 union();
1122 }
1123}
1124
1125
1126// Section: Operations on VNFs
1127
1128// Function: vnf_volume()
1129// Synopsis: Returns the volume of a VNF.
1130// Topics: VNF Manipulation
1131// See Also: vnf_area(), vnf_halfspace(), vnf_bend()
1132// Usage:
1133// vol = vnf_volume(vnf);
1134// Description:
1135// Returns the volume enclosed by the given manifold VNF. The VNF must describe a valid polyhedron with consistent face direction and
1136// no holes; otherwise the results are undefined. Returns a positive volume if face direction is clockwise and a negative volume
1137// if face direction is counter-clockwise.
1138
1139// Divide the polyhedron into tetrahedra with the origin as one vertex and sum up the signed volume.
1140function vnf_volume(vnf) =
1141 let(verts = vnf[0])
1142 sum([
1143 for(face=vnf[1], j=[1:1:len(face)-2])
1144 cross(verts[face[j+1]], verts[face[j]]) * verts[face[0]]
1145 ])/6;
1146
1147
1148// Function: vnf_area()
1149// Synopsis: Returns the surface area of a VNF.
1150// Topics: VNF Manipulation
1151// See Also: vnf_volume(), vnf_halfspace(), vnf_bend()
1152// Usage:
1153// area = vnf_area(vnf);
1154// Description:
1155// Returns the surface area in any VNF by adding up the area of all its faces. The VNF need not be a manifold.
1156function vnf_area(vnf) =
1157 let(verts=vnf[0])
1158 sum([for(face=vnf[1]) polygon_area(select(verts,face))]);
1159
1160
1161/// Internal Function: _vnf_centroid()
1162/// Usage:
1163/// vol = _vnf_centroid(vnf);
1164/// Description:
1165/// Returns the centroid of the given manifold VNF. The VNF must describe a valid polyhedron with consistent face direction and
1166/// no holes; otherwise the results are undefined.
1167
1168/// Divide the solid up into tetrahedra with the origin as one vertex.
1169/// The centroid of a tetrahedron is the average of its vertices.
1170/// The centroid of the total is the volume weighted average.
1171function _vnf_centroid(vnf,eps=EPSILON) =
1172 assert(is_vnf(vnf) && len(vnf[0])!=0 && len(vnf[1])!=0,"Invalid or empty VNF given to centroid")
1173 let(
1174 verts = vnf[0],
1175 pos = sum([
1176 for(face=vnf[1], j=[1:1:len(face)-2]) let(
1177 v0 = verts[face[0]],
1178 v1 = verts[face[j]],
1179 v2 = verts[face[j+1]],
1180 vol = cross(v2,v1)*v0
1181 )
1182 [ vol, (v0+v1+v2)*vol ]
1183 ])
1184 )
1185 assert(!approx(pos[0],0, eps), "The vnf has self-intersections.")
1186 pos[1]/pos[0]/4;
1187
1188
1189// Function: vnf_halfspace()
1190// Synopsis: Returns the intersection of the vnf with a half space.
1191// SynTags: VNF
1192// Topics: VNF Manipulation
1193// See Also: vnf_volume(), vnf_area(), vnf_bend()
1194// Usage:
1195// newvnf = vnf_halfspace(plane, vnf, [closed], [boundary]);
1196// Description:
1197// Returns the intersection of the vnf with a half space. The half space is defined by
1198// plane = [A,B,C,D], taking the side where the normal [A,B,C] points: Ax+By+Cz≥D.
1199// If closed is set to false then the cut face is not included in the vnf. This could
1200// allow further extension of the vnf by join with other vnfs using {{vnf_join()}}.
1201// Note that if your given VNF has holes (missing faces) or is not a complete polyhedron
1202// then closed=true is may produce invalid results when it tries to construct closing faces
1203// on the cut plane. Set closed=false for such inputs.
1204// .
1205// If you set boundary to true then the return will be the pair [vnf,boundary] where vnf is the
1206// vnf as usual (with closed=false) and boundary is a list giving each connected component of the cut
1207// boundary surface. Each entry in boundary is a list of index values that index into the vnf vertex list (vnf[0]).
1208// This makes it possible to construct mating shapes, e.g. with {{skin()}} or {{vnf_vertex_array()}} that
1209// can be combined using {{vnf_join()}} to make a valid polyhedron.
1210// .
1211// Note that the input to vnf_halfspace() does not need to be a closed, manifold polyhedron.
1212// Because it adds the faces on the cut surface, you can use vnf_halfspace() to cap off an open shape if you
1213// slice through a region that excludes all of the gaps in the input VNF.
1214// Arguments:
1215// plane = plane defining the boundary of the half space
1216// vnf = VNF to cut
1217// closed = if false do not return the cut face(s) in the returned VNF. Default: true
1218// boundary = if true return a pair [vnf,boundary] where boundary is a list of paths on the cut boundary indexed into the VNF vertex list. If boundary is true, then closed is set to false. Default: false
1219// Example(3D):
1220// vnf = cube(10,center=true);
1221// cutvnf = vnf_halfspace([-1,1,-1,0], vnf);
1222// vnf_polyhedron(cutvnf);
1223// Example(3D): Cut face has 2 components
1224// vnf = path_sweep(circle(r=4, $fn=16),
1225// circle(r=20, $fn=64),closed=true);
1226// cutvnf = vnf_halfspace([-1,1,-4,0], vnf);
1227// vnf_polyhedron(cutvnf);
1228// Example(3D): Cut face is not simply connected
1229// vnf = path_sweep(circle(r=4, $fn=16),
1230// circle(r=20, $fn=64),closed=true);
1231// cutvnf = vnf_halfspace([0,0.7,-4,0], vnf);
1232// vnf_polyhedron(cutvnf);
1233// Example(3D): Cut object has multiple components
1234// function knot(a,b,t) = // rolling knot
1235// [ a * cos (3 * t) / (1 - b* sin (2 *t)),
1236// a * sin( 3 * t) / (1 - b* sin (2 *t)),
1237// 1.8 * b * cos (2 * t) /(1 - b* sin (2 *t))];
1238// a = 0.8; b = sqrt (1 - a * a);
1239// ksteps = 400;
1240// knot_path = [for (i=[0:ksteps-1]) 50 * knot(a,b,(i/ksteps)*360)];
1241// ushape = [[-10, 0],[-10, 10],[ -7, 10],[ -7, 2],[ 7, 2],[ 7, 7],[ 10, 7],[ 10, 0]];
1242// knot=path_sweep(ushape, knot_path, closed=true, method="incremental");
1243// cut_knot = vnf_halfspace([1,0,0,0], knot);
1244// vnf_polyhedron(cut_knot);
1245// Example(VPR=[80,0,15]): Cut a sphere with an arbitrary plane
1246// vnf1=sphere(r=50, style="icosa", $fn=16);
1247// vnf2=vnf_halfspace([.8,1,-1.5,0], vnf1);
1248// vnf_polyhedron(vnf2);
1249// Example(VPR=[80,0,15]): Cut it again, but with closed=false to leave an open boundary.
1250// vnf1=sphere(r=50, style="icosa", $fn=16);
1251// vnf2=vnf_halfspace([.8,1,-1.5,0], vnf1);
1252// vnf3=vnf_halfspace([0,0,-1,0], vnf2, closed=false);
1253// vnf_polyhedron(vnf3);
1254// Example(VPR=[80,0,15]): Use {vnf_join()} to combine with a mating vnf, in this case a reflection of the part we made.
1255// vnf1=sphere(r=50, style="icosa", $fn=16);
1256// vnf2=vnf_halfspace([.8,1,-1.5,0], vnf1);
1257// vnf3=vnf_halfspace([0,0,-1,0], vnf2, closed=false);
1258// vnf4=vnf_join([vnf3, zflip(vnf3,1)]);
1259// vnf_polyhedron(vnf4);
1260// Example: When the input VNF is a surface with a boundary, if you use the default setting closed=true, then vnf_halfspace() tries to construct closing faces from the edges created by the cut. These faces may be invalid, for example if the cut points are collinear. In this example the constructed face is a valid face.
1261// include <BOSL2/beziers.scad>
1262// patch=[
1263// [[10,-10,0],[1,-1,0],[-1,-1,0],[-10,-10,0]],
1264// [[10,-10,20],[1,-1,20],[-1,-1,20],[-10,-10,20]]
1265// ];
1266// vnf=bezier_vnf(patch);
1267// vnfcut = vnf_halfspace([-.8,0,-1,-14],vnf);
1268// vnf_polyhedron(vnfcut);
1269// Example: Setting closed to false eliminates this (possibly invalid) face:
1270// include <BOSL2/beziers.scad>
1271// patch=[
1272// [[10,-10,0],[1,-1,0],[-1,-1,0],[-10,-10,0]],
1273// [[10,-10,20],[1,-1,20],[-1,-1,20],[-10,-10,20]]
1274// ];
1275// vnf=bezier_vnf(patch);
1276// vnfcut = vnf_halfspace([-.8,0,-1,-14],vnf,closed=false);
1277// vnf_polyhedron(vnfcut);
1278// Example: Here is a VNF that has holes, so it is not a valid manifold.
1279// outside = linear_sweep(circle(r=30), h=100, caps=false);
1280// inside = yrot(7,linear_sweep(circle(r=10), h=120, caps=false));
1281// open_vnf=vnf_join([outside, vnf_reverse_faces(inside)]);
1282// vnf_polyhedron(open_vnf);
1283// Example: By cutting it at each end we can create closing faces, resulting in a valid manifold without holes.
1284// outside = linear_sweep(circle(r=30), h=100, caps=false);
1285// inside = yrot(11,linear_sweep(circle(r=10), h=120, caps=false));
1286// open_vnf=vnf_join([outside, vnf_reverse_faces(inside)]);
1287// vnf = vnf_halfspace([0,0,1,5], vnf_halfspace([0,.7,-1,-75], open_vnf));
1288// vnf_polyhedron(vnf);
1289// Example: If boundary=true then the return is a list with the VNF and boundary data.
1290// vnf = path_sweep(circle(r=4, $fn=16),
1291// circle(r=20, $fn=64),closed=true);
1292// cut_bnd = vnf_halfspace([-1,1,-4,0], vnf, boundary=true);*/
1293// cutvnf = cut_bnd[0];
1294// boundary = [for(b=cut_bnd[1]) select(cutvnf[0],b)];
1295// vnf_polyhedron(cutvnf);
1296// stroke(boundary,color="red");
1297function vnf_halfspace(plane, vnf, closed=true, boundary=false) =
1298 assert(_valid_plane(plane), "Invalid plane")
1299 assert(is_vnf(vnf), "Invalid vnf")
1300 let(
1301 inside = [for(x=vnf[0]) plane*[each x,-1] >= -EPSILON ? 1 : 0],
1302 vertexmap = [0,each cumsum(inside)],
1303 faces_edges_vertices = _vnfcut(plane, vnf[0],vertexmap,inside, vnf[1], last(vertexmap)),
1304 newvert = concat(bselect(vnf[0],inside), faces_edges_vertices[2])
1305 )
1306 closed==false && !boundary ? [newvert, faces_edges_vertices[0]]
1307 : let(
1308 allpaths = _assemble_paths(newvert, faces_edges_vertices[1]),
1309 newpaths = [for(p=allpaths) if (len(p)>=3) p
1310 else assert(approx(p[0],p[1]),"Orphan edge found when assembling cut edges.")
1311 ]
1312 )
1313 boundary ? [[newvert, faces_edges_vertices[0]], newpaths]
1314 : len(newpaths)<=1 ? [newvert, concat(faces_edges_vertices[0], newpaths)]
1315 : let(
1316 M = project_plane(plane),
1317 faceregion = [for(path=newpaths) path2d(apply(M,select(newvert,path)))],
1318 facevnf = vnf_from_region(faceregion,transform=rot_inverse(M),reverse=true)
1319 )
1320 vnf_join([[newvert, faces_edges_vertices[0]], facevnf]);
1321
1322function _assemble_paths(vertices, edges, paths=[],i=0) =
1323 i==len(edges) ? paths :
1324 norm(vertices[edges[i][0]]-vertices[edges[i][1]])<EPSILON ? _assemble_paths(vertices,edges,paths,i+1) :
1325 let( // Find paths that connects on left side and right side of the edges (if one exists)
1326 left = [for(j=idx(paths)) if (approx(vertices[last(paths[j])],vertices[edges[i][0]])) j],
1327 right = [for(j=idx(paths)) if (approx(vertices[edges[i][1]],vertices[paths[j][0]])) j]
1328 )
1329 assert(len(left)<=1 && len(right)<=1)
1330 let(
1331 keep_path = list_remove(paths,concat(left,right)),
1332 update_path = left==[] && right==[] ? edges[i]
1333 : left==[] ? concat([edges[i][0]],paths[right[0]])
1334 : right==[] ? concat(paths[left[0]],[edges[i][1]])
1335 : left != right ? concat(paths[left[0]], paths[right[0]])
1336 : paths[left[0]]
1337 )
1338 _assemble_paths(vertices, edges, concat(keep_path, [update_path]), i+1);
1339
1340
1341function _vnfcut(plane, vertices, vertexmap, inside, faces, vertcount, newfaces=[], newedges=[], newvertices=[], i=0) =
1342 i==len(faces) ? [newfaces, newedges, newvertices] :
1343 let(
1344 pts_inside = select(inside,faces[i])
1345 )
1346 all(pts_inside) ? _vnfcut(plane, vertices, vertexmap, inside, faces, vertcount,
1347 concat(newfaces, [select(vertexmap,faces[i])]), newedges, newvertices, i+1):
1348 !any(pts_inside) ? _vnfcut(plane, vertices, vertexmap,inside, faces, vertcount, newfaces, newedges, newvertices, i+1):
1349 let(
1350 first = search([[1,0]],pair(pts_inside,wrap=true),0)[0],
1351 second = search([[0,1]],pair(pts_inside,wrap=true),0)[0]
1352 )
1353 assert(len(first)==1 && len(second)==1, "Found concave face in VNF. Run vnf_triangulate first to ensure convex faces.")
1354 let(
1355 newface = [each select(vertexmap,select(faces[i],second[0]+1,first[0])),vertcount, vertcount+1],
1356 newvert = [plane_line_intersection(plane, select(vertices,select(faces[i],first[0],first[0]+1)),eps=0),
1357 plane_line_intersection(plane, select(vertices,select(faces[i],second[0],second[0]+1)),eps=0)]
1358 )
1359 true //!approx(newvert[0],newvert[1])
1360 ? _vnfcut(plane, vertices, vertexmap, inside, faces, vertcount+2,
1361 concat(newfaces, [newface]), concat(newedges,[[vertcount+1,vertcount]]),concat(newvertices,newvert),i+1)
1362 :len(newface)>3
1363 ? _vnfcut(plane, vertices, vertexmap, inside, faces, vertcount+1,
1364 concat(newfaces, [list_head(newface)]), newedges,concat(newvertices,[newvert[0]]),i+1)
1365 :
1366 _vnfcut(plane, vertices, vertexmap, inside, faces, vertcount,newfaces, newedges, newvert, i+1);
1367
1368
1369
1370
1371function _triangulate_planar_convex_polygons(polys) =
1372 polys==[]? [] :
1373 let(
1374 tris = [for (poly=polys) if (len(poly)==3) poly],
1375 bigs = [for (poly=polys) if (len(poly)>3) poly],
1376 newtris = [for (poly=bigs) select(poly,-2,0)],
1377 newbigs = [for (poly=bigs) select(poly,0,-2)],
1378 newtris2 = _triangulate_planar_convex_polygons(newbigs),
1379 outtris = concat(tris, newtris, newtris2)
1380 ) outtris;
1381
1382//**
1383// this function may produce degenerate triangles:
1384// _triangulate_planar_convex_polygons([ [for(i=[0:1]) [i,i],
1385// [1,-1], [-1,-1],
1386// for(i=[-1:0]) [i,i] ] ] )
1387// == [[[-1, -1], [ 0, 0], [0, 0]]
1388// [[-1, -1], [-1, -1], [0, 0]]
1389// [[ 1, -1], [-1, -1], [0, 0]]
1390// [[ 0, 0], [ 1, 1], [1, -1]] ]
1391//
1392
1393// Function: vnf_bend()
1394// Synopsis: Bends a VNF around an axis.
1395// SynTags: VNF
1396// Topics: VNF Manipulation
1397// See Also: vnf_volume(), vnf_area(), vnf_halfspace()
1398// Usage:
1399// bentvnf = vnf_bend(vnf,r|d=,[axis=]);
1400// Description:
1401// Bend a VNF around the X, Y or Z axis, splitting up faces as necessary. Returns the bent
1402// VNF. For bending around the Z axis the input VNF must not cross the Y=0 plane. For bending
1403// around the X or Y axes the VNF must not cross the Z=0 plane. Note that if you wrap a VNF all the way around
1404// it may intersect itself, which produces an invalid polyhedron. It is your responsibility to
1405// avoid this situation. The 1:1
1406// radius is where the curved length of the bent VNF matches the length of the original VNF. If the
1407// `r` or `d` arguments are given, then they will specify the 1:1 radius or diameter. If they are
1408// not given, then the 1:1 radius will be defined by the distance of the furthest vertex in the
1409// original VNF from the Z=0 plane. You can adjust the granularity of the bend using the standard
1410// `$fa`, `$fs`, and `$fn` variables.
1411// Arguments:
1412// vnf = The original VNF to bend.
1413// r = If given, the radius where the size of the original shape is the same as in the original.
1414// ---
1415// d = If given, the diameter where the size of the original shape is the same as in the original.
1416// axis = The axis to wrap around. "X", "Y", or "Z". Default: "Z"
1417// Example(3D):
1418// vnf0 = cube([100,40,10], center=true);
1419// vnf1 = up(50, p=vnf0);
1420// vnf2 = down(50, p=vnf0);
1421// bent1 = vnf_bend(vnf1, axis="Y");
1422// bent2 = vnf_bend(vnf2, axis="Y");
1423// vnf_polyhedron([bent1,bent2]);
1424// Example(3D):
1425// vnf0 = linear_sweep(star(n=5,step=2,d=100), height=10);
1426// vnf1 = up(50, p=vnf0);
1427// vnf2 = down(50, p=vnf0);
1428// bent1 = vnf_bend(vnf1, axis="Y");
1429// bent2 = vnf_bend(vnf2, axis="Y");
1430// vnf_polyhedron([bent1,bent2]);
1431// Example(3D):
1432// rgn = union(rect([100,20]),
1433// rect([20,100]));
1434// vnf0 = linear_sweep(zrot(45,p=rgn), height=10);
1435// vnf1 = up(50, p=vnf0);
1436// vnf2 = down(50, p=vnf0);
1437// bent1 = vnf_bend(vnf1, axis="Y");
1438// bent2 = vnf_bend(vnf2, axis="Y");
1439// vnf_polyhedron([bent1,bent2]);
1440// Example(3D): Bending Around X Axis.
1441// rgnr = union(
1442// rect([20,100]),
1443// back(50, p=trapezoid(w1=40, w2=0, h=20, anchor=FRONT))
1444// );
1445// vnf0 = xrot(00,p=linear_sweep(rgnr, height=10));
1446// vnf1 = up(50, p=vnf0);
1447// #vnf_polyhedron(vnf1);
1448// bent1 = vnf_bend(vnf1, axis="X");
1449// vnf_polyhedron([bent1]);
1450// Example(3D): Bending Around Y Axis.
1451// rgn = union(
1452// rect([20,100]),
1453// back(50, p=trapezoid(w1=40, w2=0, h=20, anchor=FRONT))
1454// );
1455// rgnr = zrot(-90, p=rgn);
1456// vnf0 = xrot(00,p=linear_sweep(rgnr, height=10));
1457// vnf1 = up(50, p=vnf0);
1458// #vnf_polyhedron(vnf1);
1459// bent1 = vnf_bend(vnf1, axis="Y");
1460// vnf_polyhedron([bent1]);
1461// Example(3D): Bending Around Z Axis.
1462// rgn = union(
1463// rect([20,100]),
1464// back(50, p=trapezoid(w1=40, w2=0, h=20, anchor=FRONT))
1465// );
1466// rgnr = zrot(90, p=rgn);
1467// vnf0 = xrot(90,p=linear_sweep(rgnr, height=10));
1468// vnf1 = fwd(50, p=vnf0);
1469// #vnf_polyhedron(vnf1);
1470// bent1 = vnf_bend(vnf1, axis="Z");
1471// vnf_polyhedron([bent1]);
1472// Example(3D): Bending more than once around the cylinder
1473// $fn=32;
1474// vnf = apply(fwd(5)*yrot(30),cube([100,2,5],center=true));
1475// bent = vnf_bend(vnf, axis="Z");
1476// vnf_polyhedron(bent);
1477function vnf_bend(vnf,r,d,axis="Z") =
1478 let(
1479 chk_axis = assert(in_list(axis,["X","Y","Z"])),
1480 verts = vnf[0],
1481 bounds = pointlist_bounds(verts),
1482 bmin = bounds[0],
1483 bmax = bounds[1],
1484 dflt = axis=="Z"?
1485 max(abs(bmax.y), abs(bmin.y)) :
1486 max(abs(bmax.z), abs(bmin.z)),
1487 r = get_radius(r=r,d=d,dflt=dflt),
1488 extent = axis=="X" ? [bmin.y, bmax.y] : [bmin.x, bmax.x]
1489 )
1490 let(
1491 span_chk = axis=="Z"?
1492 assert(bmin.y > 0 || bmax.y < 0, "Entire shape MUST be completely in front of or behind y=0.") :
1493 assert(bmin.z > 0 || bmax.z < 0, "Entire shape MUST be completely above or below z=0."),
1494 steps = 1+ceil(segs(r) * (extent[1]-extent[0])/(2*PI*r)),
1495 step = (extent[1]-extent[0]) / steps,
1496 bend_at = [for(i = [1:1:steps-1]) i*step+extent[0]],
1497 slicedir = axis=="X"? "Y" : "X", // slice in y dir for X axis case, and x dir otherwise
1498 sliced = vnf_slice(vnf, slicedir, bend_at),
1499 coord = axis=="X" ? [0,sign(bmax.z),0] : axis=="Y" ? [sign(bmax.z),0,0] : [sign(bmax.y),0,0],
1500 new_vert = [for(p=sliced[0])
1501 let(a=coord*p*180/(PI*r))
1502 axis=="X"? [p.x, p.z*sin(a), p.z*cos(a)] :
1503 axis=="Y"? [p.z*sin(a), p.y, p.z*cos(a)] :
1504 [p.y*sin(a), p.y*cos(a), p.z]]
1505 ) [new_vert,sliced[1]];
1506
1507
1508
1509// Function&Module: vnf_hull()
1510// Synopsis: Compute convex hull of VNF or 3d path
1511// Usage:
1512// vnf_hull = hull_vnf(vnf);
1513// hull_vnf(vnf,[fast]);
1514// Description:
1515// Given a VNF or a list of 3d points, compute the convex hull
1516// and return it as a VNF. This differs from {{hull()}} and {{hull3d_faces()}} which
1517// return just the face list referenced to the input point list. Note that the point
1518// list that is returned will contain all the points that are actually used in the input
1519// VNF, which may be many more points than are needed to represent the convex hull.
1520// This is not usually a problem, but you can run the somewhat slow {{vnf_drop_unused_points()}}
1521// function to fix this if necessary.
1522// Arguments:
1523// region = region or path listing points to compute the hull from.
1524// fast = (module only) if input is a point list (not a VNF) use a fasterer cheat that may handle more points, but could emit warnings. Ignored if input is a VNF. Default: false.
1525// Example(3D,Big,NoAxes,VPR=[55,0,25],VPT=[9.47096,-4.50217,8.45727],VPD=60.2654): Input is a VNF
1526// ellipse = xscale(2, p=circle($fn=48, r=3));
1527// pentagon = subdivide_path(pentagon(r=1), 20);
1528// vnf=path_sweep(pentagon, path3d(ellipse),
1529// closed=true, twist=360*2);
1530// vnfhull = vnf_hull(vnf);
1531// vnf_polyhedron(vnf);
1532// move([10,10])
1533// vnf_polyhedron(vnfhull);
1534// Example(3D,Med,NoAxes,VPR=[70.4,0,110.4],VPT=[5.97456,1.26459,18.0317],VPD=126): Input is a point list
1535// h=helix(l=40, turns=1, r=8);
1536// color("red")move_copies(h)
1537// sphere(r=0.5,$fn=12);
1538// vnf_polyhedron(vnf_hull(h));
1539function vnf_hull(vnf) =
1540 assert(is_vnf(vnf) || is_path(vnf,3),"Input must be a VNF or a 3d path")
1541 let(
1542 pts = is_vnf(vnf) ? select(vnf[0],unique(flatten(vnf[1])))
1543 : vnf,
1544 faces = hull3d_faces(pts)
1545 )
1546 [pts, faces];
1547
1548module vnf_hull(vnf, fast=false)
1549{
1550 if (is_vnf(vnf)) hull()vnf_polyhedron(vnf);
1551 else hull_points(vnf, fast);
1552}
1553
1554
1555// Section: Debugging Polyhedrons
1556
1557/// Internal Module: _show_vertices()
1558/// Usage:
1559/// _show_vertices(vertices, [size], [filter=])
1560/// Description:
1561/// Draws all the vertices in an array, at their 3D position, numbered by their
1562/// position in the vertex array. Also draws any children of this module with
1563/// transparency.
1564/// Arguments:
1565/// vertices = Array of point vertices.
1566/// size = The size of the text used to label the vertices. Default: 1
1567/// Example:
1568/// verts = [for (z=[-10,10], y=[-10,10], x=[-10,10]) [x,y,z]];
1569/// faces = [[0,1,2], [1,3,2], [0,4,5], [0,5,1], [1,5,7], [1,7,3], [3,7,6], [3,6,2], [2,6,4], [2,4,0], [4,6,7], [4,7,5]];
1570/// _show_vertices(vertices=verts, size=2) {
1571/// polyhedron(points=verts, faces=faces);
1572/// }
1573module _show_vertices(vertices, size=1, filter) {
1574 color("blue") {
1575 dups = vector_search(vertices, EPSILON, vertices);
1576 for (ind = dups) {
1577 if (is_undef(filter) || any(ind, filter)) {
1578 numstr = str_join([for(i=ind) str(i)],",");
1579 v = vertices[ind[0]];
1580 translate(v) {
1581 rot($vpr) back(size/8){
1582 linear_extrude(height=size/10, center=true, convexity=10) {
1583 text(text=numstr, size=size, halign="center");
1584 }
1585 }
1586 sphere(size/10);
1587 }
1588 }
1589 }
1590 }
1591}
1592
1593
1594/// Internal Module: _show_faces()
1595/// Usage:
1596/// _show_faces(vertices, faces, [size=], [filter=]);
1597/// Description:
1598/// Draws all the vertices at their 3D position, numbered in blue by their
1599/// position in the vertex array. Each face will have their face number drawn
1600/// in red, aligned with the center of face. All children of this module are drawn
1601/// with transparency.
1602/// Arguments:
1603/// vertices = Array of point vertices.
1604/// faces = Array of faces by vertex numbers.
1605/// size = The size of the text used to label the faces and vertices. Default: 1
1606/// Example(EdgesMed):
1607/// verts = [for (z=[-10,10], y=[-10,10], x=[-10,10]) [x,y,z]];
1608/// faces = [[0,1,2], [1,3,2], [0,4,5], [0,5,1], [1,5,7], [1,7,3], [3,7,6], [3,6,2], [2,6,4], [2,4,0], [4,6,7], [4,7,5]];
1609/// _show_faces(vertices=verts, faces=faces, size=2) {
1610/// polyhedron(points=verts, faces=faces);
1611/// }
1612module _show_faces(vertices, faces, size=1, filter) {
1613 vlen = len(vertices);
1614 color("red") {
1615 for (i = [0:1:len(faces)-1]) {
1616 face = faces[i];
1617 if (face[0] < 0 || face[1] < 0 || face[2] < 0 || face[0] >= vlen || face[1] >= vlen || face[2] >= vlen) {
1618 echo(str("INVALID FACE: indices of face ",i," are out of bounds [0,",vlen-1,"]: face=",face));
1619 }
1620 else if (is_undef(filter) || any(face,filter)) {
1621 verts = select(vertices,face);
1622 normal = polygon_normal(verts);
1623 if (is_undef(normal))
1624 echo(str("DEGENERATE FACE: face ",i," has no normal vector, face=", face));
1625 else {
1626 axis = vector_axis(normal, DOWN);
1627 ang = vector_angle(normal, DOWN);
1628 theta = atan2(normal[1], normal[0]);
1629 translate(mean(verts))
1630 rotate(a=(180-ang), v=axis)
1631 zrot(theta+90)
1632 linear_extrude(height=size/10, center=true, convexity=10) {
1633 text(text=str(i), size=size, halign="center");
1634 text(text=str("_"), size=size, halign="center");
1635 }
1636 }
1637 }
1638 }
1639 }
1640}
1641
1642
1643
1644// Module: debug_vnf()
1645// Synopsis: A replacement for `vnf_polyhedron()` to help with debugging.
1646// SynTags: VNF
1647// Topics: VNF Manipulation, Debugging
1648// See Also: vnf_validate()
1649// Usage:
1650// debug_vnf(vnfs, [faces=], [vertices=], [opacity=], [size=], [convexity=], [filter=]);
1651// Description:
1652// A drop-in module to replace `vnf_polyhedron()` to help debug vertices and faces.
1653// Draws all the vertices at their 3D position, numbered in blue by their
1654// position in the vertex array. Each face will have its face number drawn
1655// in red, aligned with the center of face. All given faces are drawn with
1656// transparency. All children of this module are drawn with transparency.
1657// Works best with Thrown-Together preview mode, to see reversed faces.
1658// You can set opacity to 0 if you want to supress the display of the polyhedron faces.
1659// .
1660// The vertex numbers are shown rotated to face you. As you rotate your polyhedron you
1661// can rerun the preview to display them oriented for viewing from a different viewpoint.
1662// Topics: Polyhedra, Debugging
1663// Arguments:
1664// vnf = VNF to display
1665// ---
1666// faces = if true display face numbers. Default: true
1667// vertices = if true display vertex numbers. Default: true
1668// opacity = Opacity of the polyhedron faces. Default: 0.5
1669// convexity = The max number of walls a ray can pass through the given polygon paths.
1670// size = The size of the text used to label the faces and vertices. Default: 1
1671// filter = If given a function literal of signature `function(i)`, will only show labels for vertices and faces that have a vertex index that gets a true result from that function. Default: no filter.
1672// Example(EdgesMed):
1673// verts = [for (z=[-10,10], a=[0:120:359.9]) [10*cos(a),10*sin(a),z]];
1674// faces = [[0,1,2], [5,4,3], [0,3,4], [0,4,1], [1,4,5], [1,5,2], [2,5,3], [2,3,0]];
1675// debug_vnf([verts,faces], size=2);
1676module debug_vnf(vnf, faces=true, vertices=true, opacity=0.5, size=1, convexity=6, filter ) {
1677 no_children($children);
1678 if (faces)
1679 _show_faces(vertices=vnf[0], faces=vnf[1], size=size, filter=filter);
1680 if (vertices)
1681 _show_vertices(vertices=vnf[0], size=size, filter=filter);
1682 if (opacity > 0)
1683 color([0.2, 1.0, 0, opacity])
1684 vnf_polyhedron(vnf,convexity=convexity);
1685}
1686
1687
1688// Module: vnf_validate()
1689// Synopsis: Echos non-manifold VNF errors to the console.
1690// SynTags: VNF
1691// Topics: VNF Manipulation, Debugging
1692// See Also: debug_vnf()
1693//
1694// Usage:
1695// vnf_validate(vnf, [size], [show_warns=], [check_isects=], [opacity=], [adjacent=], [label_verts=], [label_faces=], [wireframe=]);
1696// Description:
1697// When called as a module, echoes the non-manifold errors to the console, and color hilites the
1698// bad edges and vertices, overlaid on a transparent gray polyhedron of the VNF.
1699// .
1700// Currently checks for these problems:
1701// .
1702// Type | Color | Code | Message
1703// ------- | -------- | ------------ | ---------------------------------
1704// WARNING | Yellow | BIG_FACE | Face has more than 3 vertices, and may confuse CGAL.
1705// WARNING | Blue | NULL_FACE | Face has zero area.
1706// ERROR | Cyan | NONPLANAR | Face vertices are not coplanar.
1707// ERROR | Brown | DUP_FACE | Multiple instances of the same face.
1708// ERROR | Orange | MULTCONN | Multiply Connected Geometry. Too many faces attached at Edge.
1709// ERROR | Violet | REVERSAL | Faces reverse across edge.
1710// ERROR | Red | T_JUNCTION | Vertex is mid-edge on another Face.
1711// ERROR | Brown | FACE_ISECT | Faces intersect.
1712// ERROR | Magenta | HOLE_EDGE | Edge bounds Hole.
1713// .
1714// Still to implement:
1715// - Overlapping coplanar faces.
1716// Arguments:
1717// vnf = The VNF to validate.
1718// size = The width of the lines and diameter of points used to highlight edges and vertices. Module only. Default: 1
1719// ---
1720// show_warns = If true show warnings for non-triangular faces. Default: true
1721// check_isects = If true, performs slow checks for intersecting faces. Default: false
1722// opacity = The opacity level to show the polyhedron itself with. Default: 0.67
1723// label_verts = If true, shows labels at each vertex that show the vertex number. Default: false
1724// label_faces = If true, shows labels at the center of each face that show the face number. Default: false
1725// wireframe = If true, shows edges more clearly so you can see them in Thrown Together mode. Default: false
1726// adjacent = If true, only display faces adjacent to a vertex listed in the errors. Default: false
1727// Example(3D,Edges): BIG_FACE Warnings; Faces with More Than 3 Vertices. CGAL often will fail to accept that a face is planar after a rotation, if it has more than 3 vertices.
1728// vnf = skin([
1729// path3d(regular_ngon(n=3, d=100),0),
1730// path3d(regular_ngon(n=5, d=100),100)
1731// ], slices=0, caps=true, method="tangent");
1732// vnf_validate(vnf);
1733// Example(3D,Edges): NONPLANAR Errors; Face Vertices are Not Coplanar
1734// a = [ 0, 0,-50];
1735// b = [-50,-50, 50];
1736// c = [-50, 50, 50];
1737// d = [ 50, 50, 60];
1738// e = [ 50,-50, 50];
1739// vnf = vnf_from_polygons([
1740// [a, b, e], [a, c, b], [a, d, c], [a, e, d], [b, c, d, e]
1741// ],fast=true);
1742// vnf_validate(vnf);
1743// Example(3D,Edges): MULTCONN Errors; More Than Two Faces Attached to the Same Edge. This confuses CGAL, and can lead to failed renders.
1744// vnf = vnf_triangulate(linear_sweep(union(square(50), square(50,anchor=BACK+RIGHT)), height=50));
1745// vnf_validate(vnf);
1746// Example(3D,Edges): REVERSAL Errors; Faces Reversed Across Edge
1747// vnf1 = skin([
1748// path3d(square(100,center=true),0),
1749// path3d(square(100,center=true),100),
1750// ], slices=0, caps=false);
1751// vnf = vnf_join([vnf1, vnf_from_polygons([
1752// [[-50,-50, 0], [ 50, 50, 0], [-50, 50, 0]],
1753// [[-50,-50, 0], [ 50,-50, 0], [ 50, 50, 0]],
1754// [[-50,-50,100], [-50, 50,100], [ 50, 50,100]],
1755// [[-50,-50,100], [ 50,-50,100], [ 50, 50,100]],
1756// ])]);
1757// vnf_validate(vnf);
1758// Example(3D,Edges): T_JUNCTION Errors; Vertex is Mid-Edge on Another Face.
1759// vnf = [
1760// [
1761// each path3d(square(100,center=true),0),
1762// each path3d(square(100,center=true),100),
1763// [0,-50,100],
1764// ], [
1765// [0,2,1], [0,3,2], [0,8,4], [0,1,8], [1,5,8],
1766// [0,4,3], [4,7,3], [1,2,5], [2,6,5], [3,7,6],
1767// [3,6,2], [4,5,6], [4,6,7],
1768// ]
1769// ];
1770// vnf_validate(vnf);
1771// Example(3D,Edges): FACE_ISECT Errors; Faces Intersect
1772// vnf = vnf_join([
1773// vnf_triangulate(linear_sweep(square(100,center=true), height=100)),
1774// move([75,35,30],p=vnf_triangulate(linear_sweep(square(100,center=true), height=100)))
1775// ]);
1776// vnf_validate(vnf,size=2,check_isects=true);
1777// Example(3D,Edges): HOLE_EDGE Errors; Edges Adjacent to Holes.
1778// vnf = skin([
1779// path3d(regular_ngon(n=4, d=100),0),
1780// path3d(regular_ngon(n=5, d=100),100)
1781// ], slices=0, caps=false);
1782// vnf_validate(vnf,size=2);
1783
1784
1785// Returns a list of non-manifold errors with the given VNF.
1786// Each error has the format `[ERR_OR_WARN,CODE,MESG,POINTS,COLOR]`.
1787function _vnf_validate(vnf, show_warns=true, check_isects=false) =
1788 assert(is_vnf(vnf), "Invalid VNF")
1789 let(
1790 varr = vnf[0],
1791 faces = vnf[1],
1792 lvarr = len(varr),
1793 edges = sort([
1794 for (face=faces, edge=pair(face,true))
1795 edge[0]<edge[1]? edge : [edge[1],edge[0]]
1796 ]),
1797 dfaces = [
1798 for (face=faces) let(
1799 face=deduplicate_indexed(varr,face,closed=true)
1800 ) if(len(face)>=3)
1801 face
1802 ],
1803 face_areas = [
1804 for (face = faces)
1805 len(face) < 3? 0 :
1806 polygon_area([for (k=face) varr[k]])
1807 ],
1808 edgecnts = unique_count(edges),
1809 uniq_edges = edgecnts[0],
1810 issues = []
1811 )
1812 let(
1813 big_faces = !show_warns? [] : [
1814 for (face = faces)
1815 if (len(face) > 3)
1816 _vnf_validate_err("BIG_FACE", face)
1817 ],
1818 null_faces = !show_warns? [] : [
1819 for (i = idx(faces)) let(
1820 face = faces[i],
1821 area = face_areas[i]
1822 )
1823 if (is_num(area) && abs(area) < EPSILON)
1824 _vnf_validate_err("NULL_FACE", face)
1825 ],
1826 issues = concat(big_faces, null_faces)
1827 )
1828 let(
1829 bad_indices = [
1830 for (face = faces, idx = face)
1831 if (idx < 0 || idx >= lvarr)
1832 _vnf_validate_err("BAD_INDEX", [idx])
1833 ],
1834 issues = concat(issues, bad_indices)
1835 ) bad_indices? issues :
1836 let(
1837 repeated_faces = [
1838 for (i=idx(dfaces), j=idx(dfaces))
1839 if (i!=j) let(
1840 face1 = dfaces[i],
1841 face2 = dfaces[j]
1842 ) if (min(face1) == min(face2)) let(
1843 min1 = min_index(face1),
1844 min2 = min_index(face2)
1845 ) if (min1 == min2) let(
1846 sface1 = list_rotate(face1,min1),
1847 sface2 = list_rotate(face2,min2)
1848 ) if (sface1 == sface2)
1849 _vnf_validate_err("DUP_FACE", sface1)
1850 ],
1851 issues = concat(issues, repeated_faces)
1852 ) repeated_faces? issues :
1853 let(
1854 multconn_edges = unique([
1855 for (i = idx(uniq_edges))
1856 if (edgecnts[1][i]>2)
1857 _vnf_validate_err("MULTCONN", uniq_edges[i])
1858 ]),
1859 issues = concat(issues, multconn_edges)
1860 ) multconn_edges? issues :
1861 let(
1862 reversals = unique([
1863 for(i = idx(dfaces), j = idx(dfaces)) if(i != j)
1864 for(edge1 = pair(faces[i],true))
1865 for(edge2 = pair(faces[j],true))
1866 if(edge1 == edge2) // Valid adjacent faces will never have the same vertex ordering.
1867 if(_edge_not_reported(edge1, varr, multconn_edges))
1868 _vnf_validate_err("REVERSAL", edge1)
1869 ]),
1870 issues = concat(issues, reversals)
1871 ) reversals? issues :
1872 let(
1873 t_juncts = unique([
1874 for (v=idx(varr), edge=uniq_edges) let(
1875 ia = edge[0],
1876 ib = v,
1877 ic = edge[1]
1878 )
1879 if (ia!=ib && ib!=ic && ia!=ic) let(
1880 a = varr[ia],
1881 b = varr[ib],
1882 c = varr[ic]
1883 )
1884 if (!approx(a,b) && !approx(b,c) && !approx(a,c)) let(
1885 pt = line_closest_point([a,c],b,SEGMENT)
1886 )
1887 if (approx(pt,b))
1888 _vnf_validate_err("T_JUNCTION", [ib])
1889 ]),
1890 issues = concat(issues, t_juncts)
1891 ) t_juncts? issues :
1892 let(
1893 isect_faces = !check_isects? [] : unique([
1894 for (i = [0:1:len(faces)-2]) let(
1895 f1 = faces[i],
1896 poly1 = select(varr, faces[i]),
1897 plane1 = plane3pt(poly1[0], poly1[1], poly1[2]),
1898 normal1 = [plane1[0], plane1[1], plane1[2]]
1899 )
1900 for (j = [i+1:1:len(faces)-1]) let(
1901 f2 = faces[j],
1902 poly2 = select(varr, f2),
1903 val = poly2 * normal1
1904 )
1905 if( min(val)<=plane1[3] && max(val)>=plane1[3] ) let(
1906 plane2 = plane_from_polygon(poly2),
1907 normal2 = [plane2[0], plane2[1], plane2[2]],
1908 val = poly1 * normal2
1909 )
1910 if( min(val)<=plane2[3] && max(val)>=plane2[3] ) let(
1911 shared_edges = [
1912 for (edge1 = pair(f1, true), edge2 = pair(f2, true))
1913 if (edge1 == [edge2[1], edge2[0]]) 1
1914 ]
1915 )
1916 if (!shared_edges) let(
1917 line = plane_intersection(plane1, plane2)
1918 )
1919 if (!is_undef(line)) let(
1920 isects = polygon_line_intersection(poly1, line)
1921 )
1922 if (!is_undef(isects))
1923 for (isect = isects)
1924 if (len(isect) > 1) let(
1925 isects2 = polygon_line_intersection(poly2, isect, bounded=true)
1926 )
1927 if (!is_undef(isects2))
1928 for (seg = isects2)
1929 if (seg[0] != seg[1])
1930 _vnf_validate_err("FACE_ISECT", seg)
1931 ]),
1932 issues = concat(issues, isect_faces)
1933 ) isect_faces? issues :
1934 let(
1935 hole_edges = unique([
1936 for (i=idx(uniq_edges))
1937 if (edgecnts[1][i]<2)
1938 if (_pts_not_reported(uniq_edges[i], varr, t_juncts))
1939 if (_pts_not_reported(uniq_edges[i], varr, isect_faces))
1940 _vnf_validate_err("HOLE_EDGE", uniq_edges[i])
1941 ]),
1942 issues = concat(issues, hole_edges)
1943 ) hole_edges? issues :
1944 let(
1945 nonplanars = unique([
1946 for (i = idx(faces))
1947 if (is_undef(face_areas[i]))
1948 _vnf_validate_err("NONPLANAR", faces[i])
1949 ]),
1950 issues = concat(issues, nonplanars)
1951 ) issues;
1952
1953
1954_vnf_validate_errs = [
1955 ["BIG_FACE", "WARNING", "cyan", "Face has more than 3 vertices, and may confuse CGAL"],
1956 ["NULL_FACE", "WARNING", "blue", "Face has zero area."],
1957 ["BAD_INDEX", "ERROR", "cyan", "Invalid face vertex index."],
1958 ["NONPLANAR", "ERROR", "yellow", "Face vertices are not coplanar"],
1959 ["DUP_FACE", "ERROR", "brown", "Multiple instances of the same face."],
1960 ["MULTCONN", "ERROR", "orange", "Multiply Connected Geometry. Too many faces attached at Edge"],
1961 ["REVERSAL", "ERROR", "violet", "Faces Reverse Across Edge"],
1962 ["T_JUNCTION", "ERROR", "magenta", "Vertex is mid-edge on another Face"],
1963 ["FACE_ISECT", "ERROR", "brown", "Faces intersect"],
1964 ["HOLE_EDGE", "ERROR", "red", "Edge bounds Hole"]
1965];
1966
1967
1968function _vnf_validate_err(name, extra) =
1969 let(
1970 info = [for (x = _vnf_validate_errs) if (x[0] == name) x][0]
1971 ) concat(info, [extra]);
1972
1973
1974function _pts_not_reported(pts, varr, reports) =
1975 [
1976 for (i = pts, report = reports, pt = report[3])
1977 if (varr[i] == pt) 1
1978 ] == [];
1979
1980
1981function _edge_not_reported(edge, varr, reports) =
1982 let(
1983 edge = sort([for (i=edge) varr[i]])
1984 ) [
1985 for (report = reports) let(
1986 pts = sort(report[3])
1987 ) if (len(pts)==2 && edge == pts) 1
1988 ] == [];
1989
1990
1991module vnf_validate(vnf, size=1, show_warns=true, check_isects=false, opacity=0.67, adjacent=false, label_verts=false, label_faces=false, wireframe=false) {
1992 no_children($children);
1993 vcount = len(vnf[0]);
1994 fcount = len(vnf[1]);
1995 vnf = vnf_merge_points(vnf);
1996 faults = _vnf_validate(
1997 vnf, show_warns=show_warns,
1998 check_isects=check_isects
1999 );
2000 verts = vnf[0];
2001 vnf_changed = len(verts)!=vcount || len(vnf[1])!=fcount;
2002 if (!faults) {
2003 echo("VNF appears valid.");
2004 }
2005 if (vnf_changed) echo("VNF changed when merging points; unable to display indices");
2006 for (fault = faults) {
2007 err = fault[0];
2008 typ = fault[1];
2009 clr = fault[2];
2010 msg = fault[3];
2011 idxs = fault[4];
2012 pts = err=="FACE_ISECT" ? idxs : [for (i=idxs) if(is_finite(i) && i>=0 && i<len(verts)) verts[i]];
2013 if (vnf_changed || err=="FACE_ISECT")
2014 echo(str(typ, " ", err, " (", clr ,"): ", msg, " at ", pts));
2015 else
2016 echo(str(typ, " ", err, " (", clr ,"): ", msg, " at ", pts, " indices: ", idxs));
2017 color(clr) {
2018 if (is_vector(pts[0])) {
2019 if (len(pts)==2) {
2020 stroke(pts, width=size, endcaps="butt", $fn=8);
2021 } else if (len(pts)>2) {
2022 stroke(pts, width=size, closed=true, $fn=8);
2023 polyhedron(pts,[[for (i=idx(pts)) i]]);
2024 } else {
2025 move_copies(pts) sphere(d=size*3, $fn=18);
2026 }
2027 }
2028 }
2029 }
2030 badverts = unique([for (fault=faults) each fault[4]]);
2031 badverts2 = unique([for (j=idx(verts), i=badverts) if (i!=j && verts[i]==verts[j]) j]);
2032 all_badverts = unique(concat(badverts, badverts2));
2033 adjacent = !faults? false : adjacent;
2034 filter_fn = !adjacent? undef : function(i) in_list(i,all_badverts);
2035 adj_vnf = !adjacent? vnf : [
2036 verts, [for (face=vnf[1]) if (any(face,filter_fn)) face]
2037 ];
2038 if (wireframe) {
2039 vnf_wireframe(adj_vnf, width=size*0.25);
2040 }
2041 if (label_verts) {
2042 debug_vnf(adj_vnf, size=size*3, opacity=0, faces=false, vertices=true, filter=filter_fn);
2043 }
2044 if (label_faces) {
2045 debug_vnf(vnf, size=size*3, opacity=0, faces=true, vertices=false, filter=filter_fn);
2046 }
2047 if (opacity > 0) {
2048 color([0.5,1,0.5,opacity]) vnf_polyhedron(adj_vnf);
2049 }
2050}
2051
2052
2053
2054// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap