rewrote most of the VM_Polygon/DebugPolygon code, it should perform much
[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 "quakedef.h"
6
7 #include <math.h>
8 #include <string.h>
9 #include "svbsp.h"
10 #include "polygon.h"
11
12 #define MAX_SVBSP_POLYGONPOINTS 64
13 #define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
14
15 #define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
16
17 static void SVBSP_PlaneFromPoints(double *plane4f, const double *p1, const double *p2, const double *p3)
18 {
19         double ilength;
20         // calculate unnormalized plane
21         plane4f[0] = (p1[1] - p2[1]) * (p3[2] - p2[2]) - (p1[2] - p2[2]) * (p3[1] - p2[1]);
22         plane4f[1] = (p1[2] - p2[2]) * (p3[0] - p2[0]) - (p1[0] - p2[0]) * (p3[2] - p2[2]);
23         plane4f[2] = (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0]);
24         plane4f[3] = SVBSP_DotProduct(plane4f, p1);
25         // normalize the plane normal and adjust distance accordingly
26         ilength = sqrt(SVBSP_DotProduct(plane4f, plane4f));
27         if (ilength)
28                 ilength = 1.0 / ilength;
29         plane4f[0] *= ilength;
30         plane4f[1] *= ilength;
31         plane4f[2] *= ilength;
32         plane4f[3] *= ilength;
33 }
34
35 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
36 {
37         memset(b, 0, sizeof(*b));
38         b->origin[0] = origin[0];
39         b->origin[1] = origin[1];
40         b->origin[2] = origin[2];
41         b->numnodes = 3;
42         b->maxnodes = maxnodes;
43         b->nodes = nodes;
44         b->ranoutofnodes = 0;
45         b->stat_occluders_rejected = 0;
46         b->stat_occluders_accepted = 0;
47         b->stat_occluders_fragments_accepted = 0;
48         b->stat_occluders_fragments_rejected = 0;
49         b->stat_queries_rejected = 0;
50         b->stat_queries_accepted = 0;
51         b->stat_queries_fragments_accepted = 0;
52         b->stat_queries_fragments_rejected = 0;
53
54         // the bsp tree must be initialized to have two perpendicular splits axes
55         // through origin, otherwise the polygon insertions would affect the
56         // opposite side of the tree, which would be disasterous.
57         //
58         // so this code has to make 3 nodes and 4 leafs, and since the leafs are
59         // represented by empty/solid state numbers in this system rather than
60         // actual structs, we only need to make the 3 nodes.
61
62         // root node
63         // this one splits the world into +X and -X sides
64         b->nodes[0].plane[0] = 1;
65         b->nodes[0].plane[1] = 0;
66         b->nodes[0].plane[2] = 0;
67         b->nodes[0].plane[3] = origin[0];
68         b->nodes[0].parent = -1;
69         b->nodes[0].children[0] = 1;
70         b->nodes[0].children[1] = 2;
71
72         // +X side node
73         // this one splits the +X half of the world into +Y and -Y
74         b->nodes[1].plane[0] = 0;
75         b->nodes[1].plane[1] = 1;
76         b->nodes[1].plane[2] = 0;
77         b->nodes[1].plane[3] = origin[1];
78         b->nodes[1].parent = 0;
79         b->nodes[1].children[0] = -1;
80         b->nodes[1].children[1] = -1;
81
82         // -X side node
83         // this one splits the -X half of the world into +Y and -Y
84         b->nodes[2].plane[0] = 0;
85         b->nodes[2].plane[1] = 1;
86         b->nodes[2].plane[2] = 0;
87         b->nodes[2].plane[3] = origin[1];
88         b->nodes[2].parent = 0;
89         b->nodes[2].children[0] = -1;
90         b->nodes[2].children[1] = -1;
91 }
92
93 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)
94 {
95         // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
96         // describing the occluder polygon's shadow volume
97         int i, j, p, basenum;
98         svbsp_node_t *node;
99
100         // if there aren't enough nodes remaining, skip it
101         if (b->numnodes + numpoints + 1 >= b->maxnodes)
102         {
103                 b->ranoutofnodes = 1;
104                 return;
105         }
106
107         // add one node per side, then the actual occluding face node
108
109         // thread safety notes:
110         // DO NOT multithread insertion, it could be made 'safe' but the results
111         // would be inconsistent.
112         //
113         // it is completely safe to multithread queries in all cases.
114         //
115         // if an insertion is occurring the query will give intermediate results,
116         // being blocked by some volumes but not others, which is perfectly okay
117         // for visibility culling intended only to reduce rendering work
118
119         // note down the first available nodenum for the *parentnodenumpointer
120         // line which is done last to allow multithreaded queries during an
121         // insertion
122         basenum = b->numnodes;
123         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
124         {
125 #if 1
126                 // see if a parent plane describes this side
127                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
128                 {
129                         double *parentnodeplane = b->nodes[j].plane;
130                         if (fabs(SVBSP_DotProduct(b->origin     , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
131                          && fabs(SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
132                          && fabs(SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
133                                 break;
134                 }
135                 if (j >= 0)
136                         continue; // already have a matching parent plane
137 #endif
138
139                 // create a side plane
140                 // anything infront of this is not inside the shadow volume
141                 node = b->nodes + b->numnodes++;
142                 SVBSP_PlaneFromPoints(node->plane, b->origin, points + p * 3, points + i * 3);
143                 // we need to flip the plane if it puts any part of the polygon on the
144                 // wrong side
145                 // (in this way this code treats all polygons as double sided)
146                 //
147                 // because speed is important this stops as soon as it finds proof
148                 // that the orientation is right or wrong
149                 // (we know that the plane is on one edge of the polygon, so there is
150                 // never a case where points lie on both sides, so the first hint is
151                 // sufficient)
152                 for (j = 0;j < numpoints;j++)
153                 {
154                         double d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
155                         if (d < -SVBSP_CLIP_EPSILON)
156                                 break;
157                         if (d > SVBSP_CLIP_EPSILON)
158                         {
159                                 node->plane[0] *= -1;
160                                 node->plane[1] *= -1;
161                                 node->plane[2] *= -1;
162                                 node->plane[3] *= -1;
163                                 break;
164                         }
165                 }
166                 node->parent = parentnodenum;
167                 node->children[0] = -1; // empty
168                 node->children[1] = -1; // empty
169                 // link this child into the tree
170                 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
171                 // now point to the child pointer for the next node to update later
172                 parentnodenumpointer = &node->children[1];
173         }
174
175 #if 1
176         // see if a parent plane describes the face plane
177         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
178         {
179                 double *parentnodeplane = b->nodes[j].plane;
180                 if (fabs(SVBSP_DotProduct(points    , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
181                  && fabs(SVBSP_DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
182                  && fabs(SVBSP_DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
183                         break;
184         }
185         if (j < 0)
186 #endif
187         {
188                 // add the face-plane node
189                 // infront is empty, behind is shadow
190                 node = b->nodes + b->numnodes++;
191                 SVBSP_PlaneFromPoints(node->plane, points, points + 3, points + 6);
192                 // this is a flip check similar to the one above
193                 // this one checks if the plane faces the origin, if not, flip it
194                 if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
195                 {
196                         node->plane[0] *= -1;
197                         node->plane[1] *= -1;
198                         node->plane[2] *= -1;
199                         node->plane[3] *= -1;
200                 }
201                 node->parent = parentnodenum;
202                 node->children[0] = -1; // empty
203                 node->children[1] = -2; // shadow
204                 // link this child into the tree
205                 // (with the addition of this node, queries will now be culled by it)
206                 *parentnodenumpointer = (int)(node - b->nodes);
207         }
208 }
209
210 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)
211 {
212         int i;
213         int frontnumpoints, backnumpoints;
214         double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
215         if (numpoints < 3)
216                 return 0;
217         // recurse through plane nodes
218         while (*parentnodenumpointer >= 0)
219         {
220                 // do a quick check to see if there is any need to split the polygon
221                 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
222                 parentnodenum = *parentnodenumpointer;
223 #if 1
224                 if (SVBSP_DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
225                 {
226                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
227                         if (i == numpoints)
228                         {
229                                 // no need to split, just go to one side
230                                 parentnodenumpointer = &node->children[0];
231                                 continue;
232                         }
233                 }
234                 else if (SVBSP_DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
235                 {
236                         for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
237                         if (i == numpoints)
238                         {
239                                 // no need to split, just go to one side
240                                 parentnodenumpointer = &node->children[1];
241                                 continue;
242                         }
243                 }
244 #endif
245                 // at this point we know it crosses the plane, so we need to split it
246                 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);
247                 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
248                         frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
249                 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
250                         backnumpoints = MAX_SVBSP_POLYGONPOINTS;
251                 // recurse the sides and return the resulting bit flags
252                 i = 0;
253                 if (frontnumpoints >= 3)
254                         i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
255                 if (backnumpoints >= 3)
256                         i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
257                 return i;
258         }
259         // leaf node
260         if (*parentnodenumpointer == -1)
261         {
262                 // empty leaf node; and some geometry survived
263                 // if inserting an occluder, replace this empty leaf with a shadow volume
264 #if 0
265                 for (i = 0;i < numpoints-2;i++)
266                 {
267                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
268                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
269                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
270                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
271                         Debug_PolygonEnd();
272                 }
273 #endif
274                 if (insertoccluder)
275                 {
276                         b->stat_occluders_fragments_accepted++;
277                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
278                 }
279                 else
280                         b->stat_queries_fragments_accepted++;
281                 if (fragmentcallback)
282                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
283                 return 2;
284         }
285         else
286         {
287                 // otherwise it's a solid leaf which destroys all polygons inside it
288                 if (insertoccluder)
289                         b->stat_occluders_fragments_rejected++;
290                 else
291                         b->stat_queries_fragments_rejected++;
292 #if 0
293                 for (i = 0;i < numpoints-2;i++)
294                 {
295                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
296                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
297                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
298                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
299                         Debug_PolygonEnd();
300                 }
301 #endif
302         }
303         return 1;
304 }
305
306 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)
307 {
308         int i;
309         int nodenum;
310         // don't even consider an empty polygon
311         if (numpoints < 3)
312                 return 0;
313 #if 0
314 //if (insertoccluder)
315         for (i = 0;i < numpoints-2;i++)
316         {
317                 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE);
318                 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
319                 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
320                 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
321                 Debug_PolygonEnd();
322         }
323 #endif
324         nodenum = 0;
325         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
326         if (insertoccluder)
327         {
328                 if (i & 2)
329                         b->stat_occluders_accepted++;
330                 else
331                         b->stat_occluders_rejected++;
332         }
333         else
334         {
335                 if (i & 2)
336                         b->stat_queries_accepted++;
337                 else
338                         b->stat_queries_rejected++;
339         }
340         return i;
341 }
342