src/rt/oococt.c

/* 
   ======================================================================
   Out-of-core octree data structure
   
   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: oococt.c,v 1.28 2016/04/25 17:49:50 taschreg Exp taschreg $
*/


#include "oococt.h"
#include "rtio.h"
#include <stdlib.h>
#include <unistd.h>


void OOC_Null (OOC_Octree *oct)
/* Init empty octree */
{
   oct -> maxNodes = oct -> numNodes = oct -> leafMax = oct -> maxDepth =
      oct -> numData = oct -> size = oct -> recSize = oct -> mortonScale = 0;
   oct -> org [0] = oct -> org [1] = oct -> org [2] = 
      oct -> bound [0] = oct -> bound [1] = oct -> bound [2] = 0;
   oct -> key = NULL;
   oct -> nodes = NULL;
   oct -> leafFile = NULL;
   oct -> cache = NULL;
}


void OOC_Init (OOC_Octree *oct, unsigned recSize, FVECT org, RREAL size, 
               RREAL *(*key)(const void*), FILE *leafFile)
{
   oct -> maxNodes = oct -> numNodes = oct -> leafMax = 
      oct -> maxDepth = oct -> numData = 0;
   VCOPY(oct -> org, org);
   oct -> size = oct -> bound[0] = oct -> bound[1] = oct -> bound[2] = size;
   VADD(oct -> bound, oct -> bound, org);
   oct -> mortonScale = size > 0 ? OOC_MORTON_MAX / size : 0;
   oct -> recSize = recSize;
   oct -> key = key;
   oct -> nodes = NULL;
   oct -> leafFile = leafFile;
   oct -> cache = NULL;    /* Cache currently initialised externally */
}


OOC_Node *NewNode (OOC_Octree *oct)
/* Allocate new octree node, enlarge array if necessary.
   Return pointer to new node or NULL if failed. */
{
   OOC_Node *n = NULL;

   if (oct -> numNodes >= OOC_NODEIDX_MAX) {
      /* Node index overflow */
      fprintf(stderr, "OOC_NewNode: node index overflow (numNodes = %d)\n",
              oct -> numNodes);
      return NULL;
   }
      
   if (++oct -> numNodes > oct -> maxNodes) {
      /* Need to allocate root or enlarge array */
      oct -> maxNodes += OOC_BLKSIZE / sizeof(OOC_Node);
      oct -> nodes = realloc(oct -> nodes, 
                             oct -> maxNodes * sizeof(OOC_Node));
      if (!oct -> nodes) {
         perror("OOC_NewNode: couldn't realloc() nodes");
         return NULL;
      }
   }
   
   n = oct -> nodes + oct -> numNodes - 1;
   n -> node.num = n -> node.kid = n -> node.branch = n -> node.type = 0;
   
   return n;
}


int OOC_GetData (OOC_Octree *oct, OOC_DataIdx idx, void *rec)
/* Reads indexed data record from leaf file and copies it to rec, else
 * returns -1 on failure */
{
   if (!oct || !rec)
      return -1;
   
   if (idx >= oct -> numData) {
      fprintf(stderr, "OOC_GetData: invalid data record index %u\n", idx);
      return -1;
   }   

   if (oct -> cache) {
      /* Retrieve record from leaf file via I/O cache */
      void  *cachedRec;

      if (!(cachedRec = OOC_CacheData(oct -> cache, oct -> leafFile, idx)))
         return -1;
            
      /* It's safer to copy the record to the caller's local buffer as a
       * returned pointer may be invalidated by subsequent calls if the
       * page it points to is swapped out */
      memcpy(rec, cachedRec, oct -> recSize);
   }
   else {
      /* No I/O caching; do (SLOW!) per-record I/O from leaf file */ 
      const unsigned long  pos = (unsigned long)oct -> recSize * idx;

      if (pread(fileno(oct -> leafFile), rec, oct -> recSize, pos) !=
          oct -> recSize) {
         perror("OOC_GetData: failed seek/read in leaf file");
         return -1;
      }
   }

   return 0;
}


int OOC_InBBox (const OOC_Octree *oct, const FVECT org, RREAL size, 
                const FVECT key)
/* Check whether key lies within bounding box defined by org and size.
 * Compares Morton codes rather than the coordinates directly to account
 * for dicretisation error introduced by the former. */
{
   const OOC_MortonIdx  keyZ = OOC_KEY2MORTON(key, oct);
   FVECT                bbox = {size, size, size};
   
   VADD(bbox, org, bbox);
   return keyZ > OOC_KEY2MORTON(org, oct) && 
          keyZ < OOC_KEY2MORTON(bbox, oct);
}


int OOC_Branch (const OOC_Octree *oct, const FVECT org, RREAL size, 
                const FVECT key, FVECT nuOrg)
/* Return index of octant containing key and corresponding origin if nuOrg
 * != NULL, or -1 if key lies outside all octants.  Size is already assumed
 * to be halved, i.e.  corresponding to the length of an octant axis.
 * Compares Morton codes rather than the coordinates directly to account
 * for dicretisation error introduced by the former. */
{
   int   o;
   FVECT octOrg;
   
   for (o = 0; o < 8; o++) {
      VCOPY(octOrg, org);
      OOC_OCTORIGIN(octOrg, o, size);
      
      if (OOC_InBBox(oct, octOrg, size, key)) {
         if (nuOrg)
            VCOPY(nuOrg, octOrg);
            
         return o;
      }
   }
   
   return -1;   
}


int OOC_BranchZ (const OOC_Octree *oct, const FVECT org, RREAL size, 
                 OOC_MortonIdx keyZ, FVECT nuOrg)
/* Optimised version of OOC_Branch() with precomputed key Morton code */
{
   int         o;
   const FVECT cent = {size, size, size};
   FVECT       octOrg, bbox;
   
   for (o = 0; o < 8; o++) {
      VCOPY(octOrg, org);
      OOC_OCTORIGIN(octOrg, o, size);
      VADD(bbox, octOrg, cent);
      
      if (keyZ > OOC_KEY2MORTON(octOrg, oct) && 
          keyZ < OOC_KEY2MORTON(bbox, oct)) {
         if (nuOrg)
            VCOPY(nuOrg, octOrg);
            
         return o;
      }
   }
   
   return -1;   
}


OOC_DataIdx OOC_GetKid (const OOC_Octree *oct, OOC_Node **node, unsigned kid)
/* For a given octree node, return the sum of the data counters for kids
 * [0..k-1].  On return, the node either points to the k'th kid, or
 * NULL if the kid is nonexistent or the node is a leaf */                        
{
   unsigned       k;
   OOC_Node       *kidNode = OOC_KID1(oct, *node); /* NULL if leaf */
   OOC_DataIdx    dataIdx = 0;
   
   for (k = 0; k < kid; k++) {
      if (OOC_ISLEAF(*node))
         /* Sum data counters of leaf octants */
         dataIdx += (*node) -> leaf.num [k];
      else 
         /* Sum data counter of inner node's nonempty kids and advance
          * pointer to sibling */
         if (OOC_ISBRANCH(*node, k)) {
            dataIdx += OOC_DATACNT(kidNode);
            kidNode++;
         }
   }
   
   /* Update node pointer to selected kid (or NULL if nonexistent or node is
    * a leaf) */
   *node = OOC_ISBRANCH(*node, kid) ? kidNode : NULL;
   return dataIdx;
}


#ifdef DEBUG_OOC
int OOC_Check (OOC_Octree *oct, const OOC_Node *node, 
               FVECT org, RREAL size, OOC_DataIdx dataIdx)
/* Traverse tree & check for valid nodes; oct -> leafFile must be open;
 * return 0 if ok, otherwise -1 */
{
   unsigned    k;
   FVECT       kidOrg;
   const RREAL kidSize = size * 0.5;

   if (!oct || !node)
      return -1;
      
   if (OOC_ISLEAF(node)) {
      /* Node is a leaf; check records in each octant */
      char        rec [oct -> recSize];   /* Violates C89! */
      OOC_OctCnt  d;
      RREAL       *key;
      
      for (k = 0; k < 8; k++) {
         VCOPY(kidOrg, org);
         OOC_OCTORIGIN(kidOrg, k, kidSize);
         
         for (d = node -> leaf.num [k]; d; d--, dataIdx++) {
#ifdef DEBUG_OOC_CHECK
            fprintf(stderr, "OOC_Check: checking record %lu\n", 
                    (unsigned long)dataIdx);
#endif            
            if (OOC_GetData(oct, dataIdx, rec)) {
               fprintf(stderr, "OOC_Check: failed getting record at %lu\n",
                       (unsigned long)dataIdx);
               return -1;
            }
            
            key = oct -> key(rec);
            if (!OOC_InBBox(oct, kidOrg, kidSize, key)) {
               fprintf(stderr, "OOC_Check: key [%f, %f, %f] (zIdx %020lu) "
                       "outside bbox [[%f-%f], [%f-%f], [%f-%f]] "
                       "in octant %d (should be %d)\n",
                       key [0], key [1], key [2], 
                       OOC_KEY2MORTON(key, oct),
                       kidOrg [0], kidOrg [0] + kidSize, 
                       kidOrg [1], kidOrg [1] + kidSize, 
                       kidOrg [2], kidOrg [2] + kidSize,
                       k, OOC_Branch(oct, org, kidSize, key, NULL));
               /* return -1; */               
            }
         }
      }
   }
   else {
      /* Internal node; recurse on all kids */
      const OOC_Node *kid = OOC_KID1(oct, node);
      OOC_DataIdx    numData = 0;
      
      if (node -> node.kid >= oct -> numNodes) {
         fprintf(stderr, "OOC_Check: invalid node index %u\n", 
                 node -> node.kid);
         return -1;
      }
         
      if (!node -> node.num) {
         fputs("OOC_Check: empty octree node\n", stderr);
         return -1;
      }
      
      for (k = 0; k < 8; k++)
         if (OOC_ISBRANCH(node, k)) {
            VCOPY(kidOrg, org);
            OOC_OCTORIGIN(kidOrg, k, kidSize);
            
            if (OOC_Check(oct, kid, kidOrg, kidSize, dataIdx))
               return -1;
            
            dataIdx += OOC_DATACNT(kid);
            numData += OOC_DATACNT(kid);
            kid++;
         }
      
      if (node -> node.num != numData) {
         fprintf(stderr, 
                 "Parent/kid data count mismatch; expected %u, found %u\n",
                 node -> node.num, numData);
         return -1;
      }
   }
   
   return 0;
}
#endif
         

int OOC_SaveOctree (const OOC_Octree *oct, FILE *out)
/* Appends octree nodes to specified file along with metadata. Uses
 * RADIANCE's portable I/O routines.  Returns 0 on success, else -1.  Note
 * the internal representation of the nodes is platform specific as they
 * contain unions, therefore we use the portable I/O routines from the
 * RADIANCE library */
{
   int         i;
   OOC_NodeIdx nc;
   OOC_Node    *np = NULL;
   
   if (!oct || !oct->nodes || !oct->numData || !oct->numNodes || !out) {
      fputs("OOC_SaveOctree: empty octree\n", stderr);
      return -1;
   }
      
   /* Write octree origin, size, data record size, number of records, and
    * number of nodes */
   for (i = 0; i < 3; i++)
      putflt(oct -> org [i], out);
      
   putflt(oct -> size, out);

#if 0   
   for (i = 0; i < 3; i++)
      putflt(oct -> bound [i], out);
      
   putint(oct -> mortonScale, sizeof(oct -> mortonScale),   out);
#endif   
   putint(oct -> recSize,     sizeof(oct -> recSize),       out);
   putint(oct -> numData,     sizeof(oct -> numData),       out);
   putint(oct -> numNodes,    sizeof(oct -> numNodes),      out);
   
   /* Write nodes to file */
   for (nc = oct -> numNodes, np = oct -> nodes; nc; nc--, np++) {
      if (OOC_ISLEAF(np)) {
         /* Write leaf marker */
         putint(-1, 1, out);
         
         /* Write leaf octant counters */
         for (i = 0; i < 8; i++)
            putint(np -> leaf.num [i], sizeof(np -> leaf.num [i]), out);
      }
      else {
         /* Write node marker */
         putint(0, 1, out);
         
         /* Write node, rounding field size up to nearest number of bytes */
         putint(np -> node.kid,     (OOC_NODEIDX_BITS + 7) >> 3, out);
         putint(np -> node.num,     (OOC_DATAIDX_BITS + 7) >> 3, out);
         putint(np -> node.branch,  1,                           out);
      }
         
      if (ferror(out)) {
         fputs("OOC_SaveOctree: failed writing to node file", stderr);
         return -1;
      }
   }
   
   fflush(out);
   return 0;
}


int OOC_LoadOctree (OOC_Octree *oct, FILE *nodeFile, 
                    RREAL *(*key)(const void*), FILE *leafFile)
/* Load octree nodes and metadata from nodeFile and associate with records
 * in leafFile.  Uses RADIANCE's portable I/O routines.  Returns 0 on
 * success, else -1.  */
{
   int         i;
   OOC_NodeIdx nc;
   OOC_Node    *np = NULL;
   
   if (!oct || !nodeFile)
      return -1;

   OOC_Null(oct);
   
   /* Read octree origin, size, record size, #records and #nodes */
   for (i = 0; i < 3; i++)
      oct -> org [i] = getflt(nodeFile);

   oct -> size = getflt(nodeFile);
   
#if 0   
   for (i = 0; i < 3; i++)
      oct -> bound [i] = getflt(nodeFile);
      
   oct -> mortonScale   = getint(sizeof(oct -> mortonScale),   nodeFile);
#else
   oct -> bound [0] = oct -> bound [1] = oct -> bound [2] = oct -> size;
   VADD(oct -> bound, oct -> bound, oct -> org);   
   
   oct -> mortonScale   = OOC_MORTON_MAX / oct -> size;
#endif
   
#if 0
   fprintf(stderr, "OOC_LoadOctree: mortonScale = %lf\n", oct -> mortonScale);
#endif      

   oct -> recSize       = getint(sizeof(oct -> recSize),       nodeFile);
   oct -> numData       = getint(sizeof(oct -> numData),       nodeFile);
   oct -> numNodes      = getint(sizeof(oct -> numNodes),      nodeFile);
   oct -> key           = key;
   oct -> leafFile      = leafFile;
   
   if (feof(nodeFile) || !oct -> numData || !oct -> numNodes) {
      fputs("OOC_LoadOctree: empty octree\n", stderr);
      return -1;
   }
   
   /* Allocate octree nodes */
   if (!(oct -> nodes = calloc(oct -> numNodes, sizeof(OOC_Node)))) {
      fputs("OOC_LoadOctree: failed octree allocation\n", stderr);
      return -1;
   }

   /* Read nodes from file */   
   for (nc = oct -> numNodes, np = oct -> nodes; nc; nc--, np++) {
      OOC_CLEARNODE(np);
      
      /* Read node type marker */
      if (getint(1, nodeFile)) {
         /* Read leaf octant counters and set node type */
         for (i = 0; i < 8; i++)
            np -> leaf.num [i] = getint(sizeof(np -> leaf.num [i]), 
                                        nodeFile);
         
         OOC_SETLEAF(np);
      }
      else {
         /* Read node, rounding field size up to nearest number of bytes */
         np -> node.kid    = getint((OOC_NODEIDX_BITS + 7) >> 3,  nodeFile);
         np -> node.num    = getint((OOC_DATAIDX_BITS + 7) >> 3,  nodeFile);
         np -> node.branch = getint(1,                            nodeFile);
      }
         
      if (ferror(nodeFile)) {
         fputs("OOC_LoadOctree: failed reading from node file\n", stderr);
         return -1;
      }
   }
   
   return 0;
}   


void OOC_Delete (OOC_Octree *oct)
/* Self-destruct */
{
   free(oct -> nodes);
   fclose(oct -> leafFile);
   
   if (oct -> cache)
      OOC_DeleteCache(oct -> cache);
}
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:	+417 -139 lines
Log Message:	Initial import of ooC photon map
#	User	Rev	Content
1	greg	2.1	/*
2	rschregle	2.3	======================================================================
3	greg	2.1	Out-of-core octree data structure
4
5			Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
6	rschregle	2.3	(c) Lucerne University of Applied Sciences and Arts,
7			supported by the Swiss National Science Foundation (SNSF, #147053)
8			======================================================================
9	greg	2.1
10	rschregle	2.3	$Id: oococt.c,v 1.28 2016/04/25 17:49:50 taschreg Exp taschreg $
11	greg	2.1	*/
12
13
14	rschregle	2.3
15			#include "oococt.h"
16			#include "rtio.h"
17	greg	2.1	#include <stdlib.h>
18	rschregle	2.3	#include <unistd.h>
19
20	greg	2.1
21
22	rschregle	2.3	void OOC_Null (OOC_Octree *oct)
23			/* Init empty octree */
24	greg	2.1	{
25	rschregle	2.3	oct -> maxNodes = oct -> numNodes = oct -> leafMax = oct -> maxDepth =
26			oct -> numData = oct -> size = oct -> recSize = oct -> mortonScale = 0;
27			oct -> org [0] = oct -> org [1] = oct -> org [2] =
28			oct -> bound [0] = oct -> bound [1] = oct -> bound [2] = 0;
29			oct -> key = NULL;
30			oct -> nodes = NULL;
31			oct -> leafFile = NULL;
32			oct -> cache = NULL;
33	greg	2.1	}
34
35
36	rschregle	2.3
37			void OOC_Init (OOC_Octree *oct, unsigned recSize, FVECT org, RREAL size,
38			RREAL (key)(const void), FILE leafFile)
39	greg	2.1	{
40	rschregle	2.3	oct -> maxNodes = oct -> numNodes = oct -> leafMax =
41			oct -> maxDepth = oct -> numData = 0;
42			VCOPY(oct -> org, org);
43			oct -> size = oct -> bound[0] = oct -> bound[1] = oct -> bound[2] = size;
44			VADD(oct -> bound, oct -> bound, org);
45			oct -> mortonScale = size > 0 ? OOC_MORTON_MAX / size : 0;
46			oct -> recSize = recSize;
47			oct -> key = key;
48			oct -> nodes = NULL;
49			oct -> leafFile = leafFile;
50			oct -> cache = NULL; /* Cache currently initialised externally */
51	greg	2.1	}
52
53	rschregle	2.3
54
55			OOC_Node NewNode (OOC_Octree oct)
56	greg	2.1	/* Allocate new octree node, enlarge array if necessary.
57			Return pointer to new node or NULL if failed. */
58			{
59			OOC_Node *n = NULL;
60	rschregle	2.3
61			if (oct -> numNodes >= OOC_NODEIDX_MAX) {
62			/* Node index overflow */
63			fprintf(stderr, "OOC_NewNode: node index overflow (numNodes = %d)\n",
64			oct -> numNodes);
65			return NULL;
66			}
67
68	greg	2.1	if (++oct -> numNodes > oct -> maxNodes) {
69			/* Need to allocate root or enlarge array */
70			oct -> maxNodes += OOC_BLKSIZE / sizeof(OOC_Node);
71	rschregle	2.3	oct -> nodes = realloc(oct -> nodes,
72			oct -> maxNodes * sizeof(OOC_Node));
73			if (!oct -> nodes) {
74			perror("OOC_NewNode: couldn't realloc() nodes");
75	greg	2.1	return NULL;
76	rschregle	2.3	}
77	greg	2.1	}
78
79	rschregle	2.3	n = oct -> nodes + oct -> numNodes - 1;
80			n -> node.num = n -> node.kid = n -> node.branch = n -> node.type = 0;
81
82			return n;
83	greg	2.1	}
84
85	rschregle	2.3
86
87			int OOC_GetData (OOC_Octree oct, OOC_DataIdx idx, void rec)
88			/* Reads indexed data record from leaf file and copies it to rec, else
89			* returns -1 on failure */
90	greg	2.1	{
91	rschregle	2.3	if (!oct \|\| !rec)
92			return -1;
93
94			if (idx >= oct -> numData) {
95			fprintf(stderr, "OOC_GetData: invalid data record index %u\n", idx);
96			return -1;
97			}
98
99			if (oct -> cache) {
100			/* Retrieve record from leaf file via I/O cache */
101			void *cachedRec;
102
103			if (!(cachedRec = OOC_CacheData(oct -> cache, oct -> leafFile, idx)))
104			return -1;
105
106			/* It's safer to copy the record to the caller's local buffer as a
107			* returned pointer may be invalidated by subsequent calls if the
108			* page it points to is swapped out */
109			memcpy(rec, cachedRec, oct -> recSize);
110			}
111			else {
112			/* No I/O caching; do (SLOW!) per-record I/O from leaf file */
113			const unsigned long pos = (unsigned long)oct -> recSize * idx;
114
115			if (pread(fileno(oct -> leafFile), rec, oct -> recSize, pos) !=
116			oct -> recSize) {
117			perror("OOC_GetData: failed seek/read in leaf file");
118			return -1;
119			}
120			}
121	greg	2.1
122	rschregle	2.3	return 0;
123	greg	2.1	}
124
125
126	rschregle	2.3
127			int OOC_InBBox (const OOC_Octree *oct, const FVECT org, RREAL size,
128			const FVECT key)
129			/* Check whether key lies within bounding box defined by org and size.
130			* Compares Morton codes rather than the coordinates directly to account
131			* for dicretisation error introduced by the former. */
132			{
133			const OOC_MortonIdx keyZ = OOC_KEY2MORTON(key, oct);
134			FVECT bbox = {size, size, size};
135
136			VADD(bbox, org, bbox);
137			return keyZ > OOC_KEY2MORTON(org, oct) &&
138			keyZ < OOC_KEY2MORTON(bbox, oct);
139			}
140
141
142
143			int OOC_Branch (const OOC_Octree *oct, const FVECT org, RREAL size,
144			const FVECT key, FVECT nuOrg)
145			/* Return index of octant containing key and corresponding origin if nuOrg
146			* != NULL, or -1 if key lies outside all octants. Size is already assumed
147			* to be halved, i.e. corresponding to the length of an octant axis.
148			* Compares Morton codes rather than the coordinates directly to account
149			* for dicretisation error introduced by the former. */
150	greg	2.1	{
151	rschregle	2.3	int o;
152			FVECT octOrg;
153	greg	2.1
154	rschregle	2.3	for (o = 0; o < 8; o++) {
155			VCOPY(octOrg, org);
156			OOC_OCTORIGIN(octOrg, o, size);
157
158			if (OOC_InBBox(oct, octOrg, size, key)) {
159			if (nuOrg)
160			VCOPY(nuOrg, octOrg);
161
162			return o;
163	greg	2.1	}
164			}
165
166	rschregle	2.3	return -1;
167	greg	2.1	}
168
169
170	rschregle	2.3
171			int OOC_BranchZ (const OOC_Octree *oct, const FVECT org, RREAL size,
172			OOC_MortonIdx keyZ, FVECT nuOrg)
173			/* Optimised version of OOC_Branch() with precomputed key Morton code */
174	greg	2.1	{
175	rschregle	2.3	int o;
176			const FVECT cent = {size, size, size};
177			FVECT octOrg, bbox;
178
179			for (o = 0; o < 8; o++) {
180			VCOPY(octOrg, org);
181			OOC_OCTORIGIN(octOrg, o, size);
182			VADD(bbox, octOrg, cent);
183
184			if (keyZ > OOC_KEY2MORTON(octOrg, oct) &&
185			keyZ < OOC_KEY2MORTON(bbox, oct)) {
186			if (nuOrg)
187			VCOPY(nuOrg, octOrg);
188
189			return o;
190			}
191			}
192	greg	2.1
193	rschregle	2.3	return -1;
194			}
195
196
197
198			OOC_DataIdx OOC_GetKid (const OOC_Octree oct, OOC_Node *node, unsigned kid)
199			/* For a given octree node, return the sum of the data counters for kids
200			* [0..k-1]. On return, the node either points to the k'th kid, or
201			* NULL if the kid is nonexistent or the node is a leaf */
202			{
203			unsigned k;
204			OOC_Node kidNode = OOC_KID1(oct, node); /* NULL if leaf */
205			OOC_DataIdx dataIdx = 0;
206
207			for (k = 0; k < kid; k++) {
208			if (OOC_ISLEAF(*node))
209			/* Sum data counters of leaf octants */
210			dataIdx += (*node) -> leaf.num [k];
211			else
212			/* Sum data counter of inner node's nonempty kids and advance
213			* pointer to sibling */
214			if (OOC_ISBRANCH(*node, k)) {
215			dataIdx += OOC_DATACNT(kidNode);
216			kidNode++;
217			}
218			}
219
220			/* Update node pointer to selected kid (or NULL if nonexistent or node is
221			* a leaf) */
222			node = OOC_ISBRANCH(node, kid) ? kidNode : NULL;
223			return dataIdx;
224			}
225
226
227
228			#ifdef DEBUG_OOC
229			int OOC_Check (OOC_Octree oct, const OOC_Node node,
230			FVECT org, RREAL size, OOC_DataIdx dataIdx)
231			/* Traverse tree & check for valid nodes; oct -> leafFile must be open;
232			* return 0 if ok, otherwise -1 */
233			{
234			unsigned k;
235			FVECT kidOrg;
236			const RREAL kidSize = size * 0.5;
237
238			if (!oct \|\| !node)
239	greg	2.1	return -1;
240	rschregle	2.3
241			if (OOC_ISLEAF(node)) {
242			/* Node is a leaf; check records in each octant */
243			char rec [oct -> recSize]; /* Violates C89! */
244			OOC_OctCnt d;
245			RREAL *key;
246
247			for (k = 0; k < 8; k++) {
248			VCOPY(kidOrg, org);
249			OOC_OCTORIGIN(kidOrg, k, kidSize);
250
251			for (d = node -> leaf.num [k]; d; d--, dataIdx++) {
252			#ifdef DEBUG_OOC_CHECK
253			fprintf(stderr, "OOC_Check: checking record %lu\n",
254			(unsigned long)dataIdx);
255			#endif
256			if (OOC_GetData(oct, dataIdx, rec)) {
257			fprintf(stderr, "OOC_Check: failed getting record at %lu\n",
258			(unsigned long)dataIdx);
259			return -1;
260			}
261
262			key = oct -> key(rec);
263			if (!OOC_InBBox(oct, kidOrg, kidSize, key)) {
264			fprintf(stderr, "OOC_Check: key [%f, %f, %f] (zIdx %020lu) "
265			"outside bbox [[%f-%f], [%f-%f], [%f-%f]] "
266			"in octant %d (should be %d)\n",
267			key [0], key [1], key [2],
268			OOC_KEY2MORTON(key, oct),
269			kidOrg [0], kidOrg [0] + kidSize,
270			kidOrg [1], kidOrg [1] + kidSize,
271			kidOrg [2], kidOrg [2] + kidSize,
272			k, OOC_Branch(oct, org, kidSize, key, NULL));
273			/* return -1; */
274			}
275			}
276			}
277			}
278			else {
279			/* Internal node; recurse on all kids */
280			const OOC_Node *kid = OOC_KID1(oct, node);
281			OOC_DataIdx numData = 0;
282
283			if (node -> node.kid >= oct -> numNodes) {
284			fprintf(stderr, "OOC_Check: invalid node index %u\n",
285			node -> node.kid);
286			return -1;
287			}
288
289			if (!node -> node.num) {
290			fputs("OOC_Check: empty octree node\n", stderr);
291			return -1;
292			}
293
294			for (k = 0; k < 8; k++)
295			if (OOC_ISBRANCH(node, k)) {
296			VCOPY(kidOrg, org);
297			OOC_OCTORIGIN(kidOrg, k, kidSize);
298
299			if (OOC_Check(oct, kid, kidOrg, kidSize, dataIdx))
300			return -1;
301
302			dataIdx += OOC_DATACNT(kid);
303			numData += OOC_DATACNT(kid);
304			kid++;
305			}
306
307			if (node -> node.num != numData) {
308			fprintf(stderr,
309			"Parent/kid data count mismatch; expected %u, found %u\n",
310			node -> node.num, numData);
311			return -1;
312			}
313			}
314	greg	2.1
315	rschregle	2.3	return 0;
316			}
317			#endif
318
319
320
321			int OOC_SaveOctree (const OOC_Octree oct, FILE out)
322			/* Appends octree nodes to specified file along with metadata. Uses
323			* RADIANCE's portable I/O routines. Returns 0 on success, else -1. Note
324			* the internal representation of the nodes is platform specific as they
325			* contain unions, therefore we use the portable I/O routines from the
326			* RADIANCE library */
327			{
328			int i;
329			OOC_NodeIdx nc;
330			OOC_Node *np = NULL;
331	greg	2.1
332	rschregle	2.3	if (!oct \|\| !oct->nodes \|\| !oct->numData \|\| !oct->numNodes \|\| !out) {
333			fputs("OOC_SaveOctree: empty octree\n", stderr);
334	greg	2.1	return -1;
335			}
336	rschregle	2.3
337			/* Write octree origin, size, data record size, number of records, and
338			* number of nodes */
339			for (i = 0; i < 3; i++)
340			putflt(oct -> org [i], out);
341
342			putflt(oct -> size, out);
343	greg	2.1
344	rschregle	2.3	#if 0
345			for (i = 0; i < 3; i++)
346			putflt(oct -> bound [i], out);
347
348			putint(oct -> mortonScale, sizeof(oct -> mortonScale), out);
349			#endif
350			putint(oct -> recSize, sizeof(oct -> recSize), out);
351			putint(oct -> numData, sizeof(oct -> numData), out);
352			putint(oct -> numNodes, sizeof(oct -> numNodes), out);
353
354			/* Write nodes to file */
355			for (nc = oct -> numNodes, np = oct -> nodes; nc; nc--, np++) {
356			if (OOC_ISLEAF(np)) {
357			/* Write leaf marker */
358			putint(-1, 1, out);
359
360			/* Write leaf octant counters */
361			for (i = 0; i < 8; i++)
362			putint(np -> leaf.num [i], sizeof(np -> leaf.num [i]), out);
363			}
364			else {
365			/* Write node marker */
366			putint(0, 1, out);
367
368			/* Write node, rounding field size up to nearest number of bytes */
369			putint(np -> node.kid, (OOC_NODEIDX_BITS + 7) >> 3, out);
370			putint(np -> node.num, (OOC_DATAIDX_BITS + 7) >> 3, out);
371			putint(np -> node.branch, 1, out);
372			}
373
374			if (ferror(out)) {
375			fputs("OOC_SaveOctree: failed writing to node file", stderr);
376			return -1;
377			}
378			}
379
380			fflush(out);
381			return 0;
382	greg	2.1	}
383
384
385	rschregle	2.3
386			int OOC_LoadOctree (OOC_Octree oct, FILE nodeFile,
387			RREAL (key)(const void), FILE leafFile)
388			/* Load octree nodes and metadata from nodeFile and associate with records
389			* in leafFile. Uses RADIANCE's portable I/O routines. Returns 0 on
390			* success, else -1. */
391			{
392			int i;
393			OOC_NodeIdx nc;
394			OOC_Node *np = NULL;
395
396			if (!oct \|\| !nodeFile)
397			return -1;
398
399			OOC_Null(oct);
400
401			/* Read octree origin, size, record size, #records and #nodes */
402			for (i = 0; i < 3; i++)
403			oct -> org [i] = getflt(nodeFile);
404
405			oct -> size = getflt(nodeFile);
406	greg	2.1
407	rschregle	2.3	#if 0
408			for (i = 0; i < 3; i++)
409			oct -> bound [i] = getflt(nodeFile);
410
411			oct -> mortonScale = getint(sizeof(oct -> mortonScale), nodeFile);
412			#else
413			oct -> bound [0] = oct -> bound [1] = oct -> bound [2] = oct -> size;
414			VADD(oct -> bound, oct -> bound, oct -> org);
415
416			oct -> mortonScale = OOC_MORTON_MAX / oct -> size;
417			#endif
418
419			#if 0
420			fprintf(stderr, "OOC_LoadOctree: mortonScale = %lf\n", oct -> mortonScale);
421			#endif
422
423			oct -> recSize = getint(sizeof(oct -> recSize), nodeFile);
424			oct -> numData = getint(sizeof(oct -> numData), nodeFile);
425			oct -> numNodes = getint(sizeof(oct -> numNodes), nodeFile);
426			oct -> key = key;
427			oct -> leafFile = leafFile;
428
429			if (feof(nodeFile) \|\| !oct -> numData \|\| !oct -> numNodes) {
430			fputs("OOC_LoadOctree: empty octree\n", stderr);
431			return -1;
432			}
433	greg	2.1
434	rschregle	2.3	/* Allocate octree nodes */
435			if (!(oct -> nodes = calloc(oct -> numNodes, sizeof(OOC_Node)))) {
436			fputs("OOC_LoadOctree: failed octree allocation\n", stderr);
437			return -1;
438			}
439
440			/* Read nodes from file */
441			for (nc = oct -> numNodes, np = oct -> nodes; nc; nc--, np++) {
442			OOC_CLEARNODE(np);
443
444			/* Read node type marker */
445			if (getint(1, nodeFile)) {
446			/* Read leaf octant counters and set node type */
447			for (i = 0; i < 8; i++)
448			np -> leaf.num [i] = getint(sizeof(np -> leaf.num [i]),
449			nodeFile);
450
451			OOC_SETLEAF(np);
452			}
453			else {
454			/* Read node, rounding field size up to nearest number of bytes */
455			np -> node.kid = getint((OOC_NODEIDX_BITS + 7) >> 3, nodeFile);
456			np -> node.num = getint((OOC_DATAIDX_BITS + 7) >> 3, nodeFile);
457			np -> node.branch = getint(1, nodeFile);
458			}
459
460			if (ferror(nodeFile)) {
461			fputs("OOC_LoadOctree: failed reading from node file\n", stderr);
462			return -1;
463	greg	2.1	}
464			}
465
466	rschregle	2.3	return 0;
467			}
468
469
470	greg	2.1
471	rschregle	2.3	void OOC_Delete (OOC_Octree *oct)
472			/* Self-destruct */
473	greg	2.1	{
474	rschregle	2.3	free(oct -> nodes);
475			fclose(oct -> leafFile);
476	greg	2.1
477	rschregle	2.3	if (oct -> cache)
478			OOC_DeleteCache(oct -> cache);
479			}