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         BIH_LEAF = 3,
  22 }
  23 bih_nodetype_t;
  24
  25 typedef struct bih_node_s
  26 {
  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?
  30         float mins[3];
  31         float maxs[3];
  32         // < 0 is a leaf index (-1-leafindex), >= 0 is another node index (always >= this node's index)
  33         int front;
  34         int back;
  35         // interval of children
  36         float frontmin; // children[0]
  37         float backmax; // children[1]
  38 }
  39 bih_node_t;
  40
  41 typedef struct bih_leaf_s
  42 {
  43         bih_nodetype_t type; // = BIH_LEAF
  44         float mins[3];
  45         float maxs[3];
  46         // data past this point is generic and entirely up to the caller...
  47         int textureindex;
  48         int itemindex; // triangle or brush index
  49 }
  50 bih_leaf_t;
  51
  52 typedef struct bih_s
  53 {
  54         // permanent fields
  55         // leafs are constructed by caller before calling BIH_Build
  56         int numleafs;
  57         bih_leaf_t *leafs;
  58         // nodes are constructed by BIH_Build
  59         int numnodes;
  60         bih_node_t *nodes;
  61         int rootnode; // 0 if numnodes > 0, -1 otherwise
  62         // bounds calculated by BIH_Build
  63         float mins[3];
  64         float maxs[3];
  65
  66         // fields used only during BIH_Build:
  67         int maxnodes;
  68         int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
  69         int *leafsort;
  70         int *leafsortscratch;
  71 }
  72 bih_t;
  73
  74 int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);
  75
  76 #endif