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

#include "SharedConfig.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 logAndProfile = true) : m_logEnabled(logAndProfile), m_timerEnabled(logAndProfile) {}
    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 cellSizeXZ;

    float cellSizeY;

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


struct rcSpan
{
    static const int RC_SPAN_HEIGHT_BITS = 16; 
    static const int RC_SPAN_MAX_HEIGHT = (1 << RC_SPAN_HEIGHT_BITS) - 1; 

    unsigned int smin : RC_SPAN_HEIGHT_BITS;    
    unsigned int smax : RC_SPAN_HEIGHT_BITS;    
    navAreaMask areaMask;            

    rcSpan* next;                               
};

struct rcSpanPool
{
    static const int RC_SPANS_PER_POOL = 2048;

    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 minY;                
    unsigned short regionID;            
    unsigned int connectionData : 24;   
    unsigned int height : 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;       
    navAreaMask* areaMasks;         
};

struct rcHeightfieldLayer
{
    float bmin[3];              
    float bmax[3];              
    float cellSizeXZ;           
    float cellSizeY;            
    int width;                  
    int height;                 
    int minx;                   
    int maxx;                   
    int miny;                   
    int maxy;                   
    int hmin;                   
    int hmax;                   
    unsigned char* heights;     
    navAreaMask* areaMasks;     
    unsigned char* cons;        
};

struct rcHeightfieldLayerSet
{
    rcHeightfieldLayer* layers;         
    int nlayers;                        
};

struct rcContour
{
    int* verts;         
    int nverts;         
    int* rverts;        
    int nrverts;        
    unsigned short reg; 
    navAreaMask areaMask;   
};

struct rcContourSet
{
    rcContour* conts;   
    int nconts;         
    float bmin[3];      
    float bmax[3];      
    float cellSizeXZ;   
    float cellSizeY;    
    int width;          
    int height;         
    int borderSize;     
};

struct rcPolyMesh
{
    unsigned short* verts;  
    unsigned short* polys;  
    unsigned short* regs;   
    navAreaMask* areaMasks; 
    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 navAreaMask RC_NULL_AREA = 0;

static const navAreaMask RC_WALKABLE_AREA = 0x1;

static const int RC_NOT_CONNECTED = 0x3f;

#include "Util.h"
#include "Vector.h"
#include "Heightfield.h"
#include "CompactHeightfield.h"

struct rcHeightThreshold
{
    int             height;
    unsigned int    flag;
};
void rcFilterHeightThresholds(rcContext* ctx, const rcHeightThreshold *heights, int numHeights, rcHeightfield& solid);


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

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

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

void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
    const float hmin, const float hmax, navAreaMask 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, navAreaMask areaMask,
    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);


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


int rcConvexhull(const float* pts, int npts, int* out);

#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.