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
10 #define MAX_SVBSP_POLYGONPOINTS 64
11 #define SVBSP_CLIP_EPSILON (1.0f / 1024.0f)
13 #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
15 static void SVBSP_PlaneFromPoints(float *plane4f, const float *p1, const float *p2, const float *p3)
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 = (float)sqrt(SVBSP_DotProduct(plane4f, plane4f));
26 ilength = 1.0f / ilength;
27 plane4f[0] *= ilength;
28 plane4f[1] *= ilength;
29 plane4f[2] *= ilength;
30 plane4f[3] *= ilength;
33 void SVBSP_Init(svbsp_t *b, const float *origin, int maxnodes, svbsp_node_t *nodes)
35 memset(b, 0, sizeof(*b));
36 b->origin[0] = origin[0];
37 b->origin[1] = origin[1];
38 b->origin[2] = origin[2];
40 b->maxnodes = maxnodes;
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;
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.
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.
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;
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;
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;
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)
93 // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
94 // describing the occluder polygon's shadow volume
98 unsigned int sideflags[(MAX_SVBSP_POLYGONPOINTS+31)>>5];
99 float *parentnodeplane;
109 // if there aren't enough nodes remaining, skip it
110 if (b->numnodes + numpoints + 1 >= b->maxnodes)
112 b->ranoutofnodes = 1;
116 // add one node per side, then the actual occluding face node
118 // thread safety notes:
119 // DO NOT multithread insertion, it could be made 'safe' but the results
120 // would be inconsistent.
122 // it is completely safe to multithread queries in all cases.
124 // if an insertion is occurring the query will give intermediate results,
125 // being blocked by some volumes but not others, which is perfectly okay
126 // for visibility culling intended only to reduce rendering work
128 // note down the first available nodenum for the *parentnodenumpointer
129 // line which is done last to allow multithreaded queries during an
131 basenum = b->numnodes;
133 for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
136 // see if a parent plane describes this side
137 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
139 float *parentnodeplane = b->nodes[j].plane;
141 // v[0] = SVBSP_DotProduct(b->origin , parentnodeplane) - parentnodeplane[3];
142 // v[1] = SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3];
143 // v[2] = SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3];
144 // if (SVBSP_DotProduct(v,v) < (SVBSP_CLIP_EPSILON*SVBSP_CLIP_EPSILON))
145 if (fabs(SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
146 && fabs(SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
147 && fabs(SVBSP_DotProduct(b->origin , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
151 continue; // already have a matching parent plane
156 // 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
157 for (i = 0;i < (int)(sizeof(sideflags)/sizeof(sideflags[0]));i++)
159 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
161 parentnodeplane = b->nodes[j].plane;
162 plane[0] = parentnodeplane[0];
163 plane[1] = parentnodeplane[1];
164 plane[2] = parentnodeplane[2];
165 plane[3] = parentnodeplane[3];
167 mindist = plane[3] - SVBSP_CLIP_EPSILON;
168 maxdist = plane[3] + SVBSP_CLIP_EPSILON;
170 // if a parent plane crosses the origin, it is a side plane
171 // if it does not cross the origin, it is a face plane, and thus will
172 // not match any side planes we could add
174 if (fabs(SVBSP_DotProduct(b->origin, plane) - plane[3]) > SVBSP_CLIP_EPSILON)
177 d = SVBSP_DotProduct(b->origin , plane);
178 if (d < mindist || d > maxdist)
181 // classify each side as belonging to this parent plane or not
182 // do a distance check on the last point of the polygon first, and
183 // then one distance check per point, reusing the previous point
184 // distance check to classify this side as being on or off the plane
187 p = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
189 d = SVBSP_DotProduct(points + i * 3, plane);
190 p = d >= mindist && d <= maxdist;
192 for (i = 0;i < numpoints;i++)
195 n = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
197 d = SVBSP_DotProduct(points + i * 3, plane);
198 n = d >= mindist && d <= maxdist;
201 sideflags[i>>5] |= 1<<(i&31);
207 for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
210 // skip any sides that were classified as belonging to a parent plane
211 if (sideflags[i>>5] & (1<<(i&31)))
215 // create a side plane
216 // anything infront of this is not inside the shadow volume
217 node = b->nodes + b->numnodes++;
218 SVBSP_PlaneFromPoints(node->plane, b->origin, points + p * 3, points + i * 3);
219 // we need to flip the plane if it puts any part of the polygon on the
221 // (in this way this code treats all polygons as float sided)
223 // because speed is important this stops as soon as it finds proof
224 // that the orientation is right or wrong
225 // (we know that the plane is on one edge of the polygon, so there is
226 // never a case where points lie on both sides, so the first hint is
228 for (j = 0;j < numpoints;j++)
230 float d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
231 if (d < -SVBSP_CLIP_EPSILON)
233 if (d > SVBSP_CLIP_EPSILON)
235 node->plane[0] *= -1;
236 node->plane[1] *= -1;
237 node->plane[2] *= -1;
238 node->plane[3] *= -1;
242 node->parent = parentnodenum;
243 node->children[0] = -1; // empty
244 node->children[1] = -1; // empty
245 // link this child into the tree
246 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
247 // now point to the child pointer for the next node to update later
248 parentnodenumpointer = &node->children[1];
252 // see if a parent plane describes the face plane
253 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
255 float *parentnodeplane = b->nodes[j].plane;
256 if (fabs(SVBSP_DotProduct(points , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
257 && fabs(SVBSP_DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
258 && fabs(SVBSP_DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
264 // add the face-plane node
265 // infront is empty, behind is shadow
266 node = b->nodes + b->numnodes++;
267 SVBSP_PlaneFromPoints(node->plane, points, points + 3, points + 6);
268 // this is a flip check similar to the one above
269 // this one checks if the plane faces the origin, if not, flip it
270 if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
272 node->plane[0] *= -1;
273 node->plane[1] *= -1;
274 node->plane[2] *= -1;
275 node->plane[3] *= -1;
277 node->parent = parentnodenum;
278 node->children[0] = -1; // empty
279 node->children[1] = -2; // shadow
280 // link this child into the tree
281 // (with the addition of this node, queries will now be culled by it)
282 *parentnodenumpointer = (int)(node - b->nodes);
286 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)
289 int frontnumpoints, backnumpoints;
291 float frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
295 // recurse through plane nodes
296 while (*parentnodenumpointer >= 0)
298 // do a quick check to see if there is any need to split the polygon
299 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
300 parentnodenum = *parentnodenumpointer;
302 plane[0] = node->plane[0];
303 plane[1] = node->plane[1];
304 plane[2] = node->plane[2];
305 plane[3] = node->plane[3];
306 d = SVBSP_DotProduct(points, plane) - plane[3];
307 if (d >= SVBSP_CLIP_EPSILON)
309 for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] >= SVBSP_CLIP_EPSILON;i++);
312 // no need to split, just go to one side
313 parentnodenumpointer = &node->children[0];
317 else if (d <= -SVBSP_CLIP_EPSILON)
319 for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] <= -SVBSP_CLIP_EPSILON;i++);
322 // no need to split, just go to one side
323 parentnodenumpointer = &node->children[1];
328 // at this point we know it crosses the plane, so we need to split it
329 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);
330 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
331 frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
332 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
333 backnumpoints = MAX_SVBSP_POLYGONPOINTS;
334 // recurse the sides and return the resulting bit flags
336 if (frontnumpoints >= 3)
337 i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
338 if (backnumpoints >= 3)
339 i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
343 if (*parentnodenumpointer == -1)
345 // empty leaf node; and some geometry survived
346 // if inserting an occluder, replace this empty leaf with a shadow volume
348 for (i = 0;i < numpoints-2;i++)
350 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
351 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
352 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
353 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
359 b->stat_occluders_fragments_accepted++;
360 SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
363 b->stat_queries_fragments_accepted++;
364 if (fragmentcallback)
365 fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
370 // otherwise it's a solid leaf which destroys all polygons inside it
372 b->stat_occluders_fragments_rejected++;
374 b->stat_queries_fragments_rejected++;
376 for (i = 0;i < numpoints-2;i++)
378 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
379 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
380 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
381 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
389 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)
393 // don't even consider an empty polygon
397 //if (insertoccluder)
398 for (i = 0;i < numpoints-2;i++)
400 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
401 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
402 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
403 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
408 i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
412 b->stat_occluders_accepted++;
414 b->stat_occluders_rejected++;
419 b->stat_queries_accepted++;
421 b->stat_queries_rejected++;