neo/tools/compilers/dmap/usurface.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 "dmap.h"
  33
  34
  35 #define  TEXTURE_OFFSET_EQUAL_EPSILON   0.005
  36 #define  TEXTURE_VECTOR_EQUAL_EPSILON   0.001
  37
  38 /*
  39 ===============
  40 AddTriListToArea
  41
  42 The triList is appended to the apropriate optimzeGroup_t,
  43 creating a new one if needed.
  44 The entire list is assumed to come from the same planar primitive
  45 ===============
  46 */
  47 static void AddTriListToArea( uEntity_t *e, mapTri_t *triList, int planeNum, int areaNum, textureVectors_t *texVec ) {
  48         uArea_t         *area;
  49         optimizeGroup_t *group;
  50         int                     i, j;
  51
  52         if ( !triList ) {
  53                 return;
  54         }
  55
  56         area = &e->areas[areaNum];
  57         for ( group = area->groups ; group ; group = group->nextGroup ) {
  58                 if ( group->material == triList->material
  59                         && group->planeNum == planeNum
  60                         && group->mergeGroup == triList->mergeGroup ) {
  61                         // check the texture vectors
  62                         for ( i = 0 ; i < 2 ; i++ ) {
  63                                 for ( j = 0 ; j < 3 ; j++ ) {
  64                                         if ( idMath::Fabs( texVec->v[i][j] - group->texVec.v[i][j] ) > TEXTURE_VECTOR_EQUAL_EPSILON ) {
  65                                                 break;
  66                                         }
  67                                 }
  68                                 if ( j != 3 ) {
  69                                         break;
  70                                 }
  71                                 if ( idMath::Fabs( texVec->v[i][3] - group->texVec.v[i][3] ) > TEXTURE_OFFSET_EQUAL_EPSILON ) {
  72                                         break;
  73                                 }
  74                         }
  75                         if ( i == 2 ) {
  76                                 break;  // exact match
  77                         } else {
  78                                 // different texture offsets
  79                                 i = 1;  // just for debugger breakpoint
  80                         }
  81                 }
  82         }
  83
  84         if ( !group ) {
  85                 group = (optimizeGroup_t *)Mem_Alloc( sizeof( *group ) );
  86                 memset( group, 0, sizeof( *group ) );
  87                 group->planeNum = planeNum;
  88                 group->mergeGroup = triList->mergeGroup;
  89                 group->material = triList->material;
  90                 group->nextGroup = area->groups;
  91                 group->texVec = *texVec;
  92                 area->groups = group;
  93         }
  94
  95         group->triList = MergeTriLists( group->triList, triList );
  96 }
  97
  98 /*
  99 ===================
 100 TexVecForTri
 101 ===================
 102 */
 103 static void TexVecForTri( textureVectors_t *texVec, mapTri_t *tri ) {
 104         float   area, inva;
 105         idVec3  temp;
 106         idVec5  d0, d1;
 107         idDrawVert      *a, *b, *c;
 108
 109         a = &tri->v[0];
 110         b = &tri->v[1];
 111         c = &tri->v[2];
 112
 113         d0[0] = b->xyz[0] - a->xyz[0];
 114         d0[1] = b->xyz[1] - a->xyz[1];
 115         d0[2] = b->xyz[2] - a->xyz[2];
 116         d0[3] = b->st[0] - a->st[0];
 117         d0[4] = b->st[1] - a->st[1];
 118
 119         d1[0] = c->xyz[0] - a->xyz[0];
 120         d1[1] = c->xyz[1] - a->xyz[1];
 121         d1[2] = c->xyz[2] - a->xyz[2];
 122         d1[3] = c->st[0] - a->st[0];
 123         d1[4] = c->st[1] - a->st[1];
 124
 125         area = d0[3] * d1[4] - d0[4] * d1[3];
 126         inva = 1.0 / area;
 127
 128     temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
 129     temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
 130     temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
 131         temp.Normalize();
 132         texVec->v[0].ToVec3() = temp;
 133         texVec->v[0][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[0];
 134
 135     temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
 136     temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
 137     temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
 138         temp.Normalize();
 139         texVec->v[1].ToVec3() = temp;
 140         texVec->v[1][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[1];
 141 }
 142
 143
 144 /*
 145 =================
 146 TriListForSide
 147 =================
 148 */
 149 //#define       SNAP_FLOAT_TO_INT       8
 150 #define SNAP_FLOAT_TO_INT       256
 151 #define SNAP_INT_TO_FLOAT       (1.0/SNAP_FLOAT_TO_INT)
 152
 153 mapTri_t *TriListForSide( const side_t *s, const idWinding *w ) {
 154         int                             i, j;
 155         idDrawVert              *dv;
 156         mapTri_t                *tri, *triList;
 157         const idVec3            *vec;
 158         const idMaterial        *si;
 159
 160         si = s->material;
 161
 162         // skip any generated faces
 163         if ( !si ) {
 164                 return NULL;
 165         }
 166
 167         // don't create faces for non-visible sides
 168         if ( !si->SurfaceCastsShadow() && !si->IsDrawn() ) {
 169                 return NULL;
 170         }
 171
 172         if ( 1 ) {
 173                 // triangle fan using only the outer verts
 174                 // this gives the minimum triangle count,
 175                 // but may have some very distended triangles
 176                 triList = NULL;
 177                 for ( i = 2 ; i < w->GetNumPoints() ; i++ ) {
 178                         tri = AllocTri();
 179                         tri->material = si;
 180                         tri->next = triList;
 181                         triList = tri;
 182
 183                         for ( j = 0 ; j < 3 ; j++ ) {
 184                                 if ( j == 0 ) {
 185                                         vec = &((*w)[0]).ToVec3();
 186                                 } else if ( j == 1 ) {
 187                                         vec = &((*w)[i-1]).ToVec3();
 188                                 } else {
 189                                         vec = &((*w)[i]).ToVec3();
 190                                 }
 191
 192                                 dv = tri->v + j;
 193 #if 0
 194                                 // round the xyz to a given precision
 195                                 for ( k = 0 ; k < 3 ; k++ ) {
 196                                         dv->xyz[k] = SNAP_INT_TO_FLOAT * floor( vec[k] * SNAP_FLOAT_TO_INT + 0.5 );
 197                                 }
 198 #else
 199                                 VectorCopy( *vec, dv->xyz );
 200 #endif
 201
 202                                 // calculate texture s/t from brush primitive texture matrix
 203                                 dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
 204                                 dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];
 205
 206                                 // copy normal
 207                                 dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
 208                                 if ( dv->normal.Length() < 0.9 || dv->normal.Length() > 1.1 ) {
 209                                         common->Error( "Bad normal in TriListForSide" );
 210                                 }
 211                         }
 212                 }
 213         } else {
 214                 // triangle fan from central point, more verts and tris, but less distended
 215                 // I use this when debugging some tjunction problems
 216                 triList = NULL;
 217                 for ( i = 0 ; i < w->GetNumPoints() ; i++ ) {
 218                         idVec3  midPoint;
 219
 220                         tri = AllocTri();
 221                         tri->material = si;
 222                         tri->next = triList;
 223                         triList = tri;
 224
 225                         for ( j = 0 ; j < 3 ; j++ ) {
 226                                 if ( j == 0 ) {
 227                                         vec = &midPoint;
 228                                         midPoint = w->GetCenter();
 229                                 } else if ( j == 1 ) {
 230                                         vec = &((*w)[i]).ToVec3();
 231                                 } else {
 232                                         vec = &((*w)[(i+1)%w->GetNumPoints()]).ToVec3();
 233                                 }
 234
 235                                 dv = tri->v + j;
 236
 237                                 VectorCopy( *vec, dv->xyz );
 238
 239                                 // calculate texture s/t from brush primitive texture matrix
 240                                 dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
 241                                 dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];
 242
 243                                 // copy normal
 244                                 dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
 245                                 if ( dv->normal.Length() < 0.9f || dv->normal.Length() > 1.1f ) {
 246                                         common->Error( "Bad normal in TriListForSide" );
 247                                 }
 248                         }
 249                 }
 250         }
 251
 252         // set merge groups if needed, to prevent multiple sides from being
 253         // merged into a single surface in the case of gui shaders, mirrors, and autosprites
 254         if ( s->material->IsDiscrete() ) {
 255                 for ( tri = triList ; tri ; tri = tri->next ) {
 256                         tri->mergeGroup = (void *)s;
 257                 }
 258         }
 259
 260         return triList;
 261 }
 262
 263 //=================================================================================
 264
 265 /*
 266 ====================
 267 ClipSideByTree_r
 268
 269 Adds non-opaque leaf fragments to the convex hull
 270 ====================
 271 */
 272 static void ClipSideByTree_r( idWinding *w, side_t *side, node_t *node ) {
 273         idWinding               *front, *back;
 274
 275         if ( !w ) {
 276                 return;
 277         }
 278
 279         if ( node->planenum != PLANENUM_LEAF ) {
 280                 if ( side->planenum == node->planenum ) {
 281                         ClipSideByTree_r( w, side, node->children[0] );
 282                         return;
 283                 }
 284                 if ( side->planenum == ( node->planenum ^ 1) ) {
 285                         ClipSideByTree_r( w, side, node->children[1] );
 286                         return;
 287                 }
 288
 289                 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
 290                 delete w;
 291
 292                 ClipSideByTree_r( front, side, node->children[0] );
 293                 ClipSideByTree_r( back, side, node->children[1] );
 294
 295                 return;
 296         }
 297
 298         // if opaque leaf, don't add
 299         if ( !node->opaque ) {
 300                 if ( !side->visibleHull ) {
 301                         side->visibleHull = w->Copy();
 302                 }
 303                 else {
 304                         side->visibleHull->AddToConvexHull( w, dmapGlobals.mapPlanes[ side->planenum ].Normal() );
 305                 }
 306         }
 307
 308         delete w;
 309         return;
 310 }
 311
 312
 313 /*
 314 =====================
 315 ClipSidesByTree
 316
 317 Creates side->visibleHull for all visible sides
 318
 319 The visible hull for a side will consist of the convex hull of
 320 all points in non-opaque clusters, which allows overlaps
 321 to be trimmed off automatically.
 322 =====================
 323 */
 324 void ClipSidesByTree( uEntity_t *e ) {
 325         uBrush_t                *b;
 326         int                             i;
 327         idWinding               *w;
 328         side_t                  *side;
 329         primitive_t             *prim;
 330
 331         common->Printf( "----- ClipSidesByTree -----\n");
 332
 333         for ( prim = e->primitives ; prim ; prim = prim->next ) {
 334                 b = prim->brush;
 335                 if ( !b ) {
 336                         // FIXME: other primitives!
 337                         continue;
 338                 }
 339                 for ( i = 0 ; i < b->numsides ; i++ ) {
 340                         side = &b->sides[i];
 341                         if ( !side->winding) {
 342                                 continue;
 343                         }
 344                         w = side->winding->Copy();
 345                         side->visibleHull = NULL;
 346                         ClipSideByTree_r( w, side, e->tree->headnode );
 347                         // for debugging, we can choose to use the entire original side
 348                         // but we skip this if the side was completely clipped away
 349                         if ( side->visibleHull && dmapGlobals.noClipSides ) {
 350                                 delete side->visibleHull;
 351                                 side->visibleHull = side->winding->Copy();
 352                         }
 353                 }
 354         }
 355 }
 356
 357
 358
 359 //=================================================================================
 360
 361 /*
 362 ====================
 363 ClipTriIntoTree_r
 364
 365 This is used for adding curve triangles
 366 The winding will be freed before it returns
 367 ====================
 368 */
 369 void ClipTriIntoTree_r( idWinding *w, mapTri_t *originalTri, uEntity_t *e, node_t *node ) {
 370         idWinding               *front, *back;
 371
 372         if ( !w ) {
 373                 return;
 374         }
 375
 376         if ( node->planenum != PLANENUM_LEAF ) {
 377                 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
 378                 delete w;
 379
 380                 ClipTriIntoTree_r( front, originalTri, e, node->children[0] );
 381                 ClipTriIntoTree_r( back, originalTri, e, node->children[1] );
 382
 383                 return;
 384         }
 385
 386         // if opaque leaf, don't add
 387         if ( !node->opaque && node->area >= 0 ) {
 388                 mapTri_t        *list;
 389                 int                     planeNum;
 390                 idPlane         plane;
 391                 textureVectors_t        texVec;
 392
 393                 list = WindingToTriList( w, originalTri );
 394
 395                 PlaneForTri( originalTri, plane );
 396                 planeNum = FindFloatPlane( plane );
 397
 398                 TexVecForTri( &texVec, originalTri );
 399
 400                 AddTriListToArea( e, list, planeNum, node->area, &texVec );
 401         }
 402
 403         delete w;
 404         return;
 405 }
 406
 407
 408
 409 //=============================================================
 410
 411 /*
 412 ====================
 413 CheckWindingInAreas_r
 414
 415 Returns the area number that the winding is in, or
 416 -2 if it crosses multiple areas.
 417
 418 ====================
 419 */
 420 static int CheckWindingInAreas_r( const idWinding *w, node_t *node ) {
 421         idWinding               *front, *back;
 422
 423         if ( !w ) {
 424                 return -1;
 425         }
 426
 427         if ( node->planenum != PLANENUM_LEAF ) {
 428                 int             a1, a2;
 429 #if 0
 430                 if ( side->planenum == node->planenum ) {
 431                         return CheckWindingInAreas_r( w, node->children[0] );
 432                 }
 433                 if ( side->planenum == ( node->planenum ^ 1) ) {
 434                         return CheckWindingInAreas_r( w, node->children[1] );
 435                 }
 436 #endif
 437                 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
 438
 439                 a1 = CheckWindingInAreas_r( front, node->children[0] );
 440                 delete front;
 441                 a2 = CheckWindingInAreas_r( back, node->children[1] );
 442                 delete back;
 443
 444                 if ( a1 == -2 || a2 == -2 ) {
 445                         return -2;      // different
 446                 }
 447                 if ( a1 == -1 ) {
 448                         return a2;      // one solid
 449                 }
 450                 if ( a2 == -1 ) {
 451                         return a1;      // one solid
 452                 }
 453
 454                 if ( a1 != a2 ) {
 455                         return -2;      // cross areas
 456                 }
 457                 return a1;
 458         }
 459
 460         return node->area;
 461 }
 462
 463
 464
 465 /*
 466 ====================
 467 PutWindingIntoAreas_r
 468
 469 Clips a winding down into the bsp tree, then converts
 470 the fragments to triangles and adds them to the area lists
 471 ====================
 472 */
 473 static void PutWindingIntoAreas_r( uEntity_t *e, const idWinding *w, side_t *side, node_t *node ) {
 474         idWinding               *front, *back;
 475         int                             area;
 476
 477         if ( !w ) {
 478                 return;
 479         }
 480
 481         if ( node->planenum != PLANENUM_LEAF ) {
 482                 if ( side->planenum == node->planenum ) {
 483                         PutWindingIntoAreas_r( e, w, side, node->children[0] );
 484                         return;
 485                 }
 486                 if ( side->planenum == ( node->planenum ^ 1) ) {
 487                         PutWindingIntoAreas_r( e, w, side, node->children[1] );
 488                         return;
 489                 }
 490
 491                 // see if we need to split it
 492                 // adding the "noFragment" flag to big surfaces like sky boxes
 493                 // will avoid potentially dicing them up into tons of triangles
 494                 // that take forever to optimize back together
 495                 if ( !dmapGlobals.fullCarve || side->material->NoFragment() ) {
 496                         area = CheckWindingInAreas_r( w, node );
 497                         if ( area >= 0 ) {
 498                                 mapTri_t        *tri;
 499
 500                                 // put in single area
 501                                 tri = TriListForSide( side, w );
 502                                 AddTriListToArea( e, tri, side->planenum, area, &side->texVec );
 503                                 return;
 504                         }
 505                 }
 506
 507                 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
 508
 509                 PutWindingIntoAreas_r( e, front, side, node->children[0] );
 510                 if ( front ) {
 511                         delete front;
 512                 }
 513
 514                 PutWindingIntoAreas_r( e, back, side, node->children[1] );
 515                 if ( back ) {
 516                         delete back;
 517                 }
 518
 519                 return;
 520         }
 521
 522         // if opaque leaf, don't add
 523         if ( node->area >= 0 && !node->opaque ) {
 524                 mapTri_t        *tri;
 525
 526                 tri = TriListForSide( side, w );
 527                 AddTriListToArea( e, tri, side->planenum, node->area, &side->texVec );
 528         }
 529 }
 530
 531 /*
 532 ==================
 533 AddMapTriToAreas
 534
 535 Used for curves and inlined models
 536 ==================
 537 */
 538 void AddMapTriToAreas( mapTri_t *tri, uEntity_t *e ) {
 539         int                             area;
 540         idWinding               *w;
 541
 542         // skip degenerate triangles from pinched curves
 543         if ( MapTriArea( tri ) <= 0 ) {
 544                 return;
 545         }
 546
 547         if ( dmapGlobals.fullCarve ) {
 548                 // always fragment into areas
 549                 w = WindingForTri( tri );
 550                 ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
 551                 return;
 552         }
 553
 554         w = WindingForTri( tri );
 555         area = CheckWindingInAreas_r( w, e->tree->headnode );
 556         delete w;
 557         if ( area == -1 ) {
 558                 return;
 559         }
 560         if ( area >= 0 ) {
 561                 mapTri_t        *newTri;
 562                 idPlane         plane;
 563                 int                     planeNum;
 564                 textureVectors_t        texVec;
 565
 566                 // put in single area
 567                 newTri = CopyMapTri( tri );
 568                 newTri->next = NULL;
 569
 570                 PlaneForTri( tri, plane );
 571                 planeNum = FindFloatPlane( plane );
 572
 573                 TexVecForTri( &texVec, newTri );
 574
 575                 AddTriListToArea( e, newTri, planeNum, area, &texVec );
 576         } else {
 577                 // fragment into areas
 578                 w = WindingForTri( tri );
 579                 ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
 580         }
 581 }
 582
 583 /*
 584 =====================
 585 PutPrimitivesInAreas
 586
 587 =====================
 588 */
 589 void PutPrimitivesInAreas( uEntity_t *e ) {
 590         uBrush_t                *b;
 591         int                             i;
 592         side_t                  *side;
 593         primitive_t             *prim;
 594         mapTri_t                *tri;
 595
 596         common->Printf( "----- PutPrimitivesInAreas -----\n");
 597
 598         // allocate space for surface chains for each area
 599         e->areas = (uArea_t *)Mem_Alloc( e->numAreas * sizeof( e->areas[0] ) );
 600         memset( e->areas, 0, e->numAreas * sizeof( e->areas[0] ) );
 601
 602         // for each primitive, clip it to the non-solid leafs
 603         // and divide it into different areas
 604         for ( prim = e->primitives ; prim ; prim = prim->next ) {
 605                 b = prim->brush;
 606
 607                 if ( !b ) {
 608                         // add curve triangles
 609                         for ( tri = prim->tris ; tri ; tri = tri->next ) {
 610                                 AddMapTriToAreas( tri, e );
 611                         }
 612                         continue;
 613                 }
 614
 615                 // clip in brush sides
 616                 for ( i = 0 ; i < b->numsides ; i++ ) {
 617                         side = &b->sides[i];
 618                         if ( !side->visibleHull ) {
 619                                 continue;
 620                         }
 621                         PutWindingIntoAreas_r( e, side->visibleHull, side, e->tree->headnode );
 622                 }
 623         }
 624
 625
 626         // optionally inline some of the func_static models
 627         if ( dmapGlobals.entityNum == 0 ) {
 628                 bool inlineAll = dmapGlobals.uEntities[0].mapEntity->epairs.GetBool( "inlineAllStatics" );
 629
 630                 for ( int eNum = 1 ; eNum < dmapGlobals.num_entities ; eNum++ ) {
 631                         uEntity_t *entity = &dmapGlobals.uEntities[eNum];
 632                         const char *className = entity->mapEntity->epairs.GetString( "classname" );
 633                         if ( idStr::Icmp( className, "func_static" ) ) {
 634                                 continue;
 635                         }
 636                         if ( !entity->mapEntity->epairs.GetBool( "inline" ) && !inlineAll ) {
 637                                 continue;
 638                         }
 639                         const char *modelName = entity->mapEntity->epairs.GetString( "model" );
 640                         if ( !modelName ) {
 641                                 continue;
 642                         }
 643                         idRenderModel   *model = renderModelManager->FindModel( modelName );
 644
 645                         common->Printf( "inlining %s.\n", entity->mapEntity->epairs.GetString( "name" ) );
 646
 647                         idMat3  axis;
 648                         // get the rotation matrix in either full form, or single angle form
 649                         if ( !entity->mapEntity->epairs.GetMatrix( "rotation", "1 0 0 0 1 0 0 0 1", axis ) ) {
 650                                 float angle = entity->mapEntity->epairs.GetFloat( "angle" );
 651                                 if ( angle != 0.0f ) {
 652                                         axis = idAngles( 0.0f, angle, 0.0f ).ToMat3();
 653                                 } else {
 654                                         axis.Identity();
 655                                 }
 656                         }
 657
 658                         idVec3  origin = entity->mapEntity->epairs.GetVector( "origin" );
 659
 660                         for ( i = 0 ; i < model->NumSurfaces() ; i++ ) {
 661                                 const modelSurface_t *surface = model->Surface( i );
 662                                 const srfTriangles_t *tri = surface->geometry;
 663
 664                                 mapTri_t        mapTri;
 665                                 memset( &mapTri, 0, sizeof( mapTri ) );
 666                                 mapTri.material = surface->shader;
 667                                 // don't let discretes (autosprites, etc) merge together
 668                                 if ( mapTri.material->IsDiscrete() ) {
 669                                         mapTri.mergeGroup = (void *)surface;
 670                                 }
 671                                 for ( int j = 0 ; j < tri->numIndexes ; j += 3 ) {
 672                                         for ( int k = 0 ; k < 3 ; k++ ) {
 673                                                 idVec3 v = tri->verts[tri->indexes[j+k]].xyz;
 674
 675                                                 mapTri.v[k].xyz = v * axis + origin;
 676
 677                                                 mapTri.v[k].normal = tri->verts[tri->indexes[j+k]].normal * axis;
 678                                                 mapTri.v[k].st = tri->verts[tri->indexes[j+k]].st;
 679                                         }
 680                                         AddMapTriToAreas( &mapTri, e );
 681                                 }
 682                         }
 683                 }
 684         }
 685 }
 686
 687 //============================================================================
 688
 689 /*
 690 =================
 691 ClipTriByLight
 692
 693 Carves a triangle by the frustom planes of a light, producing
 694 a (possibly empty) list of triangles on the inside and outside.
 695
 696 The original triangle is not modified.
 697
 698 If no clipping is required, the result will be a copy of the original.
 699
 700 If clipping was required, the outside fragments will be planar clips, which
 701 will benefit from re-optimization.
 702 =================
 703 */
 704 static void ClipTriByLight( const mapLight_t *light, const mapTri_t *tri,
 705                                                    mapTri_t **in, mapTri_t **out ) {
 706         idWinding       *inside, *oldInside;
 707         idWinding       *outside[6];
 708         bool    hasOutside;
 709         int                     i;
 710
 711         *in = NULL;
 712         *out = NULL;
 713
 714         // clip this winding to the light
 715         inside = WindingForTri( tri );
 716         hasOutside = false;
 717         for ( i = 0 ; i < 6 ; i++ ) {
 718                 oldInside = inside;
 719                 if ( oldInside ) {
 720                         oldInside->Split( light->def.frustum[i], 0, &outside[i], &inside );
 721                         delete oldInside;
 722                 }
 723                 else {
 724                         outside[i] = NULL;
 725                 }
 726                 if ( outside[i] ) {
 727                         hasOutside = true;
 728                 }
 729         }
 730
 731         if ( !inside ) {
 732                 // the entire winding is outside this light
 733
 734                 // free the clipped fragments
 735                 for ( i = 0 ; i < 6 ; i++ ) {
 736                         if ( outside[i] ) {
 737                                 delete outside[i];
 738                         }
 739                 }
 740
 741                 *out = CopyMapTri( tri );
 742                 (*out)->next = NULL;
 743
 744                 return;
 745         }
 746
 747         if ( !hasOutside ) {
 748                 // the entire winding is inside this light
 749
 750                 // free the inside copy
 751                 delete inside;
 752
 753                 *in = CopyMapTri( tri );
 754                 (*in)->next = NULL;
 755
 756                 return;
 757         }
 758
 759         // the winding is split
 760         *in = WindingToTriList( inside, tri );
 761         delete inside;
 762
 763         // combine all the outside fragments
 764         for ( i = 0 ; i < 6 ; i++ ) {
 765                 if ( outside[i] ) {
 766                         mapTri_t        *list;
 767
 768                         list = WindingToTriList( outside[i], tri );
 769                         delete outside[i];
 770                         *out = MergeTriLists( *out, list );
 771                 }
 772         }
 773 }
 774
 775 /*
 776 =================
 777 BoundOptimizeGroup
 778 =================
 779 */
 780 static void BoundOptimizeGroup( optimizeGroup_t *group ) {
 781         group->bounds.Clear();
 782         for ( mapTri_t *tri = group->triList ; tri ; tri = tri->next ) {
 783                 group->bounds.AddPoint( tri->v[0].xyz );
 784                 group->bounds.AddPoint( tri->v[1].xyz );
 785                 group->bounds.AddPoint( tri->v[2].xyz );
 786         }
 787 }
 788
 789 /*
 790 ====================
 791 BuildLightShadows
 792
 793 Build the beam tree and shadow volume surface for a light
 794 ====================
 795 */
 796 static void BuildLightShadows( uEntity_t *e, mapLight_t *light ) {
 797         int                     i;
 798         optimizeGroup_t *group;
 799         mapTri_t        *tri;
 800         mapTri_t        *shadowers;
 801         optimizeGroup_t         *shadowerGroups;
 802         idVec3          lightOrigin;
 803         bool            hasPerforatedSurface = false;
 804
 805         //
 806         // build a group list of all the triangles that will contribute to
 807         // the optimized shadow volume, leaving the original triangles alone
 808         //
 809
 810
 811         // shadowers will contain all the triangles that will contribute to the
 812         // shadow volume
 813         shadowerGroups = NULL;
 814         lightOrigin = light->def.globalLightOrigin;
 815
 816         // if the light is no-shadows, don't add any surfaces
 817         // to the beam tree at all
 818         if ( !light->def.parms.noShadows
 819                 && light->def.lightShader->LightCastsShadows() ) {
 820                 for ( i = 0 ; i < e->numAreas ; i++ ) {
 821                         for ( group = e->areas[i].groups ; group ; group = group->nextGroup ) {
 822                                 // if the surface doesn't cast shadows, skip it
 823                                 if ( !group->material->SurfaceCastsShadow() ) {
 824                                         continue;
 825                                 }
 826
 827                                 // if the group doesn't face away from the light, it
 828                                 // won't contribute to the shadow volume
 829                                 if ( dmapGlobals.mapPlanes[ group->planeNum ].Distance( lightOrigin ) > 0 ) {
 830                                         continue;
 831                                 }
 832
 833                                 // if the group bounds doesn't intersect the light bounds,
 834                                 // skip it
 835                                 if ( !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {
 836                                         continue;
 837                                 }
 838
 839                                 // build up a list of the triangle fragments inside the
 840                                 // light frustum
 841                                 shadowers = NULL;
 842                                 for ( tri = group->triList ; tri ; tri = tri->next ) {
 843                                         mapTri_t        *in, *out;
 844
 845                                         // clip it to the light frustum
 846                                         ClipTriByLight( light, tri, &in, &out );
 847                                         FreeTriList( out );
 848                                         shadowers = MergeTriLists( shadowers, in );
 849                                 }
 850
 851                                 // if we didn't get any out of this group, we don't
 852                                 // need to create a new group in the shadower list
 853                                 if ( !shadowers ) {
 854                                         continue;
 855                                 }
 856
 857                                 // find a group in shadowerGroups to add these to
 858                                 // we will ignore everything but planenum, and we
 859                                 // can merge across areas
 860                                 optimizeGroup_t *check;
 861
 862                                 for ( check = shadowerGroups ; check ; check = check->nextGroup ) {
 863                                         if ( check->planeNum == group->planeNum ) {
 864                                                 break;
 865                                         }
 866                                 }
 867                                 if ( !check ) {
 868                                         check = (optimizeGroup_t *)Mem_Alloc( sizeof( *check ) );
 869                                         *check = *group;
 870                                         check->triList = NULL;
 871                                         check->nextGroup = shadowerGroups;
 872                                         shadowerGroups = check;
 873                                 }
 874
 875                                 // if any surface is a shadow-casting perforated or translucent surface, we
 876                                 // can't use the face removal optimizations because we can see through
 877                                 // some of the faces
 878                                 if ( group->material->Coverage() != MC_OPAQUE ) {
 879                                         hasPerforatedSurface = true;
 880                                 }
 881
 882                                 check->triList = MergeTriLists( check->triList, shadowers );
 883                         }
 884                 }
 885         }
 886
 887         // take the shadower group list and create a beam tree and shadow volume
 888         light->shadowTris = CreateLightShadow( shadowerGroups, light );
 889
 890         if ( light->shadowTris && hasPerforatedSurface ) {
 891                 // can't ever remove front faces, because we can see through some of them
 892                 light->shadowTris->numShadowIndexesNoCaps = light->shadowTris->numShadowIndexesNoFrontCaps =
 893                         light->shadowTris->numIndexes;
 894         }
 895
 896         // we don't need the original shadower triangles for anything else
 897         FreeOptimizeGroupList( shadowerGroups );
 898 }
 899
 900
 901 /*
 902 ====================
 903 CarveGroupsByLight
 904
 905 Divide each group into an inside group and an outside group, based
 906 on which fragments are illuminated by the light's beam tree
 907 ====================
 908 */
 909 static void CarveGroupsByLight( uEntity_t *e, mapLight_t *light ) {
 910         int                     i;
 911         optimizeGroup_t *group, *newGroup, *carvedGroups, *nextGroup;
 912         mapTri_t        *tri, *inside, *outside;
 913         uArea_t         *area;
 914
 915         for ( i = 0 ; i < e->numAreas ; i++ ) {
 916                 area = &e->areas[i];
 917                 carvedGroups = NULL;
 918
 919                 // we will be either freeing or reassigning the groups as we go
 920                 for ( group = area->groups ; group ; group = nextGroup ) {
 921                         nextGroup = group->nextGroup;
 922                         // if the surface doesn't get lit, don't carve it up
 923                         if ( ( light->def.lightShader->IsFogLight() && !group->material->ReceivesFog() )
 924                                 || ( !light->def.lightShader->IsFogLight() && !group->material->ReceivesLighting() )
 925                                 || !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {
 926
 927                                 group->nextGroup = carvedGroups;
 928                                 carvedGroups = group;
 929                                 continue;
 930                         }
 931
 932                         if ( group->numGroupLights == MAX_GROUP_LIGHTS ) {
 933                                 common->Error( "MAX_GROUP_LIGHTS around %f %f %f",
 934                                          group->triList->v[0].xyz[0], group->triList->v[0].xyz[1], group->triList->v[0].xyz[2] );
 935                         }
 936
 937                         // if the group doesn't face the light,
 938                         // it won't get carved at all
 939                         if ( !light->def.lightShader->LightEffectsBackSides() &&
 940                                 !group->material->ReceivesLightingOnBackSides() &&
 941                                 dmapGlobals.mapPlanes[ group->planeNum ].Distance( light->def.parms.origin ) <= 0  ) {
 942
 943                                 group->nextGroup = carvedGroups;
 944                                 carvedGroups = group;
 945                                 continue;
 946                         }
 947
 948                         // split into lists for hit-by-light, and not-hit-by-light
 949                         inside = NULL;
 950                         outside = NULL;
 951
 952                         for ( tri = group->triList ; tri ; tri = tri->next ) {
 953                                 mapTri_t        *in, *out;
 954
 955                                 ClipTriByLight( light, tri, &in, &out );
 956                                 inside = MergeTriLists( inside, in );
 957                                 outside = MergeTriLists( outside, out );
 958                         }
 959
 960                         if ( inside ) {
 961                                 newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
 962                                 *newGroup = *group;
 963                                 newGroup->groupLights[newGroup->numGroupLights] = light;
 964                                 newGroup->numGroupLights++;
 965                                 newGroup->triList = inside;
 966                                 newGroup->nextGroup = carvedGroups;
 967                                 carvedGroups = newGroup;
 968                         }
 969
 970                         if ( outside ) {
 971                                 newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
 972                                 *newGroup = *group;
 973                                 newGroup->triList = outside;
 974                                 newGroup->nextGroup = carvedGroups;
 975                                 carvedGroups = newGroup;
 976                         }
 977
 978                         // free the original
 979                         group->nextGroup = NULL;
 980                         FreeOptimizeGroupList( group );
 981                 }
 982
 983                 // replace this area's group list with the new one
 984                 area->groups = carvedGroups;
 985         }
 986 }
 987
 988 /*
 989 =====================
 990 Prelight
 991
 992 Break optimize groups up into additional groups at light boundaries, so
 993 optimization won't cross light bounds
 994 =====================
 995 */
 996 void Prelight( uEntity_t *e ) {
 997         int                     i;
 998         int                     start, end;
 999         mapLight_t      *light;
1000
1001         // don't prelight anything but the world entity
1002         if ( dmapGlobals.entityNum != 0 ) {
1003                 return;
1004         }
1005
1006         if ( dmapGlobals.shadowOptLevel > 0 ) {
1007                 common->Printf( "----- BuildLightShadows -----\n" );
1008                 start = Sys_Milliseconds();
1009
1010                 // calc bounds for all the groups to speed things up
1011                 for ( i = 0 ; i < e->numAreas ; i++ ) {
1012                         uArea_t *area = &e->areas[i];
1013
1014                         for ( optimizeGroup_t *group = area->groups ; group ; group = group->nextGroup ) {
1015                                 BoundOptimizeGroup( group );
1016                         }
1017                 }
1018
1019                 for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
1020                         light = dmapGlobals.mapLights[i];
1021                         BuildLightShadows( e, light );
1022                 }
1023
1024                 end = Sys_Milliseconds();
1025                 common->Printf( "%5.1f seconds for BuildLightShadows\n", ( end - start ) / 1000.0 );
1026         }
1027
1028
1029         if ( !dmapGlobals.noLightCarve ) {
1030                 common->Printf( "----- CarveGroupsByLight -----\n" );
1031                 start = Sys_Milliseconds();
1032                 // now subdivide the optimize groups into additional groups for
1033                 // each light that illuminates them
1034                 for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
1035                         light = dmapGlobals.mapLights[i];
1036                         CarveGroupsByLight( e, light );
1037                 }
1038
1039                 end = Sys_Milliseconds();
1040                 common->Printf( "%5.1f seconds for CarveGroupsByLight\n", ( end - start ) / 1000.0 );
1041         }
1042
1043 }
1044
1045
1046