triListOpt.cpp
Engine/source/gfx/util/triListOpt.cpp
Namespaces:
namespace
namespace
Public Defines
define
_CHECK_NEXT_BEST(score, idx) { (score > nextBestTriScore) { (nextBestTriScore, nextBestTriIdx); nextBestTriIdx = ; nextBestTriScore = score; } (nextBestTriIdx); }
define
_CHECK_NEXT_NEXT_BEST(score, idx) { (score > nextNextBestTriScore) { nextNextBestTriIdx = ; nextNextBestTriScore = score; } }
define
_VALIDATE_TRI_IDX(idx) ( > -1) { ( < NumPrimitives, "Out of range triangle index."); AssertFatal(!triangleData[].isInList, "Triangle already in list, bad."); }
Detailed Description
Public Defines
_CHECK_NEXT_BEST(score, idx) { (score > nextBestTriScore) { (nextBestTriScore, nextBestTriIdx); nextBestTriIdx = ; nextBestTriScore = score; } (nextBestTriIdx); }
_CHECK_NEXT_NEXT_BEST(score, idx) { (score > nextNextBestTriScore) { nextNextBestTriIdx = ; nextNextBestTriScore = score; } }
_VALIDATE_TRI_IDX(idx) ( > -1) { ( < NumPrimitives, "Out of range triangle index."); AssertFatal(!triangleData[].isInList, "Triangle already in list, bad."); }
1 2//----------------------------------------------------------------------------- 3// Copyright (c) 2012 GarageGames, LLC 4// 5// Permission is hereby granted, free of charge, to any person obtaining a copy 6// of this software and associated documentation files (the "Software"), to 7// deal in the Software without restriction, including without limitation the 8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 9// sell copies of the Software, and to permit persons to whom the Software is 10// furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21// IN THE SOFTWARE. 22//----------------------------------------------------------------------------- 23 24#include "gfx/util/triListOpt.h" 25#include "core/frameAllocator.h" 26#include "platform/profiler.h" 27#include "math/mMathFn.h" 28 29namespace TriListOpt 30{ 31 32void OptimizeTriangleOrdering(const dsize_t numVerts, const dsize_t numIndices, const U32 *indices, IndexType *outIndices) 33{ 34 PROFILE_SCOPE(TriListOpt_OptimizeTriangleOrdering); 35 36 if(numVerts == 0 || numIndices == 0) 37 { 38 dCopyArray(outIndices, indices, numIndices); 39 return; 40 } 41 42 const U32 NumPrimitives = numIndices / 3; 43 AssertFatal(NumPrimitives == U32(mFloor(numIndices / 3.0f)), "Number of indicies not divisible by 3, not a good triangle list."); 44 45 // 46 // Step 1: Run through the data, and initialize 47 // 48 FrameTemp<VertData> vertexData(numVerts); 49 FrameTemp<TriData> triangleData(NumPrimitives); 50 51 U32 curIdx = 0; 52 for(S32 tri = 0; tri < NumPrimitives; tri++) 53 { 54 TriData &curTri = triangleData[tri]; 55 56 for(S32 c = 0; c < 3; c++) 57 { 58 const U32 &curVIdx = indices[curIdx]; 59 AssertFatal(curVIdx < numVerts, "Out of range index."); 60 61 // Add this vert to the list of verts that define the triangle 62 curTri.vertIdx[c] = curVIdx; 63 64 VertData &curVert = vertexData[curVIdx]; 65 66 // Increment the number of triangles that reference this vertex 67 curVert.numUnaddedReferences++; 68 69 curIdx++; 70 } 71 } 72 73 // Allocate per-vertex triangle lists, and calculate the starting score of 74 // each of the verts 75 for(S32 v = 0; v < numVerts; v++) 76 { 77 VertData &curVert = vertexData[v]; 78 curVert.triIndex = new S32[curVert.numUnaddedReferences]; 79 curVert.score = FindVertexScore::score(curVert); 80 } 81 82 // These variables will be used later, but need to be declared now 83 S32 nextNextBestTriIdx = -1, nextBestTriIdx = -1; 84 F32 nextNextBestTriScore = -1.0f, nextBestTriScore = -1.0f; 85 86#define _VALIDATE_TRI_IDX(idx) if(idx > -1) { AssertFatal(idx < NumPrimitives, "Out of range triangle index."); AssertFatal(!triangleData[idx].isInList, "Triangle already in list, bad."); } 87#define _CHECK_NEXT_NEXT_BEST(score, idx) { if(score > nextNextBestTriScore) { nextNextBestTriIdx = idx; nextNextBestTriScore = score; } } 88#define _CHECK_NEXT_BEST(score, idx) { if(score > nextBestTriScore) { _CHECK_NEXT_NEXT_BEST(nextBestTriScore, nextBestTriIdx); nextBestTriIdx = idx; nextBestTriScore = score; } _VALIDATE_TRI_IDX(nextBestTriIdx); } 89 90 // Fill-in per-vertex triangle lists, and sum the scores of each vertex used 91 // per-triangle, to get the starting triangle score 92 curIdx = 0; 93 for(S32 tri = 0; tri < NumPrimitives; tri++) 94 { 95 TriData &curTri = triangleData[tri]; 96 97 for(S32 c = 0; c < 3; c++) 98 { 99 const U32 &curVIdx = indices[curIdx]; 100 AssertFatal(curVIdx < numVerts, "Out of range index."); 101 VertData &curVert = vertexData[curVIdx]; 102 103 // Add triangle to triangle list 104 curVert.triIndex[curVert.numReferences++] = tri; 105 106 // Add vertex score to triangle score 107 curTri.score += curVert.score; 108 109 curIdx++; 110 } 111 112 // This will pick the first triangle to add to the list in 'Step 2' 113 _CHECK_NEXT_BEST(curTri.score, tri); 114 _CHECK_NEXT_NEXT_BEST(curTri.score, tri); 115 } 116 117 // 118 // Step 2: Start emitting triangles...this is the emit loop 119 // 120 LRUCacheModel lruCache; 121 for(S32 outIdx = 0; outIdx < numIndices; /* this space intentionally left blank */ ) 122 { 123 // If there is no next best triangle, than search for the next highest 124 // scored triangle that isn't in the list already 125 if(nextBestTriIdx < 0) 126 { 127 // TODO: Something better than linear performance here... 128 nextBestTriScore = nextNextBestTriScore = -1.0f; 129 nextBestTriIdx = nextNextBestTriIdx = -1; 130 131 for(S32 tri = 0; tri < NumPrimitives; tri++) 132 { 133 TriData &curTri = triangleData[tri]; 134 135 if(!curTri.isInList) 136 { 137 _CHECK_NEXT_BEST(curTri.score, tri); 138 _CHECK_NEXT_NEXT_BEST(curTri.score, tri); 139 } 140 } 141 } 142 AssertFatal(nextBestTriIdx > -1, "Ran out of 'nextBestTriangle' before I ran out of indices...not good."); 143 144 // Emit the next best triangle 145 TriData &nextBestTri = triangleData[nextBestTriIdx]; 146 AssertFatal(!nextBestTri.isInList, "Next best triangle already in list, this is no good."); 147 for(S32 i = 0; i < 3; i++) 148 { 149 // Emit index 150 outIndices[outIdx++] = IndexType(nextBestTri.vertIdx[i]); 151 152 // Update the list of triangles on the vert 153 VertData &curVert = vertexData[nextBestTri.vertIdx[i]]; 154 curVert.numUnaddedReferences--; 155 for(S32 t = 0; t < curVert.numReferences; t++) 156 { 157 if(curVert.triIndex[t] == nextBestTriIdx) 158 { 159 curVert.triIndex[t] = -1; 160 break; 161 } 162 } 163 164 // Update cache 165 lruCache.useVertex(nextBestTri.vertIdx[i], &curVert); 166 } 167 nextBestTri.isInList = true; 168 169 // Enforce cache size, this will update the cache position of all verts 170 // still in the cache. It will also update the score of the verts in the 171 // cache, and give back a list of triangle indicies that need updating. 172 Vector<U32> trisToUpdate; 173 lruCache.enforceSize(MaxSizeVertexCache, trisToUpdate); 174 175 // Now update scores for triangles that need updates, and find the new best 176 // triangle score/index 177 nextBestTriIdx = -1; 178 nextBestTriScore = -1.0f; 179 for(Vector<U32>::iterator itr = trisToUpdate.begin(); itr != trisToUpdate.end(); itr++) 180 { 181 TriData &tri = triangleData[*itr]; 182 183 // If this triangle isn't already emitted, re-score it 184 if(!tri.isInList) 185 { 186 tri.score = 0.0f; 187 188 for(S32 i = 0; i < 3; i++) 189 tri.score += vertexData[tri.vertIdx[i]].score; 190 191 _CHECK_NEXT_BEST(tri.score, *itr); 192 _CHECK_NEXT_NEXT_BEST(tri.score, *itr); 193 } 194 } 195 196 // If there was no love finding a good triangle, than see if there is a 197 // next-next-best triangle, and if there isn't one of those...well than 198 // I guess we have to find one next time 199 if(nextBestTriIdx < 0 && nextNextBestTriIdx > -1) 200 { 201 if(!triangleData[nextNextBestTriIdx].isInList) 202 { 203 nextBestTriIdx = nextNextBestTriIdx; 204 nextBestTriScore = nextNextBestTriScore; 205 _VALIDATE_TRI_IDX(nextNextBestTriIdx); 206 } 207 208 // Nuke the next-next best 209 nextNextBestTriIdx = -1; 210 nextNextBestTriScore = -1.0f; 211 } 212 213 // Validate triangle we are marking as next-best 214 _VALIDATE_TRI_IDX(nextBestTriIdx); 215 } 216 217#undef _CHECK_NEXT_BEST 218#undef _CHECK_NEXT_NEXT_BEST 219#undef _VALIDATE_TRI_IDX 220 221 // FrameTemp will call destructInPlace to clean up vertex lists 222} 223 224//------------------------------------------------------------------------------ 225//------------------------------------------------------------------------------ 226 227LRUCacheModel::~LRUCacheModel() 228{ 229 for( LRUCacheEntry* entry = mCacheHead; entry != NULL; ) 230 { 231 LRUCacheEntry* next = entry->next; 232 delete entry; 233 entry = next; 234 } 235} 236 237//------------------------------------------------------------------------------ 238 239void LRUCacheModel::useVertex(const U32 vIdx, VertData *vData) 240{ 241 LRUCacheEntry *search = mCacheHead; 242 LRUCacheEntry *last = NULL; 243 244 while(search != NULL) 245 { 246 if(search->vIdx == vIdx) 247 break; 248 249 last = search; 250 search = search->next; 251 } 252 253 // If this vertex wasn't found in the cache, create a new entry 254 if(search == NULL) 255 { 256 search = new LRUCacheEntry; 257 search->vIdx = vIdx; 258 search->vData = vData; 259 } 260 261 if(search != mCacheHead) 262 { 263 // Unlink the entry from the linked list 264 if(last) 265 last->next = search->next; 266 267 // Vertex that got passed in is now at the head of the cache 268 search->next = mCacheHead; 269 mCacheHead = search; 270 } 271} 272 273//------------------------------------------------------------------------------ 274 275void LRUCacheModel::enforceSize(const dsize_t maxSize, Vector<U32> &outTrisToUpdate) 276{ 277 // Clear list of triangles to update scores for 278 outTrisToUpdate.clear(); 279 280 dsize_t length = 0; 281 LRUCacheEntry *next = mCacheHead; 282 LRUCacheEntry *last = NULL; 283 284 // Run through list, up to the max size 285 while(next != NULL && length < MaxSizeVertexCache) 286 { 287 VertData &vData = *next->vData; 288 289 // Update cache position on verts still in cache 290 vData.cachePosition = length++; 291 292 for(S32 i = 0; i < vData.numReferences; i++) 293 { 294 const S32 &triIdx = vData.triIndex[i]; 295 if(triIdx > -1) 296 { 297 S32 j = 0; 298 for(; j < outTrisToUpdate.size(); j++) 299 if(outTrisToUpdate[j] == triIdx) 300 break; 301 if(j == outTrisToUpdate.size()) 302 outTrisToUpdate.push_back(triIdx); 303 } 304 } 305 306 // Update score 307 vData.score = FindVertexScore::score(vData); 308 309 last = next; 310 next = next->next; 311 } 312 313 // NULL out the pointer to the next entry on the last valid entry 314 last->next = NULL; 315 316 // If next != NULL, than we need to prune entries from the tail of the cache 317 while(next != NULL) 318 { 319 // Update cache position on verts which are going to get tossed from cache 320 next->vData->cachePosition = -1; 321 322 LRUCacheEntry *curEntry = next; 323 next = next->next; 324 325 delete curEntry; 326 } 327} 328 329//------------------------------------------------------------------------------ 330 331S32 LRUCacheModel::getCachePosition(const U32 vIdx) 332{ 333 dsize_t length = 0; 334 LRUCacheEntry *next = mCacheHead; 335 while(next != NULL) 336 { 337 if(next->vIdx == vIdx) 338 return length; 339 340 length++; 341 next = next->next; 342 } 343 344 return -1; 345} 346 347//------------------------------------------------------------------------------ 348//------------------------------------------------------------------------------ 349 350// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html 351namespace FindVertexScore 352{ 353 354F32 score(const VertData &vertexData) 355{ 356 // If nobody needs this vertex, return -1.0 357 if(vertexData.numUnaddedReferences < 1) 358 return -1.0f; 359 360 F32 Score = 0.0f; 361 362 if(vertexData.cachePosition < 0) 363 { 364 // Vertex is not in FIFO cache - no score. 365 } 366 else 367 { 368 if(vertexData.cachePosition < 3) 369 { 370 // This vertex was used in the last triangle, 371 // so it has a fixed score, whichever of the three 372 // it's in. Otherwise, you can get very different 373 // answers depending on whether you add 374 // the triangle 1,2,3 or 3,1,2 - which is silly. 375 Score = FindVertexScore::LastTriScore; 376 } 377 else 378 { 379 AssertFatal(vertexData.cachePosition < MaxSizeVertexCache, "Out of range cache position for vertex"); 380 381 // Points for being high in the cache. 382 const F32 Scaler = 1.0f / (MaxSizeVertexCache - 3); 383 Score = 1.0f - (vertexData.cachePosition - 3) * Scaler; 384 Score = mPow(Score, FindVertexScore::CacheDecayPower); 385 } 386 } 387 388 389 // Bonus points for having a low number of tris still to 390 // use the vert, so we get rid of lone verts quickly. 391 F32 ValenceBoost = mPow(vertexData.numUnaddedReferences, -FindVertexScore::ValenceBoostPower); 392 Score += FindVertexScore::ValenceBoostScale * ValenceBoost; 393 394 return Score; 395} 396 397} // namspace FindVertexScore 398 399} // namespace TriListOpt 400