2 // This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
4 // Based on information in http://zach.in.tu-clausthal.de/papers/vrst02.html (in particular vrst02_boxtree.pdf)
9 typedef enum biherror_e
11 BIHERROR_OK, // no error, be happy
12 BIHERROR_OUT_OF_NODES, // could not produce complete hierarchy, maxnodes too low (should be roughly half of numleafs)
16 typedef enum bih_nodetype_e
25 typedef struct bih_node_s
27 bih_nodetype_t type; // = BIH_SPLITX and similar values
28 // TODO: store just one float for distance, and have BIH_SPLITMINX and BIH_SPLITMAXX distinctions, to reduce memory footprint and traversal time, as described in the paper (vrst02_boxtree.pdf)
29 // TODO: move bounds data to parent node and remove it from leafs?
32 // < 0 is a leaf index (-1-leafindex), >= 0 is another node index (always >= this node's index)
37 typedef struct bih_leaf_s
39 bih_nodetype_t type; // = BIH_LEAF
42 // data past this point is generic and entirely up to the caller...
44 int itemindex; // triangle or brush index
51 // leafs are constructed by caller before calling BIH_Build
54 // nodes are constructed by BIH_Build
58 // fields used only during BIH_Build:
60 int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
66 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);