- Radiant is now Vista compatible (Aero must be disabled)
[xonotic/netradiant.git] / contrib / bobtoolz / DWinding.cpp
1 /*
2 BobToolz plugin for GtkRadiant
3 Copyright (C) 2001 Gordon Biggans
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18 */
19
20 // DWinding.cpp: implementation of the DWinding class.
21 //
22 //////////////////////////////////////////////////////////////////////
23
24 #include "DWinding.h"
25
26 #include <list>
27
28 #include "DPoint.h"
29 #include "DPlane.h"
30
31 //////////////////////////////////////////////////////////////////////
32 // Construction/Destruction
33 //////////////////////////////////////////////////////////////////////
34
35 DWinding::DWinding()
36 {
37         numpoints = 0;
38         p = NULL;
39 }
40
41 DWinding::~DWinding()
42 {
43         if(p)
44                 delete[] p;
45 }
46
47 //////////////////////////////////////////////////////////////////////
48 // Implementation
49 //////////////////////////////////////////////////////////////////////
50
51 #define BOGUS_RANGE     4096
52
53 void DWinding::AllocWinding(int points)
54 {
55         numpoints = points;
56         if(p)
57                 delete[] p;
58         p = new vec3_t[points];
59 }
60
61 vec_t DWinding::WindingArea()
62 {
63         vec3_t  d1, d2, cross;
64         vec_t   total;
65
66         total = 0;
67         for (int i = 2; i < numpoints ; i++)
68         {
69                 VectorSubtract (p[i-1], p[0], d1);
70                 VectorSubtract (p[i], p[0], d2);
71
72                 CrossProduct (d1, d2, cross);
73
74                 total += 0.5f * VectorLength ( cross );
75         }
76
77         return total;
78 }
79
80 void DWinding::RemoveColinearPoints()
81 {
82         vec3_t  p2[MAX_POINTS_ON_WINDING];
83
84         int nump = 0;
85         for (int i = 0; i < numpoints; i++)
86         {
87                 int j = (i+1)%numpoints;
88                 int k = (i+numpoints-1)%numpoints;
89
90                 vec3_t  v1, v2;
91                 VectorSubtract (p[j], p[i], v1);
92                 VectorSubtract (p[i], p[k], v2);
93                 VectorNormalize(v1, v1);
94                 VectorNormalize(v2, v2);
95
96                 if (DotProduct(v1, v2) < 0.999)
97                 {
98                         VectorCopy (p[i], p2[nump]);
99                         nump++;
100                 }
101         }
102
103         if (nump == numpoints)
104                 return;
105
106         AllocWinding(nump);
107         memcpy (p, p2, nump*sizeof(vec3_t));
108 }
109
110 DPlane* DWinding::WindingPlane()
111 {
112         DPlane* newPlane = new DPlane(p[0], p[1], p[2], NULL);
113         return newPlane;
114 }
115
116 void DWinding::WindingBounds(vec3_t mins, vec3_t maxs)
117 {
118         if(numpoints == 0)
119                 return;
120
121         VectorCopy(mins, p[0]);
122         VectorCopy(maxs, p[0]);
123
124         for (int i = 1; i < numpoints ;i++)
125         {
126                 for (int j = 0; j < 3; j++)
127                 {
128                         vec_t v = p[i][j];
129                         if (v < mins[j])
130                                 mins[j] = v;
131                         if (v > maxs[j])
132                                 maxs[j] = v;
133                 }
134         }
135 }
136
137 void DWinding::WindingCentre(vec3_t centre)
138 {
139         VectorCopy (vec3_origin, centre);
140         for (int i = 0; i < numpoints; i++)
141                 VectorAdd (p[i], centre, centre);
142
143         float scale = 1.0f/numpoints;
144         VectorScale (centre, scale, centre);
145 }
146
147
148 DWinding* DWinding::CopyWinding()
149 {
150         DWinding* c = new DWinding;
151         c->AllocWinding(numpoints);
152         memcpy (c->p, p, numpoints*sizeof(vec3_t));
153         return c;
154 }
155
156
157 int DWinding::WindingOnPlaneSide(vec3_t normal, vec_t dist)
158 {
159         bool front = false;
160         bool back = false;
161
162         for (int i = 0; i < numpoints; i++)
163         {
164                 vec_t d = DotProduct (p[i], normal) - dist;
165                 if (d < -ON_EPSILON)
166                 {
167                         if (front)
168                                 return SIDE_CROSS;
169                         back = true;
170                         continue;
171                 }
172                 if (d > ON_EPSILON)
173                 {
174                         if (back)
175                                 return SIDE_CROSS;
176                         front = true;
177                         continue;
178                 }
179         }
180
181         if (back)
182                 return SIDE_BACK;
183         if (front)
184                 return SIDE_FRONT;
185         return SIDE_ON;
186 }
187
188 void DWinding::CheckWinding()
189 {
190         vec_t   *p1, *p2;
191         vec_t   edgedist;
192         vec3_t  dir, edgenormal;
193
194         if (numpoints < 3)
195                 globalOutputStream() << "CheckWinding: " << numpoints << " points\n";
196         
197         vec_t area = WindingArea();
198         if (area < 1)
199                 globalOutputStream() << "CheckWinding: " << area << " area\n";
200
201         DPlane* wPlane = WindingPlane ();
202         int i;
203         for (i = 0; i < numpoints; i++)
204         {
205                 p1 = p[i];
206
207                 int j;
208                 for (j = 0; j < 3; j++)
209                         if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
210                                 globalOutputStream() << "CheckFace: BOGUS_RANGE: " << p1[j] << "\n";
211
212                 j = i + 1 == numpoints ? 0 : i + 1;
213                 
214                 // check the point is on the face plane
215                 vec_t d = DotProduct (p1, wPlane->normal) - wPlane->_d;
216                 if (d < -ON_EPSILON || d > ON_EPSILON)
217                         globalOutputStream() << "CheckWinding: point off plane\n";
218         
219                 // check the edge isnt degenerate
220                 p2 = p[j];
221                 VectorSubtract (p2, p1, dir);
222                 
223                 if (VectorLength (dir) < ON_EPSILON)
224                         globalOutputStream() << "CheckWinding: degenerate edge\n";
225                         
226                 CrossProduct (wPlane->normal, dir, edgenormal);
227                 VectorNormalize (edgenormal, edgenormal);
228                 edgedist = DotProduct (p1, edgenormal);
229                 
230                 // all other points must be on front side
231                 for (j = 0 ; j < numpoints ; j++)
232                 {
233                         if (j == i)
234                                 continue;
235
236                         d = DotProduct (p[j], edgenormal);
237                         if (d > (edgedist + ON_EPSILON))
238                                 globalOutputStream() << "CheckWinding: non-convex\n";
239                 }
240         }
241
242         delete wPlane;
243 }
244
245 DWinding* DWinding::ReverseWinding()
246 {
247         DWinding* c = new DWinding;
248         c->AllocWinding(numpoints);
249
250         for (int i = 0; i < numpoints ; i++)
251                 VectorCopy (p[numpoints-1-i], c->p[i]);
252
253         return c;
254 }
255
256 bool DWinding::ChopWindingInPlace(DPlane* chopPlane, vec_t epsilon)
257 {
258         vec_t   dists[MAX_POINTS_ON_WINDING+4];
259         int             sides[MAX_POINTS_ON_WINDING+4];
260         int             counts[3];
261         vec_t   *p1, *p2;
262         vec3_t  mid;
263
264         counts[0] = counts[1] = counts[2] = 0;
265
266 // determine sides for each point
267         int i;
268         for (i = 0; i < numpoints; i++)
269         {
270                 vec_t dot = DotProduct (p[i], chopPlane->normal);
271                 dot -= chopPlane->_d;
272                 dists[i] = dot;
273                 
274                 if (dot > epsilon)
275                         sides[i] = SIDE_FRONT;
276                 else if (dot < -epsilon)
277                         sides[i] = SIDE_BACK;
278                 else
279                         sides[i] = SIDE_ON;
280
281                 counts[sides[i]]++;
282         }
283         sides[i] = sides[0];
284         dists[i] = dists[0];
285         
286         if (!counts[0])
287         {
288                 delete this;
289                 return false;
290         }
291
292         if (!counts[1])
293                 return true;
294
295         int maxpts = numpoints+4;       // cant use counts[0]+2 because
296                                                                 // of fp grouping errors
297
298         DWinding* f = new DWinding;
299         f->AllocWinding(maxpts);
300         f->numpoints = 0;
301                 
302         for (i = 0; i < numpoints; i++)
303         {
304                 p1 = p[i];
305                 
306                 if (sides[i] == SIDE_ON)
307                 {
308                         VectorCopy (p1, f->p[f->numpoints]);
309                         f->numpoints++;
310                         continue;
311                 }
312         
313                 if (sides[i] == SIDE_FRONT)
314                 {
315                         VectorCopy (p1, f->p[f->numpoints]);
316                         f->numpoints++;
317                 }
318
319                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
320                         continue;
321                         
322         // generate a split point
323                 p2 = p[(i+1)%numpoints];
324                 
325                 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
326                 for (int j = 0; j < 3; j++)
327                 {
328                         if (chopPlane->normal[j] == 1)
329                                 mid[j] = chopPlane->_d;
330                         else if (chopPlane->normal[j] == -1)
331                                 mid[j] = -chopPlane->_d;
332                         else
333                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
334                 }
335                         
336                 VectorCopy (mid, f->p[f->numpoints]);
337                 f->numpoints++;
338         }
339         
340         if (f->numpoints > maxpts)
341                 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
342         if (f->numpoints > MAX_POINTS_ON_WINDING)
343                 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
344
345         delete[] p;
346         p = f->p;
347         f->p = NULL;
348         delete f;
349         return true;
350 }
351
352 void DWinding::ClipWindingEpsilon(DPlane* chopPlane, vec_t epsilon, DWinding **front, DWinding **back)
353 {
354         vec_t   dists[MAX_POINTS_ON_WINDING+4];
355         int             sides[MAX_POINTS_ON_WINDING+4];
356         int             counts[3];
357         vec_t   *p1, *p2;
358         vec3_t  mid;
359         
360         counts[0] = counts[1] = counts[2] = 0;
361
362 // determine sides for each point
363         int i;
364         for (i = 0; i < numpoints; i++)
365         {
366                 vec_t dot = -chopPlane->DistanceToPoint(p[i]);
367                 dists[i] = dot;
368                 
369                 if (dot > epsilon)
370                         sides[i] = SIDE_FRONT;
371                 else if (dot < -epsilon)
372                         sides[i] = SIDE_BACK;
373                 else
374                         sides[i] = SIDE_ON;
375
376                 counts[sides[i]]++;
377         }
378         sides[i] = sides[0];
379         dists[i] = dists[0];
380         
381         *front = *back = NULL;
382
383         if (!counts[0])
384         {
385                 *back = CopyWinding();
386                 return;
387         }
388         if (!counts[1])
389         {
390                 *front = CopyWinding();
391                 return;
392         }
393
394         int maxpts = numpoints+4;       // cant use counts[0]+2 because
395                                                                 // of fp grouping errors
396
397         DWinding* f = new DWinding;
398         DWinding* b = new DWinding;
399
400         f->AllocWinding(maxpts);
401         f->numpoints = 0;
402
403         b->AllocWinding(maxpts);
404         b->numpoints = 0;
405                 
406         *front = f;
407         *back = b;
408
409         for (i = 0; i < numpoints ; i++)
410         {
411                 p1 = p[i];
412                 
413                 if (sides[i] == SIDE_ON)
414                 {
415                         VectorCopy (p1, f->p[f->numpoints]);
416                         f->numpoints++;
417                         VectorCopy (p1, b->p[b->numpoints]);
418                         b->numpoints++;
419                         continue;
420                 }
421         
422                 if (sides[i] == SIDE_FRONT)
423                 {
424                         VectorCopy (p1, f->p[f->numpoints]);
425                         f->numpoints++;
426                 }
427                 if (sides[i] == SIDE_BACK)
428                 {
429                         VectorCopy (p1, b->p[b->numpoints]);
430                         b->numpoints++;
431                 }
432
433                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
434                         continue;
435                         
436         // generate a split point
437                 p2 = p[(i+1)%numpoints];
438                 
439                 vec_t dot = dists[i] / (dists[i]-dists[i+1]);
440                 for (int j = 0; j < 3; j++)
441                 {
442                         if (chopPlane->normal[j] == 1)
443                                 mid[j] = chopPlane->_d;
444                         else if (chopPlane->normal[j] == -1)
445                                 mid[j] = -chopPlane->_d;
446                         else
447                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
448                 }
449                         
450                 VectorCopy (mid, f->p[f->numpoints]);
451                 f->numpoints++;
452                 VectorCopy (mid, b->p[b->numpoints]);
453                 b->numpoints++;
454         }
455         
456         if (f->numpoints > maxpts || b->numpoints > maxpts)
457                 globalOutputStream() << "ClipWinding: points exceeded estimate\n";
458         if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
459                 globalOutputStream() << "ClipWinding: MAX_POINTS_ON_WINDING\n";
460 }
461
462 bool DWinding::ChopWinding(DPlane* chopPlane)
463 {
464         DWinding *f, *b;
465
466         ClipWindingEpsilon (chopPlane, (float)ON_EPSILON, &f, &b);
467
468         if (b)
469                 delete (b);
470
471
472         if(!f)
473         {
474                 delete this;
475                 return false;
476         }
477
478         delete[] p;
479         p = f->p;
480         f->p = NULL;
481         numpoints = f->numpoints;
482         delete f;
483
484         return true;
485 }