forgot to commit these
[xonotic/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         w->numpoints = 4;
98
99         return w;
100 }
101
102 //Clips the winding to the plane, returning the new winding on the positive side
103 //Frees the input winding.
104 //If keepon is true, an exactly on-plane winding will be saved, otherwise
105 //it will be clipped away.
106 winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon)
107 {
108         winding_t *neww;
109         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
110         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
111
112         splitnormal[0] = splitnormalx;
113         splitnormal[1] = splitnormaly;
114         splitnormal[2] = splitnormalz;
115         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
116
117         // determine sides for each point
118         for (i = 0;i < in->numpoints;i++)
119         {
120                 dists[i] = dot = DotProduct(in->points[i], splitnormal) - splitdist;
121                 if (dot > ON_EPSILON)
122                         sides[i] = SIDE_FRONT;
123                 else if (dot < -ON_EPSILON)
124                         sides[i] = SIDE_BACK;
125                 else
126                         sides[i] = SIDE_ON;
127                 counts[sides[i]]++;
128         }
129         sides[i] = sides[0];
130         dists[i] = dists[0];
131
132         if (keepon && !counts[0] && !counts[1])
133                 return in;
134
135         if (!counts[0])
136         {
137                 Winding_Free(in);
138                 return NULL;
139         }
140         if (!counts[1])
141                 return in;
142
143         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
144         if (maxpts > MAX_POINTS_ON_WINDING)
145                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
146
147         neww = Winding_New(maxpts);
148
149         for (i = 0;i < in->numpoints;i++)
150         {
151                 if (neww->numpoints >= maxpts)
152                         Sys_Error("Winding_Clip: points exceeded estimate");
153
154                 p1 = in->points[i];
155
156                 if (sides[i] == SIDE_ON)
157                 {
158                         VectorCopy(p1, neww->points[neww->numpoints]);
159                         neww->numpoints++;
160                         continue;
161                 }
162
163                 if (sides[i] == SIDE_FRONT)
164                 {
165                         VectorCopy(p1, neww->points[neww->numpoints]);
166                         neww->numpoints++;
167                 }
168
169                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
170                         continue;
171
172                 // generate a split point
173                 p2 = in->points[(i+1)%in->numpoints];
174
175                 dot = dists[i] / (dists[i]-dists[i+1]);
176                 for (j = 0;j < 3;j++)
177                 {       // avoid round off error when possible
178                         if (splitnormal[j] == 1)
179                                 mid[j] = splitdist;
180                         else if (splitnormal[j] == -1)
181                                 mid[j] = -splitdist;
182                         else
183                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
184                 }
185
186                 VectorCopy(mid, neww->points[neww->numpoints]);
187                 neww->numpoints++;
188         }
189
190         // free the original winding
191         Winding_Free(in);
192
193         return neww;
194 }
195
196
197 //Divides a winding by a plane, producing one or two windings.  The
198 //original winding is not damaged or freed.  If only on one side, the
199 //returned winding will be the input winding.  If on both sides, two
200 //new windings will be created.
201 void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back)
202 {
203         winding_t *f, *b;
204         double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1];
205         int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1];
206
207         splitnormal[0] = splitnormalx;
208         splitnormal[1] = splitnormaly;
209         splitnormal[2] = splitnormalz;
210
211         counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
212
213         // determine sides for each point
214         for (i = 0;i < in->numpoints;i++)
215         {
216                 dot = DotProduct(in->points[i], splitnormal);
217                 dot -= splitdist;
218                 dists[i] = dot;
219                 if (dot > ON_EPSILON) sides[i] = SIDE_FRONT;
220                 else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK;
221                 else sides[i] = SIDE_ON;
222                 counts[sides[i]]++;
223         }
224         sides[i] = sides[0];
225         dists[i] = dists[0];
226
227         *front = *back = NULL;
228
229         if (!counts[0])
230         {
231                 *back = in;
232                 return;
233         }
234         if (!counts[1])
235         {
236                 *front = in;
237                 return;
238         }
239
240         maxpts = in->numpoints+4;       // can't use counts[0]+2 because of fp grouping errors
241
242         if (maxpts > MAX_POINTS_ON_WINDING)
243                 Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING");
244
245         *front = f = Winding_New(maxpts);
246         *back = b = Winding_New(maxpts);
247
248         for (i = 0;i < in->numpoints;i++)
249         {
250                 if (f->numpoints >= maxpts || b->numpoints >= maxpts)
251                         Sys_Error("Winding_Divide: points exceeded estimate");
252
253                 p1 = in->points[i];
254
255                 if (sides[i] == SIDE_ON)
256                 {
257                         VectorCopy(p1, f->points[f->numpoints]);
258                         f->numpoints++;
259                         VectorCopy(p1, b->points[b->numpoints]);
260                         b->numpoints++;
261                         continue;
262                 }
263
264                 if (sides[i] == SIDE_FRONT)
265                 {
266                         VectorCopy(p1, f->points[f->numpoints]);
267                         f->numpoints++;
268                 }
269                 else if (sides[i] == SIDE_BACK)
270                 {
271                         VectorCopy(p1, b->points[b->numpoints]);
272                         b->numpoints++;
273                 }
274
275                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
276                         continue;
277
278                 // generate a split point
279                 p2 = in->points[(i+1)%in->numpoints];
280
281                 dot = dists[i] / (dists[i]-dists[i+1]);
282                 for (j = 0;j < 3;j++)
283                 {       // avoid round off error when possible
284                         if (splitnormal[j] == 1)
285                                 mid[j] = splitdist;
286                         else if (splitnormal[j] == -1)
287                                 mid[j] = -splitdist;
288                         else
289                                 mid[j] = p1[j] + dot* (p2[j]-p1[j]);
290                 }
291
292                 VectorCopy(mid, f->points[f->numpoints]);
293                 f->numpoints++;
294                 VectorCopy(mid, b->points[b->numpoints]);
295                 b->numpoints++;
296         }
297 }
298
299