1 #pragma warning(disable: 4018) //amckern - 64bit - '<' Singed/Unsigned Mismatch
2
3 #include "qrad.h"
4
5 typedef struct
6 {
7 unsigned offset:24;
8 unsigned values:8;
9 }
10 sparse_row_t;
11
12 typedef struct
13 {
14 sparse_row_t* row;
15 int count;
16 }
17 sparse_column_t;
18
19 sparse_column_t* s_vismatrix;
20
21 // Vismatrix protected
22 #ifdef HLRAD_HULLU
IsVisbitInArray(const unsigned x,const unsigned y)23 static int IsVisbitInArray(const unsigned x, const unsigned y)
24 #else
25 static unsigned IsVisbitInArray(const unsigned x, const unsigned y)
26 #endif
27 {
28 int first, last, current;
29 int y_byte = y / 8;
30 sparse_row_t* row;
31 sparse_column_t* column = s_vismatrix + x;
32
33 if (!column->count)
34 {
35 return -1;
36 }
37
38 first = 0;
39 last = column->count - 1;
40
41 // Warning("Searching . . .");
42 // binary search to find visbit
43 while (1)
44 {
45 current = (first + last) / 2;
46 row = column->row + current;
47 // Warning("first %u, last %u, current %u, row %p, row->offset %u", first, last, current, row, row->offset);
48 if ((row->offset) < y_byte)
49 {
50 first = current + 1;
51 }
52 else if ((row->offset) > y_byte)
53 {
54 last = current - 1;
55 }
56 else
57 {
58 return current;
59 }
60 if (first > last)
61 {
62 return -1;
63 }
64 }
65 }
66
67 // Vismatrix protected
InsertVisbitIntoArray(const unsigned x,const unsigned y)68 static void InsertVisbitIntoArray(const unsigned x, const unsigned y)
69 {
70 unsigned count;
71 unsigned y_byte = y / 8;
72 sparse_column_t* column = s_vismatrix + x;
73 sparse_row_t* row = column->row;
74
75 if (!column->count)
76 {
77 column->count++;
78 row = column->row = (sparse_row_t*)malloc(sizeof(sparse_row_t));
79 row->offset = y_byte;
80 row->values = 1 << (y & 7);
81 return;
82 }
83
84 // Insertion
85 count = 0;
86 while (count < column->count)
87 {
88 if (row->offset > y_byte)
89 {
90 unsigned newsize = (column->count + 1) * sizeof(sparse_row_t);
91 sparse_row_t* newrow = (sparse_row_t*)malloc(newsize);
92
93 memcpy(newrow, column->row, count * sizeof(sparse_row_t));
94 memcpy(newrow + count + 1, column->row + count, (column->count - count) * sizeof(sparse_row_t));
95
96 row = newrow + count;
97 row->offset = y_byte;
98 row->values = 1 << (y & 7);
99
100 free(column->row);
101 column->row = newrow;
102 column->count++;
103 return;
104 }
105
106 row++;
107 count++;
108 }
109
110 // Append
111 {
112 unsigned newsize = (count + 1) * sizeof(sparse_row_t);
113 sparse_row_t* newrow = (sparse_row_t*)malloc(newsize);
114
115 memcpy(newrow, column->row, column->count * sizeof(sparse_row_t));
116
117 row = newrow + column->count;
118 row->offset = y_byte;
119 row->values = 1 << (y & 7);
120
121 free(column->row);
122 column->row = newrow;
123 column->count++;
124 return;
125 }
126 }
127
128 // Vismatrix public
SetVisBit(unsigned x,unsigned y)129 static void SetVisBit(unsigned x, unsigned y)
130 {
131 #ifdef HLRAD_HULLU
132 int offset;
133 #else
134 unsigned offset;
135 #endif
136
137 if (x == y)
138 {
139 return;
140 }
141
142 if (x > y)
143 {
144 const unsigned a = x;
145 const unsigned b = y;
146 x = b;
147 y = a;
148 }
149
150 if (x > g_num_patches)
151 {
152 Warning("in SetVisBit(), x > num_patches");
153 }
154 if (y > g_num_patches)
155 {
156 Warning("in SetVisBit(), y > num_patches");
157 }
158
159 ThreadLock();
160
161 if ((offset = IsVisbitInArray(x, y)) != -1)
162 {
163 s_vismatrix[x].row[offset].values |= 1 << (y & 7);
164 }
165 else
166 {
167 InsertVisbitIntoArray(x, y);
168 }
169
170 ThreadUnlock();
171 }
172
173 // Vismatrix public
174 #ifdef HLRAD_HULLU
CheckVisBitSparse(unsigned x,unsigned y,vec3_t & transparency_out,unsigned int & next_index)175 static bool CheckVisBitSparse(unsigned x, unsigned y, vec3_t &transparency_out, unsigned int &next_index)
176 #else
177 static bool CheckVisBitSparse(unsigned x, unsigned y)
178 #endif
179 {
180 #ifdef HLRAD_HULLU
181 int offset;
182 #else
183 unsigned offset;
184 #endif
185
186 #ifdef HLRAD_HULLU
187 VectorFill(transparency_out, 1.0);
188 #endif
189
190 if (x == y)
191 {
192 return 1;
193 }
194
195 #ifdef HLRAD_HULLU
196 const unsigned a = x;
197 const unsigned b = y;
198 #endif
199
200 if (x > y)
201 {
202 #ifndef HLRAD_HULLU
203 const unsigned a = x;
204 const unsigned b = y;
205 #endif
206 x = b;
207 y = a;
208 }
209
210 if (x > g_num_patches)
211 {
212 Warning("in CheckVisBit(), x > num_patches");
213 }
214 if (y > g_num_patches)
215 {
216 Warning("in CheckVisBit(), y > num_patches");
217 }
218
219 if ((offset = IsVisbitInArray(x, y)) != -1)
220 {
221 #ifdef HLRAD_HULLU
222 if(g_customshadow_with_bouncelight)
223 {
224 GetTransparency(a, b, transparency_out, next_index);
225 }
226 #endif
227 return s_vismatrix[x].row[offset].values & (1 << (y & 7));
228 }
229
230 return false;
231 }
232
233 /*
234 * ==============
235 * TestPatchToFace
236 *
237 * Sets vis bits for all patches in the face
238 * ==============
239 */
TestPatchToFace(const unsigned patchnum,const int facenum,const int head)240 static void TestPatchToFace(const unsigned patchnum, const int facenum, const int head)
241 {
242 patch_t* patch = &g_patches[patchnum];
243 patch_t* patch2 = g_face_patches[facenum];
244
245 #ifdef HLRAD_HULLU
246 vec3_t transparency;
247 #endif
248
249 // if emitter is behind that face plane, skip all patches
250
251 if (patch2)
252 {
253 const dplane_t* plane2 = getPlaneFromFaceNumber(facenum);
254
255 if (DotProduct(patch->origin, plane2->normal) > (PatchPlaneDist(patch2) + MINIMUM_PATCH_DISTANCE))
256 {
257 // we need to do a real test
258 const dplane_t* plane = getPlaneFromFaceNumber(patch->faceNumber);
259
260 for (; patch2; patch2 = patch2->next)
261 {
262 unsigned m = patch2 - g_patches;
263
264 // check vis between patch and patch2
265 // if bit has not already been set
266 // && v2 is not behind light plane
267 // && v2 is visible from v1
268 #ifdef HLRAD_HULLU
269 //removed reset of transparency - TestSegmentAgainstOpaqueList already resets to 1,1,1
270 int facenum = TestSegmentAgainstOpaqueList(patch->origin, patch2->origin, transparency);
271 #else
272 int facenum = TestSegmentAgainstOpaqueList(patch->origin, patch2->origin);
273 #endif
274 if (m > patchnum
275 && (facenum < 0 || facenum == patch2->faceNumber)
276 && (DotProduct(patch2->origin, plane->normal) > (PatchPlaneDist(patch) + MINIMUM_PATCH_DISTANCE))
277 && (TestLine_r(0, patch->origin, patch2->origin) == CONTENTS_EMPTY))
278 {
279
280 #ifdef HLRAD_HULLU
281 // transparency face fix table
282 if(g_customshadow_with_bouncelight && !VectorCompare(transparency, vec3_one) )
283 {
284 AddTransparencyToRawArray(patchnum, m, transparency);
285 }
286 #endif
287 SetVisBit(m, patchnum);
288 }
289 }
290 }
291 }
292 }
293
294 /*
295 * ==============
296 * BuildVisRow
297 *
298 * Calc vis bits from a single patch
299 * ==============
300 */
BuildVisRow(const int patchnum,byte * pvs,const int head)301 static void BuildVisRow(const int patchnum, byte* pvs, const int head)
302 {
303 int j, k, l;
304 byte face_tested[MAX_MAP_FACES];
305 dleaf_t* leaf;
306
307 memset(face_tested, 0, g_numfaces);
308
309 // leaf 0 is the solid leaf (skipped)
310 for (j = 1, leaf = g_dleafs + 1; j < g_numleafs; j++, leaf++)
311 {
312 if (!(pvs[(j - 1) >> 3] & (1 << ((j - 1) & 7))))
313 {
314 continue; // not in pvs
315 }
316 for (k = 0; k < leaf->nummarksurfaces; k++)
317 {
318 l = g_dmarksurfaces[leaf->firstmarksurface + k];
319
320 // faces can be marksurfed by multiple leaves, but
321 // don't bother testing again
322 if (face_tested[l])
323 continue;
324 face_tested[l] = 1;
325
326 TestPatchToFace(patchnum, l, head);
327 }
328 }
329 }
330
331 /*
332 * ===========
333 * BuildVisLeafs
334 *
335 * This is run by multiple threads
336 * ===========
337 */
338 #ifdef SYSTEM_WIN32
339 #pragma warning(push)
340 #pragma warning(disable: 4100) // unreferenced formal parameter
341 #endif
BuildVisLeafs(intptr_t threadnum)342 static void BuildVisLeafs(intptr_t threadnum)
343 {
344 int i;
345 int lface, facenum, facenum2;
346 byte pvs[(MAX_MAP_LEAFS + 7) / 8];
347 dleaf_t* srcleaf;
348 dleaf_t* leaf;
349 patch_t* patch;
350 int head;
351 unsigned patchnum;
352
353 while (1)
354 {
355 //
356 // build a minimal BSP tree that only
357 // covers areas relevent to the PVS
358 //
359 i = GetThreadWork();
360 if (i == -1)
361 {
362 break;
363 }
364 i++; // skip leaf 0
365 srcleaf = &g_dleafs[i];
366 DecompressVis(&g_dvisdata[srcleaf->visofs], pvs, sizeof(pvs));
367 head = 0;
368
369 //
370 // go through all the faces inside the
371 // leaf, and process the patches that
372 // actually have origins inside
373 //
374 for (lface = 0; lface < srcleaf->nummarksurfaces; lface++)
375 {
376 facenum = g_dmarksurfaces[srcleaf->firstmarksurface + lface];
377 for (patch = g_face_patches[facenum]; patch; patch = patch->next)
378 {
379 leaf = PointInLeaf(patch->origin);
380 if (leaf != srcleaf)
381 {
382 continue;
383 }
384
385 patchnum = patch - g_patches;
386 // build to all other world leafs
387 BuildVisRow(patchnum, pvs, head);
388
389 // build to bmodel faces
390 if (g_nummodels < 2)
391 {
392 continue;
393 }
394 for (facenum2 = g_dmodels[1].firstface; facenum2 < g_numfaces; facenum2++)
395 {
396 TestPatchToFace(patchnum, facenum2, head);
397 }
398 }
399 }
400
401 }
402 }
403
404 #ifdef SYSTEM_WIN32
405 #pragma warning(pop)
406 #endif
407
408 /*
409 * ==============
410 * BuildVisMatrix
411 * ==============
412 */
BuildVisMatrix()413 static void BuildVisMatrix()
414 {
415 s_vismatrix = (sparse_column_t*)AllocBlock(g_num_patches * sizeof(sparse_column_t));
416
417 if (!s_vismatrix)
418 {
419 Log("Failed to allocate vismatrix");
420 hlassume(s_vismatrix != NULL, assume_NoMemory);
421 }
422
423 NamedRunThreadsOn(g_numleafs - 1, g_estimate, BuildVisLeafs);
424 }
425
FreeVisMatrix()426 static void FreeVisMatrix()
427 {
428 if (s_vismatrix)
429 {
430 unsigned x;
431 sparse_column_t* item;
432
433 for (x = 0, item = s_vismatrix; x < g_num_patches; x++, item++)
434 {
435 if (item->row)
436 {
437 free(item->row);
438 }
439 }
440 if (FreeBlock(s_vismatrix))
441 {
442 s_vismatrix = NULL;
443 }
444 else
445 {
446 Warning("Unable to free vismatrix");
447 }
448 }
449 }
450
DumpVismatrixInfo()451 static void DumpVismatrixInfo()
452 {
453 unsigned totals[8];
454 unsigned total_vismatrix_memory = sizeof(sparse_column_t) * g_num_patches;
455
456 sparse_column_t* column_end = s_vismatrix + g_num_patches;
457 sparse_column_t* column = s_vismatrix;
458
459 memset(totals, 0, sizeof(totals));
460
461 while (column < column_end)
462 {
463 total_vismatrix_memory += column->count * sizeof(sparse_row_t);
464 column++;
465 }
466
467 Log("%-20s: %5.1f megs\n", "visibility matrix", total_vismatrix_memory / (1024 * 1024.0));
468 }
469
470 //
471 // end old vismat.c
472 ////////////////////////////
473
MakeScalesSparseVismatrix()474 void MakeScalesSparseVismatrix()
475 {
476 char transferfile[_MAX_PATH];
477
478 hlassume(g_num_patches < MAX_SPARSE_VISMATRIX_PATCHES, assume_MAX_PATCHES);
479
480 safe_strncpy(transferfile, g_source, _MAX_PATH);
481 StripExtension(transferfile);
482 DefaultExtension(transferfile, ".inc");
483
484 if (!g_incremental || !readtransfers(transferfile, g_num_patches))
485 {
486 // determine visibility between g_patches
487 BuildVisMatrix();
488 DumpVismatrixInfo();
489 g_CheckVisBit = CheckVisBitSparse;
490
491 #ifdef HLRAD_HULLU
492 CreateFinalTransparencyArrays("custom shadow array");
493 #endif
494
495 #ifndef HLRAD_HULLU
496 NamedRunThreadsOn(g_num_patches, g_estimate, MakeScales);
497 #else
498 if(g_rgb_transfers)
499 {NamedRunThreadsOn(g_num_patches, g_estimate, MakeRGBScales);}
500 else
501 {NamedRunThreadsOn(g_num_patches, g_estimate, MakeScales);}
502 #endif
503 FreeVisMatrix();
504
505 #ifdef HLRAD_HULLU
506 FreeTransparencyArrays();
507 #endif
508
509 // invert the transfers for gather vs scatter
510 #ifndef HLRAD_HULLU
511 NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapTransfers);
512 #else
513 if(g_rgb_transfers)
514 {NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapRGBTransfers);}
515 else
516 {NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapTransfers);}
517 #endif
518 if (g_incremental)
519 {
520 writetransfers(transferfile, g_num_patches);
521 }
522 else
523 {
524 _unlink(transferfile);
525 }
526 // release visibility matrix
527 DumpTransfersMemoryUsage();
528 }
529 }
530