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