pyffi.utils.trianglestripifier

1 """A general purpose stripifier, based on NvTriStrip (http://developer.nvidia.com/) 2 3 Credit for porting NvTriStrip to Python goes to the RuneBlade Foundation 4 library: 5 http://techgame.net/projects/Runeblade/browser/trunk/RBRapier/RBRapier/Tools/Geometry/Analysis/TriangleStripifier.py?rev=760 6 7 The algorithm of this stripifier is an improved version of the RuneBlade 8 Foundation / NVidia stripifier; it makes no assumptions about the 9 underlying geometry whatsoever and is intended to produce valid 10 output in all circumstances. 11 """ 12 13 # ***** BEGIN LICENSE BLOCK ***** 14 # 15 # Copyright (c) 2007-2011, Python File Format Interface 16 # All rights reserved. 17 # 18 # Redistribution and use in source and binary forms, with or without 19 # modification, are permitted provided that the following conditions 20 # are met: 21 # 22 # * Redistributions of source code must retain the above copyright 23 # notice, this list of conditions and the following disclaimer. 24 # 25 # * Redistributions in binary form must reproduce the above 26 # copyright notice, this list of conditions and the following 27 # disclaimer in the documentation and/or other materials provided 28 # with the distribution. 29 # 30 # * Neither the name of the Python File Format Interface 31 # project nor the names of its contributors may be used to endorse 32 # or promote products derived from this software without specific 33 # prior written permission. 34 # 35 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 36 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 37 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 38 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 39 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 40 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 41 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 42 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 43 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 44 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 45 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 46 # POSSIBILITY OF SUCH DAMAGE. 47 # 48 # ***** END LICENSE BLOCK ***** 49 50 import itertools 51 import random # choice 52 53 from pyffi.utils.trianglemesh import Face, Mesh

54 55 -class TriangleStrip(object):

56 """A heavily specialized oriented strip of faces. 57 58 Heavily adapted from NvTriStrip and RuneBlade. Originals can be found at 59 http://developer.nvidia.com/view.asp?IO=nvtristrip_library 60 and 61 http://techgame.net/projects/Runeblade/browser/trunk/RBRapier/RBRapier/Tools/Geometry/Analysis/TriangleStripifier.py?rev=760 62 """ 63

64 - def __init__(self, stripped_faces=None, 65 faces=None, vertices=None, reversed_=False):

66 """Initialise the triangle strip.""" 67 self.faces = faces if faces is not None else [] 68 self.vertices = vertices if vertices is not None else [] 69 self.reversed_ = reversed_ 70 71 # set of indices of stripped faces 72 self.stripped_faces = (stripped_faces 73 if stripped_faces is not None else set())

74

75 - def __repr__(self):

76 return ("TriangleStrip(stripped_faces=%s, faces=%s, vertices=%s, reversed_=%s)" 77 % (repr(self.stripped_faces), repr(self.faces), 78 repr(self.vertices), repr(self.reversed_)))

79

80 - def get_unstripped_adjacent_face(self, face, vi):

81 """Get adjacent face which is not yet stripped.""" 82 for otherface in face.get_adjacent_faces(vi): 83 if otherface.index not in self.stripped_faces: 84 return otherface

85

86 - def traverse_faces(self, start_vertex, start_face, forward):

87 """Builds a strip traveral of faces starting from the 88 start_face and the edge opposite start_vertex. Returns number 89 of faces added. 90 """ 91 count = 0 92 pv0 = start_vertex 93 pv1 = start_face.get_next_vertex(pv0) 94 pv2 = start_face.get_next_vertex(pv1) 95 next_face = self.get_unstripped_adjacent_face(start_face, pv0) 96 while next_face: 97 self.stripped_faces.add(next_face.index) 98 count += 1 99 if count & 1: 100 if forward: 101 pv0 = pv1 102 pv1 = next_face.get_next_vertex(pv0) 103 self.vertices.append(pv1) 104 self.faces.append(next_face) 105 else: 106 pv0 = pv2 107 pv2 = next_face.get_next_vertex(pv1) 108 self.vertices.insert(0, pv2) 109 self.faces.insert(0, next_face) 110 self.reversed_ = not self.reversed_ 111 else: 112 if forward: 113 pv0 = pv2 114 pv2 = next_face.get_next_vertex(pv1) 115 self.vertices.append(pv2) 116 self.faces.append(next_face) 117 else: 118 pv0 = pv1 119 pv1 = next_face.get_next_vertex(pv0) 120 self.vertices.insert(0, pv1) 121 self.faces.insert(0, next_face) 122 self.reversed_ = not self.reversed_ 123 next_face = self.get_unstripped_adjacent_face(next_face, pv0) 124 return count

125

126 - def build(self, start_vertex, start_face):

127 """Builds the face strip forwards, then backwards. Returns 128 index of start_face. 129 130 Check case of single triangle 131 ----------------------------- 132 133 >>> m = Mesh() 134 >>> face = m.add_face(0, 1, 2) 135 >>> m.lock() 136 >>> t = TriangleStrip() 137 >>> t.build(0, face) 138 0 139 >>> t 140 TriangleStrip(stripped_faces=set([0]), faces=[Face(0, 1, 2)], vertices=[0, 1, 2], reversed_=False) 141 >>> t.get_strip() 142 [0, 1, 2] 143 >>> t = TriangleStrip() 144 >>> t.build(1, face) 145 0 146 >>> t 147 TriangleStrip(stripped_faces=set([0]), faces=[Face(0, 1, 2)], vertices=[1, 2, 0], reversed_=False) 148 >>> t.get_strip() 149 [1, 2, 0] 150 >>> t = TriangleStrip() 151 >>> t.build(2, face) 152 0 153 >>> t 154 TriangleStrip(stripped_faces=set([0]), faces=[Face(0, 1, 2)], vertices=[2, 0, 1], reversed_=False) 155 >>> t.get_strip() 156 [2, 0, 1] 157 158 Check case of two triangles, with special strip winding fix 159 ----------------------------------------------------------- 160 161 >>> m = Mesh() 162 >>> face0 = m.add_face(0, 1, 2) 163 >>> face1 = m.add_face(2, 1, 3) 164 >>> m.lock() 165 >>> t = TriangleStrip() 166 >>> t.build(0, face0) 167 0 168 >>> t 169 TriangleStrip(stripped_faces=set([0, 1]), faces=[Face(0, 1, 2), Face(1, 3, 2)], vertices=[0, 1, 2, 3], reversed_=False) 170 >>> t.get_strip() 171 [0, 1, 2, 3] 172 >>> t = TriangleStrip() 173 >>> t.build(1, face0) 174 1 175 >>> t 176 TriangleStrip(stripped_faces=set([0, 1]), faces=[Face(1, 3, 2), Face(0, 1, 2)], vertices=[3, 1, 2, 0], reversed_=True) 177 >>> t.get_strip() 178 [3, 2, 1, 0] 179 >>> t = TriangleStrip() 180 >>> t.build(2, face1) 181 1 182 >>> t 183 TriangleStrip(stripped_faces=set([0, 1]), faces=[Face(0, 1, 2), Face(1, 3, 2)], vertices=[0, 2, 1, 3], reversed_=True) 184 >>> t.get_strip() 185 [0, 1, 2, 3] 186 >>> t = TriangleStrip() 187 >>> t.build(3, face1) 188 0 189 >>> t 190 TriangleStrip(stripped_faces=set([0, 1]), faces=[Face(1, 3, 2), Face(0, 1, 2)], vertices=[3, 2, 1, 0], reversed_=False) 191 >>> t.get_strip() 192 [3, 2, 1, 0] 193 194 Check that extra vertex is appended to fix winding 195 -------------------------------------------------- 196 197 >>> m = Mesh() 198 >>> face0 = m.add_face(1, 3, 2) 199 >>> face1 = m.add_face(2, 3, 4) 200 >>> face2 = m.add_face(4, 3, 5) 201 >>> face3 = m.add_face(4, 5, 6) 202 >>> m.lock() 203 >>> t = TriangleStrip() 204 >>> t.build(2, face1) 205 1 206 >>> t 207 TriangleStrip(stripped_faces=set([0, 1, 2, 3]), faces=[Face(1, 3, 2), Face(2, 3, 4), Face(3, 5, 4), Face(4, 5, 6)], vertices=[1, 2, 3, 4, 5, 6], reversed_=True) 208 >>> t.get_strip() 209 [1, 1, 2, 3, 4, 5, 6] 210 211 Check that strip is reversed to fix winding 212 ------------------------------------------- 213 214 >>> m = Mesh() 215 >>> face0 = m.add_face(1, 3, 2) 216 >>> face1 = m.add_face(2, 3, 4) 217 >>> face2 = m.add_face(4, 3, 5) 218 >>> m.lock() 219 >>> t = TriangleStrip() 220 >>> t.build(2, face1) 221 1 222 >>> t 223 TriangleStrip(stripped_faces=set([0, 1, 2]), faces=[Face(1, 3, 2), Face(2, 3, 4), Face(3, 5, 4)], vertices=[1, 2, 3, 4, 5], reversed_=True) 224 >>> t.get_strip() 225 [5, 4, 3, 2, 1] 226 227 More complicated mesh 228 --------------------- 229 230 >>> m = Mesh() 231 >>> face0 = m.add_face(0, 1, 2) 232 >>> face1 = m.add_face(2, 1, 7) 233 >>> face2 = m.add_face(2, 7, 4) 234 >>> face3 = m.add_face(5, 3, 2) 235 >>> face4 = m.add_face(2, 1, 9) 236 >>> face5 = m.add_face(4, 7, 10) 237 >>> face6 = m.add_face(4, 10, 11) 238 >>> face7 = m.add_face(11, 10, 12) 239 >>> face8 = m.add_face(1, 0, 13) 240 >>> m.lock() 241 >>> t = TriangleStrip() 242 >>> t.build(7, face1) 243 4 244 >>> t.faces[4] == face1 # check result from build 245 True 246 >>> t.stripped_faces 247 set([0, 1, 2, 5, 6, 7, 8]) 248 >>> t.faces 249 [Face(10, 12, 11), Face(4, 10, 11), Face(4, 7, 10), Face(2, 7, 4), Face(1, 7, 2), Face(0, 1, 2), Face(0, 13, 1)] 250 >>> t.vertices 251 [12, 11, 10, 4, 7, 2, 1, 0, 13] 252 >>> t.reversed_ 253 False 254 >>> t.get_strip() 255 [12, 11, 10, 4, 7, 2, 1, 0, 13] 256 257 Mesh which has more than a single strip 258 --------------------------------------- 259 260 >>> m = Mesh() 261 >>> tmp = m.add_face(2, 1, 7) # in strip 262 >>> start_face = m.add_face(0, 1, 2) # in strip 263 >>> tmp = m.add_face(2, 7, 4) # in strip 264 >>> tmp = m.add_face(4, 7, 11) # in strip 265 >>> tmp = m.add_face(5, 3, 2) 266 >>> tmp = m.add_face(1, 0, 8) # in strip 267 >>> tmp = m.add_face(0, 8, 9) # bad orientation! 268 >>> tmp = m.add_face(8, 0, 10) # in strip 269 >>> m.lock() 270 >>> t = TriangleStrip() 271 >>> t.build(0, start_face) 272 2 273 >>> t.vertices 274 [10, 8, 0, 1, 2, 7, 4, 11] 275 >>> t.get_strip() 276 [10, 8, 0, 1, 2, 7, 4, 11] 277 """ 278 del self.faces[:] 279 del self.vertices[:] 280 self.reversed_ = False 281 v0 = start_vertex 282 v1 = start_face.get_next_vertex(v0) 283 v2 = start_face.get_next_vertex(v1) 284 self.stripped_faces.add(start_face.index) 285 self.faces.append(start_face) 286 self.vertices.append(v0) 287 self.vertices.append(v1) 288 self.vertices.append(v2) 289 self.traverse_faces(v0, start_face, True) 290 return self.traverse_faces(v2, start_face, False)

291

292 - def get_strip(self):

293 """Get strip in forward winding.""" 294 strip = [] 295 if self.reversed_: 296 if len(self.vertices) & 1: 297 strip = list(reversed(self.vertices)) 298 elif len(self.vertices) == 4: 299 strip = list(self.vertices[i] for i in (0, 2, 1, 3)) 300 else: 301 strip = list(self.vertices) 302 strip.insert(0, strip[0]) 303 else: 304 strip = list(self.vertices) 305 return strip

306

307 -class Experiment(object):

308 """A stripification experiment, essentially consisting of a set of 309 adjacent strips. 310 """ 311

312 - def __init__(self, start_vertex, start_face):

313 self.stripped_faces = set() 314 self.start_vertex = start_vertex 315 self.start_face = start_face 316 self.strips = []

317

318 - def build(self):

319 """Build strips, starting from start_vertex and start_face. 320 321 >>> m = Mesh() 322 >>> tmp = m.add_face(2, 1, 7) 323 >>> s1_face = m.add_face(0, 1, 2) 324 >>> tmp = m.add_face(2, 7, 4) # in strip 325 >>> tmp = m.add_face(4, 7, 11) # in strip 326 >>> tmp = m.add_face(5, 3, 2) 327 >>> tmp = m.add_face(1, 0, 8) # in strip 328 >>> tmp = m.add_face(0, 8, 9) # bad orientation! 329 >>> tmp = m.add_face(8, 0, 10) # in strip 330 >>> tmp = m.add_face(10, 11, 8) # in strip 331 >>> # parallel strip 332 >>> s2_face = m.add_face(0, 2, 21) # in strip 333 >>> tmp = m.add_face(21, 2, 22) # in strip 334 >>> tmp = m.add_face(2, 4, 22) # in strip 335 >>> tmp = m.add_face(21, 24, 0) # in strip 336 >>> tmp = m.add_face(9, 0, 24) # in strip 337 >>> # parallel strip, further down 338 >>> s3_face = m.add_face(8, 11, 31) # in strip 339 >>> tmp = m.add_face(8, 31, 32) # in strip 340 >>> tmp = m.add_face(31, 11, 33) # in strip 341 >>> m.lock() 342 >>> # build experiment 343 >>> exp = Experiment(0, s1_face) 344 >>> exp.build() 345 >>> len(exp.strips) 346 2 347 >>> exp.strips[0].get_strip() 348 [11, 4, 7, 2, 1, 0, 8, 10, 11] 349 >>> exp.strips[1].get_strip() 350 [4, 22, 2, 21, 0, 24, 9] 351 >>> # note: with current algorithm [32, 8, 31, 11, 33] is not found 352 """ 353 # build initial strip 354 strip = TriangleStrip(stripped_faces=self.stripped_faces) 355 strip.build(self.start_vertex, self.start_face) 356 self.strips.append(strip) 357 # build adjacent strips 358 num_faces = len(strip.faces) 359 if num_faces >= 4: 360 face_index = num_faces >> 1 # quick / 2 361 self.build_adjacent(strip, face_index) 362 self.build_adjacent(strip, face_index + 1) 363 elif num_faces == 3: 364 if not self.build_adjacent(strip, 0): 365 self.build_adjacent(strip, 2) 366 self.build_adjacent(strip, 1) 367 elif num_faces == 2: 368 self.build_adjacent(strip, 0) 369 self.build_adjacent(strip, 1) 370 elif num_faces == 1: 371 self.build_adjacent(strip, 0)

372

373 - def build_adjacent(self, strip, face_index):

374 """Build strips adjacent to given strip, and add them to the 375 experiment. This is a helper function used by build. 376 """ 377 opposite_vertex = strip.vertices[face_index + 1] 378 face = strip.faces[face_index] 379 other_face = strip.get_unstripped_adjacent_face(face, opposite_vertex) 380 if other_face: 381 winding = strip.reversed_ 382 if face_index & 1: 383 winding = not winding 384 other_strip = TriangleStrip(stripped_faces=self.stripped_faces) 385 if winding: 386 other_vertex = strip.vertices[face_index] 387 face_index = other_strip.build(other_vertex, other_face) 388 else: 389 other_vertex = strip.vertices[face_index + 2] 390 face_index = other_strip.build(other_vertex, other_face) 391 self.strips.append(other_strip) 392 if face_index > (len(other_strip.faces) >> 1): # quick / 2 393 self.build_adjacent(other_strip, face_index - 1) 394 elif face_index < len(other_strip.faces) - 1: 395 self.build_adjacent(other_strip, face_index + 1) 396 return True 397 return False

398

399 -class ExperimentSelector(object):

400

401 - def __init__(self):

402 self.best_score = -1.0 403 self.best_experiment = None

404

405 - def update(self, experiment):

406 """Updates best experiment with given experiment, if given 407 experiment beats current experiment. 408 """ 409 score = (sum((len(strip.faces) for strip in experiment.strips), 0.0) 410 / len(experiment.strips)) 411 if score > self.best_score: 412 self.best_score = score 413 self.best_experiment = experiment

414

415 - def clear(self):

416 """Remove best experiment, to start a fresh sequence of 417 experiments. 418 """ 419 self.best_score = -1.0 420 self.best_experiment = None

421

422 -class TriangleStripifier(object):

423 """Implementation of a triangle stripifier. 424 425 Heavily adapted from NvTriStrip. 426 Original can be found at http://developer.nvidia.com/view.asp?IO=nvtristrip_library. 427 """ 428

429 - def __init__(self, mesh):

430 self.num_samples = 10 431 self.mesh = mesh

432 433 @staticmethod

434 - def sample(population, k):

435 """Return a k length list of unique elements chosen from the 436 population sequence. Used for random sampling without 437 replacement. Deterministic version of random.sample (being 438 deterministic means that it is easier to test). 439 440 >>> TriangleStripifier.sample(range(10), 1) 441 [0] 442 >>> TriangleStripifier.sample(range(10), 2) 443 [0, 9] 444 >>> TriangleStripifier.sample(range(10), 3) 445 [0, 4, 9] 446 >>> TriangleStripifier.sample(range(10), 4) 447 [0, 3, 6, 9] 448 >>> TriangleStripifier.sample(range(10), 5) 449 [0, 2, 4, 6, 9] 450 >>> TriangleStripifier.sample(range(10), 6) 451 [0, 1, 3, 5, 7, 9] 452 >>> TriangleStripifier.sample(range(10), 7) 453 [0, 1, 3, 4, 6, 7, 9] 454 >>> TriangleStripifier.sample(range(10), 8) 455 [0, 1, 2, 3, 5, 6, 7, 9] 456 >>> TriangleStripifier.sample(range(10), 9) 457 [0, 1, 2, 3, 4, 5, 6, 7, 9] 458 >>> TriangleStripifier.sample(range(10), 10) 459 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 460 """ 461 if k == 1: 462 # corner case 463 return [population[0]] 464 else: 465 # all other cases 466 return [ 467 population[int((i * (float(len(population)) - 1)) / (k - 1))] 468 for i in xrange(k)]

469

470 - def find_all_strips(self):

471 """Find all strips. 472 473 Empty mesh 474 ---------- 475 476 >>> m = Mesh() 477 >>> m.lock() 478 >>> ts = TriangleStripifier(m) 479 >>> ts.find_all_strips() 480 [] 481 482 Full mesh 483 --------- 484 485 >>> m = Mesh() 486 >>> tmp = m.add_face(2, 1, 7) 487 >>> tmp = m.add_face(0, 1, 2) 488 >>> tmp = m.add_face(2, 7, 4) # in strip 489 >>> tmp = m.add_face(4, 7, 11) # in strip 490 >>> tmp = m.add_face(5, 3, 2) 491 >>> tmp = m.add_face(1, 0, 8) # in strip 492 >>> tmp = m.add_face(0, 8, 9) # bad orientation! 493 >>> tmp = m.add_face(8, 0, 10) # in strip 494 >>> tmp = m.add_face(10, 11, 8) # in strip 495 >>> # parallel strip 496 >>> tmp = m.add_face(0, 2, 21) # in strip 497 >>> tmp = m.add_face(21, 2, 22) # in strip 498 >>> tmp = m.add_face(2, 4, 22) # in strip 499 >>> tmp = m.add_face(21, 24, 0) # in strip 500 >>> tmp = m.add_face(9, 0, 24) # in strip 501 >>> # parallel strip, further down 502 >>> tmp = m.add_face(8, 11, 31) # in strip 503 >>> tmp = m.add_face(8, 31, 32) # in strip 504 >>> tmp = m.add_face(31, 11, 33) # in strip 505 >>> m.lock() 506 >>> ts = TriangleStripifier(m) 507 >>> sorted(ts.find_all_strips()) 508 [[3, 2, 5], [4, 22, 2, 21, 0, 24, 9], [9, 0, 8], [11, 4, 7, 2, 1, 0, 8, 10, 11], [32, 8, 31, 11, 33]] 509 """ 510 all_strips = [] 511 selector = ExperimentSelector() 512 unstripped_faces = set(xrange(len(self.mesh.faces))) 513 while True: 514 experiments = [] 515 # note: using deterministic self.sample 516 # instead of existing random.sample in python 517 # because deterministic version is easier to test 518 for sample in self.sample(list(unstripped_faces), 519 min(self.num_samples, 520 len(unstripped_faces))): 521 exp_face = self.mesh.faces[sample] 522 for exp_vertex in exp_face.verts: 523 experiments.append( 524 Experiment(start_vertex=exp_vertex, 525 start_face=exp_face)) 526 if not experiments: 527 # done! 528 return all_strips 529 # note: use while loop so we only need to keep at most two 530 # built experiments at the same time in memory 531 while experiments: 532 experiment = experiments.pop() 533 experiment.build() 534 selector.update(experiment) 535 unstripped_faces -= selector.best_experiment.stripped_faces 536 # remove stripped faces from mesh 537 for strip in selector.best_experiment.strips: 538 for face in strip.faces: 539 self.mesh.discard_face(face) 540 # calculate actual strips for experiment 541 all_strips.extend( 542 (strip.get_strip() 543 for strip in selector.best_experiment.strips)) 544 selector.clear()

545 546 if __name__=='__main__': 547 import doctest 548 doctest.testmod() 549

Source Code for Module pyffi.utils.trianglestripifier