home *** CD-ROM | disk | FTP | other *** search
/ Xentax forum attachments archive / xentax.7z / 8090 / ModelEdit.7z / PieceLODGen.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2006-03-08  |  13.0 KB  |  496 lines
  1. #include "precompile.h"
  2. #include "model.h"
  3. #include "model_cleanup.h"
  4. #include "PieceLODGen.h"
  5.  
  6.  
  7. // generate the LOD from the source LOD
  8. bool CBuildPieceLOD::BuildLOD()
  9. {
  10.     // can't generate LODs for vertex animated pieces
  11.     if( m_ModelPiece->m_isVA )
  12.         return false;
  13.  
  14.     // remove any unused vertices
  15. //    gn_RemoveUnusedVertices( m_Model );
  16.  
  17.     // initialize internal structures
  18.     SetupGenLODModel();
  19.  
  20.     m_Collapses.SetCacheSize( 10000 );
  21.  
  22.     unsigned numStartTris = m_PieceLOD->m_Tris;
  23.     unsigned numCollapses = 0;
  24.  
  25.     // generate edge collapses
  26.     while( 1 )
  27.     {
  28.         EdgeCollapse edgeCollapse;
  29.  
  30.         // find the best edge collapse candidate
  31.         if( !FindShortestEdge( edgeCollapse ) )
  32.             break;
  33.  
  34.         numCollapses++;
  35.  
  36.         // update structures using this edge collapse
  37.         ProcessEdgeCollapse( edgeCollapse );
  38.         m_Collapses.Append( edgeCollapse );
  39.  
  40.         // check to see if we should stop collapsing edges
  41.         if( (numStartTris - (numCollapses * 2)) <= (numStartTris * m_Percent / 100.0f) )
  42.             break;
  43.     }
  44.  
  45.     // add this LOD to the model
  46.     if( (m_Collapses.GetSize() <= 0) || !AddLOD() )
  47.         return false;
  48.  
  49.     return true;
  50. }
  51.  
  52.  
  53. // initialize internal structures
  54. void CBuildPieceLOD::SetupGenLODModel( void )
  55. {
  56.     m_TriActive.SetSize( m_PieceLOD->m_Tris.GetSize() );
  57.     m_Tris.SetSize( m_PieceLOD->m_Tris.GetSize() );
  58.     for( uint32 i = 0; i < m_PieceLOD->m_Tris; i++ )
  59.     {
  60.         m_TriActive[i] = true;
  61.         m_Tris[i] = m_PieceLOD->m_Tris[i];
  62.     }
  63.  
  64.     m_Verts.SetSize( m_PieceLOD->m_Verts.GetSize() );
  65.     for( i = 0; i < m_PieceLOD->m_Verts; i++ )
  66.     {
  67.         m_Verts[i] = m_PieceLOD->m_Verts[i];
  68.         m_Verts[i].m_iReplacement = (short)i;
  69.     }
  70. }
  71.  
  72.  
  73. // find the best edge collapse candidate
  74. bool CBuildPieceLOD::FindShortestEdge( EdgeCollapse& edgeCollapse )
  75. {
  76.     // check the number of remaining tris
  77.     uint32 numActiveTris = CalcNumActiveTris();
  78.     if( (numActiveTris < m_MinNumTris) || (numActiveTris <= 2) )
  79.         return false;
  80.  
  81.     unsigned curTri, curVert, triVert, triNextVert;
  82.     float testLen;
  83.     unsigned testTris[2];
  84.     float shortestEdge = FLT_MAX;
  85.     bool foundEdge = false;
  86.  
  87.     for( curTri = 0; curTri < m_Tris; curTri++ )
  88.     {
  89.         // skip already collapsed tris
  90.         if( !m_TriActive[curTri] )
  91.             continue;
  92.  
  93.         ModelTri* tri = &m_Tris[curTri];
  94.  
  95.         for( curVert = 0; curVert < 3; curVert++ )
  96.         {
  97.             // get the length of the candidate edge
  98.             triVert = tri->m_Indices[curVert];
  99.             triNextVert = tri->m_Indices[(curVert+1)%3];
  100.             testLen = (m_Verts[triVert].m_Vec - m_Verts[triNextVert].m_Vec).Mag();
  101.  
  102.             // check to see if we have a good collapse
  103.             if( (testLen < shortestEdge) && (testLen > 0.0f) && TestEdgeCollapse( triVert, triNextVert, testTris ) )
  104.             {
  105.                 // make sure it's not too long
  106.                 if( testLen >= m_MaxEdgeLen )
  107.                     continue;
  108.  
  109.                 // fill in the collapse info
  110.                 shortestEdge = testLen;
  111.                 edgeCollapse.m_Verts[0] = triVert;
  112.                 edgeCollapse.m_Verts[1] = triNextVert;
  113.                 edgeCollapse.m_Tris[0] = testTris[0];
  114.                 edgeCollapse.m_Tris[1] = testTris[1];
  115.                 foundEdge = true;
  116.             }
  117.         }
  118.     }
  119.  
  120.     return foundEdge;
  121. }
  122.  
  123.  
  124. // count the number of uncollapsed triangles
  125. unsigned CBuildPieceLOD::CalcNumActiveTris( void )
  126. {
  127.     unsigned count = 0;
  128.  
  129.     for( unsigned i = 0; i < m_TriActive; i++ )
  130.     {
  131.         if( m_TriActive[i] )
  132.             count++;
  133.     }
  134.  
  135.     return count;
  136. }
  137.  
  138.  
  139. // returns true if 2 and only 2 triangles share the edge
  140. // fills in tris with the tris that share the edge
  141. bool CBuildPieceLOD::TestEdgeCollapse( unsigned vert0, unsigned vert1, unsigned* tris )
  142. {
  143.     unsigned test0, test1, curTri, curVert;
  144.     unsigned numTrisFound = 0;
  145.  
  146.     for( curTri = 0; curTri < m_Tris; curTri++ )
  147.     {
  148.         // skip already collapsed tris
  149.         if( !m_TriActive[curTri] )
  150.             continue;
  151.  
  152.         ModelTri* tri = &m_Tris[curTri];
  153.  
  154.         for( curVert = 0; curVert < 3; curVert++ )
  155.         {
  156.             test0 = tri->m_Indices[curVert];
  157.             test1 = tri->m_Indices[(curVert+1)%3];
  158.  
  159.             if( ((test0 == vert0) && (test1 == vert1)) ||
  160.                 ((test1 == vert0) && (test0 == vert1)) )
  161.             {
  162.                 // oops, more than 2 tris share this edge
  163.                 if( numTrisFound >= 2 )
  164.                     return false;
  165.  
  166.                 tris[numTrisFound++] = curTri;
  167.             }
  168.         }
  169.     }
  170.  
  171.     return (numTrisFound == 2) && (tris[0] != tris[1]);
  172. }
  173.  
  174.  
  175. // updates structures with an edge collapse
  176. bool CBuildPieceLOD::ProcessEdgeCollapse( const EdgeCollapse& edgeCollapse )
  177. {
  178.     unsigned curTri, curVert;
  179.     UVPair uvs[2][2];
  180.     UVPair newUVs[2];
  181.     unsigned triVerts[2][2];
  182.     ModelTri* uvRefTris[2];
  183.  
  184.     // deactivate the tris
  185.     ASSERT( m_TriActive[edgeCollapse.m_Tris[0]] );
  186.     ASSERT( m_TriActive[edgeCollapse.m_Tris[1]] );
  187.     m_TriActive[edgeCollapse.m_Tris[0]] = false;
  188.     m_TriActive[edgeCollapse.m_Tris[1]] = false;
  189.  
  190.     for( unsigned i = 0; i < 2; i++ )
  191.     {
  192.         // grab the 0-2 index of each vert on the tri
  193.         if( !GetTriVert( edgeCollapse.m_Tris[i], edgeCollapse.m_Verts[0], triVerts[i][0] ) ||
  194.             !GetTriVert( edgeCollapse.m_Tris[i], edgeCollapse.m_Verts[1], triVerts[i][1] ) )
  195.         {
  196.             ASSERT(0);
  197.             return false;
  198.         }
  199.  
  200.         uvRefTris[i] = &m_Tris[edgeCollapse.m_Tris[i]];
  201.  
  202.         uvs[i][0] = uvRefTris[i]->m_UVs[triVerts[i][0]];
  203.         uvs[i][1] = uvRefTris[i]->m_UVs[triVerts[i][1]];
  204.         newUVs[i].tu = uvs[i][0].tu + (uvs[i][1].tu - uvs[i][0].tu) * 0.5f;
  205.         newUVs[i].tv = uvs[i][0].tv + (uvs[i][1].tv - uvs[i][0].tv) * 0.5f;
  206.     }
  207.  
  208.     // update the UVs of any adjacent verts
  209.     for( curTri = 0; curTri < m_Tris; curTri++ )
  210.     {
  211.         ModelTri* tri = &m_Tris[curTri];
  212.  
  213.         // don't do anything with the tris being collapsed
  214.         if( (curTri == edgeCollapse.m_Tris[0]) || (curTri == edgeCollapse.m_Tris[1]) )
  215.             continue;
  216.  
  217.         for( curVert = 0; curVert < 3; curVert++ )
  218.         {
  219.             for( i = 0; i < 2; i++ )
  220.             {
  221.                 if( tri->m_Indices[curVert] == uvRefTris[i]->m_Indices[triVerts[i][0]] )
  222.                 {
  223.                     if( (fabs( tri->m_UVs[curVert].tu - uvs[i][0].tu ) < 0.001f) && (fabs( tri->m_UVs[curVert].tv - uvs[i][0].tv ) < 0.001f) )
  224.                         tri->m_UVs[curVert] = newUVs[i];
  225.                 }
  226.                 else if( tri->m_Indices[curVert] == uvRefTris[i]->m_Indices[triVerts[i][1]] )
  227.                 {
  228.                     if( (fabs( tri->m_UVs[curVert].tu - uvs[i][1].tu ) < 0.001f) && (fabs( tri->m_UVs[curVert].tv - uvs[i][1].tv ) < 0.001f) )
  229.                         tri->m_UVs[curVert] = newUVs[i];
  230.                 }
  231.             }
  232.         }
  233.     }
  234.  
  235.     // add the new vertex
  236.     MergeVerts( edgeCollapse );
  237.  
  238.     // update the triangle indices
  239.     for( curTri = 0; curTri < m_Tris; curTri++ )
  240.     {
  241.         ModelTri* tri = &m_Tris[curTri];
  242.  
  243.         for( curVert = 0; curVert < 3; curVert++ )
  244.         {
  245.             if( (tri->m_Indices[curVert] == edgeCollapse.m_Verts[0]) || (tri->m_Indices[curVert] == edgeCollapse.m_Verts[1]) )
  246.                 tri->m_Indices[curVert] = m_Verts.LastI();
  247.         }
  248.     }
  249.  
  250.     // any verts that reference only the removed triangles need to have any replacements
  251.     // referencing them updated to reference the new vertex instead
  252.     UpdateDeadVertexReferences( edgeCollapse, m_Verts.LastI() );
  253.  
  254.     return true;
  255. }
  256.  
  257.  
  258. // given a triangle and a vert index, get which vert on the tri has that index
  259. bool CBuildPieceLOD::GetTriVert( unsigned tri, unsigned vertIndex, unsigned& vert )
  260. {
  261.     ModelTri* t = &m_Tris[tri];
  262.  
  263.     for( unsigned i = 0; i < 3; i++ )
  264.     {
  265.         if( t->m_Indices[i] == vertIndex )
  266.         {
  267.             vert = i;
  268.             return true;
  269.         }
  270.     }
  271.  
  272.     return false;
  273. }
  274.  
  275.  
  276. // merge two verts into a new vert
  277. void CBuildPieceLOD::MergeVerts( const EdgeCollapse& edgeCollapse )
  278. {
  279.     ModelVert newVert;
  280.  
  281.     m_Verts.Append( newVert );
  282.  
  283.     ModelVert* vert0 = &m_Verts[edgeCollapse.m_Verts[0]];
  284.     ModelVert* vert1 = &m_Verts[edgeCollapse.m_Verts[1]];
  285.  
  286.     MarkReplacements( edgeCollapse.m_Verts[0], m_Verts.LastI() );
  287.     MarkReplacements( edgeCollapse.m_Verts[1], m_Verts.LastI() );
  288.  
  289.     vert0->m_iReplacement = (short)m_Verts.LastI();
  290.     vert1->m_iReplacement = (short)m_Verts.LastI();
  291.     ModelVert* vert = &m_Verts.Last();
  292.     vert->m_iReplacement = (short)m_Verts.LastI();
  293.  
  294.     ASSERT( vert0->m_iReplacement != (vert0 - m_Verts.GetArray()) );
  295.     ASSERT( vert1->m_iReplacement != (vert1 - m_Verts.GetArray()) );
  296.  
  297.     vert->m_Vec = vert0->m_Vec + (vert1->m_Vec - vert0->m_Vec) * 0.5f;
  298.     vert->m_Normal = vert0->m_Normal + (vert1->m_Normal - vert0->m_Normal) * 0.5f;
  299.     vert->m_Normal.Norm();
  300.  
  301.     NewVertexWeight *weight, *newWeight;
  302.  
  303.     // add vert0s weights
  304.     for( unsigned i = 0; i < vert0->m_nWeights; i++ )
  305.     {
  306.         weight = &vert0->m_Weights[i];
  307.         newWeight = vert->AddWeight();
  308.  
  309.         newWeight->m_Vec[0] = weight->m_Vec[0] * 0.5f;
  310.         newWeight->m_Vec[1] = weight->m_Vec[1] * 0.5f;
  311.         newWeight->m_Vec[2] = weight->m_Vec[2] * 0.5f;
  312.         newWeight->m_Vec[3] = weight->m_Vec[3] * 0.5f;
  313.         newWeight->m_iNode = weight->m_iNode;
  314.     }
  315.  
  316.     // add vert1s weights
  317.     for( i = 0; i < vert1->m_nWeights; i++ )
  318.     {
  319.         weight = &vert1->m_Weights[i];
  320.  
  321.         // check to see if the weight already exists from vert0
  322.         if( !(newWeight = FindWeight( vert, weight->m_iNode )) )
  323.             newWeight = vert->AddWeight();
  324.  
  325.         newWeight->m_Vec[0] += weight->m_Vec[0] * 0.5f;
  326.         newWeight->m_Vec[1] += weight->m_Vec[1] * 0.5f;
  327.         newWeight->m_Vec[2] += weight->m_Vec[2] * 0.5f;
  328.         newWeight->m_Vec[3] += weight->m_Vec[3] * 0.5f;
  329.         newWeight->m_iNode = weight->m_iNode;
  330.     }
  331. }
  332.  
  333.  
  334. // check to see if a vert already has a weight for a node
  335. NewVertexWeight* CBuildPieceLOD::FindWeight( ModelVert* vert, unsigned node )
  336. {
  337.     for( unsigned i = 0; i < vert->m_nWeights; i++ )
  338.     {
  339.         if( vert->m_Weights[i].m_iNode == node )
  340.             return &vert->m_Weights[i];
  341.     }
  342.  
  343.     return NULL;
  344. }
  345.  
  346.  
  347. // update any m_iReplacements referencing vertIndex to newVertIndex
  348. void CBuildPieceLOD::MarkReplacements( unsigned vertIndex, unsigned newVertIndex )
  349. {
  350.     ModelVert* vert;
  351.  
  352.     for( unsigned i = 0; i < m_Verts; i++ )
  353.     {
  354.         vert = &m_Verts[i];
  355.  
  356.         if( vert->m_iReplacement == vertIndex )
  357.             vert->m_iReplacement = newVertIndex;
  358.     }
  359. }
  360.  
  361.  
  362. // any verts that reference only the removed triangles need to have any replacements
  363. // referencing them updated to reference the new vertex instead
  364. void CBuildPieceLOD::UpdateDeadVertexReferences( const EdgeCollapse& edgeCollapse, unsigned newIndex )
  365. {
  366.     unsigned curTri, curVert;
  367.  
  368.     ModelTri* tris[2];
  369.     tris[0] = &m_Tris[edgeCollapse.m_Tris[0]];
  370.     tris[1] = &m_Tris[edgeCollapse.m_Tris[1]];
  371.  
  372.     // make a list for each vertex of what tris reference it
  373.     CMoArray<ModelTriPtrArray> vertTriRefs;
  374.     vertTriRefs.SetSize( m_Verts.GetSize() );
  375.     for( curTri = 0; curTri < m_Tris; curTri++ )
  376.     {
  377.         ModelTri* tri = &m_Tris[curTri];
  378.  
  379.         if( !m_TriActive[curTri] && (tri != tris[0] && tri != tris[1]) )
  380.             continue;
  381.  
  382.         for( curVert = 0; curVert < 3; curVert++ )
  383.         {
  384.             vertTriRefs[tri->m_Indices[curVert]].Append( tri );
  385.         }
  386.     }
  387.  
  388.     // look for vertices that are only referenced by these tris
  389.     for( curVert = 0; curVert < vertTriRefs; curVert++ )
  390.     {
  391.         ModelTriPtrArray& curArray = vertTriRefs[curVert];
  392.  
  393.         if( (curArray.GetSize() == 1) && (curArray[0] == tris[0] || curArray[0] == tris[1]) )
  394.         {
  395.             MarkReplacements( curVert, newIndex );
  396.         }
  397.         else if( (curArray.GetSize() == 2) &&
  398.                  (curArray[0] == tris[0] || curArray[0] == tris[1]) &&
  399.                  (curArray[1] == tris[0] || curArray[1] == tris[1]) )
  400.         {
  401.             MarkReplacements( curVert, newIndex );
  402.         }
  403.     }
  404. }
  405.  
  406.  
  407. // add a new LOD to the model using the current set of edge collapses
  408. bool CBuildPieceLOD::AddLOD( void )
  409. {
  410.     unsigned curEdge, curTri, curVert, curTriVert;
  411.     PieceLOD newLOD;
  412.  
  413.     newLOD.Init( m_Model );
  414.  
  415.     // find the tris that should be in the new LOD
  416.     CMoArray<bool> usedTris;
  417.     unsigned numUsedTris = m_Tris.GetSize();
  418.     usedTris.SetSizeInit2( numUsedTris, true );
  419.  
  420.     for( curEdge = 0; curEdge < m_Collapses; curEdge++ )
  421.     {
  422.         usedTris[m_Collapses[curEdge].m_Tris[0]] = usedTris[m_Collapses[curEdge].m_Tris[1]] = false;
  423.         numUsedTris -= 2;
  424.     }
  425.  
  426.     // setup the new LODs triangle list
  427.     unsigned curAddTri = 0;
  428.     newLOD.m_Tris.SetSize( numUsedTris );
  429.  
  430.     for( curTri = 0; curTri < usedTris; curTri++ )
  431.     {
  432.         if( !usedTris[curTri] )
  433.             continue;
  434.  
  435.         newLOD.m_Tris[curAddTri++] = m_Tris[curTri];
  436.     }
  437.  
  438.     // find the verts that should be in the new LOD
  439.     CMoArray<bool> usedVerts;
  440.     unsigned numUsedVerts = 0;
  441.     usedVerts.SetSizeInit2( m_Verts.GetSize(), false );
  442.     
  443.     for( curTri = 0; curTri < m_Tris; curTri++ )
  444.     {
  445.         for( curTriVert = 0; curTriVert < 3; curTriVert++ )
  446.         {
  447.             if( !usedVerts[m_Tris[curTri].m_Indices[curTriVert]] )
  448.             {
  449.                 usedVerts[m_Tris[curTri].m_Indices[curTriVert]] = true;
  450.                 numUsedVerts++;
  451.             }
  452.         }
  453.     }
  454.  
  455.     // setup the new LODs vertex list
  456.     CMoArray<unsigned> vertIndexRemap;
  457.     unsigned curAddVert = 0;
  458.     vertIndexRemap.SetSizeInit2( m_Verts.GetSize(), UINT_MAX );
  459.     newLOD.m_Verts.SetSize( numUsedVerts );
  460.  
  461.     for( curVert = 0; curVert < m_Verts; curVert++ )
  462.     {
  463.         if( !usedVerts[curVert] )
  464.             continue;
  465.  
  466.         newLOD.m_Verts[curAddVert] = m_Verts[curVert];
  467.  
  468.         vertIndexRemap[curVert] = curAddVert++;
  469.     }
  470.  
  471.     ASSERT( numUsedVerts == curAddVert );
  472.  
  473.     // remap the triangle indices
  474.     for( curTri = 0; curTri < newLOD.m_Tris; curTri++ )
  475.     {
  476.         ModelTri* tri = &newLOD.m_Tris[curTri];
  477.  
  478.         for( curTriVert = 0; curTriVert < 3; curTriVert++ )
  479.         {
  480.             ASSERT( tri->m_Indices[curTriVert] != UINT_MAX );
  481.             tri->m_Indices[curTriVert] = vertIndexRemap[tri->m_Indices[curTriVert]];
  482.         }
  483.     }
  484.  
  485.     // copy over material info
  486.     newLOD.SetMaterialInfo( *m_PieceLOD );
  487.  
  488.     newLOD.CalcUsedNodeList();
  489.  
  490.     // add the new LOD to the piece
  491.     m_ModelPiece->AddLOD( newLOD, m_Distance, true );
  492.  
  493.     return true;
  494. }
  495.  
  496.