1 |
rschregle |
2.4 |
#ifndef lint |
2 |
|
|
static const char RCSid[] = "$Id$"; |
3 |
|
|
#endif |
4 |
|
|
|
5 |
|
|
|
6 |
greg |
2.1 |
/* |
7 |
|
|
======================================================================= |
8 |
|
|
Routines for building out-of-core octree data structure |
9 |
|
|
|
10 |
|
|
Adapted from: Kontkanen J., Tabellion E. and Overbeck R.S., |
11 |
|
|
"Coherent Out-of-Core Point-Based Global Illumination", |
12 |
|
|
EGSR 2011. |
13 |
|
|
|
14 |
|
|
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
15 |
rschregle |
2.3 |
(c) Lucerne University of Applied Sciences and Arts, |
16 |
rschregle |
2.4 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
17 |
greg |
2.1 |
======================================================================= |
18 |
|
|
|
19 |
rschregle |
2.4 |
$Id: oocbuild.c,v 2.3 2016/05/17 17:39:47 rschregle Exp $ |
20 |
greg |
2.1 |
*/ |
21 |
|
|
|
22 |
|
|
|
23 |
rschregle |
2.4 |
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC) |
24 |
|
|
/* No Windoze support for now */ |
25 |
|
|
|
26 |
greg |
2.1 |
#include "oococt.h" |
27 |
|
|
#include "oocsort.h" |
28 |
rschregle |
2.3 |
#include <stdlib.h> |
29 |
|
|
#include <string.h> |
30 |
greg |
2.1 |
|
31 |
|
|
|
32 |
|
|
/* Test for empty/full input queue, return pointer to head/tail */ |
33 |
|
|
#define QueueFull(q) ((q) -> len == (q) -> cap) |
34 |
|
|
#define QueueEmpty(q) (!(q) -> len) |
35 |
|
|
#define QueueHead(q) ((q) -> data + (q) -> head * (q) -> recSize) |
36 |
|
|
#define QueueTail(q) ((q) -> data + \ |
37 |
rschregle |
2.3 |
((q)->head + (q)->len-1) % (q)->cap * (q)->recSize) |
38 |
greg |
2.1 |
|
39 |
|
|
|
40 |
rschregle |
2.3 |
|
41 |
|
|
/* Input queue for bottom-up octree construction */ |
42 |
|
|
typedef struct { |
43 |
|
|
void *data; |
44 |
|
|
unsigned head, len, cap, recSize; /* Queue head, length (from head), |
45 |
|
|
capacity and record size */ |
46 |
|
|
FILE *in; /* Input file for data records */ |
47 |
greg |
2.1 |
} OOC_BuildQueue; |
48 |
|
|
|
49 |
|
|
|
50 |
|
|
static OOC_BuildQueue *QueueInit (OOC_BuildQueue *q, unsigned recSize, |
51 |
|
|
unsigned capacity) |
52 |
|
|
/* Initialise queue of #capacity records of size recSize each; returns queue |
53 |
|
|
* pointer or NULL if failed. */ |
54 |
|
|
{ |
55 |
|
|
if (!(q && (q -> data = calloc(capacity, recSize)))) |
56 |
|
|
return NULL; |
57 |
|
|
|
58 |
|
|
q -> cap = capacity; |
59 |
|
|
q -> recSize = recSize; |
60 |
|
|
q -> head = q -> len = 0; |
61 |
|
|
|
62 |
|
|
return q; |
63 |
|
|
} |
64 |
|
|
|
65 |
|
|
|
66 |
|
|
static int QueuePush (OOC_BuildQueue *q, const void *rec) |
67 |
rschregle |
2.3 |
/* Append record to queue tail; return new queue length or -1 on failure */ |
68 |
greg |
2.1 |
{ |
69 |
rschregle |
2.3 |
if (!q || !rec || QueueFull(q)) |
70 |
greg |
2.1 |
return -1; |
71 |
|
|
|
72 |
rschregle |
2.3 |
++q->len; |
73 |
|
|
memcpy(QueueTail(q), rec, q -> recSize); |
74 |
|
|
|
75 |
greg |
2.1 |
return q -> len; |
76 |
|
|
} |
77 |
|
|
|
78 |
|
|
|
79 |
|
|
static int QueuePop (OOC_BuildQueue *q, void *rec) |
80 |
rschregle |
2.3 |
/* Remove record from queue head and return in rec if not NULL; return new |
81 |
|
|
* queue length or -1 on failure */ |
82 |
greg |
2.1 |
{ |
83 |
rschregle |
2.3 |
if (!q || QueueEmpty(q)) |
84 |
greg |
2.1 |
return -1; |
85 |
|
|
|
86 |
rschregle |
2.3 |
/* Return head if rec != NULL */ |
87 |
|
|
if (rec) |
88 |
|
|
memcpy(rec, QueueHead(q), q -> recSize); |
89 |
greg |
2.1 |
|
90 |
|
|
q -> head = (q -> head + 1) % q -> cap; |
91 |
|
|
|
92 |
|
|
return --q -> len; |
93 |
|
|
} |
94 |
|
|
|
95 |
|
|
|
96 |
rschregle |
2.3 |
static int QueueFill (OOC_BuildQueue *q) |
97 |
|
|
/* Read records from q -> in until the queue is full; return queue |
98 |
|
|
* length or -1 on failure */ |
99 |
|
|
{ |
100 |
|
|
static void *rec = NULL; |
101 |
|
|
|
102 |
|
|
if (!rec && !(rec = malloc(q -> recSize))) |
103 |
|
|
return -1; |
104 |
|
|
|
105 |
|
|
while (!QueueFull(q) && !feof(q -> in) && |
106 |
|
|
fread(rec, q -> recSize, 1, q -> in)) |
107 |
|
|
QueuePush(q, rec); |
108 |
|
|
|
109 |
|
|
return q -> len; |
110 |
|
|
} |
111 |
|
|
|
112 |
|
|
|
113 |
|
|
|
114 |
|
|
static OOC_DataIdx OOC_BuildRecurse (OOC_Octree *oct, OOC_Node* node, |
115 |
|
|
FVECT org, RREAL size, unsigned depth, |
116 |
|
|
OOC_BuildQueue *queue) |
117 |
greg |
2.1 |
/* Recursive part of OOC_Build(); insert records from input queue into |
118 |
rschregle |
2.3 |
* octree node and subdivide into kids if necessary. Returns number of |
119 |
|
|
* records in subtree or OOC_DATAIDX_ERR if failed. */ |
120 |
greg |
2.1 |
{ |
121 |
rschregle |
2.3 |
int k; |
122 |
|
|
const RREAL kidSize = size * 0.5; |
123 |
|
|
|
124 |
|
|
if (!oct || !node) |
125 |
|
|
return OOC_DATAIDX_ERR; |
126 |
|
|
|
127 |
|
|
if (QueueEmpty(queue) || |
128 |
|
|
!OOC_InBBox(oct, org, size, oct -> key(QueueHead(queue)))) |
129 |
greg |
2.1 |
/* Input exhausted or queue head outside node */ |
130 |
|
|
return 0; |
131 |
rschregle |
2.3 |
|
132 |
|
|
if (QueueFull(queue) && depth < oct -> maxDepth && |
133 |
|
|
OOC_InBBox(oct, org, size, oct -> key(QueueTail(queue)))) { |
134 |
|
|
/*************************** SUBDIVIDE NODE ************************* |
135 |
|
|
* At least leafMax + 1 records (since the queue is full) lie inside |
136 |
|
|
* the current node's bounding box, and maxDepth has not been reached |
137 |
|
|
* ==> subdivide this node. |
138 |
|
|
* (Note it suffices to only test the queue tail against the bounding |
139 |
|
|
* box, as the records are in Z-order) |
140 |
|
|
********************************************************************/ |
141 |
|
|
OOC_Node kid [8]; |
142 |
|
|
OOC_DataIdx dataCnt; |
143 |
|
|
FVECT kidOrg; |
144 |
|
|
|
145 |
|
|
#ifdef DEBUG_OOC_BUILD |
146 |
|
|
FVECT key; |
147 |
|
|
unsigned k2 = 0; |
148 |
|
|
#endif |
149 |
greg |
2.1 |
|
150 |
rschregle |
2.3 |
/* We recurse on the nonempty kids first, then finalise their nodes so |
151 |
|
|
* they are ordered consecutively, since the parent only indexes the 1st kid */ |
152 |
|
|
for (k = 0; k < 8; k++) { |
153 |
|
|
/* Clear kid node and get its octant origin */ |
154 |
|
|
OOC_CLEARNODE(kid + k); |
155 |
|
|
|
156 |
|
|
VCOPY(kidOrg, org); |
157 |
|
|
OOC_OCTORIGIN(kidOrg, k, kidSize); |
158 |
|
|
|
159 |
|
|
/* Recurse on kid and check for early bailout */ |
160 |
|
|
if (OOC_BuildRecurse(oct, kid + k, kidOrg, kidSize, |
161 |
|
|
depth + 1, queue) == OOC_DATAIDX_ERR) |
162 |
|
|
return OOC_DATAIDX_ERR; |
163 |
|
|
|
164 |
|
|
#ifdef DEBUG_OOC_BUILD |
165 |
|
|
if (!QueueEmpty(queue)) { |
166 |
|
|
VCOPY(key, oct -> key(QueueHead(queue))); |
167 |
|
|
k2 = OOC_Branch(oct, org, kidSize, key, NULL); |
168 |
|
|
if (OOC_InBBox(oct, org, size, key) && k2 < k) { |
169 |
|
|
fprintf(stderr, |
170 |
|
|
"OOC_BuildRecurse, node subdiv: unsorted key [%f, %f, %f] with " |
171 |
|
|
"octant %d (last %d with bbox [%f-%f, %f-%f, %f-%f])\n", |
172 |
|
|
key [0], key [1], key [2], k2, k, |
173 |
|
|
kidOrg [0], kidOrg [0] + kidSize, kidOrg [1], kidOrg [1] + kidSize, |
174 |
|
|
kidOrg [2], kidOrg [2] + kidSize); |
175 |
|
|
}} |
176 |
|
|
#endif |
177 |
|
|
} |
178 |
|
|
|
179 |
|
|
/* Now finalise consecutive kid nodes, skipping empty ones */ |
180 |
|
|
for (k = 0; k < 8; k++) |
181 |
|
|
if ((dataCnt = OOC_DATACNT(kid + k))) { |
182 |
|
|
/* Nonzero kid ==> allocate and set node */ |
183 |
|
|
if (!NewNode(oct)) { |
184 |
|
|
fputs("OOC_BuildRecurse: failed to allocate new node\n", |
185 |
|
|
stderr); |
186 |
|
|
return OOC_DATAIDX_ERR; |
187 |
|
|
} |
188 |
|
|
OOC_SETROOT(oct, kid + k); |
189 |
|
|
|
190 |
|
|
/* Sum kid's data count to parent's and check for overflow */ |
191 |
|
|
if ((dataCnt += node -> node.num) <= OOC_DATAIDX_MAX) |
192 |
|
|
node -> node.num = dataCnt; |
193 |
|
|
else { |
194 |
|
|
fputs("OOC_BuildRecurse: data count overflow in node\n", |
195 |
|
|
stderr); |
196 |
|
|
return OOC_DATAIDX_ERR; |
197 |
|
|
} |
198 |
|
|
|
199 |
|
|
/* Set kid index in parent (if first kid) and corresponding |
200 |
|
|
* branch bit. The kid is the most recent node and thus at the |
201 |
|
|
* end of the node array, which coincides with the current |
202 |
|
|
* subtree root */ |
203 |
|
|
if (!node -> node.branch) |
204 |
|
|
node -> node.kid = OOC_ROOTIDX(oct); |
205 |
|
|
|
206 |
|
|
OOC_SETBRANCH(node, k); |
207 |
|
|
} |
208 |
greg |
2.1 |
} |
209 |
|
|
else { |
210 |
rschregle |
2.3 |
/****************************** MAKE LEAF **************************** |
211 |
|
|
* Queue contains no more than leafMax records, queue tail lies |
212 |
|
|
* outside node's bounding box, or maxDepth reached |
213 |
|
|
* ==> make this node a leaf. |
214 |
|
|
*********************************************************************/ |
215 |
|
|
RREAL *key; |
216 |
|
|
|
217 |
|
|
#ifdef DEBUG_OOC_BUILD |
218 |
|
|
OOC_MortonIdx zIdx, lastzIdx = 0; |
219 |
|
|
FVECT /* key, */ |
220 |
|
|
lastKey, kidOrg; |
221 |
|
|
unsigned lastk = 0; |
222 |
|
|
#endif |
223 |
|
|
|
224 |
|
|
/* Mark as leaf (note it's been cleared by the parent call) */ |
225 |
|
|
OOC_SETLEAF(node); |
226 |
|
|
|
227 |
|
|
while (!QueueEmpty(queue) && |
228 |
|
|
OOC_InBBox(oct, org, size, (key = oct->key(QueueHead(queue))))) { |
229 |
|
|
/* Record lies inside leaf; increment data counter for octant |
230 |
|
|
* containing record. */ |
231 |
|
|
|
232 |
|
|
if ((k = OOC_Branch(oct, org, kidSize, key, NULL)) < 0) { |
233 |
|
|
/* Shouldn't happen, as key tested within bbox above */ |
234 |
|
|
fprintf(stderr, "OOC_BuildRecurse: buggered Morton code, " |
235 |
|
|
"disruption in space-time continuum?\n"); |
236 |
|
|
return OOC_DATAIDX_ERR; |
237 |
|
|
} |
238 |
|
|
|
239 |
|
|
if (node -> leaf.num [k] == OOC_OCTCNT_MAX) { |
240 |
|
|
/* Currently we're buggered here; merge records instead? */ |
241 |
|
|
fprintf(stderr, "OOC_BuildRecurse: data count overflow in " |
242 |
|
|
"leaf: depth = %d, count = %d\n", |
243 |
|
|
depth, node -> leaf.num [k]); |
244 |
|
|
return OOC_DATAIDX_ERR; |
245 |
|
|
} |
246 |
|
|
|
247 |
|
|
++node -> leaf.num [k]; |
248 |
|
|
|
249 |
|
|
#ifdef DEBUG_OOC_BUILD |
250 |
|
|
/* VCOPY(key, oct -> key(QueueHead(queue))); */ |
251 |
|
|
if ((zIdx = OOC_KEY2MORTON(key, oct)) < lastzIdx) { |
252 |
|
|
fprintf(stderr, "OOC_BuildRecurse, make leaf: unsorted zIdx %020ld for " |
253 |
|
|
"key [%f, %f, %f] (previous zIdx %020ld for " |
254 |
|
|
"key [%f, %f, %f]\n", zIdx, key [0], key [1], key [2], |
255 |
|
|
lastzIdx, lastKey [0], lastKey [1], lastKey [2]); |
256 |
|
|
} |
257 |
|
|
|
258 |
|
|
VCOPY(kidOrg, org); |
259 |
|
|
OOC_OCTORIGIN(kidOrg, k, kidSize); |
260 |
|
|
if (k < lastk || zIdx < lastzIdx) { |
261 |
|
|
fprintf(stderr, |
262 |
|
|
"OOC_BuildRecurse, make leaf: unsorted octant %d (last %d) with " |
263 |
|
|
"bbox [%f-%f, %f-%f, %f-%f] for key [%f, %f, %f] with zIdx %020ld " |
264 |
|
|
"(last [%f, %f, %f], zIdx %020ld)\n", |
265 |
|
|
k, lastk, kidOrg [0], kidOrg [0] + kidSize, |
266 |
|
|
kidOrg [1], kidOrg [1] + kidSize, kidOrg [2], kidOrg [2] + kidSize, |
267 |
|
|
key [0], key [1], key [2], zIdx, |
268 |
|
|
lastKey [0], lastKey [1], lastKey [2], lastzIdx); |
269 |
|
|
} |
270 |
|
|
lastk = k; |
271 |
|
|
lastzIdx = zIdx; |
272 |
|
|
VCOPY(lastKey, key); |
273 |
|
|
#endif |
274 |
|
|
|
275 |
|
|
/* Remove record from queue */ |
276 |
|
|
QueuePop(queue, NULL); |
277 |
|
|
} |
278 |
|
|
|
279 |
|
|
/* Refill queue for next node(s) */ |
280 |
|
|
if (QueueFill(queue) < 0) { |
281 |
|
|
fputs("OOC_Build: failed input queue fill\n", stderr); |
282 |
|
|
return OOC_DATAIDX_ERR; |
283 |
|
|
} |
284 |
|
|
} |
285 |
greg |
2.1 |
|
286 |
rschregle |
2.3 |
return OOC_DATACNT(node); |
287 |
greg |
2.1 |
} |
288 |
rschregle |
2.3 |
|
289 |
greg |
2.1 |
|
290 |
|
|
|
291 |
rschregle |
2.3 |
OOC_Octree *OOC_Build (OOC_Octree *oct, unsigned leafMax, unsigned maxDepth) |
292 |
|
|
/* Bottom-up construction of out-of-core octree in postorder traversal. The |
293 |
|
|
* octree oct is assumed to be initialised with its origin (oct -> org), |
294 |
|
|
* size (oct -> size), key callback (oct -> key), and its associated leaf |
295 |
|
|
* file (oct -> leafFile). |
296 |
|
|
|
297 |
|
|
* Records are read from the leafFile and assumed to be sorted in Z-order, |
298 |
|
|
* which defines an octree leaf ordering. Leaves (terminal nodes) are |
299 |
|
|
* constructed such that they contain <= leafMax records and have a maximum |
300 |
|
|
* depth of maxDepth. |
301 |
|
|
|
302 |
|
|
* Note that the following limits apply: |
303 |
|
|
* leafMax <= OOC_OCTCNT_MAX (see oococt.h) |
304 |
|
|
* maxDepth <= OOC_MORTON_BITS (see oocsort.h) |
305 |
|
|
|
306 |
|
|
* The maxDepth limit arises from the fact that the Z-ordering has a limited |
307 |
|
|
* resolution and will map node coordinates beyond a depth of |
308 |
|
|
* OOC_MORTON_BITS to the same Z-index, causing nodes to be potentially read |
309 |
|
|
* out of sequence and winding up in the wrong octree nodes. |
310 |
|
|
|
311 |
|
|
* On success, the octree pointer oct is returned, with the constructed |
312 |
|
|
* nodes in oct -> nodes, and the node count in oct -> numNodes. On |
313 |
|
|
* failure, NULL is returned. */ |
314 |
greg |
2.1 |
{ |
315 |
|
|
OOC_BuildQueue queue; |
316 |
rschregle |
2.3 |
OOC_Node root; |
317 |
greg |
2.1 |
|
318 |
rschregle |
2.3 |
if (!oct || !oct -> size) { |
319 |
|
|
fputs("OOC_Build: octree not initialised", stderr); |
320 |
greg |
2.1 |
return NULL; |
321 |
|
|
} |
322 |
rschregle |
2.3 |
|
323 |
|
|
if (!oct -> leafFile) { |
324 |
|
|
fputs("OOC_Build: empty leaf file", stderr); |
325 |
greg |
2.1 |
return NULL; |
326 |
|
|
} |
327 |
rschregle |
2.3 |
|
328 |
|
|
oct -> leafMax = leafMax; |
329 |
|
|
oct -> maxDepth = maxDepth; |
330 |
|
|
queue.in = oct -> leafFile; |
331 |
|
|
rewind(queue.in); |
332 |
|
|
|
333 |
|
|
/* Init queue and fill from leaf file */ |
334 |
|
|
if (!QueueInit(&queue, oct -> recSize, leafMax + 1) || |
335 |
|
|
QueueFill(&queue) < 0) { |
336 |
|
|
fputs("OOC_Build: failed input queue init\n", stderr); |
337 |
greg |
2.1 |
return NULL; |
338 |
|
|
} |
339 |
rschregle |
2.3 |
|
340 |
|
|
/* Clear octree root and recurse */ |
341 |
|
|
OOC_CLEARNODE(&root); |
342 |
|
|
if (OOC_BuildRecurse(oct, &root, oct -> org, oct -> size, 0, &queue) == |
343 |
|
|
OOC_DATAIDX_ERR) |
344 |
greg |
2.1 |
return NULL; |
345 |
rschregle |
2.3 |
|
346 |
|
|
/* Finalise octree root */ |
347 |
|
|
if (!NewNode(oct)) { |
348 |
|
|
fputs("OOC_Build: failed to allocate octree root\n", stderr); |
349 |
greg |
2.1 |
return NULL; |
350 |
rschregle |
2.3 |
} |
351 |
|
|
OOC_SETROOT(oct, &root); |
352 |
|
|
/* Passing OOC_ROOT(oct) avoids annoying compiler warnings about (&root) |
353 |
|
|
* always evaluating to true when calling OOC_DATAIDX() */ |
354 |
|
|
oct -> numData = OOC_DATACNT(OOC_ROOT(oct)); |
355 |
greg |
2.1 |
|
356 |
|
|
return oct; |
357 |
|
|
} |
358 |
rschregle |
2.4 |
|
359 |
|
|
#endif /* NIX / PMAP_OOC */ |