diff options
Diffstat (limited to 'deps/recastnavigation/Recast')
| -rw-r--r-- | deps/recastnavigation/Recast/CMakeLists.txt | 34 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/Recast.cpp | 423 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/Recast.h | 688 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastAlloc.cpp | 67 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastAlloc.h | 69 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastArea.cpp | 416 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastAssert.h | 33 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastContour.cpp | 802 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastFilter.cpp | 181 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastMesh.cpp | 1324 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastMeshDetail.cpp | 1237 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastRasterization.cpp | 360 | ||||
| -rw-r--r-- | deps/recastnavigation/Recast/RecastRegion.cpp | 1285 |
13 files changed, 23 insertions, 6896 deletions
diff --git a/deps/recastnavigation/Recast/CMakeLists.txt b/deps/recastnavigation/Recast/CMakeLists.txt index 975b4a9c14..30265cb7e4 100644 --- a/deps/recastnavigation/Recast/CMakeLists.txt +++ b/deps/recastnavigation/Recast/CMakeLists.txt @@ -1,4 +1,4 @@ -# Copyright (C) +# Copyright (C) 2008-2016 TrinityCore <http://www.trinitycore.org/> # # This file is free software; as a special exception the author gives # unlimited permission to copy and/or distribute it, with or without @@ -9,15 +9,16 @@ # implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. set(Recast_STAT_SRCS - Recast.cpp - RecastAlloc.cpp - RecastArea.cpp - RecastContour.cpp - RecastFilter.cpp - RecastMesh.cpp - RecastMeshDetail.cpp - RecastRasterization.cpp - RecastRegion.cpp + Source/Recast.cpp + Source/RecastAlloc.cpp + Source/RecastArea.cpp + Source/RecastContour.cpp + Source/RecastFilter.cpp + Source/RecastLayers.cpp + Source/RecastMesh.cpp + Source/RecastMeshDetail.cpp + Source/RecastRasterization.cpp + Source/RecastRegion.cpp ) if(WIN32) @@ -28,4 +29,15 @@ endif() add_library(Recast STATIC ${Recast_STAT_SRCS}) -target_link_libraries(Recast ${ZLIB_LIBRARIES}) +target_include_directories(Recast + PUBLIC + ${CMAKE_CURRENT_SOURCE_DIR}/Include) + +target_link_libraries(Recast + PUBLIC + zlib) + +set_target_properties(Recast + PROPERTIES + FOLDER + "dep") diff --git a/deps/recastnavigation/Recast/Recast.cpp b/deps/recastnavigation/Recast/Recast.cpp deleted file mode 100644 index d051418e81..0000000000 --- a/deps/recastnavigation/Recast/Recast.cpp +++ /dev/null @@ -1,423 +0,0 @@ -// -// 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 <float.h> -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdlib.h> -#include <stdio.h> -#include <stdarg.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - -float rcSqrt(float x) -{ - return sqrtf(x); -} - - -void rcContext::log(const rcLogCategory category, const char* format, ...) -{ - if (!m_logEnabled) - return; - static const int MSG_SIZE = 512; - char msg[MSG_SIZE]; - va_list ap; - va_start(ap, format); - int len = vsnprintf(msg, MSG_SIZE, format, ap); - if (len >= MSG_SIZE) - { - len = MSG_SIZE-1; - msg[MSG_SIZE-1] = '\0'; - } - va_end(ap); - doLog(category, msg, len); -} - -rcHeightfield* rcAllocHeightfield() -{ - rcHeightfield* hf = (rcHeightfield*)rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM); - memset(hf, 0, sizeof(rcHeightfield)); - return hf; -} - -void rcFreeHeightField(rcHeightfield* hf) -{ - if (!hf) return; - // Delete span array. - rcFree(hf->spans); - // Delete span pools. - while (hf->pools) - { - rcSpanPool* next = hf->pools->next; - rcFree(hf->pools); - hf->pools = next; - } - rcFree(hf); -} - -rcCompactHeightfield* rcAllocCompactHeightfield() -{ - rcCompactHeightfield* chf = (rcCompactHeightfield*)rcAlloc(sizeof(rcCompactHeightfield), RC_ALLOC_PERM); - memset(chf, 0, sizeof(rcCompactHeightfield)); - return chf; -} - -void rcFreeCompactHeightfield(rcCompactHeightfield* chf) -{ - if (!chf) return; - rcFree(chf->cells); - rcFree(chf->spans); - rcFree(chf->dist); - rcFree(chf->areas); - rcFree(chf); -} - -rcContourSet* rcAllocContourSet() -{ - rcContourSet* cset = (rcContourSet*)rcAlloc(sizeof(rcContourSet), RC_ALLOC_PERM); - memset(cset, 0, sizeof(rcContourSet)); - return cset; -} - -void rcFreeContourSet(rcContourSet* cset) -{ - if (!cset) return; - for (int i = 0; i < cset->nconts; ++i) - { - rcFree(cset->conts[i].verts); - rcFree(cset->conts[i].rverts); - } - rcFree(cset->conts); - rcFree(cset); -} - -rcPolyMesh* rcAllocPolyMesh() -{ - rcPolyMesh* pmesh = (rcPolyMesh*)rcAlloc(sizeof(rcPolyMesh), RC_ALLOC_PERM); - memset(pmesh, 0, sizeof(rcPolyMesh)); - return pmesh; -} - -void rcFreePolyMesh(rcPolyMesh* pmesh) -{ - if (!pmesh) return; - rcFree(pmesh->verts); - rcFree(pmesh->polys); - rcFree(pmesh->regs); - rcFree(pmesh->flags); - rcFree(pmesh->areas); - rcFree(pmesh); -} - -rcPolyMeshDetail* rcAllocPolyMeshDetail() -{ - rcPolyMeshDetail* dmesh = (rcPolyMeshDetail*)rcAlloc(sizeof(rcPolyMeshDetail), RC_ALLOC_PERM); - memset(dmesh, 0, sizeof(rcPolyMeshDetail)); - return dmesh; -} - -void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh) -{ - if (!dmesh) return; - rcFree(dmesh->meshes); - rcFree(dmesh->verts); - rcFree(dmesh->tris); - rcFree(dmesh); -} - - -void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax) -{ - // Calculate bounding box. - rcVcopy(bmin, verts); - rcVcopy(bmax, verts); - for (int i = 1; i < nv; ++i) - { - const float* v = &verts[i*3]; - rcVmin(bmin, v); - rcVmax(bmax, v); - } -} - -void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h) -{ - *w = (int)((bmax[0] - bmin[0])/cs+0.5f); - *h = (int)((bmax[2] - bmin[2])/cs+0.5f); -} - -bool rcCreateHeightfield(rcContext* /*ctx*/, rcHeightfield& hf, int width, int height, - const float* bmin, const float* bmax, - float cs, float ch) -{ - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); - - hf.width = width; - hf.height = height; - rcVcopy(hf.bmin, bmin); - rcVcopy(hf.bmax, bmax); - hf.cs = cs; - hf.ch = ch; - hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM); - if (!hf.spans) - return false; - memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height); - return true; -} - -static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm) -{ - float e0[3], e1[3]; - rcVsub(e0, v1, v0); - rcVsub(e1, v2, v0); - rcVcross(norm, e0, e1); - rcVnormalize(norm); -} - -void rcMarkWalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle, - const float* verts, int /*nv*/, - const int* tris, int nt, - unsigned char* areas) -{ - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); - - const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI); - - float norm[3]; - - for (int i = 0; i < nt; ++i) - { - const int* tri = &tris[i*3]; - calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm); - // Check if the face is walkable. - if (norm[1] > walkableThr) - areas[i] = RC_WALKABLE_AREA; - } -} - -void rcClearUnwalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle, - const float* verts, int /*nv*/, - const int* tris, int nt, - unsigned char* areas) -{ - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); - - const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI); - - float norm[3]; - - for (int i = 0; i < nt; ++i) - { - const int* tri = &tris[i*3]; - calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm); - // Check if the face is walkable. - if (norm[1] <= walkableThr) - areas[i] = RC_NULL_AREA; - } -} - -int rcGetHeightFieldSpanCount(rcContext* /*ctx*/, rcHeightfield& hf) -{ - // TODO: VC complains about unref formal variable, figure out a way to handle this better. -// rcAssert(ctx); - - const int w = hf.width; - const int h = hf.height; - int spanCount = 0; - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next) - { - if (s->area != RC_NULL_AREA) - spanCount++; - } - } - } - return spanCount; -} - -bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb, - rcHeightfield& hf, rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD); - - const int w = hf.width; - const int h = hf.height; - const int spanCount = rcGetHeightFieldSpanCount(ctx, hf); - - // Fill in header. - chf.width = w; - chf.height = h; - chf.spanCount = spanCount; - chf.walkableHeight = walkableHeight; - chf.walkableClimb = walkableClimb; - chf.maxRegions = 0; - rcVcopy(chf.bmin, hf.bmin); - rcVcopy(chf.bmax, hf.bmax); - chf.bmax[1] += walkableHeight*hf.ch; - chf.cs = hf.cs; - chf.ch = hf.ch; - chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM); - if (!chf.cells) - { - ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h); - return false; - } - memset(chf.cells, 0, sizeof(rcCompactCell)*w*h); - chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM); - if (!chf.spans) - { - ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount); - return false; - } - memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount); - chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM); - if (!chf.areas) - { - ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount); - return false; - } - memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount); - - const int MAX_HEIGHT = 0xffff; - - // Fill in cells and spans. - int idx = 0; - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcSpan* s = hf.spans[x + y*w]; - // If there are no spans at this cell, just leave the data to index=0, count=0. - if (!s) continue; - rcCompactCell& c = chf.cells[x+y*w]; - c.index = idx; - c.count = 0; - while (s) - { - if (s->area != RC_NULL_AREA) - { - const int bot = (int)s->smax; - const int top = s->next ? (int)s->next->smin : MAX_HEIGHT; - chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff); - chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff); - chf.areas[idx] = s->area; - idx++; - c.count++; - } - s = s->next; - } - } - } - - // Find neighbour connections. - const int MAX_LAYERS = RC_NOT_CONNECTED-1; - int tooHighNeighbour = 0; - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - rcCompactSpan& s = chf.spans[i]; - - for (int dir = 0; dir < 4; ++dir) - { - rcSetCon(s, dir, RC_NOT_CONNECTED); - const int nx = x + rcGetDirOffsetX(dir); - const int ny = y + rcGetDirOffsetY(dir); - // First check that the neighbour cell is in bounds. - if (nx < 0 || ny < 0 || nx >= w || ny >= h) - continue; - - // Iterate over all neighbour spans and check if any of the is - // accessible from current cell. - const rcCompactCell& nc = chf.cells[nx+ny*w]; - for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k) - { - const rcCompactSpan& ns = chf.spans[k]; - const int bot = rcMax(s.y, ns.y); - const int top = rcMin(s.y+s.h, ns.y+ns.h); - - // Check that the gap between the spans is walkable, - // and that the climb height between the gaps is not too high. - if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb) - { - // Mark direction as walkable. - const int idx = k - (int)nc.index; - if (idx < 0 || idx > MAX_LAYERS) - { - tooHighNeighbour = rcMax(tooHighNeighbour, idx); - continue; - } - rcSetCon(s, dir, idx); - break; - } - } - - } - } - } - } - - if (tooHighNeighbour > MAX_LAYERS) - { - ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)", - tooHighNeighbour, MAX_LAYERS); - } - - ctx->stopTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD); - - return true; -} - -/* -static int getHeightfieldMemoryUsage(const rcHeightfield& hf) -{ - int size = 0; - size += sizeof(hf); - size += hf.width * hf.height * sizeof(rcSpan*); - - rcSpanPool* pool = hf.pools; - while (pool) - { - size += (sizeof(rcSpanPool) - sizeof(rcSpan)) + sizeof(rcSpan)*RC_SPANS_PER_POOL; - pool = pool->next; - } - return size; -} - -static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf) -{ - int size = 0; - size += sizeof(rcCompactHeightfield); - size += sizeof(rcCompactSpan) * chf.spanCount; - size += sizeof(rcCompactCell) * chf.width * chf.height; - return size; -} -*/
\ No newline at end of file diff --git a/deps/recastnavigation/Recast/Recast.h b/deps/recastnavigation/Recast/Recast.h deleted file mode 100644 index 0e5f074248..0000000000 --- a/deps/recastnavigation/Recast/Recast.h +++ /dev/null @@ -1,688 +0,0 @@ -// -// 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. -// - -#ifndef RECAST_H -#define RECAST_H - -// Some math headers don't have PI defined. -static const float RC_PI = 3.14159265f; - -enum rcLogCategory -{ - RC_LOG_PROGRESS = 1, - RC_LOG_WARNING, - RC_LOG_ERROR, -}; - -enum rcTimerLabel -{ - RC_TIMER_TOTAL, - RC_TIMER_TEMP, - RC_TIMER_RASTERIZE_TRIANGLES, - RC_TIMER_BUILD_COMPACTHEIGHTFIELD, - RC_TIMER_BUILD_CONTOURS, - RC_TIMER_BUILD_CONTOURS_TRACE, - RC_TIMER_BUILD_CONTOURS_SIMPLIFY, - RC_TIMER_FILTER_BORDER, - RC_TIMER_FILTER_WALKABLE, - RC_TIMER_MEDIAN_AREA, - RC_TIMER_FILTER_LOW_OBSTACLES, - RC_TIMER_BUILD_POLYMESH, - RC_TIMER_MERGE_POLYMESH, - RC_TIMER_ERODE_AREA, - RC_TIMER_MARK_BOX_AREA, - RC_TIMER_MARK_CONVEXPOLY_AREA, - RC_TIMER_BUILD_DISTANCEFIELD, - RC_TIMER_BUILD_DISTANCEFIELD_DIST, - RC_TIMER_BUILD_DISTANCEFIELD_BLUR, - RC_TIMER_BUILD_REGIONS, - RC_TIMER_BUILD_REGIONS_WATERSHED, - RC_TIMER_BUILD_REGIONS_EXPAND, - RC_TIMER_BUILD_REGIONS_FLOOD, - RC_TIMER_BUILD_REGIONS_FILTER, - RC_TIMER_BUILD_POLYMESHDETAIL, - RC_TIMER_MERGE_POLYMESHDETAIL, - RC_MAX_TIMERS -}; - -// Build context provides several optional utilities needed for the build process, -// such as timing, logging, and build time collecting. -class rcContext -{ -public: - inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {} - virtual ~rcContext() {} - - // Enables or disables logging. - inline void enableLog(bool state) { m_logEnabled = state; } - // Resets log. - inline void resetLog() { if (m_logEnabled) doResetLog(); } - // Logs a message. - void log(const rcLogCategory category, const char* format, ...); - - // Enables or disables timer. - inline void enableTimer(bool state) { m_timerEnabled = state; } - // Resets all timers. - inline void resetTimers() { if (m_timerEnabled) doResetTimers(); } - // Starts timer, used for performance timing. - inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); } - // Stops timer, used for performance timing. - inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); } - // Returns time accumulated between timer start/stop. - inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; } - -protected: - // Virtual functions to override for custom implementations. - virtual void doResetLog() {} - virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {} - virtual void doResetTimers() {} - virtual void doStartTimer(const rcTimerLabel /*label*/) {} - virtual void doStopTimer(const rcTimerLabel /*label*/) {} - virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; } - - bool m_logEnabled; - bool m_timerEnabled; -}; - - -// The units of the parameters are specified in parenthesis as follows: -// (vx) voxels, (wu) world units -struct rcConfig -{ - int width, height; // Dimensions of the rasterized heightfield (vx) - int tileSize; // Width and Height of a tile (vx) - int borderSize; // Non-navigable Border around the heightfield (vx) - float cs, ch; // Grid cell size and height (wu) - float bmin[3], bmax[3]; // Grid bounds (wu) - float walkableSlopeAngle; // Maximum walkable slope angle in degrees. - int walkableHeight; // Minimum height where the agent can still walk (vx) - int walkableClimb; // Maximum height between grid cells the agent can climb (vx) - int walkableRadius; // Radius of the agent in cells (vx) - int maxEdgeLen; // Maximum contour edge length (vx) - float maxSimplificationError; // Maximum distance error from contour to cells (vx) - int minRegionArea; // Regions whose area is smaller than this threshold will be removed. (vx) - int mergeRegionArea; // Regions whose area is smaller than this threshold will be merged (vx) - int maxVertsPerPoly; // Max number of vertices per polygon - float detailSampleDist; // Detail mesh sample spacing. - float detailSampleMaxError; // Detail mesh simplification max sample error. -}; - -// Define number of bits in the above structure for smin/smax. -// The max height is used for clamping rasterized values. -static const int RC_SPAN_HEIGHT_BITS = 16; -static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1; - -// Heightfield span. -struct rcSpan -{ - unsigned int smin : 16; // Span min height. - unsigned int smax : 16; // Span max height. - unsigned char area; // Span area type. - rcSpan* next; // Next span in column. -}; - -// Number of spans allocated per pool. -static const int RC_SPANS_PER_POOL = 2048; - -// Memory pool used for quick span allocation. -struct rcSpanPool -{ - rcSpanPool* next; // Pointer to next pool. - rcSpan items[RC_SPANS_PER_POOL]; // Array of spans. -}; - -// Dynamic span-heightfield. -struct rcHeightfield -{ - int width, height; // Dimension of the heightfield. - float bmin[3], bmax[3]; // Bounding box of the heightfield - float cs, ch; // Cell size and height. - rcSpan** spans; // Heightfield of spans (width*height). - rcSpanPool* pools; // Linked list of span pools. - rcSpan* freelist; // Pointer to next free span. -}; - -rcHeightfield* rcAllocHeightfield(); -void rcFreeHeightField(rcHeightfield* hf); - - -struct rcCompactCell -{ - unsigned int index : 24; // Index to first span in column. - unsigned int count : 8; // Number of spans in this column. -}; - -struct rcCompactSpan -{ - unsigned short y; // Bottom coordinate of the span. - unsigned short reg; - unsigned int con : 24; // Connections to neighbour cells. - unsigned int h : 8; // Height of the span. -}; - -// Compact static heightfield. -struct rcCompactHeightfield -{ - int width, height; // Width and height of the heightfield. - int spanCount; // Number of spans in the heightfield. - int walkableHeight, walkableClimb; // Agent properties. - unsigned short maxDistance; // Maximum distance value stored in heightfield. - unsigned short maxRegions; // Maximum Region Id stored in heightfield. - float bmin[3], bmax[3]; // Bounding box of the heightfield. - float cs, ch; // Cell size and height. - rcCompactCell* cells; // Pointer to width*height cells. - rcCompactSpan* spans; // Pointer to spans. - unsigned short* dist; // Pointer to per span distance to border. - unsigned char* areas; // Pointer to per span area ID. -}; - -rcCompactHeightfield* rcAllocCompactHeightfield(); -void rcFreeCompactHeightfield(rcCompactHeightfield* chf); - - -struct rcContour -{ - int* verts; // Vertex coordinates, each vertex contains 4 components. - int nverts; // Number of vertices. - int* rverts; // Raw vertex coordinates, each vertex contains 4 components. - int nrverts; // Number of raw vertices. - unsigned short reg; // Region ID of the contour. - unsigned char area; // Area ID of the contour. -}; - -struct rcContourSet -{ - rcContour* conts; // Pointer to all contours. - int nconts; // Number of contours. - float bmin[3], bmax[3]; // Bounding box of the heightfield. - float cs, ch; // Cell size and height. -}; - -rcContourSet* rcAllocContourSet(); -void rcFreeContourSet(rcContourSet* cset); - - -// Polymesh store a connected mesh of polygons. -// The polygons are store in an array where each polygons takes -// 'nvp*2' elements. The first 'nvp' elements are indices to vertices -// and the second 'nvp' elements are indices to neighbour polygons. -// If a polygon has less than 'bvp' vertices, the remaining indices -// are set to RC_MESH_NULL_IDX. If an polygon edge does not have a neighbour -// the neighbour index is set to RC_MESH_NULL_IDX. -// Vertices can be transformed into world space as follows: -// x = bmin[0] + verts[i*3+0]*cs; -// y = bmin[1] + verts[i*3+1]*ch; -// z = bmin[2] + verts[i*3+2]*cs; -struct rcPolyMesh -{ - unsigned short* verts; // Vertices of the mesh, 3 elements per vertex. - unsigned short* polys; // Polygons of the mesh, nvp*2 elements per polygon. - unsigned short* regs; // Region ID of the polygons. - unsigned short* flags; // Per polygon flags. - unsigned char* areas; // Area ID of polygons. - int nverts; // Number of vertices. - int npolys; // Number of polygons. - int maxpolys; // Number of allocated polygons. - int nvp; // Max number of vertices per polygon. - float bmin[3], bmax[3]; // Bounding box of the mesh. - float cs, ch; // Cell size and height. -}; - -rcPolyMesh* rcAllocPolyMesh(); -void rcFreePolyMesh(rcPolyMesh* pmesh); - - -// Detail mesh generated from a rcPolyMesh. -// Each submesh represents a polygon in the polymesh and they are stored in -// exactly same order. Each submesh is described as 4 values: -// base vertex, vertex count, base triangle, triangle count. That is, -// const unsigned char* t = &dmesh.tris[(tbase+i)*3]; and -// const float* v = &dmesh.verts[(vbase+t[j])*3]; -// If the input polygon has 'n' vertices, those vertices are first in the -// submesh vertex list. This allows to compres the mesh by not storing the -// first vertices and using the polymesh vertices instead. -// Max number of vertices per submesh is 127 and -// max number of triangles per submesh is 255. - -struct rcPolyMeshDetail -{ - unsigned int* meshes; // Pointer to all mesh data. - float* verts; // Pointer to all vertex data. - unsigned char* tris; // Pointer to all triangle data. - int nmeshes; // Number of meshes. - int nverts; // Number of total vertices. - int ntris; // Number of triangles. -}; - -rcPolyMeshDetail* rcAllocPolyMeshDetail(); -void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); - - -// If heightfield region ID has the following bit set, the region is on border area -// and excluded from many calculations. -static const unsigned short RC_BORDER_REG = 0x8000; - -// If contour region ID has the following bit set, the vertex will be later -// removed in order to match the segments and vertices at tile boundaries. -static const int RC_BORDER_VERTEX = 0x10000; - -static const int RC_AREA_BORDER = 0x20000; - -enum rcBuildContoursFlags -{ - RC_CONTOUR_TESS_WALL_EDGES = 0x01, // Tessellate wall edges - RC_CONTOUR_TESS_AREA_EDGES = 0x02, // Tessellate edges between areas. -}; - -// Mask used with contours to extract region id. -static const int RC_CONTOUR_REG_MASK = 0xffff; - -// Null index which is used with meshes to mark unset or invalid indices. -static const unsigned short RC_MESH_NULL_IDX = 0xffff; - -// Area ID that is considered empty. -static const unsigned char RC_NULL_AREA = 0; - -// Area ID that is considered generally walkable. -static const unsigned char RC_WALKABLE_AREA = 63; - -// Value returned by rcGetCon() if the direction is not connected. -static const int RC_NOT_CONNECTED = 0x3f; - -// Compact span neighbour helpers. -inline void rcSetCon(rcCompactSpan& s, int dir, int i) -{ - const unsigned int shift = (unsigned int)dir*6; - unsigned int con = s.con; - s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift); -} - -inline int rcGetCon(const rcCompactSpan& s, int dir) -{ - const unsigned int shift = (unsigned int)dir*6; - return (s.con >> shift) & 0x3f; -} - -inline int rcGetDirOffsetX(int dir) -{ - const int offset[4] = { -1, 0, 1, 0, }; - return offset[dir&0x03]; -} - -inline int rcGetDirOffsetY(int dir) -{ - const int offset[4] = { 0, 1, 0, -1 }; - return offset[dir&0x03]; -} - -// Common helper functions -template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; } -template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; } -template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; } -template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; } -template<class T> inline T rcSqr(T a) { return a*a; } -template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); } -float rcSqrt(float x); - -// Common vector helper functions. -inline void rcVcross(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; - dest[1] = v1[2]*v2[0] - v1[0]*v2[2]; - dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; -} - -inline float rcVdot(const float* v1, const float* v2) -{ - return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]; -} - -inline void rcVmad(float* dest, const float* v1, const float* v2, const float s) -{ - dest[0] = v1[0]+v2[0]*s; - dest[1] = v1[1]+v2[1]*s; - dest[2] = v1[2]+v2[2]*s; -} - -inline void rcVadd(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[0]+v2[0]; - dest[1] = v1[1]+v2[1]; - dest[2] = v1[2]+v2[2]; -} - -inline void rcVsub(float* dest, const float* v1, const float* v2) -{ - dest[0] = v1[0]-v2[0]; - dest[1] = v1[1]-v2[1]; - dest[2] = v1[2]-v2[2]; -} - -inline void rcVmin(float* mn, const float* v) -{ - mn[0] = rcMin(mn[0], v[0]); - mn[1] = rcMin(mn[1], v[1]); - mn[2] = rcMin(mn[2], v[2]); -} - -inline void rcVmax(float* mx, const float* v) -{ - mx[0] = rcMax(mx[0], v[0]); - mx[1] = rcMax(mx[1], v[1]); - mx[2] = rcMax(mx[2], v[2]); -} - -inline void rcVcopy(float* dest, const float* v) -{ - dest[0] = v[0]; - dest[1] = v[1]; - dest[2] = v[2]; -} - -inline float rcVdist(const float* v1, const float* v2) -{ - float dx = v2[0] - v1[0]; - float dy = v2[1] - v1[1]; - float dz = v2[2] - v1[2]; - return rcSqrt(dx*dx + dy*dy + dz*dz); -} - -inline float rcVdistSqr(const float* v1, const float* v2) -{ - float dx = v2[0] - v1[0]; - float dy = v2[1] - v1[1]; - float dz = v2[2] - v1[2]; - return dx*dx + dy*dy + dz*dz; -} - -inline void rcVnormalize(float* v) -{ - float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2])); - v[0] *= d; - v[1] *= d; - v[2] *= d; -} - -inline bool rcVequal(const float* p0, const float* p1) -{ - static const float thr = rcSqr(1.0f/16384.0f); - const float d = rcVdistSqr(p0, p1); - return d < thr; -} - -// Calculated bounding box of array of vertices. -// Params: -// verts - (in) array of vertices -// nv - (in) vertex count -// bmin, bmax - (out) bounding box -void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax); - -// Calculates grid size based on bounding box and grid cell size. -// Params: -// bmin, bmax - (in) bounding box -// cs - (in) grid cell size -// w - (out) grid width -// h - (out) grid height -void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h); - -// Creates and initializes new heightfield. -// Params: -// hf - (in/out) heightfield to initialize. -// width - (in) width of the heightfield. -// height - (in) height of the heightfield. -// bmin, bmax - (in) bounding box of the heightfield -// cs - (in) grid cell size -// ch - (in) grid cell height -bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height, - const float* bmin, const float* bmax, - float cs, float ch); - -// Sets the RC_WALKABLE_AREA for every triangle whose slope is below -// the maximum walkable slope angle. -// Params: -// walkableSlopeAngle - (in) maximum slope angle in degrees. -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// nt - (in) triangle count -// areas - (out) array of triangle area types -void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, - const int* tris, int nt, unsigned char* areas); - -// Sets the RC_NULL_AREA for every triangle whose slope is steeper than -// the maximum walkable slope angle. -// Params: -// walkableSlopeAngle - (in) maximum slope angle in degrees. -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// nt - (in) triangle count -// areas - (out) array of triangle are types -void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, - const int* tris, int nt, unsigned char* areas); - -// Adds span to heightfield. -// The span addition can set to favor flags. If the span is merged to -// another span and the new smax is within 'flagMergeThr' units away -// from the existing span the span flags are merged and stored. -// Params: -// solid - (in) heightfield where the spans is added to -// x,y - (in) location on the heightfield where the span is added -// smin,smax - (in) spans min/max height -// flags - (in) span flags (zero or WALKABLE) -// flagMergeThr - (in) merge threshold. -void rcAddSpan(rcContext* ctx, rcHeightfield& solid, const int x, const int y, - const unsigned short smin, const unsigned short smax, - const unsigned short area, const int flagMergeThr); - -// Rasterizes a triangle into heightfield spans. -// Params: -// v0,v1,v2 - (in) the vertices of the triangle. -// area - (in) area type of the triangle. -// solid - (in) heightfield where the triangle is rasterized -// flagMergeThr - (in) distance in voxel where walkable flag is favored over non-walkable. -void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, - const unsigned char area, rcHeightfield& solid, - const int flagMergeThr = 1); - -// Rasterizes indexed triangle mesh into heightfield spans. -// Params: -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// area - (in) array of triangle area types. -// nt - (in) triangle count -// solid - (in) heightfield where the triangles are rasterized -// flagMergeThr - (in) distance in voxel where walkable flag is favored over non-walkable. -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, - const int* tris, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr = 1); - -// Rasterizes indexed triangle mesh into heightfield spans. -// Params: -// verts - (in) array of vertices -// nv - (in) vertex count -// tris - (in) array of triangle vertex indices -// area - (in) array of triangle area types. -// nt - (in) triangle count -// solid - (in) heightfield where the triangles are rasterized -// flagMergeThr - (in) distance in voxel where walkable flag is favored over non-walkable. -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, - const unsigned short* tris, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr = 1); - -// Rasterizes the triangles into heightfield spans. -// Params: -// verts - (in) array of vertices -// area - (in) array of triangle area types. -// nt - (in) triangle count -// solid - (in) heightfield where the triangles are rasterized -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr = 1); - -// Marks non-walkable low obstacles as walkable if they are closer than walkableClimb -// from a walkable surface. Applying this filter allows to step over low hanging -// low obstacles. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// solid - (in/out) heightfield describing the solid space -// TODO: Missuses ledge flag, must be called before rcFilterLedgeSpans! -void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid); - -// Removes WALKABLE flag from all spans that are at ledges. This filtering -// removes possible overestimation of the conservative voxelization so that -// the resulting mesh will not have regions hanging in air over ledges. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// walkableClimb - (in) maximum height between grid cells the agent can climb -// solid - (in/out) heightfield describing the solid space -void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, - const int walkableClimb, rcHeightfield& solid); - -// Removes WALKABLE flag from all spans which have smaller than -// 'walkableHeight' clearance above them. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// solid - (in/out) heightfield describing the solid space -void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid); - -// Returns number of spans contained in a heightfield. -// Params: -// hf - (in) heightfield to be compacted -// Returns number of spans. -int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf); - -// Builds compact representation of the heightfield. -// Params: -// walkableHeight - (in) minimum height where the agent can still walk -// walkableClimb - (in) maximum height between grid cells the agent can climb -// flags - (in) require flags for a cell to be included in the compact heightfield. -// hf - (in) heightfield to be compacted -// chf - (out) compact heightfield representing the open space. -// Returns false if operation ran out of memory. -bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb, - rcHeightfield& hf, rcCompactHeightfield& chf); - -// Erodes walkable area. -// Params: -// radius - (in) radius of erosion (max 255). -// chf - (in/out) compact heightfield to erode. -// Returns false if operation ran out of memory. -bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf); - -// Applies median filter to walkable area types, removing noise. -// Params: -// chf - (in/out) compact heightfield to erode. -// Returns false if operation ran out of memory. -bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf); - -// Marks the area of the convex polygon into the area type of the compact heightfield. -// Params: -// bmin/bmax - (in) bounds of the axis aligned box. -// areaId - (in) area ID to mark. -// chf - (in/out) compact heightfield to mark. -void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId, - rcCompactHeightfield& chf); - -// Marks the area of the convex polygon into the area type of the compact heightfield. -// Params: -// verts - (in) vertices of the convex polygon. -// nverts - (in) number of vertices in the polygon. -// hmin/hmax - (in) min and max height of the polygon. -// areaId - (in) area ID to mark. -// chf - (in/out) compact heightfield to mark. -void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, - const float hmin, const float hmax, unsigned char areaId, - rcCompactHeightfield& chf); - -// Builds distance field and stores it into the combat heightfield. -// Params: -// chf - (in/out) compact heightfield representing the open space. -// Returns false if operation ran out of memory. -bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf); - -// Divides the walkable heighfied into simple regions using watershed partitioning. -// Each region has only one contour and no overlaps. -// The regions are stored in the compact heightfield 'reg' field. -// The process sometimes creates small regions. If the area of a regions is -// smaller than 'mergeRegionArea' then the region will be merged with a neighbour -// region if possible. If multiple regions form an area which is smaller than -// 'minRegionArea' all the regions belonging to that area will be removed. -// Here area means the count of spans in an area. -// Params: -// chf - (in/out) compact heightfield representing the open space. -// minRegionArea - (in) the smallest allowed region area. -// maxMergeRegionArea - (in) the largest allowed region area which can be merged. -// Returns false if operation ran out of memory. -bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, - const int borderSize, const int minRegionArea, const int mergeRegionArea); - -// Divides the walkable heighfied into simple regions using simple monotone partitioning. -// Each region has only one contour and no overlaps. -// The regions are stored in the compact heightfield 'reg' field. -// The process sometimes creates small regions. If the area of a regions is -// smaller than 'mergeRegionArea' then the region will be merged with a neighbour -// region if possible. If multiple regions form an area which is smaller than -// 'minRegionArea' all the regions belonging to that area will be removed. -// Here area means the count of spans in an area. -// Params: -// chf - (in/out) compact heightfield representing the open space. -// minRegionArea - (in) the smallest allowed regions size. -// maxMergeRegionArea - (in) the largest allowed regions size which can be merged. -// Returns false if operation ran out of memory. -bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, - const int borderSize, const int minRegionArea, const int mergeRegionArea); - -// Builds simplified contours from the regions outlines. -// Params: -// chf - (in) compact heightfield which has regions set. -// maxError - (in) maximum allowed distance between simplified contour and cells. -// maxEdgeLen - (in) maximum allowed contour edge length in cells. -// cset - (out) Resulting contour set. -// flags - (in) build flags, see rcBuildContoursFlags. -// Returns false if operation ran out of memory. -bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, - const float maxError, const int maxEdgeLen, - rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES); - -// Builds connected convex polygon mesh from contour polygons. -// Params: -// cset - (in) contour set. -// nvp - (in) maximum number of vertices per polygon. -// mesh - (out) poly mesh. -// Returns false if operation ran out of memory. -bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& mesh); - -bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh); - -// Builds detail triangle mesh for each polygon in the poly mesh. -// Params: -// mesh - (in) poly mesh to detail. -// chf - (in) compact height field, used to query height for new vertices. -// sampleDist - (in) spacing between height samples used to generate more detail into mesh. -// sampleMaxError - (in) maximum allowed distance between simplified detail mesh and height sample. -// pmdtl - (out) detail mesh. -// Returns false if operation ran out of memory. -bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf, - const float sampleDist, const float sampleMaxError, - rcPolyMeshDetail& dmesh); - -bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh); - - -#endif // RECAST_H diff --git a/deps/recastnavigation/Recast/RecastAlloc.cpp b/deps/recastnavigation/Recast/RecastAlloc.cpp deleted file mode 100644 index 2c7396a1bf..0000000000 --- a/deps/recastnavigation/Recast/RecastAlloc.cpp +++ /dev/null @@ -1,67 +0,0 @@ -// -// 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 <stdlib.h> -#include <string.h> -#include "RecastAlloc.h" - -static void *rcAllocDefault(int size, rcAllocHint) -{ - return malloc(size); -} - -static void rcFreeDefault(void *ptr) -{ - free(ptr); -} - -static rcAllocFunc* sRecastAllocFunc = rcAllocDefault; -static rcFreeFunc* sRecastFreeFunc = rcFreeDefault; - -void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc) -{ - sRecastAllocFunc = allocFunc ? allocFunc : rcAllocDefault; - sRecastFreeFunc = freeFunc ? freeFunc : rcFreeDefault; -} - -void* rcAlloc(int size, rcAllocHint hint) -{ - return sRecastAllocFunc(size, hint); -} - -void rcFree(void* ptr) -{ - if (ptr) - sRecastFreeFunc(ptr); -} - - -void rcIntArray::resize(int n) -{ - if (n > m_cap) - { - if (!m_cap) m_cap = n; - while (m_cap < n) m_cap *= 2; - int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP); - if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int)); - rcFree(m_data); - m_data = newData; - } - m_size = n; -} - diff --git a/deps/recastnavigation/Recast/RecastAlloc.h b/deps/recastnavigation/Recast/RecastAlloc.h deleted file mode 100644 index 9a316374a7..0000000000 --- a/deps/recastnavigation/Recast/RecastAlloc.h +++ /dev/null @@ -1,69 +0,0 @@ -// -// 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. -// - -#ifndef RECASTALLOC_H -#define RECASTALLOC_H - -enum rcAllocHint -{ - RC_ALLOC_PERM, // Memory persist after a function call. - RC_ALLOC_TEMP // Memory used temporarily within a function. -}; - -typedef void* (rcAllocFunc)(int size, rcAllocHint hint); -typedef void (rcFreeFunc)(void* ptr); - -void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc); - -void* rcAlloc(int size, rcAllocHint hint); -void rcFree(void* ptr); - - - -// Simple dynamic array ints. -class rcIntArray -{ - int* m_data; - int m_size, m_cap; - inline rcIntArray(const rcIntArray&); - inline rcIntArray& operator=(const rcIntArray&); -public: - inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {} - inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(0) { resize(n); } - inline ~rcIntArray() { rcFree(m_data); } - void resize(int n); - inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; } - inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; } - inline const int& operator[](int i) const { return m_data[i]; } - inline int& operator[](int i) { return m_data[i]; } - inline int size() const { return m_size; } -}; - -// Simple internal helper class to delete array in scope -template<class T> class rcScopedDelete -{ - T* ptr; - inline T* operator=(T* p); -public: - inline rcScopedDelete() : ptr(0) {} - inline rcScopedDelete(T* p) : ptr(p) {} - inline ~rcScopedDelete() { rcFree(ptr); } - inline operator T*() { return ptr; } -}; - -#endif diff --git a/deps/recastnavigation/Recast/RecastArea.cpp b/deps/recastnavigation/Recast/RecastArea.cpp deleted file mode 100644 index c18277b878..0000000000 --- a/deps/recastnavigation/Recast/RecastArea.cpp +++ /dev/null @@ -1,416 +0,0 @@ -// -// 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 <float.h> -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdlib.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - - -bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - const int w = chf.width; - const int h = chf.height; - - ctx->startTimer(RC_TIMER_ERODE_AREA); - - unsigned char* dist = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); - if (!dist) - { - ctx->log(RC_LOG_ERROR, "erodeWalkableArea: Out of memory 'dist' (%d).", chf.spanCount); - return false; - } - - // Init distance. - memset(dist, 0xff, sizeof(unsigned char)*chf.spanCount); - - // Mark boundary cells. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (chf.areas[i] != RC_NULL_AREA) - { - const rcCompactSpan& s = chf.spans[i]; - int nc = 0; - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - nc++; - } - // At least one missing neighbour. - if (nc != 4) - dist[i] = 0; - } - } - } - } - - unsigned char nd; - - // Pass 1 - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - - if (rcGetCon(s, 0) != RC_NOT_CONNECTED) - { - // (-1,0) - const int ax = x + rcGetDirOffsetX(0); - const int ay = y + rcGetDirOffsetY(0); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); - const rcCompactSpan& as = chf.spans[ai]; - nd = (unsigned char)rcMin((int)dist[ai]+2, 255); - if (nd < dist[i]) - dist[i] = nd; - - // (-1,-1) - if (rcGetCon(as, 3) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(3); - const int aay = ay + rcGetDirOffsetY(3); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3); - nd = (unsigned char)rcMin((int)dist[aai]+3, 255); - if (nd < dist[i]) - dist[i] = nd; - } - } - if (rcGetCon(s, 3) != RC_NOT_CONNECTED) - { - // (0,-1) - const int ax = x + rcGetDirOffsetX(3); - const int ay = y + rcGetDirOffsetY(3); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); - const rcCompactSpan& as = chf.spans[ai]; - nd = (unsigned char)rcMin((int)dist[ai]+2, 255); - if (nd < dist[i]) - dist[i] = nd; - - // (1,-1) - if (rcGetCon(as, 2) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(2); - const int aay = ay + rcGetDirOffsetY(2); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2); - nd = (unsigned char)rcMin((int)dist[aai]+3, 255); - if (nd < dist[i]) - dist[i] = nd; - } - } - } - } - } - - // Pass 2 - for (int y = h-1; y >= 0; --y) - { - for (int x = w-1; x >= 0; --x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - - if (rcGetCon(s, 2) != RC_NOT_CONNECTED) - { - // (1,0) - const int ax = x + rcGetDirOffsetX(2); - const int ay = y + rcGetDirOffsetY(2); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2); - const rcCompactSpan& as = chf.spans[ai]; - nd = (unsigned char)rcMin((int)dist[ai]+2, 255); - if (nd < dist[i]) - dist[i] = nd; - - // (1,1) - if (rcGetCon(as, 1) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(1); - const int aay = ay + rcGetDirOffsetY(1); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1); - nd = (unsigned char)rcMin((int)dist[aai]+3, 255); - if (nd < dist[i]) - dist[i] = nd; - } - } - if (rcGetCon(s, 1) != RC_NOT_CONNECTED) - { - // (0,1) - const int ax = x + rcGetDirOffsetX(1); - const int ay = y + rcGetDirOffsetY(1); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1); - const rcCompactSpan& as = chf.spans[ai]; - nd = (unsigned char)rcMin((int)dist[ai]+2, 255); - if (nd < dist[i]) - dist[i] = nd; - - // (-1,1) - if (rcGetCon(as, 0) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(0); - const int aay = ay + rcGetDirOffsetY(0); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0); - nd = (unsigned char)rcMin((int)dist[aai]+3, 255); - if (nd < dist[i]) - dist[i] = nd; - } - } - } - } - } - - const unsigned char thr = (unsigned char)(radius*2); - for (int i = 0; i < chf.spanCount; ++i) - if (dist[i] < thr) - chf.areas[i] = RC_NULL_AREA; - - rcFree(dist); - - ctx->stopTimer(RC_TIMER_ERODE_AREA); - - return true; -} - -static void insertSort(unsigned char* a, const int n) -{ - int i, j; - for (i = 1; i < n; i++) - { - const unsigned char value = a[i]; - for (j = i - 1; j >= 0 && a[j] > value; j--) - a[j+1] = a[j]; - a[j+1] = value; - } -} - - -bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - const int w = chf.width; - const int h = chf.height; - - ctx->startTimer(RC_TIMER_MEDIAN_AREA); - - unsigned char* areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); - if (!areas) - { - ctx->log(RC_LOG_ERROR, "medianFilterWalkableArea: Out of memory 'areas' (%d).", chf.spanCount); - return false; - } - - // Init distance. - memset(areas, 0xff, sizeof(unsigned char)*chf.spanCount); - - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - if (chf.areas[i] == RC_NULL_AREA) - { - areas[i] = chf.areas[i]; - continue; - } - - unsigned char nei[9]; - for (int j = 0; j < 9; ++j) - nei[j] = chf.areas[i]; - - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); - if (chf.areas[ai] != RC_NULL_AREA) - nei[dir*2+0] = chf.areas[ai]; - - const rcCompactSpan& as = chf.spans[ai]; - const int dir2 = (dir+1) & 0x3; - if (rcGetCon(as, dir2) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dir2); - const int ay2 = ay + rcGetDirOffsetY(dir2); - const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2); - if (chf.areas[ai2] != RC_NULL_AREA) - nei[dir*2+1] = chf.areas[ai2]; - } - } - } - insertSort(nei, 9); - areas[i] = nei[4]; - } - } - } - - memcpy(chf.areas, areas, sizeof(unsigned char)*chf.spanCount); - - rcFree(areas); - - ctx->stopTimer(RC_TIMER_MEDIAN_AREA); - - return true; -} - -void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId, - rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_MARK_BOX_AREA); - - int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs); - int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch); - int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs); - int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs); - int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch); - int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs); - - if (maxx < 0) return; - if (minx >= chf.width) return; - if (maxz < 0) return; - if (minz >= chf.height) return; - - if (minx < 0) minx = 0; - if (maxx >= chf.width) maxx = chf.width-1; - if (minz < 0) minz = 0; - if (maxz >= chf.height) maxz = chf.height-1; - - for (int z = minz; z <= maxz; ++z) - { - for (int x = minx; x <= maxx; ++x) - { - const rcCompactCell& c = chf.cells[x+z*chf.width]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - rcCompactSpan& s = chf.spans[i]; - if ((int)s.y >= miny && (int)s.y <= maxy) - { - if (chf.areas[i] != RC_NULL_AREA) - chf.areas[i] = areaId; - } - } - } - } - - ctx->stopTimer(RC_TIMER_MARK_BOX_AREA); - -} - - -static int pointInPoly(int nvert, const float* verts, const float* p) -{ - int i, j, c = 0; - for (i = 0, j = nvert-1; i < nvert; j = i++) - { - const float* vi = &verts[i*3]; - const float* vj = &verts[j*3]; - if (((vi[2] > p[2]) != (vj[2] > p[2])) && - (p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) ) - c = !c; - } - return c; -} - -void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, - const float hmin, const float hmax, unsigned char areaId, - rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_MARK_CONVEXPOLY_AREA); - - float bmin[3], bmax[3]; - rcVcopy(bmin, verts); - rcVcopy(bmax, verts); - for (int i = 1; i < nverts; ++i) - { - rcVmin(bmin, &verts[i*3]); - rcVmax(bmax, &verts[i*3]); - } - bmin[1] = hmin; - bmax[1] = hmax; - - int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs); - int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch); - int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs); - int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs); - int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch); - int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs); - - if (maxx < 0) return; - if (minx >= chf.width) return; - if (maxz < 0) return; - if (minz >= chf.height) return; - - if (minx < 0) minx = 0; - if (maxx >= chf.width) maxx = chf.width-1; - if (minz < 0) minz = 0; - if (maxz >= chf.height) maxz = chf.height-1; - - - // TODO: Optimize. - for (int z = minz; z <= maxz; ++z) - { - for (int x = minx; x <= maxx; ++x) - { - const rcCompactCell& c = chf.cells[x+z*chf.width]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - rcCompactSpan& s = chf.spans[i]; - if (chf.areas[i] == RC_NULL_AREA) - continue; - if ((int)s.y >= miny && (int)s.y <= maxy) - { - float p[3]; - p[0] = chf.bmin[0] + (x+0.5f)*chf.cs; - p[1] = 0; - p[2] = chf.bmin[2] + (z+0.5f)*chf.cs; - - if (pointInPoly(nverts, verts, p)) - { - chf.areas[i] = areaId; - } - } - } - } - } - - ctx->stopTimer(RC_TIMER_MARK_CONVEXPOLY_AREA); -} diff --git a/deps/recastnavigation/Recast/RecastAssert.h b/deps/recastnavigation/Recast/RecastAssert.h deleted file mode 100644 index b58b8fcd28..0000000000 --- a/deps/recastnavigation/Recast/RecastAssert.h +++ /dev/null @@ -1,33 +0,0 @@ -// -// 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. -// - -#ifndef RECASTASSERT_H -#define RECASTASSERT_H - -// Note: This header file's only purpose is to include define assert. -// Feel free to change the file and include your own implementation instead. - -#ifdef NDEBUG -// From http://cnicholson.net/2009/02/stupid-c-tricks-adventures-in-assert/ -# define rcAssert(x) do { (void)sizeof(x); } while(__LINE__==-1,false) -#else -# include <assert.h> -# define rcAssert assert -#endif - -#endif // RECASTASSERT_H diff --git a/deps/recastnavigation/Recast/RecastContour.cpp b/deps/recastnavigation/Recast/RecastContour.cpp deleted file mode 100644 index 4ba8deac89..0000000000 --- a/deps/recastnavigation/Recast/RecastContour.cpp +++ /dev/null @@ -1,802 +0,0 @@ -// -// 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. -// - -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - - -static int getCornerHeight(int x, int y, int i, int dir, - const rcCompactHeightfield& chf, - bool& isBorderVertex) -{ - const rcCompactSpan& s = chf.spans[i]; - int ch = (int)s.y; - int dirp = (dir+1) & 0x3; - - unsigned int regs[4] = {0,0,0,0}; - - // Combine region and area codes in order to prevent - // border vertices which are in between two areas to be removed. - regs[0] = chf.spans[i].reg | (chf.areas[i] << 16); - - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir); - const rcCompactSpan& as = chf.spans[ai]; - ch = rcMax(ch, (int)as.y); - regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16); - if (rcGetCon(as, dirp) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dirp); - const int ay2 = ay + rcGetDirOffsetY(dirp); - const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp); - const rcCompactSpan& as2 = chf.spans[ai2]; - ch = rcMax(ch, (int)as2.y); - regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16); - } - } - if (rcGetCon(s, dirp) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dirp); - const int ay = y + rcGetDirOffsetY(dirp); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp); - const rcCompactSpan& as = chf.spans[ai]; - ch = rcMax(ch, (int)as.y); - regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16); - if (rcGetCon(as, dir) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dir); - const int ay2 = ay + rcGetDirOffsetY(dir); - const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir); - const rcCompactSpan& as2 = chf.spans[ai2]; - ch = rcMax(ch, (int)as2.y); - regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16); - } - } - - // Check if the vertex is special edge vertex, these vertices will be removed later. - for (int j = 0; j < 4; ++j) - { - const int a = j; - const int b = (j+1) & 0x3; - const int c = (j+2) & 0x3; - const int d = (j+3) & 0x3; - - // The vertex is a border vertex there are two same exterior cells in a row, - // followed by two interior cells and none of the regions are out of bounds. - const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b]; - const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0; - const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16); - const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0; - if (twoSameExts && twoInts && intsSameArea && noZeros) - { - isBorderVertex = true; - break; - } - } - - return ch; -} - -static void walkContour(int x, int y, int i, - rcCompactHeightfield& chf, - unsigned char* flags, rcIntArray& points) -{ - // Choose the first non-connected edge - unsigned char dir = 0; - while ((flags[i] & (1 << dir)) == 0) - dir++; - - unsigned char startDir = dir; - int starti = i; - - const unsigned char area = chf.areas[i]; - - int iter = 0; - while (++iter < 40000) - { - if (flags[i] & (1 << dir)) - { - // Choose the edge corner - bool isBorderVertex = false; - bool isAreaBorder = false; - int px = x; - int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex); - int pz = y; - switch(dir) - { - case 0: pz++; break; - case 1: px++; pz++; break; - case 2: px++; break; - } - int r = 0; - const rcCompactSpan& s = chf.spans[i]; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir); - r = (int)chf.spans[ai].reg; - if (area != chf.areas[ai]) - isAreaBorder = true; - } - if (isBorderVertex) - r |= RC_BORDER_VERTEX; - if (isAreaBorder) - r |= RC_AREA_BORDER; - points.push(px); - points.push(py); - points.push(pz); - points.push(r); - - flags[i] &= ~(1 << dir); // Remove visited edges - dir = (dir+1) & 0x3; // Rotate CW - } - else - { - int ni = -1; - const int nx = x + rcGetDirOffsetX(dir); - const int ny = y + rcGetDirOffsetY(dir); - const rcCompactSpan& s = chf.spans[i]; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const rcCompactCell& nc = chf.cells[nx+ny*chf.width]; - ni = (int)nc.index + rcGetCon(s, dir); - } - if (ni == -1) - { - // Should not happen. - return; - } - x = nx; - y = ny; - i = ni; - dir = (dir+3) & 0x3; // Rotate CCW - } - - if (starti == i && startDir == dir) - { - break; - } - } -} - -static float distancePtSeg(const int x, const int z, - const int px, const int pz, - const int qx, const int qz) -{ -/* float pqx = (float)(qx - px); - float pqy = (float)(qy - py); - float pqz = (float)(qz - pz); - float dx = (float)(x - px); - float dy = (float)(y - py); - float dz = (float)(z - pz); - float d = pqx*pqx + pqy*pqy + pqz*pqz; - float t = pqx*dx + pqy*dy + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = px + t*pqx - x; - dy = py + t*pqy - y; - dz = pz + t*pqz - z; - - return dx*dx + dy*dy + dz*dz;*/ - - float pqx = (float)(qx - px); - float pqz = (float)(qz - pz); - float dx = (float)(x - px); - float dz = (float)(z - pz); - float d = pqx*pqx + pqz*pqz; - float t = pqx*dx + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = px + t*pqx - x; - dz = pz + t*pqz - z; - - return dx*dx + dz*dz; -} - -static void simplifyContour(rcIntArray& points, rcIntArray& simplified, - const float maxError, const int maxEdgeLen, const int buildFlags) -{ - // Add initial points. - bool hasConnections = false; - for (int i = 0; i < points.size(); i += 4) - { - if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0) - { - hasConnections = true; - break; - } - } - - if (hasConnections) - { - // The contour has some portals to other regions. - // Add a new point to every location where the region changes. - for (int i = 0, ni = points.size()/4; i < ni; ++i) - { - int ii = (i+1) % ni; - const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK); - const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER); - if (differentRegs || areaBorders) - { - simplified.push(points[i*4+0]); - simplified.push(points[i*4+1]); - simplified.push(points[i*4+2]); - simplified.push(i); - } - } - } - - if (simplified.size() == 0) - { - // If there is no connections at all, - // create some initial points for the simplification process. - // Find lower-left and upper-right vertices of the contour. - int llx = points[0]; - int lly = points[1]; - int llz = points[2]; - int lli = 0; - int urx = points[0]; - int ury = points[1]; - int urz = points[2]; - int uri = 0; - for (int i = 0; i < points.size(); i += 4) - { - int x = points[i+0]; - int y = points[i+1]; - int z = points[i+2]; - if (x < llx || (x == llx && z < llz)) - { - llx = x; - lly = y; - llz = z; - lli = i/4; - } - if (x > urx || (x == urx && z > urz)) - { - urx = x; - ury = y; - urz = z; - uri = i/4; - } - } - simplified.push(llx); - simplified.push(lly); - simplified.push(llz); - simplified.push(lli); - - simplified.push(urx); - simplified.push(ury); - simplified.push(urz); - simplified.push(uri); - } - - // Add points until all raw points are within - // error tolerance to the simplified shape. - const int pn = points.size()/4; - for (int i = 0; i < simplified.size()/4; ) - { - int ii = (i+1) % (simplified.size()/4); - - const int ax = simplified[i*4+0]; - const int az = simplified[i*4+2]; - const int ai = simplified[i*4+3]; - - const int bx = simplified[ii*4+0]; - const int bz = simplified[ii*4+2]; - const int bi = simplified[ii*4+3]; - - // Find maximum deviation from the segment. - float maxd = 0; - int maxi = -1; - int ci, cinc, endi; - - // Traverse the segment in lexilogical order so that the - // max deviation is calculated similarly when traversing - // opposite segments. - if (bx > ax || (bx == ax && bz > az)) - { - cinc = 1; - ci = (ai+cinc) % pn; - endi = bi; - } - else - { - cinc = pn-1; - ci = (bi+cinc) % pn; - endi = ai; - } - - // Tessellate only outer edges oredges between areas. - if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 || - (points[ci*4+3] & RC_AREA_BORDER)) - { - while (ci != endi) - { - float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz); - if (d > maxd) - { - maxd = d; - maxi = ci; - } - ci = (ci+cinc) % pn; - } - } - - - // If the max deviation is larger than accepted error, - // add new point, else continue to next segment. - if (maxi != -1 && maxd > (maxError*maxError)) - { - // Add space for the new point. - simplified.resize(simplified.size()+4); - const int n = simplified.size()/4; - for (int j = n-1; j > i; --j) - { - simplified[j*4+0] = simplified[(j-1)*4+0]; - simplified[j*4+1] = simplified[(j-1)*4+1]; - simplified[j*4+2] = simplified[(j-1)*4+2]; - simplified[j*4+3] = simplified[(j-1)*4+3]; - } - // Add the point. - simplified[(i+1)*4+0] = points[maxi*4+0]; - simplified[(i+1)*4+1] = points[maxi*4+1]; - simplified[(i+1)*4+2] = points[maxi*4+2]; - simplified[(i+1)*4+3] = maxi; - } - else - { - ++i; - } - } - - // Split too long edges. - if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0) - { - for (int i = 0; i < simplified.size()/4; ) - { - const int ii = (i+1) % (simplified.size()/4); - - const int ax = simplified[i*4+0]; - const int az = simplified[i*4+2]; - const int ai = simplified[i*4+3]; - - const int bx = simplified[ii*4+0]; - const int bz = simplified[ii*4+2]; - const int bi = simplified[ii*4+3]; - - // Find maximum deviation from the segment. - int maxi = -1; - int ci = (ai+1) % pn; - - // Tessellate only outer edges or edges between areas. - bool tess = false; - // Wall edges. - if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0) - tess = true; - // Edges between areas. - if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER)) - tess = true; - - if (tess) - { - int dx = bx - ax; - int dz = bz - az; - if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen) - { - // Round based on the segments in lexilogical order so that the - // max tesselation is consistent regardles in which direction - // segments are traversed. - const int n = bi < ai ? (bi+pn - ai) : (bi - ai); - if (n > 1) - { - if (bx > ax || (bx == ax && bz > az)) - maxi = (ai + n/2) % pn; - else - maxi = (ai + (n+1)/2) % pn; - } - } - } - - // If the max deviation is larger than accepted error, - // add new point, else continue to next segment. - if (maxi != -1) - { - // Add space for the new point. - simplified.resize(simplified.size()+4); - const int n = simplified.size()/4; - for (int j = n-1; j > i; --j) - { - simplified[j*4+0] = simplified[(j-1)*4+0]; - simplified[j*4+1] = simplified[(j-1)*4+1]; - simplified[j*4+2] = simplified[(j-1)*4+2]; - simplified[j*4+3] = simplified[(j-1)*4+3]; - } - // Add the point. - simplified[(i+1)*4+0] = points[maxi*4+0]; - simplified[(i+1)*4+1] = points[maxi*4+1]; - simplified[(i+1)*4+2] = points[maxi*4+2]; - simplified[(i+1)*4+3] = maxi; - } - else - { - ++i; - } - } - } - - for (int i = 0; i < simplified.size()/4; ++i) - { - // The edge vertex flag is take from the current raw point, - // and the neighbour region is take from the next raw point. - const int ai = (simplified[i*4+3]+1) % pn; - const int bi = simplified[i*4+3]; - simplified[i*4+3] = (points[ai*4+3] & (RC_CONTOUR_REG_MASK|RC_AREA_BORDER)) | (points[bi*4+3] & RC_BORDER_VERTEX); - } - -} - -static void removeDegenerateSegments(rcIntArray& simplified) -{ - // Remove adjacent vertices which are equal on xz-plane, - // or else the triangulator will get confused. - for (int i = 0; i < simplified.size()/4; ++i) - { - int ni = i+1; - if (ni >= (simplified.size()/4)) - ni = 0; - - if (simplified[i*4+0] == simplified[ni*4+0] && - simplified[i*4+2] == simplified[ni*4+2]) - { - // Degenerate segment, remove. - for (int j = i; j < simplified.size()/4-1; ++j) - { - simplified[j*4+0] = simplified[(j+1)*4+0]; - simplified[j*4+1] = simplified[(j+1)*4+1]; - simplified[j*4+2] = simplified[(j+1)*4+2]; - simplified[j*4+3] = simplified[(j+1)*4+3]; - } - simplified.resize(simplified.size()-4); - } - } -} - -static int calcAreaOfPolygon2D(const int* verts, const int nverts) -{ - int area = 0; - for (int i = 0, j = nverts-1; i < nverts; j=i++) - { - const int* vi = &verts[i*4]; - const int* vj = &verts[j*4]; - area += vi[0] * vj[2] - vj[0] * vi[2]; - } - return (area+1) / 2; -} - -inline bool ileft(const int* a, const int* b, const int* c) -{ - return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0; -} - -static void getClosestIndices(const int* vertsa, const int nvertsa, - const int* vertsb, const int nvertsb, - int& ia, int& ib) -{ - int closestDist = 0xfffffff; - ia = -1, ib = -1; - for (int i = 0; i < nvertsa; ++i) - { - const int in = (i+1) % nvertsa; - const int ip = (i+nvertsa-1) % nvertsa; - const int* va = &vertsa[i*4]; - const int* van = &vertsa[in*4]; - const int* vap = &vertsa[ip*4]; - - for (int j = 0; j < nvertsb; ++j) - { - const int* vb = &vertsb[j*4]; - // vb must be "infront" of va. - if (ileft(vap,va,vb) && ileft(va,van,vb)) - { - const int dx = vb[0] - va[0]; - const int dz = vb[2] - va[2]; - const int d = dx*dx + dz*dz; - if (d < closestDist) - { - ia = i; - ib = j; - closestDist = d; - } - } - } - } -} - -static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib) -{ - const int maxVerts = ca.nverts + cb.nverts + 2; - int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM); - if (!verts) - return false; - - int nv = 0; - - // Copy contour A. - for (int i = 0; i <= ca.nverts; ++i) - { - int* dst = &verts[nv*4]; - const int* src = &ca.verts[((ia+i)%ca.nverts)*4]; - dst[0] = src[0]; - dst[1] = src[1]; - dst[2] = src[2]; - dst[3] = src[3]; - nv++; - } - - // Copy contour B - for (int i = 0; i <= cb.nverts; ++i) - { - int* dst = &verts[nv*4]; - const int* src = &cb.verts[((ib+i)%cb.nverts)*4]; - dst[0] = src[0]; - dst[1] = src[1]; - dst[2] = src[2]; - dst[3] = src[3]; - nv++; - } - - rcFree(ca.verts); - ca.verts = verts; - ca.nverts = nv; - - rcFree(cb.verts); - cb.verts = 0; - cb.nverts = 0; - - return true; -} - -bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, - const float maxError, const int maxEdgeLen, - rcContourSet& cset, const int buildFlags) -{ - rcAssert(ctx); - - const int w = chf.width; - const int h = chf.height; - - ctx->startTimer(RC_TIMER_BUILD_CONTOURS); - - rcVcopy(cset.bmin, chf.bmin); - rcVcopy(cset.bmax, chf.bmax); - cset.cs = chf.cs; - cset.ch = chf.ch; - - int maxContours = rcMax((int)chf.maxRegions, 8); - cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); - if (!cset.conts) - return false; - cset.nconts = 0; - - rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP); - if (!flags) - { - ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount); - return false; - } - - ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - - // Mark boundaries. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - unsigned char res = 0; - const rcCompactSpan& s = chf.spans[i]; - if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG)) - { - flags[i] = 0; - continue; - } - for (int dir = 0; dir < 4; ++dir) - { - unsigned short r = 0; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); - r = chf.spans[ai].reg; - } - if (r == chf.spans[i].reg) - res |= (1 << dir); - } - flags[i] = res ^ 0xf; // Inverse, mark non connected edges. - } - } - } - - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE); - - ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); - - rcIntArray verts(256); - rcIntArray simplified(64); - - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (flags[i] == 0 || flags[i] == 0xf) - { - flags[i] = 0; - continue; - } - const unsigned short reg = chf.spans[i].reg; - if (!reg || (reg & RC_BORDER_REG)) - continue; - const unsigned char area = chf.areas[i]; - - verts.resize(0); - simplified.resize(0); - walkContour(x, y, i, chf, flags, verts); - simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags); - removeDegenerateSegments(simplified); - - // Store region->contour remap info. - // Create contour. - if (simplified.size()/4 >= 3) - { - if (cset.nconts >= maxContours) - { - // Allocate more contours. - // This can happen when there are tiny holes in the heightfield. - const int oldMax = maxContours; - maxContours *= 2; - rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM); - for (int j = 0; j < cset.nconts; ++j) - { - newConts[j] = cset.conts[j]; - // Reset source pointers to prevent data deletion. - cset.conts[j].verts = 0; - cset.conts[j].rverts = 0; - } - rcFree(cset.conts); - cset.conts = newConts; - - ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours); - } - - rcContour* cont = &cset.conts[cset.nconts++]; - - cont->nverts = simplified.size()/4; - cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM); - if (!cont->verts) - { - ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts); - return false; - } - memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4); - - cont->nrverts = verts.size()/4; - cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM); - if (!cont->rverts) - { - ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts); - return false; - } - memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4); - -/* cont->cx = cont->cy = cont->cz = 0; - for (int i = 0; i < cont->nverts; ++i) - { - cont->cx += cont->verts[i*4+0]; - cont->cy += cont->verts[i*4+1]; - cont->cz += cont->verts[i*4+2]; - } - cont->cx /= cont->nverts; - cont->cy /= cont->nverts; - cont->cz /= cont->nverts;*/ - - cont->reg = reg; - cont->area = area; - } - } - } - } - - // Check and merge droppings. - // Sometimes the previous algorithms can fail and create several contours - // per area. This pass will try to merge the holes into the main region. - for (int i = 0; i < cset.nconts; ++i) - { - rcContour& cont = cset.conts[i]; - // Check if the contour is would backwards. - if (calcAreaOfPolygon2D(cont.verts, cont.nverts) < 0) - { - // Find another contour which has the same region ID. - int mergeIdx = -1; - for (int j = 0; j < cset.nconts; ++j) - { - if (i == j) continue; - if (cset.conts[j].nverts && cset.conts[j].reg == cont.reg) - { - // Make sure the polygon is correctly oriented. - if (calcAreaOfPolygon2D(cset.conts[j].verts, cset.conts[j].nverts)) - { - mergeIdx = j; - break; - } - } - } - if (mergeIdx == -1) - { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i); - } - else - { - rcContour& mcont = cset.conts[mergeIdx]; - // Merge by closest points. - int ia = 0, ib = 0; - getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib); - if (ia == -1 || ib == -1) - { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx); - continue; - } - if (!mergeContours(mcont, cont, ia, ib)) - { - ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx); - continue; - } - } - } - } - - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY); - - ctx->stopTimer(RC_TIMER_BUILD_CONTOURS); - - return true; -} diff --git a/deps/recastnavigation/Recast/RecastFilter.cpp b/deps/recastnavigation/Recast/RecastFilter.cpp deleted file mode 100644 index 66af37a413..0000000000 --- a/deps/recastnavigation/Recast/RecastFilter.cpp +++ /dev/null @@ -1,181 +0,0 @@ -// -// 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. -// - -#define _USE_MATH_DEFINES -#include <math.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAssert.h" - - -void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES); - - const int w = solid.width; - const int h = solid.height; - - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - rcSpan* ps = 0; - bool previousWalkable = false; - unsigned char previousArea = RC_NULL_AREA; - - for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next) - { - const bool walkable = s->area != RC_NULL_AREA; - // If current span is not walkable, but there is walkable - // span just below it, mark the span above it walkable too. - if (!walkable && previousWalkable) - { - if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb) - s->area = previousArea; - } - // Copy walkable flag so that it cannot propagate - // past multiple non-walkable objects. - previousWalkable = walkable; - previousArea = s->area; - } - } - } - - ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES); -} - -void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb, - rcHeightfield& solid) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_FILTER_BORDER); - - const int w = solid.width; - const int h = solid.height; - const int MAX_HEIGHT = 0xffff; - - // Mark border spans. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next) - { - // Skip non walkable spans. - if (s->area == RC_NULL_AREA) - continue; - - const int bot = (int)(s->smax); - const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT; - - // Find neighbours minimum height. - int minh = MAX_HEIGHT; - - // Min and max height of accessible neighbours. - int asmin = s->smax; - int asmax = s->smax; - - for (int dir = 0; dir < 4; ++dir) - { - int dx = x + rcGetDirOffsetX(dir); - int dy = y + rcGetDirOffsetY(dir); - // Skip neighbours which are out of bounds. - if (dx < 0 || dy < 0 || dx >= w || dy >= h) - { - minh = rcMin(minh, -walkableClimb - bot); - continue; - } - - // From minus infinity to the first span. - rcSpan* ns = solid.spans[dx + dy*w]; - int nbot = -walkableClimb; - int ntop = ns ? (int)ns->smin : MAX_HEIGHT; - // Skip neightbour if the gap between the spans is too small. - if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight) - minh = rcMin(minh, nbot - bot); - - // Rest of the spans. - for (ns = solid.spans[dx + dy*w]; ns; ns = ns->next) - { - nbot = (int)ns->smax; - ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT; - // Skip neightbour if the gap between the spans is too small. - if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight) - { - minh = rcMin(minh, nbot - bot); - - // Find min/max accessible neighbour height. - if (rcAbs(nbot - bot) <= walkableClimb) - { - if (nbot < asmin) asmin = nbot; - if (nbot > asmax) asmax = nbot; - } - - } - } - } - - // The current span is close to a ledge if the drop to any - // neighbour span is less than the walkableClimb. - if (minh < -walkableClimb) - s->area = RC_NULL_AREA; - - // If the difference between all neighbours is too large, - // we are at steep slope, mark the span as ledge. - if ((asmax - asmin) > walkableClimb) - { - s->area = RC_NULL_AREA; - } - } - } - } - - ctx->stopTimer(RC_TIMER_FILTER_BORDER); -} - -void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_FILTER_WALKABLE); - - const int w = solid.width; - const int h = solid.height; - const int MAX_HEIGHT = 0xffff; - - // Remove walkable flag from spans which do not have enough - // space above them for the agent to stand there. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next) - { - const int bot = (int)(s->smax); - const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT; - if ((top - bot) <= walkableHeight) - s->area = RC_NULL_AREA; - } - } - } - - ctx->stopTimer(RC_TIMER_FILTER_WALKABLE); -} diff --git a/deps/recastnavigation/Recast/RecastMesh.cpp b/deps/recastnavigation/Recast/RecastMesh.cpp deleted file mode 100644 index e7e2397dd6..0000000000 --- a/deps/recastnavigation/Recast/RecastMesh.cpp +++ /dev/null @@ -1,1324 +0,0 @@ -// -// 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. -// - -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - -struct rcEdge -{ - unsigned short vert[2]; - unsigned short polyEdge[2]; - unsigned short poly[2]; -}; - -static bool buildMeshAdjacency(unsigned short* polys, const int npolys, - const int nverts, const int vertsPerPoly) -{ - // Based on code by Eric Lengyel from: - // http://www.terathon.com/code/edges.php - - int maxEdgeCount = npolys*vertsPerPoly; - unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP); - if (!firstEdge) - return false; - unsigned short* nextEdge = firstEdge + nverts; - int edgeCount = 0; - - rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP); - if (!edges) - { - rcFree(firstEdge); - return false; - } - - for (int i = 0; i < nverts; i++) - firstEdge[i] = RC_MESH_NULL_IDX; - - for (int i = 0; i < npolys; ++i) - { - unsigned short* t = &polys[i*vertsPerPoly*2]; - for (int j = 0; j < vertsPerPoly; ++j) - { - if (t[j] == RC_MESH_NULL_IDX) break; - unsigned short v0 = t[j]; - unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1]; - if (v0 < v1) - { - rcEdge& edge = edges[edgeCount]; - edge.vert[0] = v0; - edge.vert[1] = v1; - edge.poly[0] = (unsigned short)i; - edge.polyEdge[0] = (unsigned short)j; - edge.poly[1] = (unsigned short)i; - edge.polyEdge[1] = 0; - // Insert edge - nextEdge[edgeCount] = firstEdge[v0]; - firstEdge[v0] = (unsigned short)edgeCount; - edgeCount++; - } - } - } - - for (int i = 0; i < npolys; ++i) - { - unsigned short* t = &polys[i*vertsPerPoly*2]; - for (int j = 0; j < vertsPerPoly; ++j) - { - if (t[j] == RC_MESH_NULL_IDX) break; - unsigned short v0 = t[j]; - unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1]; - if (v0 > v1) - { - for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e]) - { - rcEdge& edge = edges[e]; - if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1]) - { - edge.poly[1] = (unsigned short)i; - edge.polyEdge[1] = (unsigned short)j; - break; - } - } - } - } - } - - // Store adjacency - for (int i = 0; i < edgeCount; ++i) - { - const rcEdge& e = edges[i]; - if (e.poly[0] != e.poly[1]) - { - unsigned short* p0 = &polys[e.poly[0]*vertsPerPoly*2]; - unsigned short* p1 = &polys[e.poly[1]*vertsPerPoly*2]; - p0[vertsPerPoly + e.polyEdge[0]] = e.poly[1]; - p1[vertsPerPoly + e.polyEdge[1]] = e.poly[0]; - } - } - - rcFree(firstEdge); - rcFree(edges); - - return true; -} - - -static const int VERTEX_BUCKET_COUNT = (1<<12); - -inline int computeVertexHash(int x, int y, int z) -{ - const unsigned int h1 = 0x8da6b343; // Large multiplicative constants; - const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes - const unsigned int h3 = 0xcb1ab31f; - unsigned int n = h1 * x + h2 * y + h3 * z; - return (int)(n & (VERTEX_BUCKET_COUNT-1)); -} - -static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z, - unsigned short* verts, int* firstVert, int* nextVert, int& nv) -{ - int bucket = computeVertexHash(x, 0, z); - int i = firstVert[bucket]; - - while (i != -1) - { - const unsigned short* v = &verts[i*3]; - if (v[0] == x && (rcAbs(v[1] - y) <= 2) && v[2] == z) - return (unsigned short)i; - i = nextVert[i]; // next - } - - // Could not find, create new. - i = nv; nv++; - unsigned short* v = &verts[i*3]; - v[0] = x; - v[1] = y; - v[2] = z; - nextVert[i] = firstVert[bucket]; - firstVert[bucket] = i; - - return (unsigned short)i; -} - -inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; } -inline int next(int i, int n) { return i+1 < n ? i+1 : 0; } - -inline int area2(const int* a, const int* b, const int* c) -{ - return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]); -} - -// Exclusive or: true iff exactly one argument is true. -// The arguments are negated to ensure that they are 0/1 -// values. Then the bitwise Xor operator may apply. -// (This idea is due to Michael Baldwin.) -inline bool xorb(bool x, bool y) -{ - return !x ^ !y; -} - -// Returns true iff c is strictly to the left of the directed -// line through a to b. -inline bool left(const int* a, const int* b, const int* c) -{ - return area2(a, b, c) < 0; -} - -inline bool leftOn(const int* a, const int* b, const int* c) -{ - return area2(a, b, c) <= 0; -} - -inline bool collinear(const int* a, const int* b, const int* c) -{ - return area2(a, b, c) == 0; -} - -// Returns true iff ab properly intersects cd: they share -// a point interior to both segments. The properness of the -// intersection is ensured by using strict leftness. -bool intersectProp(const int* a, const int* b, const int* c, const int* d) -{ - // Eliminate improper cases. - if (collinear(a,b,c) || collinear(a,b,d) || - collinear(c,d,a) || collinear(c,d,b)) - return false; - - return xorb(left(a,b,c), left(a,b,d)) && xorb(left(c,d,a), left(c,d,b)); -} - -// Returns T iff (a,b,c) are collinear and point c lies -// on the closed segement ab. -static bool between(const int* a, const int* b, const int* c) -{ - if (!collinear(a, b, c)) - return false; - // If ab not vertical, check betweenness on x; else on y. - if (a[0] != b[0]) - return ((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0])); - else - return ((a[2] <= c[2]) && (c[2] <= b[2])) || ((a[2] >= c[2]) && (c[2] >= b[2])); -} - -// Returns true iff segments ab and cd intersect, properly or improperly. -static bool intersect(const int* a, const int* b, const int* c, const int* d) -{ - if (intersectProp(a, b, c, d)) - return true; - else if (between(a, b, c) || between(a, b, d) || - between(c, d, a) || between(c, d, b)) - return true; - else - return false; -} - -static bool vequal(const int* a, const int* b) -{ - return a[0] == b[0] && a[2] == b[2]; -} - -// Returns T iff (v_i, v_j) is a proper internal *or* external -// diagonal of P, *ignoring edges incident to v_i and v_j*. -static bool diagonalie(int i, int j, int n, const int* verts, int* indices) -{ - const int* d0 = &verts[(indices[i] & 0x0fffffff) * 4]; - const int* d1 = &verts[(indices[j] & 0x0fffffff) * 4]; - - // For each edge (k,k+1) of P - for (int k = 0; k < n; k++) - { - int k1 = next(k, n); - // Skip edges incident to i or j - if (!((k == i) || (k1 == i) || (k == j) || (k1 == j))) - { - const int* p0 = &verts[(indices[k] & 0x0fffffff) * 4]; - const int* p1 = &verts[(indices[k1] & 0x0fffffff) * 4]; - - if (vequal(d0, p0) || vequal(d1, p0) || vequal(d0, p1) || vequal(d1, p1)) - continue; - - if (intersect(d0, d1, p0, p1)) - return false; - } - } - return true; -} - -// Returns true iff the diagonal (i,j) is strictly internal to the -// polygon P in the neighborhood of the i endpoint. -static bool inCone(int i, int j, int n, const int* verts, int* indices) -{ - const int* pi = &verts[(indices[i] & 0x0fffffff) * 4]; - const int* pj = &verts[(indices[j] & 0x0fffffff) * 4]; - const int* pi1 = &verts[(indices[next(i, n)] & 0x0fffffff) * 4]; - const int* pin1 = &verts[(indices[prev(i, n)] & 0x0fffffff) * 4]; - - // If P[i] is a convex vertex [ i+1 left or on (i-1,i) ]. - if (leftOn(pin1, pi, pi1)) - return left(pi, pj, pin1) && left(pj, pi, pi1); - // Assume (i-1,i,i+1) not collinear. - // else P[i] is reflex. - return !(leftOn(pi, pj, pi1) && leftOn(pj, pi, pin1)); -} - -// Returns T iff (v_i, v_j) is a proper internal -// diagonal of P. -static bool diagonal(int i, int j, int n, const int* verts, int* indices) -{ - return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices); -} - -static int triangulate(int n, const int* verts, int* indices, int* tris) -{ - int ntris = 0; - int* dst = tris; - - // The last bit of the index is used to indicate if the vertex can be removed. - for (int i = 0; i < n; i++) - { - int i1 = next(i, n); - int i2 = next(i1, n); - if (diagonal(i, i2, n, verts, indices)) - indices[i1] |= 0x80000000; - } - - while (n > 3) - { - int minLen = -1; - int mini = -1; - for (int i = 0; i < n; i++) - { - int i1 = next(i, n); - if (indices[i1] & 0x80000000) - { - const int* p0 = &verts[(indices[i] & 0x0fffffff) * 4]; - const int* p2 = &verts[(indices[next(i1, n)] & 0x0fffffff) * 4]; - - int dx = p2[0] - p0[0]; - int dy = p2[2] - p0[2]; - int len = dx*dx + dy*dy; - - if (minLen < 0 || len < minLen) - { - minLen = len; - mini = i; - } - } - } - - if (mini == -1) - { - // Should not happen. -/* printf("mini == -1 ntris=%d n=%d\n", ntris, n); - for (int i = 0; i < n; i++) - { - printf("%d ", indices[i] & 0x0fffffff); - } - printf("\n");*/ - return -ntris; - } - - int i = mini; - int i1 = next(i, n); - int i2 = next(i1, n); - - *dst++ = indices[i] & 0x0fffffff; - *dst++ = indices[i1] & 0x0fffffff; - *dst++ = indices[i2] & 0x0fffffff; - ntris++; - - // Removes P[i1] by copying P[i+1]...P[n-1] left one index. - n--; - for (int k = i1; k < n; k++) - indices[k] = indices[k+1]; - - if (i1 >= n) i1 = 0; - i = prev(i1,n); - // Update diagonal flags. - if (diagonal(prev(i, n), i1, n, verts, indices)) - indices[i] |= 0x80000000; - else - indices[i] &= 0x0fffffff; - - if (diagonal(i, next(i1, n), n, verts, indices)) - indices[i1] |= 0x80000000; - else - indices[i1] &= 0x0fffffff; - } - - // Append the remaining triangle. - *dst++ = indices[0] & 0x0fffffff; - *dst++ = indices[1] & 0x0fffffff; - *dst++ = indices[2] & 0x0fffffff; - ntris++; - - return ntris; -} - -static int countPolyVerts(const unsigned short* p, const int nvp) -{ - for (int i = 0; i < nvp; ++i) - if (p[i] == RC_MESH_NULL_IDX) - return i; - return nvp; -} - -inline bool uleft(const unsigned short* a, const unsigned short* b, const unsigned short* c) -{ - return ((int)b[0] - (int)a[0]) * ((int)c[2] - (int)a[2]) - - ((int)c[0] - (int)a[0]) * ((int)b[2] - (int)a[2]) < 0; -} - -static int getPolyMergeValue(unsigned short* pa, unsigned short* pb, - const unsigned short* verts, int& ea, int& eb, - const int nvp) -{ - const int na = countPolyVerts(pa, nvp); - const int nb = countPolyVerts(pb, nvp); - - // If the merged polygon would be too big, do not merge. - if (na+nb-2 > nvp) - return -1; - - // Check if the polygons share an edge. - ea = -1; - eb = -1; - - for (int i = 0; i < na; ++i) - { - unsigned short va0 = pa[i]; - unsigned short va1 = pa[(i+1) % na]; - if (va0 > va1) - rcSwap(va0, va1); - for (int j = 0; j < nb; ++j) - { - unsigned short vb0 = pb[j]; - unsigned short vb1 = pb[(j+1) % nb]; - if (vb0 > vb1) - rcSwap(vb0, vb1); - if (va0 == vb0 && va1 == vb1) - { - ea = i; - eb = j; - break; - } - } - } - - // No common edge, cannot merge. - if (ea == -1 || eb == -1) - return -1; - - // Check to see if the merged polygon would be convex. - unsigned short va, vb, vc; - - va = pa[(ea+na-1) % na]; - vb = pa[ea]; - vc = pb[(eb+2) % nb]; - if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3])) - return -1; - - va = pb[(eb+nb-1) % nb]; - vb = pb[eb]; - vc = pa[(ea+2) % na]; - if (!uleft(&verts[va*3], &verts[vb*3], &verts[vc*3])) - return -1; - - va = pa[ea]; - vb = pa[(ea+1)%na]; - - int dx = (int)verts[va*3+0] - (int)verts[vb*3+0]; - int dy = (int)verts[va*3+2] - (int)verts[vb*3+2]; - - return dx*dx + dy*dy; -} - -static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb, - unsigned short* tmp, const int nvp) -{ - const int na = countPolyVerts(pa, nvp); - const int nb = countPolyVerts(pb, nvp); - - // Merge polygons. - memset(tmp, 0xff, sizeof(unsigned short)*nvp); - int n = 0; - // Add pa - for (int i = 0; i < na-1; ++i) - tmp[n++] = pa[(ea+1+i) % na]; - // Add pb - for (int i = 0; i < nb-1; ++i) - tmp[n++] = pb[(eb+1+i) % nb]; - - memcpy(pa, tmp, sizeof(unsigned short)*nvp); -} - -static void pushFront(int v, int* arr, int& an) -{ - an++; - for (int i = an-1; i > 0; --i) arr[i] = arr[i-1]; - arr[0] = v; -} - -static void pushBack(int v, int* arr, int& an) -{ - arr[an] = v; - an++; -} - -static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem) -{ - const int nvp = mesh.nvp; - - // Count number of polygons to remove. - int numRemovedVerts = 0; - int numTouchedVerts = 0; - int numRemainingEdges = 0; - for (int i = 0; i < mesh.npolys; ++i) - { - unsigned short* p = &mesh.polys[i*nvp*2]; - const int nv = countPolyVerts(p, nvp); - int numRemoved = 0; - int numVerts = 0; - for (int j = 0; j < nv; ++j) - { - if (p[j] == rem) - { - numTouchedVerts++; - numRemoved++; - } - numVerts++; - } - if (numRemoved) - { - numRemovedVerts += numRemoved; - numRemainingEdges += numVerts-(numRemoved+1); - } - } - - // There would be too few edges remaining to create a polygon. - // This can happen for example when a tip of a triangle is marked - // as deletion, but there are no other polys that share the vertex. - // In this case, the vertex should not be removed. - if (numRemainingEdges <= 2) - return false; - - // Find edges which share the removed vertex. - const int maxEdges = numTouchedVerts*2; - int nedges = 0; - rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP); - if (!edges) - { - ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3); - return false; - } - - for (int i = 0; i < mesh.npolys; ++i) - { - unsigned short* p = &mesh.polys[i*nvp*2]; - const int nv = countPolyVerts(p, nvp); - - // Collect edges which touches the removed vertex. - for (int j = 0, k = nv-1; j < nv; k = j++) - { - if (p[j] == rem || p[k] == rem) - { - // Arrange edge so that a=rem. - int a = p[j], b = p[k]; - if (b == rem) - rcSwap(a,b); - - // Check if the edge exists - bool exists = false; - for (int k = 0; k < nedges; ++k) - { - int* e = &edges[k*3]; - if (e[1] == b) - { - // Exists, increment vertex share count. - e[2]++; - exists = true; - } - } - // Add new edge. - if (!exists) - { - int* e = &edges[nedges*3]; - e[0] = a; - e[1] = b; - e[2] = 1; - nedges++; - } - } - } - } - - // There should be no more than 2 open edges. - // This catches the case that two non-adjacent polygons - // share the removed vertex. In that case, do not remove the vertex. - int numOpenEdges = 0; - for (int i = 0; i < nedges; ++i) - { - if (edges[i*3+2] < 2) - numOpenEdges++; - } - if (numOpenEdges > 2) - return false; - - return true; -} - -static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem, const int maxTris) -{ - const int nvp = mesh.nvp; - - // Count number of polygons to remove. - int numRemovedVerts = 0; - for (int i = 0; i < mesh.npolys; ++i) - { - unsigned short* p = &mesh.polys[i*nvp*2]; - const int nv = countPolyVerts(p, nvp); - for (int j = 0; j < nv; ++j) - { - if (p[j] == rem) - numRemovedVerts++; - } - } - - int nedges = 0; - rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP); - if (!edges) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4); - return false; - } - - int nhole = 0; - rcScopedDelete<int> hole = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); - if (!hole) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp); - return false; - } - - int nhreg = 0; - rcScopedDelete<int> hreg = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); - if (!hreg) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp); - return false; - } - - int nharea = 0; - rcScopedDelete<int> harea = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP); - if (!harea) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp); - return false; - } - - for (int i = 0; i < mesh.npolys; ++i) - { - unsigned short* p = &mesh.polys[i*nvp*2]; - const int nv = countPolyVerts(p, nvp); - bool hasRem = false; - for (int j = 0; j < nv; ++j) - if (p[j] == rem) hasRem = true; - if (hasRem) - { - // Collect edges which does not touch the removed vertex. - for (int j = 0, k = nv-1; j < nv; k = j++) - { - if (p[j] != rem && p[k] != rem) - { - int* e = &edges[nedges*4]; - e[0] = p[k]; - e[1] = p[j]; - e[2] = mesh.regs[i]; - e[3] = mesh.areas[i]; - nedges++; - } - } - // Remove the polygon. - unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2]; - memcpy(p,p2,sizeof(unsigned short)*nvp); - memset(p+nvp,0xff,sizeof(unsigned short)*nvp); - mesh.regs[i] = mesh.regs[mesh.npolys-1]; - mesh.areas[i] = mesh.areas[mesh.npolys-1]; - mesh.npolys--; - --i; - } - } - - // Remove vertex. - for (int i = (int)rem; i < mesh.nverts; ++i) - { - mesh.verts[i*3+0] = mesh.verts[(i+1)*3+0]; - mesh.verts[i*3+1] = mesh.verts[(i+1)*3+1]; - mesh.verts[i*3+2] = mesh.verts[(i+1)*3+2]; - } - mesh.nverts--; - - // Adjust indices to match the removed vertex layout. - for (int i = 0; i < mesh.npolys; ++i) - { - unsigned short* p = &mesh.polys[i*nvp*2]; - const int nv = countPolyVerts(p, nvp); - for (int j = 0; j < nv; ++j) - if (p[j] > rem) p[j]--; - } - for (int i = 0; i < nedges; ++i) - { - if (edges[i*4+0] > rem) edges[i*4+0]--; - if (edges[i*4+1] > rem) edges[i*4+1]--; - } - - if (nedges == 0) - return true; - - // Start with one vertex, keep appending connected - // segments to the start and end of the hole. - pushBack(edges[0], hole, nhole); - pushBack(edges[2], hreg, nhreg); - pushBack(edges[3], harea, nharea); - - while (nedges) - { - bool match = false; - - for (int i = 0; i < nedges; ++i) - { - const int ea = edges[i*4+0]; - const int eb = edges[i*4+1]; - const int r = edges[i*4+2]; - const int a = edges[i*4+3]; - bool add = false; - if (hole[0] == eb) - { - // The segment matches the beginning of the hole boundary. - pushFront(ea, hole, nhole); - pushFront(r, hreg, nhreg); - pushFront(a, harea, nharea); - add = true; - } - else if (hole[nhole-1] == ea) - { - // The segment matches the end of the hole boundary. - pushBack(eb, hole, nhole); - pushBack(r, hreg, nhreg); - pushBack(a, harea, nharea); - add = true; - } - if (add) - { - // The edge segment was added, remove it. - edges[i*4+0] = edges[(nedges-1)*4+0]; - edges[i*4+1] = edges[(nedges-1)*4+1]; - edges[i*4+2] = edges[(nedges-1)*4+2]; - edges[i*4+3] = edges[(nedges-1)*4+3]; - --nedges; - match = true; - --i; - } - } - - if (!match) - break; - } - - rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP); - if (!tris) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3); - return false; - } - - rcScopedDelete<int> tverts = (int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP); - if (!tverts) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4); - return false; - } - - rcScopedDelete<int> thole = (int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP); - if (!tverts) - { - ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole); - return false; - } - - // Generate temp vertex array for triangulation. - for (int i = 0; i < nhole; ++i) - { - const int pi = hole[i]; - tverts[i*4+0] = mesh.verts[pi*3+0]; - tverts[i*4+1] = mesh.verts[pi*3+1]; - tverts[i*4+2] = mesh.verts[pi*3+2]; - tverts[i*4+3] = 0; - thole[i] = i; - } - - // Triangulate the hole. - int ntris = triangulate(nhole, &tverts[0], &thole[0], tris); - if (ntris < 0) - { - ntris = -ntris; - ctx->log(RC_LOG_WARNING, "removeVertex: triangulate() returned bad results."); - } - - // Merge the hole triangles back to polygons. - rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP); - if (!polys) - { - ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp); - return false; - } - rcScopedDelete<unsigned short> pregs = (unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP); - if (!pregs) - { - ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris); - return false; - } - rcScopedDelete<unsigned char> pareas = (unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP); - if (!pregs) - { - ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris); - return false; - } - - unsigned short* tmpPoly = &polys[ntris*nvp]; - - // Build initial polygons. - int npolys = 0; - memset(polys, 0xff, ntris*nvp*sizeof(unsigned short)); - for (int j = 0; j < ntris; ++j) - { - int* t = &tris[j*3]; - if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2]) - { - polys[npolys*nvp+0] = (unsigned short)hole[t[0]]; - polys[npolys*nvp+1] = (unsigned short)hole[t[1]]; - polys[npolys*nvp+2] = (unsigned short)hole[t[2]]; - pregs[npolys] = (unsigned short)hreg[t[0]]; - pareas[npolys] = (unsigned char)harea[t[0]]; - npolys++; - } - } - if (!npolys) - return true; - - // Merge polygons. - if (nvp > 3) - { - for (;;) - { - // Find best polygons to merge. - int bestMergeVal = 0; - int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0; - - for (int j = 0; j < npolys-1; ++j) - { - unsigned short* pj = &polys[j*nvp]; - for (int k = j+1; k < npolys; ++k) - { - unsigned short* pk = &polys[k*nvp]; - int ea, eb; - int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp); - if (v > bestMergeVal) - { - bestMergeVal = v; - bestPa = j; - bestPb = k; - bestEa = ea; - bestEb = eb; - } - } - } - - if (bestMergeVal > 0) - { - // Found best, merge. - unsigned short* pa = &polys[bestPa*nvp]; - unsigned short* pb = &polys[bestPb*nvp]; - mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp); - memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp); - pregs[bestPb] = pregs[npolys-1]; - pareas[bestPb] = pareas[npolys-1]; - npolys--; - } - else - { - // Could not merge any polygons, stop. - break; - } - } - } - - // Store polygons. - for (int i = 0; i < npolys; ++i) - { - if (mesh.npolys >= maxTris) break; - unsigned short* p = &mesh.polys[mesh.npolys*nvp*2]; - memset(p,0xff,sizeof(unsigned short)*nvp*2); - for (int j = 0; j < nvp; ++j) - p[j] = polys[i*nvp+j]; - mesh.regs[mesh.npolys] = pregs[i]; - mesh.areas[mesh.npolys] = pareas[i]; - mesh.npolys++; - if (mesh.npolys > maxTris) - { - ctx->log(RC_LOG_ERROR, "removeVertex: Too many polygons %d (max:%d).", mesh.npolys, maxTris); - return false; - } - } - - return true; -} - - -bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, int nvp, rcPolyMesh& mesh) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_POLYMESH); - - rcVcopy(mesh.bmin, cset.bmin); - rcVcopy(mesh.bmax, cset.bmax); - mesh.cs = cset.cs; - mesh.ch = cset.ch; - - int maxVertices = 0; - int maxTris = 0; - int maxVertsPerCont = 0; - for (int i = 0; i < cset.nconts; ++i) - { - // Skip null contours. - if (cset.conts[i].nverts < 3) continue; - maxVertices += cset.conts[i].nverts; - maxTris += cset.conts[i].nverts - 2; - maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts); - } - - if (maxVertices >= 0xfffe) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices); - return false; - } - - rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP); - if (!vflags) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices); - return false; - } - memset(vflags, 0, maxVertices); - - mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM); - if (!mesh.verts) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices); - return false; - } - mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2*2, RC_ALLOC_PERM); - if (!mesh.polys) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2); - return false; - } - mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM); - if (!mesh.regs) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris); - return false; - } - mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM); - if (!mesh.areas) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris); - return false; - } - - mesh.nverts = 0; - mesh.npolys = 0; - mesh.nvp = nvp; - mesh.maxpolys = maxTris; - - memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3); - memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2); - memset(mesh.regs, 0, sizeof(unsigned short)*maxTris); - memset(mesh.areas, 0, sizeof(unsigned char)*maxTris); - - rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP); - if (!nextVert) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices); - return false; - } - memset(nextVert, 0, sizeof(int)*maxVertices); - - rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP); - if (!firstVert) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT); - return false; - } - for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i) - firstVert[i] = -1; - - rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP); - if (!indices) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont); - return false; - } - rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP); - if (!tris) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3); - return false; - } - rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP); - if (!polys) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp); - return false; - } - unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp]; - - for (int i = 0; i < cset.nconts; ++i) - { - rcContour& cont = cset.conts[i]; - - // Skip null contours. - if (cont.nverts < 3) - continue; - - // Triangulate contour - for (int j = 0; j < cont.nverts; ++j) - indices[j] = j; - - int ntris = triangulate(cont.nverts, cont.verts, &indices[0], &tris[0]); - if (ntris <= 0) - { - // Bad triangulation, should not happen. -/* printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]); - printf("\tconst float cs = %ff;\n", cset.cs); - printf("\tconst float ch = %ff;\n", cset.ch); - printf("\tconst int verts[] = {\n"); - for (int k = 0; k < cont.nverts; ++k) - { - const int* v = &cont.verts[k*4]; - printf("\t\t%d,%d,%d,%d,\n", v[0], v[1], v[2], v[3]); - } - printf("\t};\n\tconst int nverts = sizeof(verts)/(sizeof(int)*4);\n");*/ - ctx->log(RC_LOG_WARNING, "rcBuildPolyMesh: Bad triangulation Contour %d.", i); - ntris = -ntris; - } - - // Add and merge vertices. - for (int j = 0; j < cont.nverts; ++j) - { - const int* v = &cont.verts[j*4]; - indices[j] = addVertex((unsigned short)v[0], (unsigned short)v[1], (unsigned short)v[2], - mesh.verts, firstVert, nextVert, mesh.nverts); - if (v[3] & RC_BORDER_VERTEX) - { - // This vertex should be removed. - vflags[indices[j]] = 1; - } - } - - // Build initial polygons. - int npolys = 0; - memset(polys, 0xff, maxVertsPerCont*nvp*sizeof(unsigned short)); - for (int j = 0; j < ntris; ++j) - { - int* t = &tris[j*3]; - if (t[0] != t[1] && t[0] != t[2] && t[1] != t[2]) - { - polys[npolys*nvp+0] = (unsigned short)indices[t[0]]; - polys[npolys*nvp+1] = (unsigned short)indices[t[1]]; - polys[npolys*nvp+2] = (unsigned short)indices[t[2]]; - npolys++; - } - } - if (!npolys) - continue; - - // Merge polygons. - if (nvp > 3) - { - for(;;) - { - // Find best polygons to merge. - int bestMergeVal = 0; - int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0; - - for (int j = 0; j < npolys-1; ++j) - { - unsigned short* pj = &polys[j*nvp]; - for (int k = j+1; k < npolys; ++k) - { - unsigned short* pk = &polys[k*nvp]; - int ea, eb; - int v = getPolyMergeValue(pj, pk, mesh.verts, ea, eb, nvp); - if (v > bestMergeVal) - { - bestMergeVal = v; - bestPa = j; - bestPb = k; - bestEa = ea; - bestEb = eb; - } - } - } - - if (bestMergeVal > 0) - { - // Found best, merge. - unsigned short* pa = &polys[bestPa*nvp]; - unsigned short* pb = &polys[bestPb*nvp]; - mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp); - memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp); - npolys--; - } - else - { - // Could not merge any polygons, stop. - break; - } - } - } - - // Store polygons. - for (int j = 0; j < npolys; ++j) - { - unsigned short* p = &mesh.polys[mesh.npolys*nvp*2]; - unsigned short* q = &polys[j*nvp]; - for (int k = 0; k < nvp; ++k) - p[k] = q[k]; - mesh.regs[mesh.npolys] = cont.reg; - mesh.areas[mesh.npolys] = cont.area; - mesh.npolys++; - if (mesh.npolys > maxTris) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many polygons %d (max:%d).", mesh.npolys, maxTris); - return false; - } - } - } - - - // Remove edge vertices. - for (int i = 0; i < mesh.nverts; ++i) - { - if (vflags[i]) - { - if (!canRemoveVertex(ctx, mesh, (unsigned short)i)) - continue; - if (!removeVertex(ctx, mesh, (unsigned short)i, maxTris)) - { - // Failed to remove vertex - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Failed to remove edge vertex %d.", i); - return false; - } - // Remove vertex - // Note: mesh.nverts is already decremented inside removeVertex()! - for (int j = i; j < mesh.nverts; ++j) - vflags[j] = vflags[j+1]; - --i; - } - } - - // Calculate adjacency. - if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, nvp)) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Adjacency failed."); - return false; - } - - // Just allocate the mesh flags array. The user is resposible to fill it. - mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*mesh.npolys, RC_ALLOC_PERM); - if (!mesh.flags) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.flags' (%d).", mesh.npolys); - return false; - } - memset(mesh.flags, 0, sizeof(unsigned short) * mesh.npolys); - - if (mesh.nverts > 0xffff) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff); - } - if (mesh.npolys > 0xffff) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff); - } - - ctx->stopTimer(RC_TIMER_BUILD_POLYMESH); - - return true; -} - -bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh) -{ - rcAssert(ctx); - - if (!nmeshes || !meshes) - return true; - - ctx->startTimer(RC_TIMER_MERGE_POLYMESH); - - mesh.nvp = meshes[0]->nvp; - mesh.cs = meshes[0]->cs; - mesh.ch = meshes[0]->ch; - rcVcopy(mesh.bmin, meshes[0]->bmin); - rcVcopy(mesh.bmax, meshes[0]->bmax); - - int maxVerts = 0; - int maxPolys = 0; - int maxVertsPerMesh = 0; - for (int i = 0; i < nmeshes; ++i) - { - rcVmin(mesh.bmin, meshes[i]->bmin); - rcVmax(mesh.bmax, meshes[i]->bmax); - maxVertsPerMesh = rcMax(maxVertsPerMesh, meshes[i]->nverts); - maxVerts += meshes[i]->nverts; - maxPolys += meshes[i]->npolys; - } - - mesh.nverts = 0; - mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVerts*3, RC_ALLOC_PERM); - if (!mesh.verts) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.verts' (%d).", maxVerts*3); - return false; - } - - mesh.npolys = 0; - mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys*2*mesh.nvp, RC_ALLOC_PERM); - if (!mesh.polys) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.polys' (%d).", maxPolys*2*mesh.nvp); - return false; - } - memset(mesh.polys, 0xff, sizeof(unsigned short)*maxPolys*2*mesh.nvp); - - mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM); - if (!mesh.regs) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.regs' (%d).", maxPolys); - return false; - } - memset(mesh.regs, 0, sizeof(unsigned short)*maxPolys); - - mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxPolys, RC_ALLOC_PERM); - if (!mesh.areas) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.areas' (%d).", maxPolys); - return false; - } - memset(mesh.areas, 0, sizeof(unsigned char)*maxPolys); - - mesh.flags = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxPolys, RC_ALLOC_PERM); - if (!mesh.flags) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'mesh.flags' (%d).", maxPolys); - return false; - } - memset(mesh.flags, 0, sizeof(unsigned short)*maxPolys); - - rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVerts, RC_ALLOC_TEMP); - if (!nextVert) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'nextVert' (%d).", maxVerts); - return false; - } - memset(nextVert, 0, sizeof(int)*maxVerts); - - rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP); - if (!firstVert) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT); - return false; - } - for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i) - firstVert[i] = -1; - - rcScopedDelete<unsigned short> vremap = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertsPerMesh, RC_ALLOC_PERM); - if (!vremap) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Out of memory 'vremap' (%d).", maxVertsPerMesh); - return false; - } - memset(vremap, 0, sizeof(unsigned short)*maxVertsPerMesh); - - for (int i = 0; i < nmeshes; ++i) - { - const rcPolyMesh* pmesh = meshes[i]; - - const unsigned short ox = (unsigned short)floorf((pmesh->bmin[0]-mesh.bmin[0])/mesh.cs+0.5f); - const unsigned short oz = (unsigned short)floorf((pmesh->bmin[2]-mesh.bmin[2])/mesh.cs+0.5f); - - for (int j = 0; j < pmesh->nverts; ++j) - { - unsigned short* v = &pmesh->verts[j*3]; - vremap[j] = addVertex(v[0]+ox, v[1], v[2]+oz, - mesh.verts, firstVert, nextVert, mesh.nverts); - } - - for (int j = 0; j < pmesh->npolys; ++j) - { - unsigned short* tgt = &mesh.polys[mesh.npolys*2*mesh.nvp]; - unsigned short* src = &pmesh->polys[j*2*mesh.nvp]; - mesh.regs[mesh.npolys] = pmesh->regs[j]; - mesh.areas[mesh.npolys] = pmesh->areas[j]; - mesh.flags[mesh.npolys] = pmesh->flags[j]; - mesh.npolys++; - for (int k = 0; k < mesh.nvp; ++k) - { - if (src[k] == RC_MESH_NULL_IDX) break; - tgt[k] = vremap[src[k]]; - } - } - } - - // Calculate adjacency. - if (!buildMeshAdjacency(mesh.polys, mesh.npolys, mesh.nverts, mesh.nvp)) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: Adjacency failed."); - return false; - } - - if (mesh.nverts > 0xffff) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many vertices %d (max %d). Data can be corrupted.", mesh.nverts, 0xffff); - } - if (mesh.npolys > 0xffff) - { - ctx->log(RC_LOG_ERROR, "rcMergePolyMeshes: The resulting mesh has too many polygons %d (max %d). Data can be corrupted.", mesh.npolys, 0xffff); - } - - ctx->stopTimer(RC_TIMER_MERGE_POLYMESH); - - return true; -} diff --git a/deps/recastnavigation/Recast/RecastMeshDetail.cpp b/deps/recastnavigation/Recast/RecastMeshDetail.cpp deleted file mode 100644 index ffb4b58ee9..0000000000 --- a/deps/recastnavigation/Recast/RecastMeshDetail.cpp +++ /dev/null @@ -1,1237 +0,0 @@ -// -// 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 <float.h> -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdlib.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - - -static const unsigned RC_UNSET_HEIGHT = 0xffff; - -struct rcHeightPatch -{ - inline rcHeightPatch() : data(0), xmin(0), ymin(0), width(0), height(0) {} - inline ~rcHeightPatch() { rcFree(data); } - unsigned short* data; - int xmin, ymin, width, height; -}; - - -inline float vdot2(const float* a, const float* b) -{ - return a[0]*b[0] + a[2]*b[2]; -} - -inline float vdistSq2(const float* p, const float* q) -{ - const float dx = q[0] - p[0]; - const float dy = q[2] - p[2]; - return dx*dx + dy*dy; -} - -inline float vdist2(const float* p, const float* q) -{ - return sqrtf(vdistSq2(p,q)); -} - -inline float vcross2(const float* p1, const float* p2, const float* p3) -{ - const float u1 = p2[0] - p1[0]; - const float v1 = p2[2] - p1[2]; - const float u2 = p3[0] - p1[0]; - const float v2 = p3[2] - p1[2]; - return u1 * v2 - v1 * u2; -} - -static bool circumCircle(const float* p1, const float* p2, const float* p3, - float* c, float& r) -{ - static const float EPS = 1e-6f; - - const float cp = vcross2(p1, p2, p3); - if (fabsf(cp) > EPS) - { - const float p1Sq = vdot2(p1,p1); - const float p2Sq = vdot2(p2,p2); - const float p3Sq = vdot2(p3,p3); - c[0] = (p1Sq*(p2[2]-p3[2]) + p2Sq*(p3[2]-p1[2]) + p3Sq*(p1[2]-p2[2])) / (2*cp); - c[2] = (p1Sq*(p3[0]-p2[0]) + p2Sq*(p1[0]-p3[0]) + p3Sq*(p2[0]-p1[0])) / (2*cp); - r = vdist2(c, p1); - return true; - } - - c[0] = p1[0]; - c[2] = p1[2]; - r = 0; - return false; -} - -static float distPtTri(const float* p, const float* a, const float* b, const float* c) -{ - float v0[3], v1[3], v2[3]; - rcVsub(v0, c,a); - rcVsub(v1, b,a); - rcVsub(v2, p,a); - - const float dot00 = vdot2(v0, v0); - const float dot01 = vdot2(v0, v1); - const float dot02 = vdot2(v0, v2); - const float dot11 = vdot2(v1, v1); - const float dot12 = vdot2(v1, v2); - - // Compute barycentric coordinates - const float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01); - const float u = (dot11 * dot02 - dot01 * dot12) * invDenom; - float v = (dot00 * dot12 - dot01 * dot02) * invDenom; - - // If point lies inside the triangle, return interpolated y-coord. - static const float EPS = 1e-4f; - if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS) - { - const float y = a[1] + v0[1]*u + v1[1]*v; - return fabsf(y-p[1]); - } - return FLT_MAX; -} - -static float distancePtSeg(const float* pt, const float* p, const float* q) -{ - float pqx = q[0] - p[0]; - float pqy = q[1] - p[1]; - float pqz = q[2] - p[2]; - float dx = pt[0] - p[0]; - float dy = pt[1] - p[1]; - float dz = pt[2] - p[2]; - float d = pqx*pqx + pqy*pqy + pqz*pqz; - float t = pqx*dx + pqy*dy + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = p[0] + t*pqx - pt[0]; - dy = p[1] + t*pqy - pt[1]; - dz = p[2] + t*pqz - pt[2]; - - return dx*dx + dy*dy + dz*dz; -} - -static float distancePtSeg2d(const float* pt, const float* p, const float* q) -{ - float pqx = q[0] - p[0]; - float pqz = q[2] - p[2]; - float dx = pt[0] - p[0]; - float dz = pt[2] - p[2]; - float d = pqx*pqx + pqz*pqz; - float t = pqx*dx + pqz*dz; - if (d > 0) - t /= d; - if (t < 0) - t = 0; - else if (t > 1) - t = 1; - - dx = p[0] + t*pqx - pt[0]; - dz = p[2] + t*pqz - pt[2]; - - return dx*dx + dz*dz; -} - -static float distToTriMesh(const float* p, const float* verts, const int /*nverts*/, const int* tris, const int ntris) -{ - float dmin = FLT_MAX; - for (int i = 0; i < ntris; ++i) - { - const float* va = &verts[tris[i*4+0]*3]; - const float* vb = &verts[tris[i*4+1]*3]; - const float* vc = &verts[tris[i*4+2]*3]; - float d = distPtTri(p, va,vb,vc); - if (d < dmin) - dmin = d; - } - if (dmin == FLT_MAX) return -1; - return dmin; -} - -static float distToPoly(int nvert, const float* verts, const float* p) -{ - - float dmin = FLT_MAX; - int i, j, c = 0; - for (i = 0, j = nvert-1; i < nvert; j = i++) - { - const float* vi = &verts[i*3]; - const float* vj = &verts[j*3]; - if (((vi[2] > p[2]) != (vj[2] > p[2])) && - (p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) ) - c = !c; - dmin = rcMin(dmin, distancePtSeg2d(p, vj, vi)); - } - return c ? -dmin : dmin; -} - - -static unsigned short getHeight(const float fx, const float fy, const float fz, - const float /*cs*/, const float ics, const float ch, - const rcHeightPatch& hp) -{ - int ix = (int)floorf(fx*ics + 0.01f); - int iz = (int)floorf(fz*ics + 0.01f); - ix = rcClamp(ix-hp.xmin, 0, hp.width); - iz = rcClamp(iz-hp.ymin, 0, hp.height); - unsigned short h = hp.data[ix+iz*hp.width]; - if (h == RC_UNSET_HEIGHT) - { - // Special case when data might be bad. - // Find nearest neighbour pixel which has valid height. - const int off[8*2] = { -1,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1}; - float dmin = FLT_MAX; - for (int i = 0; i < 8; ++i) - { - const int nx = ix+off[i*2+0]; - const int nz = iz+off[i*2+1]; - if (nx < 0 || nz < 0 || nx >= hp.width || nz >= hp.height) continue; - const unsigned short nh = hp.data[nx+nz*hp.width]; - if (nh == RC_UNSET_HEIGHT) continue; - - const float d = fabsf(nh*ch - fy); - if (d < dmin) - { - h = nh; - dmin = d; - } - -/* const float dx = (nx+0.5f)*cs - fx; - const float dz = (nz+0.5f)*cs - fz; - const float d = dx*dx+dz*dz; - if (d < dmin) - { - h = nh; - dmin = d; - } */ - } - } - return h; -} - - -enum EdgeValues -{ - UNDEF = -1, - HULL = -2, -}; - -static int findEdge(const int* edges, int nedges, int s, int t) -{ - for (int i = 0; i < nedges; i++) - { - const int* e = &edges[i*4]; - if ((e[0] == s && e[1] == t) || (e[0] == t && e[1] == s)) - return i; - } - return UNDEF; -} - -static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r) -{ - if (nedges >= maxEdges) - { - ctx->log(RC_LOG_ERROR, "addEdge: Too many edges (%d/%d).", nedges, maxEdges); - return UNDEF; - } - - // Add edge if not already in the triangulation. - int e = findEdge(edges, nedges, s, t); - if (e == UNDEF) - { - int* e = &edges[nedges*4]; - e[0] = s; - e[1] = t; - e[2] = l; - e[3] = r; - return nedges++; - } - else - { - return UNDEF; - } -} - -static void updateLeftFace(int* e, int s, int t, int f) -{ - if (e[0] == s && e[1] == t && e[2] == UNDEF) - e[2] = f; - else if (e[1] == s && e[0] == t && e[3] == UNDEF) - e[3] = f; -} - -static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d) -{ - const float a1 = vcross2(a, b, d); - const float a2 = vcross2(a, b, c); - if (a1*a2 < 0.0f) - { - float a3 = vcross2(c, d, a); - float a4 = a3 + a2 - a1; - if (a3 * a4 < 0.0f) - return 1; - } - return 0; -} - -static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, int t1) -{ - for (int i = 0; i < nedges; ++i) - { - const int s0 = edges[i*4+0]; - const int t0 = edges[i*4+1]; - // Same or connected edges do not overlap. - if (s0 == s1 || s0 == t1 || t0 == s1 || t0 == t1) - continue; - if (overlapSegSeg2d(&pts[s0*3],&pts[t0*3], &pts[s1*3],&pts[t1*3])) - return true; - } - return false; -} - -static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e) -{ - static const float EPS = 1e-5f; - - int* edge = &edges[e*4]; - - // Cache s and t. - int s,t; - if (edge[2] == UNDEF) - { - s = edge[0]; - t = edge[1]; - } - else if (edge[3] == UNDEF) - { - s = edge[1]; - t = edge[0]; - } - else - { - // Edge already completed. - return; - } - - // Find best point on left of edge. - int pt = npts; - float c[3] = {0,0,0}; - float r = -1; - for (int u = 0; u < npts; ++u) - { - if (u == s || u == t) continue; - if (vcross2(&pts[s*3], &pts[t*3], &pts[u*3]) > EPS) - { - if (r < 0) - { - // The circle is not updated yet, do it now. - pt = u; - circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r); - continue; - } - const float d = vdist2(c, &pts[u*3]); - const float tol = 0.001f; - if (d > r*(1+tol)) - { - // Outside current circumcircle, skip. - continue; - } - else if (d < r*(1-tol)) - { - // Inside safe circumcircle, update circle. - pt = u; - circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r); - } - else - { - // Inside epsilon circum circle, do extra tests to make sure the edge is valid. - // s-u and t-u cannot overlap with s-pt nor t-pt if they exists. - if (overlapEdges(pts, edges, nedges, s,u)) - continue; - if (overlapEdges(pts, edges, nedges, t,u)) - continue; - // Edge is valid. - pt = u; - circumCircle(&pts[s*3], &pts[t*3], &pts[u*3], c, r); - } - } - } - - // Add new triangle or update edge info if s-t is on hull. - if (pt < npts) - { - // Update face information of edge being completed. - updateLeftFace(&edges[e*4], s, t, nfaces); - - // Add new edge or update face info of old edge. - e = findEdge(edges, nedges, pt, s); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, pt, s, nfaces, UNDEF); - else - updateLeftFace(&edges[e*4], pt, s, nfaces); - - // Add new edge or update face info of old edge. - e = findEdge(edges, nedges, t, pt); - if (e == UNDEF) - addEdge(ctx, edges, nedges, maxEdges, t, pt, nfaces, UNDEF); - else - updateLeftFace(&edges[e*4], t, pt, nfaces); - - nfaces++; - } - else - { - updateLeftFace(&edges[e*4], s, t, HULL); - } -} - -static void delaunayHull(rcContext* ctx, const int npts, const float* pts, - const int nhull, const int* hull, - rcIntArray& tris, rcIntArray& edges) -{ - int nfaces = 0; - int nedges = 0; - const int maxEdges = npts*10; - edges.resize(maxEdges*4); - - for (int i = 0, j = nhull-1; i < nhull; j=i++) - addEdge(ctx, &edges[0], nedges, maxEdges, hull[j],hull[i], HULL, UNDEF); - - int currentEdge = 0; - while (currentEdge < nedges) - { - if (edges[currentEdge*4+2] == UNDEF) - completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); - if (edges[currentEdge*4+3] == UNDEF) - completeFacet(ctx, pts, npts, &edges[0], nedges, maxEdges, nfaces, currentEdge); - currentEdge++; - } - - // Create tris - tris.resize(nfaces*4); - for (int i = 0; i < nfaces*4; ++i) - tris[i] = -1; - - for (int i = 0; i < nedges; ++i) - { - const int* e = &edges[i*4]; - if (e[3] >= 0) - { - // Left face - int* t = &tris[e[3]*4]; - if (t[0] == -1) - { - t[0] = e[0]; - t[1] = e[1]; - } - else if (t[0] == e[1]) - t[2] = e[0]; - else if (t[1] == e[0]) - t[2] = e[1]; - } - if (e[2] >= 0) - { - // Right - int* t = &tris[e[2]*4]; - if (t[0] == -1) - { - t[0] = e[1]; - t[1] = e[0]; - } - else if (t[0] == e[0]) - t[2] = e[1]; - else if (t[1] == e[1]) - t[2] = e[0]; - } - } - - for (int i = 0; i < tris.size()/4; ++i) - { - int* t = &tris[i*4]; - if (t[0] == -1 || t[1] == -1 || t[2] == -1) - { - ctx->log(RC_LOG_WARNING, "delaunayHull: Removing dangling face %d [%d,%d,%d].", i, t[0],t[1],t[2]); - t[0] = tris[tris.size()-4]; - t[1] = tris[tris.size()-3]; - t[2] = tris[tris.size()-2]; - t[3] = tris[tris.size()-1]; - tris.resize(tris.size()-4); - --i; - } - } -} - - -inline float getJitterX(const int i) -{ - return (((i * 0x8da6b343) & 0xffff) / 65535.0f * 2.0f) - 1.0f; -} - -inline float getJitterY(const int i) -{ - return (((i * 0xd8163841) & 0xffff) / 65535.0f * 2.0f) - 1.0f; -} - -static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin, - const float sampleDist, const float sampleMaxError, - const rcCompactHeightfield& chf, const rcHeightPatch& hp, - float* verts, int& nverts, rcIntArray& tris, - rcIntArray& edges, rcIntArray& samples) -{ - static const int MAX_VERTS = 127; - static const int MAX_TRIS = 255; // Max tris for delaunay is 2n-2-k (n=num verts, k=num hull verts). - static const int MAX_VERTS_PER_EDGE = 32; - float edge[(MAX_VERTS_PER_EDGE+1)*3]; - int hull[MAX_VERTS]; - int nhull = 0; - - nverts = 0; - - for (int i = 0; i < nin; ++i) - rcVcopy(&verts[i*3], &in[i*3]); - nverts = nin; - - const float cs = chf.cs; - const float ics = 1.0f/cs; - - // Tessellate outlines. - // This is done in separate pass in order to ensure - // seamless height values across the ply boundaries. - if (sampleDist > 0) - { - for (int i = 0, j = nin-1; i < nin; j=i++) - { - const float* vj = &in[j*3]; - const float* vi = &in[i*3]; - bool swapped = false; - // Make sure the segments are always handled in same order - // using lexological sort or else there will be seams. - if (fabsf(vj[0]-vi[0]) < 1e-6f) - { - if (vj[2] > vi[2]) - { - rcSwap(vj,vi); - swapped = true; - } - } - else - { - if (vj[0] > vi[0]) - { - rcSwap(vj,vi); - swapped = true; - } - } - // Create samples along the edge. - float dx = vi[0] - vj[0]; - float dy = vi[1] - vj[1]; - float dz = vi[2] - vj[2]; - float d = sqrtf(dx*dx + dz*dz); - int nn = 1 + (int)floorf(d/sampleDist); - if (nn >= MAX_VERTS_PER_EDGE) nn = MAX_VERTS_PER_EDGE-1; - if (nverts+nn >= MAX_VERTS) - nn = MAX_VERTS-1-nverts; - - for (int k = 0; k <= nn; ++k) - { - float u = (float)k/(float)nn; - float* pos = &edge[k*3]; - pos[0] = vj[0] + dx*u; - pos[1] = vj[1] + dy*u; - pos[2] = vj[2] + dz*u; - pos[1] = getHeight(pos[0],pos[1],pos[2], cs, ics, chf.ch, hp)*chf.ch; - } - // Simplify samples. - int idx[MAX_VERTS_PER_EDGE] = {0,nn}; - int nidx = 2; - for (int k = 0; k < nidx-1; ) - { - const int a = idx[k]; - const int b = idx[k+1]; - const float* va = &edge[a*3]; - const float* vb = &edge[b*3]; - // Find maximum deviation along the segment. - float maxd = 0; - int maxi = -1; - for (int m = a+1; m < b; ++m) - { - float d = distancePtSeg(&edge[m*3],va,vb); - if (d > maxd) - { - maxd = d; - maxi = m; - } - } - // If the max deviation is larger than accepted error, - // add new point, else continue to next segment. - if (maxi != -1 && maxd > rcSqr(sampleMaxError)) - { - for (int m = nidx; m > k; --m) - idx[m] = idx[m-1]; - idx[k+1] = maxi; - nidx++; - } - else - { - ++k; - } - } - - hull[nhull++] = j; - // Add new vertices. - if (swapped) - { - for (int k = nidx-2; k > 0; --k) - { - rcVcopy(&verts[nverts*3], &edge[idx[k]*3]); - hull[nhull++] = nverts; - nverts++; - } - } - else - { - for (int k = 1; k < nidx-1; ++k) - { - rcVcopy(&verts[nverts*3], &edge[idx[k]*3]); - hull[nhull++] = nverts; - nverts++; - } - } - } - } - - - // Tessellate the base mesh. - edges.resize(0); - tris.resize(0); - - delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); - - if (tris.size() == 0) - { - // Could not triangulate the poly, make sure there is some valid data there. - ctx->log(RC_LOG_WARNING, "buildPolyDetail: Could not triangulate polygon, adding default data."); - for (int i = 2; i < nverts; ++i) - { - tris.push(0); - tris.push(i-1); - tris.push(i); - tris.push(0); - } - return true; - } - - if (sampleDist > 0) - { - // Create sample locations in a grid. - float bmin[3], bmax[3]; - rcVcopy(bmin, in); - rcVcopy(bmax, in); - for (int i = 1; i < nin; ++i) - { - rcVmin(bmin, &in[i*3]); - rcVmax(bmax, &in[i*3]); - } - int x0 = (int)floorf(bmin[0]/sampleDist); - int x1 = (int)ceilf(bmax[0]/sampleDist); - int z0 = (int)floorf(bmin[2]/sampleDist); - int z1 = (int)ceilf(bmax[2]/sampleDist); - samples.resize(0); - for (int z = z0; z < z1; ++z) - { - for (int x = x0; x < x1; ++x) - { - float pt[3]; - pt[0] = x*sampleDist; - pt[1] = (bmax[1]+bmin[1])*0.5f; - pt[2] = z*sampleDist; - // Make sure the samples are not too close to the edges. - if (distToPoly(nin,in,pt) > -sampleDist/2) continue; - samples.push(x); - samples.push(getHeight(pt[0], pt[1], pt[2], cs, ics, chf.ch, hp)); - samples.push(z); - samples.push(0); // Not added - } - } - - // Add the samples starting from the one that has the most - // error. The procedure stops when all samples are added - // or when the max error is within treshold. - const int nsamples = samples.size()/4; - for (int iter = 0; iter < nsamples; ++iter) - { - if (nverts >= MAX_VERTS) - break; - - // Find sample with most error. - float bestpt[3] = {0,0,0}; - float bestd = 0; - int besti = -1; - for (int i = 0; i < nsamples; ++i) - { - const int* s = &samples[i*4]; - if (s[3]) continue; // skip added. - float pt[3]; - // The sample location is jittered to get rid of some bad triangulations - // which are cause by symmetrical data from the grid structure. - pt[0] = s[0]*sampleDist + getJitterX(i)*cs*0.1f; - pt[1] = s[1]*chf.ch; - pt[2] = s[2]*sampleDist + getJitterY(i)*cs*0.1f; - float d = distToTriMesh(pt, verts, nverts, &tris[0], tris.size()/4); - if (d < 0) continue; // did not hit the mesh. - if (d > bestd) - { - bestd = d; - besti = i; - rcVcopy(bestpt,pt); - } - } - // If the max error is within accepted threshold, stop tesselating. - if (bestd <= sampleMaxError || besti == -1) - break; - // Mark sample as added. - samples[besti*4+3] = 1; - // Add the new sample point. - rcVcopy(&verts[nverts*3],bestpt); - nverts++; - - // Create new triangulation. - // TODO: Incremental add instead of full rebuild. - edges.resize(0); - tris.resize(0); - delaunayHull(ctx, nverts, verts, nhull, hull, tris, edges); - } - } - - const int ntris = tris.size()/4; - if (ntris > MAX_TRIS) - { - tris.resize(MAX_TRIS*4); - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Shrinking triangle count from %d to max %d.", ntris, MAX_TRIS); - } - - return true; -} - -static void getHeightData(const rcCompactHeightfield& chf, - const unsigned short* poly, const int npoly, - const unsigned short* verts, - rcHeightPatch& hp, rcIntArray& stack) -{ - // Floodfill the heightfield to get 2D height data, - // starting at vertex locations as seeds. - - memset(hp.data, 0, sizeof(unsigned short)*hp.width*hp.height); - - stack.resize(0); - - static const int offset[9*2] = - { - 0,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1, -1,0, - }; - - // Use poly vertices as seed points for the flood fill. - for (int j = 0; j < npoly; ++j) - { - int cx = 0, cz = 0, ci =-1; - int dmin = RC_UNSET_HEIGHT; - for (int k = 0; k < 9; ++k) - { - const int ax = (int)verts[poly[j]*3+0] + offset[k*2+0]; - const int ay = (int)verts[poly[j]*3+1]; - const int az = (int)verts[poly[j]*3+2] + offset[k*2+1]; - if (ax < hp.xmin || ax >= hp.xmin+hp.width || - az < hp.ymin || az >= hp.ymin+hp.height) - continue; - - const rcCompactCell& c = chf.cells[ax+az*chf.width]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - int d = rcAbs(ay - (int)s.y); - if (d < dmin) - { - cx = ax; - cz = az; - ci = i; - dmin = d; - } - } - } - if (ci != -1) - { - stack.push(cx); - stack.push(cz); - stack.push(ci); - } - } - - // Find center of the polygon using flood fill. - int pcx = 0, pcz = 0; - for (int j = 0; j < npoly; ++j) - { - pcx += (int)verts[poly[j]*3+0]; - pcz += (int)verts[poly[j]*3+2]; - } - pcx /= npoly; - pcz /= npoly; - - for (int i = 0; i < stack.size(); i += 3) - { - int cx = stack[i+0]; - int cy = stack[i+1]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - hp.data[idx] = 1; - } - - while (stack.size() > 0) - { - int ci = stack.pop(); - int cy = stack.pop(); - int cx = stack.pop(); - - // Check if close to center of the polygon. - if (rcAbs(cx-pcx) <= 1 && rcAbs(cy-pcz) <= 1) - { - stack.resize(0); - stack.push(cx); - stack.push(cy); - stack.push(ci); - break; - } - - const rcCompactSpan& cs = chf.spans[ci]; - - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - - if (ax < hp.xmin || ax >= (hp.xmin+hp.width) || - ay < hp.ymin || ay >= (hp.ymin+hp.height)) - continue; - - if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != 0) - continue; - - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(cs, dir); - - int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width; - hp.data[idx] = 1; - - stack.push(ax); - stack.push(ay); - stack.push(ai); - } - } - - memset(hp.data, 0xff, sizeof(unsigned short)*hp.width*hp.height); - - // Mark start locations. - for (int i = 0; i < stack.size(); i += 3) - { - int cx = stack[i+0]; - int cy = stack[i+1]; - int ci = stack[i+2]; - int idx = cx-hp.xmin+(cy-hp.ymin)*hp.width; - const rcCompactSpan& cs = chf.spans[ci]; - hp.data[idx] = cs.y; - } - - static const int RETRACT_SIZE = 256; - int head = 0; - - while (head*3 < stack.size()) - { - int cx = stack[head*3+0]; - int cy = stack[head*3+1]; - int ci = stack[head*3+2]; - head++; - if (head >= RETRACT_SIZE) - { - head = 0; - if (stack.size() > RETRACT_SIZE*3) - memmove(&stack[0], &stack[RETRACT_SIZE*3], sizeof(int)*(stack.size()-RETRACT_SIZE*3)); - stack.resize(stack.size()-RETRACT_SIZE*3); - } - - const rcCompactSpan& cs = chf.spans[ci]; - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(cs, dir) == RC_NOT_CONNECTED) continue; - - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - - if (ax < hp.xmin || ax >= (hp.xmin+hp.width) || - ay < hp.ymin || ay >= (hp.ymin+hp.height)) - continue; - - if (hp.data[ax-hp.xmin+(ay-hp.ymin)*hp.width] != RC_UNSET_HEIGHT) - continue; - - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(cs, dir); - - const rcCompactSpan& as = chf.spans[ai]; - int idx = ax-hp.xmin+(ay-hp.ymin)*hp.width; - hp.data[idx] = as.y; - - stack.push(ax); - stack.push(ay); - stack.push(ai); - } - } - -} - -static unsigned char getEdgeFlags(const float* va, const float* vb, - const float* vpoly, const int npoly) -{ - // Return true if edge (va,vb) is part of the polygon. - static const float thrSqr = rcSqr(0.001f); - for (int i = 0, j = npoly-1; i < npoly; j=i++) - { - if (distancePtSeg2d(va, &vpoly[j*3], &vpoly[i*3]) < thrSqr && - distancePtSeg2d(vb, &vpoly[j*3], &vpoly[i*3]) < thrSqr) - return 1; - } - return 0; -} - -static unsigned char getTriFlags(const float* va, const float* vb, const float* vc, - const float* vpoly, const int npoly) -{ - unsigned char flags = 0; - flags |= getEdgeFlags(va,vb,vpoly,npoly) << 0; - flags |= getEdgeFlags(vb,vc,vpoly,npoly) << 2; - flags |= getEdgeFlags(vc,va,vpoly,npoly) << 4; - return flags; -} - - - -bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf, - const float sampleDist, const float sampleMaxError, - rcPolyMeshDetail& dmesh) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - - if (mesh.nverts == 0 || mesh.npolys == 0) - return true; - - const int nvp = mesh.nvp; - const float cs = mesh.cs; - const float ch = mesh.ch; - const float* orig = mesh.bmin; - - rcIntArray edges(64); - rcIntArray tris(512); - rcIntArray stack(512); - rcIntArray samples(512); - float verts[256*3]; - rcHeightPatch hp; - int nPolyVerts = 0; - int maxhw = 0, maxhh = 0; - - rcScopedDelete<int> bounds = (int*)rcAlloc(sizeof(int)*mesh.npolys*4, RC_ALLOC_TEMP); - if (!bounds) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'bounds' (%d).", mesh.npolys*4); - return false; - } - rcScopedDelete<float> poly = (float*)rcAlloc(sizeof(float)*nvp*3, RC_ALLOC_TEMP); - if (!poly) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'poly' (%d).", nvp*3); - return false; - } - - // Find max size for a polygon area. - for (int i = 0; i < mesh.npolys; ++i) - { - const unsigned short* p = &mesh.polys[i*nvp*2]; - int& xmin = bounds[i*4+0]; - int& xmax = bounds[i*4+1]; - int& ymin = bounds[i*4+2]; - int& ymax = bounds[i*4+3]; - xmin = chf.width; - xmax = 0; - ymin = chf.height; - ymax = 0; - for (int j = 0; j < nvp; ++j) - { - if(p[j] == RC_MESH_NULL_IDX) break; - const unsigned short* v = &mesh.verts[p[j]*3]; - xmin = rcMin(xmin, (int)v[0]); - xmax = rcMax(xmax, (int)v[0]); - ymin = rcMin(ymin, (int)v[2]); - ymax = rcMax(ymax, (int)v[2]); - nPolyVerts++; - } - xmin = rcMax(0,xmin-1); - xmax = rcMin(chf.width,xmax+1); - ymin = rcMax(0,ymin-1); - ymax = rcMin(chf.height,ymax+1); - if (xmin >= xmax || ymin >= ymax) continue; - maxhw = rcMax(maxhw, xmax-xmin); - maxhh = rcMax(maxhh, ymax-ymin); - } - - hp.data = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxhw*maxhh, RC_ALLOC_TEMP); - if (!hp.data) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'hp.data' (%d).", maxhw*maxhh); - return false; - } - - dmesh.nmeshes = mesh.npolys; - dmesh.nverts = 0; - dmesh.ntris = 0; - dmesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*dmesh.nmeshes*4, RC_ALLOC_PERM); - if (!dmesh.meshes) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.meshes' (%d).", dmesh.nmeshes*4); - return false; - } - - int vcap = nPolyVerts+nPolyVerts/2; - int tcap = vcap*2; - - dmesh.nverts = 0; - dmesh.verts = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); - if (!dmesh.verts) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", vcap*3); - return false; - } - dmesh.ntris = 0; - dmesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char*)*tcap*4, RC_ALLOC_PERM); - if (!dmesh.tris) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", tcap*4); - return false; - } - - for (int i = 0; i < mesh.npolys; ++i) - { - const unsigned short* p = &mesh.polys[i*nvp*2]; - - // Store polygon vertices for processing. - int npoly = 0; - for (int j = 0; j < nvp; ++j) - { - if(p[j] == RC_MESH_NULL_IDX) break; - const unsigned short* v = &mesh.verts[p[j]*3]; - poly[j*3+0] = v[0]*cs; - poly[j*3+1] = v[1]*ch; - poly[j*3+2] = v[2]*cs; - npoly++; - } - - // Get the height data from the area of the polygon. - hp.xmin = bounds[i*4+0]; - hp.ymin = bounds[i*4+2]; - hp.width = bounds[i*4+1]-bounds[i*4+0]; - hp.height = bounds[i*4+3]-bounds[i*4+2]; - getHeightData(chf, p, npoly, mesh.verts, hp, stack); - - // Build detail mesh. - int nverts = 0; - if (!buildPolyDetail(ctx, poly, npoly, - sampleDist, sampleMaxError, - chf, hp, verts, nverts, tris, - edges, samples)) - { - return false; - } - - // Move detail verts to world space. - for (int j = 0; j < nverts; ++j) - { - verts[j*3+0] += orig[0]; - verts[j*3+1] += orig[1] + chf.ch; // Is this offset necessary? - verts[j*3+2] += orig[2]; - } - // Offset poly too, will be used to flag checking. - for (int j = 0; j < npoly; ++j) - { - poly[j*3+0] += orig[0]; - poly[j*3+1] += orig[1]; - poly[j*3+2] += orig[2]; - } - - // Store detail submesh. - const int ntris = tris.size()/4; - - dmesh.meshes[i*4+0] = (unsigned int)dmesh.nverts; - dmesh.meshes[i*4+1] = (unsigned int)nverts; - dmesh.meshes[i*4+2] = (unsigned int)dmesh.ntris; - dmesh.meshes[i*4+3] = (unsigned int)ntris; - - // Store vertices, allocate more memory if necessary. - if (dmesh.nverts+nverts > vcap) - { - while (dmesh.nverts+nverts > vcap) - vcap += 256; - - float* newv = (float*)rcAlloc(sizeof(float)*vcap*3, RC_ALLOC_PERM); - if (!newv) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newv' (%d).", vcap*3); - return false; - } - if (dmesh.nverts) - memcpy(newv, dmesh.verts, sizeof(float)*3*dmesh.nverts); - rcFree(dmesh.verts); - dmesh.verts = newv; - } - for (int j = 0; j < nverts; ++j) - { - dmesh.verts[dmesh.nverts*3+0] = verts[j*3+0]; - dmesh.verts[dmesh.nverts*3+1] = verts[j*3+1]; - dmesh.verts[dmesh.nverts*3+2] = verts[j*3+2]; - dmesh.nverts++; - } - - // Store triangles, allocate more memory if necessary. - if (dmesh.ntris+ntris > tcap) - { - while (dmesh.ntris+ntris > tcap) - tcap += 256; - unsigned char* newt = (unsigned char*)rcAlloc(sizeof(unsigned char)*tcap*4, RC_ALLOC_PERM); - if (!newt) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'newt' (%d).", tcap*4); - return false; - } - if (dmesh.ntris) - memcpy(newt, dmesh.tris, sizeof(unsigned char)*4*dmesh.ntris); - rcFree(dmesh.tris); - dmesh.tris = newt; - } - for (int j = 0; j < ntris; ++j) - { - const int* t = &tris[j*4]; - dmesh.tris[dmesh.ntris*4+0] = (unsigned char)t[0]; - dmesh.tris[dmesh.ntris*4+1] = (unsigned char)t[1]; - dmesh.tris[dmesh.ntris*4+2] = (unsigned char)t[2]; - dmesh.tris[dmesh.ntris*4+3] = getTriFlags(&verts[t[0]*3], &verts[t[1]*3], &verts[t[2]*3], poly, npoly); - dmesh.ntris++; - } - } - - ctx->stopTimer(RC_TIMER_BUILD_POLYMESHDETAIL); - - return true; -} - -bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_MERGE_POLYMESHDETAIL); - - int maxVerts = 0; - int maxTris = 0; - int maxMeshes = 0; - - for (int i = 0; i < nmeshes; ++i) - { - if (!meshes[i]) continue; - maxVerts += meshes[i]->nverts; - maxTris += meshes[i]->ntris; - maxMeshes += meshes[i]->nmeshes; - } - - mesh.nmeshes = 0; - mesh.meshes = (unsigned int*)rcAlloc(sizeof(unsigned int)*maxMeshes*4, RC_ALLOC_PERM); - if (!mesh.meshes) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'pmdtl.meshes' (%d).", maxMeshes*4); - return false; - } - - mesh.ntris = 0; - mesh.tris = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris*4, RC_ALLOC_PERM); - if (!mesh.tris) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.tris' (%d).", maxTris*4); - return false; - } - - mesh.nverts = 0; - mesh.verts = (float*)rcAlloc(sizeof(float)*maxVerts*3, RC_ALLOC_PERM); - if (!mesh.verts) - { - ctx->log(RC_LOG_ERROR, "rcBuildPolyMeshDetail: Out of memory 'dmesh.verts' (%d).", maxVerts*3); - return false; - } - - // Merge datas. - for (int i = 0; i < nmeshes; ++i) - { - rcPolyMeshDetail* dm = meshes[i]; - if (!dm) continue; - for (int j = 0; j < dm->nmeshes; ++j) - { - unsigned int* dst = &mesh.meshes[mesh.nmeshes*4]; - unsigned int* src = &dm->meshes[j*4]; - dst[0] = (unsigned int)mesh.nverts+src[0]; - dst[1] = src[1]; - dst[2] = (unsigned int)mesh.ntris+src[2]; - dst[3] = src[3]; - mesh.nmeshes++; - } - - for (int k = 0; k < dm->nverts; ++k) - { - rcVcopy(&mesh.verts[mesh.nverts*3], &dm->verts[k*3]); - mesh.nverts++; - } - for (int k = 0; k < dm->ntris; ++k) - { - mesh.tris[mesh.ntris*4+0] = dm->tris[k*4+0]; - mesh.tris[mesh.ntris*4+1] = dm->tris[k*4+1]; - mesh.tris[mesh.ntris*4+2] = dm->tris[k*4+2]; - mesh.tris[mesh.ntris*4+3] = dm->tris[k*4+3]; - mesh.ntris++; - } - } - - ctx->stopTimer(RC_TIMER_MERGE_POLYMESHDETAIL); - - return true; -} - diff --git a/deps/recastnavigation/Recast/RecastRasterization.cpp b/deps/recastnavigation/Recast/RecastRasterization.cpp deleted file mode 100644 index 71adfb6732..0000000000 --- a/deps/recastnavigation/Recast/RecastRasterization.cpp +++ /dev/null @@ -1,360 +0,0 @@ -// -// 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. -// - -#define _USE_MATH_DEFINES -#include <math.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" - -inline bool overlapBounds(const float* amin, const float* amax, const float* bmin, const float* bmax) -{ - bool overlap = true; - overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap; - overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap; - overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap; - return overlap; -} - -inline bool overlapInterval(unsigned short amin, unsigned short amax, - unsigned short bmin, unsigned short bmax) -{ - if (amax < bmin) return false; - if (amin > bmax) return false; - return true; -} - - -static rcSpan* allocSpan(rcHeightfield& hf) -{ - // If running out of memory, allocate new page and update the freelist. - if (!hf.freelist || !hf.freelist->next) - { - // Create new page. - // Allocate memory for the new pool. - rcSpanPool* pool = (rcSpanPool*)rcAlloc(sizeof(rcSpanPool), RC_ALLOC_PERM); - if (!pool) return 0; - pool->next = 0; - // Add the pool into the list of pools. - pool->next = hf.pools; - hf.pools = pool; - // Add new items to the free list. - rcSpan* freelist = hf.freelist; - rcSpan* head = &pool->items[0]; - rcSpan* it = &pool->items[RC_SPANS_PER_POOL]; - do - { - --it; - it->next = freelist; - freelist = it; - } - while (it != head); - hf.freelist = it; - } - - // Pop item from in front of the free list. - rcSpan* it = hf.freelist; - hf.freelist = hf.freelist->next; - return it; -} - -static void freeSpan(rcHeightfield& hf, rcSpan* ptr) -{ - if (!ptr) return; - // Add the node in front of the free list. - ptr->next = hf.freelist; - hf.freelist = ptr; -} - -static void addSpan(rcHeightfield& hf, const int x, const int y, - const unsigned short smin, const unsigned short smax, - const unsigned char area, const int flagMergeThr) -{ - - int idx = x + y*hf.width; - - rcSpan* s = allocSpan(hf); - s->smin = smin; - s->smax = smax; - s->area = area; - s->next = 0; - - // Empty cell, add he first span. - if (!hf.spans[idx]) - { - hf.spans[idx] = s; - return; - } - rcSpan* prev = 0; - rcSpan* cur = hf.spans[idx]; - - // Insert and merge spans. - while (cur) - { - if (cur->smin > s->smax) - { - // Current span is further than the new span, break. - break; - } - else if (cur->smax < s->smin) - { - // Current span is before the new span advance. - prev = cur; - cur = cur->next; - } - else - { - // Merge spans. - if (cur->smin < s->smin) - s->smin = cur->smin; - if (cur->smax > s->smax) - s->smax = cur->smax; - - // Merge flags. - if (rcAbs((int)s->smax - (int)cur->smax) <= flagMergeThr) - s->area = rcMax(s->area, cur->area); - - // Remove current span. - rcSpan* next = cur->next; - freeSpan(hf, cur); - if (prev) - prev->next = next; - else - hf.spans[idx] = next; - cur = next; - } - } - - // Insert new span. - if (prev) - { - s->next = prev->next; - prev->next = s; - } - else - { - s->next = hf.spans[idx]; - hf.spans[idx] = s; - } -} - -void rcAddSpan(rcContext* /*ctx*/, rcHeightfield& hf, const int x, const int y, - const unsigned short smin, const unsigned short smax, - const unsigned char area, const int flagMergeThr) -{ -// rcAssert(ctx); - addSpan(hf, x,y, smin, smax, area, flagMergeThr); -} - -static int clipPoly(const float* in, int n, float* out, float pnx, float pnz, float pd) -{ - float d[12]; - for (int i = 0; i < n; ++i) - d[i] = pnx*in[i*3+0] + pnz*in[i*3+2] + pd; - - int m = 0; - for (int i = 0, j = n-1; i < n; j=i, ++i) - { - bool ina = d[j] >= 0; - bool inb = d[i] >= 0; - if (ina != inb) - { - float s = d[j] / (d[j] - d[i]); - out[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s; - out[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s; - out[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s; - m++; - } - if (inb) - { - out[m*3+0] = in[i*3+0]; - out[m*3+1] = in[i*3+1]; - out[m*3+2] = in[i*3+2]; - m++; - } - } - return m; -} - -static void rasterizeTri(const float* v0, const float* v1, const float* v2, - const unsigned char area, rcHeightfield& hf, - const float* bmin, const float* bmax, - const float cs, const float ics, const float ich, - const int flagMergeThr) -{ - const int w = hf.width; - const int h = hf.height; - float tmin[3], tmax[3]; - const float by = bmax[1] - bmin[1]; - - // Calculate the bounding box of the triangle. - rcVcopy(tmin, v0); - rcVcopy(tmax, v0); - rcVmin(tmin, v1); - rcVmin(tmin, v2); - rcVmax(tmax, v1); - rcVmax(tmax, v2); - - // If the triangle does not touch the bbox of the heightfield, skip the triagle. - if (!overlapBounds(bmin, bmax, tmin, tmax)) - return; - - // Calculate the footpring of the triangle on the grid. - int x0 = (int)((tmin[0] - bmin[0])*ics); - int y0 = (int)((tmin[2] - bmin[2])*ics); - int x1 = (int)((tmax[0] - bmin[0])*ics); - int y1 = (int)((tmax[2] - bmin[2])*ics); - x0 = rcClamp(x0, 0, w-1); - y0 = rcClamp(y0, 0, h-1); - x1 = rcClamp(x1, 0, w-1); - y1 = rcClamp(y1, 0, h-1); - - // Clip the triangle into all grid cells it touches. - float in[7*3], out[7*3], inrow[7*3]; - - for (int y = y0; y <= y1; ++y) - { - // Clip polygon to row. - rcVcopy(&in[0], v0); - rcVcopy(&in[1*3], v1); - rcVcopy(&in[2*3], v2); - int nvrow = 3; - const float cz = bmin[2] + y*cs; - nvrow = clipPoly(in, nvrow, out, 0, 1, -cz); - if (nvrow < 3) continue; - nvrow = clipPoly(out, nvrow, inrow, 0, -1, cz+cs); - if (nvrow < 3) continue; - - for (int x = x0; x <= x1; ++x) - { - // Clip polygon to column. - int nv = nvrow; - const float cx = bmin[0] + x*cs; - nv = clipPoly(inrow, nv, out, 1, 0, -cx); - if (nv < 3) continue; - nv = clipPoly(out, nv, in, -1, 0, cx+cs); - if (nv < 3) continue; - - // Calculate min and max of the span. - float smin = in[1], smax = in[1]; - for (int i = 1; i < nv; ++i) - { - smin = rcMin(smin, in[i*3+1]); - smax = rcMax(smax, in[i*3+1]); - } - smin -= bmin[1]; - smax -= bmin[1]; - // Skip the span if it is outside the heightfield bbox - if (smax < 0.0f) continue; - if (smin > by) continue; - // Clamp the span to the heightfield bbox. - if (smin < 0.0f) smin = 0; - if (smax > by) smax = by; - - // Snap the span to the heightfield height grid. - unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT); - unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT); - - addSpan(hf, x, y, ismin, ismax, area, flagMergeThr); - } - } -} - -void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, - const unsigned char area, rcHeightfield& solid, - const int flagMergeThr) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); - - const float ics = 1.0f/solid.cs; - const float ich = 1.0f/solid.ch; - rasterizeTri(v0, v1, v2, area, solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); -} - -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, - const int* tris, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); - - const float ics = 1.0f/solid.cs; - const float ich = 1.0f/solid.ch; - // Rasterize triangles. - for (int i = 0; i < nt; ++i) - { - const float* v0 = &verts[tris[i*3+0]*3]; - const float* v1 = &verts[tris[i*3+1]*3]; - const float* v2 = &verts[tris[i*3+2]*3]; - // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); - } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); -} - -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/, - const unsigned short* tris, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); - - const float ics = 1.0f/solid.cs; - const float ich = 1.0f/solid.ch; - // Rasterize triangles. - for (int i = 0; i < nt; ++i) - { - const float* v0 = &verts[tris[i*3+0]*3]; - const float* v1 = &verts[tris[i*3+1]*3]; - const float* v2 = &verts[tris[i*3+2]*3]; - // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); - } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); -} - -void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, - rcHeightfield& solid, const int flagMergeThr) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_RASTERIZE_TRIANGLES); - - const float ics = 1.0f/solid.cs; - const float ich = 1.0f/solid.ch; - // Rasterize triangles. - for (int i = 0; i < nt; ++i) - { - const float* v0 = &verts[(i*3+0)*3]; - const float* v1 = &verts[(i*3+1)*3]; - const float* v2 = &verts[(i*3+2)*3]; - // Rasterize. - rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr); - } - - ctx->stopTimer(RC_TIMER_RASTERIZE_TRIANGLES); -} diff --git a/deps/recastnavigation/Recast/RecastRegion.cpp b/deps/recastnavigation/Recast/RecastRegion.cpp deleted file mode 100644 index c624bf6619..0000000000 --- a/deps/recastnavigation/Recast/RecastRegion.cpp +++ /dev/null @@ -1,1285 +0,0 @@ -// -// 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 <float.h> -#define _USE_MATH_DEFINES -#include <math.h> -#include <string.h> -#include <stdlib.h> -#include <stdio.h> -#include "Recast.h" -#include "RecastAlloc.h" -#include "RecastAssert.h" -#include <new> - - -static void calculateDistanceField(rcCompactHeightfield& chf, unsigned short* src, unsigned short& maxDist) -{ - const int w = chf.width; - const int h = chf.height; - - // Init distance and points. - for (int i = 0; i < chf.spanCount; ++i) - src[i] = 0xffff; - - // Mark boundary cells. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - const unsigned char area = chf.areas[i]; - - int nc = 0; - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); - if (area == chf.areas[ai]) - nc++; - } - } - if (nc != 4) - src[i] = 0; - } - } - } - - - // Pass 1 - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - - if (rcGetCon(s, 0) != RC_NOT_CONNECTED) - { - // (-1,0) - const int ax = x + rcGetDirOffsetX(0); - const int ay = y + rcGetDirOffsetY(0); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); - const rcCompactSpan& as = chf.spans[ai]; - if (src[ai]+2 < src[i]) - src[i] = src[ai]+2; - - // (-1,-1) - if (rcGetCon(as, 3) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(3); - const int aay = ay + rcGetDirOffsetY(3); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3); - if (src[aai]+3 < src[i]) - src[i] = src[aai]+3; - } - } - if (rcGetCon(s, 3) != RC_NOT_CONNECTED) - { - // (0,-1) - const int ax = x + rcGetDirOffsetX(3); - const int ay = y + rcGetDirOffsetY(3); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); - const rcCompactSpan& as = chf.spans[ai]; - if (src[ai]+2 < src[i]) - src[i] = src[ai]+2; - - // (1,-1) - if (rcGetCon(as, 2) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(2); - const int aay = ay + rcGetDirOffsetY(2); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2); - if (src[aai]+3 < src[i]) - src[i] = src[aai]+3; - } - } - } - } - } - - // Pass 2 - for (int y = h-1; y >= 0; --y) - { - for (int x = w-1; x >= 0; --x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - - if (rcGetCon(s, 2) != RC_NOT_CONNECTED) - { - // (1,0) - const int ax = x + rcGetDirOffsetX(2); - const int ay = y + rcGetDirOffsetY(2); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2); - const rcCompactSpan& as = chf.spans[ai]; - if (src[ai]+2 < src[i]) - src[i] = src[ai]+2; - - // (1,1) - if (rcGetCon(as, 1) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(1); - const int aay = ay + rcGetDirOffsetY(1); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1); - if (src[aai]+3 < src[i]) - src[i] = src[aai]+3; - } - } - if (rcGetCon(s, 1) != RC_NOT_CONNECTED) - { - // (0,1) - const int ax = x + rcGetDirOffsetX(1); - const int ay = y + rcGetDirOffsetY(1); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1); - const rcCompactSpan& as = chf.spans[ai]; - if (src[ai]+2 < src[i]) - src[i] = src[ai]+2; - - // (-1,1) - if (rcGetCon(as, 0) != RC_NOT_CONNECTED) - { - const int aax = ax + rcGetDirOffsetX(0); - const int aay = ay + rcGetDirOffsetY(0); - const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0); - if (src[aai]+3 < src[i]) - src[i] = src[aai]+3; - } - } - } - } - } - - maxDist = 0; - for (int i = 0; i < chf.spanCount; ++i) - maxDist = rcMax(src[i], maxDist); - -} - -static unsigned short* boxBlur(rcCompactHeightfield& chf, int thr, - unsigned short* src, unsigned short* dst) -{ - const int w = chf.width; - const int h = chf.height; - - thr *= 2; - - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - const unsigned short cd = src[i]; - if (cd <= thr) - { - dst[i] = cd; - continue; - } - - int d = (int)cd; - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); - d += (int)src[ai]; - - const rcCompactSpan& as = chf.spans[ai]; - const int dir2 = (dir+1) & 0x3; - if (rcGetCon(as, dir2) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dir2); - const int ay2 = ay + rcGetDirOffsetY(dir2); - const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2); - d += (int)src[ai2]; - } - else - { - d += cd; - } - } - else - { - d += cd*2; - } - } - dst[i] = (unsigned short)((d+5)/9); - } - } - } - return dst; -} - - -static bool floodRegion(int x, int y, int i, - unsigned short level, unsigned short r, - rcCompactHeightfield& chf, - unsigned short* srcReg, unsigned short* srcDist, - rcIntArray& stack) -{ - const int w = chf.width; - - const unsigned char area = chf.areas[i]; - - // Flood fill mark region. - stack.resize(0); - stack.push((int)x); - stack.push((int)y); - stack.push((int)i); - srcReg[i] = r; - srcDist[i] = 0; - - unsigned short lev = level >= 2 ? level-2 : 0; - int count = 0; - - while (stack.size() > 0) - { - int ci = stack.pop(); - int cy = stack.pop(); - int cx = stack.pop(); - - const rcCompactSpan& cs = chf.spans[ci]; - - // Check if any of the neighbours already have a valid region set. - unsigned short ar = 0; - for (int dir = 0; dir < 4; ++dir) - { - // 8 connected - if (rcGetCon(cs, dir) != RC_NOT_CONNECTED) - { - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir); - if (chf.areas[ai] != area) - continue; - unsigned short nr = srcReg[ai]; - if (nr & RC_BORDER_REG) // Do not take borders into account. - continue; - if (nr != 0 && nr != r) - ar = nr; - - const rcCompactSpan& as = chf.spans[ai]; - - const int dir2 = (dir+1) & 0x3; - if (rcGetCon(as, dir2) != RC_NOT_CONNECTED) - { - const int ax2 = ax + rcGetDirOffsetX(dir2); - const int ay2 = ay + rcGetDirOffsetY(dir2); - const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2); - if (chf.areas[ai2] != area) - continue; - unsigned short nr = srcReg[ai2]; - if (nr != 0 && nr != r) - ar = nr; - } - } - } - if (ar != 0) - { - srcReg[ci] = 0; - continue; - } - count++; - - // Expand neighbours. - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(cs, dir) != RC_NOT_CONNECTED) - { - const int ax = cx + rcGetDirOffsetX(dir); - const int ay = cy + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(cs, dir); - if (chf.areas[ai] != area) - continue; - if (chf.dist[ai] >= lev) - { - if (srcReg[ai] == 0) - { - srcReg[ai] = r; - srcDist[ai] = 0; - stack.push(ax); - stack.push(ay); - stack.push(ai); - } - } - } - } - } - - return count > 0; -} - -static unsigned short* expandRegions(int maxIter, unsigned short level, - rcCompactHeightfield& chf, - unsigned short* srcReg, unsigned short* srcDist, - unsigned short* dstReg, unsigned short* dstDist, - rcIntArray& stack) -{ - const int w = chf.width; - const int h = chf.height; - - // Find cells revealed by the raised level. - stack.resize(0); - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (chf.dist[i] >= level && srcReg[i] == 0 && chf.areas[i] != RC_NULL_AREA) - { - stack.push(x); - stack.push(y); - stack.push(i); - } - } - } - } - - int iter = 0; - while (stack.size() > 0) - { - int failed = 0; - - memcpy(dstReg, srcReg, sizeof(unsigned short)*chf.spanCount); - memcpy(dstDist, srcDist, sizeof(unsigned short)*chf.spanCount); - - for (int j = 0; j < stack.size(); j += 3) - { - int x = stack[j+0]; - int y = stack[j+1]; - int i = stack[j+2]; - if (i < 0) - { - failed++; - continue; - } - - unsigned short r = srcReg[i]; - unsigned short d2 = 0xffff; - const unsigned char area = chf.areas[i]; - const rcCompactSpan& s = chf.spans[i]; - for (int dir = 0; dir < 4; ++dir) - { - if (rcGetCon(s, dir) == RC_NOT_CONNECTED) continue; - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir); - if (chf.areas[ai] != area) continue; - if (srcReg[ai] > 0 && (srcReg[ai] & RC_BORDER_REG) == 0) - { - if ((int)srcDist[ai]+2 < (int)d2) - { - r = srcReg[ai]; - d2 = srcDist[ai]+2; - } - } - } - if (r) - { - stack[j+2] = -1; // mark as used - dstReg[i] = r; - dstDist[i] = d2; - } - else - { - failed++; - } - } - - // rcSwap source and dest. - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); - - if (failed*3 == stack.size()) - break; - - if (level > 0) - { - ++iter; - if (iter >= maxIter) - break; - } - } - - return srcReg; -} - - -struct rcRegion -{ - inline rcRegion(unsigned short i) : - spanCount(0), - id(i), - areaType(0), - remap(false), - visited(false) - {} - - int spanCount; // Number of spans belonging to this region - unsigned short id; // ID of the region - unsigned char areaType; // Are type. - bool remap; - bool visited; - rcIntArray connections; - rcIntArray floors; -}; - -static void removeAdjacentNeighbours(rcRegion& reg) -{ - // Remove adjacent duplicates. - for (int i = 0; i < reg.connections.size() && reg.connections.size() > 1; ) - { - int ni = (i+1) % reg.connections.size(); - if (reg.connections[i] == reg.connections[ni]) - { - // Remove duplicate - for (int j = i; j < reg.connections.size()-1; ++j) - reg.connections[j] = reg.connections[j+1]; - reg.connections.pop(); - } - else - ++i; - } -} - -static void replaceNeighbour(rcRegion& reg, unsigned short oldId, unsigned short newId) -{ - bool neiChanged = false; - for (int i = 0; i < reg.connections.size(); ++i) - { - if (reg.connections[i] == oldId) - { - reg.connections[i] = newId; - neiChanged = true; - } - } - for (int i = 0; i < reg.floors.size(); ++i) - { - if (reg.floors[i] == oldId) - reg.floors[i] = newId; - } - if (neiChanged) - removeAdjacentNeighbours(reg); -} - -static bool canMergeWithRegion(const rcRegion& rega, const rcRegion& regb) -{ - if (rega.areaType != regb.areaType) - return false; - int n = 0; - for (int i = 0; i < rega.connections.size(); ++i) - { - if (rega.connections[i] == regb.id) - n++; - } - if (n > 1) - return false; - for (int i = 0; i < rega.floors.size(); ++i) - { - if (rega.floors[i] == regb.id) - return false; - } - return true; -} - -static void addUniqueFloorRegion(rcRegion& reg, int n) -{ - for (int i = 0; i < reg.floors.size(); ++i) - if (reg.floors[i] == n) - return; - reg.floors.push(n); -} - -static bool mergeRegions(rcRegion& rega, rcRegion& regb) -{ - unsigned short aid = rega.id; - unsigned short bid = regb.id; - - // Duplicate current neighbourhood. - rcIntArray acon; - acon.resize(rega.connections.size()); - for (int i = 0; i < rega.connections.size(); ++i) - acon[i] = rega.connections[i]; - rcIntArray& bcon = regb.connections; - - // Find insertion point on A. - int insa = -1; - for (int i = 0; i < acon.size(); ++i) - { - if (acon[i] == bid) - { - insa = i; - break; - } - } - if (insa == -1) - return false; - - // Find insertion point on B. - int insb = -1; - for (int i = 0; i < bcon.size(); ++i) - { - if (bcon[i] == aid) - { - insb = i; - break; - } - } - if (insb == -1) - return false; - - // Merge neighbours. - rega.connections.resize(0); - for (int i = 0, ni = acon.size(); i < ni-1; ++i) - rega.connections.push(acon[(insa+1+i) % ni]); - - for (int i = 0, ni = bcon.size(); i < ni-1; ++i) - rega.connections.push(bcon[(insb+1+i) % ni]); - - removeAdjacentNeighbours(rega); - - for (int j = 0; j < regb.floors.size(); ++j) - addUniqueFloorRegion(rega, regb.floors[j]); - rega.spanCount += regb.spanCount; - regb.spanCount = 0; - regb.connections.resize(0); - - return true; -} - -static bool isRegionConnectedToBorder(const rcRegion& reg) -{ - // Region is connected to border if - // one of the neighbours is null id. - for (int i = 0; i < reg.connections.size(); ++i) - { - if (reg.connections[i] == 0) - return true; - } - return false; -} - -static bool isSolidEdge(rcCompactHeightfield& chf, unsigned short* srcReg, - int x, int y, int i, int dir) -{ - const rcCompactSpan& s = chf.spans[i]; - unsigned short r = 0; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir); - r = srcReg[ai]; - } - if (r == srcReg[i]) - return false; - return true; -} - -static void walkContour(int x, int y, int i, int dir, - rcCompactHeightfield& chf, - unsigned short* srcReg, - rcIntArray& cont) -{ - int startDir = dir; - int starti = i; - - const rcCompactSpan& ss = chf.spans[i]; - unsigned short curReg = 0; - if (rcGetCon(ss, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(ss, dir); - curReg = srcReg[ai]; - } - cont.push(curReg); - - int iter = 0; - while (++iter < 40000) - { - const rcCompactSpan& s = chf.spans[i]; - - if (isSolidEdge(chf, srcReg, x, y, i, dir)) - { - // Choose the edge corner - unsigned short r = 0; - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(dir); - const int ay = y + rcGetDirOffsetY(dir); - const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir); - r = srcReg[ai]; - } - if (r != curReg) - { - curReg = r; - cont.push(curReg); - } - - dir = (dir+1) & 0x3; // Rotate CW - } - else - { - int ni = -1; - const int nx = x + rcGetDirOffsetX(dir); - const int ny = y + rcGetDirOffsetY(dir); - if (rcGetCon(s, dir) != RC_NOT_CONNECTED) - { - const rcCompactCell& nc = chf.cells[nx+ny*chf.width]; - ni = (int)nc.index + rcGetCon(s, dir); - } - if (ni == -1) - { - // Should not happen. - return; - } - x = nx; - y = ny; - i = ni; - dir = (dir+3) & 0x3; // Rotate CCW - } - - if (starti == i && startDir == dir) - { - break; - } - } - - // Remove adjacent duplicates. - if (cont.size() > 1) - { - for (int i = 0; i < cont.size(); ) - { - int ni = (i+1) % cont.size(); - if (cont[i] == cont[ni]) - { - for (int j = i; j < cont.size()-1; ++j) - cont[j] = cont[j+1]; - cont.pop(); - } - else - ++i; - } - } -} - -static bool filterSmallRegions(rcContext* ctx, int minRegionArea, int mergeRegionSize, - unsigned short& maxRegionId, - rcCompactHeightfield& chf, - unsigned short* srcReg) -{ - const int w = chf.width; - const int h = chf.height; - - const int nreg = maxRegionId+1; - rcRegion* regions = (rcRegion*)rcAlloc(sizeof(rcRegion)*nreg, RC_ALLOC_TEMP); - if (!regions) - { - ctx->log(RC_LOG_ERROR, "filterSmallRegions: Out of memory 'regions' (%d).", nreg); - return false; - } - - // Construct regions - for (int i = 0; i < nreg; ++i) - new(®ions[i]) rcRegion((unsigned short)i); - - // Find edge of a region and find connections around the contour. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - unsigned short r = srcReg[i]; - if (r == 0 || r >= nreg) - continue; - - rcRegion& reg = regions[r]; - reg.spanCount++; - - - // Update floors. - for (int j = (int)c.index; j < ni; ++j) - { - if (i == j) continue; - unsigned short floorId = srcReg[j]; - if (floorId == 0 || floorId >= nreg) - continue; - addUniqueFloorRegion(reg, floorId); - } - - // Have found contour - if (reg.connections.size() > 0) - continue; - - reg.areaType = chf.areas[i]; - - // Check if this cell is next to a border. - int ndir = -1; - for (int dir = 0; dir < 4; ++dir) - { - if (isSolidEdge(chf, srcReg, x, y, i, dir)) - { - ndir = dir; - break; - } - } - - if (ndir != -1) - { - // The cell is at border. - // Walk around the contour to find all the neighbours. - walkContour(x, y, i, ndir, chf, srcReg, reg.connections); - } - } - } - } - - // Remove too small regions. - rcIntArray stack(32); - rcIntArray trace(32); - for (int i = 0; i < nreg; ++i) - { - rcRegion& reg = regions[i]; - if (reg.id == 0 || (reg.id & RC_BORDER_REG)) - continue; - if (reg.spanCount == 0) - continue; - if (reg.visited) - continue; - - // Count the total size of all the connected regions. - // Also keep track of the regions connects to a tile border. - bool connectsToBorder = false; - int spanCount = 0; - stack.resize(0); - trace.resize(0); - - reg.visited = true; - stack.push(i); - - while (stack.size()) - { - // Pop - int ri = stack.pop(); - - rcRegion& creg = regions[ri]; - - spanCount += creg.spanCount; - trace.push(ri); - - for (int j = 0; j < creg.connections.size(); ++j) - { - if (creg.connections[j] & RC_BORDER_REG) - { - connectsToBorder = true; - continue; - } - rcRegion& nreg = regions[creg.connections[j]]; - if (nreg.visited) - continue; - if (nreg.id == 0 || (nreg.id & RC_BORDER_REG)) - continue; - // Visit - stack.push(nreg.id); - nreg.visited = true; - } - } - - // If the accumulated regions size is too small, remove it. - // Do not remove areas which connect to tile borders - // as their size cannot be estimated correctly and removing them - // can potentially remove necessary areas. - if (spanCount < minRegionArea && !connectsToBorder) - { - // Kill all visited regions. - for (int j = 0; j < trace.size(); ++j) - { - regions[trace[j]].spanCount = 0; - regions[trace[j]].id = 0; - } - } - } - - // Merge too small regions to neighbour regions. - int mergeCount = 0 ; - do - { - mergeCount = 0; - for (int i = 0; i < nreg; ++i) - { - rcRegion& reg = regions[i]; - if (reg.id == 0 || (reg.id & RC_BORDER_REG)) - continue; - if (reg.spanCount == 0) - continue; - - // Check to see if the region should be merged. - if (reg.spanCount > mergeRegionSize && isRegionConnectedToBorder(reg)) - continue; - - // Small region with more than 1 connection. - // Or region which is not connected to a border at all. - // Find smallest neighbour region that connects to this one. - int smallest = 0xfffffff; - unsigned short mergeId = reg.id; - for (int j = 0; j < reg.connections.size(); ++j) - { - if (reg.connections[j] & RC_BORDER_REG) continue; - rcRegion& mreg = regions[reg.connections[j]]; - if (mreg.id == 0 || (mreg.id & RC_BORDER_REG)) continue; - if (mreg.spanCount < smallest && - canMergeWithRegion(reg, mreg) && - canMergeWithRegion(mreg, reg)) - { - smallest = mreg.spanCount; - mergeId = mreg.id; - } - } - // Found new id. - if (mergeId != reg.id) - { - unsigned short oldId = reg.id; - rcRegion& target = regions[mergeId]; - - // Merge neighbours. - if (mergeRegions(target, reg)) - { - // Fixup regions pointing to current region. - for (int j = 0; j < nreg; ++j) - { - if (regions[j].id == 0 || (regions[j].id & RC_BORDER_REG)) continue; - // If another region was already merged into current region - // change the nid of the previous region too. - if (regions[j].id == oldId) - regions[j].id = mergeId; - // Replace the current region with the new one if the - // current regions is neighbour. - replaceNeighbour(regions[j], oldId, mergeId); - } - mergeCount++; - } - } - } - } - while (mergeCount > 0); - - // Compress region Ids. - for (int i = 0; i < nreg; ++i) - { - regions[i].remap = false; - if (regions[i].id == 0) continue; // Skip nil regions. - if (regions[i].id & RC_BORDER_REG) continue; // Skip external regions. - regions[i].remap = true; - } - - unsigned short regIdGen = 0; - for (int i = 0; i < nreg; ++i) - { - if (!regions[i].remap) - continue; - unsigned short oldId = regions[i].id; - unsigned short newId = ++regIdGen; - for (int j = i; j < nreg; ++j) - { - if (regions[j].id == oldId) - { - regions[j].id = newId; - regions[j].remap = false; - } - } - } - maxRegionId = regIdGen; - - // Remap regions. - for (int i = 0; i < chf.spanCount; ++i) - { - if ((srcReg[i] & RC_BORDER_REG) == 0) - srcReg[i] = regions[srcReg[i]].id; - } - - for (int i = 0; i < nreg; ++i) - regions[i].~rcRegion(); - rcFree(regions); - - return true; -} - - -bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD); - - if (chf.dist) - { - rcFree(chf.dist); - chf.dist = 0; - } - - unsigned short* src = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); - if (!src) - { - ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'src' (%d).", chf.spanCount); - return false; - } - unsigned short* dst = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); - if (!dst) - { - ctx->log(RC_LOG_ERROR, "rcBuildDistanceField: Out of memory 'dst' (%d).", chf.spanCount); - rcFree(src); - return false; - } - - unsigned short maxDist = 0; - - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - calculateDistanceField(chf, src, maxDist); - chf.maxDistance = maxDist; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_DIST); - - ctx->startTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); - - // Blur - if (boxBlur(chf, 1, src, dst) != src) - rcSwap(src, dst); - - // Store distance. - chf.dist = src; - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD_BLUR); - - ctx->stopTimer(RC_TIMER_BUILD_DISTANCEFIELD); - - rcFree(dst); - - return true; -} - -static void paintRectRegion(int minx, int maxx, int miny, int maxy, unsigned short regId, - rcCompactHeightfield& chf, unsigned short* srcReg) -{ - const int w = chf.width; - for (int y = miny; y < maxy; ++y) - { - for (int x = minx; x < maxx; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (chf.areas[i] != RC_NULL_AREA) - srcReg[i] = regId; - } - } - } -} - - -static const unsigned short RC_NULL_NEI = 0xffff; - -struct rcSweepSpan -{ - unsigned short rid; // row id - unsigned short id; // region id - unsigned short ns; // number samples - unsigned short nei; // neighbour id -}; - -bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, - const int borderSize, const int minRegionArea, const int mergeRegionArea) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS); - - const int w = chf.width; - const int h = chf.height; - unsigned short id = 1; - - rcScopedDelete<unsigned short> srcReg = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount, RC_ALLOC_TEMP); - if (!srcReg) - { - ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'src' (%d).", chf.spanCount); - return false; - } - memset(srcReg,0,sizeof(unsigned short)*chf.spanCount); - - const int nsweeps = rcMax(chf.width,chf.height); - rcScopedDelete<rcSweepSpan> sweeps = (rcSweepSpan*)rcAlloc(sizeof(rcSweepSpan)*nsweeps, RC_ALLOC_TEMP); - if (!sweeps) - { - ctx->log(RC_LOG_ERROR, "rcBuildRegionsMonotone: Out of memory 'sweeps' (%d).", nsweeps); - return false; - } - - - // Mark border regions. - if (borderSize > 0) - { - // Make sure border will not overflow. - const int bw = rcMin(w, borderSize); - const int bh = rcMin(h, borderSize); - // Paint regions - paintRectRegion(0, bw, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; - paintRectRegion(w-bw, w, 0, h, id|RC_BORDER_REG, chf, srcReg); id++; - paintRectRegion(0, w, 0, bh, id|RC_BORDER_REG, chf, srcReg); id++; - paintRectRegion(0, w, h-bh, h, id|RC_BORDER_REG, chf, srcReg); id++; - } - - rcIntArray prev(256); - - // Sweep one line at a time. - for (int y = borderSize; y < h-borderSize; ++y) - { - // Collect spans from this row. - prev.resize(id+1); - memset(&prev[0],0,sizeof(int)*id); - unsigned short rid = 1; - - for (int x = borderSize; x < w-borderSize; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - const rcCompactSpan& s = chf.spans[i]; - if (chf.areas[i] == RC_NULL_AREA) continue; - - // -x - unsigned short previd = 0; - if (rcGetCon(s, 0) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(0); - const int ay = y + rcGetDirOffsetY(0); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0); - if ((srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) - previd = srcReg[ai]; - } - - if (!previd) - { - previd = rid++; - sweeps[previd].rid = previd; - sweeps[previd].ns = 0; - sweeps[previd].nei = 0; - } - - // -y - if (rcGetCon(s,3) != RC_NOT_CONNECTED) - { - const int ax = x + rcGetDirOffsetX(3); - const int ay = y + rcGetDirOffsetY(3); - const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3); - if (srcReg[ai] && (srcReg[ai] & RC_BORDER_REG) == 0 && chf.areas[i] == chf.areas[ai]) - { - unsigned short nr = srcReg[ai]; - if (!sweeps[previd].nei || sweeps[previd].nei == nr) - { - sweeps[previd].nei = nr; - sweeps[previd].ns++; - prev[nr]++; - } - else - { - sweeps[previd].nei = RC_NULL_NEI; - } - } - } - - srcReg[i] = previd; - } - } - - // Create unique ID. - for (int i = 1; i < rid; ++i) - { - if (sweeps[i].nei != RC_NULL_NEI && sweeps[i].nei != 0 && - prev[sweeps[i].nei] == (int)sweeps[i].ns) - { - sweeps[i].id = sweeps[i].nei; - } - else - { - sweeps[i].id = id++; - } - } - - // Remap IDs - for (int x = borderSize; x < w-borderSize; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (srcReg[i] > 0 && srcReg[i] < rid) - srcReg[i] = sweeps[srcReg[i]].id; - } - } - } - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Filter out small regions. - chf.maxRegions = id; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Store the result out. - for (int i = 0; i < chf.spanCount; ++i) - chf.spans[i].reg = srcReg[i]; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); - - return true; -} - -bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, - const int borderSize, const int minRegionArea, const int mergeRegionArea) -{ - rcAssert(ctx); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS); - - const int w = chf.width; - const int h = chf.height; - - rcScopedDelete<unsigned short> buf = (unsigned short*)rcAlloc(sizeof(unsigned short)*chf.spanCount*4, RC_ALLOC_TEMP); - if (!buf) - { - ctx->log(RC_LOG_ERROR, "rcBuildRegions: Out of memory 'tmp' (%d).", chf.spanCount*4); - return false; - } - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - - rcIntArray stack(1024); - rcIntArray visited(1024); - - unsigned short* srcReg = buf; - unsigned short* srcDist = buf+chf.spanCount; - unsigned short* dstReg = buf+chf.spanCount*2; - unsigned short* dstDist = buf+chf.spanCount*3; - - memset(srcReg, 0, sizeof(unsigned short)*chf.spanCount); - memset(srcDist, 0, sizeof(unsigned short)*chf.spanCount); - - unsigned short regionId = 1; - unsigned short level = (chf.maxDistance+1) & ~1; - - // TODO: Figure better formula, expandIters defines how much the - // watershed "overflows" and simplifies the regions. Tying it to - // agent radius was usually good indication how greedy it could be. -// const int expandIters = 4 + walkableRadius * 2; - const int expandIters = 8; - - // Mark border regions. - paintRectRegion(0, borderSize, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; - paintRectRegion(w-borderSize, w, 0, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; - paintRectRegion(0, w, 0, borderSize, regionId|RC_BORDER_REG, chf, srcReg); regionId++; - paintRectRegion(0, w, h-borderSize, h, regionId|RC_BORDER_REG, chf, srcReg); regionId++; - - while (level > 0) - { - level = level >= 2 ? level-2 : 0; - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters, level, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg) - { - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); - } - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_EXPAND); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FLOOD); - - // Mark new regions with IDs. - for (int y = 0; y < h; ++y) - { - for (int x = 0; x < w; ++x) - { - const rcCompactCell& c = chf.cells[x+y*w]; - for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i) - { - if (chf.dist[i] < level || srcReg[i] != 0 || chf.areas[i] == RC_NULL_AREA) - continue; - - if (floodRegion(x, y, i, level, regionId, chf, srcReg, srcDist, stack)) - regionId++; - } - } - } - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FLOOD); - - } - - // Expand current regions until no empty connected cells found. - if (expandRegions(expandIters*8, 0, chf, srcReg, srcDist, dstReg, dstDist, stack) != srcReg) - { - rcSwap(srcReg, dstReg); - rcSwap(srcDist, dstDist); - } - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_WATERSHED); - - ctx->startTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Filter out small regions. - chf.maxRegions = regionId; - if (!filterSmallRegions(ctx, minRegionArea, mergeRegionArea, chf.maxRegions, chf, srcReg)) - return false; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS_FILTER); - - // Write the result out. - for (int i = 0; i < chf.spanCount; ++i) - chf.spans[i].reg = srcReg[i]; - - ctx->stopTimer(RC_TIMER_BUILD_REGIONS); - - return true; -} - - |