1# Copyright (c) 2018-2021 Manfred Moitzi 2# License: MIT License 3from typing import List, Sequence, Tuple, Iterable, TYPE_CHECKING, Union, Dict 4from ezdxf.lldxf.const import DXFValueError 5from ezdxf.math import (Matrix44, Vec3, NULLVEC, 6 is_planar_face, subdivide_face, normal_vector_3p, subdivide_ngons, 7) 8 9if TYPE_CHECKING: 10 from ezdxf.eztypes import Vertex, UCS, Polyface, Polymesh, GenericLayoutType 11 12 13class MeshBuilder: 14 """ A simple Mesh builder. Stores a list of vertices, a list of edges where 15 an edge is a list of indices into the vertices list, and a faces list where 16 each face is a list of indices into the vertices list. 17 18 The render() method, renders the mesh into a DXF MESH entity. The MESH 19 entity supports ngons in AutoCAD, ngons are polygons with more than 4 20 vertices. 21 22 Can only create new meshes. 23 24 """ 25 26 def __init__(self): 27 # vertex storage, list of (x, y, z) tuples or Vec3() objects 28 self.vertices: List[Vec3] = [] 29 # face storage, each face is a tuple of vertex indices (v0, v1, v2, v3, ....), 30 # AutoCAD supports ngons 31 self.faces: List[Sequence[int]] = [] 32 # edge storage, each edge is a 2-tuple of vertex indices (v0, v1) 33 self.edges: List[Tuple[int, int]] = [] 34 35 def copy(self): 36 """ Returns a copy of mesh. """ 37 return self.from_builder(self) 38 39 def faces_as_vertices(self) -> Iterable[List[Vec3]]: 40 """ Iterate over all mesh faces as list of vertices. """ 41 v = self.vertices 42 for face in self.faces: 43 yield [v[index] for index in face] 44 45 def edges_as_vertices(self) -> Iterable[Tuple[Vec3, Vec3]]: 46 """ Iterate over all mesh edges as tuple of two vertices. """ 47 v = self.vertices 48 for edge in self.edges: 49 yield v[edge[0]], v[edge[1]] 50 51 def add_face(self, vertices: Iterable['Vertex']) -> None: 52 """ Add a face as vertices list to the mesh. A face requires at least 3 53 vertices, each vertex is a ``(x, y, z)`` tuple or 54 :class:`~ezdxf.math.Vec3` object. The new vertex indices are stored as 55 face in the :attr:`faces` list. 56 57 Args: 58 vertices: list of at least 3 vertices ``[(x1, y1, z1), (x2, y2, z2), 59 (x3, y3, y3), ...]`` 60 61 """ 62 self.faces.append(self.add_vertices(vertices)) 63 64 def add_edge(self, vertices: Iterable['Vertex']) -> None: 65 """ An edge consist of two vertices ``[v1, v2]``, each vertex is a 66 ``(x, y, z)`` tuple or a :class:`~ezdxf.math.Vec3` object. The new 67 vertex indices are stored as edge in the :attr:`edges` list. 68 69 Args: 70 vertices: list of 2 vertices : [(x1, y1, z1), (x2, y2, z2)] 71 72 """ 73 vertices = list(vertices) 74 if len(vertices) == 2: 75 self.edges.append(self.add_vertices(vertices)) 76 else: 77 raise DXFValueError( 78 'Invalid vertices count, expected two vertices.') 79 80 def add_vertices(self, vertices: Iterable['Vertex']) -> Sequence[int]: 81 """ Add new vertices to the mesh, each vertex is a ``(x, y, z)`` tuple 82 or a :class:`~ezdxf.math.Vec3` object, returns the indices of the 83 `vertices` added to the :attr:`vertices` list. 84 85 e.g. adding 4 vertices to an empty mesh, returns the indices 86 ``(0, 1, 2, 3)``, adding additional 4 vertices returns the indices 87 ``(4, 5, 6, 7)``. 88 89 Args: 90 vertices: list of vertices, vertex as ``(x, y, z)`` tuple or 91 :class:`~ezdxf.math.Vec3` objects 92 93 Returns: 94 tuple: indices of the `vertices` added to the :attr:`vertices` list 95 96 """ 97 start_index = len(self.vertices) 98 self.vertices.extend(Vec3.generate(vertices)) 99 return tuple(range(start_index, len(self.vertices))) 100 101 def add_mesh(self, 102 vertices: List[Vec3] = None, 103 faces: List[Sequence[int]] = None, 104 edges: List[Tuple[int, int]] = None, 105 mesh=None) -> None: 106 """ Add another mesh to this mesh. 107 108 A `mesh` can be a :class:`MeshBuilder`, :class:`MeshVertexMerger` or 109 :class:`~ezdxf.entities.Mesh` object or requires the attributes 110 :attr:`vertices`, :attr:`edges` and :attr:`faces`. 111 112 Args: 113 vertices: list of vertices, a vertex is a ``(x, y, z)`` tuple or 114 :class:`~ezdxf.math.Vec3` object 115 faces: list of faces, a face is a list of vertex indices 116 edges: list of edges, an edge is a list of vertex indices 117 mesh: another mesh entity 118 119 """ 120 if mesh is not None: 121 vertices = Vec3.list(mesh.vertices) 122 faces = mesh.faces 123 edges = mesh.edges 124 125 if vertices is None: 126 raise ValueError("Requires vertices or another mesh.") 127 faces = faces or [] 128 edges = edges or [] 129 indices = self.add_vertices(vertices) 130 131 for v1, v2 in edges: 132 self.edges.append((indices[v1], indices[v2])) 133 134 for face_vertices in faces: 135 self.faces.append(tuple(indices[vi] for vi in face_vertices)) 136 137 def has_none_planar_faces(self) -> bool: 138 """ Returns ``True`` if any face is none planar. """ 139 return not all( 140 is_planar_face(face) for face in self.faces_as_vertices()) 141 142 def render_mesh(self, layout: 'GenericLayoutType', dxfattribs: dict = None, 143 matrix: 'Matrix44' = None, ucs: 'UCS' = None): 144 """ Render mesh as :class:`~ezdxf.entities.Mesh` entity into `layout`. 145 146 Args: 147 layout: :class:`~ezdxf.layouts.BaseLayout` object 148 dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}`` 149 matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44` 150 ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS` 151 152 """ 153 vertices = self.vertices 154 if matrix is not None: 155 vertices = list(matrix.transform_vertices(vertices)) 156 if ucs is not None: 157 vertices = ucs.points_to_wcs(vertices) 158 mesh = layout.add_mesh(dxfattribs=dxfattribs) 159 with mesh.edit_data() as data: 160 # data will be copied at setting in edit_data() 161 data.vertices = vertices 162 data.edges = self.edges 163 data.faces = self.faces 164 return mesh 165 166 render = render_mesh # TODO: 2021-02-10 - compatibility alias 167 168 def render_normals(self, layout: 'GenericLayoutType', length: float = 1, 169 relative=True, dxfattribs: dict = None): 170 """ Render face normals as :class:`~ezdxf.entities.Line` entities into 171 `layout`, useful to check orientation of mesh faces. 172 173 Args: 174 layout: :class:`~ezdxf.layouts.BaseLayout` object 175 length: visual length of normal, use length < 0 to point normals in 176 opposite direction 177 relative: scale length relative to face size if ``True`` 178 dxfattribs: dict of DXF attributes e.g. ``{'layer': 'normals', 'color': 6}`` 179 180 """ 181 for face in self.faces_as_vertices(): 182 count = len(face) 183 if count < 3: 184 continue 185 center = sum(face) / count 186 i = 0 187 n = NULLVEC 188 while i <= count - 3: 189 n = normal_vector_3p(face[i], face[i + 1], face[i + 2]) 190 if n != NULLVEC: # not colinear vectors 191 break 192 i += 1 193 194 if relative: 195 _length = (face[0] - center).magnitude * length 196 else: 197 _length = length 198 layout.add_line(center, center + n * _length, dxfattribs=dxfattribs) 199 200 @classmethod 201 def from_mesh(cls, other) -> 'MeshBuilder': 202 """ Create new mesh from other mesh as class method. 203 204 Args: 205 other: `mesh` of type :class:`MeshBuilder` and inherited or DXF 206 :class:`~ezdxf.entities.Mesh` entity or any object providing 207 attributes :attr:`vertices`, :attr:`edges` and :attr:`faces`. 208 209 """ 210 # just copy properties 211 mesh = cls() 212 mesh.add_mesh(mesh=other) 213 return mesh 214 215 @classmethod 216 def from_polyface(cls, 217 other: Union['Polymesh', 'Polyface']) -> 'MeshBuilder': 218 """ Create new mesh from a :class:`~ezdxf.entities.Polyface` or 219 :class:`~ezdxf.entities.Polymesh` object. 220 221 """ 222 if other.dxftype() != 'POLYLINE': 223 raise TypeError(f'Unsupported DXF type: {other.dxftype()}') 224 225 mesh = cls() 226 if other.is_poly_face_mesh: 227 _, faces = other.indexed_faces() 228 for face in faces: 229 mesh.add_face(face.points()) 230 elif other.is_polygon_mesh: 231 vertices = other.get_mesh_vertex_cache() 232 for m in range(other.dxf.m_count - 1): 233 for n in range(other.dxf.n_count - 1): 234 mesh.add_face( 235 ( 236 vertices[m, n], 237 vertices[m, n + 1], 238 vertices[m + 1, n + 1], 239 vertices[m + 1, n], 240 ) 241 ) 242 else: 243 raise TypeError('Not a polymesh or polyface.') 244 return mesh 245 246 def render_polyface(self, layout: 'GenericLayoutType', 247 dxfattribs: dict = None, 248 matrix: 'Matrix44' = None, 249 ucs: 'UCS' = None): 250 """ Render mesh as :class:`~ezdxf.entities.Polyface` entity into 251 `layout`. 252 253 Args: 254 layout: :class:`~ezdxf.layouts.BaseLayout` object 255 dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}`` 256 matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44` 257 ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS` 258 259 """ 260 polyface = layout.add_polyface(dxfattribs=dxfattribs) 261 t = MeshTransformer.from_builder(self) 262 if matrix is not None: 263 t.transform(matrix) 264 if ucs is not None: 265 t.transform(ucs.matrix) 266 polyface.append_faces(subdivide_ngons(t.faces_as_vertices())) 267 return polyface 268 269 def render_3dfaces(self, layout: 'GenericLayoutType', 270 dxfattribs: dict = None, 271 matrix: 'Matrix44' = None, 272 ucs: 'UCS' = None): 273 """ Render mesh as :class:`~ezdxf.entities.Face3d` entities into 274 `layout`. 275 276 Args: 277 layout: :class:`~ezdxf.layouts.BaseLayout` object 278 dxfattribs: dict of DXF attributes e.g. ``{'layer': 'mesh', 'color': 7}`` 279 matrix: transformation matrix of type :class:`~ezdxf.math.Matrix44` 280 ucs: transform vertices by :class:`~ezdxf.math.UCS` to :ref:`WCS` 281 282 """ 283 t = MeshTransformer.from_builder(self) 284 if matrix is not None: 285 t.transform(matrix) 286 if ucs is not None: 287 t.transform(ucs.matrix) 288 for face in subdivide_ngons(t.faces_as_vertices()): 289 layout.add_3dface(face, dxfattribs=dxfattribs) 290 291 @classmethod 292 def from_builder(cls, other: 'MeshBuilder') -> 'MeshBuilder': 293 """ Create new mesh from other mesh builder, faster than 294 :meth:`from_mesh` but supports only :class:`MeshBuilder` and inherited 295 classes. 296 297 """ 298 # just copy properties 299 mesh = cls() 300 mesh.vertices = list(other.vertices) 301 mesh.edges = list(other.edges) 302 mesh.faces = list(other.faces) 303 return mesh 304 305 306class MeshTransformer(MeshBuilder): 307 """ A mesh builder with inplace transformation support. """ 308 309 def subdivide(self, level: int = 1, quads=True, 310 edges=False) -> 'MeshTransformer': 311 """ Returns a new :class:`MeshTransformer` object with subdivided faces 312 and edges. 313 314 Args: 315 level: subdivide levels from 1 to max of 5 316 quads: create quad faces if ``True`` else create triangles 317 edges: also subdivide edges if ``True`` 318 """ 319 mesh = self 320 level = min(int(level), 5) 321 while level > 0: 322 mesh = _subdivide(mesh, quads, edges) 323 level -= 1 324 return MeshTransformer.from_builder(mesh) 325 326 def transform(self, matrix: 'Matrix44'): 327 """ Transform mesh inplace by applying the transformation `matrix`. 328 329 Args: 330 matrix: 4x4 transformation matrix as :class:`~ezdxf.math.Matrix44` 331 object 332 333 """ 334 self.vertices = list(matrix.transform_vertices(self.vertices)) 335 return self 336 337 def translate(self, dx: float = 0, dy: float = 0, dz: float = 0): 338 """ Translate mesh inplace. 339 340 Args: 341 dx: translation in x-axis 342 dy: translation in y-axis 343 dz: translation in z-axis 344 345 """ 346 if isinstance(dx, (float, int)): 347 t = Vec3(dx, dy, dz) 348 else: 349 t = Vec3(dx) 350 self.vertices = [t + v for v in self.vertices] 351 return self 352 353 def scale(self, sx: float = 1, sy: float = 1, sz: float = 1): 354 """ Scale mesh inplace. 355 356 Args: 357 sx: scale factor for x-axis 358 sy: scale factor for y-axis 359 sz: scale factor for z-axis 360 361 """ 362 self.vertices = [Vec3(x * sx, y * sy, z * sz) for x, y, z in 363 self.vertices] 364 return self 365 366 def scale_uniform(self, s: float): 367 """ Scale mesh uniform inplace. 368 369 Args: 370 s: scale factor for x-, y- and z-axis 371 372 """ 373 self.vertices = [v * s for v in self.vertices] 374 return self 375 376 def rotate_x(self, angle: float): 377 """ Rotate mesh around x-axis about `angle` inplace. 378 379 Args: 380 angle: rotation angle in radians 381 382 """ 383 self.vertices = list( 384 Matrix44.x_rotate(angle).transform_vertices(self.vertices)) 385 return self 386 387 def rotate_y(self, angle: float): 388 """ Rotate mesh around y-axis about `angle` inplace. 389 390 Args: 391 angle: rotation angle in radians 392 393 """ 394 self.vertices = list( 395 Matrix44.y_rotate(angle).transform_vertices(self.vertices)) 396 return self 397 398 def rotate_z(self, angle: float): 399 """ Rotate mesh around z-axis about `angle` inplace. 400 401 Args: 402 angle: rotation angle in radians 403 404 """ 405 self.vertices = list( 406 Matrix44.z_rotate(angle).transform_vertices(self.vertices)) 407 return self 408 409 def rotate_axis(self, axis: 'Vertex', angle: float): 410 """ Rotate mesh around an arbitrary axis located in the origin (0, 0, 0) 411 about `angle`. 412 413 Args: 414 axis: rotation axis as Vec3 415 angle: rotation angle in radians 416 417 """ 418 self.vertices = list( 419 Matrix44.axis_rotate(axis, angle).transform_vertices(self.vertices)) 420 return self 421 422 423def _subdivide(mesh, quads=True, edges=False) -> 'MeshVertexMerger': 424 """ Returns a new :class:`MeshVertexMerger` object with subdivided faces 425 and edges. 426 427 Args: 428 quads: create quad faces if ``True`` else create triangles 429 edges: also subdivide edges if ``True`` 430 431 """ 432 new_mesh = MeshVertexMerger() 433 for vertices in mesh.faces_as_vertices(): 434 if len(vertices) < 3: 435 continue 436 for face in subdivide_face(vertices, quads): 437 new_mesh.add_face(face) 438 439 if edges: 440 for start, end in mesh.edges_as_vertices(): 441 mid = start.lerp(end) 442 new_mesh.add_edge((start, mid)) 443 new_mesh.add_edge((mid, end)) 444 445 return new_mesh 446 447 448class MeshVertexMerger(MeshBuilder): 449 """ Subclass of :class:`MeshBuilder` 450 451 Mesh with unique vertices and no doublets, but needs extra memory for 452 bookkeeping. 453 454 :class:`MeshVertexMerger` creates a key for every vertex by rounding its 455 components by the Python :func:`round` function and a given `precision` 456 value. Each vertex with the same key gets the same vertex index, which is 457 the index of first vertex with this key, so all vertices with the same key 458 will be located at the location of this first vertex. If you want an average 459 location of and for all vertices with the same key look at the 460 :class:`MeshAverageVertexMerger` class. 461 462 Args: 463 precision: floating point precision for vertex rounding 464 465 """ 466 467 # can not support vertex transformation 468 def __init__(self, precision: int = 6): 469 """ 470 Args: 471 precision: floating point precision for vertex rounding 472 473 """ 474 super().__init__() 475 self.ledger: Dict['Vertex', int] = {} 476 self.precision: int = precision 477 478 def key(self, vertex: 'Vertex') -> 'Vertex': 479 """ Returns rounded vertex. (internal API) """ 480 p = self.precision 481 return round(vertex[0], p), round(vertex[1], p), round(vertex[2], p) 482 483 def add_vertices(self, vertices: Iterable['Vertex']) -> Sequence[int]: 484 """ Add new `vertices` only, if no vertex with identical (x, y, z) 485 coordinates already exist, else the index of the existing vertex is 486 returned as index of the added vertices. 487 488 Args: 489 vertices: list of vertices, vertex as (x, y, z) tuple or 490 :class:`~ezdxf.math.Vec3` objects 491 492 Returns: 493 indices of the added `vertices` 494 495 """ 496 indices = [] 497 for vertex in vertices: 498 key = self.key(vertex) 499 try: 500 indices.append(self.ledger[key]) 501 except KeyError: 502 index = len(self.vertices) 503 self.vertices.append(vertex) 504 self.ledger[key] = index 505 indices.append(index) 506 return tuple(indices) 507 508 def index(self, vertex: 'Vertex') -> int: 509 """ Get index of `vertex`, raise :class:`KeyError` if not found. 510 511 Args: 512 vertex: ``(x, y, z)`` tuple or :class:`~ezdxf.math.Vec3` object 513 514 (internal API) 515 """ 516 try: 517 return self.ledger[self.key(vertex)] 518 except KeyError: 519 raise IndexError(f"Vertex {str(vertex)} not found.") 520 521 @classmethod 522 def from_builder(cls, other: 'MeshBuilder'): 523 """ Create new mesh from other mesh builder. """ 524 # rebuild from scratch to crate a valid ledger 525 return cls.from_mesh(other) 526 527 528class MeshAverageVertexMerger(MeshBuilder): 529 """ Subclass of :class:`MeshBuilder` 530 531 Mesh with unique vertices and no doublets, but needs extra memory for 532 bookkeeping and runtime for calculation of average vertex location. 533 534 :class:`MeshAverageVertexMerger` creates a key for every vertex by rounding 535 its components by the Python :func:`round` function and a given `precision` 536 value. Each vertex with the same key gets the same vertex index, which is the 537 index of first vertex with this key, the difference to the 538 :class:`MeshVertexMerger` class is the calculation of the average location 539 for all vertices with the same key, this needs extra memory to keep track of 540 the count of vertices for each key and extra runtime for updating the vertex 541 location each time a vertex with an existing key is added. 542 543 Args: 544 precision: floating point precision for vertex rounding 545 546 """ 547 548 # can not support vertex transformation 549 def __init__(self, precision: int = 6): 550 super().__init__() 551 self.ledger: Dict[Vec3, Tuple[ 552 int, int]] = {} # each key points to a tuple (vertex index, vertex count) 553 self.precision: int = precision 554 555 def add_vertices(self, vertices: Iterable['Vertex']) -> Sequence[int]: 556 """ Add new `vertices` only, if no vertex with identical ``(x, y, z)`` 557 coordinates already exist, else the index of the existing vertex is 558 returned as index of the added vertices. 559 560 Args: 561 vertices: list of vertices, vertex as ``(x, y, z)`` tuple or 562 :class:`~ezdxf.math.Vec3` objects 563 564 Returns: 565 tuple: indices of the `vertices` added to the 566 :attr:`~MeshBuilder.vertices` list 567 568 """ 569 indices = [] 570 precision = self.precision 571 for vertex in vertices: 572 vertex = Vec3(vertex) 573 key = vertex.round(precision) 574 try: 575 index, count = self.ledger[key] 576 except KeyError: # new key 577 index = len(self.vertices) 578 self.vertices.append(vertex) 579 self.ledger[key] = (index, 1) 580 else: # update key entry 581 # calculate new average location 582 average = (self.vertices[index] * count) + vertex 583 count += 1 584 # update vertex location 585 self.vertices[index] = average / count 586 # update ledger 587 self.ledger[key] = (index, count) 588 indices.append(index) 589 return tuple(indices) 590 591 def index(self, vertex: 'Vertex') -> int: 592 """ Get index of `vertex`, raise :class:`KeyError` if not found. 593 594 Args: 595 vertex: ``(x, y, z)`` tuple or :class:`~ezdxf.math.Vec3` object 596 597 (internal API) 598 """ 599 try: 600 return self.ledger[Vec3(vertex).round(self.precision)][0] 601 except KeyError: 602 raise IndexError(f"Vertex {str(vertex)} not found.") 603 604 @classmethod 605 def from_builder(cls, other: 'MeshBuilder'): 606 """ Create new mesh from other mesh builder. """ 607 # rebuild from scratch to crate a valid ledger 608 return cls.from_mesh(other) 609