finally managed to fix the r_shadow_portallight bug (had to reverse portal handling...
[divverent/darkplaces.git] / winding.c
1
2 #include "quakedef.h"
3 #include "winding.h"
4
5 // this code came from qbsp source
6
7 #define MAX_POINTS_ON_WINDING 64
8
9 winding_t *Winding_New(int points)
10 {
11         winding_t *w;
12         int size;
13
14         if (points > MAX_POINTS_ON_WINDING)
15                 Sys_Error("Winding_New: too many points\n");
16
17         size = sizeof(winding_t) + sizeof(double[3]) * (points - 8);
18         w = Mem_Alloc(loadmodel->mempool, size);
19         //Mem_Alloc clears
20         //memset(w, 0, size);
21
22         return w;
23 }
24
25 void Winding_Free(winding_t *w)
26 {
27         Mem_Free(w);
28 }
29
30 winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist)
31 {
32         int x;
33         double max, v, org[3], vright[3], vup[3], normal[3];
34         winding_t *w;
35
36         normal[0] = normalx;
37         normal[1] = normaly;
38         normal[2] = normalz;
39 #if 0
40         VectorVectorsDouble(normal, vright, vup);
41 #else
42         // find the major axis
43         x = 0;
44         max = fabs(normal[0]);
45         v = fabs(normal[1]);
46         if(v > max)
47         {
48                 x = 1;
49                 max = v;
50         }
51         v = fabs(normal[2]);
52         if(v > max)
53         {
54                 x = 2;
55                 max = v;
56         }
57
58         VectorClear(vup);
59         switch(x)
60         {
61         case 0:
62         case 1:
63                 vup[2] = 1;
64                 break;
65         case 2:
66                 vup[0] = 1;
67                 break;
68         }
69
70         v = DotProduct(vup, normal);
71         VectorMA(vup, -v, normal, vup);
72         VectorNormalize(vup);
73 #endif
74
75         VectorScale(normal, dist, org);
76
77         CrossProduct(vup, normal, vright);
78
79         VectorScale(vup, 1024.0*1024.0*1024.0, vup);
80         VectorScale(vright, 1024.0*1024.0*1024.0, vright);
81
82         // project a really big axis aligned box onto the plane
83         w = Winding_New(4);
84
85         VectorSubtract(org, vright, w->points[0]);
86         VectorAdd(w->points[0], vup, w->points[0]);
87
88         VectorAdd(org, vright, w->points[1]);
89         VectorAdd(w->points[1], vup, w->points[1]);
90
91         VectorAdd(org, vright, w->points[2]);
92         VectorSubtract(w->points[2], vup, w->points[2]);
93
94         VectorSubtract(org, vright, w->points[3]);
95         VectorSubtract(w->points[3], vup, w->points[3]);
96
97 #if 0
98         {
99                 double n[3];
100                 TriangleNormal(w->points[0], w->points[1], w->points[2], n);
101                 VectorNormalize(n);
102                 if (fabs(DotProduct(n, normal) - 1) > 0.01f)
103                         Con_Printf("%.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f) != %.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f)\n", normal[0], normal[1], normal[2], vright[0], vright[1], vright[2], vup[0], vup[1], vup[2], n[0], n[1], n[2], w->points[0][0], w->points[0][1], w->points[0][2], w->points[1][0], w->points[1][1], w->points[1][2], w->points[2][0], w->points[2][1], w->points[2][2], w->points[3][0], w->points[3][1], w->points[3][2]);
104         }
105 #endif
106
107         w->numpoints = 4;
108
109         return w;
110 }
111
112 //Clips the winding to the plane, returning the new winding on the positive side
113 //Frees the input winding.
114 //If keepon is true, an exactly on-plane winding will be saved, otherwise
115 //it will be clipped away.
116 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
117 {
118         winding_t *neww;
119         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
120         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
121
122         splitnormal[0] = splitnormalx;
123         splitnormal[1] = splitnormaly;
124         splitnormal[2] = splitnormalz;
125         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
126
127         // determine sides for each point
128         for (i = 0;i < in->numpoints;i++)
129         {
130                 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
131                 if (dot > ON_EPSILON)
132                         sides[i] = SIDE_FRONT;
133                 else if (dot < -ON_EPSILON)
134                         sides[i] = SIDE_BACK;
135                 else
136                         sides[i] = SIDE_ON;
137                 counts[sides[i]]++;
138         }
139         sides[i] = sides[0];
140         dists[i] = dists[0];
141
142         if (keepon && !counts[0] && !counts[1])
143                 return in;
144
145         if (!counts[0])
146         {
147                 Winding_Free(in);
148                 return NULL;
149         }
150         if (!counts[1])
151                 return in;
152
153         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
154         if (maxpts > MAX_POINTS_ON_WINDING)
155                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
156
157         neww = Winding_New(maxpts);
158
159         for (i = 0;i < in->numpoints;i++)
160         {
161                 if (neww->numpoints >= maxpts)
162                         Sys_Error("Winding_Clip: points exceeded estimate");
163
164                 p1 = in->points[i];
165
166                 if (sides[i] == SIDE_ON)
167                 {
168                         VectorCopy(p1, neww->points[neww->numpoints]);
169                         neww->numpoints++;
170                         continue;
171                 }
172
173                 if (sides[i] == SIDE_FRONT)
174                 {
175                         VectorCopy(p1, neww->points[neww->numpoints]);
176                         neww->numpoints++;
177                 }
178
179                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
180                         continue;
181
182                 // generate a split point
183                 p2 = in->points[(i+1)%in->numpoints];
184
185                 dot = dists[i] / (dists[i]-dists[i+1]);
186                 for (j = 0;j < 3;j++)
187                 {       // avoid round off error when possible
188                         if (splitnormal[j] == 1)
189                                 mid[j] = splitdist;
190                         else if (splitnormal[j] == -1)
191                                 mid[j] = -splitdist;
192                         else
193                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
194                 }
195
196                 VectorCopy(mid, neww->points[neww->numpoints]);
197                 neww->numpoints++;
198         }
199
200         // free the original winding
201         Winding_Free(in);
202
203         return neww;
204 }
205
206
207 //Divides a winding by a plane, producing one or two windings.  The
208 //original winding is not damaged or freed.  If only on one side, the
209 //returned winding will be the input winding.  If on both sides, two
210 //new windings will be created.
211 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
212 {
213         winding_t *f, *b;
214         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
215         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
216
217         splitnormal[0] = splitnormalx;
218         splitnormal[1] = splitnormaly;
219         splitnormal[2] = splitnormalz;
220
221         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
222
223         // determine sides for each point
224         for (i = 0;i < in->numpoints;i++)
225         {
226                 dot = DotProduct(in->points[i], splitnormal);
227                 dot -= splitdist;
228                 dists[i] = dot;
229                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
230                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
231                 else sides[i] = SIDE_ON;
232                 counts[sides[i]]++;
233         }
234         sides[i] = sides[0];
235         dists[i] = dists[0];
236
237         *front = *back = NULL;
238
239         if (!counts[0])
240         {
241                 *back = in;
242                 return;
243         }
244         if (!counts[1])
245         {
246                 *front = in;
247                 return;
248         }
249
250         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
251
252         if (maxpts > MAX_POINTS_ON_WINDING)
253                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
254
255         *front = f = Winding_New(maxpts);
256         *back = b = Winding_New(maxpts);
257
258         for (i = 0;i < in->numpoints;i++)
259         {
260                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
261                         Sys_Error("Winding_Divide: points exceeded estimate");
262
263                 p1 = in->points[i];
264
265                 if (sides[i] == SIDE_ON)
266                 {
267                         VectorCopy(p1, f->points[f->numpoints]);
268                         f->numpoints++;
269                         VectorCopy(p1, b->points[b->numpoints]);
270                         b->numpoints++;
271                         continue;
272                 }
273
274                 if (sides[i] == SIDE_FRONT)
275                 {
276                         VectorCopy(p1, f->points[f->numpoints]);
277                         f->numpoints++;
278                 }
279                 else if (sides[i] == SIDE_BACK)
280                 {
281                         VectorCopy(p1, b->points[b->numpoints]);
282                         b->numpoints++;
283                 }
284
285                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
286                         continue;
287
288                 // generate a split point
289                 p2 = in->points[(i+1)%in->numpoints];
290
291                 dot = dists[i] / (dists[i]-dists[i+1]);
292                 for (j = 0;j < 3;j++)
293                 {       // avoid round off error when possible
294                         if (splitnormal[j] == 1)
295                                 mid[j] = splitdist;
296                         else if (splitnormal[j] == -1)
297                                 mid[j] = -splitdist;
298                         else
299                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
300                 }
301
302                 VectorCopy(mid, f->points[f->numpoints]);
303                 f->numpoints++;
304                 VectorCopy(mid, b->points[b->numpoints]);
305                 b->numpoints++;
306         }
307 }
308
309