Category: copy/paste UVs
[blender-addons-contrib.git] / io_vector / geom.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 """Geometry classes and operations.
22 Also, vector file representation (Art).
23 """
24
25 __author__ = "howard.trickey@gmail.com"
26
27 import math
28
29 # distances less than about DISTTOL will be considered
30 # essentially zero
31 DISTTOL = 1e-3
32 INVDISTTOL = 1e3
33
34
35 class Points(object):
36     """Container of points without duplication, each mapped to an int.
37
38     Points are either have dimension at least 2, maybe more.
39
40     Implementation:
41     In order to efficiently find duplicates, we quantize the points
42     to triples of ints and map from quantized triples to vertex
43     index.
44
45     Attributes:
46       pos: list of tuple of float - coordinates indexed by
47           vertex number
48       invmap: dict of (int, int, int) to int - quantized coordinates
49           to vertex number map
50     """
51
52     def __init__(self, initlist=[]):
53         self.pos = []
54         self.invmap = dict()
55         for p in initlist:
56             self.AddPoint(p)
57
58     @staticmethod
59     def Quantize(p):
60         """Quantize the float tuple into an int tuple.
61
62         Args:
63           p: tuple of float
64         Returns:
65           tuple of int - scaled by INVDISTTOL and rounded p
66         """
67
68         return tuple([int(round(v * INVDISTTOL)) for v in p])
69
70     def AddPoint(self, p):
71         """Add point p to the Points set and return vertex number.
72
73         If there is an existing point which quantizes the same,,
74         don't add a new one but instead return existing index.
75
76         Args:
77           p: tuple of float - coordinates (2-tuple or 3-tuple)
78         Returns:
79           int - the vertex number of added (or existing) point
80         """
81
82         qp = Points.Quantize(p)
83         if qp in self.invmap:
84             return self.invmap[qp]
85         else:
86             self.invmap[qp] = len(self.pos)
87             self.pos.append(p)
88             return len(self.pos) - 1
89
90     def AddPoints(self, points):
91         """Add another set of points to this set.
92
93         We need to return a mapping from indices
94         in the argument points space into indices
95         in this point space.
96
97         Args:
98           points: Points - to union into this set
99         Returns:
100           list of int: maps added indices to new ones
101         """
102
103         vmap = [0] * len(points.pos)
104         for i in range(len(points.pos)):
105             vmap[i] = self.AddPoint(points.pos[i])
106         return vmap
107
108     def AddZCoord(self, z):
109         """Change this in place to have a z coordinate, with value z.
110
111         Assumes the coordinates are currently 2d.
112
113         Args:
114           z: the value of the z coordinate to add
115         Side Effect:
116           self now has a z-coordinate added
117         """
118
119         assert(len(self.pos) == 0 or len(self.pos[0]) == 2)
120         newinvmap = dict()
121         for i, (x, y) in enumerate(self.pos):
122             newp = (x, y, z)
123             self.pos[i] = newp
124             newinvmap[self.Quantize(newp)] = i
125         self.invmap = newinvmap
126
127     def AddToZCoord(self, i, delta):
128         """Change the z-coordinate of point with index i to add delta.
129
130         Assumes the coordinates are currently 3d.
131
132         Args:
133           i: int - index of a point
134           delta: float - value to add to z-coord
135         """
136
137         (x, y, z) = self.pos[i]
138         self.pos[i] = (x, y, z + delta)
139
140
141 class PolyArea(object):
142     """Contains a Polygonal Area (polygon with possible holes).
143
144     A polygon is a list of vertex ids, each an index given by
145     a Points object. The list represents a CCW-oriented
146     outer boundary (implicitly closed).
147     If there are holes, they are lists of CW-oriented vertices
148     that should be contained in the outer boundary.
149     (So the left face of both the poly and the holes is
150     the filled part.)
151
152     Attributes:
153       points: Points
154       poly: list of vertex ids
155       holes: list of lists of vertex ids (each a hole in poly)
156       data: any - application data (can hold color, e.g.)
157     """
158
159     def __init__(self, points=None, poly=None, holes=None, data=None):
160         self.points = points if points else Points()
161         self.poly = poly if poly else []
162         self.holes = holes if holes else []
163         self.data = data
164
165     def AddHole(self, holepa):
166         """Add a PolyArea's poly as a hole of self.
167
168         Need to reverse the contour and
169         adjust the the point indexes and self.points.
170
171         Args:
172           holepa: PolyArea
173         """
174
175         vmap = self.points.AddPoints(holepa.points)
176         holepoly = [vmap[i] for i in holepa.poly]
177         holepoly.reverse()
178         self.holes.append(holepoly)
179
180     def ContainsPoly(self, poly, points):
181         """Tests if poly is contained within self.poly.
182
183         Args:
184           poly: list of int - indices into points
185           points: Points - maps to coords
186         Returns:
187           bool - True if poly is fully contained within self.poly
188         """
189
190         for v in poly:
191             if PointInside(points.pos[v], self.poly, self.points) == -1:
192                 return False
193         return True
194
195     def Normal(self):
196         """Returns the normal of the polyarea's main poly."""
197
198         pos = self.points.pos
199         poly = self.poly
200         if len(pos) == 0 or len(pos[0]) == 2 or len(poly) == 0:
201             print("whoops, not enough info to calculate normal")
202             return (0.0, 0.0, 1.0)
203         return Newell(poly, self.points)
204
205
206 class PolyAreas(object):
207     """Contains a list of PolyAreas and a shared Points.
208
209     Attributes:
210       polyareas: list of PolyArea
211       points: Points
212     """
213
214     def __init__(self):
215         self.polyareas = []
216         self.points = Points()
217
218     def scale_and_center(self, scaled_side_target):
219         """Adjust the coordinates of the polyareas so that
220         it is centered at the origin and has its longest
221         dimension scaled to be scaled_side_target."""
222
223         if len(self.points.pos) == 0:
224             return
225         (minv, maxv) = self.bounds()
226         maxside = max([maxv[i] - minv[i] for i in range(2)])
227         if maxside > 0.0:
228             scale = scaled_side_target / maxside
229         else:
230             scale = 1.0
231         translate = [-0.5 * (maxv[i] + minv[i]) for i in range(2)]
232         dim = len(self.points.pos[0])
233         if dim == 3:
234             translate.append([0.0])
235         for v in range(len(self.points.pos)):
236             self.points.pos[v] = tuple([scale * (self.points.pos[v][i] + \
237                 translate[i]) for i in range(dim)])
238
239     def bounds(self):
240         """Find bounding box of polyareas in xy.
241
242         Returns:
243           ([minx,miny],[maxx,maxy]) - all floats
244         """
245
246         huge = 1e100
247         minv = [huge, huge]
248         maxv = [-huge, -huge]
249         for pa in self.polyareas:
250             for face in [pa.poly] + pa.holes:
251                 for v in face:
252                     vcoords = self.points.pos[v]
253                     for i in range(2):
254                         if vcoords[i] < minv[i]:
255                             minv[i] = vcoords[i]
256                         if vcoords[i] > maxv[i]:
257                             maxv[i] = vcoords[i]
258         if minv[0] == huge:
259             minv = [0.0, 0.0]
260         if maxv[0] == huge:
261             maxv = [0.0, 0.0]
262         return (minv, maxv)
263
264
265 class Model(object):
266     """Contains a generic 3d model.
267
268     A generic 3d model has vertices with 3d coordinates.
269     Each vertex gets a 'vertex id', which is an index that
270     can be used to refer to the vertex and can be used
271     to retrieve the 3d coordinates of the point.
272
273     The actual visible part of the geometry are the faces,
274     which are n-gons (n>2), specified by a vector of the
275     n corner vertices.
276     Faces may also have data associated with them,
277     and the data will be copied into newly created faces
278     from the most likely neighbor faces..
279
280     Attributes:
281       points: geom.Points - the 3d vertices
282       faces: list of list of indices (each a CCW traversal of a face)
283       face_data: list of any - if present, is parallel to
284           faces list and holds arbitrary data
285     """
286
287     def __init__(self):
288         self.points = Points()
289         self.faces = []
290         self.face_data = []
291
292
293 class Art(object):
294     """Contains a vector art diagram.
295
296     Attributes:
297       paths: list of Path objects
298     """
299
300     def __init__(self):
301         self.paths = []
302
303
304 class Paint(object):
305     """A color or pattern to fill or stroke with.
306
307     For now, just do colors, but could later do
308     patterns or images too.
309
310     Attributes:
311       color: (r,g,b) triple of floats, 0.0=no color, 1.0=max color
312     """
313
314     def __init__(self, r=0.0, g=0.0, b=0.0):
315         self.color = (r, g, b)
316
317     @staticmethod
318     def CMYK(c, m, y, k):
319         """Return Paint specified in CMYK model.
320
321         Uses formula from 6.2.4 of PDF Reference.
322
323         Args:
324           c, m, y, k: float - in range [0, 1]
325         Returns:
326           Paint - with components in rgb form now
327         """
328
329         return Paint(1.0 - min(1.0, c + k),
330             1.0 - min(1.0, m + k), 1.0 - min(1.0, y + k))
331
332 black_paint = Paint()
333 white_paint = Paint(1.0, 1.0, 1.0)
334
335 ColorDict = {
336     'aqua': Paint(0.0, 1.0, 1.0),
337     'black': Paint(0.0, 0.0, 0.0),
338     'blue': Paint(0.0, 0.0, 1.0),
339     'fuchsia': Paint(1.0, 0.0, 1.0),
340     'gray': Paint(0.5, 0.5, 0.5),
341     'green': Paint(0.0, 0.5, 0.0),
342     'lime': Paint(0.0, 1.0, 0.0),
343     'maroon': Paint(0.5, 0.0, 0.0),
344     'navy': Paint(0.0, 0.0, 0.5),
345     'olive': Paint(0.5, 0.5, 0.0),
346     'purple': Paint(0.5, 0.0, 0.5),
347     'red': Paint(1.0, 0.0, 0.0),
348     'silver': Paint(0.75, 0.75, 0.75),
349     'teal': Paint(0.0, 0.5, 0.5),
350     'white': Paint(1.0, 1.0, 1.0),
351     'yellow': Paint(1.0, 1.0, 0.0)
352 }
353
354
355 class Path(object):
356     """Represents a path in the PDF sense, with painting instructions.
357
358     Attributes:
359       subpaths: list of Subpath objects
360       filled: True if path is to be filled
361       fillevenodd: True if use even-odd rule to fill (else non-zero winding)
362       stroked: True if path is to be stroked
363       fillpaint: Paint to fill with
364       strokepaint: Paint to stroke with
365     """
366
367     def __init__(self):
368         self.subpaths = []
369         self.filled = False
370         self.fillevenodd = False
371         self.stroked = False
372         self.fillpaint = black_paint
373         self.strokepaint = black_paint
374
375     def AddSubpath(self, subpath):
376         """"Add a subpath."""
377
378         self.subpaths.append(subpath)
379
380     def Empty(self):
381         """Returns True if this Path as no subpaths."""
382
383         return not self.subpaths
384
385
386 class Subpath(object):
387     """Represents a subpath in PDF sense, either open or closed.
388
389     We'll represent lines, bezier pieces, circular arc pieces
390     as tuples with letters giving segment type in first position
391     and coordinates (2-tuples of floats) in the other positions.
392
393     Segment types:
394      ('L', a, b)       - line from a to b
395      ('B', a, b, c, d) - cubic bezier from a to b, with control points c,d
396      ('Q', a, b, c)    - quadratic bezier from a to b, with 1 control point c
397      ('A', a, b, rad, xrot, large-arc, ccw) - elliptical arc from a to b,
398        with rad=(rx, ry) as radii, xrot is x-axis rotation in degrees,
399        large-arc is True if arc should be >= 180 degrees,
400        ccw is True if start->end follows counter-clockwise direction
401        (see SVG spec); note that after rad,
402        the rest are floats or bools, not coordinate pairs
403     Note that s[1] and s[2] are the start and end points for any segment s.
404
405     Attributes:
406       segments: list of segment tuples (see above)
407       closed: True if closed
408     """
409
410     def __init__(self):
411         self.segments = []
412         self.closed = False
413
414     def Empty(self):
415         """Returns True if this subpath as no segments."""
416
417         return not self.segments
418
419     def AddSegment(self, seg):
420         """Add a segment."""
421
422         self.segments.append(seg)
423
424     @staticmethod
425     def SegStart(s):
426         """Return start point for segment.
427
428         Args:
429           s: a segment tuple
430         Returns:
431           (float, float): the coordinates of the segment's start point
432         """
433
434         return s[1]
435
436     @staticmethod
437     def SegEnd(s):
438         """Return end point for segment.
439
440         Args:
441           s: a segment tuple
442         Returns:
443           (float, float): the coordinates of the segment's end point
444         """
445
446         return s[2]
447
448
449 class TransformMatrix(object):
450     """Transformation matrix for 2d coordinates.
451
452     The transform matrix is:
453       [ a b 0 ]
454       [ c d 0 ]
455       [ e f 1 ]
456     and coordinate tranformation is defined by:
457       [x' y' 1] = [x y 1] x TransformMatrix
458
459     Attributes:
460       a, b, c, d, e, f: floats
461     """
462
463     def __init__(self, a=1.0, b=0.0, c=0.0, d=1.0, e=0.0, f=0.0):
464         self.a = a
465         self.b = b
466         self.c = c
467         self.d = d
468         self.e = e
469         self.f = f
470
471     def __str__(self):
472         return str([self.a, self.b, self.c, self.d, self.e, self.f])
473
474     def Copy(self):
475         """Return a copy of this matrix."""
476
477         return TransformMatrix(self.a, self.b, self.c, self.d, self.e, self.f)
478
479     def ComposeTransform(self, a, b, c, d, e, f):
480         """Apply the transform given the the arguments on top of this one.
481
482         This is accomplished by returning t x sel
483         where t is the transform matrix that would be formed from the args.
484
485         Arguments:
486           a, b, c, d, e, f: float - defines a composing TransformMatrix
487         """
488
489         newa = a * self.a + b * self.c
490         newb = a * self.b + b * self.d
491         newc = c * self.a + d * self.c
492         newd = c * self.b + d * self.d
493         newe = e * self.a + f * self.c + self.e
494         newf = e * self.b + f * self.d + self.f
495         self.a = newa
496         self.b = newb
497         self.c = newc
498         self.d = newd
499         self.e = newe
500         self.f = newf
501
502     def Apply(self, pt):
503         """Return the result of applying this tranform to pt = (x,y).
504
505         Arguments:
506           (x, y) : (float, float)
507         Returns:
508           (x', y'): 2-tuple of floats, the result of [x y 1] x self
509         """
510
511         (x, y) = pt
512         return (self.a * x + self.c * y + self.e, \
513             self.b * x + self.d * y + self.f)
514
515
516 def ApproxEqualPoints(p, q):
517     """Return True if p and q are approximately the same points.
518
519     Args:
520       p: n-tuple of float
521       q: n-tuple of float
522     Returns:
523       bool - True if the 1-norm <= DISTTOL
524     """
525
526     for i in range(len(p)):
527         if abs(p[i] - q[i]) > DISTTOL:
528             return False
529         return True
530
531
532 def PointInside(v, a, points):
533     """Return 1, 0, or -1 as v is inside, on, or outside polygon.
534
535     Cf. Eric Haines ptinpoly in Graphics Gems IV.
536
537     Args:
538       v : (float, float) or (float, float, float) - coordinates of a point
539       a : list of vertex indices defining polygon (assumed CCW)
540       points: Points - to get coordinates for polygon
541     Returns:
542       1, 0, -1: as v is inside, on, or outside polygon a
543     """
544
545     (xv, yv) = (v[0], v[1])
546     vlast = points.pos[a[-1]]
547     (x0, y0) = (vlast[0], vlast[1])
548     if x0 == xv and y0 == yv:
549         return 0
550     yflag0 = y0 > yv
551     inside = False
552     n = len(a)
553     for i in range(0, n):
554         vi = points.pos[a[i]]
555         (x1, y1) = (vi[0], vi[1])
556         if x1 == xv and y1 == yv:
557             return 0
558         yflag1 = y1 > yv
559         if yflag0 != yflag1:
560             xflag0 = x0 > xv
561             xflag1 = x1 > xv
562             if xflag0 == xflag1:
563                 if xflag0:
564                     inside = not inside
565             else:
566                 z = x1 - (y1 - yv) * (x0 - x1) / (y0 - y1)
567                 if z >= xv:
568                     inside = not inside
569         x0 = x1
570         y0 = y1
571         yflag0 = yflag1
572     if inside:
573         return 1
574     else:
575         return -1
576
577
578 def SignedArea(polygon, points):
579     """Return the area of the polgon, positive if CCW, negative if CW.
580
581     Args:
582       polygon: list of vertex indices
583       points: Points
584     Returns:
585       float - area of polygon, positive if it was CCW, else negative
586     """
587
588     a = 0.0
589     n = len(polygon)
590     for i in range(0, n):
591         u = points.pos[polygon[i]]
592         v = points.pos[polygon[(i + 1) % n]]
593         a += u[0] * v[1] - u[1] * v[0]
594     return 0.5 * a
595
596
597 def VecAdd(a, b):
598     """Return vector a-b.
599
600     Args:
601       a: n-tuple of floats
602       b: n-tuple of floats
603     Returns:
604       n-tuple of floats - pairwise addition a+b
605     """
606
607     n = len(a)
608     assert(n == len(b))
609     return tuple([a[i] + b[i] for i in range(n)])
610
611
612 def VecSub(a, b):
613     """Return vector a-b.
614
615     Args:
616       a: n-tuple of floats
617       b: n-tuple of floats
618     Returns:
619       n-tuple of floats - pairwise subtraction a-b
620     """
621
622     n = len(a)
623     assert(n == len(b))
624     return tuple([a[i] - b[i] for i in range(n)])
625
626
627 def VecDot(a, b):
628     """Return the dot product of two vectors.
629
630     Args:
631       a: n-tuple of floats
632       b: n-tuple of floats
633     Returns:
634       n-tuple of floats - dot product of a and b
635     """
636
637     n = len(a)
638     assert(n == len(b))
639     sum = 0.0
640     for i in range(n):
641         sum += a[i] * b[i]
642     return sum
643
644
645 def VecLen(a):
646     """Return the Euclidean length of the argument vector.
647
648     Args:
649       a: n-tuple of floats
650     Returns:
651       float: the 2-norm of a
652     """
653
654     s = 0.0
655     for v in a:
656         s += v * v
657     return math.sqrt(s)
658
659
660 def Newell(poly, points):
661     """Use Newell method to find polygon normal.
662
663     Assume poly has length at least 3 and points are 3d.
664
665     Args:
666       poly: list of int - indices into points.pos
667       points: Points - assumed 3d
668     Returns:
669       (float, float, float) - the average normal
670     """
671
672     sumx = 0.0
673     sumy = 0.0
674     sumz = 0.0
675     n = len(poly)
676     pos = points.pos
677     for i, ai in enumerate(poly):
678         bi = poly[(i + 1) % n]
679         a = pos[ai]
680         b = pos[bi]
681         sumx += (a[1] - b[1]) * (a[2] + b[2])
682         sumy += (a[2] - b[2]) * (a[0] + b[0])
683         sumz += (a[0] - b[0]) * (a[1] + b[1])
684     return Norm3(sumx, sumy, sumz)
685
686
687 def Norm3(x, y, z):
688     """Return vector (x,y,z) normalized by dividing by squared length.
689     Return (0.0, 0.0, 1.0) if the result is undefined."""
690     sqrlen = x * x + y * y + z * z
691     if sqrlen < 1e-100:
692         return (0.0, 0.0, 1.0)
693     else:
694         try:
695             d = math.sqrt(sqrlen)
696             return (x / d, y / d, z / d)
697         except:
698             return (0.0, 0.0, 1.0)
699
700
701 # We're using right-hand coord system, where
702 # forefinger=x, middle=y, thumb=z on right hand.
703 # Then, e.g., (1,0,0) x (0,1,0) = (0,0,1)
704 def Cross3(a, b):
705     """Return the cross product of two vectors, a x b."""
706
707     (ax, ay, az) = a
708     (bx, by, bz) = b
709     return (ay * bz - az * by, az * bx - ax * bz, ax * by - ay * bx)
710
711
712 def MulPoint3(p, m):
713     """Return matrix multiplication of p times m
714     where m is a 4x3 matrix and p is a 3d point, extended with 1."""
715
716     (x, y, z) = p
717     return (x * m[0] + y * m[3] + z * m[6] + m[9],
718         x * m[1] + y * m[4] + z * m[7] + m[10],
719         x * m[2] + y * m[5] + z * m[8] + m[11])