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