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