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;

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*/) {}

        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;
};

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 : 13;                 
        unsigned int smax : 13;                 
        unsigned int area : 6;                  
        rcSpan* next;                                   
};

struct rcSpanPool
{
        rcSpanPool* next;                                       
        rcSpan items[RC_SPANS_PER_POOL];        
};

struct rcHeightfield
{
        int width;                      
        int height;                     
        float bmin[3];          
        float bmax[3];          
        float cs;                       
        float ch;                       
        rcSpan** spans;         
        rcSpanPool* pools;      
        rcSpan* freelist;       
};

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
{
        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;           
};

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
{
        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;                     
        float bmin[3];          
        float bmax[3];          
        float cs;                       
        float ch;                       
        int width;                      
        int height;                     
        int borderSize;         
};

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;                                
        float bmin[3];                  
        float bmax[3];                  
        float cs;                               
        float ch;                               
        int borderSize;                 
};

struct rcPolyMeshDetail
{
        unsigned int* meshes;   
        float* verts;                   
        unsigned char* tris;    
        int nmeshes;                    
        int nverts;                             
        int ntris;                              
};


rcHeightfield* rcAllocHeightfield();

void rcFreeHeightField(rcHeightfield* hf);

rcCompactHeightfield* rcAllocCompactHeightfield();

void rcFreeCompactHeightfield(rcCompactHeightfield* chf);

rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();

void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset);

rcContourSet* rcAllocContourSet();

void rcFreeContourSet(rcContourSet* cset);

rcPolyMesh* rcAllocPolyMesh();

void rcFreePolyMesh(rcPolyMesh* pmesh);

rcPolyMeshDetail* rcAllocPolyMeshDetail();

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,      
};

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 v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }

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 nv, float* bmin, float* bmax);

void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h);

bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
                                                 const float* bmin, const float* bmax,
                                                 float cs, float ch);

void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
                                                         const int* tris, int nt, unsigned char* areas); 

void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
                                                                const int* tris, int nt, unsigned char* areas); 

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);

void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
                                                 const unsigned char area, rcHeightfield& solid,
                                                 const int flagMergeThr = 1);

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);

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);

void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
                                                  rcHeightfield& solid, const int flagMergeThr = 1);

void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid);

void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight,
                                                const int walkableClimb, rcHeightfield& solid);

void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid);

int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf);


bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                                                           rcHeightfield& hf, rcCompactHeightfield& chf);

bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf);

bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf);

void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId,
                                   rcCompactHeightfield& chf);

void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
                                                  const float hmin, const float hmax, unsigned char areaId,
                                                  rcCompactHeightfield& chf);

int rcOffsetPoly(const float* verts, const int nverts, const float offset,
                                 float* outVerts, const int maxOutVerts);

void rcMarkCylinderArea(rcContext* ctx, const float* pos,
                                                const float r, const float h, unsigned char areaId,
                                                rcCompactHeightfield& chf);

bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);

bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
                                        const int borderSize, const int minRegionArea, const int mergeRegionArea);

bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
                                                        const int borderSize, const int minRegionArea, const int mergeRegionArea);


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];
}


bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, 
                                                          const int borderSize, const int walkableHeight,
                                                          rcHeightfieldLayerSet& lset);

bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
                                         const float maxError, const int maxEdgeLen,
                                         rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES);

bool rcBuildPolyMesh(rcContext* ctx, 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,
                                                   const float sampleDist, const 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.