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         vec3 t1, t2;
  35         vec length;
  36
  37         VectorSubtract( p0, p1, t1 );
  38         VectorSubtract( p2, p1, t2 );
  39         plane->normal[0] = t1[1] * t2[2] - t1[2] * t2[1];
  40         plane->normal[1] = t1[2] * t2[0] - t1[0] * t2[2];
  41         plane->normal[2] = t1[0] * t2[1] - t1[1] * t2[0];
  42
  43         length = (vec)( sqrt( plane->normal[0] * plane->normal[0] +
  44                                                   plane->normal[1] * plane->normal[1] +
  45                                                   plane->normal[2] * plane->normal[2]  ) );
  46         if ( length == 0 ) {
  47                 VectorClear( plane->normal );
  48         }
  49         else
  50         {
  51                 plane->normal[0] /= length;
  52                 plane->normal[1] /= length;
  53                 plane->normal[2] /= length;
  54         }
  55         plane->dist = DotProduct( p0, plane->normal );
  56 }
  57 /*
  58    void VectorMA (vec3 va, vec scale, vec3 vb, vec3 vc)
  59    {
  60     vc[0] = va[0] + scale*vb[0];
  61     vc[1] = va[1] + scale*vb[1];
  62     vc[2] = va[2] + scale*vb[2];
  63    }
  64
  65    void CrossProduct (vec3 v1, vec3 v2, vec3 cross)
  66    {
  67     cross[0] = v1[1]*v2[2] - v1[2]*v2[1];
  68     cross[1] = v1[2]*v2[0] - v1[0]*v2[2];
  69     cross[2] = v1[0]*v2[1] - v1[1]*v2[0];
  70    }
  71  */
  72 /*
  73    =============
  74    AllocWinding
  75    =============
  76  */
  77 MY_WINDING  *AllocWinding( int points ){
  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         int i, x;
 114         vec max, v;
 115         vec3 org, vright, vup;
 116         MY_WINDING *w;
 117
 118 // find the major axis
 119
 120         max = -BOGUS_RANGE;
 121         x = -1;
 122         for ( i = 0 ; i < 3; i++ )
 123         {
 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         {
 137         case 0:
 138         case 1:
 139                 vup[2] = 1;
 140                 break;
 141         case 2:
 142                 vup[0] = 1;
 143                 break;
 144         }
 145
 146         v = DotProduct( vup, normal );
 147         VectorMA( vup, -v, normal, vup );
 148         VectorNormalize( vup, vup );
 149
 150         VectorScale( normal, dist, org );
 151
 152         CrossProduct( vup, normal, vright );
 153
 154         VectorScale( vup, 65536, vup );
 155         VectorScale( vright, 65536, vright );
 156
 157 // project a really big axis aligned box onto the plane
 158         w = AllocWinding( 4 );
 159
 160         VectorSubtract( org, vright, w->p[0] );
 161         VectorAdd( w->p[0], vup, w->p[0] );
 162
 163         VectorAdd( org, vright, w->p[1] );
 164         VectorAdd( w->p[1], vup, w->p[1] );
 165
 166         VectorAdd( org, vright, w->p[2] );
 167         VectorSubtract( w->p[2], vup, w->p[2] );
 168
 169         VectorSubtract( org, vright, w->p[3] );
 170         VectorSubtract( w->p[3], vup, w->p[3] );
 171
 172         w->numpoints = 4;
 173
 174         return w;
 175 }
 176
 177 void FreeWinding( MY_WINDING *w ){
 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         MY_WINDING *in;
 194         vec dists[MAX_POINTS_ON_WINDING + 4];
 195         int sides[MAX_POINTS_ON_WINDING + 4];
 196         int counts[3];
 197         static vec dot;     // VC 4.2 optimizer bug if not static
 198         int i, j;
 199         vec        *p1, *p2;
 200         vec3 mid;
 201         MY_WINDING *f;
 202         int maxpts;
 203
 204         in = *inout;
 205         counts[0] = counts[1] = counts[2] = 0;
 206
 207 // determine sides for each point
 208         for ( i = 0 ; i < in->numpoints ; i++ )
 209         {
 210                 dot = DotProduct( in->p[i], normal );
 211                 dot -= dist;
 212                 dists[i] = dot;
 213                 if ( dot > epsilon ) {
 214                         sides[i] = SIDE_FRONT;
 215                 }
 216                 else if ( dot < -epsilon ) {
 217                         sides[i] = SIDE_BACK;
 218                 }
 219                 else
 220                 {
 221                         sides[i] = SIDE_ON;
 222                 }
 223                 counts[sides[i]]++;
 224         }
 225         sides[i] = sides[0];
 226         dists[i] = dists[0];
 227
 228         if ( !counts[0] ) {
 229                 FreeWinding( in );
 230                 *inout = NULL;
 231                 return;
 232         }
 233         if ( !counts[1] ) {
 234                 return;     // inout stays the same
 235
 236         }
 237         maxpts = in->numpoints + 4;   // cant use counts[0]+2 because
 238                                       // of fp grouping errors
 239
 240         f = AllocWinding( maxpts );
 241
 242         for ( i = 0 ; i < in->numpoints ; i++ )
 243         {
 244                 p1 = in->p[i];
 245
 246                 if ( sides[i] == SIDE_ON ) {
 247                         VectorCopy( p1, f->p[f->numpoints] );
 248                         f->numpoints++;
 249                         continue;
 250                 }
 251
 252                 if ( sides[i] == SIDE_FRONT ) {
 253                         VectorCopy( p1, f->p[f->numpoints] );
 254                         f->numpoints++;
 255                 }
 256
 257                 if ( sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i] ) {
 258                         continue;
 259                 }
 260
 261                 // generate a split point
 262                 p2 = in->p[( i + 1 ) % in->numpoints];
 263
 264                 dot = dists[i] / ( dists[i] - dists[i + 1] );
 265                 for ( j = 0 ; j < 3 ; j++ )
 266                 {   // avoid round off error when possible
 267                         if ( normal[j] == 1 ) {
 268                                 mid[j] = dist;
 269                         }
 270                         else if ( normal[j] == -1 ) {
 271                                 mid[j] = -dist;
 272                         }
 273                         else{
 274                                 mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
 275                         }
 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         LPVOID vp;
 293         float Dot, BestDot;
 294         float planepts[3][3];
 295         int BestFace;
 296         int i, j;
 297         int NumFaces;
 298         vec3 SurfNormal;
 299         vec3 vmin,vmax;
 300         PLANE plane[MAX_FACES * 2];
 301         PLANE pface;
 302         MY_WINDING   *w;
 303
 304         switch ( Plane )
 305         {
 306         case PLANE_XY1:
 307                 SurfNormal[0] = 0.0;
 308                 SurfNormal[1] = 0.0;
 309                 SurfNormal[2] = -1.0;
 310                 break;
 311         case PLANE_XZ0:
 312                 SurfNormal[0] = 0.0;
 313                 SurfNormal[1] = 1.0;
 314                 SurfNormal[2] = 0.0;
 315                 break;
 316         case PLANE_XZ1:
 317                 SurfNormal[0] = 0.0;
 318                 SurfNormal[1] = -1.0;
 319                 SurfNormal[2] = 0.0;
 320                 break;
 321         case PLANE_YZ0:
 322                 SurfNormal[0] = 1.0;
 323                 SurfNormal[1] = 0.0;
 324                 SurfNormal[2] = 0.0;
 325                 break;
 326         case PLANE_YZ1:
 327                 SurfNormal[0] = -1.0;
 328                 SurfNormal[1] = 0.0;
 329                 SurfNormal[2] = 0.0;
 330                 break;
 331         default:
 332                 SurfNormal[0] = 0.0;
 333                 SurfNormal[1] = 0.0;
 334                 SurfNormal[2] = 1.0;
 335         }
 336
 337 #if 0
 338         i  = g_FuncTable.m_pfnAllocateSelectedBrushHandles();
 339         vp = g_FuncTable.m_pfnGetSelectedBrushHandle( 0 );
 340         NumFaces = g_FuncTable.m_pfnGetFaceCount( vp );
 341
 342         BestFace = -1;
 343         BestDot  = 0.0;
 344
 345         for ( i = 0; i < NumFaces; i++ )
 346         {
 347                 _QERFaceData* QERFaceData = g_FuncTable.m_pfnGetFaceData( vp,i );
 348                 planepts[0][0] = QERFaceData->m_v1[0];
 349                 planepts[0][1] = QERFaceData->m_v1[1];
 350                 planepts[0][2] = QERFaceData->m_v1[2];
 351                 planepts[1][0] = QERFaceData->m_v2[0];
 352                 planepts[1][1] = QERFaceData->m_v2[1];
 353                 planepts[1][2] = QERFaceData->m_v2[2];
 354                 planepts[2][0] = QERFaceData->m_v3[0];
 355                 planepts[2][1] = QERFaceData->m_v3[1];
 356                 planepts[2][2] = QERFaceData->m_v3[2];
 357
 358                 PlaneFromPoints( planepts[0], planepts[1], planepts[2], &plane[2 * i] );
 359                 VectorSubtract( vec3_origin, plane[2 * i].normal, plane[2 * i + 1].normal );
 360                 plane[2 * i + 1].dist = -plane[2 * i].dist;
 361
 362                 Dot = DotProduct( plane[2 * i].normal,SurfNormal );
 363                 if ( Dot > BestDot ) {
 364                         BestDot  = Dot;
 365                         BestFace = i;
 366                         if ( strlen( QERFaceData->m_TextureName ) ) {
 367                                 strcpy( Texture[Game][0],QERFaceData->m_TextureName );
 368                         }
 369                 }
 370         }
 371         for ( i = 0; i < NumFaces; i++ )
 372         {
 373                 if ( i == BestFace ) {
 374                         continue;
 375                 }
 376                 _QERFaceData* QERFaceData = g_FuncTable.m_pfnGetFaceData( vp,i );
 377                 if ( strlen( QERFaceData->m_TextureName ) ) {
 378                         if ( strcmp( Texture[Game][0],QERFaceData->m_TextureName ) ) {
 379                                 strcpy( Texture[Game][1],QERFaceData->m_TextureName );
 380                         }
 381                 }
 382         }
 383
 384
 385         g_FuncTable.m_pfnReleaseSelectedBrushHandles();
 386
 387         w = BaseWindingForPlane( plane[BestFace * 2].normal, plane[BestFace * 2].dist );
 388
 389         for ( i = 0 ; i < NumFaces && w; i++ )
 390         {
 391                 if ( BestFace == i ) {
 392                         continue;
 393                 }
 394                 ChopWindingInPlace( &w, plane[i * 2 + 1].normal, plane[i * 2 + 1].dist, 0 );
 395         }
 396         if ( !w ) {
 397                 return;
 398         }
 399
 400         // Get bounding box for this face
 401         vmin[0] = vmax[0] = w->p[0][0];
 402         vmin[1] = vmax[1] = w->p[0][1];
 403         vmin[2] = vmax[2] = w->p[0][2];
 404         for ( j = 1; j < w->numpoints; j++ )
 405         {
 406                 vmin[0] = min( vmin[0],w->p[j][0] );
 407                 vmin[1] = min( vmin[1],w->p[j][1] );
 408                 vmin[2] = min( vmin[2],w->p[j][2] );
 409                 vmax[0] = max( vmax[0],w->p[j][0] );
 410                 vmax[1] = max( vmax[1],w->p[j][1] );
 411                 vmax[2] = max( vmax[2],w->p[j][2] );
 412         }
 413
 414         FreeWinding( w );
 415
 416         VectorCopy( plane[BestFace * 2].normal,pface.normal );
 417         pface.dist = plane[BestFace * 2].dist;
 418         switch ( Plane )
 419         {
 420         case PLANE_XZ0:
 421         case PLANE_XZ1:
 422                 if ( pface.normal[1] == 0. ) {
 423                         return;
 424                 }
 425                 Hll = vmin[0];
 426                 Hur = vmax[0];
 427                 Vll = vmin[2];
 428                 Vur = vmax[2];
 429                 Z00 = ( pface.dist - pface.normal[0] * Hll - pface.normal[2] * Vll ) / pface.normal[1];
 430                 Z01 = ( pface.dist - pface.normal[0] * Hll - pface.normal[2] * Vur ) / pface.normal[1];
 431                 Z10 = ( pface.dist - pface.normal[0] * Hur - pface.normal[2] * Vll ) / pface.normal[1];
 432                 Z11 = ( pface.dist - pface.normal[0] * Hur - pface.normal[2] * Vur ) / pface.normal[1];
 433                 break;
 434         case PLANE_YZ0:
 435         case PLANE_YZ1:
 436                 if ( pface.normal[0] == 0. ) {
 437                         return;
 438                 }
 439                 Hll = vmin[1];
 440                 Hur = vmax[1];
 441                 Vll = vmin[2];
 442                 Vur = vmax[2];
 443                 Z00 = ( pface.dist - pface.normal[1] * Hll - pface.normal[2] * Vll ) / pface.normal[0];
 444                 Z01 = ( pface.dist - pface.normal[1] * Hll - pface.normal[2] * Vur ) / pface.normal[0];
 445                 Z10 = ( pface.dist - pface.normal[1] * Hur - pface.normal[2] * Vll ) / pface.normal[0];
 446                 Z11 = ( pface.dist - pface.normal[1] * Hur - pface.normal[2] * Vur ) / pface.normal[0];
 447                 break;
 448         default:
 449                 if ( pface.normal[2] == 0. ) {
 450                         return;
 451                 }
 452                 Hll = vmin[0];
 453                 Hur = vmax[0];
 454                 Vll = vmin[1];
 455                 Vur = vmax[1];
 456                 Z00 = ( pface.dist - pface.normal[0] * Hll - pface.normal[1] * Vll ) / pface.normal[2];
 457                 Z01 = ( pface.dist - pface.normal[0] * Hll - pface.normal[1] * Vur ) / pface.normal[2];
 458                 Z10 = ( pface.dist - pface.normal[0] * Hur - pface.normal[1] * Vll ) / pface.normal[2];
 459                 Z11 = ( pface.dist - pface.normal[0] * Hur - pface.normal[1] * Vur ) / pface.normal[2];
 460         }
 461 #endif
 462 }