|
Planeshift
|
00001 // 00002 // Copyright (c) 2009-2010 Mikko Mononen [email protected] 00003 // 00004 // This software is provided 'as-is', without any express or implied 00005 // warranty. In no event will the authors be held liable for any damages 00006 // arising from the use of this software. 00007 // Permission is granted to anyone to use this software for any purpose, 00008 // including commercial applications, and to alter it and redistribute it 00009 // freely, subject to the following restrictions: 00010 // 1. The origin of this software must not be misrepresented; you must not 00011 // claim that you wrote the original software. If you use this software 00012 // in a product, an acknowledgment in the product documentation would be 00013 // appreciated but is not required. 00014 // 2. Altered source versions must be plainly marked as such, and must not be 00015 // misrepresented as being the original software. 00016 // 3. This notice may not be removed or altered from any source distribution. 00017 // 00018 00019 #ifndef RECAST_H 00020 #define RECAST_H 00021 00023 static const float RC_PI = 3.14159265f; 00024 00027 enum rcLogCategory 00028 { 00029 RC_LOG_PROGRESS = 1, 00030 RC_LOG_WARNING, 00031 RC_LOG_ERROR, 00032 }; 00033 00036 enum rcTimerLabel 00037 { 00039 RC_TIMER_TOTAL, 00041 RC_TIMER_TEMP, 00043 RC_TIMER_RASTERIZE_TRIANGLES, 00045 RC_TIMER_BUILD_COMPACTHEIGHTFIELD, 00047 RC_TIMER_BUILD_CONTOURS, 00049 RC_TIMER_BUILD_CONTOURS_TRACE, 00051 RC_TIMER_BUILD_CONTOURS_SIMPLIFY, 00053 RC_TIMER_FILTER_BORDER, 00055 RC_TIMER_FILTER_WALKABLE, 00057 RC_TIMER_MEDIAN_AREA, 00059 RC_TIMER_FILTER_LOW_OBSTACLES, 00061 RC_TIMER_BUILD_POLYMESH, 00063 RC_TIMER_MERGE_POLYMESH, 00065 RC_TIMER_ERODE_AREA, 00067 RC_TIMER_MARK_BOX_AREA, 00069 RC_TIMER_MARK_CYLINDER_AREA, 00071 RC_TIMER_MARK_CONVEXPOLY_AREA, 00073 RC_TIMER_BUILD_DISTANCEFIELD, 00075 RC_TIMER_BUILD_DISTANCEFIELD_DIST, 00077 RC_TIMER_BUILD_DISTANCEFIELD_BLUR, 00079 RC_TIMER_BUILD_REGIONS, 00081 RC_TIMER_BUILD_REGIONS_WATERSHED, 00083 RC_TIMER_BUILD_REGIONS_EXPAND, 00085 RC_TIMER_BUILD_REGIONS_FLOOD, 00087 RC_TIMER_BUILD_REGIONS_FILTER, 00089 RC_TIMER_BUILD_LAYERS, 00091 RC_TIMER_BUILD_POLYMESHDETAIL, 00093 RC_TIMER_MERGE_POLYMESHDETAIL, 00095 RC_MAX_TIMERS 00096 }; 00097 00101 class rcContext 00102 { 00103 public: 00104 00107 inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {} 00108 virtual ~rcContext() {} 00109 00112 inline void enableLog(bool state) { m_logEnabled = state; } 00113 00115 inline void resetLog() { if (m_logEnabled) doResetLog(); } 00116 00120 void log(const rcLogCategory category, const char* format, ...); 00121 00124 inline void enableTimer(bool state) { m_timerEnabled = state; } 00125 00127 inline void resetTimers() { if (m_timerEnabled) doResetTimers(); } 00128 00131 inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); } 00132 00135 inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); } 00136 00140 inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; } 00141 00142 protected: 00143 00145 virtual void doResetLog() {} 00146 00151 virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {} 00152 00154 virtual void doResetTimers() {} 00155 00158 virtual void doStartTimer(const rcTimerLabel /*label*/) {} 00159 00162 virtual void doStopTimer(const rcTimerLabel /*label*/) {} 00163 00167 virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; } 00168 00170 bool m_logEnabled; 00171 00173 bool m_timerEnabled; 00174 }; 00175 00178 struct rcConfig 00179 { 00181 int width; 00182 00184 int height; 00185 00187 int tileSize; 00188 00190 int borderSize; 00191 00193 float cs; 00194 00196 float ch; 00197 00199 float bmin[3]; 00200 00202 float bmax[3]; 00203 00205 float walkableSlopeAngle; 00206 00209 int walkableHeight; 00210 00212 int walkableClimb; 00213 00216 int walkableRadius; 00217 00219 int maxEdgeLen; 00220 00223 float maxSimplificationError; 00224 00226 int minRegionArea; 00227 00230 int mergeRegionArea; 00231 00234 int maxVertsPerPoly; 00235 00238 float detailSampleDist; 00239 00242 float detailSampleMaxError; 00243 }; 00244 00246 static const int RC_SPAN_HEIGHT_BITS = 13; 00248 static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1; 00249 00252 static const int RC_SPANS_PER_POOL = 2048; 00253 00256 struct rcSpan 00257 { 00258 unsigned int smin : 13; 00259 unsigned int smax : 13; 00260 unsigned int area : 6; 00261 rcSpan* next; 00262 }; 00263 00266 struct rcSpanPool 00267 { 00268 rcSpanPool* next; 00269 rcSpan items[RC_SPANS_PER_POOL]; 00270 }; 00271 00274 struct rcHeightfield 00275 { 00276 int width; 00277 int height; 00278 float bmin[3]; 00279 float bmax[3]; 00280 float cs; 00281 float ch; 00282 rcSpan** spans; 00283 rcSpanPool* pools; 00284 rcSpan* freelist; 00285 }; 00286 00288 struct rcCompactCell 00289 { 00290 unsigned int index : 24; 00291 unsigned int count : 8; 00292 }; 00293 00295 struct rcCompactSpan 00296 { 00297 unsigned short y; 00298 unsigned short reg; 00299 unsigned int con : 24; 00300 unsigned int h : 8; 00301 }; 00302 00305 struct rcCompactHeightfield 00306 { 00307 int width; 00308 int height; 00309 int spanCount; 00310 int walkableHeight; 00311 int walkableClimb; 00312 int borderSize; 00313 unsigned short maxDistance; 00314 unsigned short maxRegions; 00315 float bmin[3]; 00316 float bmax[3]; 00317 float cs; 00318 float ch; 00319 rcCompactCell* cells; 00320 rcCompactSpan* spans; 00321 unsigned short* dist; 00322 unsigned char* areas; 00323 }; 00324 00327 struct rcHeightfieldLayer 00328 { 00329 float bmin[3]; 00330 float bmax[3]; 00331 float cs; 00332 float ch; 00333 int width; 00334 int height; 00335 int minx; 00336 int maxx; 00337 int miny; 00338 int maxy; 00339 int hmin; 00340 int hmax; 00341 unsigned char* heights; 00342 unsigned char* areas; 00343 unsigned char* cons; 00344 }; 00345 00349 struct rcHeightfieldLayerSet 00350 { 00351 rcHeightfieldLayer* layers; 00352 int nlayers; 00353 }; 00354 00356 struct rcContour 00357 { 00358 int* verts; 00359 int nverts; 00360 int* rverts; 00361 int nrverts; 00362 unsigned short reg; 00363 unsigned char area; 00364 }; 00365 00368 struct rcContourSet 00369 { 00370 rcContour* conts; 00371 int nconts; 00372 float bmin[3]; 00373 float bmax[3]; 00374 float cs; 00375 float ch; 00376 int width; 00377 int height; 00378 int borderSize; 00379 }; 00380 00383 struct rcPolyMesh 00384 { 00385 unsigned short* verts; 00386 unsigned short* polys; 00387 unsigned short* regs; 00388 unsigned short* flags; 00389 unsigned char* areas; 00390 int nverts; 00391 int npolys; 00392 int maxpolys; 00393 int nvp; 00394 float bmin[3]; 00395 float bmax[3]; 00396 float cs; 00397 float ch; 00398 int borderSize; 00399 }; 00400 00404 struct rcPolyMeshDetail 00405 { 00406 unsigned int* meshes; 00407 float* verts; 00408 unsigned char* tris; 00409 int nmeshes; 00410 int nverts; 00411 int ntris; 00412 }; 00413 00418 00423 rcHeightfield* rcAllocHeightfield(); 00424 00429 void rcFreeHeightField(rcHeightfield* hf); 00430 00435 rcCompactHeightfield* rcAllocCompactHeightfield(); 00436 00441 void rcFreeCompactHeightfield(rcCompactHeightfield* chf); 00442 00447 rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet(); 00448 00453 void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset); 00454 00459 rcContourSet* rcAllocContourSet(); 00460 00465 void rcFreeContourSet(rcContourSet* cset); 00466 00471 rcPolyMesh* rcAllocPolyMesh(); 00472 00477 void rcFreePolyMesh(rcPolyMesh* pmesh); 00478 00483 rcPolyMeshDetail* rcAllocPolyMeshDetail(); 00484 00489 void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh); 00490 00492 00498 static const unsigned short RC_BORDER_REG = 0x8000; 00499 00507 static const int RC_BORDER_VERTEX = 0x10000; 00508 00514 static const int RC_AREA_BORDER = 0x20000; 00515 00518 enum rcBuildContoursFlags 00519 { 00520 RC_CONTOUR_TESS_WALL_EDGES = 0x01, 00521 RC_CONTOUR_TESS_AREA_EDGES = 0x02, 00522 }; 00523 00528 static const int RC_CONTOUR_REG_MASK = 0xffff; 00529 00533 static const unsigned short RC_MESH_NULL_IDX = 0xffff; 00534 00538 static const unsigned char RC_NULL_AREA = 0; 00539 00543 static const unsigned char RC_WALKABLE_AREA = 63; 00544 00547 static const int RC_NOT_CONNECTED = 0x3f; 00548 00551 00555 template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; } 00556 00561 template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; } 00562 00567 template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; } 00568 00572 template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; } 00573 00577 template<class T> inline T rcSqr(T a) { return a*a; } 00578 00584 template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); } 00585 00589 float rcSqrt(float x); 00590 00594 00599 inline void rcVcross(float* dest, const float* v1, const float* v2) 00600 { 00601 dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; 00602 dest[1] = v1[2]*v2[0] - v1[0]*v2[2]; 00603 dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; 00604 } 00605 00610 inline float rcVdot(const float* v1, const float* v2) 00611 { 00612 return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2]; 00613 } 00614 00620 inline void rcVmad(float* dest, const float* v1, const float* v2, const float s) 00621 { 00622 dest[0] = v1[0]+v2[0]*s; 00623 dest[1] = v1[1]+v2[1]*s; 00624 dest[2] = v1[2]+v2[2]*s; 00625 } 00626 00631 inline void rcVadd(float* dest, const float* v1, const float* v2) 00632 { 00633 dest[0] = v1[0]+v2[0]; 00634 dest[1] = v1[1]+v2[1]; 00635 dest[2] = v1[2]+v2[2]; 00636 } 00637 00642 inline void rcVsub(float* dest, const float* v1, const float* v2) 00643 { 00644 dest[0] = v1[0]-v2[0]; 00645 dest[1] = v1[1]-v2[1]; 00646 dest[2] = v1[2]-v2[2]; 00647 } 00648 00652 inline void rcVmin(float* mn, const float* v) 00653 { 00654 mn[0] = rcMin(mn[0], v[0]); 00655 mn[1] = rcMin(mn[1], v[1]); 00656 mn[2] = rcMin(mn[2], v[2]); 00657 } 00658 00662 inline void rcVmax(float* mx, const float* v) 00663 { 00664 mx[0] = rcMax(mx[0], v[0]); 00665 mx[1] = rcMax(mx[1], v[1]); 00666 mx[2] = rcMax(mx[2], v[2]); 00667 } 00668 00672 inline void rcVcopy(float* dest, const float* v) 00673 { 00674 dest[0] = v[0]; 00675 dest[1] = v[1]; 00676 dest[2] = v[2]; 00677 } 00678 00683 inline float rcVdist(const float* v1, const float* v2) 00684 { 00685 float dx = v2[0] - v1[0]; 00686 float dy = v2[1] - v1[1]; 00687 float dz = v2[2] - v1[2]; 00688 return rcSqrt(dx*dx + dy*dy + dz*dz); 00689 } 00690 00695 inline float rcVdistSqr(const float* v1, const float* v2) 00696 { 00697 float dx = v2[0] - v1[0]; 00698 float dy = v2[1] - v1[1]; 00699 float dz = v2[2] - v1[2]; 00700 return dx*dx + dy*dy + dz*dz; 00701 } 00702 00705 inline void rcVnormalize(float* v) 00706 { 00707 float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2])); 00708 v[0] *= d; 00709 v[1] *= d; 00710 v[2] *= d; 00711 } 00712 00717 00724 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax); 00725 00733 void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h); 00734 00745 bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height, 00746 const float* bmin, const float* bmax, 00747 float cs, float ch); 00748 00760 void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, 00761 const int* tris, int nt, unsigned char* areas); 00762 00773 void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv, 00774 const int* tris, int nt, unsigned char* areas); 00775 00788 void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y, 00789 const unsigned short smin, const unsigned short smax, 00790 const unsigned char area, const int flagMergeThr); 00791 00802 void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2, 00803 const unsigned char area, rcHeightfield& solid, 00804 const int flagMergeThr = 1); 00805 00817 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, 00818 const int* tris, const unsigned char* areas, const int nt, 00819 rcHeightfield& solid, const int flagMergeThr = 1); 00820 00832 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv, 00833 const unsigned short* tris, const unsigned char* areas, const int nt, 00834 rcHeightfield& solid, const int flagMergeThr = 1); 00835 00845 void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt, 00846 rcHeightfield& solid, const int flagMergeThr = 1); 00847 00854 void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid); 00855 00864 void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, 00865 const int walkableClimb, rcHeightfield& solid); 00866 00873 void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid); 00874 00880 int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf); 00881 00886 00897 bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb, 00898 rcHeightfield& hf, rcCompactHeightfield& chf); 00899 00906 bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf); 00907 00913 bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf); 00914 00922 void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId, 00923 rcCompactHeightfield& chf); 00924 00934 void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts, 00935 const float hmin, const float hmax, unsigned char areaId, 00936 rcCompactHeightfield& chf); 00937 00945 int rcOffsetPoly(const float* verts, const int nverts, const float offset, 00946 float* outVerts, const int maxOutVerts); 00947 00956 void rcMarkCylinderArea(rcContext* ctx, const float* pos, 00957 const float r, const float h, unsigned char areaId, 00958 rcCompactHeightfield& chf); 00959 00965 bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf); 00966 00978 bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf, 00979 const int borderSize, const int minRegionArea, const int mergeRegionArea); 00980 00992 bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf, 00993 const int borderSize, const int minRegionArea, const int mergeRegionArea); 00994 00995 01000 inline void rcSetCon(rcCompactSpan& s, int dir, int i) 01001 { 01002 const unsigned int shift = (unsigned int)dir*6; 01003 unsigned int con = s.con; 01004 s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift); 01005 } 01006 01012 inline int rcGetCon(const rcCompactSpan& s, int dir) 01013 { 01014 const unsigned int shift = (unsigned int)dir*6; 01015 return (s.con >> shift) & 0x3f; 01016 } 01017 01022 inline int rcGetDirOffsetX(int dir) 01023 { 01024 const int offset[4] = { -1, 0, 1, 0, }; 01025 return offset[dir&0x03]; 01026 } 01027 01032 inline int rcGetDirOffsetY(int dir) 01033 { 01034 const int offset[4] = { 0, 1, 0, -1 }; 01035 return offset[dir&0x03]; 01036 } 01037 01042 01053 bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, 01054 const int borderSize, const int walkableHeight, 01055 rcHeightfieldLayerSet& lset); 01056 01068 bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf, 01069 const float maxError, const int maxEdgeLen, 01070 rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES); 01071 01080 bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh); 01081 01089 bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh); 01090 01101 bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf, 01102 const float sampleDist, const float sampleMaxError, 01103 rcPolyMeshDetail& dmesh); 01104 01111 bool rcCopyPolyMesh(rcContext* ctx, const rcPolyMesh& src, rcPolyMesh& dst); 01112 01120 bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh); 01121 01123 01124 #endif // RECAST_H 01125 01127 01128 // Due to the large amount of detail documentation for this file, 01129 // the content normally located at the end of the header file has been separated 01130 // out to a file in /Docs/Extern.
1.7.3