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 }