src/rt/oococt.h

/* 
   ======================================================================
   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.h,v 2.3 2016/05/17 17:39:47 rschregle Exp $
*/


#ifndef OOC_OCT_H
#define OOC_OCT_H

   #include "oocmorton.h"
   #include "ooccache.h"
   #include <stdint.h>
   #include <stdio.h>


   /* ===================================================================
    * CONSTS
    * =================================================================== */
    
   /* Octree index & data counter types */
   typedef uint32_t           OOC_NodeIdx;
   typedef uint32_t           OOC_DataIdx;  
   typedef uint8_t            OOC_OctCnt;
   
   /* Octree node field sizes for above */   
   #define OOC_NODEIDX_BITS   31
   #define OOC_DATAIDX_BITS   32
   
   /* Limits for above */
   #define OOC_NODEIDX_MAX    ((1L << OOC_NODEIDX_BITS) - 1)
   #define OOC_DATAIDX_MAX    ((1L << OOC_DATAIDX_BITS) - 2)
   #define OOC_OCTCNT_MAX     UINT8_MAX
   
   /* Reserved values for above */
   #define OOC_DATAIDX_ERR    (OOC_DATAIDX_MAX + 1)
   
   /* Block size for node allocation (8k) */
   #define OOC_BLKSIZE        (1L << 13)


   /* ===================================================================
    * UTILZ
    * =================================================================== */   

   /* Test/set leaf flag for node n */
   #define OOC_ISLEAF(n)      ((n) -> node.type)
   #define OOC_SETLEAF(n)     ((n) -> node.type = 1)
   
   /* Test/set branch bit for octant k in node n */
   #define OOC_ISBRANCH(n,k)  (!OOC_ISLEAF(n) && (n) -> node.branch & 1 << (k))
   #define OOC_SETBRANCH(n,k) ((n) -> node.branch |=  1 << (k))
   
   /* Return index to node's 1st kid */
   #define OOC_KID1(o,n)      (!OOC_ISLEAF(n) ? (o)->nodes + (n)->node.kid \
                                              : NULL)
                                 
   /* Get index to last node in octree; -1 indicates empty octree */
   #define OOC_ROOTIDX(o)     ((o) -> nodes && (o) -> numNodes > 0 \
                                 ? (o) -> numNodes - 1 : -1)
                                 
   /* Get octree root; this is at the *end* of the node array! */
   #define OOC_ROOT(o)        (OOC_ROOTIDX(o) >= 0 \
                                 ? (o) -> nodes + OOC_ROOTIDX(o) : NULL)
   
   /* Copy node to octree root */
   #define OOC_SETROOT(o,n)   (memcpy(OOC_ROOT(o), (n), sizeof(OOC_Node)))

   /* Set all node fields to 0 */   
   #define OOC_CLEARNODE(n)   (memset((n), 0, sizeof(OOC_Node)))

   /* Modify origin o for octant k of size s */
   #define OOC_OCTORIGIN(o,k,s)  ((o) [0] += (s) * ((k)      & 1), \
                                  (o) [1] += (s) * ((k) >> 1 & 1), \
                                  (o) [2] += (s) * ((k) >> 2 & 1))

   /* Get num records stored in node (also handles leaves and NULL pointer) */
   #define OOC_DATACNT(n) \
      ((n) ? OOC_ISLEAF(n) ? (n) -> leaf.num [0] + (n) -> leaf.num [1] + \
                             (n) -> leaf.num [2] + (n) -> leaf.num [3] + \
                             (n) -> leaf.num [4] + (n) -> leaf.num [5] + \
                             (n) -> leaf.num [6] + (n) -> leaf.num [7]   \
                           : (n) -> node.num \
           : 0)

   /* Shortcuts for morton code from key and data record */
   #define OOC_KEY2MORTON(k, o)  OOC_Key2Morton((k), (o) -> org, \
                                                (o) -> mortonScale)
   #define OOC_REC2MORTON(r, o)  OOC_Key2Morton((o) -> key(r), (o) -> org, \
                                                (o) -> mortonScale)


   /* ===================================================================
    * DATA TYPEZ
    * =================================================================== */   
                           
   /* Octree node */
   typedef struct {
      union {
         struct {
            /* Interior node (node.type = 0) with:
               node.kid    = index to 1st child node in octree array (a.k.a
                             "Number One Son"), immediately followed by its
                             nonzero siblings as indicated by branch
               node.num    = num records stored in this subtree,
               node.branch = branch bitmask indicating nonzero kid nodes */
            char           type  : 1;
            OOC_NodeIdx    kid   : OOC_NODEIDX_BITS;             
            OOC_DataIdx    num   : OOC_DATAIDX_BITS;
            uint8_t        branch;
            
            /* NOTE that we can't make the kid's index relative to parent
             * (which would be more compact), since we don't know the
             * parent's index a priori during the bottom-up construction! */
         } node;

         struct {
            /* Leaf node (leaf.type = node.type = 1 with:
               leaf.num [k] = num records stored in octant k */
            char           type  : 1;
            OOC_OctCnt     num   [8];
         } leaf;
      };
   } OOC_Node;


   /* Top level octree container */
   typedef struct {
      FVECT          org, bound;    /* Cube origin (min. XYZ), size, and
                                       resulting bounds (max. XYZ) */
      RREAL          size,
                     *(*key)(const void*); /* Callback for data rec coords */
      RREAL          mortonScale;   /* Scale factor for generating Morton
                                       codes from coords */
      OOC_Node       *nodes;        /* Pointer to node array */
                                    /* *************************************
                                     * **** NODES ARE STORED IN POSTFIX ****
                                     * **** ORDER, I.E. ROOT IS LAST!   ****
                                     * *************************************/
      OOC_DataIdx    numData;       /* Num records in leaves */
      OOC_NodeIdx    maxNodes,      /* Num currently allocated nodes */
                     numNodes;      /* Num used nodes (<= maxNodes) */
      unsigned       recSize,       /* Size of data record in bytes */
                     leafMax,       /* Max #records per leaf (for build) */
                     maxDepth;      /* Max subdivision depth (for build) */
      FILE           *leafFile;     /* File containing data in leaves */
      OOC_Cache      *cache;        /* I/O cache for leafFile */
   } OOC_Octree;

   /* DOAN' FORGET: NODES IN ***POSTFIX*** ORDAH!!! */

#ifdef __cplusplus
extern "C" {
#endif


   /* ===================================================================
    * FUNKZ
    * =================================================================== */   

   /* Init empty octree */
   void OOC_Null (OOC_Octree *oct);

    
   /* Initialises octree for records of size recSize with 3D coordinates,
    * accessed via key() callback.  The octree's bounding box is defined by
    * its origin org and size per axis, and must contain all keys. The
    * octree is associated with the specified leaf file containing the
    * records in Morton order */
   void OOC_Init (OOC_Octree *oct, unsigned recSize, FVECT org, RREAL size, 
                  RREAL *(*key)(const void*), FILE *leafFile);


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


   /* Reads indexed data record from leaf file and copies it to rec, else
    * returns -1 on failure */
   int OOC_GetData (OOC_Octree *oct, OOC_DataIdx idx, void *rec);
   

   /* Appends octree nodes to specified file along with metadata. Uses
    * RADIANCE's portable I/O routines. Returns 0 on success, else -1. */
   int OOC_SaveOctree (const OOC_Octree *oct, FILE *nodeFile);


   /* 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 OOC_LoadOctree (OOC_Octree *oct, FILE *nodeFile, 
                       RREAL *(*key)(const void*), FILE *leafFile);

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

   /* Check whether key lies within bounding box defined by org and size */
   int OOC_InBBox (const OOC_Octree *oct, const FVECT org, RREAL size, 
                   const FVECT key); 

   /* 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. */
   int OOC_Branch (const OOC_Octree *oct, const FVECT org, RREAL size, 
                   const FVECT key, FVECT nuOrg);                  

   /* Optimised version of OOC_Branch() with precomputed key Morton code */
   int OOC_BranchZ (const OOC_Octree *oct, const FVECT org, RREAL size, 
                    OOC_MortonIdx keyZ, FVECT nuOrg);                  

   /* 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 */
   OOC_DataIdx OOC_GetKid (const OOC_Octree *oct, OOC_Node **node, 
                           unsigned k);

   /* Self-destruct */
   void OOC_Delete (OOC_Octree *oct);

#ifdef __cplusplus
}
#endif

   /* DID WE MENTION NODES ARE IN POSTFIX ORDAH? */
#endif
Revision:	2.4
Committed:	Tue Sep 17 16:36:04 2024 UTC (7 months, 2 weeks ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 2.3:	+8 -2 lines
Log Message:	chore: Added extern "C" to headers to avoid C++ name mangling
#	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	greg	2.4	$Id: oococt.h,v 2.3 2016/05/17 17:39:47 rschregle Exp $
11	greg	2.1	*/
12
13
14	rschregle	2.3	#ifndef OOC_OCT_H
15			#define OOC_OCT_H
16
17			#include "oocmorton.h"
18			#include "ooccache.h"
19			#include <stdint.h>
20			#include <stdio.h>
21
22
23			/* ===================================================================
24			* CONSTS
25			* =================================================================== */
26
27			/* Octree index & data counter types */
28			typedef uint32_t OOC_NodeIdx;
29			typedef uint32_t OOC_DataIdx;
30			typedef uint8_t OOC_OctCnt;
31
32			/* Octree node field sizes for above */
33			#define OOC_NODEIDX_BITS 31
34			#define OOC_DATAIDX_BITS 32
35
36			/* Limits for above */
37			#define OOC_NODEIDX_MAX ((1L << OOC_NODEIDX_BITS) - 1)
38			#define OOC_DATAIDX_MAX ((1L << OOC_DATAIDX_BITS) - 2)
39			#define OOC_OCTCNT_MAX UINT8_MAX
40
41			/* Reserved values for above */
42			#define OOC_DATAIDX_ERR (OOC_DATAIDX_MAX + 1)
43
44			/* Block size for node allocation (8k) */
45			#define OOC_BLKSIZE (1L << 13)
46
47
48	greg	2.1
49	rschregle	2.3	/* ===================================================================
50			* UTILZ
51			* =================================================================== */
52	greg	2.1
53	rschregle	2.3	/* Test/set leaf flag for node n */
54			#define OOC_ISLEAF(n) ((n) -> node.type)
55			#define OOC_SETLEAF(n) ((n) -> node.type = 1)
56
57			/* Test/set branch bit for octant k in node n */
58			#define OOC_ISBRANCH(n,k) (!OOC_ISLEAF(n) && (n) -> node.branch & 1 << (k))
59			#define OOC_SETBRANCH(n,k) ((n) -> node.branch \|= 1 << (k))
60
61			/* Return index to node's 1st kid */
62			#define OOC_KID1(o,n) (!OOC_ISLEAF(n) ? (o)->nodes + (n)->node.kid \
63			: NULL)
64
65			/* Get index to last node in octree; -1 indicates empty octree */
66			#define OOC_ROOTIDX(o) ((o) -> nodes && (o) -> numNodes > 0 \
67			? (o) -> numNodes - 1 : -1)
68
69			/* Get octree root; this is at the end of the node array! */
70			#define OOC_ROOT(o) (OOC_ROOTIDX(o) >= 0 \
71			? (o) -> nodes + OOC_ROOTIDX(o) : NULL)
72
73			/* Copy node to octree root */
74			#define OOC_SETROOT(o,n) (memcpy(OOC_ROOT(o), (n), sizeof(OOC_Node)))
75
76			/* Set all node fields to 0 */
77			#define OOC_CLEARNODE(n) (memset((n), 0, sizeof(OOC_Node)))
78	greg	2.1
79	rschregle	2.3	/* Modify origin o for octant k of size s */
80			#define OOC_OCTORIGIN(o,k,s) ((o) [0] += (s) * ((k) & 1), \
81			(o) [1] += (s) * ((k) >> 1 & 1), \
82			(o) [2] += (s) * ((k) >> 2 & 1))
83
84			/* Get num records stored in node (also handles leaves and NULL pointer) */
85			#define OOC_DATACNT(n) \
86			((n) ? OOC_ISLEAF(n) ? (n) -> leaf.num [0] + (n) -> leaf.num [1] + \
87			(n) -> leaf.num [2] + (n) -> leaf.num [3] + \
88			(n) -> leaf.num [4] + (n) -> leaf.num [5] + \
89			(n) -> leaf.num [6] + (n) -> leaf.num [7] \
90			: (n) -> node.num \
91			: 0)
92
93			/* Shortcuts for morton code from key and data record */
94			#define OOC_KEY2MORTON(k, o) OOC_Key2Morton((k), (o) -> org, \
95			(o) -> mortonScale)
96			#define OOC_REC2MORTON(r, o) OOC_Key2Morton((o) -> key(r), (o) -> org, \
97			(o) -> mortonScale)
98
99
100
101			/* ===================================================================
102			* DATA TYPEZ
103			* =================================================================== */
104
105			/* Octree node */
106			typedef struct {
107			union {
108			struct {
109			/* Interior node (node.type = 0) with:
110			node.kid = index to 1st child node in octree array (a.k.a
111			"Number One Son"), immediately followed by its
112			nonzero siblings as indicated by branch
113			node.num = num records stored in this subtree,
114			node.branch = branch bitmask indicating nonzero kid nodes */
115			char type : 1;
116			OOC_NodeIdx kid : OOC_NODEIDX_BITS;
117			OOC_DataIdx num : OOC_DATAIDX_BITS;
118			uint8_t branch;
119
120			/* NOTE that we can't make the kid's index relative to parent
121			* (which would be more compact), since we don't know the
122			* parent's index a priori during the bottom-up construction! */
123			} node;
124
125			struct {
126			/* Leaf node (leaf.type = node.type = 1 with:
127			leaf.num [k] = num records stored in octant k */
128			char type : 1;
129			OOC_OctCnt num [8];
130			} leaf;
131			};
132			} OOC_Node;
133
134
135
136			/* Top level octree container */
137			typedef struct {
138			FVECT org, bound; /* Cube origin (min. XYZ), size, and
139			resulting bounds (max. XYZ) */
140			RREAL size,
141			(key)(const void); / Callback for data rec coords */
142			RREAL mortonScale; /* Scale factor for generating Morton
143			codes from coords */
144			OOC_Node nodes; / Pointer to node array */
145			/* *************************************
146			* ** NODES ARE STORED IN POSTFIX **
147			* ** ORDER, I.E. ROOT IS LAST! **
148			* *************************************/
149			OOC_DataIdx numData; /* Num records in leaves */
150			OOC_NodeIdx maxNodes, /* Num currently allocated nodes */
151			numNodes; /* Num used nodes (<= maxNodes) */
152			unsigned recSize, /* Size of data record in bytes */
153			leafMax, /* Max #records per leaf (for build) */
154			maxDepth; /* Max subdivision depth (for build) */
155			FILE leafFile; / File containing data in leaves */
156			OOC_Cache cache; / I/O cache for leafFile */
157			} OOC_Octree;
158
159			/* DOAN' FORGET: NODES IN *POSTFIX* ORDAH!!! */
160
161	greg	2.4	#ifdef __cplusplus
162			extern "C" {
163			#endif
164	rschregle	2.3
165
166			/* ===================================================================
167			* FUNKZ
168			* =================================================================== */
169
170			/* Init empty octree */
171			void OOC_Null (OOC_Octree *oct);
172
173
174			/* Initialises octree for records of size recSize with 3D coordinates,
175			* accessed via key() callback. The octree's bounding box is defined by
176			* its origin org and size per axis, and must contain all keys. The
177			* octree is associated with the specified leaf file containing the
178			* records in Morton order */
179			void OOC_Init (OOC_Octree *oct, unsigned recSize, FVECT org, RREAL size,
180			RREAL (key)(const void), FILE leafFile);
181
182
183			/* Allocate new octree node, enlarge array if necessary. Returns pointer
184			to new node or NULL if failed. */
185			OOC_Node NewNode (OOC_Octree oct);
186
187
188			/* Reads indexed data record from leaf file and copies it to rec, else
189			* returns -1 on failure */
190			int OOC_GetData (OOC_Octree oct, OOC_DataIdx idx, void rec);
191
192	greg	2.1
193	rschregle	2.3	/* Appends octree nodes to specified file along with metadata. Uses
194			* RADIANCE's portable I/O routines. Returns 0 on success, else -1. */
195			int OOC_SaveOctree (const OOC_Octree oct, FILE nodeFile);
196
197
198			/* Load octree nodes and metadata from nodeFile and associate with
199			* records in leafFile. Uses RADIANCE's portable I/O routines. Returns
200			* 0 on success, else -1. */
201			int OOC_LoadOctree (OOC_Octree oct, FILE nodeFile,
202			RREAL (key)(const void), FILE leafFile);
203
204			#ifdef DEBUG_OOC
205			/* Traverse tree & check for valid nodes; oct -> leafFile must be open;
206			* return 0 if ok, otherwise -1 */
207			int OOC_Check (OOC_Octree oct, const OOC_Node node,
208			FVECT org, RREAL size, OOC_DataIdx dataIdx);
209	greg	2.1	#endif
210
211	rschregle	2.3	/* Check whether key lies within bounding box defined by org and size */
212			int OOC_InBBox (const OOC_Octree *oct, const FVECT org, RREAL size,
213			const FVECT key);
214
215			/* Return index of octant containing key and corresponding origin if
216			* nuOrg = NULL, or -1 if key lies outside all octants. Size is already
217			* assumed to be halved, i.e. corresponding to the length of an octant
218			* axis. */
219			int OOC_Branch (const OOC_Octree *oct, const FVECT org, RREAL size,
220			const FVECT key, FVECT nuOrg);
221
222			/* Optimised version of OOC_Branch() with precomputed key Morton code */
223			int OOC_BranchZ (const OOC_Octree *oct, const FVECT org, RREAL size,
224			OOC_MortonIdx keyZ, FVECT nuOrg);
225
226			/* For a given octree node, return the sum of the data counters for kids
227			* [0..k-1]. On return, the node either points to the k'th kid, or
228			* NULL if the kid is nonexistent or the node is a leaf */
229			OOC_DataIdx OOC_GetKid (const OOC_Octree oct, OOC_Node *node,
230			unsigned k);
231
232			/* Self-destruct */
233			void OOC_Delete (OOC_Octree *oct);
234
235	greg	2.4	#ifdef __cplusplus
236			}
237			#endif
238
239	rschregle	2.3	/* DID WE MENTION NODES ARE IN POSTFIX ORDAH? */
240	greg	2.1	#endif