Recast.h

Go to the documentation of this file.

//
// Copyright (c) 2009-2010 Mikko Mononen [email protected]
//
// 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 = 16; // EDITED BY TC
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 : 16; 
 unsigned int smax : 16; 
 unsigned char area; 
 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> void rcIgnoreUnused(const T&) { }

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 rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
 const int borderSize, const int minRegionArea);

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 buildFlags = 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.