neo/renderer/tr_trisurf.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 "../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "tr_local.h"
  33
  34 /*
  35 ==============================================================================
  36
  37 TRIANGLE MESH PROCESSING
  38
  39 The functions in this file have no vertex / index count limits.
  40
  41 Truly identical vertexes that match in position, normal, and texcoord can
  42 be merged away.
  43
  44 Vertexes that match in position and texcoord, but have distinct normals will
  45 remain distinct for all purposes.  This is usually a poor choice for models,
  46 as adding a bevel face will not add any more vertexes, and will tend to
  47 look better.
  48
  49 Match in position and normal, but differ in texcoords are referenced together
  50 for calculating tangent vectors for bump mapping.
  51 Artists should take care to have identical texels in all maps (bump/diffuse/specular)
  52 in this case
  53
  54 Vertexes that only match in position are merged for shadow edge finding.
  55
  56 Degenerate triangles.
  57
  58 Overlapped triangles, even if normals or texcoords differ, must be removed.
  59 for the silhoette based stencil shadow algorithm to function properly.
  60 Is this true???
  61 Is the overlapped triangle problem just an example of the trippled edge problem?
  62
  63 Interpenetrating triangles are not currently clipped to surfaces.
  64 Do they effect the shadows?
  65
  66 if vertexes are intended to deform apart, make sure that no vertexes
  67 are on top of each other in the base frame, or the sil edges may be
  68 calculated incorrectly.
  69
  70 We might be able to identify this from topology.
  71
  72 Dangling edges are acceptable, but three way edges are not.
  73
  74 Are any combinations of two way edges unacceptable, like one facing
  75 the backside of the other?
  76
  77
  78 Topology is determined by a collection of triangle indexes.
  79
  80 The edge list can be built up from this, and stays valid even under
  81 deformations.
  82
  83 Somewhat non-intuitively, concave edges cannot be optimized away, or the
  84 stencil shadow algorithm miscounts.
  85
  86 Face normals are needed for generating shadow volumes and for calculating
  87 the silhouette, but they will change with any deformation.
  88
  89 Vertex normals and vertex tangents will change with each deformation,
  90 but they may be able to be transformed instead of recalculated.
  91
  92 bounding volume, both box and sphere will change with deformation.
  93
  94 silhouette indexes
  95 shade indexes
  96 texture indexes
  97
  98   shade indexes will only be > silhouette indexes if there is facet shading present
  99
 100         lookups from texture to sil and texture to shade?
 101
 102 The normal and tangent vector smoothing is simple averaging, no attempt is
 103 made to better handle the cases where the distribution around the shared vertex
 104 is highly uneven.
 105
 106
 107   we may get degenerate triangles even with the uniquing and removal
 108   if the vertexes have different texcoords.
 109
 110 ==============================================================================
 111 */
 112
 113 // this shouldn't change anything, but previously renderbumped models seem to need it
 114 #define USE_INVA
 115
 116 // instead of using the texture T vector, cross the normal and S vector for an orthogonal axis
 117 #define DERIVE_UNSMOOTHED_BITANGENT
 118
 119 const int MAX_SIL_EDGES                 = 0x10000;
 120 const int SILEDGE_HASH_SIZE             = 1024;
 121
 122 static int                      numSilEdges;
 123 static silEdge_t *      silEdges;
 124 static idHashIndex      silEdgeHash( SILEDGE_HASH_SIZE, MAX_SIL_EDGES );
 125 static int                      numPlanes;
 126
 127 static idBlockAlloc<srfTriangles_t, 1<<8>                               srfTrianglesAllocator;
 128
 129 #ifdef USE_TRI_DATA_ALLOCATOR
 130 static idDynamicBlockAlloc<idDrawVert, 1<<20, 1<<10>    triVertexAllocator;
 131 static idDynamicBlockAlloc<glIndex_t, 1<<18, 1<<10>             triIndexAllocator;
 132 static idDynamicBlockAlloc<shadowCache_t, 1<<18, 1<<10> triShadowVertexAllocator;
 133 static idDynamicBlockAlloc<idPlane, 1<<17, 1<<10>               triPlaneAllocator;
 134 static idDynamicBlockAlloc<glIndex_t, 1<<17, 1<<10>             triSilIndexAllocator;
 135 static idDynamicBlockAlloc<silEdge_t, 1<<17, 1<<10>             triSilEdgeAllocator;
 136 static idDynamicBlockAlloc<dominantTri_t, 1<<16, 1<<10> triDominantTrisAllocator;
 137 static idDynamicBlockAlloc<int, 1<<16, 1<<10>                   triMirroredVertAllocator;
 138 static idDynamicBlockAlloc<int, 1<<16, 1<<10>                   triDupVertAllocator;
 139 #else
 140 static idDynamicAlloc<idDrawVert, 1<<20, 1<<10>                 triVertexAllocator;
 141 static idDynamicAlloc<glIndex_t, 1<<18, 1<<10>                  triIndexAllocator;
 142 static idDynamicAlloc<shadowCache_t, 1<<18, 1<<10>              triShadowVertexAllocator;
 143 static idDynamicAlloc<idPlane, 1<<17, 1<<10>                    triPlaneAllocator;
 144 static idDynamicAlloc<glIndex_t, 1<<17, 1<<10>                  triSilIndexAllocator;
 145 static idDynamicAlloc<silEdge_t, 1<<17, 1<<10>                  triSilEdgeAllocator;
 146 static idDynamicAlloc<dominantTri_t, 1<<16, 1<<10>              triDominantTrisAllocator;
 147 static idDynamicAlloc<int, 1<<16, 1<<10>                                triMirroredVertAllocator;
 148 static idDynamicAlloc<int, 1<<16, 1<<10>                                triDupVertAllocator;
 149 #endif
 150
 151
 152 /*
 153 ===============
 154 R_InitTriSurfData
 155 ===============
 156 */
 157 void R_InitTriSurfData( void ) {
 158         silEdges = (silEdge_t *)R_StaticAlloc( MAX_SIL_EDGES * sizeof( silEdges[0] ) );
 159
 160         // initialize allocators for triangle surfaces
 161         triVertexAllocator.Init();
 162         triIndexAllocator.Init();
 163         triShadowVertexAllocator.Init();
 164         triPlaneAllocator.Init();
 165         triSilIndexAllocator.Init();
 166         triSilEdgeAllocator.Init();
 167         triDominantTrisAllocator.Init();
 168         triMirroredVertAllocator.Init();
 169         triDupVertAllocator.Init();
 170
 171         // never swap out triangle surfaces
 172         triVertexAllocator.SetLockMemory( true );
 173         triIndexAllocator.SetLockMemory( true );
 174         triShadowVertexAllocator.SetLockMemory( true );
 175         triPlaneAllocator.SetLockMemory( true );
 176         triSilIndexAllocator.SetLockMemory( true );
 177         triSilEdgeAllocator.SetLockMemory( true );
 178         triDominantTrisAllocator.SetLockMemory( true );
 179         triMirroredVertAllocator.SetLockMemory( true );
 180         triDupVertAllocator.SetLockMemory( true );
 181 }
 182
 183 /*
 184 ===============
 185 R_ShutdownTriSurfData
 186 ===============
 187 */
 188 void R_ShutdownTriSurfData( void ) {
 189         R_StaticFree( silEdges );
 190         silEdgeHash.Free();
 191         srfTrianglesAllocator.Shutdown();
 192         triVertexAllocator.Shutdown();
 193         triIndexAllocator.Shutdown();
 194         triShadowVertexAllocator.Shutdown();
 195         triPlaneAllocator.Shutdown();
 196         triSilIndexAllocator.Shutdown();
 197         triSilEdgeAllocator.Shutdown();
 198         triDominantTrisAllocator.Shutdown();
 199         triMirroredVertAllocator.Shutdown();
 200         triDupVertAllocator.Shutdown();
 201 }
 202
 203 /*
 204 ===============
 205 R_PurgeTriSurfData
 206 ===============
 207 */
 208 void R_PurgeTriSurfData( frameData_t *frame ) {
 209         // free deferred triangle surfaces
 210         R_FreeDeferredTriSurfs( frame );
 211
 212         // free empty base blocks
 213         triVertexAllocator.FreeEmptyBaseBlocks();
 214         triIndexAllocator.FreeEmptyBaseBlocks();
 215         triShadowVertexAllocator.FreeEmptyBaseBlocks();
 216         triPlaneAllocator.FreeEmptyBaseBlocks();
 217         triSilIndexAllocator.FreeEmptyBaseBlocks();
 218         triSilEdgeAllocator.FreeEmptyBaseBlocks();
 219         triDominantTrisAllocator.FreeEmptyBaseBlocks();
 220         triMirroredVertAllocator.FreeEmptyBaseBlocks();
 221         triDupVertAllocator.FreeEmptyBaseBlocks();
 222 }
 223
 224 /*
 225 ===============
 226 R_ShowTriMemory_f
 227 ===============
 228 */
 229 void R_ShowTriSurfMemory_f( const idCmdArgs &args ) {
 230         common->Printf( "%6d kB in %d triangle surfaces\n",
 231                 ( srfTrianglesAllocator.GetAllocCount() * sizeof( srfTriangles_t ) ) >> 10,
 232                         srfTrianglesAllocator.GetAllocCount() );
 233
 234         common->Printf( "%6d kB vertex memory (%d kB free in %d blocks, %d empty base blocks)\n",
 235                 triVertexAllocator.GetBaseBlockMemory() >> 10, triVertexAllocator.GetFreeBlockMemory() >> 10,
 236                         triVertexAllocator.GetNumFreeBlocks(), triVertexAllocator.GetNumEmptyBaseBlocks() );
 237
 238         common->Printf( "%6d kB index memory (%d kB free in %d blocks, %d empty base blocks)\n",
 239                 triIndexAllocator.GetBaseBlockMemory() >> 10, triIndexAllocator.GetFreeBlockMemory() >> 10,
 240                         triIndexAllocator.GetNumFreeBlocks(), triIndexAllocator.GetNumEmptyBaseBlocks() );
 241
 242         common->Printf( "%6d kB shadow vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
 243                 triShadowVertexAllocator.GetBaseBlockMemory() >> 10, triShadowVertexAllocator.GetFreeBlockMemory() >> 10,
 244                         triShadowVertexAllocator.GetNumFreeBlocks(), triShadowVertexAllocator.GetNumEmptyBaseBlocks() );
 245
 246         common->Printf( "%6d kB tri plane memory (%d kB free in %d blocks, %d empty base blocks)\n",
 247                 triPlaneAllocator.GetBaseBlockMemory() >> 10, triPlaneAllocator.GetFreeBlockMemory() >> 10,
 248                         triPlaneAllocator.GetNumFreeBlocks(), triPlaneAllocator.GetNumEmptyBaseBlocks() );
 249
 250         common->Printf( "%6d kB sil index memory (%d kB free in %d blocks, %d empty base blocks)\n",
 251                 triSilIndexAllocator.GetBaseBlockMemory() >> 10, triSilIndexAllocator.GetFreeBlockMemory() >> 10,
 252                         triSilIndexAllocator.GetNumFreeBlocks(), triSilIndexAllocator.GetNumEmptyBaseBlocks() );
 253
 254         common->Printf( "%6d kB sil edge memory (%d kB free in %d blocks, %d empty base blocks)\n",
 255                 triSilEdgeAllocator.GetBaseBlockMemory() >> 10, triSilEdgeAllocator.GetFreeBlockMemory() >> 10,
 256                         triSilEdgeAllocator.GetNumFreeBlocks(), triSilEdgeAllocator.GetNumEmptyBaseBlocks() );
 257
 258         common->Printf( "%6d kB dominant tri memory (%d kB free in %d blocks, %d empty base blocks)\n",
 259                 triDominantTrisAllocator.GetBaseBlockMemory() >> 10, triDominantTrisAllocator.GetFreeBlockMemory() >> 10,
 260                         triDominantTrisAllocator.GetNumFreeBlocks(), triDominantTrisAllocator.GetNumEmptyBaseBlocks() );
 261
 262         common->Printf( "%6d kB mirror vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
 263                 triMirroredVertAllocator.GetBaseBlockMemory() >> 10, triMirroredVertAllocator.GetFreeBlockMemory() >> 10,
 264                         triMirroredVertAllocator.GetNumFreeBlocks(), triMirroredVertAllocator.GetNumEmptyBaseBlocks() );
 265
 266         common->Printf( "%6d kB dup vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
 267                 triDupVertAllocator.GetBaseBlockMemory() >> 10, triDupVertAllocator.GetFreeBlockMemory() >> 10,
 268                         triDupVertAllocator.GetNumFreeBlocks(), triDupVertAllocator.GetNumEmptyBaseBlocks() );
 269
 270         common->Printf( "%6d kB total triangle memory\n",
 271                 ( srfTrianglesAllocator.GetAllocCount() * sizeof( srfTriangles_t ) +
 272                         triVertexAllocator.GetBaseBlockMemory() +
 273                         triIndexAllocator.GetBaseBlockMemory() +
 274                         triShadowVertexAllocator.GetBaseBlockMemory() +
 275                         triPlaneAllocator.GetBaseBlockMemory() +
 276                         triSilIndexAllocator.GetBaseBlockMemory() +
 277                         triSilEdgeAllocator.GetBaseBlockMemory() +
 278                         triDominantTrisAllocator.GetBaseBlockMemory() +
 279                         triMirroredVertAllocator.GetBaseBlockMemory() +
 280                         triDupVertAllocator.GetBaseBlockMemory() ) >> 10 );
 281 }
 282
 283 /*
 284 =================
 285 R_TriSurfMemory
 286
 287 For memory profiling
 288 =================
 289 */
 290 int R_TriSurfMemory( const srfTriangles_t *tri ) {
 291         int total = 0;
 292
 293         if ( !tri ) {
 294                 return total;
 295         }
 296
 297         // used as a flag in interations
 298         if ( tri == LIGHT_TRIS_DEFERRED ) {
 299                 return total;
 300         }
 301
 302         if ( tri->shadowVertexes != NULL ) {
 303                 total += tri->numVerts * sizeof( tri->shadowVertexes[0] );
 304         } else if ( tri->verts != NULL ) {
 305                 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
 306                         total += tri->numVerts * sizeof( tri->verts[0] );
 307                 }
 308         }
 309         if ( tri->facePlanes != NULL ) {
 310                 total += tri->numIndexes / 3 * sizeof( tri->facePlanes[0] );
 311         }
 312         if ( tri->indexes != NULL ) {
 313                 if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
 314                         total += tri->numIndexes * sizeof( tri->indexes[0] );
 315                 }
 316         }
 317         if ( tri->silIndexes != NULL ) {
 318                 total += tri->numIndexes * sizeof( tri->silIndexes[0] );
 319         }
 320         if ( tri->silEdges != NULL ) {
 321                 total += tri->numSilEdges * sizeof( tri->silEdges[0] );
 322         }
 323         if ( tri->dominantTris != NULL ) {
 324                 total += tri->numVerts * sizeof( tri->dominantTris[0] );
 325         }
 326         if ( tri->mirroredVerts != NULL ) {
 327                 total += tri->numMirroredVerts * sizeof( tri->mirroredVerts[0] );
 328         }
 329         if ( tri->dupVerts != NULL ) {
 330                 total += tri->numDupVerts * sizeof( tri->dupVerts[0] );
 331         }
 332
 333         total += sizeof( *tri );
 334
 335         return total;
 336 }
 337
 338 /*
 339 ==============
 340 R_FreeStaticTriSurfVertexCaches
 341 ==============
 342 */
 343 void R_FreeStaticTriSurfVertexCaches( srfTriangles_t *tri ) {
 344         if ( tri->ambientSurface == NULL ) {
 345                 // this is a real model surface
 346                 vertexCache.Free( tri->ambientCache );
 347                 tri->ambientCache = NULL;
 348         } else {
 349                 // this is a light interaction surface that references
 350                 // a different ambient model surface
 351                 vertexCache.Free( tri->lightingCache );
 352                 tri->lightingCache = NULL;
 353         }
 354         if ( tri->indexCache ) {
 355                 vertexCache.Free( tri->indexCache );
 356                 tri->indexCache = NULL;
 357         }
 358         if ( tri->shadowCache && ( tri->shadowVertexes != NULL || tri->verts != NULL ) ) {
 359                 // if we don't have tri->shadowVertexes, these are a reference to a
 360                 // shadowCache on the original surface, which a vertex program
 361                 // will take care of making unique for each light
 362                 vertexCache.Free( tri->shadowCache );
 363                 tri->shadowCache = NULL;
 364         }
 365 }
 366
 367 /*
 368 ==============
 369 R_ReallyFreeStaticTriSurf
 370
 371 This does the actual free
 372 ==============
 373 */
 374 void R_ReallyFreeStaticTriSurf( srfTriangles_t *tri ) {
 375         if ( !tri ) {
 376                 return;
 377         }
 378
 379         R_FreeStaticTriSurfVertexCaches( tri );
 380
 381         if ( tri->verts != NULL ) {
 382                 // R_CreateLightTris points tri->verts at the verts of the ambient surface
 383                 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
 384                         triVertexAllocator.Free( tri->verts );
 385                 }
 386         }
 387
 388         if ( !tri->deformedSurface ) {
 389                 if ( tri->indexes != NULL ) {
 390                         // if a surface is completely inside a light volume R_CreateLightTris points tri->indexes at the indexes of the ambient surface
 391                         if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
 392                                 triIndexAllocator.Free( tri->indexes );
 393                         }
 394                 }
 395                 if ( tri->silIndexes != NULL ) {
 396                         triSilIndexAllocator.Free( tri->silIndexes );
 397                 }
 398                 if ( tri->silEdges != NULL ) {
 399                         triSilEdgeAllocator.Free( tri->silEdges );
 400                 }
 401                 if ( tri->dominantTris != NULL ) {
 402                         triDominantTrisAllocator.Free( tri->dominantTris );
 403                 }
 404                 if ( tri->mirroredVerts != NULL ) {
 405                         triMirroredVertAllocator.Free( tri->mirroredVerts );
 406                 }
 407                 if ( tri->dupVerts != NULL ) {
 408                         triDupVertAllocator.Free( tri->dupVerts );
 409                 }
 410         }
 411
 412         if ( tri->facePlanes != NULL ) {
 413                 triPlaneAllocator.Free( tri->facePlanes );
 414         }
 415
 416         if ( tri->shadowVertexes != NULL ) {
 417                 triShadowVertexAllocator.Free( tri->shadowVertexes );
 418         }
 419
 420 #ifdef _DEBUG
 421         memset( tri, 0, sizeof( srfTriangles_t ) );
 422 #endif
 423
 424         srfTrianglesAllocator.Free( tri );
 425 }
 426
 427 /*
 428 ==============
 429 R_CheckStaticTriSurfMemory
 430 ==============
 431 */
 432 void R_CheckStaticTriSurfMemory( const srfTriangles_t *tri ) {
 433         if ( !tri ) {
 434                 return;
 435         }
 436
 437         if ( tri->verts != NULL ) {
 438                 // R_CreateLightTris points tri->verts at the verts of the ambient surface
 439                 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
 440                         const char *error = triVertexAllocator.CheckMemory( tri->verts );
 441                         assert( error == NULL );
 442                 }
 443         }
 444
 445         if ( !tri->deformedSurface ) {
 446                 if ( tri->indexes != NULL ) {
 447                         // if a surface is completely inside a light volume R_CreateLightTris points tri->indexes at the indexes of the ambient surface
 448                         if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
 449                                 const char *error = triIndexAllocator.CheckMemory( tri->indexes );
 450                                 assert( error == NULL );
 451                         }
 452                 }
 453         }
 454
 455         if ( tri->shadowVertexes != NULL ) {
 456                 const char *error = triShadowVertexAllocator.CheckMemory( tri->shadowVertexes );
 457                 assert( error == NULL );
 458         }
 459 }
 460
 461 /*
 462 ==================
 463 R_FreeDeferredTriSurfs
 464 ==================
 465 */
 466 void R_FreeDeferredTriSurfs( frameData_t *frame ) {
 467         srfTriangles_t  *tri, *next;
 468
 469         if ( !frame ) {
 470                 return;
 471         }
 472
 473         for ( tri = frame->firstDeferredFreeTriSurf; tri; tri = next ) {
 474                 next = tri->nextDeferredFree;
 475                 R_ReallyFreeStaticTriSurf( tri );
 476         }
 477
 478         frame->firstDeferredFreeTriSurf = NULL;
 479         frame->lastDeferredFreeTriSurf = NULL;
 480 }
 481
 482 /*
 483 ==============
 484 R_FreeStaticTriSurf
 485
 486 This will defer the free until the current frame has run through the back end.
 487 ==============
 488 */
 489 void R_FreeStaticTriSurf( srfTriangles_t *tri ) {
 490         frameData_t             *frame;
 491
 492         if ( !tri ) {
 493                 return;
 494         }
 495
 496         if ( tri->nextDeferredFree ) {
 497                 common->Error( "R_FreeStaticTriSurf: freed a freed triangle" );
 498         }
 499         frame = frameData;
 500
 501         if ( !frame ) {
 502                 // command line utility, or rendering in editor preview mode ( force )
 503                 R_ReallyFreeStaticTriSurf( tri );
 504         } else {
 505 #ifdef ID_DEBUG_MEMORY
 506                 R_CheckStaticTriSurfMemory( tri );
 507 #endif
 508                 tri->nextDeferredFree = NULL;
 509                 if ( frame->lastDeferredFreeTriSurf ) {
 510                         frame->lastDeferredFreeTriSurf->nextDeferredFree = tri;
 511                 } else {
 512                         frame->firstDeferredFreeTriSurf = tri;
 513                 }
 514                 frame->lastDeferredFreeTriSurf = tri;
 515         }
 516 }
 517
 518 /*
 519 ==============
 520 R_AllocStaticTriSurf
 521 ==============
 522 */
 523 srfTriangles_t *R_AllocStaticTriSurf( void ) {
 524         srfTriangles_t *tris = srfTrianglesAllocator.Alloc();
 525         memset( tris, 0, sizeof( srfTriangles_t ) );
 526         return tris;
 527 }
 528
 529 /*
 530 =================
 531 R_CopyStaticTriSurf
 532
 533 This only duplicates the indexes and verts, not any of the derived data.
 534 =================
 535 */
 536 srfTriangles_t *R_CopyStaticTriSurf( const srfTriangles_t *tri ) {
 537         srfTriangles_t  *newTri;
 538
 539         newTri = R_AllocStaticTriSurf();
 540         R_AllocStaticTriSurfVerts( newTri, tri->numVerts );
 541         R_AllocStaticTriSurfIndexes( newTri, tri->numIndexes );
 542         newTri->numVerts = tri->numVerts;
 543         newTri->numIndexes = tri->numIndexes;
 544         memcpy( newTri->verts, tri->verts, tri->numVerts * sizeof( newTri->verts[0] ) );
 545         memcpy( newTri->indexes, tri->indexes, tri->numIndexes * sizeof( newTri->indexes[0] ) );
 546
 547         return newTri;
 548 }
 549
 550 /*
 551 =================
 552 R_AllocStaticTriSurfVerts
 553 =================
 554 */
 555 void R_AllocStaticTriSurfVerts( srfTriangles_t *tri, int numVerts ) {
 556         assert( tri->verts == NULL );
 557         tri->verts = triVertexAllocator.Alloc( numVerts );
 558 }
 559
 560 /*
 561 =================
 562 R_AllocStaticTriSurfIndexes
 563 =================
 564 */
 565 void R_AllocStaticTriSurfIndexes( srfTriangles_t *tri, int numIndexes ) {
 566         assert( tri->indexes == NULL );
 567         tri->indexes = triIndexAllocator.Alloc( numIndexes );
 568 }
 569
 570 /*
 571 =================
 572 R_AllocStaticTriSurfShadowVerts
 573 =================
 574 */
 575 void R_AllocStaticTriSurfShadowVerts( srfTriangles_t *tri, int numVerts ) {
 576         assert( tri->shadowVertexes == NULL );
 577         tri->shadowVertexes = triShadowVertexAllocator.Alloc( numVerts );
 578 }
 579
 580 /*
 581 =================
 582 R_AllocStaticTriSurfPlanes
 583 =================
 584 */
 585 void R_AllocStaticTriSurfPlanes( srfTriangles_t *tri, int numIndexes ) {
 586         if ( tri->facePlanes ) {
 587                 triPlaneAllocator.Free( tri->facePlanes );
 588         }
 589         tri->facePlanes = triPlaneAllocator.Alloc( numIndexes / 3 );
 590 }
 591
 592 /*
 593 =================
 594 R_ResizeStaticTriSurfVerts
 595 =================
 596 */
 597 void R_ResizeStaticTriSurfVerts( srfTriangles_t *tri, int numVerts ) {
 598 #ifdef USE_TRI_DATA_ALLOCATOR
 599         tri->verts = triVertexAllocator.Resize( tri->verts, numVerts );
 600 #else
 601         assert( false );
 602 #endif
 603 }
 604
 605 /*
 606 =================
 607 R_ResizeStaticTriSurfIndexes
 608 =================
 609 */
 610 void R_ResizeStaticTriSurfIndexes( srfTriangles_t *tri, int numIndexes ) {
 611 #ifdef USE_TRI_DATA_ALLOCATOR
 612         tri->indexes = triIndexAllocator.Resize( tri->indexes, numIndexes );
 613 #else
 614         assert( false );
 615 #endif
 616 }
 617
 618 /*
 619 =================
 620 R_ResizeStaticTriSurfShadowVerts
 621 =================
 622 */
 623 void R_ResizeStaticTriSurfShadowVerts( srfTriangles_t *tri, int numVerts ) {
 624 #ifdef USE_TRI_DATA_ALLOCATOR
 625         tri->shadowVertexes = triShadowVertexAllocator.Resize( tri->shadowVertexes, numVerts );
 626 #else
 627         assert( false );
 628 #endif
 629 }
 630
 631 /*
 632 =================
 633 R_ReferenceStaticTriSurfVerts
 634 =================
 635 */
 636 void R_ReferenceStaticTriSurfVerts( srfTriangles_t *tri, const srfTriangles_t *reference ) {
 637         tri->verts = reference->verts;
 638 }
 639
 640 /*
 641 =================
 642 R_ReferenceStaticTriSurfIndexes
 643 =================
 644 */
 645 void R_ReferenceStaticTriSurfIndexes( srfTriangles_t *tri, const srfTriangles_t *reference ) {
 646         tri->indexes = reference->indexes;
 647 }
 648
 649 /*
 650 =================
 651 R_FreeStaticTriSurfSilIndexes
 652 =================
 653 */
 654 void R_FreeStaticTriSurfSilIndexes( srfTriangles_t *tri ) {
 655         triSilIndexAllocator.Free( tri->silIndexes );
 656         tri->silIndexes = NULL;
 657 }
 658
 659 /*
 660 ===============
 661 R_RangeCheckIndexes
 662
 663 Check for syntactically incorrect indexes, like out of range values.
 664 Does not check for semantics, like degenerate triangles.
 665
 666 No vertexes is acceptable if no indexes.
 667 No indexes is acceptable.
 668 More vertexes than are referenced by indexes are acceptable.
 669 ===============
 670 */
 671 void R_RangeCheckIndexes( const srfTriangles_t *tri ) {
 672         int             i;
 673
 674         if ( tri->numIndexes < 0 ) {
 675                 common->Error( "R_RangeCheckIndexes: numIndexes < 0" );
 676         }
 677         if ( tri->numVerts < 0 ) {
 678                 common->Error( "R_RangeCheckIndexes: numVerts < 0" );
 679         }
 680
 681         // must specify an integral number of triangles
 682         if ( tri->numIndexes % 3 != 0 ) {
 683                 common->Error( "R_RangeCheckIndexes: numIndexes %% 3" );
 684         }
 685
 686         for ( i = 0 ; i < tri->numIndexes ; i++ ) {
 687                 if ( tri->indexes[i] < 0 || tri->indexes[i] >= tri->numVerts ) {
 688                         common->Error( "R_RangeCheckIndexes: index out of range" );
 689                 }
 690         }
 691
 692         // this should not be possible unless there are unused verts
 693         if ( tri->numVerts > tri->numIndexes ) {
 694                 // FIXME: find the causes of these
 695                 // common->Printf( "R_RangeCheckIndexes: tri->numVerts > tri->numIndexes\n" );
 696         }
 697 }
 698
 699 /*
 700 =================
 701 R_BoundTriSurf
 702 =================
 703 */
 704 void R_BoundTriSurf( srfTriangles_t *tri ) {
 705         SIMDProcessor->MinMax( tri->bounds[0], tri->bounds[1], tri->verts, tri->numVerts );
 706 }
 707
 708 /*
 709 =================
 710 R_CreateSilRemap
 711 =================
 712 */
 713 static int *R_CreateSilRemap( const srfTriangles_t *tri ) {
 714         int             c_removed, c_unique;
 715         int             *remap;
 716         int             i, j, hashKey;
 717         const idDrawVert *v1, *v2;
 718
 719         remap = (int *)R_ClearedStaticAlloc( tri->numVerts * sizeof( remap[0] ) );
 720
 721         if ( !r_useSilRemap.GetBool() ) {
 722                 for ( i = 0 ; i < tri->numVerts ; i++ ) {
 723                         remap[i] = i;
 724                 }
 725                 return remap;
 726         }
 727
 728         idHashIndex             hash( 1024, tri->numVerts );
 729
 730         c_removed = 0;
 731         c_unique = 0;
 732         for ( i = 0 ; i < tri->numVerts ; i++ ) {
 733                 v1 = &tri->verts[i];
 734
 735                 // see if there is an earlier vert that it can map to
 736                 hashKey = hash.GenerateKey( v1->xyz );
 737                 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) {
 738                         v2 = &tri->verts[j];
 739                         if ( v2->xyz[0] == v1->xyz[0]
 740                                 && v2->xyz[1] == v1->xyz[1]
 741                                 && v2->xyz[2] == v1->xyz[2] ) {
 742                                 c_removed++;
 743                                 remap[i] = j;
 744                                 break;
 745                         }
 746                 }
 747                 if ( j < 0 ) {
 748                         c_unique++;
 749                         remap[i] = i;
 750                         hash.Add( hashKey, i );
 751                 }
 752         }
 753
 754         return remap;
 755 }
 756
 757 /*
 758 =================
 759 R_CreateSilIndexes
 760
 761 Uniquing vertexes only on xyz before creating sil edges reduces
 762 the edge count by about 20% on Q3 models
 763 =================
 764 */
 765 void R_CreateSilIndexes( srfTriangles_t *tri ) {
 766         int             i;
 767         int             *remap;
 768
 769         if ( tri->silIndexes ) {
 770                 triSilIndexAllocator.Free( tri->silIndexes );
 771                 tri->silIndexes = NULL;
 772         }
 773
 774         remap = R_CreateSilRemap( tri );
 775
 776         // remap indexes to the first one
 777         tri->silIndexes = triSilIndexAllocator.Alloc( tri->numIndexes );
 778         for ( i = 0; i < tri->numIndexes; i++ ) {
 779                 tri->silIndexes[i] = remap[tri->indexes[i]];
 780         }
 781
 782         R_StaticFree( remap );
 783 }
 784
 785 /*
 786 =====================
 787 R_CreateDupVerts
 788 =====================
 789 */
 790 void R_CreateDupVerts( srfTriangles_t *tri ) {
 791         int i;
 792
 793         int *remap = (int *) _alloca16( tri->numVerts * sizeof( remap[0] ) );
 794
 795         // initialize vertex remap in case there are unused verts
 796         for ( i = 0; i < tri->numVerts; i++ ) {
 797                 remap[i] = i;
 798         }
 799
 800         // set the remap based on how the silhouette indexes are remapped
 801         for ( i = 0; i < tri->numIndexes; i++ ) {
 802                 remap[tri->indexes[i]] = tri->silIndexes[i];
 803         }
 804
 805         // create duplicate vertex index based on the vertex remap
 806         int * tempDupVerts = (int *) _alloca16( tri->numVerts * 2 * sizeof( tempDupVerts[0] ) );
 807         tri->numDupVerts = 0;
 808         for ( i = 0; i < tri->numVerts; i++ ) {
 809                 if ( remap[i] != i ) {
 810                         tempDupVerts[tri->numDupVerts*2+0] = i;
 811                         tempDupVerts[tri->numDupVerts*2+1] = remap[i];
 812                         tri->numDupVerts++;
 813                 }
 814         }
 815
 816         tri->dupVerts = triDupVertAllocator.Alloc( tri->numDupVerts * 2 );
 817         memcpy( tri->dupVerts, tempDupVerts, tri->numDupVerts * 2 * sizeof( tri->dupVerts[0] ) );
 818 }
 819
 820 /*
 821 =====================
 822 R_DeriveFacePlanes
 823
 824 Writes the facePlanes values, overwriting existing ones if present
 825 =====================
 826 */
 827 void R_DeriveFacePlanes( srfTriangles_t *tri ) {
 828         idPlane *       planes;
 829
 830         if ( !tri->facePlanes ) {
 831                 R_AllocStaticTriSurfPlanes( tri, tri->numIndexes );
 832         }
 833         planes = tri->facePlanes;
 834
 835 #if 1
 836
 837         SIMDProcessor->DeriveTriPlanes( planes, tri->verts, tri->numVerts, tri->indexes, tri->numIndexes );
 838
 839 #else
 840
 841         for ( int i = 0; i < tri->numIndexes; i+= 3, planes++ ) {
 842                 int             i1, i2, i3;
 843                 idVec3  d1, d2, normal;
 844                 idVec3  *v1, *v2, *v3;
 845
 846                 i1 = tri->indexes[i + 0];
 847                 i2 = tri->indexes[i + 1];
 848                 i3 = tri->indexes[i + 2];
 849
 850                 v1 = &tri->verts[i1].xyz;
 851                 v2 = &tri->verts[i2].xyz;
 852                 v3 = &tri->verts[i3].xyz;
 853
 854                 d1[0] = v2->x - v1->x;
 855                 d1[1] = v2->y - v1->y;
 856                 d1[2] = v2->z - v1->z;
 857
 858                 d2[0] = v3->x - v1->x;
 859                 d2[1] = v3->y - v1->y;
 860                 d2[2] = v3->z - v1->z;
 861
 862                 normal[0] = d2.y * d1.z - d2.z * d1.y;
 863                 normal[1] = d2.z * d1.x - d2.x * d1.z;
 864                 normal[2] = d2.x * d1.y - d2.y * d1.x;
 865
 866                 float sqrLength, invLength;
 867
 868                 sqrLength = normal.x * normal.x + normal.y * normal.y + normal.z * normal.z;
 869                 invLength = idMath::RSqrt( sqrLength );
 870
 871                 (*planes)[0] = normal[0] * invLength;
 872                 (*planes)[1] = normal[1] * invLength;
 873                 (*planes)[2] = normal[2] * invLength;
 874
 875                 planes->FitThroughPoint( *v1 );
 876         }
 877
 878 #endif
 879
 880         tri->facePlanesCalculated = true;
 881 }
 882
 883 /*
 884 =====================
 885 R_CreateVertexNormals
 886
 887 Averages together the contributions of all faces that are
 888 used by a vertex, creating drawVert->normal
 889 =====================
 890 */
 891 void R_CreateVertexNormals( srfTriangles_t *tri ) {
 892         int             i, j;
 893         const idPlane *planes;
 894
 895         for ( i = 0 ; i < tri->numVerts ; i++ ) {
 896                 tri->verts[i].normal.Zero();
 897         }
 898
 899         if ( !tri->facePlanes || !tri->facePlanesCalculated ) {
 900                 R_DeriveFacePlanes( tri );
 901         }
 902         if ( !tri->silIndexes ) {
 903                 R_CreateSilIndexes( tri );
 904         }
 905         planes = tri->facePlanes;
 906         for ( i = 0 ; i < tri->numIndexes ; i += 3, planes++ ) {
 907                 for ( j = 0 ; j < 3 ; j++ ) {
 908                         int index = tri->silIndexes[i+j];
 909                         tri->verts[index].normal += planes->Normal();
 910                 }
 911         }
 912
 913         // normalize and replicate from silIndexes to all indexes
 914         for ( i = 0 ; i < tri->numIndexes ; i++ ) {
 915                 tri->verts[tri->indexes[i]].normal = tri->verts[tri->silIndexes[i]].normal;
 916                 tri->verts[tri->indexes[i]].normal.Normalize();
 917         }
 918 }
 919
 920 /*
 921 ===============
 922 R_DefineEdge
 923 ===============
 924 */
 925 static int c_duplicatedEdges, c_tripledEdges;
 926
 927 static void R_DefineEdge( int v1, int v2, int planeNum ) {
 928         int             i, hashKey;
 929
 930         // check for degenerate edge
 931         if ( v1 == v2 ) {
 932                 return;
 933         }
 934         hashKey = silEdgeHash.GenerateKey( v1, v2 );
 935         // search for a matching other side
 936         for ( i = silEdgeHash.First( hashKey ); i >= 0 && i < MAX_SIL_EDGES; i = silEdgeHash.Next( i ) ) {
 937                 if ( silEdges[i].v1 == v1 && silEdges[i].v2 == v2 ) {
 938                         c_duplicatedEdges++;
 939                         // allow it to still create a new edge
 940                         continue;
 941                 }
 942                 if ( silEdges[i].v2 == v1 && silEdges[i].v1 == v2 ) {
 943                         if ( silEdges[i].p2 != numPlanes )  {
 944                                 c_tripledEdges++;
 945                                 // allow it to still create a new edge
 946                                 continue;
 947                         }
 948                         // this is a matching back side
 949                         silEdges[i].p2 = planeNum;
 950                         return;
 951                 }
 952
 953         }
 954
 955         // define the new edge
 956         if ( numSilEdges == MAX_SIL_EDGES ) {
 957                 common->DWarning( "MAX_SIL_EDGES" );
 958                 return;
 959         }
 960
 961         silEdgeHash.Add( hashKey, numSilEdges );
 962
 963         silEdges[numSilEdges].p1 = planeNum;
 964         silEdges[numSilEdges].p2 = numPlanes;
 965         silEdges[numSilEdges].v1 = v1;
 966         silEdges[numSilEdges].v2 = v2;
 967
 968         numSilEdges++;
 969 }
 970
 971 /*
 972 =================
 973 SilEdgeSort
 974 =================
 975 */
 976 static int SilEdgeSort( const void *a, const void *b ) {
 977         if ( ((silEdge_t *)a)->p1 < ((silEdge_t *)b)->p1 ) {
 978                 return -1;
 979         }
 980         if ( ((silEdge_t *)a)->p1 > ((silEdge_t *)b)->p1 ) {
 981                 return 1;
 982         }
 983         if ( ((silEdge_t *)a)->p2 < ((silEdge_t *)b)->p2 ) {
 984                 return -1;
 985         }
 986         if ( ((silEdge_t *)a)->p2 > ((silEdge_t *)b)->p2 ) {
 987                 return 1;
 988         }
 989         return 0;
 990 }
 991
 992 /*
 993 =================
 994 R_IdentifySilEdges
 995
 996 If the surface will not deform, coplanar edges (polygon interiors)
 997 can never create silhouette plains, and can be omited
 998 =================
 999 */
1000 int     c_coplanarSilEdges;
1001 int     c_totalSilEdges;
1002
1003 void R_IdentifySilEdges( srfTriangles_t *tri, bool omitCoplanarEdges ) {
1004         int             i;
1005         int             numTris;
1006         int             shared, single;
1007
1008         omitCoplanarEdges = false;      // optimization doesn't work for some reason
1009
1010         numTris = tri->numIndexes / 3;
1011
1012         numSilEdges = 0;
1013         silEdgeHash.Clear();
1014         numPlanes = numTris;
1015
1016         c_duplicatedEdges = 0;
1017         c_tripledEdges = 0;
1018
1019         for ( i = 0 ; i < numTris ; i++ ) {
1020                 int             i1, i2, i3;
1021
1022                 i1 = tri->silIndexes[ i*3 + 0 ];
1023                 i2 = tri->silIndexes[ i*3 + 1 ];
1024                 i3 = tri->silIndexes[ i*3 + 2 ];
1025
1026                 // create the edges
1027                 R_DefineEdge( i1, i2, i );
1028                 R_DefineEdge( i2, i3, i );
1029                 R_DefineEdge( i3, i1, i );
1030         }
1031
1032         if ( c_duplicatedEdges || c_tripledEdges ) {
1033                 common->DWarning( "%i duplicated edge directions, %i tripled edges", c_duplicatedEdges, c_tripledEdges );
1034         }
1035
1036         // if we know that the vertexes aren't going
1037         // to deform, we can remove interior triangulation edges
1038         // on otherwise planar polygons.
1039         // I earlier believed that I could also remove concave
1040         // edges, because they are never silhouettes in the conventional sense,
1041         // but they are still needed to balance out all the true sil edges
1042         // for the shadow algorithm to function
1043         int             c_coplanarCulled;
1044
1045         c_coplanarCulled = 0;
1046         if ( omitCoplanarEdges ) {
1047                 for ( i = 0 ; i < numSilEdges ; i++ ) {
1048                         int                     i1, i2, i3;
1049                         idPlane         plane;
1050                         int                     base;
1051                         int                     j;
1052                         float           d;
1053
1054                         if ( silEdges[i].p2 == numPlanes ) {    // the fake dangling edge
1055                                 continue;
1056                         }
1057
1058                         base = silEdges[i].p1 * 3;
1059                         i1 = tri->silIndexes[ base + 0 ];
1060                         i2 = tri->silIndexes[ base + 1 ];
1061                         i3 = tri->silIndexes[ base + 2 ];
1062
1063                         plane.FromPoints( tri->verts[i1].xyz, tri->verts[i2].xyz, tri->verts[i3].xyz );
1064
1065                         // check to see if points of second triangle are not coplanar
1066                         base = silEdges[i].p2 * 3;
1067                         for ( j = 0 ; j < 3 ; j++ ) {
1068                                 i1 = tri->silIndexes[ base + j ];
1069                                 d = plane.Distance( tri->verts[i1].xyz );
1070                                 if ( d != 0 ) {         // even a small epsilon causes problems
1071                                         break;
1072                                 }
1073                         }
1074
1075                         if ( j == 3 ) {
1076                                 // we can cull this sil edge
1077                                 memmove( &silEdges[i], &silEdges[i+1], (numSilEdges-i-1) * sizeof( silEdges[i] ) );
1078                                 c_coplanarCulled++;
1079                                 numSilEdges--;
1080                                 i--;
1081                         }
1082                 }
1083                 if ( c_coplanarCulled ) {
1084                         c_coplanarSilEdges += c_coplanarCulled;
1085 //                      common->Printf( "%i of %i sil edges coplanar culled\n", c_coplanarCulled,
1086 //                              c_coplanarCulled + numSilEdges );
1087                 }
1088         }
1089         c_totalSilEdges += numSilEdges;
1090
1091         // sort the sil edges based on plane number
1092         qsort( silEdges, numSilEdges, sizeof( silEdges[0] ), SilEdgeSort );
1093
1094         // count up the distribution.
1095         // a perfectly built model should only have shared
1096         // edges, but most models will have some interpenetration
1097         // and dangling edges
1098         shared = 0;
1099         single = 0;
1100         for ( i = 0 ; i < numSilEdges ; i++ ) {
1101                 if ( silEdges[i].p2 == numPlanes ) {
1102                         single++;
1103                 } else {
1104                         shared++;
1105                 }
1106         }
1107
1108         if ( !single ) {
1109                 tri->perfectHull = true;
1110         } else {
1111                 tri->perfectHull = false;
1112         }
1113
1114         tri->numSilEdges = numSilEdges;
1115         tri->silEdges = triSilEdgeAllocator.Alloc( numSilEdges );
1116         memcpy( tri->silEdges, silEdges, numSilEdges * sizeof( tri->silEdges[0] ) );
1117 }
1118
1119 /*
1120 ===============
1121 R_FaceNegativePolarity
1122
1123 Returns true if the texture polarity of the face is negative, false if it is positive or zero
1124 ===============
1125 */
1126 static bool R_FaceNegativePolarity( const srfTriangles_t *tri, int firstIndex ) {
1127         idDrawVert      *a, *b, *c;
1128         float   area;
1129         float           d0[5], d1[5];
1130
1131         a = tri->verts + tri->indexes[firstIndex + 0];
1132         b = tri->verts + tri->indexes[firstIndex + 1];
1133         c = tri->verts + tri->indexes[firstIndex + 2];
1134
1135         d0[3] = b->st[0] - a->st[0];
1136         d0[4] = b->st[1] - a->st[1];
1137
1138         d1[3] = c->st[0] - a->st[0];
1139         d1[4] = c->st[1] - a->st[1];
1140
1141         area = d0[3] * d1[4] - d0[4] * d1[3];
1142         if ( area >= 0 ) {
1143                 return false;
1144         }
1145         return true;
1146 }
1147
1148 /*
1149 ==================
1150 R_DeriveFaceTangents
1151 ==================
1152 */
1153 typedef struct {
1154         idVec3          tangents[2];
1155         bool    negativePolarity;
1156         bool    degenerate;
1157 } faceTangents_t;
1158
1159 static void     R_DeriveFaceTangents( const srfTriangles_t *tri, faceTangents_t *faceTangents ) {
1160         int             i;
1161         int                     c_textureDegenerateFaces;
1162         int                     c_positive, c_negative;
1163         faceTangents_t  *ft;
1164         idDrawVert      *a, *b, *c;
1165
1166         //
1167         // calculate tangent vectors for each face in isolation
1168         //
1169         c_positive = 0;
1170         c_negative = 0;
1171         c_textureDegenerateFaces = 0;
1172         for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1173                 float   area;
1174                 idVec3  temp;
1175                 float           d0[5], d1[5];
1176
1177                 ft = &faceTangents[i/3];
1178
1179                 a = tri->verts + tri->indexes[i + 0];
1180                 b = tri->verts + tri->indexes[i + 1];
1181                 c = tri->verts + tri->indexes[i + 2];
1182
1183                 d0[0] = b->xyz[0] - a->xyz[0];
1184                 d0[1] = b->xyz[1] - a->xyz[1];
1185                 d0[2] = b->xyz[2] - a->xyz[2];
1186                 d0[3] = b->st[0] - a->st[0];
1187                 d0[4] = b->st[1] - a->st[1];
1188
1189                 d1[0] = c->xyz[0] - a->xyz[0];
1190                 d1[1] = c->xyz[1] - a->xyz[1];
1191                 d1[2] = c->xyz[2] - a->xyz[2];
1192                 d1[3] = c->st[0] - a->st[0];
1193                 d1[4] = c->st[1] - a->st[1];
1194
1195                 area = d0[3] * d1[4] - d0[4] * d1[3];
1196                 if ( fabs( area ) < 1e-20f ) {
1197                         ft->negativePolarity = false;
1198                         ft->degenerate = true;
1199                         ft->tangents[0].Zero();
1200                         ft->tangents[1].Zero();
1201                         c_textureDegenerateFaces++;
1202                         continue;
1203                 }
1204                 if ( area > 0.0f ) {
1205                         ft->negativePolarity = false;
1206                         c_positive++;
1207                 } else {
1208                         ft->negativePolarity = true;
1209                         c_negative++;
1210                 }
1211                 ft->degenerate = false;
1212
1213 #ifdef USE_INVA
1214                 float inva = area < 0.0f ? -1 : 1;              // was = 1.0f / area;
1215
1216         temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
1217         temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
1218         temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
1219                 temp.Normalize();
1220                 ft->tangents[0] = temp;
1221
1222         temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
1223         temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
1224         temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
1225                 temp.Normalize();
1226                 ft->tangents[1] = temp;
1227 #else
1228         temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]);
1229         temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]);
1230         temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]);
1231                 temp.Normalize();
1232                 ft->tangents[0] = temp;
1233
1234         temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]);
1235         temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]);
1236         temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]);
1237                 temp.Normalize();
1238                 ft->tangents[1] = temp;
1239 #endif
1240         }
1241 }
1242
1243
1244
1245 /*
1246 ===================
1247 R_DuplicateMirroredVertexes
1248
1249 Modifies the surface to bust apart any verts that are shared by both positive and
1250 negative texture polarities, so tangent space smoothing at the vertex doesn't
1251 degenerate.
1252
1253 This will create some identical vertexes (which will eventually get different tangent
1254 vectors), so never optimize the resulting mesh, or it will get the mirrored edges back.
1255
1256 Reallocates tri->verts and changes tri->indexes in place
1257 Silindexes are unchanged by this.
1258
1259 sets mirroredVerts and mirroredVerts[]
1260
1261 ===================
1262 */
1263 typedef struct {
1264         bool    polarityUsed[2];
1265         int                     negativeRemap;
1266 } tangentVert_t;
1267
1268 static void     R_DuplicateMirroredVertexes( srfTriangles_t *tri ) {
1269         tangentVert_t   *tverts, *vert;
1270         int                             i, j;
1271         int                             totalVerts;
1272         int                             numMirror;
1273
1274         tverts = (tangentVert_t *)_alloca16( tri->numVerts * sizeof( *tverts ) );
1275         memset( tverts, 0, tri->numVerts * sizeof( *tverts ) );
1276
1277         // determine texture polarity of each surface
1278
1279         // mark each vert with the polarities it uses
1280         for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1281                 int     polarity;
1282
1283                 polarity = R_FaceNegativePolarity( tri, i );
1284                 for ( j = 0 ; j < 3 ; j++ ) {
1285                         tverts[tri->indexes[i+j]].polarityUsed[ polarity ] = true;
1286                 }
1287         }
1288
1289         // now create new verts as needed
1290         totalVerts = tri->numVerts;
1291         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1292                 vert = &tverts[i];
1293                 if ( vert->polarityUsed[0] && vert->polarityUsed[1] ) {
1294                         vert->negativeRemap = totalVerts;
1295                         totalVerts++;
1296                 }
1297         }
1298
1299         tri->numMirroredVerts = totalVerts - tri->numVerts;
1300
1301         // now create the new list
1302         if ( totalVerts == tri->numVerts ) {
1303                 tri->mirroredVerts = NULL;
1304                 return;
1305         }
1306
1307         tri->mirroredVerts = triMirroredVertAllocator.Alloc( tri->numMirroredVerts );
1308
1309 #ifdef USE_TRI_DATA_ALLOCATOR
1310         tri->verts = triVertexAllocator.Resize( tri->verts, totalVerts );
1311 #else
1312         idDrawVert *oldVerts = tri->verts;
1313         R_AllocStaticTriSurfVerts( tri, totalVerts );
1314         memcpy( tri->verts, oldVerts, tri->numVerts * sizeof( tri->verts[0] ) );
1315         triVertexAllocator.Free( oldVerts );
1316 #endif
1317
1318         // create the duplicates
1319         numMirror = 0;
1320         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1321                 j = tverts[i].negativeRemap;
1322                 if ( j ) {
1323                         tri->verts[j] = tri->verts[i];
1324                         tri->mirroredVerts[numMirror] = i;
1325                         numMirror++;
1326                 }
1327         }
1328
1329         tri->numVerts = totalVerts;
1330         // change the indexes
1331         for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1332                 if ( tverts[tri->indexes[i]].negativeRemap &&
1333                         R_FaceNegativePolarity( tri, 3*(i/3) ) ) {
1334                         tri->indexes[i] = tverts[tri->indexes[i]].negativeRemap;
1335                 }
1336         }
1337
1338         tri->numVerts = totalVerts;
1339 }
1340
1341 /*
1342 =================
1343 R_DeriveTangentsWithoutNormals
1344
1345 Build texture space tangents for bump mapping
1346 If a surface is deformed, this must be recalculated
1347
1348 This assumes that any mirrored vertexes have already been duplicated, so
1349 any shared vertexes will have the tangent spaces smoothed across.
1350
1351 Texture wrapping slightly complicates this, but as long as the normals
1352 are shared, and the tangent vectors are projected onto the normals, the
1353 separate vertexes should wind up with identical tangent spaces.
1354
1355 mirroring a normalmap WILL cause a slightly visible seam unless the normals
1356 are completely flat around the edge's full bilerp support.
1357
1358 Vertexes which are smooth shaded must have their tangent vectors
1359 in the same plane, which will allow a seamless
1360 rendering as long as the normal map is even on both sides of the
1361 seam.
1362
1363 A smooth shaded surface may have multiple tangent vectors at a vertex
1364 due to texture seams or mirroring, but it should only have a single
1365 normal vector.
1366
1367 Each triangle has a pair of tangent vectors in it's plane
1368
1369 Should we consider having vertexes point at shared tangent spaces
1370 to save space or speed transforms?
1371
1372 this version only handles bilateral symetry
1373 =================
1374 */
1375 void R_DeriveTangentsWithoutNormals( srfTriangles_t *tri ) {
1376         int                     i, j;
1377         faceTangents_t  *faceTangents;
1378         faceTangents_t  *ft;
1379         idDrawVert              *vert;
1380
1381         faceTangents = (faceTangents_t *)_alloca16( sizeof(faceTangents[0]) * tri->numIndexes/3 );
1382         R_DeriveFaceTangents( tri, faceTangents );
1383
1384         // clear the tangents
1385         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1386                 tri->verts[i].tangents[0].Zero();
1387                 tri->verts[i].tangents[1].Zero();
1388         }
1389
1390         // sum up the neighbors
1391         for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1392                 ft = &faceTangents[i/3];
1393
1394                 // for each vertex on this face
1395                 for ( j = 0 ; j < 3 ; j++ ) {
1396                         vert = &tri->verts[tri->indexes[i+j]];
1397
1398                         vert->tangents[0] += ft->tangents[0];
1399                         vert->tangents[1] += ft->tangents[1];
1400                 }
1401         }
1402
1403 #if 0
1404         // sum up both sides of the mirrored verts
1405         // so the S vectors exactly mirror, and the T vectors are equal
1406         for ( i = 0 ; i < tri->numMirroredVerts ; i++ ) {
1407                 idDrawVert      *v1, *v2;
1408
1409                 v1 = &tri->verts[ tri->numVerts - tri->numMirroredVerts + i ];
1410                 v2 = &tri->verts[ tri->mirroredVerts[i] ];
1411
1412                 v1->tangents[0] -= v2->tangents[0];
1413                 v1->tangents[1] += v2->tangents[1];
1414
1415                 v2->tangents[0] = vec3_origin - v1->tangents[0];
1416                 v2->tangents[1] = v1->tangents[1];
1417         }
1418 #endif
1419
1420
1421         // project the summed vectors onto the normal plane
1422         // and normalize.  The tangent vectors will not necessarily
1423         // be orthogonal to each other, but they will be orthogonal
1424         // to the surface normal.
1425         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1426                 vert = &tri->verts[i];
1427                 for ( j = 0 ; j < 2 ; j++ ) {
1428                         float   d;
1429
1430                         d = vert->tangents[j] * vert->normal;
1431                         vert->tangents[j] = vert->tangents[j] - d * vert->normal;
1432                         vert->tangents[j].Normalize();
1433                 }
1434         }
1435
1436         tri->tangentsCalculated = true;
1437 }
1438
1439 static ID_INLINE void VectorNormalizeFast2( const idVec3 &v, idVec3 &out) {
1440         float   ilength;
1441
1442         ilength = idMath::RSqrt( v[0]*v[0] + v[1]*v[1] + v[2]*v[2] );
1443         out[0] = v[0] * ilength;
1444         out[1] = v[1] * ilength;
1445         out[2] = v[2] * ilength;
1446 }
1447
1448 /*
1449 ===================
1450 R_BuildDominantTris
1451
1452 Find the largest triangle that uses each vertex
1453 ===================
1454 */
1455 typedef struct {
1456         int             vertexNum;
1457         int             faceNum;
1458 } indexSort_t;
1459
1460 static int IndexSort( const void *a, const void *b ) {
1461         if ( ((indexSort_t *)a)->vertexNum < ((indexSort_t *)b)->vertexNum ) {
1462                 return -1;
1463         }
1464         if ( ((indexSort_t *)a)->vertexNum > ((indexSort_t *)b)->vertexNum ) {
1465                 return 1;
1466         }
1467         return 0;
1468 }
1469
1470 void R_BuildDominantTris( srfTriangles_t *tri ) {
1471         int i, j;
1472         dominantTri_t *dt;
1473         indexSort_t *ind = (indexSort_t *)R_StaticAlloc( tri->numIndexes * sizeof( *ind ) );
1474
1475         for ( i = 0; i < tri->numIndexes; i++ ) {
1476                 ind[i].vertexNum = tri->indexes[i];
1477                 ind[i].faceNum = i / 3;
1478         }
1479         qsort( ind, tri->numIndexes, sizeof( *ind ), IndexSort );
1480
1481         tri->dominantTris = dt = triDominantTrisAllocator.Alloc( tri->numVerts );
1482         memset( dt, 0, tri->numVerts * sizeof( dt[0] ) );
1483
1484         for ( i = 0; i < tri->numIndexes; i += j ) {
1485                 float   maxArea = 0;
1486                 int             vertNum = ind[i].vertexNum;
1487                 for ( j = 0; i + j < tri->numIndexes && ind[i+j].vertexNum == vertNum; j++ ) {
1488                         float           d0[5], d1[5];
1489                         idDrawVert      *a, *b, *c;
1490                         idVec3          normal, tangent, bitangent;
1491
1492                         int     i1 = tri->indexes[ind[i+j].faceNum * 3 + 0];
1493                         int     i2 = tri->indexes[ind[i+j].faceNum * 3 + 1];
1494                         int     i3 = tri->indexes[ind[i+j].faceNum * 3 + 2];
1495
1496                         a = tri->verts + i1;
1497                         b = tri->verts + i2;
1498                         c = tri->verts + i3;
1499
1500                         d0[0] = b->xyz[0] - a->xyz[0];
1501                         d0[1] = b->xyz[1] - a->xyz[1];
1502                         d0[2] = b->xyz[2] - a->xyz[2];
1503                         d0[3] = b->st[0] - a->st[0];
1504                         d0[4] = b->st[1] - a->st[1];
1505
1506                         d1[0] = c->xyz[0] - a->xyz[0];
1507                         d1[1] = c->xyz[1] - a->xyz[1];
1508                         d1[2] = c->xyz[2] - a->xyz[2];
1509                         d1[3] = c->st[0] - a->st[0];
1510                         d1[4] = c->st[1] - a->st[1];
1511
1512                         normal[0] = ( d1[1] * d0[2] - d1[2] * d0[1] );
1513                         normal[1] = ( d1[2] * d0[0] - d1[0] * d0[2] );
1514                         normal[2] = ( d1[0] * d0[1] - d1[1] * d0[0] );
1515
1516                         float area = normal.Length();
1517
1518                         // if this is smaller than what we already have, skip it
1519                         if ( area < maxArea ) {
1520                                 continue;
1521                         }
1522                         maxArea = area;
1523
1524                         if ( i1 == vertNum ) {
1525                                 dt[vertNum].v2 = i2;
1526                                 dt[vertNum].v3 = i3;
1527                         } else if ( i2 == vertNum ) {
1528                                 dt[vertNum].v2 = i3;
1529                                 dt[vertNum].v3 = i1;
1530                         } else {
1531                                 dt[vertNum].v2 = i1;
1532                                 dt[vertNum].v3 = i2;
1533                         }
1534
1535                         float   len = area;
1536                         if ( len < 0.001f ) {
1537                                 len = 0.001f;
1538                         }
1539                         dt[vertNum].normalizationScale[2] = 1.0f / len;         // normal
1540
1541                         // texture area
1542                         area = d0[3] * d1[4] - d0[4] * d1[3];
1543
1544                         tangent[0] = ( d0[0] * d1[4] - d0[4] * d1[0] );
1545                         tangent[1] = ( d0[1] * d1[4] - d0[4] * d1[1] );
1546                         tangent[2] = ( d0[2] * d1[4] - d0[4] * d1[2] );
1547                         len = tangent.Length();
1548                         if ( len < 0.001f ) {
1549                                 len = 0.001f;
1550                         }
1551                         dt[vertNum].normalizationScale[0] = ( area > 0 ? 1 : -1 ) / len;        // tangents[0]
1552
1553                         bitangent[0] = ( d0[3] * d1[0] - d0[0] * d1[3] );
1554                         bitangent[1] = ( d0[3] * d1[1] - d0[1] * d1[3] );
1555                         bitangent[2] = ( d0[3] * d1[2] - d0[2] * d1[3] );
1556                         len = bitangent.Length();
1557                         if ( len < 0.001f ) {
1558                                 len = 0.001f;
1559                         }
1560 #ifdef DERIVE_UNSMOOTHED_BITANGENT
1561                         dt[vertNum].normalizationScale[1] = ( area > 0 ? 1 : -1 );
1562 #else
1563                         dt[vertNum].normalizationScale[1] = ( area > 0 ? 1 : -1 ) / len;        // tangents[1]
1564 #endif
1565                 }
1566         }
1567
1568         R_StaticFree( ind );
1569 }
1570
1571 /*
1572 ====================
1573 R_DeriveUnsmoothedTangents
1574
1575 Uses the single largest area triangle for each vertex, instead of smoothing over all
1576 ====================
1577 */
1578 void R_DeriveUnsmoothedTangents( srfTriangles_t *tri ) {
1579         if ( tri->tangentsCalculated ) {
1580                 return;
1581         }
1582
1583 #if 1
1584
1585         SIMDProcessor->DeriveUnsmoothedTangents( tri->verts, tri->dominantTris, tri->numVerts );
1586
1587 #else
1588
1589         for ( int i = 0 ; i < tri->numVerts ; i++ ) {
1590                 idVec3          temp;
1591                 float           d0[5], d1[5];
1592                 idDrawVert      *a, *b, *c;
1593                 dominantTri_t   *dt = &tri->dominantTris[i];
1594
1595                 a = tri->verts + i;
1596                 b = tri->verts + dt->v2;
1597                 c = tri->verts + dt->v3;
1598
1599                 d0[0] = b->xyz[0] - a->xyz[0];
1600                 d0[1] = b->xyz[1] - a->xyz[1];
1601                 d0[2] = b->xyz[2] - a->xyz[2];
1602                 d0[3] = b->st[0] - a->st[0];
1603                 d0[4] = b->st[1] - a->st[1];
1604
1605                 d1[0] = c->xyz[0] - a->xyz[0];
1606                 d1[1] = c->xyz[1] - a->xyz[1];
1607                 d1[2] = c->xyz[2] - a->xyz[2];
1608                 d1[3] = c->st[0] - a->st[0];
1609                 d1[4] = c->st[1] - a->st[1];
1610
1611                 a->normal[0] = dt->normalizationScale[2] * ( d1[1] * d0[2] - d1[2] * d0[1] );
1612                 a->normal[1] = dt->normalizationScale[2] * ( d1[2] * d0[0] - d1[0] * d0[2] );
1613                 a->normal[2] = dt->normalizationScale[2] * ( d1[0] * d0[1] - d1[1] * d0[0] );
1614
1615                 a->tangents[0][0] = dt->normalizationScale[0] * ( d0[0] * d1[4] - d0[4] * d1[0] );
1616                 a->tangents[0][1] = dt->normalizationScale[0] * ( d0[1] * d1[4] - d0[4] * d1[1] );
1617                 a->tangents[0][2] = dt->normalizationScale[0] * ( d0[2] * d1[4] - d0[4] * d1[2] );
1618
1619 #ifdef DERIVE_UNSMOOTHED_BITANGENT
1620                 // derive the bitangent for a completely orthogonal axis,
1621                 // instead of using the texture T vector
1622                 a->tangents[1][0] = dt->normalizationScale[1] * ( a->normal[2] * a->tangents[0][1] - a->normal[1] * a->tangents[0][2] );
1623                 a->tangents[1][1] = dt->normalizationScale[1] * ( a->normal[0] * a->tangents[0][2] - a->normal[2] * a->tangents[0][0] );
1624                 a->tangents[1][2] = dt->normalizationScale[1] * ( a->normal[1] * a->tangents[0][0] - a->normal[0] * a->tangents[0][1] );
1625 #else
1626                 // calculate the bitangent from the texture T vector
1627                 a->tangents[1][0] = dt->normalizationScale[1] * ( d0[3] * d1[0] - d0[0] * d1[3] );
1628                 a->tangents[1][1] = dt->normalizationScale[1] * ( d0[3] * d1[1] - d0[1] * d1[3] );
1629                 a->tangents[1][2] = dt->normalizationScale[1] * ( d0[3] * d1[2] - d0[2] * d1[3] );
1630 #endif
1631         }
1632
1633 #endif
1634
1635         tri->tangentsCalculated = true;
1636 }
1637
1638 /*
1639 ==================
1640 R_DeriveTangents
1641
1642 This is called once for static surfaces, and every frame for deforming surfaces
1643
1644 Builds tangents, normals, and face planes
1645 ==================
1646 */
1647 void R_DeriveTangents( srfTriangles_t *tri, bool allocFacePlanes ) {
1648         int                             i;
1649         idPlane                 *planes;
1650
1651         if ( tri->dominantTris != NULL ) {
1652                 R_DeriveUnsmoothedTangents( tri );
1653                 return;
1654         }
1655
1656         if ( tri->tangentsCalculated ) {
1657                 return;
1658         }
1659
1660         tr.pc.c_tangentIndexes += tri->numIndexes;
1661
1662         if ( !tri->facePlanes && allocFacePlanes ) {
1663                 R_AllocStaticTriSurfPlanes( tri, tri->numIndexes );
1664         }
1665         planes = tri->facePlanes;
1666
1667 #if 1
1668
1669         if ( !planes ) {
1670                 planes = (idPlane *)_alloca16( ( tri->numIndexes / 3 ) * sizeof( planes[0] ) );
1671         }
1672
1673         SIMDProcessor->DeriveTangents( planes, tri->verts, tri->numVerts, tri->indexes, tri->numIndexes );
1674
1675 #else
1676
1677         for ( i = 0; i < tri->numVerts; i++ ) {
1678                 tri->verts[i].normal.Zero();
1679                 tri->verts[i].tangents[0].Zero();
1680                 tri->verts[i].tangents[1].Zero();
1681         }
1682
1683         for ( i = 0; i < tri->numIndexes; i += 3 ) {
1684                 // make face tangents
1685                 float           d0[5], d1[5];
1686                 idDrawVert      *a, *b, *c;
1687                 idVec3          temp, normal, tangents[2];
1688
1689                 a = tri->verts + tri->indexes[i + 0];
1690                 b = tri->verts + tri->indexes[i + 1];
1691                 c = tri->verts + tri->indexes[i + 2];
1692
1693                 d0[0] = b->xyz[0] - a->xyz[0];
1694                 d0[1] = b->xyz[1] - a->xyz[1];
1695                 d0[2] = b->xyz[2] - a->xyz[2];
1696                 d0[3] = b->st[0] - a->st[0];
1697                 d0[4] = b->st[1] - a->st[1];
1698
1699                 d1[0] = c->xyz[0] - a->xyz[0];
1700                 d1[1] = c->xyz[1] - a->xyz[1];
1701                 d1[2] = c->xyz[2] - a->xyz[2];
1702                 d1[3] = c->st[0] - a->st[0];
1703                 d1[4] = c->st[1] - a->st[1];
1704
1705                 // normal
1706                 temp[0] = d1[1] * d0[2] - d1[2] * d0[1];
1707                 temp[1] = d1[2] * d0[0] - d1[0] * d0[2];
1708                 temp[2] = d1[0] * d0[1] - d1[1] * d0[0];
1709                 VectorNormalizeFast2( temp, normal );
1710
1711 #ifdef USE_INVA
1712                 float area = d0[3] * d1[4] - d0[4] * d1[3];
1713                 float inva = area < 0.0f ? -1 : 1;              // was = 1.0f / area;
1714
1715         temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
1716         temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
1717         temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
1718                 VectorNormalizeFast2( temp, tangents[0] );
1719
1720         temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
1721         temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
1722         temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
1723                 VectorNormalizeFast2( temp, tangents[1] );
1724 #else
1725         temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]);
1726         temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]);
1727         temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]);
1728                 VectorNormalizeFast2( temp, tangents[0] );
1729
1730         temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]);
1731         temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]);
1732         temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]);
1733                 VectorNormalizeFast2( temp, tangents[1] );
1734 #endif
1735
1736                 // sum up the tangents and normals for each vertex on this face
1737                 for ( int j = 0 ; j < 3 ; j++ ) {
1738                         vert = &tri->verts[tri->indexes[i+j]];
1739                         vert->normal += normal;
1740                         vert->tangents[0] += tangents[0];
1741                         vert->tangents[1] += tangents[1];
1742                 }
1743
1744                 if ( planes ) {
1745                         planes->Normal() = normal;
1746                         planes->FitThroughPoint( a->xyz );
1747                         planes++;
1748                 }
1749         }
1750
1751 #endif
1752
1753 #if 0
1754
1755         if ( tri->silIndexes != NULL ) {
1756                 for ( i = 0; i < tri->numVerts; i++ ) {
1757                         tri->verts[i].normal.Zero();
1758                 }
1759                 for ( i = 0; i < tri->numIndexes; i++ ) {
1760                         tri->verts[tri->silIndexes[i]].normal += planes[i/3].Normal();
1761                 }
1762                 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1763                         tri->verts[tri->indexes[i]].normal = tri->verts[tri->silIndexes[i]].normal;
1764                 }
1765         }
1766
1767 #else
1768
1769         int *dupVerts = tri->dupVerts;
1770         idDrawVert *verts = tri->verts;
1771
1772         // add the normal of a duplicated vertex to the normal of the first vertex with the same XYZ
1773         for ( i = 0; i < tri->numDupVerts; i++ ) {
1774                 verts[dupVerts[i*2+0]].normal += verts[dupVerts[i*2+1]].normal;
1775         }
1776
1777         // copy vertex normals to duplicated vertices
1778         for ( i = 0; i < tri->numDupVerts; i++ ) {
1779                 verts[dupVerts[i*2+1]].normal = verts[dupVerts[i*2+0]].normal;
1780         }
1781
1782 #endif
1783
1784 #if 0
1785         // sum up both sides of the mirrored verts
1786         // so the S vectors exactly mirror, and the T vectors are equal
1787         for ( i = 0 ; i < tri->numMirroredVerts ; i++ ) {
1788                 idDrawVert      *v1, *v2;
1789
1790                 v1 = &tri->verts[ tri->numVerts - tri->numMirroredVerts + i ];
1791                 v2 = &tri->verts[ tri->mirroredVerts[i] ];
1792
1793                 v1->tangents[0] -= v2->tangents[0];
1794                 v1->tangents[1] += v2->tangents[1];
1795
1796                 v2->tangents[0] = vec3_origin - v1->tangents[0];
1797                 v2->tangents[1] = v1->tangents[1];
1798         }
1799 #endif
1800
1801         // project the summed vectors onto the normal plane
1802         // and normalize.  The tangent vectors will not necessarily
1803         // be orthogonal to each other, but they will be orthogonal
1804         // to the surface normal.
1805 #if 1
1806
1807         SIMDProcessor->NormalizeTangents( tri->verts, tri->numVerts );
1808
1809 #else
1810
1811         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1812                 idDrawVert *vert = &tri->verts[i];
1813
1814                 VectorNormalizeFast2( vert->normal, vert->normal );
1815
1816                 // project the tangent vectors
1817                 for ( int j = 0 ; j < 2 ; j++ ) {
1818                         float d;
1819
1820                         d = vert->tangents[j] * vert->normal;
1821                         vert->tangents[j] = vert->tangents[j] - d * vert->normal;
1822                         VectorNormalizeFast2( vert->tangents[j], vert->tangents[j] );
1823                 }
1824         }
1825
1826 #endif
1827
1828         tri->tangentsCalculated = true;
1829         tri->facePlanesCalculated = true;
1830 }
1831
1832 /*
1833 =================
1834 R_RemoveDuplicatedTriangles
1835
1836 silIndexes must have already been calculated
1837
1838 silIndexes are used instead of indexes, because duplicated
1839 triangles could have different texture coordinates.
1840 =================
1841 */
1842 void R_RemoveDuplicatedTriangles( srfTriangles_t *tri ) {
1843         int             c_removed;
1844         int             i, j, r;
1845         int             a, b, c;
1846
1847         c_removed = 0;
1848
1849         // check for completely duplicated triangles
1850         // any rotation of the triangle is still the same, but a mirroring
1851         // is considered different
1852         for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1853                 for ( r = 0 ; r < 3 ; r++ ) {
1854                         a = tri->silIndexes[i+r];
1855                         b = tri->silIndexes[i+(r+1)%3];
1856                         c = tri->silIndexes[i+(r+2)%3];
1857                         for ( j = i + 3 ; j < tri->numIndexes ; j+=3 ) {
1858                                 if ( tri->silIndexes[j] == a && tri->silIndexes[j+1] == b && tri->silIndexes[j+2] == c ) {
1859                                         c_removed++;
1860                                         memmove( tri->indexes + j, tri->indexes + j + 3, ( tri->numIndexes - j - 3 ) * sizeof( tri->indexes[0] ) );
1861                                         memmove( tri->silIndexes + j, tri->silIndexes + j + 3, ( tri->numIndexes - j - 3 ) * sizeof( tri->silIndexes[0] ) );
1862                                         tri->numIndexes -= 3;
1863                                         j -= 3;
1864                                 }
1865                         }
1866                 }
1867         }
1868
1869         if ( c_removed ) {
1870                 common->Printf( "removed %i duplicated triangles\n", c_removed );
1871         }
1872
1873 }
1874
1875 /*
1876 =================
1877 R_RemoveDegenerateTriangles
1878
1879 silIndexes must have already been calculated
1880 =================
1881 */
1882 void R_RemoveDegenerateTriangles( srfTriangles_t *tri ) {
1883         int             c_removed;
1884         int             i;
1885         int             a, b, c;
1886
1887         // check for completely degenerate triangles
1888         c_removed = 0;
1889         for ( i = 0; i < tri->numIndexes; i += 3 ) {
1890                 a = tri->silIndexes[i];
1891                 b = tri->silIndexes[i+1];
1892                 c = tri->silIndexes[i+2];
1893                 if ( a == b || a == c || b == c ) {
1894                         c_removed++;
1895                         memmove( tri->indexes + i, tri->indexes + i + 3, ( tri->numIndexes - i - 3 ) * sizeof( tri->indexes[0] ) );
1896                         if ( tri->silIndexes ) {
1897                                 memmove( tri->silIndexes + i, tri->silIndexes + i + 3, ( tri->numIndexes - i - 3 ) * sizeof( tri->silIndexes[0] ) );
1898                         }
1899                         tri->numIndexes -= 3;
1900                         i -= 3;
1901                 }
1902         }
1903
1904         // this doesn't free the memory used by the unused verts
1905
1906         if ( c_removed ) {
1907                 common->Printf( "removed %i degenerate triangles\n", c_removed );
1908         }
1909 }
1910
1911 /*
1912 =================
1913 R_TestDegenerateTextureSpace
1914 =================
1915 */
1916 void R_TestDegenerateTextureSpace( srfTriangles_t *tri ) {
1917         int             c_degenerate;
1918         int             i;
1919
1920         // check for triangles with a degenerate texture space
1921         c_degenerate = 0;
1922         for ( i = 0; i < tri->numIndexes; i += 3 ) {
1923                 const idDrawVert &a = tri->verts[tri->indexes[i+0]];
1924                 const idDrawVert &b = tri->verts[tri->indexes[i+1]];
1925                 const idDrawVert &c = tri->verts[tri->indexes[i+2]];
1926
1927                 if ( a.st == b.st || b.st == c.st || c.st == a.st ) {
1928                         c_degenerate++;
1929                 }
1930         }
1931
1932         if ( c_degenerate ) {
1933 //              common->Printf( "%d triangles with a degenerate texture space\n", c_degenerate );
1934         }
1935 }
1936
1937 /*
1938 =================
1939 R_RemoveUnusedVerts
1940 =================
1941 */
1942 void R_RemoveUnusedVerts( srfTriangles_t *tri ) {
1943         int             i;
1944         int             *mark;
1945         int             index;
1946         int             used;
1947
1948         mark = (int *)R_ClearedStaticAlloc( tri->numVerts * sizeof( *mark ) );
1949
1950         for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1951                 index = tri->indexes[i];
1952                 if ( index < 0 || index >= tri->numVerts ) {
1953                         common->Error( "R_RemoveUnusedVerts: bad index" );
1954                 }
1955                 mark[ index ] = 1;
1956
1957                 if ( tri->silIndexes ) {
1958                         index = tri->silIndexes[i];
1959                         if ( index < 0 || index >= tri->numVerts ) {
1960                                 common->Error( "R_RemoveUnusedVerts: bad index" );
1961                         }
1962                         mark[ index ] = 1;
1963                 }
1964         }
1965
1966         used = 0;
1967         for ( i = 0 ; i < tri->numVerts ; i++ ) {
1968                 if ( !mark[i] ) {
1969                         continue;
1970                 }
1971                 mark[i] = used + 1;
1972                 used++;
1973         }
1974
1975         if ( used != tri->numVerts ) {
1976                 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1977                         tri->indexes[i] = mark[ tri->indexes[i] ] - 1;
1978                         if ( tri->silIndexes ) {
1979                                 tri->silIndexes[i] = mark[ tri->silIndexes[i] ] - 1;
1980                         }
1981                 }
1982                 tri->numVerts = used;
1983
1984                 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1985                         index = mark[ i ];
1986                         if ( !index ) {
1987                                 continue;
1988                         }
1989                         tri->verts[ index - 1 ] = tri->verts[i];
1990                 }
1991
1992                 // this doesn't realloc the arrays to save the memory used by the unused verts
1993         }
1994
1995         R_StaticFree( mark );
1996 }
1997
1998 /*
1999 =================
2000 R_MergeSurfaceList
2001
2002 Only deals with vertexes and indexes, not silhouettes, planes, etc.
2003 Does NOT perform a cleanup triangles, so there may be duplicated verts in the result.
2004 =================
2005 */
2006 srfTriangles_t  *R_MergeSurfaceList( const srfTriangles_t **surfaces, int numSurfaces ) {
2007         srfTriangles_t  *newTri;
2008         const srfTriangles_t    *tri;
2009         int                             i, j;
2010         int                             totalVerts;
2011         int                             totalIndexes;
2012
2013         totalVerts = 0;
2014         totalIndexes = 0;
2015         for ( i = 0 ; i < numSurfaces ; i++ ) {
2016                 totalVerts += surfaces[i]->numVerts;
2017                 totalIndexes += surfaces[i]->numIndexes;
2018         }
2019
2020         newTri = R_AllocStaticTriSurf();
2021         newTri->numVerts = totalVerts;
2022         newTri->numIndexes = totalIndexes;
2023         R_AllocStaticTriSurfVerts( newTri, newTri->numVerts );
2024         R_AllocStaticTriSurfIndexes( newTri, newTri->numIndexes );
2025
2026         totalVerts = 0;
2027         totalIndexes = 0;
2028         for ( i = 0 ; i < numSurfaces ; i++ ) {
2029                 tri = surfaces[i];
2030                 memcpy( newTri->verts + totalVerts, tri->verts, tri->numVerts * sizeof( *tri->verts ) );
2031                 for ( j = 0 ; j < tri->numIndexes ; j++ ) {
2032                         newTri->indexes[ totalIndexes + j ] = totalVerts + tri->indexes[j];
2033                 }
2034                 totalVerts += tri->numVerts;
2035                 totalIndexes += tri->numIndexes;
2036         }
2037
2038         return newTri;
2039 }
2040
2041 /*
2042 =================
2043 R_MergeTriangles
2044
2045 Only deals with vertexes and indexes, not silhouettes, planes, etc.
2046 Does NOT perform a cleanup triangles, so there may be duplicated verts in the result.
2047 =================
2048 */
2049 srfTriangles_t  *R_MergeTriangles( const srfTriangles_t *tri1, const srfTriangles_t *tri2 ) {
2050         const srfTriangles_t    *tris[2];
2051
2052         tris[0] = tri1;
2053         tris[1] = tri2;
2054
2055         return R_MergeSurfaceList( tris, 2 );
2056 }
2057
2058 /*
2059 =================
2060 R_ReverseTriangles
2061
2062 Lit two sided surfaces need to have the triangles actually duplicated,
2063 they can't just turn on two sided lighting, because the normal and tangents
2064 are wrong on the other sides.
2065
2066 This should be called before R_CleanupTriangles
2067 =================
2068 */
2069 void R_ReverseTriangles( srfTriangles_t *tri ) {
2070         int                     i;
2071
2072         // flip the normal on each vertex
2073         // If the surface is going to have generated normals, this won't matter,
2074         // but if it has explicit normals, this will keep it on the correct side
2075         for ( i = 0 ; i < tri->numVerts ; i++ ) {
2076                 tri->verts[i].normal = vec3_origin - tri->verts[i].normal;
2077         }
2078
2079         // flip the index order to make them back sided
2080         for ( i = 0 ; i < tri->numIndexes ; i+= 3 ) {
2081                 glIndex_t       temp;
2082
2083                 temp = tri->indexes[ i + 0 ];
2084                 tri->indexes[ i + 0 ] = tri->indexes[ i + 1 ];
2085                 tri->indexes[ i + 1 ] = temp;
2086         }
2087 }
2088
2089 /*
2090 =================
2091 R_CleanupTriangles
2092
2093 FIXME: allow createFlat and createSmooth normals, as well as explicit
2094 =================
2095 */
2096 void R_CleanupTriangles( srfTriangles_t *tri, bool createNormals, bool identifySilEdges, bool useUnsmoothedTangents ) {
2097         R_RangeCheckIndexes( tri );
2098
2099         R_CreateSilIndexes( tri );
2100
2101 //      R_RemoveDuplicatedTriangles( tri );     // this may remove valid overlapped transparent triangles
2102
2103         R_RemoveDegenerateTriangles( tri );
2104
2105         R_TestDegenerateTextureSpace( tri );
2106
2107 //      R_RemoveUnusedVerts( tri );
2108
2109         if ( identifySilEdges ) {
2110                 R_IdentifySilEdges( tri, true );        // assume it is non-deformable, and omit coplanar edges
2111         }
2112
2113         // bust vertexes that share a mirrored edge into separate vertexes
2114         R_DuplicateMirroredVertexes( tri );
2115
2116         // optimize the index order (not working?)
2117 //      R_OrderIndexes( tri->numIndexes, tri->indexes );
2118
2119         R_CreateDupVerts( tri );
2120
2121         R_BoundTriSurf( tri );
2122
2123         if ( useUnsmoothedTangents ) {
2124                 R_BuildDominantTris( tri );
2125                 R_DeriveUnsmoothedTangents( tri );
2126         } else if ( !createNormals ) {
2127                 R_DeriveFacePlanes( tri );
2128                 R_DeriveTangentsWithoutNormals( tri );
2129         } else {
2130                 R_DeriveTangents( tri );
2131         }
2132 }
2133
2134 /*
2135 ===================================================================================
2136
2137 DEFORMED SURFACES
2138
2139 ===================================================================================
2140 */
2141
2142 /*
2143 ===================
2144 R_BuildDeformInfo
2145 ===================
2146 */
2147 deformInfo_t *R_BuildDeformInfo( int numVerts, const idDrawVert *verts, int numIndexes, const int *indexes, bool useUnsmoothedTangents ) {
2148         deformInfo_t    *deform;
2149         srfTriangles_t  tri;
2150         int                             i;
2151
2152         memset( &tri, 0, sizeof( tri ) );
2153
2154         tri.numVerts = numVerts;
2155         R_AllocStaticTriSurfVerts( &tri, tri.numVerts );
2156         SIMDProcessor->Memcpy( tri.verts, verts, tri.numVerts * sizeof( tri.verts[0] ) );
2157
2158         tri.numIndexes = numIndexes;
2159         R_AllocStaticTriSurfIndexes( &tri, tri.numIndexes );
2160
2161         // don't memcpy, so we can change the index type from int to short without changing the interface
2162         for ( i = 0 ; i < tri.numIndexes ; i++ ) {
2163                 tri.indexes[i] = indexes[i];
2164         }
2165
2166         R_RangeCheckIndexes( &tri );
2167         R_CreateSilIndexes( &tri );
2168
2169 // should we order the indexes here?
2170
2171 //      R_RemoveDuplicatedTriangles( &tri );
2172 //      R_RemoveDegenerateTriangles( &tri );
2173 //      R_RemoveUnusedVerts( &tri );
2174         R_IdentifySilEdges( &tri, false );                      // we cannot remove coplanar edges, because
2175                                                                                                 // they can deform to silhouettes
2176
2177         R_DuplicateMirroredVertexes( &tri );            // split mirror points into multiple points
2178
2179         R_CreateDupVerts( &tri );
2180
2181         if ( useUnsmoothedTangents ) {
2182                 R_BuildDominantTris( &tri );
2183         }
2184
2185         deform = (deformInfo_t *)R_ClearedStaticAlloc( sizeof( *deform ) );
2186
2187         deform->numSourceVerts = numVerts;
2188         deform->numOutputVerts = tri.numVerts;
2189
2190         deform->numIndexes = numIndexes;
2191         deform->indexes = tri.indexes;
2192
2193         deform->silIndexes = tri.silIndexes;
2194
2195         deform->numSilEdges = tri.numSilEdges;
2196         deform->silEdges = tri.silEdges;
2197
2198         deform->dominantTris = tri.dominantTris;
2199
2200         deform->numMirroredVerts = tri.numMirroredVerts;
2201         deform->mirroredVerts = tri.mirroredVerts;
2202
2203         deform->numDupVerts = tri.numDupVerts;
2204         deform->dupVerts = tri.dupVerts;
2205
2206         if ( tri.verts ) {
2207                 triVertexAllocator.Free( tri.verts );
2208         }
2209
2210         if ( tri.facePlanes ) {
2211                 triPlaneAllocator.Free( tri.facePlanes );
2212         }
2213
2214         return deform;
2215 }
2216
2217 /*
2218 ===================
2219 R_FreeDeformInfo
2220 ===================
2221 */
2222 void R_FreeDeformInfo( deformInfo_t *deformInfo ) {
2223         if ( deformInfo->indexes != NULL ) {
2224                 triIndexAllocator.Free( deformInfo->indexes );
2225         }
2226         if ( deformInfo->silIndexes != NULL ) {
2227                 triSilIndexAllocator.Free( deformInfo->silIndexes );
2228         }
2229         if ( deformInfo->silEdges != NULL ) {
2230                 triSilEdgeAllocator.Free( deformInfo->silEdges );
2231         }
2232         if ( deformInfo->dominantTris != NULL ) {
2233                 triDominantTrisAllocator.Free( deformInfo->dominantTris );
2234         }
2235         if ( deformInfo->mirroredVerts != NULL ) {
2236                 triMirroredVertAllocator.Free( deformInfo->mirroredVerts );
2237         }
2238         if ( deformInfo->dupVerts != NULL ) {
2239                 triDupVertAllocator.Free( deformInfo->dupVerts );
2240         }
2241         R_StaticFree( deformInfo );
2242 }
2243
2244 /*
2245 ===================
2246 R_DeformInfoMemoryUsed
2247 ===================
2248 */
2249 int R_DeformInfoMemoryUsed( deformInfo_t *deformInfo ) {
2250         int total = 0;
2251
2252         if ( deformInfo->indexes != NULL ) {
2253                 total += deformInfo->numIndexes * sizeof( deformInfo->indexes[0] );
2254         }
2255         if ( deformInfo->silIndexes != NULL ) {
2256                 total += deformInfo->numIndexes * sizeof( deformInfo->silIndexes[0] );
2257         }
2258         if ( deformInfo->silEdges != NULL ) {
2259                 total += deformInfo->numSilEdges * sizeof( deformInfo->silEdges[0] );
2260         }
2261         if ( deformInfo->dominantTris != NULL ) {
2262                 total += deformInfo->numSourceVerts * sizeof( deformInfo->dominantTris[0] );
2263         }
2264         if ( deformInfo->mirroredVerts != NULL ) {
2265                 total += deformInfo->numMirroredVerts * sizeof( deformInfo->mirroredVerts[0] );
2266         }
2267         if ( deformInfo->dupVerts != NULL ) {
2268                 total += deformInfo->numDupVerts * sizeof( deformInfo->dupVerts[0] );
2269         }
2270
2271         total += sizeof( *deformInfo );
2272         return total;
2273 }
2274