BVB Source Codes

CRYENGINE Show ForsythFaceReorderer.cpp Source code

Return Download CRYENGINE: download ForsythFaceReorderer.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #include "StdAfx.h"
  4.  
  5. #if CRY_PLATFORM_WINDOWS
  6.  
  7.         #include "ForsythFaceReorderer.h"
  8.  
  9.         #include <cmath>    // powf()
  10.  
  11. ForsythFaceReorderer::ForsythFaceReorderer()
  12.         : m_cacheSize(0)
  13.         , m_cacheUsedSize(0)
  14. {
  15.         ZeroArray(m_cache);
  16.         ZeroArray(m_scoreTable_valency);
  17.         ZeroArray(m_scoreTable_cachePosition);
  18.  
  19.         computeValencyScoreTable();
  20. }
  21.  
  22. bool ForsythFaceReorderer::reorderFaces(
  23.   const size_t cacheSize,
  24.   const uint verticesPerFace,
  25.   const size_t indexCount,
  26.   const uint32* const inVertexIndices,
  27.   uint32* const outVertexIndices,
  28.   uint32* const outFaceToOldFace)
  29. {
  30.         clear();
  31.  
  32.         if (verticesPerFace < sk_minVerticesPerFace || verticesPerFace > sk_maxVerticesPerFace)
  33.         {
  34.                 return false;
  35.         }
  36.         if (indexCount <= 0)
  37.         {
  38.                 return true;
  39.         }
  40.         if (indexCount % verticesPerFace != 0)
  41.         {
  42.                 return false;
  43.         }
  44.         if (inVertexIndices == 0)
  45.         {
  46.                 return false;
  47.         }
  48.         if (outVertexIndices == 0)
  49.         {
  50.                 return false;
  51.         }
  52.  
  53.         if ((cacheSize < verticesPerFace) || (cacheSize > sk_maxCacheSize))
  54.         {
  55.                 return false;
  56.         }
  57.  
  58.         m_cacheSize = (int)cacheSize;
  59.         m_cacheUsedSize = 0;
  60.         computeCacheScoreTable(verticesPerFace);
  61.  
  62.         const uint32 faceCount = indexCount / verticesPerFace;
  63.         if (indexCount / verticesPerFace >= (uint32) - 1)
  64.         {
  65.                 // Face count is too high
  66.                 return false;
  67.         }
  68.  
  69.         size_t writtenFaceCount = 0;
  70.  
  71.         uint32 vertexCount;
  72.         {
  73.                 // TODO: use minVertexIndex also. It will allow to use less memory for ranged indices.
  74.                 // For example indices in ranges [800;899] will use memory size 100, not 900.
  75.                 uint32 maxVertexIndex = 0;
  76.                 for (size_t i = 0; i < indexCount; ++i)
  77.                 {
  78.                         if (inVertexIndices[i] > maxVertexIndex)
  79.                         {
  80.                                 maxVertexIndex = inVertexIndices[i];
  81.                         }
  82.                 }
  83.                 if (((size_t)maxVertexIndex) + 1 >= (uint32) - 1)
  84.                 {
  85.                         // Vertex count is too high
  86.                         return false;
  87.                 }
  88.                 vertexCount = maxVertexIndex + 1;
  89.         }
  90.  
  91.         // Allocate and initialize arrays
  92.         {
  93.                 {
  94.                         Vertex initVertex;
  95.                         initVertex.m_pFaceList = 0;
  96.                         initVertex.m_aliveFaceCount = 0;
  97.                         initVertex.m_posInCache = -1;
  98.                         initVertex.m_score = 0;
  99.                         m_vertices.resize(vertexCount, initVertex);
  100.                 }
  101.  
  102.                 m_deadFacesBitArray.resize((faceCount + 7) / 8, 0);
  103.  
  104.                 m_faceScores.resize(faceCount, 0);
  105.  
  106.                 m_vertexFaceLists.resize(faceCount * verticesPerFace);
  107.         }
  108.  
  109.         // Fill per-vertex face lists
  110.         {
  111.                 for (size_t i = 0; i < indexCount; ++i)
  112.                 {
  113.                         const uint32 vertexIndex = inVertexIndices[i];
  114.                         if (m_vertices[vertexIndex].m_aliveFaceCount >= sk_maxValency)
  115.                         {
  116.                                 // Vertex valency is too high
  117.                                 return false;
  118.                         }
  119.                         ++m_vertices[vertexIndex].m_aliveFaceCount;
  120.                 }
  121.  
  122.                 uint32 pos = 0;
  123.                 for (uint32 vi = 0; vi < vertexCount; ++vi)
  124.                 {
  125.                         Vertex& v = m_vertices[vi];
  126.                         v.m_pFaceList = &m_vertexFaceLists[pos];
  127.                         pos += v.m_aliveFaceCount;
  128.                         v.m_aliveFaceCount = 0;
  129.                 }
  130.                 assert(pos == faceCount * verticesPerFace);
  131.  
  132.                 const uint32* pVertexIndex = &inVertexIndices[0];
  133.                 for (uint32 fi = 0; fi < faceCount; ++fi, pVertexIndex += verticesPerFace)
  134.                 {
  135.                         for (uint j = 0; j < verticesPerFace; ++j)
  136.                         {
  137.                                 Vertex& v = m_vertices[pVertexIndex[j]];
  138.                                 v.m_pFaceList[v.m_aliveFaceCount++] = fi;
  139.                         }
  140.                 }
  141.         }
  142.  
  143.         // Compute vertex and face scores
  144.         {
  145.                 for (uint32 vi = 0; vi < vertexCount; ++vi)
  146.                 {
  147.                         computeVertexScore(m_vertices[vi]);
  148.                 }
  149.  
  150.                 const uint32* pVertexIndex = &inVertexIndices[0];
  151.                 for (uint32 fi = 0; fi < faceCount; ++fi, pVertexIndex += verticesPerFace)
  152.                 {
  153.                         m_faceScores[fi] = 0;
  154.                         for (uint j = 0; j < verticesPerFace; ++j)
  155.                         {
  156.                                 const Vertex& v = m_vertices[pVertexIndex[j]];
  157.                                 m_faceScores[fi] += v.m_score;
  158.                         }
  159.                 }
  160.         }
  161.  
  162.         // Add faces with highest scores to the output buffer, one by one.
  163.         uint32 faceSearchCursor = 0;
  164.         uint32 bestFaceToAdd;
  165.         for (;; )
  166.         {
  167.                 // Find face with highest score
  168.                 {
  169.                         bestFaceToAdd = (uint32) - 1;
  170.                         float highestScore = -1;
  171.                         for (int i = 0; i < m_cacheUsedSize; ++i)
  172.                         {
  173.                                 const Vertex& v = m_vertices[m_cache[i]];
  174.                                 const uint32* const pFaces = v.m_pFaceList;
  175.                                 for (valency_type j = 0; j < v.m_aliveFaceCount; ++j)
  176.                                 {
  177.                                         const uint32 faceIndex = pFaces[j];
  178.                                         if (highestScore < m_faceScores[faceIndex])
  179.                                         {
  180.                                                 highestScore = m_faceScores[faceIndex];
  181.                                                 bestFaceToAdd = faceIndex;
  182.                                         }
  183.                                 }
  184.                         }
  185.  
  186.                         if (bestFaceToAdd == (uint32) - 1)
  187.                         {
  188.                                 bestFaceToAdd = findBestFaceToAdd(faceSearchCursor);
  189.                                 assert(bestFaceToAdd != (uint32) - 1);
  190.                         }
  191.                 }
  192.  
  193.                 // Add the best face to the output buffer
  194.                 {
  195.                         size_t writtenIndexCount = writtenFaceCount * verticesPerFace;
  196.                         for (uint j = 0; j < verticesPerFace; ++j)
  197.                         {
  198.                                 outVertexIndices[writtenIndexCount + j] = inVertexIndices[(size_t)bestFaceToAdd * verticesPerFace + j];
  199.                         }
  200.                         if (outFaceToOldFace)
  201.                         {
  202.                                 outFaceToOldFace[writtenFaceCount] = bestFaceToAdd;
  203.                         }
  204.                         if (++writtenFaceCount == faceCount)
  205.                         {
  206.                                 // We're done.
  207.                                 return true;
  208.                         }
  209.                 }
  210.  
  211.                 // Make changes to the cache, vertex & cache scores, vertex face lists
  212.                 {
  213.                         m_deadFacesBitArray[bestFaceToAdd >> 3] |= 1 << (bestFaceToAdd & 7);
  214.  
  215.                         for (int j = verticesPerFace - 1; j >= 0; --j)
  216.                         {
  217.                                 const uint32 vertexIndex = inVertexIndices[(size_t)bestFaceToAdd * verticesPerFace + j];
  218.                                 moveVertexToCacheTop(vertexIndex);
  219.                                 removeFaceFromVertex(vertexIndex, bestFaceToAdd);
  220.                         }
  221.  
  222.                         for (int i = 0; i < m_cacheUsedSize; ++i)
  223.                         {
  224.                                 Vertex& v = m_vertices[m_cache[i]];
  225.                                 if (i >= m_cacheSize)
  226.                                 {
  227.                                         v.m_posInCache = -1;
  228.                                 }
  229.                                 const float oldScore = v.m_score;
  230.                                 computeVertexScore(v);
  231.                                 const float differenceScore = v.m_score - oldScore;
  232.                                 const uint32* const pFaces = v.m_pFaceList;
  233.                                 for (valency_type j = 0; j < v.m_aliveFaceCount; ++j)
  234.                                 {
  235.                                         m_faceScores[pFaces[j]] += differenceScore;
  236.                                 }
  237.                         }
  238.                         if (m_cacheUsedSize > m_cacheSize)
  239.                         {
  240.                                 m_cacheUsedSize = m_cacheSize;
  241.                         }
  242.                 }
  243.         }
  244. }
  245.  
  246. void ForsythFaceReorderer::clear()
  247. {
  248.         m_vertices.clear();
  249.         m_deadFacesBitArray.clear();
  250.         m_faceScores.clear();
  251.         m_vertexFaceLists.clear();
  252. }
  253.  
  254. void ForsythFaceReorderer::computeCacheScoreTable(const int verticesPerFace)
  255. {
  256.         static const float lastFaceScore = 0.75f;
  257.         static const float cacheDecayPower = 1.5f;
  258.  
  259.         // Vertices of last added face should have *same* fixed score,
  260.         // because otherwise results will depend on the order of vertices
  261.         // in face (5,6,7 and 7,5,6 will produce different results).
  262.         for (int j = 0; j < verticesPerFace; ++j)
  263.         {
  264.                 m_scoreTable_cachePosition[j] = lastFaceScore;
  265.         }
  266.  
  267.         for (int i = verticesPerFace; i < m_cacheSize; ++i)
  268.         {
  269.                 const float x = 1.0f - ((i - verticesPerFace) / (m_cacheSize - verticesPerFace));
  270.                 m_scoreTable_cachePosition[i] = powf(x, cacheDecayPower);
  271.         }
  272. }
  273.  
  274. void ForsythFaceReorderer::computeValencyScoreTable()
  275. {
  276.         // Lower number of alive faces in the vertex produces higher score.
  277.         // It allows to  get rid of lone vertices quickly.
  278.  
  279.         static const float valencyPower = -0.5f;
  280.         static const float valencyScale = 2.0f;
  281.  
  282.         m_scoreTable_valency[0] = 0;
  283.         for (valency_type i = 1; i < sk_valencyTableSize; ++i)
  284.         {
  285.                 m_scoreTable_valency[i] = valencyScale * powf(i, valencyPower);
  286.         }
  287. }
  288.  
  289. void ForsythFaceReorderer::computeVertexScore(ForsythFaceReorderer::Vertex& v)
  290. {
  291.         if (v.m_aliveFaceCount > 0)
  292.         {
  293.                 assert(v.m_posInCache < m_cacheSize);
  294.                 const float valencyScore = (v.m_aliveFaceCount < sk_valencyTableSize) ? m_scoreTable_valency[v.m_aliveFaceCount] : 0;
  295.                 // Preventing "SCA: warning C6385: Invalid data: accessing 'm_scoreTable_cachePosition', the readable size is '200' bytes, but '484' bytes might be read"
  296.                 PREFAST_SUPPRESS_WARNING(6385) const float cacheScore = (v.m_posInCache >= 0) ? m_scoreTable_cachePosition[v.m_posInCache] : 0;
  297.                 v.m_score = valencyScore + cacheScore;
  298.         }
  299. }
  300.  
  301. void ForsythFaceReorderer::moveVertexToCacheTop(const uint32 vertexIndex)
  302. {
  303.         const int oldPosInCache = m_vertices[vertexIndex].m_posInCache;
  304.         for (int dst = (oldPosInCache >= 0) ? oldPosInCache : m_cacheUsedSize; dst > 0; --dst)
  305.         {
  306.                 const uint32 v = m_cache[dst - 1];
  307.                 m_cache[dst] = v;
  308.                 ++m_vertices[v].m_posInCache;
  309.         }
  310.         m_cache[0] = vertexIndex;
  311.         m_vertices[vertexIndex].m_posInCache = 0;
  312.         if (oldPosInCache < 0)
  313.         {
  314.                 ++m_cacheUsedSize;
  315.         }
  316. }
  317.  
  318. void ForsythFaceReorderer::removeFaceFromVertex(const uint32 vertexIndex, const uint32 faceIndex)
  319. {
  320.         Vertex& v = m_vertices[vertexIndex];
  321.         assert(v.m_aliveFaceCount > 0);
  322.         uint32* const pFaces = v.m_pFaceList;
  323.         for (int j = 0;; ++j)
  324.         {
  325.                 if (pFaces[j] == faceIndex)
  326.                 {
  327.                         pFaces[j] = pFaces[--v.m_aliveFaceCount];
  328.                         return;
  329.                 }
  330.         }
  331. }
  332.  
  333. uint32 ForsythFaceReorderer::findBestFaceToAdd(uint32& faceSearchCursor) const
  334. {
  335.         assert(!m_faceScores.empty());
  336.         assert(faceSearchCursor < m_faceScores.size());
  337.         while (m_deadFacesBitArray[faceSearchCursor >> 3] & (1 << (faceSearchCursor & 7)))
  338.         {
  339.                 ++faceSearchCursor;
  340.         }
  341.         return faceSearchCursor++;
  342. }
  343.  
  344. #endif
  345.  
  346. // eof
  347.  
downloadForsythFaceReorderer.cpp Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top