nel/src/3d/mini_col.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18
  19 #include "nel/3d/mini_col.h"
  20 #include "nel/misc/aabbox.h"
  21 #include "nel/3d/quad_grid.h"
  22
  23 using namespace NLMISC;
  24 using namespace std;
  25
  26 #ifdef DEBUG_NEW
  27 #define new DEBUG_NEW
  28 #endif
  29
  30 namespace NL3D
  31 {
  32
  33 static const    sint    QuadDepth= 10;
  34
  35
  36 // Element for grid lookup.
  37 static const sint       GridSize=512;
  38 static const float      GridEltSize=2;
  39
  40
  41 // ***************************************************************************
  42 CMiniCol::CMiniCol()
  43 {
  44         _RadMin= 100;
  45         _RadMax= 125;
  46         _Grid.create(GridSize, GridEltSize);
  47 }
  48
  49
  50 // ***************************************************************************
  51 void                    CMiniCol::addFaces(const std::vector<CTriangle> &faces, uint16 zoneId, uint16 patchId)
  52 {
  53         for(sint i=0;i<(sint)faces.size();i++)
  54         {
  55                 const CTriangle &f= faces[i];
  56                 CAABBox box;
  57                 box.setCenter(f.V0);
  58                 box.extend(f.V1);
  59                 box.extend(f.V2);
  60                 CFace   node;
  61                 node.Face= f;
  62                 node.Plane.make(f.V0, f.V1, f.V2);
  63                 node.ZoneId= zoneId;
  64                 node.PatchId=patchId;
  65                 _Grid.insert(box.getMin(), box.getMax(), node);
  66         }
  67 }
  68
  69
  70 // ***************************************************************************
  71 void                    CMiniCol::addLandscapePart(uint16 zoneId, uint16 patchId)
  72 {
  73         vector<CTriangle> faces;
  74         _Landscape->buildCollideFaces(zoneId, patchId, faces);
  75         addFaces(faces, zoneId, patchId);
  76 }
  77
  78
  79 // ***************************************************************************
  80 void                    CMiniCol::removeLandScapePart(uint16 zoneId, uint16 patchId, const CBSphere &sphere)
  81 {
  82         // Build the AAbox which englobe the bsphere of the patch.
  83         CAABBox         bb;
  84         bb.setCenter(sphere.Center);
  85         float   l= sphere.Radius;
  86         bb.setHalfSize(CVector(l,l,l));
  87
  88         // For optimisation, select only faces which are IN the bbox of the patch.
  89         _Grid.select(bb.getMin(), bb.getMax());
  90         CQuadGrid<CFace>::CIterator     iFace;
  91         for(iFace= _Grid.begin();iFace!=_Grid.end();)
  92         {
  93                 if((*iFace).isFromPatch(zoneId, patchId))
  94                         iFace= _Grid.erase(iFace);
  95                 else
  96                         iFace++;
  97         }
  98 }
  99
 100
 101 // ***************************************************************************
 102 void                    CMiniCol::init(CLandscape *land, float radMin, float radDelta)
 103 {
 104         _Landscape= land;
 105         _RadMin= radMin;
 106         _RadMax= radMin+radDelta;
 107 }
 108
 109
 110 // ***************************************************************************
 111 void                    CMiniCol::addZone(uint16 zoneId)
 112 {
 113         CZoneIdent      newZone;
 114
 115         // landscape must have been inited.
 116         nlassert(_Landscape);
 117         const CZone     *zone= _Landscape->getZone(zoneId);
 118         // zone must be loaded into landscape.
 119         nlassert(zone);
 120
 121         // Fill the newzone.
 122         newZone.ZoneId= zoneId;
 123         newZone.Sphere.Center= zone->getZoneBB().getCenter();
 124         newZone.Sphere.Radius= zone->getZoneBB().getRadius();
 125         newZone.Patchs.resize(zone->getNumPatchs());
 126         for(sint i=0;i<zone->getNumPatchs();i++)
 127         {
 128                 newZone.Patchs[i].Sphere= zone->getPatchBSphere(i);
 129         }
 130
 131         // Add it to the set (if not already done...).
 132         _Zones.insert(newZone);
 133 }
 134
 135
 136 // ***************************************************************************
 137 void                    CMiniCol::removeZone(uint16 zoneId)
 138 {
 139         CZoneIdent      delZone;
 140
 141
 142         // First, delete all patch from the grid.
 143         //=======================================
 144         // Fill the key part only.
 145         delZone.ZoneId= zoneId;
 146         // Find the zone (or quit).
 147         TZoneSet::iterator      itZone;
 148         itZone= _Zones.find(delZone);
 149         if(itZone==_Zones.end())
 150                 return;
 151
 152         CZoneIdent      &zone= const_cast<CZoneIdent&>(*itZone);
 153         for(sint i=0;i<(sint)zone.Patchs.size();i++)
 154         {
 155                 CPatchIdent     &pa= zone.Patchs[i];
 156                 if(pa.Inserted)
 157                 {
 158                         // Reject the patch.
 159                         removeLandScapePart(uint16(zone.ZoneId), uint16(i), pa.Sphere);
 160                         pa.Inserted= false;
 161                         zone.NPatchInserted--;
 162                 }
 163         }
 164
 165         // Then, delete it.
 166         //=================
 167         _Zones.erase(delZone);
 168
 169 }
 170
 171
 172 // ***************************************************************************
 173 void                    CMiniCol::setCenter(const CVector& center)
 174 {
 175         CBSphere        BMin(center, _RadMin), BMax(center, _RadMax);
 176
 177         // For all zones, test if must insert patchs..
 178         TZoneSet::iterator      itZone;
 179         for(itZone= _Zones.begin();itZone!=_Zones.end();itZone++)
 180         {
 181                 CZoneIdent      &zone= const_cast<CZoneIdent&>(*itZone);
 182
 183                 // Tests must be done in 2D...
 184                 BMin.Center.z= zone.Sphere.Center.z;
 185                 BMax.Center.z= zone.Sphere.Center.z;
 186
 187                 // Must test first if the zone is IN the area.
 188                 //=============================================
 189                 bool    zoneIn= false;
 190                 if(zone.NPatchInserted==0)
 191                 {
 192                         if(BMin.intersect(zone.Sphere))
 193                                 zoneIn= true;
 194                 }
 195                 else
 196                         zoneIn= true;
 197
 198                 // Then for all patchs, must test if the patch must be inserted, or rejected.
 199                 //=============================================
 200                 if(zoneIn)
 201                 {
 202                         for(sint i=0;i<(sint)zone.Patchs.size();i++)
 203                         {
 204                                 CPatchIdent     &pa= zone.Patchs[i];
 205
 206                                 // Tests must be done in 2D...
 207                                 BMin.Center.z= pa.Sphere.Center.z;
 208                                 BMax.Center.z= pa.Sphere.Center.z;
 209
 210                                 if(pa.Inserted)
 211                                 {
 212                                         // Reject the patch, if entirely OUT the max radius.
 213                                         if(!BMax.intersect(pa.Sphere))
 214                                         {
 215                                                 removeLandScapePart(uint16(zone.ZoneId), uint16(i), pa.Sphere);
 216                                                 pa.Inserted= false;
 217                                                 zone.NPatchInserted--;
 218                                         }
 219                                 }
 220                                 else
 221                                 {
 222                                         // Insert the pacth, if only partially IN the min radius.
 223                                         if(BMin.intersect(pa.Sphere))
 224                                         {
 225                                                 addLandscapePart(uint16(zone.ZoneId), uint16(i));
 226                                                 pa.Inserted= true;
 227                                                 zone.NPatchInserted++;
 228                                         }
 229                                 }
 230                         }
 231                 }
 232         }
 233 }
 234
 235
 236 // ***************************************************************************
 237 bool                    CMiniCol::snapToGround(CVector &pos, float hup, float hbot)
 238 {
 239         CVector b1,b2;
 240         bool    found=false;
 241         float   height=0.f;
 242
 243
 244         // Select quad nodes which contains pos.
 245         b1=b2=pos;
 246         b1.z-= hbot;
 247         b2.z+= hup;
 248         // Select.
 249         _Grid.select(b1,b2);
 250
 251         // For each face, test if it is under pos, then test if height is correct.
 252         CQuadGrid<CFace>::CIterator     iFace;
 253         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
 254         {
 255                 CTriangle       &pFace= (*iFace).Face;
 256                 CPlane          &pPlane= (*iFace).Plane;
 257                 // Order is important.
 258                 CVector         &p0= pFace.V0;
 259                 CVector         &p1= pFace.V1;
 260                 CVector         &p2= pFace.V2;
 261
 262                 // TOIMP: This is VERY SLOW!!! (hope that the quadtree will help, but it still very slow...).
 263
 264                 // Yoyo Debug, test, if the point may be IN the bbox.
 265                 /*CAABBox               bbFace;
 266                 bbFace.setCenter(p0);
 267                 bbFace.extend(p1);
 268                 bbFace.extend(p2);
 269                 CVector         bext=p0;
 270                 bext.z= maxof(p0.z, p1.z, p2.z)+hbot;
 271                 bbFace.extend(bext);
 272                 bext.z= minof(p0.z, p1.z, p2.z)-hup;
 273                 bbFace.extend(bext);
 274                 if(!bbFace.include(pos))
 275                         continue;*/
 276
 277                 // Test if the face enclose the pos in X/Y plane.
 278                 // NB: compute and using a BBox to do a rapid test is not a very good idea, since it will
 279                 // add an overhead which is NOT negligeable compared to the following test.
 280                 float           a,b,c;          // 2D cartesian coefficients of line in plane X/Y.
 281                 // Line p0-p1.
 282                 a= -(p1.y-p0.y);
 283                 b= (p1.x-p0.x);
 284                 c= -(p0.x*a + p0.y*b);
 285                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 286                 // Line p1-p2.
 287                 a= -(p2.y-p1.y);
 288                 b= (p2.x-p1.x);
 289                 c= -(p1.x*a + p1.y*b);
 290                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 291                 // Line p2-p0.
 292                 a= -(p0.y-p2.y);
 293                 b= (p0.x-p2.x);
 294                 c= -(p2.x*a + p2.y*b);
 295                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 296
 297
 298                 // Compute the possible height.
 299                 CVector         tmp;
 300                 // intersect the vertical line with the plane.
 301                 tmp= pPlane.intersect(pos, pos-CVector(0,0,100));
 302
 303                 /*
 304                 // CTriangle intersect() method.
 305                 CVector tmp;
 306                 if(pFace.intersect(b1, b2, tmp, pPlane))
 307                 */
 308                 {
 309                         float           h= tmp.z;
 310                         // Test if it would fit in the wanted field.
 311                         if(h>pos.z+hup) continue;
 312                         if(h<pos.z-hbot)        continue;
 313
 314                         // OK!!
 315                         if(!found)
 316                         {
 317                                 found=true;
 318                                 height=h;
 319                         }
 320                         else
 321                         {
 322                                 height= max(height,h);
 323                         }
 324                 }
 325         }
 326
 327         if(found)
 328                 pos.z= height;
 329
 330         return found;
 331 }
 332
 333
 334
 335 // ***************************************************************************
 336 bool                    CMiniCol::getGroundNormal(const CVector &pos, CVector &normal, float hup, float hbot)
 337 {
 338         CVector b1,b2;
 339         bool    found=false;
 340         float   height=0.0;
 341
 342
 343         // Select quad nodes which contains pos.
 344         b1=b2=pos;
 345         b1.z-= hbot;
 346         b2.z+= hup;
 347         // Select.
 348         _Grid.select(b1,b2);
 349
 350         // For each face, test if it is under pos, then test if height is correct.
 351         CQuadGrid<CFace>::CIterator     iFace;
 352         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
 353         {
 354                 CTriangle       &pFace= (*iFace).Face;
 355                 CPlane          &pPlane= (*iFace).Plane;
 356                 // Order is important.
 357                 CVector         &p0= pFace.V0;
 358                 CVector         &p1= pFace.V1;
 359                 CVector         &p2= pFace.V2;
 360
 361                 // TOIMP: This is VERY SLOW!!! (hope that the quadtree will help, but it still very slow...).
 362
 363                 // Yoyo Debug, test, if the point may be IN the bbox.
 364                 CAABBox         bbFace;
 365                 bbFace.setCenter(p0);
 366                 bbFace.extend(p1);
 367                 bbFace.extend(p2);
 368                 CVector         bext=p0;
 369                 bext.z= maxof(p0.z, p1.z, p2.z)+hbot;
 370                 bbFace.extend(bext);
 371                 bext.z= minof(p0.z, p1.z, p2.z)-hup;
 372                 bbFace.extend(bext);
 373                 if(!bbFace.include(pos))
 374                         continue;
 375
 376                 // Test if the face enclose the pos in X/Y plane.
 377                 // NB: compute and using a BBox to do a rapid test is not a very good idea, since it will
 378                 // add an overhead which is NOT negligeable compared to the following test.
 379                 float           a,b,c;          // 2D cartesian coefficients of line in plane X/Y.
 380                 // Line p0-p1.
 381                 a= -(p1.y-p0.y);
 382                 b= (p1.x-p0.x);
 383                 c= -(p0.x*a + p0.y*b);
 384                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 385                 // Line p1-p2.
 386                 a= -(p2.y-p1.y);
 387                 b= (p2.x-p1.x);
 388                 c= -(p1.x*a + p1.y*b);
 389                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 390                 // Line p2-p0.
 391                 a= -(p0.y-p2.y);
 392                 b= (p0.x-p2.x);
 393                 c= -(p2.x*a + p2.y*b);
 394                 if( (a*pos.x + b*pos.y + c) < 0)        continue;
 395
 396
 397                 // Compute the possible height.
 398                 CVector         tmp;
 399                 // intersect the vertical line with the plane.
 400                 tmp= pPlane.intersect(pos, pos-CVector(0,0,100));
 401                 float           h= tmp.z;
 402                 // Test if it would fit in the wanted field.
 403                 if(h>pos.z+hup) continue;
 404                 if(h<pos.z-hbot)        continue;
 405
 406                 // OK!!
 407                 if(!found)
 408                 {
 409                         found=true;
 410                         height=h;
 411                         normal= pPlane.getNormal();
 412                 }
 413                 else
 414                 {
 415                         if(h>height)
 416                         {
 417                                 normal= pPlane.getNormal();
 418                                 height= h;
 419                         }
 420                 }
 421         }
 422
 423         return found;
 424 }
 425
 426
 427 // ***************************************************************************
 428 bool                    CMiniCol::testMove(const CVector &prec, CVector &cur)
 429 {
 430         CVector dir= cur-prec;
 431         dir.normalize();
 432
 433         // Angle max.
 434         float   anglemax= 65;   // 65 degrees.
 435         anglemax= (float)tan( anglemax*Pi/180);
 436
 437         // Must not go to near of a wall.
 438         CVector test= cur+dir*0.5;
 439         float   norm= (test-prec).norm();
 440         norm*=anglemax;
 441         if(!snapToGround(test, norm, norm))
 442         {
 443                 cur= prec;
 444                 return false;
 445         }
 446         else
 447         {
 448                 // Must test and snap the current position.
 449                 norm= (cur-prec).norm();
 450                 norm*=anglemax;
 451                 if(!snapToGround(cur, norm, norm))
 452                 {
 453                         cur= prec;
 454                         return false;
 455                 }
 456         }
 457         return true;
 458 }
 459
 460
 461 // ***************************************************************************
 462 void                    CMiniCol::getFaces(std::vector<CTriangle>       &triresult, const CAABBox &bbox)
 463 {
 464         triresult.clear();
 465
 466         // Select.
 467         _Grid.select(bbox.getMin(),bbox.getMax());
 468
 469         // For each face, test if it is under pos, then test if height is correct.
 470         CQuadGrid<CFace>::CIterator     iFace;
 471         for(iFace= _Grid.begin();iFace!=_Grid.end();iFace++)
 472         {
 473                 CTriangle       &face= (*iFace).Face;
 474
 475                 if(bbox.intersect(face.V0, face.V1, face.V2))
 476                 {
 477                         triresult.push_back(face);
 478                 }
 479         }
 480
 481 }
 482
 483
 484 } // NL3D