src/rt/oococt.c

#ifndef lint
static const char RCSid[] = "$Id$";
#endif


/* 
   ======================================================================
   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 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 "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);
   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);
   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;
   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);
}

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