tools/quake2/q2map/lightmap.c

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21 #include "qrad.h"
  22
  23 #define MAX_LSTYLES 256
  24
  25 typedef struct
  26 {
  27         dface_t     *faces[2];
  28         qboolean coplanar;
  29 } edgeshare_t;
  30
  31 edgeshare_t edgeshare[MAX_MAP_EDGES];
  32
  33 int facelinks[MAX_MAP_FACES];
  34 int planelinks[2][MAX_MAP_PLANES];
  35
  36 /*
  37    ============
  38    LinkPlaneFaces
  39    ============
  40  */
  41 void LinkPlaneFaces( void ){
  42         int i;
  43         dface_t *f;
  44
  45         f = dfaces;
  46         for ( i = 0 ; i < numfaces ; i++, f++ )
  47         {
  48                 facelinks[i] = planelinks[f->side][f->planenum];
  49                 planelinks[f->side][f->planenum] = i;
  50         }
  51 }
  52
  53 /*
  54    ============
  55    PairEdges
  56    ============
  57  */
  58 void PairEdges( void ){
  59         int i, j, k;
  60         dface_t *f;
  61         edgeshare_t *e;
  62
  63         f = dfaces;
  64         for ( i = 0 ; i < numfaces ; i++, f++ )
  65         {
  66                 for ( j = 0 ; j < f->numedges ; j++ )
  67                 {
  68                         k = dsurfedges[f->firstedge + j];
  69                         if ( k < 0 ) {
  70                                 e = &edgeshare[-k];
  71                                 e->faces[1] = f;
  72                         }
  73                         else
  74                         {
  75                                 e = &edgeshare[k];
  76                                 e->faces[0] = f;
  77                         }
  78
  79                         if ( e->faces[0] && e->faces[1] ) {
  80                                 // determine if coplanar
  81                                 if ( e->faces[0]->planenum == e->faces[1]->planenum ) {
  82                                         e->coplanar = true;
  83                                 }
  84                         }
  85                 }
  86         }
  87 }
  88
  89 /*
  90    =================================================================
  91
  92    POINT TRIANGULATION
  93
  94    =================================================================
  95  */
  96
  97 typedef struct triedge_s
  98 {
  99         int p0, p1;
 100         vec3_t normal;
 101         vec_t dist;
 102         struct triangle_s   *tri;
 103 } triedge_t;
 104
 105 typedef struct triangle_s
 106 {
 107         triedge_t   *edges[3];
 108 } triangle_t;
 109
 110 #define MAX_TRI_POINTS      1024
 111 #define MAX_TRI_EDGES       ( MAX_TRI_POINTS * 6 )
 112 #define MAX_TRI_TRIS        ( MAX_TRI_POINTS * 2 )
 113
 114 typedef struct
 115 {
 116         int numpoints;
 117         int numedges;
 118         int numtris;
 119         dplane_t    *plane;
 120         triedge_t   *edgematrix[MAX_TRI_POINTS][MAX_TRI_POINTS];
 121         patch_t     *points[MAX_TRI_POINTS];
 122         triedge_t edges[MAX_TRI_EDGES];
 123         triangle_t tris[MAX_TRI_TRIS];
 124 } triangulation_t;
 125
 126 /*
 127    ===============
 128    AllocTriangulation
 129    ===============
 130  */
 131 triangulation_t *AllocTriangulation( dplane_t *plane ){
 132         triangulation_t *t;
 133
 134         t = malloc( sizeof( triangulation_t ) );
 135         t->numpoints = 0;
 136         t->numedges = 0;
 137         t->numtris = 0;
 138
 139         t->plane = plane;
 140
 141 //      memset (t->edgematrix, 0, sizeof(t->edgematrix));
 142
 143         return t;
 144 }
 145
 146 /*
 147    ===============
 148    FreeTriangulation
 149    ===============
 150  */
 151 void FreeTriangulation( triangulation_t *tr ){
 152         free( tr );
 153 }
 154
 155
 156 triedge_t   *FindEdge( triangulation_t *trian, int p0, int p1 ){
 157         triedge_t   *e, *be;
 158         vec3_t v1;
 159         vec3_t normal;
 160         vec_t dist;
 161
 162         if ( trian->edgematrix[p0][p1] ) {
 163                 return trian->edgematrix[p0][p1];
 164         }
 165
 166         if ( trian->numedges > MAX_TRI_EDGES - 2 ) {
 167                 Error( "trian->numedges > MAX_TRI_EDGES-2" );
 168         }
 169
 170         VectorSubtract( trian->points[p1]->origin, trian->points[p0]->origin, v1 );
 171         VectorNormalize( v1, v1 );
 172         CrossProduct( v1, trian->plane->normal, normal );
 173         dist = DotProduct( trian->points[p0]->origin, normal );
 174
 175         e = &trian->edges[trian->numedges];
 176         e->p0 = p0;
 177         e->p1 = p1;
 178         e->tri = NULL;
 179         VectorCopy( normal, e->normal );
 180         e->dist = dist;
 181         trian->numedges++;
 182         trian->edgematrix[p0][p1] = e;
 183
 184         be = &trian->edges[trian->numedges];
 185         be->p0 = p1;
 186         be->p1 = p0;
 187         be->tri = NULL;
 188         VectorSubtract( vec3_origin, normal, be->normal );
 189         be->dist = -dist;
 190         trian->numedges++;
 191         trian->edgematrix[p1][p0] = be;
 192
 193         return e;
 194 }
 195
 196 triangle_t  *AllocTriangle( triangulation_t *trian ){
 197         triangle_t  *t;
 198
 199         if ( trian->numtris >= MAX_TRI_TRIS ) {
 200                 Error( "trian->numtris >= MAX_TRI_TRIS" );
 201         }
 202
 203         t = &trian->tris[trian->numtris];
 204         trian->numtris++;
 205
 206         return t;
 207 }
 208
 209 /*
 210    ============
 211    TriEdge_r
 212    ============
 213  */
 214 void TriEdge_r( triangulation_t *trian, triedge_t *e ){
 215         int i, bestp;
 216         vec3_t v1, v2;
 217         vec_t   *p0, *p1, *p;
 218         vec_t best, ang;
 219         triangle_t  *nt;
 220
 221         if ( e->tri ) {
 222                 return;     // allready connected by someone
 223
 224         }
 225         // find the point with the best angle
 226         p0 = trian->points[e->p0]->origin;
 227         p1 = trian->points[e->p1]->origin;
 228         best = 1.1;
 229         for ( i = 0 ; i < trian->numpoints ; i++ )
 230         {
 231                 p = trian->points[i]->origin;
 232                 // a 0 dist will form a degenerate triangle
 233                 if ( DotProduct( p, e->normal ) - e->dist < 0 ) {
 234                         continue;   // behind edge
 235                 }
 236                 VectorSubtract( p0, p, v1 );
 237                 VectorSubtract( p1, p, v2 );
 238                 if ( !VectorNormalize( v1,v1 ) ) {
 239                         continue;
 240                 }
 241                 if ( !VectorNormalize( v2,v2 ) ) {
 242                         continue;
 243                 }
 244                 ang = DotProduct( v1, v2 );
 245                 if ( ang < best ) {
 246                         best = ang;
 247                         bestp = i;
 248                 }
 249         }
 250         if ( best >= 1 ) {
 251                 return;     // edge doesn't match anything
 252
 253         }
 254         // make a new triangle
 255         nt = AllocTriangle( trian );
 256         nt->edges[0] = e;
 257         nt->edges[1] = FindEdge( trian, e->p1, bestp );
 258         nt->edges[2] = FindEdge( trian, bestp, e->p0 );
 259         for ( i = 0 ; i < 3 ; i++ )
 260                 nt->edges[i]->tri = nt;
 261         TriEdge_r( trian, FindEdge( trian, bestp, e->p1 ) );
 262         TriEdge_r( trian, FindEdge( trian, e->p0, bestp ) );
 263 }
 264
 265 /*
 266    ============
 267    TriangulatePoints
 268    ============
 269  */
 270 void TriangulatePoints( triangulation_t *trian ){
 271         vec_t d, bestd;
 272         vec3_t v1;
 273         int bp1, bp2, i, j;
 274         vec_t   *p1, *p2;
 275         triedge_t   *e, *e2;
 276
 277         if ( trian->numpoints < 2 ) {
 278                 return;
 279         }
 280
 281         // find the two closest points
 282         bestd = 9999;
 283         for ( i = 0 ; i < trian->numpoints ; i++ )
 284         {
 285                 p1 = trian->points[i]->origin;
 286                 for ( j = i + 1 ; j < trian->numpoints ; j++ )
 287                 {
 288                         p2 = trian->points[j]->origin;
 289                         VectorSubtract( p2, p1, v1 );
 290                         d = VectorLength( v1 );
 291                         if ( d < bestd ) {
 292                                 bestd = d;
 293                                 bp1 = i;
 294                                 bp2 = j;
 295                         }
 296                 }
 297         }
 298
 299         e = FindEdge( trian, bp1, bp2 );
 300         e2 = FindEdge( trian, bp2, bp1 );
 301         TriEdge_r( trian, e );
 302         TriEdge_r( trian, e2 );
 303 }
 304
 305 /*
 306    ===============
 307    AddPointToTriangulation
 308    ===============
 309  */
 310 void AddPointToTriangulation( patch_t *patch, triangulation_t *trian ){
 311         int pnum;
 312
 313         pnum = trian->numpoints;
 314         if ( pnum == MAX_TRI_POINTS ) {
 315                 Error( "trian->numpoints == MAX_TRI_POINTS" );
 316         }
 317         trian->points[pnum] = patch;
 318         trian->numpoints++;
 319 }
 320
 321 /*
 322    ===============
 323    LerpTriangle
 324    ===============
 325  */
 326 void    LerpTriangle( triangulation_t *trian, triangle_t *t, vec3_t point, vec3_t color ){
 327         patch_t     *p1, *p2, *p3;
 328         vec3_t base, d1, d2;
 329         float x, y, x1, y1, x2, y2;
 330
 331         p1 = trian->points[t->edges[0]->p0];
 332         p2 = trian->points[t->edges[1]->p0];
 333         p3 = trian->points[t->edges[2]->p0];
 334
 335         VectorCopy( p1->totallight, base );
 336         VectorSubtract( p2->totallight, base, d1 );
 337         VectorSubtract( p3->totallight, base, d2 );
 338
 339         x = DotProduct( point, t->edges[0]->normal ) - t->edges[0]->dist;
 340         y = DotProduct( point, t->edges[2]->normal ) - t->edges[2]->dist;
 341
 342         x1 = 0;
 343         y1 = DotProduct( p2->origin, t->edges[2]->normal ) - t->edges[2]->dist;
 344
 345         x2 = DotProduct( p3->origin, t->edges[0]->normal ) - t->edges[0]->dist;
 346         y2 = 0;
 347
 348         if ( fabs( y1 ) < ON_EPSILON || fabs( x2 ) < ON_EPSILON ) {
 349                 VectorCopy( base, color );
 350                 return;
 351         }
 352
 353         VectorMA( base, x / x2, d2, color );
 354         VectorMA( color, y / y1, d1, color );
 355 }
 356
 357 qboolean PointInTriangle( vec3_t point, triangle_t *t ){
 358         int i;
 359         triedge_t   *e;
 360         vec_t d;
 361
 362         for ( i = 0 ; i < 3 ; i++ )
 363         {
 364                 e = t->edges[i];
 365                 d = DotProduct( e->normal, point ) - e->dist;
 366                 if ( d < 0 ) {
 367                         return false;   // not inside
 368                 }
 369         }
 370
 371         return true;
 372 }
 373
 374 /*
 375    ===============
 376    SampleTriangulation
 377    ===============
 378  */
 379 void SampleTriangulation( vec3_t point, triangulation_t *trian, vec3_t color ){
 380         triangle_t  *t;
 381         triedge_t   *e;
 382         vec_t d, best;
 383         patch_t     *p0, *p1;
 384         vec3_t v1, v2;
 385         int i, j;
 386
 387         if ( trian->numpoints == 0 ) {
 388                 VectorClear( color );
 389                 return;
 390         }
 391         if ( trian->numpoints == 1 ) {
 392                 VectorCopy( trian->points[0]->totallight, color );
 393                 return;
 394         }
 395
 396         // search for triangles
 397         for ( t = trian->tris, j = 0 ; j < trian->numtris ; t++, j++ )
 398         {
 399                 if ( !PointInTriangle( point, t ) ) {
 400                         continue;
 401                 }
 402
 403                 // this is it
 404                 LerpTriangle( trian, t, point, color );
 405                 return;
 406         }
 407
 408         // search for exterior edge
 409         for ( e = trian->edges, j = 0 ; j < trian->numedges ; e++, j++ )
 410         {
 411                 if ( e->tri ) {
 412                         continue;       // not an exterior edge
 413
 414                 }
 415                 d = DotProduct( point, e->normal ) - e->dist;
 416                 if ( d < 0 ) {
 417                         continue;   // not in front of edge
 418
 419                 }
 420                 p0 = trian->points[e->p0];
 421                 p1 = trian->points[e->p1];
 422
 423                 VectorSubtract( p1->origin, p0->origin, v1 );
 424                 VectorNormalize( v1, v1 );
 425                 VectorSubtract( point, p0->origin, v2 );
 426                 d = DotProduct( v2, v1 );
 427                 if ( d < 0 ) {
 428                         continue;
 429                 }
 430                 if ( d > 1 ) {
 431                         continue;
 432                 }
 433                 for ( i = 0 ; i < 3 ; i++ )
 434                         color[i] = p0->totallight[i] + d * ( p1->totallight[i] - p0->totallight[i] );
 435                 return;
 436         }
 437
 438         // search for nearest point
 439         best = 99999;
 440         p1 = NULL;
 441         for ( j = 0 ; j < trian->numpoints ; j++ )
 442         {
 443                 p0 = trian->points[j];
 444                 VectorSubtract( point, p0->origin, v1 );
 445                 d = VectorLength( v1 );
 446                 if ( d < best ) {
 447                         best = d;
 448                         p1 = p0;
 449                 }
 450         }
 451
 452         if ( !p1 ) {
 453                 Error( "SampleTriangulation: no points" );
 454         }
 455
 456         VectorCopy( p1->totallight, color );
 457 }
 458
 459 /*
 460    =================================================================
 461
 462    LIGHTMAP SAMPLE GENERATION
 463
 464    =================================================================
 465  */
 466
 467
 468 #define SINGLEMAP   ( 64 * 64 * 4 )
 469
 470 typedef struct
 471 {
 472         vec_t facedist;
 473         vec3_t facenormal;
 474
 475         int numsurfpt;
 476         vec3_t surfpt[SINGLEMAP];
 477
 478         vec3_t modelorg;        // for origined bmodels
 479
 480         vec3_t texorg;
 481         vec3_t worldtotex[2];   // s = (world - texorg) . worldtotex[0]
 482         vec3_t textoworld[2];   // world = texorg + s * textoworld[0]
 483
 484         vec_t exactmins[2], exactmaxs[2];
 485
 486         int texmins[2], texsize[2];
 487         int surfnum;
 488         dface_t *face;
 489 } lightinfo_t;
 490
 491
 492 /*
 493    ================
 494    CalcFaceExtents
 495
 496    Fills in s->texmins[] and s->texsize[]
 497    also sets exactmins[] and exactmaxs[]
 498    ================
 499  */
 500 void CalcFaceExtents( lightinfo_t *l ){
 501         dface_t *s;
 502         vec_t mins[2], maxs[2], val;
 503         int i,j, e;
 504         dvertex_t   *v;
 505         texinfo_t   *tex;
 506         vec3_t vt;
 507
 508         s = l->face;
 509
 510         mins[0] = mins[1] = 999999;
 511         maxs[0] = maxs[1] = -99999;
 512
 513         tex = &texinfo[s->texinfo];
 514
 515         for ( i = 0 ; i < s->numedges ; i++ )
 516         {
 517                 e = dsurfedges[s->firstedge + i];
 518                 if ( e >= 0 ) {
 519                         v = dvertexes + dedges[e].v[0];
 520                 }
 521                 else{
 522                         v = dvertexes + dedges[-e].v[1];
 523                 }
 524
 525 //              VectorAdd (v->point, l->modelorg, vt);
 526                 VectorCopy( v->point, vt );
 527
 528                 for ( j = 0 ; j < 2 ; j++ )
 529                 {
 530                         val = DotProduct( vt, tex->vecs[j] ) + tex->vecs[j][3];
 531                         if ( val < mins[j] ) {
 532                                 mins[j] = val;
 533                         }
 534                         if ( val > maxs[j] ) {
 535                                 maxs[j] = val;
 536                         }
 537                 }
 538         }
 539
 540         for ( i = 0 ; i < 2 ; i++ )
 541         {
 542                 l->exactmins[i] = mins[i];
 543                 l->exactmaxs[i] = maxs[i];
 544
 545                 mins[i] = floor( mins[i] / 16 );
 546                 maxs[i] = ceil( maxs[i] / 16 );
 547
 548                 l->texmins[i] = mins[i];
 549                 l->texsize[i] = maxs[i] - mins[i];
 550                 if ( l->texsize[0] * l->texsize[1] > SINGLEMAP / 4 ) {  // div 4 for extrasamples
 551                         Error( "Surface to large to map" );
 552                 }
 553         }
 554 }
 555
 556 /*
 557    ================
 558    CalcFaceVectors
 559
 560    Fills in texorg, worldtotex. and textoworld
 561    ================
 562  */
 563 void CalcFaceVectors( lightinfo_t *l ){
 564         texinfo_t   *tex;
 565         int i, j;
 566         vec3_t texnormal;
 567         vec_t distscale;
 568         vec_t dist, len;
 569         int w, h;
 570
 571         tex = &texinfo[l->face->texinfo];
 572
 573 // convert from float to double
 574         for ( i = 0 ; i < 2 ; i++ )
 575                 for ( j = 0 ; j < 3 ; j++ )
 576                         l->worldtotex[i][j] = tex->vecs[i][j];
 577
 578 // calculate a normal to the texture axis.  points can be moved along this
 579 // without changing their S/T
 580         texnormal[0] = tex->vecs[1][1] * tex->vecs[0][2]
 581                                    - tex->vecs[1][2] * tex->vecs[0][1];
 582         texnormal[1] = tex->vecs[1][2] * tex->vecs[0][0]
 583                                    - tex->vecs[1][0] * tex->vecs[0][2];
 584         texnormal[2] = tex->vecs[1][0] * tex->vecs[0][1]
 585                                    - tex->vecs[1][1] * tex->vecs[0][0];
 586         VectorNormalize( texnormal, texnormal );
 587
 588 // flip it towards plane normal
 589         distscale = DotProduct( texnormal, l->facenormal );
 590         if ( !distscale ) {
 591                 Sys_FPrintf( SYS_VRB, "WARNING: Texture axis perpendicular to face\n" );
 592                 distscale = 1;
 593         }
 594         if ( distscale < 0 ) {
 595                 distscale = -distscale;
 596                 VectorSubtract( vec3_origin, texnormal, texnormal );
 597         }
 598
 599 // distscale is the ratio of the distance along the texture normal to
 600 // the distance along the plane normal
 601         distscale = 1 / distscale;
 602
 603         for ( i = 0 ; i < 2 ; i++ )
 604         {
 605                 len = VectorLength( l->worldtotex[i] );
 606                 dist = DotProduct( l->worldtotex[i], l->facenormal );
 607                 dist *= distscale;
 608                 VectorMA( l->worldtotex[i], -dist, texnormal, l->textoworld[i] );
 609                 VectorScale( l->textoworld[i], ( 1 / len ) * ( 1 / len ), l->textoworld[i] );
 610         }
 611
 612
 613 // calculate texorg on the texture plane
 614         for ( i = 0 ; i < 3 ; i++ )
 615                 l->texorg[i] = -tex->vecs[0][3] * l->textoworld[0][i] - tex->vecs[1][3] * l->textoworld[1][i];
 616
 617 // project back to the face plane
 618         dist = DotProduct( l->texorg, l->facenormal ) - l->facedist - 1;
 619         dist *= distscale;
 620         VectorMA( l->texorg, -dist, texnormal, l->texorg );
 621
 622         // compensate for org'd bmodels
 623         VectorAdd( l->texorg, l->modelorg, l->texorg );
 624
 625         // total sample count
 626         h = l->texsize[1] + 1;
 627         w = l->texsize[0] + 1;
 628         l->numsurfpt = w * h;
 629 }
 630
 631 /*
 632    =================
 633    CalcPoints
 634
 635    For each texture aligned grid point, back project onto the plane
 636    to get the world xyz value of the sample point
 637    =================
 638  */
 639 void CalcPoints( lightinfo_t *l, float sofs, float tofs ){
 640         int i;
 641         int s, t, j;
 642         int w, h, step;
 643         vec_t starts, startt, us, ut;
 644         vec_t   *surf;
 645         vec_t mids, midt;
 646         vec3_t facemid;
 647         dleaf_t *leaf;
 648
 649         surf = l->surfpt[0];
 650         mids = ( l->exactmaxs[0] + l->exactmins[0] ) / 2;
 651         midt = ( l->exactmaxs[1] + l->exactmins[1] ) / 2;
 652
 653         for ( j = 0 ; j < 3 ; j++ )
 654                 facemid[j] = l->texorg[j] + l->textoworld[0][j] * mids + l->textoworld[1][j] * midt;
 655
 656         h = l->texsize[1] + 1;
 657         w = l->texsize[0] + 1;
 658         l->numsurfpt = w * h;
 659
 660         starts = l->texmins[0] * 16;
 661         startt = l->texmins[1] * 16;
 662         step = 16;
 663
 664
 665         for ( t = 0 ; t < h ; t++ )
 666         {
 667                 for ( s = 0 ; s < w ; s++, surf += 3 )
 668                 {
 669                         us = starts + ( s + sofs ) * step;
 670                         ut = startt + ( t + tofs ) * step;
 671
 672
 673                         // if a line can be traced from surf to facemid, the point is good
 674                         for ( i = 0 ; i < 6 ; i++ )
 675                         {
 676                                 // calculate texture point
 677                                 for ( j = 0 ; j < 3 ; j++ )
 678                                         surf[j] = l->texorg[j] + l->textoworld[0][j] * us
 679                                                           + l->textoworld[1][j] * ut;
 680
 681                                 leaf = Rad_PointInLeaf( surf );
 682                                 if ( leaf->contents != CONTENTS_SOLID ) {
 683                                         if ( !TestLine_r( 0, facemid, surf ) ) {
 684                                                 break;  // got it
 685                                         }
 686                                 }
 687
 688                                 // nudge it
 689                                 if ( i & 1 ) {
 690                                         if ( us > mids ) {
 691                                                 us -= 8;
 692                                                 if ( us < mids ) {
 693                                                         us = mids;
 694                                                 }
 695                                         }
 696                                         else
 697                                         {
 698                                                 us += 8;
 699                                                 if ( us > mids ) {
 700                                                         us = mids;
 701                                                 }
 702                                         }
 703                                 }
 704                                 else
 705                                 {
 706                                         if ( ut > midt ) {
 707                                                 ut -= 8;
 708                                                 if ( ut < midt ) {
 709                                                         ut = midt;
 710                                                 }
 711                                         }
 712                                         else
 713                                         {
 714                                                 ut += 8;
 715                                                 if ( ut > midt ) {
 716                                                         ut = midt;
 717                                                 }
 718                                         }
 719                                 }
 720                         }
 721                 }
 722         }
 723
 724 }
 725
 726
 727 //==============================================================
 728
 729
 730
 731 #define MAX_STYLES  32
 732 typedef struct
 733 {
 734         int numsamples;
 735         float       *origins;
 736         int numstyles;
 737         int stylenums[MAX_STYLES];
 738         float       *samples[MAX_STYLES];
 739 } facelight_t;
 740
 741 directlight_t   *directlights[MAX_MAP_LEAFS];
 742 facelight_t facelight[MAX_MAP_FACES];
 743 int numdlights;
 744
 745 /*
 746    ==================
 747    FindTargetEntity
 748    ==================
 749  */
 750 entity_t *FindTargetEntity( char *target ){
 751         int i;
 752         char    *n;
 753
 754         for ( i = 0 ; i < num_entities ; i++ )
 755         {
 756                 n = ValueForKey( &entities[i], "targetname" );
 757                 if ( !strcmp( n, target ) ) {
 758                         return &entities[i];
 759                 }
 760         }
 761
 762         return NULL;
 763 }
 764
 765 //#define       DIRECT_LIGHT    3000
 766 #define DIRECT_LIGHT    3
 767
 768 /*
 769    =============
 770    CreateDirectLights
 771    =============
 772  */
 773 void CreateDirectLights( void ){
 774         int i;
 775         patch_t *p;
 776         directlight_t   *dl;
 777         dleaf_t *leaf;
 778         int cluster;
 779         entity_t    *e, *e2;
 780         char    *name;
 781         char    *target;
 782         float angle;
 783         vec3_t dest;
 784         char    *_color;
 785         float intensity;
 786
 787         //
 788         // surfaces
 789         //
 790         for ( i = 0, p = patches ; i < (int) num_patches ; i++, p++ )
 791         {
 792                 if ( p->totallight[0] < DIRECT_LIGHT
 793                          && p->totallight[1] < DIRECT_LIGHT
 794                          && p->totallight[2] < DIRECT_LIGHT ) {
 795                         continue;
 796                 }
 797
 798                 numdlights++;
 799                 dl = malloc( sizeof( directlight_t ) );
 800                 memset( dl, 0, sizeof( *dl ) );
 801
 802                 VectorCopy( p->origin, dl->origin );
 803
 804                 leaf = Rad_PointInLeaf( dl->origin );
 805                 cluster = leaf->cluster;
 806                 dl->next = directlights[cluster];
 807                 directlights[cluster] = dl;
 808
 809                 dl->type = emit_surface;
 810                 VectorCopy( p->plane->normal, dl->normal );
 811
 812                 dl->intensity = ColorNormalize( p->totallight, dl->color );
 813                 dl->intensity *= p->area * direct_scale;
 814                 VectorClear( p->totallight );    // all sent now
 815         }
 816
 817         //
 818         // entities
 819         //
 820         for ( i = 0 ; i < num_entities ; i++ )
 821         {
 822                 e = &entities[i];
 823                 name = ValueForKey( e, "classname" );
 824                 if ( strncmp( name, "light", 5 ) ) {
 825                         continue;
 826                 }
 827
 828                 numdlights++;
 829                 dl = malloc( sizeof( directlight_t ) );
 830                 memset( dl, 0, sizeof( *dl ) );
 831
 832                 GetVectorForKey( e, "origin", dl->origin );
 833                 dl->style = FloatForKey( e, "_style" );
 834                 if ( !dl->style ) {
 835                         dl->style = FloatForKey( e, "style" );
 836                 }
 837                 if ( dl->style < 0 || dl->style >= MAX_LSTYLES ) {
 838                         dl->style = 0;
 839                 }
 840
 841                 leaf = Rad_PointInLeaf( dl->origin );
 842                 cluster = leaf->cluster;
 843
 844                 dl->next = directlights[cluster];
 845                 directlights[cluster] = dl;
 846
 847                 intensity = FloatForKey( e, "light" );
 848                 if ( !intensity ) {
 849                         intensity = FloatForKey( e, "_light" );
 850                 }
 851                 if ( !intensity ) {
 852                         intensity = 300;
 853                 }
 854                 _color = ValueForKey( e, "_color" );
 855                 if ( _color && _color[0] ) {
 856                         sscanf( _color, "%f %f %f", &dl->color[0],&dl->color[1],&dl->color[2] );
 857                         ColorNormalize( dl->color, dl->color );
 858                 }
 859                 else{
 860                         dl->color[0] = dl->color[1] = dl->color[2] = 1.0;
 861                 }
 862                 dl->intensity = intensity * entity_scale;
 863                 dl->type = emit_point;
 864
 865                 target = ValueForKey( e, "target" );
 866
 867                 if ( !strcmp( name, "light_spot" ) || target[0] ) {
 868                         dl->type = emit_spotlight;
 869                         dl->stopdot = FloatForKey( e, "_cone" );
 870                         if ( !dl->stopdot ) {
 871                                 dl->stopdot = 10;
 872                         }
 873                         dl->stopdot = cos( dl->stopdot / 180 * 3.14159 );
 874                         if ( target[0] ) { // point towards target
 875                                 e2 = FindTargetEntity( target );
 876                                 if ( !e2 ) {
 877                                         Sys_FPrintf( SYS_WRN, "WARNING: light at (%i %i %i) has missing target\n",
 878                                                                 (int)dl->origin[0], (int)dl->origin[1], (int)dl->origin[2] );
 879                                 }
 880                                 else
 881                                 {
 882                                         GetVectorForKey( e2, "origin", dest );
 883                                         VectorSubtract( dest, dl->origin, dl->normal );
 884                                         VectorNormalize( dl->normal, dl->normal );
 885                                 }
 886                         }
 887                         else
 888                         {   // point down angle
 889                                 angle = FloatForKey( e, "angle" );
 890                                 if ( angle == ANGLE_UP ) {
 891                                         dl->normal[0] = dl->normal[1] = 0;
 892                                         dl->normal[2] = 1;
 893                                 }
 894                                 else if ( angle == ANGLE_DOWN ) {
 895                                         dl->normal[0] = dl->normal[1] = 0;
 896                                         dl->normal[2] = -1;
 897                                 }
 898                                 else
 899                                 {
 900                                         dl->normal[2] = 0;
 901                                         dl->normal[0] = cos( angle / 180 * 3.14159 );
 902                                         dl->normal[1] = sin( angle / 180 * 3.14159 );
 903                                 }
 904                         }
 905                 }
 906         }
 907
 908         Sys_FPrintf( SYS_VRB, "%i direct lights\n", numdlights );
 909 }
 910
 911 /*
 912    =============
 913    GatherSampleLight
 914
 915    Lightscale is the normalizer for multisampling
 916    =============
 917  */
 918 void GatherSampleLight( vec3_t pos, vec3_t normal,
 919                                                 float **styletable, int offset, int mapsize, float lightscale ){
 920         int i;
 921         directlight_t   *l;
 922         byte pvs[( MAX_MAP_LEAFS + 7 ) / 8];
 923         vec3_t delta;
 924         float dot, dot2;
 925         float dist;
 926         float scale;
 927         float           *dest;
 928
 929         // get the PVS for the pos to limit the number of checks
 930         if ( !PvsForOrigin( pos, pvs ) ) {
 931                 return;
 932         }
 933
 934         for ( i = 0 ; i < dvis->numclusters ; i++ )
 935         {
 936                 if ( !( pvs[ i >> 3] & ( 1 << ( i & 7 ) ) ) ) {
 937                         continue;
 938                 }
 939
 940                 for ( l = directlights[i] ; l ; l = l->next )
 941                 {
 942                         VectorSubtract( l->origin, pos, delta );
 943                         dist = VectorNormalize( delta, delta );
 944                         dot = DotProduct( delta, normal );
 945                         if ( dot <= 0.001 ) {
 946                                 continue;   // behind sample surface
 947
 948                         }
 949                         switch ( l->type )
 950                         {
 951                         case emit_point:
 952                                 // linear falloff
 953                                 scale = ( l->intensity - dist ) * dot;
 954                                 break;
 955
 956                         case emit_surface:
 957                                 dot2 = -DotProduct( delta, l->normal );
 958                                 if ( dot2 <= 0.001 ) {
 959                                         goto skipadd;   // behind light surface
 960                                 }
 961                                 scale = ( l->intensity / ( dist * dist ) ) * dot * dot2;
 962                                 break;
 963
 964                         case emit_spotlight:
 965                                 // linear falloff
 966                                 dot2 = -DotProduct( delta, l->normal );
 967                                 if ( dot2 <= l->stopdot ) {
 968                                         goto skipadd;   // outside light cone
 969                                 }
 970                                 scale = ( l->intensity - dist ) * dot;
 971                                 break;
 972                         default:
 973                                 Error( "Bad l->type" );
 974                         }
 975
 976                         if ( TestLine_r( 0, pos, l->origin ) ) {
 977                                 continue;   // occluded
 978
 979                         }
 980                         if ( scale <= 0 ) {
 981                                 continue;
 982                         }
 983
 984                         // if this style doesn't have a table yet, allocate one
 985                         if ( !styletable[l->style] ) {
 986                                 styletable[l->style] = malloc( mapsize );
 987                                 memset( styletable[l->style], 0, mapsize );
 988                         }
 989
 990                         dest = styletable[l->style] + offset;
 991                         // add some light to it
 992                         VectorMA( dest, scale * lightscale, l->color, dest );
 993
 994 skipadd: ;
 995                 }
 996         }
 997
 998 }
 999
1000 /*
1001    =============
1002    AddSampleToPatch
1003
1004    Take the sample's collected light and
1005    add it back into the apropriate patch
1006    for the radiosity pass.
1007
1008    The sample is added to all patches that might include
1009    any part of it.  They are counted and averaged, so it
1010    doesn't generate extra light.
1011    =============
1012  */
1013 void AddSampleToPatch( vec3_t pos, vec3_t color, int facenum ){
1014         patch_t *patch;
1015         vec3_t mins, maxs;
1016         int i;
1017
1018         if ( numbounce == 0 ) {
1019                 return;
1020         }
1021         if ( color[0] + color[1] + color[2] < 3 ) {
1022                 return;
1023         }
1024
1025         for ( patch = face_patches[facenum] ; patch ; patch = patch->next )
1026         {
1027                 // see if the point is in this patch (roughly)
1028                 WindingBounds( patch->winding, mins, maxs );
1029                 for ( i = 0 ; i < 3 ; i++ )
1030                 {
1031                         if ( mins[i] > pos[i] + 16 ) {
1032                                 goto nextpatch;
1033                         }
1034                         if ( maxs[i] < pos[i] - 16 ) {
1035                                 goto nextpatch;
1036                         }
1037                 }
1038
1039                 // add the sample to the patch
1040                 patch->samples++;
1041                 VectorAdd( patch->samplelight, color, patch->samplelight );
1042 nextpatch:;
1043         }
1044
1045 }
1046
1047
1048 /*
1049    =============
1050    BuildFacelights
1051    =============
1052  */
1053 float sampleofs[5][2] =
1054 {  {0,0}, {-0.25, -0.25}, {0.25, -0.25}, {0.25, 0.25}, {-0.25, 0.25} };
1055
1056
1057 void BuildFacelights( int facenum ){
1058         dface_t *f;
1059         lightinfo_t l[5];
1060         float       *styletable[MAX_LSTYLES];
1061         int i, j;
1062         float       *spot;
1063         patch_t     *patch;
1064         int numsamples;
1065         int tablesize;
1066         facelight_t     *fl;
1067
1068         f = &dfaces[facenum];
1069
1070         if ( texinfo[f->texinfo].flags & ( SURF_WARP | SURF_SKY ) ) {
1071                 return;     // non-lit texture
1072
1073         }
1074         memset( styletable,0, sizeof( styletable ) );
1075
1076         if ( extrasamples ) {
1077                 numsamples = 5;
1078         }
1079         else{
1080                 numsamples = 1;
1081         }
1082         for ( i = 0 ; i < numsamples ; i++ )
1083         {
1084                 memset( &l[i], 0, sizeof( l[i] ) );
1085                 l[i].surfnum = facenum;
1086                 l[i].face = f;
1087                 VectorCopy( dplanes[f->planenum].normal, l[i].facenormal );
1088                 l[i].facedist = dplanes[f->planenum].dist;
1089                 if ( f->side ) {
1090                         VectorSubtract( vec3_origin, l[i].facenormal, l[i].facenormal );
1091                         l[i].facedist = -l[i].facedist;
1092                 }
1093
1094                 // get the origin offset for rotating bmodels
1095                 VectorCopy( face_offset[facenum], l[i].modelorg );
1096
1097                 CalcFaceVectors( &l[i] );
1098                 CalcFaceExtents( &l[i] );
1099                 CalcPoints( &l[i], sampleofs[i][0], sampleofs[i][1] );
1100         }
1101
1102         tablesize = l[0].numsurfpt * sizeof( vec3_t );
1103         styletable[0] = malloc( tablesize );
1104         memset( styletable[0], 0, tablesize );
1105
1106         fl = &facelight[facenum];
1107         fl->numsamples = l[0].numsurfpt;
1108         fl->origins = malloc( tablesize );
1109         memcpy( fl->origins, l[0].surfpt, tablesize );
1110
1111         for ( i = 0 ; i < l[0].numsurfpt ; i++ )
1112         {
1113                 for ( j = 0 ; j < numsamples ; j++ )
1114                 {
1115                         GatherSampleLight( l[j].surfpt[i], l[0].facenormal, styletable,
1116                                                            i * 3, tablesize, 1.0 / numsamples );
1117                 }
1118
1119                 // contribute the sample to one or more patches
1120                 AddSampleToPatch( l[0].surfpt[i], styletable[0] + i * 3, facenum );
1121         }
1122
1123         // average up the direct light on each patch for radiosity
1124         for ( patch = face_patches[facenum] ; patch ; patch = patch->next )
1125         {
1126                 if ( patch->samples ) {
1127                         VectorScale( patch->samplelight, 1.0 / patch->samples, patch->samplelight );
1128                 }
1129                 else
1130                 {
1131 //                      printf ("patch with no samples\n");
1132                 }
1133         }
1134
1135         for ( i = 0 ; i < MAX_LSTYLES ; i++ )
1136         {
1137                 if ( !styletable[i] ) {
1138                         continue;
1139                 }
1140                 if ( fl->numstyles == MAX_STYLES ) {
1141                         break;
1142                 }
1143                 fl->samples[fl->numstyles] = styletable[i];
1144                 fl->stylenums[fl->numstyles] = i;
1145                 fl->numstyles++;
1146         }
1147
1148         // the light from DIRECT_LIGHTS is sent out, but the
1149         // texture itself should still be full bright
1150
1151         if ( face_patches[facenum]->baselight[0] >= DIRECT_LIGHT ||
1152                  face_patches[facenum]->baselight[1] >= DIRECT_LIGHT ||
1153                  face_patches[facenum]->baselight[2] >= DIRECT_LIGHT
1154                  ) {
1155                 spot = fl->samples[0];
1156                 for ( i = 0 ; i < l[0].numsurfpt ; i++, spot += 3 )
1157                 {
1158                         VectorAdd( spot, face_patches[facenum]->baselight, spot );
1159                 }
1160         }
1161 }
1162
1163
1164 /*
1165    =============
1166    FinalLightFace
1167
1168    Add the indirect lighting on top of the direct
1169    lighting and save into final map format
1170    =============
1171  */
1172 void FinalLightFace( int facenum ){
1173         dface_t     *f;
1174         int i, j, k, st;
1175         vec3_t lb;
1176         patch_t     *patch;
1177         triangulation_t *trian;
1178         facelight_t *fl;
1179         float minlight;
1180         float max, newmax;
1181         byte        *dest;
1182         int pfacenum;
1183         vec3_t facemins, facemaxs;
1184
1185         f = &dfaces[facenum];
1186         fl = &facelight[facenum];
1187
1188         if ( texinfo[f->texinfo].flags & ( SURF_WARP | SURF_SKY ) ) {
1189                 return;     // non-lit texture
1190
1191         }
1192         ThreadLock();
1193         f->lightofs = lightdatasize;
1194         lightdatasize += fl->numstyles * ( fl->numsamples * 3 );
1195
1196 // add green sentinals between lightmaps
1197 #if 0
1198         lightdatasize += 64 * 3;
1199         for ( i = 0 ; i < 64 ; i++ )
1200                 dlightdata[lightdatasize - ( i + 1 ) * 3 + 1] = 255;
1201 #endif
1202
1203         if ( lightdatasize > MAX_MAP_LIGHTING ) {
1204                 Error( "MAX_MAP_LIGHTING" );
1205         }
1206         ThreadUnlock();
1207
1208         f->styles[0] = 0;
1209         f->styles[1] = f->styles[2] = f->styles[3] = 0xff;
1210
1211         //
1212         // set up the triangulation
1213         //
1214         if ( numbounce > 0 ) {
1215                 ClearBounds( facemins, facemaxs );
1216                 for ( i = 0 ; i < f->numedges ; i++ )
1217                 {
1218                         int ednum;
1219
1220                         ednum = dsurfedges[f->firstedge + i];
1221                         if ( ednum >= 0 ) {
1222                                 AddPointToBounds( dvertexes[dedges[ednum].v[0]].point,
1223                                                                   facemins, facemaxs );
1224                         }
1225                         else{
1226                                 AddPointToBounds( dvertexes[dedges[-ednum].v[1]].point,
1227                                                                   facemins, facemaxs );
1228                         }
1229                 }
1230
1231                 trian = AllocTriangulation( &dplanes[f->planenum] );
1232
1233                 // for all faces on the plane, add the nearby patches
1234                 // to the triangulation
1235                 for ( pfacenum = planelinks[f->side][f->planenum]
1236                           ; pfacenum ; pfacenum = facelinks[pfacenum] )
1237                 {
1238                         for ( patch = face_patches[pfacenum] ; patch ; patch = patch->next )
1239                         {
1240                                 for ( i = 0 ; i < 3 ; i++ )
1241                                 {
1242                                         if ( facemins[i] - patch->origin[i] > subdiv * 2 ) {
1243                                                 break;
1244                                         }
1245                                         if ( patch->origin[i] - facemaxs[i] > subdiv * 2 ) {
1246                                                 break;
1247                                         }
1248                                 }
1249                                 if ( i != 3 ) {
1250                                         continue;   // not needed for this face
1251                                 }
1252                                 AddPointToTriangulation( patch, trian );
1253                         }
1254                 }
1255                 for ( i = 0 ; i < trian->numpoints ; i++ )
1256                         memset( trian->edgematrix[i], 0, trian->numpoints * sizeof( trian->edgematrix[0][0] ) );
1257                 TriangulatePoints( trian );
1258         }
1259
1260         //
1261         // sample the triangulation
1262         //
1263
1264         // _minlight allows models that have faces that would not be
1265         // illuminated to receive a mottled light pattern instead of
1266         // black
1267         minlight = FloatForKey( face_entity[facenum], "_minlight" ) * 128;
1268
1269         dest = &dlightdata[f->lightofs];
1270
1271         if ( fl->numstyles > MAXLIGHTMAPS ) {
1272                 fl->numstyles = MAXLIGHTMAPS;
1273                 Sys_Printf( "face with too many lightstyles: (%f %f %f)\n",
1274                                         face_patches[facenum]->origin[0],
1275                                         face_patches[facenum]->origin[1],
1276                                         face_patches[facenum]->origin[2]
1277                                         );
1278         }
1279
1280         for ( st = 0 ; st < fl->numstyles ; st++ )
1281         {
1282                 f->styles[st] = fl->stylenums[st];
1283                 for ( j = 0 ; j < fl->numsamples ; j++ )
1284                 {
1285                         VectorCopy( ( fl->samples[st] + j * 3 ), lb );
1286                         if ( numbounce > 0 && st == 0 ) {
1287                                 vec3_t add;
1288
1289                                 SampleTriangulation( fl->origins + j * 3, trian, add );
1290                                 VectorAdd( lb, add, lb );
1291                         }
1292                         // add an ambient term if desired
1293                         lb[0] += ambient;
1294                         lb[1] += ambient;
1295                         lb[2] += ambient;
1296
1297                         VectorScale( lb, lightscale, lb );
1298
1299                         // we need to clamp without allowing hue to change
1300                         for ( k = 0 ; k < 3 ; k++ )
1301                                 if ( lb[k] < 1 ) {
1302                                         lb[k] = 1;
1303                                 }
1304                         max = lb[0];
1305                         if ( lb[1] > max ) {
1306                                 max = lb[1];
1307                         }
1308                         if ( lb[2] > max ) {
1309                                 max = lb[2];
1310                         }
1311                         newmax = max;
1312                         if ( newmax < 0 ) {
1313                                 newmax = 0;     // roundoff problems
1314                         }
1315                         if ( newmax < minlight ) {
1316                                 newmax = minlight + ( rand() % 48 );
1317                         }
1318                         if ( newmax > maxlight ) {
1319                                 newmax = maxlight;
1320                         }
1321
1322                         for ( k = 0 ; k < 3 ; k++ )
1323                         {
1324                                 *dest++ = lb[k] * newmax / max;
1325                         }
1326                 }
1327         }
1328
1329         if ( numbounce > 0 ) {
1330                 FreeTriangulation( trian );
1331         }
1332 }