1 /*
2 ===========================================================================
3 Copyright (C) 1999 - 2005, Id Software, Inc.
4 Copyright (C) 2000 - 2013, Raven Software, Inc.
5 Copyright (C) 2001 - 2013, Activision, Inc.
6 Copyright (C) 2013 - 2015, OpenJK contributors
7
8 This file is part of the OpenJK source code.
9
10 OpenJK is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License version 2 as
12 published by the Free Software Foundation.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, see <http://www.gnu.org/licenses/>.
21 ===========================================================================
22 */
23
24 // this is only used for visualization tools in cm_ debug functions
25
26 #include "cm_local.h"
27
28 // counters are only bumped when running single threaded,
29 // because they are an awefull coherence problem
30 int c_active_windings;
31 int c_peak_windings;
32 int c_winding_allocs;
33 int c_winding_points;
34
pw(winding_t * w)35 void pw(winding_t *w)
36 {
37 int i;
38 for (i=0 ; i<w->numpoints ; i++)
39 printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
40 }
41
42
43 /*
44 =============
45 AllocWinding
46 =============
47 */
AllocWinding(int points)48 winding_t *AllocWinding (int points)
49 {
50 winding_t *w;
51 int s;
52
53 c_winding_allocs++;
54 c_winding_points += points;
55 c_active_windings++;
56 if (c_active_windings > c_peak_windings)
57 c_peak_windings = c_active_windings;
58
59 s = sizeof(vec_t)*3*points + sizeof(int);
60 w = (winding_t *) Z_Malloc (s,TAG_BSP, qtrue);//TAG_WINDING);
61 // memset (w, 0, s); // qtrue above does this
62 return w;
63 }
64
FreeWinding(winding_t * w)65 void FreeWinding (winding_t *w)
66 {
67 if (*(unsigned *)w == 0xdeaddead)
68 Com_Error (ERR_FATAL, "FreeWinding: freed a freed winding");
69 *(unsigned *)w = 0xdeaddead;
70
71 c_active_windings--;
72 Z_Free (w);
73 }
74
WindingBounds(winding_t * w,vec3_t mins,vec3_t maxs)75 void WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
76 {
77 vec_t v;
78 int i,j;
79
80 mins[0] = mins[1] = mins[2] = WORLD_SIZE; // 99999; // WORLD_SIZE instead of MAX_WORLD_COORD so that...
81 maxs[0] = maxs[1] = maxs[2] = -WORLD_SIZE; //-99999; // ... it's guaranteed to be outide of legal
82
83 for (i=0 ; i<w->numpoints ; i++)
84 {
85 for (j=0 ; j<3 ; j++)
86 {
87 v = w->p[i][j];
88 if (v < mins[j])
89 mins[j] = v;
90 if (v > maxs[j])
91 maxs[j] = v;
92 }
93 }
94 }
95
96 /*
97 =================
98 BaseWindingForPlane
99 =================
100 */
BaseWindingForPlane(vec3_t normal,vec_t dist)101 winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
102 {
103 int i, x;
104 vec_t max, v;
105 vec3_t org, vright, vup;
106 winding_t *w;
107
108 // find the major axis
109
110 max = -MAX_MAP_BOUNDS;
111 x = -1;
112 for (i=0 ; i<3; i++)
113 {
114 v = fabs(normal[i]);
115 if (v > max)
116 {
117 x = i;
118 max = v;
119 }
120 }
121 if (x==-1)
122 Com_Error (ERR_DROP, "BaseWindingForPlane: no axis found");
123
124 VectorCopy (vec3_origin, vup);
125 switch (x)
126 {
127 case 0:
128 case 1:
129 vup[2] = 1;
130 break;
131 case 2:
132 vup[0] = 1;
133 break;
134 }
135
136 v = DotProduct (vup, normal);
137 VectorMA (vup, -v, normal, vup);
138 VectorNormalize2(vup, vup);
139
140 VectorScale (normal, dist, org);
141
142 CrossProduct (vup, normal, vright);
143
144 VectorScale (vup, MAX_MAP_BOUNDS, vup);
145 VectorScale (vright, MAX_MAP_BOUNDS, vright);
146
147 // project a really big axis aligned box onto the plane
148 w = AllocWinding (4);
149
150 VectorSubtract (org, vright, w->p[0]);
151 VectorAdd (w->p[0], vup, w->p[0]);
152
153 VectorAdd (org, vright, w->p[1]);
154 VectorAdd (w->p[1], vup, w->p[1]);
155
156 VectorAdd (org, vright, w->p[2]);
157 VectorSubtract (w->p[2], vup, w->p[2]);
158
159 VectorSubtract (org, vright, w->p[3]);
160 VectorSubtract (w->p[3], vup, w->p[3]);
161
162 w->numpoints = 4;
163
164 return w;
165 }
166
167 /*
168 ==================
169 CopyWinding
170 ==================
171 */
CopyWinding(winding_t * w)172 winding_t *CopyWinding (winding_t *w)
173 {
174 intptr_t size;
175 winding_t *c;
176
177 c = AllocWinding (w->numpoints);
178 size = (intptr_t)((winding_t *)0)->p[w->numpoints];
179 memcpy (c, w, size);
180 return c;
181 }
182
183 /*
184 =============
185 ChopWindingInPlace
186 =============
187 */
ChopWindingInPlace(winding_t ** inout,vec3_t normal,vec_t dist,vec_t epsilon)188 void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
189 {
190 winding_t *in;
191 vec_t dists[MAX_POINTS_ON_WINDING+4];
192 int sides[MAX_POINTS_ON_WINDING+4];
193 int counts[3];
194 static vec_t dot; // VC 4.2 optimizer bug if not static
195 int i, j;
196 vec_t *p1, *p2;
197 vec3_t mid;
198 winding_t *f;
199 int maxpts;
200
201 in = *inout;
202 counts[0] = counts[1] = counts[2] = 0;
203
204 // determine sides for each point
205 for (i=0 ; i<in->numpoints ; i++)
206 {
207 dot = DotProduct (in->p[i], normal);
208 dot -= dist;
209 dists[i] = dot;
210 if (dot > epsilon)
211 sides[i] = SIDE_FRONT;
212 else if (dot < -epsilon)
213 sides[i] = SIDE_BACK;
214 else
215 {
216 sides[i] = SIDE_ON;
217 }
218 counts[sides[i]]++;
219 }
220 sides[i] = sides[0];
221 dists[i] = dists[0];
222
223 if (!counts[0])
224 {
225 FreeWinding (in);
226 *inout = NULL;
227 return;
228 }
229 if (!counts[1])
230 return; // inout stays the same
231
232 maxpts = in->numpoints+4; // cant use counts[0]+2 because
233 // of fp grouping errors
234
235 f = AllocWinding (maxpts);
236
237 for (i=0 ; i<in->numpoints ; i++)
238 {
239 p1 = in->p[i];
240
241 if (sides[i] == SIDE_ON)
242 {
243 VectorCopy (p1, f->p[f->numpoints]);
244 f->numpoints++;
245 continue;
246 }
247
248 if (sides[i] == SIDE_FRONT)
249 {
250 VectorCopy (p1, f->p[f->numpoints]);
251 f->numpoints++;
252 }
253
254 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
255 continue;
256
257 // generate a split point
258 p2 = in->p[(i+1)%in->numpoints];
259
260 dot = dists[i] / (dists[i]-dists[i+1]);
261 for (j=0 ; j<3 ; j++)
262 { // avoid round off error when possible
263 if (normal[j] == 1)
264 mid[j] = dist;
265 else if (normal[j] == -1)
266 mid[j] = -dist;
267 else
268 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
269 }
270
271 VectorCopy (mid, f->p[f->numpoints]);
272 f->numpoints++;
273 }
274
275 if (f->numpoints > maxpts)
276 Com_Error (ERR_DROP, "ClipWinding: points exceeded estimate");
277 if (f->numpoints > MAX_POINTS_ON_WINDING)
278 Com_Error (ERR_DROP, "ClipWinding: MAX_POINTS_ON_WINDING");
279
280 FreeWinding (in);
281 *inout = f;
282 }
283