triListOpt.h

Engine/source/gfx/util/triListOpt.h

More...

Classes:

Namespaces:

Detailed Description

  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#ifndef _TRI_LIST_OPT_H_
 25#define _TRI_LIST_OPT_H_
 26
 27#include "core/util/tVector.h"
 28
 29namespace TriListOpt
 30{
 31   typedef U32 IndexType;
 32
 33   const U32 MaxSizeVertexCache = 32;
 34
 35   struct VertData
 36   {
 37      S32 cachePosition;
 38      F32 score;
 39      U32 numReferences;
 40      U32 numUnaddedReferences;
 41      S32 *triIndex;
 42
 43      VertData() : cachePosition(-1), score(0.0f), numReferences(0), numUnaddedReferences(0), triIndex(NULL) {}
 44      ~VertData() { if(triIndex != NULL) delete [] triIndex; triIndex = NULL; }
 45   };
 46
 47   struct TriData
 48   {
 49      bool isInList;
 50      F32 score;
 51      U32 vertIdx[3];
 52
 53      TriData() : isInList(false), score(0.0f) { dMemset(vertIdx, 0, sizeof(vertIdx)); }
 54   };
 55
 56   class LRUCacheModel
 57   {
 58      struct LRUCacheEntry
 59      {
 60         LRUCacheEntry *next;
 61         U32 vIdx;
 62         VertData *vData;
 63
 64         LRUCacheEntry() : next(NULL), vIdx(0), vData(NULL) {}
 65      };
 66
 67      LRUCacheEntry *mCacheHead;
 68
 69   public:
 70      LRUCacheModel() : mCacheHead(NULL) {}
 71      ~LRUCacheModel();
 72      void enforceSize(const dsize_t maxSize, Vector<U32> &outTrisToUpdate);
 73      void useVertex(const U32 vIdx, VertData *vData);
 74      S32 getCachePosition(const U32 vIdx);
 75   };
 76
 77
 78   /// This method will look at the index buffer for a triangle list, and generate
 79   /// a new index buffer which is optimized using Tom Forsyth's paper:
 80   /// "Linear-Speed Vertex Cache Optimization" 
 81   /// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
 82   /// @param   numVerts Number of vertices indexed by the 'indices'
 83   /// @param numIndices Number of elements in both 'indices' and 'outIndices'
 84   /// @param    indices Input index buffer
 85   /// @param outIndices Output index buffer
 86   ///
 87   /// @note Both 'indices' and 'outIndices' can point to the same memory.
 88   void OptimizeTriangleOrdering(const dsize_t numVerts, const dsize_t numIndices, const U32 *indices, IndexType *outIndices);
 89
 90   namespace FindVertexScore
 91   {
 92      const F32 CacheDecayPower = 1.5f;
 93      const F32 LastTriScore = 0.75f;
 94      const F32 ValenceBoostScale = 2.0f;
 95      const F32 ValenceBoostPower = 0.5f;
 96
 97      F32 score(const VertData &vertexData);
 98   };
 99};
100
101#endif
102