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