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