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
6 #include <math.h>
7 #include <string.h>
8 #include "svbsp.h"
9 #include "polygon.h"
11 #define MAX_SVBSP_POLYGONPOINTS 64
12 #define SVBSP_CLIP_EPSILON (1.0f / 1024.0f)
14 #define SVBSP_DotProduct(a,b) ((a)*(b)+(a)*(b)+(a)*(b))
16 typedef struct svbsp_polygon_s
17 {
18         float points[MAX_SVBSP_POLYGONPOINTS];
19         //unsigned char splitflags[MAX_SVBSP_POLYGONPOINTS];
20         int facesplitflag;
21         int numpoints;
22 }
23 svbsp_polygon_t;
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 = (p1 - p2) * (p3 - p2) - (p1 - p2) * (p3 - p2);
30         plane4f = (p1 - p2) * (p3 - p2) - (p1 - p2) * (p3 - p2);
31         plane4f = (p1 - p2) * (p3 - p2) - (p1 - p2) * (p3 - p2);
32         plane4f = 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 *= ilength;
38         plane4f *= ilength;
39         plane4f *= ilength;
40         plane4f *= ilength;
41 }
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, pdist, ndist;
47         const float *nextpoint;
48         const float *points = poly->points;
49         float *outfront = front->points;
50         float *outback = back->points;
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;
59                         outfront[frontcount*3+1] = points;
60                         outfront[frontcount*3+2] = points;
61                         frontcount++;
62                 }
63                 if (!(sides[i] & 1))
64                 {
65                         outback[backcount*3+0] = points;
66                         outback[backcount*3+1] = points;
67                         outback[backcount*3+2] = points;
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 = points * ifrac + frac * nextpoint;
83                         c = points * ifrac + frac * nextpoint;
84                         c = points * ifrac + frac * nextpoint;
85                         outfront[frontcount*3+0] = c;
86                         outfront[frontcount*3+1] = c;
87                         outfront[frontcount*3+2] = c;
88                         frontcount++;
89                         outback[backcount*3+0] = c;
90                         outback[backcount*3+1] = c;
91                         outback[backcount*3+2] = c;
92                         backcount++;
93                 }
94         }
95         front->numpoints = frontcount;
96         back->numpoints = backcount;
97 }
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 = origin;
103         b->origin = origin;
104         b->origin = origin;
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;
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.
126         // root node
127         // this one splits the world into +X and -X sides
128         b->nodes.plane = 1;
129         b->nodes.plane = 0;
130         b->nodes.plane = 0;
131         b->nodes.plane = origin;
132         b->nodes.parent = -1;
133         b->nodes.children = 1;
134         b->nodes.children = 2;
136         // +X side node
137         // this one splits the +X half of the world into +Y and -Y
138         b->nodes.plane = 0;
139         b->nodes.plane = 1;
140         b->nodes.plane = 0;
141         b->nodes.plane = origin;
142         b->nodes.parent = 0;
143         b->nodes.children = -1;
144         b->nodes.children = -1;
146         // -X side node
147         // this one splits the -X half of the world into +Y and -Y
148         b->nodes.plane = 0;
149         b->nodes.plane = 1;
150         b->nodes.plane = 0;
151         b->nodes.plane = origin;
152         b->nodes.parent = 0;
153         b->nodes.children = -1;
154         b->nodes.children = -1;
155 }
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;
164         // points and lines are valid testers but not occluders
165         if (poly->numpoints < 3)
166                 return;
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         }
175         // add one node per side, then the actual occluding face node
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
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) < SVBSP_CLIP_EPSILON
199                          && fabs(SVBSP_DotProduct(poly->points[i], parentnodeplane) - parentnodeplane) < SVBSP_CLIP_EPSILON
200                          && fabs(SVBSP_DotProduct(b->origin      , parentnodeplane) - parentnodeplane) < 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;
227                         if (d < -SVBSP_CLIP_EPSILON)
228                                 break;
229                         if (d > SVBSP_CLIP_EPSILON)
230                         {
231                                 node->plane *= -1;
232                                 node->plane *= -1;
233                                 node->plane *= -1;
234                                 node->plane *= -1;
235                                 break;
236                         }
237                 }
238                 node->parent = parentnodenum;
239                 node->children = -1; // empty
240                 node->children = -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;
245         }
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, poly->points, poly->points);
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 < -SVBSP_CLIP_EPSILON)
259                 {
260                         node->plane *= -1;
261                         node->plane *= -1;
262                         node->plane *= -1;
263                         node->plane *= -1;
264                 }
265                 node->parent = parentnodenum;
266                 node->children = -1; // empty
267                 node->children = -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 }
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;
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 = node->plane;
296                 plane = node->plane;
297                 plane = node->plane;
298                 plane = node->plane;
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;
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;
329                         continue;
330                 case 1:
331                         // no need to split, just go to one side
332                         parentnodenumpointer = &node->children;
333                         continue;
334                 case 2:
335                         // no need to split, just go to one side
336                         parentnodenumpointer = &node->children;
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, plane, plane, plane, plane, SVBSP_CLIP_EPSILON, MAX_SVBSP_POLYGONPOINTS, front.points, &front.numpoints, MAX_SVBSP_POLYGONPOINTS, back.points, &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, *parentnodenumpointer, &front, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
353                         i |= SVBSP_AddPolygonNode(b, &node->children, *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], poly->points[  0], poly->points[  0], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
367                         Debug_PolygonVertex(poly->points[i+1], poly->points[i+1], poly->points[i+1], 0.0f, 0.0f, 0.25f, 0.0f, 0.0f, 1.0f);
368                         Debug_PolygonVertex(poly->points[i+2], poly->points[i+2], poly->points[i+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);
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], poly->points[  0], poly->points[  0], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
395                         Debug_PolygonVertex(poly->points[i+1], poly->points[i+1], poly->points[i+1], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
396                         Debug_PolygonVertex(poly->points[i+2], poly->points[i+2], poly->points[i+2], 0.0f, 0.0f, 0.0f, 0.0f, 0.25f, 1.0f);
397                         Debug_PolygonEnd();
398                 }
399 #endif
400         }
401         return 1;
402 }
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] = points[i*3+0];
417                 poly.points[i] = points[i*3+1];
418                 poly.points[i] = 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], poly.points[  0], poly.points[  0], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
428                 Debug_PolygonVertex(poly.points[i+1], poly.points[i+1], poly.points[i+1], 0.0f, 0.0f, 0.0f, 0.25f, 0.0f, 1.0f);
429                 Debug_PolygonVertex(poly.points[i+2], poly.points[i+2], poly.points[i+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 }