some minor optimizations, comment corrections, and changed debug polygon colors
[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 #ifdef USEMALLOC
6 #include "string.h"
7 #define Mem_Alloc(p,s) malloc(s)
8 #define Mem_Free free
9 #else
10 #include "quakedef.h"
11 #endif
12 #include "polygon.h"
13 #include "svbsp.h"
14
15 #define MAX_SVBSP_POLYGONPOINTS 64
16 #define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
17
18 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
19 {
20         memset(b, 0, sizeof(*b));
21         b->origin[0] = origin[0];
22         b->origin[1] = origin[1];
23         b->origin[2] = origin[2];
24         b->numnodes = 3;
25         b->maxnodes = maxnodes;
26         b->nodes = nodes;
27         b->ranoutofnodes = 0;
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;
36
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.
40         //
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.
44
45         // root node
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;
54
55         // +X side node
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;
64
65         // -X side node
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;
74 }
75
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)
77 {
78         // now we need to create up to numpoints + 1 new nodes, forming a BSP tree
79         // describing the occluder polygon's shadow volume
80         int i, j, p, basenum;
81         svbsp_node_t *node;
82
83         // if there aren't enough nodes remaining, skip it
84         if (b->numnodes + numpoints + 1 >= b->maxnodes)
85         {
86                 b->ranoutofnodes = 1;
87                 return;
88         }
89
90         // add one node per side, then the actual occluding face node
91
92         // thread safety notes:
93         // DO NOT multithread insertion, it could be made 'safe' but the results
94         // would be inconsistent.
95         //
96         // it is completely safe to multithread queries in all cases.
97         //
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
101
102         // note down the first available nodenum for the *parentnodenumpointer
103         // line which is done last to allow multithreaded queries during an
104         // insertion
105         basenum = b->numnodes;
106         for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
107         {
108 #if 1
109                 // see if a parent plane describes this side
110                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
111                 {
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)
116                                 break;
117                 }
118                 if (j >= 0)
119                         continue; // already have a matching parent plane
120 #endif
121
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
129                 // wrong side
130                 // (in this way this code treats all polygons as double sided)
131                 //
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
136                 // sufficient)
137                 for (j = 0;j < numpoints;j++)
138                 {
139                         double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
140                         if (d < -SVBSP_CLIP_EPSILON)
141                                 break;
142                         if (d > SVBSP_CLIP_EPSILON)
143                         {
144                                 node->plane[0] *= -1;
145                                 node->plane[1] *= -1;
146                                 node->plane[2] *= -1;
147                                 node->plane[3] *= -1;
148                                 break;
149                         }
150                 }
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];
158         }
159
160 #if 1
161         // see if a parent plane describes the face plane
162         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
163         {
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)
168                         break;
169         }
170         if (j < 0)
171 #endif
172         {
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)
182                 {
183                         node->plane[0] *= -1;
184                         node->plane[1] *= -1;
185                         node->plane[2] *= -1;
186                         node->plane[3] *= -1;
187                 }
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);
194         }
195 }
196
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)
198 {
199         int i;
200         int frontnumpoints, backnumpoints;
201         double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
202         if (numpoints < 3)
203                 return 0;
204         // recurse through plane nodes
205         while (*parentnodenumpointer >= 0)
206         {
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;
210 #if 1
211                 if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
212                 {
213                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
214                         if (i == numpoints)
215                         {
216                                 // no need to split, just go to one side
217                                 parentnodenumpointer = &node->children[0];
218                                 continue;
219                         }
220                 }
221                 else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
222                 {
223                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
224                         if (i == numpoints)
225                         {
226                                 // no need to split, just go to one side
227                                 parentnodenumpointer = &node->children[1];
228                                 continue;
229                         }
230                 }
231 #endif
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
239                 i = 0;
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);
244                 return i;
245         }
246         // leaf node
247         if (*parentnodenumpointer == -1)
248         {
249                 // empty leaf node; and some geometry survived
250                 // if inserting an occluder, replace this empty leaf with a shadow volume
251 #if 0
252                 for (i = 0;i < numpoints-2;i++)
253                 {
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);
258                         Debug_PolygonEnd();
259                 }
260 #endif
261                 if (insertoccluder)
262                 {
263                         b->stat_occluders_fragments_accepted++;
264                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
265                 }
266                 else
267                         b->stat_queries_fragments_accepted++;
268                 if (fragmentcallback)
269                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
270                 return 2;
271         }
272         else
273         {
274                 // otherwise it's a solid leaf which destroys all polygons inside it
275                 if (insertoccluder)
276                         b->stat_occluders_fragments_rejected++;
277                 else
278                         b->stat_queries_fragments_rejected++;
279 #if 0
280                 for (i = 0;i < numpoints-2;i++)
281                 {
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);
286                         Debug_PolygonEnd();
287                 }
288 #endif
289         }
290         return 1;
291 }
292
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)
294 {
295         int i;
296         int nodenum;
297         // don't even consider an empty polygon
298         if (numpoints < 3)
299                 return 0;
300 #if 0
301 //if (insertoccluder)
302         for (i = 0;i < numpoints-2;i++)
303         {
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);
308                 Debug_PolygonEnd();
309         }
310 #endif
311         nodenum = 0;
312         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
313         if (insertoccluder)
314         {
315                 if (i & 2)
316                         b->stat_occluders_accepted++;
317                 else
318                         b->stat_occluders_rejected++;
319         }
320         else
321         {
322                 if (i & 2)
323                         b->stat_queries_accepted++;
324                 else
325                         b->stat_queries_rejected++;
326         }
327         return i;
328 }
329