Back to index

supertuxkart  0.5+dfsg1
static_ssg.cpp
Go to the documentation of this file.
00001 //  $Id: static_ssg.cpp 2111 2008-05-31 07:04:30Z cosmosninja $
00002 //
00003 //  SuperTuxKart - a fun racing game with go-kart
00004 //  Copyright (C) 2006 Joerg Henrichs
00005 //        Using the plib functions for InfoTriangle::collision and
00006 //        InfoTriangle::hot, (C) Steve Baker
00007 //
00008 //  This program is free software; you can redistribute it and/or
00009 //  modify it under the terms of the GNU General Public License
00010 //  as published by the Free Software Foundation; either version 2
00011 //  of the License, or (at your option) any later version.
00012 //
00013 //  This program is distribhuted in the hope that it will be useful,
00014 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 //  GNU General Public License for more details.
00017 //
00018 //  You should have received a copy of the GNU General Public License
00019 //  along with this program; if not, write to the Free Software
00020 //  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00021 #include <algorithm>
00022 #include "static_ssg.hpp"
00023 #include "material_manager.hpp"
00024 #include "material.hpp"
00025 #include "ssg_help.hpp"
00026 
00027 #ifndef round
00028 # define round(x)  (floor(x+0.5f))
00029 #endif
00030 
00031 StaticSSG::StaticSSG(ssgEntity* start_, int nSize)
00032 {
00033     m_start  = start_;
00034     m_x_min   = m_y_min =  1E10;
00035     m_x_max   = m_y_max = -1E10;
00036     m_test_number = 0;
00037     Setup(nSize);
00038 }   // StaticSSG
00039 
00040 //-----------------------------------------------------------------------------
00041 void StaticSSG::Setup(int nSize)
00042 {
00043     // First compute the minimum and maximum x/y values of all leaves
00044     MinMax(m_start, &m_x_min, &m_x_max, &m_y_min, &m_y_max);
00045 
00046     const float RATIO = (m_x_max-m_x_min)/(m_y_max-m_y_min);
00047 
00048     /* The m_n, m_m computed here is the maximum value which can be used,
00049        so the actual range is 0-m_n and 0-m_m, or m_n+1 and m_m+1 'buckets' */
00050     m_n = (int)round(sqrt(nSize/RATIO));
00051     m_m = (int)round(nSize/m_n);
00052 
00053     /* Make sure that we don't use more than requested.
00054        This is done by reducing the larger value by 1.  */
00055     while(m_n*m_m>nSize)
00056     {
00057         if(m_n>m_m) m_n--; else m_m--;
00058     }
00059 
00060     /* If 'm_m' would be used instead of 'm_m-1', the hash value for the column
00061        can be any number between 0 and m_m, i.e. m_m+1 different values!        */
00062     m_invdx   = (float)(m_m-1)/(m_x_max-m_x_min);
00063     m_invdy   = (float)(m_n-1)/(m_y_max-m_y_min);
00064     //JH  printf("hash data: m_m=%d, m_n=%d, m_x_max=%f, m_x_min=%f, m_y_max=%f, m_y_min=%f, m_invdx=%f, m_invdy=%f\m_n",
00065     //  m_m,m_n,m_x_max,m_x_min,m_y_max,m_y_min,m_invdx,m_invdy);
00066     m_buckets   = new allBucketsType(m_n*m_m);
00067 
00068     sgMat4 mat;
00069     sgMakeIdentMat4(mat);
00070     Distribute(m_start, mat);
00071 }   // Setup
00072 
00073 //-----------------------------------------------------------------------------
00074 void StaticSSG::Draw(ssgBranch* b)
00075 {
00076     for(int j=0; j<m_n; j++)
00077     {
00078         for(int i=0; i<m_m; i++)
00079         {
00080             ssgVertexArray* a = new ssgVertexArray();
00081             sgVec3 v;
00082             float h=0.2f;
00083             v[0]=m_x_min+1/m_invdx*i;    v[1]= m_y_min+1/m_invdy*j;    v[2]=h; a->add(v);
00084             v[0]=m_x_min+1/m_invdx*(i+1);v[1]= m_y_min+1/m_invdy*j;    v[2]=h; a->add(v);
00085             v[0]=m_x_min+1/m_invdx*(i+1);v[1]= m_y_min+1/m_invdy*(j+1);v[2]=h; a->add(v);
00086             v[0]=m_x_min+1/m_invdx*i;    v[1]= m_y_min+1/m_invdy*(j+1);v[2]=h; a->add(v);
00087             ssgColourArray* c = new ssgColourArray();
00088             v[0]=float(j)/float(m_n);v[1]=float(i)/float(m_m);v[2]=0;
00089             c->add(v);c->add(v);c->add(v);c->add(v);
00090             ssgVtxTable*    l = new ssgVtxTable(GL_POLYGON, a,
00091                                                 (ssgNormalArray*)NULL,
00092                                                 (ssgTexCoordArray*)NULL,
00093                                                 c);
00094             //       (ssgColourArray*)NULL);
00095             b->addKid(l);
00096         }   // for i
00097     }   //   for j
00098 }   // Draw
00099 
00100 //-----------------------------------------------------------------------------
00101 void StaticSSG::Distribute(ssgEntity* p, sgMat4 m)
00102 {
00103     if(p->isAKindOf(ssgTypeLeaf()))
00104     {
00105         ssgLeaf* l=(ssgLeaf*)p;
00106         if (material_manager->getMaterial(l)->isIgnore())return;
00107         for(int i=0; i<l->getNumTriangles(); i++)
00108         {
00109             short v1,v2,v3;
00110             sgVec3 vv1, vv2, vv3;
00111 
00112             l->getTriangle(i, &v1, &v2, &v3);
00113 
00114             sgXformPnt3 ( vv1, l->getVertex(v1), m );
00115             sgXformPnt3 ( vv2, l->getVertex(v2), m );
00116             sgXformPnt3 ( vv3, l->getVertex(v3), m );
00117             StoreTriangle(l, i, vv1, vv2, vv3);
00118         }   // for i<p->getNumTriangles
00119     }
00120     else if (p->isAKindOf(ssgTypeTransform()))
00121     {
00122         ssgBaseTransform* t=(ssgBaseTransform*)p;
00123 
00124         sgMat4 tmpT, tmpM;
00125         t->getTransform(tmpT);
00126         sgCopyMat4(tmpM, m);
00127         sgPreMultMat4(tmpM,tmpT);
00128 
00129         for(ssgEntity* e=t->getKid(0); e!=NULL; e=t->getNextKid())
00130         {
00131             Distribute(e, tmpM);
00132         }   // for i<getNumKids
00133 
00134     }
00135     else if (p->isAKindOf(ssgTypeBranch()))
00136     {
00137         ssgBranch* b =(ssgBranch*)p;
00138         for(ssgEntity* e=b->getKid(0); e!=NULL; e=b->getNextKid())
00139         {
00140             Distribute(e, m);
00141         }   // for i<getNumKids
00142     }
00143     else
00144     {
00145         printf("StaticSSG::Distribute: unkown type\n");
00146         p->print(stdout, 0, 0);
00147     }
00148 }   // Distribute
00149 //-----------------------------------------------------------------------------
00150 void StaticSSG::StoreTriangle(ssgLeaf* l, int indx, sgVec3 vv1,
00151                               sgVec3 vv2, sgVec3 vv3           )
00152 {
00153     InfoTriangle* t;
00154     t = new InfoTriangle(l, indx, vv1, vv2, vv3);
00155     t->m_x_min = std::min(std::min(vv1[0],vv2[0]), vv3[0]);
00156     t->m_x_max = std::max(std::max(vv1[0],vv2[0]), vv3[0]);
00157     t->m_y_min = std::min(std::min(vv1[1],vv2[1]), vv3[1]);
00158     t->m_y_max = std::max(std::max(vv1[1],vv2[1]), vv3[1]);
00159     sgMakePlane(t->m_plane, vv1,vv2,vv3);
00160     int nMin, mMin, nMax, mMax;
00161     GetRowCol(t->m_x_min, t->m_y_min, &mMin, &nMin);
00162     GetRowCol(t->m_x_max, t->m_y_max, &mMax, &nMax);
00163     for(int j=nMin; j<=nMax; j++)
00164     {
00165         for(int i=mMin; i<=mMax; i++)
00166         {
00167             int nHash = GetHash(i, j);
00168             (*m_buckets)[nHash].push_back(t);
00169         }   // for i<=mMax
00170     }   // for j<=nMax
00171 
00172 }   // StoreTriangle
00173 
00174 //-----------------------------------------------------------------------------
00175 float StaticSSG::hot(sgVec3 start, sgVec3 end, ssgLeaf** leaf, sgVec4** nrm)
00176 {
00177 
00178     float hot      = NOINTERSECT;
00179     int N_HASH_START = GetHash(start[0], start[1]);
00180     int nTriangles = (int)(*m_buckets)[N_HASH_START].size();
00181     *leaf          = NULL;
00182     for(int i=0; i<nTriangles; i++)
00183     {
00184         InfoTriangle *t = (*m_buckets)[N_HASH_START][i];
00185         const float HOT_NEW = t->hot(start);
00186         if(HOT_NEW>hot)
00187         {
00188             hot   = HOT_NEW;
00189             *leaf = t->m_leaf;
00190             *nrm  = &t->m_plane;
00191         }
00192     }   // for i <nTriangles
00193 
00194     if(start[0]==end[0] && start[1]==end[1]) return hot;
00195 
00196     const int HASH_END = GetHash(end[0], end[1]);
00197     nTriangles   = (int)(*m_buckets)[HASH_END].size();
00198     for(int i=0; i<nTriangles; i++)
00199     {
00200         InfoTriangle *t = (*m_buckets)[HASH_END][i];
00201         const float HOT_NEW = t->hot(end);
00202         if(HOT_NEW>hot)
00203         {
00204             hot=HOT_NEW;
00205             *leaf = t->m_leaf;
00206         }
00207     }   // for i <nTriangles
00208     return hot;
00209 }   // StaticSSG::hot
00210 //-----------------------------------------------------------------------------
00211 int StaticSSG::collision(sgSphere *s, AllHits *allHits)
00212 {
00213 
00214     sgVec3 center; sgCopyVec3(center,s->getCenter());
00215     float  RADIUS  = s->getRadius();
00216 
00217     /* m_test_number is used to tag each triangle tested during this call to
00218        collision. This way we make sure that each triangle is tested at 
00219        most once, even if it belongs to different buckets. To remove the 
00220        need to reset the m_test_nr value, we increase the testnumber at each test, 
00221        and only reset this flag if the m_test_number wraps around again to 
00222        zero ... which is unlikely to happen :)                              */
00223     m_test_number++;
00224     if(m_test_number==0)
00225     {
00226         /* wrap around of the test number, reset all m_test_nr values to zero,
00227            and set m_test_number to 1 to have a clean start                      */
00228         for(unsigned int i=0; i<m_all_leaves.size(); i++)
00229         {
00230             m_all_leaves[i]->m_test_nr=0;
00231         }
00232         m_test_number=1;
00233     }   // if m_test_number==0
00234 
00235     int nMin, nMax, mMin, mMax;
00236     GetRowCol(center[0]-RADIUS, center[1]-RADIUS, &mMin, &nMin);
00237     GetRowCol(center[0]+RADIUS, center[1]+RADIUS, &mMax, &nMax);
00238     int count=0;
00239     for(int j=nMin; j<=nMax; j++)
00240     {
00241         for(int i=mMin; i<=mMax; i++)
00242         {
00243             int N_HASH  = GetHash(i, j);
00244             if(N_HASH<0 || N_HASH>=m_n*m_m)
00245             {   // that should be a car off track
00246                 continue;                   // rescue should take care of this
00247             }
00248             int nCount = (int)(*m_buckets)[N_HASH].size();
00249             for(int k=0; k<nCount; k++)
00250             {
00251                 InfoTriangle *t = (*m_buckets)[N_HASH][k];
00252                 // Make sure that each triangle is tested only once
00253                 if(t->m_test_nr!=m_test_number)
00254                 {
00255                     t->m_test_nr=m_test_number;
00256                     if(t->collision(s))
00257                     {
00258                         allHits->push_back(t);
00259                         count++;
00260                     }   // if hit
00261                 }   // if t->m_test_nr!=m_test_number
00262             }   // for k
00263         }   // for i<=mMax
00264     }   // for j<=nMax
00265 
00266     return count;
00267 }   // StaticSSG::collision
00268 
00269 //=============================================================================
00270 float InfoTriangle::hot(sgVec3 s)
00271 {
00272     /*
00273       Does the X/Y coordinate lie outside the triangle's bbox, or
00274       does the Z coordinate lie beneath the bbox ?
00275     */
00276     if ( ( s[0] < m_vv1[0] && s[0] < m_vv2[0] && s[0] < m_vv3[0] ) ||
00277          ( s[1] < m_vv1[1] && s[1] < m_vv2[1] && s[1] < m_vv3[1] ) ||
00278          ( s[0] > m_vv1[0] && s[0] > m_vv2[0] && s[0] > m_vv3[0] ) ||
00279          ( s[1] > m_vv1[1] && s[1] > m_vv2[1] && s[1] > m_vv3[1] ) ||
00280          ( s[2] < m_vv1[2] && s[2] < m_vv2[2] && s[2] < m_vv3[2] ) ) return NOINTERSECT;
00281 
00282 
00283     /* No HOT from upside-down or vertical triangles */
00284     if ( m_leaf->getCullFace() && m_plane [ 2 ] <= 0 ) return NOINTERSECT;
00285 
00286     /* Find the point vertically below the text point
00287        as it crosses the plane of the polygon */
00288     const float Z = sgHeightOfPlaneVec2 ( m_plane, s );
00289 
00290     /* No HOT from below the triangle */
00291     if ( Z > s[2] ) return NOINTERSECT;
00292 
00293     /* Outside the vertical extent of the triangle? */
00294     if ( ( Z < m_vv1[2] && Z < m_vv2[2] && Z < m_vv3[2] ) ||
00295          ( Z > m_vv1[2] && Z > m_vv2[2] && Z > m_vv3[2] ) ) return NOINTERSECT;
00296 
00297     /*
00298       Now it gets messy - the isect point is inside
00299       the bbox of the triangle - but that's not enough.
00300       Is it inside the triangle itself?
00301     */
00302     const float  E1 =  s [0] * m_vv1[1] -  s [1] * m_vv1[0] ;
00303     const float  E2 =  s [0] * m_vv2[1] -  s [1] * m_vv2[0] ;
00304     const float  E3 =  s [0] * m_vv3[1] -  s [1] * m_vv3[0] ;
00305     const float EP1 = m_vv1[0] * m_vv2[1] - m_vv1[1] * m_vv2[0] ;
00306     const float EP2 = m_vv2[0] * m_vv3[1] - m_vv2[1] * m_vv3[0] ;
00307     const float EP3 = m_vv3[0] * m_vv1[1] - m_vv3[1] * m_vv1[0] ;
00308 
00309     const float AP = (float) fabs ( EP1 + EP2 + EP3 ) ;
00310     const float AI = (float) ( fabs ( E1 + EP1 - E2 ) +
00311                          fabs ( E2 + EP2 - E3 ) +
00312                          fabs ( E3 + EP3 - E1 ) ) ;
00313 
00314     if ( AI > AP * 1.01 ) return NOINTERSECT;
00315 
00316     return Z;
00317 }   // InfoTriangle::hot
00318 
00319 //-----------------------------------------------------------------------------
00320 int InfoTriangle::collision(sgSphere *s)
00321 {
00322 
00323     const sgVec3 * const CENTER = (sgVec3*)s->getCenter();
00324     const float R = s->getRadius();
00325 
00326     /* First test: see if the sphere is outside the 2d bounding box
00327        of the triangle - a quite fast and easy test                 */
00328     if((*CENTER)[0]+R<m_x_min || (*CENTER)[0]-R>m_x_max ||
00329        (*CENTER)[1]+R<m_y_min || (*CENTER)[1]-R>m_y_max)
00330     {
00331         return 0;
00332     }
00333 
00334     m_dist = (float)fabs( sgDistToPlaneVec3(m_plane, s->getCenter()) );
00335 
00336     if ( m_dist > R ) return 0;
00337 
00338     /*
00339       The BSphere touches the plane containing
00340       the triangle - but does it actually touch
00341       the triangle itself?  Let's erect some
00342       vertical walls around the triangle.
00343     */
00344 
00345     /*
00346       Construct a 'wall' as a plane through
00347       two vertices and a third vertex made
00348       by adding the surface normal to the
00349       first of those two vertices.
00350     */
00351 
00352     sgVec3 vvX;
00353     sgVec4 planeX;
00354 
00355     sgAddVec3 ( vvX, m_plane, m_vv1 );
00356     sgMakePlane ( planeX, m_vv1, m_vv2, vvX );
00357     const float DP1 = sgDistToPlaneVec3 ( planeX, s->getCenter() );
00358 
00359     if ( DP1 > s->getRadius() ) return 0;
00360 
00361     sgAddVec3 ( vvX, m_plane, m_vv2 );
00362     sgMakePlane ( planeX, m_vv2, m_vv3, vvX );
00363     const float DP2 = sgDistToPlaneVec3 ( planeX, s->getCenter() );
00364 
00365     if ( DP2 > s->getRadius() ) return 0;
00366 
00367     sgAddVec3 ( vvX, m_plane, m_vv3 );
00368     sgMakePlane ( planeX, m_vv3, m_vv1, vvX );
00369     const float DP3 = sgDistToPlaneVec3 ( planeX, s->getCenter() );
00370 
00371     if ( DP3 > s->getRadius() ) return 0;
00372 
00373     /*
00374       OK, so we now know that the sphere
00375       intersects the plane of the triangle
00376       and is not more than one radius outside
00377       the walls. However, you can still get
00378       close enough to the wall and to the
00379       triangle itself and *still* not
00380       intersect the triangle itself.
00381 
00382       However, if the center is inside the
00383       triangle then we don't need that
00384       costly test.
00385     */
00386 
00387     if ( DP1 <= 0 && DP2 <= 0 && DP3 <= 0 ) return 1;
00388 
00389     /*
00390       <sigh> ...now we really need that costly set of tests...
00391 
00392       If the sphere penetrates the plane of the triangle
00393       and the plane of the wall, then we can use pythagoras
00394       to determine if the sphere actually intersects that
00395       edge between the wall and the triangle.
00396 
00397       if ( dp_sqd + dp1_sqd > radius_sqd ) ...in! else ...out!
00398     */
00399 
00400     const float R2 = s->getRadius() * s->getRadius() - m_dist * m_dist ;
00401 
00402     if ( DP1 * DP1 <= R2 || DP2 * DP2 <= R2 || DP3 * DP3 <= R2 )
00403     {
00404         return 1;
00405     }
00406     return 0;
00407 }   // InfoTriangle::collision