Recast.h

Go to the documentation of this 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
 
static const float RC_PI = 3.14159265f;
 
template<class T> void rcIgnoreUnused(const T&) { }
 
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_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
};
 
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(); }
 
    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) { rcIgnoreUnused(category); rcIgnoreUnused(msg); rcIgnoreUnused(len); }
 
    virtual void doResetTimers() {}
 
    virtual void doStartTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
 
    virtual void doStopTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
 
    virtual int doGetAccumulatedTime(const rcTimerLabel label) const { rcIgnoreUnused(label); return -1; }
    
    bool m_logEnabled;
 
    bool m_timerEnabled;
};
 
class rcScopedTimer
{
public:
    inline rcScopedTimer(rcContext* ctx, const rcTimerLabel label) : m_ctx(ctx), m_label(label) { m_ctx->startTimer(m_label); }
    inline ~rcScopedTimer() { m_ctx->stopTimer(m_label); }
 
private:
    // Explicitly disabled copy constructor and copy assignment operator.
    rcScopedTimer(const rcScopedTimer&);
    rcScopedTimer& operator=(const rcScopedTimer&);
    
    rcContext* const m_ctx;
    const rcTimerLabel m_label;
};
 
struct rcConfig
{
    int width;
 
    int height;
    
    int tileSize;
    
    int borderSize;
 
    float cs;
 
    float ch;
 
    float bmin[3]; 
 
    float bmax[3];
 
    float walkableSlopeAngle;
 
    int walkableHeight;
    
    int walkableClimb;
    
    int walkableRadius;
    
    int maxEdgeLen;
    
    float maxSimplificationError;
    
    int minRegionArea;
    
    int mergeRegionArea;
    
    int maxVertsPerPoly;
    
    float detailSampleDist;
    
    float detailSampleMaxError;
};
 
static const int RC_SPAN_HEIGHT_BITS = 13;
static const int RC_SPAN_MAX_HEIGHT = (1 << RC_SPAN_HEIGHT_BITS) - 1;
 
static const int RC_SPANS_PER_POOL = 2048;
 
struct rcSpan
{
    unsigned int smin : RC_SPAN_HEIGHT_BITS; 
    unsigned int smax : RC_SPAN_HEIGHT_BITS; 
    unsigned int area : 6;                   
    rcSpan* next;                            
};
 
struct rcSpanPool
{
    rcSpanPool* next;                   
    rcSpan items[RC_SPANS_PER_POOL];    
};
 
struct rcHeightfield
{
    rcHeightfield();
    ~rcHeightfield();
 
    int width;          
    int height;         
    float bmin[3];      
    float bmax[3];      
    float cs;           
    float ch;           
    rcSpan** spans;     
 
    // memory pool for rcSpan instances.
    rcSpanPool* pools;  
    rcSpan* freelist;   
 
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcHeightfield(const rcHeightfield&);
    rcHeightfield& operator=(const rcHeightfield&);
};
 
struct rcCompactCell
{
    unsigned int index : 24;    
    unsigned int count : 8;     
};
 
struct rcCompactSpan
{
    unsigned short y;           
    unsigned short reg;         
    unsigned int con : 24;      
    unsigned int h : 8;         
};
 
struct rcCompactHeightfield
{
    rcCompactHeightfield();
    ~rcCompactHeightfield();
    
    int width;                  
    int height;                 
    int spanCount;              
    int walkableHeight;         
    int walkableClimb;          
    int borderSize;             
    unsigned short maxDistance; 
    unsigned short maxRegions;  
    float bmin[3];              
    float bmax[3];              
    float cs;                   
    float ch;                   
    rcCompactCell* cells;       
    rcCompactSpan* spans;       
    unsigned short* dist;       
    unsigned char* areas;       
    
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcCompactHeightfield(const rcCompactHeightfield&);
    rcCompactHeightfield& operator=(const rcCompactHeightfield&);
};
 
struct rcHeightfieldLayer
{
    float bmin[3];              
    float bmax[3];              
    float cs;                   
    float ch;                   
    int width;                  
    int height;                 
    int minx;                   
    int maxx;                   
    int miny;                   
    int maxy;                   
    int hmin;                   
    int hmax;                   
    unsigned char* heights;     
    unsigned char* areas;       
    unsigned char* cons;        
};
 
struct rcHeightfieldLayerSet
{
    rcHeightfieldLayerSet();
    ~rcHeightfieldLayerSet();
    
    rcHeightfieldLayer* layers;         
    int nlayers;                        
    
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcHeightfieldLayerSet(const rcHeightfieldLayerSet&);
    rcHeightfieldLayerSet& operator=(const rcHeightfieldLayerSet&);
};
 
struct rcContour
{
    int* verts;         
    int nverts;         
    int* rverts;        
    int nrverts;        
    unsigned short reg; 
    unsigned char area; 
};
 
struct rcContourSet
{
    rcContourSet();
    ~rcContourSet();
    
    rcContour* conts;   
    int nconts;         
    float bmin[3];      
    float bmax[3];      
    float cs;           
    float ch;           
    int width;          
    int height;         
    int borderSize;     
    float maxError;     
    
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcContourSet(const rcContourSet&);
    rcContourSet& operator=(const rcContourSet&);
};
 
struct rcPolyMesh
{
    rcPolyMesh();
    ~rcPolyMesh();
    
    unsigned short* verts;  
    unsigned short* polys;  
    unsigned short* regs;   
    unsigned short* flags;  
    unsigned char* areas;   
    int nverts;             
    int npolys;             
    int maxpolys;           
    int nvp;                
    float bmin[3];          
    float bmax[3];          
    float cs;               
    float ch;               
    int borderSize;         
    float maxEdgeError;     
    
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcPolyMesh(const rcPolyMesh&);
    rcPolyMesh& operator=(const rcPolyMesh&);
};
 
struct rcPolyMeshDetail
{
    rcPolyMeshDetail();
    
    unsigned int* meshes;   
    float* verts;           
    unsigned char* tris;    
    int nmeshes;            
    int nverts;             
    int ntris;              
    
private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcPolyMeshDetail(const rcPolyMeshDetail&);
    rcPolyMeshDetail& operator=(const rcPolyMeshDetail&);
};
 
 
rcHeightfield* rcAllocHeightfield();
 
void rcFreeHeightField(rcHeightfield* heightfield);
 
rcCompactHeightfield* rcAllocCompactHeightfield();
 
void rcFreeCompactHeightfield(rcCompactHeightfield* compactHeightfield);
 
rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();
 
void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* layerSet);
 
rcContourSet* rcAllocContourSet();
 
void rcFreeContourSet(rcContourSet* contourSet);
 
rcPolyMesh* rcAllocPolyMesh();
 
void rcFreePolyMesh(rcPolyMesh* polyMesh);
 
rcPolyMeshDetail* rcAllocPolyMeshDetail();
 
void rcFreePolyMeshDetail(rcPolyMeshDetail* detailMesh);
 
 
static const unsigned short RC_BORDER_REG = 0x8000;
 
static const unsigned short RC_MULTIPLE_REGS = 0;
 
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   
};
 
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 = 0x3f;
 
 
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 value, T minInclusive, T maxInclusive)
{
    return value < minInclusive ? minInclusive: (value > maxInclusive ? maxInclusive : value);
}
 
float rcSqrt(float x);
 
 
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;
}
 
 
void rcCalcBounds(const float* verts, int numVerts, float* minBounds, float* maxBounds);
 
void rcCalcGridSize(const float* minBounds, const float* maxBounds, float cellSize, int* sizeX, int* sizeZ);
 
bool rcCreateHeightfield(rcContext* context, rcHeightfield& heightfield, int sizeX, int sizeZ,
                         const float* minBounds, const float* maxBounds,
                         float cellSize, float cellHeight);
 
void rcMarkWalkableTriangles(rcContext* context, float walkableSlopeAngle, const float* verts, int numVerts,
                             const int* tris, int numTris, unsigned char* triAreaIDs); 
 
void rcClearUnwalkableTriangles(rcContext* context, float walkableSlopeAngle, const float* verts, int numVerts,
                                const int* tris, int numTris, unsigned char* triAreaIDs); 
 
bool rcAddSpan(rcContext* context, rcHeightfield& heightfield,
               int x, int z,
               unsigned short spanMin, unsigned short spanMax,
               unsigned char areaID, int flagMergeThreshold);
 
bool rcRasterizeTriangle(rcContext* context,
                         const float* v0, const float* v1, const float* v2,
                         unsigned char areaID, rcHeightfield& heightfield, int flagMergeThreshold = 1);
 
bool rcRasterizeTriangles(rcContext* context,
                          const float* verts, int numVerts,
                          const int* tris, const unsigned char* triAreaIDs, int numTris,
                          rcHeightfield& heightfield, int flagMergeThreshold = 1);
 
bool rcRasterizeTriangles(rcContext* context,
                          const float* verts, int numVerts,
                          const unsigned short* tris, const unsigned char* triAreaIDs, int numTris,
                          rcHeightfield& heightfield, int flagMergeThreshold = 1);
 
bool rcRasterizeTriangles(rcContext* context,
                          const float* verts, const unsigned char* triAreaIDs, int numTris,
                          rcHeightfield& heightfield, int flagMergeThreshold = 1);
 
void rcFilterLowHangingWalkableObstacles(rcContext* context, int walkableClimb, rcHeightfield& heightfield);
 
void rcFilterLedgeSpans(rcContext* context, int walkableHeight, int walkableClimb, rcHeightfield& heightfield);
 
void rcFilterWalkableLowHeightSpans(rcContext* context, int walkableHeight, rcHeightfield& heightfield);
 
int rcGetHeightFieldSpanCount(rcContext* context, const rcHeightfield& heightfield);
 
 
bool rcBuildCompactHeightfield(rcContext* context, int walkableHeight, int walkableClimb,
                               const rcHeightfield& heightfield, rcCompactHeightfield& compactHeightfield);
 
bool rcErodeWalkableArea(rcContext* context, int erosionRadius, rcCompactHeightfield& compactHeightfield);
 
bool rcMedianFilterWalkableArea(rcContext* context, rcCompactHeightfield& compactHeightfield);
 
void rcMarkBoxArea(rcContext* context, const float* boxMinBounds, const float* boxMaxBounds, unsigned char areaId,
                   rcCompactHeightfield& compactHeightfield);
 
void rcMarkConvexPolyArea(rcContext* context, const float* verts, int numVerts,
                          float minY, float maxY, unsigned char areaId,
                          rcCompactHeightfield& compactHeightfield);
 
int rcOffsetPoly(const float* verts, int numVerts, float offset, float* outVerts, int maxOutVerts);
 
void rcMarkCylinderArea(rcContext* context, const float* position, float radius, float height,
                        unsigned char areaId, rcCompactHeightfield& compactHeightfield);
 
bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
 
bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, int borderSize, int minRegionArea, int mergeRegionArea);
 
bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf, int borderSize, int minRegionArea);
 
bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
                            int borderSize, int minRegionArea, int mergeRegionArea);
 
inline void rcSetCon(rcCompactSpan& span, int direction, int neighborIndex)
{
    const unsigned int shift = (unsigned int)direction * 6;
    const unsigned int con = span.con;
    span.con = (con & ~(0x3f << shift)) | (((unsigned int)neighborIndex & 0x3f) << shift);
}
 
inline int rcGetCon(const rcCompactSpan& span, int direction)
{
    const unsigned int shift = (unsigned int)direction * 6;
    return (span.con >> shift) & 0x3f;
}
 
inline int rcGetDirOffsetX(int direction)
{
    static const int offset[4] = { -1, 0, 1, 0, };
    return offset[direction & 0x03];
}
 
// TODO (graham): Rename this to rcGetDirOffsetZ
inline int rcGetDirOffsetY(int direction)
{
    static const int offset[4] = { 0, 1, 0, -1 };
    return offset[direction & 0x03];
}
 
inline int rcGetDirForOffset(int offsetX, int offsetZ)
{
    static const int dirs[5] = { 3, 0, -1, 2, 1 };
    return dirs[((offsetZ + 1) << 1) + offsetX];
}
 
 
bool rcBuildHeightfieldLayers(rcContext* ctx, const rcCompactHeightfield& chf, 
                              int borderSize, int walkableHeight,
                              rcHeightfieldLayerSet& lset);
 
bool rcBuildContours(rcContext* ctx, const rcCompactHeightfield& chf,
                     float maxError, int maxEdgeLen,
                     rcContourSet& cset, int buildFlags = RC_CONTOUR_TESS_WALL_EDGES);
 
bool rcBuildPolyMesh(rcContext* ctx, const rcContourSet& cset, const int nvp, rcPolyMesh& mesh);
 
bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
 
bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
                           float sampleDist, float sampleMaxError,
                           rcPolyMeshDetail& dmesh);
 
bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst);
 
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.