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