| 1 |
– |
#ifndef OOC_OCT_H |
| 2 |
– |
#define OOC_OCT_H |
| 3 |
– |
|
| 1 |
|
/* |
| 2 |
< |
================================================================== |
| 2 |
> |
====================================================================== |
| 3 |
|
Out-of-core octree data structure |
| 4 |
|
|
| 5 |
|
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
| 6 |
< |
(c) Fraunhofer Institute for Solar Energy Systems, |
| 7 |
< |
Lucerne University of Applied Sciences & Arts |
| 8 |
< |
================================================================== |
| 6 |
> |
(c) Lucerne University of Applied Sciences and Arts, |
| 7 |
> |
supported by the Swiss National Science Foundation (SNSF, #147053) |
| 8 |
> |
====================================================================== |
| 9 |
|
|
| 10 |
|
$Id$ |
| 11 |
|
*/ |
| 12 |
|
|
| 13 |
|
|
| 14 |
< |
#include "fvect.h" |
| 14 |
> |
#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 |
|
|
| 20 |
– |
/* Pointer to i-th record */ |
| 21 |
– |
#define OOC_RECPTR(p,i) ((p) + |
| 22 |
|
|
| 23 |
< |
/* Default data block size (8k) */ |
| 24 |
< |
#define OOC_BLKBITS 13 |
| 25 |
< |
#define OOC_BLKSIZE (1 << OOC_BLKBITS) |
| 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 |
|
|
| 27 |
– |
/* Index to data block and index within the block */ |
| 28 |
– |
#define OOC_IDXTOBLK(i) ((i) >> OOC_BLKBITS) |
| 29 |
– |
#define OOC_IDXINBLK(i) ((i) & (1 << OOC_BLKBITS) - 1) |
| 47 |
|
|
| 31 |
– |
/* Check for block overflow when adding node |
| 32 |
– |
#define OOC_BLKFULL(n) ((!(n) * sizeof(OOC_Node) % OOC_BLKSIZE) */ |
| 48 |
|
|
| 49 |
< |
/* Check for internal node, empty node, interior leaf, or terminal node |
| 50 |
< |
(8 leaves) */ |
| 51 |
< |
#define OOC_INTNODE(n) ((n).num > 0 && (n).kid > 0) |
| 37 |
< |
#define OOC_EMPTYNODE(n) (!(n).num) |
| 38 |
< |
#define OOC_INTLEAF(n) ((n).kid < 0) |
| 39 |
< |
#define OOC_TERMNODE(n) ((n).num < 0) |
| 49 |
> |
/* =================================================================== |
| 50 |
> |
* UTILZ |
| 51 |
> |
* =================================================================== */ |
| 52 |
|
|
| 53 |
< |
/* Return record count and kid/leaf index for node */ |
| 54 |
< |
#define OOC_NUMREC(n) abs((n).num) |
| 55 |
< |
#define OOC_KID(n) abs((n).kid) |
| 53 |
> |
/* 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 |
< |
/* Check for loaded data block */ |
| 77 |
< |
#define OOC_LOADED(b) ((b).dataBlk != NULL) |
| 76 |
> |
/* Set all node fields to 0 */ |
| 77 |
> |
#define OOC_CLEARNODE(n) (memset((n), 0, sizeof(OOC_Node))) |
| 78 |
|
|
| 79 |
< |
/* (Mutually exclusive) operations on octree to be specified as flags */ |
| 80 |
< |
#define OOC_INSERT 1 |
| 81 |
< |
#define OOC_SEARCH 2 |
| 79 |
> |
/* 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 |
< |
/* Counter for records at leaves (2 bytes) */ |
| 85 |
< |
typedef unsigned short OOC_Leaf; |
| 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 |
< |
/* Node and record index type */ |
| 94 |
< |
typedef int OOC_Idx; |
| 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 |
|
|
| 58 |
– |
/* Octree node */ |
| 59 |
– |
typedef struct { |
| 60 |
– |
/* |
| 61 |
– |
For interior nodes (num > 0): |
| 62 |
– |
num = num records stored in this (sub)tree, |
| 63 |
– |
kid = index to 1st child node (immediately followed by its |
| 64 |
– |
siblings) in octree array. |
| 65 |
– |
|
| 66 |
– |
For interior leaves (kid < 0): |
| 67 |
– |
num = num records stored in leaf, |
| 68 |
– |
abs(kid) = index to single leaf, no siblings. |
| 69 |
– |
|
| 70 |
– |
For terminal nodes (num < 0): |
| 71 |
– |
abs(num) = num records stored in leaves, |
| 72 |
– |
kid = index to 1st of 8 leaves (immediately followed by its |
| 73 |
– |
siblings) in leaf array. |
| 74 |
– |
*/ |
| 75 |
– |
OOC_Idx num, kid; |
| 76 |
– |
} OOC_Node; |
| 99 |
|
|
| 100 |
|
|
| 101 |
< |
/* Load map entry; points to start of data block of size OOC_BLKSIZE, or |
| 102 |
< |
* NULL if not loaded. LRU counter counts accesses for paging from disk */ |
| 103 |
< |
typedef struct { |
| 104 |
< |
void *dataBlk; |
| 105 |
< |
unsigned long lruCnt; |
| 106 |
< |
} OOC_Load; |
| 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 |
|
|
| 87 |
– |
/* Top level octree container */ |
| 88 |
– |
typedef struct { |
| 89 |
– |
FVECT org; /* Cube origin (min. XYZ) and size */ |
| 90 |
– |
RREAL size; |
| 91 |
– |
OOC_Node *root; /* Pointer to node array */ |
| 92 |
– |
OOC_Idx maxNodes, /* Num currently allocated nodes */ |
| 93 |
– |
numNodes; /* Num used nodes (< maxNodes) */ |
| 94 |
– |
OOC_Load *loadMap; /* Pointer to load map */ |
| 95 |
– |
OOC_Leaf *leaves; /* Pointer to leaf array */ |
| 96 |
– |
unsigned recSize, /* Size of data record in bytes */ |
| 97 |
– |
leafMax, /* Max num records per leaf */ |
| 98 |
– |
maxDepth; /* Max subdivision depth */ |
| 99 |
– |
} OOC_Octree; |
| 134 |
|
|
| 135 |
|
|
| 136 |
< |
/* Initialise octree for records of size recSize, return -1 on failure */ |
| 137 |
< |
int OOC_Init (OOC_Octree *oct, unsigned recSize, unsigned leafMax); |
| 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 |
< |
/* Return index of kid containing key, update origin and size accordingly */ |
| 106 |
< |
int OOC_Branch (FVECT key, FVECT org, RREAL *size); |
| 159 |
> |
/* DOAN' FORGET: NODES IN ***POSTFIX*** ORDAH!!! */ |
| 160 |
|
|
| 161 |
< |
/* Return data index to leaf containing key, or -1 if not found */ |
| 162 |
< |
OOC_Idx OOC_Find (OOC_Octree *oct, FVECT key); |
| 161 |
> |
#ifdef __cplusplus |
| 162 |
> |
extern "C" { |
| 163 |
> |
#endif |
| 164 |
|
|
| 111 |
– |
#if 0 |
| 112 |
– |
/* Return pointer to terminal node containing key */ |
| 113 |
– |
OOC_Node *FindNode (OOC_Octree *oct, FVECT key); |
| 165 |
|
|
| 166 |
< |
/* Return index into data block for leaf containing key */ |
| 167 |
< |
OOC_Idx FindLeaf (OOC_Leaf *leaf, FVECT key); |
| 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 |
> |
|
| 193 |
> |
/* 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 |
|
#endif |
| 210 |
|
|
| 211 |
+ |
/* 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 |
+ |
#ifdef __cplusplus |
| 236 |
+ |
} |
| 237 |
+ |
#endif |
| 238 |
+ |
|
| 239 |
+ |
/* DID WE MENTION NODES ARE IN POSTFIX ORDAH? */ |
| 240 |
|
#endif |
