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
7 #define Mem_Alloc(p,s) malloc(s)
15 #define MAX_SVBSP_POLYGONPOINTS 64
16 #define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
18 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
20 memset(b, 0, sizeof(*b));
21 b->origin[0] = origin[0];
22 b->origin[1] = origin[1];
23 b->origin[2] = origin[2];
25 b->maxnodes = maxnodes;
28 b->stat_occluders_rejected = 0;
29 b->stat_occluders_accepted = 0;
30 b->stat_occluders_fragments_accepted = 0;
31 b->stat_occluders_fragments_rejected = 0;
32 b->stat_queries_rejected = 0;
33 b->stat_queries_accepted = 0;
34 b->stat_queries_fragments_accepted = 0;
35 b->stat_queries_fragments_rejected = 0;
37 // the bsp tree must be initialized to have two perpendicular splits axes
38 // through origin, otherwise the polygon insertions would affect the
39 // opposite side of the tree, which would be disasterous.
41 // so this code has to make 3 nodes and 4 leafs, and since the leafs are
42 // represented by empty/solid state numbers in this system rather than
43 // actual structs, we only need to make the 3 nodes.
46 // this one splits the world into +X and -X sides
47 b->nodes[0].plane[0] = 1;
48 b->nodes[0].plane[1] = 0;
49 b->nodes[0].plane[2] = 0;
50 b->nodes[0].plane[3] = origin[0];
51 b->nodes[0].parent = -1;
52 b->nodes[0].children[0] = 1;
53 b->nodes[0].children[1] = 2;
56 // this one splits the +X half of the world into +Y and -Y
57 b->nodes[1].plane[0] = 0;
58 b->nodes[1].plane[1] = 1;
59 b->nodes[1].plane[2] = 0;
60 b->nodes[1].plane[3] = origin[1];
61 b->nodes[1].parent = 0;
62 b->nodes[1].children[0] = -1;
63 b->nodes[1].children[1] = -1;
66 // this one splits the -X half of the world into +Y and -Y
67 b->nodes[2].plane[0] = 0;
68 b->nodes[2].plane[1] = 1;
69 b->nodes[2].plane[2] = 0;
70 b->nodes[2].plane[3] = origin[1];
71 b->nodes[2].parent = 0;
72 b->nodes[2].children[0] = -1;
73 b->nodes[2].children[1] = -1;
76 static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const double *points, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
78 // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
79 // describing the occluder polygon's shadow volume
83 // if there aren't enough nodes remaining, skip it
84 if (b->numnodes + numpoints + 1 >= b->maxnodes)
90 // add one node per side, then the actual occluding face node
92 // thread safety notes:
93 // DO NOT multithread insertion, it could be made 'safe' but the results
94 // would be inconsistent.
96 // it is completely safe to multithread queries in all cases.
98 // if an insertion is occurring the query will give intermediate results,
99 // being blocked by some volumes but not others, which is perfectly okay
100 // for visibility culling intended only to reduce rendering work
102 // note down the first available nodenum for the *parentnodenumpointer
103 // line which is done last to allow multithreaded queries during an
105 basenum = b->numnodes;
106 for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
109 // see if a parent plane describes this side
110 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
112 double *parentnodeplane = b->nodes[j].plane;
113 if (fabs(DotProduct(b->origin , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
114 && fabs(DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
115 && fabs(DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
119 continue; // already have a matching parent plane
122 // create a side plane
123 // anything infront of this is not inside the shadow volume
124 node = b->nodes + b->numnodes++;
125 TriangleNormal(b->origin, points + p * 3, points + i * 3, node->plane);
126 VectorNormalize(node->plane);
127 node->plane[3] = DotProduct(node->plane, b->origin);
128 // we need to flip the plane if it puts any part of the polygon on the
130 // (in this way this code treats all polygons as double sided)
132 // because speed is important this stops as soon as it finds proof
133 // that the orientation is right or wrong
134 // (we know that the plane is on one edge of the polygon, so there is
135 // never a case where points lie on both sides, so the first hint is
137 for (j = 0;j < numpoints;j++)
139 double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
140 if (d < -SVBSP_CLIP_EPSILON)
142 if (d > SVBSP_CLIP_EPSILON)
144 node->plane[0] *= -1;
145 node->plane[1] *= -1;
146 node->plane[2] *= -1;
147 node->plane[3] *= -1;
151 node->parent = parentnodenum;
152 node->children[0] = -1; // empty
153 node->children[1] = -1; // empty
154 // link this child into the tree
155 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
156 // now point to the child pointer for the next node to update later
157 parentnodenumpointer = &node->children[1];
161 // see if a parent plane describes the face plane
162 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
164 double *parentnodeplane = b->nodes[j].plane;
165 if (fabs(DotProduct(points , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
166 && fabs(DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
167 && fabs(DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
173 // add the face-plane node
174 // infront is empty, behind is shadow
175 node = b->nodes + b->numnodes++;
176 TriangleNormal(points, points + 3, points + 6, node->plane);
177 VectorNormalize(node->plane);
178 node->plane[3] = DotProduct(node->plane, points);
179 // this is a flip check similar to the one above
180 // this one checks if the plane faces the origin, if not, flip it
181 if (DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
183 node->plane[0] *= -1;
184 node->plane[1] *= -1;
185 node->plane[2] *= -1;
186 node->plane[3] *= -1;
188 node->parent = parentnodenum;
189 node->children[0] = -1; // empty
190 node->children[1] = -2; // shadow
191 // link this child into the tree
192 // (with the addition of this node, queries will now be culled by it)
193 *parentnodenumpointer = (int)(node - b->nodes);
197 static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int parentnodenum, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
200 int frontnumpoints, backnumpoints;
201 double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
204 // recurse through plane nodes
205 while (*parentnodenumpointer >= 0)
207 // do a quick check to see if there is any need to split the polygon
208 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
209 parentnodenum = *parentnodenumpointer;
211 if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
213 for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
216 // no need to split, just go to one side
217 parentnodenumpointer = &node->children[0];
221 else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
223 for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
226 // no need to split, just go to one side
227 parentnodenumpointer = &node->children[1];
232 // at this point we know it crosses the plane, so we need to split it
233 PolygonD_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);
234 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
235 frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
236 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
237 backnumpoints = MAX_SVBSP_POLYGONPOINTS;
238 // recurse the sides and return the resulting bit flags
240 if (frontnumpoints >= 3)
241 i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
242 if (backnumpoints >= 3)
243 i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
247 if (*parentnodenumpointer == -1)
249 // empty leaf node; and some geometry survived
250 // if inserting an occluder, replace this empty leaf with a shadow volume
252 for (i = 0;i < numpoints-2;i++)
254 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
255 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
256 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
257 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
263 b->stat_occluders_fragments_accepted++;
264 SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
267 b->stat_queries_fragments_accepted++;
268 if (fragmentcallback)
269 fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
274 // otherwise it's a solid leaf which destroys all polygons inside it
276 b->stat_occluders_fragments_rejected++;
278 b->stat_queries_fragments_rejected++;
280 for (i = 0;i < numpoints-2;i++)
282 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
283 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
284 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
285 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
293 int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const double *points, int insertoccluder, void (*fragmentcallback)(void *fragmentcallback_pointer1, int fragmentcallback_number1, svbsp_t *b, int numpoints, const double *points), void *fragmentcallback_pointer1, int fragmentcallback_number1)
297 // don't even consider an empty polygon
301 //if (insertoccluder)
302 for (i = 0;i < numpoints-2;i++)
304 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
305 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
306 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
307 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
312 i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
316 b->stat_occluders_accepted++;
318 b->stat_occluders_rejected++;
323 b->stat_queries_accepted++;
325 b->stat_queries_rejected++;