| 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
|
