Page MenuHomec4science
Files F59166009

oocbuild.c
No OneTemporary
Actions

File Metadata

Created
Sat, Apr 20, 06:27

oocbuild.c
View Options

#ifndef lint
static const char RCSid[] = "$Id: oocbuild.c,v 2.4 2017/08/14 21:12:10 rschregle Exp $";
#endif
/*
=======================================================================
Routines for building out-of-core octree data structure
Adapted from: Kontkanen J., Tabellion E. and Overbeck R.S.,
"Coherent Out-of-Core Point-Based Global Illumination",
EGSR 2011.
Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
(c) Lucerne University of Applied Sciences and Arts,
supported by the Swiss National Science Foundation (SNSF, #147053)
=======================================================================
$Id: oocbuild.c,v 2.4 2017/08/14 21:12:10 rschregle Exp $
*/
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC)
/* No Windoze support for now */
#include "oococt.h"
#include "oocsort.h"
#include <stdlib.h>
#include <string.h>
/* Test for empty/full input queue, return pointer to head/tail */
#define QueueFull(q) ((q) -> len == (q) -> cap)
#define QueueEmpty(q) (!(q) -> len)
#define QueueHead(q) ((q) -> data + (q) -> head * (q) -> recSize)
#define QueueTail(q) ((q) -> data + \
((q)->head + (q)->len-1) % (q)->cap * (q)->recSize)
/* Input queue for bottom-up octree construction */
typedef struct {
void *data;
unsigned head, len, cap, recSize; /* Queue head, length (from head),
capacity and record size */
FILE *in; /* Input file for data records */
} OOC_BuildQueue;
static OOC_BuildQueue *QueueInit (OOC_BuildQueue *q, unsigned recSize,
unsigned capacity)
/* Initialise queue of #capacity records of size recSize each; returns queue
* pointer or NULL if failed. */
{
if (!(q && (q -> data = calloc(capacity, recSize))))
return NULL;
q -> cap = capacity;
q -> recSize = recSize;
q -> head = q -> len = 0;
return q;
}
static int QueuePush (OOC_BuildQueue *q, const void *rec)
/* Append record to queue tail; return new queue length or -1 on failure */
{
if (!q || !rec || QueueFull(q))
return -1;
++q->len;
memcpy(QueueTail(q), rec, q -> recSize);
return q -> len;
}
static int QueuePop (OOC_BuildQueue *q, void *rec)
/* Remove record from queue head and return in rec if not NULL; return new
* queue length or -1 on failure */
{
if (!q || QueueEmpty(q))
return -1;
/* Return head if rec != NULL */
if (rec)
memcpy(rec, QueueHead(q), q -> recSize);
q -> head = (q -> head + 1) % q -> cap;
return --q -> len;
}
static int QueueFill (OOC_BuildQueue *q)
/* Read records from q -> in until the queue is full; return queue
* length or -1 on failure */
{
static void *rec = NULL;
if (!rec && !(rec = malloc(q -> recSize)))
return -1;
while (!QueueFull(q) && !feof(q -> in) &&
fread(rec, q -> recSize, 1, q -> in))
QueuePush(q, rec);
return q -> len;
}
static OOC_DataIdx OOC_BuildRecurse (OOC_Octree *oct, OOC_Node* node,
FVECT org, RREAL size, unsigned depth,
OOC_BuildQueue *queue)
/* Recursive part of OOC_Build(); insert records from input queue into
* octree node and subdivide into kids if necessary. Returns number of
* records in subtree or OOC_DATAIDX_ERR if failed. */
{
int k;
const RREAL kidSize = size * 0.5;
if (!oct || !node)
return OOC_DATAIDX_ERR;
if (QueueEmpty(queue) ||
!OOC_InBBox(oct, org, size, oct -> key(QueueHead(queue))))
/* Input exhausted or queue head outside node */
return 0;
if (QueueFull(queue) && depth < oct -> maxDepth &&
OOC_InBBox(oct, org, size, oct -> key(QueueTail(queue)))) {
/*************************** SUBDIVIDE NODE *************************
* At least leafMax + 1 records (since the queue is full) lie inside
* the current node's bounding box, and maxDepth has not been reached
* ==> subdivide this node.
* (Note it suffices to only test the queue tail against the bounding
* box, as the records are in Z-order)
********************************************************************/
OOC_Node kid [8];
OOC_DataIdx dataCnt;
FVECT kidOrg;
#ifdef DEBUG_OOC_BUILD
FVECT key;
unsigned k2 = 0;
#endif
/* We recurse on the nonempty kids first, then finalise their nodes so
* they are ordered consecutively, since the parent only indexes the 1st kid */
for (k = 0; k < 8; k++) {
/* Clear kid node and get its octant origin */
OOC_CLEARNODE(kid + k);
VCOPY(kidOrg, org);
OOC_OCTORIGIN(kidOrg, k, kidSize);
/* Recurse on kid and check for early bailout */
if (OOC_BuildRecurse(oct, kid + k, kidOrg, kidSize,
depth + 1, queue) == OOC_DATAIDX_ERR)
return OOC_DATAIDX_ERR;
#ifdef DEBUG_OOC_BUILD
if (!QueueEmpty(queue)) {
VCOPY(key, oct -> key(QueueHead(queue)));
k2 = OOC_Branch(oct, org, kidSize, key, NULL);
if (OOC_InBBox(oct, org, size, key) && k2 < k) {
fprintf(stderr,
"OOC_BuildRecurse, node subdiv: unsorted key [%f, %f, %f] with "
"octant %d (last %d with bbox [%f-%f, %f-%f, %f-%f])\n",
key [0], key [1], key [2], k2, k,
kidOrg [0], kidOrg [0] + kidSize, kidOrg [1], kidOrg [1] + kidSize,
kidOrg [2], kidOrg [2] + kidSize);
}}
#endif
}
/* Now finalise consecutive kid nodes, skipping empty ones */
for (k = 0; k < 8; k++)
if ((dataCnt = OOC_DATACNT(kid + k))) {
/* Nonzero kid ==> allocate and set node */
if (!NewNode(oct)) {
fputs("OOC_BuildRecurse: failed to allocate new node\n",
stderr);
return OOC_DATAIDX_ERR;
}
OOC_SETROOT(oct, kid + k);
/* Sum kid's data count to parent's and check for overflow */
if ((dataCnt += node -> node.num) <= OOC_DATAIDX_MAX)
node -> node.num = dataCnt;
else {
fputs("OOC_BuildRecurse: data count overflow in node\n",
stderr);
return OOC_DATAIDX_ERR;
}
/* Set kid index in parent (if first kid) and corresponding
* branch bit. The kid is the most recent node and thus at the
* end of the node array, which coincides with the current
* subtree root */
if (!node -> node.branch)
node -> node.kid = OOC_ROOTIDX(oct);
OOC_SETBRANCH(node, k);
}
}
else {
/****************************** MAKE LEAF ****************************
* Queue contains no more than leafMax records, queue tail lies
* outside node's bounding box, or maxDepth reached
* ==> make this node a leaf.
*********************************************************************/
RREAL *key;
#ifdef DEBUG_OOC_BUILD
OOC_MortonIdx zIdx, lastzIdx = 0;
FVECT /* key, */
lastKey, kidOrg;
unsigned lastk = 0;
#endif
/* Mark as leaf (note it's been cleared by the parent call) */
OOC_SETLEAF(node);
while (!QueueEmpty(queue) &&
OOC_InBBox(oct, org, size, (key = oct->key(QueueHead(queue))))) {
/* Record lies inside leaf; increment data counter for octant
* containing record. */
if ((k = OOC_Branch(oct, org, kidSize, key, NULL)) < 0) {
/* Shouldn't happen, as key tested within bbox above */
fprintf(stderr, "OOC_BuildRecurse: buggered Morton code, "
"disruption in space-time continuum?\n");
return OOC_DATAIDX_ERR;
}
if (node -> leaf.num [k] == OOC_OCTCNT_MAX) {
/* Currently we're buggered here; merge records instead? */
fprintf(stderr, "OOC_BuildRecurse: data count overflow in "
"leaf: depth = %d, count = %d\n",
depth, node -> leaf.num [k]);
return OOC_DATAIDX_ERR;
}
++node -> leaf.num [k];
#ifdef DEBUG_OOC_BUILD
/* VCOPY(key, oct -> key(QueueHead(queue))); */
if ((zIdx = OOC_KEY2MORTON(key, oct)) < lastzIdx) {
fprintf(stderr, "OOC_BuildRecurse, make leaf: unsorted zIdx %020ld for "
"key [%f, %f, %f] (previous zIdx %020ld for "
"key [%f, %f, %f]\n", zIdx, key [0], key [1], key [2],
lastzIdx, lastKey [0], lastKey [1], lastKey [2]);
}
VCOPY(kidOrg, org);
OOC_OCTORIGIN(kidOrg, k, kidSize);
if (k < lastk || zIdx < lastzIdx) {
fprintf(stderr,
"OOC_BuildRecurse, make leaf: unsorted octant %d (last %d) with "
"bbox [%f-%f, %f-%f, %f-%f] for key [%f, %f, %f] with zIdx %020ld "
"(last [%f, %f, %f], zIdx %020ld)\n",
k, lastk, kidOrg [0], kidOrg [0] + kidSize,
kidOrg [1], kidOrg [1] + kidSize, kidOrg [2], kidOrg [2] + kidSize,
key [0], key [1], key [2], zIdx,
lastKey [0], lastKey [1], lastKey [2], lastzIdx);
}
lastk = k;
lastzIdx = zIdx;
VCOPY(lastKey, key);
#endif
/* Remove record from queue */
QueuePop(queue, NULL);
}
/* Refill queue for next node(s) */
if (QueueFill(queue) < 0) {
fputs("OOC_Build: failed input queue fill\n", stderr);
return OOC_DATAIDX_ERR;
}
}
return OOC_DATACNT(node);
}
OOC_Octree *OOC_Build (OOC_Octree *oct, unsigned leafMax, unsigned maxDepth)
/* Bottom-up construction of out-of-core octree in postorder traversal. The
* octree oct is assumed to be initialised with its origin (oct -> org),
* size (oct -> size), key callback (oct -> key), and its associated leaf
* file (oct -> leafFile).
* Records are read from the leafFile and assumed to be sorted in Z-order,
* which defines an octree leaf ordering. Leaves (terminal nodes) are
* constructed such that they contain <= leafMax records and have a maximum
* depth of maxDepth.
* Note that the following limits apply:
* leafMax <= OOC_OCTCNT_MAX (see oococt.h)
* maxDepth <= OOC_MORTON_BITS (see oocsort.h)
* The maxDepth limit arises from the fact that the Z-ordering has a limited
* resolution and will map node coordinates beyond a depth of
* OOC_MORTON_BITS to the same Z-index, causing nodes to be potentially read
* out of sequence and winding up in the wrong octree nodes.
* On success, the octree pointer oct is returned, with the constructed
* nodes in oct -> nodes, and the node count in oct -> numNodes. On
* failure, NULL is returned. */
{
OOC_BuildQueue queue;
OOC_Node root;
if (!oct || !oct -> size) {
fputs("OOC_Build: octree not initialised", stderr);
return NULL;
}
if (!oct -> leafFile) {
fputs("OOC_Build: empty leaf file", stderr);
return NULL;
}
oct -> leafMax = leafMax;
oct -> maxDepth = maxDepth;
queue.in = oct -> leafFile;
rewind(queue.in);
/* Init queue and fill from leaf file */
if (!QueueInit(&queue, oct -> recSize, leafMax + 1) ||
QueueFill(&queue) < 0) {
fputs("OOC_Build: failed input queue init\n", stderr);
return NULL;
}
/* Clear octree root and recurse */
OOC_CLEARNODE(&root);
if (OOC_BuildRecurse(oct, &root, oct -> org, oct -> size, 0, &queue) ==
OOC_DATAIDX_ERR)
return NULL;
/* Finalise octree root */
if (!NewNode(oct)) {
fputs("OOC_Build: failed to allocate octree root\n", stderr);
return NULL;
}
OOC_SETROOT(oct, &root);
/* Passing OOC_ROOT(oct) avoids annoying compiler warnings about (&root)
* always evaluating to true when calling OOC_DATAIDX() */
oct -> numData = OOC_DATACNT(OOC_ROOT(oct));
return oct;
}
#endif /* NIX / PMAP_OOC */

Event Timeline

c4science · Help