added back the old method of comparing points to the parent planes,
[divverent/darkplaces.git] / 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.0f / 1024.0f)
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 = (float)sqrt(SVBSP_DotProduct(plane4f, plane4f));
25         if (ilength)
26                 ilength = 1.0f / 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 0
98         unsigned int sideflags[(MAX_SVBSP_POLYGONPOINTS+31)>>5];
99         float *parentnodeplane;
100         float plane[4];
101 #if 0
102         float mindist;
103         float maxdist;
104         float d;
105 #endif
106         int n;
107 #endif
108
109         // if there aren't enough nodes remaining, skip it
110         if (b->numnodes + numpoints + 1 >= b->maxnodes)
111         {
112                 b->ranoutofnodes = 1;
113                 return;
114         }
115
116         // add one node per side, then the actual occluding face node
117
118         // thread safety notes:
119         // DO NOT multithread insertion, it could be made 'safe' but the results
120         // would be inconsistent.
121         //
122         // it is completely safe to multithread queries in all cases.
123         //
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
127
128         // note down the first available nodenum for the *parentnodenumpointer
129         // line which is done last to allow multithreaded queries during an
130         // insertion
131         basenum = b->numnodes;
132 #if 1
133         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
134         {
135 #if 1
136                 // see if a parent plane describes this side
137                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
138                 {
139                         float *parentnodeplane = b->nodes[j].plane;
140                 //      float v[3];
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)
148                                 break;
149                 }
150                 if (j >= 0)
151                         continue; // already have a matching parent plane
152 #endif
153
154 #else
155 #if 1
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++)
158                 sideflags[i] = 0;
159         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
160         {
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];
166 #if 0
167                 mindist = plane[3] - SVBSP_CLIP_EPSILON;
168                 maxdist = plane[3] + SVBSP_CLIP_EPSILON;
169 #endif
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
173 #if 1
174                 if (fabs(SVBSP_DotProduct(b->origin, plane) - plane[3]) > SVBSP_CLIP_EPSILON)
175                         continue;
176 #else
177                 d = SVBSP_DotProduct(b->origin     , plane);
178                 if (d < mindist || d > maxdist)
179                         continue;
180 #endif
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
185                 i = numpoints-1;
186 #if 1
187                 p = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
188 #else
189                 d = SVBSP_DotProduct(points + i * 3, plane);
190                 p = d >= mindist && d <= maxdist;
191 #endif
192                 for (i = 0;i < numpoints;i++)
193                 {
194 #if 1
195                         n = fabs(SVBSP_DotProduct(points + i * 3, plane) - plane[3]) <= SVBSP_CLIP_EPSILON;
196 #else
197                         d = SVBSP_DotProduct(points + i * 3, plane);
198                         n = d >= mindist && d <= maxdist;
199 #endif
200                         if (p && n)
201                                 sideflags[i>>5] |= 1<<(i&31);
202                         p = n;
203                 }
204 #endif
205         }
206
207         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
208         {
209 #if 1
210                 // skip any sides that were classified as belonging to a parent plane
211                 if (sideflags[i>>5] & (1<<(i&31)))
212                         continue;
213 #endif
214 #endif
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
220                 // wrong side
221                 // (in this way this code treats all polygons as float sided)
222                 //
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
227                 // sufficient)
228                 for (j = 0;j < numpoints;j++)
229                 {
230                         float d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
231                         if (d < -SVBSP_CLIP_EPSILON)
232                                 break;
233                         if (d > SVBSP_CLIP_EPSILON)
234                         {
235                                 node->plane[0] *= -1;
236                                 node->plane[1] *= -1;
237                                 node->plane[2] *= -1;
238                                 node->plane[3] *= -1;
239                                 break;
240                         }
241                 }
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];
249         }
250
251 #if 1
252         // see if a parent plane describes the face plane
253         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
254         {
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)
259                         break;
260         }
261         if (j < 0)
262 #endif
263         {
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)
271                 {
272                         node->plane[0] *= -1;
273                         node->plane[1] *= -1;
274                         node->plane[2] *= -1;
275                         node->plane[3] *= -1;
276                 }
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);
283         }
284 }
285
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)
287 {
288         int i;
289         int frontnumpoints, backnumpoints;
290         float plane[4];
291         float frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
292         float d;
293         if (numpoints < 3)
294                 return 0;
295         // recurse through plane nodes
296         while (*parentnodenumpointer >= 0)
297         {
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;
301 #if 1
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)
308                 {
309                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] >= SVBSP_CLIP_EPSILON;i++);
310                         if (i == numpoints)
311                         {
312                                 // no need to split, just go to one side
313                                 parentnodenumpointer = &node->children[0];
314                                 continue;
315                         }
316                 }
317                 else if (d <= -SVBSP_CLIP_EPSILON)
318                 {
319                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] <= -SVBSP_CLIP_EPSILON;i++);
320                         if (i == numpoints)
321                         {
322                                 // no need to split, just go to one side
323                                 parentnodenumpointer = &node->children[1];
324                                 continue;
325                         }
326                 }
327 #endif
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
335                 i = 0;
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);
340                 return i;
341         }
342         // leaf node
343         if (*parentnodenumpointer == -1)
344         {
345                 // empty leaf node; and some geometry survived
346                 // if inserting an occluder, replace this empty leaf with a shadow volume
347 #if 0
348                 for (i = 0;i < numpoints-2;i++)
349                 {
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);
354                         Debug_PolygonEnd();
355                 }
356 #endif
357                 if (insertoccluder)
358                 {
359                         b->stat_occluders_fragments_accepted++;
360                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
361                 }
362                 else
363                         b->stat_queries_fragments_accepted++;
364                 if (fragmentcallback)
365                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
366                 return 2;
367         }
368         else
369         {
370                 // otherwise it's a solid leaf which destroys all polygons inside it
371                 if (insertoccluder)
372                         b->stat_occluders_fragments_rejected++;
373                 else
374                         b->stat_queries_fragments_rejected++;
375 #if 0
376                 for (i = 0;i < numpoints-2;i++)
377                 {
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);
382                         Debug_PolygonEnd();
383                 }
384 #endif
385         }
386         return 1;
387 }
388
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)
390 {
391         int i;
392         int nodenum;
393         // don't even consider an empty polygon
394         if (numpoints < 3)
395                 return 0;
396 #if 0
397 //if (insertoccluder)
398         for (i = 0;i < numpoints-2;i++)
399         {
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);
404                 Debug_PolygonEnd();
405         }
406 #endif
407         nodenum = 0;
408         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
409         if (insertoccluder)
410         {
411                 if (i & 2)
412                         b->stat_occluders_accepted++;
413                 else
414                         b->stat_occluders_rejected++;
415         }
416         else
417         {
418                 if (i & 2)
419                         b->stat_queries_accepted++;
420                 else
421                         b->stat_queries_rejected++;
422         }
423         return i;
424 }
425