synched with trunk at revision 30243
authorNick Samarin <nicks1987@bigmir.net>
Wed, 14 Jul 2010 07:35:39 +0000 (07:35 +0000)
committerNick Samarin <nicks1987@bigmir.net>
Wed, 14 Jul 2010 07:35:39 +0000 (07:35 +0000)
82 files changed:
extern/recastnavigation/Detour/Include/DetourCommon.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourDebugDraw.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourNode.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourStatNavMesh.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourTileNavMesh.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourCommon.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourDebugDraw.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourNode.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp [new file with mode: 0644]
extern/recastnavigation/License.txt [new file with mode: 0644]
extern/recastnavigation/Readme.txt [new file with mode: 0644]
extern/recastnavigation/Recast/Include/Recast.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastDebugDraw.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastLog.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastTimer.h [new file with mode: 0644]
extern/recastnavigation/Recast/Source/Recast.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastContour.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastDebugDraw.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastFilter.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastLog.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastRasterization.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastRegion.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastTimer.cpp [new file with mode: 0644]
extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj [new file with mode: 0644]
projectfiles_vc9/blender/blender.sln
projectfiles_vc9/blender/editors/ED_editors.vcproj
projectfiles_vc9/blender/imbuf/BL_imbuf.vcproj
projectfiles_vc9/blender/modifiers/modifiers.vcproj
projectfiles_vc9/gameengine/converter/KX_converter.vcproj
projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj
release/scripts/ui/properties_data_modifier.py
release/scripts/ui/properties_game.py
release/scripts/ui/properties_scene.py
source/blender/blenkernel/BKE_context.h
source/blender/blenkernel/intern/object.c
source/blender/blenkernel/intern/sca.c
source/blender/blenkernel/intern/scene.c
source/blender/blenloader/intern/readfile.c
source/blender/blenloader/intern/writefile.c
source/blender/editors/include/ED_object.h
source/blender/editors/object/object_intern.h
source/blender/editors/object/object_navmesh.cpp [new file with mode: 0644]
source/blender/editors/object/object_ops.c
source/blender/editors/space_logic/logic_window.c
source/blender/makesdna/DNA_actuator_types.h
source/blender/makesdna/DNA_modifier_types.h
source/blender/makesdna/DNA_object_types.h
source/blender/makesdna/DNA_scene_types.h
source/blender/makesrna/intern/rna_actuator.c
source/blender/makesrna/intern/rna_modifier.c
source/blender/makesrna/intern/rna_object.c
source/blender/makesrna/intern/rna_scene.c
source/blender/modifiers/MOD_modifiertypes.h
source/blender/modifiers/intern/MOD_navmesh.cpp [new file with mode: 0644]
source/blender/modifiers/intern/MOD_util.c
source/gameengine/Converter/BL_BlenderDataConversion.cpp
source/gameengine/Converter/KX_ConvertActuators.cpp
source/gameengine/GameLogic/SCA_IActuator.h
source/gameengine/Ketsji/KX_GameObject.cpp
source/gameengine/Ketsji/KX_GameObject.h
source/gameengine/Ketsji/KX_KetsjiEngine.cpp
source/gameengine/Ketsji/KX_NavMeshObject.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_NavMeshObject.h [new file with mode: 0644]
source/gameengine/Ketsji/KX_ObstacleSimulation.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_ObstacleSimulation.h [new file with mode: 0644]
source/gameengine/Ketsji/KX_PythonInit.cpp
source/gameengine/Ketsji/KX_PythonInit.h
source/gameengine/Ketsji/KX_PythonInitTypes.cpp
source/gameengine/Ketsji/KX_Scene.cpp
source/gameengine/Ketsji/KX_Scene.h
source/gameengine/Ketsji/KX_SteeringActuator.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_SteeringActuator.h [new file with mode: 0644]
source/gameengine/Rasterizer/RAS_IRasterizer.h
source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp
source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h

diff --git a/extern/recastnavigation/Detour/Include/DetourCommon.h b/extern/recastnavigation/Detour/Include/DetourCommon.h
new file mode 100644 (file)
index 0000000..d824efc
--- /dev/null
@@ -0,0 +1,167 @@
+//
+// Copyright (c) 2009 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 DETOURCOMMON_H
+#define DETOURCOMMON_H
+
+//////////////////////////////////////////////////////////////////////////////////////////
+
+template<class T> inline void swap(T& a, T& b) { T t = a; a = b; b = t; }
+template<class T> inline T min(T a, T b) { return a < b ? a : b; }
+template<class T> inline T max(T a, T b) { return a > b ? a : b; }
+template<class T> inline T abs(T a) { return a < 0 ? -a : a; }
+template<class T> inline T sqr(T a) { return a*a; }
+template<class T> inline T clamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }
+
+inline void vcross(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 vdot(const float* v1, const float* v2)
+{
+       return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
+}
+
+inline void vmad(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 vadd(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 vsub(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 vmin(float* mn, const float* v)
+{
+       mn[0] = min(mn[0], v[0]);
+       mn[1] = min(mn[1], v[1]);
+       mn[2] = min(mn[2], v[2]);
+}
+
+inline void vmax(float* mx, const float* v)
+{
+       mx[0] = max(mx[0], v[0]);
+       mx[1] = max(mx[1], v[1]);
+       mx[2] = max(mx[2], v[2]);
+}
+
+inline void vcopy(float* dest, const float* a)
+{
+       dest[0] = a[0];
+       dest[1] = a[1];
+       dest[2] = a[2];
+}
+
+inline float vdist(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 sqrtf(dx*dx + dy*dy + dz*dz);
+}
+
+inline float vdistSqr(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 vnormalize(float* v)
+{
+       float d = 1.0f / sqrtf(sqr(v[0]) + sqr(v[1]) + sqr(v[2]));
+       v[0] *= d;
+       v[1] *= d;
+       v[2] *= d;
+}
+
+inline bool vequal(const float* p0, const float* p1)
+{
+       static const float thr = sqr(1.0f/16384.0f);
+       const float d = vdistSqr(p0, p1);
+       return d < thr;
+}
+
+inline int nextPow2(int v)
+{
+       v--;
+       v |= v >> 1;
+       v |= v >> 2;
+       v |= v >> 4;
+       v |= v >> 8;
+       v |= v >> 16;
+       v++;
+       return v;
+}
+
+inline float vdot2D(const float* u, const float* v)
+{
+       return u[0]*v[0] + u[2]*v[2];
+}
+
+inline float vperp2D(const float* u, const float* v)
+{
+       return u[2]*v[0] - u[0]*v[2];
+}
+
+inline float triArea2D(const float* a, const float* b, const float* c)
+{
+       return ((b[0]*a[2] - a[0]*b[2]) + (c[0]*b[2] - b[0]*c[2]) + (a[0]*c[2] - c[0]*a[2])) * 0.5f;
+}
+
+inline bool checkOverlapBox(const unsigned short amin[3], const unsigned short amax[3],
+                                                       const unsigned short bmin[3], const unsigned short bmax[3])
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
+       return overlap;
+}
+
+void closestPtPointTriangle(float* closest, const float* p,
+                                                       const float* a, const float* b, const float* c);
+
+bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h);
+
+bool intersectSegmentPoly2D(const float* p0, const float* p1,
+                                                       const float* verts, int nverts,
+                                                       float& tmin, float& tmax,
+                                                       int& segMin, int& segMax);
+
+float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t);
+
+void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts);
+
+#endif // DETOURCOMMON_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourDebugDraw.h b/extern/recastnavigation/Detour/Include/DetourDebugDraw.h
new file mode 100644 (file)
index 0000000..8e1cfe4
--- /dev/null
@@ -0,0 +1,32 @@
+//
+// Copyright (c) 2009 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 DETOURDEBUGDRAW_H
+#define DETOURDEBUGDRAW_H
+
+#include "DetourStatNavMesh.h"
+#include "DetourTileNavMesh.h"
+
+void dtDebugDrawStatNavMeshPoly(const dtStatNavMesh* mesh, dtStatPolyRef ref, const float* col);
+void dtDebugDrawStatNavMeshBVTree(const dtStatNavMesh* mesh);
+void dtDebugDrawStatNavMesh(const dtStatNavMesh* mesh, bool drawClosedList = false);
+
+void dtDebugDrawTiledNavMesh(const dtTiledNavMesh* mesh);
+void dtDebugDrawTiledNavMeshPoly(const dtTiledNavMesh* mesh, dtTilePolyRef ref, const float* col);
+
+#endif // DETOURDEBUGDRAW_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourNode.h b/extern/recastnavigation/Detour/Include/DetourNode.h
new file mode 100644 (file)
index 0000000..316d5bf
--- /dev/null
@@ -0,0 +1,149 @@
+//
+// Copyright (c) 2009 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 DETOURNODE_H
+#define DETOURNODE_H
+
+enum dtNodeFlags
+{
+       DT_NODE_OPEN = 0x01,
+       DT_NODE_CLOSED = 0x02,
+};
+
+struct dtNode
+{
+       float cost;
+       float total;
+       unsigned int id;
+       unsigned int pidx : 30;
+       unsigned int flags : 2;
+};
+
+class dtNodePool
+{
+public:
+       dtNodePool(int maxNodes, int hashSize);
+       ~dtNodePool();
+       inline void operator=(const dtNodePool&) {}
+       void clear();
+       dtNode* getNode(unsigned int id);
+       const dtNode* findNode(unsigned int id) const;
+
+       inline unsigned int getNodeIdx(const dtNode* node) const
+       {
+               if (!node) return 0;
+               return (unsigned int)(node - m_nodes)+1;
+       }
+
+       inline dtNode* getNodeAtIdx(unsigned int idx)
+       {
+               if (!idx) return 0;
+               return &m_nodes[idx-1];
+       }
+       
+       inline int getMemUsed() const
+       {
+               return sizeof(*this) +
+               sizeof(dtNode)*m_maxNodes +
+               sizeof(unsigned short)*m_maxNodes +
+               sizeof(unsigned short)*m_hashSize;
+       }
+       
+private:
+       inline unsigned int hashint(unsigned int a) const
+       {
+               a += ~(a<<15);
+               a ^=  (a>>10);
+               a +=  (a<<3);
+               a ^=  (a>>6);
+               a += ~(a<<11);
+               a ^=  (a>>16);
+               return a;
+       }
+       
+       dtNode* m_nodes;
+       unsigned short* m_first;
+       unsigned short* m_next;
+       const int m_maxNodes;
+       const int m_hashSize;
+       int m_nodeCount;
+};
+
+class dtNodeQueue
+{
+public:
+       dtNodeQueue(int n);
+       ~dtNodeQueue();
+       inline void operator=(dtNodeQueue&) {}
+       
+       inline void clear()
+       {
+               m_size = 0;
+       }
+       
+       inline dtNode* top()
+       {
+               return m_heap[0];
+       }
+       
+       inline dtNode* pop()
+       {
+               dtNode* result = m_heap[0];
+               m_size--;
+               trickleDown(0, m_heap[m_size]);
+               return result;
+       }
+       
+       inline void push(dtNode* node)
+       {
+               m_size++;
+               bubbleUp(m_size-1, node);
+       }
+       
+       inline void modify(dtNode* node)
+       {
+               for (int i = 0; i < m_size; ++i)
+               {
+                       if (m_heap[i] == node)
+                       {
+                               bubbleUp(i, node);
+                               return;
+                       }
+               }
+       }
+       
+       inline bool empty() const { return m_size == 0; }
+       
+       inline int getMemUsed() const
+       {
+               return sizeof(*this) +
+               sizeof(dtNode*)*(m_capacity+1);
+       }
+       
+       
+private:
+       void bubbleUp(int i, dtNode* node);
+       void trickleDown(int i, dtNode* node);
+       
+       dtNode** m_heap;
+       const int m_capacity;
+       int m_size;
+};             
+
+
+#endif // DETOURNODE_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h b/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h
new file mode 100644 (file)
index 0000000..71ee4cb
--- /dev/null
@@ -0,0 +1,234 @@
+//
+// Copyright (c) 2009 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 DETOURSTATNAVMESH_H
+#define DETOURSTATNAVMESH_H
+
+// Reference to navigation polygon.
+typedef unsigned short dtStatPolyRef;
+
+// Maximum number of vertices per navigation polygon.
+static const int DT_STAT_VERTS_PER_POLYGON = 6;
+
+// Structure holding the navigation polygon data.
+struct dtStatPoly
+{
+       unsigned short v[DT_STAT_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
+       dtStatPolyRef n[DT_STAT_VERTS_PER_POLYGON];             // Refs to neighbours of the poly.
+       unsigned char nv;                                                               // Number of vertices.
+       unsigned char flags;                                                    // Flags (not used).
+};
+
+struct dtStatPolyDetail
+{
+       unsigned short vbase;   // Offset to detail vertex array.
+       unsigned short nverts;  // Number of vertices in the detail mesh.
+       unsigned short tbase;   // Offset to detail triangle array.
+       unsigned short ntris;   // Number of triangles.
+};
+
+const int DT_STAT_NAVMESH_MAGIC = 'NAVM';
+const int DT_STAT_NAVMESH_VERSION = 3;
+
+struct dtStatBVNode
+{
+       unsigned short bmin[3], bmax[3];
+       int i;
+};
+
+struct dtStatNavMeshHeader
+{
+       int magic;
+       int version;
+       int npolys;
+       int nverts;
+       int nnodes;
+       int ndmeshes;
+       int ndverts;
+       int ndtris;
+       float cs;
+       float bmin[3], bmax[3];
+       dtStatPoly* polys;
+       float* verts;
+       dtStatBVNode* bvtree;
+       dtStatPolyDetail* dmeshes;
+       float* dverts;
+       unsigned char* dtris;
+};
+
+class dtStatNavMesh
+{
+public:
+       
+       dtStatNavMesh();
+       ~dtStatNavMesh();
+
+       // Initializes the navmesh with data.
+       // Params:
+       //      data - (in) Pointer to navmesh data.
+       //      dataSize - (in) size of the navmesh data.
+       //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
+       bool init(unsigned char* data, int dataSize, bool ownsData);
+
+       // Finds the nearest navigation polygon around the center location.
+       // Params:
+       //      center - (in) The center of the search box.
+       //      extents - (in) The extents of the search box.
+       // Returns: Reference identifier for the polygon, or 0 if no polygons found.
+       dtStatPolyRef findNearestPoly(const float* center, const float* extents);
+
+       // Returns polygons which touch the query box.
+       // Params:
+       //      center - (in) the center of the search box.
+       //      extents - (in) the extents of the search box.
+       //      polys - (out) array holding the search result.
+       //      maxPolys - (in) The max number of polygons the polys array can hold.
+       // Returns: Number of polygons in search result array.
+       int queryPolygons(const float* center, const float* extents,
+                                         dtStatPolyRef* polys, const int maxPolys);
+       
+       // Finds path from start polygon to end polygon.
+       // If target polygon canno be reached through the navigation graph,
+       // the last node on the array is nearest node to the end polygon.
+       // Params:
+       //      startRef - (in) ref to path start polygon.
+       //      endRef - (in) ref to path end polygon.
+       //      path - (out) array holding the search result.
+       //      maxPathSize - (in) The max number of polygons the path array can hold.
+       // Returns: Number of polygons in search result array.
+       int findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
+                                const float* startPos, const float* endPos,
+                                dtStatPolyRef* path, const int maxPathSize);
+
+       // Finds a straight path from start to end locations within the corridor
+       // described by the path polygons.
+       // Start and end locations will be clamped on the corridor.
+       // Params:
+       //      startPos - (in) Path start location.
+       //      endPos - (in) Path end location.
+       //      path - (in) Array of connected polygons describing the corridor.
+       //      pathSize - (in) Number of polygons in path array.
+       //      straightPath - (out) Points describing the straight path.
+       //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
+       // Returns: Number of points in the path.
+       int findStraightPath(const float* startPos, const float* endPos,
+                                                const dtStatPolyRef* path, const int pathSize,
+                                                float* straightPath, const int maxStraightPathSize);
+
+       // Finds intersection againts walls starting from start pos.
+       // Params:
+       //      startRef - (in) ref to the polygon where the start lies.
+       //      startPos - (in) start position of the query.
+       //      endPos - (in) end position of the query.
+       //      t - (out) hit parameter along the segment, 0 if no hit.
+       //      endRef - (out) ref to the last polygon which was processed.
+       // Returns: Number of polygons in path or 0 if failed.
+       int raycast(dtStatPolyRef startRef, const float* startPos, const float* endPos,
+                                float& t, dtStatPolyRef* path, const int pathSize);
+       
+       // Returns distance to nearest wall from the specified location.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle.
+       //      maxRadius - (in) max search radius.
+       //      hitPos - (out) location of the nearest hit.
+       //      hitNormal - (out) normal of the nearest hit.
+       // Returns: Distance to nearest wall from the test location.
+       float findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
+                                                        float* hitPos, float* hitNormal);
+       
+       // Finds polygons found along the navigation graph which touch the specified circle.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle
+       //      radius - (in) radius of the query circle
+       //      resultRef - (out, opt) refs to the polygons touched by the circle.
+       //      resultParent - (out, opt) parent of each result polygon.
+       //      resultCost - (out, opt) search cost at each result polygon.
+       //      maxResult - (int) maximum capacity of search results.
+       // Returns: Number of results.
+       int     findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
+                                               dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
+                                               const int maxResult);
+
+       // Returns closest point on navigation polygon.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point to check.
+       //      closest - (out) closest point.
+       // Returns: true if closest point found.
+       bool closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const;
+
+       // Returns height of the polygon at specified location.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point where to locate the height.
+       //      height - (out) height at the location.
+       // Returns: true if oer polygon.
+       bool getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const;
+
+       // Returns pointer to a polygon based on ref.
+       const dtStatPoly* getPolyByRef(dtStatPolyRef ref) const;
+       // Returns polygon index based on ref, or -1 if failed.
+       int getPolyIndexByRef(dtStatPolyRef ref) const;
+       // Returns number of navigation polygons.
+       inline int getPolyCount() const { return m_header ? m_header->npolys : 0; }
+       // Rerturns pointer to specified navigation polygon.
+       inline const dtStatPoly* getPoly(int i) const { return &m_header->polys[i]; }
+       // Returns number of vertices.
+       inline int getVertexCount() const { return m_header ? m_header->nverts : 0; }
+       // Returns pointer to specified vertex.
+       inline const float* getVertex(int i) const { return &m_header->verts[i*3]; }
+       // Returns number of navigation polygons details.
+       inline int getPolyDetailCount() const { return m_header ? m_header->ndmeshes : 0; }
+       // Rerturns pointer to specified navigation polygon detail.
+       const dtStatPolyDetail* getPolyDetail(int i) const { return &m_header->dmeshes[i]; }
+       // Returns pointer to specified vertex.
+       inline const float* getDetailVertex(int i) const { return &m_header->dverts[i*3]; }
+       // Returns pointer to specified vertex.
+       inline const unsigned char* getDetailTri(int i) const { return &m_header->dtris[i*4]; }
+
+       bool isInClosedList(dtStatPolyRef ref) const;
+       
+       int getMemUsed() const;
+
+       inline unsigned char* getData() const { return m_data; }
+       inline int getDataSize() const { return m_dataSize; }
+       inline const dtStatNavMeshHeader* getHeader() const { return m_header; }
+       inline const dtStatBVNode* getBvTreeNodes() const { return m_header ? m_header->bvtree : 0; }
+       inline int getBvTreeNodeCount() const { return m_header ? m_header->nnodes : 0; }
+       
+private:
+
+       // Copies the locations of vertices of a polygon to an array.
+       int getPolyVerts(dtStatPolyRef ref, float* verts) const;
+       // Returns portal points between two polygons.
+       bool getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const;
+       // Returns edge mid point between two polygons.
+       bool getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const;
+
+       unsigned char* m_data;
+       int m_dataSize;
+       
+       dtStatNavMeshHeader* m_header;
+
+       class dtNodePool* m_nodePool;
+       class dtNodeQueue* m_openList;
+};
+
+#endif // DETOURSTATNAVMESH_H
diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h
new file mode 100644 (file)
index 0000000..03c79c4
--- /dev/null
@@ -0,0 +1,33 @@
+//
+// Copyright (c) 2009 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 DETOURSTATNAVMESHBUILDER_H
+#define DETOURSTATNAVMESHBUILDER_H
+
+bool dtCreateNavMeshData(const unsigned short* verts, const int nverts,
+                                                const unsigned short* polys, const int npolys, const int nvp,
+                                                const float* bmin, const float* bmax, float cs, float ch,
+                                                const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                const unsigned char* dtris, const int ndtris, 
+                                                unsigned char** outData, int* outDataSize);
+
+int createBVTree(const unsigned short* verts, const int nverts,
+                                               const unsigned short* polys, const int npolys, const int nvp,
+                                               float cs, float ch, int nnodes, dtStatBVNode* nodes);
+
+#endif // DETOURSTATNAVMESHBUILDER_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h b/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h
new file mode 100644 (file)
index 0000000..d615b17
--- /dev/null
@@ -0,0 +1,315 @@
+//
+// Copyright (c) 2009 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 DETOURTILENAVMESH_H
+#define DETOURTILENAVMESH_H
+
+// Reference to navigation polygon.
+typedef unsigned int dtTilePolyRef;
+
+// The bits used in the poly ref.
+static const int DT_TILE_REF_SALT_BITS = 12;
+static const int DT_TILE_REF_TILE_BITS = 12;
+static const int DT_TILE_REF_POLY_BITS = 8;
+static const int DT_TILE_REF_SALT_MASK = (1<<DT_TILE_REF_SALT_BITS)-1;
+static const int DT_TILE_REF_TILE_MASK = (1<<DT_TILE_REF_TILE_BITS)-1;
+static const int DT_TILE_REF_POLY_MASK = (1<<DT_TILE_REF_POLY_BITS)-1;
+
+// Maximum number of vertices per navigation polygon.
+static const int DT_TILE_VERTS_PER_POLYGON = 6;
+
+static const int DT_MAX_TILES = 1 << DT_TILE_REF_TILE_BITS;
+static const int DT_MAX_POLYGONS = 1 << DT_TILE_REF_POLY_BITS;
+
+static const int DT_TILE_NAVMESH_MAGIC = 'NAVT';
+static const int DT_TILE_NAVMESH_VERSION = 2;
+
+// Structure holding the navigation polygon data.
+struct dtTilePoly
+{
+       unsigned short v[DT_TILE_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
+       unsigned short n[DT_TILE_VERTS_PER_POLYGON];    // Refs to neighbours of the poly.
+       unsigned short links;                                                   // Base index to header 'links' array. 
+       unsigned char nlinks;                                                   // Number of links for 
+       unsigned char nv;                                                               // Number of vertices.
+       unsigned char flags;                                                    // Flags (not used).
+};
+
+struct dtTilePolyDetail
+{
+       unsigned short vbase;   // Offset to detail vertex array.
+       unsigned short nverts;  // Number of vertices in the detail mesh.
+       unsigned short tbase;   // Offset to detail triangle array.
+       unsigned short ntris;   // Number of triangles.
+};
+
+// Stucture holding a link to another polygon.
+struct dtTileLink
+{
+       dtTilePolyRef ref;                      // Neighbour reference.
+       unsigned short p;                       // Index to polygon which owns this link.
+       unsigned char e;                        // Index to polygon edge which owns this link. 
+       unsigned char side;                     // If boundary link, defines on which side the link is.
+       unsigned char bmin, bmax;       // If boundary link, defines the sub edge area.
+};
+
+struct dtTileHeader
+{
+       int magic;                                      // Magic number, used to identify the data.
+       int version;                            // Data version number.
+       int npolys;                                     // Number of polygons in the tile.
+       int nverts;                                     // Number of vertices in the tile.
+       int nlinks;                                     // Number of links in the tile (will be updated when tile is added).
+       int maxlinks;                           // Number of allocated links.
+       int ndmeshes;
+       int ndverts;
+       int ndtris;
+       float bmin[3], bmax[3];         // Bounding box of the tile.
+       dtTilePoly* polys;                      // Pointer to the polygons (will be updated when tile is added).
+       float* verts;                           // Pointer to the vertices (will be updated when tile added).
+       dtTileLink* links;                      // Pointer to the links (will be updated when tile added).
+       dtTilePolyDetail* dmeshes;
+       float* dverts;
+       unsigned char* dtris;
+};
+
+struct dtTile
+{
+       int salt;                               // Counter describing modifications to the tile.
+       int x,y;                                // Grid location of the tile.
+       dtTileHeader* header;   // Pointer to tile header.
+       unsigned char* data;    // Pointer to tile data.
+       int dataSize;                   // Size of the tile data.
+       bool ownsData;                  // Flag indicating of the navmesh should release the data.
+       dtTile* next;                   // Next free tile or, next tile in spatial grid.
+};
+
+// Encodes a tile id.
+inline dtTilePolyRef dtEncodeTileId(unsigned int salt, unsigned int it, unsigned int ip)
+{
+       return (salt << (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) | ((it+1) << DT_TILE_REF_POLY_BITS) | ip;
+}
+
+// Decodes a tile id.
+inline void dtDecodeTileId(dtTilePolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip)
+{
+       salt = (ref >> (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) & DT_TILE_REF_SALT_MASK;
+       it = ((ref >> DT_TILE_REF_POLY_BITS) & DT_TILE_REF_TILE_MASK) - 1;
+       ip = ref & DT_TILE_REF_POLY_MASK;
+}
+
+static const int DT_TILE_LOOKUP_SIZE = DT_MAX_TILES/4;
+
+class dtTiledNavMesh
+{
+public:
+       dtTiledNavMesh();
+       ~dtTiledNavMesh();
+
+       // Initializes the nav mesh.
+       // Params:
+       //  orig - (in) origin of the nav mesh tile space.
+       //  tileSiz - (in) size of a tile.
+       //  portalheight - (in) height of the portal region between tiles.
+       // Returns: True if succeed, else false.
+       bool init(const float* orig, float tileSize, float portalHeight);
+
+       // Adds new tile into the navmesh.
+       // The add will fail if the data is in wrong format,
+       // there is not enough tiles left, or if there is a tile already at the location.
+       // Params:
+       //  x,y - (in) Location of the new tile.
+       //  data - (in) Data of the new tile mesh.
+       //  dataSize - (in) Data size of the new tile mesh.
+       //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
+       // Returns: True if tile was added, else false. 
+       bool addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData);
+       
+       // Removes tile at specified location.
+       // Params:
+       //  x,y - (in) Location of the tile to remove.
+       //  data - (out) Data associated with deleted tile.
+       //  dataSize - (out) Size of the data associated with deleted tile. 
+       // Returns: True if remove suceed, else false.
+       bool removeTileAt(int x, int y, unsigned char** data, int* dataSize);
+
+       // Returns pointer to tile at specified location.
+       // Params:
+       //  x,y - (in) Location of the tile to get.
+       // Returns: pointer to tile if tile exists or 0 tile does not exists.
+       dtTile* getTileAt(int x, int y);
+
+       // Returns pointer to tile in the tile array.
+       // Params:
+       //  i - (in) Index to the tile to retrieve, must be in range [0,DT_MAX_TILES[
+       // Returns: Pointer to specified tile.
+       dtTile* getTile(int i);
+       const dtTile* getTile(int i) const;
+       
+       // Finds the nearest navigation polygon around the center location.
+       // Params:
+       //      center - (in) The center of the search box.
+       //      extents - (in) The extents of the search box.
+       // Returns: Reference identifier for the polygon, or 0 if no polygons found.
+       dtTilePolyRef findNearestPoly(const float* center, const float* extents);
+       
+       // Returns polygons which touch the query box.
+       // Params:
+       //      center - (in) the center of the search box.
+       //      extents - (in) the extents of the search box.
+       //      polys - (out) array holding the search result.
+       //      maxPolys - (in) The max number of polygons the polys array can hold.
+       // Returns: Number of polygons in search result array.
+       int queryPolygons(const float* center, const float* extents,
+                                         dtTilePolyRef* polys, const int maxPolys);
+       
+       // Finds path from start polygon to end polygon.
+       // If target polygon canno be reached through the navigation graph,
+       // the last node on the array is nearest node to the end polygon.
+       // Params:
+       //      startRef - (in) ref to path start polygon.
+       //      endRef - (in) ref to path end polygon.
+       //      path - (out) array holding the search result.
+       //      maxPathSize - (in) The max number of polygons the path array can hold.
+       // Returns: Number of polygons in search result array.
+       int findPath(dtTilePolyRef startRef, dtTilePolyRef endRef,
+                                const float* startPos, const float* endPos,
+                                dtTilePolyRef* path, const int maxPathSize);
+
+       // Finds a straight path from start to end locations within the corridor
+       // described by the path polygons.
+       // Start and end locations will be clamped on the corridor.
+       // Params:
+       //      startPos - (in) Path start location.
+       //      endPos - (in) Path end location.
+       //      path - (in) Array of connected polygons describing the corridor.
+       //      pathSize - (in) Number of polygons in path array.
+       //      straightPath - (out) Points describing the straight path.
+       //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
+       // Returns: Number of points in the path.
+       int findStraightPath(const float* startPos, const float* endPos,
+                                                const dtTilePolyRef* path, const int pathSize,
+                                                float* straightPath, const int maxStraightPathSize);
+
+       // Finds intersection againts walls starting from start pos.
+       // Params:
+       //      startRef - (in) ref to the polygon where the start lies.
+       //      startPos - (in) start position of the query.
+       //      endPos - (in) end position of the query.
+       //      t - (out) hit parameter along the segment, 0 if no hit.
+       //      endRef - (out) ref to the last polygon which was processed.
+       // Returns: Number of polygons in path or 0 if failed.
+       int raycast(dtTilePolyRef startRef, const float* startPos, const float* endPos,
+                               float& t, dtTilePolyRef* path, const int pathSize);
+
+       // Returns distance to nearest wall from the specified location.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle.
+       //      maxRadius - (in) max search radius.
+       //      hitPos - (out) location of the nearest hit.
+       //      hitNormal - (out) normal of the nearest hit.
+       // Returns: Distance to nearest wall from the test location.
+       float findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius,
+                                                        float* hitPos, float* hitNormal);
+
+       // Finds polygons found along the navigation graph which touch the specified circle.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle
+       //      radius - (in) radius of the query circle
+       //      resultRef - (out, opt) refs to the polygons touched by the circle.
+       //      resultParent - (out, opt) parent of each result polygon.
+       //      resultCost - (out, opt) search cost at each result polygon.
+       //      maxResult - (int) maximum capacity of search results.
+       // Returns: Number of results.
+       int     findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius,
+                                               dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost,
+                                               const int maxResult);
+       
+       // Returns closest point on navigation polygon.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point to check.
+       //      closest - (out) closest point.
+       // Returns: true if closest point found.
+       bool closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const;
+
+       // Returns height of the polygon at specified location.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point where to locate the height.
+       //      height - (out) height at the location.
+       // Returns: true if over polygon.
+       bool getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const;
+       
+       // Returns pointer to a polygon based on ref.
+       const dtTilePoly* getPolyByRef(dtTilePolyRef ref) const;
+
+       // Returns pointer to a polygon vertices based on ref.
+       const float* getPolyVertsByRef(dtTilePolyRef ref) const;
+
+       // Returns pointer to a polygon link based on ref.
+       const dtTileLink* getPolyLinksByRef(dtTilePolyRef ref) const;
+       
+private:
+
+       // Returns base id for the tile.
+       dtTilePolyRef getTileId(dtTile* tile);
+       // Returns neighbour tile based on side. 
+       dtTile* getNeighbourTileAt(int x, int y, int side);
+       // Returns all polygons in neighbour tile based on portal defined by the segment.
+       int findConnectingPolys(const float* va, const float* vb,
+                                                       dtTile* tile, int side,
+                                                       dtTilePolyRef* con, float* conarea, int maxcon);
+       // Builds internal polygons links for a tile.
+       void buildIntLinks(dtTile* tile);
+       // Builds external polygon links for a tile.
+       void buildExtLinks(dtTile* tile, dtTile* target, int side);
+       // Removes external links at specified side.
+       void removeExtLinks(dtTile* tile, int side);
+       // Queries polygons within a tile.
+       int queryTilePolygons(dtTile* tile, const float* qmin, const float* qmax,
+                                                 dtTilePolyRef* polys, const int maxPolys);
+                                                 
+       float getCost(dtTilePolyRef prev, dtTilePolyRef from, dtTilePolyRef to) const;
+       float getFirstCost(const float* pos, dtTilePolyRef from, dtTilePolyRef to) const;
+       float getLastCost(dtTilePolyRef from, dtTilePolyRef to, const float* pos) const;
+       float getHeuristic(const float* from, const float* to) const;
+       
+       // Returns portal points between two polygons.
+       bool getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const;
+       // Returns edge mid point between two polygons.
+       bool getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const;
+
+       float m_orig[3];
+       float m_tileSize;
+       float m_portalHeight;
+
+       dtTile* m_posLookup[DT_TILE_LOOKUP_SIZE];
+       dtTile* m_nextFree;
+       dtTile m_tiles[DT_MAX_TILES];
+       
+       dtTileLink* m_tmpLinks;
+       int m_ntmpLinks;
+
+       class dtNodePool* m_nodePool;
+       class dtNodeQueue* m_openList;
+};
+
+#endif // DETOURTILENAVMESH_H
diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h
new file mode 100644 (file)
index 0000000..643dec1
--- /dev/null
@@ -0,0 +1,29 @@
+//
+// Copyright (c) 2009 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 DETOURTILEDNAVMESHBUILDER_H
+#define DETOURTILEDNAVMESHBUILDER_H
+
+bool dtCreateNavMeshTileData(const unsigned short* verts, const int nverts,
+                                                        const unsigned short* polys, const int npolys, const int nvp,
+                                                        const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                        const unsigned char* dtris, const int ndtris, 
+                                                        const float* bmin, const float* bmax, float cs, float ch, int tileSize, int walkableClimb,
+                                                        unsigned char** outData, int* outDataSize);
+
+#endif // DETOURTILEDNAVMESHBUILDER_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Source/DetourCommon.cpp b/extern/recastnavigation/Detour/Source/DetourCommon.cpp
new file mode 100644 (file)
index 0000000..e55ce5e
--- /dev/null
@@ -0,0 +1,244 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <math.h>
+#include "DetourCommon.h"
+
+void closestPtPointTriangle(float* closest, const float* p,
+                                                       const float* a, const float* b, const float* c)
+{
+       // Check if P in vertex region outside A
+       float ab[3], ac[3], ap[3];
+       vsub(ab, b, a);
+       vsub(ac, c, a);
+       vsub(ap, p, a);
+       float d1 = vdot(ab, ap);
+       float d2 = vdot(ac, ap);
+       if (d1 <= 0.0f && d2 <= 0.0f)
+       {
+               // barycentric coordinates (1,0,0)
+               vcopy(closest, a);
+               return;
+       }
+       
+       // Check if P in vertex region outside B
+       float bp[3];
+       vsub(bp, p, b);
+       float d3 = vdot(ab, bp);
+       float d4 = vdot(ac, bp);
+       if (d3 >= 0.0f && d4 <= d3)
+       {
+               // barycentric coordinates (0,1,0)
+               vcopy(closest, b);
+               return;
+       }
+       
+       // Check if P in edge region of AB, if so return projection of P onto AB
+       float vc = d1*d4 - d3*d2;
+       if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f)
+       {
+               // barycentric coordinates (1-v,v,0)
+               float v = d1 / (d1 - d3);
+               closest[0] = a[0] + v * ab[0];
+               closest[1] = a[1] + v * ab[1];
+               closest[2] = a[2] + v * ab[2];
+               return;
+       }
+       
+       // Check if P in vertex region outside C
+       float cp[3];
+       vsub(cp, p, c);
+       float d5 = vdot(ab, cp);
+       float d6 = vdot(ac, cp);
+       if (d6 >= 0.0f && d5 <= d6)
+       {
+               // barycentric coordinates (0,0,1)
+               vcopy(closest, c);
+               return;
+       }
+       
+       // Check if P in edge region of AC, if so return projection of P onto AC
+       float vb = d5*d2 - d1*d6;
+       if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f)
+       {
+               // barycentric coordinates (1-w,0,w)
+               float w = d2 / (d2 - d6);
+               closest[0] = a[0] + w * ac[0];
+               closest[1] = a[1] + w * ac[1];
+               closest[2] = a[2] + w * ac[2];
+               return;
+       }
+       
+       // Check if P in edge region of BC, if so return projection of P onto BC
+       float va = d3*d6 - d5*d4;
+       if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f)
+       {
+               // barycentric coordinates (0,1-w,w)
+               float w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
+               closest[0] = b[0] + w * (c[0] - b[0]);
+               closest[1] = b[1] + w * (c[1] - b[1]);
+               closest[2] = b[2] + w * (c[2] - b[2]);
+               return;
+       }
+       
+       // P inside face region. Compute Q through its barycentric coordinates (u,v,w)
+       float denom = 1.0f / (va + vb + vc);
+       float v = vb * denom;
+       float w = vc * denom;
+       closest[0] = a[0] + ab[0] * v + ac[0] * w;
+       closest[1] = a[1] + ab[1] * v + ac[1] * w;
+       closest[2] = a[2] + ab[2] * v + ac[2] * w;
+}
+
+bool intersectSegmentPoly2D(const float* p0, const float* p1,
+                                                       const float* verts, int nverts,
+                                                       float& tmin, float& tmax,
+                                                       int& segMin, int& segMax)
+{
+       static const float EPS = 0.00000001f;
+       
+       tmin = 0;
+       tmax = 1;
+       segMin = -1;
+       segMax = -1;
+       
+       float dir[3];
+       vsub(dir, p1, p0);
+       
+       for (int i = 0, j = nverts-1; i < nverts; j=i++)
+       {
+               float edge[3], diff[3];
+               vsub(edge, &verts[i*3], &verts[j*3]);
+               vsub(diff, p0, &verts[j*3]);
+               float n = vperp2D(edge, diff);
+               float d = -vperp2D(edge, dir);
+               if (fabs(d) < EPS)
+               {
+                       // S is nearly parallel to this edge
+                       if (n < 0)
+                               return false;
+                       else
+                               continue;
+               }
+               float t = n / d;
+               if (d < 0)
+               {
+                       // segment S is entering across this edge
+                       if (t > tmin)
+                       {
+                               tmin = t;
+                               segMin = j;
+                               // S enters after leaving polygon
+                               if (tmin > tmax)
+                                       return false;
+                       }
+               }
+               else
+               {
+                       // segment S is leaving across this edge
+                       if (t < tmax)
+                       {
+                               tmax = t;
+                               segMax = j;
+                               // S leaves before entering polygon
+                               if (tmax < tmin)
+                                       return false;
+                       }
+               }
+       }
+       
+       return true;
+}
+
+float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t)
+{
+       float pqx = q[0] - p[0];
+       float pqz = q[2] - p[2];
+       float dx = pt[0] - p[0];
+       float dz = pt[2] - p[2];
+       float d = pqx*pqx + pqz*pqz;
+       t = pqx*dx + pqz*dz;
+       if (d > 0)
+               t /= d;
+       if (t < 0)
+               t = 0;
+       else if (t > 1)
+               t = 1;
+       
+       dx = p[0] + t*pqx - pt[0];
+       dz = p[2] + t*pqz - pt[2];
+       
+       return dx*dx + dz*dz;
+}
+
+void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts)
+{
+       tc[0] = 0.0f;
+       tc[1] = 0.0f;
+       tc[2] = 0.0f;
+       for (int j = 0; j < nidx; ++j)
+       {
+               const float* v = &verts[idx[j]*3];
+               tc[0] += v[0];
+               tc[1] += v[1];
+               tc[2] += v[2];
+       }
+       const float s = 1.0f / nidx;
+       tc[0] *= s;
+       tc[1] *= s;
+       tc[2] *= s;
+}
+
+inline float vdot2(const float* a, const float* b)
+{
+       return a[0]*b[0] + a[2]*b[2];
+}
+
+#include <stdio.h>
+
+bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h)
+{
+       float v0[3], v1[3], v2[3];
+       vsub(v0, c,a);
+       vsub(v1, b,a);
+       vsub(v2, p,a);
+       
+       const float dot00 = vdot2(v0, v0);
+       const float dot01 = vdot2(v0, v1);
+       const float dot02 = vdot2(v0, v2);
+       const float dot11 = vdot2(v1, v1);
+       const float dot12 = vdot2(v1, v2);
+       
+       // Compute barycentric coordinates
+       float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
+       float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+       float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+       // The (sloppy) epsilon is needed to allow to get height of points which
+       // are interpolated along the edges of the triangles.
+       static const float EPS = 1e-4f;
+       
+       // If point lies inside the triangle, return interpolated ycoord.
+       if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS)
+       {
+               h = a[1] + v0[1]*u + v1[1]*v;
+               return true;
+       }
+       
+       return false;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourDebugDraw.cpp b/extern/recastnavigation/Detour/Source/DetourDebugDraw.cpp
new file mode 100644 (file)
index 0000000..25f32f1
--- /dev/null
@@ -0,0 +1,496 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include "DetourDebugDraw.h"
+#include "DetourStatNavMesh.h"
+#include "SDL.h"
+#include "SDL_Opengl.h"
+
+void dtDebugDrawStatNavMeshPoly(const dtStatNavMesh* mesh, dtStatPolyRef ref, const float* col)
+{
+       int idx = mesh->getPolyIndexByRef(ref);
+       if (idx == -1) return;
+
+       glColor4f(col[0],col[1],col[2],0.25f);
+
+       if (mesh->getPolyDetailCount())
+       {
+               const dtStatPoly* p = mesh->getPoly(idx);
+               const dtStatPolyDetail* pd = mesh->getPolyDetail(idx);
+               glBegin(GL_TRIANGLES);
+               for (int j = 0; j < pd->ntris; ++j)
+               {
+                       const unsigned char* t = mesh->getDetailTri(pd->tbase+j);
+                       for (int k = 0; k < 3; ++k)
+                       {
+                               if (t[k] < p->nv)
+                                       glVertex3fv(mesh->getVertex(p->v[t[k]]));
+                               else
+                                       glVertex3fv(mesh->getDetailVertex(pd->vbase+(t[k]-p->nv)));
+                       }
+               }
+               glEnd();
+       }
+       else
+       {
+               const dtStatPoly* p = mesh->getPoly(idx);
+               glBegin(GL_TRIANGLES);
+               unsigned short vi[3];
+               for (int j = 2; j < (int)p->nv; ++j)
+               {
+                       vi[0] = p->v[0];
+                       vi[1] = p->v[j-1];
+                       vi[2] = p->v[j];
+                       for (int k = 0; k < 3; ++k)
+                       {
+                               const float* v = mesh->getVertex(vi[k]);
+                               glVertex3f(v[0], v[1]+0.2f, v[2]);
+                       }
+               }
+               glEnd();
+       }
+}
+
+static void drawBoxWire(float minx, float miny, float minz, float maxx, float maxy, float maxz, const float* col)
+{
+       glColor4fv(col);
+       
+       // Top
+       glVertex3f(minx, miny, minz);
+       glVertex3f(maxx, miny, minz);
+       glVertex3f(maxx, miny, minz);
+       glVertex3f(maxx, miny, maxz);
+       glVertex3f(maxx, miny, maxz);
+       glVertex3f(minx, miny, maxz);
+       glVertex3f(minx, miny, maxz);
+       glVertex3f(minx, miny, minz);
+       
+       // bottom
+       glVertex3f(minx, maxy, minz);
+       glVertex3f(maxx, maxy, minz);
+       glVertex3f(maxx, maxy, minz);
+       glVertex3f(maxx, maxy, maxz);
+       glVertex3f(maxx, maxy, maxz);
+       glVertex3f(minx, maxy, maxz);
+       glVertex3f(minx, maxy, maxz);
+       glVertex3f(minx, maxy, minz);
+       
+       // Sides
+       glVertex3f(minx, miny, minz);
+       glVertex3f(minx, maxy, minz);
+       glVertex3f(maxx, miny, minz);
+       glVertex3f(maxx, maxy, minz);
+       glVertex3f(maxx, miny, maxz);
+       glVertex3f(maxx, maxy, maxz);
+       glVertex3f(minx, miny, maxz);
+       glVertex3f(minx, maxy, maxz);
+}
+
+void dtDebugDrawStatNavMeshBVTree(const dtStatNavMesh* mesh)
+{
+       const float col[] = { 1,1,1,0.5f };
+       const dtStatNavMeshHeader* hdr = mesh->getHeader();
+       
+       const dtStatBVNode* nodes = mesh->getBvTreeNodes();
+       int nnodes = mesh->getBvTreeNodeCount();
+       
+       glBegin(GL_LINES);
+
+       for (int i = 0; i < nnodes; ++i)
+       {
+               const dtStatBVNode* n = &nodes[i];
+               if (n->i < 0) // Leaf indices are positive.
+                       continue;
+               drawBoxWire(hdr->bmin[0] + n->bmin[0]*hdr->cs,
+                                       hdr->bmin[1] + n->bmin[1]*hdr->cs,
+                                       hdr->bmin[2] + n->bmin[2]*hdr->cs,
+                                       hdr->bmin[0] + n->bmax[0]*hdr->cs,
+                                       hdr->bmin[1] + n->bmax[1]*hdr->cs,
+                                       hdr->bmin[2] + n->bmax[2]*hdr->cs, col);
+       }
+       glEnd();
+}
+
+
+static float distancePtLine2d(const float* pt, const float* p, const float* q)
+{
+       float pqx = q[0] - p[0];
+       float pqz = q[2] - p[2];
+       float dx = pt[0] - p[0];
+       float dz = pt[2] - p[2];
+       float d = pqx*pqx + pqz*pqz;
+       float t = pqx*dx + pqz*dz;
+       if (d != 0) t /= d;
+       dx = p[0] + t*pqx - pt[0];
+       dz = p[2] + t*pqz - pt[2];
+       return dx*dx + dz*dz;
+}
+
+static void drawStatMeshPolyBoundaries(const dtStatNavMesh* mesh, bool inner)
+{
+       static const float thr = 0.01f*0.01f;
+
+       glBegin(GL_LINES);
+       for (int i = 0; i < mesh->getPolyCount(); ++i)
+       {
+               const dtStatPoly* p = mesh->getPoly(i);
+               const dtStatPolyDetail* pd = mesh->getPolyDetail(i);
+               
+               for (int j = 0, nj = (int)p->nv; j < nj; ++j)
+               {
+                       if (inner)
+                       {
+                               // Skip non-connected edges.
+                               if (p->n[j] == 0) continue;
+                       }
+                       else
+                       {
+                               // Skip connected edges.
+                               if (p->n[j] != 0) continue;
+                       }
+                               
+                       const float* v0 = mesh->getVertex(p->v[j]);
+                       const float* v1 = mesh->getVertex(p->v[(j+1) % nj]);
+                       
+                       // Draw detail mesh edges which align with the actual poly edge.
+                       // This is really slow.
+                       for (int k = 0; k < pd->ntris; ++k)
+                       {
+                               const unsigned char* t = mesh->getDetailTri(pd->tbase+k);
+                               const float* tv[3];
+                               for (int m = 0; m < 3; ++m)
+                               {
+                                       if (t[m] < p->nv)
+                                               tv[m] = mesh->getVertex(p->v[t[m]]);
+                                       else
+                                               tv[m] = mesh->getDetailVertex(pd->vbase+(t[m]-p->nv));
+                               }
+                               for (int m = 0, n = 2; m < 3; n=m++)
+                               {
+                                       if (((t[3] >> (n*2)) & 0x3) == 0) continue;     // Skip inner edges.
+                                       if (distancePtLine2d(tv[n],v0,v1) < thr &&
+                                               distancePtLine2d(tv[m],v0,v1) < thr)
+                                       {
+                                               glVertex3fv(tv[n]);
+                                               glVertex3fv(tv[m]);
+                                       }
+                               }
+                       }
+               }
+       }
+       glEnd();
+}
+
+void dtDebugDrawStatNavMesh(const dtStatNavMesh* mesh, bool drawClosedList)
+{
+       glBegin(GL_TRIANGLES);
+       for (int i = 0; i < mesh->getPolyDetailCount(); ++i)
+       {
+               const dtStatPoly* p = mesh->getPoly(i);
+               const dtStatPolyDetail* pd = mesh->getPolyDetail(i);
+               
+               if (drawClosedList && mesh->isInClosedList(i+1))
+                       glColor4ub(255,196,0,64);
+               else
+                       glColor4ub(0,196,255,64);
+                       
+               for (int j = 0; j < pd->ntris; ++j)
+               {
+                       const unsigned char* t = mesh->getDetailTri(pd->tbase+j);
+                       for (int k = 0; k < 3; ++k)
+                       {
+                               if (t[k] < p->nv)
+                                       glVertex3fv(mesh->getVertex(p->v[t[k]]));
+                               else
+                                       glVertex3fv(mesh->getDetailVertex(pd->vbase+(t[k]-p->nv)));
+                       }
+               }
+       }
+       glEnd();
+       
+       // Draw inter poly boundaries
+       glColor4ub(0,48,64,32);
+       glLineWidth(1.5f);
+       drawStatMeshPolyBoundaries(mesh, true);
+       
+       // Draw outer poly boundaries
+       glLineWidth(2.5f);
+       glColor4ub(0,48,64,220);
+       drawStatMeshPolyBoundaries(mesh, false);
+
+       glLineWidth(1.0f);
+       
+       glPointSize(3.0f);
+       glColor4ub(0,0,0,196);
+       glBegin(GL_POINTS);
+       for (int i = 0; i < mesh->getVertexCount(); ++i)
+       {
+               const float* v = mesh->getVertex(i);
+               glVertex3f(v[0], v[1], v[2]);
+       }
+       glEnd();
+       glPointSize(1.0f);      
+}
+
+
+static void drawTilePolyBoundaries(const dtTileHeader* header, bool inner)
+{
+       static const float thr = 0.01f*0.01f;
+
+       glBegin(GL_LINES);
+       for (int i = 0; i < header->npolys; ++i)
+       {
+               const dtTilePoly* p = &header->polys[i];
+               const dtTilePolyDetail* pd = &header->dmeshes[i];
+               
+               for (int j = 0, nj = (int)p->nv; j < nj; ++j)
+               {
+                       if (inner)
+                       {
+                               if (p->n[j] == 0) continue;
+                               if (p->n[j] & 0x8000)
+                               {
+                                       bool con = false;
+                                       for (int k = 0; k < p->nlinks; ++k)
+                                       {
+                                               if (header->links[p->links+k].e == j)
+                                               {
+                                                       con = true;
+                                                       break;
+                                               }
+                                       }
+                                       if (con)
+                                               glColor4ub(255,255,255,128);
+                                       else
+                                               glColor4ub(0,0,0,128);
+                               }
+                               else
+                                       glColor4ub(0,48,64,32);
+                       }
+                       else
+                       {
+                               if (p->n[j] != 0) continue;
+                       }
+                       
+                       const float* v0 = &header->verts[p->v[j]*3];
+                       const float* v1 = &header->verts[p->v[(j+1)%nj]*3];
+                       
+                       // Draw detail mesh edges which align with the actual poly edge.
+                       // This is really slow.
+                       for (int k = 0; k < pd->ntris; ++k)
+                       {
+                               const unsigned char* t = &header->dtris[(pd->tbase+k)*4];
+                               const float* tv[3];
+                               for (int m = 0; m < 3; ++m)
+                               {
+                                       if (t[m] < p->nv)
+                                               tv[m] = &header->verts[p->v[t[m]]*3];
+                                       else
+                                               tv[m] = &header->dverts[(pd->vbase+(t[m]-p->nv))*3];
+                               }
+                               for (int m = 0, n = 2; m < 3; n=m++)
+                               {
+                                       if (((t[3] >> (n*2)) & 0x3) == 0) continue;     // Skip inner detail edges.
+                                       if (distancePtLine2d(tv[n],v0,v1) < thr &&
+                                               distancePtLine2d(tv[m],v0,v1) < thr)
+                                       {
+                                               glVertex3fv(tv[n]);
+                                               glVertex3fv(tv[m]);
+                                       }
+                               }
+                       }
+               }
+       }
+       glEnd();
+}
+
+static void drawTile(const dtTileHeader* header)
+{
+       glBegin(GL_TRIANGLES);
+       for (int i = 0; i < header->npolys; ++i)
+       {
+               const dtTilePoly* p = &header->polys[i];
+               const dtTilePolyDetail* pd = &header->dmeshes[i];
+               
+               glColor4ub(0,196,255,64);
+               
+               for (int j = 0; j < pd->ntris; ++j)
+               {
+                       const unsigned char* t = &header->dtris[(pd->tbase+j)*4];
+                       for (int k = 0; k < 3; ++k)
+                       {
+                               if (t[k] < p->nv)
+                                       glVertex3fv(&header->verts[p->v[t[k]]*3]);
+                               else
+                                       glVertex3fv(&header->dverts[(pd->vbase+t[k]-p->nv)*3]);
+                       }
+               }
+       }
+       glEnd();
+       
+       // Draw inter poly boundaries
+       glColor4ub(0,48,64,32);
+       glLineWidth(1.5f);
+       
+       drawTilePolyBoundaries(header, true);
+
+       // Draw outer poly boundaries
+       glLineWidth(2.5f);
+       glColor4ub(0,48,64,220);
+
+       drawTilePolyBoundaries(header, false);
+       
+       glLineWidth(1.0f);
+       
+       glPointSize(3.0f);
+       glColor4ub(0,0,0,196);
+       glBegin(GL_POINTS);
+       for (int i = 0; i < header->nverts; ++i)
+       {
+               const float* v = &header->verts[i*3];
+               glVertex3f(v[0], v[1], v[2]);
+       }
+       glEnd();
+       glPointSize(1.0f);      
+       
+       // Draw portals
+/*     glBegin(GL_LINES);
+
+       for (int i = 0; i < header->nportals[0]; ++i)
+       {
+               const dtTilePortal* p = &header->portals[0][i];         
+               if (p->ncon)
+                       glColor4ub(255,255,255,192);
+               else
+                       glColor4ub(255,0,0,64);
+               glVertex3f(header->bmax[0]-0.1f, p->bmin[1], p->bmin[0]);
+               glVertex3f(header->bmax[0]-0.1f, p->bmax[1], p->bmin[0]);
+
+               glVertex3f(header->bmax[0]-0.1f, p->bmax[1], p->bmin[0]);
+               glVertex3f(header->bmax[0]-0.1f, p->bmax[1], p->bmax[0]);
+
+               glVertex3f(header->bmax[0]-0.1f, p->bmax[1], p->bmax[0]);
+               glVertex3f(header->bmax[0]-0.1f, p->bmin[1], p->bmax[0]);
+
+               glVertex3f(header->bmax[0]-0.1f, p->bmin[1], p->bmax[0]);
+               glVertex3f(header->bmax[0]-0.1f, p->bmin[1], p->bmin[0]);
+       }
+       for (int i = 0; i < header->nportals[1]; ++i)
+       {
+               const dtTilePortal* p = &header->portals[1][i];
+               if (p->ncon)
+                       glColor4ub(255,255,255,192);
+               else
+                       glColor4ub(255,0,0,64);
+               glVertex3f(p->bmin[0], p->bmin[1], header->bmax[2]-0.1f);
+               glVertex3f(p->bmin[0], p->bmax[1], header->bmax[2]-0.1f);
+               
+               glVertex3f(p->bmin[0], p->bmax[1], header->bmax[2]-0.1f);
+               glVertex3f(p->bmax[0], p->bmax[1], header->bmax[2]-0.1f);
+               
+               glVertex3f(p->bmax[0], p->bmax[1], header->bmax[2]-0.1f);
+               glVertex3f(p->bmax[0], p->bmin[1], header->bmax[2]-0.1f);
+               
+               glVertex3f(p->bmax[0], p->bmin[1], header->bmax[2]-0.1f);
+               glVertex3f(p->bmin[0], p->bmin[1], header->bmax[2]-0.1f);
+       }
+       for (int i = 0; i < header->nportals[2]; ++i)
+       {
+               const dtTilePortal* p = &header->portals[2][i];
+               if (p->ncon)
+                       glColor4ub(255,255,255,192);
+               else
+                       glColor4ub(255,0,0,64);
+               glVertex3f(header->bmin[0]+0.1f, p->bmin[1], p->bmin[0]);
+               glVertex3f(header->bmin[0]+0.1f, p->bmax[1], p->bmin[0]);
+               
+               glVertex3f(header->bmin[0]+0.1f, p->bmax[1], p->bmin[0]);
+               glVertex3f(header->bmin[0]+0.1f, p->bmax[1], p->bmax[0]);
+               
+               glVertex3f(header->bmin[0]+0.1f, p->bmax[1], p->bmax[0]);
+               glVertex3f(header->bmin[0]+0.1f, p->bmin[1], p->bmax[0]);
+               
+               glVertex3f(header->bmin[0]+0.1f, p->bmin[1], p->bmax[0]);
+               glVertex3f(header->bmin[0]+0.1f, p->bmin[1], p->bmin[0]);
+       }
+       for (int i = 0; i < header->nportals[3]; ++i)
+       {
+               const dtTilePortal* p = &header->portals[3][i];
+               if (p->ncon)
+                       glColor4ub(255,255,255,192);
+               else
+                       glColor4ub(255,0,0,64);
+               glVertex3f(p->bmin[0], p->bmin[1], header->bmin[2]+0.1f);
+               glVertex3f(p->bmin[0], p->bmax[1], header->bmin[2]+0.1f);
+               
+               glVertex3f(p->bmin[0], p->bmax[1], header->bmin[2]+0.1f);
+               glVertex3f(p->bmax[0], p->bmax[1], header->bmin[2]+0.1f);
+               
+               glVertex3f(p->bmax[0], p->bmax[1], header->bmin[2]+0.1f);
+               glVertex3f(p->bmax[0], p->bmin[1], header->bmin[2]+0.1f);
+               
+               glVertex3f(p->bmax[0], p->bmin[1], header->bmin[2]+0.1f);
+               glVertex3f(p->bmin[0], p->bmin[1], header->bmin[2]+0.1f);
+       }
+       glEnd();*/
+}
+
+void dtDebugDrawTiledNavMesh(const dtTiledNavMesh* mesh)
+{
+       if (!mesh) return;
+       
+       for (int i = 0; i < DT_MAX_TILES; ++i)
+       {
+               const dtTile* tile = mesh->getTile(i);
+               if (!tile->header) continue;
+
+               drawTile(tile->header);
+       }
+}
+
+void dtDebugDrawTiledNavMeshPoly(const dtTiledNavMesh* mesh, dtTilePolyRef ref, const float* col)
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return;
+       const dtTile* tile = mesh->getTile(it);
+       if (tile->salt != salt || tile->header == 0) return;
+       const dtTileHeader* header = tile->header;
+       
+       if (ip >= (unsigned int)header->npolys) return;
+       
+       glColor4f(col[0],col[1],col[2],0.25f);
+
+       const dtTilePoly* p = &header->polys[ip];
+       const dtTilePolyDetail* pd = &header->dmeshes[ip];
+       
+       glBegin(GL_TRIANGLES);
+       for (int i = 0; i < pd->ntris; ++i)
+       {
+               const unsigned char* t = &header->dtris[(pd->tbase+i)*4];
+               for (int j = 0; j < 3; ++j)
+               {
+                       if (t[j] < p->nv)
+                               glVertex3fv(&header->verts[p->v[t[j]]*3]);
+                       else
+                               glVertex3fv(&header->dverts[(pd->vbase+t[j]-p->nv)*3]);
+               }
+       }
+       glEnd();
+}
+
diff --git a/extern/recastnavigation/Detour/Source/DetourNode.cpp b/extern/recastnavigation/Detour/Source/DetourNode.cpp
new file mode 100644 (file)
index 0000000..1a2305f
--- /dev/null
@@ -0,0 +1,140 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include "DetourNode.h"
+#include <string.h>
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtNodePool::dtNodePool(int maxNodes, int hashSize) :
+
+       m_nodes(0),
+       m_first(0),
+       m_next(0),
+       m_maxNodes(maxNodes),
+       m_hashSize(hashSize),
+       m_nodeCount(0)
+{
+       m_nodes = new dtNode[m_maxNodes];
+       m_next = new unsigned short[m_maxNodes];
+       m_first = new unsigned short[hashSize];
+       memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize);
+       memset(m_next, 0xff, sizeof(unsigned short)*m_maxNodes);
+}
+
+dtNodePool::~dtNodePool()
+{
+       delete [] m_nodes;
+       delete [] m_next;
+       delete [] m_first;
+}
+
+void dtNodePool::clear()
+{
+       memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize);
+       m_nodeCount = 0;
+}
+
+const dtNode* dtNodePool::findNode(unsigned int id) const
+{
+       unsigned int bucket = hashint(id) & (m_hashSize-1);
+       unsigned short i = m_first[bucket];
+       while (i != 0xffff)
+       {
+               if (m_nodes[i].id == id)
+                       return &m_nodes[i];
+               i = m_next[i];
+       }
+       return 0;
+}
+
+dtNode* dtNodePool::getNode(unsigned int id)
+{
+       unsigned int bucket = hashint(id) & (m_hashSize-1);
+       unsigned short i = m_first[bucket];
+       dtNode* node = 0;
+       while (i != 0xffff)
+       {
+               if (m_nodes[i].id == id)
+                       return &m_nodes[i];
+               i = m_next[i];
+       }
+       
+       if (m_nodeCount >= m_maxNodes)
+               return 0;
+       
+       i = (unsigned short)m_nodeCount;
+       m_nodeCount++;
+       
+       // Init node
+       node = &m_nodes[i];
+       node->pidx = 0;
+       node->cost = 0;
+       node->total = 0;
+       node->id = id;
+       node->flags = 0;
+       
+       m_next[i] = m_first[bucket];
+       m_first[bucket] = i;
+       
+       return node;
+}
+
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtNodeQueue::dtNodeQueue(int n) :
+       m_heap(0),
+       m_capacity(n),
+       m_size(0)
+{
+       m_heap = new dtNode*[m_capacity+1];
+}
+
+dtNodeQueue::~dtNodeQueue()
+{
+       delete [] m_heap;
+}
+
+void dtNodeQueue::bubbleUp(int i, dtNode* node)
+{
+       int parent = (i-1)/2;
+       // note: (index > 0) means there is a parent
+       while ((i > 0) && (m_heap[parent]->total > node->total))
+       {
+               m_heap[i] = m_heap[parent];
+               i = parent;
+               parent = (i-1)/2;
+       }
+       m_heap[i] = node;
+}
+
+void dtNodeQueue::trickleDown(int i, dtNode* node)
+{
+       int child = (i*2)+1;
+       while (child < m_size)
+       {
+               if (((child+1) < m_size) && 
+                       (m_heap[child]->total > m_heap[child+1]->total))
+               {
+                       child++;
+               }
+               m_heap[i] = m_heap[child];
+               i = child;
+               child = (i*2)+1;
+       }
+       bubbleUp(i, node);
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp
new file mode 100644 (file)
index 0000000..bf59cd8
--- /dev/null
@@ -0,0 +1,876 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <math.h>
+#include <float.h>
+#include <string.h>
+#include <stdio.h>
+#include "DetourStatNavMesh.h"
+#include "DetourNode.h"
+#include "DetourCommon.h"
+
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtStatNavMesh::dtStatNavMesh() :
+       m_data(0),
+       m_dataSize(0),
+       m_header(0),
+       m_nodePool(0),
+       m_openList(0)
+{
+}
+
+dtStatNavMesh::~dtStatNavMesh()
+{
+       delete m_nodePool;
+       delete m_openList;
+       if (m_data)
+               delete [] m_data;
+}
+
+bool dtStatNavMesh::init(unsigned char* data, int dataSize, bool ownsData)
+{
+       dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)data;
+       
+       if (header->magic != DT_STAT_NAVMESH_MAGIC)
+               return false;
+       if (header->version != DT_STAT_NAVMESH_VERSION)
+               return false;
+
+       const int headerSize = sizeof(dtStatNavMeshHeader);
+       const int vertsSize = sizeof(float)*3*header->nverts;
+       const int polysSize = sizeof(dtStatPoly)*header->npolys;
+       const int nodesSize = sizeof(dtStatBVNode)*header->npolys*2;
+       const int detailMeshesSize = sizeof(dtStatPolyDetail)*header->ndmeshes;
+       const int detailVertsSize = sizeof(float)*3*header->ndverts;
+       const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris;
+       
+
+       unsigned char* d = data + headerSize;
+       header->verts = (float*)d; d += vertsSize;
+       header->polys = (dtStatPoly*)d; d += polysSize;
+       header->bvtree = (dtStatBVNode*)d; d += nodesSize;
+       header->dmeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
+       header->dverts = (float*)d; d += detailVertsSize;
+       header->dtris = (unsigned char*)d; d += detailTrisSize;
+       
+       m_nodePool = new dtNodePool(2048, 256);
+       if (!m_nodePool)
+               return false;
+               
+       m_openList = new dtNodeQueue(2048);
+       if (!m_openList)
+               return false;
+       
+       if (ownsData)
+       {
+               m_data = data;
+               m_dataSize = dataSize;
+       }
+
+       m_header = header;
+
+       return true;
+}
+
+const dtStatPoly* dtStatNavMesh::getPolyByRef(dtStatPolyRef ref) const
+{
+       if (!m_header || ref == 0 || (int)ref > m_header->npolys) return 0;
+       return &m_header->polys[ref-1];
+}
+
+int dtStatNavMesh::getPolyIndexByRef(dtStatPolyRef ref) const
+{
+       if (!m_header || ref == 0 || (int)ref > m_header->npolys) return -1;
+       return (int)ref-1;
+}
+
+int dtStatNavMesh::findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
+                                                       const float* startPos, const float* endPos,
+                                                       dtStatPolyRef* path, const int maxPathSize)
+{
+       if (!m_header) return 0;
+       
+       if (!startRef || !endRef)
+               return 0;
+
+       if (!maxPathSize)
+               return 0;
+
+       if (startRef == endRef)
+       {
+               path[0] = startRef;
+               return 1;
+       }
+
+       m_nodePool->clear();
+       m_openList->clear();
+
+       static const float H_SCALE = 1.1f;      // Heuristic scale.
+       
+       dtNode* startNode = m_nodePool->getNode(startRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = vdist(startPos, endPos) * H_SCALE;
+       startNode->id = startRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+
+       dtNode* lastBestNode = startNode;
+       float lastBestNodeCost = startNode->total;
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+       
+               if (bestNode->id == endRef)
+               {
+                       lastBestNode = bestNode;
+                       break;
+               }
+
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               for (int i = 0; i < (int)poly->nv; ++i)
+               {
+                       dtStatPolyRef neighbour = poly->n[i];
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Calculate cost.
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, startPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.cost = parent->cost + vdist(p0,p1);
+                               // Special case for last node.
+                               if (newNode.id == endRef)
+                                       newNode.cost += vdist(p1, endPos);
+                               
+                               // Heuristic
+                               const float h = vdist(p1,endPos)*H_SCALE;
+                               newNode.total = newNode.cost + h;
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->cost = newNode.cost;
+                                       actualNode->total = newNode.total;
+
+                                       if (h < lastBestNodeCost)
+                                       {
+                                               lastBestNodeCost = h;
+                                               lastBestNode = actualNode;
+                                       }
+
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+
+       // Reverse the path.
+       dtNode* prev = 0;
+       dtNode* node = lastBestNode;
+       do
+       {
+               dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+               node->pidx = m_nodePool->getNodeIdx(prev);
+               prev = node;
+               node = next;
+       }
+       while (node);
+       
+       // Store path
+       node = prev;
+       int n = 0;
+       do
+       {
+               path[n++] = node->id;
+               node = m_nodePool->getNodeAtIdx(node->pidx);
+       }
+       while (node && n < maxPathSize);
+
+       return n;
+}
+
+bool dtStatNavMesh::closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const
+{
+       int idx = getPolyIndexByRef(ref);
+       if (idx == -1)
+               return false;
+
+       float closestDistSqr = FLT_MAX;
+       const dtStatPoly* p = getPoly(idx);
+       const dtStatPolyDetail* pd = getPolyDetail(idx);
+
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = getDetailTri(pd->tbase+j);
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < p->nv)
+                               v[k] = getVertex(p->v[t[k]]);
+                       else
+                               v[k] = getDetailVertex(pd->vbase+(t[k]-p->nv));
+               }
+               float pt[3];
+               closestPtPointTriangle(pt, pos, v[0], v[1], v[2]);
+               float d = vdistSqr(pos, pt);
+               if (d < closestDistSqr)
+               {
+                       vcopy(closest, pt);
+                       closestDistSqr = d;
+               }
+       }
+       
+       return true;
+}
+
+bool dtStatNavMesh::getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const
+{
+       int idx = getPolyIndexByRef(ref);
+       if (idx == -1)
+               return false;
+       
+       const dtStatPoly* p = getPoly(idx);
+       const dtStatPolyDetail* pd = getPolyDetail(idx);
+
+       for (int i = 0; i < pd->ntris; ++i)
+       {
+               const unsigned char* t = getDetailTri(pd->tbase+i);
+               const float* v[3];
+               for (int j = 0; j < 3; ++j)
+               {
+                       if (t[j] < p->nv)
+                               v[j] = getVertex(p->v[t[j]]);
+                       else
+                               v[j] = getDetailVertex(pd->vbase+(t[j]-p->nv));
+               }
+               float h;
+               if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h))
+               {
+                       if (height)
+                               *height = h;
+                       return true;
+               }
+       }
+       
+       return false;
+}
+
+int dtStatNavMesh::findStraightPath(const float* startPos, const float* endPos,
+                                                                       const dtStatPolyRef* path, const int pathSize,
+                                                                       float* straightPath, const int maxStraightPathSize)
+{
+       if (!m_header) return 0;
+       
+       if (!maxStraightPathSize)
+               return 0;
+
+       if (!path[0])
+               return 0;
+
+       int straightPathSize = 0;
+       
+       float closestStartPos[3];
+       if (!closestPointToPoly(path[0], startPos, closestStartPos))
+               return 0;
+
+       // Add start point.
+       vcopy(&straightPath[straightPathSize*3], closestStartPos);
+       straightPathSize++;
+       if (straightPathSize >= maxStraightPathSize)
+               return straightPathSize;
+
+       float closestEndPos[3];
+       if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos))
+               return 0;
+
+       float portalApex[3], portalLeft[3], portalRight[3];
+
+       if (pathSize > 1)
+       {
+               vcopy(portalApex, closestStartPos);
+               vcopy(portalLeft, portalApex);
+               vcopy(portalRight, portalApex);
+               int apexIndex = 0;
+               int leftIndex = 0;
+               int rightIndex = 0;
+
+               for (int i = 0; i < pathSize; ++i)
+               {
+                       float left[3], right[3];
+                       if (i < pathSize-1)
+                       {
+                               // Next portal.
+                               getPortalPoints(path[i], path[i+1], left, right);
+                       }
+                       else
+                       {
+                               // End of the path.
+                               vcopy(left, closestEndPos);
+                               vcopy(right, closestEndPos);
+                       }
+
+                       // Right vertex.
+                       if (vequal(portalApex, portalRight))
+                       {
+                               vcopy(portalRight, right);
+                               rightIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalRight, right) <= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalLeft, right) > 0.0f)
+                                       {
+                                               vcopy(portalRight, right);
+                                               rightIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalLeft);
+                                               apexIndex = leftIndex;
+
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+
+                                               // Restart
+                                               i = apexIndex;
+
+                                               continue;
+                                       }
+                               }
+                       }
+
+                       // Left vertex.
+                       if (vequal(portalApex, portalLeft))
+                       {
+                               vcopy(portalLeft, left);
+                               leftIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalLeft, left) >= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalRight, left) < 0.0f)
+                                       {
+                                               vcopy(portalLeft, left);
+                                               leftIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalRight);
+                                               apexIndex = rightIndex;
+
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+
+                                               // Restart
+                                               i = apexIndex;
+
+                                               continue;
+                                       }
+                               }
+                       }
+               }
+       }
+
+       // Add end point.
+       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+       straightPathSize++;
+       
+       return straightPathSize;
+}
+
+int dtStatNavMesh::getPolyVerts(dtStatPolyRef ref, float* verts) const
+{
+       if (!m_header) return 0;
+       const dtStatPoly* poly = getPolyByRef(ref);
+       if (!poly) return 0;
+       float* v = verts;
+       for (int i = 0; i < (int)poly->nv; ++i)
+       {
+               const float* cv = &m_header->verts[poly->v[i]*3];
+               *v++ = cv[0];
+               *v++ = cv[1];
+               *v++ = cv[2];
+       }
+       return (int)poly->nv;
+}
+
+int dtStatNavMesh::raycast(dtStatPolyRef centerRef, const float* startPos, const float* endPos,
+                                         float& t, dtStatPolyRef* path, const int pathSize)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+       
+       dtStatPolyRef prevRef = centerRef;
+       dtStatPolyRef curRef = centerRef;
+       t = 0;
+
+       float verts[DT_STAT_VERTS_PER_POLYGON*3];
+       int n = 0;
+
+       while (curRef)
+       {
+               // Cast ray against current polygon.
+               int nv = getPolyVerts(curRef, verts);
+               if (nv < 3)
+               {
+                       // Hit bad polygon, report hit.
+                       return n;
+               }
+               
+               float tmin, tmax;
+               int segMin, segMax;
+               if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
+               {
+                       // Could not a polygon, keep the old t and report hit.
+                       return n;
+               }
+               // Keep track of furthest t so far.
+               if (tmax > t)
+                       t = tmax;
+
+               if (n < pathSize)
+                       path[n++] = curRef;
+
+               // Check the neighbour of this polygon.
+               const dtStatPoly* poly = getPolyByRef(curRef);
+               dtStatPolyRef nextRef = poly->n[segMax];
+               if (!nextRef)
+               {
+                       // No neighbour, we hit a wall.
+                       return n;
+               }
+               
+               // No hit, advance to neighbour polygon.
+               prevRef = curRef;
+               curRef = nextRef;
+       }
+       
+       return n;
+}
+
+
+float dtStatNavMesh::findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
+                                                                 float* hitPos, float* hitNormal)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       float radiusSqr = sqr(maxRadius);
+       
+       hitNormal[0] = 1;
+       hitNormal[1] = 0;
+       hitNormal[2] = 0;
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               
+               // Hit test walls.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip non-solid edges.
+                       if (poly->n[j]) continue;
+                       
+                       // Calc distance to the edge.
+                       const float* vj = getVertex(poly->v[j]);
+                       const float* vi = getVertex(poly->v[i]);
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                               
+                       // Hit wall, update radius.
+                       radiusSqr = distSqr;
+                       // Calculate hit pos.
+                       hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
+                       hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
+                       hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
+               }
+
+               // Check to see if teh circle expands to one of the neighbours and expand.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip solid edges.
+                       if (!poly->n[j]) continue;
+                       
+                       // Expand to neighbour if not visited yet.
+                       dtStatPolyRef neighbour = poly->n[j];
+                       
+                       // Skip parent node.
+                       if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                               continue;
+                       
+                       // Calc distance to the edge.
+                       const float* vj = getVertex(poly->v[j]);
+                       const float* vi = getVertex(poly->v[i]);
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                       
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                       
+                       dtNode* parent = bestNode;
+                       dtNode newNode;
+                       newNode.pidx = m_nodePool->getNodeIdx(parent);
+                       newNode.id = neighbour;
+                       
+                       // Cost
+                       float p0[3], p1[3];
+                       if (!parent->pidx)
+                               vcopy(p0, centerPos);
+                       else
+                               getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                       getEdgeMidPoint(parent->id, newNode.id, p1);
+                       newNode.total = parent->total + vdist(p0,p1);
+                       
+                       dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                       if (!actualNode)
+                               continue;
+
+                       if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                               !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                       {
+                               actualNode->flags &= ~DT_NODE_CLOSED;
+                               actualNode->pidx = newNode.pidx;
+                               actualNode->total = newNode.total;
+                               
+                               if (actualNode->flags & DT_NODE_OPEN)
+                               {
+                                       m_openList->modify(actualNode);
+                               }
+                               else
+                               {
+                                       actualNode->flags |= DT_NODE_OPEN;
+                                       m_openList->push(actualNode);
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+
+       // Calc hit normal.
+       vsub(hitNormal, centerPos, hitPos);
+       vnormalize(hitNormal);
+       
+       return sqrtf(radiusSqr);
+}
+
+int dtStatNavMesh::findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
+                                                                  dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
+                                                                  const int maxResult)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+
+       m_nodePool->clear();
+       m_openList->clear();
+
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+
+       int n = 0;
+       if (n < maxResult)
+       {
+               if (resultRef)
+                       resultRef[n] = startNode->id;
+               if (resultParent)
+                       resultParent[n] = 0;
+               if (resultCost)
+                       resultCost[n] = 0;
+               ++n;
+       }
+
+       const float radiusSqr = sqr(radius);
+
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               for (unsigned i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j=i++)
+               {
+                       dtStatPolyRef neighbour = poly->n[j];
+
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                                       
+                               // Calc distance to the edge.
+                               const float* vj = getVertex(poly->v[j]);
+                               const float* vi = getVertex(poly->v[i]);
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Cost
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               if (n < maxResult)
+                                               {
+                                                       if (resultRef)
+                                                               resultRef[n] = actualNode->id;
+                                                       if (resultParent)
+                                                               resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id;
+                                                       if (resultCost)
+                                                               resultCost[n] = actualNode->total;
+                                                       ++n;
+                                               }
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+               
+       }
+
+       return n;
+}
+
+// Returns polygons which are withing certain radius from the query location.
+int dtStatNavMesh::queryPolygons(const float* center, const float* extents,
+                                                                dtStatPolyRef* polys, const int maxIds)
+{
+       if (!m_header) return 0;
+       
+       const dtStatBVNode* node = &m_header->bvtree[0];
+       const dtStatBVNode* end = &m_header->bvtree[m_header->nnodes];
+
+       // Calculate quantized box
+       const float ics = 1.0f / m_header->cs;
+       unsigned short bmin[3], bmax[3];
+       // Clamp query box to world box.
+       float minx = clamp(center[0] - extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0];
+       float miny = clamp(center[1] - extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1];
+       float minz = clamp(center[2] - extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2];
+       float maxx = clamp(center[0] + extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0];
+       float maxy = clamp(center[1] + extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1];
+       float maxz = clamp(center[2] + extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2];
+       // Quantize
+       bmin[0] = (unsigned short)(ics * minx) & 0xfffe;
+       bmin[1] = (unsigned short)(ics * miny) & 0xfffe;
+       bmin[2] = (unsigned short)(ics * minz) & 0xfffe;
+       bmax[0] = (unsigned short)(ics * maxx + 1) | 1;
+       bmax[1] = (unsigned short)(ics * maxy + 1) | 1;
+       bmax[2] = (unsigned short)(ics * maxz + 1) | 1;
+       
+       // Traverse tree
+       int n = 0;
+       while (node < end)
+       {
+               bool overlap = checkOverlapBox(bmin, bmax, node->bmin, node->bmax);
+               bool isLeafNode = node->i >= 0;
+               
+               if (isLeafNode && overlap)
+               {
+                       if (n < maxIds)
+                       {
+                               polys[n] = (dtStatPolyRef)node->i;
+                               n++;
+                       }
+               }
+               
+               if (overlap || isLeafNode)
+                       node++;
+               else
+               {
+                       const int escapeIndex = -node->i;
+                       node += escapeIndex;
+               }
+       }
+       
+       return n;
+}
+
+dtStatPolyRef dtStatNavMesh::findNearestPoly(const float* center, const float* extents)
+{
+       if (!m_header) return 0;
+       
+       // Get nearby polygons from proximity grid.
+       dtStatPolyRef polys[128];
+       int npolys = queryPolygons(center, extents, polys, 128);
+
+       // Find nearest polygon amongst the nearby polygons.
+       dtStatPolyRef nearest = 0;
+       float nearestDistanceSqr = FLT_MAX;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPolyRef ref = polys[i];
+               float closest[3];
+               if (!closestPointToPoly(ref, center, closest))
+                       continue;
+               float d = vdistSqr(center, closest);
+               if (d < nearestDistanceSqr)
+               {
+                       nearestDistanceSqr = d;
+                       nearest = ref;
+               }
+       }
+
+       return nearest;
+}
+
+bool dtStatNavMesh::getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const
+{
+       const dtStatPoly* fromPoly = getPolyByRef(from);
+       if (!fromPoly)
+               return false;
+
+       // Find common edge between the polygons and returns the segment end points.
+       for (unsigned i = 0, j = (int)fromPoly->nv - 1; i < (int)fromPoly->nv; j = i++)
+       {
+               unsigned short neighbour = fromPoly->n[j];
+               if (neighbour == to)
+               {
+                       vcopy(left, getVertex(fromPoly->v[j]));
+                       vcopy(right, getVertex(fromPoly->v[i]));
+                       return true;
+               }
+       }
+
+       return false;
+}
+
+bool dtStatNavMesh::getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const
+{
+       float left[3], right[3];
+       if (!getPortalPoints(from, to, left,right)) return false;
+       mid[0] = (left[0]+right[0])*0.5f;
+       mid[1] = (left[1]+right[1])*0.5f;
+       mid[2] = (left[2]+right[2])*0.5f;
+       return true;
+}
+
+bool dtStatNavMesh::isInClosedList(dtStatPolyRef ref) const
+{
+       if (!m_nodePool) return false;
+       const dtNode* node = m_nodePool->findNode(ref);
+       return node && node->flags & DT_NODE_CLOSED;
+}
+
+int dtStatNavMesh::getMemUsed() const
+{
+       if (!m_nodePool || ! m_openList)
+               return 0;
+       return sizeof(*this) + m_dataSize +
+                       m_nodePool->getMemUsed() +
+                       m_openList->getMemUsed();
+}      
diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp
new file mode 100644 (file)
index 0000000..2ca455f
--- /dev/null
@@ -0,0 +1,346 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <math.h>
+#include <stdlib.h>
+#include <string.h>
+#include "DetourStatNavMesh.h"
+
+struct BVItem
+{
+       unsigned short bmin[3];
+       unsigned short bmax[3];
+       int i;
+};
+
+static int compareItemX(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[0] < b->bmin[0])
+               return -1;
+       if (a->bmin[0] > b->bmin[0])
+               return 1;
+       return 0;
+}
+
+static int compareItemY(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[1] < b->bmin[1])
+               return -1;
+       if (a->bmin[1] > b->bmin[1])
+               return 1;
+       return 0;
+}
+
+static int compareItemZ(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[2] < b->bmin[2])
+               return -1;
+       if (a->bmin[2] > b->bmin[2])
+               return 1;
+       return 0;
+}
+
+static void calcExtends(BVItem* items, int nitems, int imin, int imax,
+                                               unsigned short* bmin, unsigned short* bmax)
+{
+       bmin[0] = items[imin].bmin[0];
+       bmin[1] = items[imin].bmin[1];
+       bmin[2] = items[imin].bmin[2];
+       
+       bmax[0] = items[imin].bmax[0];
+       bmax[1] = items[imin].bmax[1];
+       bmax[2] = items[imin].bmax[2];
+       
+       for (int i = imin+1; i < imax; ++i)
+       {
+               const BVItem& it = items[i];
+               if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
+               if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];
+               if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2];
+               
+               if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
+               if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
+               if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2];
+       }
+}
+
+inline int longestAxis(unsigned short x, unsigned short y, unsigned short z)
+{
+       int     axis = 0;
+       unsigned short maxVal = x;
+       if (y > maxVal)
+       {
+               axis = 1;
+               maxVal = y;
+       }
+       if (z > maxVal)
+       {
+               axis = 2;
+               maxVal = z;
+       }
+       return axis;
+}
+
+static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNode, dtStatBVNode* nodes)
+{
+       int inum = imax - imin;
+       int icur = curNode;
+       
+       dtStatBVNode& node = nodes[curNode++];
+       
+       if (inum == 1)
+       {
+               // Leaf
+               node.bmin[0] = items[imin].bmin[0];
+               node.bmin[1] = items[imin].bmin[1];
+               node.bmin[2] = items[imin].bmin[2];
+               
+               node.bmax[0] = items[imin].bmax[0];
+               node.bmax[1] = items[imin].bmax[1];
+               node.bmax[2] = items[imin].bmax[2];
+               
+               node.i = items[imin].i;
+       }
+       else
+       {
+               // Split
+               calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);
+               
+               int     axis = longestAxis(node.bmax[0] - node.bmin[0],
+                                                          node.bmax[1] - node.bmin[1],
+                                                          node.bmax[2] - node.bmin[2]);
+               
+               if (axis == 0)
+               {
+                       // Sort along x-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemX);
+               }
+               else if (axis == 1)
+               {
+                       // Sort along y-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemY);
+               }
+               else
+               {
+                       // Sort along z-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemZ);
+               }
+               
+               int isplit = imin+inum/2;
+               
+               // Left
+               subdivide(items, nitems, imin, isplit, curNode, nodes);
+               // Right
+               subdivide(items, nitems, isplit, imax, curNode, nodes);
+               
+               int iescape = curNode - icur;
+               // Negative index means escape.
+               node.i = -iescape;
+       }
+}
+
+/*static*/ int createBVTree(const unsigned short* verts, const int nverts,
+                                               const unsigned short* polys, const int npolys, const int nvp,
+                                               float cs, float ch,
+                                               int nnodes, dtStatBVNode* nodes)
+{
+       // Build tree
+       BVItem* items = new BVItem[npolys];
+       for (int i = 0; i < npolys; i++)
+       {
+               BVItem& it = items[i];
+               it.i = i+1;
+               // Calc polygon bounds.
+               const unsigned short* p = &polys[i*nvp*2];
+               it.bmin[0] = it.bmax[0] = verts[p[0]*3+0];
+               it.bmin[1] = it.bmax[1] = verts[p[0]*3+1];
+               it.bmin[2] = it.bmax[2] = verts[p[0]*3+2];
+               
+               for (int j = 1; j < nvp; ++j)
+               {
+                       if (p[j] == 0xffff) break;
+                       unsigned short x = verts[p[j]*3+0];
+                       unsigned short y = verts[p[j]*3+1];
+                       unsigned short z = verts[p[j]*3+2];
+                       
+                       if (x < it.bmin[0]) it.bmin[0] = x;
+                       if (y < it.bmin[1]) it.bmin[1] = y;
+                       if (z < it.bmin[2]) it.bmin[2] = z;
+                       
+                       if (x > it.bmax[0]) it.bmax[0] = x;
+                       if (y > it.bmax[1]) it.bmax[1] = y;
+                       if (z > it.bmax[2]) it.bmax[2] = z;
+               }
+               // Remap y
+               it.bmin[1] = (unsigned short)floorf((float)it.bmin[1]*ch/cs);
+               it.bmax[1] = (unsigned short)ceilf((float)it.bmax[1]*ch/cs);
+       }
+       
+       int curNode = 0;
+       subdivide(items, npolys, 0, npolys, curNode, nodes);
+       
+       delete [] items;
+       
+       return curNode;
+}
+
+
+bool dtCreateNavMeshData(const unsigned short* verts, const int nverts,
+                                                const unsigned short* polys, const int npolys, const int nvp,
+                                                const float* bmin, const float* bmax, float cs, float ch,
+                                                const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                const unsigned char* dtris, const int ndtris, 
+                                                unsigned char** outData, int* outDataSize)
+{
+       if (nvp > DT_STAT_VERTS_PER_POLYGON)
+               return false;
+       if (nverts >= 0xffff)
+               return false;
+               
+       if (!nverts)
+               return false;
+       if (!npolys)
+               return false;
+       if (!dmeshes || !dverts || ! dtris)
+               return false;
+       
+       // Find unique detail vertices.
+       int uniqueDetailVerts = 0;
+       if (dmeshes)
+       {
+               for (int i = 0; i < npolys; ++i)
+               {
+                       const unsigned short* p = &polys[i*nvp*2];
+                       int ndv = dmeshes[i*4+1];
+                       int nv = 0;
+                       for (int j = 0; j < nvp; ++j)
+                       {
+                               if (p[j] == 0xffff) break;
+                               nv++;
+                       }
+                       ndv -= nv;
+                       uniqueDetailVerts += ndv;
+               }
+       }
+       
+       // Calculate data size
+       const int headerSize = sizeof(dtStatNavMeshHeader);
+       const int vertsSize = sizeof(float)*3*nverts;
+       const int polysSize = sizeof(dtStatPoly)*npolys;
+       const int nodesSize = sizeof(dtStatBVNode)*npolys*2;
+       const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys;
+       const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts;
+       const int detailTrisSize = sizeof(unsigned char)*4*ndtris;
+       
+       const int dataSize = headerSize + vertsSize + polysSize + nodesSize +
+                                                detailMeshesSize + detailVertsSize + detailTrisSize;
+       unsigned char* data = new unsigned char[dataSize];
+       if (!data)
+               return false;
+       memset(data, 0, dataSize);
+
+       unsigned char* d = data;
+       dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize;
+       float* navVerts = (float*)d; d += vertsSize;
+       dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize;
+       dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize;
+       dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
+       float* navDVerts = (float*)d; d += detailVertsSize;
+       unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
+       
+       // Store header
+       header->magic = DT_STAT_NAVMESH_MAGIC;
+       header->version = DT_STAT_NAVMESH_VERSION;
+       header->npolys = npolys;
+       header->nverts = nverts;
+       header->cs = cs;
+       header->bmin[0] = bmin[0];
+       header->bmin[1] = bmin[1];
+       header->bmin[2] = bmin[2];
+       header->bmax[0] = bmax[0];
+       header->bmax[1] = bmax[1];
+       header->bmax[2] = bmax[2];
+       header->ndmeshes = dmeshes ? npolys : 0;
+       header->ndverts = dmeshes ? uniqueDetailVerts : 0;
+       header->ndtris = dmeshes ? ndtris : 0;
+       
+       // Store vertices
+       for (int i = 0; i < nverts; ++i)
+       {
+               const unsigned short* iv = &verts[i*3];
+               float* v = &navVerts[i*3];
+               v[0] = bmin[0] + iv[0] * cs;
+               v[1] = bmin[1] + iv[1] * ch;
+               v[2] = bmin[2] + iv[2] * cs;
+       }
+       
+       // Store polygons
+       const unsigned short* src = polys;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPoly* p = &navPolys[i];
+               p->nv = 0;
+               for (int j = 0; j < nvp; ++j)
+               {
+                       if (src[j] == 0xffff) break;
+                       p->v[j] = src[j];
+                       p->n[j] = src[nvp+j]+1;
+                       p->nv++;
+               }
+               src += nvp*2;
+       }
+       
+       header->nnodes = createBVTree(verts, nverts, polys, npolys, nvp,
+                                        cs, ch, npolys*2, navNodes);
+       
+
+       // Store detail meshes and vertices.
+       // The nav polygon vertices are stored as the first vertices on each mesh.
+       // We compress the mesh data by skipping them and using the navmesh coordinates.
+       unsigned short vbase = 0;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPolyDetail& dtl = navDMeshes[i];
+               const int vb = dmeshes[i*4+0];
+               const int ndv = dmeshes[i*4+1];
+               const int nv = navPolys[i].nv;
+               dtl.vbase = vbase;
+               dtl.nverts = ndv-nv;
+               dtl.tbase = dmeshes[i*4+2];
+               dtl.ntris = dmeshes[i*4+3];
+               // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
+               if (ndv-nv)
+               {
+                       memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
+                       vbase += ndv-nv;
+               }
+       }
+       // Store triangles.
+       memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris);
+       
+       *outData = data;
+       *outDataSize = dataSize;
+       
+       return true;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp
new file mode 100644 (file)
index 0000000..0813c77
--- /dev/null
@@ -0,0 +1,1428 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <math.h>
+#include <float.h>
+#include <string.h>
+#include <stdio.h>
+#include "DetourTileNavMesh.h"
+#include "DetourNode.h"
+#include "DetourCommon.h"
+
+
+inline int opposite(int side) { return (side+2) & 0x3; }
+
+inline bool overlapBoxes(const float* amin, const float* amax,
+                                                const float* bmin, const float* bmax)
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
+       return overlap;
+}
+
+inline bool overlapRects(const float* amin, const float* amax,
+                                                const float* bmin, const float* bmax)
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       return overlap;
+}
+
+static void calcRect(const float* va, const float* vb,
+                                        float* bmin, float* bmax,
+                                        int side, float padx, float pady)
+{
+       if ((side&1) == 0)
+       {
+               bmin[0] = min(va[2],vb[2]) + padx;
+               bmin[1] = min(va[1],vb[1]) - pady;
+               bmax[0] = max(va[2],vb[2]) - padx;
+               bmax[1] = max(va[1],vb[1]) + pady;
+       }
+       else
+       {
+               bmin[0] = min(va[0],vb[0]) + padx;
+               bmin[1] = min(va[1],vb[1]) - pady;
+               bmax[0] = max(va[0],vb[0]) - padx;
+               bmax[1] = max(va[1],vb[1]) + pady;
+       }
+}
+
+inline int computeTileHash(int x, int y)
+{
+       const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
+       const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
+       unsigned int n = h1 * x + h2 * y;
+       return (int)(n & (DT_TILE_LOOKUP_SIZE-1));
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtTiledNavMesh::dtTiledNavMesh() :
+       m_tileSize(0),
+       m_portalHeight(0),
+       m_nextFree(0),
+       m_tmpLinks(0),
+       m_ntmpLinks(0),
+       m_nodePool(0),
+       m_openList(0)
+{
+}
+
+dtTiledNavMesh::~dtTiledNavMesh()
+{
+       for (int i = 0; i < DT_MAX_TILES; ++i)
+       {
+               if (m_tiles[i].data && m_tiles[i].dataSize < 0)
+               {
+                       delete [] m_tiles[i].data;
+                       m_tiles[i].data = 0;
+                       m_tiles[i].dataSize = 0;
+               }
+       }
+       delete [] m_tmpLinks;
+       delete m_nodePool;
+       delete m_openList;
+}
+               
+bool dtTiledNavMesh::init(const float* orig, float tileSize, float portalHeight)
+{
+       vcopy(m_orig, orig);
+       m_tileSize = tileSize;
+       m_portalHeight = portalHeight;
+       
+       // Init tiles
+       memset(m_tiles, 0, sizeof(dtTile)*DT_MAX_TILES);
+       memset(m_posLookup, 0, sizeof(dtTile*)*DT_TILE_LOOKUP_SIZE);
+       m_nextFree = 0;
+       for (int i = DT_MAX_TILES-1; i >= 0; --i)
+       {
+               m_tiles[i].next = m_nextFree;
+               m_nextFree = &m_tiles[i];
+       }
+
+       if (!m_nodePool)
+       {
+               m_nodePool = new dtNodePool(2048, 256);
+               if (!m_nodePool)
+                       return false;
+       }
+       
+       if (!m_openList)
+       {
+               m_openList = new dtNodeQueue(2048);
+               if (!m_openList)
+                       return false;
+       }
+       
+       return true;
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////
+int dtTiledNavMesh::findConnectingPolys(const float* va, const float* vb,
+                                                                               dtTile* tile, int side,
+                                                                               dtTilePolyRef* con, float* conarea, int maxcon)
+{
+       if (!tile) return 0;
+       dtTileHeader* h = tile->header;
+       
+       float amin[2], amax[2];
+       calcRect(va,vb, amin,amax, side, 0.01f, m_portalHeight);
+
+       // Remove links pointing to 'side' and compact the links array. 
+       float bmin[2], bmax[2];
+       unsigned short m = 0x8000 | (unsigned short)side;
+       int n = 0;
+       
+       dtTilePolyRef base = getTileId(tile);
+       
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip edges which do not point to the right side.
+                       if (poly->n[j] != m) continue;
+                       // Check if the segments touch.
+                       const float* vc = &h->verts[poly->v[j]*3];
+                       const float* vd = &h->verts[poly->v[(j+1) % (int)poly->nv]*3];
+                       calcRect(vc,vd, bmin,bmax, side, 0.01f, m_portalHeight);
+                       if (!overlapRects(amin,amax, bmin,bmax)) continue;
+                       // Add return value.
+                       if (n < maxcon)
+                       {
+                               conarea[n*2+0] = max(amin[0], bmin[0]);
+                               conarea[n*2+1] = min(amax[0], bmax[0]);
+                               con[n] = base | (unsigned int)i;
+                               n++;
+                       }
+                       break;
+               }
+       }
+       return n;
+}
+
+void dtTiledNavMesh::removeExtLinks(dtTile* tile, int side)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+       
+       // Remove links pointing to 'side' and compact the links array. 
+       dtTileLink* pool = m_tmpLinks;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               int plinks = nlinks;
+               int nplinks = 0;                
+               for (int j = 0; j < poly->nlinks; ++j)
+               {
+                       dtTileLink* link = &h->links[poly->links+j];
+                       if ((int)link->side != side)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* dst = &pool[nlinks++];
+                                       memcpy(dst, link, sizeof(dtTileLink));
+                                       nplinks++;
+                               }
+                       }
+               }
+               poly->links = plinks;
+               poly->nlinks = nplinks;
+       }
+       h->nlinks = nlinks;
+       if (h->nlinks)
+               memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks);
+}
+
+void dtTiledNavMesh::buildExtLinks(dtTile* tile, dtTile* target, int side)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+       
+       // Remove links pointing to 'side' and compact the links array. 
+       dtTileLink* pool = m_tmpLinks;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               int plinks = nlinks;
+               int nplinks = 0;
+               // Copy internal and other external links.
+               for (int j = 0; j < poly->nlinks; ++j)
+               {
+                       dtTileLink* link = &h->links[poly->links+j];
+                       if ((int)link->side != side)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* dst = &pool[nlinks++];
+                                       memcpy(dst, link, sizeof(dtTileLink));
+                                       nplinks++;
+                               }
+                       }
+               }
+               // Create new links.
+               unsigned short m = 0x8000 | (unsigned short)side;
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip edges which do not point to the right side.
+                       if (poly->n[j] != m) continue;
+                       
+                       // Create new links
+                       const float* va = &h->verts[poly->v[j]*3];
+                       const float* vb = &h->verts[poly->v[(j+1)%(int)poly->nv]*3];
+                       dtTilePolyRef nei[4];
+                       float neia[4*2];
+                       int nnei = findConnectingPolys(va,vb, target, opposite(side), nei,neia,4);
+                       for (int k = 0; k < nnei; ++k)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* link = &pool[nlinks++];
+                                       link->ref = nei[k];
+                                       link->p = (unsigned short)i;
+                                       link->e = (unsigned char)j;
+                                       link->side = (unsigned char)side;
+
+                                       // Compress portal limits to a byte value.
+                                       if (side == 0 || side == 2)
+                                       {
+                                               const float lmin = min(va[2], vb[2]);
+                                               const float lmax = max(va[2], vb[2]);
+                                               link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                               link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                       }
+                                       else
+                                       {
+                                               const float lmin = min(va[0], vb[0]);
+                                               const float lmax = max(va[0], vb[0]);
+                                               link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                               link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                       }                                       
+                                       nplinks++;
+                               }
+                       }
+               }
+               
+               poly->links = plinks;
+               poly->nlinks = nplinks;
+       }
+       h->nlinks = nlinks;
+       if (h->nlinks)
+               memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks);
+}
+
+void dtTiledNavMesh::buildIntLinks(dtTile* tile)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+
+       dtTilePolyRef base = getTileId(tile);
+       dtTileLink* pool = h->links;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               poly->links = nlinks;
+               poly->nlinks = 0;
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip hard and non-internal edges.
+                       if (poly->n[j] == 0 || (poly->n[j] & 0x8000)) continue;
+                       
+                       if (nlinks < h->maxlinks)
+                       {
+                               dtTileLink* link = &pool[nlinks++];
+                               link->ref = base | (unsigned int)(poly->n[j]-1);
+                               link->p = (unsigned short)i;
+                               link->e = (unsigned char)j;
+                               link->side = 0xff;
+                               link->bmin = link->bmax = 0;
+                               poly->nlinks++;
+                       }
+               }
+       }
+       h->nlinks = nlinks;
+}
+
+bool dtTiledNavMesh::addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData)
+{
+       if (getTileAt(x,y))
+               return false;
+       // Make sure there is enough space for new tile.
+       if (!m_nextFree)
+               return false;
+       // Make sure the data is in right format.
+       dtTileHeader* header = (dtTileHeader*)data;
+       if (header->magic != DT_TILE_NAVMESH_MAGIC)
+               return false;
+       if (header->version != DT_TILE_NAVMESH_VERSION)
+               return false;
+       
+       // Make sure the tmp link array is large enough.
+       if (header->maxlinks > m_ntmpLinks)
+       {
+               m_ntmpLinks = header->maxlinks;
+               delete [] m_tmpLinks;
+               m_tmpLinks = 0;
+               m_tmpLinks = new dtTileLink[m_ntmpLinks];
+       }
+       if (!m_tmpLinks)
+               return false;
+       
+       // Allocate a tile.
+       dtTile* tile = m_nextFree;
+       m_nextFree = tile->next;
+       tile->next = 0;
+
+       // Insert tile into the position lut.
+       int h = computeTileHash(x,y);
+       tile->next = m_posLookup[h];
+       m_posLookup[h] = tile;
+       
+       // Patch header pointers.
+       const int headerSize = sizeof(dtTileHeader);
+       const int vertsSize = sizeof(float)*3*header->nverts;
+       const int polysSize = sizeof(dtTilePoly)*header->npolys;
+       const int linksSize = sizeof(dtTileLink)*(header->maxlinks);
+       const int detailMeshesSize = sizeof(dtTilePolyDetail)*header->ndmeshes;
+       const int detailVertsSize = sizeof(float)*3*header->ndverts;
+       const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris;
+       
+       unsigned char* d = data + headerSize;
+       header->verts = (float*)d; d += vertsSize;
+       header->polys = (dtTilePoly*)d; d += polysSize;
+       header->links = (dtTileLink*)d; d += linksSize;
+       header->dmeshes = (dtTilePolyDetail*)d; d += detailMeshesSize;
+       header->dverts = (float*)d; d += detailVertsSize;
+       header->dtris = (unsigned char*)d; d += detailTrisSize;
+
+       // Init tile.
+       tile->header = header;
+       tile->x = x;
+       tile->y = y;
+       tile->data = data;
+       tile->dataSize = dataSize;
+       tile->ownsData = ownsData;
+
+       buildIntLinks(tile);
+
+       // Create connections connections.
+       for (int i = 0; i < 4; ++i)
+       {
+               dtTile* nei = getNeighbourTileAt(x,y,i);
+               if (nei)
+               {
+                       buildExtLinks(tile, nei, i);
+                       buildExtLinks(nei, tile, opposite(i));
+               }
+       }
+       
+       return true;
+}
+
+dtTile* dtTiledNavMesh::getTileAt(int x, int y)
+{
+       // Find tile based on hash.
+       int h = computeTileHash(x,y);
+       dtTile* tile = m_posLookup[h];
+       while (tile)
+       {
+               if (tile->x == x && tile->y == y)
+                       return tile;
+               tile = tile->next;
+       }
+       return 0;
+}
+
+dtTile* dtTiledNavMesh::getTile(int i)
+{
+       return &m_tiles[i];
+}
+
+const dtTile* dtTiledNavMesh::getTile(int i) const
+{
+       return &m_tiles[i];
+}
+
+dtTile* dtTiledNavMesh::getNeighbourTileAt(int x, int y, int side)
+{
+       switch (side)
+       {
+       case 0: x++; break;
+       case 1: y++; break;
+       case 2: x--; break;
+       case 3: y--; break;
+       };
+       return getTileAt(x,y);
+}
+
+bool dtTiledNavMesh::removeTileAt(int x, int y, unsigned char** data, int* dataSize)
+{
+       // Remove tile from hash lookup.
+       int h = computeTileHash(x,y);
+       dtTile* prev = 0;
+       dtTile* tile = m_posLookup[h];
+       while (tile)
+       {
+               if (tile->x == x && tile->y == y)
+               {
+                       if (prev)
+                               prev->next = tile->next;
+                       else
+                               m_posLookup[h] = tile->next;
+                       break;
+               }
+               prev = tile;
+               tile = tile->next;
+       }
+       if (!tile)
+               return false;
+       
+       // Remove connections to neighbour tiles.
+       for (int i = 0; i < 4; ++i)
+       {
+               dtTile* nei = getNeighbourTileAt(x,y,i);
+               if (!nei) continue;
+               removeExtLinks(nei, opposite(i));
+       }
+       
+       
+       // Reset tile.
+       if (tile->ownsData)
+       {
+               // Owns data
+               delete [] tile->data;
+               tile->data = 0;
+               tile->dataSize = 0;
+               if (data) *data = 0;
+               if (dataSize) *dataSize = 0;
+       }
+       else
+       {
+               if (data) *data = tile->data;
+               if (dataSize) *dataSize = tile->dataSize;
+       }
+       tile->header = 0;
+       tile->x = tile->y = 0;
+       tile->salt++;
+
+       // Add to free list.
+       tile->next = m_nextFree;
+       m_nextFree = tile;
+
+       return true;
+}
+
+
+
+bool dtTiledNavMesh::closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       const dtTileHeader* header = m_tiles[it].header;
+
+       if (ip >= (unsigned int)header->npolys) return false;
+       const dtTilePoly* poly = &header->polys[ip];
+       
+       float closestDistSqr = FLT_MAX;
+       const dtTilePolyDetail* pd = &header->dmeshes[ip];
+       
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = &header->dtris[(pd->tbase+j)*4];
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < poly->nv)
+                               v[k] = &header->verts[poly->v[t[k]]*3];
+                       else
+                               v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3];
+               }
+               float pt[3];
+               closestPtPointTriangle(pt, pos, v[0], v[1], v[2]);
+               float d = vdistSqr(pos, pt);
+               if (d < closestDistSqr)
+               {
+                       vcopy(closest, pt);
+                       closestDistSqr = d;
+               }
+       }
+       
+       return true;
+}
+
+bool dtTiledNavMesh::getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       const dtTileHeader* header = m_tiles[it].header;
+       
+       if (ip >= (unsigned int)header->npolys) return false;
+       const dtTilePoly* poly = &header->polys[ip];
+       
+       const dtTilePolyDetail* pd = &header->dmeshes[ip];
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = &header->dtris[(pd->tbase+j)*4];
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < poly->nv)
+                               v[k] = &header->verts[poly->v[t[k]]*3];
+                       else
+                               v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3];
+               }
+               float h;
+               if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h))
+               {
+                       if (height)
+                               *height = h;
+                       return true;
+               }
+       }
+       
+       return false;
+}
+
+
+dtTilePolyRef dtTiledNavMesh::findNearestPoly(const float* center, const float* extents)
+{
+       // Get nearby polygons from proximity grid.
+       dtTilePolyRef polys[128];
+       int npolys = queryPolygons(center, extents, polys, 128);
+       
+       // Find nearest polygon amongst the nearby polygons.
+       dtTilePolyRef nearest = 0;
+       float nearestDistanceSqr = FLT_MAX;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtTilePolyRef ref = polys[i];
+               float closest[3];
+               if (!closestPointToPoly(ref, center, closest))
+                       continue;
+               float d = vdistSqr(center, closest);
+               if (d < nearestDistanceSqr)
+               {
+                       nearestDistanceSqr = d;
+                       nearest = ref;
+               }
+       }
+       
+       return nearest;
+}
+
+dtTilePolyRef dtTiledNavMesh::getTileId(dtTile* tile)
+{
+       if (!tile) return 0;
+       const unsigned int it = tile - m_tiles;
+       return dtEncodeTileId(tile->salt, it, 0);
+}
+
+int dtTiledNavMesh::queryTilePolygons(dtTile* tile,
+                                                                         const float* qmin, const float* qmax,
+                                                                         dtTilePolyRef* polys, const int maxPolys)
+{
+       float bmin[3], bmax[3];
+       const dtTileHeader* header = tile->header;
+       int n = 0;
+       dtTilePolyRef base = getTileId(tile);
+       for (int i = 0; i < header->npolys; ++i)
+       {
+               // Calc polygon bounds.
+               dtTilePoly* p = &header->polys[i];
+               const float* v = &header->verts[p->v[0]*3];
+               vcopy(bmin, v);
+               vcopy(bmax, v);
+               for (int j = 1; j < p->nv; ++j)
+               {
+                       v = &header->verts[p->v[j]*3];
+                       vmin(bmin, v);
+                       vmax(bmax, v);
+               }
+               if (overlapBoxes(qmin,qmax, bmin,bmax))
+               {
+                       if (n < maxPolys)
+                               polys[n++] = base | (dtTilePolyRef)i;
+               }
+       }
+       return n;
+}
+
+int dtTiledNavMesh::queryPolygons(const float* center, const float* extents,
+                                                                 dtTilePolyRef* polys, const int maxPolys)
+{
+       float bmin[3], bmax[3];
+       bmin[0] = center[0] - extents[0];
+       bmin[1] = center[1] - extents[1];
+       bmin[2] = center[2] - extents[2];
+       
+       bmax[0] = center[0] + extents[0];
+       bmax[1] = center[1] + extents[1];
+       bmax[2] = center[2] + extents[2];
+       
+       // Find tiles the query touches.
+       const int minx = (int)floorf((bmin[0]-m_orig[0]) / m_tileSize);
+       const int maxx = (int)ceilf((bmax[0]-m_orig[0]) / m_tileSize);
+
+       const int miny = (int)floorf((bmin[2]-m_orig[2]) / m_tileSize);
+       const int maxy = (int)ceilf((bmax[2]-m_orig[2]) / m_tileSize);
+
+       int n = 0;
+       for (int y = miny; y < maxy; ++y)
+       {
+               for (int x = minx; x < maxx; ++x)
+               {
+                       dtTile* tile = getTileAt(x,y);
+                       if (!tile) continue;
+                       n += queryTilePolygons(tile, bmin, bmax, polys+n, maxPolys-n);
+                       if (n >= maxPolys) return n;
+               }
+       }
+
+       return n;
+}
+
+int dtTiledNavMesh::findPath(dtTilePolyRef startRef, dtTilePolyRef endRef,
+                                                        const float* startPos, const float* endPos,
+                                                        dtTilePolyRef* path, const int maxPathSize)
+{
+       if (!startRef || !endRef)
+               return 0;
+       
+       if (!maxPathSize)
+               return 0;
+       
+       if (!getPolyByRef(startRef) || !getPolyByRef(endRef))
+               return 0;
+       
+       if (startRef == endRef)
+       {
+               path[0] = startRef;
+               return 1;
+       }
+       
+       if (!m_nodePool || !m_openList)
+               return 0;
+               
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       static const float H_SCALE = 1.1f;      // Heuristic scale.
+       
+       dtNode* startNode = m_nodePool->getNode(startRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = vdist(startPos, endPos) * H_SCALE;
+       startNode->id = startRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       dtNode* lastBestNode = startNode;
+       float lastBestNodeCost = startNode->total;
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               
+               if (bestNode->id == endRef)
+               {
+                       lastBestNode = bestNode;
+                       break;
+               }
+
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       dtTilePolyRef neighbour = header->links[poly->links+i].ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Calculate cost.
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, startPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.cost = parent->cost + vdist(p0,p1);
+                               // Special case for last node.
+                               if (newNode.id == endRef)
+                                       newNode.cost += vdist(p1, endPos);
+
+                               // Heuristic
+                               const float h = vdist(p1,endPos)*H_SCALE;
+                               newNode.total = newNode.cost + h;
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->cost = newNode.cost;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (h < lastBestNodeCost)
+                                       {
+                                               lastBestNodeCost = h;
+                                               lastBestNode = actualNode;
+                                       }
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+       
+       // Reverse the path.
+       dtNode* prev = 0;
+       dtNode* node = lastBestNode;
+       do
+       {
+               dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+               node->pidx = m_nodePool->getNodeIdx(prev);
+               prev = node;
+               node = next;
+       }
+       while (node);
+       
+       // Store path
+       node = prev;
+       int n = 0;
+       do
+       {
+               path[n++] = node->id;
+               node = m_nodePool->getNodeAtIdx(node->pidx);
+       }
+       while (node && n < maxPathSize);
+       
+       return n;
+}
+
+int dtTiledNavMesh::findStraightPath(const float* startPos, const float* endPos,
+                                                                        const dtTilePolyRef* path, const int pathSize,
+                                                                        float* straightPath, const int maxStraightPathSize)
+{
+       if (!maxStraightPathSize)
+               return 0;
+       
+       if (!path[0])
+               return 0;
+       
+       int straightPathSize = 0;
+       
+       float closestStartPos[3];
+       if (!closestPointToPoly(path[0], startPos, closestStartPos))
+               return 0;
+       
+       // Add start point.
+       vcopy(&straightPath[straightPathSize*3], closestStartPos);
+       straightPathSize++;
+       if (straightPathSize >= maxStraightPathSize)
+               return straightPathSize;
+       
+       float closestEndPos[3];
+       if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos))
+               return 0;
+       
+       float portalApex[3], portalLeft[3], portalRight[3];
+       
+       if (pathSize > 1)
+       {
+               vcopy(portalApex, closestStartPos);
+               vcopy(portalLeft, portalApex);
+               vcopy(portalRight, portalApex);
+               int apexIndex = 0;
+               int leftIndex = 0;
+               int rightIndex = 0;
+               
+               for (int i = 0; i < pathSize; ++i)
+               {
+                       float left[3], right[3];
+                       if (i < pathSize-1)
+                       {
+                               // Next portal.
+                               if (!getPortalPoints(path[i], path[i+1], left, right))
+                               {
+                                       if (!closestPointToPoly(path[i], endPos, closestEndPos))
+                                               return 0;
+                                       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+                                       straightPathSize++;
+                                       return straightPathSize;
+                               }
+                       }
+                       else
+                       {
+                               // End of the path.
+                               vcopy(left, closestEndPos);
+                               vcopy(right, closestEndPos);
+                       }
+                       
+                       // Right vertex.
+                       if (vequal(portalApex, portalRight))
+                       {
+                               vcopy(portalRight, right);
+                               rightIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalRight, right) <= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalLeft, right) > 0.0f)
+                                       {
+                                               vcopy(portalRight, right);
+                                               rightIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalLeft);
+                                               apexIndex = leftIndex;
+                                               
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+                                               
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+                                               
+                                               // Restart
+                                               i = apexIndex;
+                                               
+                                               continue;
+                                       }
+                               }
+                       }
+                       
+                       // Left vertex.
+                       if (vequal(portalApex, portalLeft))
+                       {
+                               vcopy(portalLeft, left);
+                               leftIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalLeft, left) >= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalRight, left) < 0.0f)
+                                       {
+                                               vcopy(portalLeft, left);
+                                               leftIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalRight);
+                                               apexIndex = rightIndex;
+                                               
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+                                               
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+                                               
+                                               // Restart
+                                               i = apexIndex;
+                                               
+                                               continue;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       // Add end point.
+       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+       straightPathSize++;
+       
+       return straightPathSize;
+}
+
+// Returns portal points between two polygons.
+bool dtTiledNavMesh::getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(from, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return false;
+       const dtTileHeader* fromHeader = m_tiles[it].header;
+       const dtTilePoly* fromPoly = &fromHeader->polys[ip];
+
+       for (int i = 0; i < fromPoly->nlinks; ++i)
+       {
+               const dtTileLink* link = &fromHeader->links[fromPoly->links+i];
+               if (link->ref == to)
+               {
+                       // Find portal vertices.
+                       const int v0 = fromPoly->v[link->e];
+                       const int v1 = fromPoly->v[(link->e+1) % fromPoly->nv];
+                       vcopy(left, &fromHeader->verts[v0*3]);
+                       vcopy(right, &fromHeader->verts[v1*3]);
+                       // If the link is at tile boundary, clamp the vertices to
+                       // the link width.
+                       if (link->side == 0 || link->side == 2)
+                       {
+                               // Unpack portal limits.
+                               const float smin = min(left[2],right[2]);
+                               const float smax = max(left[2],right[2]);
+                               const float s = (smax-smin) / 255.0f;
+                               const float lmin = smin + link->bmin*s;
+                               const float lmax = smin + link->bmax*s;
+                               left[2] = max(left[2],lmin);
+                               left[2] = min(left[2],lmax);
+                               right[2] = max(right[2],lmin);
+                               right[2] = min(right[2],lmax);
+                       }
+                       else if (link->side == 1 || link->side == 3)
+                       {
+                               // Unpack portal limits.
+                               const float smin = min(left[0],right[0]);
+                               const float smax = max(left[0],right[0]);
+                               const float s = (smax-smin) / 255.0f;
+                               const float lmin = smin + link->bmin*s;
+                               const float lmax = smin + link->bmax*s;
+                               left[0] = max(left[0],lmin);
+                               left[0] = min(left[0],lmax);
+                               right[0] = max(right[0],lmin);
+                               right[0] = min(right[0],lmax);
+                       }
+                       return true;
+               }
+       }
+       return false;
+}
+
+// Returns edge mid point between two polygons.
+bool dtTiledNavMesh::getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const
+{
+       float left[3], right[3];
+       if (!getPortalPoints(from, to, left,right)) return false;
+       mid[0] = (left[0]+right[0])*0.5f;
+       mid[1] = (left[1]+right[1])*0.5f;
+       mid[2] = (left[2]+right[2])*0.5f;
+       return true;
+}
+
+int dtTiledNavMesh::raycast(dtTilePolyRef centerRef, const float* startPos, const float* endPos,
+                                                       float& t, dtTilePolyRef* path, const int pathSize)
+{
+       t = 0;
+       
+       if (!centerRef || !getPolyByRef(centerRef))
+               return 0;
+       
+       dtTilePolyRef curRef = centerRef;
+       float verts[DT_TILE_VERTS_PER_POLYGON*3];       
+       int n = 0;
+       
+       while (curRef)
+       {
+               // Cast ray against current polygon.
+               
+               // The API input has been cheked already, skip checking internal data.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(curRef, salt, it, ip);
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+
+               // Collect vertices.
+               int nv = 0;
+               for (int i = 0; i < (int)poly->nv; ++i)
+               {
+                       vcopy(&verts[nv*3], &header->verts[poly->v[i]*3]);
+                       nv++;
+               }               
+               if (nv < 3)
+               {
+                       // Hit bad polygon, report hit.
+                       return n;
+               }
+               
+               float tmin, tmax;
+               int segMin, segMax;
+               if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
+               {
+                       // Could not hit the polygon, keep the old t and report hit.
+                       return n;
+               }
+               // Keep track of furthest t so far.
+               if (tmax > t)
+                       t = tmax;
+
+               if (n < pathSize)
+                       path[n++] = curRef;
+               
+               // Follow neighbours.
+               dtTilePolyRef nextRef = 0;
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       if ((int)link->e == segMax)
+                       {
+                               // If the link is internal, just return the ref.
+                               if (link->side == 0xff)
+                               {
+                                       nextRef = link->ref;
+                                       break;
+                               }
+                               
+                               // If the link is at tile boundary,
+                               const int v0 = poly->v[link->e];
+                               const int v1 = poly->v[(link->e+1) % poly->nv];
+                               const float* left = &header->verts[v0*3];
+                               const float* right = &header->verts[v1*3];
+                               
+                               // Check that the intersection lies inside the link portal.
+                               if (link->side == 0 || link->side == 2)
+                               {
+                                       // Calculate link size.
+                                       const float smin = min(left[2],right[2]);
+                                       const float smax = max(left[2],right[2]);
+                                       const float s = (smax-smin) / 255.0f;
+                                       const float lmin = smin + link->bmin*s;
+                                       const float lmax = smin + link->bmax*s;
+                                       // Find Z intersection.
+                                       float z = startPos[2] + (endPos[2]-startPos[2])*tmax;
+                                       if (z >= lmin && z <= lmax)
+                                       {
+                                               nextRef = link->ref;
+                                               break;
+                                       }
+                               }
+                               else if (link->side == 1 || link->side == 3)
+                               {
+                                       // Calculate link size.
+                                       const float smin = min(left[0],right[0]);
+                                       const float smax = max(left[0],right[0]);
+                                       const float s = (smax-smin) / 255.0f;
+                                       const float lmin = smin + link->bmin*s;
+                                       const float lmax = smin + link->bmax*s;
+                                       // Find X intersection.
+                                       float x = startPos[0] + (endPos[0]-startPos[0])*tmax;
+                                       if (x >= lmin && x <= lmax)
+                                       {
+                                               nextRef = link->ref;
+                                               break;
+                                       }
+                               }
+                       }
+               }
+               
+               if (!nextRef)
+               {
+                       // No neighbour, we hit a wall.
+                       return n;
+               }
+               
+               // No hit, advance to neighbour polygon.
+               curRef = nextRef;
+       }
+       
+       return n;
+}
+
+int dtTiledNavMesh::findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius,
+                                                                       dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost,
+                                                                       const int maxResult)
+{
+       if (!centerRef) return 0;
+       if (!getPolyByRef(centerRef)) return 0;
+       if (!m_nodePool || !m_openList) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       int n = 0;
+       if (n < maxResult)
+       {
+               if (resultRef)
+                       resultRef[n] = startNode->id;
+               if (resultParent)
+                       resultParent[n] = 0;
+               if (resultCost)
+                       resultCost[n] = 0;
+               ++n;
+       }
+       
+       const float radiusSqr = sqr(radius);
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       dtTilePolyRef neighbour = link->ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                               
+                               // Calc distance to the edge.
+                               const float* va = &header->verts[poly->v[link->e]*3];
+                               const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3];
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Cost
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               if (n < maxResult)
+                                               {
+                                                       if (resultRef)
+                                                               resultRef[n] = actualNode->id;
+                                                       if (resultParent)
+                                                               resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id;
+                                                       if (resultCost)
+                                                               resultCost[n] = actualNode->total;
+                                                       ++n;
+                                               }
+                                               actualNode->flags = DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       return n;
+}
+
+float dtTiledNavMesh::findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius,
+                                                float* hitPos, float* hitNormal)
+{
+       if (!centerRef) return 0;
+       if (!getPolyByRef(centerRef)) return 0;
+       if (!m_nodePool || !m_openList) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       float radiusSqr = sqr(maxRadius);
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               // Hit test walls.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip non-solid edges.
+                       if (poly->n[j] & 0x8000)
+                       {
+                               // Tile border.
+                               bool solid = true;
+                               for (int i = 0; i < poly->nlinks; ++i)
+                               {
+                                       const dtTileLink* link = &header->links[poly->links+i];
+                                       if (link->e == j && link->ref != 0)
+                                       {
+                                               solid = false;
+                                               break;
+                                       }
+                               }
+                               if (!solid) continue;
+                       }
+                       else if (poly->n[j])
+                       {
+                               // Internal edge
+                               continue;
+                       }
+                       
+                       // Calc distance to the edge.
+                       const float* vj = &header->verts[poly->v[j]*3];
+                       const float* vi = &header->verts[poly->v[i]*3];
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                       
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                       
+                       // Hit wall, update radius.
+                       radiusSqr = distSqr;
+                       // Calculate hit pos.
+                       hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
+                       hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
+                       hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
+               }
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       dtTilePolyRef neighbour = link->ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                               
+                               // Calc distance to the edge.
+                               const float* va = &header->verts[poly->v[link->e]*3];
+                               const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3];
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags = DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       // Calc hit normal.
+       vsub(hitNormal, centerPos, hitPos);
+       vnormalize(hitNormal);
+       
+       return sqrtf(radiusSqr);
+}
+
+const dtTilePoly* dtTiledNavMesh::getPolyByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return &m_tiles[it].header->polys[ip];
+}
+
+const float* dtTiledNavMesh::getPolyVertsByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return m_tiles[it].header->verts;
+}
+
+const dtTileLink* dtTiledNavMesh::getPolyLinksByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return m_tiles[it].header->links;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp
new file mode 100644 (file)
index 0000000..95dd34b
--- /dev/null
@@ -0,0 +1,213 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "DetourTileNavMesh.h"
+#include "DetourCommon.h"
+
+bool dtCreateNavMeshTileData(const unsigned short* verts, const int nverts,
+                                                        const unsigned short* polys, const int npolys, const int nvp,
+                                                        const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                        const unsigned char* dtris, const int ndtris, 
+                                                        const float* bmin, const float* bmax, float cs, float ch, int tileSize, int walkableClimb,
+                                                        unsigned char** outData, int* outDataSize)
+{
+       if (nvp != DT_TILE_VERTS_PER_POLYGON)
+               return false;
+       if (nverts >= 0xffff)
+               return false;
+       
+       if (!nverts)
+               return false;
+       if (!npolys)
+               return false;
+       if (!dmeshes || !dverts || ! dtris)
+               return false;
+       
+       // Find portal edges which are at tile borders.
+       int nedges = 0;
+       int nportals = 0;
+       for (int i = 0; i < npolys; ++i)
+       {
+               const unsigned short* p = &polys[i*2*nvp];
+               for (int j = 0; j < nvp; ++j)
+               {
+                       if (p[j] == 0xffff) break;
+                       int nj = j+1;
+                       if (nj >= nvp || p[nj] == 0xffff) nj = 0;
+                       const unsigned short* va = &verts[p[j]*3];
+                       const unsigned short* vb = &verts[p[nj]*3];
+                       
+                       nedges++;
+                       
+                       if (va[0] == tileSize && vb[0] == tileSize)
+                               nportals++; // x+
+                       else if (va[2] == tileSize && vb[2]  == tileSize)
+                               nportals++; // z+
+                       else if (va[0] == 0 && vb[0] == 0)
+                               nportals++; // x-
+                       else if (va[2] == 0 && vb[2] == 0)
+                               nportals++; // z-
+               }
+       }
+
+       const int maxLinks = nedges + nportals*2;
+       
+       
+       // Find unique detail vertices.
+       int uniqueDetailVerts = 0;
+       if (dmeshes)
+       {
+               for (int i = 0; i < npolys; ++i)
+               {
+                       const unsigned short* p = &polys[i*nvp*2];
+                       int ndv = dmeshes[i*4+1];
+                       int nv = 0;
+                       for (int j = 0; j < nvp; ++j)
+                       {
+                               if (p[j] == 0xffff) break;
+                               nv++;
+                       }
+                       ndv -= nv;
+                       uniqueDetailVerts += ndv;
+               }
+       }
+       
+       // Calculate data size
+       const int headerSize = sizeof(dtTileHeader);
+       const int vertsSize = sizeof(float)*3*nverts;
+       const int polysSize = sizeof(dtTilePoly)*npolys;
+       const int linksSize = sizeof(dtTileLink)*maxLinks;
+       const int detailMeshesSize = sizeof(dtTilePolyDetail)*npolys;
+       const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts;
+       const int detailTrisSize = sizeof(unsigned char)*4*ndtris;
+       
+       const int dataSize = headerSize + vertsSize + polysSize + linksSize +
+                                                detailMeshesSize + detailVertsSize + detailTrisSize;
+       unsigned char* data = new unsigned char[dataSize];
+       if (!data)
+               return false;
+       memset(data, 0, dataSize);
+       
+       unsigned char* d = data;
+       dtTileHeader* header = (dtTileHeader*)d; d += headerSize;
+       float* navVerts = (float*)d; d += vertsSize;
+       dtTilePoly* navPolys = (dtTilePoly*)d; d += polysSize;
+       d += linksSize;
+       dtTilePolyDetail* navDMeshes = (dtTilePolyDetail*)d; d += detailMeshesSize;
+       float* navDVerts = (float*)d; d += detailVertsSize;
+       unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
+       
+       
+       // Store header
+       header->magic = DT_TILE_NAVMESH_MAGIC;
+       header->version = DT_TILE_NAVMESH_VERSION;
+       header->npolys = npolys;
+       header->nverts = nverts;
+       header->maxlinks = maxLinks;
+       header->bmin[0] = bmin[0];
+       header->bmin[1] = bmin[1];
+       header->bmin[2] = bmin[2];
+       header->bmax[0] = bmax[0];
+       header->bmax[1] = bmax[1];
+       header->bmax[2] = bmax[2];
+       header->ndmeshes = npolys;
+       header->ndverts = uniqueDetailVerts;
+       header->ndtris = ndtris;
+       
+       // Store vertices
+       for (int i = 0; i < nverts; ++i)
+       {
+               const unsigned short* iv = &verts[i*3];
+               float* v = &navVerts[i*3];
+               v[0] = bmin[0] + iv[0] * cs;
+               v[1] = bmin[1] + iv[1] * ch;
+               v[2] = bmin[2] + iv[2] * cs;
+       }
+       
+       // Store polygons
+       const unsigned short* src = polys;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtTilePoly* p = &navPolys[i];
+               p->nv = 0;
+               for (int j = 0; j < nvp; ++j)
+               {
+                       if (src[j] == 0xffff) break;
+                       p->v[j] = src[j];
+                       p->n[j] = (src[nvp+j]+1) & 0xffff;
+                       p->nv++;
+               }
+               src += nvp*2;
+       }
+
+       // Store portal edges.
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtTilePoly* poly = &navPolys[i];
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       int nj = j+1;
+                       if (nj >= poly->nv) nj = 0;
+
+                       const unsigned short* va = &verts[poly->v[j]*3];
+                       const unsigned short* vb = &verts[poly->v[nj]*3];
+                                               
+                       if (va[0] == tileSize && vb[0] == tileSize) // x+
+                               poly->n[j] = 0x8000 | 0;
+                       else if (va[2] == tileSize && vb[2]  == tileSize) // z+
+                               poly->n[j] = 0x8000 | 1;
+                       else if (va[0] == 0 && vb[0] == 0) // x-
+                               poly->n[j] = 0x8000 | 2;
+                       else if (va[2] == 0 && vb[2] == 0) // z-
+                               poly->n[j] = 0x8000 | 3;
+               }
+       }
+
+       // Store detail meshes and vertices.
+       // The nav polygon vertices are stored as the first vertices on each mesh.
+       // We compress the mesh data by skipping them and using the navmesh coordinates.
+       unsigned short vbase = 0;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtTilePolyDetail& dtl = navDMeshes[i];
+               const int vb = dmeshes[i*4+0];
+               const int ndv = dmeshes[i*4+1];
+               const int nv = navPolys[i].nv;
+               dtl.vbase = vbase;
+               dtl.nverts = ndv-nv;
+               dtl.tbase = dmeshes[i*4+2];
+               dtl.ntris = dmeshes[i*4+3];
+               // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
+               if (ndv-nv)
+               {
+                       memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
+                       vbase += ndv-nv;
+               }
+       }
+       // Store triangles.
+       memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris);
+       
+       *outData = data;
+       *outDataSize = dataSize;
+       
+       return true;
+}
diff --git a/extern/recastnavigation/License.txt b/extern/recastnavigation/License.txt
new file mode 100644 (file)
index 0000000..95f4bfc
--- /dev/null
@@ -0,0 +1,18 @@
+Copyright (c) 2009 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.
+
diff --git a/extern/recastnavigation/Readme.txt b/extern/recastnavigation/Readme.txt
new file mode 100644 (file)
index 0000000..0c2f7b1
--- /dev/null
@@ -0,0 +1,120 @@
+
+Recast & Detour Version 1.4
+
+
+Recast
+
+Recast is state of the art navigation mesh construction toolset for games.
+
+    * It is automatic, which means that you can throw any level geometry
+      at it and you will get robust mesh out
+    * It is fast which means swift turnaround times for level designers
+    * It is open source so it comes with full source and you can
+      customize it to your hearts content. 
+
+The Recast process starts with constructing a voxel mold from a level geometry 
+and then casting a navigation mesh over it. The process consists of three steps, 
+building the voxel mold, partitioning the mold into simple regions, peeling off 
+the regions as simple polygons.
+
+   1. The voxel mold is build from the input triangle mesh by rasterizing 
+      the triangles into a multi-layer heightfield. Some simple filters are 
+      then applied to the mold to prune out locations where the character 
+      would not be able to move.
+   2. The walkable areas described by the mold are divided into simple 
+      overlayed 2D regions. The resulting regions have only one non-overlapping 
+      contour, which simplifies the final step of the process tremendously.
+   3. The navigation polygons are peeled off from the regions by first tracing 
+      the boundaries and then simplifying them. The resulting polygons are 
+      finally converted to convex polygons which makes them perfect for 
+      pathfinding and spatial reasoning about the level. 
+
+The toolset code is located in the Recast folder and demo application using the Recast
+toolset is located in the RecastDemo folder.
+
+The project files with this distribution can be compiled with Microsoft Visual C++ 2008
+(you can download it for free) and XCode 3.1.
+
+
+Detour
+
+Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. You can use any navigation mesh with Detour, but of course the data generated with Recast fits perfectly.
+
+Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes. 
+
+
+Latest code available at http://code.google.com/p/recastnavigation/
+
+
+--
+
+Release Notes
+
+----------------
+* Recast 1.4
+  Released August 24th, 2009
+
+- Added detail height mesh generation (RecastDetailMesh.cpp) for single,
+  tiled statmeshes as well as tilemesh.
+- Added feature to contour tracing which detects extra vertices along
+  tile edges which should be removed later.
+- Changed the tiled stat mesh preprocess, so that it first generated
+  polymeshes per tile and finally combines them.
+- Fixed bug in the GUI code where invisible buttons could be pressed.
+
+----------------
+* Recast 1.31
+  Released July 24th, 2009
+
+- Better cost and heuristic functions.
+- Fixed tile navmesh raycast on tile borders.
+
+----------------
+* Recast 1.3
+  Released July 14th, 2009
+
+- Added dtTileNavMesh which allows to dynamically add and remove navmesh pieces at runtime.
+- Renamed stat navmesh types to dtStat* (i.e. dtPoly is now dtStatPoly).
+- Moved common code used by tile and stat navmesh to DetourNode.h/cpp and DetourCommon.h/cpp.
+- Refactores the demo code.
+
+----------------
+* Recast 1.2
+  Released June 17th, 2009
+
+- Added tiled mesh generation. The tiled generation allows to generate navigation for
+  much larger worlds, it removes some of the artifacts that comes from distance fields
+  in open areas, and allows later streaming and dynamic runtime generation
+- Improved and added some debug draw modes
+- API change: The helper function rcBuildNavMesh does not exists anymore,
+  had to change few internal things to cope with the tiled processing,
+  similar API functionality will be added later once the tiled process matures
+- The demo is getting way too complicated, need to split demos
+- Fixed several filtering functions so that the mesh is tighter to the geometry,
+  sometimes there could be up error up to tow voxel units close to walls,
+  now it should be just one.
+
+----------------
+* Recast 1.1
+  Released April 11th, 2009
+
+This is the first release of Detour.
+
+----------------
+* Recast 1.0
+  Released March 29th, 2009
+
+This is the first release of Recast.
+
+The process is not always as robust as I would wish. The watershed phase sometimes swallows tiny islands
+which are close to edges. These droppings are handled in rcBuildContours, but the code is not
+particularly robust either.
+
+Another non-robust case is when portal contours (contours shared between two regions) are always
+assumed to be straight. That can lead to overlapping contours specially when the level has
+large open areas.
+
+
+
+Mikko Mononen
+memon@inside.org
diff --git a/extern/recastnavigation/Recast/Include/Recast.h b/extern/recastnavigation/Recast/Include/Recast.h
new file mode 100644 (file)
index 0000000..f25ab47
--- /dev/null
@@ -0,0 +1,501 @@
+//
+// Copyright (c) 2009 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
+
+// The units of the parameters are specified in parenthesis as follows:
+// (vx) voxels, (wu) world units
+struct rcConfig
+{
+       int width, height;                              // Dimensions of the rasterized heighfield (vx)
+       int tileSize;                                   // Width and Height of a tile (vx)
+       int borderSize;                                 // Non-navigable Border around the heightfield (vx)
+       float cs, ch;                                   // Grid cell size and height (wu)
+       float bmin[3], bmax[3];                 // Grid bounds (wu)
+       float walkableSlopeAngle;               // Maximum walkble slope angle in degrees.
+       int walkableHeight;                             // Minimum height where the agent can still walk (vx)
+       int walkableClimb;                              // Maximum height between grid cells the agent can climb (vx)
+       int walkableRadius;                             // Radius of the agent in cells (vx)
+       int maxEdgeLen;                                 // Maximum contour edge length (vx)
+       float maxSimplificationError;   // Maximum distance error from contour to cells (vx)
+       int minRegionSize;                              // Minimum regions size. Smaller regions will be deleted (vx)
+       int mergeRegionSize;                    // Minimum regions size. Smaller regions will be merged (vx)
+       int maxVertsPerPoly;                    // Max number of vertices per polygon
+       float detailSampleDist;                 // Detail mesh sample spacing.
+       float detailSampleMaxError;             // Detail mesh simplification max sample error.
+};
+
+// Heightfield span.
+struct rcSpan
+{
+       unsigned int smin : 15;                 // Span min height.
+       unsigned int smax : 15;                 // Span max height.
+       unsigned int flags : 2;                 // Span flags.
+       rcSpan* next;                                   // Next span in column.
+};
+
+static const int RC_SPANS_PER_POOL = 2048;
+
+// Memory pool used for quick span allocation.
+struct rcSpanPool
+{
+       rcSpanPool* next;       // Pointer to next pool.
+       rcSpan items[1];        // Array of spans (size RC_SPANS_PER_POOL).
+};
+
+// Dynamic span-heightfield.
+struct rcHeightfield
+{
+       inline rcHeightfield() : width(0), height(0), spans(0), pools(0), freelist(0) {}
+       inline ~rcHeightfield()
+       {
+               // Delete span array.
+               delete [] spans;
+               // Delete span pools.
+               while (pools)
+               {
+                       rcSpanPool* next = pools->next;
+                       delete [] reinterpret_cast<unsigned char*>(pools);
+                       pools = next;
+               }
+       }
+       int width, height;                      // Dimension of the heightfield.
+       float bmin[3], bmax[3];         // Bounding box of the heightfield
+       float cs, ch;                           // Cell size and height.
+       rcSpan** spans;                         // Heightfield of spans (width*height).
+       rcSpanPool* pools;                      // Linked list of span pools.
+       rcSpan* freelist;                       // Pointer to next free span.
+};
+
+struct rcCompactCell
+{
+       unsigned int index : 24;        // Index to first span in column.
+       unsigned int count : 8;         // Number of spans in this column.
+};
+
+struct rcCompactSpan
+{
+       unsigned short y;                       // Bottom coordinate of the span.
+       unsigned short reg;                     // Region ID
+       unsigned short dist;            // Distance to border
+       unsigned short con;                     // Connections to neighbour cells.
+       unsigned char h;                        // Height of the span.
+       unsigned char flags;            // Flags.
+};
+
+// Compact static heightfield. 
+struct rcCompactHeightfield
+{
+       inline rcCompactHeightfield() : maxDistance(0), maxRegions(0), cells(0), spans(0) {}
+       inline ~rcCompactHeightfield() { delete [] cells; delete [] spans; }
+       int width, height;                                      // Width and height of the heighfield.
+       int spanCount;                                          // Number of spans in the heightfield.
+       int walkableHeight, walkableClimb;      // Agent properties.
+       unsigned short maxDistance;                     // Maximum distance value stored in heightfield.
+       unsigned short maxRegions;                      // Maximum Region Id stored in heightfield.
+       float bmin[3], bmax[3];                         // Bounding box of the heightfield.
+       float cs, ch;                                           // Cell size and height.
+       rcCompactCell* cells;                           // Pointer to width*height cells.
+       rcCompactSpan* spans;                           // Pointer to spans.
+};
+
+struct rcContour
+{
+       inline rcContour() : verts(0), nverts(0), rverts(0), nrverts(0) { }
+       inline ~rcContour() { delete [] verts; delete [] rverts; }
+       int* verts;                     // Vertex coordinates, each vertex contains 4 components.
+       int nverts;                     // Number of vertices.
+       int* rverts;            // Raw vertex coordinates, each vertex contains 4 components.
+       int nrverts;            // Number of raw vertices.
+       unsigned short reg;     // Region ID of the contour.
+};
+
+struct rcContourSet
+{
+       inline rcContourSet() : conts(0), nconts(0) {}
+       inline ~rcContourSet() { delete [] conts; }
+       rcContour* conts;               // Pointer to all contours.
+       int nconts;                             // Number of contours.
+       float bmin[3], bmax[3]; // Bounding box of the heightfield.
+       float cs, ch;                   // Cell size and height.
+};
+
+// Polymesh store a connected mesh of polygons.
+// The polygons are store in an array where each polygons takes
+// 'nvp*2' elements. The first 'nvp' elements are indices to vertices
+// and the second 'nvp' elements are indices to neighbour polygons.
+// If a polygona has less than 'bvp' vertices, the remaining indices
+// are set os 0xffff. If an polygon edge does not have a neighbour
+// the neighbour index is set to 0xffff.
+// Vertices can be transformed into world space as follows:
+//   x = bmin[0] + verts[i*3+0]*cs;
+//   y = bmin[1] + verts[i*3+1]*ch;
+//   z = bmin[2] + verts[i*3+2]*cs;
+struct rcPolyMesh
+{
+       inline rcPolyMesh() : verts(0), polys(0), regs(0), nverts(0), npolys(0), nvp(3) {}
+       inline ~rcPolyMesh() { delete [] verts; delete [] polys; delete [] regs; }
+       unsigned short* verts;  // Vertices of the mesh, 3 elements per vertex.
+       unsigned short* polys;  // Polygons of the mesh, nvp*2 elements per polygon.
+       unsigned short* regs;   // Regions of the polygons.
+       int nverts;                             // Number of vertices.
+       int npolys;                             // Number of polygons.
+       int nvp;                                // Max number of vertices per polygon.
+       float bmin[3], bmax[3]; // Bounding box of the mesh.
+       float cs, ch;                   // Cell size and height.
+};
+
+// Detail mesh generated from a rcPolyMesh.
+// Each submesh represents a polygon in the polymesh and they are stored in
+// excatly same order. Each submesh is described as 4 values:
+// base vertex, vertex count, base triangle, triangle count. That is,
+//   const unsigned char* t = &dtl.tris[(tbase+i)*3]; and
+//   const float* v = &dtl.verts[(vbase+t[j])*3];
+// If the input polygon has 'n' vertices, those vertices are first in the
+// submesh vertex list. This allows to compres the mesh by not storing the
+// first vertices and using the polymesh vertices instead.
+
+struct rcPolyMeshDetail
+{
+       inline rcPolyMeshDetail() :
+               meshes(0), verts(0), tris(0),
+               nmeshes(0), nverts(0), ntris(0) {}
+       inline ~rcPolyMeshDetail()
+       {
+               delete [] meshes; delete [] verts; delete [] tris;
+       }
+       
+       unsigned short* meshes; // Pointer to all mesh data.
+       float* verts;                   // Pointer to all vertex data.
+       unsigned char* tris;    // Pointer to all triangle data.
+       int nmeshes;                    // Number of meshes.
+       int nverts;                             // Number of total vertices.
+       int ntris;                              // Number of triangles.
+};
+
+
+// Simple dynamic array ints.
+class rcIntArray
+{
+       int* m_data;
+       int m_size, m_cap;
+public:
+       inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {}
+       inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(n) { m_data = new int[n]; }
+       inline ~rcIntArray() { delete [] m_data; }
+       void resize(int n);
+       inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; }
+       inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; }
+       inline const int& operator[](int i) const { return m_data[i]; }
+       inline int& operator[](int i) { return m_data[i]; }
+       inline int size() const { return m_size; }
+};
+
+enum rcSpanFlags
+{
+       RC_WALKABLE = 0x01,
+       RC_REACHABLE = 0x02,
+};
+
+// If heightfield region ID has the following bit set, the region is on border area
+// and excluded from many calculations.
+static const unsigned short RC_BORDER_REG = 0x8000;
+
+// If contour region ID has the following bit set, the vertex will be later
+// removed in order to match the segments and vertices at tile boundaries.
+static const int RC_BORDER_VERTEX = 0x10000;
+
+// Compact span neighbour helpers.
+inline int rcGetCon(const rcCompactSpan& s, int dir)
+{
+       return (s.con >> (dir*4)) & 0xf;
+}
+
+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];
+}
+
+// Common helper functions
+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); }
+
+// Common vector helper functions.
+inline void vcross(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 vdot(const float* v1, const float* v2)
+{
+       return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
+}
+
+inline void vmad(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 vadd(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 vsub(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 vmin(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 vmax(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 vcopy(float* dest, const float* v)
+{
+       dest[0] = v[0];
+       dest[1] = v[1];
+       dest[2] = v[2];
+}
+
+inline float vdist(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 sqrtf(dx*dx + dy*dy + dz*dz);
+}
+
+inline float vdistSqr(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 vnormalize(float* v)
+{
+       float d = 1.0f / sqrtf(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
+       v[0] *= d;
+       v[1] *= d;
+       v[2] *= d;
+}
+
+inline bool vequal(const float* p0, const float* p1)
+{
+       static const float thr = rcSqr(1.0f/16384.0f);
+       const float d = vdistSqr(p0, p1);
+       return d < thr;
+}
+
+
+// Calculated bounding box of array of vertices.
+// Params:
+//     verts - (in) array of vertices
+//     nv - (in) vertex count
+//     bmin, bmax - (out) bounding box
+void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax);
+
+// Calculates grid size based on bounding box and grid cell size.
+// Params:
+//     bmin, bmax - (in) bounding box
+//     cs - (in) grid cell size
+//     w - (out) grid width
+//     h - (out) grid height
+void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h);
+
+// Creates and initializes new heightfield.
+// Params:
+//     hf - (in/out) heightfield to initialize.
+//     width - (in) width of the heightfield.
+//     height - (in) height of the heightfield.
+//     bmin, bmax - (in) bounding box of the heightfield
+//     cs - (in) grid cell size
+//     ch - (in) grid cell height
+bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
+                                                const float* bmin, const float* bmax,
+                                                float cs, float ch);
+
+// Sets the WALKABLE flag for every triangle whose slope is below
+// the maximun walkable slope angle.
+// Params:
+//     walkableSlopeAngle - (in) maximun slope angle in degrees.
+//     verts - (in) array of vertices
+//     nv - (in) vertex count
+//     tris - (in) array of triangle vertex indices
+//     nt - (in) triangle count
+//     flags - (out) array of triangle flags
+void rcMarkWalkableTriangles(const float walkableSlopeAngle,
+                                                        const float* verts, int nv,
+                                                        const int* tris, int nt,
+                                                        unsigned char* flags); 
+
+// Rasterizes a triangle into heightfield spans.
+// Params:
+//     v0,v1,v2 - (in) the vertices of the triangle.
+//     flags - (in) triangle flags (uses WALKABLE)
+//     solid - (in) heighfield where the triangle is rasterized
+void rcRasterizeTriangle(const float* v0, const float* v1, const float* v2,
+                                                unsigned char flags, rcHeightfield& solid);
+
+// Rasterizes the triangles into heightfield spans.
+// Params:
+//     verts - (in) array of vertices
+//     nv - (in) vertex count
+//     tris - (in) array of triangle vertex indices
+//     norms - (in) array of triangle normals
+//     flags - (in) array of triangle flags (uses WALKABLE)
+//     nt - (in) triangle count
+//     solid - (in) heighfield where the triangles are rasterized
+void rcRasterizeTriangles(const float* verts, int nv,
+                                                 const int* tris, const unsigned char* flags, int nt,
+                                                 rcHeightfield& solid);
+
+// Removes WALKABLE flag from all spans that are at ledges. This filtering
+// removes possible overestimation of the conservative voxelization so that
+// the resulting mesh will not have regions hanging in air over ledges.
+// Params:
+//     walkableHeight - (in) minimum height where the agent can still walk
+//     walkableClimb - (in) maximum height between grid cells the agent can climb
+//     solid - (in/out) heightfield describing the solid space
+void rcFilterLedgeSpans(const int walkableHeight,
+                                               const int walkableClimb,
+                                               rcHeightfield& solid);
+
+// Removes WALKABLE flag from all spans which have smaller than
+// 'walkableHeight' clearane above them.
+// Params:
+//     walkableHeight - (in) minimum height where the agent can still walk
+//     solid - (in/out) heightfield describing the solid space
+void rcFilterWalkableLowHeightSpans(int walkableHeight,
+                                                                       rcHeightfield& solid);
+
+// Marks spans which are reachable from any of the topmost spans.
+// Params:
+//     walkableHeight - (in) minimum height where the agent can still walk
+//     walkableClimb - (in) maximum height between grid cells the agent can climb
+//     solid - (in/out) heightfield describing the solid space
+// Returns false if operation ran out of memory.
+bool rcMarkReachableSpans(const int walkableHeight,
+                                                 const int walkableClimb,
+                                                 rcHeightfield& solid);
+
+// Builds compact representation of the heightfield.
+// Params:
+//     walkableHeight - (in) minimum height where the agent can still walk
+//     walkableClimb - (in) maximum height between grid cells the agent can climb
+//     hf - (in) heightfield to be compacted
+//     chf - (out) compact heightfield representing the open space.
+// Returns false if operation ran out of memory.
+bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
+                                                          unsigned char flags,
+                                                          rcHeightfield& hf,
+                                                          rcCompactHeightfield& chf);
+
+// Builds distance field and stores it into the combat heightfield.
+// Params:
+//     chf - (in/out) compact heightfield representing the open space.
+// Returns false if operation ran out of memory.
+bool rcBuildDistanceField(rcCompactHeightfield& chf);
+
+// Divides the walkable heighfied into simple regions.
+// Each region has only one contour and no overlaps.
+// The regions are stored in the compact heightfield 'reg' field.
+// The regions will be shrinked by the radius of the agent.
+// The process sometimes creates small regions. The parameter
+// 'minRegionSize' specifies the smallest allowed regions size.
+// If the area of a regions is smaller than allowed, the regions is
+// removed or merged to neighbour region. 
+// Params:
+//     chf - (in/out) compact heightfield representing the open space.
+//     walkableRadius - (in) the radius of the agent.
+//     minRegionSize - (in) the smallest allowed regions size.
+//     maxMergeRegionSize - (in) the largest allowed regions size which can be merged.
+// Returns false if operation ran out of memory.
+bool rcBuildRegions(rcCompactHeightfield& chf,
+                                       int walkableRadius, int borderSize,
+                                       int minRegionSize, int mergeRegionSize);
+
+// Builds simplified contours from the regions outlines.
+// Params:
+//     chf - (in) compact heightfield which has regions set.
+//     maxError - (in) maximum allowed distance between simplified countour and cells.
+//     maxEdgeLen - (in) maximum allowed contour edge length in cells.
+//     cset - (out) Resulting contour set.
+// Returns false if operation ran out of memory.
+bool rcBuildContours(rcCompactHeightfield& chf,
+                                        const float maxError, const int maxEdgeLen,
+                                        rcContourSet& cset);
+
+// Builds connected convex polygon mesh from contour polygons.
+// Params:
+//     cset - (in) contour set.
+//     nvp - (in) maximum number of vertices per polygon.
+//     mesh - (out) poly mesh.
+// Returns false if operation ran out of memory.
+bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh);
+
+bool rcMergePolyMeshes(rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
+
+// Builds detail triangle mesh for each polygon in the poly mesh.
+// Params:
+//     mesh - (in) poly mesh to detail.
+//     chf - (in) compacy height field, used to query height for new vertices.
+//  sampleDist - (in) spacing between height samples used to generate more detail into mesh.
+//  sampleMaxError - (in) maximum allowed distance between simplified detail mesh and height sample.
+//     pmdtl - (out) detail mesh.
+// Returns false if operation ran out of memory.
+bool rcBuildPolyMeshDetail(const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
+                                                  const float sampleDist, const float sampleMaxError,
+                                                  rcPolyMeshDetail& dmesh);
+
+bool rcMergePolyMeshDetails(rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
+
+bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nverts, const int vertsPerPoly);
+
+#endif // RECAST_H
diff --git a/extern/recastnavigation/Recast/Include/RecastDebugDraw.h b/extern/recastnavigation/Recast/Include/RecastDebugDraw.h
new file mode 100644 (file)
index 0000000..27ba0a1
--- /dev/null
@@ -0,0 +1,59 @@
+//
+// Copyright (c) 2009 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_DEBUGDRAW_H
+#define RECAST_DEBUGDRAW_H
+
+inline int bit(int a, int b)
+{
+       return (a & (1 << b)) >> b;
+}
+
+inline void intToCol(int i, float* col)
+{
+       int     r = bit(i, 0) + bit(i, 3) * 2 + 1;
+       int     g = bit(i, 1) + bit(i, 4) * 2 + 1;
+       int     b = bit(i, 2) + bit(i, 5) * 2 + 1;
+       col[0] = 1 - r*63.0f/255.0f;
+       col[1] = 1 - g*63.0f/255.0f;
+       col[2] = 1 - b*63.0f/255.0f;
+}
+
+void rcDebugDrawHeightfieldSolid(const struct rcHeightfield& hf);
+void rcDebugDrawHeightfieldWalkable(const struct rcHeightfield& hf);
+
+void rcDebugDrawMesh(const float* verts, int nverts, const int* tris, const float* normals, int ntris, const unsigned char* flags);
+void rcDebugDrawMeshSlope(const float* verts, int nverts, const int* tris, const float* normals, int ntris, const float walkableSlopeAngle);
+
+void rcDebugDrawCompactHeightfieldSolid(const struct rcCompactHeightfield& chf);
+void rcDebugDrawCompactHeightfieldRegions(const struct rcCompactHeightfield& chf);
+void rcDebugDrawCompactHeightfieldDistance(const struct rcCompactHeightfield& chf);
+
+void rcDebugDrawRegionConnections(const struct rcContourSet& cset, const float alpha = 1.0f);
+void rcDebugDrawRawContours(const struct rcContourSet& cset, const float alpha = 1.0f);
+void rcDebugDrawContours(const struct rcContourSet& cset, const float alpha = 1.0f);
+void rcDebugDrawPolyMesh(const struct rcPolyMesh& mesh);
+void rcDebugDrawPolyMeshDetail(const struct rcPolyMeshDetail& dmesh);
+
+void rcDebugDrawCylinderWire(float minx, float miny, float minz, float maxx, float maxy, float maxz, const float* col);
+void rcDebugDrawBoxWire(float minx, float miny, float minz, float maxx, float maxy, float maxz, const float* col);
+void rcDebugDrawBox(float minx, float miny, float minz, float maxx, float maxy, float maxz,
+                                       const float* col1, const float* col2);
+void rcDrawArc(const float* p0, const float* p1);
+
+#endif // RECAST_DEBUGDRAW_H
diff --git a/extern/recastnavigation/Recast/Include/RecastLog.h b/extern/recastnavigation/Recast/Include/RecastLog.h
new file mode 100644 (file)
index 0000000..026ef73
--- /dev/null
@@ -0,0 +1,80 @@
+//
+// Copyright (c) 2009 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_LOG_H
+#define RECAST_LOG_H
+
+enum rcLogCategory
+{
+       RC_LOG_PROGRESS = 1,
+       RC_LOG_WARNING,
+       RC_LOG_ERROR,
+};
+
+class rcLog
+{
+public:
+       rcLog();
+       ~rcLog();
+       
+       void log(rcLogCategory category, const char* format, ...);
+       inline void clear() { m_messageCount = 0; m_textPoolSize = 0; }
+       inline int getMessageCount() const { return m_messageCount; }
+       inline char getMessageType(int i) const { return *m_messages[i]; }
+       inline const char* getMessageText(int i) const { return m_messages[i]+1; }
+
+private:
+       static const int MAX_MESSAGES = 1000;
+       const char* m_messages[MAX_MESSAGES];
+       int m_messageCount;
+       static const int TEXT_POOL_SIZE = 8000;
+       char m_textPool[TEXT_POOL_SIZE];
+       int m_textPoolSize;
+};
+
+struct rcBuildTimes
+{
+       int rasterizeTriangles;
+       int buildCompact;
+       int buildContours;
+       int buildContoursTrace;
+       int buildContoursSimplify;
+       int filterBorder;
+       int filterWalkable;
+       int filterMarkReachable;
+       int buildPolymesh;
+       int buildDistanceField;
+       int buildDistanceFieldDist;
+       int buildDistanceFieldBlur;
+       int buildRegions;
+       int buildRegionsReg;
+       int buildRegionsExp;
+       int buildRegionsFlood;
+       int buildRegionsFilter;
+       int buildDetailMesh;
+       int mergePolyMesh;
+       int mergePolyMeshDetail;
+};
+
+void rcSetLog(rcLog* log);
+rcLog* rcGetLog();
+
+void rcSetBuildTimes(rcBuildTimes* btimes);
+rcBuildTimes* rcGetBuildTimes();
+
+#endif // RECAST_LOG_H
diff --git a/extern/recastnavigation/Recast/Include/RecastTimer.h b/extern/recastnavigation/Recast/Include/RecastTimer.h
new file mode 100644 (file)
index 0000000..d4f21e5
--- /dev/null
@@ -0,0 +1,31 @@
+//
+// Copyright (c) 2009 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_TIMER_H
+#define RECAST_TIMER_H
+
+#ifdef __GNUC__
+#include <stdint.h>
+typedef int64_t rcTimeVal;
+#else
+typedef __int64 rcTimeVal;
+#endif
+
+rcTimeVal rcGetPerformanceTimer();
+int rcGetDeltaTimeUsec(rcTimeVal start, rcTimeVal end);
+
+#endif // RECAST_TIMER_H
diff --git a/extern/recastnavigation/Recast/Source/Recast.cpp b/extern/recastnavigation/Recast/Source/Recast.cpp
new file mode 100644 (file)
index 0000000..4bd8b7a
--- /dev/null
@@ -0,0 +1,272 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#include <float.h>
+#define _USE_MATH_DEFINES
+#include <math.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "Recast.h"
+#include "RecastLog.h"
+#include "RecastTimer.h"
+
+
+void rcIntArray::resize(int n)
+{
+       if (n > m_cap)
+       {
+               if (!m_cap) m_cap = 8;
+               while (m_cap < n) m_cap *= 2;
+               int* newData = new int[m_cap];
+               if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
+               delete [] m_data;
+               m_data = newData;
+       }
+       m_size = n;
+}
+
+void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax)
+{
+       // Calculate bounding box.
+       vcopy(bmin, verts);
+       vcopy(bmax, verts);
+       for (int i = 1; i < nv; ++i)
+       {
+               const float* v = &verts[i*3];
+               vmin(bmin, v);
+               vmax(bmax, v);
+       }
+}
+
+void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h)
+{
+       *w = (int)((bmax[0] - bmin[0])/cs+0.5f);
+       *h = (int)((bmax[2] - bmin[2])/cs+0.5f);
+}
+
+bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
+                                                const float* bmin, const float* bmax,
+                                                float cs, float ch)
+{
+       hf.width = width;
+       hf.height = height;
+       hf.spans = new rcSpan*[hf.width*hf.height];
+       vcopy(hf.bmin, bmin);
+       vcopy(hf.bmax, bmax);
+       hf.cs = cs;
+       hf.ch = ch;
+       if (!hf.spans)
+               return false;
+       memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
+       return true;
+}
+
+static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
+{
+       float e0[3], e1[3];
+       vsub(e0, v1, v0);
+       vsub(e1, v2, v0);
+       vcross(norm, e0, e1);
+       vnormalize(norm);
+}
+
+void rcMarkWalkableTriangles(const float walkableSlopeAngle,
+                                                        const float* verts, int nv,
+                                                        const int* tris, int nt,
+                                                        unsigned char* flags)
+{
+       const float walkableThr = cosf(walkableSlopeAngle/180.0f*(float)M_PI);
+
+       float norm[3];
+       
+       for (int i = 0; i < nt; ++i)
+       {
+               const int* tri = &tris[i*3];
+               calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
+               // Check if the face is walkable.
+               if (norm[1] > walkableThr)
+                       flags[i] |= RC_WALKABLE;
+       }
+}
+
+static int getSpanCount(unsigned char flags, rcHeightfield& hf)
+{
+       const int w = hf.width;
+       const int h = hf.height;
+       int spanCount = 0;
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next)
+                       {
+                               if (s->flags == flags)
+                                       spanCount++;
+                       }
+               }
+       }
+       return spanCount;
+}
+
+inline void setCon(rcCompactSpan& s, int dir, int i)
+{
+       s.con &= ~(0xf << (dir*4));
+       s.con |= (i&0xf) << (dir*4);
+}
+
+bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
+                                                          unsigned char flags, rcHeightfield& hf,
+                                                          rcCompactHeightfield& chf)
+{
+       rcTimeVal startTime = rcGetPerformanceTimer();
+       
+       const int w = hf.width;
+       const int h = hf.height;
+       const int spanCount = getSpanCount(flags, hf);
+
+       // Fill in header.
+       chf.width = w;
+       chf.height = h;
+       chf.spanCount = spanCount;
+       chf.walkableHeight = walkableHeight;
+       chf.walkableClimb = walkableClimb;
+       chf.maxRegions = 0;
+       vcopy(chf.bmin, hf.bmin);
+       vcopy(chf.bmax, hf.bmax);
+       chf.bmax[1] += walkableHeight*hf.ch;
+       chf.cs = hf.cs;
+       chf.ch = hf.ch;
+       chf.cells = new rcCompactCell[w*h];
+       if (!chf.cells)
+       {
+               if (rcGetLog())
+                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
+               return false;
+       }
+       memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
+       chf.spans = new rcCompactSpan[spanCount];
+       if (!chf.spans)
+       {
+               if (rcGetLog())
+                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
+               return false;
+       }
+       memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
+       
+       const int MAX_HEIGHT = 0xffff;
+       
+       // Fill in cells and spans.
+       int idx = 0;
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcSpan* s = hf.spans[x + y*w];
+                       // If there are no spans at this cell, just leave the data to index=0, count=0.
+                       if (!s) continue;
+                       rcCompactCell& c = chf.cells[x+y*w];
+                       c.index = idx;
+                       c.count = 0;
+                       while (s)
+                       {
+                               if (s->flags == flags)
+                               {
+                                       const int bot = (int)s->smax;
+                                       const int top = (int)s->next ? (int)s->next->smin : MAX_HEIGHT;
+                                       chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
+                                       chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
+                                       idx++;
+                                       c.count++;
+                               }
+                               s = s->next;
+                       }
+               }
+       }
+
+       // Find neighbour connections.
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               rcCompactSpan& s = chf.spans[i];
+                               for (int dir = 0; dir < 4; ++dir)
+                               {
+                                       setCon(s, dir, 0xf);
+                                       const int nx = x + rcGetDirOffsetX(dir);
+                                       const int ny = y + rcGetDirOffsetY(dir);
+                                       // First check that the neighbour cell is in bounds.
+                                       if (nx < 0 || ny < 0 || nx >= w || ny >= h)
+                                               continue;
+                                       // Iterate over all neighbour spans and check if any of the is
+                                       // accessible from current cell.
+                                       const rcCompactCell& nc = chf.cells[nx+ny*w];
+                                       for (int k = (int)nc.index, nk = (int)(nc.index+nc.count); k < nk; ++k)
+                                       {
+                                               const rcCompactSpan& ns = chf.spans[k];
+                                               const int bot = rcMax(s.y, ns.y);
+                                               const int top = rcMin(s.y+s.h, ns.y+ns.h);
+
+                                               // Check that the gap between the spans is walkable,
+                                               // and that the climb height between the gaps is not too high.
+                                               if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
+                                               {
+                                                       // Mark direction as walkable.
+                                                       setCon(s, dir, k - (int)nc.index);
+                                                       break;
+                                               }
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       rcTimeVal endTime = rcGetPerformanceTimer();
+       
+       if (rcGetBuildTimes())
+               rcGetBuildTimes()->buildCompact += rcGetDeltaTimeUsec(startTime, endTime);
+       
+       return true;
+}
+
+static int getHeightfieldMemoryUsage(const rcHeightfield& hf)
+{
+       int size = 0;
+       size += sizeof(hf);
+       size += hf.width * hf.height * sizeof(rcSpan*);
+       
+       rcSpanPool* pool = hf.pools;
+       while (pool)
+       {
+               size += (sizeof(rcSpanPool) - sizeof(rcSpan)) + sizeof(rcSpan)*RC_SPANS_PER_POOL;
+               pool = pool->next;
+       }
+       return size;
+}
+
+static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf)
+{
+       int size = 0;
+       size += sizeof(rcCompactHeightfield);
+       size += sizeof(rcCompactSpan) * chf.spanCount;
+       size += sizeof(rcCompactCell) * chf.width * chf.height;
+       return size;
+}
diff --git a/extern/recastnavigation/Recast/Source/RecastContour.cpp b/extern/recastnavigation/Recast/Source/RecastContour.cpp
new file mode 100644 (file)
index 0000000..96f763a
--- /dev/null
@@ -0,0 +1,732 @@
+//
+// Copyright (c) 2009 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.
+//
+
+#define _USE_MATH_DEFINES
+#include <math.h>
+#include <string.h>
+#include <stdio.h>
+#include "Recast.h"
+#include "RecastLog.h"
+#include "RecastTimer.h"
+
+
+static int getCornerHeight(int x, int y, int i, int dir,
+                                                  const rcCompactHeightfield& chf,
+                                                  bool& isBorderVertex)
+{
+       const rcCompactSpan& s = chf.spans[i];
+       int ch = (int)s.y;
+       int dirp = (dir+1) & 0x3;
+       
+       unsigned short regs[4] = {0,0,0,0};
+       
+       regs[0] = s.reg;
+       
+       if (rcGetCon(s, dir) != 0xf)
+       {
+               const int ax = x + rcGetDirOffsetX(dir);
+               const int ay = y + rcGetDirOffsetY(dir);
+               const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
+               const rcCompactSpan& as = chf.spans[ai];
+               ch = rcMax(ch, (int)as.y);
+               regs[1] = as.reg;
+               if (rcGetCon(as, dirp) != 0xf)
+               {
+                       const int ax2 = ax + rcGetDirOffsetX(dirp);
+                       const int ay2 = ay + rcGetDirOffsetY(dirp);
+                       const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
+                       const rcCompactSpan& as2 = chf.spans[ai2];
+                       ch = rcMax(ch, (int)as2.y);
+                       regs[2] = as2.reg;
+               }
+       }
+       if (rcGetCon(s, dirp) != 0xf)
+       {
+               const int ax = x + rcGetDirOffsetX(dirp);
+               const int ay = y + rcGetDirOffsetY(dirp);
+               const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
+               const rcCompactSpan& as = chf.spans[ai];
+               ch = rcMax(ch, (int)as.y);
+               regs[3] = as.reg;
+               if (rcGetCon(as, dir) != 0xf)
+               {
+                       const int ax2 = ax + rcGetDirOffsetX(dir);
+                       const int ay2 = ay + rcGetDirOffsetY(dir);
+                       const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
+                       const rcCompactSpan& as2 = chf.spans[ai2];
+                       ch = rcMax(ch, (int)as2.y);
+                       regs[2] = as2.reg;
+               }
+       }
+
+       // Check if the vertex is special edge vertex, these vertices will be removed later.
+       for (int j = 0; j < 4; ++j)
+       {
+               const int a = j;
+               const int b = (j+1) & 0x3;
+               const int c = (j+2) & 0x3;
+               const int d = (j+3) & 0x3;
+               
+               // The vertex is a border vertex there are two same exterior cells in a row,
+               // followed by two interior cells and none of the regions are out of bounds.
+               const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
+               const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
+               const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
+               if (twoSameExts && twoInts && noZeros)
+               {
+                       isBorderVertex = true;
+                       break;
+               }
+       }
+       
+       return ch;
+}
+
+static void walkContour(int x, int y, int i,
+                                               rcCompactHeightfield& chf,
+                                               unsigned char* flags, rcIntArray& points)
+{
+       // Choose the first non-connected edge
+       unsigned char dir = 0;
+       while ((flags[i] & (1 << dir)) == 0)
+               dir++;
+       
+       unsigned char startDir = dir;
+       int starti = i;
+       
+       int iter = 0;
+       while (++iter < 40000)
+       {
+               if (flags[i] & (1 << dir))
+               {
+                       // Choose the edge corner
+                       bool isBorderVertex = false;
+                       int px = x;
+                       int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
+                       int pz = y;
+                       switch(dir)
+                       {
+                               case 0: pz++; break;
+                               case 1: px++; pz++; break;
+                               case 2: px++; break;
+                       }
+                       int r = 0;
+                       const rcCompactSpan& s = chf.spans[i];
+                       if (rcGetCon(s, dir) != 0xf)
+                       {
+                               const int ax = x + rcGetDirOffsetX(dir);
+                               const int ay = y + rcGetDirOffsetY(dir);
+                               const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
+                               const rcCompactSpan& as = chf.spans[ai];
+                               r = (int)as.reg;
+                       }
+                       if (isBorderVertex)
+                               r |= RC_BORDER_VERTEX;
+                       points.push(px);
+                       points.push(py);
+                       points.push(pz);
+                       points.push(r);
+                       
+                       flags[i] &= ~(1 << dir); // Remove visited edges
+                       dir = (dir+1) & 0x3;  // Rotate CW
+               }
+               else
+               {
+                       int ni = -1;
+                       const int nx = x + rcGetDirOffsetX(dir);
+                       const int ny = y + rcGetDirOffsetY(dir);
+                       const rcCompactSpan& s = chf.spans[i];
+                       if (rcGetCon(s, dir) != 0xf)
+                       {
+                               const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
+                               ni = (int)nc.index + rcGetCon(s, dir);
+                       }
+                       if (ni == -1)
+                       {
+                               // Should not happen.
+                               return;
+                       }
+                       x = nx;
+                       y = ny;
+                       i = ni;
+                       dir = (dir+3) & 0x3;    // Rotate CCW
+               }
+               
+               if (starti == i && startDir == dir)
+               {
+                       break;
+               }
+       }
+}
+
+static float distancePtSeg(int x, int y, int z,
+                                                  int px, int py, int pz,
+                                                  int qx, int qy, int qz)
+{
+/*     float pqx = (float)(qx - px);
+       float pqy = (float)(qy - py);
+       float pqz = (float)(qz - pz);
+       float dx = (float)(x - px);
+       float dy = (float)(y - py);
+       float dz = (float)(z - pz);
+       float d = pqx*pqx + pqy*pqy + pqz*pqz;
+       float t = pqx*dx + pqy*dy + pqz*dz;
+       if (d > 0)
+               t /= d;
+       if (t < 0)
+               t = 0;
+       else if (t > 1)
+               t = 1;
+       
+       dx = px + t*pqx - x;
+       dy = py + t*pqy - y;
+       dz = pz + t*pqz - z;
+       
+       return dx*dx + dy*dy + dz*dz;*/
+
+       float pqx = (float)(qx - px);
+       float pqz = (float)(qz - pz);
+       float dx = (float)(x - px);
+       float dz = (float)(z - pz);
+       float d = pqx*pqx + pqz*pqz;
+       float t = pqx*dx + pqz*dz;
+       if (d > 0)
+               t /= d;
+       if (t < 0)
+               t = 0;
+       else if (t > 1)
+               t = 1;
+       
+       dx = px + t*pqx - x;
+       dz = pz + t*pqz - z;
+       
+       return dx*dx + dz*dz;
+}
+
+static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float maxError, int maxEdgeLen)
+{
+       // Add initial points.
+       bool noConnections = true;
+       for (int i = 0; i < points.size(); i += 4)
+       {
+               if ((points[i+3] & 0xffff) != 0)
+               {
+                       noConnections = false;
+                       break;
+               }
+       }
+       
+       if (noConnections)
+       {
+               // If there is no connections at all,
+               // create some initial points for the simplification process. 
+               // Find lower-left and upper-right vertices of the contour.
+               int llx = points[0];
+               int lly = points[1];
+               int llz = points[2];
+               int lli = 0;
+               int urx = points[0];
+               int ury = points[1];
+               int urz = points[2];
+               int uri = 0;
+               for (int i = 0; i < points.size(); i += 4)
+               {
+                       int x = points[i+0];
+                       int y = points[i+1];
+                       int z = points[i+2];
+                       if (x < llx || (x == llx && z < llz))
+                       {
+                               llx = x;
+                               lly = y;
+                               llz = z;
+                               lli = i/4;
+                       }
+                       if (x >= urx || (x == urx && z > urz))
+                       {
+                               urx = x;
+                               ury = y;
+                               urz = z;
+                               uri = i/4;
+                       }
+               }
+               simplified.push(llx);
+               simplified.push(lly);
+               simplified.push(llz);
+               simplified.push(lli);
+               
+               simplified.push(urx);
+               simplified.push(ury);
+               simplified.push(urz);
+               simplified.push(uri);
+       }
+       else
+       {
+               // The contour has some portals to other regions.
+               // Add a new point to every location where the region changes.
+               for (int i = 0, ni = points.size()/4; i < ni; ++i)
+               {
+                       int ii = (i+1) % ni;
+                       if ((points[i*4+3] & 0xffff) != (points[ii*4+3] & 0xffff))
+                       {
+                               simplified.push(points[i*4+0]);
+                               simplified.push(points[i*4+1]);
+                               simplified.push(points[i*4+2]);
+                               simplified.push(i);
+                       }
+               }       
+       }
+       
+       // Add points until all raw points are within
+       // error tolerance to the simplified shape.
+       const int pn = points.size()/4;
+       for (int i = 0; i < simplified.size()/4; )
+       {
+               int ii = (i+1) % (simplified.size()/4);
+               
+               int ax = simplified[i*4+0];
+               int ay = simplified[i*4+1];
+               int az = simplified[i*4+2];
+               int ai = simplified[i*4+3];
+               
+               int bx = simplified[ii*4+0];
+               int by = simplified[ii*4+1];
+               int bz = simplified[ii*4+2];
+               int bi = simplified[ii*4+3];
+               
+               // Find maximum deviation from the segment.
+               float maxd = 0;
+               int maxi = -1;
+               int ci = (ai+1) % pn;
+               
+               // Tesselate only outer edges.
+               if ((points[ci*4+3] & 0xffff) == 0)
+               {
+                       while (ci != bi)
+                       {
+                               float d = distancePtSeg(points[ci*4+0], points[ci*4+1]/4, points[ci*4+2],
+                                                                               ax, ay/4, az, bx, by/4, bz);
+                               if (d > maxd)
+                               {
+                                       maxd = d;
+                                       maxi = ci;
+                               }
+                               ci = (ci+1) % pn;
+                       }
+               }
+               
+               
+               // If the max deviation is larger than accepted error,
+               // add new point, else continue to next segment.
+               if (maxi != -1 && maxd > (maxError*maxError))
+               {
+                       // Add space for the new point.
+                       simplified.resize(simplified.size()+4);
+                       int n = simplified.size()/4;
+                       for (int j = n-1; j > i; --j)
+                       {
+                               simplified[j*4+0] = simplified[(j-1)*4+0];
+                               simplified[j*4+1] = simplified[(j-1)*4+1];
+                               simplified[j*4+2] = simplified[(j-1)*4+2];
+                               simplified[j*4+3] = simplified[(j-1)*4+3];
+                       }
+                       // Add the point.
+                       simplified[(i+1)*4+0] = points[maxi*4+0];
+                       simplified[(i+1)*4+1] = points[maxi*4+1];
+                       simplified[(i+1)*4+2] = points[maxi*4+2];
+                       simplified[(i+1)*4+3] = maxi;
+               }
+               else
+               {
+                       ++i;
+               }
+       }
+       
+       // Split too long edges.
+       if (maxEdgeLen > 0)
+       {
+               for (int i = 0; i < simplified.size()/4; )
+               {
+                       int ii = (i+1) % (simplified.size()/4);
+                       
+                       int ax = simplified[i*4+0];
+                       int az = simplified[i*4+2];
+                       int ai = simplified[i*4+3];
+                       
+                       int bx = simplified[ii*4+0];
+                       int bz = simplified[ii*4+2];
+                       int bi = simplified[ii*4+3];
+                       
+                       // Find maximum deviation from the segment.
+                       int maxi = -1;
+                       int ci = (ai+1) % pn;
+                       
+                       // Tesselate only outer edges.
+                       if ((points[ci*4+3] & 0xffff) == 0)
+                       {
+                               int dx = bx - ax;
+                               int dz = bz - az;
+                               if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
+                               {
+                                       int n = bi < ai ? (bi+pn - ai) : (bi - ai);
+                                       maxi = (ai + n/2) % pn;
+                               }
+                       }
+                       
+                       // If the max deviation is larger than accepted error,
+                       // add new point, else continue to next segment.
+                       if (maxi != -1)
+                       {
+                               // Add space for the new point.
+                               simplified.resize(simplified.size()+4);
+                               int n = simplified.size()/4;
+                               for (int j = n-1; j > i; --j)
+                               {
+                                       simplified[j*4+0] = simplified[(j-1)*4+0];
+                                       simplified[j*4+1] = simplified[(j-1)*4+1];
+                                       simplified[j*4+2] = simplified[(j-1)*4+2];
+                                       simplified[j*4+3] = simplified[(j-1)*4+3];
+                               }
+                               // Add the point.
+                               simplified[(i+1)*4+0] = points[maxi*4+0];
+                               simplified[(i+1)*4+1] = points[maxi*4+1];
+                               simplified[(i+1)*4+2] = points[maxi*4+2];
+                               simplified[(i+1)*4+3] = maxi;
+                       }
+                       else
+                       {
+                               ++i;
+                       }
+               }
+       }
+       
+       for (int i = 0; i < simplified.size()/4; ++i)
+       {
+               // The edge vertex flag is take from the current raw point,
+               // and the neighbour region is take from the next raw point.
+               const int ai = (simplified[i*4+3]+1) % pn;
+               const int bi = simplified[i*4+3];
+               simplified[i*4+3] = (points[ai*4+3] & 0xffff) | (points[bi*4+3] & RC_BORDER_VERTEX);
+       }
+       
+}
+
+static void removeDegenerateSegments(rcIntArray& simplified)
+{
+       // Remove adjacent vertices which are equal on xz-plane,
+       // or else the triangulator will get confused.
+       for (int i = 0; i < simplified.size()/4; ++i)
+       {
+               int ni = i+1;
+               if (ni >= (simplified.size()/4))
+                       ni = 0;
+                       
+               if (simplified[i*4+0] == simplified[ni*4+0] &&
+                       simplified[i*4+2] == simplified[ni*4+2])
+               {
+                       // Degenerate segment, remove.
+                       for (int j = i; j < simplified.size()/4-1; ++j)
+                       {
+                               simplified[j*4+0] = simplified[(j+1)*4+0];
+                               simplified[j*4+1] = simplified[(j+1)*4+1];
+                               simplified[j*4+2] = simplified[(j+1)*4+2];
+                               simplified[j*4+3] = simplified[(j+1)*4+3];
+                       }
+                       simplified.pop();
+               }
+       }
+}
+
+static int calcAreaOfPolygon2D(const int* verts, const int nverts)
+{
+       int area = 0;
+       for (int i = 0, j = nverts-1; i < nverts; j=i++)
+       {
+               const int* vi = &verts[i*4];
+               const int* vj = &verts[j*4];
+               area += vi[0] * vj[2] - vj[0] * vi[2];
+       }
+       return (area+1) / 2;
+}
+
+static void getClosestIndices(const int* vertsa, const int nvertsa,
+                                                         const int* vertsb, const int nvertsb,
+                                                         int& ia, int& ib)
+{
+       int closestDist = 0xfffffff;
+       for (int i = 0; i < nvertsa; ++i)
+       {
+               const int* va = &vertsa[i*4];
+               for (int j = 0; j < nvertsb; ++j)
+               {
+                       const int* vb = &vertsb[j*4];
+                       const int dx = vb[0] - va[0];
+                       const int dz = vb[2] - va[2];
+                       const int d = dx*dx + dz*dz;
+                       if (d < closestDist)
+                       {
+                               ia = i;
+                               ib = j;
+                               closestDist = d;
+                       }
+               }
+       }
+}
+
+static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
+{
+       const int maxVerts = ca.nverts + cb.nverts + 2;
+       int* verts = new int[maxVerts*4];
+       if (!verts)
+               return false;
+
+       int nv = 0;
+
+       // Copy contour A.
+       for (int i = 0; i <= ca.nverts; ++i)
+       {
+               int* dst = &verts[nv*4];
+               const int* src = &ca.verts[((ia+i)%ca.nverts)*4];
+               dst[0] = src[0];
+               dst[1] = src[1];
+               dst[2] = src[2];
+               dst[3] = src[3];
+               nv++;
+       }
+
+       // Copy contour B
+       for (int i = 0; i <= cb.nverts; ++i)
+       {
+               int* dst = &verts[nv*4];
+               const int* src = &cb.verts[((ib+i)%cb.nverts)*4];
+               dst[0] = src[0];
+               dst[1] = src[1];
+               dst[2] = src[2];
+               dst[3] = src[3];
+               nv++;
+       }
+       
+       delete [] ca.verts;
+       ca.verts = verts;
+       ca.nverts = nv;
+
+       delete [] cb.verts;
+       cb.verts = 0;
+       cb.nverts = 0;
+       
+       return true;
+}
+
+bool rcBuildContours(rcCompactHeightfield& chf,
+                                        const float maxError, const int maxEdgeLen,
+                                        rcContourSet& cset)
+{
+       const int w = chf.width;
+       const int h = chf.height;
+       
+       rcTimeVal startTime = rcGetPerformanceTimer();
+       
+       vcopy(cset.bmin, chf.bmin);
+       vcopy(cset.bmax, chf.bmax);
+       cset.cs = chf.cs;
+       cset.ch = chf.ch;
+       
+       const int maxContours = chf.maxRegions*2;
+       cset.conts = new rcContour[maxContours];
+       if (!cset.conts)
+               return false;
+       cset.nconts = 0;
+       
+       unsigned char* flags = new unsigned char[chf.spanCount];
+       if (!flags)
+       {
+               if (rcGetLog())
+                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags'.");
+               return false;
+       }
+       
+       rcTimeVal traceStartTime = rcGetPerformanceTimer();
+                                       
+       
+       // Mark boundaries.
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               unsigned char res = 0;
+                               const rcCompactSpan& s = chf.spans[i];
+                               if (!s.reg || (s.reg & RC_BORDER_REG))
+                               {
+                                       flags[i] = 0;
+                                       continue;
+                               }
+                               for (int dir = 0; dir < 4; ++dir)
+                               {
+                                       unsigned short r = 0;
+                                       if (rcGetCon(s, dir) != 0xf)
+                                       {
+                                               const int ax = x + rcGetDirOffsetX(dir);
+                                               const int ay = y + rcGetDirOffsetY(dir);
+                           &nbs