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