| 1 |
#ifndef lint
|
| 2 |
static const char RCSid[] = "$Id$";
|
| 3 |
#endif
|
| 4 |
|
| 5 |
|
| 6 |
/*
|
| 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 |
(c) Lucerne University of Applied Sciences and Arts,
|
| 16 |
supported by the Swiss National Science Foundation (SNSF, #147053)
|
| 17 |
=======================================================================
|
| 18 |
|
| 19 |
$Id: oocbuild.c,v 2.3 2016/05/17 17:39:47 rschregle Exp $
|
| 20 |
*/
|
| 21 |
|
| 22 |
|
| 23 |
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC)
|
| 24 |
/* No Windoze support for now */
|
| 25 |
|
| 26 |
#include "oococt.h"
|
| 27 |
#include "oocsort.h"
|
| 28 |
#include <stdlib.h>
|
| 29 |
#include <string.h>
|
| 30 |
|
| 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 |
((q)->head + (q)->len-1) % (q)->cap * (q)->recSize)
|
| 38 |
|
| 39 |
|
| 40 |
|
| 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 |
} 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 |
/* Append record to queue tail; return new queue length or -1 on failure */
|
| 68 |
{
|
| 69 |
if (!q || !rec || QueueFull(q))
|
| 70 |
return -1;
|
| 71 |
|
| 72 |
++q->len;
|
| 73 |
memcpy(QueueTail(q), rec, q -> recSize);
|
| 74 |
|
| 75 |
return q -> len;
|
| 76 |
}
|
| 77 |
|
| 78 |
|
| 79 |
static int QueuePop (OOC_BuildQueue *q, void *rec)
|
| 80 |
/* Remove record from queue head and return in rec if not NULL; return new
|
| 81 |
* queue length or -1 on failure */
|
| 82 |
{
|
| 83 |
if (!q || QueueEmpty(q))
|
| 84 |
return -1;
|
| 85 |
|
| 86 |
/* Return head if rec != NULL */
|
| 87 |
if (rec)
|
| 88 |
memcpy(rec, QueueHead(q), q -> recSize);
|
| 89 |
|
| 90 |
q -> head = (q -> head + 1) % q -> cap;
|
| 91 |
|
| 92 |
return --q -> len;
|
| 93 |
}
|
| 94 |
|
| 95 |
|
| 96 |
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 |
/* Recursive part of OOC_Build(); insert records from input queue into
|
| 118 |
* octree node and subdivide into kids if necessary. Returns number of
|
| 119 |
* records in subtree or OOC_DATAIDX_ERR if failed. */
|
| 120 |
{
|
| 121 |
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 |
/* Input exhausted or queue head outside node */
|
| 130 |
return 0;
|
| 131 |
|
| 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 |
|
| 150 |
/* 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 |
}
|
| 209 |
else {
|
| 210 |
/****************************** 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 |
|
| 286 |
return OOC_DATACNT(node);
|
| 287 |
}
|
| 288 |
|
| 289 |
|
| 290 |
|
| 291 |
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 |
{
|
| 315 |
OOC_BuildQueue queue;
|
| 316 |
OOC_Node root;
|
| 317 |
|
| 318 |
if (!oct || !oct -> size) {
|
| 319 |
fputs("OOC_Build: octree not initialised", stderr);
|
| 320 |
return NULL;
|
| 321 |
}
|
| 322 |
|
| 323 |
if (!oct -> leafFile) {
|
| 324 |
fputs("OOC_Build: empty leaf file", stderr);
|
| 325 |
return NULL;
|
| 326 |
}
|
| 327 |
|
| 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 |
return NULL;
|
| 338 |
}
|
| 339 |
|
| 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 |
return NULL;
|
| 345 |
|
| 346 |
/* Finalise octree root */
|
| 347 |
if (!NewNode(oct)) {
|
| 348 |
fputs("OOC_Build: failed to allocate octree root\n", stderr);
|
| 349 |
return NULL;
|
| 350 |
}
|
| 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 |
|
| 356 |
return oct;
|
| 357 |
}
|
| 358 |
|
| 359 |
#endif /* NIX / PMAP_OOC */
|
