| 1 |
/* |
| 2 |
====================================================================== |
| 3 |
Out-of-core octree data structure |
| 4 |
|
| 5 |
Roland Schregle (roland.schregle@{hslu.ch, gmail.com}) |
| 6 |
(c) Lucerne University of Applied Sciences and Arts, |
| 7 |
supported by the Swiss National Science Foundation (SNSF, #147053) |
| 8 |
====================================================================== |
| 9 |
|
| 10 |
$Id: oococt.h,v 1.22 2015/11/13 17:26:05 taschreg Exp taschreg $ |
| 11 |
*/ |
| 12 |
|
| 13 |
|
| 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 |
|
| 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 |
|
| 50 |
/* =================================================================== |
| 51 |
* UTILZ |
| 52 |
* =================================================================== */ |
| 53 |
|
| 54 |
/* 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 |
|
| 80 |
/* 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 |
|
| 191 |
/* 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 |
#endif |
| 208 |
|
| 209 |
/* 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 |
#endif |
