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 // Optimized by LordHavoc on 2009-12-24 and 2009-12-25
   5
   6 #include <math.h>
   7 #include <string.h>
   8 #include "svbsp.h"
   9 #include "polygon.h"
  10
  11 #define MAX_SVBSP_POLYGONPOINTS 64
  12 #define SVBSP_CLIP_EPSILON (1.0f / 1024.0f)
  13
  14 #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
  15
  16 typedef struct svbsp_polygon_s
  17 {
  18         float points[MAX_SVBSP_POLYGONPOINTS][3];
  19         //unsigned char splitflags[MAX_SVBSP_POLYGONPOINTS];
  20         int facesplitflag;
  21         int numpoints;
  22 }
  23 svbsp_polygon_t;
  24
  25 static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *p2, const float *p3)
  26 {
  27         float ilength;
  28         // calculate unnormalized plane
  29         plane4f[0] = (p1[1] - p2[1]) * (p3[2] - p2[2]) - (p1[2] - p2[2]) * (p3[1] - p2[1]);
  30         plane4f[1] = (p1[2] - p2[2]) * (p3[0] - p2[0]) - (p1[0] - p2[0]) * (p3[2] - p2[2]);
  31         plane4f[2] = (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0]);
  32         plane4f[3] = SVBSP_DotProduct(plane4f, p1);
  33         // normalize the plane normal and adjust distance accordingly
  34         ilength = (float)sqrt(SVBSP_DotProduct(plane4f, plane4f));
  35         if (ilength)
  36                 ilength = 1.0f / ilength;
  37         plane4f[0] *= ilength;
  38         plane4f[1] *= ilength;
  39         plane4f[2] *= ilength;
  40         plane4f[3] *= ilength;
  41 }
  42
  43 static void SVBSP_DividePolygon(const svbsp_polygon_t *poly, const float *plane, svbsp_polygon_t *front, svbsp_polygon_t *back, const float *dists, const int *sides)
  44 {
  45         int i, j, count = poly->numpoints, frontcount = 0, backcount = 0;
  46         float frac, ifrac, c[3], pdist, ndist;
  47         const float *nextpoint;
  48         const float *points = poly->points[0];
  49         float *outfront = front->points[0];
  50         float *outback = back->points[0];
  51         for(i = 0;i < count;i++, points += 3)
  52         {
  53                 j = i + 1;
  54                 if (j >= count)
  55                         j = 0;
  56                 if (!(sides[i] & 2))
  57                 {
  58                         outfront[frontcount*3+0] = points[0];
  59                         outfront[frontcount*3+1] = points[1];
  60                         outfront[frontcount*3+2] = points[2];
  61                         frontcount++;
  62                 }
  63                 if (!(sides[i] & 1))
  64                 {
  65                         outback[backcount*3+0] = points[0];
  66                         outback[backcount*3+1] = points[1];
  67                         outback[backcount*3+2] = points[2];
  68                         backcount++;
  69                 }
  70                 if ((sides[i] | sides[j]) == 3)
  71                 {
  72                         // don't allow splits if remaining points would overflow point buffer
  73                         if (frontcount + (count - i) > MAX_SVBSP_POLYGONPOINTS - 1)
  74                                 continue;
  75                         if (backcount + (count - i) > MAX_SVBSP_POLYGONPOINTS - 1)
  76                                 continue;
  77                         nextpoint = poly->points[j];
  78                         pdist = dists[i];
  79                         ndist = dists[j];
  80                         frac = pdist / (pdist - ndist);
  81                         ifrac = 1.0f - frac;
  82                         c[0] = points[0] * ifrac + frac * nextpoint[0];
  83                         c[1] = points[1] * ifrac + frac * nextpoint[1];
  84                         c[2] = points[2] * ifrac + frac * nextpoint[2];
  85                         outfront[frontcount*3+0] = c[0];
  86                         outfront[frontcount*3+1] = c[1];
  87                         outfront[frontcount*3+2] = c[2];
  88                         frontcount++;
  89                         outback[backcount*3+0] = c[0];
  90                         outback[backcount*3+1] = c[1];
  91                         outback[backcount*3+2] = c[2];
  92                         backcount++;
  93                 }
  94         }
  95         front->numpoints = frontcount;
  96         back->numpoints = backcount;
  97 }
  98
  99 void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes)
 100 {
 101         memset(b, 0, sizeof(*b));
 102         b->origin[0] = origin[0];
 103         b->origin[1] = origin[1];
 104         b->origin[2] = origin[2];
 105         b->numnodes = 3;
 106         b->maxnodes = maxnodes;
 107         b->nodes = nodes;
 108         b->ranoutofnodes = 0;
 109         b->stat_occluders_rejected = 0;
 110         b->stat_occluders_accepted = 0;
 111         b->stat_occluders_fragments_accepted = 0;
 112         b->stat_occluders_fragments_rejected = 0;
 113         b->stat_queries_rejected = 0;
 114         b->stat_queries_accepted = 0;
 115         b->stat_queries_fragments_accepted = 0;
 116         b->stat_queries_fragments_rejected = 0;
 117
 118         // the bsp tree must be initialized to have two perpendicular splits axes
 119         // through origin, otherwise the polygon insertions would affect the
 120         // opposite side of the tree, which would be disasterous.
 121         //
 122         // so this code has to make 3 nodes and 4 leafs, and since the leafs are
 123         // represented by empty/solid state numbers in this system rather than
 124         // actual structs, we only need to make the 3 nodes.
 125
 126         // root node
 127         // this one splits the world into +X and -X sides
 128         b->nodes[0].plane[0] = 1;
 129         b->nodes[0].plane[1] = 0;
 130         b->nodes[0].plane[2] = 0;
 131         b->nodes[0].plane[3] = origin[0];
 132         b->nodes[0].parent = -1;
 133         b->nodes[0].children[0] = 1;
 134         b->nodes[0].children[1] = 2;
 135
 136         // +X side node
 137         // this one splits the +X half of the world into +Y and -Y
 138         b->nodes[1].plane[0] = 0;
 139         b->nodes[1].plane[1] = 1;
 140         b->nodes[1].plane[2] = 0;
 141         b->nodes[1].plane[3] = origin[1];
 142         b->nodes[1].parent = 0;
 143         b->nodes[1].children[0] = -1;
 144         b->nodes[1].children[1] = -1;
 145
 146         // -X side node
 147         // this one splits the -X half of the world into +Y and -Y
 148         b->nodes[2].plane[0] = 0;
 149         b->nodes[2].plane[1] = 1;
 150         b->nodes[2].plane[2] = 0;
 151         b->nodes[2].plane[3] = origin[1];
 152         b->nodes[2].parent = 0;
 153         b->nodes[2].children[0] = -1;
 154         b->nodes[2].children[1] = -1;
 155 }
 156
 157 static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, const svbsp_polygon_t *poly, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
 158 {
 159         // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
 160         // describing the occluder polygon's shadow volume
 161         int i, j, p, basenum;
 162         svbsp_node_t *node;
 163
 164         // points and lines are valid testers but not occluders
 165         if (poly->numpoints < 3)
 166                 return;
 167
 168         // if there aren't enough nodes remaining, skip it
 169         if (b->numnodes + poly->numpoints + 1 >= b->maxnodes)
 170         {
 171                 b->ranoutofnodes = 1;
 172                 return;
 173         }
 174
 175         // add one node per side, then the actual occluding face node
 176
 177         // thread safety notes:
 178         // DO NOT multithread insertion, it could be made 'safe' but the results
 179         // would be inconsistent.
 180         //
 181         // it is completely safe to multithread queries in all cases.
 182         //
 183         // if an insertion is occurring the query will give intermediate results,
 184         // being blocked by some volumes but not others, which is perfectly okay
 185         // for visibility culling intended only to reduce rendering work
 186
 187         // note down the first available nodenum for the *parentnodenumpointer
 188         // line which is done last to allow multithreaded queries during an
 189         // insertion
 190         basenum = b->numnodes;
 191         for (i = 0, p = poly->numpoints - 1;i < poly->numpoints;p = i, i++)
 192         {
 193 #if 1
 194                 // see if a parent plane describes this side
 195                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
 196                 {
 197                         float *parentnodeplane = b->nodes[j].plane;
 198                         if (fabs(SVBSP_DotProduct(poly->points[p], parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 199                          && fabs(SVBSP_DotProduct(poly->points[i], parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
 200                          && fabs(SVBSP_DotProduct(b->origin      , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
 201                                 break;
 202                 }
 203                 if (j >= 0)
 204                         continue; // already have a matching parent plane
 205 #endif
 206 #if 0
 207                 // skip any sides that were classified as belonging to a parent plane
 208                 if (poly->splitflags[i])
 209                         continue;
 210 #endif
 211                 // create a side plane
 212                 // anything infront of this is not inside the shadow volume
 213                 node = b->nodes + b->numnodes++;
 214                 SVBSP_PlaneFromPoints(node->plane, b->origin, poly->points[p], poly->points[i]);
 215                 // we need to flip the plane if it puts any part of the polygon on the
 216                 // wrong side
 217                 // (in this way this code treats all polygons as float sided)
 218                 //
 219                 // because speed is important this stops as soon as it finds proof
 220                 // that the orientation is right or wrong
 221                 // (we know that the plane is on one edge of the polygon, so there is
 222                 // never a case where points lie on both sides, so the first hint is
 223                 // sufficient)
 224                 for (j = 0;j < poly->numpoints;j++)
 225                 {
 226                         float d = SVBSP_DotProduct(poly->points[j], node->plane) - node->plane[3];
 227                         if (d < -SVBSP_CLIP_EPSILON)
 228                                 break;
 229                         if (d > SVBSP_CLIP_EPSILON)
 230                         {
 231                                 node->plane[0] *= -1;
 232                                 node->plane[1] *= -1;
 233                                 node->plane[2] *= -1;
 234                                 node->plane[3] *= -1;
 235                                 break;
 236                         }
 237                 }
 238                 node->parent = parentnodenum;
 239                 node->children[0] = -1; // empty
 240                 node->children[1] = -1; // empty
 241                 // link this child into the tree
 242                 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
 243                 // now point to the child pointer for the next node to update later
 244                 parentnodenumpointer = &node->children[1];
 245         }
 246
 247 #if 1
 248         // skip the face plane if it lies on a parent plane
 249         if (!poly->facesplitflag)
 250 #endif
 251         {
 252                 // add the face-plane node
 253                 // infront is empty, behind is shadow
 254                 node = b->nodes + b->numnodes++;
 255                 SVBSP_PlaneFromPoints(node->plane, poly->points[0], poly->points[1], poly->points[2]);
 256                 // this is a flip check similar to the one above
 257                 // this one checks if the plane faces the origin, if not, flip it
 258                 if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
 259                 {
 260                         node->plane[0] *= -1;
 261                         node->plane[1] *= -1;
 262                         node->plane[2] *= -1;
 263                         node->plane[3] *= -1;
 264                 }
 265                 node->parent = parentnodenum;
 266                 node->children[0] = -1; // empty
 267                 node->children[1] = -2; // shadow
 268                 // link this child into the tree
 269                 // (with the addition of this node, queries will now be culled by it)
 270                 *parentnodenumpointer = (int)(node - b->nodes);
 271         }
 272 }
 273
 274 static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, const svbsp_polygon_t *poly, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
 275 {
 276         int i;
 277         int s;
 278         int facesplitflag = poly->facesplitflag;
 279         int bothsides;
 280         float plane[4];
 281         float d;
 282         svbsp_polygon_t front;
 283         svbsp_polygon_t back;
 284         svbsp_node_t *node;
 285         int sides[MAX_SVBSP_POLYGONPOINTS];
 286         float dists[MAX_SVBSP_POLYGONPOINTS];
 287         if (poly->numpoints < 1)
 288                 return 0;
 289         // recurse through plane nodes
 290         while (*parentnodenumpointer >= 0)
 291         {
 292                 // get node info
 293                 parentnodenum = *parentnodenumpointer;
 294                 node = b->nodes + parentnodenum;
 295                 plane[0] = node->plane[0];
 296                 plane[1] = node->plane[1];
 297                 plane[2] = node->plane[2];
 298                 plane[3] = node->plane[3];
 299                 // calculate point dists for clipping
 300                 bothsides = 0;
 301                 for (i = 0;i < poly->numpoints;i++)
 302                 {
 303                         d = SVBSP_DotProduct(poly->points[i], plane) - plane[3];
 304                         s = 0;
 305                         if (d > SVBSP_CLIP_EPSILON)
 306                                 s = 1;
 307                         if (d < -SVBSP_CLIP_EPSILON)
 308                                 s = 2;
 309                         bothsides |= s;
 310                         dists[i] = d;
 311                         sides[i] = s;
 312                 }
 313                 // see which side the polygon is on
 314                 switch(bothsides)
 315                 {
 316                 default:
 317                 case 0:
 318                         // no need to split, this polygon is on the plane
 319                         // this case only occurs for polygons on the face plane, usually
 320                         // the same polygon (inserted twice - once as occluder, once as
 321                         // tester)
 322                         // if this is an occluder, it is redundant
 323                         if (insertoccluder)
 324                                 return 1; // occluded
 325                         // if this is a tester, test the front side, because it is
 326                         // probably the same polygon that created this node...
 327                         facesplitflag = 1;
 328                         parentnodenumpointer = &node->children[0];
 329                         continue;
 330                 case 1:
 331                         // no need to split, just go to one side
 332                         parentnodenumpointer = &node->children[0];
 333                         continue;
 334                 case 2:
 335                         // no need to split, just go to one side
 336                         parentnodenumpointer = &node->children[1];
 337                         continue;
 338                 case 3:
 339                         // lies on both sides of the plane, we need to split it
 340 #if 1
 341                         SVBSP_DividePolygon(poly, plane, &front, &back, dists, sides);
 342 #else
 343                         PolygonF_Divide(poly->numpoints, poly->points[0], plane[0], plane[1], plane[2], plane[3], SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, front.points[0], &front.numpoints, MAX_SVBSP_POLYGONPOINTS, back.points[0], &back.numpoints, NULL);
 344                         if (front.numpoints > MAX_SVBSP_POLYGONPOINTS)
 345                                 front.numpoints = MAX_SVBSP_POLYGONPOINTS;
 346                         if (back.numpoints > MAX_SVBSP_POLYGONPOINTS)
 347                                 back.numpoints = MAX_SVBSP_POLYGONPOINTS;
 348 #endif
 349                         front.facesplitflag = facesplitflag;
 350                         back.facesplitflag = facesplitflag;
 351                         // recurse the sides and return the resulting occlusion flags
 352                         i  = SVBSP_AddPolygonNode(b, &node->children[0], *parentnodenumpointer, &front, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 353                         i |= SVBSP_AddPolygonNode(b, &node->children[1], *parentnodenumpointer, &back , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 354                         return i;
 355                 }
 356         }
 357         // leaf node
 358         if (*parentnodenumpointer == -1)
 359         {
 360                 // empty leaf node; and some geometry survived
 361                 // if inserting an occluder, replace this empty leaf with a shadow volume
 362 #if 0
 363                 for (i = 0;i < poly->numpoints-2;i++)
 364                 {
 365                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
 366                         Debug_PolygonVertex(poly->points[  0][0], poly->points[  0][1], poly->points[  0][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
 367                         Debug_PolygonVertex(poly->points[i+1][0], poly->points[i+1][1], poly->points[i+1][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
 368                         Debug_PolygonVertex(poly->points[i+2][0], poly->points[i+2][1], poly->points[i+2][2], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
 369                         Debug_PolygonEnd();
 370                 }
 371 #endif
 372                 if (insertoccluder)
 373                 {
 374                         b->stat_occluders_fragments_accepted++;
 375                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, poly, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 376                 }
 377                 else
 378                         b->stat_queries_fragments_accepted++;
 379                 if (fragmentcallback)
 380                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, poly->numpoints, poly->points[0]);
 381                 return 2;
 382         }
 383         else
 384         {
 385                 // otherwise it's a solid leaf which destroys all polygons inside it
 386                 if (insertoccluder)
 387                         b->stat_occluders_fragments_rejected++;
 388                 else
 389                         b->stat_queries_fragments_rejected++;
 390 #if 0
 391                 for (i = 0;i < poly->numpoints-2;i++)
 392                 {
 393                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
 394                         Debug_PolygonVertex(poly->points[  0][0], poly->points[  0][1], poly->points[  0][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
 395                         Debug_PolygonVertex(poly->points[i+1][0], poly->points[i+1][1], poly->points[i+1][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
 396                         Debug_PolygonVertex(poly->points[i+2][0], poly->points[i+2][1], poly->points[i+2][2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
 397                         Debug_PolygonEnd();
 398                 }
 399 #endif
 400         }
 401         return 1;
 402 }
 403
 404 int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const float *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const float *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
 405 {
 406         int i;
 407         int nodenum;
 408         svbsp_polygon_t poly;
 409         // don't even consider an empty polygon
 410         // note we still allow points and lines to be tested...
 411         if (numpoints < 1)
 412                 return 0;
 413         poly.numpoints = numpoints;
 414         for (i = 0;i < numpoints;i++)
 415         {
 416                 poly.points[i][0] = points[i*3+0];
 417                 poly.points[i][1] = points[i*3+1];
 418                 poly.points[i][2] = points[i*3+2];
 419                 //poly.splitflags[i] = 0; // this edge is a valid BSP splitter - clipped edges are not (because they lie on a bsp plane)
 420                 poly.facesplitflag = 0; // this face is a valid BSP Splitter - if it lies on a bsp plane it is not
 421         }
 422 #if 0
 423 //if (insertoccluder)
 424         for (i = 0;i < poly.numpoints-2;i++)
 425         {
 426                 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
 427                 Debug_PolygonVertex(poly.points[  0][0], poly.points[  0][1], poly.points[  0][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
 428                 Debug_PolygonVertex(poly.points[i+1][0], poly.points[i+1][1], poly.points[i+1][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
 429                 Debug_PolygonVertex(poly.points[i+2][0], poly.points[i+2][1], poly.points[i+2][2], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
 430                 Debug_PolygonEnd();
 431         }
 432 #endif
 433         nodenum = 0;
 434         i = SVBSP_AddPolygonNode(b, &nodenum, -1, &poly, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
 435         if (insertoccluder)
 436         {
 437                 if (i & 2)
 438                         b->stat_occluders_accepted++;
 439                 else
 440                         b->stat_occluders_rejected++;
 441         }
 442         else
 443         {
 444                 if (i & 2)
 445                         b->stat_queries_accepted++;
 446                 else
 447                         b->stat_queries_rejected++;
 448         }
 449         return i;
 450 }
 451