Back to index

extremetuxracer  0.5beta
hier_util.cpp
Go to the documentation of this file.
00001 /* 
00002  * PPRacer 
00003  * Copyright (C) 2004-2005 Volker Stroebel <volker@planetpenguin.de>
00004  *
00005  * Copyright (C) 1999-2001 Jasmin F. Patry
00006  * 
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  * 
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  * 
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00020  */
00021 
00022 #include "render_util.h"
00023 #include "hier.h"
00024 
00025 #include "ppgltk/alg/defs.h"
00026 
00027 #include "game_config.h"
00028 
00029 
00030 #define USE_GLUSPHERE 0
00031 
00032 #if USE_GLUSPHERE
00033 
00034 /* Draws a sphere using gluSphere
00035  */
00036 void draw_sphere( int num_divisions )
00037 {
00038     GLUquadricObj *qobj;
00039 
00040     qobj = gluNewQuadric();
00041     gluQuadricDrawStyle( qobj, GLU_FILL );
00042     gluQuadricOrientation( qobj, GLU_OUTSIDE );
00043     gluQuadricNormals( qobj, GLU_SMOOTH );
00044 
00045     gluSphere( qobj, 1.0, 2.0 * num_divisions, num_divisions );
00046 
00047     gluDeleteQuadric( qobj );
00048     
00049 }
00050 
00051 #else 
00052 
00053 void draw_sphere( int num_divisions )
00054 {
00055     double theta, phi, d_theta, d_phi, eps, twopi;
00056     double x, y, z;
00057     int div = num_divisions;
00058 
00059     eps = 1e-15;
00060     twopi = M_PI * 2.0;
00061 
00062     d_theta = d_phi = M_PI / div;
00063 
00064     for ( phi = 0.0; phi + eps < M_PI; phi += d_phi ) {
00065        double cos_theta, sin_theta;
00066        double sin_phi, cos_phi;
00067        double sin_phi_d_phi, cos_phi_d_phi;
00068 
00069        sin_phi = sin( phi );
00070        cos_phi = cos( phi );
00071        sin_phi_d_phi = sin( phi + d_phi );
00072        cos_phi_d_phi = cos( phi + d_phi );
00073         
00074         if ( phi <= eps ) {
00075 
00076             glBegin( GL_TRIANGLE_FAN );
00077                 glNormal3f( 0.0, 0.0, 1.0 );
00078                 glVertex3f( 0.0, 0.0, 1.0 );
00079 
00080                 for ( theta = 0.0; theta + eps < twopi; theta += d_theta ) {
00081                   sin_theta = sin( theta );
00082                   cos_theta = cos( theta );
00083 
00084                     x = cos_theta * sin_phi_d_phi;
00085                   y = sin_theta * sin_phi_d_phi;
00086                     z = cos_phi_d_phi;
00087                     glNormal3f( x, y, z );
00088                     glVertex3f( x, y, z );
00089 
00090                 } 
00091 
00092               x = sin_phi_d_phi;
00093               y = 0.0;
00094               z = cos_phi_d_phi;
00095                 glNormal3f( x, y, z );
00096                 glVertex3f( x, y, z );
00097             glEnd();
00098 
00099         } else if ( phi + d_phi + eps >= M_PI ) {
00100             
00101             glBegin( GL_TRIANGLE_FAN );
00102                 glNormal3f( 0.0, 0.0, -1.0 );
00103                 glVertex3f( 0.0, 0.0, -1.0 );
00104 
00105                 for ( theta = twopi; theta - eps > 0; theta -= d_theta ) {
00106                   sin_theta = sin( theta );
00107                   cos_theta = cos( theta );
00108 
00109                     x = cos_theta * sin_phi;
00110                     y = sin_theta * sin_phi;
00111                     z = cos_phi;
00112                     glNormal3f( x, y, z );
00113                     glVertex3f( x, y, z );
00114                 } 
00115                 x = sin_phi;
00116                 y = 0.0;
00117                 z = cos_phi;
00118                 glNormal3f( x, y, z );
00119                 glVertex3f( x, y, z );
00120             glEnd();
00121 
00122         } else {
00123             
00124             glBegin( GL_TRIANGLE_STRIP );
00125                 
00126                 for ( theta = 0.0; theta + eps < twopi; theta += d_theta ) {
00127                   sin_theta = sin( theta );
00128                   cos_theta = cos( theta );
00129 
00130                     x = cos_theta * sin_phi;
00131                     y = sin_theta * sin_phi;
00132                     z = cos_phi;
00133                     glNormal3f( x, y, z );
00134                     glVertex3f( x, y, z );
00135 
00136                     x = cos_theta * sin_phi_d_phi;
00137                     y = sin_theta * sin_phi_d_phi;
00138                     z = cos_phi_d_phi;
00139                     glNormal3f( x, y, z );
00140                     glVertex3f( x, y, z );
00141                 } 
00142                 x = sin_phi;
00143                 y = 0.0;
00144                 z = cos_phi;
00145                 glNormal3f( x, y, z );
00146                 glVertex3f( x, y, z );
00147 
00148                 x = sin_phi_d_phi;
00149                 y = 0.0;
00150                 z = cos_phi_d_phi;
00151                 glNormal3f( x, y, z );
00152                 glVertex3f( x, y, z );
00153 
00154             glEnd();
00155 
00156         } 
00157     } 
00158 } 
00159 
00160 #endif /* USE_GLUSPHERE */
00161 
00162 static GLuint get_sphere_display_list( int divisions ) {
00163     static bool initialized = false;
00164     static int num_display_lists;
00165     static GLuint *display_lists = NULL;
00166     int base_divisions;
00167     int i, idx;
00168 
00169     if ( !initialized ) {
00170        initialized = true;
00171        base_divisions = getparam_tux_sphere_divisions();
00172 
00173        num_display_lists = MAX_SPHERE_DIVISIONS - MIN_SPHERE_DIVISIONS + 1;
00174 
00175        check_assertion( display_lists == NULL, "display_lists not NULL" );
00176        display_lists = (GLuint*) malloc( sizeof(GLuint) * num_display_lists );
00177 
00178        for (i=0; i<num_display_lists; i++) {
00179            display_lists[i] = 0;
00180        }
00181     }
00182 
00183 
00184     idx = divisions - MIN_SPHERE_DIVISIONS;
00185 
00186     check_assertion( idx >= 0 &&
00187                    idx < num_display_lists, 
00188                    "invalid number of sphere subdivisions" );
00189 
00190     if ( display_lists[idx] == 0 ) {
00191        /* Initialize the sphere display list */
00192        display_lists[idx] = glGenLists(1);
00193        glNewList( display_lists[idx], GL_COMPILE );
00194        draw_sphere( divisions );
00195        glEndList();
00196     }
00197 
00198     return display_lists[idx];
00199 }
00200 
00201 
00202 
00203 /*--------------------------------------------------------------------------*/
00204 
00205 /* Traverses the DAG structure and draws the nodes
00206  */
00207 void traverse_dag( scene_node_t *node, material_t *mat )
00208 {
00209     scene_node_t *child;
00210 
00211     check_assertion( node != NULL, "node is NULL" );
00212     glPushMatrix();
00213 
00214     glMultMatrixd( (double *) node->trans.data );
00215 
00216     if ( node->mat != NULL ) {
00217         mat = node->mat;
00218     } 
00219 
00220     if ( node->geom == Sphere ) {
00221         set_material( mat->diffuse, mat->specular, 
00222                      mat->specular_exp );
00223 
00224        if ( getparam_use_sphere_display_list() ) {
00225            glCallList( get_sphere_display_list( 
00226               node->param.sphere.divisions ) );
00227        } else {
00228            draw_sphere( node->param.sphere.divisions );
00229        }
00230     } 
00231 
00232     child = node->child;
00233     while (child != NULL) {
00234         traverse_dag( child, mat );
00235         child = child->next;
00236     } 
00237 
00238     glPopMatrix();
00239 } 
00240 
00241 /*--------------------------------------------------------------------------*/
00242 
00243 /*
00244  * make_normal - creates the normal vector for the surface defined by a convex
00245  * polygon; points in polygon must be specifed in counter-clockwise direction
00246  * when viewed from outside the shape for the normal to be outward-facing
00247  */
00248 pp::Vec3d make_normal( pp::Polygon p, pp::Vec3d *v )
00249 {
00250     pp::Vec3d normal, v1, v2;
00251     double old_len;
00252 
00253     check_assertion( p.numVertices > 2, "number of vertices must be > 2" );
00254 
00255     v1 = v[p.vertices[1]] - v[p.vertices[0]];
00256     v2 = v[p.vertices[p.numVertices-1]] - v[p.vertices[0]];
00257     normal = v1^v2;
00258 
00259     old_len = normal.normalize();
00260     //check_assertion( old_len > 0, "normal vector has length 0" );
00261     return normal;
00262 } 
00263 
00264 /*--------------------------------------------------------------------------*/
00265 
00266 /* Returns true iff the specified polygon intersections a unit-radius sphere
00267  * centered at the origin.  */
00268 bool intersect_polygon( pp::Polygon p, pp::Vec3d *v )
00269 {
00270     ray_t ray; 
00271     pp::Vec3d nml, edge_nml, edge_vec;
00272     pp::Vec3d pt;
00273     double d, s, nuDotProd, wec;
00274     double edge_len, t, distsq;
00275     int i;
00276 
00277     /* create a ray from origin along polygon normal */
00278     nml = make_normal( p, v );
00279     ray.pt = pp::Vec3d( 0., 0., 0. );
00280     ray.vec = nml;
00281 
00282     nuDotProd = nml*ray.vec;
00283     if ( fabs(nuDotProd) < EPS )
00284         return false;
00285 
00286     /* determine distance of plane from origin */
00287     d = -( nml.x * v[p.vertices[0]].x + 
00288            nml.y * v[p.vertices[0]].y + 
00289            nml.z * v[p.vertices[0]].z );
00290 
00291     /* if plane's distance to origin > 1, immediately reject */
00292     if ( fabs( d ) > 1 )
00293         return false;
00294 
00295     /* check distances of edges from origin */
00296     for ( i=0; i < p.numVertices; i++ ) {
00297        pp::Vec3d *v0, *v1;
00298 
00299        v0 = &v[p.vertices[i]];
00300        v1 = &v[p.vertices[ (i+1) % p.numVertices ]]; 
00301 
00302        edge_vec = (*v1) - (*v0) ;
00303        edge_len = edge_vec.normalize();
00304 
00305        /* t is the distance from v0 of the closest point on the line
00306            to the origin */
00307        t = - ( *((pp::Vec3d *) v0)* edge_vec );
00308 
00309        if ( t < 0 ) {
00310            /* use distance from v0 */
00311            distsq = v0->length2();
00312        } else if ( t > edge_len ) {
00313            /* use distance from v1 */
00314            distsq = v1->length2();
00315        } else {
00316            /* closest point to origin is on the line segment */
00317            *v0 = (*v0)+(t*edge_vec);
00318            distsq = v0->length2();
00319        }
00320 
00321        if ( distsq <= 1 ) {
00322            return true;
00323        }
00324     }
00325 
00326     /* find intersection point of ray and plane */
00327     s = - ( d + ( nml*pp::Vec3d(ray.pt.x, ray.pt.y, ray.pt.z) ) ) /
00328         nuDotProd;
00329 
00330     pt = ray.pt+(s*ray.vec);
00331 
00332     /* test if intersection point is in polygon by clipping against it 
00333      * (we are assuming that polygon is convex) */
00334     for ( i=0; i < p.numVertices; i++ ) {
00335         edge_nml = nml^( (v[p.vertices[ (i+1) % p.numVertices ]]) - v[p.vertices[i]] );
00336 
00337         wec = (pt - v[p.vertices[i]] )*edge_nml;
00338         if (wec < 0)
00339             return false;
00340     } 
00341 
00342     return true;
00343 } 
00344 
00345 /*--------------------------------------------------------------------------*/
00346 
00347 /* returns true iff polyhedron intersects unit-radius sphere centered
00348    at origin */
00349 bool intersect_polyhedron( pp::Polyhedron p )
00350 {
00351     bool hit = false;
00352     int i;
00353        
00354     for (i=0; i<p.num_polygons; i++) {
00355               
00356               hit = intersect_polygon( p.polygons[i], p.vertices );
00357         if ( hit == true ) 
00358             break;
00359     } 
00360     return hit;
00361 } 
00362 
00363 /*--------------------------------------------------------------------------*/
00364 
00365 pp::Polyhedron copy_polyhedron( pp::Polyhedron ph )
00366 {
00367     int i;
00368     pp::Polyhedron newph = ph;
00369     newph.vertices = (pp::Vec3d *) malloc( sizeof(pp::Vec3d) * ph.num_vertices );
00370     for (i=0; i<ph.num_vertices; i++) {
00371         newph.vertices[i] = ph.vertices[i];
00372     } 
00373     return newph;
00374 } 
00375 
00376 /*--------------------------------------------------------------------------*/
00377 
00378 void free_polyhedron( pp::Polyhedron ph ) 
00379 {
00380     free(ph.vertices);
00381 } 
00382 
00383 /*--------------------------------------------------------------------------*/
00384 
00385 void trans_polyhedron( pp::Matrix mat, pp::Polyhedron ph )
00386 {
00387     int i;
00388     for (i=0; i<ph.num_vertices; i++) {
00389         ph.vertices[i] = mat.transformPoint(ph.vertices[i]);
00390     }
00391 }
00392 
00393 /*--------------------------------------------------------------------------*/
00394 
00395 bool check_polyhedron_collision_with_dag( 
00396     scene_node_t *node, pp::Matrix modelMatrix, pp::Matrix invModelMatrix,
00397     pp::Polyhedron ph)
00398 {
00399     pp::Matrix newModelMatrix, newInvModelMatrix;
00400     scene_node_t *child;
00401     pp::Polyhedron newph;
00402     bool hit = false;
00403 
00404     check_assertion( node != NULL, "node is NULL" );
00405 
00406     newModelMatrix=modelMatrix*node->trans;
00407     newInvModelMatrix=node->invtrans*invModelMatrix;
00408 
00409     if ( node->geom == Sphere ) {
00410         newph = copy_polyhedron( ph );
00411         trans_polyhedron( newInvModelMatrix, newph );
00412 
00413         hit = intersect_polyhedron( newph );
00414         free_polyhedron( newph );
00415     } 
00416 
00417     if (hit == true) return hit;
00418 
00419     child = node->child;
00420     while (child != NULL) {
00421 
00422         hit = check_polyhedron_collision_with_dag( 
00423            child, newModelMatrix, newInvModelMatrix, ph );
00424 
00425         if ( hit == true ) {
00426             return hit;
00427         }
00428 
00429         child = child->next;
00430     } 
00431 
00432     return false;
00433 }