misc/mediasource/netradiant-src/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 }