三角形帶優化庫nvtrisrip的使用

nvtrisrip是NVIDIA提供的一個開源優化庫，這個庫可以將三角形頂點索引數組轉換為三角形帶索引數組。可以極大的提高渲染速度。

NVIDIA這個庫的官方地址是：
http://www.nvidia.com/object/nvtristrip_library.html

不過這里代碼不全也不夠新，推薦從GitHub上下載：
https://github.com/turbulenz/NvTriStrip

下載完畢后，我們把下面文件夾中的源代碼加入到項目中：
/NvTriStrip/include
/NvTriStrip/src

一共為6個文件 

需要注意的是VertexCache類有個非常奇怪的設計，在.h和.cpp中同時有兩套實現代碼。這會導致重定義，我們可以把.h中的代碼注釋起來。另外還需要修改entries變量為unsign short類型。 

#ifndef VERTEX_CACHE_H
 
#define VERTEX_CACHE_H
 
#include <string.h>
 
class VertexCache
{
     
public:
     
    VertexCache(int size);
//  {
//      numEntries = size;
//     
//      entries = new int[numEntries];
//     
//      for(int i = 0; i < numEntries; i++)
//          entries[i] = -1;
//  }
         
    VertexCache();// { VertexCache(16); }
    ~VertexCache();// { delete[] entries; entries = 0; }
     
    bool InCache(int entry);
//  {
//      bool returnVal = false;
//      for(int i = 0; i < numEntries; i++)
//      {
//          if(entries[i] == entry)
//          {
//              returnVal = true;
//              break;
//          }
//      }
//     
//      return returnVal;
//  }
     
    int AddEntry(int entry);
//  {
//      int removed;
//     
//      removed = entries[numEntries - 1];
//     
//      //push everything right one
//      for(int i = numEntries - 2; i >= 0; i--)
//      {
//          entries[i + 1] = entries[i];
//      }
//     
//      entries[0] = entry;
//     
//      return removed;
//  }
 
    void Clear();
//  {
//      memset(entries, -1, sizeof(int) * numEntries);
//  }
     
    void Copy(VertexCache* inVcache) ;
//  {
//      for(int i = 0; i < numEntries; i++)
//      {
//          inVcache->Set(i, entries[i]);
//      }
//  }
 
    int At(int index);// { return entries[index]; }
    void Set(int index, int value);// { entries[index] = value; }
 
private:
 
//  int *entries;
  //此處修改為unsigned short
  unsigned short *entries;
  int numEntries;
 
};
 
#endif

我們看一下在SIO2中的使用，其他引擎中的用法，大同小異

void ObjMod::optimize_mesh(unsigned int mesh_index, unsigned int vertex_cache_size) {
    ObjMesh *objmesh = &this->objmesh[ mesh_index ];
      
    unsigned int i = 0,
    s = 0;
      
    unsigned short n_group = 0;
      
    //設置頂點緩存大小，頂點緩存越大，優化時間越長，優化效果越好，但是成邊界遞減關系
    if( vertex_cache_size )
        SetCacheSize( vertex_cache_size );
      
    while( i != objmesh->n_objtrianglelist )
    {
        PrimitiveGroup *primitivegroup;
          
        //通過三角形索引創建
        //四個參數依次：被優化的三角形索引數組，三角形索引元素數量，優化后的三角形帶數組，優化后的三角形帶元素個數
        if( GenerateStrips( objmesh->objtrianglelist[ i ].indice_array,
                           objmesh->objtrianglelist[ i ].n_indice_array,
                           &primitivegroup,
                           &n_group,
                           true ) )
        {
            if( primitivegroup[ 0 ].numIndices < objmesh->objtrianglelist[ i ].n_indice_array )
            {
                objmesh->objtrianglelist[ i ].mode = GL_TRIANGLE_STRIP;//渲染模式修改為三角形帶
                objmesh->objtrianglelist[ i ].n_indice_array = primitivegroup[ 0 ].numIndices;//重置數據數量
                  
                //重新申請內存//
                s = primitivegroup[ 0 ].numIndices * sizeof( unsigned short );
                  
                //這塊使用realloc有點浪費空間，因為優化后的三角形帶占用內存比原先的三角形索引要小
                objmesh->objtrianglelist[ i ].indice_array = ( unsigned short * ) realloc( objmesh->objtrianglelist[ i ].indice_array,
                                                                                          s );
                //復制數據
                memcpy( &objmesh->objtrianglelist[ i ].indice_array[ 0 ],
                       &primitivegroup[ 0 ].indices[ 0 ],
                       s );
            }
              
            //刪除優化后的臨時數據
            delete[] primitivegroup;
        }
          
        ++i;
    }
}

我們這里調用庫的函數有兩個：
SetCacheSize為設置優化庫使用的緩存大小并非越大越好。而是根據模型精細度來考量的。
GenerateStrips就是核心的三角形優化算法了。

然后保存輸出的數據刪掉臨時數據即可。

下面是一個測試報告，畫面數為4726個三角形的靜態模型。重復繪制模型200次，在iPad mini2上面的結果是：

未開三角形帶優化時的FPS： 

開啟三角形帶優化之后的FPS：

FPS提高了70%，效果還是非常明顯的。


在這里為了方便，我們使用的是在線優化方式（模型數據加載進內存后再優化）。而實際開發中，往往多使用離線優化，預先處理好模型數據，然后直接調用渲染就可以了，這樣沒有緩存和時間限制，效果更好。

這個庫是平臺無關，也沒有第三方依賴，可以很方便的集成到自己的工具中去。