Scenery/tile.cxx

   1 // tile.cxx -- routines to handle a scenery tile
   2 //
   3 // Written by Curtis Olson, started May 1998.
   4 //
   5 // Copyright (C) 1998  Curtis L. Olson  - curt@infoplane.com
   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
  29 #include "tile.hxx"
  30
  31
  32 // Constructor
  33 fgFRAGMENT::fgFRAGMENT ( void ) {
  34 }
  35
  36
  37 // Add a face to the face list
  38 void fgFRAGMENT::add_face(int n1, int n2, int n3) {
  39     fgFACE face;
  40
  41     face.n1 = n1;
  42     face.n2 = n2;
  43     face.n3 = n3;
  44
  45     faces.push_back(face);
  46 }
  47
  48
  49 // return the sign of a value
  50 static int fg_sign( double x ) {
  51     if ( x >= 0 ) {
  52         return(1);
  53     } else {
  54         return(-1);
  55     }
  56 }
  57
  58
  59 // return the minimum of the three values
  60 static double fg_min( double a, double b, double c ) {
  61     double result;
  62     result = a;
  63     if (result > b) result = b;
  64     if (result > c) result = c;
  65
  66     return(result);
  67 }
  68
  69
  70 // return the maximum of the three values
  71 static double fg_max( double a, double b, double c ) {
  72     double result;
  73     result = a;
  74     if (result < b) result = b;
  75     if (result < c) result = c;
  76
  77     return(result);
  78 }
  79
  80
  81 // test if line intesects with this fragment.  p0 and p1 are the two
  82 // line end points of the line.  If side_flag is true, check to see
  83 // that end points are on opposite sides of face.  Returns 1 if it
  84 // does, 0 otherwise.  If it intesects, result is the point of
  85 // intersection
  86
  87 int fgFRAGMENT::intersect( fgPoint3d *end0, fgPoint3d *end1, int side_flag,
  88                            fgPoint3d *result)
  89 {
  90     fgTILE *t;
  91     fgFACE face;
  92     MAT3vec v1, v2, n, center;
  93     double p1[3], p2[3], p3[3];
  94     double a, b, c, d;
  95     double x0, y0, z0, x1, y1, z1, a1, b1, c1;
  96     double t1, t2, t3;
  97     double xmin, xmax, ymin, ymax, zmin, zmax;
  98     double dx, dy, dz, min_dim, x2, y2, x3, y3, rx, ry;
  99     int side1, side2;
 100     list < fgFACE > :: iterator current;
 101     list < fgFACE > :: iterator last;
 102
 103     // find the associated tile
 104     t = (fgTILE *)tile_ptr;
 105
 106     // printf("Intersecting\n");
 107
 108     // traverse the face list for this fragment
 109     current = faces.begin();
 110     last = faces.end();
 111     while ( current != last ) {
 112         face = *current;
 113         current++;
 114
 115         // printf(".");
 116
 117         // get face vertex coordinates
 118         center[0] = t->center.x;
 119         center[1] = t->center.y;
 120         center[2] = t->center.z;
 121
 122         MAT3_ADD_VEC(p1, t->nodes[face.n1], center);
 123         MAT3_ADD_VEC(p2, t->nodes[face.n2], center);
 124         MAT3_ADD_VEC(p3, t->nodes[face.n3], center);
 125
 126         // printf("point 1 = %.2f %.2f %.2f\n", p1[0], p1[1], p1[2]);
 127         // printf("point 2 = %.2f %.2f %.2f\n", p2[0], p2[1], p2[2]);
 128         // printf("point 3 = %.2f %.2f %.2f\n", p3[0], p3[1], p3[2]);
 129
 130         // calculate two edge vectors, and the face normal
 131         MAT3_SUB_VEC(v1, p2, p1);
 132         MAT3_SUB_VEC(v2, p3, p1);
 133         MAT3cross_product(n, v1, v2);
 134
 135         // calculate the plane coefficients for the plane defined by
 136         // this face.  If n is the normal vector, n = (a, b, c) and p1
 137         // is a point on the plane, p1 = (x0, y0, z0), then the
 138         // equation of the line is a(x-x0) + b(y-y0) + c(z-z0) = 0
 139         a = n[0];
 140         b = n[1];
 141         c = n[2];
 142         d = a * p1[0] + b * p1[1] + c * p1[2];
 143         // printf("a, b, c, d = %.2f %.2f %.2f %.2f\n", a, b, c, d);
 144
 145         // printf("p1(d) = %.2f\n", a * p1[0] + b * p1[1] + c * p1[2]);
 146         // printf("p2(d) = %.2f\n", a * p2[0] + b * p2[1] + c * p2[2]);
 147         // printf("p3(d) = %.2f\n", a * p3[0] + b * p3[1] + c * p3[2]);
 148
 149         // calculate the line coefficients for the specified line
 150         x0 = end0->x;  x1 = end1->x;
 151         y0 = end0->y;  y1 = end1->y;
 152         z0 = end0->z;  z1 = end1->z;
 153
 154         a1 = x1 - x0;
 155         b1 = y1 - y0;
 156         c1 = z1 - z0;
 157
 158         // intersect the specified line with this plane
 159         t1 = b * b1 / a1;
 160         t2 = c * c1 / a1;
 161
 162         // printf("a = %.2f  t1 = %.2f  t2 = %.2f\n", a, t1, t2);
 163
 164         if ( fabs(a + t1 + t2) > FG_EPSILON ) {
 165             result->x = (t1*x0 - b*y0 + t2*x0 - c*z0 + d) / (a + t1 + t2);
 166             result->y = (b1/a1) * (result->x - x0) + y0;
 167             result->z = (c1/a1) * (result->x - x0) + z0;
 168             // printf("result(d) = %.2f\n",
 169             //        a * result->x + b * result->y + c * result->z);
 170         } else {
 171             // no intersection point
 172             continue;
 173         }
 174
 175         if ( side_flag ) {
 176             // check to see if end0 and end1 are on opposite sides of
 177             // plane
 178             if ( (result->x - x0) > FG_EPSILON ) {
 179                 t1 = result->x; t2 = x0; t3 = x1;
 180             } else if ( (result->y - y0) > FG_EPSILON ) {
 181                 t1 = result->y; t2 = y0; t3 = y1;
 182             } else if ( (result->z - z0) > FG_EPSILON ) {
 183                 t1 = result->z; t2 = z0; t3 = z1;
 184             } else {
 185                 // everything is too close together to tell the difference
 186                 // so the current intersection point should work as good
 187                 // as any
 188                 return(1);
 189             }
 190             if ( fg_sign(t1 - t2) == fg_sign(t1 - t3) ) {
 191                 // same side, punt
 192                 continue;
 193             }
 194         }
 195
 196         // check to see if intersection point is in the bounding
 197         // cube of the face
 198         xmin = fg_min(p1[0], p2[0], p3[0]);
 199         xmax = fg_max(p1[0], p2[0], p3[0]);
 200         ymin = fg_min(p1[1], p2[1], p3[1]);
 201         ymax = fg_max(p1[1], p2[1], p3[1]);
 202         zmin = fg_min(p1[2], p2[2], p3[2]);
 203         zmax = fg_max(p1[2], p2[2], p3[2]);
 204         // printf("bounding cube = %.2f,%.2f,%.2f  %.2f,%.2f,%.2f\n",
 205         //        xmin, ymin, zmin, xmax, ymax, zmax);
 206         // punt if outside bouding cube
 207         if ( result->x < xmin ) {
 208             continue;
 209         } else if ( result->x > xmax ) {
 210             continue;
 211         } else if ( result->y < ymin ) {
 212             continue;
 213         } else if ( result->y > ymax ) {
 214             continue;
 215         } else if ( result->z < zmin ) {
 216             continue;
 217         } else if ( result->z > zmax ) {
 218             continue;
 219         }
 220
 221         // (finally) check to see if the intersection point is
 222         // actually inside this face
 223
 224         //first, drop the smallest dimension so we only have to work
 225         //in 2d.
 226         dx = xmax - xmin;
 227         dy = ymax - ymin;
 228         dz = zmax - zmin;
 229         min_dim = fg_min(dx, dy, dz);
 230         if ( fabs(min_dim - dx) <= FG_EPSILON ) {
 231             // x is the smallest dimension
 232             x1 = p1[1]; y1 = p1[2];
 233             x2 = p2[1]; y2 = p2[2];
 234             x3 = p3[1]; y3 = p3[2];
 235             rx = result->y; ry = result->z;
 236         } else if ( fabs(min_dim - dy) <= FG_EPSILON ) {
 237             // y is the smallest dimension
 238             x1 = p1[0]; y1 = p1[2];
 239             x2 = p2[0]; y2 = p2[2];
 240             x3 = p3[0]; y3 = p3[2];
 241             rx = result->x; ry = result->z;
 242         } else if ( fabs(min_dim - dz) <= FG_EPSILON ) {
 243             // z is the smallest dimension
 244             x1 = p1[0]; y1 = p1[1];
 245             x2 = p2[0]; y2 = p2[1];
 246             x3 = p3[0]; y3 = p3[1];
 247             rx = result->x; ry = result->y;
 248         }
 249
 250         // check if intersection point is on the same side of p1 <-> p2 as p3
 251         side1 = fg_sign((y1 - y2) * ((x3) - x2) / (x1 - x2) + y2 - (y3));
 252         side2 = fg_sign((y1 - y2) * ((rx) - x2) / (x1 - x2) + y2 - (ry));
 253         if ( side1 != side2 ) {
 254             // printf("failed side 1 check\n");
 255             continue;
 256         }
 257
 258         // check if intersection point is on correct side of p2 <-> p3 as p1
 259         side1 = fg_sign((y2 - y3) * ((x1) - x3) / (x2 - x3) + y3 - (y1));
 260         side2 = fg_sign((y2 - y3) * ((rx) - x3) / (x2 - x3) + y3 - (ry));
 261         if ( side1 != side2 ) {
 262             // printf("failed side 2 check\n");
 263             continue;
 264         }
 265
 266         // check if intersection point is on correct side of p1 <-> p3 as p2
 267         side1 = fg_sign((y1 - y3) * ((x2) - x3) / (x1 - x3) + y3 - (y2));
 268         side2 = fg_sign((y1 - y3) * ((rx) - x3) / (x1 - x3) + y3 - (ry));
 269         if ( side1 != side2 ) {
 270             // printf("failed side 3  check\n");
 271             continue;
 272         }
 273
 274         // printf( "intersection point = %.2f %.2f %.2f\n",
 275         //         result->x, result->y, result->z);
 276         return(1);
 277     }
 278
 279     // printf("\n");
 280
 281     return(0);
 282 }
 283
 284
 285 // Destructor
 286 fgFRAGMENT::~fgFRAGMENT ( void ) {
 287     // Step through the face list deleting the items until the list is
 288     // empty
 289
 290     // printf("destructing a fragment with %d faces\n", faces.size());
 291
 292     while ( faces.size() ) {
 293         //  printf("emptying face list\n");
 294         faces.pop_front();
 295     }
 296 }
 297
 298
 299 // Constructor
 300 fgTILE::fgTILE ( void ) {
 301     nodes = new double[MAX_NODES][3];
 302 }
 303
 304
 305 // Destructor
 306 fgTILE::~fgTILE ( void ) {
 307     free(nodes);
 308 }
 309
 310
 311 // $Log$
 312 // Revision 1.2  1998/07/12 03:18:28  curt
 313 // Added ground collision detection.  This involved:
 314 // - saving the entire vertex list for each tile with the tile records.
 315 // - saving the face list for each fragment with the fragment records.
 316 // - code to intersect the current vertical line with the proper face in
 317 //   an efficient manner as possible.
 318 // Fixed a bug where the tiles weren't being shifted to "near" (0,0,0)
 319 //
 320 // Revision 1.1  1998/05/23 14:09:21  curt
 321 // Added tile.cxx and tile.hxx.
 322 // Working on rewriting the tile management system so a tile is just a list
 323 // fragments, and the fragment record contains the display list for that fragment.
 324 //