NeL: NL3D::CStripifier class Reference

+reorganize triangles to get efficiency of GPU vertex-cache. Default vertex cache is 10. out get the same list of triangles, but in different order. any list of lines / quads in out are not modified. NB: &in == &out is possible. +
00197 {
+00198         vector<COrderFace>      inFaces;
+00199         sint                    i;
+00200         sint                    numTris= in.getNumTri();
+00201 
+00202         // TestYoyo: All the same tri => perfect vertex caching...
+00203         /*out.setNumTri(numTris);
+00204         for(i=0;i< numTris; i++)
+00205         {
+00206                 uint32  v0= *(in.getTriPointer()+0);
+00207                 uint32  v1= *(in.getTriPointer()+1);
+00208                 uint32  v2= *(in.getTriPointer()+2);
+00209                 out.setTri(i, v0, v1, v2);
+00210         }
+00211         return;*/
+00212 
+00213 
+00214         // prepare inIndices.
+00215         //--------------------
+00216         inFaces.resize(numTris);
+00217         for(i=0;i< numTris; i++)
+00218         {
+00219                 inFaces[i].v[0]= in.getTriPointer()[i*3 + 0];
+00220                 inFaces[i].v[1]= in.getTriPointer()[i*3 + 1];
+00221                 inFaces[i].v[2]= in.getTriPointer()[i*3 + 2];
+00222                 inFaces[i].Inserted= false;
+00223         }
+00224 
+00225 
+00226         // build our cache, and compute max number of vertices.
+00227         //--------------------
+00228         int     numVerts=0;
+00229         for (i = 0; i < numTris; i++)
+00230         {
+00231                 numVerts= max(numVerts, (int)inFaces[i].v[0]);
+00232                 numVerts= max(numVerts, (int)inFaces[i].v[1]);
+00233                 numVerts= max(numVerts, (int)inFaces[i].v[2]);
+00234         }
+00235         numVerts++;
+00236         CVertexCache    vertexCache(cacheSize, numVerts);
+00237 
+00238 
+00239         // Compute vertex connectivity.
+00240         //--------------------
+00241         vector<CCornerNode*>    vertexConnectivity;
+00242         vector<CCornerNode>             cornerAllocator;
+00243         cornerAllocator.resize(numTris * 3);
+00244         vertexConnectivity.resize(numVerts, NULL);
+00245         // For all triangles.
+00246         for (i = 0; i < numTris; i++)
+00247         {
+00248                 COrderFace      *ordFace= &inFaces[i];
+00249                 // For each corner, allocate and fill
+00250                 for(sint j=0; j<3;j++)
+00251                 {
+00252                         sint    vertexId= ordFace->v[j];
+00253 
+00254                         // allocate a corner
+00255                         CCornerNode             *corner= &cornerAllocator[i*3 + j];
+00256 
+00257                         // fill it.
+00258                         corner->FaceId= i;
+00259                         corner->VertexId= vertexId;
+00260                         // Link it to the vertex list of faces.
+00261                         corner->Next= vertexConnectivity[vertexId];
+00262                         vertexConnectivity[vertexId]= corner;
+00263                 }
+00264         }
+00265 
+00266 
+00267         // build output optimized triangles
+00268         //--------------------
+00269         out.setNumTri(0);
+00270         out.reserveTri(numTris);
+00271 
+00272         for(i=0; i<numTris; i++)
+00273         {
+00274                 // force insertion of the ith face.
+00275                 sint    nextToInsert= i;
+00276                 bool    nextToInsertFound= true;
+00277                 while( nextToInsertFound )
+00278                 {
+00279                         nextToInsertFound= false;
+00280 
+00281                         // if the face is not yet inserted.
+00282                         if(!inFaces[nextToInsert].Inserted)
+00283                         {
+00284                                 // must insert this face.
+00285                                 inFaces[nextToInsert].insertInPB(out, vertexCache);
+00286 
+00287                                 sint    minC= 3;
+00288 
+00289                                 // look only for faces which use vertices in VertexCache, to get a face with at least one vertex.
+00290                                 for(uint j=0; j<cacheSize; j++)
+00291                                 {
+00292                                         // get a vertex from the vertex cache.
+00293                                         uint    vertexId= vertexCache.getVertexInCache(j);
+00294                                         // if empty entry
+00295                                         if(vertexId==0xFFFFFFFF)
+00296                                                 continue;
+00297 
+00298                                         // parse list of faces which use this vertex.
+00299                                         CCornerNode             *corner= vertexConnectivity[vertexId];
+00300                                         while(corner)
+00301                                         {
+00302                                                 uint    faceId= corner->FaceId;
+00303 
+00304                                                 // if the face is not yet inserted.
+00305                                                 if(!inFaces[faceId].Inserted)
+00306                                                 {
+00307                                                         sint    c= inFaces[faceId].countCacheMiss(vertexCache);
+00308                                                         // insert first any face which don't add any vertex in the cache.
+00309                                                         if(c==0)
+00310                                                         {
+00311                                                                 inFaces[faceId].insertInPB(out, vertexCache);
+00312                                                         }
+00313                                                         // else the one which add the minimum of vertex possible: nextToInsert
+00314                                                         else
+00315                                                         {
+00316                                                                 // Add cost of faces that use vertices pushed out (better results...)
+00317                                                                 uint    numVOut= c;
+00318                                                                 uint    k;
+00319                                                                 for(k=cacheSize-numVOut; k<cacheSize; k++)
+00320                                                                 {
+00321                                                                         uint    vertexOutId= vertexCache.getVertexInCache(k);
+00322                                                                         if(vertexOutId==0xFFFFFFFF)
+00323                                                                                 continue;
+00324                                                                         // TempRemove the vertex from the cache
+00325                                                                         vertexCache.tempTouchVertex(vertexOutId, false);
+00326                                                                 }
+00327                                                                 // parse all faces that still use those out vertices.
+00328                                                                 for(k=cacheSize-numVOut; k<cacheSize; k++)
+00329                                                                 {
+00330                                                                         uint    vertexOutId= vertexCache.getVertexInCache(k);
+00331                                                                         if(vertexOutId==0xFFFFFFFF)
+00332                                                                                 continue;
+00333                                                                         CCornerNode             *cornerOut= vertexConnectivity[vertexOutId];
+00334                                                                         while(cornerOut)
+00335                                                                         {
+00336                                                                                 uint    faceOutId= cornerOut->FaceId;
+00337 
+00338                                                                                 // if the face is not yet inserted AND not the one treated
+00339                                                                                 if(!inFaces[faceOutId].Inserted && faceOutId!=faceId)
+00340                                                                                 {
+00341                                                                                         // Add cache miss of this face
+00342                                                                                         c+= inFaces[faceOutId].countCacheMiss(vertexCache);
+00343                                                                                 }
+00344 
+00345                                                                                 // next corner
+00346                                                                                 cornerOut= cornerOut->Next;
+00347                                                                         }
+00348                                                                 }
+00349                                                                 // reset touch
+00350                                                                 for(k=cacheSize-numVOut; k<cacheSize; k++)
+00351                                                                 {
+00352                                                                         uint    vertexOutId= vertexCache.getVertexInCache(k);
+00353                                                                         if(vertexOutId==0xFFFFFFFF)
+00354                                                                                 continue;
+00355                                                                         // restore TempTouch the vertex from the cache
+00356                                                                         vertexCache.tempTouchVertex(vertexOutId, true);
+00357                                                                 }
+00358 
+00359 
+00360                                                                 // take the minimum cost
+00361                                                                 if(c<minC)
+00362                                                                 {
+00363                                                                         nextToInsert= faceId;
+00364                                                                         nextToInsertFound= true;
+00365                                                                         minC= c;
+00366                                                                 }
+00367                                                         }
+00368                                                 }
+00369 
+00370                                                 // next corner
+00371                                                 corner= corner->Next;
+00372                                         }
+00373 
+00374                                 }
+00375 
+00376                                 // if nextToInsertFound, then nextToInsert has the face which add the minimum of vertex possible in the cache
+00377                         }
+00378                 }
+00379 
+00380         }
+00381 
+00382 }
+

Public Member Functions
	CStripifier ()
	Constructor.
void	optimizeTriangles (const CPrimitiveBlock &in, CPrimitiveBlock &out, uint cacheSize=10)
NL3D::CStripifier Class Reference

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation
