svbsp.c

   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 #ifdef USEMALLOC
   6 #include "string.h"
   7 #define Mem_Alloc(p,s) malloc(s)
   8 #define Mem_Free free
   9 #else
  10 #include "quakedef.h"
  11 #endif
  12 #include "polygon.h"
  13 #include "svbsp.h"
  14
  15 #define MAX_SVBSP_POLYGONPOINTS 64
  16 #define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
  17
  18 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
  19 {
  20         memset(b, 0, sizeof(*b));
  21         b->origin[0] = origin[0];
  22         b->origin[1] = origin[1];
  23         b->origin[2] = origin[2];
  24         b->numnodes = 3;
  25         b->maxnodes = maxnodes;
  26         b->nodes = nodes;
  27         b->ranoutofnodes = 0;
  28         b->stat_occluders_rejected = 0;
  29         b->stat_occluders_accepted = 0;
  30         b->stat_occluders_fragments_accepted = 0;
  31         b->stat_occluders_fragments_rejected = 0;
  32         b->stat_queries_rejected = 0;
  33         b->stat_queries_accepted = 0;
  34         b->stat_queries_fragments_accepted = 0;
  35         b->stat_queries_fragments_rejected = 0;
  36
  37         // the bsp tree must be initialized to have two perpendicular splits axes
  38         // through origin, otherwise the polygon insertions would affect the
  39         // opposite side of the tree, which would be disasterous.
  40         //
  41         // so this code has to make 3 nodes and 4 leafs, and since the leafs are
  42         // represented by empty/solid state numbers in this system rather than
  43         // actual structs, we only need to make the 3 nodes.
  44
  45         // root node
  46         // this one splits the world into +X and -X sides
  47         b->nodes[0].plane[0] = 1;
  48         b->nodes[0].plane[1] = 0;
  49         b->nodes[0].plane[2] = 0;
  50         b->nodes[0].plane[3] = origin[0];
  51         b->nodes[0].parent = -1;
  52         b->nodes[0].children[0] = 1;
  53         b->nodes[0].children[1] = 2;
  54
  55         // +X side node
  56         // this one splits the +X half of the world into +Y and -Y
  57         b->nodes[1].plane[0] = 0;
  58         b->nodes[1].plane[1] = 1;
  59         b->nodes[1].plane[2] = 0;
  60         b->nodes[1].plane[3] = origin[1];
  61         b->nodes[1].parent = 0;
  62         b->nodes[1].children[0] = -1;
  63         b->nodes[1].children[1] = -1;
  64
  65         // -X side node
  66         // this one splits the -X half of the world into +Y and -Y
  67         b->nodes[2].plane[0] = 0;
  68         b->nodes[2].plane[1] = 1;
  69         b->nodes[2].plane[2] = 0;
  70         b->nodes[2].plane[3] = origin[1];
  71         b->nodes[2].parent = 0;
  72         b->nodes[2].children[0] = -1;
  73         b->nodes[2].children[1] = -1;
  74 }
  75
  76 static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const double *points, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
  77 {
  78         // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
  79         // describing the occluder polygon's shadow volume
  80         int i, j, p, basenum;
  81         svbsp_node_t *node;
  82
  83         // if there aren't enough nodes remaining, skip it
  84         if (b->numnodes + numpoints + 1 >= b->maxnodes)
  85         {
  86                 b->ranoutofnodes = 1;
  87                 return;
  88         }
  89
  90         // add one node per side, then the actual occluding face node
  91
  92         // thread safety notes:
  93         // DO NOT multithread insertion, it could be made 'safe' but the results
  94         // would be inconsistent.
  95         //
  96         // it is completely safe to multithread queries in all cases.
  97         //
  98         // if an insertion is occurring the query will give intermediate results,
  99         // being blocked by some volumes but not others, which is perfectly okay
 100         // for visibility culling intended only to reduce rendering work
 101
 102         // note down the first available nodenum for the *parentnodenumpointer
 103         // line which is done last to allow multithreaded queries during an
 104         // insertion
 105         basenum = b->numnodes;
 106         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
 107         {
 108 #if 1
 109                 // see if a parent plane describes this side
 110                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
 111                 {
 112                         double *parentnodeplane = b->nodes[j].plane;
 113                         if (fabs(DotProduct(b->origin     , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 114                          && fabs(DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 115                          && fabs(DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
 116                                 break;
 117                 }
 118                 if (j >= 0)
 119                         continue; // already have a matching parent plane
 120 #endif
 121
 122                 // create a side plane
 123                 // anything infront of this is not inside the shadow volume
 124                 node = b->nodes + b->numnodes++;
 125                 TriangleNormal(b->origin, points + p * 3, points + i * 3, node->plane);
 126                 VectorNormalize(node->plane);
 127                 node->plane[3] = DotProduct(node->plane, b->origin);
 128                 // we need to flip the plane if it puts any part of the polygon on the
 129                 // wrong side
 130                 // (in this way this code treats all polygons as double sided)
 131                 //
 132                 // because speed is important this stops as soon as it finds proof
 133                 // that the orientation is right or wrong
 134                 // (we know that the plane is on one edge of the polygon, so there is
 135                 // never a case where points lie on both sides, so the first hint is
 136                 // sufficient)
 137                 for (j = 0;j < numpoints;j++)
 138                 {
 139                         double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
 140                         if (d < -SVBSP_CLIP_EPSILON)
 141                                 break;
 142                         if (d > SVBSP_CLIP_EPSILON)
 143                         {
 144                                 node->plane[0] *= -1;
 145                                 node->plane[1] *= -1;
 146                                 node->plane[2] *= -1;
 147                                 node->plane[3] *= -1;
 148                                 break;
 149                         }
 150                 }
 151                 node->parent = parentnodenum;
 152                 node->children[0] = -1; // empty
 153                 node->children[1] = -1; // empty
 154                 // link this child into the tree
 155                 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
 156                 // now point to the child pointer for the next node to update later
 157                 parentnodenumpointer = &node->children[1];
 158         }
 159
 160 #if 1
 161         // see if a parent plane describes the face plane
 162         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
 163         {
 164                 double *parentnodeplane = b->nodes[j].plane;
 165                 if (fabs(DotProduct(points    , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 166                  && fabs(DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 167                  && fabs(DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
 168                         break;
 169         }
 170         if (j < 0)
 171 #endif
 172         {
 173                 // add the face-plane node
 174                 // infront is empty, behind is shadow
 175                 node = b->nodes + b->numnodes++;
 176                 TriangleNormal(points, points + 3, points + 6, node->plane);
 177                 VectorNormalize(node->plane);
 178                 node->plane[3] = DotProduct(node->plane, points);
 179                 // this is a flip check similar to the one above
 180                 // this one checks if the plane faces the origin, if not, flip it
 181                 if (DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
 182                 {
 183                         node->plane[0] *= -1;
 184                         node->plane[1] *= -1;
 185                         node->plane[2] *= -1;
 186                         node->plane[3] *= -1;
 187                 }
 188                 node->parent = parentnodenum;
 189                 node->children[0] = -1; // empty
 190                 node->children[1] = -2; // shadow
 191                 // link this child into the tree
 192                 // (with the addition of this node, queries will now be culled by it)
 193                 *parentnodenumpointer = (int)(node - b->nodes);
 194         }
 195 }
 196
 197 static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, 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)
 198 {
 199         int i;
 200         int frontnumpoints, backnumpoints;
 201         double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
 202         if (numpoints < 3)
 203                 return 0;
 204         // recurse through plane nodes
 205         while (*parentnodenumpointer >= 0)
 206         {
 207                 // do a quick check to see if there is any need to split the polygon
 208                 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
 209                 parentnodenum = *parentnodenumpointer;
 210 #if 1
 211                 if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
 212                 {
 213                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
 214                         if (i == numpoints)
 215                         {
 216                                 // no need to split, just go to one side
 217                                 parentnodenumpointer = &node->children[0];
 218                                 continue;
 219                         }
 220                 }
 221                 else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
 222                 {
 223                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
 224                         if (i == numpoints)
 225                         {
 226                                 // no need to split, just go to one side
 227                                 parentnodenumpointer = &node->children[1];
 228                                 continue;
 229                         }
 230                 }
 231 #endif
 232                 // at this point we know it crosses the plane, so we need to split it
 233                 PolygonD_Divide(numpoints, points, node->plane[0], node->plane[1], node->plane[2], node->plane[3], SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, frontpoints, &frontnumpoints, MAX_SVBSP_POLYGONPOINTS, backpoints, &backnumpoints, NULL);
 234                 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
 235                         frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
 236                 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
 237                         backnumpoints = MAX_SVBSP_POLYGONPOINTS;
 238                 // recurse the sides and return the resulting bit flags
 239                 i = 0;
 240                 if (frontnumpoints >= 3)
 241                         i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 242                 if (backnumpoints >= 3)
 243                         i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 244                 return i;
 245         }
 246         // leaf node
 247         if (*parentnodenumpointer == -1)
 248         {
 249                 // empty leaf node; and some geometry survived
 250                 // if inserting an occluder, replace this empty leaf with a shadow volume
 251 #if 0
 252                 for (i = 0;i < numpoints-2;i++)
 253                 {
 254                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
 255                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
 256                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
 257                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
 258                         Debug_PolygonEnd();
 259                 }
 260 #endif
 261                 if (insertoccluder)
 262                 {
 263                         b->stat_occluders_fragments_accepted++;
 264                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 265                 }
 266                 else
 267                         b->stat_queries_fragments_accepted++;
 268                 if (fragmentcallback)
 269                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
 270                 return 2;
 271         }
 272         else
 273         {
 274                 // otherwise it's a solid leaf which destroys all polygons inside it
 275                 if (insertoccluder)
 276                         b->stat_occluders_fragments_rejected++;
 277                 else
 278                         b->stat_queries_fragments_rejected++;
 279 #if 0
 280                 for (i = 0;i < numpoints-2;i++)
 281                 {
 282                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
 283                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
 284                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
 285                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
 286                         Debug_PolygonEnd();
 287                 }
 288 #endif
 289         }
 290         return 1;
 291 }
 292
 293 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)
 294 {
 295         int i;
 296         int nodenum;
 297         // don't even consider an empty polygon
 298         if (numpoints < 3)
 299                 return 0;
 300 #if 0
 301 //if (insertoccluder)
 302         for (i = 0;i < numpoints-2;i++)
 303         {
 304                 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
 305                 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
 306                 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
 307                 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
 308                 Debug_PolygonEnd();
 309         }
 310 #endif
 311         nodenum = 0;
 312         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 313         if (insertoccluder)
 314         {
 315                 if (i & 2)
 316                         b->stat_occluders_accepted++;
 317                 else
 318                         b->stat_occluders_rejected++;
 319         }
 320         else
 321         {
 322                 if (i & 2)
 323                         b->stat_queries_accepted++;
 324                 else
 325                         b->stat_queries_rejected++;
 326         }
 327         return i;
 328 }
 329