rewrote RecursiveHullCheck, no longer gets stuck on angle changes, and is generally...
[divverent/darkplaces.git] / r_light.c
1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20 // r_light.c
21
22 #include "quakedef.h"
23
24 cvar_t r_lightmodels = {0, "r_lightmodels", "1"};
25
26 void r_light_start(void)
27 {
28 }
29
30 void r_light_shutdown(void)
31 {
32 }
33
34 void r_light_newmap(void)
35 {
36 }
37
38 void R_Light_Init(void)
39 {
40         Cvar_RegisterVariable(&r_lightmodels);
41         R_RegisterModule("R_Light", r_light_start, r_light_shutdown, r_light_newmap);
42 }
43
44 /*
45 ==================
46 R_AnimateLight
47 ==================
48 */
49 void R_AnimateLight (void)
50 {
51         int                     i,j,k;
52
53 //
54 // light animations
55 // 'm' is normal light, 'a' is no light, 'z' is double bright
56         i = (int)(cl.time*10);
57         for (j=0 ; j<MAX_LIGHTSTYLES ; j++)
58         {
59                 if (!cl_lightstyle[j].length)
60                 {
61                         d_lightstylevalue[j] = 256;
62                         continue;
63                 }
64                 k = i % cl_lightstyle[j].length;
65                 k = cl_lightstyle[j].map[k] - 'a';
66                 k = k*22;
67                 d_lightstylevalue[j] = k;
68         }       
69 }
70
71 /*
72 =============================================================================
73
74 DYNAMIC LIGHTS
75
76 =============================================================================
77 */
78
79 /*
80 =============
81 R_MarkLights
82 =============
83 */
84 void R_OldMarkLights (vec3_t lightorigin, dlight_t *light, int bit, int bitindex, mnode_t *node)
85 {
86         float           ndist, maxdist;
87         msurface_t      *surf;
88         mleaf_t         *leaf;
89         int                     i;
90
91         if (!r_dynamic.value)
92                 return;
93
94         // for comparisons to minimum acceptable light
95         maxdist = light->radius * light->radius;
96
97         // clamp radius to avoid exceeding 32768 entry division table
98         if (maxdist > 4194304)
99                 maxdist = 4194304;
100
101 loc0:
102         if (node->contents < 0)
103         {
104                 if (node->contents != CONTENTS_SOLID)
105                 {
106                         leaf = (mleaf_t *)node;
107                         if (leaf->dlightframe != r_framecount) // not dynamic until now
108                         {
109                                 leaf->dlightbits[0] = leaf->dlightbits[1] = leaf->dlightbits[2] = leaf->dlightbits[3] = leaf->dlightbits[4] = leaf->dlightbits[5] = leaf->dlightbits[6] = leaf->dlightbits[7] = 0;
110                                 leaf->dlightframe = r_framecount;
111                         }
112                         leaf->dlightbits[bitindex] |= bit;
113                 }
114                 return;
115         }
116
117         ndist = PlaneDiff(lightorigin, node->plane);
118         
119         if (ndist > light->radius)
120         {
121                 node = node->children[0];
122                 goto loc0;
123         }
124         if (ndist < -light->radius)
125         {
126                 node = node->children[1];
127                 goto loc0;
128         }
129
130 // mark the polygons
131         surf = cl.worldmodel->surfaces + node->firstsurface;
132         for (i=0 ; i<node->numsurfaces ; i++, surf++)
133         {
134                 int d, impacts, impactt;
135                 float dist, dist2, impact[3];
136                 if (surf->visframe != r_framecount)
137                         continue;
138                 dist = ndist;
139                 if (surf->flags & SURF_PLANEBACK)
140                         dist = -dist;
141
142                 if (dist < -0.25f && !(surf->flags & SURF_LIGHTBOTHSIDES))
143                         continue;
144
145                 dist2 = dist * dist;
146                 if (dist2 >= maxdist)
147                         continue;
148
149                 impact[0] = light->origin[0] - surf->plane->normal[0] * dist;
150                 impact[1] = light->origin[1] - surf->plane->normal[1] * dist;
151                 impact[2] = light->origin[2] - surf->plane->normal[2] * dist;
152
153                 impacts = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
154
155                 d = bound(0, impacts, surf->extents[0] + 16) - impacts;
156                 dist2 += d * d;
157                 if (dist2 > maxdist)
158                         continue;
159
160                 impactt = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
161
162                 d = bound(0, impactt, surf->extents[1] + 16) - impactt;
163                 dist2 += d * d;
164                 if (dist2 > maxdist)
165                         continue;
166
167
168                 /*
169                 d = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
170
171                 if (d < 0)
172                 {
173                         dist2 += d * d;
174                         if (dist2 >= maxdist)
175                                 continue;
176                 }
177                 else
178                 {
179                         d -= surf->extents[0] + 16;
180                         if (d > 0)
181                         {
182                                 dist2 += d * d;
183                                 if (dist2 >= maxdist)
184                                         continue;
185                         }
186                 }
187
188                 d = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
189
190                 if (d < 0)
191                 {
192                         dist2 += d * d;
193                         if (dist2 >= maxdist)
194                                 continue;
195                 }
196                 else
197                 {
198                         d -= surf->extents[1] + 16;
199                         if (d > 0)
200                         {
201                                 dist2 += d * d;
202                                 if (dist2 >= maxdist)
203                                         continue;
204                         }
205                 }
206                 */
207
208                 if (surf->dlightframe != r_framecount) // not dynamic until now
209                 {
210                         surf->dlightbits[0] = surf->dlightbits[1] = surf->dlightbits[2] = surf->dlightbits[3] = surf->dlightbits[4] = surf->dlightbits[5] = surf->dlightbits[6] = surf->dlightbits[7] = 0;
211                         surf->dlightframe = r_framecount;
212                 }
213                 surf->dlightbits[bitindex] |= bit;
214
215                 /*
216                 if (((surf->flags & SURF_PLANEBACK) == 0) == ((PlaneDist(lightorigin, surf->plane)) >= surf->plane->dist))
217                 {
218                         if (surf->dlightframe != r_framecount) // not dynamic until now
219                         {
220                                 surf->dlightbits[0] = surf->dlightbits[1] = surf->dlightbits[2] = surf->dlightbits[3] = surf->dlightbits[4] = surf->dlightbits[5] = surf->dlightbits[6] = surf->dlightbits[7] = 0;
221                                 surf->dlightframe = r_framecount;
222                         }
223                         surf->dlightbits[bitindex] |= bit;
224                 }
225                 */
226         }
227
228         if (node->children[0]->contents >= 0)
229         {
230                 if (node->children[1]->contents >= 0)
231                 {
232                         R_OldMarkLights (lightorigin, light, bit, bitindex, node->children[0]);
233                         node = node->children[1];
234                         goto loc0;
235                 }
236                 else
237                 {
238                         node = node->children[0];
239                         goto loc0;
240                 }
241         }
242         else if (node->children[1]->contents >= 0)
243         {
244                 node = node->children[1];
245                 goto loc0;
246         }
247 }
248
249 void R_NoVisMarkLights (vec3_t lightorigin, dlight_t *light, int bit, int bitindex, model_t *model)
250 {
251         R_OldMarkLights(lightorigin, light, bit, bitindex, model->nodes + model->hulls[0].firstclipnode);
252 }
253
254 void R_VisMarkLights (vec3_t lightorigin, dlight_t *light, int bit, int bitindex, model_t *model)
255 {
256         static int lightframe = 0;
257         mleaf_t *pvsleaf = Mod_PointInLeaf (lightorigin, model);
258
259         if (!r_dynamic.value)
260                 return;
261
262         if (!pvsleaf->compressed_vis)
263         {       // no vis info, so make all visible
264                 R_OldMarkLights(lightorigin, light, bit, bitindex, model->nodes + model->hulls[0].firstclipnode);
265                 return;
266         }
267         else
268         {
269                 int             i, k, m, c, leafnum;
270                 msurface_t *surf, **mark;
271                 mleaf_t *leaf;
272                 byte    *in = pvsleaf->compressed_vis;
273                 int             row = (model->numleafs+7)>>3;
274                 float   low[3], high[3], radius, dist, maxdist;
275
276                 lightframe++;
277
278                 radius = light->radius * 3;
279
280                 // clamp radius to avoid exceeding 32768 entry division table
281                 if (radius > 2048)
282                         radius = 2048;
283
284                 low[0] = lightorigin[0] - radius;low[1] = lightorigin[1] - radius;low[2] = lightorigin[2] - radius;
285                 high[0] = lightorigin[0] + radius;high[1] = lightorigin[1] + radius;high[2] = lightorigin[2] + radius;
286
287                 // for comparisons to minimum acceptable light
288                 maxdist = radius*radius;
289
290                 k = 0;
291                 while (k < row)
292                 {
293                         c = *in++;
294                         if (c)
295                         {
296                                 for (i = 0;i < 8;i++)
297                                 {
298                                         if (c & (1<<i))
299                                         {
300                                                 // warning to the clumsy: numleafs is one less than it should be, it only counts leafs with vis bits (skips leaf 0)
301                                                 leafnum = (k << 3)+i+1;
302                                                 if (leafnum > model->numleafs)
303                                                         return;
304                                                 leaf = &model->leafs[leafnum];
305 //                                              if (leaf->visframe != r_framecount)
306 //                                                      continue;
307 //                                              if (leaf->contents == CONTENTS_SOLID)
308 //                                                      continue;
309                                                 // if out of the light radius, skip
310                                                 if (leaf->mins[0] > high[0] || leaf->maxs[0] < low[0]
311                                                  || leaf->mins[1] > high[1] || leaf->maxs[1] < low[1]
312                                                  || leaf->mins[2] > high[2] || leaf->maxs[2] < low[2])
313                                                         continue;
314                                                 if (leaf->dlightframe != r_framecount) // not dynamic until now
315                                                 {
316                                                         leaf->dlightbits[0] = leaf->dlightbits[1] = leaf->dlightbits[2] = leaf->dlightbits[3] = leaf->dlightbits[4] = leaf->dlightbits[5] = leaf->dlightbits[6] = leaf->dlightbits[7] = 0;
317                                                         leaf->dlightframe = r_framecount;
318                                                 }
319                                                 leaf->dlightbits[bitindex] |= bit;
320                                                 if ((m = leaf->nummarksurfaces))
321                                                 {
322                                                         mark = leaf->firstmarksurface;
323                                                         do
324                                                         {
325                                                                 surf = *mark++;
326                                                                 // if not visible in current frame, or already marked because it was in another leaf we passed, skip
327                                                                 if (surf->lightframe == lightframe)
328                                                                         continue;
329                                                                 surf->lightframe = lightframe;
330                                                                 if (surf->visframe != r_framecount)
331                                                                         continue;
332                                                                 dist = PlaneDiff(lightorigin, surf->plane);
333                                                                 if (surf->flags & SURF_PLANEBACK)
334                                                                         dist = -dist;
335                                                                 // LordHavoc: make sure it is infront of the surface and not too far away
336                                                                 if (dist < radius && (dist > -0.25f || ((surf->flags & SURF_LIGHTBOTHSIDES) && dist > -radius)))
337                                                                 {
338                                                                         int d, impacts, impactt;
339                                                                         float dist2, impact[3];
340
341                                                                         dist2 = dist * dist;
342
343                                                                         impact[0] = light->origin[0] - surf->plane->normal[0] * dist;
344                                                                         impact[1] = light->origin[1] - surf->plane->normal[1] * dist;
345                                                                         impact[2] = light->origin[2] - surf->plane->normal[2] * dist;
346
347                                                                         impacts = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
348
349                                                                         d = bound(0, impacts, surf->extents[0] + 16) - impacts;
350                                                                         dist2 += d * d;
351                                                                         if (dist2 > maxdist)
352                                                                                 continue;
353
354                                                                         impactt = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
355
356                                                                         d = bound(0, impactt, surf->extents[1] + 16) - impactt;
357                                                                         dist2 += d * d;
358                                                                         if (dist2 > maxdist)
359                                                                                 continue;
360
361                                                                         /*
362                                                                         d = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
363
364                                                                         if (d < 0)
365                                                                         {
366                                                                                 dist2 += d * d;
367                                                                                 if (dist2 >= maxdist)
368                                                                                         continue;
369                                                                         }
370                                                                         else
371                                                                         {
372                                                                                 d -= surf->extents[0] + 16;
373                                                                                 if (d > 0)
374                                                                                 {
375                                                                                         dist2 += d * d;
376                                                                                         if (dist2 >= maxdist)
377                                                                                                 continue;
378                                                                                 }
379                                                                         }
380
381                                                                         d = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
382
383                                                                         if (d < 0)
384                                                                         {
385                                                                                 dist2 += d * d;
386                                                                                 if (dist2 >= maxdist)
387                                                                                         continue;
388                                                                         }
389                                                                         else
390                                                                         {
391                                                                                 d -= surf->extents[1] + 16;
392                                                                                 if (d > 0)
393                                                                                 {
394                                                                                         dist2 += d * d;
395                                                                                         if (dist2 >= maxdist)
396                                                                                                 continue;
397                                                                                 }
398                                                                         }
399                                                                         */
400
401                                                                         if (surf->dlightframe != r_framecount) // not dynamic until now
402                                                                         {
403                                                                                 surf->dlightbits[0] = surf->dlightbits[1] = surf->dlightbits[2] = surf->dlightbits[3] = surf->dlightbits[4] = surf->dlightbits[5] = surf->dlightbits[6] = surf->dlightbits[7] = 0;
404                                                                                 surf->dlightframe = r_framecount;
405                                                                         }
406                                                                         surf->dlightbits[bitindex] |= bit;
407                                                                 }
408                                                         }
409                                                         while (--m);
410                                                 }
411                                         }
412                                 }
413                                 k++;
414                                 continue;
415                         }
416
417                         k += *in++;
418                 }
419         }
420 }
421
422
423 /*
424 =============
425 R_PushDlights
426 =============
427 */
428 void R_PushDlights (void)
429 {
430         int             i;
431         dlight_t        *l;
432
433         if (!r_dynamic.value)
434                 return;
435
436         l = cl_dlights;
437
438         for (i=0 ; i<MAX_DLIGHTS ; i++, l++)
439         {
440                 if (!l->radius)
441                         continue;
442 //              R_MarkLights (l->origin, l, 1<<(i&31), i >> 5, cl.worldmodel->nodes );
443                 R_VisMarkLights (l->origin, l, 1<<(i&31), i >> 5, cl.worldmodel);
444         }
445
446
447 }
448
449
450 /*
451 =============================================================================
452
453 LIGHT SAMPLING
454
455 =============================================================================
456 */
457
458 mplane_t                *lightplane;
459 vec3_t                  lightspot;
460
461 /*
462 int RecursiveLightPoint (vec3_t color, mnode_t *node, vec3_t start, vec3_t end)
463 {
464         float           front, back, frac;
465         vec3_t          mid;
466
467 loc0:
468         if (node->contents < 0)
469                 return false;           // didn't hit anything
470         
471 // calculate mid point
472         front = PlaneDiff (start, node->plane);
473         back = PlaneDiff (end, node->plane);
474
475         // LordHavoc: optimized recursion
476         if ((back < 0) == (front < 0))
477 //              return RecursiveLightPoint (color, node->children[front < 0], start, end);
478         {
479                 node = node->children[front < 0];
480                 goto loc0;
481         }
482         
483         frac = front / (front-back);
484         mid[0] = start[0] + (end[0] - start[0])*frac;
485         mid[1] = start[1] + (end[1] - start[1])*frac;
486         mid[2] = start[2] + (end[2] - start[2])*frac;
487         
488 // go down front side
489         if (RecursiveLightPoint (color, node->children[front < 0], start, mid))
490                 return true;    // hit something
491         else
492         {
493                 int i, ds, dt;
494                 msurface_t *surf;
495         // check for impact on this node
496                 VectorCopy (mid, lightspot);
497                 lightplane = node->plane;
498
499                 surf = cl.worldmodel->surfaces + node->firstsurface;
500                 for (i = 0;i < node->numsurfaces;i++, surf++)
501                 {
502                         if (surf->flags & SURF_DRAWTILED)
503                                 continue;       // no lightmaps
504
505                         ds = (int) ((float) DotProduct (mid, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]);
506                         dt = (int) ((float) DotProduct (mid, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]);
507
508                         if (ds < surf->texturemins[0] || dt < surf->texturemins[1])
509                                 continue;
510                         
511                         ds -= surf->texturemins[0];
512                         dt -= surf->texturemins[1];
513                         
514                         if (ds > surf->extents[0] || dt > surf->extents[1])
515                                 continue;
516
517                         if (surf->samples)
518                         {
519                                 byte *lightmap;
520                                 int maps, line3, dsfrac = ds & 15, dtfrac = dt & 15, r00 = 0, g00 = 0, b00 = 0, r01 = 0, g01 = 0, b01 = 0, r10 = 0, g10 = 0, b10 = 0, r11 = 0, g11 = 0, b11 = 0;
521                                 float scale;
522                                 line3 = ((surf->extents[0]>>4)+1)*3;
523
524                                 lightmap = surf->samples + ((dt>>4) * ((surf->extents[0]>>4)+1) + (ds>>4))*3; // LordHavoc: *3 for color
525
526                                 for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
527                                 {
528                                         scale = (float) d_lightstylevalue[surf->styles[maps]] * 1.0 / 256.0;
529                                         r00 += (float) lightmap[      0] * scale;g00 += (float) lightmap[      1] * scale;b00 += (float) lightmap[2] * scale;
530                                         r01 += (float) lightmap[      3] * scale;g01 += (float) lightmap[      4] * scale;b01 += (float) lightmap[5] * scale;
531                                         r10 += (float) lightmap[line3+0] * scale;g10 += (float) lightmap[line3+1] * scale;b10 += (float) lightmap[line3+2] * scale;
532                                         r11 += (float) lightmap[line3+3] * scale;g11 += (float) lightmap[line3+4] * scale;b11 += (float) lightmap[line3+5] * scale;
533                                         lightmap += ((surf->extents[0]>>4)+1) * ((surf->extents[1]>>4)+1)*3; // LordHavoc: *3 for colored lighting
534                                 }
535
536                                 color[0] += (float) ((int) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)));
537                                 color[1] += (float) ((int) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)));
538                                 color[2] += (float) ((int) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)));
539                         }
540                         return true; // success
541                 }
542
543         // go down back side
544                 return RecursiveLightPoint (color, node->children[front >= 0], mid, end);
545         }
546 }
547
548 void R_LightPoint (vec3_t color, vec3_t p)
549 {
550         vec3_t          end;
551         
552         if (r_fullbright.value || !cl.worldmodel->lightdata)
553         {
554                 color[0] = color[1] = color[2] = 255;
555                 return;
556         }
557
558         end[0] = p[0];
559         end[1] = p[1];
560         end[2] = p[2] - 2048;
561
562         color[0] = color[1] = color[2] = r_ambient.value * 2.0f;
563         RecursiveLightPoint (color, cl.worldmodel->nodes, p, end);
564 }
565
566 void SV_LightPoint (vec3_t color, vec3_t p)
567 {
568         vec3_t          end;
569         
570         if (!sv.worldmodel->lightdata)
571         {
572                 color[0] = color[1] = color[2] = 255;
573                 return;
574         }
575         
576         end[0] = p[0];
577         end[1] = p[1];
578         end[2] = p[2] - 2048;
579
580         color[0] = color[1] = color[2] = 0;
581         RecursiveLightPoint (color, sv.worldmodel->nodes, p, end);
582 }
583 */
584
585 int RecursiveLightPoint (vec3_t color, mnode_t *node, float x, float y, float startz, float endz)
586 {
587         int             side, distz = endz - startz;
588         float   front, back;
589         float   mid;
590
591 loc0:
592         if (node->contents < 0)
593                 return false;           // didn't hit anything
594
595         switch (node->plane->type)
596         {
597         case PLANE_X:
598                 node = node->children[x < node->plane->dist];
599                 goto loc0;
600         case PLANE_Y:
601                 node = node->children[y < node->plane->dist];
602                 goto loc0;
603         case PLANE_Z:
604                 side = startz < node->plane->dist;
605                 if ((endz < node->plane->dist) == side)
606                 {
607                         node = node->children[side];
608                         goto loc0;
609                 }
610                 // found an intersection
611 //              mid = startz + (endz - startz) * (startz - node->plane->dist) / (startz - endz);
612 //              mid = startz + distz * (startz - node->plane->dist) / (-distz);
613 //              mid = startz + (-(startz - node->plane->dist));
614 //              mid = startz - (startz - node->plane->dist);
615 //              mid = startz + node->plane->dist - startz;
616                 mid = node->plane->dist;
617                 break;
618         default:
619                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
620                 front += startz * node->plane->normal[2];
621                 back += endz * node->plane->normal[2];
622                 side = front < node->plane->dist;
623                 if ((back < node->plane->dist) == side)
624                 {
625                         node = node->children[side];
626                         goto loc0;
627                 }
628                 // found an intersection
629 //              mid = startz + (endz - startz) * ((front - node->plane->dist) / ((front - node->plane->dist) - (back - node->plane->dist)));
630 //              mid = startz + (endz - startz) * ((front - node->plane->dist) / (front - back));
631                 mid = startz + distz * (front - node->plane->dist) / (front - back);
632                 break;
633         }
634         
635         // go down front side
636         if (node->children[side]->contents >= 0 && RecursiveLightPoint (color, node->children[side], x, y, startz, mid))
637                 return true;    // hit something
638         else
639         {
640                 // check for impact on this node
641                 if (node->numsurfaces)
642                 {
643                         int i, ds, dt;
644                         msurface_t *surf;
645                         lightspot[0] = x;
646                         lightspot[1] = y;
647                         lightspot[2] = mid;
648                         lightplane = node->plane;
649
650                         surf = cl.worldmodel->surfaces + node->firstsurface;
651                         for (i = 0;i < node->numsurfaces;i++, surf++)
652                         {
653                                 if (surf->flags & SURF_DRAWTILED)
654                                         continue;       // no lightmaps
655
656                                 ds = (int) (x * surf->texinfo->vecs[0][0] + y * surf->texinfo->vecs[0][1] + mid * surf->texinfo->vecs[0][2] + surf->texinfo->vecs[0][3]);
657                                 dt = (int) (x * surf->texinfo->vecs[1][0] + y * surf->texinfo->vecs[1][1] + mid * surf->texinfo->vecs[1][2] + surf->texinfo->vecs[1][3]);
658
659                                 if (ds < surf->texturemins[0] || dt < surf->texturemins[1])
660                                         continue;
661
662                                 ds -= surf->texturemins[0];
663                                 dt -= surf->texturemins[1];
664
665                                 if (ds > surf->extents[0] || dt > surf->extents[1])
666                                         continue;
667
668                                 if (surf->samples)
669                                 {
670                                         byte *lightmap;
671                                         int maps, line3, size3, dsfrac = ds & 15, dtfrac = dt & 15, scale = 0, r00 = 0, g00 = 0, b00 = 0, r01 = 0, g01 = 0, b01 = 0, r10 = 0, g10 = 0, b10 = 0, r11 = 0, g11 = 0, b11 = 0;
672                                         line3 = ((surf->extents[0]>>4)+1)*3;
673                                         size3 = ((surf->extents[0]>>4)+1) * ((surf->extents[1]>>4)+1)*3; // LordHavoc: *3 for colored lighting
674
675                                         lightmap = surf->samples + ((dt>>4) * ((surf->extents[0]>>4)+1) + (ds>>4))*3; // LordHavoc: *3 for color
676
677                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
678                                         {
679                                                 scale = d_lightstylevalue[surf->styles[maps]];
680                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
681                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
682                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
683                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
684                                                 lightmap += size3;
685                                         }
686
687                                         /*
688                                         // LordHavoc: here's the readable version of the interpolation
689                                         // code, not quite as easy for the compiler to optimize...
690
691                                         // dsfrac is the X position in the lightmap pixel, * 16
692                                         // dtfrac is the Y position in the lightmap pixel, * 16
693                                         // r00 is top left corner, r01 is top right corner
694                                         // r10 is bottom left corner, r11 is bottom right corner
695                                         // g and b are the same layout.
696                                         // r0 and r1 are the top and bottom intermediate results
697
698                                         // first we interpolate the top two points, to get the top
699                                         // edge sample
700                                         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
701                                         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
702                                         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
703                                         // then we interpolate the bottom two points, to get the
704                                         // bottom edge sample
705                                         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
706                                         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
707                                         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
708                                         // then we interpolate the top and bottom samples to get the
709                                         // middle sample (the one which was requested)
710                                         r = (((r1-r0) * dtfrac) >> 4) + r0;
711                                         g = (((g1-g0) * dtfrac) >> 4) + g0;
712                                         b = (((b1-b0) * dtfrac) >> 4) + b0;
713                                         */
714
715                                         color[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 256.0f);
716                                         color[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 256.0f);
717                                         color[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 256.0f);
718                                 }
719                                 return true; // success
720                         }
721                 }
722
723                 // go down back side
724                 node = node->children[side ^ 1];
725                 startz = mid;
726                 distz = endz - startz;
727                 goto loc0;
728 //              return RecursiveLightPoint (color, node->children[side ^ 1], x, y, mid, endz);
729         }
730 }
731
732 void R_DynamicLightPoint(vec3_t color, vec3_t org, int *dlightbits)
733 {
734         int             i, j, k;
735         vec3_t  dist;
736         float   brightness, r, f;
737
738         if (!r_dynamic.value || (!dlightbits[0] && !dlightbits[1] && !dlightbits[2] && !dlightbits[3] && !dlightbits[4] && !dlightbits[5] && !dlightbits[6] && !dlightbits[7]))
739                 return;
740
741         for (j = 0;j < (MAX_DLIGHTS >> 5);j++)
742         {
743                 if (dlightbits[j])
744                 {
745                         for (i=0 ; i<32 ; i++)
746                         {
747                                 if (!((1 << i) & dlightbits[j]))
748                                         continue;
749                                 k = (j<<5)+i;
750                                 if (!cl_dlights[k].radius)
751                                         continue;
752                                 VectorSubtract (org, cl_dlights[k].origin, dist);
753                                 f = DotProduct(dist, dist) + LIGHTOFFSET;
754                                 r = cl_dlights[k].radius*cl_dlights[k].radius;
755                                 if (f < r)
756                                 {
757                                         brightness = r * 128.0f / f;
758                                         color[0] += brightness * cl_dlights[k].color[0];
759                                         color[1] += brightness * cl_dlights[k].color[1];
760                                         color[2] += brightness * cl_dlights[k].color[2];
761                                 }
762                         }
763                 }
764         }
765 }
766
767 void R_CompleteLightPoint (vec3_t color, vec3_t p, int dynamic, mleaf_t *leaf)
768 {
769         if (leaf == NULL)
770                 leaf = Mod_PointInLeaf(p, cl.worldmodel);
771
772         if (leaf->contents == CONTENTS_SOLID)
773         {
774                 color[0] = color[1] = color[2] = 0;
775                 return;
776         }
777
778         if (r_fullbright.value || !cl.worldmodel->lightdata)
779         {
780                 color[0] = color[1] = color[2] = 255;
781                 return;
782         }
783         
784         color[0] = color[1] = color[2] = r_ambient.value * 2.0f;
785         RecursiveLightPoint (color, cl.worldmodel->nodes, p[0], p[1], p[2], p[2] - 65536);
786
787         if (dynamic)
788                 R_DynamicLightPoint(color, p, leaf->dlightbits);
789 }
790
791 void R_ModelLightPoint (vec3_t color, vec3_t p, int *dlightbits)
792 {
793         mleaf_t *leaf;
794         leaf = Mod_PointInLeaf(p, cl.worldmodel);
795         if (leaf->contents == CONTENTS_SOLID)
796         {
797                 color[0] = color[1] = color[2] = 0;
798                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
799                 return;
800         }
801
802         if (r_fullbright.value || !cl.worldmodel->lightdata)
803         {
804                 color[0] = color[1] = color[2] = 255;
805                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
806                 return;
807         }
808
809         color[0] = color[1] = color[2] = r_ambient.value * 2.0f;
810         RecursiveLightPoint (color, cl.worldmodel->nodes, p[0], p[1], p[2], p[2] - 65536);
811
812         if (leaf->dlightframe == r_framecount)
813         {
814                 dlightbits[0] = leaf->dlightbits[0];
815                 dlightbits[1] = leaf->dlightbits[1];
816                 dlightbits[2] = leaf->dlightbits[2];
817                 dlightbits[3] = leaf->dlightbits[3];
818                 dlightbits[4] = leaf->dlightbits[4];
819                 dlightbits[5] = leaf->dlightbits[5];
820                 dlightbits[6] = leaf->dlightbits[6];
821                 dlightbits[7] = leaf->dlightbits[7];
822         }
823         else
824                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
825 }
826
827 /* // not currently used
828 void R_DynamicLightPointNoMask(vec3_t color, vec3_t org)
829 {
830         int             i;
831         vec3_t  dist;
832         float   brightness, r, f;
833
834         if (!r_dynamic.value)
835                 return;
836
837         for (i=0 ; i<MAX_DLIGHTS ; i++)
838         {
839                 if (!cl_dlights[i].radius)
840                         continue;
841                 VectorSubtract (org, cl_dlights[i].origin, dist);
842                 f = DotProduct(dist, dist) + LIGHTOFFSET;
843                 r = cl_dlights[i].radius*cl_dlights[i].radius;
844                 if (f < r)
845                 {
846                         brightness = r * 256.0f / f;
847                         if (cl_dlights[i].dark)
848                                 brightness = -brightness;
849                         color[0] += brightness * cl_dlights[i].color[0];
850                         color[1] += brightness * cl_dlights[i].color[1];
851                         color[2] += brightness * cl_dlights[i].color[2];
852                 }
853         }
854 }
855 */
856
857 void R_LightModel(int numverts)
858 {
859         // LordHavoc: warning: reliance on int being 4 bytes here (of course the d_8to24table relies on that too...)
860         int i, j, nearlights = 0, color;
861         vec3_t dist, mod, basecolor, center;
862         float t, t1, t2, t3, *avn, number;
863         byte r,g,b,a, *avc;
864         struct
865         {
866                 vec3_t color;
867                 vec3_t origin;
868         } nearlight[MAX_DLIGHTS];
869         int modeldlightbits[8];
870         avc = aliasvertcolor;
871         avn = aliasvertnorm;
872         VectorCopy(currentrenderentity->origin, center);
873         a = (byte) bound((int) 0, (int) (currentrenderentity->alpha * 255.0f), (int) 255);
874         if (lighthalf)
875         {
876                 mod[0] = currentrenderentity->colormod[0] * 0.5f;
877                 mod[1] = currentrenderentity->colormod[1] * 0.5f;
878                 mod[2] = currentrenderentity->colormod[2] * 0.5f;
879         }
880         else
881         {
882                 mod[0] = currentrenderentity->colormod[0];
883                 mod[1] = currentrenderentity->colormod[1];
884                 mod[2] = currentrenderentity->colormod[2];
885         }
886         if (currentrenderentity->effects & EF_FULLBRIGHT)
887         {
888                 if (a == 255)
889                         memset(avc, 0, 4 * numverts);
890                 else
891                 {
892                         ((byte *)&color)[0] = (byte) (255.0f * mod[0]);
893                         ((byte *)&color)[1] = (byte) (255.0f * mod[1]);
894                         ((byte *)&color)[2] = (byte) (255.0f * mod[2]);
895                         ((byte *)&color)[3] = a;
896                         for (i = 0;i < numverts;i++)
897                         {
898                                 *((int *)avc) = color;
899                                 avc += 4;
900                         }
901                 }
902                 return;
903         }
904         R_ModelLightPoint(basecolor, center, modeldlightbits);
905
906         basecolor[0] *= mod[0];
907         basecolor[1] *= mod[1];
908         basecolor[2] *= mod[2];
909         for (i = 0;i < MAX_DLIGHTS;i++)
910         {
911                 if (!modeldlightbits[i >> 5])
912                 {
913                         i |= 31;
914                         continue;
915                 }
916                 if (!(modeldlightbits[i >> 5] & (1 << (i & 31))))
917                         continue;
918                 VectorSubtract (center, cl_dlights[i].origin, dist);
919                 t2 = DotProduct(dist,dist) + LIGHTOFFSET;
920                 t1 = cl_dlights[i].radius*cl_dlights[i].radius;
921                 if (t2 < t1)
922                 {
923                         if (TraceLine(center, cl_dlights[i].origin, NULL, NULL, 0))
924                         {
925                                 // transform the light into the model's coordinate system
926                                 if (gl_transform.value)
927                                         softwareuntransform(cl_dlights[i].origin, nearlight[nearlights].origin);
928                                 else
929                                         VectorCopy(cl_dlights[i].origin, nearlight[nearlights].origin);
930                                 nearlight[nearlights].color[0] = cl_dlights[i].color[0] * t1 * mod[0];
931                                 nearlight[nearlights].color[1] = cl_dlights[i].color[1] * t1 * mod[1];
932                                 nearlight[nearlights].color[2] = cl_dlights[i].color[2] * t1 * mod[2];
933                                 if (r_lightmodels.value && currentrenderentity != cl_dlights[i].ent)
934                                 {
935                                         // boost color, to compensate for dark lighting calcs
936                                         VectorScale(nearlight[nearlights].color, cl_dlights[i].radius * 16.0f, nearlight[nearlights].color);
937                                         nearlights++;
938                                 }
939                                 else
940                                 {
941 #if SLOWMATH
942                                         t1 = 1.0f / sqrt(t2);
943 #else
944                                         number = t1;
945                                         *((long *)&t1) = 0x5f3759df - ((* (long *) &number) >> 1);
946                                         t1 = t1 * (1.5f - (number * 0.5f * t1 * t1));
947 #endif
948                                         t1 = t1 * t1;
949                                         basecolor[0] += nearlight[nearlights].color[0] * t1;
950                                         basecolor[1] += nearlight[nearlights].color[1] * t1;
951                                         basecolor[2] += nearlight[nearlights].color[2] * t1;
952                                 }
953                         }
954                 }
955         }
956         t1 = bound(0, basecolor[0], 255);r = (byte) t1;
957         t1 = bound(0, basecolor[1], 255);g = (byte) t1;
958         t1 = bound(0, basecolor[2], 255);b = (byte) t1;
959         ((byte *)&color)[0] = r;
960         ((byte *)&color)[1] = g;
961         ((byte *)&color)[2] = b;
962         ((byte *)&color)[3] = a;
963         if (nearlights)
964         {
965                 int i1, i2, i3;
966                 vec3_t v;
967                 float *av, number;
968                 av = aliasvert;
969                 for (i = 0;i < numverts;i++)
970                 {
971                         t1 = basecolor[0];
972                         t2 = basecolor[1];
973                         t3 = basecolor[2];
974                         for (j = 0;j < nearlights;j++)
975                         {
976                                 VectorSubtract(nearlight[j].origin, av, v);
977                                 t = DotProduct(avn,v);
978                                 if (t > 0)
979                                 {
980 #if SLOWMATH
981                                         t = 1.0f / sqrt(DotProduct(v,v) + 1.0f);
982 #else
983                                         number = DotProduct(v, v) + LIGHTOFFSET;
984                                         *((long *)&t) = 0x5f3759df - ((* (long *) &number) >> 1);
985                                         t = t * (1.5f - (number * 0.5f * t * t));
986 #endif
987                                         t = t * t * t;
988                                         t1 += nearlight[j].color[0] * t;
989                                         t2 += nearlight[j].color[1] * t;
990                                         t3 += nearlight[j].color[2] * t;
991                                 }
992                         }
993
994                         // FIXME: float to int conversions are very slow on x86 because of
995                         // mode switchs (switch from nearest rounding to down, then back,
996                         // each time), reimplement this part in assembly, SSE and 3DNow!
997                         // versions recommended as well
998 #if SLOWMATH
999                         i1 = (int) t1;
1000                         i2 = (int) t2;
1001                         i3 = (int) t3;
1002 #else
1003                         // later note: implemented bit hacking float to integer,
1004                         // probably makes the issue irrelevant
1005                         t1 += 8388608.0f;
1006                         i1 = *((long *)&t1) & 0x007FFFFF;
1007                         t2 += 8388608.0f;
1008                         i2 = *((long *)&t2) & 0x007FFFFF;
1009                         t3 += 8388608.0f;
1010                         i3 = *((long *)&t3) & 0x007FFFFF;
1011 #endif
1012
1013                         avc[0] = bound(0, i1, 255);
1014                         avc[1] = bound(0, i2, 255);
1015                         avc[2] = bound(0, i3, 255);
1016                         avc[3] = a;
1017                         avc += 4;
1018                         av += 3;
1019                         avn += 3;
1020                 }
1021         }
1022         else
1023         {
1024                 for (i = 0;i < numverts;i++)
1025                 {
1026                         *((int *)avc) = color;
1027                         avc += 4;
1028                 }
1029         }
1030 }