implemented Shadow Volume BSP based culling of lit surfaces, this is slightly better...
[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                 // see if a parent plane describes this side
109                 for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
110                 {
111                         svbsp_node_t *parentnode = b->nodes + j;
112                         if (fabs(DotProduct(b->origin     , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
113                          && fabs(DotProduct(points + p * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
114                          && fabs(DotProduct(points + i * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
115                                 break;
116                 }
117                 if (j >= 0)
118                         continue; // already have a matching parent plane
119
120                 // create a side plane
121                 // anything infront of this is not inside the shadow volume
122                 node = b->nodes + b->numnodes++;
123                 TriangleNormal(b->origin, points + p * 3, points + i * 3, node->plane);
124                 VectorNormalize(node->plane);
125                 node->plane[3] = DotProduct(node->plane, b->origin);
126                 // we need to flip the plane if it puts any part of the polygon on the
127                 // wrong side
128                 // (in this way this code treats all polygons as double sided)
129                 //
130                 // because speed is important this stops as soon as it finds proof
131                 // that the orientation is right or wrong
132                 // (we know that the plane is on one edge of the polygon, so there is
133                 // never a case where points lie on both sides, so the first hint is
134                 // sufficient)
135                 for (j = 0;j < numpoints;j++)
136                 {
137                         double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
138                         if (d < -SVBSP_CLIP_EPSILON)
139                                 break;
140                         if (d > SVBSP_CLIP_EPSILON)
141                         {
142                                 node->plane[0] *= -1;
143                                 node->plane[1] *= -1;
144                                 node->plane[2] *= -1;
145                                 node->plane[3] *= -1;
146                                 break;
147                         }
148                 }
149                 node->parent = parentnodenum;
150                 node->children[0] = -1; // empty
151                 node->children[1] = -1; // empty
152                 // link this child into the tree
153                 *parentnodenumpointer = parentnodenum = (int)(node - b->nodes);
154                 // now point to the child pointer for the next node to update later
155                 parentnodenumpointer = &node->children[1];
156         }
157
158         // see if a parent plane describes the face plane
159         for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
160         {
161                 svbsp_node_t *parentnode = b->nodes + j;
162                 if (fabs(DotProduct(points    , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
163                  && fabs(DotProduct(points + 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
164                  && fabs(DotProduct(points + 6, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
165                         break;
166         }
167         if (j < 0)
168         {
169                 // add the face-plane node
170                 // infront is empty, behind is shadow
171                 node = b->nodes + b->numnodes++;
172                 TriangleNormal(points, points + 3, points + 6, node->plane);
173                 VectorNormalize(node->plane);
174                 node->plane[3] = DotProduct(node->plane, points);
175                 // this is a flip check similar to the one above
176                 // this one checks if the plane faces the origin, if not, flip it
177                 if (DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
178                 {
179                         node->plane[0] *= -1;
180                         node->plane[1] *= -1;
181                         node->plane[2] *= -1;
182                         node->plane[3] *= -1;
183                 }
184                 node->parent = parentnodenum;
185                 node->children[0] = -1; // empty
186                 node->children[1] = -2; // shadow
187                 // link this child into the tree
188                 // (with the addition of this node, queries will now culled by it)
189                 *parentnodenumpointer = (int)(node - b->nodes);
190         }
191 }
192
193 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)
194 {
195         int i;
196         int frontnumpoints, backnumpoints;
197         double frontpoints[MAX_SVBSP_POLYGONPOINTS * 3], backpoints[MAX_SVBSP_POLYGONPOINTS * 3];
198         if (numpoints < 3)
199                 return 0;
200         // recurse through plane nodes
201         while (*parentnodenumpointer >= 0)
202         {
203                 // do a quick check to see if there is any need to split the polygon
204                 svbsp_node_t *node = b->nodes + *parentnodenumpointer;
205                 parentnodenum = *parentnodenumpointer;
206 #if 1
207                 if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
208                 {
209                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
210                         if (i == numpoints)
211                         {
212                                 // no need to split, just go to one side
213                                 parentnodenumpointer = &node->children[0];
214                                 continue;
215                         }
216                 }
217                 else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
218                 {
219                         for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
220                         if (i == numpoints)
221                         {
222                                 // no need to split, just go to one side
223                                 parentnodenumpointer = &node->children[1];
224                                 continue;
225                         }
226                 }
227 #endif
228                 // at this point we know it crosses the plane, so we need to split it
229                 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);
230                 if (frontnumpoints > MAX_SVBSP_POLYGONPOINTS)
231                         frontnumpoints = MAX_SVBSP_POLYGONPOINTS;
232                 if (backnumpoints > MAX_SVBSP_POLYGONPOINTS)
233                         backnumpoints = MAX_SVBSP_POLYGONPOINTS;
234                 // recurse the sides and return the resulting bit flags
235                 i = 0;
236                 if (frontnumpoints >= 3)
237                         i |= SVBSP_AddPolygonNode(b, &node->children[0], (int)(node - b->nodes), frontnumpoints, frontpoints, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
238                 if (backnumpoints >= 3)
239                         i |= SVBSP_AddPolygonNode(b, &node->children[1], (int)(node - b->nodes), backnumpoints , backpoints , insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
240                 return i;
241         }
242         // leaf node
243         if (*parentnodenumpointer == -1)
244         {
245                 // empty leaf node; and some geometry survived
246                 // if inserting an occluder, replace this empty leaf with a shadow volume
247 #if 0
248                 for (i = 0;i < numpoints-2;i++)
249                 {
250                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
251                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 1, 0, 0, 0.25);
252                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 1, 0, 0, 0.25);
253                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 1, 0, 0, 0.25);
254                         Debug_PolygonEnd();
255                 }
256 #endif
257                 if (insertoccluder)
258                 {
259                         b->stat_occluders_fragments_accepted++;
260                         SVBSP_InsertOccluderPolygonNodes(b, parentnodenumpointer, parentnodenum, numpoints, points, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
261                 }
262                 else
263                         b->stat_queries_fragments_accepted++;
264                 if (fragmentcallback)
265                         fragmentcallback(fragmentcallback_pointer1, fragmentcallback_number1, b, numpoints, points);
266                 return 2;
267         }
268         else
269         {
270                 // otherwise it's a solid leaf which destroys all polygons inside it
271                 if (insertoccluder)
272                         b->stat_occluders_fragments_rejected++;
273                 else
274                         b->stat_queries_fragments_rejected++;
275 #if 0
276                 for (i = 0;i < numpoints-2;i++)
277                 {
278                         Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
279                         Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 1, 0.25);
280                         Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 1, 0.25);
281                         Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 1, 0.25);
282                         Debug_PolygonEnd();
283                 }
284 #endif
285         }
286         return 1;
287 }
288
289 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)
290 {
291         int i;
292         int nodenum;
293         // don't even consider an empty polygon
294         if (numpoints < 3)
295                 return 0;
296 #if 0
297         for (i = 0;i < numpoints-2;i++)
298         {
299                 Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
300                 Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 1, 0, 0.25);
301                 Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 1, 0, 0.25);
302                 Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 1, 0, 0.25);
303                 Debug_PolygonEnd();
304         }
305 #endif
306         nodenum = 0;
307         i = SVBSP_AddPolygonNode(b, &nodenum, -1, numpoints, points, insertoccluder, fragmentcallback, fragmentcallback_pointer1, fragmentcallback_number1);
308         if (insertoccluder)
309         {
310                 if (i & 2)
311                         b->stat_occluders_accepted++;
312                 else
313                         b->stat_occluders_rejected++;
314         }
315         else
316         {
317                 if (i & 2)
318                         b->stat_queries_accepted++;
319                 else
320                         b->stat_queries_rejected++;
321         }
322         return i;
323 }
324