navMesh.cpp

Public Functions

buildCallback(SceneObject * object, void * key)

DefineEngineFunction(getNavMeshEventManager , S32 , () , "@brief Get the <a href="/coding/class/classeventmanager/">EventManager</a> object <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1a2732ab74fa0237854c2ba0f75f88a624">for</a> all <a href="/coding/class/classnavmesh/">NavMesh</a> updates." )

DefineEngineFunction(NavMeshIgnore , void , (S32 objid, bool _ignore) , (0, true) , "@brief Flag this object as not generating <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> navmesh result." )

DefineEngineFunction(NavMeshUpdateAll , void , (S32 objid, bool remove) , (0, false) , "@brief Update all <a href="/coding/class/classnavmesh/">NavMesh</a> tiles that intersect the given object's world box." )

DefineEngineFunction(NavMeshUpdateAroundObject , void , (S32 objid, bool remove) , (0, false) , "@brief Update all <a href="/coding/class/classnavmesh/">NavMesh</a> tiles that intersect the given object's world box." )

DefineEngineFunction(NavMeshUpdateOne , void , (S32 meshid, S32 objid, bool remove) , (0, 0, false) , "@brief Update all tiles in <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> given <a href="/coding/class/classnavmesh/">NavMesh</a> that intersect the given object's world box." )

DefineEngineMethod(NavMesh , addLink , S32 , (Point3F from, Point3F to, U32 flags) , (0) , "Add <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> link <a href="/coding/file/cmdgram_8cpp/#cmdgram_8cpp_1a5bafda9519252aa2d0fd038153f77dca">to</a> this <a href="/coding/class/classnavmesh/">NavMesh</a> between two <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1aeab71244afb687f16d8c4f5ee9d6ef0e">points.\n\n</a>" "" )

DefineEngineMethod(NavMesh , build , bool , (bool background, bool save) , (true, false) , "@brief Create <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> Recast nav mesh." )

DefineEngineMethod(NavMesh , buildLinks , void , () , "@brief Build tiles of this mesh where there are unsynchronised links." )

DefineEngineMethod(NavMesh , buildTiles , void , (Box3F box) , "@brief Rebuild the tiles overlapped by the input box." )

DefineEngineMethod(NavMesh , cancelBuild , void , () , "@brief Cancel the current <a href="/coding/class/classnavmesh/">NavMesh</a> build." )

DefineEngineMethod(NavMesh , createCoverPoints , bool , () , "@brief Create cover points <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1a2732ab74fa0237854c2ba0f75f88a624">for</a> this NavMesh." )

DefineEngineMethod(NavMesh , deleteCoverPoints , void , () , "@brief Remove all cover points <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1a2732ab74fa0237854c2ba0f75f88a624">for</a> this NavMesh." )

DefineEngineMethod(NavMesh , deleteLink , void , (U32 id) , "Delete <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> given off-mesh link." )

DefineEngineMethod(NavMesh , deleteLinks , void , () , "Deletes all off-mesh links on this NavMesh." )

DefineEngineMethod(NavMesh , getLink , S32 , (Point3F pos) , "Get the off-mesh link closest <a href="/coding/file/cmdgram_8cpp/#cmdgram_8cpp_1a5bafda9519252aa2d0fd038153f77dca">to</a> <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> given world point." )

DefineEngineMethod(NavMesh , getLinkCount , S32 , () , "Return the number of links this mesh has." )

DefineEngineMethod(NavMesh , getLinkEnd , Point3F , (U32 id) , "Get the ending point of an off-mesh link." )

DefineEngineMethod(NavMesh , getLinkFlags , S32 , (U32 id) , "Get the flags set <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1a2732ab74fa0237854c2ba0f75f88a624">for</a> <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> particular off-mesh link." )

DefineEngineMethod(NavMesh , getLinkStart , Point3F , (U32 id) , "Get the starting point of an off-mesh link." )

DefineEngineMethod(NavMesh , load , bool , () , "@brief Load this <a href="/coding/class/classnavmesh/">NavMesh</a> from its file." )

DefineEngineMethod(NavMesh , save , void , () , "@brief Save this <a href="/coding/class/classnavmesh/">NavMesh</a> <a href="/coding/file/cmdgram_8cpp/#cmdgram_8cpp_1a5bafda9519252aa2d0fd038153f77dca">to</a> its file." )

DefineEngineMethod(NavMesh , setLinkFlags , void , (U32 id, U32 flags) , "Set the flags of <a href="/coding/file/pointer_8h/#pointer_8h_1aeeddce917cf130d62c370b8f216026dd">a</a> particular off-mesh link." )

IMPLEMENT_CO_NETOBJECT_V1(NavMesh )

ImplementEnumType(NavMeshWaterMethod , "The method used <a href="/coding/file/cmdgram_8cpp/#cmdgram_8cpp_1a5bafda9519252aa2d0fd038153f77dca">to</a> include water surfaces in the <a href="/coding/file/cmdscan_8cpp/#cmdscan_8cpp_1aeab71244afb687f16d8c4f5ee9d6ef0e">NavMesh.\n</a>" )

   1
   2//-----------------------------------------------------------------------------
   3// Copyright (c) 2014 Daniel Buckmaster
   4//
   5// Permission is hereby granted, free of charge, to any person obtaining a copy
   6// of this software and associated documentation files (the "Software"), to
   7// deal in the Software without restriction, including without limitation the
   8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   9// sell copies of the Software, and to permit persons to whom the Software is
  10// furnished to do so, subject to the following conditions:
  11//
  12// The above copyright notice and this permission notice shall be included in
  13// all copies or substantial portions of the Software.
  14//
  15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21// IN THE SOFTWARE.
  22//-----------------------------------------------------------------------------
  23
  24#include "navMesh.h"
  25#include "navContext.h"
  26#include <DetourDebugDraw.h>
  27#include <RecastDebugDraw.h>
  28
  29#include "math/mathUtils.h"
  30#include "math/mRandom.h"
  31#include "console/consoleTypes.h"
  32#include "console/engineAPI.h"
  33#include "console/typeValidators.h"
  34
  35#include "scene/sceneRenderState.h"
  36#include "gfx/gfxDrawUtil.h"
  37#include "renderInstance/renderPassManager.h"
  38#include "gfx/primBuilder.h"
  39
  40#include "core/stream/bitStream.h"
  41#include "math/mathIO.h"
  42
  43#include "core/fileio.h"
  44
  45extern bool gEditingMission;
  46
  47IMPLEMENT_CO_NETOBJECT_V1(NavMesh);
  48
  49const U32 NavMesh::mMaxVertsPerPoly = 3;
  50
  51SimObjectPtr<SimSet> NavMesh::smServerSet = NULL;
  52
  53ImplementEnumType(NavMeshWaterMethod,
  54   "The method used to include water surfaces in the NavMesh.\n")
  55   { NavMesh::Ignore,     "Ignore",     "Ignore all water surfaces.\n" },
  56   { NavMesh::Solid,      "Solid",      "Treat water surfaces as solid and walkable.\n" },
  57   { NavMesh::Impassable, "Impassable", "Treat water as an impassable obstacle.\n" },
  58EndImplementEnumType;
  59
  60SimSet *NavMesh::getServerSet()
  61{
  62   if(!smServerSet)
  63   {
  64      SimSet *set = NULL;
  65      if(Sim::findObject("ServerNavMeshSet", set))
  66         smServerSet = set;
  67      else
  68      {
  69         smServerSet = new SimSet();
  70         smServerSet->registerObject("ServerNavMeshSet");
  71         Sim::getRootGroup()->addObject(smServerSet);
  72      }
  73   }
  74   return smServerSet;
  75}
  76
  77SimObjectPtr<EventManager> NavMesh::smEventManager = NULL;
  78
  79EventManager *NavMesh::getEventManager()
  80{
  81   if(!smEventManager)
  82   {
  83      smEventManager = new EventManager();
  84      smEventManager->registerObject("NavEventManager");
  85      Sim::getRootGroup()->addObject(smEventManager);
  86      smEventManager->setMessageQueue("NavEventManagerQueue");
  87      smEventManager->registerEvent("NavMeshCreated");
  88      smEventManager->registerEvent("NavMeshRemoved");
  89      smEventManager->registerEvent("NavMeshStartUpdate");
  90      smEventManager->registerEvent("NavMeshUpdate");
  91      smEventManager->registerEvent("NavMeshTileUpdate");
  92      smEventManager->registerEvent("NavMeshUpdateBox");
  93      smEventManager->registerEvent("NavMeshObstacleAdded");
  94      smEventManager->registerEvent("NavMeshObstacleRemoved");
  95   }
  96   return smEventManager;
  97}
  98
  99DefineEngineFunction(getNavMeshEventManager, S32, (),,
 100   "@brief Get the EventManager object for all NavMesh updates.")
 101{
 102   return NavMesh::getEventManager()->getId();
 103}
 104
 105DefineEngineFunction(NavMeshUpdateAll, void, (S32 objid, bool remove), (0, false),
 106   "@brief Update all NavMesh tiles that intersect the given object's world box.")
 107{
 108   SceneObject *obj;
 109   if(!Sim::findObject(objid, obj))
 110      return;
 111   obj->mPathfindingIgnore = remove;
 112   SimSet *set = NavMesh::getServerSet();
 113   for(U32 i = 0; i < set->size(); i++)
 114   {
 115      NavMesh *m = dynamic_cast<NavMesh*>(set->at(i));
 116      if (m)
 117      {
 118         m->cancelBuild();
 119         m->buildTiles(obj->getWorldBox());
 120      }
 121   }
 122}
 123
 124DefineEngineFunction(NavMeshUpdateAroundObject, void, (S32 objid, bool remove), (0, false),
 125   "@brief Update all NavMesh tiles that intersect the given object's world box.")
 126{
 127   SceneObject *obj;
 128   if (!Sim::findObject(objid, obj))
 129      return;
 130   obj->mPathfindingIgnore = remove;
 131   SimSet *set = NavMesh::getServerSet();
 132   for (U32 i = 0; i < set->size(); i++)
 133   {
 134      NavMesh *m = dynamic_cast<NavMesh*>(set->at(i));
 135      if (m)
 136      {
 137         m->cancelBuild();
 138         m->buildTiles(obj->getWorldBox());
 139      }
 140   }
 141}
 142
 143
 144DefineEngineFunction(NavMeshIgnore, void, (S32 objid, bool _ignore), (0, true),
 145   "@brief Flag this object as not generating a navmesh result.")
 146{
 147   SceneObject *obj;
 148   if(!Sim::findObject(objid, obj))
 149      return;
 150
 151      obj->mPathfindingIgnore = _ignore;
 152}
 153
 154DefineEngineFunction(NavMeshUpdateOne, void, (S32 meshid, S32 objid, bool remove), (0, 0, false),
 155   "@brief Update all tiles in a given NavMesh that intersect the given object's world box.")
 156{
 157   NavMesh *mesh;
 158   SceneObject *obj;
 159   if(!Sim::findObject(meshid, mesh))
 160   {
 161      Con::errorf("NavMeshUpdateOne: cannot find NavMesh %d", meshid);
 162      return;
 163   }
 164   if(!Sim::findObject(objid, obj))
 165   {
 166      Con::errorf("NavMeshUpdateOne: cannot find SceneObject %d", objid);
 167      return;
 168   }
 169   if(remove)
 170      obj->disableCollision();
 171   mesh->buildTiles(obj->getWorldBox());
 172   if(remove)
 173      obj->enableCollision();
 174}
 175
 176NavMesh::NavMesh()
 177{
 178   mTypeMask |= StaticShapeObjectType | MarkerObjectType;
 179   mFileName = StringTable->EmptyString();
 180   mNetFlags.clear(Ghostable);
 181
 182   mSaveIntermediates = false;
 183   nm = NULL;
 184   ctx = NULL;
 185
 186   mWaterMethod = Ignore;
 187
 188   dMemset(&cfg, 0, sizeof(cfg));
 189   mCellSize = mCellHeight = 0.2f;
 190   mWalkableHeight = 2.0f;
 191   mWalkableClimb = 0.3f;
 192   mWalkableRadius = 0.5f;
 193   mWalkableSlope = 40.0f;
 194   mBorderSize = 1;
 195   mDetailSampleDist = 6.0f;
 196   mDetailSampleMaxError = 1.0f;
 197   mMaxEdgeLen = 12;
 198   mMaxSimplificationError = 1.3f;
 199   mMinRegionArea = 8;
 200   mMergeRegionArea = 20;
 201   mTileSize = 10.0f;
 202   mMaxPolysPerTile = 128;
 203
 204   mSmallCharacters = false;
 205   mRegularCharacters = true;
 206   mLargeCharacters = false;
 207   mVehicles = false;
 208
 209   mCoverSet = StringTable->EmptyString();
 210   mInnerCover = false;
 211   mCoverDist = 1.0f;
 212   mPeekDist = 0.7f;
 213
 214   mAlwaysRender = false;
 215
 216   mBuilding = false;
 217   mCurLinkID = 0;
 218}
 219
 220NavMesh::~NavMesh()
 221{
 222   dtFreeNavMesh(nm);
 223   nm = NULL;
 224   delete ctx;
 225   ctx = NULL;
 226}
 227
 228bool NavMesh::setProtectedDetailSampleDist(void *obj, const char *index, const char *data)
 229{
 230   F32 dist = dAtof(data);
 231   if(dist == 0.0f || dist >= 0.9f)
 232      return true;
 233   Con::errorf("NavMesh::detailSampleDist must be 0 or greater than 0.9!");
 234   return false;
 235}
 236
 237bool NavMesh::setProtectedAlwaysRender(void *obj, const char *index, const char *data)
 238{
 239   NavMesh *mesh = static_cast<NavMesh*>(obj);
 240   bool always = dAtob(data);
 241   if(always)
 242   {
 243      if(!gEditingMission)
 244         mesh->mNetFlags.set(Ghostable);
 245   }
 246   else
 247   {
 248      if(!gEditingMission)
 249         mesh->mNetFlags.clear(Ghostable);
 250   }
 251   mesh->mAlwaysRender = always;
 252   mesh->setMaskBits(LoadFlag);
 253   return true;
 254}
 255
 256FRangeValidator ValidCellSize(0.01f, 10.0f);
 257FRangeValidator ValidSlopeAngle(0.0f, 89.9f);
 258IRangeValidator PositiveInt(0, S32_MAX);
 259IRangeValidator NaturalNumber(1, S32_MAX);
 260FRangeValidator CornerAngle(0.0f, 90.0f);
 261
 262void NavMesh::initPersistFields()
 263{
 264   addGroup("NavMesh Options");
 265
 266   addField("fileName", TypeString, Offset(mFileName, NavMesh),
 267      "Name of the data file to store this navmesh in (relative to engine executable).");
 268
 269   addField("waterMethod", TYPEID<NavMeshWaterMethod>(), Offset(mWaterMethod, NavMesh),
 270      "The method to use to handle water surfaces.");
 271
 272   addFieldV("cellSize", TypeF32, Offset(mCellSize, NavMesh), &ValidCellSize,
 273      "Length/width of a voxel.");
 274   addFieldV("cellHeight", TypeF32, Offset(mCellHeight, NavMesh), &ValidCellSize,
 275      "Height of a voxel.");
 276   addFieldV("tileSize", TypeF32, Offset(mTileSize, NavMesh), &CommonValidators::PositiveNonZeroFloat,
 277      "The horizontal size of tiles.");
 278
 279   addFieldV("actorHeight", TypeF32, Offset(mWalkableHeight, NavMesh), &CommonValidators::PositiveFloat,
 280      "Height of an actor.");
 281   addFieldV("actorClimb", TypeF32, Offset(mWalkableClimb, NavMesh), &CommonValidators::PositiveFloat,
 282      "Maximum climbing height of an actor.");
 283   addFieldV("actorRadius", TypeF32, Offset(mWalkableRadius, NavMesh), &CommonValidators::PositiveFloat,
 284      "Radius of an actor.");
 285   addFieldV("walkableSlope", TypeF32, Offset(mWalkableSlope, NavMesh), &ValidSlopeAngle,
 286      "Maximum walkable slope in degrees.");
 287
 288   addField("smallCharacters", TypeBool, Offset(mSmallCharacters, NavMesh),
 289      "Is this NavMesh for smaller-than-usual characters?");
 290   addField("regularCharacters", TypeBool, Offset(mRegularCharacters, NavMesh),
 291      "Is this NavMesh for regular-sized characters?");
 292   addField("largeCharacters", TypeBool, Offset(mLargeCharacters, NavMesh),
 293      "Is this NavMesh for larger-than-usual characters?");
 294   addField("vehicles", TypeBool, Offset(mVehicles, NavMesh),
 295      "Is this NavMesh for characters driving vehicles?");
 296
 297   endGroup("NavMesh Options");
 298
 299   addGroup("NavMesh Annotations");
 300
 301   addField("coverGroup", TypeString, Offset(mCoverSet, NavMesh),
 302      "Name of the SimGroup to store cover points in.");
 303
 304   addField("innerCover", TypeBool, Offset(mInnerCover, NavMesh),
 305      "Add cover points everywhere, not just on corners?");
 306
 307   addField("coverDist", TypeF32, Offset(mCoverDist, NavMesh),
 308      "Distance from the edge of the NavMesh to search for cover.");
 309   addField("peekDist", TypeF32, Offset(mPeekDist, NavMesh),
 310      "Distance to the side of each cover point that peeking happens.");
 311
 312   endGroup("NavMesh Annotations");
 313
 314   addGroup("NavMesh Rendering");
 315
 316   addProtectedField("alwaysRender", TypeBool, Offset(mAlwaysRender, NavMesh),
 317      &setProtectedAlwaysRender, &defaultProtectedGetFn,
 318      "Display this NavMesh even outside the editor.");
 319
 320   endGroup("NavMesh Rendering");
 321
 322   addGroup("NavMesh Advanced Options");
 323
 324   addFieldV("borderSize", TypeS32, Offset(mBorderSize, NavMesh), &PositiveInt,
 325      "Size of the non-walkable border around the navigation mesh (in voxels).");
 326   addProtectedField("detailSampleDist", TypeF32, Offset(mDetailSampleDist, NavMesh),
 327      &setProtectedDetailSampleDist, &defaultProtectedGetFn,
 328      "Sets the sampling distance to use when generating the detail mesh.");
 329   addFieldV("detailSampleError", TypeF32, Offset(mDetailSampleMaxError, NavMesh), &CommonValidators::PositiveFloat,
 330      "The maximum distance the detail mesh surface should deviate from heightfield data.");
 331   addFieldV("maxEdgeLen", TypeS32, Offset(mDetailSampleDist, NavMesh), &PositiveInt,
 332      "The maximum allowed length for contour edges along the border of the mesh.");
 333   addFieldV("simplificationError", TypeF32, Offset(mMaxSimplificationError, NavMesh), &CommonValidators::PositiveFloat,
 334      "The maximum distance a simplfied contour's border edges should deviate from the original raw contour.");
 335   addFieldV("minRegionArea", TypeS32, Offset(mMinRegionArea, NavMesh), &PositiveInt,
 336      "The minimum number of cells allowed to form isolated island areas.");
 337   addFieldV("mergeRegionArea", TypeS32, Offset(mMergeRegionArea, NavMesh), &PositiveInt,
 338      "Any regions with a span count smaller than this value will, if possible, be merged with larger regions.");
 339   addFieldV("maxPolysPerTile", TypeS32, Offset(mMaxPolysPerTile, NavMesh), &NaturalNumber,
 340      "The maximum number of polygons allowed in a tile.");
 341
 342   endGroup("NavMesh Advanced Options");
 343
 344   Parent::initPersistFields();
 345}
 346
 347bool NavMesh::onAdd()
 348{
 349   if(!Parent::onAdd())
 350      return false;
 351
 352   mObjBox.set(Point3F(-0.5f, -0.5f, -0.5f),
 353               Point3F( 0.5f,  0.5f,  0.5f));
 354   resetWorldBox();
 355
 356   addToScene();
 357
 358   if(gEditingMission || mAlwaysRender)
 359   {
 360      mNetFlags.set(Ghostable);
 361      if(isClientObject())
 362         renderToDrawer();
 363   }
 364
 365   if(isServerObject())
 366   {
 367      getServerSet()->addObject(this);
 368      ctx = new NavContext();
 369      setProcessTick(true);
 370      if(getEventManager())
 371         getEventManager()->postEvent("NavMeshCreated", getIdString());
 372   }
 373
 374   load();
 375
 376   return true;
 377}
 378
 379void NavMesh::onRemove()
 380{
 381   if(getEventManager())
 382      getEventManager()->postEvent("NavMeshRemoved", getIdString());
 383
 384   removeFromScene();
 385
 386   Parent::onRemove();
 387}
 388
 389void NavMesh::setTransform(const MatrixF &mat)
 390{
 391   Parent::setTransform(mat);
 392}
 393
 394void NavMesh::setScale(const VectorF &scale)
 395{
 396   Parent::setScale(scale);
 397}
 398
 399S32 NavMesh::addLink(const Point3F &from, const Point3F &to, U32 flags)
 400{
 401   Point3F rcFrom = DTStoRC(from), rcTo = DTStoRC(to);
 402   mLinkVerts.push_back(rcFrom.x);
 403   mLinkVerts.push_back(rcFrom.y);
 404   mLinkVerts.push_back(rcFrom.z);
 405   mLinkVerts.push_back(rcTo.x);
 406   mLinkVerts.push_back(rcTo.y);
 407   mLinkVerts.push_back(rcTo.z);
 408   mLinksUnsynced.push_back(true);
 409   mLinkRads.push_back(mWalkableRadius);
 410   mLinkDirs.push_back(0);
 411   mLinkAreas.push_back(OffMeshArea);
 412   if (flags == 0) {
 413      Point3F dir = to - from;
 414      F32 drop = -dir.z;
 415      dir.z = 0;
 416      // If we drop more than we travel horizontally, we're a drop link.
 417      if(drop > dir.len())
 418         mLinkFlags.push_back(DropFlag);
 419      else
 420         mLinkFlags.push_back(JumpFlag);
 421   }
 422   mLinkIDs.push_back(1000 + mCurLinkID);
 423   mLinkSelectStates.push_back(Unselected);
 424   mDeleteLinks.push_back(false);
 425   mCurLinkID++;
 426   return mLinkIDs.size() - 1;
 427}
 428
 429DefineEngineMethod(NavMesh, addLink, S32, (Point3F from, Point3F to, U32 flags), (0),
 430   "Add a link to this NavMesh between two points.\n\n"
 431   "")
 432{
 433   return object->addLink(from, to, flags);
 434}
 435
 436S32 NavMesh::getLink(const Point3F &pos)
 437{
 438   for(U32 i = 0; i < mLinkIDs.size(); i++)
 439   {
 440      if(mDeleteLinks[i])
 441         continue;
 442      SphereF start(getLinkStart(i), mLinkRads[i]);
 443      SphereF end(getLinkEnd(i), mLinkRads[i]);
 444      if(start.isContained(pos) || end.isContained(pos))
 445         return i;
 446   }
 447   return -1;
 448}
 449
 450DefineEngineMethod(NavMesh, getLink, S32, (Point3F pos),,
 451   "Get the off-mesh link closest to a given world point.")
 452{
 453   return object->getLink(pos);
 454}
 455
 456S32 NavMesh::getLinkCount()
 457{
 458   return mLinkIDs.size();
 459}
 460
 461DefineEngineMethod(NavMesh, getLinkCount, S32, (),,
 462   "Return the number of links this mesh has.")
 463{
 464   return object->getLinkCount();
 465}
 466
 467LinkData NavMesh::getLinkFlags(U32 idx)
 468{
 469   if(idx < mLinkIDs.size())
 470   {
 471      return LinkData(mLinkFlags[idx]);
 472   }
 473   return LinkData();
 474}
 475
 476DefineEngineMethod(NavMesh, getLinkFlags, S32, (U32 id),,
 477   "Get the flags set for a particular off-mesh link.")
 478{
 479   return object->getLinkFlags(id).getFlags();
 480}
 481
 482void NavMesh::setLinkFlags(U32 idx, const LinkData &d)
 483{
 484   if(idx < mLinkIDs.size())
 485   {
 486      mLinkFlags[idx] = d.getFlags();
 487      mLinksUnsynced[idx] = true;
 488   }
 489}
 490
 491DefineEngineMethod(NavMesh, setLinkFlags, void, (U32 id, U32 flags),,
 492   "Set the flags of a particular off-mesh link.")
 493{
 494   LinkData d(flags);
 495   object->setLinkFlags(id, d);
 496}
 497
 498Point3F NavMesh::getLinkStart(U32 idx)
 499{
 500   return RCtoDTS(Point3F(
 501      mLinkVerts[idx*6],
 502      mLinkVerts[idx*6 + 1],
 503      mLinkVerts[idx*6 + 2]));
 504}
 505
 506DefineEngineMethod(NavMesh, getLinkStart, Point3F, (U32 id),,
 507   "Get the starting point of an off-mesh link.")
 508{
 509   return object->getLinkStart(id);
 510}
 511
 512Point3F NavMesh::getLinkEnd(U32 idx)
 513{
 514   return RCtoDTS(Point3F(
 515      mLinkVerts[idx*6 + 3],
 516      mLinkVerts[idx*6 + 4],
 517      mLinkVerts[idx*6 + 5]));
 518}
 519
 520DefineEngineMethod(NavMesh, getLinkEnd, Point3F, (U32 id),,
 521   "Get the ending point of an off-mesh link.")
 522{
 523   return object->getLinkEnd(id);
 524}
 525
 526void NavMesh::selectLink(U32 idx, bool select, bool hover)
 527{
 528   if(idx < mLinkIDs.size())
 529   {
 530      if(!select)
 531         mLinkSelectStates[idx] = Unselected;
 532      else
 533         mLinkSelectStates[idx] = hover ? Hovered : Selected;
 534   }
 535}
 536
 537void NavMesh::eraseLink(U32 i)
 538{
 539   mLinkVerts.erase(i*6, 6);
 540   mLinksUnsynced.erase(i);
 541   mLinkRads.erase(i);
 542   mLinkDirs.erase(i);
 543   mLinkAreas.erase(i);
 544   mLinkFlags.erase(i);
 545   mLinkIDs.erase(i);
 546   mLinkSelectStates.erase(i);
 547   mDeleteLinks.erase(i);
 548}
 549
 550void NavMesh::eraseLinks()
 551{
 552   mLinkVerts.clear();
 553   mLinksUnsynced.clear();
 554   mLinkRads.clear();
 555   mLinkDirs.clear();
 556   mLinkAreas.clear();
 557   mLinkFlags.clear();
 558   mLinkIDs.clear();
 559   mLinkSelectStates.clear();
 560   mDeleteLinks.clear();
 561}
 562
 563void NavMesh::setLinkCount(U32 c)
 564{
 565   eraseLinks();
 566   mLinkVerts.setSize(c * 6);
 567   mLinksUnsynced.setSize(c);
 568   mLinkRads.setSize(c);
 569   mLinkDirs.setSize(c);
 570   mLinkAreas.setSize(c);
 571   mLinkFlags.setSize(c);
 572   mLinkIDs.setSize(c);
 573   mLinkSelectStates.setSize(c);
 574   mDeleteLinks.setSize(c);
 575}
 576
 577void NavMesh::deleteLink(U32 idx)
 578{
 579   if(idx < mLinkIDs.size())
 580   {
 581      mDeleteLinks[idx] = true;
 582      if(mLinksUnsynced[idx])
 583         eraseLink(idx);
 584      else
 585         mLinksUnsynced[idx] = true;
 586   }
 587}
 588
 589DefineEngineMethod(NavMesh, deleteLink, void, (U32 id),,
 590   "Delete a given off-mesh link.")
 591{
 592   object->deleteLink(id);
 593}
 594
 595DefineEngineMethod(NavMesh, deleteLinks, void, (),,
 596   "Deletes all off-mesh links on this NavMesh.")
 597{
 598   //object->eraseLinks();
 599}
 600
 601bool NavMesh::build(bool background, bool saveIntermediates)
 602{
 603   if(mBuilding)
 604      cancelBuild();
 605   else
 606   {
 607      if(getEventManager())
 608         getEventManager()->postEvent("NavMeshStartUpdate", getIdString());
 609   }
 610
 611   mBuilding = true;
 612
 613   ctx->startTimer(RC_TIMER_TOTAL);
 614
 615   dtFreeNavMesh(nm);
 616   // Allocate a new navmesh.
 617   nm = dtAllocNavMesh();
 618   if(!nm)
 619   {
 620      Con::errorf("Could not allocate dtNavMesh for NavMesh %s", getIdString());
 621      return false;
 622   }
 623
 624   updateConfig();
 625
 626   // Build navmesh parameters from console members.
 627   dtNavMeshParams params;
 628   rcVcopy(params.orig, cfg.bmin);
 629   params.tileWidth = cfg.tileSize * mCellSize;
 630   params.tileHeight = cfg.tileSize * mCellSize;
 631   params.maxTiles = mCeil(getWorldBox().len_x() / params.tileWidth) * mCeil(getWorldBox().len_y() / params.tileHeight);
 632   params.maxPolys = mMaxPolysPerTile;
 633
 634   // Initialise our navmesh.
 635   if(dtStatusFailed(nm->init(&params)))
 636   {
 637      Con::errorf("Could not init dtNavMesh for NavMesh %s", getIdString());
 638      return false;
 639   }
 640
 641   // Update links to be deleted.
 642   for(U32 i = 0; i < mLinkIDs.size();)
 643   {
 644      if(mDeleteLinks[i])
 645         eraseLink(i);
 646      else
 647         i++;
 648   }
 649   mLinksUnsynced.fill(false);
 650   mCurLinkID = 0;
 651
 652   mSaveIntermediates = saveIntermediates;
 653
 654   updateTiles(true);
 655
 656   if(!background)
 657   {
 658      while(!mDirtyTiles.empty())
 659         buildNextTile();
 660   }
 661
 662   return true;
 663}
 664
 665DefineEngineMethod(NavMesh, build, bool, (bool background, bool save), (true, false),
 666   "@brief Create a Recast nav mesh.")
 667{
 668   return object->build(background, save);
 669}
 670
 671void NavMesh::cancelBuild()
 672{
 673   mDirtyTiles.clear();
 674   ctx->stopTimer(RC_TIMER_TOTAL);
 675   mBuilding = false;
 676}
 677
 678DefineEngineMethod(NavMesh, cancelBuild, void, (),,
 679   "@brief Cancel the current NavMesh build.")
 680{
 681   object->cancelBuild();
 682}
 683
 684void NavMesh::inspectPostApply()
 685{
 686   if(mBuilding)
 687      cancelBuild();
 688}
 689
 690void NavMesh::updateConfig()
 691{
 692   // Build rcConfig object from our console members.
 693   dMemset(&cfg, 0, sizeof(cfg));
 694   cfg.cs = mCellSize;
 695   cfg.ch = mCellHeight;
 696   Box3F box = DTStoRC(getWorldBox());
 697   rcVcopy(cfg.bmin, box.minExtents);
 698   rcVcopy(cfg.bmax, box.maxExtents);
 699   rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);
 700
 701   cfg.walkableHeight = mCeil(mWalkableHeight / mCellHeight);
 702   cfg.walkableClimb = mCeil(mWalkableClimb / mCellHeight);
 703   cfg.walkableRadius = mCeil(mWalkableRadius / mCellSize);
 704   cfg.walkableSlopeAngle = mWalkableSlope;
 705   cfg.borderSize = cfg.walkableRadius + 3;
 706
 707   cfg.detailSampleDist = mDetailSampleDist;
 708   cfg.detailSampleMaxError = mDetailSampleMaxError;
 709   cfg.maxEdgeLen = mMaxEdgeLen;
 710   cfg.maxSimplificationError = mMaxSimplificationError;
 711   cfg.maxVertsPerPoly = mMaxVertsPerPoly;
 712   cfg.minRegionArea = mMinRegionArea;
 713   cfg.mergeRegionArea = mMergeRegionArea;
 714   cfg.tileSize = mTileSize / cfg.cs;
 715}
 716
 717S32 NavMesh::getTile(const Point3F& pos)
 718{
 719   if(mBuilding)
 720      return -1;
 721   for(U32 i = 0; i < mTiles.size(); i++)
 722   {
 723      if(mTiles[i].box.isContained(pos))
 724         return i;
 725   }
 726   return -1;
 727}
 728
 729Box3F NavMesh::getTileBox(U32 id)
 730{
 731   if(mBuilding || id >= mTiles.size())
 732      return Box3F::Invalid;
 733   return mTiles[id].box;
 734}
 735
 736void NavMesh::updateTiles(bool dirty)
 737{
 738   PROFILE_SCOPE(NavMesh_updateTiles);
 739   if(!isProperlyAdded())
 740      return;
 741
 742   mTiles.clear();
 743   mTileData.clear();
 744   mDirtyTiles.clear();
 745
 746   const Box3F &box = DTStoRC(getWorldBox());
 747   if(box.isEmpty())
 748      return;
 749
 750   updateConfig();
 751
 752   // Calculate tile dimensions.
 753   const U32 ts = cfg.tileSize;
 754   const U32 tw = (cfg.width  + ts-1) / ts;
 755   const U32 th = (cfg.height + ts-1) / ts;
 756   const F32 tcs = cfg.tileSize * cfg.cs;
 757
 758   // Iterate over tiles.
 759   F32 tileBmin[3], tileBmax[3];
 760   for(U32 y = 0; y < th; ++y)
 761   {
 762      for(U32 x = 0; x < tw; ++x)
 763      {
 764         tileBmin[0] = cfg.bmin[0] + x*tcs;
 765         tileBmin[1] = cfg.bmin[1];
 766         tileBmin[2] = cfg.bmin[2] + y*tcs;
 767
 768         tileBmax[0] = cfg.bmin[0] + (x+1)*tcs;
 769         tileBmax[1] = cfg.bmax[1];
 770         tileBmax[2] = cfg.bmin[2] + (y+1)*tcs;
 771
 772         mTiles.push_back(
 773            Tile(RCtoDTS(tileBmin, tileBmax),
 774                  x, y,
 775                  tileBmin, tileBmax));
 776
 777         if(dirty)
 778            mDirtyTiles.push_back_unique(mTiles.size() - 1);
 779
 780         if(mSaveIntermediates)
 781            mTileData.increment();
 782      }
 783   }
 784}
 785
 786void NavMesh::processTick(const Move *move)
 787{
 788   buildNextTile();
 789}
 790
 791void NavMesh::buildNextTile()
 792{
 793   PROFILE_SCOPE(NavMesh_buildNextTile);
 794   if(!mDirtyTiles.empty())
 795   {
 796      // Pop a single dirty tile and process it.
 797      U32 i = mDirtyTiles.front();
 798      mDirtyTiles.pop_front();
 799      const Tile &tile = mTiles[i];
 800      // Intermediate data for tile build.
 801      TileData tempdata;
 802      TileData &tdata = mSaveIntermediates ? mTileData[i] : tempdata;
 803      
 804      // Remove any previous data.
 805      nm->removeTile(nm->getTileRefAt(tile.x, tile.y, 0), 0, 0);
 806
 807      // Generate navmesh for this tile.
 808      U32 dataSize = 0;
 809      unsigned char* data = buildTileData(tile, tdata, dataSize);
 810      if(data)
 811      {
 812         // Add new data (navmesh owns and deletes the data).
 813         dtStatus status = nm->addTile(data, dataSize, DT_TILE_FREE_DATA, 0, 0);
 814         int success = 1;
 815         if(dtStatusFailed(status))
 816         {
 817            success = 0;
 818            dtFree(data);
 819         }
 820         if(getEventManager())
 821         {
 822            String str = String::ToString("%d %d %d (%d, %d) %d %.3f %s",
 823               getId(),
 824               i, mTiles.size(),
 825               tile.x, tile.y,
 826               success,
 827               ctx->getAccumulatedTime(RC_TIMER_TOTAL) / 1000.0f,
 828               castConsoleTypeToString(tile.box));
 829            getEventManager()->postEvent("NavMeshTileUpdate", str.c_str());
 830            setMaskBits(LoadFlag);
 831         }
 832      }
 833      // Did we just build the last tile?
 834      if(mDirtyTiles.empty())
 835      {
 836         ctx->stopTimer(RC_TIMER_TOTAL);
 837         if(getEventManager())
 838         {
 839            String str = String::ToString("%d", getId());
 840            getEventManager()->postEvent("NavMeshUpdate", str.c_str());
 841            setMaskBits(LoadFlag);
 842         }
 843         mBuilding = false;
 844      }
 845   }
 846}
 847
 848static void buildCallback(SceneObject* object,void *key)
 849{
 850   SceneContainer::CallbackInfo* info = reinterpret_cast<SceneContainer::CallbackInfo*>(key);
 851   if (!object->mPathfindingIgnore)
 852   object->buildPolyList(info->context,info->polyList,info->boundingBox,info->boundingSphere);
 853}
 854
 855unsigned char *NavMesh::buildTileData(const Tile &tile, TileData &data, U32 &dataSize)
 856{
 857   // Push out tile boundaries a bit.
 858   F32 tileBmin[3], tileBmax[3];
 859   rcVcopy(tileBmin, tile.bmin);
 860   rcVcopy(tileBmax, tile.bmax);
 861   tileBmin[0] -= cfg.borderSize * cfg.cs;
 862   tileBmin[2] -= cfg.borderSize * cfg.cs;
 863   tileBmax[0] += cfg.borderSize * cfg.cs;
 864   tileBmax[2] += cfg.borderSize * cfg.cs;
 865
 866   // Parse objects from level into RC-compatible format.
 867   Box3F box = RCtoDTS(tileBmin, tileBmax);
 868   SceneContainer::CallbackInfo info;
 869   info.context = PLC_Navigation;
 870   info.boundingBox = box;
 871   data.geom.clear();
 872   info.polyList = &data.geom;
 873   info.key = this;
 874   getContainer()->findObjects(box, StaticObjectType | DynamicShapeObjectType, buildCallback, &info);
 875
 876   // Parse water objects into the same list, but remember how much geometry was /not/ water.
 877   U32 nonWaterVertCount = data.geom.getVertCount();
 878   U32 nonWaterTriCount = data.geom.getTriCount();
 879   if(mWaterMethod != Ignore)
 880   {
 881      getContainer()->findObjects(box, WaterObjectType, buildCallback, &info);
 882   }
 883
 884   // Check for no geometry.
 885   if (!data.geom.getVertCount())
 886   {
 887      data.geom.clear();
 888      return NULL;
 889   }
 890
 891   // Figure out voxel dimensions of this tile.
 892   U32 width = 0, height = 0;
 893   width = cfg.tileSize + cfg.borderSize * 2;
 894   height = cfg.tileSize + cfg.borderSize * 2;
 895
 896   // Create a heightfield to voxelise our input geometry.
 897   data.hf = rcAllocHeightfield();
 898   if(!data.hf)
 899   {
 900      Con::errorf("Out of memory (rcHeightField) for NavMesh %s", getIdString());
 901      return NULL;
 902   }
 903   if(!rcCreateHeightfield(ctx, *data.hf, width, height, tileBmin, tileBmax, cfg.cs, cfg.ch))
 904   {
 905      Con::errorf("Could not generate rcHeightField for NavMesh %s", getIdString());
 906      return NULL;
 907   }
 908
 909   unsigned char *areas = new unsigned char[data.geom.getTriCount()];
 910
 911   dMemset(areas, 0, data.geom.getTriCount() * sizeof(unsigned char));
 912
 913   // Mark walkable triangles with the appropriate area flags, and rasterize.
 914   if(mWaterMethod == Solid)
 915   {
 916      // Treat water as solid: i.e. mark areas as walkable based on angle.
 917      rcMarkWalkableTriangles(ctx, cfg.walkableSlopeAngle,
 918         data.geom.getVerts(), data.geom.getVertCount(),
 919         data.geom.getTris(), data.geom.getTriCount(), areas);
 920   }
 921   else
 922   {
 923      // Treat water as impassable: leave all area flags 0.
 924      rcMarkWalkableTriangles(ctx, cfg.walkableSlopeAngle,
 925         data.geom.getVerts(), nonWaterVertCount,
 926         data.geom.getTris(), nonWaterTriCount, areas);
 927   }
 928   rcRasterizeTriangles(ctx,
 929      data.geom.getVerts(), data.geom.getVertCount(),
 930      data.geom.getTris(), areas, data.geom.getTriCount(),
 931      *data.hf, cfg.walkableClimb);
 932
 933   delete[] areas;
 934
 935   // Filter out areas with low ceilings and other stuff.
 936   rcFilterLowHangingWalkableObstacles(ctx, cfg.walkableClimb, *data.hf);
 937   rcFilterLedgeSpans(ctx, cfg.walkableHeight, cfg.walkableClimb, *data.hf);
 938   rcFilterWalkableLowHeightSpans(ctx, cfg.walkableHeight, *data.hf);
 939
 940   data.chf = rcAllocCompactHeightfield();
 941   if(!data.chf)
 942   {
 943      Con::errorf("Out of memory (rcCompactHeightField) for NavMesh %s", getIdString());
 944      return NULL;
 945   }
 946   if(!rcBuildCompactHeightfield(ctx, cfg.walkableHeight, cfg.walkableClimb, *data.hf, *data.chf))
 947   {
 948      Con::errorf("Could not generate rcCompactHeightField for NavMesh %s", getIdString());
 949      return NULL;
 950   }
 951   if(!rcErodeWalkableArea(ctx, cfg.walkableRadius, *data.chf))
 952   {
 953      Con::errorf("Could not erode walkable area for NavMesh %s", getIdString());
 954      return NULL;
 955   }
 956
 957   //--------------------------
 958   // Todo: mark areas here.
 959   //const ConvexVolume* vols = m_geom->getConvexVolumes();
 960   //for (int i  = 0; i < m_geom->getConvexVolumeCount(); ++i)
 961      //rcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned char)vols[i].area, *m_chf);
 962   //--------------------------
 963
 964   if(false)
 965   {
 966      if(!rcBuildRegionsMonotone(ctx, *data.chf, cfg.borderSize, cfg.minRegionArea, cfg.mergeRegionArea))
 967      {
 968         Con::errorf("Could not build regions for NavMesh %s", getIdString());
 969         return NULL;
 970      }
 971   }
 972   else
 973   {
 974      if(!rcBuildDistanceField(ctx, *data.chf))
 975      {
 976         Con::errorf("Could not build distance field for NavMesh %s", getIdString());
 977         return NULL;
 978      }
 979      if(!rcBuildRegions(ctx, *data.chf, cfg.borderSize, cfg.minRegionArea, cfg.mergeRegionArea))
 980      {
 981         Con::errorf("Could not build regions for NavMesh %s", getIdString());
 982         return NULL;
 983      }
 984   }
 985
 986   data.cs = rcAllocContourSet();
 987   if(!data.cs)
 988   {
 989      Con::errorf("Out of memory (rcContourSet) for NavMesh %s", getIdString());
 990      return NULL;
 991   }
 992   if(!rcBuildContours(ctx, *data.chf, cfg.maxSimplificationError, cfg.maxEdgeLen, *data.cs))
 993   {
 994      Con::errorf("Could not construct rcContourSet for NavMesh %s", getIdString());
 995      return NULL;
 996   }
 997   if(data.cs->nconts <= 0)
 998   {
 999      Con::errorf("No contours in rcContourSet for NavMesh %s", getIdString());
1000      return NULL;
1001   }
1002
1003   data.pm = rcAllocPolyMesh();
1004   if(!data.pm)
1005   {
1006      Con::errorf("Out of memory (rcPolyMesh) for NavMesh %s", getIdString());
1007      return NULL;
1008   }
1009   if(!rcBuildPolyMesh(ctx, *data.cs, cfg.maxVertsPerPoly, *data.pm))
1010   {
1011      Con::errorf("Could not construct rcPolyMesh for NavMesh %s", getIdString());
1012      return NULL;
1013   }
1014
1015   data.pmd = rcAllocPolyMeshDetail();
1016   if(!data.pmd)
1017   {
1018      Con::errorf("Out of memory (rcPolyMeshDetail) for NavMesh %s", getIdString());
1019      return NULL;
1020   }
1021   if(!rcBuildPolyMeshDetail(ctx, *data.pm, *data.chf, cfg.detailSampleDist, cfg.detailSampleMaxError, *data.pmd))
1022   {
1023      Con::errorf("Could not construct rcPolyMeshDetail for NavMesh %s", getIdString());
1024      return NULL;
1025   }
1026
1027   if(data.pm->nverts >= 0xffff)
1028   {
1029      Con::errorf("Too many vertices in rcPolyMesh for NavMesh %s", getIdString());
1030      return NULL;
1031   }
1032   for(U32 i = 0; i < data.pm->npolys; i++)
1033   {
1034      if(data.pm->areas[i] == RC_WALKABLE_AREA)
1035         data.pm->areas[i] = GroundArea;
1036
1037      if(data.pm->areas[i] == GroundArea)
1038         data.pm->flags[i] |= WalkFlag;
1039      if(data.pm->areas[i] == WaterArea)
1040         data.pm->flags[i] |= SwimFlag;
1041   }
1042
1043   unsigned char* navData = 0;
1044   int navDataSize = 0;
1045
1046   dtNavMeshCreateParams params;
1047   dMemset(&params, 0, sizeof(params));
1048
1049   params.verts = data.pm->verts;
1050   params.vertCount = data.pm->nverts;
1051   params.polys = data.pm->polys;
1052   params.polyAreas = data.pm->areas;
1053   params.polyFlags = data.pm->flags;
1054   params.polyCount = data.pm->npolys;
1055   params.nvp = data.pm->nvp;
1056
1057   params.detailMeshes = data.pmd->meshes;
1058   params.detailVerts = data.pmd->verts;
1059   params.detailVertsCount = data.pmd->nverts;
1060   params.detailTris = data.pmd->tris;
1061   params.detailTriCount = data.pmd->ntris;
1062
1063   params.offMeshConVerts = mLinkVerts.address();
1064   params.offMeshConRad = mLinkRads.address();
1065   params.offMeshConDir = mLinkDirs.address();
1066   params.offMeshConAreas = mLinkAreas.address();
1067   params.offMeshConFlags = mLinkFlags.address();
1068   params.offMeshConUserID = mLinkIDs.address();
1069   params.offMeshConCount = mLinkIDs.size();
1070
1071   params.walkableHeight = mWalkableHeight;
1072   params.walkableRadius = mWalkableRadius;
1073   params.walkableClimb = mWalkableClimb;
1074   params.tileX = tile.x;
1075   params.tileY = tile.y;
1076   params.tileLayer = 0;
1077   rcVcopy(params.bmin, data.pm->bmin);
1078   rcVcopy(params.bmax, data.pm->bmax);
1079   params.cs = cfg.cs;
1080   params.ch = cfg.ch;
1081   params.buildBvTree = true;
1082
1083   if(!dtCreateNavMeshData(&params, &navData, &navDataSize))
1084   {
1085      Con::errorf("Could not create dtNavMeshData for tile (%d, %d) of NavMesh %s",
1086         tile.x, tile.y, getIdString());
1087      return NULL;
1088   }
1089
1090   dataSize = navDataSize;
1091
1092   return navData;
1093}
1094
1095/// This method should never be called in a separate thread to the rendering
1096/// or pathfinding logic. It directly replaces data in the dtNavMesh for
1097/// this NavMesh object.
1098void NavMesh::buildTiles(const Box3F &box)
1099{
1100   PROFILE_SCOPE(NavMesh_buildTiles);
1101   // Make sure we've already built or loaded.
1102   if(!nm)
1103      return;
1104   // Iterate over tiles.
1105   for(U32 i = 0; i < mTiles.size(); i++)
1106   {
1107      const Tile &tile = mTiles[i];
1108      // Check tile box.
1109      if(!tile.box.isOverlapped(box))
1110         continue;
1111      // Mark as dirty.
1112      mDirtyTiles.push_back_unique(i);
1113   }
1114   if(mDirtyTiles.size())
1115      ctx->startTimer(RC_TIMER_TOTAL);
1116}
1117
1118DefineEngineMethod(NavMesh, buildTiles, void, (Box3F box),,
1119   "@brief Rebuild the tiles overlapped by the input box.")
1120{
1121   return object->buildTiles(box);
1122}
1123
1124void NavMesh::buildTile(const U32 &tile)
1125{
1126   PROFILE_SCOPE(NavMesh_buildTile);
1127   if(tile < mTiles.size())
1128   {
1129      mDirtyTiles.push_back_unique(tile);
1130      ctx->startTimer(RC_TIMER_TOTAL);
1131   }
1132}
1133
1134void NavMesh::buildLinks()
1135{
1136   // Make sure we've already built or loaded.
1137   if(!nm)
1138      return;
1139   // Iterate over tiles.
1140   for(U32 i = 0; i < mTiles.size(); i++)
1141   {
1142      const Tile &tile = mTiles[i];
1143      // Iterate over links
1144      for(U32 j = 0; j < mLinkIDs.size(); j++)
1145      {
1146         if (mLinksUnsynced[j])
1147         {
1148         if(tile.box.isContained(getLinkStart(j)) ||
1149               tile.box.isContained(getLinkEnd(j)))
1150         {
1151            // Mark tile for build.
1152            mDirtyTiles.push_back_unique(i);
1153            // Delete link if necessary
1154            if(mDeleteLinks[j])
1155            {
1156               eraseLink(j);
1157               j--;
1158            }
1159            else
1160               mLinksUnsynced[j] = false;
1161         }
1162      }
1163   }
1164   }
1165   if(mDirtyTiles.size())
1166      ctx->startTimer(RC_TIMER_TOTAL);
1167}
1168
1169DefineEngineMethod(NavMesh, buildLinks, void, (),,
1170   "@brief Build tiles of this mesh where there are unsynchronised links.")
1171{
1172   object->buildLinks();
1173}
1174
1175void NavMesh::deleteCoverPoints()
1176{
1177   SimSet *set = NULL;
1178   if(Sim::findObject(mCoverSet, set))
1179      set->deleteAllObjects();
1180}
1181
1182DefineEngineMethod(NavMesh, deleteCoverPoints, void, (),,
1183   "@brief Remove all cover points for this NavMesh.")
1184{
1185   object->deleteCoverPoints();
1186}
1187
1188bool NavMesh::createCoverPoints()
1189{
1190   if(!nm || !isServerObject())
1191      return false;
1192
1193   SimSet *set = NULL;
1194   if(Sim::findObject(mCoverSet, set))
1195   {
1196      set->deleteAllObjects();
1197   }
1198   else
1199   {
1200      set = new SimGroup();
1201      if(set->registerObject(mCoverSet))
1202      {
1203         getGroup()->addObject(set);
1204      }
1205      else
1206      {
1207         delete set;
1208         set = getGroup();
1209      }
1210   }
1211
1212   dtNavMeshQuery *query = dtAllocNavMeshQuery();
1213   if(!query || dtStatusFailed(query->init(nm, 1)))
1214      return false;
1215
1216   dtQueryFilter f;
1217
1218   // Iterate over all polys in our navmesh.
1219   const int MAX_SEGS = 6;
1220   for(U32 i = 0; i < nm->getMaxTiles(); ++i)
1221   {
1222      const dtMeshTile* tile = ((const dtNavMesh*)nm)->getTile(i);
1223      if(!tile->header) continue;
1224      const dtPolyRef base = nm->getPolyRefBase(tile);
1225      for(U32 j = 0; j < tile->header->polyCount; ++j)
1226      {
1227         const dtPolyRef ref = base | j;
1228         float segs[MAX_SEGS*6];
1229         int nsegs = 0;
1230         query->getPolyWallSegments(ref, &f, segs, NULL, &nsegs, MAX_SEGS);
1231         for(int segIDx = 0; segIDx < nsegs; ++segIDx)
1232         {
1233            const float* sa = &segs[segIDx *6];
1234            const float* sb = &segs[segIDx *6+3];
1235            Point3F a = RCtoDTS(sa), b = RCtoDTS(sb);
1236            F32 len = (b - a).len();
1237            if(len < mWalkableRadius * 2)
1238               continue;
1239            Point3F edge = b - a;
1240            edge.normalize();
1241            // Number of points to try placing - for now, one at each end.
1242            U32 pointCount = (len > mWalkableRadius * 4) ? 2 : 1;
1243            for(U32 pointIDx = 0; pointIDx < pointCount; pointIDx++)
1244            {
1245               MatrixF mat;
1246               Point3F pos;
1247               // If we're only placing one point, put it in the middle.
1248               if(pointCount == 1)
1249                  pos = a + edge * len / 2;
1250               // Otherwise, stand off from edge ends.
1251               else
1252               {
1253                  if(pointIDx % 2)
1254                     pos = a + edge * (pointIDx /2+1) * mWalkableRadius;
1255                  else
1256                     pos = b - edge * (pointIDx /2+1) * mWalkableRadius;
1257               }
1258               CoverPointData data;
1259               if(testEdgeCover(pos, edge, data))
1260               {
1261                  CoverPoint *m = new CoverPoint();
1262                  if(!m->registerObject())
1263                     delete m;
1264                  else
1265                  {
1266                     m->setTransform(data.trans);
1267                     m->setSize(data.size);
1268                     m->setPeek(data.peek[0], data.peek[1], data.peek[2]);
1269                     if(set)
1270                        set->addObject(m);
1271                  }
1272               }
1273            }
1274         }
1275      }
1276   }
1277   return true;
1278}
1279
1280DefineEngineMethod(NavMesh, createCoverPoints, bool, (),,
1281   "@brief Create cover points for this NavMesh.")
1282{
1283   return object->createCoverPoints();
1284}
1285
1286bool NavMesh::testEdgeCover(const Point3F &pos, const VectorF &dir, CoverPointData &data)
1287{
1288   data.peek[0] = data.peek[1] = data.peek[2] = false;
1289   // Get the edge normal.
1290   Point3F norm;
1291   mCross(dir, Point3F(0, 0, 1), &norm);
1292   RayInfo ray;
1293   U32 hits = 0;
1294   for(U32 j = 0; j < CoverPoint::NumSizes; j++)
1295   {
1296      Point3F test = pos + Point3F(0.0f, 0.0f, mWalkableHeight * j / CoverPoint::NumSizes);
1297      if(getContainer()->castRay(test, test + norm * mCoverDist, StaticObjectType, &ray))
1298      {
1299         // Test peeking.
1300         Point3F left = test + dir * mPeekDist;
1301         data.peek[0] = !getContainer()->castRay(test, left, StaticObjectType, &ray)
1302            && !getContainer()->castRay(left, left + norm * mCoverDist, StaticObjectType, &ray);
1303
1304         Point3F right = test - dir * mPeekDist;
1305         data.peek[1] = !getContainer()->castRay(test, right, StaticObjectType, &ray)
1306            && !getContainer()->castRay(right, right + norm * mCoverDist, StaticObjectType, &ray);
1307
1308         Point3F over = test + Point3F(0, 0, 1) * 0.2f;
1309         data.peek[2] = !getContainer()->castRay(test, over, StaticObjectType, &ray)
1310            && !getContainer()->castRay(over, over + norm * mCoverDist, StaticObjectType, &ray);
1311
1312         if(mInnerCover || data.peek[0] || data.peek[1] || data.peek[2])
1313            hits++;
1314         // If we couldn't peek here, we may be able to peek further up.
1315      }
1316      else
1317         // No cover at this height - break off.
1318         break;
1319   }
1320   if(hits > 0)
1321   {
1322      data.size = (CoverPoint::Size)(hits - 1);
1323      data.trans = MathUtils::createOrientFromDir(norm);
1324      data.trans.setPosition(pos);
1325   }
1326   return hits > 0;
1327}
1328
1329void NavMesh::renderToDrawer()
1330{
1331   mDbgDraw.clear();
1332   // Recast debug draw
1333   NetObject *no = getServerObject();
1334   if(no)
1335   {
1336      NavMesh *n = static_cast<NavMesh*>(no);
1337
1338      if(n->nm)
1339      {
1340         mDbgDraw.beginGroup(0);
1341         duDebugDrawNavMesh       (&mDbgDraw, *n->nm, 0);
1342       mDbgDraw.beginGroup(1);
1343         duDebugDrawNavMeshPortals(&mDbgDraw, *n->nm);
1344       mDbgDraw.beginGroup(2);
1345         duDebugDrawNavMeshBVTree (&mDbgDraw, *n->nm);
1346      }
1347   }
1348}
1349
1350void NavMesh::prepRenderImage(SceneRenderState *state)
1351{
1352   ObjectRenderInst *ri = state->getRenderPass()->allocInst<ObjectRenderInst>();
1353   ri->renderDelegate.bind(this, &NavMesh::render);
1354   ri->type = RenderPassManager::RIT_Object;
1355   ri->translucentSort = true;
1356   ri->defaultKey = 1;
1357   state->getRenderPass()->addInst(ri);
1358}
1359
1360void NavMesh::render(ObjectRenderInst *ri, SceneRenderState *state, BaseMatInstance *overrideMat)
1361{
1362   if(overrideMat)
1363      return;
1364
1365   if(state->isReflectPass())
1366      return;
1367
1368   PROFILE_SCOPE(NavMesh_Render);
1369   
1370   // Recast debug draw
1371   NetObject *no = getServerObject();
1372   if(no)
1373   {
1374      NavMesh *n = static_cast<NavMesh*>(no);
1375
1376      if(n->isSelected())
1377      {
1378         GFXDrawUtil *drawer = GFX->getDrawUtil();
1379
1380         GFXStateBlockDesc desc;
1381         desc.setZReadWrite(true, false);
1382         desc.setBlend(true);
1383         desc.setCullMode(GFXCullNone);
1384
1385         drawer->drawCube(desc, getWorldBox(), n->mBuilding
1386            ? ColorI(255, 0, 0, 80)
1387            : ColorI(136, 228, 255, 45));
1388         desc.setFillModeWireframe();
1389         drawer->drawCube(desc, getWorldBox(), ColorI::BLACK);
1390      }
1391
1392      if(n->mBuilding)
1393      {
1394         int alpha = 80;
1395         if(!n->isSelected() || !Con::getBoolVariable("$Nav::EditorOpen"))
1396            alpha = 20;
1397       mDbgDraw.overrideColor(duRGBA(255, 0, 0, alpha));
1398      }
1399      else
1400      {
1401        mDbgDraw.cancelOverride();
1402      }
1403      
1404      if((!gEditingMission && n->mAlwaysRender) || (gEditingMission && Con::getBoolVariable("$Nav::Editor::renderMesh", 1))) mDbgDraw.renderGroup(0);
1405      if(Con::getBoolVariable("$Nav::Editor::renderPortals")) mDbgDraw.renderGroup(1);
1406      if(Con::getBoolVariable("$Nav::Editor::renderBVTree"))  mDbgDraw.renderGroup(2);
1407   }
1408}
1409
1410void NavMesh::renderLinks(duDebugDraw &dd)
1411{
1412   if(mBuilding)
1413      return;
1414   dd.depthMask(true);
1415   dd.begin(DU_DRAW_LINES);
1416   for(U32 i = 0; i < mLinkIDs.size(); i++)
1417   {
1418      U32 col = 0;
1419      switch(mLinkSelectStates[i])
1420      {
1421         case Unselected: col = mLinksUnsynced[i] ? duRGBA(255, 0, 0, 200) : duRGBA(0, 0, 255, 255); break;
1422         case Hovered:    col = duRGBA(255, 255, 255, 255); break;
1423         case Selected:   col = duRGBA(0, 255, 0, 255); break;
1424      }
1425      F32 *s = &mLinkVerts[i*6];
1426      F32 *e = &mLinkVerts[i*6 + 3];
1427      if(!mDeleteLinks[i])
1428         duAppendCircle(&dd, s[0], s[1], s[2], mLinkRads[i], col);
1429      duAppendArc(&dd,
1430         s[0], s[1], s[2],
1431         e[0], e[1], e[2],
1432         0.3f,
1433         0.0f, mLinkFlags[i] == DropFlag ? 0.0f : 0.4f,
1434         col);
1435      if(!mDeleteLinks[i])
1436         duAppendCircle(&dd, e[0], e[1], e[2], mLinkRads[i], col);
1437   }
1438   dd.end();
1439}
1440
1441void NavMesh::renderTileData(duDebugDrawTorque &dd, U32 tile)
1442{
1443   if(tile >= mTileData.size())
1444      return;
1445   if(nm)
1446   {
1447      dd.beginGroup(0);
1448      if(mTileData[tile].chf) duDebugDrawCompactHeightfieldSolid(&dd, *mTileData[tile].chf);
1449
1450      dd.beginGroup(1);
1451      int col = duRGBA(255, 0, 255, 255);
1452      RecastPolyList &in = mTileData[tile].geom;
1453      dd.begin(DU_DRAW_LINES);
1454      const F32 *verts = in.getVerts();
1455      const S32 *tris = in.getTris();
1456      for(U32 t = 0; t < in.getTriCount(); t++)
1457      {
1458         dd.vertex(&verts[tris[t*3]*3], col);
1459         dd.vertex(&verts[tris[t*3+1]*3], col);
1460         dd.vertex(&verts[tris[t*3+1]*3], col);
1461         dd.vertex(&verts[tris[t*3+2]*3], col);
1462         dd.vertex(&verts[tris[t*3+2]*3], col);
1463         dd.vertex(&verts[tris[t*3]*3], col);
1464      }
1465      dd.end();
1466   }
1467}
1468
1469void NavMesh::onEditorEnable()
1470{
1471   mNetFlags.set(Ghostable);
1472   if(isClientObject() && !mAlwaysRender)
1473      addToScene();
1474}
1475
1476void NavMesh::onEditorDisable()
1477{
1478   if(!mAlwaysRender)
1479   {
1480      mNetFlags.clear(Ghostable);
1481      if(isClientObject())
1482         removeFromScene();
1483   }
1484}
1485
1486U32 NavMesh::packUpdate(NetConnection *conn, U32 mask, BitStream *stream)
1487{
1488   U32 retMask = Parent::packUpdate(conn, mask, stream);
1489
1490   mathWrite(*stream, getTransform());
1491   mathWrite(*stream, getScale());
1492   stream->writeFlag(mAlwaysRender);
1493
1494   return retMask;
1495}
1496
1497void NavMesh::unpackUpdate(NetConnection *conn, BitStream *stream)
1498{
1499   Parent::unpackUpdate(conn, stream);
1500
1501   mathRead(*stream, &mObjToWorld);
1502   mathRead(*stream, &mObjScale);
1503   mAlwaysRender = stream->readFlag();
1504
1505   setTransform(mObjToWorld);
1506
1507   renderToDrawer();
1508}
1509
1510static const int NAVMESHSET_MAGIC = 'M'<<24 | 'S'<<16 | 'E'<<8 | 'T'; //'MSET';
1511static const int NAVMESHSET_VERSION = 1;
1512
1513struct NavMeshSetHeader
1514{
1515   int magic;
1516   int version;
1517   int numTiles;
1518   dtNavMeshParams params;
1519};
1520
1521struct NavMeshTileHeader
1522{
1523   dtTileRef tileRef;
1524   int dataSize;
1525};
1526
1527bool NavMesh::load()
1528{
1529   if(!dStrlen(mFileName))
1530      return false;
1531
1532   File file;
1533   if(file.open(mFileName, File::Read) != File::Ok)
1534   {
1535      file.close();
1536      Con::errorf("Could not open file %s when loading navmesh %s.",
1537         mFileName, getName() ? getName() : getIdString());
1538      return false;
1539   }
1540
1541   // Read header.
1542   NavMeshSetHeader header;
1543   file.read(sizeof(NavMeshSetHeader), (char*)&header);
1544   if(header.magic != NAVMESHSET_MAGIC)
1545   {
1546      file.close();
1547      Con::errorf("Navmesh magic incorrect when loading navmesh %s; possible corrupt navmesh file %s.",
1548         getName() ? getName() : getIdString(), mFileName);
1549      return false;
1550   }
1551   if(header.version != NAVMESHSET_VERSION)
1552   {
1553      file.close();
1554      Con::errorf("Navmesh version incorrect when loading navmesh %s; possible corrupt navmesh file %s.",
1555         getName() ? getName() : getIdString(), mFileName);
1556      return false;
1557   }
1558
1559   if(nm)
1560      dtFreeNavMesh(nm);
1561   nm = dtAllocNavMesh();
1562   if(!nm)
1563   {
1564      file.close();
1565      Con::errorf("Out of memory when loading navmesh %s.",
1566         getName() ? getName() : getIdString());
1567      return false;
1568   }
1569
1570   dtStatus status = nm->init(&header.params);
1571   if(dtStatusFailed(status))
1572   {
1573      file.close();
1574      Con::errorf("Failed to initialise navmesh params when loading navmesh %s.",
1575         getName() ? getName() : getIdString());
1576      return false;
1577   }
1578
1579   // Read tiles.
1580   for(U32 i = 0; i < header.numTiles; ++i)
1581   {
1582      NavMeshTileHeader tileHeader;
1583      file.read(sizeof(NavMeshTileHeader), (char*)&tileHeader);
1584      if(!tileHeader.tileRef || !tileHeader.dataSize)
1585         break;
1586
1587      unsigned char* data = (unsigned char*)dtAlloc(tileHeader.dataSize, DT_ALLOC_PERM);
1588      if(!data) break;
1589      memset(data, 0, tileHeader.dataSize);
1590      file.read(tileHeader.dataSize, (char*)data);
1591
1592      nm->addTile(data, tileHeader.dataSize, DT_TILE_FREE_DATA, tileHeader.tileRef, 0);
1593   }
1594
1595   S32 s;
1596   file.read(sizeof(S32), (char*)&s);
1597   setLinkCount(s);
1598   if (s > 0)
1599   {
1600      file.read(sizeof(F32) * s * 6, (char*)const_cast<F32*>(mLinkVerts.address()));
1601      file.read(sizeof(F32) * s, (char*)const_cast<F32*>(mLinkRads.address()));
1602      file.read(sizeof(U8) * s, (char*)const_cast<U8*>(mLinkDirs.address()));
1603      file.read(sizeof(U8) * s, (char*)const_cast<U8*>(mLinkAreas.address()));
1604      file.read(sizeof(U16) * s, (char*)const_cast<U16*>(mLinkFlags.address()));
1605      file.read(sizeof(F32) * s, (char*)const_cast<U32*>(mLinkIDs.address()));
1606   }
1607   mLinksUnsynced.fill(false);
1608   mLinkSelectStates.fill(Unselected);
1609   mDeleteLinks.fill(false);
1610
1611   file.close();
1612
1613   updateTiles();
1614
1615   if(isServerObject())
1616   {
1617      setMaskBits(LoadFlag);
1618      if(getEventManager())
1619         getEventManager()->postEvent("NavMeshUpdate", getIdString());
1620   }
1621
1622   return true;
1623}
1624
1625DefineEngineMethod(NavMesh, load, bool, (),,
1626   "@brief Load this NavMesh from its file.")
1627{
1628   return object->load();
1629}
1630
1631bool NavMesh::save()
1632{
1633   if(!dStrlen(mFileName) || !nm)
1634      return false;
1635   
1636   File file;
1637   if(file.open(mFileName, File::Write) != File::Ok)
1638   {
1639      file.close();
1640      Con::errorf("Could not open file %s when saving navmesh %s.",
1641         mFileName, getName() ? getName() : getIdString());
1642      return false;
1643   }
1644
1645   // Store header.
1646   NavMeshSetHeader header;
1647   header.magic = NAVMESHSET_MAGIC;
1648   header.version = NAVMESHSET_VERSION;
1649   header.numTiles = 0;
1650   for(U32 i = 0; i < nm->getMaxTiles(); ++i)
1651   {
1652      const dtMeshTile* tile = ((const dtNavMesh*)nm)->getTile(i);
1653      if (!tile || !tile->header || !tile->dataSize) continue;
1654      header.numTiles++;
1655   }
1656   memcpy(&header.params, nm->getParams(), sizeof(dtNavMeshParams));
1657   file.write(sizeof(NavMeshSetHeader), (const char*)&header);
1658
1659   // Store tiles.
1660   for(U32 i = 0; i < nm->getMaxTiles(); ++i)
1661   {
1662      const dtMeshTile* tile = ((const dtNavMesh*)nm)->getTile(i);
1663      if(!tile || !tile->header || !tile->dataSize) continue;
1664
1665      NavMeshTileHeader tileHeader;
1666      tileHeader.tileRef = nm->getTileRef(tile);
1667      tileHeader.dataSize = tile->dataSize;
1668
1669      file.write(sizeof(tileHeader), (const char*)&tileHeader);
1670      file.write(tile->dataSize, (const char*)tile->data);
1671   }
1672
1673   S32 s = mLinkIDs.size();
1674   file.write(sizeof(S32), (const char*)&s);
1675   if (s > 0)
1676   {
1677      file.write(sizeof(F32) * s * 6, (const char*)mLinkVerts.address());
1678      file.write(sizeof(F32) * s,     (const char*)mLinkRads.address());
1679      file.write(sizeof(U8) * s,      (const char*)mLinkDirs.address());
1680      file.write(sizeof(U8) * s,      (const char*)mLinkAreas.address());
1681      file.write(sizeof(U16) * s,     (const char*)mLinkFlags.address());
1682      file.write(sizeof(U32) * s,     (const char*)mLinkIDs.address());
1683   }
1684
1685   file.close();
1686
1687   return true;
1688}
1689
1690DefineEngineMethod(NavMesh, save, void, (),,
1691   "@brief Save this NavMesh to its file.")
1692{
1693   object->save();
1694}
1695
1696void NavMesh::write(Stream &stream, U32 tabStop, U32 flags)
1697{
1698   save();
1699   Parent::write(stream, tabStop, flags);
1700}
1701