in src/esp/nav/PathFinder.cpp [342:656]
bool PathFinder::Impl::build(const NavMeshSettings& bs,
const float* verts,
const int nverts,
const int* tris,
const int ntris,
const float* bmin,
const float* bmax) {
Workspace ws;
rcContext ctx;
//
// Step 1. Initialize build config.
//
// Init build configuration from GUI
rcConfig cfg{};
memset(&cfg, 0, sizeof(cfg));
cfg.cs = bs.cellSize;
cfg.ch = bs.cellHeight;
cfg.walkableSlopeAngle = bs.agentMaxSlope;
cfg.walkableHeight = static_cast<int>(ceilf(bs.agentHeight / cfg.ch));
cfg.walkableClimb = static_cast<int>(floorf(bs.agentMaxClimb / cfg.ch));
cfg.walkableRadius = static_cast<int>(ceilf(bs.agentRadius / cfg.cs));
cfg.maxEdgeLen = static_cast<int>(bs.edgeMaxLen / bs.cellSize);
cfg.maxSimplificationError = bs.edgeMaxError;
cfg.minRegionArea =
static_cast<int>(rcSqr(bs.regionMinSize)); // Note: area = size*size
cfg.mergeRegionArea =
static_cast<int>(rcSqr(bs.regionMergeSize)); // Note: area = size*size
cfg.maxVertsPerPoly = static_cast<int>(bs.vertsPerPoly);
cfg.detailSampleDist =
bs.detailSampleDist < 0.9f ? 0 : bs.cellSize * bs.detailSampleDist;
cfg.detailSampleMaxError = bs.cellHeight * bs.detailSampleMaxError;
// Set the area where the navigation will be build.
// Here the bounds of the input mesh are used, but the
// area could be specified by an user defined box, etc.
rcVcopy(cfg.bmin, bmin);
rcVcopy(cfg.bmax, bmax);
rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);
ESP_DEBUG() << "Building navmesh with" << cfg.width << "x" << cfg.height
<< "cells";
//
// Step 2. Rasterize input polygon soup.
//
// Allocate voxel heightfield where we rasterize our input data to.
ws.solid = rcAllocHeightfield();
if (!ws.solid) {
ESP_ERROR() << "Out of memory for heightfield allocation";
return false;
}
if (!rcCreateHeightfield(&ctx, *ws.solid, cfg.width, cfg.height, cfg.bmin,
cfg.bmax, cfg.cs, cfg.ch)) {
ESP_ERROR() << "Could not create solid heightfield";
return false;
}
// Allocate array that can hold triangle area types.
// If you have multiple meshes you need to process, allocate
// and array which can hold the max number of triangles you need to process.
ws.triareas = new unsigned char[ntris];
if (!ws.triareas) {
ESP_ERROR() << "Out of memory for triareas" << ntris;
return false;
}
// Find triangles which are walkable based on their slope and rasterize them.
// If your input data is multiple meshes, you can transform them here,
// calculate the are type for each of the meshes and rasterize them.
memset(ws.triareas, 0, ntris * sizeof(unsigned char));
rcMarkWalkableTriangles(&ctx, cfg.walkableSlopeAngle, verts, nverts, tris,
ntris, ws.triareas);
if (!rcRasterizeTriangles(&ctx, verts, nverts, tris, ws.triareas, ntris,
*ws.solid, cfg.walkableClimb)) {
ESP_ERROR() << "Could not rasterize triangles.";
return false;
}
//
// Step 3. Filter walkables surfaces.
//
// Once all geoemtry is rasterized, we do initial pass of filtering to
// remove unwanted overhangs caused by the conservative rasterization
// as well as filter spans where the character cannot possibly stand.
if (bs.filterLowHangingObstacles)
rcFilterLowHangingWalkableObstacles(&ctx, cfg.walkableClimb, *ws.solid);
if (bs.filterLedgeSpans)
rcFilterLedgeSpans(&ctx, cfg.walkableHeight, cfg.walkableClimb, *ws.solid);
if (bs.filterWalkableLowHeightSpans)
rcFilterWalkableLowHeightSpans(&ctx, cfg.walkableHeight, *ws.solid);
//
// Step 4. Partition walkable surface to simple regions.
//
// Compact the heightfield so that it is faster to handle from now on.
// This will result more cache coherent data as well as the neighbours
// between walkable cells will be calculated.
ws.chf = rcAllocCompactHeightfield();
if (!ws.chf) {
ESP_ERROR() << "Out of memory for compact heightfield";
return false;
}
if (!rcBuildCompactHeightfield(&ctx, cfg.walkableHeight, cfg.walkableClimb,
*ws.solid, *ws.chf)) {
ESP_ERROR() << "Could not build compact heightfield";
return false;
}
// Erode the walkable area by agent radius.
if (!rcErodeWalkableArea(&ctx, cfg.walkableRadius, *ws.chf)) {
ESP_ERROR() << "Could not erode walkable area";
return false;
}
// // (Optional) Mark areas.
// const ConvexVolume* vols = geom->getConvexVolumes();
// for (int i = 0; i < geom->getConvexVolumeCount(); ++i)
// rcMarkConvexPolyArea(ctx, vols[i].verts, vols[i].nverts, vols[i].hmin,
// vols[i].hmax, (unsigned char)vols[i].area, *ws.chf);
// Partition the heightfield so that we can use simple algorithm later to
// triangulate the walkable areas. There are 3 martitioning methods, each with
// some pros and cons: 1) Watershed partitioning
// - the classic Recast partitioning
// - creates the nicest tessellation
// - usually slowest
// - partitions the heightfield into nice regions without holes or overlaps
// - the are some corner cases where this method creates produces holes and
// overlaps
// - holes may appear when a small obstacles is close to large open area
// (triangulation can handle this)
// - overlaps may occur if you have narrow spiral corridors (i.e stairs),
// this make triangulation to fail
// * generally the best choice if you precompute the nacmesh, use this if
// you have large open areas
// 2) Monotone partioning
// - fastest
// - partitions the heightfield into regions without holes and overlaps
// (guaranteed)
// - creates long thin polygons, which sometimes causes paths with detours
// * use this if you want fast navmesh generation
// 3) Layer partitoining
// - quite fast
// - partitions the heighfield into non-overlapping regions
// - relies on the triangulation code to cope with holes (thus slower than
// monotone partitioning)
// - produces better triangles than monotone partitioning
// - does not have the corner cases of watershed partitioning
// - can be slow and create a bit ugly tessellation (still better than
// monotone)
// if you have large open areas with small obstacles (not a problem if you
// use tiles)
// * good choice to use for tiled navmesh with medium and small sized tiles
// Prepare for region partitioning, by calculating distance field along the
// walkable surface.
if (!rcBuildDistanceField(&ctx, *ws.chf)) {
ESP_ERROR() << "Could not build distance field";
return false;
}
// Partition the walkable surface into simple regions without holes.
if (!rcBuildRegions(&ctx, *ws.chf, 0, cfg.minRegionArea,
cfg.mergeRegionArea)) {
ESP_ERROR() << "Could not build watershed regions";
return false;
}
// // Partition the walkable surface into simple regions without holes.
// // Monotone partitioning does not need distancefield.
// if (!rcBuildRegionsMonotone(ctx, *ws.chf, 0, cfg.minRegionArea,
// cfg.mergeRegionArea))
// // Partition the walkable surface into simple regions without holes.
// if (!rcBuildLayerRegions(ctx, *ws.chf, 0, cfg.minRegionArea))
//
// Step 5. Trace and simplify region contours.
//
// Create contours.
ws.cset = rcAllocContourSet();
if (!ws.cset) {
ESP_ERROR() << "Out of memory for contour set";
return false;
}
if (!rcBuildContours(&ctx, *ws.chf, cfg.maxSimplificationError,
cfg.maxEdgeLen, *ws.cset)) {
ESP_ERROR() << "Could not create contours";
return false;
}
//
// Step 6. Build polygons mesh from contours.
//
// Build polygon navmesh from the contours.
ws.pmesh = rcAllocPolyMesh();
if (!ws.pmesh) {
ESP_ERROR() << "Out of memory for polymesh";
return false;
}
if (!rcBuildPolyMesh(&ctx, *ws.cset, cfg.maxVertsPerPoly, *ws.pmesh)) {
ESP_ERROR() << "Could not triangulate contours";
return false;
}
//
// Step 7. Create detail mesh which allows to access approximate height on
// each polygon.
//
ws.dmesh = rcAllocPolyMeshDetail();
if (!ws.dmesh) {
ESP_ERROR() << "Out of memory for polymesh detail";
return false;
}
if (!rcBuildPolyMeshDetail(&ctx, *ws.pmesh, *ws.chf, cfg.detailSampleDist,
cfg.detailSampleMaxError, *ws.dmesh)) {
ESP_ERROR() << "Could not build detail mesh";
return false;
}
// At this point the navigation mesh data is ready, you can access it from
// ws.pmesh. See duDebugDrawPolyMesh or dtCreateNavMeshData as examples how to
// access the data.
//
// (Optional) Step 8. Create Detour data from Recast poly mesh.
//
// The GUI may allow more max points per polygon than Detour can handle.
// Only build the detour navmesh if we do not exceed the limit.
if (cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON) {
unsigned char* navData = nullptr;
int navDataSize = 0;
// Update poly flags from areas.
for (int i = 0; i < ws.pmesh->npolys; ++i) {
if (ws.pmesh->areas[i] == RC_WALKABLE_AREA) {
ws.pmesh->areas[i] = POLYAREA_GROUND;
}
if (ws.pmesh->areas[i] == POLYAREA_GROUND) {
ws.pmesh->flags[i] = POLYFLAGS_WALK;
} else if (ws.pmesh->areas[i] == POLYAREA_DOOR) {
ws.pmesh->flags[i] = POLYFLAGS_WALK | POLYFLAGS_DOOR;
}
}
dtNavMeshCreateParams params{};
memset(¶ms, 0, sizeof(params));
params.verts = ws.pmesh->verts;
params.vertCount = ws.pmesh->nverts;
params.polys = ws.pmesh->polys;
params.polyAreas = ws.pmesh->areas;
params.polyFlags = ws.pmesh->flags;
params.polyCount = ws.pmesh->npolys;
params.nvp = ws.pmesh->nvp;
params.detailMeshes = ws.dmesh->meshes;
params.detailVerts = ws.dmesh->verts;
params.detailVertsCount = ws.dmesh->nverts;
params.detailTris = ws.dmesh->tris;
params.detailTriCount = ws.dmesh->ntris;
// params.offMeshConVerts = geom->getOffMeshConnectionVerts();
// params.offMeshConRad = geom->getOffMeshConnectionRads();
// params.offMeshConDir = geom->getOffMeshConnectionDirs();
// params.offMeshConAreas = geom->getOffMeshConnectionAreas();
// params.offMeshConFlags = geom->getOffMeshConnectionFlags();
// params.offMeshConUserID = geom->getOffMeshConnectionId();
// params.offMeshConCount = geom->getOffMeshConnectionCount();
params.walkableHeight = bs.agentHeight;
params.walkableRadius = bs.agentRadius;
params.walkableClimb = bs.agentMaxClimb;
rcVcopy(params.bmin, ws.pmesh->bmin);
rcVcopy(params.bmax, ws.pmesh->bmax);
params.cs = cfg.cs;
params.ch = cfg.ch;
params.buildBvTree = true;
if (!dtCreateNavMeshData(¶ms, &navData, &navDataSize)) {
ESP_ERROR() << "Could not build Detour navmesh";
return false;
}
navMesh_.reset(dtAllocNavMesh());
if (!navMesh_) {
dtFree(navData);
ESP_ERROR() << "Could not allocate Detour navmesh";
return false;
}
dtStatus status = 0;
status = navMesh_->init(navData, navDataSize, DT_TILE_FREE_DATA);
if (dtStatusFailed(status)) {
dtFree(navData);
ESP_ERROR() << "Could not init Detour navmesh";
return false;
}
if (!initNavQuery()) {
return false;
}
}
bounds_ = std::make_pair(vec3f(bmin), vec3f(bmax));
// Added as we also need to remove these on navmesh recomputation
removeZeroAreaPolys();
ESP_DEBUG() << "Created navmesh with" << ws.pmesh->nverts << "vertices"
<< ws.pmesh->npolys << "polygons";
return true;
}