Objects/fragment.cxx

   1 // fragment.cxx -- routines to handle "atomic" display objects
   2 //
   3 // Written by Curtis Olson, started August 1998.
   4 //
   5 // Copyright (C) 1998  Curtis L. Olson  - curt@me.umn.edu
   6 //
   7 // This program is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU General Public License as
   9 // published by the Free Software Foundation; either version 2 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this program; if not, write to the Free Software
  19 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20 //
  21 // $Id$
  22 // (Log is kept at end of this file)
  23
  24
  25 #include <Include/fg_constants.h>
  26 #include <Include/fg_types.h>
  27 #include <Math/mat3.h>
  28 #include <Scenery/tile.hxx>
  29
  30 #include "fragment.hxx"
  31
  32
  33 // return the sign of a value
  34 #define FG_SIGN( x )  ((x) < 0 ? -1 : 1)
  35
  36 // return min or max of two values
  37 #define FG_MIN(A,B)     ((A) < (B) ? (A) :  (B))
  38 #define FG_MAX(A,B)     ((A) > (B) ? (A) :  (B))
  39
  40
  41 fgFACE :: fgFACE () :
  42     n1(0), n2(0), n3(0)
  43 {
  44 }
  45
  46 fgFACE :: ~fgFACE()
  47 {
  48 }
  49
  50 fgFACE :: fgFACE( const fgFACE & image ) :
  51     n1( image.n1), n2( image.n2), n3( image.n3)
  52 {
  53 }
  54
  55 bool fgFACE :: operator < (const fgFACE & rhs )
  56 {
  57     return ( n1 < rhs.n1 ? true : false);
  58 }
  59
  60 bool fgFACE :: operator == (const fgFACE & rhs )
  61 {
  62     return ((n1 == rhs.n1) && (n2 == rhs.n2) && ( n3 == rhs.n3));
  63 }
  64
  65
  66 // Constructor
  67 fgFRAGMENT::fgFRAGMENT ( void ) {
  68 }
  69
  70
  71 // Copy constructor
  72 fgFRAGMENT ::   fgFRAGMENT ( const fgFRAGMENT & rhs ) :
  73     center         ( rhs.center          ),
  74     bounding_radius( rhs.bounding_radius ),
  75     material_ptr   ( rhs.material_ptr    ),
  76     tile_ptr       ( rhs.tile_ptr        ),
  77     display_list   ( rhs.display_list    ),
  78     faces          ( rhs.faces           ),
  79     num_faces      ( rhs.num_faces       )
  80 {
  81 }
  82
  83 fgFRAGMENT & fgFRAGMENT :: operator = ( const fgFRAGMENT & rhs )
  84 {
  85     if(!(this == &rhs )) {
  86         center          = rhs.center;
  87         bounding_radius = rhs.bounding_radius;
  88         material_ptr    = rhs.material_ptr;
  89         tile_ptr        = rhs.tile_ptr;
  90         // display_list    = rhs.display_list;
  91         faces           = rhs.faces;
  92     }
  93     return *this;
  94 }
  95
  96
  97 // Add a face to the face list
  98 void fgFRAGMENT::add_face(int n1, int n2, int n3) {
  99     fgFACE face;
 100
 101     face.n1 = n1;
 102     face.n2 = n2;
 103     face.n3 = n3;
 104
 105     faces.push_back(face);
 106     num_faces++;
 107 }
 108
 109
 110 // return the minimum of the three values
 111 static double fg_min3 (double a, double b, double c)
 112 {
 113     return (a > b ? FG_MIN (b, c) : FG_MIN (a, c));
 114 }
 115
 116
 117 // return the maximum of the three values
 118 static double fg_max3 (double a, double b, double c)
 119 {
 120   return (a < b ? FG_MAX (b, c) : FG_MAX (a, c));
 121 }
 122
 123
 124 // test if line intesects with this fragment.  p0 and p1 are the two
 125 // line end points of the line.  If side_flag is true, check to see
 126 // that end points are on opposite sides of face.  Returns 1 if it
 127 // intersection found, 0 otherwise.  If it intesects, result is the
 128 // point of intersection
 129
 130 int fgFRAGMENT::intersect( fgPoint3d *end0, fgPoint3d *end1, int side_flag,
 131                            fgPoint3d *result)
 132 {
 133     fgTILE *t;
 134     fgFACE face;
 135     MAT3vec v1, v2, n, center;
 136     double p1[3], p2[3], p3[3];
 137     double x, y, z;  // temporary holding spot for result
 138     double a, b, c, d;
 139     double x0, y0, z0, x1, y1, z1, a1, b1, c1;
 140     double t1, t2, t3;
 141     double xmin, xmax, ymin, ymax, zmin, zmax;
 142     double dx, dy, dz, min_dim, x2, y2, x3, y3, rx, ry;
 143     int side1, side2;
 144     list < fgFACE > :: iterator current;
 145     list < fgFACE > :: iterator last;
 146
 147     // find the associated tile
 148     t = tile_ptr;
 149
 150     // printf("Intersecting\n");
 151
 152     // traverse the face list for this fragment
 153     current = faces.begin();
 154     last = faces.end();
 155     while ( current != last ) {
 156         face = *current;
 157         current++;
 158
 159         // printf(".");
 160
 161         // get face vertex coordinates
 162         center[0] = t->center.x;
 163         center[1] = t->center.y;
 164         center[2] = t->center.z;
 165
 166         MAT3_ADD_VEC(p1, t->nodes[face.n1], center);
 167         MAT3_ADD_VEC(p2, t->nodes[face.n2], center);
 168         MAT3_ADD_VEC(p3, t->nodes[face.n3], center);
 169
 170         // printf("point 1 = %.2f %.2f %.2f\n", p1[0], p1[1], p1[2]);
 171         // printf("point 2 = %.2f %.2f %.2f\n", p2[0], p2[1], p2[2]);
 172         // printf("point 3 = %.2f %.2f %.2f\n", p3[0], p3[1], p3[2]);
 173
 174         // calculate two edge vectors, and the face normal
 175         MAT3_SUB_VEC(v1, p2, p1);
 176         MAT3_SUB_VEC(v2, p3, p1);
 177         MAT3cross_product(n, v1, v2);
 178
 179         // calculate the plane coefficients for the plane defined by
 180         // this face.  If n is the normal vector, n = (a, b, c) and p1
 181         // is a point on the plane, p1 = (x0, y0, z0), then the
 182         // equation of the line is a(x-x0) + b(y-y0) + c(z-z0) = 0
 183         a = n[0];
 184         b = n[1];
 185         c = n[2];
 186         d = a * p1[0] + b * p1[1] + c * p1[2];
 187         // printf("a, b, c, d = %.2f %.2f %.2f %.2f\n", a, b, c, d);
 188
 189         // printf("p1(d) = %.2f\n", a * p1[0] + b * p1[1] + c * p1[2]);
 190         // printf("p2(d) = %.2f\n", a * p2[0] + b * p2[1] + c * p2[2]);
 191         // printf("p3(d) = %.2f\n", a * p3[0] + b * p3[1] + c * p3[2]);
 192
 193         // calculate the line coefficients for the specified line
 194         x0 = end0->x;  x1 = end1->x;
 195         y0 = end0->y;  y1 = end1->y;
 196         z0 = end0->z;  z1 = end1->z;
 197
 198         if ( fabs(x1 - x0) > FG_EPSILON ) {
 199             a1 = 1.0 / (x1 - x0);
 200         } else {
 201             // we got a big divide by zero problem here
 202             a1 = 0.0;
 203         }
 204         b1 = y1 - y0;
 205         c1 = z1 - z0;
 206
 207         // intersect the specified line with this plane
 208         t1 = b * b1 * a1;
 209         t2 = c * c1 * a1;
 210
 211         // printf("a = %.2f  t1 = %.2f  t2 = %.2f\n", a, t1, t2);
 212
 213         if ( fabs(a + t1 + t2) > FG_EPSILON ) {
 214             x = (t1*x0 - b*y0 + t2*x0 - c*z0 + d) / (a + t1 + t2);
 215             t3 = a1 * (x - x0);
 216             y = b1 * t3 + y0;
 217             z = c1 * t3 + z0;
 218             // printf("result(d) = %.2f\n", a * x + b * y + c * z);
 219         } else {
 220             // no intersection point
 221             continue;
 222         }
 223
 224         if ( side_flag ) {
 225             // check to see if end0 and end1 are on opposite sides of
 226             // plane
 227             if ( (x - x0) > FG_EPSILON ) {
 228                 t1 = x;
 229                 t2 = x0;
 230                 t3 = x1;
 231             } else if ( (y - y0) > FG_EPSILON ) {
 232                 t1 = y;
 233                 t2 = y0;
 234                 t3 = y1;
 235             } else if ( (z - z0) > FG_EPSILON ) {
 236                 t1 = z;
 237                 t2 = z0;
 238                 t3 = z1;
 239             } else {
 240                 // everything is too close together to tell the difference
 241                 // so the current intersection point should work as good
 242                 // as any
 243                 result->x = x;
 244                 result->y = y;
 245                 result->z = z;
 246                 return(1);
 247             }
 248             side1 = FG_SIGN (t1 - t2);
 249             side2 = FG_SIGN (t1 - t3);
 250             if ( side1 == side2 ) {
 251                 // same side, punt
 252                 continue;
 253             }
 254         }
 255
 256         // check to see if intersection point is in the bounding
 257         // cube of the face
 258 #ifdef XTRA_DEBUG_STUFF
 259         xmin = fg_min3 (p1[0], p2[0], p3[0]);
 260         xmax = fg_max3 (p1[0], p2[0], p3[0]);
 261         ymin = fg_min3 (p1[1], p2[1], p3[1]);
 262         ymax = fg_max3 (p1[1], p2[1], p3[1]);
 263         zmin = fg_min3 (p1[2], p2[2], p3[2]);
 264         zmax = fg_max3 (p1[2], p2[2], p3[2]);
 265         printf("bounding cube = %.2f,%.2f,%.2f  %.2f,%.2f,%.2f\n",
 266                xmin, ymin, zmin, xmax, ymax, zmax);
 267 #endif
 268         // punt if outside bouding cube
 269         if ( x < (xmin = fg_min3 (p1[0], p2[0], p3[0])) ) {
 270             continue;
 271         } else if ( x > (xmax = fg_max3 (p1[0], p2[0], p3[0])) ) {
 272             continue;
 273         } else if ( y < (ymin = fg_min3 (p1[1], p2[1], p3[1])) ) {
 274             continue;
 275         } else if ( y > (ymax = fg_max3 (p1[1], p2[1], p3[1])) ) {
 276             continue;
 277         } else if ( z < (zmin = fg_min3 (p1[2], p2[2], p3[2])) ) {
 278             continue;
 279         } else if ( z > (zmax = fg_max3 (p1[2], p2[2], p3[2])) ) {
 280             continue;
 281         }
 282
 283         // (finally) check to see if the intersection point is
 284         // actually inside this face
 285
 286         //first, drop the smallest dimension so we only have to work
 287         //in 2d.
 288         dx = xmax - xmin;
 289         dy = ymax - ymin;
 290         dz = zmax - zmin;
 291         min_dim = fg_min3 (dx, dy, dz);
 292         if ( fabs(min_dim - dx) <= FG_EPSILON ) {
 293             // x is the smallest dimension
 294             x1 = p1[1];
 295             y1 = p1[2];
 296             x2 = p2[1];
 297             y2 = p2[2];
 298             x3 = p3[1];
 299             y3 = p3[2];
 300             rx = y;
 301             ry = z;
 302         } else if ( fabs(min_dim - dy) <= FG_EPSILON ) {
 303             // y is the smallest dimension
 304             x1 = p1[0];
 305             y1 = p1[2];
 306             x2 = p2[0];
 307             y2 = p2[2];
 308             x3 = p3[0];
 309             y3 = p3[2];
 310             rx = x;
 311             ry = z;
 312         } else if ( fabs(min_dim - dz) <= FG_EPSILON ) {
 313             // z is the smallest dimension
 314             x1 = p1[0];
 315             y1 = p1[1];
 316             x2 = p2[0];
 317             y2 = p2[1];
 318             x3 = p3[0];
 319             y3 = p3[1];
 320             rx = x;
 321             ry = y;
 322         } else {
 323             // all dimensions are really small so lets call it close
 324             // enough and return a successful match
 325             result->x = x;
 326             result->y = y;
 327             result->z = z;
 328             return(1);
 329         }
 330
 331         // check if intersection point is on the same side of p1 <-> p2 as p3
 332         t1 = (y1 - y2) / (x1 - x2);
 333         side1 = FG_SIGN (t1 * ((x3) - x2) + y2 - (y3));
 334         side2 = FG_SIGN (t1 * ((rx) - x2) + y2 - (ry));
 335         if ( side1 != side2 ) {
 336             // printf("failed side 1 check\n");
 337             continue;
 338         }
 339
 340         // check if intersection point is on correct side of p2 <-> p3 as p1
 341         t1 = (y2 - y3) / (x2 - x3);
 342         side1 = FG_SIGN (t1 * ((x1) - x3) + y3 - (y1));
 343         side2 = FG_SIGN (t1 * ((rx) - x3) + y3 - (ry));
 344         if ( side1 != side2 ) {
 345             // printf("failed side 2 check\n");
 346             continue;
 347         }
 348
 349         // check if intersection point is on correct side of p1 <-> p3 as p2
 350         t1 = (y1 - y3) / (x1 - x3);
 351         side1 = FG_SIGN (t1 * ((x2) - x3) + y3 - (y2));
 352         side2 = FG_SIGN (t1 * ((rx) - x3) + y3 - (ry));
 353         if ( side1 != side2 ) {
 354             // printf("failed side 3  check\n");
 355             continue;
 356         }
 357
 358         // printf( "intersection point = %.2f %.2f %.2f\n", x, y, z);
 359         result->x = x;
 360         result->y = y;
 361         result->z = z;
 362         return(1);
 363     }
 364
 365     // printf("\n");
 366
 367     return(0);
 368 }
 369
 370
 371 // Destructor
 372 fgFRAGMENT::~fgFRAGMENT ( void ) {
 373     // Step through the face list deleting the items until the list is
 374     // empty
 375
 376     // printf("destructing a fragment with %d faces\n", faces.size());
 377
 378     while ( faces.size() ) {
 379         //  printf("emptying face list\n");
 380         faces.pop_front();
 381     }
 382 }
 383
 384
 385 // equality operator
 386 bool  fgFRAGMENT :: operator == ( const fgFRAGMENT & rhs)
 387 {
 388     if(( center.x - rhs.center.x ) < FG_EPSILON) {
 389         if(( center.y - rhs.center.y) < FG_EPSILON) {
 390             if(( center.z - rhs.center.z) < FG_EPSILON) {
 391                 return true;
 392             }
 393         }
 394     }
 395     return false;
 396 }
 397
 398 // comparison operator
 399 bool  fgFRAGMENT :: operator < ( const fgFRAGMENT &rhs)
 400 {
 401     // This is completely arbitrary. It satisfies RW's STL implementation
 402
 403     return bounding_radius < rhs.bounding_radius;
 404 }
 405
 406
 407 // $Log$
 408 // Revision 1.1  1998/08/25 16:51:23  curt
 409 // Moved from ../Scenery
 410 //
 411 //
 412