bih.h

   1
   2 // This code written in 2010 by Ashley Rose Hale (LadyHavoc) (darkplacesengine gmail 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 #define BIH_MAXUNORDEREDCHILDREN 8
  10
  11 typedef enum biherror_e
  12 {
  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)
  15 }
  16 biherror_t;
  17
  18 typedef enum bih_nodetype_e
  19 {
  20         BIH_SPLITX = 0,
  21         BIH_SPLITY = 1,
  22         BIH_SPLITZ = 2,
  23         BIH_UNORDERED = 3,
  24 }
  25 bih_nodetype_t;
  26
  27 typedef enum bih_leaftype_e
  28 {
  29         BIH_BRUSH = 4,
  30         BIH_COLLISIONTRIANGLE = 5,
  31         BIH_RENDERTRIANGLE = 6
  32 }
  33 bih_leaftype_t;
  34
  35 typedef struct bih_node_s
  36 {
  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?
  40         float mins[3];
  41         float maxs[3];
  42         // node indexes of children (always > this node's index)
  43         int front;
  44         int back;
  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];
  50 }
  51 bih_node_t;
  52
  53 typedef struct bih_leaf_s
  54 {
  55         bih_leaftype_t type; // = BIH_BRUSH And similar values
  56         float mins[3];
  57         float maxs[3];
  58         // data past this point is generic and entirely up to the caller...
  59         int textureindex;
  60         int surfaceindex;
  61         int itemindex; // triangle or brush index
  62 }
  63 bih_leaf_t;
  64
  65 typedef struct bih_s
  66 {
  67         // permanent fields
  68         // leafs are constructed by caller before calling BIH_Build
  69         int numleafs;
  70         bih_leaf_t *leafs;
  71         // nodes are constructed by BIH_Build
  72         int numnodes;
  73         bih_node_t *nodes;
  74         int rootnode; // 0 if numnodes > 0, -1 otherwise
  75         // bounds calculated by BIH_Build
  76         float mins[3];
  77         float maxs[3];
  78
  79         // fields used only during BIH_Build:
  80         int maxnodes;
  81         int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
  82         int *leafsort;
  83         int *leafsortscratch;
  84 }
  85 bih_t;
  86
  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);
  88
  89 int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs);
  90
  91 #endif