commented out bit-hacking 1/sqrt code
[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 #include "cl_collision.h"
24
25 rdlight_t r_dlight[MAX_DLIGHTS];
26 int r_numdlights = 0;
27
28 cvar_t r_modellights = {CVAR_SAVE, "r_modellights", "4"};
29 cvar_t r_vismarklights = {0, "r_vismarklights", "1"};
30 cvar_t r_coronas = {CVAR_SAVE, "r_coronas", "1"};
31 cvar_t gl_flashblend = {CVAR_SAVE, "gl_flashblend", "1"};
32
33 static rtexture_t *lightcorona;
34 static rtexturepool_t *lighttexturepool;
35
36 void r_light_start(void)
37 {
38         float dx, dy;
39         int x, y, a;
40         qbyte pixels[32][32][4];
41         lighttexturepool = R_AllocTexturePool();
42         for (y = 0;y < 32;y++)
43         {
44                 dy = (y - 15.5f) * (1.0f / 16.0f);
45                 for (x = 0;x < 32;x++)
46                 {
47                         dx = (x - 15.5f) * (1.0f / 16.0f);
48                         a = ((1.0f / (dx * dx + dy * dy + 0.2f)) - (1.0f / (1.0f + 0.2))) * 32.0f / (1.0f / (1.0f + 0.2));
49                         a = bound(0, a, 255);
50                         pixels[y][x][0] = a;
51                         pixels[y][x][1] = a;
52                         pixels[y][x][2] = a;
53                         pixels[y][x][3] = 255;
54                 }
55         }
56         lightcorona = R_LoadTexture (lighttexturepool, "lightcorona", 32, 32, &pixels[0][0][0], TEXTYPE_RGBA, TEXF_PRECACHE);
57 }
58
59 void r_light_shutdown(void)
60 {
61         lighttexturepool = NULL;
62         lightcorona = NULL;
63 }
64
65 void r_light_newmap(void)
66 {
67 }
68
69 void R_Light_Init(void)
70 {
71         Cvar_RegisterVariable(&r_modellights);
72         Cvar_RegisterVariable(&r_vismarklights);
73         Cvar_RegisterVariable(&r_coronas);
74         Cvar_RegisterVariable(&gl_flashblend);
75         R_RegisterModule("R_Light", r_light_start, r_light_shutdown, r_light_newmap);
76 }
77
78 /*
79 ==================
80 R_AnimateLight
81 ==================
82 */
83 void R_AnimateLight (void)
84 {
85         int i, j, k;
86
87 //
88 // light animations
89 // 'm' is normal light, 'a' is no light, 'z' is double bright
90         i = (int)(cl.time * 10);
91         for (j = 0;j < MAX_LIGHTSTYLES;j++)
92         {
93                 if (!cl_lightstyle[j].length)
94                 {
95                         d_lightstylevalue[j] = 256;
96                         continue;
97                 }
98                 k = i % cl_lightstyle[j].length;
99                 k = cl_lightstyle[j].map[k] - 'a';
100                 k = k*22;
101                 d_lightstylevalue[j] = k;
102         }
103 }
104
105
106 void R_BuildLightList(void)
107 {
108         int i;
109         dlight_t *cd;
110         rdlight_t *rd;
111
112         r_numdlights = 0;
113         c_dlights = 0;
114
115         if (!r_dynamic.integer)
116                 return;
117
118         for (i = 0;i < MAX_DLIGHTS;i++)
119         {
120                 cd = cl_dlights + i;
121                 if (cd->radius <= 0)
122                         continue;
123                 rd = &r_dlight[r_numdlights++];
124                 VectorCopy(cd->origin, rd->origin);
125                 VectorScale(cd->color, cd->radius * 64.0f, rd->light);
126                 rd->cullradius2 = DotProduct(rd->light, rd->light) * (0.25f / (64.0f * 64.0f)) + 4096.0f;
127                 // clamp radius to avoid overflowing division table in lightmap code
128                 if (rd->cullradius2 > (2048.0f * 2048.0f))
129                         rd->cullradius2 = (2048.0f * 2048.0f);
130                 rd->cullradius = sqrt(rd->cullradius2);
131                 rd->subtract = 1.0f / rd->cullradius2;
132                 //rd->ent = cd->ent;
133                 c_dlights++; // count every dlight in use
134         }
135 }
136
137 void R_DrawCoronas(void)
138 {
139         int i;
140         rmeshbufferinfo_t m;
141         float scale, viewdist, diff[3], dist;
142         rdlight_t *rd;
143         if (!r_coronas.integer)
144                 return;
145         memset(&m, 0, sizeof(m));
146         m.blendfunc1 = GL_ONE;
147         m.blendfunc2 = GL_ONE;
148         m.depthdisable = true; // magic
149         m.numtriangles = 2;
150         m.numverts = 4;
151         m.tex[0] = R_GetTexture(lightcorona);
152         viewdist = DotProduct(r_origin, vpn);
153         for (i = 0;i < r_numdlights;i++)
154         {
155                 rd = r_dlight + i;
156                 dist = (DotProduct(rd->origin, vpn) - viewdist);
157                 if (dist >= 24.0f)
158                 {
159                         if (CL_TraceLine(rd->origin, r_origin, NULL, NULL, 0, true) == 1)
160                         {
161                                 Matrix4x4_CreateIdentity(&m.matrix);
162                                 if (R_Mesh_Draw_GetBuffer(&m, false))
163                                 {
164                                         scale = m.colorscale * (1.0f / 131072.0f);
165                                         if (gl_flashblend.integer)
166                                                 scale *= 4.0f;
167                                         if (fogenabled)
168                                         {
169                                                 VectorSubtract(rd->origin, r_origin, diff);
170                                                 scale *= 1 - exp(fogdensity/DotProduct(diff,diff));
171                                         }
172                                         m.index[0] = 0;
173                                         m.index[1] = 1;
174                                         m.index[2] = 2;
175                                         m.index[3] = 0;
176                                         m.index[4] = 2;
177                                         m.index[5] = 3;
178                                         m.color[0] = m.color[4] = m.color[8] = m.color[12] = rd->light[0] * scale;
179                                         m.color[1] = m.color[5] = m.color[9] = m.color[13] = rd->light[1] * scale;
180                                         m.color[2] = m.color[6] = m.color[10] = m.color[14] = rd->light[2] * scale;
181                                         m.color[3] = m.color[7] = m.color[11] = m.color[15] = 1;
182                                         m.texcoords[0][0] = 0;
183                                         m.texcoords[0][1] = 0;
184                                         m.texcoords[0][2] = 0;
185                                         m.texcoords[0][3] = 1;
186                                         m.texcoords[0][4] = 1;
187                                         m.texcoords[0][5] = 1;
188                                         m.texcoords[0][6] = 1;
189                                         m.texcoords[0][7] = 0;
190                                         scale = rd->cullradius * 0.25f;
191                                         if (gl_flashblend.integer)
192                                                 scale *= 2.0f;
193                                         m.vertex[0] = rd->origin[0] - vright[0] * scale - vup[0] * scale;
194                                         m.vertex[1] = rd->origin[1] - vright[1] * scale - vup[1] * scale;
195                                         m.vertex[2] = rd->origin[2] - vright[2] * scale - vup[2] * scale;
196                                         m.vertex[4] = rd->origin[0] - vright[0] * scale + vup[0] * scale;
197                                         m.vertex[5] = rd->origin[1] - vright[1] * scale + vup[1] * scale;
198                                         m.vertex[6] = rd->origin[2] - vright[2] * scale + vup[2] * scale;
199                                         m.vertex[8] = rd->origin[0] + vright[0] * scale + vup[0] * scale;
200                                         m.vertex[9] = rd->origin[1] + vright[1] * scale + vup[1] * scale;
201                                         m.vertex[10] = rd->origin[2] + vright[2] * scale + vup[2] * scale;
202                                         m.vertex[12] = rd->origin[0] + vright[0] * scale - vup[0] * scale;
203                                         m.vertex[13] = rd->origin[1] + vright[1] * scale - vup[1] * scale;
204                                         m.vertex[14] = rd->origin[2] + vright[2] * scale - vup[2] * scale;
205                                         R_Mesh_Render();
206                                 }
207                         }
208                 }
209         }
210 }
211
212 /*
213 =============================================================================
214
215 DYNAMIC LIGHTS
216
217 =============================================================================
218 */
219
220 /*
221 =============
222 R_MarkLights
223 =============
224 */
225 static void R_OldMarkLights (entity_render_t *ent, vec3_t lightorigin, rdlight_t *rd, int bit, int bitindex, mnode_t *node)
226 {
227         float ndist, maxdist;
228         msurface_t *surf;
229         mleaf_t *leaf;
230         int i;
231
232         if (!r_dynamic.integer)
233                 return;
234
235         // for comparisons to minimum acceptable light
236         maxdist = rd->cullradius2;
237
238 loc0:
239         if (node->contents < 0)
240         {
241                 if (node->contents != CONTENTS_SOLID)
242                 {
243                         leaf = (mleaf_t *)node;
244                         if (leaf->dlightframe != r_framecount) // not dynamic until now
245                         {
246                                 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;
247                                 leaf->dlightframe = r_framecount;
248                         }
249                         leaf->dlightbits[bitindex] |= bit;
250                 }
251                 return;
252         }
253
254         ndist = PlaneDiff(lightorigin, node->plane);
255
256         if (ndist > rd->cullradius)
257         {
258                 node = node->children[0];
259                 goto loc0;
260         }
261         if (ndist < -rd->cullradius)
262         {
263                 node = node->children[1];
264                 goto loc0;
265         }
266
267 // mark the polygons
268         surf = ent->model->surfaces + node->firstsurface;
269         for (i=0 ; i<node->numsurfaces ; i++, surf++)
270         {
271                 int d, impacts, impactt;
272                 float dist, dist2, impact[3];
273                 if (surf->visframe != r_framecount)
274                         continue;
275                 dist = ndist;
276                 if (surf->flags & SURF_PLANEBACK)
277                         dist = -dist;
278
279                 if (dist < -0.25f && !(surf->flags & SURF_LIGHTBOTHSIDES))
280                         continue;
281
282                 dist2 = dist * dist;
283                 if (dist2 >= maxdist)
284                         continue;
285
286                 if (node->plane->type < 3)
287                 {
288                         VectorCopy(rd->origin, impact);
289                         impact[node->plane->type] -= dist;
290                 }
291                 else
292                 {
293                         impact[0] = rd->origin[0] - surf->plane->normal[0] * dist;
294                         impact[1] = rd->origin[1] - surf->plane->normal[1] * dist;
295                         impact[2] = rd->origin[2] - surf->plane->normal[2] * dist;
296                 }
297
298                 impacts = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
299
300                 d = bound(0, impacts, surf->extents[0] + 16) - impacts;
301                 dist2 += d * d;
302                 if (dist2 > maxdist)
303                         continue;
304
305                 impactt = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
306
307                 d = bound(0, impactt, surf->extents[1] + 16) - impactt;
308                 dist2 += d * d;
309                 if (dist2 > maxdist)
310                         continue;
311
312                 if (surf->dlightframe != r_framecount) // not dynamic until now
313                 {
314                         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;
315                         surf->dlightframe = r_framecount;
316                 }
317                 surf->dlightbits[bitindex] |= bit;
318         }
319
320         if (node->children[0]->contents >= 0)
321         {
322                 if (node->children[1]->contents >= 0)
323                 {
324                         R_OldMarkLights (ent, lightorigin, rd, bit, bitindex, node->children[0]);
325                         node = node->children[1];
326                         goto loc0;
327                 }
328                 else
329                 {
330                         node = node->children[0];
331                         goto loc0;
332                 }
333         }
334         else if (node->children[1]->contents >= 0)
335         {
336                 node = node->children[1];
337                 goto loc0;
338         }
339 }
340
341
342 static void R_VisMarkLights (entity_render_t *ent, rdlight_t *rd, int bit, int bitindex)
343 {
344         static int lightframe = 0;
345         mleaf_t *pvsleaf;
346         vec3_t lightorigin;
347         model_t *model;
348         int i, k, m, c, leafnum;
349         msurface_t *surf, **mark;
350         mleaf_t *leaf;
351         qbyte *in;
352         int row;
353         float low[3], high[3], dist, maxdist;
354
355         if (!r_dynamic.integer)
356                 return;
357
358         model = ent->model;
359         //softwareuntransform(rd->origin, lightorigin);
360         Matrix4x4_Transform(&ent->inversematrix, rd->origin, lightorigin);
361
362         if (!r_vismarklights.integer)
363         {
364                 R_OldMarkLights(ent, lightorigin, rd, bit, bitindex, model->nodes + model->hulls[0].firstclipnode);
365                 return;
366         }
367
368         pvsleaf = Mod_PointInLeaf (lightorigin, model);
369         if (pvsleaf == NULL)
370         {
371                 Con_Printf("R_VisMarkLights: NULL leaf??\n");
372                 R_OldMarkLights(ent, lightorigin, rd, bit, bitindex, model->nodes + model->hulls[0].firstclipnode);
373                 return;
374         }
375
376         in = pvsleaf->compressed_vis;
377         if (!in)
378         {
379                 // no vis info, so make all visible
380                 R_OldMarkLights(ent, lightorigin, rd, bit, bitindex, model->nodes + model->hulls[0].firstclipnode);
381                 return;
382         }
383
384         lightframe++;
385
386         low[0] = lightorigin[0] - rd->cullradius;low[1] = lightorigin[1] - rd->cullradius;low[2] = lightorigin[2] - rd->cullradius;
387         high[0] = lightorigin[0] + rd->cullradius;high[1] = lightorigin[1] + rd->cullradius;high[2] = lightorigin[2] + rd->cullradius;
388
389         // for comparisons to minimum acceptable light
390         maxdist = rd->cullradius2;
391
392         row = (model->numleafs+7)>>3;
393
394         k = 0;
395         while (k < row)
396         {
397                 c = *in++;
398                 if (c)
399                 {
400                         for (i = 0;i < 8;i++)
401                         {
402                                 if (c & (1<<i))
403                                 {
404                                         // warning to the clumsy: numleafs is one less than it should be, it only counts leafs with vis bits (skips leaf 0)
405                                         leafnum = (k << 3)+i+1;
406                                         if (leafnum > model->numleafs)
407                                                 return;
408                                         leaf = &model->leafs[leafnum];
409                                         if (leaf->visframe != r_framecount
410                                          || leaf->contents == CONTENTS_SOLID
411                                          || leaf->mins[0] > high[0] || leaf->maxs[0] < low[0]
412                                          || leaf->mins[1] > high[1] || leaf->maxs[1] < low[1]
413                                          || leaf->mins[2] > high[2] || leaf->maxs[2] < low[2])
414                                                 continue;
415                                         if (leaf->dlightframe != r_framecount)
416                                         {
417                                                 // not dynamic until now
418                                                 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;
419                                                 leaf->dlightframe = r_framecount;
420                                         }
421                                         leaf->dlightbits[bitindex] |= bit;
422                                         if ((m = leaf->nummarksurfaces))
423                                         {
424                                                 mark = leaf->firstmarksurface;
425                                                 do
426                                                 {
427                                                         surf = *mark++;
428                                                         // if not visible in current frame, or already marked because it was in another leaf we passed, skip
429                                                         if (surf->lightframe == lightframe)
430                                                                 continue;
431                                                         surf->lightframe = lightframe;
432                                                         if (surf->visframe != r_framecount)
433                                                                 continue;
434                                                         dist = PlaneDiff(lightorigin, surf->plane);
435                                                         if (surf->flags & SURF_PLANEBACK)
436                                                                 dist = -dist;
437                                                         // LordHavoc: make sure it is infront of the surface and not too far away
438                                                         if (dist < rd->cullradius && (dist > -0.25f || ((surf->flags & SURF_LIGHTBOTHSIDES) && dist > -rd->cullradius)))
439                                                         {
440                                                                 int d;
441                                                                 int impacts, impactt;
442                                                                 float dist2, impact[3];
443
444                                                                 dist2 = dist * dist;
445
446                                                                 if (surf->plane->type < 3)
447                                                                 {
448                                                                         VectorCopy(rd->origin, impact);
449                                                                         impact[surf->plane->type] -= dist;
450                                                                 }
451                                                                 else
452                                                                 {
453                                                                         impact[0] = rd->origin[0] - surf->plane->normal[0] * dist;
454                                                                         impact[1] = rd->origin[1] - surf->plane->normal[1] * dist;
455                                                                         impact[2] = rd->origin[2] - surf->plane->normal[2] * dist;
456                                                                 }
457
458                                                                 impacts = DotProduct (impact, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3] - surf->texturemins[0];
459                                                                 d = bound(0, impacts, surf->extents[0] + 16) - impacts;
460                                                                 dist2 += d * d;
461                                                                 if (dist2 > maxdist)
462                                                                         continue;
463
464                                                                 impactt = DotProduct (impact, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3] - surf->texturemins[1];
465                                                                 d = bound(0, impactt, surf->extents[1] + 16) - impactt;
466                                                                 dist2 += d * d;
467                                                                 if (dist2 > maxdist)
468                                                                         continue;
469
470                                                                 if (surf->dlightframe != r_framecount) // not dynamic until now
471                                                                 {
472                                                                         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;
473                                                                         surf->dlightframe = r_framecount;
474                                                                 }
475                                                                 surf->dlightbits[bitindex] |= bit;
476                                                         }
477                                                 }
478                                                 while (--m);
479                                         }
480                                 }
481                         }
482                         k++;
483                         continue;
484                 }
485
486                 k += *in++;
487         }
488 }
489
490 void R_MarkLights(entity_render_t *ent)
491 {
492         int i;
493         if (!gl_flashblend.integer)
494                 for (i = 0;i < r_numdlights;i++)
495                         R_VisMarkLights (ent, r_dlight + i, 1 << (i & 31), i >> 5);
496 }
497
498 /*
499 =============================================================================
500
501 LIGHT SAMPLING
502
503 =============================================================================
504 */
505
506 static int RecursiveLightPoint (vec3_t color, const mnode_t *node, float x, float y, float startz, float endz)
507 {
508         int side, distz = endz - startz;
509         float front, back;
510         float mid;
511
512 loc0:
513         if (node->contents < 0)
514                 return false;           // didn't hit anything
515
516         switch (node->plane->type)
517         {
518         case PLANE_X:
519                 node = node->children[x < node->plane->dist];
520                 goto loc0;
521         case PLANE_Y:
522                 node = node->children[y < node->plane->dist];
523                 goto loc0;
524         case PLANE_Z:
525                 side = startz < node->plane->dist;
526                 if ((endz < node->plane->dist) == side)
527                 {
528                         node = node->children[side];
529                         goto loc0;
530                 }
531                 // found an intersection
532                 mid = node->plane->dist;
533                 break;
534         default:
535                 back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
536                 front += startz * node->plane->normal[2];
537                 back += endz * node->plane->normal[2];
538                 side = front < node->plane->dist;
539                 if ((back < node->plane->dist) == side)
540                 {
541                         node = node->children[side];
542                         goto loc0;
543                 }
544                 // found an intersection
545                 mid = startz + distz * (front - node->plane->dist) / (front - back);
546                 break;
547         }
548
549         // go down front side
550         if (node->children[side]->contents >= 0 && RecursiveLightPoint (color, node->children[side], x, y, startz, mid))
551                 return true;    // hit something
552         else
553         {
554                 // check for impact on this node
555                 if (node->numsurfaces)
556                 {
557                         int i, ds, dt;
558                         msurface_t *surf;
559
560                         surf = cl.worldmodel->surfaces + node->firstsurface;
561                         for (i = 0;i < node->numsurfaces;i++, surf++)
562                         {
563                                 if (!(surf->flags & SURF_LIGHTMAP))
564                                         continue;       // no lightmaps
565
566                                 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]);
567                                 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]);
568
569                                 if (ds < surf->texturemins[0] || dt < surf->texturemins[1])
570                                         continue;
571
572                                 ds -= surf->texturemins[0];
573                                 dt -= surf->texturemins[1];
574
575                                 if (ds > surf->extents[0] || dt > surf->extents[1])
576                                         continue;
577
578                                 if (surf->samples)
579                                 {
580                                         qbyte *lightmap;
581                                         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;
582                                         line3 = ((surf->extents[0]>>4)+1)*3;
583                                         size3 = ((surf->extents[0]>>4)+1) * ((surf->extents[1]>>4)+1)*3; // LordHavoc: *3 for colored lighting
584
585                                         lightmap = surf->samples + ((dt>>4) * ((surf->extents[0]>>4)+1) + (ds>>4))*3; // LordHavoc: *3 for color
586
587                                         for (maps = 0;maps < MAXLIGHTMAPS && surf->styles[maps] != 255;maps++)
588                                         {
589                                                 scale = d_lightstylevalue[surf->styles[maps]];
590                                                 r00 += lightmap[      0] * scale;g00 += lightmap[      1] * scale;b00 += lightmap[      2] * scale;
591                                                 r01 += lightmap[      3] * scale;g01 += lightmap[      4] * scale;b01 += lightmap[      5] * scale;
592                                                 r10 += lightmap[line3+0] * scale;g10 += lightmap[line3+1] * scale;b10 += lightmap[line3+2] * scale;
593                                                 r11 += lightmap[line3+3] * scale;g11 += lightmap[line3+4] * scale;b11 += lightmap[line3+5] * scale;
594                                                 lightmap += size3;
595                                         }
596
597 /*
598 LordHavoc: here's the readable version of the interpolation
599 code, not quite as easy for the compiler to optimize...
600
601 dsfrac is the X position in the lightmap pixel, * 16
602 dtfrac is the Y position in the lightmap pixel, * 16
603 r00 is top left corner, r01 is top right corner
604 r10 is bottom left corner, r11 is bottom right corner
605 g and b are the same layout.
606 r0 and r1 are the top and bottom intermediate results
607
608 first we interpolate the top two points, to get the top
609 edge sample
610
611         r0 = (((r01-r00) * dsfrac) >> 4) + r00;
612         g0 = (((g01-g00) * dsfrac) >> 4) + g00;
613         b0 = (((b01-b00) * dsfrac) >> 4) + b00;
614
615 then we interpolate the bottom two points, to get the
616 bottom edge sample
617
618         r1 = (((r11-r10) * dsfrac) >> 4) + r10;
619         g1 = (((g11-g10) * dsfrac) >> 4) + g10;
620         b1 = (((b11-b10) * dsfrac) >> 4) + b10;
621
622 then we interpolate the top and bottom samples to get the
623 middle sample (the one which was requested)
624
625         r = (((r1-r0) * dtfrac) >> 4) + r0;
626         g = (((g1-g0) * dtfrac) >> 4) + g0;
627         b = (((b1-b0) * dtfrac) >> 4) + b0;
628 */
629
630                                         color[0] += (float) ((((((((r11-r10) * dsfrac) >> 4) + r10)-((((r01-r00) * dsfrac) >> 4) + r00)) * dtfrac) >> 4) + ((((r01-r00) * dsfrac) >> 4) + r00)) * (1.0f / 32768.0f);
631                                         color[1] += (float) ((((((((g11-g10) * dsfrac) >> 4) + g10)-((((g01-g00) * dsfrac) >> 4) + g00)) * dtfrac) >> 4) + ((((g01-g00) * dsfrac) >> 4) + g00)) * (1.0f / 32768.0f);
632                                         color[2] += (float) ((((((((b11-b10) * dsfrac) >> 4) + b10)-((((b01-b00) * dsfrac) >> 4) + b00)) * dtfrac) >> 4) + ((((b01-b00) * dsfrac) >> 4) + b00)) * (1.0f / 32768.0f);
633                                 }
634                                 return true; // success
635                         }
636                 }
637
638                 // go down back side
639                 node = node->children[side ^ 1];
640                 startz = mid;
641                 distz = endz - startz;
642                 goto loc0;
643         }
644 }
645
646 void R_CompleteLightPoint (vec3_t color, const vec3_t p, int dynamic, const mleaf_t *leaf)
647 {
648         int i;
649         const int *dlightbits;
650         vec3_t v;
651         float f;
652         rdlight_t *rd;
653         mlight_t *sl;
654         if (leaf == NULL)
655                 leaf = Mod_PointInLeaf(p, cl.worldmodel);
656
657         if (leaf->contents == CONTENTS_SOLID)
658         {
659                 color[0] = color[1] = color[2] = 0;
660                 return;
661         }
662
663         if (r_fullbright.integer || !cl.worldmodel->lightdata)
664         {
665                 color[0] = color[1] = color[2] = 2;
666                 return;
667         }
668
669         color[0] = color[1] = color[2] = r_ambient.value * (2.0f / 128.0f);
670         if (cl.worldmodel->numlights)
671         {
672                 for (i = 0;i < cl.worldmodel->numlights;i++)
673                 {
674                         sl = cl.worldmodel->lights + i;
675                         if (d_lightstylevalue[sl->style] > 0)
676                         {
677                                 VectorSubtract (p, sl->origin, v);
678                                 f = ((1.0f / (DotProduct(v, v) * sl->falloff + sl->distbias)) - sl->subtract);
679                                 if (f > 0 && CL_TraceLine(p, sl->origin, NULL, NULL, 0, false) == 1)
680                                 {
681                                         f *= d_lightstylevalue[sl->style] * (1.0f / 65536.0f);
682                                         VectorMA(color, f, sl->light, color);
683                                 }
684                         }
685                 }
686         }
687         else
688                 RecursiveLightPoint (color, cl.worldmodel->nodes, p[0], p[1], p[2], p[2] - 65536);
689
690         if (dynamic && leaf->dlightframe == r_framecount)
691         {
692                 dlightbits = leaf->dlightbits;
693                 for (i = 0;i < r_numdlights;i++)
694                 {
695                         if (!(dlightbits[i >> 5] & (1 << (i & 31))))
696                                 continue;
697                         rd = r_dlight + i;
698                         VectorSubtract (p, rd->origin, v);
699                         f = DotProduct(v, v);
700                         if (f < rd->cullradius2)
701                         {
702                                 f = (1.0f / (f + LIGHTOFFSET)) - rd->subtract;
703                                 VectorMA(color, f, rd->light, color);
704                         }
705                 }
706         }
707 }
708
709 void R_ModelLightPoint (const entity_render_t *ent, vec3_t color, const vec3_t p, int *dlightbits)
710 {
711         mleaf_t *leaf;
712         leaf = Mod_PointInLeaf(p, cl.worldmodel);
713         if (leaf->contents == CONTENTS_SOLID)
714         {
715                 color[0] = color[1] = color[2] = 0;
716                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
717                 return;
718         }
719
720         if (r_fullbright.integer || !cl.worldmodel->lightdata || ent->effects & EF_FULLBRIGHT)
721         {
722                 color[0] = color[1] = color[2] = 2;
723                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
724                 return;
725         }
726
727         color[0] = color[1] = color[2] = r_ambient.value * (2.0f / 128.0f);
728         if (!cl.worldmodel->numlights)
729                 RecursiveLightPoint (color, cl.worldmodel->nodes, p[0], p[1], p[2], p[2] - 65536);
730
731         if (leaf->dlightframe == r_framecount)
732         {
733                 dlightbits[0] = leaf->dlightbits[0];
734                 dlightbits[1] = leaf->dlightbits[1];
735                 dlightbits[2] = leaf->dlightbits[2];
736                 dlightbits[3] = leaf->dlightbits[3];
737                 dlightbits[4] = leaf->dlightbits[4];
738                 dlightbits[5] = leaf->dlightbits[5];
739                 dlightbits[6] = leaf->dlightbits[6];
740                 dlightbits[7] = leaf->dlightbits[7];
741         }
742         else
743                 dlightbits[0] = dlightbits[1] = dlightbits[2] = dlightbits[3] = dlightbits[4] = dlightbits[5] = dlightbits[6] = dlightbits[7] = 0;
744 }
745
746 void R_LightModel(const entity_render_t *ent, int numverts, float colorr, float colorg, float colorb, int worldcoords)
747 {
748         int i, j, nearlights = 0, maxnearlights = r_modellights.integer;
749         float color[3], basecolor[3], v[3], t, *av, *avn, *avc, a, f, dist2, mscale, dot, stylescale, intensity, ambientcolor[3];
750         struct
751         {
752                 vec3_t origin;
753                 //vec_t cullradius2;
754                 vec3_t light;
755                 // how much this light would contribute to ambient if replaced
756                 vec3_t ambientlight;
757                 vec_t subtract;
758                 vec_t falloff;
759                 vec_t offset;
760                 // used for choosing only the brightest lights
761                 vec_t intensity;
762         }
763         nearlight[MAX_DLIGHTS], *nl;
764         int modeldlightbits[8];
765         mlight_t *sl;
766         rdlight_t *rd;
767         a = ent->alpha;
768         // scale of the model's coordinate space, to alter light attenuation to match
769         // make the mscale squared so it can scale the squared distance results
770         mscale = ent->scale * ent->scale;
771         if ((maxnearlights != 0) && !r_fullbright.integer && !(ent->effects & EF_FULLBRIGHT))
772         {
773                 R_ModelLightPoint(ent, basecolor, ent->origin, modeldlightbits);
774
775                 nl = &nearlight[0];
776                 for (i = 0;i < ent->numentlights;i++)
777                 {
778                         sl = cl.worldmodel->lights + ent->entlights[i];
779                         stylescale = d_lightstylevalue[sl->style] * (1.0f / 65536.0f);
780                         VectorSubtract (ent->origin, sl->origin, v);
781                         f = ((1.0f / (DotProduct(v, v) * sl->falloff + sl->distbias)) - sl->subtract) * stylescale;
782                         VectorScale(sl->light, f, ambientcolor);
783                         intensity = DotProduct(ambientcolor, ambientcolor);
784                         if (f < 0)
785                                 intensity *= -1.0f;
786                         if (nearlights < maxnearlights)
787                                 j = nearlights++;
788                         else
789                         {
790                                 for (j = 0;j < maxnearlights;j++)
791                                 {
792                                         if (nearlight[j].intensity < intensity)
793                                         {
794                                                 if (nearlight[j].intensity > 0)
795                                                         VectorAdd(basecolor, nearlight[j].ambientlight, basecolor);
796                                                 break;
797                                         }
798                                 }
799                         }
800                         if (j >= maxnearlights)
801                         {
802                                 // this light is less significant than all others,
803                                 // add it to ambient
804                                 if (intensity > 0)
805                                         VectorAdd(basecolor, ambientcolor, basecolor);
806                         }
807                         else
808                         {
809                                 nl = nearlight + j;
810                                 nl->intensity = intensity;
811                                 // transform the light into the model's coordinate system
812                                 if (worldcoords)
813                                         VectorCopy(sl->origin, nl->origin);
814                                 else
815                                         //softwareuntransform(sl->origin, nl->origin);
816                                         Matrix4x4_Transform(&ent->inversematrix, sl->origin, nl->origin);
817                                 // integrate mscale into falloff, for maximum speed
818                                 nl->falloff = sl->falloff * mscale;
819                                 VectorCopy(ambientcolor, nl->ambientlight);
820                                 nl->light[0] = sl->light[0] * stylescale * colorr * 4.0f;
821                                 nl->light[1] = sl->light[1] * stylescale * colorg * 4.0f;
822                                 nl->light[2] = sl->light[2] * stylescale * colorb * 4.0f;
823                                 nl->subtract = sl->subtract;
824                                 nl->offset = sl->distbias;
825                         }
826                 }
827                 for (i = 0;i < r_numdlights;i++)
828                 {
829                         if (!(modeldlightbits[i >> 5] & (1 << (i & 31))))
830                                 continue;
831                         rd = r_dlight + i;
832                         VectorSubtract (ent->origin, rd->origin, v);
833                         f = ((1.0f / (DotProduct(v, v) + LIGHTOFFSET)) - rd->subtract);
834                         VectorScale(rd->light, f, ambientcolor);
835                         intensity = DotProduct(ambientcolor, ambientcolor);
836                         if (f < 0)
837                                 intensity *= -1.0f;
838                         if (nearlights < maxnearlights)
839                                 j = nearlights++;
840                         else
841                         {
842                                 for (j = 0;j < maxnearlights;j++)
843                                 {
844                                         if (nearlight[j].intensity < intensity)
845                                         {
846                                                 if (nearlight[j].intensity > 0)
847                                                         VectorAdd(basecolor, nearlight[j].ambientlight, basecolor);
848                                                 break;
849                                         }
850                                 }
851                         }
852                         if (j >= maxnearlights)
853                         {
854                                 // this light is less significant than all others,
855                                 // add it to ambient
856                                 if (intensity > 0)
857                                         VectorAdd(basecolor, ambientcolor, basecolor);
858                         }
859                         else
860                         {
861                                 nl = nearlight + j;
862                                 nl->intensity = intensity;
863                                 // transform the light into the model's coordinate system
864                                 if (worldcoords)
865                                         VectorCopy(rd->origin, nl->origin);
866                                 else
867                                 {
868                                         //softwareuntransform(rd->origin, nl->origin);
869                                         Matrix4x4_Transform(&ent->inversematrix, rd->origin, nl->origin);
870                                         /*
871                                         Con_Printf("%i %s : %f %f %f : %f %f %f\n%f %f %f %f\n%f %f %f %f\n%f %f %f %f\n%f %f %f %f\n"
872                                         , rd - r_dlight, ent->model->name
873                                         , rd->origin[0], rd->origin[1], rd->origin[2]
874                                         , nl->origin[0], nl->origin[1], nl->origin[2]
875                                         , ent->inversematrix.m[0][0], ent->inversematrix.m[0][1], ent->inversematrix.m[0][2], ent->inversematrix.m[0][3]
876                                         , ent->inversematrix.m[1][0], ent->inversematrix.m[1][1], ent->inversematrix.m[1][2], ent->inversematrix.m[1][3]
877                                         , ent->inversematrix.m[2][0], ent->inversematrix.m[2][1], ent->inversematrix.m[2][2], ent->inversematrix.m[2][3]
878                                         , ent->inversematrix.m[3][0], ent->inversematrix.m[3][1], ent->inversematrix.m[3][2], ent->inversematrix.m[3][3]);
879                                         */
880                                 }
881                                 // integrate mscale into falloff, for maximum speed
882                                 nl->falloff = mscale;
883                                 VectorCopy(ambientcolor, nl->ambientlight);
884                                 nl->light[0] = rd->light[0] * colorr * 4.0f;
885                                 nl->light[1] = rd->light[1] * colorg * 4.0f;
886                                 nl->light[2] = rd->light[2] * colorb * 4.0f;
887                                 nl->subtract = rd->subtract;
888                                 nl->offset = LIGHTOFFSET;
889                         }
890                 }
891         }
892         else
893         {
894                 R_CompleteLightPoint (basecolor, ent->origin, true, NULL);
895         }
896         basecolor[0] *= colorr;
897         basecolor[1] *= colorg;
898         basecolor[2] *= colorb;
899         avc = aliasvertcolor;
900         if (nearlights)
901         {
902                 av = aliasvert;
903                 avn = aliasvertnorm;
904                 for (i = 0;i < numverts;i++)
905                 {
906                         VectorCopy(basecolor, color);
907                         for (j = 0, nl = &nearlight[0];j < nearlights;j++, nl++)
908                         {
909                                 VectorSubtract(nl->origin, av, v);
910                                 // directional shading
911                                 dot = DotProduct(avn,v);
912                                 if (dot > 0)
913                                 {
914                                         // the vertex normal faces the light
915
916                                         // do the distance attenuation
917                                         dist2 = DotProduct(v,v);
918                                         f = (1.0f / (dist2 * nl->falloff + nl->offset)) - nl->subtract;
919                                         if (f > 0)
920                                         {
921                                                 //#if SLOWMATH
922                                                 t = 1.0f / sqrt(dist2);
923                                                 //#else
924                                                 //*((int *)&t) = 0x5f3759df - ((* (int *) &dist2) >> 1);
925                                                 //t = t * (1.5f - (dist2 * 0.5f * t * t));
926                                                 //#endif
927
928                                                 // dot * t is dotproduct with a normalized v.
929                                                 // (the result would be -1 to +1, but we already
930                                                 // eliminated the <= 0 case, so it is 0 to 1)
931
932                                                 // the hardness variables are for backlighting/shinyness
933                                                 // these have been hardwired at * 0.5 + 0.5 to match
934                                                 // the quake map lighting utility's equations
935                                                 f *= dot * t;// * 0.5f + 0.5f;// * hardness + hardnessoffset;
936                                                 VectorMA(color, f, nl->light, color);
937                                         }
938                                 }
939                         }
940
941                         VectorCopy(color, avc);
942                         avc[3] = a;
943                         avc += 4;
944                         av += 4;
945                         avn += 3;
946                 }
947         }
948         else
949         {
950                 for (i = 0;i < numverts;i++)
951                 {
952                         VectorCopy(basecolor, avc);
953                         avc[3] = a;
954                         avc += 4;
955                 }
956         }
957 }
958
959 void R_UpdateEntLights(entity_render_t *ent)
960 {
961         int i;
962         const mlight_t *sl;
963         vec3_t v;
964         VectorSubtract(ent->origin, ent->entlightsorigin, v);
965         if (ent->entlightsframe != (r_framecount - 1) || (realtime > ent->entlightstime && DotProduct(v,v) >= 1.0f))
966         {
967                 ent->entlightstime = realtime + 0.1;
968                 VectorCopy(ent->origin, ent->entlightsorigin);
969                 ent->numentlights = 0;
970                 for (i = 0, sl = cl.worldmodel->lights;i < cl.worldmodel->numlights && ent->numentlights < MAXENTLIGHTS;i++, sl++)
971                         if (CL_TraceLine(ent->origin, sl->origin, NULL, NULL, 0, false) == 1)
972                                 ent->entlights[ent->numentlights++] = i;
973         }
974         ent->entlightsframe = r_framecount;
975 }