1 |
greg |
2.11 |
#ifndef lint |
2 |
rschregle |
2.14 |
static const char RCSid[] = "$Id: pmapdata.c,v 4.35 2016/01/20 16:05:16 taschreg Exp taschreg $"; |
3 |
greg |
2.11 |
#endif |
4 |
greg |
2.1 |
/* |
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 |
rschregle |
2.3 |
(c) Lucerne University of Applied Sciences and Arts, |
11 |
|
|
supported by the Swiss National Science Foundation (SNSF, #147053) |
12 |
greg |
2.1 |
================================================================== |
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 |
rschregle |
2.7 |
#include "random.h" |
25 |
greg |
2.1 |
|
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 |
greg |
2.5 |
FVECT dvec; |
73 |
greg |
2.1 |
|
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 |
greg |
2.5 |
dvec [0] = -ray -> rdir [0]; |
106 |
|
|
dvec [1] = -ray -> rdir [1]; |
107 |
|
|
dvec [2] = -ray -> rdir [2]; |
108 |
|
|
prim -> dir = encodedir(dvec); |
109 |
greg |
2.1 |
|
110 |
greg |
2.4 |
VCOPY(prim -> pos, ray -> rop); |
111 |
greg |
2.1 |
|
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 |
rschregle |
2.14 |
/* 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 |
greg |
2.1 |
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 |
greg |
2.6 |
srcMod = findmaterial(source [srcIdx].so); |
249 |
greg |
2.1 |
|
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 |
rschregle |
2.8 |
/* Coefficient for adaptive maximum search radius */ |
320 |
|
|
#define PMAP_MAXDIST_COEFF 100 |
321 |
|
|
|
322 |
|
|
|
323 |
greg |
2.1 |
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 |
rschregle |
2.9 |
/* SQUARED max search radius limit is based on avg photon distance to |
345 |
rschregle |
2.8 |
* centre of gravity, unless fixed by user (maxDistFix > 0) */ |
346 |
greg |
2.1 |
pmap -> maxDist0 = pmap -> maxDistLimit = |
347 |
rschregle |
2.9 |
maxDistFix > 0 ? maxDistFix * maxDistFix |
348 |
rschregle |
2.8 |
: PMAP_MAXDIST_COEFF * pmap -> squeueSize * |
349 |
|
|
pmap -> CoGdist / pmap -> heapSize; |
350 |
greg |
2.1 |
} |
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 |
rschregle |
2.3 |
|
369 |
rschregle |
2.13 |
#ifdef PMAP_ITSYBITSY |
370 |
rschregle |
2.10 |
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 |
rschregle |
2.13 |
#endif |
376 |
rschregle |
2.10 |
|
377 |
greg |
2.1 |
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 |
rschregle |
2.8 |
#ifdef PMAP_LOOKUP_WARN |
385 |
greg |
2.1 |
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 |
rschregle |
2.8 |
#endif |
392 |
rschregle |
2.3 |
|
393 |
rschregle |
2.8 |
/* Bail out after warning if maxDist is fixed */ |
394 |
|
|
if (maxDistFix > 0) |
395 |
|
|
return; |
396 |
|
|
|
397 |
greg |
2.1 |
if (pmap -> maxDist0 < pmap -> maxDistLimit) { |
398 |
|
|
/* Increase max search radius if below limit & redo search */ |
399 |
|
|
pmap -> maxDist0 *= PMAP_MAXDIST_INC; |
400 |
rschregle |
2.8 |
#ifdef PMAP_LOOKUP_REDO |
401 |
greg |
2.1 |
redo = 1; |
402 |
rschregle |
2.8 |
#endif |
403 |
|
|
#ifdef PMAP_LOOKUP_WARN |
404 |
greg |
2.1 |
sprintf(errmsg, |
405 |
|
|
redo ? "restarting photon lookup with max radius %.1e" |
406 |
|
|
: "max photon lookup radius adjusted to %.1e", |
407 |
rschregle |
2.10 |
sqrt(pmap -> maxDist0)); |
408 |
greg |
2.1 |
error(WARNING, errmsg); |
409 |
rschregle |
2.8 |
#endif |
410 |
greg |
2.1 |
} |
411 |
rschregle |
2.8 |
#ifdef PMAP_LOOKUP_REDO |
412 |
greg |
2.1 |
else { |
413 |
|
|
sprintf(errmsg, "max photon lookup radius clamped to %.1e", |
414 |
rschregle |
2.10 |
sqrt(pmap -> maxDist0)); |
415 |
greg |
2.1 |
error(WARNING, errmsg); |
416 |
|
|
} |
417 |
rschregle |
2.8 |
#endif |
418 |
greg |
2.1 |
} |
419 |
|
|
|
420 |
|
|
/* Reset successful lookup counter */ |
421 |
|
|
pmap -> numLookups = 0; |
422 |
rschregle |
2.3 |
} |
423 |
greg |
2.1 |
else { |
424 |
rschregle |
2.8 |
/* Bail out after warning if maxDist is fixed */ |
425 |
|
|
if (maxDistFix > 0) |
426 |
|
|
return; |
427 |
|
|
|
428 |
greg |
2.1 |
/* 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 |
rschregle |
2.8 |
|
437 |
greg |
2.1 |
} 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 |
rschregle |
2.14 |
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 |
greg |
2.1 |
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 |
|
|
} |