fix a small bug regarding bobfall
[divverent/darkplaces.git] / bih.h
1
2 // This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
3
4 // Based on information in http://zach.in.tu-clausthal.de/papers/vrst02.html (in particular vrst02_boxtree.pdf)
5
6 #ifndef BIH_H
7 #define BIH_H
8
9 typedef enum biherror_e
10 {
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)
13 }
14 biherror_t;
15
16 typedef enum bih_nodetype_e
17 {
18         BIH_SPLITX = 0,
19         BIH_SPLITY = 1,
20         BIH_SPLITZ = 2
21 }
22 bih_nodetype_t;
23
24 typedef enum bih_leaftype_e
25 {
26         BIH_BRUSH = 3,
27         BIH_COLLISIONTRIANGLE = 4,
28         BIH_RENDERTRIANGLE = 5
29 }
30 bih_leaftype_t;
31
32 typedef struct bih_node_s
33 {
34         bih_nodetype_t type; // = BIH_SPLITX and similar values
35         // 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)
36         // TODO: move bounds data to parent node and remove it from leafs?
37         float mins[3];
38         float maxs[3];
39         // < 0 is a leaf index (-1-leafindex), >= 0 is another node index (always >= this node's index)
40         int front;
41         int back;
42         // interval of children
43         float frontmin; // children[0]
44         float backmax; // children[1]
45 }
46 bih_node_t;
47
48 typedef struct bih_leaf_s
49 {
50         bih_leaftype_t type; // = BIH_BRUSH And similar values
51         float mins[3];
52         float maxs[3];
53         // data past this point is generic and entirely up to the caller...
54         int textureindex;
55         int surfaceindex;
56         int itemindex; // triangle or brush index
57 }
58 bih_leaf_t;
59
60 typedef struct bih_s
61 {
62         // permanent fields
63         // leafs are constructed by caller before calling BIH_Build
64         int numleafs;
65         bih_leaf_t *leafs;
66         // nodes are constructed by BIH_Build
67         int numnodes;
68         bih_node_t *nodes;
69         int rootnode; // 0 if numnodes > 0, -1 otherwise
70         // bounds calculated by BIH_Build
71         float mins[3];
72         float maxs[3];
73
74         // fields used only during BIH_Build:
75         int maxnodes;
76         int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
77         int *leafsort;
78         int *leafsortscratch;
79 }
80 bih_t;
81
82 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);
83
84 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs);
85
86 #endif