pyffi.utils.tristrip

1 """A wrapper for TriangleStripifier and some utility functions, for 2 stripification of sets of triangles, stitching and unstitching strips, 3 and triangulation of strips.""" 4 5 # ***** BEGIN LICENSE BLOCK ***** 6 # 7 # Copyright (c) 2007-2011, Python File Format Interface 8 # All rights reserved. 9 # 10 # Redistribution and use in source and binary forms, with or without 11 # modification, are permitted provided that the following conditions 12 # are met: 13 # 14 # * Redistributions of source code must retain the above copyright 15 # notice, this list of conditions and the following disclaimer. 16 # 17 # * Redistributions in binary form must reproduce the above 18 # copyright notice, this list of conditions and the following 19 # disclaimer in the documentation and/or other materials provided 20 # with the distribution. 21 # 22 # * Neither the name of the Python File Format Interface 23 # project nor the names of its contributors may be used to endorse 24 # or promote products derived from this software without specific 25 # prior written permission. 26 # 27 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 28 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 29 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 30 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 31 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 32 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 33 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 34 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 35 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 37 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 38 # POSSIBILITY OF SUCH DAMAGE. 39 # 40 # ***** END LICENSE BLOCK ***** 41 42 try: 43 import pytristrip 44 except ImportError: 45 pytristrip = None 46 from pyffi.utils.trianglestripifier import TriangleStripifier 47 from pyffi.utils.trianglemesh import Mesh 48

49 -def triangulate(strips):

50 """A generator for iterating over the faces in a set of 51 strips. Degenerate triangles in strips are discarded. 52 53 >>> triangulate([[1, 0, 1, 2, 3, 4, 5, 6]]) 54 [(0, 2, 1), (1, 2, 3), (2, 4, 3), (3, 4, 5), (4, 6, 5)] 55 """ 56 57 triangles = [] 58 59 for strip in strips: 60 if len(strip) < 3: continue # skip empty strips 61 i = strip.__iter__() 62 j = False 63 t1, t2 = i.next(), i.next() 64 for k in xrange(2, len(strip)): 65 j = not j 66 t0, t1, t2 = t1, t2, i.next() 67 if t0 == t1 or t1 == t2 or t2 == t0: continue 68 triangles.append((t0, t1, t2) if j else (t0, t2, t1)) 69 70 return triangles

71

72 -def _generate_faces_from_triangles(triangles):

73 i = triangles.__iter__() 74 while True: 75 yield (i.next(), i.next(), i.next())

76

77 -def _sort_triangle_indices(triangles):

78 """Sorts indices of each triangle so lowest index always comes first. 79 Also removes degenerate triangles. 80 81 >>> list(_sort_triangle_indices([(2,1,3),(0,2,6),(9,8,4)])) 82 [(1, 3, 2), (0, 2, 6), (4, 9, 8)] 83 >>> list(_sort_triangle_indices([(2,1,1),(0,2,6),(9,8,4)])) 84 [(0, 2, 6), (4, 9, 8)] 85 """ 86 for t0, t1, t2 in triangles: 87 # skip degenerate triangles 88 if t0 == t1 or t1 == t2 or t2 == t0: 89 continue 90 # sort indices 91 if t0 < t1 and t0 < t2: 92 yield (t0, t1, t2) 93 elif t1 < t0 and t1 < t2: 94 yield (t1, t2, t0) 95 elif t2 < t0 and t2 < t1: 96 yield (t2, t0, t1) 97 else: 98 # should *never* happen 99 raise RuntimeError( 100 "Unexpected error while sorting triangle indices.")

101

102 -def _check_strips(triangles, strips):

103 """Checks that triangles and strips describe the same geometry. 104 105 >>> _check_strips([(0,1,2),(2,1,3)], [[0,1,2,3]]) 106 >>> _check_strips([(0,1,2),(2,1,3)], [[3,2,1,0]]) 107 >>> _check_strips([(0,1,2),(2,1,3)], [[3,2,1,0,1]]) 108 >>> _check_strips([(0,1,2),(2,1,3)], [[3,3,3,2,1,0,1]]) 109 >>> _check_strips([(0,1,2),(2,1,3),(1,0,1)], [[0,1,2,3]]) 110 >>> _check_strips([(0,1,2),(2,1,3),(4,4,4)], [[0,1,2,3]]) 111 >>> _check_strips([(0,1,2),(2,1,3)], [[0,1,2,3], [2,3,4]]) # doctest: +ELLIPSIS 112 Traceback (most recent call last): 113 ... 114 ValueError: ... 115 >>> _check_strips([(0,1,2),(2,1,3),(2,3,4)], [[0,1,2,3]]) # doctest: +ELLIPSIS 116 Traceback (most recent call last): 117 ... 118 ValueError: ... 119 >>> _check_strips([(0,1,2),(2,1,3),(2,3,4),(3,8,1)], [[0,1,2,3,7],[9,10,5,9]]) # doctest: +ELLIPSIS 120 Traceback (most recent call last): 121 ... 122 ValueError: ... 123 """ 124 # triangulate 125 strips_triangles = set(_sort_triangle_indices(triangulate(strips))) 126 triangles = set(_sort_triangle_indices(triangles)) 127 # compare 128 if strips_triangles != triangles: 129 raise ValueError( 130 "triangles and strips do not match\n" 131 "triangles = %s\n" 132 "strips = %s\n" 133 "triangles - strips = %s\n" 134 "strips - triangles = %s\n" 135 % (triangles, strips, 136 triangles - strips_triangles, 137 strips_triangles - triangles))

138

139 -def stripify(triangles, stitchstrips = False):

140 """Converts triangles into a list of strips. 141 142 If stitchstrips is True, then everything is wrapped in a single strip using 143 degenerate triangles. 144 145 >>> triangles = [(0,1,4),(1,2,4),(2,3,4),(3,0,4)] 146 >>> strips = stripify(triangles) 147 >>> _check_strips(triangles, strips) 148 >>> triangles = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, 14), (15, 16, 17), (18, 19, 20), (21, 22, 23)] 149 >>> strips = stripify(triangles) 150 >>> _check_strips(triangles, strips) 151 >>> triangles = [(0, 1, 2), (0, 1, 2)] 152 >>> strips = stripify(triangles) 153 >>> _check_strips(triangles, strips) 154 >>> triangles = [(0, 1, 2), (2, 1, 0)] 155 >>> strips = stripify(triangles) 156 >>> _check_strips(triangles, strips) 157 >>> triangles = [(0, 1, 2), (2, 1, 0), (1, 2, 3)] 158 >>> strips = stripify(triangles) 159 >>> _check_strips(triangles, strips) # NvTriStrip gives wrong result 160 >>> triangles = [(0, 1, 2), (0, 1, 3)] 161 >>> strips = stripify(triangles) 162 >>> _check_strips(triangles, strips) # NvTriStrip gives wrong result 163 >>> triangles = [(1, 5, 2), (5, 2, 6), (5, 9, 6), (9, 6, 10), (9, 13, 10), (13, 10, 14), (0, 4, 1), (4, 1, 5), (4, 8, 5), (8, 5, 9), (8, 12, 9), (12, 9, 13), (2, 6, 3), (6, 3, 7), (6, 10, 7), (10, 7, 11), (10, 14, 11), (14, 11, 15)] 164 >>> strips = stripify(triangles) 165 >>> _check_strips(triangles, strips) # NvTriStrip gives wrong result 166 >>> triangles = [(1, 2, 3), (4, 5, 6), (6, 5, 7), (8, 5, 9), (4, 10, 9), (8, 3, 11), (8, 10, 3), (12, 13, 6), (14, 2, 15), (16, 13, 15), (16, 2, 3), (3, 2, 1)] 167 >>> strips = stripify(triangles) 168 >>> _check_strips(triangles, strips) # detects bug reported by PacificMorrowind 169 >>> triangles = [(354, 355, 356), (355, 356, 354), (354, 355, 356), (355, 356, 354), (354, 355, 356), (356, 354, 355), (354, 355, 356), (357, 359, 358), 170 ... (380, 372, 381), (372, 370, 381), (381, 370, 354), (370, 367, 354), (367, 366, 354), (366, 355, 354), (355, 356, 354), (354, 356, 381), 171 ... (356, 355, 357), (357, 356, 355), (356, 355, 357), (356, 355, 357), (357, 356, 355)] 172 >>> strips = stripify(triangles) 173 >>> _check_strips(triangles, strips) # NvTriStrip gives wrong result 174 """ 175 176 if pytristrip: 177 strips = pytristrip.stripify(triangles) 178 else: 179 strips = [] 180 # build a mesh from triangles 181 mesh = Mesh() 182 for face in triangles: 183 try: 184 mesh.add_face(*face) 185 except ValueError: 186 # degenerate face 187 pass 188 mesh.lock() 189 190 # calculate the strip 191 stripifier = TriangleStripifier(mesh) 192 strips = stripifier.find_all_strips() 193 194 # stitch the strips if needed 195 if stitchstrips: 196 return [stitch_strips(strips)] 197 else: 198 return strips

199

200 -class OrientedStrip:

201 """An oriented strip, with stitching support.""" 202

203 - def __init__(self, strip):

204 """Construct oriented strip from regular strip (i.e. a list). 205 206 Constructors 207 ------------ 208 209 >>> ostrip = OrientedStrip([0,1,2,3]) 210 >>> ostrip.vertices 211 [0, 1, 2, 3] 212 >>> ostrip.reversed 213 False 214 215 >>> ostrip = OrientedStrip([0,0,1,2,3]) 216 >>> ostrip.vertices 217 [0, 1, 2, 3] 218 >>> ostrip.reversed 219 True 220 >>> ostrip2 = OrientedStrip(ostrip) 221 >>> ostrip2.vertices 222 [0, 1, 2, 3] 223 >>> ostrip2.reversed 224 True 225 226 >>> ostrip = OrientedStrip(None) # doctest: +ELLIPSIS 227 Traceback (most recent call last): 228 ... 229 TypeError: ... 230 231 Compactify 232 ---------- 233 234 >>> ostrip = OrientedStrip([0,0,0,1,2,3]) 235 >>> ostrip.vertices 236 [0, 1, 2, 3] 237 >>> ostrip.reversed 238 False 239 >>> ostrip = OrientedStrip([0,0,0,0,1,2,3]) 240 >>> ostrip.vertices 241 [0, 1, 2, 3] 242 >>> ostrip.reversed 243 True 244 >>> ostrip = OrientedStrip([0,0,0,1,2,3,3,3,3]) 245 >>> ostrip.vertices 246 [0, 1, 2, 3] 247 >>> ostrip.reversed 248 False 249 >>> ostrip = OrientedStrip([0,0,0,0,1,2,3,3,3,3]) 250 >>> ostrip.vertices 251 [0, 1, 2, 3] 252 >>> ostrip.reversed 253 True 254 """ 255 256 if isinstance(strip, (list, tuple)): 257 # construct from strip 258 self.vertices = list(strip) 259 self.reversed = False 260 self.compactify() 261 elif isinstance(strip, OrientedStrip): 262 # copy constructor 263 self.vertices = strip.vertices[:] 264 self.reversed = strip.reversed 265 else: 266 raise TypeError( 267 "expected list or OrientedStrip, but got %s" 268 % strip.__class__.__name__)

269

270 - def compactify(self):

271 """Remove degenerate faces from front and back.""" 272 # remove from front 273 if len(self.vertices) < 3: 274 raise ValueError( 275 "strip must have at least one non-degenerate face") 276 while self.vertices[0] == self.vertices[1]: 277 del self.vertices[0] 278 self.reversed = not self.reversed 279 if len(self.vertices) < 3: 280 raise ValueError( 281 "strip must have at least one non-degenerate face") 282 # remove from back 283 while self.vertices[-1] == self.vertices[-2]: 284 del self.vertices[-1] 285 if len(self.vertices) < 3: 286 raise ValueError( 287 "strip must have at least one non-degenerate face")

288

289 - def reverse(self):

290 """Reverse vertices.""" 291 self.vertices.reverse() 292 if len(self.vertices) & 1: 293 self.reversed = not self.reversed

294

295 - def __len__(self):

296 if self.reversed: 297 return len(self.vertices) + 1 298 else: 299 return len(self.vertices)

300

301 - def __iter__(self):

302 if self.reversed: 303 yield self.vertices[0] 304 for vert in self.vertices: 305 yield vert

306

307 - def __str__(self):

308 """String representation. 309 310 >>> print(OrientedStrip([0, 1, 2, 3, 4])) 311 [0, 1, 2, 3, 4] 312 >>> print(OrientedStrip([0, 0, 1, 2, 3, 4])) 313 [0, 0, 1, 2, 3, 4] 314 """ 315 return str(list(self))

316

317 - def __repr__(self):

318 return "OrientedStrip(%s)" % str(list(self))

319

320 - def get_num_stitches(self, other):

321 """Get number of stitches required to glue the vertices of self to 322 other. 323 """ 324 # do last vertex of self and first vertex of other match? 325 has_common_vertex = (self.vertices[-1] == other.vertices[0]) 326 327 # do windings match? 328 if len(self.vertices) & 1: 329 has_winding_match = (self.reversed != other.reversed) 330 else: 331 has_winding_match = (self.reversed == other.reversed) 332 333 # append stitches 334 if has_common_vertex: 335 if has_winding_match: 336 return 0 337 else: 338 return 1 339 else: 340 if has_winding_match: 341 return 2 342 else: 343 return 3

344

345 - def __add__(self, other):

346 """Combine two strips, using minimal number of stitches. 347 348 >>> # stitch length 0 code path 349 >>> OrientedStrip([0,1,2,3]) + OrientedStrip([3,4,5]) 350 OrientedStrip([0, 1, 2, 3, 3, 4, 5]) 351 >>> OrientedStrip([0,1,2]) + OrientedStrip([2,2,3,4]) 352 OrientedStrip([0, 1, 2, 2, 3, 4]) 353 354 >>> # stitch length 1 code path 355 >>> OrientedStrip([0,1,2]) + OrientedStrip([2,3,4]) 356 OrientedStrip([0, 1, 2, 2, 2, 3, 4]) 357 >>> OrientedStrip([0,1,2,3]) + OrientedStrip([3,3,4,5]) 358 OrientedStrip([0, 1, 2, 3, 3, 3, 4, 5]) 359 360 >>> # stitch length 2 code path 361 >>> OrientedStrip([0,1,2,3]) + OrientedStrip([7,8,9]) 362 OrientedStrip([0, 1, 2, 3, 3, 7, 7, 8, 9]) 363 >>> OrientedStrip([0,1,2]) + OrientedStrip([7,7,8,9]) 364 OrientedStrip([0, 1, 2, 2, 7, 7, 8, 9]) 365 366 >>> # stitch length 3 code path 367 >>> OrientedStrip([0,1,2,3]) + OrientedStrip([7,7,8,9]) 368 OrientedStrip([0, 1, 2, 3, 3, 7, 7, 7, 8, 9]) 369 >>> OrientedStrip([0,1,2]) + OrientedStrip([7,8,9]) 370 OrientedStrip([0, 1, 2, 2, 7, 7, 7, 8, 9]) 371 """ 372 # make copy of self 373 result = OrientedStrip(self) 374 375 # get number of stitches required 376 num_stitches = self.get_num_stitches(other) 377 if num_stitches >= 4 or num_stitches < 0: 378 # should *never* happen 379 raise RuntimeError("Unexpected error during stitching.") 380 381 # append stitches 382 if num_stitches >= 1: 383 result.vertices.append(self.vertices[-1]) # first stitch 384 if num_stitches >= 2: 385 result.vertices.append(other.vertices[0]) # second stitch 386 if num_stitches >= 3: 387 result.vertices.append(other.vertices[0]) # third stitch 388 389 # append other vertices 390 result.vertices.extend(other.vertices) 391 392 return result

393

394 -def stitch_strips(strips):

395 """Stitch strips keeping stitch size minimal. 396 397 >>> # stitch length 0 code path 398 >>> stitch_strips([[3,4,5],[0,1,2,3]]) 399 [0, 1, 2, 3, 3, 4, 5] 400 >>> stitch_strips([[2,2,3,4],[0,1,2]]) 401 [0, 1, 2, 2, 3, 4] 402 403 >>> # check result when changing ordering of strips 404 >>> stitch_strips([[0,1,2,3],[3,4,5]]) 405 [0, 1, 2, 3, 3, 4, 5] 406 407 >>> # check result when changing direction of strips 408 >>> stitch_strips([[3,2,1,0],[3,4,5]]) 409 [0, 1, 2, 3, 3, 4, 5] 410 411 >>> # stitch length 1 code path 412 >>> stitch_strips([[2,3,4],[0,1,2]]) 413 [0, 1, 2, 2, 2, 3, 4] 414 >>> stitch_strips([[3,3,4,5],[0,1,2,3]]) 415 [0, 1, 2, 3, 3, 3, 4, 5] 416 417 >>> # stitch length 2 code path 418 >>> stitch_strips([[7,8,9],[0,1,2,3]]) 419 [0, 1, 2, 3, 3, 7, 7, 8, 9] 420 >>> stitch_strips([[7,7,8,9],[0,1,2]]) 421 [0, 1, 2, 2, 7, 7, 8, 9] 422 423 >>> # stitch length 3 code path... but algorithm reverses strips so 424 >>> # only 2 stitches are needed (compare with OrientedStrip doctest) 425 >>> stitch_strips([[7,7,8,9],[0,1,2,3]]) 426 [3, 2, 1, 0, 0, 9, 9, 8, 7] 427 >>> stitch_strips([[7,8,9],[0,1,2]]) 428 [0, 1, 2, 2, 9, 9, 8, 7] 429 """ 430 431 class ExperimentSelector: 432 """Helper class to select best experiment.""" 433 def __init__(self): 434 self.best_ostrip1 = None 435 self.best_ostrip2 = None 436 self.best_num_stitches = None 437 self.best_ostrip_index = None

438 439 def update(self, ostrip_index, ostrip1, ostrip2): 440 num_stitches = ostrip1.get_num_stitches(ostrip2) 441 if ((self.best_num_stitches is None) 442 or (num_stitches < self.best_num_stitches)): 443 self.best_ostrip1 = ostrip1 444 self.best_ostrip2 = ostrip2 445 self.best_ostrip_index = ostrip_index 446 self.best_num_stitches = num_stitches 447 448 # get all strips and their orientation, and their reverse 449 ostrips = [(OrientedStrip(strip), OrientedStrip(strip)) 450 for strip in strips if len(strip) >= 3] 451 for ostrip, reversed_ostrip in ostrips: 452 reversed_ostrip.reverse() 453 # start with one of the strips 454 if not ostrips: 455 # no strips! 456 return [] 457 result = ostrips.pop()[0] 458 # go on as long as there are strips left to process 459 while ostrips: 460 selector = ExperimentSelector() 461 462 for ostrip_index, (ostrip, reversed_ostrip) in enumerate(ostrips): 463 # try various ways of stitching strips 464 selector.update(ostrip_index, result, ostrip) 465 selector.update(ostrip_index, ostrip, result) 466 selector.update(ostrip_index, result, reversed_ostrip) 467 selector.update(ostrip_index, reversed_ostrip, result) 468 # break early if global optimum is already reached 469 if selector.best_num_stitches == 0: 470 break 471 # get best result, perform the actual stitching, and remove 472 # strip from ostrips 473 result = selector.best_ostrip1 + selector.best_ostrip2 474 ostrips.pop(selector.best_ostrip_index) 475 # get strip 476 strip = list(result) 477 # check if we can remove first vertex by reversing strip 478 if strip[0] == strip[1] and (len(strip) & 1 == 0): 479 strip = strip[1:] 480 strip.reverse() 481 # return resulting strip 482 return strip 483

484 -def unstitch_strip(strip):

485 """Revert stitched strip back to a set of strips without stitches. 486 487 >>> strip = [0,1,2,2,3,3,4,5,6,7,8] 488 >>> triangles = triangulate([strip]) 489 >>> strips = unstitch_strip(strip) 490 >>> _check_strips(triangles, strips) 491 >>> strips 492 [[0, 1, 2], [3, 3, 4, 5, 6, 7, 8]] 493 >>> strip = [0,1,2,3,3,4,4,4,5,6,7,8] 494 >>> triangles = triangulate([strip]) 495 >>> strips = unstitch_strip(strip) 496 >>> _check_strips(triangles, strips) 497 >>> strips 498 [[0, 1, 2, 3], [4, 4, 5, 6, 7, 8]] 499 >>> strip = [0,1,2,3,4,4,4,4,5,6,7,8] 500 >>> triangles = triangulate([strip]) 501 >>> strips = unstitch_strip(strip) 502 >>> _check_strips(triangles, strips) 503 >>> strips 504 [[0, 1, 2, 3, 4], [4, 4, 5, 6, 7, 8]] 505 >>> strip = [0,1,2,3,4,4,4,4,4,5,6,7,8] 506 >>> triangles = triangulate([strip]) 507 >>> strips = unstitch_strip(strip) 508 >>> _check_strips(triangles, strips) 509 >>> strips 510 [[0, 1, 2, 3, 4], [4, 5, 6, 7, 8]] 511 >>> strip = [0,0,1,1,2,2,3,3,4,4,4,4,4,5,5,6,6,7,7,8,8] 512 >>> triangles = triangulate([strip]) 513 >>> strips = unstitch_strip(strip) 514 >>> _check_strips(triangles, strips) 515 >>> strips 516 []""" 517 strips = [] 518 currentstrip = [] 519 i = 0 520 while i < len(strip)-1: 521 winding = i & 1 522 currentstrip.append(strip[i]) 523 if strip[i] == strip[i+1]: 524 # stitch detected, add current strip to list of strips 525 strips.append(currentstrip) 526 # and start a new one, taking into account winding 527 if winding == 1: 528 currentstrip = [] 529 else: 530 currentstrip = [strip[i+1]] 531 i += 1 532 # add last part 533 currentstrip.extend(strip[i:]) 534 strips.append(currentstrip) 535 # sanitize strips 536 for strip in strips: 537 while len(strip) >= 3 and strip[0] == strip[1] == strip[2]: 538 strip.pop(0) 539 strip.pop(0) 540 return [strip for strip in strips if len(strip) > 3 or (len(strip) == 3 and strip[0] != strip[1])]

541 542 if __name__=='__main__': 543 import doctest 544 doctest.testmod() 545

Source Code for Module pyffi.utils.tristrip