tools/quake2/q2map/lightmap.c

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