fix tracker url
[blender-addons-contrib.git] / mesh_bevel_round.py
1 # ##### BEGIN GPL LICENSE BLOCK #####
2 #
3 #  This program is free software; you can redistribute it and/or
4 #  modify it under the terms of the GNU General Public License
5 #  as published by the Free Software Foundation; either version 2
6 #  of the License, or (at your option) any later version.
7 #
8 #  This program is distributed in the hope that it will be useful,
9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 #  GNU General Public License for more details.
12 #
13 #  You should have received a copy of the GNU General Public License
14 #  along with this program; if not, write to the Free Software Foundation,
15 #  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
16 #
17 # ##### END GPL LICENSE BLOCK #####
18
19 # <pep8 compliant>
20
21 # Ported from RoundCorner Ruby program for Sketchup by Fredo6
22 # Fredo6 gave permission to port and distribute with Blender
23
24 bl_info = {
25     "name": "Bevel Round",
26     "author": "Fredo6, Howard Trickey",
27     "version": (0, 1),
28     "blender": (2, 6, 3),
29     "location": "View3D > Tools",
30     "description": "Bevel selected edges, possibly rounded",
31     "warning": "",
32     "wiki_url": "http://wiki.blender.org/index.php/Extensions:2.6/Py/"\
33         "Scripts",
34     "tracker_url": "http://projects.blender.org/tracker/index.php?"\
35         "func=detail&aid=32582",
36     "category": "Mesh"}
37
38 import math
39 import functools
40 import bpy
41 import bmesh
42 import mathutils
43 from bpy.props import (BoolProperty,
44                        EnumProperty,
45                        IntProperty,
46                        FloatProperty,
47                        )
48 from mathutils import Vector
49
50 EPSILON = 1e-6
51
52 class BevelRound(bpy.types.Operator):
53     bl_idname = "mesh.bevel_round"
54     bl_label = "Bevel Round"
55     bl_description = "Bevel selected edges, possibly rounded"
56     bl_options = {'REGISTER', 'UNDO'}
57
58     bevel_kind = EnumProperty(name="Bevel Kind",
59         description="Style for beveling edges and corners",
60         items=[
61             ('ROUND', "Round",
62                 "Round edges and corners"),
63             ('SHARP', "Sharp",
64                 "Round edges, peaked corners"),
65             ('BEVEL', "Bevel",
66                 "Flat edges and corners")
67             ],
68         default='BEVEL')
69
70     offset_amount = FloatProperty(name="Offset",
71         description="Amount to offset edges along faces",
72         default=0.2,
73         min=0.0,
74         max=1000.0,
75         soft_min=0.0,
76         soft_max=10.0,
77         unit='LENGTH')
78
79     segments = IntProperty(name="Segments",
80         description="How many segments on bevel profile",
81         min=1,
82         max=100,
83         default=1)
84
85     strict_offset = BoolProperty(name="Strict Offset",
86         description="Keep offset the same on all faces",
87         default=True)
88
89     rounding = BoolProperty(name="Inner Rounding",
90         description="Round inside faces at concave corners",
91         default=True)
92
93     @classmethod
94     def poll(cls, context):
95         obj = context.active_object
96         return (obj and obj.type == 'MESH' and context.mode == 'EDIT_MESH')
97
98     def draw(self, context):
99         layout = self.layout
100         box = layout.box()
101         box.label("Bevel Round Options:")
102         box.prop(self, "bevel_kind")
103         box.prop(self, "offset_amount")
104         box.prop(self, "segments")
105         box.prop(self, "strict_offset")
106         box.prop(self, "rounding")
107
108     def invoke(self, context, event):
109         self.action(context)
110         return {'FINISHED'}
111
112     def execute(self, context):
113         self.action(context)
114         return {'FINISHED'}
115
116     def action(self, context):
117         obj = bpy.context.active_object
118         bm = bmesh.from_edit_mesh(obj.data)
119         # make sure vert, edge, face indexes match their positions
120         bm.verts.index_update()
121         bm.edges.index_update()
122         bm.faces.index_update()
123         algo = BevelRoundAlgo(bm, self.bevel_kind, self.offset_amount,
124             self.segments, self.strict_offset, self.rounding)
125         algo.execute()
126         # Force mesh data recalculation
127         bpy.ops.object.editmode_toggle()
128         bpy.ops.object.editmode_toggle()
129
130
131 class BevelRoundAlgo(object):
132     def __init__(self, bm, kind, offset, num_seg, strict, round):
133         # The bmesh object
134         self.bm = bm
135
136         # How much to move offset edges
137         # (projected onto 90deg angle planes, unless strict_offset)
138         self.offset = offset
139
140         # How many segments in the profile of an edge
141         self.num_seg = num_seg
142
143         # Cache of profiles in standard position, keyed by "kind-numseg"
144         # Kind will be one of 'C' or 'P', for now
145         self.hsh_profile_pts = {}
146
147         # bmesh Edge index -> BEdge for it
148         # Will have one for all the edges in the bevel selection
149         self.hsh_ed = {}
150
151         # bmesh Vertex index -> BCorner for it
152         # Will have one for all ends of edges in hsh_ed
153         self.hsh_corners = {}
154
155         # bmesh Face index -> BFace for it
156         self.hsh_faces = {}
157
158         # List of [Vector, Vector], each a border line segment (for display only?)
159         self.lpt_borders = []
160
161         # Catenas are chains of edges with related offsets
162         # Each has eds, a list of BEdges;
163         #  chain, a list of [BEdge, face index]l
164         #  nbsmall: seems to be some kind of edge count
165         self.lst_catenas = []
166
167         # List of Vector, pivot points for star corners
168         self.lst_mark_points = []
169
170         # lst_triangulate is list of [vd, ed1, ed2, seg1, seg2]
171         # for each vd for a vert with only two edges and >=3 pairs
172         self.lst_triangulated = []
173
174         # List of BCorner, those signaled as errors (pair lines don't cross (?))
175         self.hsh_error_vertex = {}
176
177         # Edge index -> bmesh Edge for edges to bevel
178         self.hash_edges = {}
179
180         # hash_edges_extra : Edge index -> bmesh Edge added for valence >= 4 reasons
181         self.hash_edges_extra = {}
182
183         # Vertex index -> list of bmesh edges to bevel attached
184         self.hsh_vertex_edges = {}
185
186         # Vertex index -> list of all bmesh edges attached to it
187         self.hsh_vertex_info = {}
188
189         # Map from point to BMVert
190         self.points = Points(self.bm)
191
192         # Used to orient asymmetric corner mesh patterns
193         self.golden_axis = Vector([0.0, 0.0, 1.0])
194
195         # Profile spec for edges: [string, number]
196         # where string is 'C' for quarter circle, 'CR' for concave quarter circle,
197         # 'BZ' for Bezier, 'P' for 'perso' (?, some kind of multi-bezier).
198         # number is number of line segments in profile (so 1 means just
199         # a single straight line from start to end)
200         if kind == 'BEVEL':
201             self.profile_type = ['C', 1]
202             self.num_seg = 1
203         else:
204             self.profile_type = ['C', num_seg]
205
206         # Controls whether or not to use a round profile in certain disagreeing cases (?)
207         self.mode_profile = 1
208
209         # Corners come to peaks if mode_sharp
210         self.mode_sharp = True if kind == 'SHARP' else False
211
212         # Forces offset along faces to  be uniform rather than adjusted
213         # to make them uniform when projected on 90deg-meeting-faces
214         self.strict_offset = strict
215
216         # Should we round the edges in the faces themselves too?
217         self.mode_rounding = round
218
219     def execute(self):
220         bm = self.bm
221
222         # Add the bmesh edges and compute everything
223         # needed for bevel
224         self.build_model(bm)
225
226         # print("after build:")
227         # self.print()
228
229         # Initialization for geometry making
230         self.prepare_geometry()
231
232         # print("after prepare_geometry")
233         # self.print()
234
235         self.lst_corners = list(self.hsh_corners.values())
236         self.nb_corners = len(self.lst_corners) - 1
237         self.lst_eds = list(self.hsh_ed.values())
238         self.nb_eds = len(self.lst_eds) - 1
239         self.hsh_edge_erase = {}
240         self.nb_borders = len(self.lpt_borders) // 2 - 1
241
242         # Process geometry
243
244         self.lst_edge_erase = []
245         self.nb_edge_erase = -1
246
247         # Creating the rounding faces
248         for k in range(0, self.nb_eds + 1):
249             ed = self.lst_eds[k]
250             if ed.vmesh:
251                 self.create_geometry_vmesh(ed.vmesh)
252
253         # Creating the triangulated  vmesh if any
254         self.create_geometry_vmesh(self.lst_vmesh_triangulated)
255         self.create_geometry_vborders(self.lst_vborders_triangulated)
256
257         # Creating the corner round faces
258         for k in range(0, self.nb_corners + 1):
259            vd = self.lst_corners[k]
260            if vd.vmesh:
261                self.create_geometry_vmesh(vd.vmesh)
262
263         # Creating the new faces
264         for fc in self.hsh_faces.values():
265             if not fc.anynew():
266                 continue
267             lv = []
268             for i in range(len(fc.bmverts)):
269                 npl = fc.newpts[i]
270                 if npl:
271                     lv.extend(self.get_bmverts(npl))
272                 else:
273                     lv.append(fc.bmverts[i])
274             self.bm.faces.new(lv)
275
276         # Deleting the unneeded geometry
277         for f in self.hsh_faces.values():
278             if f.face.is_valid:
279                 if not f.anynew():
280                     continue
281                 fedges = f.face.edges[::]
282                 self.bm.faces.remove(f.face)
283                 for e in fedges:
284                     if e.is_valid:
285                         if e.is_wire:
286                             self.bm.edges.remove(e)
287         for k in range(0, self.nb_corners + 1):
288             vd = self.lst_corners[k]
289             if len(vd.leds) == 1:
290                 edge = vd.leds[0].edge
291                 if edge.is_valid:
292                     self.bm.edges.remove(edge)
293             else:
294                 # print("remove edges:", vd.vertex.link_edges)
295                 pass  # is there stuff to do here?
296             if vd.vertex.is_valid:
297                 self.bm.verts.remove(vd.vertex)
298
299     # Prepare the geometry
300     def prepare_geometry(self):
301         # Compute the corners
302         for vd in self.hsh_corners.values():
303             self.corner_compute(vd)
304
305         # Compute the edge roundings
306         for ed in self.hsh_ed.values():
307             self.compute_mesh_edge(ed)
308
309         # Compute the edge roundings for triangulated corners, if any
310         self.lst_vmesh_triangulated = []
311         self.lst_vborders_triangulated = []
312         for ll in self.lst_triangulated:
313             self.compute_mesh_edge_triangulated(ll[0], ll[1], ll[2], ll[3], ll[4])
314
315         # Compute the faces
316         for fc in self.hsh_faces.values():
317             self.compute_face(fc)
318
319     # Adds more edges if needed to make it so that for
320     # vertices of valence 4 or more, all edges are beveled if any are.
321     # Fills hsh_vertex_info for involved vertices with list of all bmesh
322     # edges attached to a vertex.
323     # Fills hsh_ed with BEdge for each edge to be beveled.
324     # Fills hsh_corners with BCorner for each vertex involved in each BEdge.
325     # Computes pairs at each BCorner.
326     # Add bmesh edges to be beveled and compute the other
327     # structures needed for the bevel.
328     def build_model(self, bm):
329         # Fill self.hash_edges with selected bmesh edges
330         # if they are acceptable (separate two faces, not-coplanar)
331         for bme in bm.edges:
332             if bme.select and self.acceptable_edge(bme):
333                 self.hash_edges[bme.index] = bme
334
335         if len(self.hash_edges) == 0:
336             return
337
338        # Fill self.hash_vertex_edges[i] with list of
339        # bmesh edges attached to vertex with bmesh index i
340         self.hsh_vertex_edges = {}
341         for edge in self.hash_edges.values():
342             self.register_vertex(edge.verts[0], edge)
343             self.register_vertex(edge.verts[1], edge)
344
345         # Add extra edges needed to make valence
346         # >=4 verts have all edges beveled if any are.
347         # Extra edges go in self.hash_edges and
348         # self.hash_edges_extra.
349         self.hash_edges_extra = {}
350         for edge in self.hash_edges.values():
351             self.verify_vertex(edge.verts[0])
352             self.verify_vertex(edge.verts[1])
353         
354         # create BEdges in hsh_ed, BCorners in hsh_corners
355         for edge in self.hash_edges.values():
356             self.integrate_edge(edge)
357
358         # create BPairs in vd.pairs for each BCorner vd.
359         for vd in self.hsh_corners.values():
360             self.compute_pairs_at_vertex(vd)
361
362         # create BCatenas in ed.catenas for each BEdge ed.
363         self.catena_compute_all()
364         if self.strict_offset:
365             self.catena_offset_all()
366
367         self.lpt_borders = []
368         for ed in self.hsh_ed.values():
369             self.nsection = None
370             for pair in ed.pairs:
371                 pair.ptcross = None
372             self.compute_borders(ed)
373
374         # Scan the corners to determine the roundings
375         self.corner_scan_all()
376
377         # Compute the faces orientation: tricky when # segments is odd
378         self.compute_face_orientation()
379
380         # Compute alone pairs in case of triangulation
381         self.evaluate_pair_triangulated()
382
383         # Compute the roundings
384         for vd in self.hsh_corners.values():
385             self.rounding_compute(vd)
386         for ed in self.hsh_ed.values():
387             self.compute_borders_for_display(ed)
388
389
390     def acceptable_edge(self, bme):
391         # algorithm requires that edges separate
392         # exactly two, non coplanar faces
393         if len(bme.link_faces) == 2:
394             f1 = bme.link_faces[0]
395             f2 = bme.link_faces[1]
396             return not parallel(f1.normal, f2.normal)
397         return False
398
399     def register_vertex(self, vertex, bme):
400         if vertex.index not in self.hsh_vertex_edges:
401             self.hsh_vertex_edges[vertex.index] = []
402         ledges = self.hsh_vertex_edges[vertex.index]
403         if bme not in ledges:
404             ledges.append(bme)
405         self.register_faces(vertex.link_faces)
406
407     def verify_vertex(self, vertex):
408         # algorithm requires that vertices with valence >= 4
409         # must have all edges included
410         if vertex.index not in self.hsh_vertex_info:
411             ledges = []
412             self.hsh_vertex_info[vertex.index] = list(vertex.link_edges)
413         ledges = self.hsh_vertex_info[vertex.index]  # list of bmesh edges
414         lsel = self.hsh_vertex_edges[vertex.index]
415         nsel = len(lsel)
416         if nsel <=3 or nsel == len(ledges):
417             return
418         # add extra edges
419         for bme in ledges:
420             if bme.index in self.hash_edges:
421                 continue
422             # kind of an impasse if edge is unacceptable - oh well
423             if self.acceptable_edge(bme):
424                 self.hash_edges[edge.index] = bme
425                 self.register_vertex(edge.verts[0], bme)
426                 self.register_vertex(edge.verts[1], bme)
427                 self.hash_edges_extra[edge.index] = bme
428
429     def register_faces(self, faces):
430         for f in faces:
431             if f.index not in self.hsh_faces:
432                 self.hsh_faces[f.index] = BFace(f)
433
434     # Evaluate and treat pairs at triangulated corners
435     def evaluate_pair_triangulated(self):
436         self.lst_triangulated = []
437         lalone = [ vd for vd in self.hsh_corners.values() \
438                    if len(vd.leds) == 2 and len(vd.pairs) >= 3 ]
439         for i, vd in enumerate(lalone):
440             ed1 = vd.leds[0]
441             ed2 = vd.leds[1]
442             pairs1 = [ pair for pair in vd.pairs if pair.alone and pair.leds[0] == ed1 ]
443             pairs2 = [ pair for pair in vd.pairs if pair.alone and pair.leds[0] == ed2 ]
444             if not pairs1 or not pairs2:
445                 continue
446             ptcross10 = pairs1[0].ptcross
447             ptcross11 = pairs1[1].ptcross if len(pairs1) > 1 else None
448             ptcross20 = pairs2[0].ptcross
449             ptcross21 = pairs2[1].ptcross if len(pairs2) > 1 else None
450             if ptcross21 and (ptcross21 - ptcross10).length < (ptcross20 - ptcross10).length:
451                 seg1 = [ptcross10, ptcross21]
452             else:
453                 seg1 = [ptcross10, ptcross20]
454             seg2 = None
455             if ptcross11:
456                 if ptcross21 and (ptcross21 - ptcross11).length < (ptcross20 - ptcross11).length:
457                     seg2 = [ptcross11, ptcross21]
458                 else:
459                     seg2 = [ptcross11, ptcross20]
460             self.lpt_borders.extend(seg1)
461             if seg2:
462                 self.lpt_borders.extend(seg2)
463             self.lst_triangulated.append([vd, ed1, ed2, seg1, seg2])
464
465     def integrate_edge(self, edge):
466         if not self.acceptable_edge(edge):
467             return None
468         index = edge.index
469         if index in self.hsh_ed:
470             return self.hsh_ed[index]
471         ed = BEdge(edge)
472         self.hsh_ed[index] = ed
473         ed.corners.append(self.create_corner(edge.verts[0], ed))
474         ed.corners.append(self.create_corner(edge.verts[1], ed))
475         return ed
476
477     def create_corner(self, vertex, ed):
478         index = vertex.index
479         if index not in self.hsh_corners:
480             vd = BCorner(vertex, ed)
481             self.hsh_corners[index] = vd
482         else:
483             vd = self.hsh_corners[index]
484             if ed not in vd.leds:
485                 vd.leds.append(ed)
486         return vd
487
488     # vd should be for a vertex and one end of ed1's edge and face1
489     # should be one or the other of the faces incident to it.
490     # Similarly for ed2, face2 if present
491     def create_pair(self, vd, ed1, face1, ed2=None, face2=None):
492         edge1 = ed1.edge
493         edge2 = ed2.edge if ed2 else None
494         pair = BPair(vd, ed1, face1, ed2, face2)
495         vd.pairs.append(pair)
496         vertex = vd.vertex
497         iface1 = 0 if face1 == ed1.lfaces[0] else 1
498         ivtx = 0 if vertex == edge1.verts[0] else 1
499         ed1.pairs[iface1 + 2 * ivtx] = pair
500         if edge2:
501             iface2 = 0 if face2 == ed2.lfaces[0] else 1
502             ivtx = 0 if vertex == edge2.verts[0] else 1
503             if not ed2.pairs:
504                 ed2.pairs = [None, None, None, None]
505             ed2.pairs[iface2 + 2 * ivtx] = pair
506             pair.monoface = (face1 == face2) or parallel(face1.normal, face2.normal)
507             if pair.monoface:
508                 pair.convex = convex_at_vertex(vertex, face1, ed1.edge, ed2.edge, face2)
509                 pair.vd.convex = pair.convex
510         # computing planes for cross points - special for termination corners
511         if pair.alone:
512             self.compute_edge_terms(pair, pair.ledges[0], pair.lfaces[0], pair.vd.vertex)
513         return pair
514
515     # Find the matching edges at a vertex
516     def compute_pairs_at_vertex(self, vd):
517         nb_edge = len(vd.leds)
518         if nb_edge == 1:
519             ed = vd.leds[0]
520             self.create_pair(vd, ed, ed.lfaces[0])
521             self.create_pair(vd, ed, ed.lfaces[1])
522         elif nb_edge == 2:
523             self.check_pair_2(vd, vd.leds[0], vd.leds[1])
524         else:
525             for i in range(0, nb_edge - 1):
526                 for j in range(i+1, nb_edge):
527                     self.check_pair_N(vd, vd.leds[i], vd.leds[j], vd.leds)
528
529     # Find the common faces (or coplanar) to 2 edges when there are 2 at vertex.
530     # Makes a pair for the two edges matching when there's common or coplanar faces.
531     # Also makes pairs for the two edges matching when there's a common edge
532     # between them (and some convexity test I don't understand).
533     # Finally, makes an alone pair for any (edge, face) pairs not otherwise used.
534     def check_pair_2(self, vd, ed1, ed2):
535         edge1 = ed1.edge
536         edge2 = ed2.edge
537         faces1 = list(edge1.link_faces)
538         faces2 = list(edge2.link_faces)
539
540         # Finding faces on the same plane
541         for f1 in edge1.link_faces:
542             for f2 in edge2.link_faces:
543                 if f1 == f2 or parallel(f1.normal, f2.normal):
544                     self.create_pair(vd, ed1, f1, ed2, f2)
545                     faces1.remove(f1)
546                     faces2.remove(f2)
547
548         # Finding faces with common edges
549         lf1 = []
550         lf2 = []
551         for f1 in faces1:
552             for f2 in faces2:
553                 linter = list(set(f1.edges).intersection(set(f2.edges)))
554                 if len(linter) > 0:
555                     e = linter[0]
556                     if not (convex_at_vertex(vd.vertex, f1, edge1, e) or \
557                             convex_at_vertex(vd.vertex, f2, edge2, e)):
558                         self.create_pair(vd, ed1, f1, ed2, f2)
559                         lf1.append(f1)
560                         lf2.append(f2)
561
562         # Creating alone pair if any unaffected faces left
563         for f1 in faces1:
564             if f1 not in lf1:
565                 self.create_pair(vd, ed1, f1)
566         for f2 in faces2:
567             if f2 not in lf2:
568                 self.create_pair(vd, ed2, f2)
569
570     # Find the common faces (or coplanar) to 2 edges when there are more than 2 total.
571     # Makes a pair for the the two edges matching the first of any common faces
572     # and returns if so.
573     # Else makes a pair matching up the two edges with faces that are parallel
574     # and returns if it finds one.
575     # Else makes a pair matching up the two edges with faces sharing an edge
576     # and that edge isn't in leds, and returns if it finds one.
577     # Otherwise makes no pair.
578     def check_pair_N(self, vd, ed1, ed2, leds):
579         edge1 = ed1.edge
580         edge2 = ed2.edge
581         if edge1 == edge2:
582             return
583         faces1 = list(edge1.link_faces)
584         faces2 = list(edge2.link_faces)
585         lfaces = list(set(faces1).intersection(set(faces2)))
586
587         # Common face found
588         if len(lfaces) >= 1:
589             return self.create_pair(vd, ed1, lfaces[0], ed2, lfaces[0])
590
591         # Finding faces that are on the same plane
592         for f1 in edge1.link_faces:
593             for f2 in edge2.link_faces:
594                 if parallel(f1.normal, f2.normal):
595                     return self.create_pair(vd, ed1, f1, ed2, f2)
596  
597         # Check common edges
598         for f1 in faces1:
599             for f2 in faces2:
600                 linter = list(set(f1.edges).intersection(set(f2.edges)))
601                 if len(linter) > 0 and not find(leds, lambda ed: ed.edge == linter[0]):
602                     return self.create_pair(vd, ed1, f1, ed2, f2)
603                     
604     def compute_borders(self, ed):
605         pairs = ed.pairs
606         for i in range(0,4):
607             if pairs[i]:
608                self.compute_pair_ptcross(pairs[i])
609
610     # Compute the borders for display, including the rounding
611     def compute_borders_for_display(self, ed):
612         pairs = ed.pairs
613         lseg = []
614         lroundings = []
615         for i in [0, 2, 1, 3]:
616             pair = pairs[i]
617             lpt = pair.rounding
618             if lpt and len(lpt) > 0:
619                 if on_line(lpt[0], [pair.ptcross, ed.vec]):
620                     pt = lpt[0]
621                 else:
622                     pt = lpt[-1]
623             else:
624                 pt = pair.ptcross
625             lseg.append(pt)
626         self.lpt_borders.extend(lseg)
627
628
629     # Compute and return the vector representing the border
630     def compute_edge_terms(self, pair, edge, face, vertex):
631         normal = face.normal
632         for e in vertex.link_edges:
633             if e == edge:
634                 continue
635             for f in e.link_faces:
636                 if f == face or parallel(f.normal, normal):
637                     pair.edge_terms.append(e)
638
639     # Compute the cross points for the pair
640     def compute_pair_ptcross(self, pair):
641         if pair.ptcross:
642             return
643         line1 = self.line_border(pair, 0)
644         if pair.alone:
645             pair.ptcross = self.find_intersect_edge_term(pair, line1)
646         else:
647             line2 = self.line_border(pair, 1)
648             if parallel(line1[1], line2[1]):
649                 pair.ptcross = intersect_line_plane(line1,
650                         [pair.vd.vertex.co, line1[1]])
651             else:
652                 pair.ptcross = intersect_line_line(line1, line2)
653                 if not pair.ptcross:
654                     self.signal_error_vd(pair.vd)
655                     lpt = closest_points(line1, line2)
656                     pair.ptcross = lpt[0]
657
658     # Fine the best stop point for a standalone edge pair
659     def find_intersect_edge_term(self, pair, line):
660         ed = pair.leds[0]
661         lptinter = []
662         for edge in pair.edge_terms:
663             pt = intersect_edge_line(edge, line)
664             if pt:
665                 lptinter.append(pt)
666         # if no intersection just take the orthogonal plane
667         if len(lptinter) == 0:
668             return intersect_line_plane(line, [pair.vd.vertex.co, ed.vec])
669         # sort the interesection point and take the farthest
670         ptmid = ed.ptmid
671         lptinter.sort(key = lambda p: (ptmid-p).length)
672         return lptinter[-1]
673
674     # Compute the line defining a border on  a face
675     # (Maybe don't need this function if not drawing borders)
676     def line_border(self, pair, iedge):
677         edge = pair.ledges[iedge]
678         ed = self.hsh_ed[edge.index]
679         face = pair.lfaces[iedge]
680         iface = 0 if face == ed.lfaces[0] else 1
681         offset = self.offset * ed.lfactors[iface]
682         vecin = normal_in_to_edge(edge, face)
683         pt = ed.ptmid + offset * vecin
684         return [pt, ed.vec]
685
686     # Compute the orthogonal profile for an edge at its midpoint
687     def compute_profile_edge(self, ed):
688         if ed.nsection:
689             return ed.nsection
690         offset1 = self.offset * ed.lfactors[0]
691         offset2 = self.offset * ed.lfactors[1]
692         vec1 = ed.lvecins[0]
693         vec2 = ed.lvecins[1]
694         ptcenter = ed.ptmid
695         profile = ['C', self.num_seg] if ed.round_profile else self.profile_type
696         section = self.profile_compute_by_offset(profile, ptcenter,
697                     vec1, offset1, vec2, offset2)
698         if not on_plane(section[0], face_plane(ed.facemain)):
699             section.reverse()
700         ed.nsection = section
701         return section
702
703     # Compute the section for an edge at corners
704     # The section will go from the facemain face to the non-facemain one.
705     def compute_sections_multi(self, ed, icorner):
706         vd = ed.corners[icorner]
707         vpos = vd.vertex.co
708         iA = 0 if ed.facemain == ed.lfaces[0] else 1
709         iB = 1 - iA
710         pairA = ed.pairs[2 * icorner + iA]
711         pairB = ed.pairs[2 * icorner + iB]
712
713         ptA = pairA.ptcross
714         ptB = pairB.ptcross
715
716         profile = ['C', self.num_seg] if ed.round_profile else self.profile_type
717
718         if len(vd.leds) <= 1:
719             vecA = ptA - vpos
720             vecB = ptB - vpos
721             offsetA = vecA.length
722             offsetB = vecB.length
723             section = self.profile_compute_by_offset(profile, vpos,
724                         vecA, offsetA, vecB, offsetB)
725         elif len(vd.leds) == 2:
726             vecA = ptA - vpos
727             vecB = ptB - vpos
728             section = self.profile_compute_by_vectors(profile,
729                         ptA, vecA, ptB, ed.vec.cross(vecB))
730         else:
731             edA = find(pairA.leds, lambda edd: edd != ed)
732             edB = find(pairB.leds, lambda edd: edd != ed)
733             vecA = edA.vec.copy()
734             if vecA.dot(edA.ptmid - vpos) < 0:
735                 vecA.negate()
736             vecB = edB.vec.copy()
737             if vecB.dot(edB.ptmid - vpos) < 0:
738                 vecB.negate()
739             section = self.profile_compute_by_vectors(profile,
740                         ptA, vecA, ptB, ed.vec.cross(vecB))
741
742         if not on_plane(section[0], face_plane(ed.facemain)):
743             section.reverse()
744         ed.cross_sections[icorner] = section
745         return section
746
747     # Construct the lattice for the rounding of an edge
748     def build_lattice(self, i, xsection1, xsection2, sh_section1, sh_section2):
749         if vec_approx_eq(xsection1[i], xsection2[i]):
750             lpts = [xsection1[i]]
751         else:
752             lpts = [xsection1[i], xsection2[i]]
753
754         if sh_section2 and sh_section2[i] and len(sh_section2[i]) > 0:
755             for pt in sh_section2[i]:
756                 if not (vec_approx_eq(pt, xsection2[i]) or vec_approx_eq(pt, xsection2[i+1])):
757                     lpts.append(pt)
758
759         lpts.append(xsection2[i + 1])
760         if not vec_approx_eq(xsection2[i + 1], xsection1[i + 1]):
761             lpts.append(xsection1[i + 1])
762
763         if sh_section1 and sh_section1[i] and len(sh_section1[i]) > 0:
764             lpt1 = []
765             for pt in sh_section1[i]:
766                 if not (vec_approx_eq(pt, xsection1[i]) or vec_approx_eq(pt, xsection1[i+1])):
767                     lpt1.append(pt)
768             lpt1.reverse()
769             lpts.extend(lpt1)
770
771         return lpts
772
773     # Compute the round border on an edge as a vmesh
774     def compute_mesh_edge(self, ed):
775         xsection1 = ed.cross_sections[0]
776         xsection2 = ed.cross_sections[1]
777         sh_section1 = ed.sharp_sections[0]
778         sh_section2 = ed.sharp_sections[1]
779  
780         nblat = len(xsection1) - 1
781         n2 = nblat // 2
782         n1 = nblat - n2
783  
784         # Part close to main face
785         face1 = ed.facemain
786         mesh1 = []
787         for i in range(0, n1):
788             mesh1.append(self.build_lattice(i, xsection1, xsection2, sh_section1, sh_section2))
789         if n1 > 0:
790             normalref1 = self.compute_normal_reference(ed, face1, xsection1[0], xsection1[1])
791
792         # Part close to the other face
793         face2 = ed.lfaces[1] if ed.lfaces[0] == ed.facemain else ed.lfaces[0]
794         mesh2 = []
795         for i in range(n1, nblat):
796             mesh2.append(self.build_lattice(i, xsection1, xsection2, sh_section1, sh_section2))
797         if n2 > 0:
798             normalref2 = self.compute_normal_reference(ed, face2, xsection1[n1+1], xsection1[n1])
799
800         # Creating the vmesh, single or double
801         ed.vmesh = []
802         if edge_reversed_in_face(ed.edge, face1) == edge_reversed_in_face(ed.edge, face2):
803             if n1 > 0:
804                 ed.vmesh.append([mesh1, face1, normalref1])
805             if n2 > 0:
806                 ed.vmesh.append([mesh2, face2, normalref2])
807         else:
808             ed.vmesh.append([mesh1 + mesh2, face1, normalref1])
809
810         # Creating the border edges
811         ed.vborders = []
812         ed.vborders.append([[xsection1[0], xsection2[0]], 'S'])
813         ed.vborders.append([[xsection1[-1], xsection2[-1]], 'S'])
814
815         # Termination edges
816         xs = [xsection1, xsection2]
817         for i in range(0, 2):
818             if len(ed.corners[i].leds) == 1:
819                 ed.vborders.append([xs[i], 'P'])
820
821     def compute_mesh_edge_triangulated(self, vd, ed1, ed2, seg1, seg2):
822         icorner1 = 0 if ed1.corners[0] == vd else 1
823         icorner2 = 0 if ed2.corners[0] == vd else 1
824         xsection1 = ed1.cross_sections[icorner1]
825         xsection2 = ed2.cross_sections[icorner2]
826         reversed = (xsection1[0] - xsection2[0]).length > (xsection1[0] - xsection2[-1]).length and \
827                    (xsection1[-1] - xsection2[-1]).length >= (xsection1[-1] - xsection2[0]).length
828
829         nblat = len(xsection1) - 1
830         n2 = nblat // 2
831         n1 = nblat - n2
832
833         # Part close to main face
834         face1 = ed1.facemain
835         mesh1 = []
836         for i in range(0, n1):
837             mesh1.append(self.build_lattice(i, xsection1, xsection2, None, None))
838         if n1 > 0:
839             normalref1 = self.compute_normal_reference(ed1, face1, xsection1[0], xsection1[1])
840
841         # Part close to the other face
842         if reversed:
843             face2 = ed2.facemain
844         else:
845             face2 = find(ed2.lfaces, lambda f: f != ed2.facemain)
846         mesh2 = []
847         for i in range(0, nblat):
848             mesh1.append(self.build_lattice(i, xsection1, xsection2, None, None))
849         if n2 > 0:
850             normalref2 = self.compute_normal_reference(ed2, face2, xsection1[n1+1], xsection1[n1])
851
852         # Creating the vmesh, single or double
853         if n1 > 0:
854             self.lst_vmesh_triangulated.append([mesh1, face1, normalref1])
855         if n2 > 0:
856             self.lst_vmesh_triangulated.append([mesh2, face2, normalref2])
857
858         # Creating the border edges
859         if xsection1[0] != xsection2[0]:
860             self.lst_vborders_triangulated.append([[xsection1[0], xsection2[0]], 'S'])
861         if xsection1[-1] != xsection2[-1]:
862             self.lst_vborders_triangulated.append([[xsection1[-1], xsection2[-1]], 'S'])
863
864     def sort_corners_for_orientation(self, vda, vdb):
865         eda = vda.gold_ed
866         edb = vdb.gold_ed
867         if vda.convex:
868             return -1
869         if vdb.convex:
870             return 1
871         if eda and edb:
872             return  cmp(eda.golden, edb.golden)
873         elif eda:
874             return -1
875         elif edb:
876             return 1
877         else:
878             return 0
879
880     # Compute right orientation at corner
881     def orientation_at_corner(self, vd):
882         edgold = vd.gold_ed
883         if not edgold:
884             return
885         ledface = []
886         for ed in vd.leds:
887             for face in ed.lfaces:
888                 if ed == edgold:
889                     continue
890                 if self.ed_common_face(ed, face, edgold):
891                     iface = 0 if ed.lfaces[0] == face else 1
892                     ledface.append([ed, iface])
893                     break
894         main = 0 if find(ledface, lambda ll: ll[0].facemain) else 1
895         for ll in ledface:
896             ed = ll[0]
897             iface = ll[1]
898             iface2 = (iface + main) % 2
899             if not ed.facemain:
900                 ed.facemain = ed.lfaces[iface2]
901             catena = ed.catenas[iface2]
902             if catena.nbsmall <= 0:
903                 self.assign_ed_facemain(catena)
904             ed.catenas[iface].nbsmall += 1
905
906     # Find if 2 edges share a common face
907     def ed_common_face(self, ed0, face0, ed1):
908         for face in ed1.lfaces:
909             if parallel(face.normal, face0.normal):
910                 return True
911         return False
912
913     # Compute all face orientations - needed for odd number of segments
914     def compute_face_orientation(self):
915         # Starting with the round corners
916         lcorners = list(self.hsh_corners.values())
917         lcorners.sort(key = functools.cmp_to_key(
918             lambda x, y : self.sort_corners_for_orientation(x,y)))
919
920         hsh = {}
921         for vd in lcorners:
922             if vd in hsh:
923                 continue
924             hsh[vd] = True
925             edgold = vd.gold_ed
926             if not edgold:
927                 continue
928             self.orientation_at_corner(vd)
929             vd2 = edgold.corners[1] if edgold.corners[0] == vd else edgold.corners[0]
930             if vd2 and vd2 not in hsh:
931                 hsh[vd2] = True
932                 self.orientation_at_corner(vd)
933
934         # Assigning the main faces to edge
935         for catena in self.lst_catenas:
936             if catena.nbsmall == 0:
937                 self.assign_ed_facemain(catena)
938
939         # Remaining edges
940         for ed in self.hsh_ed.values():
941             if not ed.facemain:
942                 ed.facemain = ed.lfaces[0]
943
944     # Propagate face orientation on a catena
945     def assign_ed_facemain(self, catena):
946         for ll in catena.chain:
947             ed = ll[0]
948             iface = ll[1]
949             other_catena = ed.catenas[1] if ed.catenas[0] == catena else ed.catenas[1]
950             if not ed.facemain:
951                 ed.facemain = ed.lfaces[iface]
952             other_catena.nbsmall += 1
953
954     # Scan all corners for determining golden edges
955     def corner_scan_all(self):
956         # find golden edge if vd has valence 3 or 4
957         for vd in self.hsh_corners.values():
958             self.corner_scan_golden(vd)
959         # Final golden edge calc, for valence 3
960         for vd in self.hsh_corners.values():
961             self.corner_determine_golden(vd)
962
963         # For valence 3, which have round profile?
964         # (TODO: is it really necessary to do this twice?)
965         for vd in self.hsh_corners.values():
966             self.corner_round_profile(vd)
967         for vd in self.hsh_corners.values():
968             self.corner_round_profile(vd)
969
970     # Search and propagate the golden edges.
971     # Only assigns a value if valence is 3 or 4.
972     # In those caes, sets the vd.gold_ed to
973     # the corner's ed that is best for golden edge.
974     # When valence is 3, picks the golden edge
975     # (somehow) and sets the edge's aligned property
976     # to True if the other pairs edges intersect.
977     def corner_scan_golden(self, vd):
978         if len(vd.leds) == 4:
979             vd.leds.sort(key = functools.cmp_to_key(compare_gold_ed))
980             vd.gold_ed = vd.leds[0]
981
982         if len(vd.leds) != 3:
983             return
984
985         # Identifying convex corners
986         leds = vd.leds
987         pairs = vd.pairs
988         for pair in pairs:
989             ed1 = pair.leds[0]
990             ed2 = pair.leds[1]
991             ed0 = find(leds, lambda ed: ed != ed1 and ed != ed2)
992             if pair.convex:
993                 ed0.golden = -1
994                 vd.gold_ed = ed0
995             otherpairs = [p for p in pairs if p != pair]
996             if ed1 in otherpairs[0].leds:
997                 pair1 = otherpairs[0]
998                 pair2 = otherpairs[1]
999             else:
1000                 pair1 = otherpairs[1]
1001                 pair2 = otherpairs[0]
1002             ed0.aligned = intersect_line_line(
1003                 [pair1.ptcross, ed1.vec],
1004                 [pair2.ptcross, ed2.vec])
1005
1006     # Compare two edges to determine which one has to be gold.
1007     # If the vertex is convex, then the 'golden' member of the
1008     # edge should be set to something to help compare.
1009     # Else if the cosines of the angles the edges faces
1010     # differ from 90 differ a lot then the one that
1011     # is more acute wins.
1012     # Else the one that is more closely aligned with the
1013     # golden axis wins.
1014     # Else the longer edge wins.
1015     def compare_gold_ed(self, vd, eda, edb):
1016         if vd.convex:
1017             return cmp(eda.golden, edb.golden)
1018         if eda.aligned and not edb.aligned:
1019             return -1
1020         elif edb.aligned and not eda.aligned:
1021             return 1
1022         cosa = eda.cos
1023         cosb = edb.cos
1024         val = 0 if abs(cosa - cosb) < 0.5 else cmp(cosa, cosb)
1025         if val == 0:
1026             val = -cmp(abs(eda.vec.dot(self.golden_axis)), abs(edb.vec.dot(self.golden_axis)))
1027         if val == 0:
1028             val = -cmp(eda.length, edb.length)
1029         return val
1030
1031     # Determine the golden edge at a 3 edges corner
1032     def corner_determine_golden(self, vd):
1033         if len(vd.leds) != 3:
1034             return
1035         lsgold = vd.leds[::]
1036         lsgold.sort(key = functools.cmp_to_key(lambda x, y: self.compare_gold_ed(vd, x, y)))
1037         ed0 = lsgold[0]
1038         if not vd.gold_ed:
1039             vd.gold_ed = ed0
1040         for pair in vd.pairs:
1041             if ed0 in pair.leds:
1042                 continue
1043             vd.round_pair = pair
1044
1045     # Calculate whether edges at a vertex should have a round profile
1046     def corner_round_profile(self, vd):
1047         if len(vd.leds) != 3:
1048             return
1049         ed0 = vd.gold_ed
1050         ledothers = [ed for ed in vd.leds if ed != ed0]
1051         ed1 = ledothers[0]
1052         ed2 = ledothers[1]
1053  
1054         ed0.round_profile = self.use_round_profile(ed0)
1055         if self.use_round_profile(ed1) or self.use_round_profile(ed2):
1056             ed1.round_profile = True
1057             ed2.round_profile = True
1058
1059     # Get the profiles for the edge depending on the hybrid settings
1060     def use_round_profile(self, ed):
1061         if ed.round_profile:
1062             return True
1063         if self.mode_profile == -1:
1064             return False
1065         elif self.mode_profile == 0:
1066             return ed.golden == -1
1067         else:
1068             return ed.golden == -1 or ed.corners[0].gold_ed == ed or ed.corners[1].gold_ed == ed
1069  
1070     # Calculate rounding at corner, if applicable
1071     def rounding_compute(self, vd):
1072         if not self.mode_rounding:
1073             return
1074         if self.num_seg == 1 or (self.mode_sharp and not vd.convex) or len(vd.leds) !=3:
1075             return
1076         # Getting the golden edge and determining the metal pair
1077         ed_gold = vd.gold_ed
1078         pair_gold = find(vd.pairs, lambda pair: ed_gold not in pair.leds)
1079         pair_silver = None
1080         pair_bronze = None
1081         ed_silver = None
1082         ed_bronze = None
1083         facemain = ed_gold.facemain
1084         otherface = ed_gold.lfaces[1] if ed_gold.lfaces[0] == facemain else ed_gold.lfaces[0]
1085         for pair in vd.pairs:
1086             if pair == pair_gold:
1087                 continue
1088             if on_plane(pair.ptcross, face_plane(facemain)):
1089                 pair_silver = pair
1090                 ed_silver = pair.leds[1] if pair.leds[0] == ed_gold else pair.leds[0]
1091             else:
1092                 pair_bronze = pair
1093                 ed_bronze = pair.leds[1] if pair.leds[0] == ed_gold else pair.leds[0]
1094         if not (pair_silver and pair_bronze):
1095             return
1096
1097         # Calculate the planes for the golden edge
1098         gold_ptcross = pair_gold.ptcross
1099         plane_silver = [pair_silver.ptcross, ed_silver.vec]
1100         line_silver = [gold_ptcross, ed_silver.vec]
1101         plane_bronze = [pair_bronze, ed_bronze.vec]
1102         line_bronze = [gold_ptcross, ed_bronze.vec]
1103         pt_silver = intersect_line_plane([gold_ptcross, ed_silver.vec], [pair_silver.ptcross, ed_silver.vec])
1104         pt_bronze = intersect_line_plane([gold_ptcross, ed_bronze.vec], [pair_bronze.ptcross, ed_bronze.vec])
1105
1106         # Rounding is not materialized
1107         if not pt_silver or not pt_bronze or vec_approx_eq(pt_silver, pt_bronze) or \
1108                 vec_approx_eq(pt_silver, gold_ptcross) or vec_approx_eq(pt_bronze, gold_ptcross):
1109             return
1110
1111
1112         # Computing the rounding
1113         vpos = vd.vertex.co
1114         vec1 = ed_silver.ptmid - vpos
1115         vec2 = ed_bronze.ptmid - vpos
1116         normal2 = vec1.cross(vec2)
1117         offset1 = (pt_silver - gold_ptcross).length
1118         offset2 = (pt_bronze - gold_ptcross).length
1119         pair_gold.rounding = self.profile_compute_by_offset(['C', self.num_seg],
1120                 gold_ptcross, vec1, offset1, vec2, offset2)
1121
1122     # Corner calculation
1123     def corner_compute(self, vd):
1124         mode_sharp = self.mode_sharp
1125         n = len(vd.leds)
1126         if n == 1 or n == 2:
1127             self.corner_compute_12(vd)
1128         elif n == 3:
1129             if self.num_seg == 1:
1130                 self.corner_compute_3round(vd)
1131             elif (not mode_sharp and self.num_seg != 1) or vd.convex:
1132                 self.corner_compute_3round(vd)
1133             elif self.strict_offset:
1134                 self.corner_compute_any_sharp(vd)
1135             else:
1136                 self.corner_compute_3sharp(vd)
1137         elif n == 4:
1138             if mode_sharp:
1139                 self.corner_compute_any_sharp(vd)
1140             else:
1141                 self.corner_compute_round_4(vd)
1142         else:
1143             if mode_sharp:
1144                 self.corner_compute_any_sharp(vd)
1145             else:
1146                 self.corner_compute_star(vd)
1147  
1148     # Compute a corner with 1 or 2 edges (sharp)
1149     def corner_compute_12(self, vd):
1150         for ed in vd.leds:
1151             icorner = 0 if ed.corners[0] == vd else 1
1152             section = self.compute_sections_multi(ed, icorner)
1153             if len(vd.leds) == 1:
1154                 # Do we need an extra face between end of beveled
1155                 # edge and vd?  Usually yes, but not in certain cases.
1156                 # One case where we don't: if there are only 3 faces
1157                 # at the vertex and the 3rd face contains the
1158                 # beveled end completely.
1159                 needcornerface = True
1160                 vfaces = vd.vertex.link_faces
1161                 if len(vfaces) == 3:
1162                     f3 = find(vfaces, lambda f: f != ed.lfaces[0] and f != ed.lfaces[1])
1163                     if not f3:
1164                         print("whoops, couldn't find 3rd face")
1165                     bf3 = self.hsh_faces[f3.index]
1166                     # test segment containment by containment of midpoint
1167                     # in face - for this case, should be ok
1168                     mid = section[0].lerp(section[1], 0.5)
1169                     if bf3.contains_point(mid):
1170                         needcornerface = False
1171                 if needcornerface:
1172                     facepts = section + [vd.vertex.co]
1173                     norm = ed.lfaces[0].normal + ed.lfaces[1].normal
1174                     norm.normalize()
1175                     vd.vmesh = [[[facepts], ed.lfaces[0], norm]]
1176  
1177     # Compute a round corner with 3 edges
1178     def corner_compute_3round(self, vd):
1179         leds = vd.leds
1180
1181         # Using the golden edge and compute the golden section0
1182         # which is the profile for the end of the golden edge,
1183         # going from its main face to its non-main face.
1184         ed0 = vd.gold_ed
1185         icorner0 = 0 if ed0.corners[0] == vd else 1
1186         section0 = self.compute_sections_multi(ed0, icorner0)
1187
1188         # Computing the other edges
1189         # Pair A is the one for ed0 going around its facemain
1190         # Pair B is the remaining one
1191         iA = 0 if ed0.facemain == ed0.lfaces[0] else 1
1192         iB = 1 - iA
1193         pairA = ed0.pairs[2 * icorner0 + iA]
1194         pairB = ed0.pairs[2 * icorner0 + iB]
1195         ed1 = find(pairA.leds, lambda ed: ed != ed0 and \
1196                         self.ed_common_face(ed0, ed0.facemain, ed))
1197         ed2 = find(pairB.leds, lambda ed: ed != ed0 and ed != ed1)
1198         pair_other = find(vd.pairs, lambda pair: ed0 not in pair.leds)
1199
1200         # Computing the grid
1201         # Make lpts be an array of sections, where the start points
1202         # are the cross-point of the non-golden-edge pair (or, if that
1203         # is rounded, the rounding points for that), and the end points
1204         # are the points on the golden section (going from its facemain
1205         # to the other face).
1206         n0 = len(section0) - 1
1207         origin = pair_other.ptcross
1208         if pair_other.rounding:
1209             lorigin = pair_other.rounding[::]
1210             lorigin.reverse()
1211         else:
1212             lorigin = (n0+1) * [ None ]
1213             for i in range(0, n0+1):
1214                 lorigin[i] = origin
1215         vec0 = ed0.vec
1216         if icorner0 == 1:
1217             vec0 = vec0.copy()
1218             vec0.negate()
1219         normal = ed1.vec.cross(ed2.vec)
1220         vec = origin - vd.vertex.co
1221         lpts = []
1222         profile = ['C', self.num_seg] if (ed1.round_profile or ed2.round_profile) \
1223                 else self.profile_type
1224         for i in range(0, n0 + 1):
1225             lpt = self.profile_compute_by_vectors(profile, section0[i],
1226                 vec0, lorigin[i], normal)
1227             lpts.append(lpt)
1228         icorner1 = 0 if ed1.corners[0] == vd else 1
1229         icorner2 = 0 if ed2.corners[0] == vd else 1
1230
1231         # ed1 is the edge sharing the golden edge's facemain, so it
1232         # gets the first section in lpts
1233         section1 = lpts[0]
1234         if not on_plane(section1[0], face_plane(ed1.facemain)):
1235             section1 = section1[::]
1236             section1.reverse()
1237
1238         # ed2 is the other of the non-golden pair, so it gets the last
1239         # section in lpts
1240         section2 = lpts[-1]
1241         if not on_plane(section2[0], face_plane(ed2.facemain)):
1242             section2 = section2[::]
1243             section2.reverse()
1244
1245         ed1.cross_sections[icorner1] = section1
1246         ed2.cross_sections[icorner2] = section2
1247
1248         # Constructing the mesh.
1249         # Makes nseg strips of nseg quads (the first quad
1250         # in the strip will really be a tri unless this corner has rounding).
1251         # Strip i starts at the other-pair cross point (or the ith point on
1252         # it, if rounded), and proceeds to end at the edge between
1253         # (section0[i], section0[i+1]).
1254         vmesh = []
1255         lquads =[]
1256         n = len(lpts) - 2
1257         for i in range(0, n + 1):
1258             pts1 = lpts[i]
1259             pts2 = lpts[i + 1]
1260             m = len(pts1) - 2
1261             for j in range(0, m + 1):
1262                 if vec_approx_eq(pts1[j + 1], pts2[j + 1]):
1263                     pts = [pts1[j], pts1[j + 1], pts2[j]]
1264                 elif vec_approx_eq(pts1[j], pts2[j]):
1265                     pts = [pts1[j], pts1[j + 1], pts2[j + 1]]
1266                 else:
1267                     pts = [pts1[j], pts1[j + 1], pts2[j + 1], pts2[j]]
1268                 lquads.append(pts)
1269
1270         nb = self.num_seg
1271         n0 = nb // 2
1272         odd = (nb % 2) != 0
1273
1274         # Triangle corner
1275         if parallel(ed1.facemain.normal, ed0.facemain.normal):
1276             n1 = n0 - 1
1277             face1 = ed1.lfaces[1] if ed1.lfaces[0] == ed1.facemain else ed1.lfaces[0]
1278         else:
1279             n1 = n0 - 1 + odd
1280             face1 = ed1.facemain
1281         lq1 = []
1282         for i in range(0, nb):
1283             for j in range(0, n1 + 1):
1284                 lq1.append(lquads[i * nb + j])
1285         if len(lq1) > 0:
1286             quad = lquads[0]
1287             normalref = self.compute_normal_reference(ed1, face1, quad[0], quad[1])
1288             vmesh.append([lq1, face1, normalref])
1289
1290         # Side corner 1
1291         lq2 = []
1292         for i in range(0, n0 + odd):
1293             for j in range(n1 + 1, nb):
1294                 lq2.append(lquads[i * nb + j])
1295         if len(lq2) > 0:
1296             quad = lquads[n1 + 1]
1297             normalref = self.compute_normal_reference(ed1, ed0.facemain, quad[1], quad[0])
1298             vmesh.append([lq2, ed0.facemain, normalref])
1299
1300         # Side corner 2
1301         lq3 = []
1302         for i in range(n0 + odd, nb):
1303             for j in range(n1 + 1, nb):
1304                 lq3.append(lquads[i * nb + j])
1305         if parallel(ed2.facemain.normal, face1.normal):
1306             face2 = ed2.lfaces[1] if ed2.lfaces[0] == ed2.facemain else ed2.lfaces[0]
1307         else:
1308             face2 = ed2.lfaces[0] if ed2.lfaces[0] == ed2.facemain else ed2.lfaces[1]
1309         if len(lq3) > 0:
1310             quad = lquads[(n0 + odd) * nb + 1]
1311             normalref = self.compute_normal_reference(ed2, face2, quad[1], quad[0])
1312             vmesh.append([lq3, face2, normalref])
1313
1314         # Storing the mesh
1315         vd.vmesh = vmesh
1316
1317     # Compute round corner for termination with 4 edges
1318     def corner_compute_round_4(self, vd):
1319         # Computing the cross sections for each edge
1320         leds = vd.leds
1321         for ed in leds:
1322             icorner0 = 0 if ed.corners[0] == vd else 1
1323             self.compute_sections_multi(ed, icorner0)
1324
1325         # picking one edge
1326         ed0 = leds[0]
1327
1328         # looking for adjacent edges
1329         oface0 = ed0.lfaces[1] if ed0.facemain == ed0.lfaces[0] else ed0.lfaces[0]
1330         ed1 = find(leds, lambda ed: ed != ed0 and self.ed_common_face(ed0, ed0.facemain, ed))
1331         ed2 = find(leds, lambda ed: ed != ed0 and ed != ed1 and \
1332                         self.ed_common_face(ed0, oface, ed))
1333         ed4 = find(leds, lambda ed: ed != ed0 and ed != ed1 and ed != ed2)
1334
1335         # orientation of the edges
1336         icorner0 = 0 if ed0.corners[0] == vd else 1
1337         icorner1 = 0 if ed1.corners[0] == vd else 1
1338         icorner2 = 0 if ed2.corners[0] == vd else 1
1339         icorner4 = 0 if ed4.corners[0] == vd else 1
1340
1341         xsection0 = ed0.cross_sections[icorner0]
1342         xsection1 = ed1.cross_sections[icorner1]
1343         xsection2 = ed2.cross_sections[icorner2]
1344         xsection4 = ed4.cross_sections[icorner4]
1345  
1346         if xsection1[0] in xsection0:
1347             xfirst = xsection0
1348             xlast = xsection4
1349         else:
1350             xlast = xsection0
1351             xfirst = xsection4
1352
1353         if xfirst[0] in xsection1:
1354             xfirst = xfirst[::]
1355             xfirst.reverse()
1356         if xlast[0] in xsection1:
1357             xlast = xlast[::]
1358             xlast.reverse()
1359         if (xsection2[0] - xsection1[0]).length > (xsection2[0] - xsection1[-1]).length and \
1360             (xsection2[-1] - xsection1[0]).length < (xsection2[-1] - xsection1[-1]).length:
1361             xsection2 = xsection2[::]
1362             xsection2.reverse()
1363  
1364         # creating the grid sections
1365         profile0 = ['C', self.num_seg] if ed0.round_profile else self.profile_type
1366         vec1 = ed1.ptmid - vd.vertex.co
1367         vec2 = ed2.ptmid - vd.vertex.co
1368
1369         lpts = [xfirst]
1370         n = len(xsection1) - 2
1371         n1 = n // 2
1372         for i in range(1, n1 + 1):
1373             norm = (xsection1[i + 1] - xsection1[i]).cross(vec1)
1374             sec = self.profile_compute_by_vectors(profile0, xsection2[i], vec2,
1375                     xsection1[i], norm)
1376             sec.reverse()
1377             lpts.append(sec)
1378         for i in range(n1 + 1, n + 1):
1379             norm = (xsection2[i + 1] - xsection2[i]).cross(vec2)
1380             lpts.append(self.profile_compute_by_vectors(profile0, xsection1[i],
1381                     vec1, xsection2[i], norm))
1382         lpts.append(xlast)
1383
1384         # Constructing the vmesh
1385         vmesh = []
1386         lquads = []
1387         n = len(lpts) - 2
1388         for i in range(0, n + 1):
1389             pts1 = lpts[i]
1390             pts2 = lpts[i + 1]
1391             m = len(pts1) - 2
1392             for j in range(0, m + 1):
1393                 if vec_approx_eq(pts1[j + 1], pts2[j + 1]):
1394                     pts = [pts1[j], pts1[j + 1], pts2[j]]
1395                 elif vec_approx_eq(pts1[j], pts2[j]):
1396                     pts = [pts1[j], pts1[j + 1], pts2[j + 1]]
1397                 else:
1398                     pts = [pts1[j], pts1[j + 1], pts2[j + 1], pts2[j]]
1399                 lquads.append(pts)
1400
1401         # List of faces
1402         nb = self.num_seg
1403         n0 = nb // 2
1404         odd = (nb % 2) == 1
1405
1406         # First quadrant
1407         quad = lquads[0]
1408         pt = quad[0]
1409         ll = self.locate_point_face_4(pt, ed0, ed1, ed2, ed4)
1410         faceA = ll[0]
1411         edA = ll[1]
1412         edB = ll[2]
1413         lq = []
1414         ni = n0 + odd if parallel(faceA.normal, edB.facemain.normal) else n0
1415         nj = n0 + odd if faceA == edA.facemain else n0
1416         for i in range(0, ni):
1417             for j in range(0, nj):
1418                 lq.append(lquads[i * nb + j])
1419         if len(lq) > 0:
1420             normalref = self.compute_normal_reference(edA, faceA, quad[0], quad[1])
1421             vmesh.push([lq, faceA, normalref])
1422
1423         # second quadrant
1424         quad = lquads[nb - 1]
1425         pt = quad[1]
1426         ll = self.locate_point_face_4(pt, ed0, ed1, ed2, ed4)
1427         faceA = ll[0]
1428         edA = ll[1]
1429         edB = ll[2]
1430         ni2 = n0 + odd if parallel(faceA.normal, edB.facemain.normal) else n0
1431         for i in range(0, ni2):
1432             for j in range(nj, nb):
1433                 lq.append(lquads[i * nb + j])
1434         if len(lq) > 0:
1435             normalref = self.compute_normal_reference(edA, faceA, quad[1], quad[2])
1436             vmesh.append([lq, faceA, normalref])
1437
1438         # third quadrant
1439         quad = lquads[nb * (nb - 1)]
1440         pt = quad[3]
1441         ll = self.locate_point_face_4(pt, ed0, ed1, ed2, ed4)
1442         faceA = ll[0]
1443         edA = ll[1]
1444         edB = ll[2]
1445         lq = []
1446         nj = n0 + odd if faceA == edA.facemain else n0
1447         for i in range(ni, nb):
1448             for j in range(0, nj):
1449                 lq.append(lquads[i * nb + j])
1450
1451         if len(lq) > 0:
1452             normalref = self.compute_normal_reference(edA, faceA, quad[0], quad[1])
1453             vmesh.append([lq, faceA, normalref])
1454
1455         # fourth quadrant
1456         quad = lquads[nb * nb - 1]
1457         pt = quad[2]
1458         ll = self.locate_point_face_4(pt, ed0, ed1, ed2, ed4)
1459         faceA = ll[0]
1460         edA = ll[1]
1461         edB = ll[2]
1462         lq = []
1463         for i in range(ni2, nb):
1464             for j in range(nj, nb):
1465                 lq.append(lquads[i * nb + j])
1466         if len(lq) > 0:
1467             normalref = self.compute_normal_reference(edA, faceA, quad[1], quad[0])
1468             vmesh.append([lq, faceA, normalref])
1469
1470         # Storing the vmesh
1471         vd.mesh = vmesh
1472
1473     # Locate on which edge is the given point
1474     def locate_point_face_4(self, pt, ed0, ed1, ed2, ed4):
1475         for ll in [[ed0, ed1], [ed0, ed2], [ed4, ed1], [ed4, ed2]]:
1476             face = self.which_face_4(pt, ll[0], ll[1])
1477             if face:
1478                 return [face] + ll
1479         return None
1480
1481     # Determine on which face is a given point
1482     def which_face_4(self, pt, eda, edb):
1483         plane = [eda.ptmid, eda.vec.cross(edb.vec)]
1484         if not on_plane(pt, plane):
1485             return
1486         for face in eda.lfaces:
1487             if self.ed_common_face(eda, face, edb):
1488                 return face
1489         return None
1490
1491     # Orthogonal section to an edge at a vertex
1492     # Let ptA and ptB be the pair intersection points
1493     # at for the edge at the vertex.
1494     # Make a plane that goes through ptA and the
1495     # average normal of the two planes for the edge.
1496     # Calculate the cross section for the edge at the
1497     # vertex and project onto the plane, and return that.
1498     def orthogonal_section_ed(self, ed, vd):
1499         # getting the pairs and cross points
1500         icorner = 0 if ed.corners[0] == vd else 1
1501         iA = 0 if ed.facemain == ed.lfaces[0] else 1
1502         iB = 1 - iA
1503         pairA = ed.pairs[2 * icorner + iA]
1504         pairB = ed.pairs[2 * icorner + iB]
1505         ptA = pairA.ptcross
1506         ptB = pairB.ptcross
1507         vf1 = ed.lfaces[0].normal
1508         vf2 = ed.lfaces[1].normal
1509         if vf1.dot(vf2) <= 0:
1510             vf2 = vf2.copy()
1511             vf2.negate()
1512         vfmean = vf1.lerp(vf2, 0.5)
1513
1514         # computing the projection on plane
1515         plane = [ptA, vfmean.cross(ptB - ptA)]
1516         section = self.compute_profile_edge(ed)
1517         ed.cross_sections[icorner] = [intersect_line_plane([pt, ed.vec], plane) \
1518                                         for pt in section]
1519         return ed.cross_sections[icorner]
1520
1521     # Compute a round corner with 5 or more edges -
1522     # Triangulation of Rastapopoulos
1523     def corner_compute_star(self, vd):
1524         # Computing the cross sections for each edge
1525         # These cross sections are at the corner but projected onto a plane
1526         # (see comment for orthogonal_section_ed).
1527         lsec = [[ed, self.orthogonal_section_ed(ed, vd)] for ed in vd.leds]
1528
1529         # Finding the pivot point and plane that best fit cross points
1530         # ptpivot will be the point in the center of the star.
1531         # It is fac (0.5) of the way between the corner vertex and
1532         # a point on the best-fitting plane for points on the edge cross sections.
1533         nb = self.num_seg // 2 + 1
1534         lptcross = [ll[1][nb] for ll in lsec]
1535         plane = fit_plane_to_points(lptcross)
1536         vpos = vd.vertex.co
1537         ptproj = project_to_plane(vpos, plane)
1538         normal = vpos - ptproj
1539         fac = 0.5
1540         ptpivot = vpos.lerp(ptproj, fac)
1541         self.lst_mark_points.append(ptpivot)
1542
1543         # Create the mesh
1544         vmesh = []
1545         profile0 = ['C', nb]
1546         for ll in lsec:
1547             ed = ll[0]
1548             xsection = ll[1]
1549             # For edge ed, take each point in the cross section and make a profile going
1550             # from the pivot to that point, putting the results lpts.
1551             lpts = [self.profile_compute_by_vectors(profile0, pt, (pt - vpos), ptpivot, normal) \
1552                     for pt in xsection]
1553             lquads = []
1554             n = len(lpts) - 2
1555             # For each i, use the pivot->point on edge cross section profile
1556             # for i and i+1 to make tris and quads.  The first will be a tri.
1557             for i in range(0, n + 1):
1558                 pts1 = lpts[i]
1559                 pts2 = lpts[i + 1]
1560                 m = len(pts1) - 2
1561                 for j in range(0, m + 1):
1562                     if vec_approx_eq(pts1[j + 1], pts2[j + 1]):
1563                         pts = [pts1[j], pts1[j + 1], pts2[j]]
1564                     elif vec_approx_eq(pts1[j], pts2[j]):
1565                         pts = [pts1[j], pts1[j + 1], pts2[j + 1]]
1566                     else:
1567                         pts = [pts1[j], pts1[j + 1], pts2[j + 1], pts2[j]]
1568                     lquads.append(pts)
1569
1570             # Separating the vmesh in two parts
1571             odd = (self.num_seg % 2) == 1
1572             if odd == 0:
1573                 n1 = self.num_seg // 2 + odd
1574                 m1 = n1 * (nb + odd) - 1
1575             else:
1576                 n1 = self.num_seg // 2 + odd + 1
1577                 m1 = n1 * (nb - odd)
1578
1579             quad = lquads[0]
1580             faceref = ed.facemain
1581             normalref = self.compute_normal_reference(ed, faceref, quad[1], quad[0])
1582             vmesh.append([lquads[0:m1 + 1], faceref, normalref])
1583
1584             quad = lquads[-1]
1585             faceref = ed.lfaces[1] if ed.lfaces[0] == ed.facemain else ed.lfaces[0]
1586             normalref = self.compute_normal_reference(ed, faceref, quad[1], quad[0])
1587             if m1 >= 0:
1588                 vmesh.append([lquads[m1 + 1:], faceref, normalref])
1589
1590         vd.vmesh = vmesh
1591
1592     # Compute a sharp corner with 3 edges in standardized offset mode
1593     def corner_compute_3sharp(self, vd):
1594         leds = vd.leds
1595
1596         # Calculating the bisecting planes
1597         vpos = vd.vertex.co
1598         lplanes = []
1599         for pair in vd.pairs:
1600             ed1 = pair.leds[0]
1601             ed2 = pair.leds[1]
1602             ed0 = find(leds, lambda ed: ed != ed1 and ed != ed2)
1603             plane = plane_by_3_points(pair.ptcross, vpos, ed0.ptmid)
1604             lplanes.append([ed0, plane])
1605
1606         # Calculating the intersections of edge profiles with stop planes
1607         for ed in leds:
1608             cross_section = []
1609             section = compute_profile_edge(ed)
1610             ptmid = ed.ptmid
1611             vec = vpos - ptmid
1612             icorner = 0 if ed.corners[0] == vd else 1
1613             ed_planes = []
1614             for ll in lplanes:
1615                 if ll[0] != ed:
1616                     ed_planes.append(ll[1])
1617             for pt in section:
1618                 pt1 = intersect_line_plane([pt, vec], ed_planes[0])
1619                 pt2 = intersect_line_plane([pt, vec], ed_planes[1])
1620                 cross_section.append(pt1 \
1621                     if (pt1 - ptmid).length < (pt2 - ptmid).length else pt2)
1622             if not on_plane(cross_section[0], plane(ed.facemain)):
1623                 cross_section.reverse()
1624             ed.cross_sections[icorner] = cross_section
1625
1626         # Compute the corner triangle if the number of segments is odd
1627         n = self.num_seg // 2
1628         if n * 2 == self.num_seg:
1629             return
1630         lfaces = []
1631         for ed in leds:
1632             lfaces.append(ed.facemain)
1633         face0 = lfaces[0]
1634         if parallel(face0.normal, lfaces[1].normal):
1635             ieds = [0, 1]
1636         elif parallel(face0.normal, lfaces[2].normal):
1637             ieds = [0, 2]
1638         else:
1639             ieds = [1, 2]
1640         lpt = []
1641         ed1 = leds[ieds[0]]
1642         icorner1 = 0 if ed1.corners[0] == vd else 1
1643         ed2 = leds[ieds[1]]
1644         icorner2 = 0 if ed2.corners[0] == vd else 1
1645
1646         pt1 = ed1.cross_sections[icorner1][n]
1647         pt2 = ed1.cross_sections[icorner1][n+1]
1648         pt3 = ed2.cross_sections[icorner2][n+1]
1649         if pt3 == pt1 or pt3 == pt2:
1650             pt3 = ed2.cross_sections[icorner2][n]
1651
1652         lpt.extend([pt1, pt2, pt3]) # or should it be .append??
1653         faceref = ed1.facemain
1654         normalref = compute_normal_reference(ed1, faceref, pt1, pt2)
1655         vd.mesh = [[[lpt], faceref, normalref]]
1656
1657     # Compute a sharp corner with any number of edges
1658     def corner_compute_any_sharp(self, vd):
1659         leds = vd.leds
1660
1661         hshcross = {}
1662         for ed in leds:
1663             hshcross[ed] = []
1664
1665         # Calculating the sections
1666         for ed in leds:
1667             self.intersection_any_sharp(vd, ed)
1668
1669         # Filtering the edge termination
1670         # linter will be a hash from (ed, index in cross section for ed)
1671         # to one of the intersection data calculated for ed at vd.
1672         # We want the one that minimizes the length of the intersection
1673         # to the point on the mid-point edge for the index.
1674         linter = {}
1675         for inter in vd.sharp_inter:
1676             pt = inter[0]
1677             ed0 = inter[1]
1678             i0 = inter[2]
1679             icorner0 = 0 if ed0.corners[0] == vd else 1
1680             nsection0 = ed0.nsection
1681             make_index_valid(ed0.cross_sections[icorner0], i0)
1682             ptold = ed0.cross_sections[icorner0][i0]
1683             if ptold and (pt - nsection0[i0]).length > (ptold - nsection0[i0]).length:
1684                 continue
1685             ed0.cross_sections[icorner0][i0] = pt
1686             make_index_valid(inter, 5)
1687             inter[5] = 0
1688             make_index_valid(hshcross[ed0], i0)
1689             hshcross[ed0][i0] = [inter]
1690             linter[(ed0, i0)] = inter
1691
1692         # Assigning the intermediate points
1693         for inter in linter.values():
1694             pt = inter[0]
1695             ed1 = inter[3]
1696             j1 = inter[4]
1697             icorner1 = 0 if ed1.corners[0] == vd else 1
1698             ptcross = ed1.cross_sections[icorner1][j1]
1699             if vec_approx_eq(pt, ptcross):
1700                 continue
1701             inter = inter[::]
1702             line = [ptcross, ed1.cross_sections[icorner1][j1 + 1] - ptcross]
1703
1704             origin = ed1.cross_sections[icorner1][j1]
1705             ptmid = ed1.cross_sections[icorner1][j1 + 1]
1706             vec0 = origin - ptmid
1707
1708             inter[5] = vec0.angle(pt - ptmid)
1709
1710             hsh = hshcross[ed1][j1]
1711             hsh.append(inter)
1712             hsh.sort(key = lambda inter: inter[5])
1713             make_index_valid(ed1.sharp_sections[icorner1], j1)
1714             ed1.sharp_sections[icorner1][j1] = [inter[0] for inter in hsh]
1715
1716         # Identifying the holes
1717         hsh_edplanes = {}
1718         for ed in leds:
1719             lcross = hshcross[ed]
1720             n0 = len(lcross) - 2
1721             for i in range(0, n0 + 1):
1722                 linter = lcross[i] + [lcross[i + 1][0]]
1723                 n1 = len(linter) - 2
1724                 for j in range(0, n1 + 1):
1725                     inter1 = linter[j]
1726                     inter2 = linter[j + 1]
1727                     lled = []
1728                     edc = None
1729                     for edd in [inter1[1], inter1[3], inter2[1], inter2[3]]:
1730                         if edd in lled:
1731                             edc = edd
1732                         else:
1733                             lled.append(edd)
1734                     if len(lled) > 2:
1735                         self.lst_mark_points.extend([inter1[0], inter2[0]])
1736                         pt = edc.nsection[i].lerp(edc.nsection[i + 1], 0.5)
1737                         plane = [pt, (edc.nsection[i + 1] - edc.nsection[i]).cross(edc.vec)]
1738                         key = (edc, i)
1739                         hsh_edplanes[key] = [key, edc, i, plane, inter1[0], inter2[0]]
1740                         self.lst_mark_points.append(pt)
1741
1742         # Finding the plane intersections
1743         lst_loops = self.sharp_find_loops(hsh_edplanes)
1744         for loop in lst_loops:
1745             for i in range(0, len(loop)):
1746                 lst_insert = self.sharp_intersect_planes(vd, loop)
1747                 if lst_insert:
1748                     for ll in lst_insert:
1749                         self.sharp_insert_in_section(vd, ll[0], ll[1], ll[2])
1750                     break
1751
1752     # Compute the section for an edge in Sharp mode at a vertex
1753     # Sets vd.sharp_inter to a list of data about where lines on
1754     # the cross section for ed0 intersect lines on segments
1755     # of cross sections of other edges at vd.
1756     # Each element of list is:
1757     # [intersection pt, ed0, index in ed0's cross section,
1758     #  ed1 (another edge), index in ed1's cross section]
1759     def intersection_any_sharp(self, vd, ed0):
1760         nsection0 = self.compute_profile_edge(ed0)
1761         n0 = len(nsection0) - 1
1762         vec0 = ed0.vec
1763         for ed1 in vd.leds:
1764             if ed1 == ed0:
1765                 continue
1766             vec1 = ed1.vec
1767             nsection1 = self.compute_profile_edge(ed1)
1768             for i0 in range(0, n0 + 1):
1769                 pt0 = nsection0[i0]
1770                 line0 = [pt0, vec0]
1771                 for j1 in range(0, n0):
1772                     pt = self.intersect_between_two_lines(line0, vec1,
1773                                 nsection1[j1], nsection1[j1+1])
1774                     if pt:
1775                         vd.sharp_inter.append([pt, ed0, i0, ed1, j1])
1776
1777     # Determine if a line cuts a segment defined by two points and a vector.
1778     # line0 is the line we are trying to intersect.
1779     # Two other lines are defined by direction v1 through points pt1A and pt1B.
1780     # Where line0 intersections the plane defined by those other two lines,
1781     # the segment in question is between the two lines at the closest points
1782     # to the intersection point.
1783     def intersect_between_two_lines(self, line0, vec1, pt1A, pt1B):
1784         plane1 = [pt1A, (pt1B - pt1A).cross(vec1)]
1785         pt = intersect_line_plane(line0, plane1)
1786         if not pt:
1787             return None
1788         ptprojA = project_to_line(pt, [pt1A, vec1])
1789         ptprojB = project_to_line(pt, [pt1B, vec1])
1790         vA = ptprojA - pt
1791         if vA.length < EPSILON:
1792             return pt
1793         vB = ptprojB - pt
1794         if vB.length < EPSILON:
1795             return pt
1796         if vA.dot(vB) <= 0.0:
1797             return pt
1798         else:
1799             return None
1800
1801     # Identify the loops in the holes
1802     def sharp_find_loops(self, hsh_edplanes):
1803         lplanes = hsh_edplanes.values()
1804
1805         # Loop on edges to det
1806         hshed = {}
1807         lst_loops = []
1808         loop = []
1809
1810         while True:
1811             # Resuming or continuing at current loop end, or initiating a new loop
1812             if len(loop) > 0:
1813                 edp0 = loop[-1][1]
1814                 ptend = edp0[4] if edp0[5] == loop[-1][0] else edp0[5]
1815             else:
1816                 edp0 = find(lplanes, lambda edp: edp[0] not in hshed)
1817                 if not edp0:
1818                     break
1819                 ptend = edp0[5]
1820                 loop = [[edp0[4], edp0]]
1821             hshed[edp0[0]] = 1
1822
1823             # Getting new segment
1824             edp1 = find(lplanes, lambda edp: edp[0]!= edp0[0] and \
1825                         (edp[0] not in hshed or hshed[edp[0]] != -1) and \
1826                         (vec_approx_eq(edp[4], ptend) or vec_approx_eq(edp[5], ptend)))
1827             if not edp1:
1828                 break
1829
1830             # Checking if segment was already set
1831             for i, ll in enumerate(loop):
1832                 if ptend == ll[0]:
1833                     newloop = [a[1] for a in loop[i:]]
1834                     for edp in newloop:
1835                         hshed[edp[0]] = -1
1836                     lst_loops.append(newloop)
1837                     loop[i:] = []
1838                     edp1 = None
1839
1840             # New segment in loop
1841             if edp1:
1842                 loop.append([ptend, edp1])
1843
1844         lst_loops.append([a[1] for a in loop if len(loop) > 0])
1845         return lst_loops
1846
1847     # Determinethe intersection of planes for sharp corners.
1848     # Progressive algorithm, based on heuristics
1849     def sharp_intersect_planes(self, vd, lplanes):
1850
1851         # Sorting the planes by inclinations
1852         # lplanes = self.sharp_sort_planes_by_inclination(vd, lplanes)
1853
1854         # Algorithm to explore intersections of planes by group of 3
1855         n = len(lplanes)
1856         for i0 in range(0, n):
1857             lst_insert = []
1858             lst_pt = []
1859             for i in range(i0, n + i0):
1860                 icur = i0 % n
1861                 inext = (i + 1) % n
1862                 iprev = (i + 2) % n
1863                 lst_3planes = [lplanes[icur], lplanes[inext], lplanes[iprev]]
1864                 ptinter = self.sharp_compute_intersect_planes(vd, lplanes, lst_3planes)
1865                 if not ptinter:
1866                     continue
1867                 lst_pt.append(ptinter)
1868                 for edp in lst_3planes:
1869                     lst_insert.append([edp[1], edp[2], ptinter])
1870                 if len(lst_pt) == n - 2:
1871                     for pt in lst_pt:
1872                         self.lst_mark_points.append(pt)
1873                     return lst_insert
1874         return None
1875
1876     # Determine the intersection point between 3 planes, and check if valid
1877     def sharp_compute_intersect_planes(self, vd, all_planes, lst_3planes):
1878         # Computing the intersection of the 3 planes
1879         planes = [edp[3] for edp in lst_3planes]
1880         line = intersect_plane_plane(planes[0], planes[1])
1881         if not line:
1882             return None
1883         ptinter = intersect_line_plane(line, planes[2])
1884         if not ptinter:
1885             return None
1886         if len(all_planes) == 3:
1887             return ptinter
1888
1889         # List of all other planes
1890         otherplanes = [p for p in all_planes if p not in lst_3planes]
1891
1892         # Check if point is not 'above' otherplane
1893         vpos = vd.vertex.co
1894         for edp in otherplanes:
1895             plane = edp[3]
1896             if on_plane(ptinter, plane):
1897                 continue
1898             vdproj = project_to_plane(vpos, plane)
1899             ptproj = project_to_plane(ptinter, plane)
1900             if (vdproj - vpos).dot(ptproj - ptinter) > 0:
1901                 # Above
1902                 return None
1903         return ptinter
1904
1905     # Insert an intermediate point for the latte
1906     def sharp_insert_in_section(self, vd, ed, j, ptinter):
1907         icorner = 0 if ed.corners[0] == vd else 1
1908         sharp_section = ed.sharp_sections[icorner][j]
1909
1910         # No point already in the intermediate section
1911         if not (sharp_section and len(sharp_section) > 0):
1912             ed.sharp_sections[icorner][j] = [ptinter]
1913             return
1914
1915         # Inserting the point in the right place
1916         ptmid = ed.cross_sections[icorner][j + 1]
1917         vec0 = ed.cross_sections[icorner][j] - ptmid
1918         angle0 = vec0.angle(ptinter - ptmid)
1919         for i, pt in enumerate(sharp_section):
1920             if pt == ptinter:
1921                 return
1922             angle = vec0.angle(pt - ptmid)
1923             if angle > angle0:
1924                 if i == 0:
1925                     ed.sharp_sections[icorner][j] = [ptinter] + sharp_section
1926                 else:
1927                     ed.sharp_sections[icorner][j] = sharp_section[0:i] + \
1928                             [ptinter] + sharp_section[i:]
1929                 return
1930         ed.sharp_section[icorner][j].append(ptinter)
1931
1932
1933     # Compute the normal reference at a position of the edge or corner profile,
1934     # This is done for the right orientation of faces created
1935     def compute_normal_reference(self, ed, face, pt1, pt2):
1936         iface = 0 if ed.lfaces[0] == face else 1
1937         vy = ed.lvecins[iface] + face.normal
1938         vec = pt2 - pt1
1939         return vec.cross(vy)
1940
1941     def compute_face(self, fc):
1942         f = fc.face
1943         for i, bmv in enumerate(fc.bmverts):
1944             if bmv.index in self.hsh_corners:
1945                 v = self.hsh_corners[bmv.index]
1946                 pr = self.pair_for_face(v.pairs, f)
1947                 if pr:
1948                    fc.newpts[i] = [pr.ptcross]
1949                 else:
1950                     # This is a face that is not adjacent to
1951                     # a beveled edge, yet there is a beveled
1952                     # edge going into this corner.
1953                     # What to do depends on whether or
1954                     # not this face is adjacent to a face
1955                     # that is adjacent to a beveled edge.
1956
1957                     # One case is that this is a valence-three corner
1958                     # with only one beveled edge,
1959                     # and this is the third (unaffected) face.
1960                     # We need to cut the corner off this face if
1961                     # we are in the case where the beveled end
1962                     # is in the plane of this face - we should have
1963                     # a corner mesh, if so.
1964                     # TODO: this corner cutting may happen even in
1965                     # valence > 3 cases, but hard to do.
1966                     if len(v.vertex.link_edges) == 3 and not v.vmesh:
1967                        ed = v.leds[0]
1968                        icorner = 0 if ed.corners[0] == v else 1
1969                        section = ed.cross_sections[icorner]
1970                        # Now need to find if we have to
1971                        # reverse the section.
1972                        # Find the pairs.
1973                        e1 = f.loops[i].edge
1974                        e2 = f.loops[i].link_loop_prev.edge
1975                        for f1 in e1.link_faces:
1976                            if f1 != f:
1977                                pr1 = self.pair_for_face(v.pairs, f1)
1978                                if pr1:
1979                                    break
1980                        for f2 in e2.link_faces:
1981                            if f2 != f:
1982                                pr2 = self.pair_for_face(v.pairs, f2)
1983                                if pr2:
1984                                    break
1985                        if not pr1 or not pr2:
1986                            print("whoops, couldn't find term face pairs")
1987                            # just so we won't create a dup face:
1988                            fc.newpts[i] = [v.vertex.co]
1989                        else:
1990                            if vec_approx_eq(pr2.ptcross, section[0]):
1991                                fc.newpts[i] = section
1992                            else:
1993                                rsection = section[::]
1994                                rsection.reverse()
1995                                fc.newpts[i] = rsection
1996                     elif len(v.vertex.link_edges) > 3:
1997                         # Either or both of the edges into this vertex
1998                         # may have been split because the adjacent face
1999                         # was adjacent to a beveled edge.
2000                         e1 = f.loops[i].edge
2001                         f1 = find(e1.link_faces, lambda g: g != f)
2002                         e2 = f.loops[i].link_loop_prev.edge
2003                         f2 = find(e2.link_faces, lambda g: g != f)
2004                         nco1 = None
2005                         nco2 = None
2006                         for ed in v.leds:
2007                             if f in ed.lfaces:
2008                                 continue
2009                             if f1 in ed.lfaces:
2010                                 pr1 = self.pair_for_face(v.pairs, f1)
2011                                 if pr1:
2012                                     nco1 = pr1.ptcross
2013                             if f2 in ed.lfaces:
2014                                 pr2 = self.pair_for_face(v.pairs, f2)
2015                                 if pr2:
2016                                     nco2 = pr2.ptcross
2017                         fc.newpts[i] = [v.vertex.co]
2018                         if nco1:
2019                             fc.newpts[i] = fc.newpts[i] + [nco1]
2020                         if nco2:
2021                             fc.newpts[i] = [nco2] + fc.newpts[i]
2022
2023     def pair_for_face(self, lpairs, f):
2024         for pr in lpairs:
2025             if pr.lfaces[0] == f:
2026                 return pr
2027             if pr.lfaces[1] == f:
2028                 return pr
2029         return None
2030
2031     # Catena calculations: chain of edges with related offsets
2032  
2033     # Compute the extension of a catena for an edge, and its face and corner
2034     def catena_extend(self, catena, chain, ed, iface, icorner):
2035         k = 2 * icorner + iface
2036         if k >= len(ed.pairs):
2037             return None  # shouldn't happen
2038         pair = ed.pairs[k]
2039         if not pair or pair.alone:
2040             return None
2041         # should only be two ed's in pair.leds,
2042         # one is for ed, the other is ed2
2043         ed2 = find(pair.leds, lambda edd: edd != ed)
2044         n = 0
2045         for i, pair2 in enumerate(ed2.pairs):
2046             if pair2 == pair:
2047                 n = i
2048                 break
2049         iface2 = n % 2
2050         if ed2.catenas[iface2] == catena:
2051             return None
2052         icorner2 = (n - iface2) // 2
2053         icorner2 = (icorner2 + 1) % 2
2054         chain.append([ed2, iface2])
2055         ed2.catenas[iface2] = catena
2056         return [ed2, iface2, icorner2]
2057
2058     # Compute the half chain in a direction for an edge.
2059     # This is the extension of the chain for (ed, iface) in the
2060     # direction given by the end of the edge whose vertex
2061     # has index icorner.
2062     def catena_compute_half_by_face(self, catena, ed, iface, icorner):
2063         chain = []
2064         ll = [ed, iface, icorner]
2065         while True:
2066             ll = self.catena_extend(catena, chain, ll[0], ll[1], ll[2])
2067             if not ll or ll[0] == ed:
2068                 break
2069         return chain
2070
2071     # Compute the catena for an initial edge.
2072     # The catena is for the edge ed as associated
2073     # with the side of the edge indicated by index
2074     # iface in its faces.
2075     def catena_compute(self, ed, iface):
2076         catena = BCatena()
2077         self.lst_catenas.append(catena)
2078         ed.catenas[iface] = catena
2079         chain1 = self.catena_compute_half_by_face(catena, ed, iface, 0)
2080         chain2 = []
2081         if len(chain1) == 0 or chain1[-1] == None or chain1[-1][0] != ed:
2082             chain2 = self.catena_compute_half_by_face(catena, ed, iface, 1)
2083         chain2.reverse()
2084         catena.chain = chain2 + [[ed, iface]] + chain1
2085         return catena
2086
2087     # Compute all the catenas in the selection.
2088     # There are two catenas for each BEdge: one for each incident face.
2089     # The catena is a chain - list of [ed, face-index] pairs that
2090     # traverse along matched-up pairs as computed at each vertex.
2091     def catena_compute_all(self):
2092         for ed in self.hsh_ed.values():
2093             for iface in range(0, 2):
2094                 if ed.catenas[iface] is None:
2095                     self.catena_compute(ed, iface)
2096
2097         # sorting the eds by angle
2098         for i, catena in enumerate(self.lst_catenas):
2099             catena.leds = [ll[0] for ll in catena.chain]
2100             catena.leds.sort(key = functools.cmp_to_key(lambda ed1, ed2: cmp(ed1.cos, ed2.cos)))
2101
2102         # sorting the catenas
2103         for i, catena in enumerate(self.lst_catenas):
2104             self.catena_sort(catena)
2105
2106     def catena_offset_all(self):
2107         for catena in self.lst_catenas:
2108             icur = self.catena_begin_ed(catena)
2109             while self.catena_propagate_offset_factors(catena, icur, 1):
2110                 icur += 1
2111             while self.catena_propagate_offset_factors(catena, icur, -1):
2112                 icur -= 1
2113
2114     def catena_begin_ed(self, catena):
2115         # Assigning 1 to the first edge in the sorted list
2116         ed = catena.leds[0]
2117         for icur, ll in enumerate(catena.chain):
2118             if ll[0] == ed:
2119                 if self.strict_offset:
2120                      ed.lfactors[ll[1]] = 1.0
2121                 return icur
2122  
2123     # Propagate the offset factors from an edge to the next one
2124     def catena_propagate_offset_factors(self, catena, icur, incr):
2125         chain = catena.chain
2126
2127         # Checking if end of chain
2128         inext = icur + incr
2129         if inext < 0 or inext >= len(catena.chain):
2130             return False
2131         llnext = catena.chain[inext]
2132  
2133         # Current edge
2134         llcur = catena.chain[icur]
2135         edcur = llcur[0]
2136         ifacecur = llcur[1]
2137         edgecur = edcur.edge
2138         facecur = edcur.lfaces[ifacecur]
2139         ptmidcur = edcur.ptmid
2140         factorcur = edcur.lfactors[ifacecur]
2141
2142         # Next edge
2143         ednext = llnext[0]
2144         ifacenext = llnext[1]
2145         edgenext = ednext.edge
2146         facenext = ednext.lfaces[ifacenext]
2147         ptmidnext = ednext.ptmid
2148
2149         # Computing the intersection of the two face planes
2150         normalcur = facecur.normal
2151         normalnext = facenext.normal
2152         if parallel(normalcur, normalnext):
2153             if self.strict_offset:
2154                 ednext.lfactors[ifacenext] = edcur.lfactors[ifacecur]
2155             return True
2156         lineinter = intersect_plane_plane([ptmidcur, normalcur], [ptmidnext, normalnext])
2157
2158         # Computing the intersection of the offset lines with the intersection of faces
2159         ptcur = intersect_line_line(edcur.parallels[ifacecur], lineinter)
2160         ptnext = intersect_line_line(ednext.parallels[ifacenext], lineinter)
2161
2162         # It is possible that the offset lines don't intersect the face intersection if
2163         # either face is non-planar.
2164         if not ptcur or not ptnext:
2165             return False
2166
2167         # Common vertex
2168         vertex = None
2169         for v1 in edgecur.verts:
2170             for v2 in edgenext.verts:
2171                 if v1 == v2:
2172                     vertex = v1
2173                     break
2174         vpos = vertex.co
2175
2176         # Computing the factor for next edge
2177         dcur = (ptcur - vpos).length
2178         dnext = (ptnext - vpos).length
2179         if self.strict_offset:
2180             ednext.lfactors[ifacenext] = factorcur * dcur / dnext
2181
2182         return True
2183
2184     # ??? This is a complete no-op
2185     def catena_sort(self, catena):
2186         for ll in catena.chain:
2187             ed = ll[0]
2188             iface = ll[1]
2189
2190     # Create geometry for mesh borders
2191     def create_geometry_vborders(self, vborders):
2192         for vb in vborders:
2193             lpt = vb[0]
2194             style = vb[1]
2195             # print("new edge:", V3(lpt[0]), V3(lpt[1]), "style:", style)
2196             # style could be 'S' or 'P'
2197             # 'S' means: apply prop_borders (?) to edges
2198             # 'P' means: not soft or smooth
2199
2200     # Create geometry for mesh
2201     def create_geometry_vmesh(self, vmesh):
2202         for vm in vmesh:
2203             faceref = vm[1]
2204             normalref = vm[2]
2205             # use faceref as example for material, etc.
2206             allfaces = []
2207             for lpt in vm[0]:
2208                 # print("new face:", LV3(lpt), "norm:", V3(normalref), "ref:", faceref)
2209                 bmverts = self.get_bmverts(lpt)
2210                 newf = self.bm.faces.new(bmverts)
2211                 allfaces.append(newf)
2212             for lface in allfaces:
2213                 if normalref and allfaces[0] and allfaces[0].normal.dot(normalref) < 0:
2214                     bmesh.utils.face_flip(lface)
2215
2216     def get_bmverts(self, ptlist):
2217         return [ self.points.get_bmvert(p) for p in ptlist ]
2218
2219     # Signal errors in preparing the geometry
2220     def signal_error_vd(self, vd):
2221         if vd:
2222             self.hsh_error_vertex[vd.vertex.index] = vd.vertex
2223
2224     # Profile methods
2225
2226     # Compute the transformed profile by indicating the start and end point,
2227     # and the start vector and end face normal.
2228     # The profile will go from pt2 to pt1, and the origin for the profile
2229     # will be at the intersection of the line through pt1 in direction vec1
2230     # and the plane containing pt2 with normal normal2.
2231     def profile_compute_by_vectors(self, profile_type, pt1, vec1, pt2, normal2):
2232         origin = intersect_line_plane([pt1, vec1], [pt2, normal2])
2233         if not origin:
2234             # Can happen if one of the faces is non-planar
2235             # Just make an origin to avoid a crash
2236             origin = pt1.lerp(pt2, 0.5) + (pt2 - pt1).length * Vector([0.1, 0.1, 0.2])
2237         offset1 = (pt1 - origin).length
2238         offset2 = (pt2 - origin).length
2239         vec2 = pt2 - origin
2240         return self.profile_compute_by_offset(profile_type, origin, vec1, offset1, vec2, offset2)
2241
2242     def profile_compute_by_vectors2(self, profile_type, pt1, vec1, pt2, vec2):
2243         lpt = closest_points([pt1, vec1], [pt2, vec2])
2244         origin = lpt[0].lerp(lpt[1], 0.5)
2245         vec1 = pt1 - origin
2246         vec2 = pt2 - origin
2247         offset1 = vec1.length
2248         offset2 = vec2.length
2249         return self.profile_compute_by_offset(profile_type, origin, vec1, offset1, vec2, offset2)
2250
2251     # Compute the transformed profile by indicating the offsets and direction on faces.
2252     # The origin is mapped to the 0,0 of the profile (e.g., the center of the circle
2253     # for a quarter-circle profile).
2254     # The start of the profile will be mapped to offset2 in the direction of vec2 from origin.
2255     # The end of the profile will be mapped to offset1 in the direction of vec1 from the origin.
2256     # (Think of vec1 -> the x-axis, vec2 -> y-axis, and profile goes from (0, 1) to (1, 0) in 2d).
2257     def profile_compute_by_offset(self, profile_type, origin, vec1, offset1, vec2, offset2):
2258         # Getting the nominal profile
2259         pts = self.nominal_profile(profile_type)
2260
2261         # Transformation from golden normalized form:
2262         # Takes nominal profile endpoints (0,1,0) and (1,0,0)
2263         # to (0, offset1, 0) and (offset1, 0, 0) respectively
2264         tsg = mathutils.Matrix([[0.0, -offset1, 0.0, offset1],
2265                                [-offset1, 0.0, 0.0, offset1],
2266                                [0.0, 0.0, 1.0, 0.0],
2267                                [0.0, 0.0, 0.0, 1.0]])
2268
2269         # Scaling and shearing to adjust differences of offset and angle
2270         angle = 0.5 * math.pi - vec1.angle(vec2, 0.0)
2271         tgt = math.tan(angle)
2272         fac = offset2 / offset1 * math.cos(angle)
2273
2274         # Stretch y by fac
2275         ts = mathutils.Matrix([[1.0, 0.0, 0.0, 0.0],
2276                                [0.0, fac, 0.0, 0.0],
2277                                [0.0, 0.0, 1.0, 0.0],
2278                                [0.0, 0.0, 1.0, 1.0]])
2279
2280         # Shear in x, by factor of tgt as move up in y
2281         tsh = mathutils.Matrix([[1.0, tgt, 0.0, 0.0],
2282                                 [0.0, 1.0, 0.0, 0.0],
2283                                 [0.0, 0.0, 1.0, 0.0],
2284                                 [0.0, 0.0, 0.0, 1.0]])
2285
2286         # Transforming to match given coordinates at origin, vec1, vec2
2287         normal = vec1.cross(vec2)
2288         normal.normalize()
2289         ux = vec1
2290         ux.normalize()
2291         uy = normal.cross(ux)
2292         uz = normal
2293         taxe = mathutils.Matrix()
2294         taxe = mathutils.Matrix([[ux[0], uy[0], uz[0], origin[0]],
2295                                  [ux[1], uy[1], uz[1], origin[1]],
2296                                  [ux[2], uy[2], uz[2], origin[2]],
2297                                  [0.0, 0.0, 0.0, 1.0]])
2298         t = taxe * tsh * ts * tsg
2299
2300         # Performing the transformation
2301         return [t * pt for pt in pts]
2302
2303     # Get the nominal profile and compute Nb of segment
2304     def verify_profile(self, profile_type, numseg = None):
2305         ty = profile_type
2306         self.num_seg_lock = ty == 'P'
2307         if numseg and not self.num_seg_lock:
2308             self.profile_type[1] = numseg
2309         pts = self.nominal_profile(self.profile_type)
2310         self.num_seg = len(pts) - 1
2311
2312     # Get the nominal profile and compute Nb of segment
2313     def nominal_profile(self, profile_type):
2314         # Computing the normalized profile in X, Y
2315         ty = profile_type[0]
2316         param = profile_type[1]
2317         key = ty + "-" + str(param)
2318
2319         # Standard profiles
2320         if key in self.hsh_profile_pts:
2321             pts = self.hsh_profile_pts[key]
2322         else:
2323             if ty == 'BZ':
2324                 pts = self.golden_bezier(param)
2325             elif key == 'CR':
2326                 pts = self.golden_circular_reverse(param)
2327             elif key == 'P':
2328                 pts = self.golden_perso(param)
2329             else:
2330                 pts = self.golden_circular(param)
2331             self.hsh_profile_pts[key] = pts
2332         return pts
2333
2334     # Makes a quarter circle profile from
2335     # (0, 1, 0) to (1, 0, 0) with nb_seg line segments
2336     def golden_circular(self, nb_seg):
2337         pts = []
2338         anglesec = 0.5 * math.pi / nb_seg
2339         for i in range(0, nb_seg + 1):
2340             angle = anglesec * i
2341             x = math.cos(angle)
2342             y = math.sin(angle)
2343             pts.append(Vector([x, y, 0.0]))
2344         pts.reverse()
2345         return pts
2346
2347     # Makes a a concave quarter circle profile from
2348     # (0, 1, 0) to (1, 0, 0)
2349     def golden_circular_reverse(self, nb_seg):
2350         pts = []
2351         anglesec = 0.5 * math.pi / nb_seg
2352         for i in range(0, nb_seg + 1):
2353             angle = anglesec * i
2354             x = 1.0 - math.sin(angle)
2355             y = 1.0 - math.cos(angle)
2356             pts.append(Vector([x, y, 0.0]))
2357         pts.reverse()
2358         return pts
2359
2360     def golden_bezier(self, nb_seg):
2361         pt1 = Vector([0.0, 1.0, 0.0])
2362         pt2 = Vector([1.0, 1.0, 0.0])
2363         pt3 = Vector([1.0, 0.0, 0.0])
2364         ctrl_pts = [pt1, pt2, pt3]
2365         # TODO: BezierCurve.compute(ctrl_pts, nb_seg)
2366         return []
2367
2368     def golden_perso(self, fac):
2369         pt1 = Vector([0.0, 1.0, 0.0])
2370         pt2 = Vector([1.0, 1.0, 0.0])
2371         pt3 = Vector([1.0, 0.0, 0.0])
2372         pt4 = Vector([fac, fac, 0.0])
2373         ctrl_pts = [pt1, pt2, pt3]
2374         # TODO: BezierCurve.compute(ctrl_pts, 8)
2375         ctrl_pts = [crv[3], pt4, crv[5]]
2376         crv2 = BezierCurve.compute(ctrl_pts, 6)
2377         crv = crv1[1:3] + crv2 + crv1[6:]
2378         return crv
2379
2380     def print(self):  # XXX - better call something else
2381         print("BevelRoundAlgo:")
2382         print("offset", self.offset)
2383         print("num_seg", self.num_seg)
2384         print("hsh_ed:")
2385         for i, ed in self.hsh_ed.items():
2386             print("E%d ->" % i)
2387             ed.print()
2388         print("hsh_corners:")
2389         for i, v in self.hsh_corners.items():
2390             print("V%d ->"  % i)
2391             v.print()
2392         print("hsh_faces:")
2393         for i, fc in self.hsh_faces.items():
2394             print("F%d ->" % i)
2395             fc.print()
2396         print("lst_catenas", " ".join([str(cat) for cat in self.lst_catenas]))
2397         print("lpt_borders:")
2398         print("  ", " ".join([V3(p) for p in self.lpt_borders]))
2399         print("hsh_profile_pts:")
2400         for s, pts in self.hsh_profile_pts.items():
2401             print(s, "->", LV3(pts))
2402         print("lst_mark_points", self.lst_mark_points)
2403         print("lst_triangulated", self.lst_triangulated)
2404         print("hsh_error_vertex", self.hsh_error_vertex)
2405         print("hash_edges", self.hash_edges)
2406         print("hash_edges_extra", self.hash_edges_extra)
2407         print("hsh_vertex_info", self.hsh_vertex_info)
2408         print("profile_type", self.profile_type)
2409         print("mode_profile", self.mode_profile)
2410         print("mode_sharp", self.mode_sharp)
2411         print("strict_offset", self.strict_offset)
2412         print("mode_rounding", self.mode_rounding)
2413
2414
2415 # Wraps a bmesh edge involved in beveling
2416 class BEdge(object):
2417     def __init__(self, edge):
2418         self.edge = edge
2419         self.index = edge.index
2420         if len(edge.link_faces) != 2:
2421             print("whoops, edge doesn't have exactly two faces")
2422             return
2423         face1 = edge.link_faces[0]
2424         face2 = edge.link_faces[1]
2425         self.lfaces = [face1, face2]
2426         # lvecins are in face1, face2 planes, perp to edge, pointing in
2427         self.lvecins = [normal_in_to_edge(edge, face1), normal_in_to_edge(edge, face2)]
2428         # angle is deviation of two planes meeting angle from 90 degrees
2429         # (positive angle: they meet at less than 90)
2430         self.angle = 0.5 * math.pi - self.lvecins[0].angle(self.lvecins[1], 0.0)
2431         self.cos = math.cos(self.angle)
2432         # cosinv is the amount one should move along a face to have the
2433         # same effect as moving 1.0 along the 90 degree-meeting face
2434         self.cosinv = 1 / self.cos if abs(self.cos) >= 1e-2 else 100.0
2435         self.lfactors = [self.cosinv, self.cosinv]
2436         self.corners = []
2437         # catenas is indexed by corner index (0 for first vert, 1 for second)
2438         self.catenas = [None, None]
2439         # pairs is indexed by 2 * (corner index) + face index
2440         # each gives a pair matching the this to a corresponding
2441         # (edge, corner index, face index) that this edge can continue to
2442         self.pairs = [None, None, None, None]
2443         self.cross_sections = [[], []]
2444         self.sharp_sections = [[], []]
2445         self.golden = 100
2446         self.aligned = False
2447         vxbeg = edge.verts[0]
2448         vxend = edge.verts[1]
2449         # vec is normalized edge direction and length is edge length
2450         self.vec = vxend.co - vxbeg.co
2451         self.length = self.vec.length
2452         self.vec.normalize()
2453         self.round_profile = False
2454         # ptmid is the midpoint of the edge
2455         self.ptmid = vxend.co.lerp(vxbeg.co, 0.5)
2456         self.parallels = [[self.ptmid + vecin, self.vec] for vecin in self.lvecins]
2457         self.loffset = [None, None]
2458         self.profile = None
2459         self.facemain = None
2460         self.nsection = None
2461         self.vmesh = None
2462         self.vborders = None
2463
2464     def __str__(self):
2465         return "ed%d" % self.index
2466
2467     def print(self):
2468         print("BEdge", self.index)
2469         print("  edge", V3(self.edge.verts[0].co), V3(self.edge.verts[1].co))
2470         print("  lfaces", F(self.lfaces[0]), F(self.lfaces[1]))
2471         print("  lvecins", V3(self.lvecins[0]), V3(self.lvecins[1]))
2472         print("  angle %.3f" % self.angle)
2473         print("  lfactors", ["%.3f" % fac for fac in self.lfactors])
2474         print("  corners", [str(v) for v in self.corners])
2475         print("  catenas", [str(cat) for cat in self.catenas])
2476         print("  vec", V3(self.vec))
2477         print("  ptmid", V3(self.ptmid))
2478         print("  pairs: (icorner, iface) in (0,0), (0,1), (1,0), (1,1)")
2479         for pair in self.pairs:
2480             pair.print()
2481         print("  parallels", [[V3(p), V3(n)] for (p,n) in self.parallels])
2482         if self.cross_sections:
2483             print("  cross_sections:")
2484             for cs in self.cross_sections:
2485                 print("   ", LV3(cs))
2486         if self.sharp_sections:
2487             print("  sharp_sections:")
2488             for cs in self.sharp_sections:
2489                 print("   ", cs)
2490         print("  round_profile", self.round_profile)
2491         print("  loffset", self.loffset)
2492         print("  profile", self.profile)
2493         print("  facemain", F(self.facemain))
2494         print("  nsection", LV3(self.nsection))
2495         if self.vmesh:
2496             print("  vmesh:")
2497             for vm in self.vmesh:
2498                 print("    face: faceref=%s, norm=%s" % (F(vm[1]), V3(vm[2])))
2499                 for lpt in vm[0]:
2500                     print("     ", ",".join([V3(p) for p in lpt]))
2501         if self.vborders:
2502             print("  vborders:")
2503             for vb in self.vborders:
2504                 if len(vb[0]) == 2:
2505                     (p1, p2) = vb[0]
2506                     print("    edge:", V3(p1), V3(p2), vb[1])
2507
2508
2509 # Wraps a bmesh vertex involved in beveling
2510 class BCorner(object):
2511     def __init__(self, v, ed):
2512         self.vertex = v
2513         self.index = v.index
2514         self.leds = [ed]
2515         self.pairs = []
2516         self.gold_ed = None
2517         self.sharp_inter = []
2518         self.round_pair = None
2519         self.convex = None
2520         self.vmesh = None
2521
2522     def __str__(self):
2523         return "c%d" % self.index
2524
2525     def print(self):
2526         print("BCorner", self.index)
2527         print("  vertex", V3(self.vertex.co))
2528         print("  leds", [str(ed) for ed in self.leds])
2529         print("  pairs", [str(pair) for pair in self.pairs])
2530         print("  gold_ed", self.gold_ed)
2531         if self.sharp_inter:
2532             print("  sharp_inter:")
2533             for si in self.sharp_inter:
2534                 print(V3(si[0]), si[1], si[2], si[3], si[4])
2535         print("  round_pair", self.round_pair)
2536         print("  convex", self.convex)
2537         if self.vmesh:
2538             print("  vmesh:")
2539             for vm in self.vmesh:
2540                 print("    face: faceref=%s, norm=%s" % (F(vm[1]), V3(vm[2])))
2541                 for lpt in vm[0]:
2542                     print("     ", ",".join([V3(p) for p in lpt]))
2543
2544 # Wraps a bmesh face involved in beveling
2545 class BFace(object):
2546     def __init__(self, f):
2547         self.face = f
2548         self.index = f.index
2549         self.bmverts = [lp.vert for lp in f.loops]
2550         self.bmedges = [lp.edge for lp in f.loops]
2551         self.edgereversed = [self.bmedges[i].verts[0] == self.bmverts[i] \
2552             for i in range(0, len(self.bmverts))]
2553         # for verts that change to one or more new points,
2554         # self.newpts[i] is list of float triple for replacement
2555         self.newpts = len(self.bmverts) * [None]
2556
2557     def anynew(self):
2558         for p in self.newpts:
2559             if p is not None:
2560                 return True
2561         return False
2562
2563     # Probably should give access to C routine BM_face_point_inside_test
2564     # but for now reimplement it here
2565     def contains_point(self, v):
2566         (ax, ay) = axis_dominant(self.face.normal)
2567         co2 = Vector([v[ax], v[ay]])
2568         cent = Vector([0.0, 0.0])
2569         for l in self.face.loops:
2570             v = l.vert.co
2571             cent = cent + Vector([v[ax], v[ay]])
2572         cent = cent / len(self.face.loops)
2573         crosses = 0
2574         onepluseps = 1.0 + EPSILON * 150.0
2575         out = Vector([1e30, 1e30])
2576         for l in self.face.loops:
2577             vprev = l.link_loop_prev.vert.co
2578             v = l.vert.co
2579             v1 = (Vector([vprev[ax], vprev[ay]]) - cent) * onepluseps + cent
2580             v2 = (Vector([v[ax], v[ay]]) - cent) * onepluseps + cent
2581             if line_segments_cross(v1, v2, co2, out):
2582                 crosses += 1
2583         return crosses % 2 != 0
2584
2585     def __str__(self):
2586         return "f%d" % self.index
2587
2588     def print(self):
2589         print("BFace", self.index)
2590         print("  bmverts", [V(v) for v in self.bmverts])
2591         print("  bmedges", [E(e) for e in self.bmedges])
2592         print("  edgereversed", self.edgereversed)
2593         print("  newpts", [LV3(pl) if pl else 'None' \
2594             for pl in self.newpts])
2595         
2596
2597 # At vertices to be beveled, the incoming edges involved
2598 # in beveling are matched up in pairs (to be connected up).
2599 # There will be two pairs for such a matchup: one for each
2600 # face-side of the edge.
2601 # So (ed1, face1) is a BEdge and one of the bmesh faces
2602 # that is incident on it, and similarly for (ed2, face2).
2603 # Some edges won't get matched and are 'alone' pairs
2604 # with None for all of the second components.
2605 class BPair(object):
2606     def __init__(self, vd, ed1, face1, ed2, face2):
2607         edge1 = ed1.edge
2608         edge2 = ed2.edge if ed2 else None
2609         self.vd = vd
2610         self.ledges = [edge1, edge2]
2611         self.leds = [ed1, ed2]
2612         self.lfaces = [face1, face2]
2613         self.ptcross = None
2614         self.edge_terms = []
2615         self.monoface = True
2616         self.convex = False
2617         self.alone = not edge2
2618         self.rounding = None
2619         self.mode = None
2620
2621     def __str__(self):
2622         if not self.alone:
2623             return "pr2(%s,%s)(%s,%s)" % \
2624                 (self.leds[0], F(self.lfaces[0]), self.leds[1], F(self.lfaces[1]))
2625         else:
2626             return "pr1(%s,%s)" % (self.leds[0], F(self.lfaces[0]))
2627
2628     def print(self):
2629         print("BPair", str(self))
2630         print("  ptcross", V3(self.ptcross))
2631         print("  edge_terms", [E(e) for e in self.edge_terms])
2632         print("  monoface", self.monoface, "convex", self.convex,
2633             "rounding", self.rounding, "mode", self.mode)
2634
2635 # A catena is a chain - a list of [ed, face-index] pairs that
2636 # traverse along matched-up pairs as computed at each vertex.
2637 class BCatena(object):
2638     def __init__(self):
2639         self.chain = []
2640         self.leds = []
2641         self.nbsmall = 0
2642
2643     def __str__(self):
2644         return "catena(" + \
2645             " ".join(["(%s,%d)" % (p[0], p[1]) for p in self.chain]) + \
2646             ", %d)" % self.nbsmall
2647
2648
2649 # distances less than about DISTTOL will be considered
2650 # essentially zero
2651 DISTTOL = 1e-4
2652 INVDISTTOL = 1e4
2653
2654 class Points(object):
2655     """Container of points without duplication, each mapped to a BMVert
2656
2657     Points are triples of floats.
2658
2659     Implementation:
2660     In order to efficiently find duplicates, we quantize the points
2661     to triples of ints and map from quantized triples to vertex
2662     index.
2663     """
2664
2665     def __init__(self, bm):
2666         self.pos = []
2667         self.bm = bm
2668         self.invmap = dict()
2669
2670     def get_bmvert(self, p):
2671         """Return the BMVert for the given point, making one if necessary.
2672
2673         Args:
2674           p: 3-tuple of float - coordinates
2675         Returns:
2676           BMVert - the vertex of added (or existing) point
2677         """
2678
2679         qp = tuple([int(round(v * INVDISTTOL)) for v in p])
2680         if qp in self.invmap:
2681             return self.invmap[qp]
2682         else:
2683             newv = self.bm.verts.new(p)
2684             self.invmap[qp] = newv
2685             self.pos.append(p)
2686             return newv
2687
2688
2689 # Returns vector perpendicular to edge in face plane
2690 # pointing to the interior of the fac
2691 def normal_in_to_edge(edge, face):
2692     pt1 = edge.verts[0].co
2693     pt2 = edge.verts[1].co
2694     vec = face.normal.cross(pt2 - pt1)
2695     vec.normalize()
2696     if edge_reversed_in_face(edge, face):
2697         vec.negate()
2698     return vec
2699
2700
2701 # Returns True if if two edges form a convex corner in face
2702 # at vertex
2703 def convex_at_vertex(vertex, face, edge1, edge2, face2=None):
2704     vother1 = edge1.other_vert(vertex)
2705     vec1 = vother1.co - vertex.co
2706     vecin1 = normal_in_to_edge(edge1, face)
2707     vecin2 = normal_in_to_edge(edge2, face2 if face2 else face)
2708     # I don't understand this computation: seems to take dot
2709     # product of two vectors that are the face normal (?)
2710     return vec1.cross(vecin1).dot(vecin1.cross(vecin2)) >= 0
2711
2712
2713 # For the functions on 'planes' and 'lines':
2714 # A plane defined by [point-on-plane, plane-normal]
2715 # A line is defined by [point-on-line, line-direction-vector]
2716
2717
2718 # Return Vector that is point where line intersects plane,
2719 def intersect_line_plane(line, plane):
2720     (lv, vec) = line
2721     (pp, pnorm) = plane
2722     return mathutils.geometry.intersect_line_plane(lv, lv + vec, pp, pnorm)
2723
2724
2725 # Return intersection point of the two lines, or None.
2726 def intersect_line_line(linea, lineb):
2727     (av, avec) = linea
2728     (bv, bvec) = lineb
2729     (cv1, cv2) = mathutils.geometry.intersect_line_line(av, av + avec, bv, bv + bvec)
2730     if vec_approx_eq(cv1, cv2):
2731         return cv1
2732     else:
2733         return None
2734
2735
2736 # Return intersection line of two planes
2737 def intersect_plane_plane(plane1, plane2):
2738     (pp1, pnorm1) = plane1
2739     (pp2, pnorm2) = plane2
2740     (a, b) = mathutils.geometry.intersect_plane_plane(pp1, pnorm1, pp2, pnorm2)
2741     # seems like it returns (pt-on-line, line-dir)
2742     return (a, b)
2743
2744 # Return closes points of two lines as tuple of two.
2745 def closest_points(linea, lineb):
2746     (av, avec) = linea
2747     (bv, bvec) = lineb
2748     return mathutils.geometry.intersect_line_line(av, av + avec, bv, bv + bvec)
2749
2750
2751 # Intersection where point must be between endpoints of edge
2752 def intersect_edge_line(edge, line):
2753     pt = intersect_line_line([edge.verts[0].co, edge.verts[1].co - edge.verts[0].co], line)
2754     if not pt:
2755         return None
2756     ptbeg = edge.verts[0].co
2757     if vec_approx_eq(pt, ptbeg):
2758         return pt
2759     ptend = edge.verts[1].co
2760     if vec_approx_eq(pt, ptend):
2761         return pt
2762     if (ptbeg-pt).dot(ptend-pt) < 0:
2763         return pt
2764     else:
2765         return None
2766
2767
2768 # Project a point onto a plane
2769 def project_to_plane(point, plane):
2770     (pco, pnorm) = plane
2771     ptb = point + pnorm
2772     return mathutils.geometry.intersect_line_plane(point, ptb, pco, pnorm)
2773
2774
2775 # Project a point onto a line
2776 def project_to_line(point, line):
2777     (lv, lvec) = line
2778     (ptproj, _) = mathutils.geometry.intersect_point_line(point, lv, lv + lvec)
2779     return ptproj
2780
2781
2782 # Return the plane the best fits the points.
2783 # The right way to do this involves finding a singular value decomposition.
2784 # (search for "Orthogonal Distance Regression Planes").
2785 # For now, just use the centroid as point on the plane and
2786 # the average normal.
2787 def fit_plane_to_points(pts):
2788     n = len(pts)
2789     if n < 3:
2790         return None
2791     center = pts[0]
2792     for i in range(1, n):
2793         center = center + pts[i]
2794     center = center / n
2795     # Newell method for normal, pretending this is a polygon
2796     sumx = 0.0
2797     sumy = 0.0
2798     sumz = 0.0
2799     for i in range(0, n):
2800         a = pts[i]
2801         b = pts[(i + 1) % n]
2802         sumx += (a[1] - b[1]) * (a[2] + b[2])
2803         sumy += (a[2] - b[2]) * (a[0] + b[0])
2804         sumz += (a[0] - b[0]) * (a[1] + b[1])
2805     norm = mathutils.Vector([sumx, sumy, sumz])
2806     norm.normalize()
2807     return [center, norm]
2808
2809
2810 # Return True if point is on the plane
2811 def on_plane(point, plane):
2812     (pp, pnorm) = plane
2813     d = mathutils.geometry.distance_point_to_plane(point, pp, pnorm)
2814     return abs(d) < EPSILON
2815
2816
2817 # Return True if point is on the line
2818 def on_line(point, line):
2819     (lv, lvec) = line
2820     (vint, _) = mathutils.geometry.intersect_point_line(point, lv, lv + lvec)
2821     return (point-vint).length < EPSILON
2822
2823
2824 def parallel(v1, v2):
2825     return abs(v1.cross(v2).length) < EPSILON
2826
2827
2828 # A plane is a [point-on-plane, normal-vec] tuple
2829 def face_plane(face):
2830     return [face.verts[0].co, face.normal]
2831
2832
2833 # Return True if Vectors are approximately equal
2834 def vec_approx_eq(a, b):
2835     return (a-b).length < EPSILON
2836
2837
2838 # Return True if edge points in CW direction around face
2839 # when viewed from the side the normal is pointing to
2840 def edge_reversed_in_face(edge, face):
2841     for lp in face.loops:
2842         if lp.edge == edge:
2843             return lp.vert != edge.verts[0]
2844     print("whoops, edge_reversed_in_face: edge not in face")
2845     return False
2846
2847
2848 # Find the indices of axes which make for closest
2849 # alignment with vector axis, for a fast projection
2850 # of 3d -> 2d
2851 def axis_dominant(axis):
2852     xn = abs(axis[0])
2853     yn = abs(axis[1])
2854     zn = abs(axis[2])
2855     if zn >= xn and zn >= yn:
2856         return (0, 1)
2857     elif yn >= xn and yn >= zn:
2858         return (0, 2)
2859     else:
2860         return (1, 2)
2861
2862
2863 # Return True if v3 is to the right of line v1v2
2864 # but False if v3 is the same as v1 or v2
2865 # (all points are 2d Vectors)
2866 def test_edge_side(v1, v2, v3):
2867     inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0])
2868     if inp < 0.0:
2869         return False
2870     elif inp < 0.0:
2871         if v1 == v3 or v2 == v3:
2872             return False
2873     return True
2874
2875
2876 # Return True if two line segments cross each other
2877 # with careful attention to edge cases
2878 def line_segments_cross(v1, v2, v3, v4):
2879     eps = EPSILON * 15
2880     w1 = test_edge_side(v1, v3, v2)
2881     w2 = test_edge_side(v2, v4, v1)
2882     w3 = not test_edge_side(v1, v2, v3)
2883     w4 = test_edge_side(v3, v2, v4)
2884     w5 = not test_edge_side(v3, v1, v4)
2885     if w1 == w2 == w3 == w4 == w5:
2886         return True
2887     mv1= (min(v1[0], v2[0]), min(v1[1], v2[1]))
2888     mv2 = (max(v1[0], v2[0]), max(v1[1], v2[1]))
2889     mv3= (min(v3[0], v4[0]), min(v3[1], v4[1]))
2890     mv4 = (max(v3[0], v4[0]), max(v3[1], v4[1]))
2891     if abs(v1[1] - v2[1]) < eps and abs(v3[1] - v4[1]) < eps and abs(v1[1] - v3[1]) < eps:
2892         return (mv4[0] >= mv1[0] and mv3[0] <= mv2[0])
2893     if abs(v1[0] - v2[0]) < eps and abs(v3[0] - v4[0]) < eps and abs(v1[0] - v3[0]) < eps:
2894         return (mv4[1] >= mv1[1] and mv3[1] <= mv2[1])
2895     return False
2896
2897
2898 # Three-way compare
2899 def cmp(a, b):
2900     return (a > b) - (a < b)
2901
2902
2903 # A find-in-iterable function
2904 def find(iterable, func):
2905     for x in iterable:
2906         if func(x):
2907             return x
2908     return None
2909
2910 # Grow a sequence, if necessary, with Nones, to make i a valid index
2911 def make_index_valid(s, i):
2912     if i >= len(s):
2913         s.extend((i - len(s) + 1) * [None])
2914
2915 # for debug prints
2916 def V3(v):
2917     return "None" if not v else "(%.2f,%.2f,%.2f)" % (v[0], v[1], v[2])
2918
2919 def V2(v):
2920     return "None" if not v else "(%.2f,%.2f)" % (v[0], v[1])
2921
2922 def LV3(lv):
2923     return "None" if not lv else ",".join([V3(v) for v in lv])
2924
2925 def F(f):
2926     return "None" if not f else "F%d" % f.index
2927
2928 def E(e):
2929     return "None" if not e else "E%d" % e.index
2930
2931 def V(v):
2932     return "None" if not v else "V%d" % v.index
2933
2934 def printmat(mat, str):
2935     print(str)
2936     for i in range(0,4):
2937         print("  |" + " ".join(["%5.2f" % mat[i][j] for j in range(0,4)]) + "|")
2938
2939
2940 def panel_func(self, context):
2941     self.layout.label(text="Bevel Round:")
2942     self.layout.operator("mesh.bevel_round", text="Bevel Round")
2943
2944
2945 def register():
2946     bpy.utils.register_class(BevelRound)
2947     bpy.types.VIEW3D_PT_tools_meshedit.append(panel_func)
2948
2949
2950 def unregister():
2951     bpy.utils.unregister_class(BevelRound)
2952     bpy.types.VIEW3D_PT_tools_meshedit.remove(panel_func)
2953
2954
2955 if __name__ == "__main__":
2956     register()