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