changed svbsp code to use floats instead of doubles
[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.0 / 1024.0)
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 = sqrt(SVBSP_DotProduct(plane4f, plane4f));
25         if (ilength)
26                 ilength = 1.0 / 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 1
98         unsigned int sideflags[(MAX_SVBSP_POLYGONPOINTS+31)>>5];
99 #endif
100
101         // if there aren't enough nodes remaining, skip it
102         if (b->numnodes + numpoints + 1 >= b->maxnodes)
103         {
104                 b->ranoutofnodes = 1;
105                 return;
106         }
107
108         // add one node per side, then the actual occluding face node
109
110         // thread safety notes:
111         // DO NOT multithread insertion, it could be made 'safe' but the results
112         // would be inconsistent.
113         //
114         // it is completely safe to multithread queries in all cases.
115         //
116         // if an insertion is occurring the query will give intermediate results,
117         // being blocked by some volumes but not others, which is perfectly okay
118         // for visibility culling intended only to reduce rendering work
119
120         // note down the first available nodenum for the *parentnodenumpointer
121         // line which is done last to allow multithreaded queries during an
122         // insertion
123         basenum = b->numnodes;
124 #if 1
125         // 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
126         memset(sideflags, 0, sizeof(sideflags[0])*((numpoints+31)>>5));
127         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
128         {
129                 float *parentnodeplane = b->nodes[j].plane;
130                 float plane[4] = {parentnodeplane[0], parentnodeplane[1], parentnodeplane[2], parentnodeplane[3]};
131                 float mindist = plane[3] - SVBSP_CLIP_EPSILON;
132                 float maxdist = plane[3] + SVBSP_CLIP_EPSILON;
133                 float d;
134                 int i, p, n;
135                 // if a parent plane crosses the origin, it is a side plane
136                 // if it does not cross the origin, it is a face plane, and thus will
137                 // not match any side planes we could add
138                 d = SVBSP_DotProduct(b->origin     , plane);
139                 if (d < mindist || d > maxdist)
140                         continue;
141                 // classify each side as belonging to this parent plane or not
142                 // do a distance check on the last point of the polygon first, and
143                 // then one distance check per point, reusing the previous point
144                 // distance check to classify this side as being on or off the plane
145                 i = numpoints-1;
146                 d = SVBSP_DotProduct(points + i * 3, plane);
147                 p = d >= mindist && d <= maxdist;
148                 for (i = 0;i < numpoints;i++)
149                 {
150                         d = SVBSP_DotProduct(points + i * 3, plane);
151                         n = d >= mindist && d <= maxdist;
152                         if (p && n)
153                                 sideflags[i>>5] |= 1<<(i&31);
154                         p = n;
155                 }
156 #endif
157         }
158
159         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
160         {
161 #if 1
162                 // skip any sides that were classified as belonging to a parent plane
163                 if (sideflags[i>>5] & (1<<(i&31)))
164                         continue;
165 #endif
166                 // create a side plane
167                 // anything infront of this is not inside the shadow volume
168                 node = b->nodes + b->numnodes++;
169                 SVBSP_PlaneFromPoints(node->plane, b->origin, points + p * 3, points + i * 3);
170                 // we need to flip the plane if it puts any part of the polygon on the
171                 // wrong side
172                 // (in this way this code treats all polygons as float sided)
173                 //
174                 // because speed is important this stops as soon as it finds proof
175                 // that the orientation is right or wrong
176                 // (we know that the plane is on one edge of the polygon, so there is
177                 // never a case where points lie on both sides, so the first hint is
178                 // sufficient)
179                 for (j = 0;j < numpoints;j++)
180                 {
181                         float d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
182                         if (d < -SVBSP_CLIP_EPSILON)
183                                 break;
184                         if (d > SVBSP_CLIP_EPSILON)
185                         {
186                                 node->plane[0] *= -1;
187                                 node->plane[1] *= -1;
188                                 node->plane[2] *= -1;
189                                 node->plane[3] *= -1;
190                                 break;
191                         }
192                 }
193                 node->parent = parentnodenum;
194                 node->children[0] = -1; // empty
195                 node->children[1] = -1; // empty
196                 // link this child into the tree
197                 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
198                 // now point to the child pointer for the next node to update later
199                 parentnodenumpointer = &node->children[1];
200         }
201
202 #if 1
203         // see if a parent plane describes the face plane
204         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
205         {
206                 float *parentnodeplane = b->nodes[j].plane;
207                 if (fabs(SVBSP_DotProduct(points    , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
208                  && fabs(SVBSP_DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
209                  && fabs(SVBSP_DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
210                         break;
211         }
212         if (j < 0)
213 #endif
214         {
215                 // add the face-plane node
216                 // infront is empty, behind is shadow
217                 node = b->nodes + b->numnodes++;
218                 SVBSP_PlaneFromPoints(node->plane, points, points + 3, points + 6);
219                 // this is a flip check similar to the one above
220                 // this one checks if the plane faces the origin, if not, flip it
221                 if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
222                 {
223                         node->plane[0] *= -1;
224                         node->plane[1] *= -1;
225                         node->plane[2] *= -1;
226                         node->plane[3] *= -1;
227                 }
228                 node->parent = parentnodenum;
229                 node->children[0] = -1; // empty
230                 node->children[1] = -2; // shadow
231                 // link this child into the tree
232                 // (with the addition of this node, queries will now be culled by it)
233                 *parentnodenumpointer = (int)(node - b->nodes);
234         }
235 }
236
237 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)
238 {
239         int i;
240         int frontnumpoints, backnumpoints;
241         float plane[4];
242         float frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
243         float d;
244         if (numpoints < 3)
245                 return 0;
246         // recurse through plane nodes
247         while (*parentnodenumpointer >= 0)
248         {
249                 // do a quick check to see if there is any need to split the polygon
250                 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
251                 parentnodenum = *parentnodenumpointer;
252 #if 1
253                 plane[0] = node->plane[0];
254                 plane[1] = node->plane[1];
255                 plane[2] = node->plane[2];
256                 plane[3] = node->plane[3];
257                 d = SVBSP_DotProduct(points, plane) >= plane[3];
258                 if (d >= SVBSP_CLIP_EPSILON)
259                 {
260                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] >= SVBSP_CLIP_EPSILON;i++);
261                         if (i == numpoints)
262                         {
263                                 // no need to split, just go to one side
264                                 parentnodenumpointer = &node->children[0];
265                                 continue;
266                         }
267                 }
268                 else if (d <= -SVBSP_CLIP_EPSILON)
269                 {
270                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, plane) - plane[3] <= -SVBSP_CLIP_EPSILON;i++);
271                         if (i == numpoints)
272                         {
273                                 // no need to split, just go to one side
274                                 parentnodenumpointer = &node->children[1];
275                                 continue;
276                         }
277                 }
278 #endif
279                 // at this point we know it crosses the plane, so we need to split it
280                 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);
281                 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
282                         frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
283                 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
284                         backnumpoints = MAX_SVBSP_POLYGONPOINTS;
285                 // recurse the sides and return the resulting bit flags
286                 i = 0;
287                 if (frontnumpoints >= 3)
288                         i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
289                 if (backnumpoints >= 3)
290                         i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
291                 return i;
292         }
293         // leaf node
294         if (*parentnodenumpointer == -1)
295         {
296                 // empty leaf node; and some geometry survived
297                 // if inserting an occluder, replace this empty leaf with a shadow volume
298 #if 0
299                 for (i = 0;i < numpoints-2;i++)
300                 {
301                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
302                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
303                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
304                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
305                         Debug_PolygonEnd();
306                 }
307 #endif
308                 if (insertoccluder)
309                 {
310                         b->stat_occluders_fragments_accepted++;
311                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
312                 }
313                 else
314                         b->stat_queries_fragments_accepted++;
315                 if (fragmentcallback)
316                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
317                 return 2;
318         }
319         else
320         {
321                 // otherwise it's a solid leaf which destroys all polygons inside it
322                 if (insertoccluder)
323                         b->stat_occluders_fragments_rejected++;
324                 else
325                         b->stat_queries_fragments_rejected++;
326 #if 0
327                 for (i = 0;i < numpoints-2;i++)
328                 {
329                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
330                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
331                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
332                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
333                         Debug_PolygonEnd();
334                 }
335 #endif
336         }
337         return 1;
338 }
339
340 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)
341 {
342         int i;
343         int nodenum;
344         // don't even consider an empty polygon
345         if (numpoints < 3)
346                 return 0;
347 #if 0
348 //if (insertoccluder)
349         for (i = 0;i < numpoints-2;i++)
350         {
351                 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
352                 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
353                 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
354                 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
355                 Debug_PolygonEnd();
356         }
357 #endif
358         nodenum = 0;
359         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
360         if (insertoccluder)
361         {
362                 if (i & 2)
363                         b->stat_occluders_accepted++;
364                 else
365                         b->stat_occluders_rejected++;
366         }
367         else
368         {
369                 if (i & 2)
370                         b->stat_queries_accepted++;
371                 else
372                         b->stat_queries_rejected++;
373         }
374         return i;
375 }
376