navMesh.cpp

Public Functions

buildCallback(SceneObject * object, void * key)

DefineConsoleFunction(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." )

DefineConsoleFunction(NavMeshIgnore , void , (S32 objid, bool _ignore) , (0, true) , "@brief Flag this object as not generating a navmesh result." )

DefineConsoleFunction(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." )

DefineConsoleFunction(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." )

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