- Weird shiftvalues are now hidden to the user, shiftvalues will
[xonotic/netradiant.git] / contrib / gtkgensurf / face.cpp
1 /*
2 GenSurf plugin for GtkRadiant
3 Copyright (C) 2001 David Hyde, Loki software and qeradiant.com
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 #include <stdlib.h>
21 #include <math.h>
22 #include "gensurf.h"
23
24 #define MAX_FACES 128    // Maximum number of faces on a brush
25 #define MAX_POINTS_ON_WINDING   64
26 #define SIDE_FRONT              0
27 #define SIDE_ON                 2
28 #define SIDE_BACK               1
29 #define SIDE_CROSS              -2
30
31 //vec3 vec3_origin = {0,0,0};
32
33 void PlaneFromPoints (float *p0, float *p1, float *p2, PLANE *plane)
34 {
35         vec3 t1, t2;
36         vec     length;
37         
38         VectorSubtract (p0, p1, t1);
39         VectorSubtract (p2, p1, t2);
40         plane->normal[0] = t1[1]*t2[2] - t1[2]*t2[1];
41         plane->normal[1] = t1[2]*t2[0] - t1[0]*t2[2];
42         plane->normal[2] = t1[0]*t2[1] - t1[1]*t2[0];
43         
44         length = (vec)(sqrt(plane->normal[0]*plane->normal[0] +
45                                 plane->normal[1]*plane->normal[1] +
46                                                 plane->normal[2]*plane->normal[2]  ));
47         if (length == 0)
48         {
49                 VectorClear(plane->normal);
50         }
51         else
52         {
53                 plane->normal[0] /= length;
54                 plane->normal[1] /= length;
55                 plane->normal[2] /= length;
56         }
57         plane->dist = DotProduct (p0, plane->normal);
58 }
59 /*
60 void VectorMA (vec3 va, vec scale, vec3 vb, vec3 vc)
61 {
62         vc[0] = va[0] + scale*vb[0];
63         vc[1] = va[1] + scale*vb[1];
64         vc[2] = va[2] + scale*vb[2];
65 }
66
67 void CrossProduct (vec3 v1, vec3 v2, vec3 cross)
68 {
69         cross[0] = v1[1]*v2[2] - v1[2]*v2[1];
70         cross[1] = v1[2]*v2[0] - v1[0]*v2[2];
71         cross[2] = v1[0]*v2[1] - v1[1]*v2[0];
72 }
73 */
74 /*
75 =============
76 AllocWinding
77 =============
78 */
79 MY_WINDING      *AllocWinding (int points)
80 {
81         MY_WINDING      *w;
82         int                     s;
83
84         s = sizeof(vec)*3*points + sizeof(int);
85         w = (MY_WINDING*)malloc (s);
86         memset (w, 0, s); 
87         return w;
88 }
89 /*
90 vec VectorNormalize (vec3 in, vec3 out)
91 {
92         vec     length, ilength;
93
94         length = (vec)(sqrt (in[0]*in[0] + in[1]*in[1] + in[2]*in[2]));
95         if (length == 0)
96         {
97                 VectorClear (out);
98                 return 0;
99         }
100
101         ilength = (vec)1.0/length;
102         out[0] = in[0]*ilength;
103         out[1] = in[1]*ilength;
104         out[2] = in[2]*ilength;
105
106         return length;
107 }
108 */
109
110 /*
111 =================
112 BaseWindingForPlane
113 =================
114 */
115 MY_WINDING *BaseWindingForPlane (vec3 normal, vec dist)
116 {
117         int                i, x;
118         vec        max, v;
119         vec3       org, vright, vup;
120         MY_WINDING *w;
121
122 // find the major axis
123
124         max = -BOGUS_RANGE;
125         x = -1;
126         for (i=0 ; i<3; i++)
127         {
128                 v = (vec)(fabs(normal[i]));
129                 if (v > max)
130                 {
131                         x = i;
132                         max = v;
133                 }
134         }
135         if (x==-1) x = 2;
136                 
137         VectorCopy(vec3_origin,vup);
138         switch (x)
139         {
140         case 0:
141         case 1:
142                 vup[2] = 1;
143                 break;          
144         case 2:
145                 vup[0] = 1;
146                 break;          
147         }
148
149         v = DotProduct (vup, normal);
150         VectorMA (vup, -v, normal, vup);
151         VectorNormalize (vup, vup);
152                 
153         VectorScale (normal, dist, org);
154         
155         CrossProduct (vup, normal, vright);
156         
157         VectorScale (vup, 65536, vup);
158         VectorScale (vright, 65536, vright);
159
160 // project a really big axis aligned box onto the plane
161         w = AllocWinding (4);
162         
163         VectorSubtract (org, vright, w->p[0]);
164         VectorAdd (w->p[0], vup, w->p[0]);
165         
166         VectorAdd (org, vright, w->p[1]);
167         VectorAdd (w->p[1], vup, w->p[1]);
168         
169         VectorAdd (org, vright, w->p[2]);
170         VectorSubtract (w->p[2], vup, w->p[2]);
171         
172         VectorSubtract (org, vright, w->p[3]);
173         VectorSubtract (w->p[3], vup, w->p[3]);
174         
175         w->numpoints = 4;
176         
177         return w;       
178 }
179
180 void FreeWinding (MY_WINDING *w)
181 {
182         if (*(unsigned *)w == 0xdeaddead)
183 //              Error ("FreeWinding: freed a freed winding");
184                 return;
185         *(unsigned *)w = 0xdeaddead;
186
187         free (w);
188 }
189
190 /*
191 =============
192 ChopWindingInPlace
193 =============
194 */
195 void ChopWindingInPlace (MY_WINDING **inout, vec3 normal, vec dist, vec epsilon)
196 {
197         MY_WINDING *in;
198         vec        dists[MAX_POINTS_ON_WINDING+4];
199         int        sides[MAX_POINTS_ON_WINDING+4];
200         int        counts[3];
201         static vec dot;         // VC 4.2 optimizer bug if not static
202         int        i, j;
203         vec        *p1, *p2;
204         vec3       mid;
205         MY_WINDING *f;
206         int        maxpts;
207
208         in = *inout;
209         counts[0] = counts[1] = counts[2] = 0;
210
211 // determine sides for each point
212         for (i=0 ; i<in->numpoints ; i++)
213         {
214                 dot = DotProduct (in->p[i], normal);
215                 dot -= dist;
216                 dists[i] = dot;
217                 if (dot > epsilon)
218                         sides[i] = SIDE_FRONT;
219                 else if (dot < -epsilon)
220                         sides[i] = SIDE_BACK;
221                 else
222                 {
223                         sides[i] = SIDE_ON;
224                 }
225                 counts[sides[i]]++;
226         }
227         sides[i] = sides[0];
228         dists[i] = dists[0];
229         
230         if (!counts[0])
231         {
232                 FreeWinding(in);
233                 *inout = NULL;
234                 return;
235         }
236         if (!counts[1])
237                 return;         // inout stays the same
238
239         maxpts = in->numpoints+4;       // cant use counts[0]+2 because
240                                                                 // of fp grouping errors
241
242         f = AllocWinding (maxpts);
243                 
244         for (i=0 ; i<in->numpoints ; i++)
245         {
246                 p1 = in->p[i];
247                 
248                 if (sides[i] == SIDE_ON)
249                 {
250                         VectorCopy (p1, f->p[f->numpoints]);
251                         f->numpoints++;
252                         continue;
253                 }
254         
255                 if (sides[i] == SIDE_FRONT)
256                 {
257                         VectorCopy (p1, f->p[f->numpoints]);
258                         f->numpoints++;
259                 }
260
261                 if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
262                         continue;
263                         
264         // generate a split point
265                 p2 = in->p[(i+1)%in->numpoints];
266                 
267                 dot = dists[i] / (dists[i]-dists[i+1]);
268                 for (j=0 ; j<3 ; j++)
269                 {       // avoid round off error when possible
270                         if (normal[j] == 1)
271                                 mid[j] = dist;
272                         else if (normal[j] == -1)
273                                 mid[j] = -dist;
274                         else
275                                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
276                 }
277                         
278                 VectorCopy (mid, f->p[f->numpoints]);
279                 f->numpoints++;
280         }
281         
282 //      if (f->numpoints > maxpts)
283 //              Error ("ClipWinding: points exceeded estimate");
284 //      if (f->numpoints > MAX_POINTS_ON_WINDING)
285 //              Error ("ClipWinding: MAX_POINTS_ON_WINDING");
286
287         FreeWinding(in);
288         *inout = f;
289 }
290
291 void UseFaceBounds()
292 {
293         LPVOID       vp;
294         float        Dot, BestDot;
295         float            planepts[3][3];
296         int          BestFace;
297         int          i, j;
298         int          NumFaces;
299         vec3         SurfNormal;
300         vec3         vmin,vmax;
301         PLANE        plane[MAX_FACES*2];
302         PLANE        pface;
303         MY_WINDING   *w;
304
305         switch(Plane)
306         {
307         case PLANE_XY1:
308                 SurfNormal[0] = 0.0;
309                 SurfNormal[1] = 0.0;
310                 SurfNormal[2] =-1.0;
311                 break;
312         case PLANE_XZ0:
313                 SurfNormal[0] = 0.0;
314                 SurfNormal[1] = 1.0;
315                 SurfNormal[2] = 0.0;
316                 break;
317         case PLANE_XZ1:
318                 SurfNormal[0] = 0.0;
319                 SurfNormal[1] =-1.0;
320                 SurfNormal[2] = 0.0;
321                 break;
322         case PLANE_YZ0:
323                 SurfNormal[0] = 1.0;
324                 SurfNormal[1] = 0.0;
325                 SurfNormal[2] = 0.0;
326                 break;
327         case PLANE_YZ1:
328                 SurfNormal[0] =-1.0;
329                 SurfNormal[1] = 0.0;
330                 SurfNormal[2] = 0.0;
331                 break;
332         default:
333                 SurfNormal[0] = 0.0;
334                 SurfNormal[1] = 0.0;
335                 SurfNormal[2] = 1.0;
336         }
337
338 #if 0
339         i  = g_FuncTable.m_pfnAllocateSelectedBrushHandles();
340         vp = g_FuncTable.m_pfnGetSelectedBrushHandle(0);
341         NumFaces = g_FuncTable.m_pfnGetFaceCount(vp);
342
343         BestFace = -1;
344         BestDot  = 0.0;
345
346         for(i=0; i<NumFaces; i++)
347         {
348           _QERFaceData* QERFaceData = g_FuncTable.m_pfnGetFaceData(vp,i);
349                 planepts[0][0] = QERFaceData->m_v1[0];
350                 planepts[0][1] = QERFaceData->m_v1[1];
351                 planepts[0][2] = QERFaceData->m_v1[2];
352                 planepts[1][0] = QERFaceData->m_v2[0];
353                 planepts[1][1] = QERFaceData->m_v2[1];
354                 planepts[1][2] = QERFaceData->m_v2[2];
355                 planepts[2][0] = QERFaceData->m_v3[0];
356                 planepts[2][1] = QERFaceData->m_v3[1];
357                 planepts[2][2] = QERFaceData->m_v3[2];
358
359                 PlaneFromPoints (planepts[0], planepts[1], planepts[2], &plane[2*i]);
360                 VectorSubtract (vec3_origin, plane[2*i].normal, plane[2*i+1].normal);
361                 plane[2*i+1].dist = -plane[2*i].dist;
362
363                 Dot = DotProduct(plane[2*i].normal,SurfNormal);
364                 if(Dot > BestDot)
365                 {
366                         BestDot  = Dot;
367                         BestFace = i;
368                         if(strlen(QERFaceData->m_TextureName))
369                                 strcpy(Texture[Game][0],QERFaceData->m_TextureName);
370                 }
371         }
372         for(i=0; i<NumFaces; i++)
373         {
374                 if(i==BestFace) continue;
375                 _QERFaceData* QERFaceData = g_FuncTable.m_pfnGetFaceData(vp,i);
376                 if(strlen(QERFaceData->m_TextureName))
377                 {
378                         if(strcmp(Texture[Game][0],QERFaceData->m_TextureName))
379                                 strcpy(Texture[Game][1],QERFaceData->m_TextureName);
380                 }
381         }
382
383
384         g_FuncTable.m_pfnReleaseSelectedBrushHandles();
385
386         w = BaseWindingForPlane (plane[BestFace*2].normal, plane[BestFace*2].dist);
387
388         for (i=0 ; i<NumFaces && w; i++)
389         {
390                 if (BestFace == i)
391                         continue;
392                 ChopWindingInPlace (&w, plane[i*2+1].normal, plane[i*2+1].dist, 0);
393         }
394         if(!w) return;
395
396         // Get bounding box for this face
397         vmin[0] = vmax[0] = w->p[0][0];
398         vmin[1] = vmax[1] = w->p[0][1];
399         vmin[2] = vmax[2] = w->p[0][2];
400         for(j=1; j<w->numpoints; j++)
401         {
402                 vmin[0] = min(vmin[0],w->p[j][0]);
403                 vmin[1] = min(vmin[1],w->p[j][1]);
404                 vmin[2] = min(vmin[2],w->p[j][2]);
405                 vmax[0] = max(vmax[0],w->p[j][0]);
406                 vmax[1] = max(vmax[1],w->p[j][1]);
407                 vmax[2] = max(vmax[2],w->p[j][2]);
408         }
409
410         FreeWinding(w);
411
412         VectorCopy(plane[BestFace*2].normal,pface.normal);
413         pface.dist = plane[BestFace*2].dist;
414         switch(Plane)
415         {
416         case PLANE_XZ0:
417         case PLANE_XZ1:
418                 if(pface.normal[1] == 0.) return;
419                 Hll = vmin[0];
420                 Hur = vmax[0];
421                 Vll = vmin[2];
422                 Vur = vmax[2];
423                 Z00 = (pface.dist - pface.normal[0]*Hll - pface.normal[2]*Vll)/pface.normal[1];
424                 Z01 = (pface.dist - pface.normal[0]*Hll - pface.normal[2]*Vur)/pface.normal[1];
425                 Z10 = (pface.dist - pface.normal[0]*Hur - pface.normal[2]*Vll)/pface.normal[1];
426                 Z11 = (pface.dist - pface.normal[0]*Hur - pface.normal[2]*Vur)/pface.normal[1];
427                 break;
428         case PLANE_YZ0:
429         case PLANE_YZ1:
430                 if(pface.normal[0] == 0.) return;
431                 Hll = vmin[1];
432                 Hur = vmax[1];
433                 Vll = vmin[2];
434                 Vur = vmax[2];
435                 Z00 = (pface.dist - pface.normal[1]*Hll - pface.normal[2]*Vll)/pface.normal[0];
436                 Z01 = (pface.dist - pface.normal[1]*Hll - pface.normal[2]*Vur)/pface.normal[0];
437                 Z10 = (pface.dist - pface.normal[1]*Hur - pface.normal[2]*Vll)/pface.normal[0];
438                 Z11 = (pface.dist - pface.normal[1]*Hur - pface.normal[2]*Vur)/pface.normal[0];
439                 break;
440         default:
441                 if(pface.normal[2] == 0.) return;
442                 Hll = vmin[0];
443                 Hur = vmax[0];
444                 Vll = vmin[1];
445                 Vur = vmax[1];
446                 Z00 = (pface.dist - pface.normal[0]*Hll - pface.normal[1]*Vll)/pface.normal[2];
447                 Z01 = (pface.dist - pface.normal[0]*Hll - pface.normal[1]*Vur)/pface.normal[2];
448                 Z10 = (pface.dist - pface.normal[0]*Hur - pface.normal[1]*Vll)/pface.normal[2];
449                 Z11 = (pface.dist - pface.normal[0]*Hur - pface.normal[1]*Vur)/pface.normal[2];
450         }
451 #endif
452 }