mesh_inset/geom.py

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