Original Post
Hi everyone, Since some days, I'm trying to implement an easy vertex cache algorithm, in order to load a model in an ASE format (non-optimized), optimized it, and then save it into a new file. I'm implemeting that algorithm : http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html, which seems good, judging by the results. But the problem is that I've implemented it, but the optimized version is slower than the non-optimized version (my graphics card is a Radeon 9800 Pro, so I think it's have a cache). But maybe my implementation is not good, for those who have implemented this algorithm, please say me why :(. First, it is a pseudo-code of what I have understand by reading the article : Now when I execute the algorithm. It's not optimized, but it should work :/ : verts is the array from the ase file, like faces, so it's the unoptimized faces orders : I think the code is quite clear given the pseudo code... I don't know what it doesn't work. Some things are really strange, because whatever the maxCacheSize is (8, 32, 1024...) the order is the same, but on the paper given above, the lists seems to be different (because he gets different results...). Maybe there is an error either from my implementation, or the understanding of the algorithm... I contacted the author but he didn't answer me... So if you could help me, thanks for your help ;)
Quote:Now, here is the code. I assume that I have already an array of the vertices, and another of the indices, loaded from the ASE file. The two classes, one for the vertices, and another for the triangles... The code is from the algorithm :
Initialisation (just one time) : numberOfTrianglesThatUseThisVertex = 0 // The name is simple posInCache = -1 // The position in the modelled cache For each triangle of the mesh : We increment numberOfTrianglesThatUseThisVertex for the three vertices of the triangle For each vertex, we calculate its score For each triangle, we calculate its score (the sum of its three vertices' scores) Body of the algorithm : modelledCache [32] // Array of 32 vertices While there are triangles to draw : We add the triangle with the higher score to another array, and delete it from the original array For each of its vertices : We decrement numberOfTrianglesThatUseThisVertex Each vertex is shift 3 If the vertex is not in the cache We add it at the top Else We erase it from the cache, and add it in the top of the cache For each vertex, we calculate its new score For each triangle, we calculate its new score
const float FindVertexScore_CacheDecayPower = 1.5f;
const float FindVertexScore_LastTriScore = 0.75f;
const float FindVertexScore_ValenceBoostScale = 2.0f;
const float FindVertexScore_ValenceBoostPower = 0.5f;
const std::size_t MaxSizeVertexCache = 32;
struct Vert
{
int positionInCache; // La position dans le cache modèle
float score; // Le score de la vertice
std::size_t numTrianglesThatUseIt; // Nombre de triangles qui l'utilisent
std::vector<std::size_t> trianglesIndices; // Indices des triangles
bool operator== (const Vert & vert)
{
if (positionInCache == vert.positionInCache &&
score == vert.score && numTrianglesThatUseIt == vert.numTrianglesThatUseIt && trianglesIndices == vert.trianglesIndices)
return true;
return false;
}
void ComputeScore ()
{
score = 0.0f;
if (numTrianglesThatUseIt == 0)
{
score = -1.0f;
return;
}
if (positionInCache < 0)
{
// Vertex is not in FIFO cache - no score.
}
else
{
if (positionInCache < 3)
{
// This vertex was used in the last triangle,
// so it has a fixed score, whichever of the three
// it's in. Otherwise, you can get very different
// answers depending on whether you add
// the triangle 1,2,3 or 3,1,2 - which is silly.
score = FindVertexScore_LastTriScore;
}
else
{
assert (positionInCache < MaxSizeVertexCache);
// Points for being high in the cache.
const float Scaler = 1.0f / (MaxSizeVertexCache);
score = 1.0f - (positionInCache) * Scaler;
score = std::powf (score, FindVertexScore_CacheDecayPower);
}
}
// Bonus points for having a low number of tris still to
// use the vert, so we get rid of lone verts quickly.
float ValenceBoost = std::powf (numTrianglesThatUseIt,
-FindVertexScore_ValenceBoostPower);
score += FindVertexScore_ValenceBoostScale * ValenceBoost;
}
};
struct Tri
{
bool isAdded; // Est-il ajouté ?
float score; // Le score du triangle
std::size_t indices[3]; // Indices des vertices
bool operator< (const Tri & anotherTri)
{
return score < anotherTri.score;
}
};
std::vector<Vert> vertTab;
vertTab.reserve (verts.size());
std::vector<Tri> triTab;
triTab.reserve (faces.size());
// We add as many numbers of vertices as the unoptimized version
for (std::size_t i = 0 ; i != verts.size() ; ++i)
{
Vert oneVert;
oneVert.positionInCache = -1;
oneVert.numActiveTriangles = oneVert.numTrianglesThatUseIt = 0;
vertTab.push_back (oneVert);
}
// Don't know what the algorithm needs that...
for (std::size_t i = 0 ; i != faces.size() ; ++i)
{
Tri oneTri;
oneTri.isAdded = false;
oneTri.indices[0] = faces.at(i).indexVertices[0];
oneTri.indices[1] = faces.at(i).indexVertices[1];
oneTri.indices[2] = faces.at(i).indexVertices[2];
triTab.push_back (oneTri);
}
// Calculate le number of triangles that use each vertex
for (std::size_t i = 0 ; i != triTab.size() ; ++i)
{
++vertTab[triTab.indices[0]].numActiveTriangles;
++vertTab[triTab.indices[0]].numTrianglesThatUseIt;
vertTab[triTab.indices[0]].trianglesIndices.push_back (i);
++vertTab[triTab.indices[1]].numActiveTriangles;
++vertTab[triTab.indices[1]].numTrianglesThatUseIt;
vertTab[triTab.indices[1]].trianglesIndices.push_back (i);
++vertTab[triTab.indices[2]].numActiveTriangles;
++vertTab[triTab.indices[2]].numTrianglesThatUseIt;
vertTab[triTab.indices[2]].trianglesIndices.push_back (i);
}
// Compute the score for eahc vertex
std::for_each (vertTab.begin(), vertTab.end(), std::mem_fun_ref (‖::ComputeScore));
// And for each triangle
for (std::size_t i = 0 ; i != triTab.size() ; ++i)
{
triTab.score = vertTab[triTab.indices[0]].score +
vertTab[triTab.indices[1]].score +
vertTab[triTab.indices[2]].score;
}
// newTriTab is the new array (the drawing list)... So it must be the optimized order of faces...
std::vector <Tri> newTriTab;
newTriTab.reserve (triTab.size());
const std::size_t NumVertexInCache = 32;
Vert modelledCache [NumVertexInCache];
Vert onevert;
const std::size_t triTabsize = triTab.size();
// Debug purpose
for (std::size_t i = 0 ; i != 20 ; ++i)
{
std::cout << triTab.indices[0] << ' ' <<
triTab.indices[1] << ' ' <<
triTab.indices[2] << std::endl;
}
// While all the triangles of the old list are not added to the new
while (newTriTab.size() != triTabsize)
{
// Looking for the higher scoring triangle
std::vector<Tri>::iterator it = std::max_element (triTab.begin(), triTab.end());
Tri higherScoreTri (*it);
// Copy it into the new array and erase it from the old
newTriTab.push_back (higherScoreTri);
triTab.erase (it);
// We decremente the number of triangles that use the three vertices
for (std::size_t i = 0 ; i != 3 ; ++i)
--(vertTab [higherScoreTri.indices].numTrianglesThatUseIt);
// On décale chaque vertice dans le cache
for (std::size_t i = NumVertexInCache - 1 ; i > 2 ; --i)
{
modelledCache = modelledCache[i - 3];
modelledCache.positionInCache = i;
}
for (std::size_t i = NumVertexInCache - 1 ; i > 2 ; --i)
{
if ((modelledCache == vertTab [higherScoreTri.indices[0]]) ||
(modelledCache == vertTab [higherScoreTri.indices[1]]) ||
(modelledCache == vertTab [higherScoreTri.indices[2]]))
modelledCache = onevert;
}
for (std::size_t i = 0 ; i != 3 ; ++i)
{
//if (std::find (modelledCache, modelledCache + NumVertexInCache,
// vertTab [higherScoreTri.indices]))
modelledCache = vertTab [higherScoreTri.indices];
vertTab [higherScoreTri.indices].positionInCache = i;
}
std::for_each (vertTab.begin(), vertTab.end(), std::mem_fun_ref (‖::ComputeScore));
for (std::size_t i = 0 ; i != triTab.size() ; ++i)
{
triTab.score = vertTab[triTab.indices[0]].score +
vertTab[triTab.indices[1]].score +
vertTab[triTab.indices[2]].score;
}
}
