nevrax.org : docs

00001 
+00007 /* Copyright, 2000 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "std3d.h"
+00027 
+00028 #include "3d/mini_col.h"
+00029 #include "nel/misc/aabbox.h"
+00030 #include "3d/quad_grid.h"
+00031 using namespace NLMISC;
+00032 using namespace std;
+00033 
+00034 
+00035 namespace NL3D 
+00036 {
+00037 
+00038 static const    sint    QuadDepth= 10;
+00039 
+00040 
+00041 // Element for grid lookup.
+00042 static const sint       GridSize=512;
+00043 static const float      GridEltSize=2;
+00044 
+00045 
+00046 // ***************************************************************************
+00047 CMiniCol::CMiniCol()
+00048 {
+00049         _RadMin= 100;
+00050         _RadMax= 125;
+00051         _Grid.create(GridSize, GridEltSize);
+00052 }
+00053 
+00054 
+00055 // ***************************************************************************
+00056 void                    CMiniCol::addFaces(const std::vector<CTriangle> &faces, uint16 zoneId, uint16 patchId)
+00057 {
+00058         for(sint i=0;i<(sint)faces.size();i++)
+00059         {
+00060                 const CTriangle &f= faces[i];
+00061                 CAABBox box;
+00062                 box.setCenter(f.V0);
+00063                 box.extend(f.V1);
+00064                 box.extend(f.V2);
+00065                 CFace   node;
+00066                 node.Face= f;
+00067                 node.Plane.make(f.V0, f.V1, f.V2);
+00068                 node.ZoneId= zoneId;
+00069                 node.PatchId=patchId;
+00070                 _Grid.insert(box.getMin(), box.getMax(), node);
+00071         }
+00072 }
+00073 
+00074 
+00075 // ***************************************************************************
+00076 void                    CMiniCol::addLandscapePart(uint16 zoneId, uint16 patchId)
+00077 {
+00078         vector<CTriangle> faces;
+00079         _Landscape->buildCollideFaces(zoneId, patchId, faces);
+00080         addFaces(faces, zoneId, patchId);
+00081 }
+00082 
+00083 
+00084 // ***************************************************************************
+00085 void                    CMiniCol::removeLandScapePart(uint16 zoneId, uint16 patchId, const CBSphere &sphere)
+00086 {
+00087         // Build the AAbox which englobe the bsphere of the patch.
+00088         CAABBox         bb;
+00089         bb.setCenter(sphere.Center);
+00090         float   l= sphere.Radius;
+00091         bb.setHalfSize(CVector(l,l,l));
+00092 
+00093         // For optimisation, select only faces which are IN the bbox of the patch.
+00094         _Grid.select(bb.getMin(), bb.getMax());
+00095         CQuadGrid<CFace>::CIterator     iFace;
+00096         for(iFace= _Grid.begin();iFace!=_Grid.end();)
+00097         {
+00098                 if((*iFace).isFromPatch(zoneId, patchId))
+00099                         iFace= _Grid.erase(iFace);
+00100                 else
+00101                         iFace++;
+00102         }
+00103 }
+00104 
+00105 
+00106 // ***************************************************************************
+00107 void                    CMiniCol::init(CLandscape *land, float radMin, float radDelta)
+00108 {
+00109         _Landscape= land;
+00110         _RadMin= radMin;
+00111         _RadMax= radMin+radDelta;
+00112 }
+00113 
+00114 
+00115 // ***************************************************************************
+00116 void                    CMiniCol::addZone(uint16 zoneId)
+00117 {
+00118         CZoneIdent      newZone;
+00119 
+00120         // landscape must have been inited.
+00121         nlassert(_Landscape);
+00122         const CZone     *zone= _Landscape->getZone(zoneId);
+00123         // zone must be loaded into landscape.
+00124         nlassert(zone);
+00125 
+00126         // Fill the newzone.
+00127         newZone.ZoneId= zoneId;
+00128         newZone.Sphere.Center= zone->getZoneBB().getCenter();
+00129         newZone.Sphere.Radius= zone->getZoneBB().getRadius();
+00130         newZone.Patchs.resize(zone->getNumPatchs());
+00131         for(sint i=0;i<zone->getNumPatchs();i++)
+00132         {
+00133                 const   CPatch  &pa= *zone->getPatch(i);
+00134                 newZone.Patchs[i].Sphere= pa.getBSphere();
+00135         }
+00136 
+00137         // Add it to the set (if not already done...).
+00138         _Zones.insert(newZone);
+00139 }
+00140 
+00141 
+00142 // ***************************************************************************
+00143 void                    CMiniCol::removeZone(uint16 zoneId)
+00144 {
+00145         CZoneIdent      delZone;
+00146 
+00147 
+00148         // First, delete all patch from the grid.
+00149         //=======================================
+00150         // Fill the key part only.
+00151         delZone.ZoneId= zoneId;
+00152         // Find the zone (or quit).
+00153         TZoneSet::iterator      itZone;
+00154         itZone= _Zones.find(delZone);
+00155         if(itZone==_Zones.end())
+00156                 return;
+00157 
+00158         CZoneIdent      &zone= const_cast<CZoneIdent&>(*itZone);
+00159         for(sint i=0;i<(sint)zone.Patchs.size();i++)
+00160         {
+00161                 CPatchIdent     &pa= zone.Patchs[i];
+00162                 if(pa.Inserted)
+00163                 {
+00164                         // Reject the patch.
+00165                         removeLandScapePart(zone.ZoneId, i, pa.Sphere);
+00166                         pa.Inserted= false;
+00167                         zone.NPatchInserted--;
+00168                 }
+00169         }
+00170 
+00171         // Then, delete it.
+00172         //=================
+00173         _Zones.erase(delZone);
+00174         
+00175 }
+00176 
+00177 
+00178 // ***************************************************************************
+00179 void                    CMiniCol::setCenter(const CVector& center)
+00180 {
+00181         CBSphere        BMin(center, _RadMin), BMax(center, _RadMax);
+00182 
+00183         // For all zones, test if must insert patchs..
+00184         TZoneSet::iterator      itZone;
+00185         for(itZone= _Zones.begin();itZone!=_Zones.end();itZone++)
+00186         {
+00187                 CZoneIdent      &zone= const_cast<CZoneIdent&>(*itZone);
+00188 
+00189                 // Tests must be done in 2D...
+00190                 BMin.Center.z= zone.Sphere.Center.z;
+00191                 BMax.Center.z= zone.Sphere.Center.z;
+00192 
+00193                 // Must test first if the zone is IN the area.
+00194                 //=============================================
+00195                 bool    zoneIn= false;
+00196                 if(zone.NPatchInserted==0)
+00197                 {
+00198                         if(BMin.intersect(zone.Sphere))
+00199                                 zoneIn= true;
+00200                 }
+00201                 else
+00202                         zoneIn= true;
+00203 
+00204                 // Then for all patchs, must test if the patch must be inserted, or rejected.
+00205                 //=============================================
+00206                 if(zoneIn)
+00207                 {
+00208                         for(sint i=0;i<(sint)zone.Patchs.size();i++)
+00209                         {
+00210                                 CPatchIdent     &pa= zone.Patchs[i];
+00211 
+00212                                 // Tests must be done in 2D...
+00213                                 BMin.Center.z= pa.Sphere.Center.z;
+00214                                 BMax.Center.z= pa.Sphere.Center.z;
+00215 
+00216                                 if(pa.Inserted)
+00217                                 {
+00218                                         // Reject the patch, if entirely OUT the max radius.
+00219                                         if(!BMax.intersect(pa.Sphere))
+00220                                         {
+00221                                                 removeLandScapePart(zone.ZoneId, i, pa.Sphere);
+00222                                                 pa.Inserted= false;
+00223                                                 zone.NPatchInserted--;
+00224                                         }
+00225                                 }
+00226                                 else
+00227                                 {
+00228                                         // Insert the pacth, if only partially IN the min radius.
+00229                                         if(BMin.intersect(pa.Sphere))
+00230                                         {
+00231                                                 addLandscapePart(zone.ZoneId, i);
+00232                                                 pa.Inserted= true;
+00233                                                 zone.NPatchInserted++;
+00234                                         }
+00235                                 }
+00236                         }
+00237                 }
+00238         }
+00239 }
+00240 
+00241 
+00242 // ***************************************************************************
+00243 bool                    CMiniCol::snapToGround(CVector &pos, float hup, float hbot)
+00244 {
+00245         CVector b1,b2;
+00246         bool    found=false;
+00247         float   height;
+00248 
+00249 
+00250         // Select quad nodes which contains pos.
+00251         b1=b2=pos;
+00252         b1.z-= hbot;
+00253         b2.z+= hup;
+00254         // Select.
+00255         _Grid.select(b1,b2);
+00256 
+00257         // For each face, test if it is under pos, then test if height is correct.
+00258         CQuadGrid<CFace>::CIterator     iFace;
+00259         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
+00260         {
+00261                 CTriangle       &pFace= (*iFace).Face;
+00262                 CPlane          &pPlane= (*iFace).Plane;
+00263                 // Order is important.
+00264                 CVector         &p0= pFace.V0;
+00265                 CVector         &p1= pFace.V1;
+00266                 CVector         &p2= pFace.V2;
+00267 
+00268                 // TOIMP: This is VERY SLOW!!! (hope that the quadtree will help, but it still very slow...).
+00269 
+00270                 // Yoyo Debug, test, if the point may be IN the bbox.
+00271                 /*CAABBox               bbFace;
+00272                 bbFace.setCenter(p0);
+00273                 bbFace.extend(p1);
+00274                 bbFace.extend(p2);
+00275                 CVector         bext=p0;
+00276                 bext.z= maxof(p0.z, p1.z, p2.z)+hbot;
+00277                 bbFace.extend(bext);
+00278                 bext.z= minof(p0.z, p1.z, p2.z)-hup;
+00279                 bbFace.extend(bext);
+00280                 if(!bbFace.include(pos))
+00281                         continue;*/
+00282 
+00283                 // Test if the face enclose the pos in X/Y plane.
+00284                 // NB: compute and using a BBox to do a rapid test is not a very good idea, since it will 
+00285                 // add an overhead which is NOT negligeable compared to the following test.
+00286                 float           a,b,c;          // 2D cartesian coefficients of line in plane X/Y.
+00287                 // Line p0-p1.
+00288                 a= -(p1.y-p0.y);
+00289                 b= (p1.x-p0.x);
+00290                 c= -(p0.x*a + p0.y*b);
+00291                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00292                 // Line p1-p2.
+00293                 a= -(p2.y-p1.y);
+00294                 b= (p2.x-p1.x);
+00295                 c= -(p1.x*a + p1.y*b);
+00296                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00297                 // Line p2-p0.
+00298                 a= -(p0.y-p2.y);
+00299                 b= (p0.x-p2.x);
+00300                 c= -(p2.x*a + p2.y*b);
+00301                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00302 
+00303 
+00304                 // Compute the possible height.
+00305                 CVector         tmp;
+00306                 // intersect the vertical line with the plane.
+00307                 tmp= pPlane.intersect(pos, pos-CVector(0,0,100));
+00308 
+00309                 /*
+00310                 // CTriangle intersect() method.
+00311                 CVector tmp;
+00312                 if(pFace.intersect(b1, b2, tmp, pPlane))
+00313                 */
+00314                 {
+00315                         float           h= tmp.z;
+00316                         // Test if it would fit in the wanted field.
+00317                         if(h>pos.z+hup) continue;
+00318                         if(h<pos.z-hbot)        continue;
+00319 
+00320                         // OK!!
+00321                         if(!found)
+00322                         {
+00323                                 found=true;
+00324                                 height=h;
+00325                         }
+00326                         else
+00327                         {
+00328                                 height= max(height,h);
+00329                         }
+00330                 }
+00331         }
+00332 
+00333         if(found)
+00334                 pos.z= height;
+00335 
+00336         return found;
+00337 }
+00338 
+00339 
+00340 
+00341 // ***************************************************************************
+00342 bool                    CMiniCol::getGroundNormal(const CVector &pos, CVector &normal, float hup, float hbot)
+00343 {
+00344         CVector b1,b2;
+00345         bool    found=false;
+00346         float   height=0.0;
+00347 
+00348 
+00349         // Select quad nodes which contains pos.
+00350         b1=b2=pos;
+00351         b1.z-= hbot;
+00352         b2.z+= hup;
+00353         // Select.
+00354         _Grid.select(b1,b2);
+00355 
+00356         // For each face, test if it is under pos, then test if height is correct.
+00357         CQuadGrid<CFace>::CIterator     iFace;
+00358         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
+00359         {
+00360                 CTriangle       &pFace= (*iFace).Face;
+00361                 CPlane          &pPlane= (*iFace).Plane;
+00362                 // Order is important.
+00363                 CVector         &p0= pFace.V0;
+00364                 CVector         &p1= pFace.V1;
+00365                 CVector         &p2= pFace.V2;
+00366 
+00367                 // TOIMP: This is VERY SLOW!!! (hope that the quadtree will help, but it still very slow...).
+00368 
+00369                 // Yoyo Debug, test, if the point may be IN the bbox.
+00370                 CAABBox         bbFace;
+00371                 bbFace.setCenter(p0);
+00372                 bbFace.extend(p1);
+00373                 bbFace.extend(p2);
+00374                 CVector         bext=p0;
+00375                 bext.z= maxof(p0.z, p1.z, p2.z)+hbot;
+00376                 bbFace.extend(bext);
+00377                 bext.z= minof(p0.z, p1.z, p2.z)-hup;
+00378                 bbFace.extend(bext);
+00379                 if(!bbFace.include(pos))
+00380                         continue;
+00381 
+00382                 // Test if the face enclose the pos in X/Y plane.
+00383                 // NB: compute and using a BBox to do a rapid test is not a very good idea, since it will 
+00384                 // add an overhead which is NOT negligeable compared to the following test.
+00385                 float           a,b,c;          // 2D cartesian coefficients of line in plane X/Y.
+00386                 // Line p0-p1.
+00387                 a= -(p1.y-p0.y);
+00388                 b= (p1.x-p0.x);
+00389                 c= -(p0.x*a + p0.y*b);
+00390                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00391                 // Line p1-p2.
+00392                 a= -(p2.y-p1.y);
+00393                 b= (p2.x-p1.x);
+00394                 c= -(p1.x*a + p1.y*b);
+00395                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00396                 // Line p2-p0.
+00397                 a= -(p0.y-p2.y);
+00398                 b= (p0.x-p2.x);
+00399                 c= -(p2.x*a + p2.y*b);
+00400                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
+00401 
+00402 
+00403                 // Compute the possible height.
+00404                 CVector         tmp;
+00405                 // intersect the vertical line with the plane.
+00406                 tmp= pPlane.intersect(pos, pos-CVector(0,0,100));
+00407                 float           h= tmp.z;
+00408                 // Test if it would fit in the wanted field.
+00409                 if(h>pos.z+hup) continue;
+00410                 if(h<pos.z-hbot)        continue;
+00411 
+00412                 // OK!!
+00413                 if(!found)
+00414                 {
+00415                         found=true;
+00416                         height=h;
+00417                         normal= pPlane.getNormal();
+00418                 }
+00419                 else
+00420                 {
+00421                         if(h>height)
+00422                         {
+00423                                 normal= pPlane.getNormal();
+00424                                 height= h;
+00425                         }
+00426                 }
+00427         }
+00428 
+00429         return found;
+00430 }
+00431 
+00432 
+00433 // ***************************************************************************
+00434 bool                    CMiniCol::testMove(const CVector &prec, CVector &cur)
+00435 {
+00436         CVector dir= cur-prec;
+00437         dir.normalize();
+00438 
+00439         // Angle max.
+00440         float   anglemax= 65;   // 65 degrees.
+00441         anglemax= (float)tan( anglemax*Pi/180);
+00442 
+00443         // Must not go to near of a wall.
+00444         CVector test= cur+dir*0.5;
+00445         float   norm= (test-prec).norm();
+00446         norm*=anglemax;
+00447         if(!snapToGround(test, norm, norm))
+00448         {
+00449                 cur= prec;
+00450                 return false;
+00451         }
+00452         else
+00453         {
+00454                 // Must test and snap the current position.
+00455                 norm= (cur-prec).norm();
+00456                 norm*=anglemax;
+00457                 if(!snapToGround(cur, norm, norm))
+00458                 {
+00459                         cur= prec;
+00460                         return false;
+00461                 }
+00462         }
+00463         return true;
+00464 }
+00465 
+00466 
+00467 // ***************************************************************************
+00468 void                    CMiniCol::getFaces(std::vector<CTriangle>       &triresult, const CAABBox &bbox)
+00469 {
+00470         triresult.clear();
+00471 
+00472         // Select.
+00473         _Grid.select(bbox.getMin(),bbox.getMax());
+00474 
+00475         // For each face, test if it is under pos, then test if height is correct.
+00476         CQuadGrid<CFace>::CIterator     iFace;
+00477         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
+00478         {
+00479                 CTriangle       &face= (*iFace).Face;
+00480 
+00481                 if(bbox.intersect(face.V0, face.V1, face.V2))
+00482                 {
+00483                         triresult.push_back(face);
+00484                 }
+00485         }
+00486 
+00487 }
+00488 
+00489 
+00490 } // NL3D
+
mini_col.cpp
