1 /*
2 trace.c
3
4 (description)
5
6 Copyright (C) 1996-1997 Id Software, Inc.
7 Copyright (C) 2002 Colin Thompson
8
9 This program is free software; you can redistribute it and/or
10 modify it under the terms of the GNU General Public License
11 as published by the Free Software Foundation; either version 2
12 of the License, or (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
17
18 See the GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to:
22
23 Free Software Foundation, Inc.
24 59 Temple Place - Suite 330
25 Boston, MA 02111-1307, USA
26
27 */
28 #ifdef HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31
32 #ifdef HAVE_UNISTD_H
33 # include <unistd.h>
34 #endif
35 #ifdef HAVE_IO_H
36 # include <io.h>
37 #endif
38 #ifdef HAVE_STRING_H
39 # include <string.h>
40 #endif
41 #ifdef HAVE_STRINGS_H
42 # include <strings.h>
43 #endif
44 #include <stdlib.h>
45
46 #include "QF/bspfile.h"
47 #include "QF/dstring.h"
48 #include "QF/mathlib.h"
49 #include "QF/qtypes.h"
50 #include "QF/quakefs.h"
51 #include "QF/sys.h"
52
53 #include "compat.h"
54
55 #include "light.h"
56 #include "entities.h"
57 #include "noise.h"
58 #include "options.h"
59 #include "threads.h"
60
61 int c_bad;
62 int c_culldistplane, c_proper;
63
64 /*
65 SAMPLE POINT DETERMINATION
66
67 void SetupBlock (dface_t *f) Returns with surfpt[] set
68
69 This is a little tricky because the lightmap covers more area than the face.
70 If done in the straightforward fashion, some of the
71 sample points will be inside walls or on the other side of walls, causing
72 false shadows and light bleeds.
73
74 To solve this, I consider a sample point valid only if a line can be drawn
75 between it and the exact midpoint of the face. If invalid, it is adjusted
76 towards the center until it is valid.
77
78 (this doesn't completely work)
79 */
80
81
82 /*
83 CalcFaceVectors
84
85 Fills in texorg, worldtotex. and textoworld
86 */
87 static void
CalcFaceVectors(lightinfo_t * l,vec3_t faceorg)88 CalcFaceVectors (lightinfo_t *l, vec3_t faceorg)
89 {
90 int i, j;
91 float distscale;
92 vec3_t texnormal;
93 vec_t dist, len;
94 texinfo_t *tex;
95
96 tex = &bsp->texinfo[l->face->texinfo];
97
98 // convert from float to vec_t
99 for (i = 0; i < 2; i++)
100 for (j = 0; j < 3; j++)
101 l->worldtotex[i][j] = tex->vecs[i][j];
102
103 // calculate a normal to the texture axis. points can
104 // be moved along this without changing their S/T
105 texnormal[0] = tex->vecs[1][1] * tex->vecs[0][2] -
106 tex->vecs[1][2] * tex->vecs[0][1];
107 texnormal[1] = tex->vecs[1][2] * tex->vecs[0][0] -
108 tex->vecs[1][0] * tex->vecs[0][2];
109 texnormal[2] = tex->vecs[1][0] * tex->vecs[0][1] -
110 tex->vecs[1][1] * tex->vecs[0][0];
111 VectorNormalize (texnormal);
112
113 // flip it towards plane normal
114 distscale = DotProduct (texnormal, l->facenormal);
115 if (!distscale)
116 fprintf (stderr, "Texture axis perpendicular to face");
117 if (distscale < 0) {
118 distscale = -distscale;
119 VectorNegate (texnormal, texnormal);
120 }
121
122 // distscale is the ratio of the distance along the
123 // texture normal to the distance along the plane normal
124 distscale = 1 / distscale;
125
126 for (i = 0; i < 2; i++) {
127 len = VectorLength (l->worldtotex[i]);
128 dist = DotProduct (l->worldtotex[i], l->facenormal);
129 dist *= distscale;
130 VectorMultSub (l->worldtotex[i], dist, texnormal, l->textoworld[i]);
131 VectorScale (l->textoworld[i], (1 / len) * (1 / len),
132 l->textoworld[i]);
133 }
134
135 // calculate texorg on the texture plane
136 for (i = 0; i < 3; i++)
137 l->texorg[i] = -tex->vecs[0][3] * l->textoworld[0][i] -
138 tex->vecs[1][3] * l->textoworld[1][i];
139
140 VectorAdd (l->texorg, faceorg, l->texorg);
141
142 // project back to the face plane
143 dist = DotProduct (l->texorg, l->facenormal) - l->facedist - 1;
144 dist *= distscale;
145 VectorMultSub (l->texorg, dist, texnormal, l->texorg);
146 }
147
148 /*
149 CalcFaceExtents
150
151 Fills in s->texmins[] and s->texsize[]
152 also sets exactmins[] and exactmaxs[]
153 */
154 static void
CalcFaceExtents(lightinfo_t * l)155 CalcFaceExtents (lightinfo_t *l)
156 {
157 int i, j, e;
158 vec_t mins[2], maxs[2], val;
159 dface_t *s;
160 dvertex_t *v;
161 texinfo_t *tex;
162
163 s = l->face;
164
165 mins[0] = mins[1] = BOGUS_RANGE;
166 maxs[0] = maxs[1] = -BOGUS_RANGE;
167
168 tex = &bsp->texinfo[s->texinfo];
169
170 for (i = 0; i < s->numedges; i++) {
171 e = bsp->surfedges[s->firstedge + i];
172 if (e >= 0)
173 v = bsp->vertexes + bsp->edges[e].v[0];
174 else
175 v = bsp->vertexes + bsp->edges[-e].v[1];
176
177 for (j = 0; j < 2; j++) {
178 val = DotProduct (v->point, tex->vecs[j]) + tex->vecs[j][3];
179 if (val < mins[j])
180 mins[j] = val;
181 if (val > maxs[j])
182 maxs[j] = val;
183 }
184 }
185
186 for (i = 0; i < 2; i++) {
187 l->exactmins[i] = mins[i];
188 l->exactmaxs[i] = maxs[i];
189
190 mins[i] = floor (mins[i] / 16);
191 maxs[i] = ceil (maxs[i] / 16);
192
193 l->texmins[i] = mins[i];
194 l->texsize[i] = maxs[i] - mins[i] + 1;
195 if (l->texsize[i] > 256)
196 fprintf (stderr, "Bad surface extents");
197 }
198 }
199
200 static inline void
CalcSamples(lightinfo_t * l)201 CalcSamples (lightinfo_t *l)
202 {
203 l->numsamples = l->texsize[0] * l->texsize[1];
204 }
205
206 /*
207 CalcPoints
208
209 For each texture aligned grid point, back project onto the plane
210 to get the world xyz value of the sample point
211 */
212 static void
CalcPoints(lightinfo_t * l)213 CalcPoints (lightinfo_t *l)
214 {
215 int realw, realh, stepbit, j, s, t, w, h;
216 vec_t mids, midt, starts, startt, us, ut;
217 vec3_t facemid, v;
218 lightpoint_t *point;
219
220 // fill in surforg
221 // the points are biased towards the center of the surface
222 // to help avoid edge cases just inside walls
223 mids = (l->exactmaxs[0] + l->exactmins[0]) / 2;
224 midt = (l->exactmaxs[1] + l->exactmins[1]) / 2;
225
226 for (j = 0; j < 3; j++)
227 facemid[j] = l->texorg[j] +
228 l->textoworld[0][j] * mids +
229 l->textoworld[1][j] * midt;
230
231 realw = l->texsize[0];
232 realh = l->texsize[1];
233 starts = l->texmins[0] * 16;
234 startt = l->texmins[1] * 16;
235
236 stepbit = 4 - options.extrabit;
237
238 w = realw << options.extrabit;
239 h = realh << options.extrabit;
240
241 if (stepbit < 4) {
242 starts -= 1 << stepbit;
243 startt -= 1 << stepbit;
244 }
245
246 point = l->point;
247 l->numpoints = w * h;
248 for (t = 0; t < h; t++) {
249 for (s = 0; s < w; s++, point++) {
250 us = starts + (s << stepbit);
251 ut = startt + (t << stepbit);
252 point->samplepos = ((t >> options.extrabit) * realw
253 + (s >> options.extrabit));
254
255 // calculate texture point
256 for (j = 0; j < 3; j++)
257 point->v[j] = l->texorg[j] +
258 l->textoworld[0][j] * us + l->textoworld[1][j] * ut;
259
260 if (!TestLine (l, facemid, point->v)) {
261 VectorCopy(l->testlineimpact, point->v);
262 VectorSubtract(facemid, point->v, v);
263 VectorNormalize(v);
264 VectorMultAdd (point->v, 0.25, v, point->v);
265 }
266 }
267 }
268 }
269
270 static void
SingleLightFace(entity_t * light,lightinfo_t * l)271 SingleLightFace (entity_t *light, lightinfo_t *l)
272 {
273 int mapnum, i;
274 qboolean hit;
275 vec3_t incoming, spotvec;
276 vec_t angle, dist, idist, lightfalloff, lightsubtract, spotcone;
277 vec_t add = 0.0;
278 lightpoint_t *point;
279 lightsample_t *sample;
280
281 dist = DotProduct (light->origin, l->facenormal) - l->facedist;
282 dist *= options.distance;
283
284 // don't bother with lights behind the surface
285 if (dist <= -0.25)
286 return;
287
288 lightfalloff = light->falloff;
289 lightsubtract = light->subbrightness;
290
291 // don't bother with light too far away
292 if (light->radius && dist > light->radius) {
293 c_culldistplane++;
294 return;
295 }
296 if (lightsubtract > (1.0 / (dist * dist * lightfalloff + LIGHTDISTBIAS))) {
297 c_culldistplane++;
298 return;
299 }
300
301 for (mapnum = 0; mapnum < MAXLIGHTMAPS; mapnum++) {
302 if (l->lightstyles[mapnum] == light->style)
303 break;
304 if (l->lightstyles[mapnum] == 255) {
305 memset (l->sample[mapnum], 0,
306 sizeof (lightsample_t) * l->numsamples);
307 break;
308 }
309 }
310 if (mapnum == MAXLIGHTMAPS) {
311 printf ("WARNING: Too many light styles on a face\n");
312 return;
313 }
314
315 spotcone = light->spotcone;
316 VectorCopy(light->spotdir, spotvec);
317
318 // check it for real
319 hit = false;
320 c_proper++;
321
322 for (i = 0, point = l->point; i < l->numpoints; i++, point++) {
323 VectorSubtract (light->origin, point->v, incoming);
324 // avoid float roundoff
325 dist = sqrt (DotProduct(incoming, incoming));
326 idist = 1.0 / dist;
327 VectorScale (incoming, idist, incoming);
328
329 if (light->radius && dist > light->radius)
330 continue;
331
332 // spotlight cutoff
333 if (spotcone && DotProduct (spotvec, incoming) > spotcone)
334 continue;
335
336 angle = DotProduct (incoming, l->facenormal);
337
338 switch (light->attenuation) {
339 case LIGHT_LINEAR:
340 add = fabs (light->light) - dist;
341 break;
342 case LIGHT_RADIUS:
343 add = fabs (light->light) * (light->radius - dist);
344 add /= light->radius;
345 break;
346 case LIGHT_INVERSE:
347 add = fabs (light->light) / dist;
348 break;
349 case LIGHT_REALISTIC:
350 add = fabs (light->light) / (dist * dist);
351 break;
352 case LIGHT_NO_ATTEN:
353 add = fabs (light->light);
354 break;
355 case LIGHT_LH:
356 add = 1 / (dist * dist * lightfalloff + LIGHTDISTBIAS);
357 // LordHavoc: changed to be more realistic (entirely different
358 // lighting model)
359 // LordHavoc: use subbrightness on all lights, simply to have
360 // some distance culling
361 add -= lightsubtract;
362 break;
363 }
364
365 if (light->noise) {
366 int seed = light - entities;
367 vec3_t snap;
368 vec_t intensity = 0.0;
369 lightpoint_t *noise_point = point;
370
371 if (options.extrascale) {
372 // FIXME not correct for extrascale > 2
373 // We don't want to oversample noise because that just
374 // waters it down. So we "undersample" noise by using
375 // the same surf coord for every group of 4 lightmap pixels
376 // ("undersampling", "pixelation", "anti-interpolation" :-)
377 int width = (l->texsize[0] + 1) * 2;
378 int x = i % width;
379 int y = i / width;
380
381 if (x % 2 && y % 2)
382 noise_point -= width * 3 + 3;
383 else if (y % 2)
384 noise_point -= width * 3;
385 else if (x % 2)
386 noise_point -= 3;
387 }
388
389 if (light->noisetype == NOISE_SMOOTH) {
390 snap_vector (noise_point->v, snap, 0);
391 intensity = noise_scaled (snap, light->resolution, seed);
392 } else
393 snap_vector (noise_point->v, snap, light->resolution);
394
395 if (light->noisetype == NOISE_RANDOM)
396 intensity = noise3d (snap, seed);
397 if (light->noisetype == NOISE_PERLIN)
398 intensity = noise_perlin (snap, light->persistence, seed);
399
400 add *= intensity * light->noise + 1.0 - light->noise;
401 }
402
403 if (add <= 0)
404 continue;
405 if (!TestLine (l, point->v, light->origin))
406 continue;
407
408 if (light->attenuation == LIGHT_LH) {
409 // LordHavoc: FIXME: decide this 0.5 bias based on shader
410 // properties (some are dull, some are shiny)
411 add *= angle * 0.5 + 0.5;
412 } else {
413 add *= angle;
414 }
415 add *= options.extrascale;
416
417 if (light->light < 0)
418 add *= -1; // negative light
419
420 sample = &l->sample[mapnum][point->samplepos];
421 VectorMultAdd (sample->c, add, light->color, sample->c);
422 if (!hit && ((sample->c[0] + sample->c[1] + sample->c[2]) >= 1))
423 hit = true;
424 }
425
426 // if the style has some data now, make sure it is in the list
427 if (hit)
428 l->lightstyles[mapnum] = light->style;
429 }
430
431 #if 0
432 static void
433 FixMinlight (lightinfo_t *l)
434 {
435 float minlight;
436 int i, j;
437
438 minlight = minlights[l->surfnum];
439
440 // if minlight is set, there must be a style 0 light map
441 if (!minlight)
442 return;
443
444 for (i = 0; i < l->numlightstyles; i++) {
445 if (l->lightstyles[i] == 0)
446 break;
447 }
448 if (i == l->numlightstyles) {
449 if (l->numlightstyles == MAXLIGHTMAPS)
450 return; // oh well..
451 for (j = 0; j < l->numsurfpt; j++)
452 l->lightmaps[i][j] = minlight;
453 l->lightstyles[i] = 0;
454 l->numlightstyles++;
455 } else {
456 for (j = 0; j < l->numsurfpt; j++)
457 if (l->lightmaps[i][j] < minlight)
458 l->lightmaps[i][j] = minlight;
459 }
460 }
461 #endif
462
463 void
LightFace(lightinfo_t * l,int surfnum)464 LightFace (lightinfo_t *l, int surfnum)
465 {
466 byte *lit, *out, *outdata, *rgbdata;
467 int ofs, size, red, green, blue, white, i, j;
468 dface_t *f;
469 lightchain_t *lightchain;
470 lightsample_t *sample;
471
472 f = bsp->faces + surfnum;
473
474 l->face = f;
475
476 // some surfaces don't need lightmaps
477 f->lightofs = -1;
478 for (i = 0; i < MAXLIGHTMAPS; i++)
479 f->styles[i] = l->lightstyles[i] = 255;
480
481 if (bsp->texinfo[f->texinfo].flags & TEX_SPECIAL)
482 return; // non-lit texture
483
484 // rotate plane
485 VectorCopy (bsp->planes[f->planenum].normal, l->facenormal);
486 l->facedist = bsp->planes[f->planenum].dist;
487 if (f->side) {
488 VectorNegate (l->facenormal, l->facenormal);
489 l->facedist = -l->facedist;
490 }
491
492 CalcFaceVectors (l, surfaceorgs[surfnum]);
493 CalcFaceExtents (l);
494 CalcSamples (l);
495 CalcPoints (l);
496
497 if (l->numsamples > SINGLEMAP)
498 fprintf (stderr, "Bad lightmap size");
499
500 // cast all lights
501 for (lightchain = surfacelightchain[surfnum]; lightchain;
502 lightchain = lightchain->next) {
503 SingleLightFace (lightchain->light, l);
504 }
505 for (i = 0; i < num_novislights; i++) {
506 SingleLightFace (novislights[i], l);
507 }
508
509 // FixMinlight (&l);
510
511 for (i = 0; i < MAXLIGHTMAPS; i++)
512 if (l->lightstyles[i] == 255)
513 break;
514 size = l->numsamples * i;
515 if (!size) {
516 // no light styles
517 return;
518 }
519
520 // save out the values
521 for (i = 0; i < MAXLIGHTMAPS; i++)
522 f->styles[i] = l->lightstyles[i];
523
524 LOCK;
525 outdata = out = malloc (size * 4);
526 UNLOCK;
527 rgbdata = lit = outdata + size;
528 ofs = GetFileSpace (size);
529 f->lightofs = ofs;
530
531 for (i = 0; i < MAXLIGHTMAPS && f->styles[i] != 255; i++) {
532 for (j = 0, sample = l->sample[i]; j < l->numsamples; j++, sample++) {
533 red = (int) sample->c[0];
534 green = (int) sample->c[1];
535 blue = (int) sample->c[2];
536 white = (int) ((sample->c[0] + sample->c[1] + sample->c[2])
537 * (1.0 / 3.0));
538
539 red = bound (0, red, 255);
540 green = bound (0, green, 255);
541 blue = bound (0, blue, 255);
542 white = bound (0, white, 255);
543 *lit++ = red;
544 *lit++ = green;
545 *lit++ = blue;
546 *out++ = white;
547 }
548 }
549 LOCK;
550 memcpy (lightdata->str + ofs, outdata, size);
551 memcpy (rgblightdata->str + ofs * 3, rgbdata, size * 3);
552 free (outdata);
553 UNLOCK;
554 }
555