neo/idlib/geometry/Surface.cpp

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