1 |
#ifndef lint |
2 |
static const char RCSid[] = "$Id: pmapdata.c,v 4.35 2016/01/20 16:05:16 taschreg Exp taschreg $"; |
3 |
#endif |
4 |
/* |
5 |
================================================================== |
6 |
Photon map data structures and kd-tree handling |
7 |
|
8 |
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
9 |
(c) Fraunhofer Institute for Solar Energy Systems, |
10 |
(c) Lucerne University of Applied Sciences and Arts, |
11 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
12 |
================================================================== |
13 |
|
14 |
*/ |
15 |
|
16 |
|
17 |
|
18 |
#include "pmap.h" |
19 |
#include "pmaprand.h" |
20 |
#include "pmapmat.h" |
21 |
#include "otypes.h" |
22 |
#include "source.h" |
23 |
#include "rcontrib.h" |
24 |
#include "random.h" |
25 |
|
26 |
|
27 |
|
28 |
PhotonMap *photonMaps [NUM_PMAP_TYPES] = { |
29 |
NULL, NULL, NULL, NULL, NULL, NULL |
30 |
}; |
31 |
|
32 |
|
33 |
|
34 |
void initPhotonMap (PhotonMap *pmap, PhotonMapType t) |
35 |
/* Init photon map 'n' stuff... */ |
36 |
{ |
37 |
if (!pmap) |
38 |
return; |
39 |
|
40 |
pmap -> heapSize = pmap -> heapEnd = 0; |
41 |
pmap -> heap = NULL; |
42 |
pmap -> squeue = NULL; |
43 |
pmap -> biasCompHist = NULL; |
44 |
pmap -> maxPos [0] = pmap -> maxPos [1] = pmap -> maxPos [2] = -FHUGE; |
45 |
pmap -> minPos [0] = pmap -> minPos [1] = pmap -> minPos [2] = FHUGE; |
46 |
pmap -> minGathered = pmap -> maxGathered = pmap -> totalGathered = 0; |
47 |
pmap -> gatherTolerance = gatherTolerance; |
48 |
pmap -> minError = pmap -> maxError = pmap -> rmsError = 0; |
49 |
pmap -> numDensity = 0; |
50 |
pmap -> distribRatio = 1; |
51 |
pmap -> type = t; |
52 |
|
53 |
/* Init local RNG state */ |
54 |
pmap -> randState [0] = 10243; |
55 |
pmap -> randState [1] = 39829; |
56 |
pmap -> randState [2] = 9433; |
57 |
/* pmapSeed(25999, pmap -> randState); */ |
58 |
pmapSeed(randSeed, pmap -> randState); |
59 |
|
60 |
/* Set up type-specific photon lookup callback */ |
61 |
pmap -> lookup = pmapLookup [t]; |
62 |
|
63 |
pmap -> primary = NULL; |
64 |
pmap -> primarySize = pmap -> primaryEnd = 0; |
65 |
} |
66 |
|
67 |
|
68 |
|
69 |
const PhotonPrimary* addPhotonPrimary (PhotonMap *pmap, const RAY *ray) |
70 |
{ |
71 |
PhotonPrimary *prim = NULL; |
72 |
FVECT dvec; |
73 |
|
74 |
if (!pmap || !ray) |
75 |
return NULL; |
76 |
|
77 |
/* Check if last primary ray has spawned photons (srcIdx >= 0, see |
78 |
* addPhoton()), in which case we keep it and allocate a new one; |
79 |
* otherwise we overwrite the unused entry */ |
80 |
if (pmap -> primary && pmap -> primary [pmap -> primaryEnd].srcIdx >= 0) |
81 |
pmap -> primaryEnd++; |
82 |
|
83 |
if (!pmap -> primarySize || pmap -> primaryEnd >= pmap -> primarySize) { |
84 |
/* Allocate/enlarge array */ |
85 |
pmap -> primarySize += pmap -> heapSizeInc; |
86 |
|
87 |
/* Counter wraparound? */ |
88 |
if (pmap -> primarySize < pmap -> heapSizeInc) |
89 |
error(INTERNAL, "photon primary overflow"); |
90 |
|
91 |
pmap -> primary = (PhotonPrimary *)realloc(pmap -> primary, |
92 |
sizeof(PhotonPrimary) * |
93 |
pmap -> primarySize); |
94 |
if (!pmap -> primary) |
95 |
error(USER, "can't allocate photon primaries"); |
96 |
} |
97 |
|
98 |
prim = pmap -> primary + pmap -> primaryEnd; |
99 |
|
100 |
/* Mark unused with negative source index until path spawns a photon (see |
101 |
* addPhoton()) */ |
102 |
prim -> srcIdx = -1; |
103 |
|
104 |
/* Reverse incident direction to point to light source */ |
105 |
dvec [0] = -ray -> rdir [0]; |
106 |
dvec [1] = -ray -> rdir [1]; |
107 |
dvec [2] = -ray -> rdir [2]; |
108 |
prim -> dir = encodedir(dvec); |
109 |
|
110 |
VCOPY(prim -> pos, ray -> rop); |
111 |
|
112 |
return prim; |
113 |
} |
114 |
|
115 |
|
116 |
|
117 |
const Photon* addPhoton (PhotonMap* pmap, const RAY* ray) |
118 |
{ |
119 |
unsigned i; |
120 |
Photon* photon = NULL; |
121 |
COLOR photonFlux; |
122 |
|
123 |
/* Account for distribution ratio */ |
124 |
if (!pmap || pmapRandom(pmap -> randState) > pmap -> distribRatio) |
125 |
return NULL; |
126 |
|
127 |
/* Don't store on sources */ |
128 |
if (ray -> robj > -1 && islight(objptr(ray -> ro -> omod) -> otype)) |
129 |
return NULL; |
130 |
|
131 |
#if 0 |
132 |
if (inContribPmap(pmap)) { |
133 |
/* Adding contribution photon */ |
134 |
if (ray -> parent && ray -> parent -> rtype & PRIMARY) |
135 |
/* Add primary photon ray if parent is primary; by putting this |
136 |
* here and checking the ray's immediate parent, we only add |
137 |
* primaries that actually contribute photons, and we only add them |
138 |
* once. */ |
139 |
addPhotonPrimary(pmap, ray -> parent); |
140 |
|
141 |
/* Save index to primary ray (remains unchanged if primary already in |
142 |
* array) */ |
143 |
primary = pmap -> primaryEnd; |
144 |
} |
145 |
#endif |
146 |
|
147 |
#ifdef PMAP_ROI |
148 |
/* Store photon if within region of interest -- for egg-spurtz only! */ |
149 |
if (ray -> rop [0] >= pmapROI [0] && ray -> rop [0] <= pmapROI [1] && |
150 |
ray -> rop [1] >= pmapROI [2] && ray -> rop [1] <= pmapROI [3] && |
151 |
ray -> rop [2] >= pmapROI [4] && ray -> rop [2] <= pmapROI [5]) |
152 |
#endif |
153 |
{ |
154 |
if (pmap -> heapEnd >= pmap -> heapSize) { |
155 |
/* Enlarge heap */ |
156 |
pmap -> heapSize += pmap -> heapSizeInc; |
157 |
|
158 |
/* Counter wraparound? */ |
159 |
if (pmap -> heapSize < pmap -> heapSizeInc) |
160 |
error(INTERNAL, "photon heap overflow"); |
161 |
|
162 |
pmap -> heap = (Photon *)realloc(pmap -> heap, |
163 |
sizeof(Photon) * pmap -> heapSize); |
164 |
if (!pmap -> heap) |
165 |
error(USER, "can't allocate photon heap"); |
166 |
} |
167 |
|
168 |
photon = pmap -> heap + pmap -> heapEnd++; |
169 |
|
170 |
/* Adjust flux according to distribution ratio and ray weight */ |
171 |
copycolor(photonFlux, ray -> rcol); |
172 |
scalecolor(photonFlux, |
173 |
ray -> rweight / (pmap -> distribRatio ? pmap -> distribRatio |
174 |
: 1)); |
175 |
setPhotonFlux(photon, photonFlux); |
176 |
|
177 |
/* Set photon position and flags */ |
178 |
VCOPY(photon -> pos, ray -> rop); |
179 |
photon -> flags = PMAP_CAUSTICRAY(ray) ? PMAP_CAUST_BIT : 0; |
180 |
|
181 |
/* Set primary ray index and mark as used for contrib photons */ |
182 |
if (isContribPmap(pmap)) { |
183 |
photon -> primary = pmap -> primaryEnd; |
184 |
pmap -> primary [pmap -> primaryEnd].srcIdx = ray -> rsrc; |
185 |
} |
186 |
else photon -> primary = 0; |
187 |
|
188 |
/* Update min and max positions & set normal */ |
189 |
for (i = 0; i <= 2; i++) { |
190 |
if (photon -> pos [i] < pmap -> minPos [i]) |
191 |
pmap -> minPos [i] = photon -> pos [i]; |
192 |
if (photon -> pos [i] > pmap -> maxPos [i]) |
193 |
pmap -> maxPos [i] = photon -> pos [i]; |
194 |
photon -> norm [i] = 127.0 * (isVolumePmap(pmap) ? ray -> rdir [i] |
195 |
: ray -> ron [i]); |
196 |
} |
197 |
} |
198 |
|
199 |
return photon; |
200 |
} |
201 |
|
202 |
|
203 |
|
204 |
static void nearestNeighbours (PhotonMap* pmap, const float pos [3], |
205 |
const float norm [3], unsigned long node) |
206 |
/* Recursive part of findPhotons(..). |
207 |
Note that all heap and priority queue index handling is 1-based, but |
208 |
accesses to the arrays are 0-based! */ |
209 |
{ |
210 |
Photon* p = &pmap -> heap [node - 1]; |
211 |
unsigned i, j; |
212 |
/* Signed distance to current photon's splitting plane */ |
213 |
float d = pos [photonDiscr(*p)] - p -> pos [photonDiscr(*p)], |
214 |
d2 = d * d; |
215 |
PhotonSQNode* sq = pmap -> squeue; |
216 |
const unsigned sqSize = pmap -> squeueSize; |
217 |
float dv [3]; |
218 |
|
219 |
/* Search subtree closer to pos first; exclude other subtree if the |
220 |
distance to the splitting plane is greater than maxDist */ |
221 |
if (d < 0) { |
222 |
if (node << 1 <= pmap -> heapSize) |
223 |
nearestNeighbours(pmap, pos, norm, node << 1); |
224 |
if (d2 < pmap -> maxDist && node << 1 < pmap -> heapSize) |
225 |
nearestNeighbours(pmap, pos, norm, (node << 1) + 1); |
226 |
} |
227 |
else { |
228 |
if (node << 1 < pmap -> heapSize) |
229 |
nearestNeighbours(pmap, pos, norm, (node << 1) + 1); |
230 |
if (d2 < pmap -> maxDist && node << 1 <= pmap -> heapSize) |
231 |
nearestNeighbours(pmap, pos, norm, node << 1); |
232 |
} |
233 |
|
234 |
/* Reject photon if normal faces away (ignored for volume photons) with |
235 |
* 50% tolerance to account for perturbation; note photon normal is coded |
236 |
* in range [-127,127]. */ |
237 |
if (norm && DOT(norm, p -> norm) <= 63.5 * frandom()) |
238 |
return; |
239 |
|
240 |
if (isContribPmap(pmap) && pmap -> srcContrib) { |
241 |
/* Lookup in contribution photon map */ |
242 |
OBJREC *srcMod; |
243 |
const int srcIdx = photonSrcIdx(pmap, p); |
244 |
|
245 |
if (srcIdx < 0 || srcIdx >= nsources) |
246 |
error(INTERNAL, "invalid light source index in photon map"); |
247 |
|
248 |
srcMod = findmaterial(source [srcIdx].so); |
249 |
|
250 |
/* Reject photon if contributions from light source which emitted it |
251 |
* are not sought */ |
252 |
if (!lu_find(pmap -> srcContrib, srcMod -> oname) -> data) |
253 |
return; |
254 |
|
255 |
/* Reject non-caustic photon if lookup for caustic contribs */ |
256 |
if (pmap -> lookupFlags & PMAP_CAUST_BIT & ~p -> flags) |
257 |
return; |
258 |
} |
259 |
|
260 |
/* Squared distance to current photon */ |
261 |
dv [0] = pos [0] - p -> pos [0]; |
262 |
dv [1] = pos [1] - p -> pos [1]; |
263 |
dv [2] = pos [2] - p -> pos [2]; |
264 |
d2 = DOT(dv, dv); |
265 |
|
266 |
/* Accept photon if closer than current max dist & add to priority queue */ |
267 |
if (d2 < pmap -> maxDist) { |
268 |
if (pmap -> squeueEnd < sqSize) { |
269 |
/* Priority queue not full; append photon and restore heap */ |
270 |
i = ++pmap -> squeueEnd; |
271 |
|
272 |
while (i > 1 && sq [(i >> 1) - 1].dist <= d2) { |
273 |
sq [i - 1].photon = sq [(i >> 1) - 1].photon; |
274 |
sq [i - 1].dist = sq [(i >> 1) - 1].dist; |
275 |
i >>= 1; |
276 |
} |
277 |
|
278 |
sq [--i].photon = p; |
279 |
sq [i].dist = d2; |
280 |
/* Update maxDist if we've just filled the queue */ |
281 |
if (pmap -> squeueEnd >= pmap -> squeueSize) |
282 |
pmap -> maxDist = sq [0].dist; |
283 |
} |
284 |
else { |
285 |
/* Priority queue full; replace maximum, restore heap, and |
286 |
update maxDist */ |
287 |
i = 1; |
288 |
|
289 |
while (i <= sqSize >> 1) { |
290 |
j = i << 1; |
291 |
if (j < sqSize && sq [j - 1].dist < sq [j].dist) |
292 |
j++; |
293 |
if (d2 >= sq [j - 1].dist) |
294 |
break; |
295 |
sq [i - 1].photon = sq [j - 1].photon; |
296 |
sq [i - 1].dist = sq [j - 1].dist; |
297 |
i = j; |
298 |
} |
299 |
|
300 |
sq [--i].photon = p; |
301 |
sq [i].dist = d2; |
302 |
pmap -> maxDist = sq [0].dist; |
303 |
} |
304 |
} |
305 |
} |
306 |
|
307 |
|
308 |
|
309 |
/* Dynamic max photon search radius increase and reduction factors */ |
310 |
#define PMAP_MAXDIST_INC 4 |
311 |
#define PMAP_MAXDIST_DEC 0.9 |
312 |
|
313 |
/* Num successful lookups before reducing in max search radius */ |
314 |
#define PMAP_MAXDIST_CNT 1000 |
315 |
|
316 |
/* Threshold below which we assume increasing max radius won't help */ |
317 |
#define PMAP_SHORT_LOOKUP_THRESH 1 |
318 |
|
319 |
/* Coefficient for adaptive maximum search radius */ |
320 |
#define PMAP_MAXDIST_COEFF 100 |
321 |
|
322 |
|
323 |
void findPhotons (PhotonMap* pmap, const RAY* ray) |
324 |
{ |
325 |
float pos [3], norm [3]; |
326 |
int redo = 0; |
327 |
|
328 |
if (!pmap -> squeue) { |
329 |
/* Lazy init priority queue */ |
330 |
pmap -> squeueSize = pmap -> maxGather + 1; |
331 |
pmap -> squeue = (PhotonSQNode*)malloc(pmap -> squeueSize * |
332 |
sizeof(PhotonSQNode)); |
333 |
if (!pmap -> squeue) |
334 |
error(USER, "can't allocate photon priority queue"); |
335 |
|
336 |
pmap -> minGathered = pmap -> maxGather; |
337 |
pmap -> maxGathered = pmap -> minGather; |
338 |
pmap -> totalGathered = 0; |
339 |
pmap -> numLookups = pmap -> numShortLookups = 0; |
340 |
pmap -> shortLookupPct = 0; |
341 |
pmap -> minError = FHUGE; |
342 |
pmap -> maxError = -FHUGE; |
343 |
pmap -> rmsError = 0; |
344 |
/* SQUARED max search radius limit is based on avg photon distance to |
345 |
* centre of gravity, unless fixed by user (maxDistFix > 0) */ |
346 |
pmap -> maxDist0 = pmap -> maxDistLimit = |
347 |
maxDistFix > 0 ? maxDistFix * maxDistFix |
348 |
: PMAP_MAXDIST_COEFF * pmap -> squeueSize * |
349 |
pmap -> CoGdist / pmap -> heapSize; |
350 |
} |
351 |
|
352 |
do { |
353 |
pmap -> squeueEnd = 0; |
354 |
pmap -> maxDist = pmap -> maxDist0; |
355 |
|
356 |
/* Search position is ray -> rorg for volume photons, since we have no |
357 |
intersection point. Normals are ignored -- these are incident |
358 |
directions). */ |
359 |
if (isVolumePmap(pmap)) { |
360 |
VCOPY(pos, ray -> rorg); |
361 |
nearestNeighbours(pmap, pos, NULL, 1); |
362 |
} |
363 |
else { |
364 |
VCOPY(pos, ray -> rop); |
365 |
VCOPY(norm, ray -> ron); |
366 |
nearestNeighbours(pmap, pos, norm, 1); |
367 |
} |
368 |
|
369 |
#ifdef PMAP_ITSYBITSY |
370 |
if (pmap -> maxDist < FTINY) { |
371 |
sprintf(errmsg, "itsy bitsy teeny weeny photon search radius %e", |
372 |
sqrt(pmap -> maxDist)); |
373 |
error(WARNING, errmsg); |
374 |
} |
375 |
#endif |
376 |
|
377 |
if (pmap -> squeueEnd < pmap -> squeueSize * pmap -> gatherTolerance) { |
378 |
/* Short lookup; too few photons found */ |
379 |
if (pmap -> squeueEnd > PMAP_SHORT_LOOKUP_THRESH) { |
380 |
/* Ignore short lookups which return fewer than |
381 |
* PMAP_SHORT_LOOKUP_THRESH photons under the assumption there |
382 |
* really are no photons in the vicinity, and increasing the max |
383 |
* search radius therefore won't help */ |
384 |
#ifdef PMAP_LOOKUP_WARN |
385 |
sprintf(errmsg, |
386 |
"%d/%d %s photons found at (%.2f,%.2f,%.2f) on %s", |
387 |
pmap -> squeueEnd, pmap -> squeueSize, |
388 |
pmapName [pmap -> type], pos [0], pos [1], pos [2], |
389 |
ray -> ro ? ray -> ro -> oname : "<null>"); |
390 |
error(WARNING, errmsg); |
391 |
#endif |
392 |
|
393 |
/* Bail out after warning if maxDist is fixed */ |
394 |
if (maxDistFix > 0) |
395 |
return; |
396 |
|
397 |
if (pmap -> maxDist0 < pmap -> maxDistLimit) { |
398 |
/* Increase max search radius if below limit & redo search */ |
399 |
pmap -> maxDist0 *= PMAP_MAXDIST_INC; |
400 |
#ifdef PMAP_LOOKUP_REDO |
401 |
redo = 1; |
402 |
#endif |
403 |
#ifdef PMAP_LOOKUP_WARN |
404 |
sprintf(errmsg, |
405 |
redo ? "restarting photon lookup with max radius %.1e" |
406 |
: "max photon lookup radius adjusted to %.1e", |
407 |
sqrt(pmap -> maxDist0)); |
408 |
error(WARNING, errmsg); |
409 |
#endif |
410 |
} |
411 |
#ifdef PMAP_LOOKUP_REDO |
412 |
else { |
413 |
sprintf(errmsg, "max photon lookup radius clamped to %.1e", |
414 |
sqrt(pmap -> maxDist0)); |
415 |
error(WARNING, errmsg); |
416 |
} |
417 |
#endif |
418 |
} |
419 |
|
420 |
/* Reset successful lookup counter */ |
421 |
pmap -> numLookups = 0; |
422 |
} |
423 |
else { |
424 |
/* Bail out after warning if maxDist is fixed */ |
425 |
if (maxDistFix > 0) |
426 |
return; |
427 |
|
428 |
/* Increment successful lookup counter and reduce max search radius if |
429 |
* wraparound */ |
430 |
pmap -> numLookups = (pmap -> numLookups + 1) % PMAP_MAXDIST_CNT; |
431 |
if (!pmap -> numLookups) |
432 |
pmap -> maxDist0 *= PMAP_MAXDIST_DEC; |
433 |
|
434 |
redo = 0; |
435 |
} |
436 |
|
437 |
} while (redo); |
438 |
} |
439 |
|
440 |
|
441 |
|
442 |
static void nearest1Neighbour (PhotonMap *pmap, const float pos [3], |
443 |
const float norm [3], Photon **photon, |
444 |
unsigned long node) |
445 |
/* Recursive part of find1Photon(..). |
446 |
Note that all heap index handling is 1-based, but accesses to the |
447 |
arrays are 0-based! */ |
448 |
{ |
449 |
Photon *p = pmap -> heap + node - 1; |
450 |
/* Signed distance to current photon's splitting plane */ |
451 |
float d = pos [photonDiscr(*p)] - p -> pos [photonDiscr(*p)], |
452 |
d2 = d * d; |
453 |
float dv [3]; |
454 |
|
455 |
/* Search subtree closer to pos first; exclude other subtree if the |
456 |
distance to the splitting plane is greater than maxDist */ |
457 |
if (d < 0) { |
458 |
if (node << 1 <= pmap -> heapSize) |
459 |
nearest1Neighbour(pmap, pos, norm, photon, node << 1); |
460 |
if (d2 < pmap -> maxDist && node << 1 < pmap -> heapSize) |
461 |
nearest1Neighbour(pmap, pos, norm, photon, (node << 1) + 1); |
462 |
} |
463 |
else { |
464 |
if (node << 1 < pmap -> heapSize) |
465 |
nearest1Neighbour(pmap, pos, norm, photon, (node << 1) + 1); |
466 |
if (d2 < pmap -> maxDist && node << 1 <= pmap -> heapSize) |
467 |
nearest1Neighbour(pmap, pos, norm, photon, node << 1); |
468 |
} |
469 |
|
470 |
/* Squared distance to current photon */ |
471 |
dv [0] = pos [0] - p -> pos [0]; |
472 |
dv [1] = pos [1] - p -> pos [1]; |
473 |
dv [2] = pos [2] - p -> pos [2]; |
474 |
d2 = DOT(dv, dv); |
475 |
|
476 |
if (d2 < pmap -> maxDist && DOT(norm, p -> norm) > 63.5 * frandom()) { |
477 |
/* Closest photon so far with similar normal. We allow a 50% tolerance |
478 |
* to account for perturbation in the latter; note the photon normal |
479 |
* is coded in the range [-127,127]. */ |
480 |
pmap -> maxDist = d2; |
481 |
*photon = p; |
482 |
} |
483 |
} |
484 |
|
485 |
|
486 |
|
487 |
Photon* find1Photon (PhotonMap *pmap, const RAY* ray) |
488 |
{ |
489 |
float fpos [3], norm [3]; |
490 |
Photon* photon = NULL; |
491 |
|
492 |
VCOPY(fpos, ray -> rop); |
493 |
VCOPY(norm, ray -> ron); |
494 |
pmap -> maxDist = thescene.cusize; |
495 |
nearest1Neighbour(pmap, fpos, norm, &photon, 1); |
496 |
|
497 |
return photon; |
498 |
} |
499 |
|
500 |
|
501 |
|
502 |
static unsigned long medianPartition (const Photon* heap, |
503 |
unsigned long* heapIdx, |
504 |
unsigned long* heapXdi, |
505 |
unsigned long left, |
506 |
unsigned long right, unsigned dim) |
507 |
/* Returns index to median in heap from indices left to right |
508 |
(inclusive) in dimension dim. The heap is partitioned relative to |
509 |
median using a quicksort algorithm. The heap indices in heapIdx are |
510 |
sorted rather than the heap itself. */ |
511 |
{ |
512 |
register const float* p; |
513 |
const unsigned long n = right - left + 1; |
514 |
register unsigned long l, r, lg2, n2, m; |
515 |
register unsigned d; |
516 |
|
517 |
/* Round down n to nearest power of 2 */ |
518 |
for (lg2 = 0, n2 = n; n2 > 1; n2 >>= 1, ++lg2); |
519 |
n2 = 1 << lg2; |
520 |
|
521 |
/* Determine median position; this takes into account the fact that |
522 |
only the last level in the heap can be partially empty, and that |
523 |
it fills from left to right */ |
524 |
m = left + ((n - n2) > (n2 >> 1) - 1 ? n2 - 1 : n - (n2 >> 1)); |
525 |
|
526 |
while (right > left) { |
527 |
/* Pivot node */ |
528 |
p = heap [heapIdx [right]].pos; |
529 |
l = left; |
530 |
r = right - 1; |
531 |
|
532 |
/* l & r converge, swapping elements out of order with respect to |
533 |
pivot node. Identical keys are resolved by cycling through |
534 |
dim. The convergence point is then the pivot's position. */ |
535 |
do { |
536 |
while (l <= r) { |
537 |
d = dim; |
538 |
|
539 |
while (heap [heapIdx [l]].pos [d] == p [d]) { |
540 |
d = (d + 1) % 3; |
541 |
|
542 |
if (d == dim) { |
543 |
/* Ignore dupes? */ |
544 |
error(WARNING, "duplicate keys in photon heap"); |
545 |
l++; |
546 |
break; |
547 |
} |
548 |
} |
549 |
|
550 |
if (heap [heapIdx [l]].pos [d] < p [d]) |
551 |
l++; |
552 |
else break; |
553 |
} |
554 |
|
555 |
while (r > l) { |
556 |
d = dim; |
557 |
|
558 |
while (heap [heapIdx [r]].pos [d] == p [d]) { |
559 |
d = (d + 1) % 3; |
560 |
|
561 |
if (d == dim) { |
562 |
/* Ignore dupes? */ |
563 |
error(WARNING, "duplicate keys in photon heap"); |
564 |
r--; |
565 |
break; |
566 |
} |
567 |
} |
568 |
|
569 |
if (heap [heapIdx [r]].pos [d] > p [d]) |
570 |
r--; |
571 |
else break; |
572 |
} |
573 |
|
574 |
/* Swap indices (not the nodes they point to) */ |
575 |
n2 = heapIdx [l]; |
576 |
heapIdx [l] = heapIdx [r]; |
577 |
heapIdx [r] = n2; |
578 |
/* Update reverse indices */ |
579 |
heapXdi [heapIdx [l]] = l; |
580 |
heapXdi [n2] = r; |
581 |
} while (l < r); |
582 |
|
583 |
/* Swap indices of convergence and pivot nodes */ |
584 |
heapIdx [r] = heapIdx [l]; |
585 |
heapIdx [l] = heapIdx [right]; |
586 |
heapIdx [right] = n2; |
587 |
/* Update reverse indices */ |
588 |
heapXdi [heapIdx [r]] = r; |
589 |
heapXdi [heapIdx [l]] = l; |
590 |
heapXdi [n2] = right; |
591 |
if (l >= m) right = l - 1; |
592 |
if (l <= m) left = l + 1; |
593 |
} |
594 |
|
595 |
/* Once left & right have converged at m, we have found the median */ |
596 |
return m; |
597 |
} |
598 |
|
599 |
|
600 |
|
601 |
void buildHeap (Photon* heap, unsigned long* heapIdx, |
602 |
unsigned long* heapXdi, const float min [3], |
603 |
const float max [3], unsigned long left, |
604 |
unsigned long right, unsigned long root) |
605 |
/* Recursive part of balancePhotons(..). Builds heap from subarray |
606 |
defined by indices left and right. min and max are the minimum resp. |
607 |
maximum photon positions in the array. root is the index of the |
608 |
current subtree's root, which corresponds to the median's 1-based |
609 |
index in the heap. heapIdx are the balanced heap indices. The heap |
610 |
is accessed indirectly through these. heapXdi are the reverse indices |
611 |
from the heap to heapIdx so that heapXdi [heapIdx [i]] = i. */ |
612 |
{ |
613 |
float maxLeft [3], minRight [3]; |
614 |
Photon rootNode; |
615 |
unsigned d; |
616 |
|
617 |
/* Choose median for dimension with largest spread and partition |
618 |
accordingly */ |
619 |
const float d0 = max [0] - min [0], |
620 |
d1 = max [1] - min [1], |
621 |
d2 = max [2] - min [2]; |
622 |
const unsigned char dim = d0 > d1 ? d0 > d2 ? 0 : 2 |
623 |
: d1 > d2 ? 1 : 2; |
624 |
const unsigned long median = |
625 |
left == right ? left |
626 |
: medianPartition(heap, heapIdx, heapXdi, left, right, dim); |
627 |
|
628 |
/* Place median at root of current subtree. This consists of swapping |
629 |
the median and the root nodes and updating the heap indices */ |
630 |
memcpy(&rootNode, heap + heapIdx [median], sizeof(Photon)); |
631 |
memcpy(heap + heapIdx [median], heap + root - 1, sizeof(Photon)); |
632 |
setPhotonDiscr(rootNode, dim); |
633 |
memcpy(heap + root - 1, &rootNode, sizeof(Photon)); |
634 |
heapIdx [heapXdi [root - 1]] = heapIdx [median]; |
635 |
heapXdi [heapIdx [median]] = heapXdi [root - 1]; |
636 |
heapIdx [median] = root - 1; |
637 |
heapXdi [root - 1] = median; |
638 |
|
639 |
/* Update bounds for left and right subtrees and recurse on them */ |
640 |
for (d = 0; d <= 2; d++) |
641 |
if (d == dim) |
642 |
maxLeft [d] = minRight [d] = rootNode.pos [d]; |
643 |
else { |
644 |
maxLeft [d] = max [d]; |
645 |
minRight [d] = min [d]; |
646 |
} |
647 |
|
648 |
if (left < median) |
649 |
buildHeap(heap, heapIdx, heapXdi, min, maxLeft, |
650 |
left, median - 1, root << 1); |
651 |
|
652 |
if (right > median) |
653 |
buildHeap(heap, heapIdx, heapXdi, minRight, max, |
654 |
median + 1, right, (root << 1) + 1); |
655 |
} |
656 |
|
657 |
|
658 |
|
659 |
void balancePhotons (PhotonMap* pmap, double *photonFlux) |
660 |
{ |
661 |
Photon *heap = pmap -> heap; |
662 |
unsigned long i; |
663 |
unsigned long *heapIdx; /* Photon index array */ |
664 |
unsigned long *heapXdi; /* Reverse index to heapIdx */ |
665 |
unsigned j; |
666 |
COLOR flux; |
667 |
/* Need doubles here to reduce errors from increment */ |
668 |
double avgFlux [3] = {0, 0, 0}, CoG [3] = {0, 0, 0}, CoGdist = 0; |
669 |
FVECT d; |
670 |
|
671 |
if (pmap -> heapEnd) { |
672 |
pmap -> heapSize = pmap -> heapEnd; |
673 |
heapIdx = (unsigned long*)malloc(pmap -> heapSize * |
674 |
sizeof(unsigned long)); |
675 |
heapXdi = (unsigned long*)malloc(pmap -> heapSize * |
676 |
sizeof(unsigned long)); |
677 |
if (!heapIdx || !heapXdi) |
678 |
error(USER, "can't allocate heap index"); |
679 |
|
680 |
for (i = 0; i < pmap -> heapSize; i++) { |
681 |
/* Initialize index arrays */ |
682 |
heapXdi [i] = heapIdx [i] = i; |
683 |
getPhotonFlux(heap + i, flux); |
684 |
|
685 |
/* Scale photon's flux (hitherto normalised to 1 over RGB); in case |
686 |
* of a contrib photon map, this is done per light source, and |
687 |
* photonFlux is assumed to be an array */ |
688 |
if (photonFlux) { |
689 |
scalecolor(flux, photonFlux [isContribPmap(pmap) ? |
690 |
photonSrcIdx(pmap, heap + i) : 0]); |
691 |
setPhotonFlux(heap + i, flux); |
692 |
} |
693 |
|
694 |
/* Need a double here */ |
695 |
addcolor(avgFlux, flux); |
696 |
|
697 |
/* Add photon position to centre of gravity */ |
698 |
for (j = 0; j < 3; j++) |
699 |
CoG [j] += heap [i].pos [j]; |
700 |
} |
701 |
|
702 |
/* Average photon positions to get centre of gravity */ |
703 |
for (j = 0; j < 3; j++) |
704 |
pmap -> CoG [j] = CoG [j] /= pmap -> heapSize; |
705 |
|
706 |
/* Compute average photon distance to CoG */ |
707 |
for (i = 0; i < pmap -> heapSize; i++) { |
708 |
VSUB(d, heap [i].pos, CoG); |
709 |
CoGdist += DOT(d, d); |
710 |
} |
711 |
|
712 |
pmap -> CoGdist = CoGdist /= pmap -> heapSize; |
713 |
|
714 |
/* Average photon flux based on RGBE representation */ |
715 |
scalecolor(avgFlux, 1.0 / pmap -> heapSize); |
716 |
copycolor(pmap -> photonFlux, avgFlux); |
717 |
|
718 |
/* Build kd-tree */ |
719 |
buildHeap(pmap -> heap, heapIdx, heapXdi, pmap -> minPos, |
720 |
pmap -> maxPos, 0, pmap -> heapSize - 1, 1); |
721 |
|
722 |
free(heapIdx); |
723 |
free(heapXdi); |
724 |
} |
725 |
} |
726 |
|
727 |
|
728 |
|
729 |
void deletePhotons (PhotonMap* pmap) |
730 |
{ |
731 |
free(pmap -> heap); |
732 |
free(pmap -> squeue); |
733 |
free(pmap -> biasCompHist); |
734 |
|
735 |
pmap -> heapSize = 0; |
736 |
pmap -> minGather = pmap -> maxGather = |
737 |
pmap -> squeueSize = pmap -> squeueEnd = 0; |
738 |
} |