2 // This code written in 2010 by Ashley Rose Hale (LadyHavoc) (darkplacesengine gmail 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 #define BIH_MAXUNORDEREDCHILDREN 8
11 typedef enum biherror_e
13 BIHERROR_OK, // no error, be happy
14 BIHERROR_OUT_OF_NODES // could not produce complete hierarchy, maxnodes too low (should be roughly half of numleafs)
18 typedef enum bih_nodetype_e
27 typedef enum bih_leaftype_e
30 BIH_COLLISIONTRIANGLE = 5,
31 BIH_RENDERTRIANGLE = 6
35 typedef struct bih_node_s
37 bih_nodetype_t type; // = BIH_SPLITX and similar values
38 // 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)
39 // TODO: move bounds data to parent node and remove it from leafs?
42 // node indexes of children (always > this node's index)
45 // interval of children
46 float frontmin; // children[0]
47 float backmax; // children[1]
48 // BIH_UNORDERED uses this for a list of leafindex (all >= 0), -1 = end of list
49 int children[BIH_MAXUNORDEREDCHILDREN];
53 typedef struct bih_leaf_s
55 bih_leaftype_t type; // = BIH_BRUSH And similar values
58 // data past this point is generic and entirely up to the caller...
61 int itemindex; // triangle or brush index
68 // leafs are constructed by caller before calling BIH_Build
71 // nodes are constructed by BIH_Build
74 int rootnode; // 0 if numnodes > 0, -1 otherwise
75 // bounds calculated by BIH_Build
79 // fields used only during BIH_Build:
81 int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
87 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);
89 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs);