pyffi.utils.trianglemesh

1 # ***** BEGIN LICENSE BLOCK ***** 2 # 3 # Copyright (c) 2007-2011, Python File Format Interface 4 # All rights reserved. 5 # 6 # Redistribution and use in source and binary forms, with or without 7 # modification, are permitted provided that the following conditions 8 # are met: 9 # 10 # * Redistributions of source code must retain the above copyright 11 # notice, this list of conditions and the following disclaimer. 12 # 13 # * Redistributions in binary form must reproduce the above 14 # copyright notice, this list of conditions and the following 15 # disclaimer in the documentation and/or other materials provided 16 # with the distribution. 17 # 18 # * Neither the name of the Python File Format Interface 19 # project nor the names of its contributors may be used to endorse 20 # or promote products derived from this software without specific 21 # prior written permission. 22 # 23 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 31 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 33 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 # POSSIBILITY OF SUCH DAMAGE. 35 # 36 # ***** END LICENSE BLOCK ***** 37 38 # modified from: 39 40 # http://techgame.net/projects/Runeblade/browser/trunk/RBRapier/RBRapier/Tools/Geometry/Analysis/TriangleMesh.py?rev=760 41 42 # original license: 43 44 ##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 45 ##~ License 46 ##~ 47 ##- The RuneBlade Foundation library is intended to ease some 48 ##- aspects of writing intricate Jabber, XML, and User Interface (wxPython, etc.) 49 ##- applications, while providing the flexibility to modularly change the 50 ##- architecture. Enjoy. 51 ##~ 52 ##~ Copyright (C) 2002 TechGame Networks, LLC. 53 ##~ 54 ##~ This library is free software; you can redistribute it and/or 55 ##~ modify it under the terms of the BSD style License as found in the 56 ##~ LICENSE file included with this distribution. 57 ##~ 58 ##~ TechGame Networks, LLC can be reached at: 59 ##~ 3578 E. Hartsel Drive #211 60 ##~ Colorado Springs, Colorado, USA, 80920 61 ##~ 62 ##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 63 64 #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 65 #~ Imports 66 #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 67 68 import operator # itemgetter 69 70 71 try: 72 from weakref import WeakSet 73 except ImportError: 74 # for py2k 75 from weakref import ref

76 - class WeakSet(object):

77 """Simple weak set implementation. 78 79 >>> import gc 80 >>> ws = WeakSet() 81 >>> class Test(object): 82 ... pass 83 >>> x = Test() 84 >>> y = Test() 85 >>> ws.add(x) 86 >>> list(ws)[0] is x 87 True 88 >>> ws.add(y) 89 >>> len(list(ws)) == 2 90 True 91 >>> del x 92 >>> tmp = gc.collect() 93 >>> list(ws)[0] is y 94 True 95 >>> del y 96 >>> tmp = gc.collect() 97 >>> list(ws) 98 [] 99 """

100 - def __init__(self, data=None):

101 self.data = set() 102 def _remove(item, selfref=ref(self)): 103 self = selfref() 104 if self is not None: 105 self.data.discard(item)

106 self._remove = _remove 107 if data is not None: 108 self.update(data)

109

110 - def __iter__(self):

111 for itemref in self.data: 112 item = itemref() 113 if item is not None: 114 yield item

115

116 - def __len__(self):

117 return sum(x() is not None for x in self.data)

118

119 - def __contains__(self, item):

120 return ref(item) in self.data

121

122 - def __reduce__(self):

123 return (self.__class__, (list(self),), 124 getattr(self, '__dict__', None))

125

126 - def add(self, item):

127 self.data.add(ref(item, self._remove))

128

129 - def clear(self):

130 self.data.clear()

131

132 - def copy(self):

133 return self.__class__(self)

134

135 - def pop(self):

136 while True: 137 try: 138 itemref = self.data.pop() 139 except KeyError: 140 raise KeyError('pop from empty WeakSet') 141 item = itemref() 142 if item is not None: 143 return item

144

145 - def remove(self, item):

146 self.data.remove(ref(item))

147

148 - def discard(self, item):

149 self.data.discard(ref(item))

150

151 - def update(self, other):

152 if isinstance(other, self.__class__): 153 self.data.update(other.data) 154 else: 155 for element in other: 156 self.add(element)

157 - def __ior__(self, other):

158 self.update(other) 159 return self

160 161 # Helper functions for simple delegating methods.

162 - def _apply(self, other, method):

163 if not isinstance(other, self.__class__): 164 other = self.__class__(other) 165 newdata = method(other.data) 166 newset = self.__class__() 167 newset.data = newdata 168 return newset

169

170 - def difference(self, other):

171 return self._apply(other, self.data.difference)

172 __sub__ = difference 173

174 - def difference_update(self, other):

175 if self is other: 176 self.data.clear() 177 else: 178 self.data.difference_update(ref(item) for item in other)

179 - def __isub__(self, other):

180 if self is other: 181 self.data.clear() 182 else: 183 self.data.difference_update(ref(item) for item in other) 184 return self

185

186 - def intersection(self, other):

187 return self._apply(other, self.data.intersection)

188 __and__ = intersection 189

190 - def intersection_update(self, other):

191 self.data.intersection_update(ref(item) for item in other)

192 - def __iand__(self, other):

193 self.data.intersection_update(ref(item) for item in other) 194 return self

195

196 - def issubset(self, other):

197 return self.data.issubset(ref(item) for item in other)

198 __lt__ = issubset 199

200 - def __le__(self, other):

201 return self.data <= set(ref(item) for item in other)

202

203 - def issuperset(self, other):

204 return self.data.issuperset(ref(item) for item in other)

205 __gt__ = issuperset 206

207 - def __ge__(self, other):

208 return self.data >= set(ref(item) for item in other)

209

210 - def __eq__(self, other):

211 if not isinstance(other, self.__class__): 212 return NotImplemented 213 return self.data == set(ref(item) for item in other)

214

215 - def symmetric_difference(self, other):

216 return self._apply(other, self.data.symmetric_difference)

217 __xor__ = symmetric_difference 218

219 - def symmetric_difference_update(self, other):

220 if self is other: 221 self.data.clear() 222 else: 223 self.data.symmetric_difference_update(ref(item) for item in other)

224 - def __ixor__(self, other):

225 if self is other: 226 self.data.clear() 227 else: 228 self.data.symmetric_difference_update(ref(item) for item in other) 229 return self

230

231 - def union(self, other):

232 return self._apply(other, self.data.union)

233 __or__ = union 234

235 - def isdisjoint(self, other):

236 return len(self.intersection(other)) == 0

237

238 -class Edge:

239 """A directed edge which keeps track of its faces.""" 240

241 - def __init__(self, ev0, ev1):

242 """Edge constructor. 243 244 >>> edge = Edge(6, 9) 245 >>> edge.verts 246 (6, 9) 247 >>> edge = Edge(8, 5) 248 >>> edge.verts 249 (8, 5) 250 >>> edge = Edge(3, 3) # doctest: +ELLIPSIS 251 Traceback (most recent call last): 252 ... 253 ValueError: ... 254 """ 255 256 if ev0 == ev1: 257 raise ValueError("Degenerate edge.") 258 259 self.verts = (ev0, ev1) 260 """Vertices of the edge.""" 261 262 self.faces = WeakSet() 263 """Weak set of faces that have this edge."""

264

265 - def __repr__(self):

266 """String representation. 267 268 >>> Edge(1, 2) 269 Edge(1, 2) 270 """ 271 return "Edge(%s, %s)" % self.verts

272

273 -class Face:

274 """An oriented face which keeps track its adjacent faces.""" 275

276 - def __init__(self, v0, v1, v2):

277 """Construct face from vertices. 278 279 >>> face = Face(3, 7, 5) 280 >>> face.verts 281 (3, 7, 5) 282 >>> face = Face(9, 8, 2) 283 >>> face.verts 284 (2, 9, 8) 285 >>> face = Face(6, 1, 4) 286 >>> face.verts 287 (1, 4, 6) 288 >>> Face(30, 0, 30) # doctest: +ELLIPSIS 289 Traceback (most recent call last): 290 ... 291 ValueError: ... 292 >>> Face(0, 40, 40) # doctest: +ELLIPSIS 293 Traceback (most recent call last): 294 ... 295 ValueError: ... 296 >>> Face(50, 50, 0) # doctest: +ELLIPSIS 297 Traceback (most recent call last): 298 ... 299 ValueError: ... 300 >>> Face(7, 7, 7) # doctest: +ELLIPSIS 301 Traceback (most recent call last): 302 ... 303 ValueError: ... 304 """ 305 if v0 == v1 or v1 == v2 or v2 == v0: 306 raise ValueError("Degenerate face.") 307 if v0 < v1 and v0 < v2: 308 self.verts = (v0, v1, v2) 309 if v1 < v0 and v1 < v2: 310 self.verts = (v1, v2, v0) 311 if v2 < v0 and v2 < v1: 312 self.verts = (v2, v0, v1) 313 # no index yet 314 self.index = None 315 316 self.adjacent_faces = (WeakSet(), WeakSet(), WeakSet()) 317 """Weak sets of adjacent faces along edge opposite each vertex."""

318

319 - def __repr__(self):

320 """String representation. 321 322 >>> Face(3, 1, 2) 323 Face(1, 2, 3) 324 """ 325 return "Face(%s, %s, %s)" % self.verts

326

327 - def get_next_vertex(self, vi):

328 """Get next vertex of face. 329 330 >>> face = Face(8, 7, 5) 331 >>> face.get_next_vertex(8) 332 7 333 >>> face.get_next_vertex(7) 334 5 335 >>> face.get_next_vertex(5) 336 8 337 >>> face.get_next_vertex(10) # doctest: +ELLIPSIS 338 Traceback (most recent call last): 339 ... 340 ValueError: ... 341 """ 342 # XXX using list(self.verts) instead of self.verts 343 # XXX for Python 2.5 compatibility 344 return self.verts[(1, 2, 0)[list(self.verts).index(vi)]]

345

346 - def get_adjacent_faces(self, vi):

347 """Get adjacent faces associated with the edge opposite a vertex.""" 348 # XXX using list(self.verts) instead of self.verts 349 # XXX for Python 2.5 compatibility 350 return self.adjacent_faces[list(self.verts).index(vi)]

351

352 -class Mesh:

353 """A mesh of interconnected faces. 354 355 :ivar faces: List of faces of the mesh. 356 :type faces: ``list`` of :class:`Face`"""

357 - def __init__(self, faces=None, lock=True):

358 """Initialize a mesh, and optionally assign its faces and lock. 359 360 :param faces: ``None``, or an iterator over faces to assign to 361 the mesh. 362 :type faces: ``Iterable`` or ``type(None)`` 363 :param lock: Whether to lock the mesh or not (ignored when 364 `faces` are not specified). 365 :type lock: ``bool`` 366 """ 367 self._faces = {} 368 """Dictionary of all faces.""" 369 370 self._edges = {} 371 """Dictionary of all edges.""" 372 373 if faces is not None: 374 for v0, v1, v2 in faces: 375 self.add_face(v0, v1, v2) 376 if lock: 377 self.lock()

378

379 - def __repr__(self):

380 """String representation. Examples: 381 382 >>> m = Mesh() 383 >>> m 384 Mesh() 385 >>> tmp = m.add_face(1, 2, 3) 386 >>> tmp = m.add_face(3, 2, 4) 387 >>> m 388 Mesh(faces=[(1, 2, 3), (2, 4, 3)], lock=False) 389 >>> m.lock() 390 >>> m 391 Mesh(faces=[(1, 2, 3), (2, 4, 3)]) 392 >>> Mesh(faces=[(1, 2, 3),(3, 2, 4)]) 393 Mesh(faces=[(1, 2, 3), (2, 4, 3)]) 394 """ 395 try: 396 self.faces 397 except AttributeError: 398 # unlocked 399 if not self._faces: 400 # special case 401 return "Mesh()" 402 return ("Mesh(faces=[%s], lock=False)" 403 % ', '.join(repr(faceverts) 404 for faceverts in sorted(self._faces))) 405 else: 406 # locked 407 return ("Mesh(faces=[%s])" 408 % ', '.join(repr(face.verts) 409 for face in self.faces))

410

411 - def _add_edge(self, face, pv0, pv1):

412 """Create new edge for mesh for given face, or return existing 413 edge. Lists of faces of the new/existing edge is also updated, 414 as well as lists of adjacent faces. For internal use only, 415 called on each edge of the face in add_face. 416 """ 417 # create edge if not found 418 try: 419 edge = self._edges[(pv0, pv1)] 420 except KeyError: 421 # create edge 422 edge = Edge(pv0, pv1) 423 self._edges[(pv0, pv1)] = edge 424 425 # update edge's faces 426 edge.faces.add(face) 427 428 # find reverse edge in mesh 429 try: 430 otheredge = self._edges[(pv1, pv0)] 431 except KeyError: 432 pass 433 else: 434 # update adjacent faces 435 pv2 = face.get_next_vertex(pv1) 436 for otherface in otheredge.faces: 437 otherpv2 = otherface.get_next_vertex(pv0) 438 face.get_adjacent_faces(pv2).add(otherface) 439 otherface.get_adjacent_faces(otherpv2).add(face)

440

441 - def add_face(self, v0, v1, v2):

442 """Create new face for mesh, or return existing face. List of 443 adjacent faces is also updated. 444 445 >>> m = Mesh() 446 >>> f0 = m.add_face(0, 1, 2) 447 >>> [list(faces) for faces in f0.adjacent_faces] 448 [[], [], []] 449 450 >>> m = Mesh() 451 >>> f0 = m.add_face(0, 1, 2) 452 >>> f1 = m.add_face(2, 1, 3) 453 >>> f2 = m.add_face(2, 3, 4) 454 >>> len(m._faces) 455 3 456 >>> len(m._edges) 457 9 458 >>> f3 = m.add_face(2, 3, 4) 459 >>> f3 is f2 460 True 461 >>> f4 = m.add_face(10, 11, 12) 462 >>> f5 = m.add_face(12, 10, 11) 463 >>> f6 = m.add_face(11, 12, 10) 464 >>> f4 is f5 465 True 466 >>> f4 is f6 467 True 468 >>> len(m._faces) 469 4 470 >>> len(m._edges) 471 12 472 473 Another mesh:: 474 475 0->-1 476 \\ / \\ 477 2-<-3 478 2->-3 479 \\ / 480 4 481 482 >>> m = Mesh() 483 >>> f0 = m.add_face(0, 1, 2) 484 >>> f1 = m.add_face(1, 3, 2) 485 >>> f2 = m.add_face(2, 3, 4) 486 >>> list(f0.get_adjacent_faces(0)) 487 [Face(1, 3, 2)] 488 >>> list(f0.get_adjacent_faces(1)) 489 [] 490 >>> list(f0.get_adjacent_faces(2)) 491 [] 492 >>> list(f1.get_adjacent_faces(1)) 493 [Face(2, 3, 4)] 494 >>> list(f1.get_adjacent_faces(3)) 495 [Face(0, 1, 2)] 496 >>> list(f1.get_adjacent_faces(2)) 497 [] 498 >>> list(f2.get_adjacent_faces(2)) 499 [] 500 >>> list(f2.get_adjacent_faces(3)) 501 [] 502 >>> list(f2.get_adjacent_faces(4)) 503 [Face(1, 3, 2)] 504 >>> # add an extra face, and check changes 505 >>> f3 = m.add_face(2, 3, 5) 506 >>> list(f0.get_adjacent_faces(0)) 507 [Face(1, 3, 2)] 508 >>> list(f0.get_adjacent_faces(1)) 509 [] 510 >>> list(f0.get_adjacent_faces(2)) 511 [] 512 >>> list(f1.get_adjacent_faces(1)) # extra face here! 513 [Face(2, 3, 4), Face(2, 3, 5)] 514 >>> list(f1.get_adjacent_faces(3)) 515 [Face(0, 1, 2)] 516 >>> list(f1.get_adjacent_faces(2)) 517 [] 518 >>> list(f2.get_adjacent_faces(2)) 519 [] 520 >>> list(f2.get_adjacent_faces(3)) 521 [] 522 >>> list(f2.get_adjacent_faces(4)) 523 [Face(1, 3, 2)] 524 """ 525 face = Face(v0, v1, v2) 526 try: 527 face = self._faces[face.verts] 528 except KeyError: 529 # create edges and update links between faces 530 self._add_edge(face, v0, v1) 531 self._add_edge(face, v1, v2) 532 self._add_edge(face, v2, v0) 533 # register face in mesh 534 self._faces[face.verts] = face 535 536 return face

537

538 - def lock(self):

539 """Lock the mesh. Frees memory by clearing the structures 540 which are only used to update the face adjacency lists. Sets 541 the faces attribute to the sorted list of all faces (sorting helps 542 with ensuring that the strips in faces are close together). 543 544 >>> m = Mesh() 545 >>> f0 = m.add_face(3, 1, 2) 546 >>> f1 = m.add_face(0, 1, 2) 547 >>> f2 = m.add_face(5, 6, 2) 548 >>> m.faces # doctest: +ELLIPSIS 549 Traceback (most recent call last): 550 ... 551 AttributeError: ... 552 >>> m.lock() 553 >>> m.faces # should be sorted 554 [Face(0, 1, 2), Face(1, 2, 3), Face(2, 5, 6)] 555 >>> m.faces[0].index 556 0 557 >>> m.faces[1].index 558 1 559 >>> m.faces[2].index 560 2 561 >>> m._faces # doctest: +ELLIPSIS 562 Traceback (most recent call last): 563 ... 564 AttributeError: ... 565 >>> m._edges # doctest: +ELLIPSIS 566 Traceback (most recent call last): 567 ... 568 AttributeError: ... 569 >>> m.add_face(1, 2, 3) # doctest: +ELLIPSIS 570 Traceback (most recent call last): 571 ... 572 AttributeError: ... 573 """ 574 # store faces and set their index 575 self.faces = [] 576 for i, (verts, face) in enumerate(sorted(self._faces.iteritems(), 577 key=operator.itemgetter(0))): 578 face.index = i 579 self.faces.append(face) 580 # remove helper structures 581 del self._faces 582 del self._edges

583

584 - def discard_face(self, face):

585 """Remove the face from the mesh. 586 587 >>> m = Mesh() 588 >>> f0 = m.add_face(0, 1, 2) 589 >>> f1 = m.add_face(1, 3, 2) 590 >>> f2 = m.add_face(2, 3, 4) 591 >>> m.lock() 592 >>> list(f0.get_adjacent_faces(0)) 593 [Face(1, 3, 2)] 594 >>> m.discard_face(f1) 595 >>> list(f0.get_adjacent_faces(0)) 596 [] 597 """ 598 # note: don't delete, but set to None, to ensure that other 599 # face indices remain valid 600 self.faces[face.index] = None 601 for adj_faces in face.adjacent_faces: 602 for adj_face in adj_faces: 603 for adj_adj_faces in adj_face.adjacent_faces: 604 adj_adj_faces.discard(face)

605 # faster (but breaks py3k!!): 606 #if id(face) in adj_adj_faces.data: 607 # del adj_adj_faces.data[id(face)] 608 609 if __name__=='__main__': 610 import doctest 611 doctest.testmod() 612

Source Code for Module pyffi.utils.trianglemesh