home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / geometry / Surface.cpp < prev    next >
C/C++ Source or Header  |  2005-11-14  |  28KB  |  904 lines
  1.  
  2. #include "../precompiled.h"
  3. #pragma hdrstop
  4.  
  5.  
  6. /*
  7. =================
  8. UpdateVertexIndex
  9. =================
  10. */
  11. ID_INLINE int UpdateVertexIndex( int vertexIndexNum[2], int *vertexRemap, int *vertexCopyIndex, int vertNum ) {
  12.     int s = INTSIGNBITSET( vertexRemap[vertNum] );
  13.     vertexIndexNum[0] = vertexRemap[vertNum];
  14.     vertexRemap[vertNum] = vertexIndexNum[s];
  15.     vertexIndexNum[1] += s;
  16.     vertexCopyIndex[vertexRemap[vertNum]] = vertNum;
  17.     return vertexRemap[vertNum];
  18. }
  19.  
  20. /*
  21. =================
  22. idSurface::Split
  23. =================
  24. */
  25. int idSurface::Split( const idPlane &plane, const float epsilon, idSurface **front, idSurface **back, int *frontOnPlaneEdges, int *backOnPlaneEdges ) const {
  26.     float *            dists;
  27.     float            f;
  28.     byte *            sides;
  29.     int                counts[3];
  30.     int *            edgeSplitVertex;
  31.     int                numEdgeSplitVertexes;
  32.     int *            vertexRemap[2];
  33.     int                vertexIndexNum[2][2];
  34.     int *            vertexCopyIndex[2];
  35.     int *            indexPtr[2];
  36.     int                indexNum[2];
  37.     int *            index;
  38.     int *            onPlaneEdges[2];
  39.     int                numOnPlaneEdges[2];
  40.     int                maxOnPlaneEdges;
  41.     int                i;
  42.     idSurface *        surface[2];
  43.     idDrawVert        v;
  44.  
  45.     dists = (float *) _alloca( verts.Num() * sizeof( float ) );
  46.     sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
  47.  
  48.     counts[0] = counts[1] = counts[2] = 0;
  49.  
  50.     // determine side for each vertex
  51.     for ( i = 0; i < verts.Num(); i++ ) {
  52.         dists[i] = f = plane.Distance( verts[i].xyz );
  53.         if ( f > epsilon ) {
  54.             sides[i] = SIDE_FRONT;
  55.         } else if ( f < -epsilon ) {
  56.             sides[i] = SIDE_BACK;
  57.         } else {
  58.             sides[i] = SIDE_ON;
  59.         }
  60.         counts[sides[i]]++;
  61.     }
  62.     
  63.     *front = *back = NULL;
  64.  
  65.     // if coplanar, put on the front side if the normals match
  66.     if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
  67.  
  68.         f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
  69.         if ( FLOATSIGNBITSET( f ) ) {
  70.             *back = new idSurface( *this );
  71.             return SIDE_BACK;
  72.         } else {
  73.             *front = new idSurface( *this );
  74.             return SIDE_FRONT;
  75.         }
  76.     }
  77.     // if nothing at the front of the clipping plane
  78.     if ( !counts[SIDE_FRONT] ) {
  79.         *back = new idSurface( *this );
  80.         return SIDE_BACK;
  81.     }
  82.     // if nothing at the back of the clipping plane
  83.     if ( !counts[SIDE_BACK] ) {
  84.         *front = new idSurface( *this );
  85.         return SIDE_FRONT;
  86.     }
  87.  
  88.     // allocate front and back surface
  89.     *front = surface[0] = new idSurface();
  90.     *back = surface[1] = new idSurface();
  91.  
  92.     edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
  93.     numEdgeSplitVertexes = 0;
  94.  
  95.     maxOnPlaneEdges = 4 * counts[SIDE_ON];
  96.     counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
  97.  
  98.     // split edges
  99.     for ( i = 0; i < edges.Num(); i++ ) {
  100.         int v0 = edges[i].verts[0];
  101.         int v1 = edges[i].verts[1];
  102.         int sidesOr = ( sides[v0] | sides[v1] );
  103.  
  104.         // if both vertexes are on the same side or one is on the clipping plane
  105.         if ( !( sides[v0] ^ sides[v1] ) || ( sidesOr & SIDE_ON ) ) {
  106.             edgeSplitVertex[i] = -1;
  107.             counts[sidesOr & SIDE_BACK]++;
  108.             counts[SIDE_ON] += ( sidesOr & SIDE_ON ) >> 1;
  109.         } else {
  110.             f = dists[v0] / ( dists[v0] - dists[v1] );
  111.             v.LerpAll( verts[v0], verts[v1], f );
  112.             edgeSplitVertex[i] = numEdgeSplitVertexes++;
  113.             surface[0]->verts.Append( v );
  114.             surface[1]->verts.Append( v );
  115.         }
  116.     }
  117.  
  118.     // each edge is shared by at most two triangles, as such there can never be more indexes than twice the number of edges
  119.     surface[0]->indexes.Resize( ( ( counts[SIDE_FRONT] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 ) );
  120.     surface[1]->indexes.Resize( ( ( counts[SIDE_BACK] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 ) );
  121.  
  122.     // allocate indexes to construct the triangle indexes for the front and back surface
  123.     vertexRemap[0] = (int *) _alloca( verts.Num() * sizeof( int ) );
  124.     memset( vertexRemap[0], -1, verts.Num() * sizeof( int ) );
  125.     vertexRemap[1] = (int *) _alloca( verts.Num() * sizeof( int ) );
  126.     memset( vertexRemap[1], -1, verts.Num() * sizeof( int ) );
  127.  
  128.     vertexCopyIndex[0] = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
  129.     vertexCopyIndex[1] = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
  130.  
  131.     vertexIndexNum[0][0] = vertexIndexNum[1][0] = 0;
  132.     vertexIndexNum[0][1] = vertexIndexNum[1][1] = numEdgeSplitVertexes;
  133.  
  134.     indexPtr[0] = surface[0]->indexes.Ptr();
  135.     indexPtr[1] = surface[1]->indexes.Ptr();
  136.     indexNum[0] = surface[0]->indexes.Num();
  137.     indexNum[1] = surface[1]->indexes.Num();
  138.  
  139.     maxOnPlaneEdges += 4 * numEdgeSplitVertexes;
  140.     // allocate one more in case no triangles are actually split which may happen for a disconnected surface
  141.     onPlaneEdges[0] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
  142.     onPlaneEdges[1] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
  143.     numOnPlaneEdges[0] = numOnPlaneEdges[1] = 0;
  144.  
  145.     // split surface triangles
  146.     for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
  147.         int e0, e1, e2, v0, v1, v2, s, n;
  148.  
  149.         e0 = abs( edgeIndexes[i+0] );
  150.         e1 = abs( edgeIndexes[i+1] );
  151.         e2 = abs( edgeIndexes[i+2] );
  152.  
  153.         v0 = indexes[i+0];
  154.         v1 = indexes[i+1];
  155.         v2 = indexes[i+2];
  156.  
  157.         switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
  158.             case 0: {    // no edges split
  159.                 if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
  160.                     // coplanar
  161.                     f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
  162.                     s = FLOATSIGNBITSET( f );
  163.                 } else {
  164.                     s = ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK;
  165.                 }
  166.                 n = indexNum[s];
  167.                 onPlaneEdges[s][numOnPlaneEdges[s]] = n;
  168.                 numOnPlaneEdges[s] += ( sides[v0] & sides[v1] ) >> 1;
  169.                 onPlaneEdges[s][numOnPlaneEdges[s]] = n+1;
  170.                 numOnPlaneEdges[s] += ( sides[v1] & sides[v2] ) >> 1;
  171.                 onPlaneEdges[s][numOnPlaneEdges[s]] = n+2;
  172.                 numOnPlaneEdges[s] += ( sides[v2] & sides[v0] ) >> 1;
  173.                 index = indexPtr[s];
  174.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  175.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  176.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  177.                 indexNum[s] = n;
  178.                 break;
  179.             }
  180.             case 1: {    // first edge split
  181.                 s = sides[v0] & SIDE_BACK;
  182.                 n = indexNum[s];
  183.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  184.                 index = indexPtr[s];
  185.                 index[n++] = edgeSplitVertex[e0];
  186.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  187.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  188.                 indexNum[s] = n;
  189.                 s ^= 1;
  190.                 n = indexNum[s];
  191.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  192.                 index = indexPtr[s];
  193.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  194.                 index[n++] = edgeSplitVertex[e0];
  195.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  196.                 indexNum[s] = n;
  197.                 break;
  198.             }
  199.             case 2: {    // second edge split
  200.                 s = sides[v1] & SIDE_BACK;
  201.                 n = indexNum[s];
  202.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  203.                 index = indexPtr[s];
  204.                 index[n++] = edgeSplitVertex[e1];
  205.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  206.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  207.                 indexNum[s] = n;
  208.                 s ^= 1;
  209.                 n = indexNum[s];
  210.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  211.                 index = indexPtr[s];
  212.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  213.                 index[n++] = edgeSplitVertex[e1];
  214.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  215.                 indexNum[s] = n;
  216.                 break;
  217.             }
  218.             case 3: {    // first and second edge split
  219.                 s = sides[v1] & SIDE_BACK;
  220.                 n = indexNum[s];
  221.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  222.                 index = indexPtr[s];
  223.                 index[n++] = edgeSplitVertex[e1];
  224.                 index[n++] = edgeSplitVertex[e0];
  225.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  226.                 indexNum[s] = n;
  227.                 s ^= 1;
  228.                 n = indexNum[s];
  229.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  230.                 index = indexPtr[s];
  231.                 index[n++] = edgeSplitVertex[e0];
  232.                 index[n++] = edgeSplitVertex[e1];
  233.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  234.                 index[n++] = edgeSplitVertex[e1];
  235.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  236.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  237.                 indexNum[s] = n;
  238.                 break;
  239.             }
  240.             case 4: {    // third edge split
  241.                 s = sides[v2] & SIDE_BACK;
  242.                 n = indexNum[s];
  243.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  244.                 index = indexPtr[s];
  245.                 index[n++] = edgeSplitVertex[e2];
  246.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  247.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  248.                 indexNum[s] = n;
  249.                 s ^= 1;
  250.                 n = indexNum[s];
  251.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  252.                 index = indexPtr[s];
  253.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  254.                 index[n++] = edgeSplitVertex[e2];
  255.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  256.                 indexNum[s] = n;
  257.                 break;
  258.             }
  259.             case 5: {    // first and third edge split
  260.                 s = sides[v0] & SIDE_BACK;
  261.                 n = indexNum[s];
  262.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  263.                 index = indexPtr[s];
  264.                 index[n++] = edgeSplitVertex[e0];
  265.                 index[n++] = edgeSplitVertex[e2];
  266.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  267.                 indexNum[s] = n;
  268.                 s ^= 1;
  269.                 n = indexNum[s];
  270.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  271.                 index = indexPtr[s];
  272.                 index[n++] = edgeSplitVertex[e2];
  273.                 index[n++] = edgeSplitVertex[e0];
  274.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  275.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  276.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  277.                 index[n++] = edgeSplitVertex[e2];
  278.                 indexNum[s] = n;
  279.                 break;
  280.             }
  281.             case 6: {    // second and third edge split
  282.                 s = sides[v2] & SIDE_BACK;
  283.                 n = indexNum[s];
  284.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  285.                 index = indexPtr[s];
  286.                 index[n++] = edgeSplitVertex[e2];
  287.                 index[n++] = edgeSplitVertex[e1];
  288.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
  289.                 indexNum[s] = n;
  290.                 s ^= 1;
  291.                 n = indexNum[s];
  292.                 onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
  293.                 index = indexPtr[s];
  294.                 index[n++] = edgeSplitVertex[e1];
  295.                 index[n++] = edgeSplitVertex[e2];
  296.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  297.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
  298.                 index[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
  299.                 index[n++] = edgeSplitVertex[e2];
  300.                 indexNum[s] = n;
  301.                 break;
  302.             }
  303.         }
  304.     }
  305.  
  306.     surface[0]->indexes.SetNum( indexNum[0], false );
  307.     surface[1]->indexes.SetNum( indexNum[1], false );
  308.  
  309.     // copy vertexes
  310.     surface[0]->verts.SetNum( vertexIndexNum[0][1], false );
  311.     index = vertexCopyIndex[0];
  312.     for ( i = numEdgeSplitVertexes; i < surface[0]->verts.Num(); i++ ) {
  313.         surface[0]->verts[i] = verts[index[i]];
  314.     }
  315.     surface[1]->verts.SetNum( vertexIndexNum[1][1], false );
  316.     index = vertexCopyIndex[1];
  317.     for ( i = numEdgeSplitVertexes; i < surface[1]->verts.Num(); i++ ) {
  318.         surface[1]->verts[i] = verts[index[i]];
  319.     }
  320.  
  321.     // generate edge indexes
  322.     surface[0]->GenerateEdgeIndexes();
  323.     surface[1]->GenerateEdgeIndexes();
  324.  
  325.     if ( frontOnPlaneEdges ) {
  326.         memcpy( frontOnPlaneEdges, onPlaneEdges[0], numOnPlaneEdges[0] * sizeof( int ) );
  327.         frontOnPlaneEdges[numOnPlaneEdges[0]] = -1;
  328.     }
  329.  
  330.     if ( backOnPlaneEdges ) {
  331.         memcpy( backOnPlaneEdges, onPlaneEdges[1], numOnPlaneEdges[1] * sizeof( int ) );
  332.         backOnPlaneEdges[numOnPlaneEdges[1]] = -1;
  333.     }
  334.  
  335.     return SIDE_CROSS;
  336. }
  337.  
  338. /*
  339. =================
  340. idSurface::ClipInPlace
  341. =================
  342. */
  343. bool idSurface::ClipInPlace( const idPlane &plane, const float epsilon, const bool keepOn ) {
  344.     float *            dists;
  345.     float            f;
  346.     byte *            sides;
  347.     int                counts[3];
  348.     int                i;
  349.     int *            edgeSplitVertex;
  350.     int *            vertexRemap;
  351.     int                vertexIndexNum[2];
  352.     int *            vertexCopyIndex;
  353.     int *            indexPtr;
  354.     int                indexNum;
  355.     int                numEdgeSplitVertexes;
  356.     idDrawVert        v;
  357.     idList<idDrawVert> newVerts;
  358.     idList<int>        newIndexes;
  359.  
  360.     dists = (float *) _alloca( verts.Num() * sizeof( float ) );
  361.     sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
  362.  
  363.     counts[0] = counts[1] = counts[2] = 0;
  364.  
  365.     // determine side for each vertex
  366.     for ( i = 0; i < verts.Num(); i++ ) {
  367.         dists[i] = f = plane.Distance( verts[i].xyz );
  368.         if ( f > epsilon ) {
  369.             sides[i] = SIDE_FRONT;
  370.         } else if ( f < -epsilon ) {
  371.             sides[i] = SIDE_BACK;
  372.         } else {
  373.             sides[i] = SIDE_ON;
  374.         }
  375.         counts[sides[i]]++;
  376.     }
  377.     
  378.     // if coplanar, put on the front side if the normals match
  379.     if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
  380.  
  381.         f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
  382.         if ( FLOATSIGNBITSET( f ) ) {
  383.             Clear();
  384.             return false;
  385.         } else {
  386.             return true;
  387.         }
  388.     }
  389.     // if nothing at the front of the clipping plane
  390.     if ( !counts[SIDE_FRONT] ) {
  391.         Clear();
  392.         return false;
  393.     }
  394.     // if nothing at the back of the clipping plane
  395.     if ( !counts[SIDE_BACK] ) {
  396.         return true;
  397.     }
  398.  
  399.     edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
  400.     numEdgeSplitVertexes = 0;
  401.  
  402.     counts[SIDE_FRONT] = counts[SIDE_BACK] = 0;
  403.  
  404.     // split edges
  405.     for ( i = 0; i < edges.Num(); i++ ) {
  406.         int v0 = edges[i].verts[0];
  407.         int v1 = edges[i].verts[1];
  408.  
  409.         // if both vertexes are on the same side or one is on the clipping plane
  410.         if ( !( sides[v0] ^ sides[v1] ) || ( ( sides[v0] | sides[v1] ) & SIDE_ON ) ) {
  411.             edgeSplitVertex[i] = -1;
  412.             counts[(sides[v0]|sides[v1]) & SIDE_BACK]++;
  413.         } else {
  414.             f = dists[v0] / ( dists[v0] - dists[v1] );
  415.             v.LerpAll( verts[v0], verts[v1], f );
  416.             edgeSplitVertex[i] = numEdgeSplitVertexes++;
  417.             newVerts.Append( v );
  418.         }
  419.     }
  420.  
  421.     // each edge is shared by at most two triangles, as such there can never be
  422.     // more indexes than twice the number of edges
  423.     newIndexes.Resize( ( counts[SIDE_FRONT] << 1 ) + ( numEdgeSplitVertexes << 2 ) );
  424.  
  425.     // allocate indexes to construct the triangle indexes for the front and back surface
  426.     vertexRemap = (int *) _alloca( verts.Num() * sizeof( int ) );
  427.     memset( vertexRemap, -1, verts.Num() * sizeof( int ) );
  428.  
  429.     vertexCopyIndex = (int *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( int ) );
  430.  
  431.     vertexIndexNum[0] = 0;
  432.     vertexIndexNum[1] = numEdgeSplitVertexes;
  433.  
  434.     indexPtr = newIndexes.Ptr();
  435.     indexNum = newIndexes.Num();
  436.  
  437.     // split surface triangles
  438.     for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
  439.         int e0, e1, e2, v0, v1, v2;
  440.  
  441.         e0 = abs( edgeIndexes[i+0] );
  442.         e1 = abs( edgeIndexes[i+1] );
  443.         e2 = abs( edgeIndexes[i+2] );
  444.  
  445.         v0 = indexes[i+0];
  446.         v1 = indexes[i+1];
  447.         v2 = indexes[i+2];
  448.  
  449.         switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
  450.             case 0: {    // no edges split
  451.                 if ( ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK ) {
  452.                     break;
  453.                 }
  454.                 if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
  455.                     // coplanar
  456.                     if ( !keepOn ) {
  457.                         break;
  458.                     }
  459.                     f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
  460.                     if ( FLOATSIGNBITSET( f ) ) {
  461.                         break;
  462.                     }
  463.                 }
  464.                 indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  465.                 indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  466.                 indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  467.                 break;
  468.             }
  469.             case 1: {    // first edge split
  470.                 if ( !( sides[v0] & SIDE_BACK ) ) {
  471.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  472.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  473.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  474.                 } else {
  475.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  476.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  477.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  478.                 }
  479.                 break;
  480.             }
  481.             case 2: {    // second edge split
  482.                 if ( !( sides[v1] & SIDE_BACK ) ) {
  483.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  484.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  485.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  486.                 } else {
  487.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  488.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  489.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  490.                 }
  491.                 break;
  492.             }
  493.             case 3: {    // first and second edge split
  494.                 if ( !( sides[v1] & SIDE_BACK ) ) {
  495.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  496.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  497.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  498.                 } else {
  499.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  500.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  501.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  502.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  503.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  504.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  505.                 }
  506.                 break;
  507.             }
  508.             case 4: {    // third edge split
  509.                 if ( !( sides[v2] & SIDE_BACK ) ) {
  510.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  511.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  512.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  513.                 } else {
  514.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  515.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  516.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  517.                 }
  518.                 break;
  519.             }
  520.             case 5: {    // first and third edge split
  521.                 if ( !( sides[v0] & SIDE_BACK ) ) {
  522.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  523.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  524.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  525.                 } else {
  526.                     indexPtr[indexNum++] = edgeSplitVertex[e0];
  527.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  528.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  529.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  530.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  531.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  532.                 }
  533.                 break;
  534.             }
  535.             case 6: {    // second and third edge split
  536.                 if ( !( sides[v2] & SIDE_BACK ) ) {
  537.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
  538.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  539.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  540.                 } else {
  541.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  542.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  543.                     indexPtr[indexNum++] = edgeSplitVertex[e1];
  544.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
  545.                     indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
  546.                     indexPtr[indexNum++] = edgeSplitVertex[e2];
  547.                 }
  548.                 break;
  549.             }
  550.         }
  551.     }
  552.  
  553.     newIndexes.SetNum( indexNum, false );
  554.  
  555.     // copy vertexes
  556.     newVerts.SetNum( vertexIndexNum[1], false );
  557.     for ( i = numEdgeSplitVertexes; i < newVerts.Num(); i++ ) {
  558.         newVerts[i] = verts[vertexCopyIndex[i]];
  559.     }
  560.  
  561.     // copy back to this surface
  562.     indexes = newIndexes;
  563.     verts = newVerts;
  564.  
  565.     GenerateEdgeIndexes();
  566.  
  567.     return true;
  568. }
  569.  
  570. /*
  571. =============
  572. idSurface::IsConnected
  573. =============
  574. */
  575. bool idSurface::IsConnected( void ) const {
  576.     int i, j, numIslands, numTris;
  577.     int queueStart, queueEnd;
  578.     int *queue, *islandNum;
  579.     int curTri, nextTri, edgeNum;
  580.     const int *index;
  581.  
  582.     numIslands = 0;
  583.     numTris = indexes.Num() / 3;
  584.     islandNum = (int *) _alloca16( numTris * sizeof( int ) );
  585.     memset( islandNum, -1, numTris * sizeof( int ) );
  586.     queue = (int *) _alloca16( numTris * sizeof( int ) );
  587.  
  588.     for ( i = 0; i < numTris; i++ ) {
  589.  
  590.         if ( islandNum[i] != -1 ) {
  591.             continue;
  592.         }
  593.  
  594.         queueStart = 0;
  595.         queueEnd = 1;
  596.         queue[0] = i;
  597.         islandNum[i] = numIslands;
  598.  
  599.         for ( curTri = queue[queueStart]; queueStart < queueEnd; curTri = queue[++queueStart] ) {
  600.  
  601.             index = &edgeIndexes[curTri * 3];
  602.  
  603.             for ( j = 0; j < 3; j++ ) {
  604.  
  605.                 edgeNum = index[j];
  606.                 nextTri = edges[abs(edgeNum)].tris[INTSIGNBITNOTSET(edgeNum)];
  607.  
  608.                 if ( nextTri == -1 ) {
  609.                     continue;
  610.                 }
  611.  
  612.                 nextTri /= 3;
  613.  
  614.                 if ( islandNum[nextTri] != -1 ) {
  615.                     continue;
  616.                 }
  617.  
  618.                 queue[queueEnd++] = nextTri;
  619.                 islandNum[nextTri] = numIslands;
  620.             }
  621.         }
  622.         numIslands++;
  623.     }
  624.  
  625.     return ( numIslands == 1 );
  626. }
  627.  
  628. /*
  629. =================
  630. idSurface::IsClosed
  631. =================
  632. */
  633. bool idSurface::IsClosed( void ) const {
  634.     for ( int i = 0; i < edges.Num(); i++ ) {
  635.         if ( edges[i].tris[0] < 0 || edges[i].tris[1] < 0 ) {
  636.             return false;
  637.         }
  638.     }
  639.     return true;
  640. }
  641.  
  642. /*
  643. =============
  644. idSurface::IsPolytope
  645. =============
  646. */
  647. bool idSurface::IsPolytope( const float epsilon ) const {
  648.     int i, j;
  649.     idPlane plane;
  650.  
  651.     if ( !IsClosed() ) {
  652.         return false;
  653.     }
  654.  
  655.     for ( i = 0; i < indexes.Num(); i += 3 ) {
  656.         plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
  657.  
  658.         for ( j = 0; j < verts.Num(); j++ ) {
  659.             if ( plane.Side( verts[j].xyz, epsilon ) == SIDE_FRONT ) {
  660.                 return false;
  661.             }
  662.         }
  663.     }
  664.     return true;
  665. }
  666.  
  667. /*
  668. =============
  669. idSurface::PlaneDistance
  670. =============
  671. */
  672. float idSurface::PlaneDistance( const idPlane &plane ) const {
  673.     int        i;
  674.     float    d, min, max;
  675.  
  676.     min = idMath::INFINITY;
  677.     max = -min;
  678.     for ( i = 0; i < verts.Num(); i++ ) {
  679.         d = plane.Distance( verts[i].xyz );
  680.         if ( d < min ) {
  681.             min = d;
  682.             if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
  683.                 return 0.0f;
  684.             }
  685.         }
  686.         if ( d > max ) {
  687.             max = d;
  688.             if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
  689.                 return 0.0f;
  690.             }
  691.         }
  692.     }
  693.     if ( FLOATSIGNBITNOTSET( min ) ) {
  694.         return min;
  695.     }
  696.     if ( FLOATSIGNBITSET( max ) ) {
  697.         return max;
  698.     }
  699.     return 0.0f;
  700. }
  701.  
  702. /*
  703. =============
  704. idSurface::PlaneSide
  705. =============
  706. */
  707. int idSurface::PlaneSide( const idPlane &plane, const float epsilon ) const {
  708.     bool    front, back;
  709.     int        i;
  710.     float    d;
  711.  
  712.     front = false;
  713.     back = false;
  714.     for ( i = 0; i < verts.Num(); i++ ) {
  715.         d = plane.Distance( verts[i].xyz );
  716.         if ( d < -epsilon ) {
  717.             if ( front ) {
  718.                 return SIDE_CROSS;
  719.             }
  720.             back = true;
  721.             continue;
  722.         }
  723.         else if ( d > epsilon ) {
  724.             if ( back ) {
  725.                 return SIDE_CROSS;
  726.             }
  727.             front = true;
  728.             continue;
  729.         }
  730.     }
  731.  
  732.     if ( back ) {
  733.         return SIDE_BACK;
  734.     }
  735.     if ( front ) {
  736.         return SIDE_FRONT;
  737.     }
  738.     return SIDE_ON;
  739. }
  740.  
  741. /*
  742. =================
  743. idSurface::LineIntersection
  744. =================
  745. */
  746. bool idSurface::LineIntersection( const idVec3 &start, const idVec3 &end, bool backFaceCull ) const {
  747.     float scale;
  748.  
  749.     RayIntersection( start, end - start, scale, false );
  750.     return ( scale >= 0.0f && scale <= 1.0f );
  751. }
  752.  
  753. /*
  754. =================
  755. idSurface::RayIntersection
  756. =================
  757. */
  758. bool idSurface::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull ) const {
  759.     int i, i0, i1, i2, s0, s1, s2;
  760.     float d, s;
  761.     byte *sidedness;
  762.     idPluecker rayPl, pl;
  763.     idPlane plane;
  764.  
  765.     sidedness = (byte *)_alloca( edges.Num() * sizeof(byte) );
  766.     scale = idMath::INFINITY;
  767.  
  768.     rayPl.FromRay( start, dir );
  769.  
  770.     // ray sidedness for edges
  771.     for ( i = 0; i < edges.Num(); i++ ) {
  772.         pl.FromLine( verts[ edges[i].verts[1] ].xyz, verts[ edges[i].verts[0] ].xyz );
  773.         d = pl.PermutedInnerProduct( rayPl );
  774.         sidedness[ i ] = FLOATSIGNBITSET( d );
  775.     }
  776.  
  777.     // test triangles
  778.     for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
  779.         i0 = edgeIndexes[i+0];
  780.         i1 = edgeIndexes[i+1];
  781.         i2 = edgeIndexes[i+2];
  782.         s0 = sidedness[abs(i0)] ^ INTSIGNBITSET( i0 );
  783.         s1 = sidedness[abs(i1)] ^ INTSIGNBITSET( i1 );
  784.         s2 = sidedness[abs(i2)] ^ INTSIGNBITSET( i2 );
  785.  
  786.         if ( s0 & s1 & s2 ) {
  787.             plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
  788.             plane.RayIntersection( start, dir, s );
  789.             if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
  790.                 scale = s;
  791.             }
  792.         } else if ( !backFaceCull && !(s0 | s1 | s2) ) {
  793.             plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
  794.             plane.RayIntersection( start, dir, s );
  795.             if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
  796.                 scale = s;
  797.             }
  798.         }
  799.     }
  800.  
  801.     if ( idMath::Fabs( scale ) < idMath::INFINITY ) {
  802.         return true;
  803.     }
  804.     return false;
  805. }
  806.  
  807. /*
  808. =================
  809. idSurface::GenerateEdgeIndexes
  810.  
  811.   Assumes each edge is shared by at most two triangles.
  812. =================
  813. */
  814. void idSurface::GenerateEdgeIndexes( void ) {
  815.     int i, j, i0, i1, i2, s, v0, v1, edgeNum;
  816.     int *index, *vertexEdges, *edgeChain;
  817.     surfaceEdge_t e[3];
  818.  
  819.     vertexEdges = (int *) _alloca16( verts.Num() * sizeof( int ) );
  820.     memset( vertexEdges, -1, verts.Num() * sizeof( int ) );
  821.     edgeChain = (int *) _alloca16( indexes.Num() * sizeof( int ) );
  822.  
  823.     edgeIndexes.SetNum( indexes.Num(), true );
  824.  
  825.     edges.Clear();
  826.  
  827.     // the first edge is a dummy
  828.     e[0].verts[0] = e[0].verts[1] = e[0].tris[0] = e[0].tris[1] = 0;
  829.     edges.Append( e[0] );
  830.  
  831.     for ( i = 0; i < indexes.Num(); i += 3 ) {
  832.         index = indexes.Ptr() + i;
  833.         // vertex numbers
  834.         i0 = index[0];
  835.         i1 = index[1];
  836.         i2 = index[2];
  837.         // setup edges each with smallest vertex number first
  838.         s = INTSIGNBITSET(i1 - i0);
  839.         e[0].verts[0] = index[s];
  840.         e[0].verts[1] = index[s^1];
  841.         s = INTSIGNBITSET(i2 - i1) + 1;
  842.         e[1].verts[0] = index[s];
  843.         e[1].verts[1] = index[s^3];
  844.         s = INTSIGNBITSET(i2 - i0) << 1;
  845.         e[2].verts[0] = index[s];
  846.         e[2].verts[1] = index[s^2];
  847.         // get edges
  848.         for ( j = 0; j < 3; j++ ) {
  849.             v0 = e[j].verts[0];
  850.             v1 = e[j].verts[1];
  851.             for ( edgeNum = vertexEdges[v0]; edgeNum >= 0; edgeNum = edgeChain[edgeNum] ) {
  852.                 if ( edges[edgeNum].verts[1] == v1 ) {
  853.                     break;
  854.                 }
  855.             }
  856.             // if the edge does not yet exist
  857.             if ( edgeNum < 0 ) {
  858.                 e[j].tris[0] = e[j].tris[1] = -1;
  859.                 edgeNum = edges.Append( e[j] );
  860.                 edgeChain[edgeNum] = vertexEdges[v0];
  861.                 vertexEdges[v0] = edgeNum;
  862.             }
  863.             // update edge index and edge tri references
  864.             if ( index[j] == v0 ) {
  865.                 assert( edges[edgeNum].tris[0] == -1 ); // edge may not be shared by more than two triangles
  866.                 edges[edgeNum].tris[0] = i;
  867.                 edgeIndexes[i+j] = edgeNum;
  868.             } else {
  869.                 assert( edges[edgeNum].tris[1] == -1 ); // edge may not be shared by more than two triangles
  870.                 edges[edgeNum].tris[1] = i;
  871.                 edgeIndexes[i+j] = -edgeNum;
  872.             }
  873.         }
  874.     }
  875. }
  876.  
  877. /*
  878. =================
  879. idSurface::FindEdge
  880. =================
  881. */
  882. int idSurface::FindEdge( int v1, int v2 ) const {
  883.     int i, firstVert, secondVert;
  884.  
  885.     if ( v1 < v2 ) {
  886.         firstVert = v1;
  887.         secondVert = v2;
  888.     } else {
  889.         firstVert = v2;
  890.         secondVert = v1;
  891.     }
  892.     for ( i = 1; i < edges.Num(); i++ ) {
  893.         if ( edges[i].verts[0] == firstVert ) {
  894.             if ( edges[i].verts[1] == secondVert ) {
  895.                 break;
  896.             }
  897.         }
  898.     }
  899.     if ( i < edges.Num() ) {
  900.         return v1 < v2 ? i : -i;
  901.     }
  902.     return 0;
  903. }
  904.