Re: [Algorithms] VIPM With T&L

[Angel P. <ju...@bi...>]

What about having an array with the vertex collapses ( the N-th element storing the
new index of the N-th vertex after the collapse ) with the verts sorted in discard order
and several static LODs (each LOD with ~ half the verts of the next one ) of the trilist
with the triangles stored in strip order.

The algho should work like this:
1. Pick the number of used verts from a lookup table using the distance and screen area.
2. Pick the LOD and the trilist for that LOD.
3. For each triangle from the trilist - collapse each vertex untill it's index becomes smaller
than the number of verts, if the triangle does not have degenerate edges then put its
vert indexes in the index list.

You will preform less than one split per vertex average, the triangles will always be in roughly
strip order, the memory requirements will be slightly lower (no more 14 bytes per vsplit )
than for the vsplit approach, it will handle worst-case situations (huge landcape showing
behind the door ) much more gracefully than updating the PM each frame, it's much easier
to understand and and simpler to implement.

Here's some code I just wrote (so it probably has bugs):

int currentNumVerts =
  GetNumVertsFromLookupTable( ScreenArea, ObjectDistance );//with interpolation

int currentLOD;
while( LODs[currentLOD].NumVerts < currentNumVerts )
    currentLOD++;

numVerts=0;

for( int i=0; i<TriListLODs[currentLOD]->NumTris; i++ )
{
    CIndexedTriangle currentTri = &TriListLODs[currentLOD]->Tris[ i ];

    if( CurrentTri->NumVertsBeforeCollapse<currentNumVerts )
        continue; //quickly reject this triangle

    int index1 = currentTri->Index1;
    while( collapseArray[ index1 ]>currentNumVerts )
        index1=collapseArray[ index1 ].collapsedVertIndex;

    int index2 = currentTri->Index2;
    while( collapseArray[ index2 ]>currentNumVerts )
        index1=collapseArray[ index2 ].collapsedVertIndex;

    int index3 = currentTri.Index3;
    while( collapseArray[ index3 ]>currentNumVerts )
        index3=collapseArray[ index3 ].collapsedVertIndex;

    vertexIndexes[ numVerts ] = index1;
    vertexIndexes[ numVerts+1 ] = index2;
    vertexIndexes[ numVerts+2 ] = index3;    
    numVerts+=3;
}