added CVAR_SAVE and CVAR_NOTIFY flags to cvar_t structure (at the beginning), updated...
[divverent/darkplaces.git] / portals.c
1
2 #include "quakedef.h"
3
4 #define MAXRECURSIVEPORTALPLANES 1024
5 #define MAXRECURSIVEPORTALS 256
6
7 tinyplane_t portalplanes[MAXRECURSIVEPORTALPLANES];
8 int portalplanestack[MAXRECURSIVEPORTALS];
9 int portalplanecount;
10 int ranoutofportalplanes;
11 int ranoutofportals;
12
13 int R_ClipPolygonToPlane(float *in, float *out, int inpoints, int maxoutpoints, tinyplane_t *p)
14 {
15         int i, outpoints, prevside, side;
16         float *prevpoint, prevdist, dist, dot;
17
18         if (inpoints < 3)
19                 return inpoints;
20         // begin with the last point, then enter the loop with the first point as current
21         prevpoint = in + 3 * (inpoints - 1);
22         prevdist = DotProduct(prevpoint, p->normal) - p->dist;
23         prevside = prevdist >= 0 ? SIDE_FRONT : SIDE_BACK;
24         i = 0;
25         outpoints = 0;
26         goto begin;
27         for (;i < inpoints;i++)
28         {
29                 prevpoint = in;
30                 prevdist = dist;
31                 prevside = side;
32                 in += 3;
33
34 begin:
35                 dist = DotProduct(in, p->normal) - p->dist;
36                 side = dist >= 0 ? SIDE_FRONT : SIDE_BACK;
37
38                 if (prevside == SIDE_FRONT)
39                 {
40                         if (outpoints >= maxoutpoints)
41                                 return -1;
42                         VectorCopy(prevpoint, out);
43                         out += 3;
44                         outpoints++;
45                         if (side == SIDE_FRONT)
46                                 continue;
47                 }
48                 else if (side == SIDE_BACK)
49                         continue;
50
51                 // generate a split point
52                 if (outpoints >= maxoutpoints)
53                         return -1;
54                 dot = prevdist / (prevdist - dist);
55                 out[0] = prevpoint[0] + dot * (in[0] - prevpoint[0]);
56                 out[1] = prevpoint[1] + dot * (in[1] - prevpoint[1]);
57                 out[2] = prevpoint[2] + dot * (in[2] - prevpoint[2]);
58                 out += 3;
59                 outpoints++;
60         }
61
62         return outpoints;
63 }
64
65 float portaltemppoints[2][256][3];
66 float portaltemppoints2[256][3];
67
68 /*
69 void R_TriangleToPlane(vec3_t point1, vec3_t point2, vec3_t point3, tinyplane_t *p)
70 {
71         vec3_t v1, v2;
72         VectorSubtract(point1, point2, v1);
73         VectorSubtract(point3, point2, v2);
74         CrossProduct(v1, v2, p->normal);
75 //      VectorNormalize(p->normal);
76         VectorNormalizeFast(p->normal);
77         p->dist = DotProduct(point1, p->normal);
78 }
79 */
80
81 int R_PortalThroughPortalPlanes(tinyplane_t *clipplanes, int clipnumplanes, float *targpoints, int targnumpoints, float *out, int maxpoints)
82 {
83         int numpoints, i;
84         if (targnumpoints < 3)
85                 return targnumpoints;
86         if (maxpoints < 3)
87                 return -1;
88         numpoints = targnumpoints;
89         memcpy(&portaltemppoints[0][0][0], targpoints, numpoints * 3 * sizeof(float));
90         for (i = 0;i < clipnumplanes;i++)
91         {
92                 numpoints = R_ClipPolygonToPlane(&portaltemppoints[0][0][0], &portaltemppoints[1][0][0], numpoints, 256, clipplanes + i);
93                 if (numpoints < 3)
94                         return numpoints;
95                 memcpy(&portaltemppoints[0][0][0], &portaltemppoints[1][0][0], numpoints * 3 * sizeof(float));
96         }
97         if (numpoints > maxpoints)
98                 return -1;
99         memcpy(out, &portaltemppoints[1][0][0], numpoints * 3 * sizeof(float));
100         return numpoints;
101 }
102
103 static int portal_markid = 0;
104
105 int Portal_RecursiveFlowSearch (mleaf_t *leaf, vec3_t eye, int firstclipplane, int numclipplanes)
106 {
107         mportal_t *p;
108
109         if (leaf->portalmarkid == portal_markid)
110                 return true;
111
112         // follow portals into other leafs
113         for (p = leaf->portals;p;p = p->next)
114         {
115                 int newpoints, i, prev;
116                 vec3_t center;
117                 vec3_t v1, v2;
118                 tinyplane_t *newplanes;
119                 // only flow through portals facing away from the viewer
120                 if (PlaneDiff(eye, (&p->plane)) < 0)
121                 {
122                         newpoints = R_PortalThroughPortalPlanes(&portalplanes[firstclipplane], numclipplanes, (float *) p->points, p->numpoints, &portaltemppoints2[0][0], 256);
123                         if (newpoints < 3)
124                                 continue;
125                         else if (firstclipplane + numclipplanes + newpoints > MAXRECURSIVEPORTALPLANES)
126                                 ranoutofportalplanes = true;
127                         else
128                         {
129                                 // find the center by averaging
130                                 VectorClear(center);
131                                 for (i = 0;i < newpoints;i++)
132                                         VectorAdd(center, portaltemppoints2[i], center);
133                                 // ixtable is a 1.0f / N table
134                                 VectorScale(center, ixtable[newpoints], center);
135                                 // calculate the planes, and make sure the polygon can see it's own center
136                                 newplanes = &portalplanes[firstclipplane + numclipplanes];
137                                 for (prev = newpoints - 1, i = 0;i < newpoints;prev = i, i++)
138                                 {
139 //                                      R_TriangleToPlane(eye, portaltemppoints2[i], portaltemppoints2[prev], newplanes + i);
140                                         VectorSubtract(eye, portaltemppoints2[i], v1);
141                                         VectorSubtract(portaltemppoints2[prev], portaltemppoints2[i], v2);
142                                         CrossProduct(v1, v2, newplanes[i].normal);
143                                         VectorNormalizeFast(newplanes[i].normal);
144                                         newplanes[i].dist = DotProduct(eye, newplanes[i].normal);
145                                         if (DotProduct(newplanes[i].normal, center) <= newplanes[i].dist)
146                                         {
147                                                 // polygon can't see it's own center, discard and use parent portal
148                                                 break;
149                                         }
150                                 }
151                                 if (i == newpoints)
152                                 {
153                                         if (Portal_RecursiveFlowSearch(p->past, eye, firstclipplane + numclipplanes, newpoints))
154                                                 return true;
155                         }
156                                 else
157                                 {
158                                         if (Portal_RecursiveFlowSearch(p->past, eye, firstclipplane, numclipplanes))
159                                                 return true;
160                         }
161                         }
162                 }
163         }
164
165         return false;
166 }
167
168 //float viewportalpoints[16*3];
169
170 void Portal_PolygonRecursiveMarkLeafs(mnode_t *node, float *polypoints, int numpoints)
171 {
172         int i, front;
173         float *p;
174
175 loc0:
176         if (node->contents < 0)
177         {
178                 ((mleaf_t *)node)->portalmarkid = portal_markid;
179                 return;
180         }
181
182         front = 0;
183         for (i = 0, p = polypoints;i < numpoints;i++, p += 3)
184         {
185                 if (DotProduct(p, node->plane->normal) > node->plane->dist)
186                         front++;
187         }
188         if (front > 0)
189         {
190                 if (front == numpoints)
191                 {
192                         node = node->children[0];
193                         goto loc0;
194                 }
195                 else
196                         Portal_PolygonRecursiveMarkLeafs(node->children[0], polypoints, numpoints);
197         }
198         node = node->children[1];
199         goto loc0;
200 }
201
202 int Portal_CheckPolygon(model_t *model, vec3_t eye, float *polypoints, int numpoints)
203 {
204         int i, prev, returnvalue;
205         mleaf_t *eyeleaf;
206         vec3_t center, v1, v2;
207
208         portal_markid++;
209
210         Portal_PolygonRecursiveMarkLeafs(model->nodes, polypoints, numpoints);
211
212         eyeleaf = Mod_PointInLeaf(eye, model);
213
214         // find the center by averaging
215         VectorClear(center);
216         for (i = 0;i < numpoints;i++)
217                 VectorAdd(center, (&polypoints[i * 3]), center);
218         // ixtable is a 1.0f / N table
219         VectorScale(center, ixtable[numpoints], center);
220
221         // calculate the planes, and make sure the polygon can see it's own center
222         for (prev = numpoints - 1, i = 0;i < numpoints;prev = i, i++)
223         {
224 //              R_TriangleToPlane(eye, portaltemppoints2[i], portaltemppoints2[prev], newplanes + i);
225                 VectorSubtract(eye, (&polypoints[i * 3]), v1);
226                 VectorSubtract((&polypoints[prev * 3]), (&polypoints[i * 3]), v2);
227                 CrossProduct(v1, v2, portalplanes[i].normal);
228                 VectorNormalizeFast(portalplanes[i].normal);
229                 portalplanes[i].dist = DotProduct(eye, portalplanes[i].normal);
230                 if (DotProduct(portalplanes[i].normal, center) <= portalplanes[i].dist)
231                 {
232                         // polygon can't see it's own center, discard
233                         return false;
234                 }
235         }
236
237         portalplanecount = 0;
238         ranoutofportalplanes = false;
239         ranoutofportals = false;
240
241         returnvalue = Portal_RecursiveFlowSearch(eyeleaf, eye, 0, numpoints);
242
243         if (ranoutofportalplanes)
244                 Con_Printf("Portal_RecursiveFlowSearch: ran out of %d plane stack when recursing through portals\n", MAXRECURSIVEPORTALPLANES);
245         if (ranoutofportals)
246                 Con_Printf("Portal_RecursiveFlowSearch: ran out of %d portal stack when recursing through portals\n", MAXRECURSIVEPORTALS);
247
248         return returnvalue;
249 }
250
251 float boxpoints[4*3];
252
253 #define Portal_MinsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4) \
254 {\
255         if (eye[(axis)] < ((axisvalue) - 0.5f))\
256         {\
257                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
258                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
259                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
260                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
261                 if (Portal_CheckPolygon(model, eye, boxpoints, 4))\
262                         return true;\
263         }\
264 }
265
266 #define Portal_MaxsBoxPolygon(axis, axisvalue, x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4) \
267 {\
268         if (eye[(axis)] > ((axisvalue) + 0.5f))\
269         {\
270                 boxpoints[ 0] = x1;boxpoints[ 1] = y1;boxpoints[ 2] = z1;\
271                 boxpoints[ 3] = x2;boxpoints[ 4] = y2;boxpoints[ 5] = z2;\
272                 boxpoints[ 6] = x3;boxpoints[ 7] = y3;boxpoints[ 8] = z3;\
273                 boxpoints[ 9] = x4;boxpoints[10] = y4;boxpoints[11] = z4;\
274                 if (Portal_CheckPolygon(model, eye, boxpoints, 4))\
275                         return true;\
276         }\
277 }
278
279 int Portal_CheckBox(model_t *model, vec3_t eye, vec3_t a, vec3_t b)
280 {
281         if (eye[0] >= (a[0] - 1.0f) && eye[0] < (b[0] + 1.0f)
282          && eye[1] >= (a[1] - 1.0f) && eye[1] < (b[1] + 1.0f)
283          && eye[2] >= (a[2] - 1.0f) && eye[2] < (b[2] + 1.0f))
284         {
285                 return true;
286         }
287
288         Portal_MinsBoxPolygon
289         (
290                 0, a[0],
291                 a[0], a[1], a[2],
292                 a[0], b[1], a[2],
293                 a[0], b[1], b[2],
294                 a[0], a[1], b[2]
295         );
296         Portal_MaxsBoxPolygon
297         (
298                 0, b[0],
299                 b[0], b[1], a[2],
300                 b[0], a[1], a[2],
301                 b[0], a[1], b[2],
302                 b[0], b[1], b[2]
303         );
304         Portal_MinsBoxPolygon
305         (
306                 1, a[1],
307                 b[0], a[1], a[2],
308                 a[0], a[1], a[2],
309                 a[0], a[1], b[2],
310                 b[0], a[1], b[2]
311         );
312         Portal_MaxsBoxPolygon
313         (
314                 1, b[1],
315                 a[0], b[1], a[2],
316                 b[0], b[1], a[2],
317                 b[0], b[1], b[2],
318                 a[0], b[1], b[2]
319         );
320         Portal_MinsBoxPolygon
321         (
322                 2, a[2],
323                 a[0], a[1], a[2],
324                 b[0], a[1], a[2],
325                 b[0], b[1], a[2],
326                 a[0], b[1], a[2]
327         );
328         Portal_MaxsBoxPolygon
329         (
330                 2, b[2],
331                 b[0], a[1], b[2],
332                 a[0], a[1], b[2],
333                 a[0], b[1], b[2],
334                 b[0], b[1], b[2]
335         );
336
337         return false;
338 }