diff options
Diffstat (limited to 'dep/recastnavigation/Detour/Source')
5 files changed, 112 insertions, 52 deletions
diff --git a/dep/recastnavigation/Detour/Source/DetourAssert.cpp b/dep/recastnavigation/Detour/Source/DetourAssert.cpp new file mode 100644 index 00000000000..5e019e0cfc5 --- /dev/null +++ b/dep/recastnavigation/Detour/Source/DetourAssert.cpp @@ -0,0 +1,35 @@ +// +// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org +// +// This software is provided 'as-is', without any express or implied +// warranty. In no event will the authors be held liable for any damages +// arising from the use of this software. +// Permission is granted to anyone to use this software for any purpose, +// including commercial applications, and to alter it and redistribute it +// freely, subject to the following restrictions: +// 1. The origin of this software must not be misrepresented; you must not +// claim that you wrote the original software. If you use this software +// in a product, an acknowledgment in the product documentation would be +// appreciated but is not required. +// 2. Altered source versions must be plainly marked as such, and must not be +// misrepresented as being the original software. +// 3. This notice may not be removed or altered from any source distribution. +// + +#include "DetourAssert.h" + +#ifndef NDEBUG + +static dtAssertFailFunc* sAssertFailFunc = 0; + +void dtAssertFailSetCustom(dtAssertFailFunc *assertFailFunc) +{ + sAssertFailFunc = assertFailFunc; +} + +dtAssertFailFunc* dtAssertFailGetCustom() +{ + return sAssertFailFunc; +} + +#endif diff --git a/dep/recastnavigation/Detour/Source/DetourCommon.cpp b/dep/recastnavigation/Detour/Source/DetourCommon.cpp index 26fe65c1781..41d0d7bd387 100644 --- a/dep/recastnavigation/Detour/Source/DetourCommon.cpp +++ b/dep/recastnavigation/Detour/Source/DetourCommon.cpp @@ -342,8 +342,8 @@ void dtRandomPointInConvexPoly(const float* pts, const int npts, float* areas, // Find sub triangle weighted by area. const float thr = s*areasum; float acc = 0.0f; - float u = 0.0f; - int tri = 0; + float u = 1.0f; + int tri = npts - 1; for (int i = 2; i < npts; i++) { const float dacc = areas[i]; if (thr >= acc && thr < (acc+dacc)) diff --git a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp index f70fa04729a..b81a2567b2e 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMesh.cpp @@ -470,12 +470,12 @@ void dtNavMesh::connectExtOffMeshLinks(dtMeshTile* tile, dtMeshTile* target, int if (targetPoly->firstLink == DT_NULL_LINK) continue; - const float ext[3] = { targetCon->rad, target->header->walkableClimb, targetCon->rad }; + const float halfExtents[3] = { targetCon->rad, target->header->walkableClimb, targetCon->rad }; // Find polygon to connect to. const float* p = &targetCon->pos[3]; float nearestPt[3]; - dtPolyRef ref = findNearestPolyInTile(tile, p, ext, nearestPt); + dtPolyRef ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt); if (!ref) continue; // findNearestPoly may return too optimistic results, further check to make sure. @@ -570,12 +570,12 @@ void dtNavMesh::baseOffMeshLinks(dtMeshTile* tile) dtOffMeshConnection* con = &tile->offMeshCons[i]; dtPoly* poly = &tile->polys[con->poly]; - const float ext[3] = { con->rad, tile->header->walkableClimb, con->rad }; + const float halfExtents[3] = { con->rad, tile->header->walkableClimb, con->rad }; // Find polygon to connect to. const float* p = &con->pos[0]; // First vertex float nearestPt[3]; - dtPolyRef ref = findNearestPolyInTile(tile, p, ext, nearestPt); + dtPolyRef ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt); if (!ref) continue; // findNearestPoly may return too optimistic results, further check to make sure. if (dtSqr(nearestPt[0]-p[0])+dtSqr(nearestPt[2]-p[2]) > dtSqr(con->rad)) @@ -687,7 +687,7 @@ void dtNavMesh::closestPointOnPoly(dtPolyRef ref, const float* pos, float* close v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3]; } float h; - if (dtClosestHeightPointTriangle(pos, v[0], v[1], v[2], h)) + if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h)) { closest[1] = h; break; @@ -696,12 +696,12 @@ void dtNavMesh::closestPointOnPoly(dtPolyRef ref, const float* pos, float* close } dtPolyRef dtNavMesh::findNearestPolyInTile(const dtMeshTile* tile, - const float* center, const float* extents, + const float* center, const float* halfExtents, float* nearestPt) const { float bmin[3], bmax[3]; - dtVsub(bmin, center, extents); - dtVadd(bmax, center, extents); + dtVsub(bmin, center, halfExtents); + dtVadd(bmax, center, halfExtents); // Get nearby polygons from proximity grid. dtPolyRef polys[128]; diff --git a/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp index 965e6cdc5c5..e93a97629b8 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMeshBuilder.cpp @@ -168,45 +168,72 @@ static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNod } } -static int createBVTree(const unsigned short* verts, const int /*nverts*/, - const unsigned short* polys, const int npolys, const int nvp, - const float cs, const float ch, - const int /*nnodes*/, dtBVNode* nodes) +static int createBVTree(dtNavMeshCreateParams* params, dtBVNode* nodes, int /*nnodes*/) { // Build tree - BVItem* items = (BVItem*)dtAlloc(sizeof(BVItem)*npolys, DT_ALLOC_TEMP); - for (int i = 0; i < npolys; i++) + float quantFactor = 1 / params->cs; + BVItem* items = (BVItem*)dtAlloc(sizeof(BVItem)*params->polyCount, DT_ALLOC_TEMP); + for (int i = 0; i < params->polyCount; i++) { BVItem& it = items[i]; it.i = i; - // Calc polygon bounds. - const unsigned short* p = &polys[i*nvp*2]; - it.bmin[0] = it.bmax[0] = verts[p[0]*3+0]; - it.bmin[1] = it.bmax[1] = verts[p[0]*3+1]; - it.bmin[2] = it.bmax[2] = verts[p[0]*3+2]; - - for (int j = 1; j < nvp; ++j) + // Calc polygon bounds. Use detail meshes if available. + if (params->detailMeshes) { - if (p[j] == MESH_NULL_IDX) break; - unsigned short x = verts[p[j]*3+0]; - unsigned short y = verts[p[j]*3+1]; - unsigned short z = verts[p[j]*3+2]; - - if (x < it.bmin[0]) it.bmin[0] = x; - if (y < it.bmin[1]) it.bmin[1] = y; - if (z < it.bmin[2]) it.bmin[2] = z; - - if (x > it.bmax[0]) it.bmax[0] = x; - if (y > it.bmax[1]) it.bmax[1] = y; - if (z > it.bmax[2]) it.bmax[2] = z; + int vb = (int)params->detailMeshes[i*4+0]; + int ndv = (int)params->detailMeshes[i*4+1]; + float bmin[3]; + float bmax[3]; + + const float* dv = ¶ms->detailVerts[vb*3]; + dtVcopy(bmin, dv); + dtVcopy(bmax, dv); + + for (int j = 1; j < ndv; j++) + { + dtVmin(bmin, &dv[j * 3]); + dtVmax(bmax, &dv[j * 3]); + } + + // BV-tree uses cs for all dimensions + it.bmin[0] = (unsigned short)dtClamp((int)((bmin[0] - params->bmin[0])*quantFactor), 0, 0xffff); + it.bmin[1] = (unsigned short)dtClamp((int)((bmin[1] - params->bmin[1])*quantFactor), 0, 0xffff); + it.bmin[2] = (unsigned short)dtClamp((int)((bmin[2] - params->bmin[2])*quantFactor), 0, 0xffff); + + it.bmax[0] = (unsigned short)dtClamp((int)((bmax[0] - params->bmin[0])*quantFactor), 0, 0xffff); + it.bmax[1] = (unsigned short)dtClamp((int)((bmax[1] - params->bmin[1])*quantFactor), 0, 0xffff); + it.bmax[2] = (unsigned short)dtClamp((int)((bmax[2] - params->bmin[2])*quantFactor), 0, 0xffff); + } + else + { + const unsigned short* p = ¶ms->polys[i*params->nvp * 2]; + it.bmin[0] = it.bmax[0] = params->verts[p[0] * 3 + 0]; + it.bmin[1] = it.bmax[1] = params->verts[p[0] * 3 + 1]; + it.bmin[2] = it.bmax[2] = params->verts[p[0] * 3 + 2]; + + for (int j = 1; j < params->nvp; ++j) + { + if (p[j] == MESH_NULL_IDX) break; + unsigned short x = params->verts[p[j] * 3 + 0]; + unsigned short y = params->verts[p[j] * 3 + 1]; + unsigned short z = params->verts[p[j] * 3 + 2]; + + if (x < it.bmin[0]) it.bmin[0] = x; + if (y < it.bmin[1]) it.bmin[1] = y; + if (z < it.bmin[2]) it.bmin[2] = z; + + if (x > it.bmax[0]) it.bmax[0] = x; + if (y > it.bmax[1]) it.bmax[1] = y; + if (z > it.bmax[2]) it.bmax[2] = z; + } + // Remap y + it.bmin[1] = (unsigned short)dtMathFloorf((float)it.bmin[1] * params->ch / params->cs); + it.bmax[1] = (unsigned short)dtMathCeilf((float)it.bmax[1] * params->ch / params->cs); } - // Remap y - it.bmin[1] = (unsigned short)dtMathFloorf((float)it.bmin[1]*ch/cs); - it.bmax[1] = (unsigned short)dtMathCeilf((float)it.bmax[1]*ch/cs); } int curNode = 0; - subdivide(items, npolys, 0, npolys, curNode, nodes); + subdivide(items, params->polyCount, 0, params->polyCount, curNode, nodes); dtFree(items); @@ -595,11 +622,9 @@ bool dtCreateNavMeshData(dtNavMeshCreateParams* params, unsigned char** outData, } // Store and create BVtree. - // TODO: take detail mesh into account! use byte per bbox extent? if (params->buildBvTree) { - createBVTree(params->verts, params->vertCount, params->polys, params->polyCount, - nvp, params->cs, params->ch, params->polyCount*2, navBvtree); + createBVTree(params, navBvtree, 2*params->polyCount); } // Store Off-Mesh connections. diff --git a/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp index 2f781fb92a2..4e69fcbcc53 100644 --- a/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp +++ b/dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp @@ -578,7 +578,7 @@ dtStatus dtNavMeshQuery::closestPointOnPoly(dtPolyRef ref, const float* pos, flo v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3]; } float h; - if (dtClosestHeightPointTriangle(pos, v[0], v[1], v[2], h)) + if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h)) { closest[1] = h; break; @@ -759,7 +759,7 @@ public: /// return #DT_SUCCESS, but @p nearestRef will be zero. So if in doubt, check /// @p nearestRef before using @p nearestPt. /// -dtStatus dtNavMeshQuery::findNearestPoly(const float* center, const float* extents, +dtStatus dtNavMeshQuery::findNearestPoly(const float* center, const float* halfExtents, const dtQueryFilter* filter, dtPolyRef* nearestRef, float* nearestPt) const { @@ -770,7 +770,7 @@ dtStatus dtNavMeshQuery::findNearestPoly(const float* center, const float* exten dtFindNearestPolyQuery query(this, center); - dtStatus status = queryPolygons(center, extents, filter, &query); + dtStatus status = queryPolygons(center, halfExtents, filter, &query); if (dtStatusFailed(status)) return status; @@ -943,7 +943,7 @@ public: /// be filled to capacity. The method of choosing which polygons from the /// full set are included in the partial result set is undefined. /// -dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents, +dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* halfExtents, const dtQueryFilter* filter, dtPolyRef* polys, int* polyCount, const int maxPolys) const { @@ -952,7 +952,7 @@ dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents dtCollectPolysQuery collector(polys, maxPolys); - dtStatus status = queryPolygons(center, extents, filter, &collector); + dtStatus status = queryPolygons(center, halfExtents, filter, &collector); if (dtStatusFailed(status)) return status; @@ -963,21 +963,21 @@ dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents /// @par /// /// The query will be invoked with batches of polygons. Polygons passed -/// to the query have bounding boxes that overlap with the center and extents +/// to the query have bounding boxes that overlap with the center and halfExtents /// passed to this function. The dtPolyQuery::process function is invoked multiple /// times until all overlapping polygons have been processed. /// -dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* extents, +dtStatus dtNavMeshQuery::queryPolygons(const float* center, const float* halfExtents, const dtQueryFilter* filter, dtPolyQuery* query) const { dtAssert(m_nav); - if (!center || !extents || !filter || !query) + if (!center || !halfExtents || !filter || !query) return DT_FAILURE | DT_INVALID_PARAM; float bmin[3], bmax[3]; - dtVsub(bmin, center, extents); - dtVadd(bmax, center, extents); + dtVsub(bmin, center, halfExtents); + dtVadd(bmax, center, halfExtents); // Find tiles the query touches. int minx, miny, maxx, maxy; |