1 2 // Shadow Volume BSP code written by Forest "LordHavoc" Hale on 2003-11-06 and placed into public domain. 3 // Modified by LordHavoc (to make it work and other nice things like that) on 2007-01-24 and 2007-01-25 4 5 #ifndef SVBSP_H 6 #define SVBSP_H 7 8 typedef struct svbsp_node_s 9 { 10 // notes: 11 // leaf nodes are not stored, these are always structural nodes 12 // (they always have a plane and two children) 13 // children[] can be -1 for empty leaf or -2 for shadow leaf, >= 0 is node 14 // parent can be -1 if this is the root node, >= 0 is a node 15 int parent, children[2], padding; 16 // node plane, splits space 17 double plane[4]; 18 } 19 svbsp_node_t; 20 21 typedef struct svbsp_s 22 { 23 // lightsource or view origin 24 double origin[3]; 25 // current number of nodes in the svbsp 26 int numnodes; 27 // how big the nodes array is 28 int maxnodes; 29 // first node is the root node 30 svbsp_node_t *nodes; 31 // non-zero indicates that an insertion failed because of lack of nodes 32 int ranoutofnodes; 33 // tree statistics 34 // note: do not use multithreading when gathering statistics! 35 // (the code updating these counters is not thread-safe, increments may 36 // sometimes fail when multithreaded) 37 int stat_occluders_rejected; 38 int stat_occluders_accepted; 39 int stat_occluders_fragments_rejected; 40 int stat_occluders_fragments_accepted; 41 int stat_queries_rejected; 42 int stat_queries_accepted; 43 int stat_queries_fragments_rejected; 44 int stat_queries_fragments_accepted; 45 } 46 svbsp_t; 47 48 // this function initializes a tree to prepare for polygon insertions 49 // 50 // the maxnodes needed for a given polygon set can vary wildly, if there are 51 // not enough maxnodes then later polygons will not be inserted and the field 52 // svbsp_t->ranoutofnodes will be non-zero 53 // 54 // as a rule of thumb the minimum nodes needed for a polygon set is 55 // numpolygons * (averagepolygonvertices + 1) 56 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes); 57 58 // this function tests if any part of a polygon is not in shadow, and returns 59 // non-zero if the polygon is not completely shadowed 60 // 61 // returns 0 if the polygon was rejected (not facing origin or no points) 62 // returns 1 if all of the polygon is in shadow 63 // returns 2 if all of the polygon is unshadowed 64 // returns 3 if some of the polygon is shadowed and some unshadowed 65 // 66 // it also can add a new shadow volume (insertoccluder parameter) 67 // 68 // additionally it calls your fragmentcallback on each unshadowed clipped 69 // part of the polygon 70 // (beware that polygons often get split heavily, even if entirely unshadowed) 71 // 72 // thread-safety notes: do not multi-thread insertions! 73 int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1); 74 75 #endif 76