Recast.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
// Modified version of Recast/Detour's source file
 
//
// 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
 
#include "CoreMinimal.h"
#include "Logging/LogMacros.h"
#include "RecastLargeWorldCoordinates.h"
 
//@UE BEGIN Adding support for LWCoords.
static const rcReal RC_PI = 3.14159265358979323846;
 
inline float rcSin(float x)
{
    return sinf(x);
}
 
inline double rcSin(double x)
{
    return sin(x);
}
 
inline float rcCos(float x)
{
    return cosf(x);
}
 
inline double rcCos(double x)
{
    return cos(x);
}
 
inline float rcFloor(float x)
{
    return floorf(x);
}
 
inline double rcFloor(double x)
{
    return floor(x);
}
 
inline float rcCeil(float x)
{
    return ceilf(x);
}
 
inline double rcCeil(double x)
{
    return ceil(x);
}
 
inline float rcAbs(float x)
{
    return fabsf(x);
}
 
inline double rcAbs(double x)
{
    return fabs(x);
}
//@UE END Adding support for LWCoords.
 
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_BUILD_CLUSTERS, 
    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_CYLINDER_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_LAYERS, 
    RC_TIMER_BUILD_POLYMESHDETAIL,
    RC_TIMER_MERGE_POLYMESHDETAIL,
    RC_MAX_TIMERS
};
 
NAVMESH_API DECLARE_LOG_CATEGORY_EXTERN(LogRecast, Log, All);
 
class rcContext
{
public:
 
    inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {}
    virtual ~rcContext() {}
 
    inline void enableLog(bool state) { m_logEnabled = state; }
 
    inline void resetLog() { if (m_logEnabled) doResetLog(); }
 
    NAVMESH_API void log(const rcLogCategory category, const char* format, ...);
 
    inline void enableTimer(bool state) { m_timerEnabled = state; }
 
    inline void resetTimers() { if (m_timerEnabled) doResetTimers(); }
 
    inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); }
 
    inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); }
 
    inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; }
 
protected:
 
    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;
};
 
enum rcRegionPartitioning
{
    RC_REGION_MONOTONE,     
    RC_REGION_WATERSHED,    
    RC_REGION_CHUNKY,       
};
 
//@UE BEGIN
struct rcBorderSize
{
    int low;    
    int high;   
};
//@UE END
 
struct rcConfig
{
    int width;
 
    int height;
    
    int tileSize;
    
    rcBorderSize borderSize;                                                    //@UE                                                       
 
    rcReal cs;
 
    rcReal ch;
 
    rcReal bmin[3];
 
    rcReal bmax[3];
 
    rcReal walkableSlopeAngle;
 
    int walkableHeight;
    
    int walkableClimb;
    
    int walkableRadius;
 
    rcReal maxStepFromWalkableSlope;
    
    int maxEdgeLen;
    
    rcReal maxSimplificationError;
 
    rcReal simplificationElevationRatio;    // UE
    
    int minRegionArea;
    
    int mergeRegionArea;
 
    int regionChunkSize;
 
    int regionPartitioning;
 
    int maxVertsPerPoly;
    
    rcReal detailSampleDist;
    
    rcReal detailSampleMaxError;
};
 
static constexpr int RC_SPAN_HEIGHT_BITS = 29;  // UE
 
static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1;
 
static const int RC_SPANS_PER_POOL = 2048;
 
typedef unsigned int rcSpanUInt;
 
struct rcSpanData
{
    rcSpanUInt smin : RC_SPAN_HEIGHT_BITS;  
    rcSpanUInt smax : RC_SPAN_HEIGHT_BITS;  
    unsigned int area : 6;                  
};
 
struct rcSpanCache
{
    unsigned short x;
    unsigned short y;
    rcSpanData data;
};
 
struct rcSpan
{
    rcSpanData data;                
    rcSpan* next;                   
};
 
struct rcSpanPool
{
    rcSpanPool* next;                   
    rcSpan items[RC_SPANS_PER_POOL];    
};
 
 
#define EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER 1
 
#if EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER
struct rcRowExt
{
    int MinCol;
    int MaxCol;
};
struct rcEdgeHit
{
    unsigned char Hits[2];
};
struct rcTempSpan
{
    int sminmax[2];         
};
#endif // EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER
 
struct rcHeightfield
{
    int width;          
    int height;         
    rcReal bmin[3];     
    rcReal bmax[3];     
    rcReal cs;          
    rcReal ch;          
    rcSpan** spans;     
    rcSpanPool* pools;  
    rcSpan* freelist;   
 
#if EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER
    rcEdgeHit* EdgeHits; 
    rcRowExt* RowExt;       
    rcTempSpan* tempspans;      
    rcSpanData* tempSpanColumns;    
#endif // EPIC_ADDITION_USE_NEW_RECAST_RASTERIZER
 
};
 
struct rcCompactCell
{
    unsigned int index : 24;    
    unsigned int count : 8;     
};
 
struct rcCompactSpan
{
    rcSpanUInt y;               
    unsigned int con;           
    unsigned short reg;         
    unsigned char h;            
};
 
struct rcCompactHeightfield
{
    int width;                  
    int height;                 
    int spanCount;              
    int walkableHeight;         
    int walkableClimb;          
    rcBorderSize borderSize;    
    unsigned short maxDistance; 
    unsigned short maxRegions;  
    rcReal bmin[3];             
    rcReal bmax[3];             
    rcReal cs;                  
    rcReal ch;                  
    rcCompactCell* cells;       
    rcCompactSpan* spans;       
    unsigned short* dist;       
    unsigned char* areas;       
};
 
struct rcHeightfieldLayer
{
    rcReal bmin[3];             
    rcReal bmax[3];             
    rcReal cs;                  
    rcReal ch;                  
    int width;                  
    int height;                 
    int minx;                   
    int maxx;                   
    int miny;                   
    int maxy;                   
    int hmin;                   
    int hmax;                   
    unsigned short* heights;    
    unsigned char* areas;       
    unsigned char* cons;        
};
 
struct rcHeightfieldLayerSet
{
    rcHeightfieldLayer* layers;         
    int nlayers;                        
};
 
struct rcContour
{
    int* verts;         
    int nverts;         
    int* rverts;        
    int nrverts;        
    unsigned short reg; 
    unsigned char area; 
};
 
struct rcContourSet
{
    rcContour* conts;           
    int nconts;                 
    rcReal bmin[3];             
    rcReal bmax[3];             
    rcReal cs;                  
    rcReal ch;                  
    int width;                  
    int height;                 
    rcBorderSize borderSize;    
};
 
// @UE BEGIN
#if WITH_NAVMESH_CLUSTER_LINKS
struct rcClusterSet
{
    int nclusters;          
    rcReal* center;         
    unsigned short* nlinks; 
    unsigned short* links;  
};
#endif // WITH_NAVMESH_CLUSTER_LINKS
// @UE END 
 
struct rcPolyMesh
{
    unsigned short* verts;  
    unsigned short* polys;  
    unsigned short* regs;   
    unsigned short* flags;  
    unsigned char* areas;   
    int nverts;             
    int npolys;             
    int maxpolys;           
    int nvp;                
    rcReal bmin[3];         
    rcReal bmax[3];         
    rcReal cs;              
    rcReal ch;              
    rcBorderSize borderSize;
};
 
struct rcPolyMeshDetail
{
    unsigned int* meshes;   
    rcReal* verts;          
    unsigned char* tris;    
    int nmeshes;            
    int nverts;             
    int ntris;              
};
 
 
NAVMESH_API rcHeightfield* rcAllocHeightfield();
 
NAVMESH_API void rcFreeHeightField(rcHeightfield* hf);
 
NAVMESH_API rcCompactHeightfield* rcAllocCompactHeightfield();
 
NAVMESH_API void rcFreeCompactHeightfield(rcCompactHeightfield* chf);
 
NAVMESH_API rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();
 
NAVMESH_API void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset);
 
NAVMESH_API rcContourSet* rcAllocContourSet();
 
NAVMESH_API void rcFreeContourSet(rcContourSet* cset);
 
// @UE BEGIN
#if WITH_NAVMESH_CLUSTER_LINKS
NAVMESH_API rcClusterSet* rcAllocClusterSet();
 
NAVMESH_API void rcFreeClusterSet(rcClusterSet* clset);
#endif // WITH_NAVMESH_CLUSTER_LINKS
// @UE END 
 
NAVMESH_API rcPolyMesh* rcAllocPolyMesh();
 
NAVMESH_API void rcFreePolyMesh(rcPolyMesh* pmesh);
 
NAVMESH_API rcPolyMeshDetail* rcAllocPolyMeshDetail();
 
NAVMESH_API void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh);
 
 
static const unsigned short RC_BORDER_REG = 0x8000;
 
static const int RC_BORDER_VERTEX = 0x10000;
 
static const int RC_AREA_BORDER = 0x20000;
 
enum rcBuildContoursFlags
{
    RC_CONTOUR_TESS_WALL_EDGES = 0x01,  
    RC_CONTOUR_TESS_AREA_EDGES = 0x02,  
};
 
// UE
enum rcFilterLowAreaFlags
{
    RC_LOW_FILTER_SEED_SPANS = 0x01,    
    RC_LOW_FILTER_POST_PROCESS = 0x02,  
};
 
// UE
enum rcRasterizationFlags
{
    RC_PROJECT_TO_BOTTOM = 1 << 0,      
    RC_RASTERIZE_AS_FILLED_CONVEX = 1 << 1,     
};
 
// UE
enum rcNeighborSlopeFilterMode
{
    RC_SLOPE_FILTER_RECAST,                         // Use walkableClimb value to filter
    RC_SLOPE_FILTER_NONE,                           // Skip slope filtering
    RC_SLOPE_FILTER_USE_HEIGHT_FROM_WALKABLE_SLOPE  // Use maximum step height computed from walkableSlopeAngle
};
 
static const int RC_CONTOUR_REG_MASK = 0xffff;
 
static const unsigned short RC_MESH_NULL_IDX = 0xffff;
 
static const unsigned char RC_NULL_AREA = 0;
 
static const unsigned char RC_WALKABLE_AREA = 63;
 
static const int RC_NOT_CONNECTED = 0xff;
 
 
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; }
inline rcReal rcMin(rcReal a, rcReal b) { return rcMin<rcReal>(a, b); }
 
template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; }
inline rcReal rcMax(rcReal a, rcReal b) { return rcMax<rcReal>(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); }
inline rcReal rcClamp(rcReal v, rcReal mn, rcReal mx) { return v < mn ? mn : (v > mx ? mx : v); }
 
rcReal rcSqrt(rcReal x);
 
 
inline void rcVcross(rcReal* dest, const rcReal* v1, const rcReal* 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 rcReal rcVdot(const rcReal* v1, const rcReal* v2)
{
    return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
}
 
inline void rcVmad(rcReal* dest, const rcReal* v1, const rcReal* v2, const rcReal 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(rcReal* dest, const rcReal* v1, const rcReal* v2)
{
    dest[0] = v1[0]+v2[0];
    dest[1] = v1[1]+v2[1];
    dest[2] = v1[2]+v2[2];
}
 
inline void rcVsub(rcReal* dest, const rcReal* v1, const rcReal* v2)
{
    dest[0] = v1[0]-v2[0];
    dest[1] = v1[1]-v2[1];
    dest[2] = v1[2]-v2[2];
}
 
inline void rcVmin(rcReal* mn, const rcReal* 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(rcReal* mx, const rcReal* 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(rcReal* dest, const rcReal* v)
{
    dest[0] = v[0];
    dest[1] = v[1];
    dest[2] = v[2];
}
 
inline rcReal rcVdist(const rcReal* v1, const rcReal* v2)
{
    rcReal dx = v2[0] - v1[0];
    rcReal dy = v2[1] - v1[1];
    rcReal dz = v2[2] - v1[2];
    return rcSqrt(dx*dx + dy*dy + dz*dz);
}
 
inline rcReal rcVdistSqr(const rcReal* v1, const rcReal* v2)
{
    rcReal dx = v2[0] - v1[0];
    rcReal dy = v2[1] - v1[1];
    rcReal dz = v2[2] - v1[2];
    return dx*dx + dy*dy + dz*dz;
}
 
inline void rcVnormalize(rcReal* v)
{
    rcReal d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
    v[0] *= d;
    v[1] *= d;
    v[2] *= d;
}
 
//@UE BEGIN
NAVMESH_API void rcCalcTriNormals(const rcReal* verts, const int nv, const int* tris, const int nt, rcReal* norms);
//@UE END
 
 
NAVMESH_API void rcCalcBounds(const rcReal* verts, int nv, rcReal* bmin, rcReal* bmax);
 
NAVMESH_API void rcCalcGridSize(const rcReal* bmin, const rcReal* bmax, rcReal cs, int* w, int* h);
 
NAVMESH_API bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
                         const rcReal* bmin, const rcReal* bmax,
                         rcReal cs, rcReal ch,
                         bool bAllocateTempSpanColumns = false); //UE
 
NAVMESH_API void rcResetHeightfield(rcHeightfield& hf);
 
NAVMESH_API void rcMarkWalkableTriangles(rcContext* ctx, const rcReal walkableSlopeAngle, const rcReal* verts, int nv,
                             const int* tris, int nt, unsigned char* areas); 
 
NAVMESH_API void rcMarkWalkableTrianglesCos(rcContext* ctx, const rcReal walkableSlopeCos, const rcReal* verts, int nv,
                                const int* tris, int nt, unsigned char* areas);
 
NAVMESH_API void rcClearUnwalkableTriangles(rcContext* ctx, const rcReal walkableSlopeAngle, const rcReal* verts, int nv,
                                const int* tris, int nt, unsigned char* areas); 
 
NAVMESH_API 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);
 
NAVMESH_API void rcAddSpans(rcContext* ctx, rcHeightfield& hf, const int flagMergeThr,
                const rcSpanCache* cachedSpans, const int nspans);
 
NAVMESH_API int rcCountSpans(rcContext* ctx, rcHeightfield& hf);
NAVMESH_API void rcCacheSpans(rcContext* ctx, rcHeightfield& hf, rcSpanCache* cachedSpans);
 
NAVMESH_API void rcRasterizeTriangle(rcContext* ctx, const rcReal* v0, const rcReal* v1, const rcReal* v2,
                         const unsigned char area, rcHeightfield& solid,
                         const int flagMergeThr = 1, 
                         const int rasterizationFlags = 0, const int* rasterizationMasks = nullptr); //UE
 
NAVMESH_API void rcRasterizeTriangles(rcContext* ctx, const rcReal* verts, const int nv,
                          const int* tris, const unsigned char* areas, const int nt,
                          rcHeightfield& solid, const int flagMergeThr = 1, 
                          const int rasterizationFlags = 0, const int* rasterizationMasks = nullptr, //UE
                          const rcReal* vertsbmin = nullptr, const rcReal* vertsbmax = nullptr); //UE
 
NAVMESH_API void rcRasterizeTriangles(rcContext* ctx, const rcReal* verts, const int nv,
                          const unsigned short* tris, const unsigned char* areas, const int nt,
                          rcHeightfield& solid, const int flagMergeThr = 1, 
                          const int rasterizationFlags = 0, const int* rasterizationMasks = nullptr, //UE
                          const rcReal* vertsbmin = nullptr, const rcReal* vertsbmax = nullptr); //UE
 
NAVMESH_API void rcRasterizeTriangles(rcContext* ctx, const rcReal* verts, const unsigned char* areas, const int nt,
                          rcHeightfield& solid, const int flagMergeThr = 1,
                          const int rasterizationFlags = 0, const int* rasterizationMasks = nullptr, //UE
                          const rcReal* vertsbmin = nullptr, const rcReal* vertsbmax = nullptr); //UE
 
NAVMESH_API void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid);
 
NAVMESH_API void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                    const rcNeighborSlopeFilterMode neighborSlopeFilterMode, const rcReal maxStepFromWalkableSlope, const rcReal ch, const int yStart, const int maxYProcess, rcHeightfield& solid); //UE
 
NAVMESH_API void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                    const rcNeighborSlopeFilterMode neighborSlopeFilterMode, const rcReal maxStepFromWalkableSlope, const rcReal ch, rcHeightfield& solid); //UE
 
NAVMESH_API void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid);
NAVMESH_API void rcFilterWalkableLowHeightSpansSequences(rcContext* ctx, int walkableHeight, rcHeightfield& solid);
 
NAVMESH_API int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf);
 
 
NAVMESH_API bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                               rcHeightfield& hf, rcCompactHeightfield& chf);
 
NAVMESH_API bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf);
 
NAVMESH_API bool rcErodeWalkableAndLowAreas(rcContext* ctx, int radius, unsigned int height,
                                            unsigned char areaId, unsigned char filterFlags,
                                            rcCompactHeightfield& chf);
 
NAVMESH_API bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf);
 
NAVMESH_API bool rcMarkLowAreas(rcContext* ctx, unsigned int height, unsigned char areaId, rcCompactHeightfield& chf);
 
NAVMESH_API void rcMarkBoxArea(rcContext* ctx, const rcReal* bmin, const rcReal* bmax, unsigned char areaId,
                   rcCompactHeightfield& chf);
 
NAVMESH_API void rcMarkConvexPolyArea(rcContext* ctx, const rcReal* verts, const int nverts,
                          const rcReal hmin, const rcReal hmax, unsigned char areaId,
                          rcCompactHeightfield& chf);
 
NAVMESH_API int rcOffsetPoly(const rcReal* verts, const int nverts, const rcReal offset,
                 rcReal* outVerts, const int maxOutVerts);
 
NAVMESH_API void rcMarkCylinderArea(rcContext* ctx, const rcReal* pos,
                        const rcReal r, const rcReal h, unsigned char areaId,
                        rcCompactHeightfield& chf);
 
NAVMESH_API void rcReplaceBoxArea(rcContext* ctx, const rcReal* bmin, const rcReal* bmax,
    unsigned char areaId, unsigned char filterAreaId,
    rcCompactHeightfield& chf);
 
NAVMESH_API void rcReplaceConvexPolyArea(rcContext* ctx, const rcReal* verts, const int nverts,
    const rcReal hmin, const rcReal hmax, unsigned char areaId, unsigned char filterAreaId,
    rcCompactHeightfield& chf);
 
NAVMESH_API void rcReplaceCylinderArea(rcContext* ctx, const rcReal* pos,
    const rcReal r, const rcReal h, unsigned char areaId, unsigned char filterAreaId,
    rcCompactHeightfield& chf);
 
NAVMESH_API bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
 
NAVMESH_API bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
                    const int borderSize, const int minRegionArea, const int mergeRegionArea);
 
NAVMESH_API bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
                            const rcBorderSize borderSize, const int minRegionArea, const int mergeRegionArea);     //@UE
 
NAVMESH_API bool rcBuildRegionsChunky(rcContext* ctx, rcCompactHeightfield& chf,
                          const rcBorderSize borderSize, const int minRegionArea, const int mergeRegionArea,        //@UE
                          const int chunkSize);
 
inline void rcSetCon(rcCompactSpan& s, int dir, int i)
{
    const unsigned int shift = (unsigned int)dir * 8;
    unsigned int con = s.con;
    s.con = (con & ~(0xff << shift)) | (((unsigned int)i & 0xff) << shift);
}
 
inline int rcGetCon(const rcCompactSpan& s, int dir)
{
    const unsigned int shift = (unsigned int)dir * 8;
    return (s.con >> shift) & 0xff;
}
 
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];
}
 
 
// @UE BEGIN: renamed building layers to rcBuildHeightfieldLayersMonotone, added flood fill based implementation 
 
NAVMESH_API bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
                              const rcBorderSize borderSize, const int walkableHeight,      //@UE
                              rcHeightfieldLayerSet& lset);
 
NAVMESH_API bool rcBuildHeightfieldLayersMonotone(rcContext* ctx, rcCompactHeightfield& chf,
                                      const rcBorderSize borderSize, const int walkableHeight,      //@UE
                                      rcHeightfieldLayerSet& lset);
 
NAVMESH_API bool rcBuildHeightfieldLayersChunky(rcContext* ctx, rcCompactHeightfield& chf,
                                    const rcBorderSize borderSize, const int walkableHeight,        //@UE
                                    const int chunkSize,
                                    rcHeightfieldLayerSet& lset);
 
// @UE END
 
NAVMESH_API bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
                     const rcReal maxError, const int maxEdgeLen,
                     rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES);
 
//@UE BEGIN
#if WITH_NAVMESH_CLUSTER_LINKS
NAVMESH_API bool rcBuildClusters(rcContext* ctx, rcContourSet& cset, rcClusterSet& clusters);
#endif // WITH_NAVMESH_CLUSTER_LINKS
//@UE END
 
NAVMESH_API bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh);
 
NAVMESH_API bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
 
NAVMESH_API bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
                           const rcReal sampleDist, const rcReal sampleMaxError,
                           rcPolyMeshDetail& dmesh);
 
NAVMESH_API bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst);
 
NAVMESH_API bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
 
 
#endif // RECAST_H
 
 
// Due to the large amount of detail documentation for this file, 
// the content normally located at the end of the header file has been separated
// out to a file in /Docs/Extern.