src/rt/oocbuild.c

/* 
   =======================================================================
   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 1.23 2015/09/15 13:32:13 taschreg Exp taschreg $
*/


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