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
11 #define MAX_SVBSP_POLYGONPOINTS 64
12 #define SVBSP_CLIP_EPSILON (1.0f / 1024.0f)
14 #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
16 typedef struct svbsp_polygon_s
18 float points[MAX_SVBSP_POLYGONPOINTS][3];
19 //unsigned char splitflags[MAX_SVBSP_POLYGONPOINTS];
25 static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *p2, const float *p3)
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));
36 ilength = 1.0f / ilength;
37 plane4f[0] *= ilength;
38 plane4f[1] *= ilength;
39 plane4f[2] *= ilength;
40 plane4f[3] *= ilength;
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)
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)
58 outfront[frontcount*3+0] = points[0];
59 outfront[frontcount*3+1] = points[1];
60 outfront[frontcount*3+2] = points[2];
65 outback[backcount*3+0] = points[0];
66 outback[backcount*3+1] = points[1];
67 outback[backcount*3+2] = points[2];
70 if ((sides[i] | sides[j]) == 3)
72 // don't allow splits if remaining points would overflow point buffer
73 if (frontcount + (count - i) > MAX_SVBSP_POLYGONPOINTS - 1)
75 if (backcount + (count - i) > MAX_SVBSP_POLYGONPOINTS - 1)
77 nextpoint = poly->points[j];
80 frac = pdist / (pdist - ndist);
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];
89 outback[backcount*3+0] = c[0];
90 outback[backcount*3+1] = c[1];
91 outback[backcount*3+2] = c[2];
95 front->numpoints = frontcount;
96 back->numpoints = backcount;
99 void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes)
101 memset(b, 0, sizeof(*b));
102 b->origin[0] = origin[0];
103 b->origin[1] = origin[1];
104 b->origin[2] = origin[2];
106 b->maxnodes = maxnodes;
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.
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.
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;
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;
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;
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)
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;
164 // points and lines are valid testers but not occluders
165 if (poly->numpoints < 3)
168 // if there aren't enough nodes remaining, skip it
169 if (b->numnodes + poly->numpoints + 1 >= b->maxnodes)
171 b->ranoutofnodes = 1;
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.
181 // it is completely safe to multithread queries in all cases.
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
190 basenum = b->numnodes;
191 for (i = 0, p = poly->numpoints - 1;i < poly->numpoints;p = i, i++)
194 // see if a parent plane describes this side
195 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
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)
204 continue; // already have a matching parent plane
207 // skip any sides that were classified as belonging to a parent plane
208 if (poly->splitflags[i])
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
217 // (in this way this code treats all polygons as float sided)
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
224 for (j = 0;j < poly->numpoints;j++)
226 float d = SVBSP_DotProduct(poly->points[j], node->plane) - node->plane[3];
227 if (d < -SVBSP_CLIP_EPSILON)
229 if (d > SVBSP_CLIP_EPSILON)
231 node->plane[0] *= -1;
232 node->plane[1] *= -1;
233 node->plane[2] *= -1;
234 node->plane[3] *= -1;
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];
248 // skip the face plane if it lies on a parent plane
249 if (!poly->facesplitflag)
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)
260 node->plane[0] *= -1;
261 node->plane[1] *= -1;
262 node->plane[2] *= -1;
263 node->plane[3] *= -1;
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);
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)
278 int facesplitflag = poly->facesplitflag;
282 svbsp_polygon_t front;
283 svbsp_polygon_t back;
285 int sides[MAX_SVBSP_POLYGONPOINTS];
286 float dists[MAX_SVBSP_POLYGONPOINTS];
287 if (poly->numpoints < 1)
289 // recurse through plane nodes
290 while (*parentnodenumpointer >= 0)
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
301 for (i = 0;i < poly->numpoints;i++)
303 d = SVBSP_DotProduct(poly->points[i], plane) - plane[3];
305 if (d > SVBSP_CLIP_EPSILON)
307 if (d < -SVBSP_CLIP_EPSILON)
313 // see which side the polygon is on
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
322 // if this is an occluder, it is redundant
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...
328 parentnodenumpointer = &node->children[0];
331 // no need to split, just go to one side
332 parentnodenumpointer = &node->children[0];
335 // no need to split, just go to one side
336 parentnodenumpointer = &node->children[1];
339 // lies on both sides of the plane, we need to split it
341 SVBSP_DividePolygon(poly, plane, &front, &back, dists, sides);
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;
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);
358 if (*parentnodenumpointer == -1)
360 // empty leaf node; and some geometry survived
361 // if inserting an occluder, replace this empty leaf with a shadow volume
363 for (i = 0;i < poly->numpoints-2;i++)
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);
374 b->stat_occluders_fragments_accepted++;
375 SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, poly, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
378 b->stat_queries_fragments_accepted++;
379 if (fragmentcallback)
380 fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, poly->numpoints, poly->points[0]);
385 // otherwise it's a solid leaf which destroys all polygons inside it
387 b->stat_occluders_fragments_rejected++;
389 b->stat_queries_fragments_rejected++;
391 for (i = 0;i < poly->numpoints-2;i++)
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);
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)
408 svbsp_polygon_t poly;
409 // don't even consider an empty polygon
410 // note we still allow points and lines to be tested...
413 poly.numpoints = numpoints;
414 for (i = 0;i < numpoints;i++)
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
423 //if (insertoccluder)
424 for (i = 0;i < poly.numpoints-2;i++)
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);
434 i = SVBSP_AddPolygonNode(b, &nodenum, -1, &poly, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
438 b->stat_occluders_accepted++;
440 b->stat_occluders_rejected++;
445 b->stat_queries_accepted++;
447 b->stat_queries_rejected++;