src/rt/oocbuild.c

#ifndef lint
static const char RCSid[] = "$Id$";
#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.3 2016/05/17 17:39:47 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 */
Revision:	2.4
Committed:	Mon Aug 14 21:12:10 2017 UTC (8 years, 2 months ago) by rschregle
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad5R3, rad5R1, rad6R0, HEAD
Changes since 2.3:	+12 -2 lines
Log Message:	Updated photon map code for Windows; no multproc or ooC for now
#	User	Rev	Content
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 */