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 1.22 2015/11/13 17:26:05 taschreg Exp taschreg $
*/


#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!!! */


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

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