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