pyffi.utils.vertex

1 """Algorithms to reorder triangle list order and vertex order aiming to 2 minimize vertex cache misses. 3 4 This is effectively an implementation of 5 'Linear-Speed Vertex Cache Optimisation' by Tom Forsyth, 28th September 2006 6 http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html 7 """ 8 9 # ***** BEGIN LICENSE BLOCK ***** 10 # 11 # Copyright (c) 2007-2011, Python File Format Interface 12 # All rights reserved. 13 # 14 # Redistribution and use in source and binary forms, with or without 15 # modification, are permitted provided that the following conditions 16 # are met: 17 # 18 # * Redistributions of source code must retain the above copyright 19 # notice, this list of conditions and the following disclaimer. 20 # 21 # * Redistributions in binary form must reproduce the above 22 # copyright notice, this list of conditions and the following 23 # disclaimer in the documentation and/or other materials provided 24 # with the distribution. 25 # 26 # * Neither the name of the Python File Format Interface 27 # project nor the names of its contributors may be used to endorse 28 # or promote products derived from this software without specific 29 # prior written permission. 30 # 31 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 34 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 35 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 36 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 37 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 38 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 39 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 40 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 41 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 42 # POSSIBILITY OF SUCH DAMAGE. 43 # 44 # ***** END LICENSE BLOCK ***** 45 46 from __future__ import division 47 48 import collections 49 50 from pyffi.utils.tristrip import OrientedStrip 51

52 -class VertexScore:

53 """Vertex score calculation.""" 54 # constants used for scoring algorithm 55 CACHE_SIZE = 32 # higher values yield virtually no improvement 56 """The size of the modeled cache.""" 57 58 CACHE_DECAY_POWER = 1.5 59 LAST_TRI_SCORE = 0.75 60 VALENCE_BOOST_SCALE = 2.0 61 VALENCE_BOOST_POWER = 0.5 62 63 # implementation note: limitation of 255 triangles per vertex 64 # this is unlikely to be exceeded... 65 MAX_TRIANGLES_PER_VERTEX = 255 66

67 - def __init__(self):

68 # calculation of score is precalculated for speed 69 self.precalculate()

70

71 - def precalculate(self):

72 self.CACHE_SCORE = [ 73 self.LAST_TRI_SCORE 74 if cache_position < 3 else 75 ((self.CACHE_SIZE - cache_position) 76 / (self.CACHE_SIZE - 3)) ** self.CACHE_DECAY_POWER 77 for cache_position in range(self.CACHE_SIZE)] 78 79 self.VALENCE_SCORE = [ 80 self.VALENCE_BOOST_SCALE * (valence ** (-self.VALENCE_BOOST_POWER)) 81 if valence > 0 else None 82 for valence in range(self.MAX_TRIANGLES_PER_VERTEX + 1)]

83

84 - def update_score(self, vertex_info):

85 """Update score: 86 87 * -1 if vertex has no triangles 88 * cache score + valence score otherwise 89 90 where cache score is 91 92 * 0 if vertex is not in cache 93 * 0.75 if vertex has been used very recently 94 (position 0, 1, or 2) 95 * (1 - (cache position - 3) / (32 - 3)) ** 1.5 96 otherwise 97 98 and valence score is 2 * (num triangles ** (-0.5)) 99 100 >>> vertex_score = VertexScore() 101 >>> def get_score(cache_position, triangle_indices): 102 ... vert = VertexInfo(cache_position=cache_position, 103 ... triangle_indices=triangle_indices) 104 ... vertex_score.update_score(vert) 105 ... return vert.score 106 >>> for cache_position in [-1, 0, 1, 2, 3, 4, 5]: 107 ... print("cache position = {0}".format(cache_position)) 108 ... for num_triangles in range(4): 109 ... print(" num triangles = {0} : {1:.3f}" 110 ... .format(num_triangles, 111 ... get_score(cache_position, 112 ... list(range(num_triangles))))) 113 cache position = -1 114 num triangles = 0 : -1.000 115 num triangles = 1 : 2.000 116 num triangles = 2 : 1.414 117 num triangles = 3 : 1.155 118 cache position = 0 119 num triangles = 0 : -1.000 120 num triangles = 1 : 2.750 121 num triangles = 2 : 2.164 122 num triangles = 3 : 1.905 123 cache position = 1 124 num triangles = 0 : -1.000 125 num triangles = 1 : 2.750 126 num triangles = 2 : 2.164 127 num triangles = 3 : 1.905 128 cache position = 2 129 num triangles = 0 : -1.000 130 num triangles = 1 : 2.750 131 num triangles = 2 : 2.164 132 num triangles = 3 : 1.905 133 cache position = 3 134 num triangles = 0 : -1.000 135 num triangles = 1 : 3.000 136 num triangles = 2 : 2.414 137 num triangles = 3 : 2.155 138 cache position = 4 139 num triangles = 0 : -1.000 140 num triangles = 1 : 2.949 141 num triangles = 2 : 2.363 142 num triangles = 3 : 2.103 143 cache position = 5 144 num triangles = 0 : -1.000 145 num triangles = 1 : 2.898 146 num triangles = 2 : 2.313 147 num triangles = 3 : 2.053 148 """ 149 if not vertex_info.triangle_indices: 150 # no triangle needs this vertex 151 vertex_info.score = -1 152 return 153 154 if vertex_info.cache_position < 0: 155 # not in cache 156 vertex_info.score = 0 157 else: 158 # use cache score lookup table 159 vertex_info.score = self.CACHE_SCORE[vertex_info.cache_position] 160 161 # bonus points for having low number of triangles still in use 162 # note: example mesh with more than 255 triangles per vertex is 163 # falloutnv/meshes/landscape/lod/freesidefortworld/freesidefortworld.level8.x-9.y1.nif 164 vertex_info.score += self.VALENCE_SCORE[ 165 min(len(vertex_info.triangle_indices), 166 self.MAX_TRIANGLES_PER_VERTEX)]

167

168 -class VertexInfo:

169 """Stores information about a vertex.""" 170

171 - def __init__(self, cache_position=-1, score=-1, 172 triangle_indices=None):

173 self.cache_position = cache_position 174 self.score = score 175 # only triangles that have *not* yet been drawn are in this list 176 self.triangle_indices = ([] if triangle_indices is None 177 else triangle_indices)

178

179 -class TriangleInfo:

180 - def __init__(self, score=0, vertex_indices=None):

181 self.score = score 182 self.vertex_indices = ([] if vertex_indices is None 183 else vertex_indices)

184

185 -class Mesh:

186 """Simple mesh implementation which keeps track of which triangles 187 are used by which vertex, and vertex cache positions. 188 """ 189 190 _DEBUG = False # to enable debugging of the algorithm 191

192 - def __init__(self, triangles, vertex_score=None):

193 """Initialize mesh from given set of triangles. 194 195 Empty mesh 196 ---------- 197 198 >>> Mesh([]).triangle_infos 199 [] 200 201 Single triangle mesh (with degenerate) 202 -------------------------------------- 203 204 >>> m = Mesh([(0,1,2), (1,2,0)]) 205 >>> [vertex_info.triangle_indices for vertex_info in m.vertex_infos] 206 [[0], [0], [0]] 207 >>> [triangle_info.vertex_indices for triangle_info in m.triangle_infos] 208 [(0, 1, 2)] 209 210 Double triangle mesh 211 -------------------- 212 213 >>> m = Mesh([(0,1,2), (2,1,3)]) 214 >>> [vertex_info.triangle_indices for vertex_info in m.vertex_infos] 215 [[0], [0, 1], [0, 1], [1]] 216 >>> [triangle_info.vertex_indices for triangle_info in m.triangle_infos] 217 [(0, 1, 2), (1, 3, 2)] 218 """ 219 # initialize vertex and triangle information, and vertex cache 220 self.vertex_infos = [] 221 self.triangle_infos = [] 222 # add all vertices 223 if triangles: 224 num_vertices = max(max(verts) for verts in triangles) + 1 225 else: 226 num_vertices = 0 227 # scoring algorithm 228 if vertex_score is None: 229 self.vertex_score = VertexScore() 230 else: 231 self.vertex_score = vertex_score 232 self.vertex_infos = [VertexInfo() for i in xrange(num_vertices)] 233 # add all triangles 234 for triangle_index, verts in enumerate(get_unique_triangles(triangles)): 235 self.triangle_infos.append(TriangleInfo(vertex_indices=verts)) 236 for vertex in verts: 237 self.vertex_infos[vertex].triangle_indices.append( 238 triangle_index) 239 # calculate score of all vertices 240 for vertex_info in self.vertex_infos: 241 self.vertex_score.update_score(vertex_info) 242 # calculate score of all triangles 243 for triangle_info in self.triangle_infos: 244 triangle_info.score = sum( 245 self.vertex_infos[vertex].score 246 for vertex in triangle_info.vertex_indices)

247

248 - def get_cache_optimized_triangles(self):

249 """Reorder triangles in a cache efficient way. 250 251 >>> m = Mesh([(0,1,2), (7,8,9),(2,3,4)]) 252 >>> m.get_cache_optimized_triangles() 253 [(7, 8, 9), (0, 1, 2), (2, 3, 4)] 254 """ 255 triangles = [] 256 cache = collections.deque() 257 # set of vertex indices whose scores were updated in the previous run 258 updated_vertices = set() 259 # set of triangle indices whose scores were updated in the previous run 260 updated_triangles = set() 261 while (updated_triangles 262 or any(triangle_info for triangle_info in self.triangle_infos)): 263 # pick triangle with highest score 264 if self._DEBUG or not updated_triangles: 265 # very slow but correct global maximum 266 best_triangle_index, best_triangle_info = max( 267 (triangle 268 for triangle in enumerate(self.triangle_infos) 269 if triangle[1]), 270 key=lambda triangle: triangle[1].score) 271 if updated_triangles: 272 if self._DEBUG: 273 globally_optimal_score = best_triangle_info.score 274 # if scores of triangles were updated in the previous run 275 # then restrict the search to those 276 # this is suboptimal, but the difference is usually very small 277 # and it is *much* faster (as noted by Forsyth) 278 best_triangle_index = max( 279 updated_triangles, 280 key=lambda triangle_index: 281 self.triangle_infos[triangle_index].score) 282 best_triangle_info = self.triangle_infos[best_triangle_index] 283 if (self._DEBUG and 284 globally_optimal_score - best_triangle_info.score > 0.01): 285 print(globally_optimal_score, 286 globally_optimal_score - best_triangle_info.score, 287 len(updated_triangles)) 288 # mark as added 289 self.triangle_infos[best_triangle_index] = None 290 # append to ordered list of triangles 291 triangles.append(best_triangle_info.vertex_indices) 292 # clean lists of vertices and triangles whose score we will update 293 updated_vertices = set() 294 updated_triangles = set() 295 # for each vertex in the just added triangle 296 for vertex in best_triangle_info.vertex_indices: 297 vertex_info = self.vertex_infos[vertex] 298 # remove triangle from the triangle list of the vertex 299 vertex_info.triangle_indices.remove(best_triangle_index) 300 # must update its score 301 updated_vertices.add(vertex) 302 updated_triangles.update(vertex_info.triangle_indices) 303 # add each vertex to cache (score is updated later) 304 for vertex in best_triangle_info.vertex_indices: 305 if vertex not in cache: 306 cache.appendleft(vertex) 307 if len(cache) > self.vertex_score.CACHE_SIZE: 308 # cache overflow! 309 # remove vertex from cache 310 removed_vertex = cache.pop() 311 removed_vertex_info = self.vertex_infos[removed_vertex] 312 # update its cache position 313 removed_vertex_info.cache_position = -1 314 # must update its score 315 updated_vertices.add(removed_vertex) 316 updated_triangles.update(removed_vertex_info.triangle_indices) 317 # for each vertex in the cache (this includes those from the 318 # just added triangle) 319 for i, vertex in enumerate(cache): 320 vertex_info = self.vertex_infos[vertex] 321 # update cache positions 322 vertex_info.cache_position = i 323 # must update its score 324 updated_vertices.add(vertex) 325 updated_triangles.update(vertex_info.triangle_indices) 326 # update scores 327 for vertex in updated_vertices: 328 self.vertex_score.update_score(self.vertex_infos[vertex]) 329 for triangle in updated_triangles: 330 triangle_info = self.triangle_infos[triangle] 331 triangle_info.score = sum( 332 self.vertex_infos[vertex].score 333 for vertex in triangle_info.vertex_indices) 334 # return result 335 return triangles

336

337 -def get_cache_optimized_triangles(triangles):

338 """Calculate cache optimized triangles, and return the result as 339 a reordered set of triangles or strip of stitched triangles. 340 341 :param triangles: The triangles (triples of vertex indices). 342 :return: A list of reordered triangles. 343 """ 344 mesh = Mesh(triangles) 345 return mesh.get_cache_optimized_triangles()

346

347 -def get_unique_triangles(triangles):

348 """Yield unique triangles. 349 350 >>> list(get_unique_triangles([(0, 1, 2), (1, 1, 0), (2, 1, 0), (1, 0, 0)])) 351 [(0, 1, 2), (0, 2, 1)] 352 >>> list(get_unique_triangles([(0, 1, 2), (1, 1, 0), (2, 0, 1)])) 353 [(0, 1, 2)] 354 """ 355 _added_triangles = set() 356 for v0, v1, v2 in triangles: 357 if v0 == v1 or v1 == v2 or v2 == v0: 358 # skip degenerate triangles 359 continue 360 if v0 < v1 and v0 < v2: 361 verts = (v0, v1, v2) 362 elif v1 < v0 and v1 < v2: 363 verts = (v1, v2, v0) 364 elif v2 < v0 and v2 < v1: 365 verts = (v2, v0, v1) 366 if verts not in _added_triangles: 367 yield verts 368 _added_triangles.add(verts)

369

370 -def stable_stripify(triangles, stitchstrips=False):

371 """Stitch all triangles together into a strip without changing the 372 triangle ordering (for example because their ordering is already 373 optimized). 374 375 :param triangles: The triangles (triples of vertex indices). 376 :return: A list of strips (list of vertex indices). 377 378 >>> stable_stripify([(0, 1, 2), (2, 1, 4)]) 379 [[0, 1, 2, 4]] 380 >>> stable_stripify([(0, 1, 2), (2, 3, 4)]) 381 [[0, 1, 2], [2, 3, 4]] 382 >>> stable_stripify([(0, 1, 2), (2, 1, 3), (2, 3, 4), (1, 4, 5), (5, 4, 6)]) 383 [[0, 1, 2, 3, 4], [1, 4, 5, 6]] 384 >>> stable_stripify([(0, 1, 2), (0, 3, 1), (0, 4, 3), (3, 5, 1), (6, 3, 4)]) 385 [[2, 0, 1, 3], [0, 4, 3], [3, 5, 1], [6, 3, 4]] 386 """ 387 # all orientation preserving triangle permutations 388 indices = ((0, 1, 2), (1, 2, 0), (2, 0, 1)) 389 # list of all strips so far 390 strips = [] 391 # current strip that is being built 392 strip = [] 393 # add a triangle at a time 394 for tri in triangles: 395 if not strip: 396 # empty strip 397 strip.extend(tri) 398 elif len(strip) == 3: 399 # strip with single triangle 400 # see if we can append a vertex 401 # we can rearrange the original strip as well 402 added = False 403 for v0, v1, v2 in indices: 404 for ov0, ov1, ov2 in indices: 405 if strip[v1] == tri[ov1] and strip[v2] == tri[ov0]: 406 strip = [strip[v0], strip[v1], strip[v2], tri[ov2]] 407 added = True 408 break 409 if added: 410 # triangle added: break loop 411 break 412 if added: 413 # triangle added: process next triangle 414 continue 415 # start new strip 416 strips.append(strip) 417 strip = list(tri) 418 else: 419 # strip with multiple triangles 420 added = False 421 for ov0, ov1, ov2 in indices: 422 if len(strip) & 1: 423 if strip[-2] == tri[ov1] and strip[-1] == tri[ov0]: 424 strip.append(tri[ov2]) 425 added = True 426 break 427 else: 428 if strip[-2] == tri[ov0] and strip[-1] == tri[ov1]: 429 strip.append(tri[ov2]) 430 added = True 431 break 432 if added: 433 # triangle added: process next triangle 434 continue 435 # start new strip 436 strips.append(strip) 437 strip = list(tri) 438 # append last strip 439 strips.append(strip) 440 if not stitchstrips or not strips: 441 return strips 442 else: 443 result = reduce(lambda x, y: x + y, 444 (OrientedStrip(strip) for strip in strips)) 445 return [list(result)]

446

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

448 """Stripify triangles, optimizing for the vertex cache.""" 449 return stable_stripify( 450 get_cache_optimized_triangles(triangles), 451 stitchstrips=stitchstrips)

452

453 -def get_cache_optimized_vertex_map(strips):

454 """Map vertices so triangles/strips have consequetive indices. 455 456 >>> get_cache_optimized_vertex_map([]) 457 [] 458 >>> get_cache_optimized_vertex_map([[]]) 459 [] 460 >>> get_cache_optimized_vertex_map([[0, 1, 3], []]) 461 [0, 1, None, 2] 462 >>> get_cache_optimized_vertex_map([(5,2,1),(0,2,3)]) 463 [3, 2, 1, 4, None, 0] 464 """ 465 if strips: 466 num_vertices = max(max(strip) if strip else -1 467 for strip in strips) + 1 468 else: 469 num_vertices = 0 470 vertex_map = [None for i in xrange(num_vertices)] 471 new_vertex = 0 472 for strip in strips: 473 for old_vertex in strip: 474 if vertex_map[old_vertex] is None: 475 vertex_map[old_vertex] = new_vertex 476 new_vertex += 1 477 return vertex_map

478

479 -def average_transform_to_vertex_ratio(strips, cache_size=16):

480 """Calculate number of transforms per vertex for a given cache size 481 and triangles/strips. See 482 http://castano.ludicon.com/blog/2009/01/29/acmr/ 483 """ 484 cache = collections.deque(maxlen=cache_size) 485 # get number of vertices 486 vertices = set([]) 487 for strip in strips: 488 vertices.update(strip) 489 # get number of cache misses (each miss needs a transform) 490 num_misses = 0 491 for strip in strips: 492 for vertex in strip: 493 if vertex in cache: 494 pass 495 else: 496 cache.appendleft(vertex) 497 num_misses += 1 498 # return result 499 if vertices: 500 return num_misses / float(len(vertices)) 501 else: 502 # no vertices... 503 return 1

504 505 if __name__=='__main__': 506 import doctest 507 doctest.testmod() 508

Source Code for Module pyffi.utils.vertex_cache