8 files changed, 600 insertions, 633 deletions

diff --git a/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp
new file mode 100644
index 00000000000..ed02a27cc43
--- /dev/null
+++ b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.cpp
@@ -0,0 +1,406 @@
+/**
+* $Id$ 
+*
+* ***** BEGIN GPL LICENSE BLOCK *****
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software Foundation,
+* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#include "NavMeshConversion.h"
+extern "C"{
+#include "BLI_math.h"
+}
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
+{
+	int nv = 0;
+	for (int i=0; i<vertsPerPoly; i++)
+	{
+		if (p[i]==0xffff)
+			break;
+		nv++;
+	}
+	return nv;
+}
+
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
+{
+	int nv = polyNumVerts(p, vertsPerPoly);
+	if (nv<3)
+		return false;
+	for (int j=0; j<nv; j++)
+	{
+		const float* v = &verts[3*p[j]];
+		const float* v_next = &verts[3*p[(j+1)%nv]];
+		const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
+		if (!left(v_prev, v, v_next))
+			return false;
+
+	}
+	return true;
+}
+
+float distPointToSegmentSq(const float* point, const float* a, const float* b)
+{
+	float abx[3], dx[3];
+	vsub(abx, b,a);
+	vsub(dx, point,a);
+	float d = abx[0]*abx[0]+abx[2]*abx[2];
+	float t = abx[0]*dx[0]+abx[2]*dx[2];
+	if (d > 0)
+		t /= d;
+	if (t < 0)
+		t = 0;
+	else if (t > 1)
+		t = 1;
+	dx[0] = a[0] + t*abx[0] - point[0];
+	dx[2] = a[2] + t*abx[2] - point[2];
+	return dx[0]*dx[0] + dx[2]*dx[2];
+}
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+									int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+									int *&recastData)
+{
+	nverts = dm->getNumVerts(dm);
+	verts = new float[3*nverts];
+	dm->getVertCos(dm, (float(*)[3])verts);
+
+	//flip coordinates
+	for (int vi=0; vi<nverts; vi++)
+	{
+		SWAP(float, verts[3*vi+1], verts[3*vi+2]);
+	}
+
+	//calculate number of tris
+	int nfaces = dm->getNumFaces(dm);
+	MFace *faces = dm->getFaceArray(dm);
+	ntris = nfaces;
+	for (int fi=0; fi<nfaces; fi++)
+	{
+		MFace* face = &faces[fi];
+		if (face->v4)
+			ntris++;
+	}
+
+	//copy and transform to triangles (reorder on the run)
+	trisToFacesMap = new int[ntris];
+	tris = new unsigned short[3*ntris];
+	unsigned short* tri = tris;
+	int triIdx = 0;
+	for (int fi=0; fi<nfaces; fi++)
+	{
+		MFace* face = &faces[fi];
+		tri[3*triIdx+0] = face->v1;
+		tri[3*triIdx+1] = face->v3;
+		tri[3*triIdx+2] = face->v2;
+		trisToFacesMap[triIdx++]=fi;
+		if (face->v4)
+		{
+			tri[3*triIdx+0] = face->v1;
+			tri[3*triIdx+1] = face->v4;
+			tri[3*triIdx+2] = face->v3;
+			trisToFacesMap[triIdx++]=fi;
+		}
+	}
+
+	//carefully, recast data is just reference to data in derived mesh
+	recastData = (int*)CustomData_get_layer(&dm->faceData, CD_PROP_INT);
+	return true;
+}
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+										  unsigned short* polys, const unsigned short* dmeshes, 
+										  const float* verts, const unsigned short* dtris, 
+										  const int* dtrisToPolysMap)
+{
+	bool res = false;
+	int capacity = vertsPerPoly;
+	unsigned short* newPoly =  new unsigned short[capacity];
+	memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
+	for (int polyidx=0; polyidx<npolys; polyidx++)
+	{
+		int nv = 0;
+		//search border 
+		int btri = -1;
+		int bedge = -1;
+		for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
+		{
+			int curpolytri = dmeshes[polyidx*4+2]+j;
+			for (int k=0; k<3; k++)
+			{
+				unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
+				if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+				{
+					btri = curpolytri;
+					bedge = k;
+					break;
+				}
+			}							
+		}
+		if (btri==-1 || bedge==-1)
+		{
+			//can't find triangle with border edge
+			return false;
+		}
+
+		newPoly[nv++] = dtris[btri*3*2+bedge];
+
+		int tri = btri;
+		int edge = (bedge+1)%3;
+		while (tri!=btri || edge!=bedge)
+		{
+			int neighbortri = dtris[tri*3*2+3+edge];
+			if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+			{
+				if (nv==capacity)
+				{
+					capacity += vertsPerPoly;
+					unsigned short* newPolyBig =  new unsigned short[capacity];
+					memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
+					memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
+					delete newPoly;
+					newPoly = newPolyBig;			
+				}
+				newPoly[nv++] = dtris[tri*3*2+edge];
+				//move to next edge					
+				edge = (edge+1)%3;
+			}
+			else
+			{
+				//move to next tri
+				int twinedge = -1;
+				for (int k=0; k<3; k++)
+				{
+					if (dtris[neighbortri*3*2+3+k] == tri)
+					{
+						twinedge = k;
+						break;
+					}
+				}
+				if (twinedge==-1)
+				{
+					printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
+					goto returnLabel;					
+				}
+				tri = neighbortri;
+				edge = (twinedge+1)%3;
+			}
+		}
+
+		unsigned short* adjustedPoly = new unsigned short[nv];
+		int adjustedNv = 0;
+		for (size_t i=0; i<(size_t)nv; i++)
+		{
+			unsigned short prev = newPoly[(nv+i-1)%nv];
+			unsigned short cur = newPoly[i];
+			unsigned short next = newPoly[(i+1)%nv];
+			float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
+			static const float tolerance = 0.001f;
+			if (distSq>tolerance)
+				adjustedPoly[adjustedNv++] = cur;
+		}
+		memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
+		delete adjustedPoly;
+		nv = adjustedNv;
+
+		if (nv<=vertsPerPoly)
+		{
+			for (int i=0; i<nv; i++)
+			{
+				polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
+			}
+		}
+		else
+		{
+			int a=0;
+		}
+	}
+	res = true;
+
+returnLabel:
+	delete newPoly;
+	return true;
+}
+
+struct SortContext
+{
+	const int* recastData;
+	const int* trisToFacesMap;
+};
+static int compareByData(void* data, const void * a, const void * b){
+	SortContext* context = (SortContext*)data;
+	return ( context->recastData[context->trisToFacesMap[*(int*)a]] - 
+		context->recastData[context->trisToFacesMap[*(int*)b]] );
+}
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+							 const int ntris, const unsigned short *tris, 
+							 const int* recastData, const int* trisToFacesMap,
+							 int &ndtris, unsigned short *&dtris,
+							 int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+							 int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap)
+
+{
+	if (!recastData)
+	{
+		printf("Converting navmesh: Error! Can't find recast custom data\n");
+		return false;
+	}
+
+	//sort the triangles by polygon idx
+	int* trisMapping = new int[ntris];
+	for (int i=0; i<ntris; i++)
+		trisMapping[i]=i;
+	SortContext context;
+	context.recastData = recastData;
+	context.trisToFacesMap = trisToFacesMap;
+	qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
+
+	//search first valid triangle - triangle of convex polygon
+	int validTriStart = -1;
+	for (int i=0; i< ntris; i++)
+	{
+		if (recastData[trisToFacesMap[trisMapping[i]]]>0)
+		{
+			validTriStart = i;
+			break;
+		}
+	}
+
+	if (validTriStart<0)
+	{
+		printf("Converting navmesh: Error! No valid polygons in mesh\n");
+		delete trisMapping;
+		return false;
+	}
+
+	ndtris = ntris-validTriStart;
+	//fill dtris to faces mapping
+	dtrisToTrisMap = new int[ndtris];
+	memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
+	delete trisMapping; trisMapping=NULL;
+
+	//create detailed mesh triangles  - copy only valid triangles
+	//and reserve memory for adjacency info
+	dtris = new unsigned short[3*2*ndtris];
+	memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
+	for (int i=0; i<ndtris; i++)
+	{
+		memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
+	}
+	//create new recast data corresponded to dtris
+	dtrisToPolysMap = new int[ndtris];
+	for (int i=0; i<ndtris; i++)
+	{
+		dtrisToPolysMap[i] = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
+	}
+
+
+	//build adjacency info for detailed mesh triangles
+	buildMeshAdjacency(dtris, ntris, nverts, 3);
+
+	//create detailed mesh description for each navigation polygon
+	npolys = dtrisToPolysMap[ndtris-1];
+	dmeshes = new unsigned short[npolys*4];
+	memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
+	unsigned short *dmesh = NULL;
+	int prevpolyidx = 0;
+	for (int i=0; i<ndtris; i++)
+	{
+		int curpolyidx = dtrisToPolysMap[i];
+		if (curpolyidx!=prevpolyidx)
+		{
+			if (curpolyidx!=prevpolyidx+1)
+			{
+				printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
+				return false;
+			}
+			dmesh = dmesh==NULL ? dmeshes : dmesh+4;
+			dmesh[2] = i;	//tbase
+			dmesh[3] = 0;	//tnum
+			prevpolyidx = curpolyidx;
+		}
+		dmesh[3]++;
+	}
+
+	//create navigation polygons
+	vertsPerPoly = 6;
+	polys = new unsigned short[npolys*vertsPerPoly*2];
+	memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
+
+	buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
+
+	return true;
+}
+
+
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+										  int &nverts, float *&verts,
+										  int &ndtris, unsigned short *&dtris,
+										  int& npolys, unsigned short *&dmeshes,
+										  unsigned short*& polys, int *&dtrisToPolysMap,
+										  int *&dtrisToTrisMap, int *&trisToFacesMap)
+{
+	bool res = true;
+	int ntris =0, *recastData=NULL;
+	unsigned short *tris=NULL;
+	res = buildRawVertIndicesData(dm, nverts, verts, ntris, tris, trisToFacesMap, recastData);
+	if (!res)
+	{
+		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+		goto exit;
+	}
+
+	res = buildNavMeshData(nverts, verts, ntris, tris, recastData, trisToFacesMap,
+		ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
+		dtrisToPolysMap, dtrisToTrisMap);
+	if (!res)
+	{
+		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
+		goto exit;
+	}
+
+exit:
+	if (tris)
+		delete tris;
+
+	return res;
+}
+
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx)
+{
+	int res = -1;
+	for(int i=0; i<vertsPerPoly; i++)
+	{
+		if (p[i]==0xffff)
+			break;
+		if (p[i]==vertexIdx)
+		{
+			res = i;
+			break;
+		}
+	}
+	return res;
+}
\ No newline at end of file
diff --git a/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h
new file mode 100644
index 00000000000..5a30d927c7f
--- /dev/null
+++ b/extern/recastnavigation/BlenderNavMesh/NavMeshConversion.h
@@ -0,0 +1,98 @@
+/**
+* $Id$ 
+*
+* ***** BEGIN GPL LICENSE BLOCK *****
+*
+* This program is free software; you can redistribute it and/or
+* modify it under the terms of the GNU General Public License
+* as published by the Free Software Foundation; either version 2
+* of the License, or (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program; if not, write to the Free Software Foundation,
+* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+*
+* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#ifndef NAVMESH_CONVERSION_H
+#define NAVMESH_CONVERSION_H
+
+#include <math.h>
+#include "Recast.h"
+extern "C"{
+#include "DNA_meshdata_types.h"
+#include "BKE_cdderivedmesh.h"
+}
+
+bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
+								   int &nverts, float *&verts,
+								   int &ndtris, unsigned short *&dtris,
+								   int& npolys, unsigned short *&dmeshes,
+								   unsigned short*& polys, int *&dtrisToPolysMap,
+								   int *&dtrisToTrisMap, int *&trisToFacesMap);
+
+bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
+				int &ntris, unsigned short *&tris, int *&trisToFacesMap,
+				int *&recastData);
+
+bool buildNavMeshData(const int nverts, const float* verts, 
+					  const int ntris, const unsigned short *tris, 
+					  const int* recastData, const int* trisToFacesMap,
+					  int &ndtris, unsigned short *&dtris,
+					  int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
+					  int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap);
+
+bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
+				unsigned short* polys, const unsigned short* dmeshes, 
+				const float* verts, const unsigned short* dtris, 
+				const int* dtrisToPolysMap);
+
+int polyNumVerts(const unsigned short* p, const int vertsPerPoly);
+bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts);
+int polyFindVertex(const unsigned short* p, const int vertsPerPoly, unsigned short vertexIdx);
+float distPointToSegmentSq(const float* point, const float* a, const float* b);
+
+
+inline int abs2(int a)
+{
+	return a>=0 ? a: -a;
+}
+
+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;
+}
+
+inline float area2(const float* a, const float* b, const float* c)
+{
+	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
+}
+inline bool left(const float* a, const float* b, const float* c)
+{
+	return area2(a, b, c) < 0;
+}
+
+#endif //NAVMESH_CONVERSION_H
\ No newline at end of file
diff --git a/extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj b/extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj
index c0f451176c6..5dfa123e471 100644
--- a/extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj
+++ b/extern/recastnavigation/make/msvc_9_0/recastnavigation.vcproj
@@ -41,7 +41,7 @@
 			<Tool

 				Name="VCCLCompilerTool"

 				Optimization="0"

-				AdditionalIncludeDirectories="../../Recast/Include; ../../Detour/Include"

+				AdditionalIncludeDirectories="../../Recast/Include;../../Detour/Include;../../../../source/blender/makesdna;../../../../source/blender/blenkernel;../../../../source/blender/blenlib"

 				PreprocessorDefinitions="WIN32;_DEBUG;_WINDOWS"

 				MinimalRebuild="true"

 				BasicRuntimeChecks="3"

@@ -77,7 +77,7 @@
 			/>

 			<Tool

 				Name="VCPostBuildEventTool"

-				CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done"

+				CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;XCOPY /Y ..\..\BlenderNavMesh\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done&#x0D;&#x0A;"

 			/>

 		</Configuration>

 		<Configuration

@@ -106,8 +106,8 @@
 			<Tool

 				Name="VCCLCompilerTool"

 				Optimization="2"

-				EnableIntrinsicFunctions="true"

-				AdditionalIncludeDirectories="../../Recast/Include; ../../Detour/Include"

+				EnableIntrinsicFunctions="false"

+				AdditionalIncludeDirectories="../../Recast/Include;../../Detour/Include;../../../../source/blender/makesdna;../../../../source/blender/blenkernel;../../../../source/blender/blenlib"

 				PreprocessorDefinitions="WIN32;NDEBUG;_WINDOWS"

 				RuntimeLibrary="0"

 				EnableFunctionLevelLinking="true"

@@ -142,7 +142,7 @@
 			/>

 			<Tool

 				Name="VCPostBuildEventTool"

-				CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done"

+				CommandLine="ECHO Copying header files&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\ MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;IF NOT EXIST ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh MKDIR ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;XCOPY /Y ..\..\Detour\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include&#x0D;&#x0A;XCOPY /Y ..\..\Recast\Include\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include&#x0D;&#x0A;XCOPY /Y ..\..\BlenderNavMesh\*.h ..\..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh&#x0D;&#x0A;&#x0D;&#x0A;ECHO Done&#x0D;&#x0A;"

 			/>

 		</Configuration>

 	</Configurations>

@@ -269,6 +269,18 @@
 				</File>

 			</Filter>

 		</Filter>

+		<Filter

+			Name="BlenderNavMesh"

+			>

+			<File

+				RelativePath="..\..\BlenderNavMesh\NavMeshConversion.cpp"

+				>

+			</File>

+			<File

+				RelativePath="..\..\BlenderNavMesh\NavMeshConversion.h"

+				>

+			</File>

+		</Filter>

 	</Files>

 	<Globals>

 	</Globals>

diff --git a/projectfiles_vc9/blender/blender.sln b/projectfiles_vc9/blender/blender.sln
index c9cc7fa20b4..5051332afc1 100644
--- a/projectfiles_vc9/blender/blender.sln
+++ b/projectfiles_vc9/blender/blender.sln
@@ -185,6 +185,9 @@ EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_converter", "..\gameengine\converter\KX_converter.vcproj", "{F90BD995-FFA4-4B18-81E8-FA4322C939E8}"

 EndProject

 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_ketsji", "..\gameengine\ketsji\KX_ketsji.vcproj", "{E645CC32-4823-463E-82F0-46ADDE664018}"

+	ProjectSection(ProjectDependencies) = postProject

+		{FB55B14E-D38E-4D04-BA7B-748EBC97FDB6} = {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}

+	EndProjectSection

 EndProject

 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "KX_network", "..\gameengine\ketsji\network\KX_network.vcproj", "{6E24BF09-9653-4166-A871-F65CC9E98A9B}"

 EndProject

@@ -340,6 +343,9 @@ EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "BF_collada", "collada\BF_collada.vcproj", "{76D3102B-7DD2-8BA1-034A-8B19FE2897C2}"

 EndProject

 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "BL_modifiers", "modifiers\modifiers.vcproj", "{7CB0C521-91E0-40CE-A7C4-45FEA7ABE8BC}"

+	ProjectSection(ProjectDependencies) = postProject

+		{FB55B14E-D38E-4D04-BA7B-748EBC97FDB6} = {FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}

+	EndProjectSection

 EndProject

 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "EXT_recastnavigation", "..\..\extern\recastnavigation\make\msvc_9_0\recastnavigation.vcproj", "{FB55B14E-D38E-4D04-BA7B-748EBC97FDB6}"

 EndProject

diff --git a/projectfiles_vc9/blender/modifiers/modifiers.vcproj b/projectfiles_vc9/blender/modifiers/modifiers.vcproj
index f47c3ec00ca..c994e838dc9 100644
--- a/projectfiles_vc9/blender/modifiers/modifiers.vcproj
+++ b/projectfiles_vc9/blender/modifiers/modifiers.vcproj
@@ -182,7 +182,7 @@
 			<Tool

 				Name="VCCLCompilerTool"

 				Optimization="0"

-				AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include"

+				AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh"

 				PreprocessorDefinitions="_DEBUG;WIN32;_LIB;WITH_LZO;WITH_LZMA"

 				MinimalRebuild="false"

 				BasicRuntimeChecks="3"

@@ -253,7 +253,7 @@
 			<Tool

 				Name="VCCLCompilerTool"

 				Optimization="2"

-				AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu"

+				AdditionalIncludeDirectories="..\..\..\..\lib\windows\zlib\include;..\..\..\..\build\msvc_9\intern\bsp\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\intern\decimation\include;..\..\..\..\build\msvc_9\intern\elbeem\include;..\..\..\..\build\msvc_9\intern\iksolver\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\blenkernel;..\..\..\source\blender\blenkernel\intern;..\..\..\source\blender\makesdna;..\..\..\source\blender\modifiers;..\..\..\source\blender\render\extern\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\source\blender\editors\include;..\..\..\source\blender\gpu"

 				PreprocessorDefinitions="NDEBUG;WIN32;_LIB;WITH_LZO;WITH_LZMA"

 				BasicRuntimeChecks="0"

 				RuntimeLibrary="0"

diff --git a/projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj b/projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj
index a4d33fd9d21..28ba0b332fc 100644
--- a/projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj
+++ b/projectfiles_vc9/gameengine/ketsji/KX_ketsji.vcproj
@@ -194,7 +194,7 @@
 			<Tool

 				Name="VCCLCompilerTool"

 				Optimization="0"

-				AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"

+				AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"

 				PreprocessorDefinitions="JANCODEPANCO;WIN32;_LIB;EXP_PYTHON_EMBEDDING;_DEBUG;USE_SUMO_SOLID;WITH_GLEXT;GLEW_STATIC;WITH_FFMPEG"

 				BasicRuntimeChecks="3"

 				RuntimeLibrary="1"

@@ -271,7 +271,7 @@
 				Name="VCCLCompilerTool"

 				Optimization="2"

 				InlineFunctionExpansion="1"

-				AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"

+				AdditionalIncludeDirectories="..\..\..\..\build\msvc_9\intern\string\include;..\..\..\..\build\msvc_9\intern\moto\include;..\..\..\..\build\msvc_9\intern\soundsystem\include;..\..\..\..\build\msvc_9\intern\guardedalloc\include;..\..\..\..\build\msvc_9\extern\bullet\include;..\..\..\..\build\msvc_9\extern\solid\include;..\..\..\..\build\msvc_9\extern\recastnavigation\Detour\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\Recast\Include;..\..\..\..\build\msvc_9\extern\recastnavigation\BlenderNavMesh;..\..\..\..\build\msvc_9\extern\glew\include;..\..\..\..\lib\windows\python\include\python3.1;..\..\..\..\lib\windows\sdl\include;..\..\..\source\blender\imbuf;..\..\..\source\blender\include;..\..\..\source\blender\blenlib;..\..\..\source\blender\python;..\..\..\source\blender\python\generic;..\..\..\source\blender\makesdna;..\..\..\source\blender\blenloader;..\..\..\source\blender\blenkernel;..\..\..\source\kernel\gen_system;..\..\..\source\gameengine\physics;..\..\..\source\gameengine\rasterizer;..\..\..\source\gameengine\network;..\..\..\source\gameengine\Converter;..\..\..\source\gameengine\gamelogic;..\..\..\source\gameengine\scenegraph;..\..\..\source\gameengine\expressions;..\..\..\source\gameengine\physics\sumo;..\..\..\source\gameengine\physics\dummy;..\..\..\source\gameengine\physics\BlOde;..\..\..\source\gameengine\ketsji\kxnetwork;..\..\..\source\gameengine\physics\common;..\..\..\source\gameengine\physics\sumo\include;..\..\..\source\gameengine\physics\common\dummy;..\..\..\source\gameengine\Rasterizer\RAS_OpenGLRasterizer;..\..\..\source\gameengine\physics\sumo\fuzzics\include;..\..\..\source\sumo\include;..\..\..\source\sumo\fuzzics\include;..\..\..\source\gameengine\physics\bullet;..\..\..\source\blender\python\api2_2x;..\..\..\source\blender\gpu;..\..\..\intern\audaspace\intern"

 				PreprocessorDefinitions="NDEBUG;WIN32;_LIB;USE_SUMO_SOLID;WITH_GLEXT;GLEW_STATIC;WITH_FFMPEG"

 				StringPooling="true"

 				RuntimeLibrary="0"

diff --git a/source/blender/modifiers/intern/MOD_navmesh.cpp b/source/blender/modifiers/intern/MOD_navmesh.cpp
index 6bf2400b3f6..8f914245888 100644
--- a/source/blender/modifiers/intern/MOD_navmesh.cpp
+++ b/source/blender/modifiers/intern/MOD_navmesh.cpp
@@ -27,6 +27,7 @@
 */
 #include <math.h>
 #include "Recast.h"
+#include "NavMeshConversion.h"
 
 extern "C"{
 
@@ -36,399 +37,13 @@ extern "C"{
 #include "BKE_mesh.h"
 #include "BKE_modifier.h"
 #include "BKE_particle.h"
+#include "BKE_customdata.h"
 #include "MEM_guardedalloc.h"
 #include "BIF_gl.h"
 #include "gpu_buffers.h"
 #include "GPU_draw.h"
 #include "UI_resources.h"
 
-//service function
-inline int abs(int a)
-{
-	return a>=0 ? a: -a;
-}
-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;
-}
-
-inline float area2(const float* a, const float* b, const float* c)
-{
-	return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]);
-}
-inline bool left(const float* a, const float* b, const float* c)
-{
-	return area2(a, b, c) < 0;
-}
-
-inline int polyNumVerts(const unsigned short* p, const int vertsPerPoly)
-{
-	int nv = 0;
-	for (int i=0; i<vertsPerPoly; i++)
-	{
-		if (p[i]==0xffff)
-			break;
-		nv++;
-	}
-	return nv;
-}
-
-inline bool polyIsConvex(const unsigned short* p, const int vertsPerPoly, const float* verts)
-{
-	int nv = polyNumVerts(p, vertsPerPoly);
-	if (nv<3)
-		return false;
-	for (int j=0; j<nv; j++)
-	{
-		const float* v = &verts[3*p[j]];
-		const float* v_next = &verts[3*p[(j+1)%nv]];
-		const float* v_prev = &verts[3*p[(nv+j-1)%nv]];
-		if (!left(v_prev, v, v_next))
-			return false;
-
-	}
-	return true;
-}
-
-static float distPointToSegmentSq(const float* point, const float* a, const float* b)
-{
-	float abx[3], dx[3];
-	vsub(abx, b,a);
-	vsub(dx, point,a);
-	float d = abx[0]*abx[0]+abx[2]*abx[2];
-	float t = abx[0]*dx[0]+abx[2]*dx[2];
-	if (d > 0)
-		t /= d;
-	if (t < 0)
-		t = 0;
-	else if (t > 1)
-		t = 1;
-	dx[0] = a[0] + t*abx[0] - point[0];
-	dx[2] = a[2] + t*abx[2] - point[2];
-	return dx[0]*dx[0] + dx[2]*dx[2];
-}
-
-static bool buildRawVertIndicesData(DerivedMesh* dm, int &nverts, float *&verts, 
-									int &ntris, unsigned short *&tris, int *&trisToFacesMap,
-									int *&recastData)
-{
-	nverts = dm->getNumVerts(dm);
-	verts = new float[3*nverts];
-	dm->getVertCos(dm, (float(*)[3])verts);
-	
-	//flip coordinates
-	for (int vi=0; vi<nverts; vi++)
-	{
-		SWAP(float, verts[3*vi+1], verts[3*vi+2]);
-	}
-
-	//calculate number of tris
-	int nfaces = dm->getNumFaces(dm);
-	MFace *faces = dm->getFaceArray(dm);
-	ntris = nfaces;
-	for (int fi=0; fi<nfaces; fi++)
-	{
-		MFace* face = &faces[fi];
-		if (face->v4)
-			ntris++;
-	}
-
-	//copy and transform to triangles (reorder on the run)
-	trisToFacesMap = new int[ntris];
-	tris = new unsigned short[3*ntris];
-	unsigned short* tri = tris;
-	int triIdx = 0;
-	for (int fi=0; fi<nfaces; fi++)
-	{
-		MFace* face = &faces[fi];
-		tri[3*triIdx+0] = face->v1;
-		tri[3*triIdx+1] = face->v3;
-		tri[3*triIdx+2] = face->v2;
-		trisToFacesMap[triIdx++]=fi;
-		if (face->v4)
-		{
-			tri[3*triIdx+0] = face->v1;
-			tri[3*triIdx+1] = face->v4;
-			tri[3*triIdx+2] = face->v2;
-			trisToFacesMap[triIdx++]=fi;
-		}
-	}
-
-	//carefully, recast data is just reference to data in derived mesh
-	recastData = (int*)CustomData_get_layer(&dm->faceData, CD_PROP_INT);
-	return true;
-}
-
-static bool buildPolygonsByDetailedMeshes(const int vertsPerPoly, const int npolys, 
-										  unsigned short* polys, const unsigned short* dmeshes, 
-										  const float* verts, const unsigned short* dtris, 
-										  const int* dtrisToPolysMap)
-{
-	bool res = false;
-	int capacity = vertsPerPoly;
-	unsigned short* newPoly =  new unsigned short[capacity];
-	memset(newPoly, 0xff, sizeof(unsigned short)*capacity);
-	for (int polyidx=0; polyidx<npolys; polyidx++)
-	{
-		int nv = 0;
-		//search border 
-		int btri = -1;
-		int bedge = -1;
-		for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
-		{
-			int curpolytri = dmeshes[polyidx*4+2]+j;
-			for (int k=0; k<3; k++)
-			{
-				unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
-				if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
-				{
-					btri = curpolytri;
-					bedge = k;
-					break;
-				}
-			}							
-		}
-		if (btri==-1 || bedge==-1)
-		{
-			//can't find triangle with border edge
-			return false;
-		}
-
-		newPoly[nv++] = dtris[btri*3*2+bedge];
-
-		int tri = btri;
-		int edge = (bedge+1)%3;
-		while (tri!=btri || edge!=bedge)
-		{
-			int neighbortri = dtris[tri*3*2+3+edge];
-			if (neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
-			{
-				if (nv==capacity)
-				{
-					capacity += vertsPerPoly;
-					unsigned short* newPolyBig =  new unsigned short[capacity];
-					memset(newPolyBig, 0xff, sizeof(unsigned short)*capacity);
-					memcpy(newPolyBig, newPoly, sizeof(unsigned short)*nv);
-					delete newPoly;
-					newPoly = newPolyBig;			
-				}
-				newPoly[nv++] = dtris[tri*3*2+edge];
-				//move to next edge					
-				edge = (edge+1)%3;
-			}
-			else
-			{
-				//move to next tri
-				int twinedge = -1;
-				for (int k=0; k<3; k++)
-				{
-					if (dtris[neighbortri*3*2+3+k] == tri)
-					{
-						twinedge = k;
-						break;
-					}
-				}
-				if (twinedge==-1)
-				{
-					printf("Converting navmesh: Error! Can't find neighbor edge - invalid adjacency info\n");
-					goto returnLabel;					
-				}
-				tri = neighbortri;
-				edge = (twinedge+1)%3;
-			}
-		}
-
-		unsigned short* adjustedPoly = new unsigned short[nv];
-		int adjustedNv = 0;
-		for (size_t i=0; i<(size_t)nv; i++)
-		{
-			unsigned short prev = newPoly[(nv+i-1)%nv];
-			unsigned short cur = newPoly[i];
-			unsigned short next = newPoly[(i+1)%nv];
-			float distSq = distPointToSegmentSq(&verts[3*cur], &verts[3*prev], &verts[3*next]);
-			static const float tolerance = 0.001f;
-			if (distSq>tolerance)
-				adjustedPoly[adjustedNv++] = cur;
-		}
-		memcpy(newPoly, adjustedPoly, adjustedNv*sizeof(unsigned short));
-		delete adjustedPoly;
-		nv = adjustedNv;
-
-		if (nv<=vertsPerPoly)
-		{
-			for (int i=0; i<nv; i++)
-			{
-				polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
-			}
-		}
-		else
-		{
-			int a=0;
-		}
-	}
-	res = true;
-
-returnLabel:
-	delete newPoly;
-	return true;
-}
-
-struct SortContext
-{
-	const int* recastData;
-	const int* trisToFacesMap;
-};
-static int compareByData(void* data, const void * a, const void * b){
-	SortContext* context = (SortContext*)data;
-	return ( context->recastData[context->trisToFacesMap[*(int*)a]] - 
-				context->recastData[context->trisToFacesMap[*(int*)b]] );
-}
-
-static bool buildNavMeshData(const int nverts, const float* verts, 
-							const int ntris, const unsigned short *tris, 
-							const int* recastData, const int* trisToFacesMap,
-							int &ndtris, unsigned short *&dtris,
-							int &npolys, unsigned short *&dmeshes, unsigned short *&polys,
-							int &vertsPerPoly, int *&dtrisToPolysMap, int *&dtrisToTrisMap)
-
-{
-	if (!recastData)
-	{
-		printf("Converting navmesh: Error! Can't find recast custom data\n");
-		return false;
-	}
-
-	//sort the triangles by polygon idx
-	int* trisMapping = new int[ntris];
-	for (int i=0; i<ntris; i++)
-		trisMapping[i]=i;
-	SortContext context;
-	context.recastData = recastData;
-	context.trisToFacesMap = trisToFacesMap;
-	qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
-	
-	//search first valid triangle - triangle of convex polygon
-	int validTriStart = -1;
-	for (int i=0; i< ntris; i++)
-	{
-		if (recastData[trisToFacesMap[trisMapping[i]]]>0)
-		{
-			validTriStart = i;
-			break;
-		}
-	}
-
-	if (validTriStart<0)
-	{
-		printf("Converting navmesh: Error! No valid polygons in mesh\n");
-		delete trisMapping;
-		return false;
-	}
-
-	ndtris = ntris-validTriStart;
-	//fill dtris to faces mapping
-	dtrisToTrisMap = new int[ndtris];
-	memcpy(dtrisToTrisMap, &trisMapping[validTriStart], ndtris*sizeof(int));
-	delete trisMapping; trisMapping=NULL;
-
-	//create detailed mesh triangles  - copy only valid triangles
-	//and reserve memory for adjacency info
-	dtris = new unsigned short[3*2*ndtris];
-	memset(dtris, 0xffff, sizeof(unsigned short)*3*2*ndtris);
-	for (int i=0; i<ndtris; i++)
-	{
-		memcpy(dtris+3*2*i, tris+3*dtrisToTrisMap[i], sizeof(unsigned short)*3);
-	}
-	//create new recast data corresponded to dtris
-	dtrisToPolysMap = new int[ndtris];
-	for (int i=0; i<ndtris; i++)
-	{
-		dtrisToPolysMap[i] = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
-	}
-	
-	
-	//build adjacency info for detailed mesh triangles
-	buildMeshAdjacency(dtris, ntris, nverts, 3);
-
-	//create detailed mesh description for each navigation polygon
-	npolys = dtrisToPolysMap[ndtris-1];
-	dmeshes = new unsigned short[npolys*4];
-	memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
-	unsigned short *dmesh = NULL;
-	int prevpolyidx = 0;
-	for (int i=0; i<ndtris; i++)
-	{
-		int curpolyidx = dtrisToPolysMap[i];
-		if (curpolyidx!=prevpolyidx)
-		{
-			if (curpolyidx!=prevpolyidx+1)
-			{
-				printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
-				return false;
-			}
-			dmesh = dmesh==NULL ? dmeshes : dmesh+4;
-			dmesh[2] = i;	//tbase
-			dmesh[3] = 0;	//tnum
-			prevpolyidx = curpolyidx;
-		}
-		dmesh[3]++;
-	}
-
-	//create navigation polygons
-	vertsPerPoly = 6;
-	polys = new unsigned short[npolys*vertsPerPoly*2];
-	memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
-
-	buildPolygonsByDetailedMeshes(vertsPerPoly, npolys, polys, dmeshes, verts, dtris, dtrisToPolysMap);
-
-	return true;
-}
-
-
-static bool buildNavMeshDataByDerivedMesh(DerivedMesh *dm, int& vertsPerPoly, 
-											int &nverts, float *&verts,
-											int &ndtris, unsigned short *&dtris,
-											int& npolys, unsigned short *&dmeshes,
-											unsigned short*& polys, int *&dtrisToPolysMap,
-											int *&dtrisToTrisMap, int *&trisToFacesMap)
-{
-	bool res = true;
-	int ntris =0, *recastData=NULL;
-	unsigned short *tris=NULL;
-	res = buildRawVertIndicesData(dm, nverts, verts, ntris, tris, trisToFacesMap, recastData);
-	if (!res)
-	{
-		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
-		goto exit;
-	}
-
-	res = buildNavMeshData(nverts, verts, ntris, tris, recastData, trisToFacesMap,
-							ndtris, dtris, npolys, dmeshes,polys, vertsPerPoly, 
-							dtrisToPolysMap, dtrisToTrisMap);
-	if (!res)
-	{
-		printf("Converting navmesh: Error! Can't get vertices and indices from mesh\n");
-		goto exit;
-	}
-
-exit:
-	if (tris)
-		delete tris;
-
-	return res;
-}
-
-
 static void initData(ModifierData *md)
 {
 	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
diff --git a/source/gameengine/Ketsji/KX_NavMeshObject.cpp b/source/gameengine/Ketsji/KX_NavMeshObject.cpp
index 3d4dcb928a6..8ba2f78958b 100644
--- a/source/gameengine/Ketsji/KX_NavMeshObject.cpp
+++ b/source/gameengine/Ketsji/KX_NavMeshObject.cpp
@@ -43,6 +43,7 @@ extern "C" {
 #include "Value.h"
 #include "Recast.h"
 #include "DetourStatNavMeshBuilder.h"
+#include "NavMeshConversion.h"
 #include "KX_ObstacleSimulation.h"
 
 static const int MAX_PATH_LEN = 256;
@@ -69,25 +70,6 @@ inline void flipAxes(float* vec)
 {
 	std::swap(vec[1],vec[2]);
 }
-
-static float distPointToSegmentSq(const float* point, const float* a, const float* b)
-{
-	float abx[3], dx[3];
-	vsub(abx, b,a);
-	vsub(dx, point,a);
-	float d = abx[0]*abx[0]+abx[1]*abx[1];
-	float t = abx[0]*dx[0]+abx[1]*dx[1];
-	if (d > 0)
-		t /= d;
-	if (t < 0)
-		t = 0;
-	else if (t > 1)
-		t = 1;
-	dx[0] = a[0] + t*abx[0] - point[0];
-	dx[1] = a[1] + t*abx[1] - point[1];
-	return dx[0]*dx[0] + dx[1]*dx[1];
-}
-
 KX_NavMeshObject::KX_NavMeshObject(void* sgReplicationInfo, SG_Callbacks callbacks)
 :	KX_GameObject(sgReplicationInfo, callbacks)
 ,	m_navMesh(NULL)
@@ -130,253 +112,98 @@ bool KX_NavMeshObject::BuildVertIndArrays(float *&vertices, int& nverts,
 	int* recastData = (int*) dm->getFaceDataArray(dm, CD_PROP_INT);
 	if (recastData)
 	{
-		//create from blender mesh using recast data to build navigation 
-		//polygon mesh from detailed triangle mesh
-		MVert *mvert = dm->getVertArray(dm);
-		MFace *mface = dm->getFaceArray(dm);
-		int numfaces = dm->getNumFaces(dm);
-		int numverts = dm->getNumVerts(dm);
-
-		if (numfaces==0)
-		{
-			return true;
-		}
-
-		//build detailed mesh adjacency (with triangle reordering)
-		ndtris = numfaces;
-		dtris = new unsigned short[numfaces*3*2];
-		memset(dtris, 0xffff, sizeof(unsigned short)*3*2*numfaces);
-		for (int i=0; i<numfaces;i++)
-		{
-			MFace* mf = &mface[i];
-			dtris[i*3*2+0] = mf->v1;
-			dtris[i*3*2+1] = mf->v3;
-			dtris[i*3*2+2] = mf->v2;
-			
-		}
-		buildMeshAdjacency(dtris, numfaces, numverts, 3);
-
-
-		//assumption: detailed mesh triangles are sorted by polygon idx
-		npolys = recastData[numfaces-1]/* + 1*/; //stored indices start from 1
-		
-		dmeshes = new unsigned short[npolys*4];
-		memset(dmeshes, 0, npolys*4*sizeof(unsigned short));
-		unsigned short *dmesh = NULL;
-		int prevpolyidx = -1;
-		for (int i=0; i<numfaces; i++)
+		int *dtrisToPolysMap=NULL, *dtrisToTrisMap=NULL, *trisToFacesMap=NULL;
+		int nAllVerts = 0;
+		float *allVerts = NULL;
+		buildNavMeshDataByDerivedMesh(dm, vertsPerPoly, nAllVerts, allVerts, ndtris, dtris,
+			npolys, dmeshes, polys, dtrisToPolysMap, dtrisToTrisMap, trisToFacesMap);
+
+		unsigned short *verticesMap = new unsigned short[nAllVerts];
+		memset(verticesMap, 0xffff, sizeof(unsigned short)*nAllVerts);
+		int curIdx = 0;
+		//vertices - mesh verts
+		//iterate over all polys and create map for their vertices first...
+		for (int polyidx=0; polyidx<npolys; polyidx++)
 		{
-			int curpolyidx = recastData[i];
-			if (curpolyidx!=prevpolyidx)
+			unsigned short* poly = &polys[polyidx*vertsPerPoly*2];
+			for (int i=0; i<vertsPerPoly; i++)
 			{
-				if (curpolyidx!=prevpolyidx+1)
+				unsigned short idx = poly[i];
+				if (idx==0xffff)
+					break;
+				if (verticesMap[idx]==0xffff)
 				{
-					//error - wrong order of detailed mesh faces
-					printf("Converting navmesh: Error! Wrong order of detailed mesh faces\n");
-					return false;
+					verticesMap[idx] = curIdx++;
 				}
-				dmesh = dmesh==NULL ? dmeshes : dmesh+4;
-				dmesh[2] = i;	//tbase
-				dmesh[3] = 0;	//tnum
-				prevpolyidx = curpolyidx;
+				poly[i] = verticesMap[idx];
 			}
-			dmesh[3]++;
 		}
-
-		vertsPerPoly = 6;
-		polys = new unsigned short[npolys*vertsPerPoly*2];
-		memset(polys, 0xff, sizeof(unsigned short)*vertsPerPoly*2*npolys);
-		
-		int curpolytri = 0;
-		
+		nverts = curIdx;
+		//...then iterate over detailed meshes
+		//transform indices to local ones (for each navigation polygon)
 		for (int polyidx=0; polyidx<npolys; polyidx++)
 		{
-			vector<unsigned short> poly, tempPoly;
-			//search border 
-			int btri = -1;
-			int bedge = -1;
-			
-			for (int j=0; j<dmeshes[polyidx*4+3] && btri==-1;j++)
+			unsigned short *poly = &polys[polyidx*vertsPerPoly*2];
+			int nv = polyNumVerts(poly, vertsPerPoly);
+			unsigned short *dmesh = &dmeshes[4*polyidx];
+			unsigned short tribase = dmesh[2];
+			unsigned short trinum = dmesh[3];
+			unsigned short vbase = curIdx;
+			for (int j=0; j<trinum; j++)
 			{
-				int curpolytri = dmeshes[polyidx*4+2]+j;
+				unsigned short* dtri = &dtris[(tribase+j)*3*2];
 				for (int k=0; k<3; k++)
 				{
-					unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
-					if ( neighbortri==0xffff || recastData[neighbortri]!=polyidx)
+					int newVertexIdx = verticesMap[dtri[k]];
+					if (newVertexIdx==0xffff)
 					{
-						btri = curpolytri;
-						bedge = k;
-						break;
+						newVertexIdx = curIdx++;
+						verticesMap[dtri[k]] = newVertexIdx;
 					}
-				}							
-			}
-			if (btri==-1 || bedge==-1)
-			{
-				//can't find triangle with border edge
-				return false;
-			}
-
-			poly.push_back(dtris[btri*3*2+bedge]);
-			//poly.push_back(detailedpolys[btri*3*2+(bedge+1)%3]);
 
-			int tri = btri;
-			int edge = (bedge+1)%3;
-			while (tri!=btri || edge!=bedge)
-			{
-				int neighbortri = dtris[tri*3*2+3+edge];
-				if (neighbortri==0xffff || recastData[neighbortri]!=polyidx)
-				{
-					//add vertex to current edge
-					poly.push_back(dtris[tri*3*2+edge]);
-					//move to next edge					
-					edge = (edge+1)%3;
-				}
-				else
-				{
-					//move to next tri
-					int twinedge = -1;
-					for (int k=0; k<3; k++)
+					if (newVertexIdx<nverts)
 					{
-						if (dtris[neighbortri*3*2+3+k] == tri)
+						//it's polygon vertex ("shared")
+						int idxInPoly = polyFindVertex(poly, vertsPerPoly, newVertexIdx);
+						if (idxInPoly==-1)
 						{
-							twinedge = k;
-							break;
+							printf("Building NavMeshObject: Error! Can't find vertex in polygon\n");
+							return false;
 						}
+						dtri[k] = idxInPoly;
 					}
-					if (twinedge==-1)
+					else
 					{
-						//can't find neighbor edge - invalid adjacency info
-						return false;
+						dtri[k] = newVertexIdx - vbase + nv;
 					}
-					tri = neighbortri;
-					edge = (twinedge+1)%3;
 				}
 			}
-			
-			size_t nv = poly.size();
-			for (size_t i=0; i<nv; i++)
-			{
-				unsigned short prev = poly[(poly.size()+i-1)%nv];
-				unsigned short cur = poly[i];
-				unsigned short next = poly[(i+1)%nv];
-				float distSq = distPointToSegmentSq(mvert[cur].co, mvert[prev].co, mvert[next].co);
-				static const float tolerance = 0.001f;
-				if (distSq>tolerance)
-					tempPoly.push_back(cur);
-			}
-			poly = tempPoly;
-
-			if (poly.size()>vertsPerPoly)
-			{
-				printf("Error! Polygon size exceeds max verts count");
-				return false;
-			}
-
-			for (int i=0; i<poly.size(); i++)
-			{
-				polys[polyidx*vertsPerPoly*2+i] = poly[i];
-			}
+			dmesh[0] = vbase-nverts; //verts base
+			dmesh[1] = curIdx-vbase; //verts num
 		}
 
-		//assumption: vertices in mesh are stored in following order: 
-		//navigation mesh vertices - unique detailed mesh vertex
-		unsigned short  maxidx = 0;
-		for (int polyidx=0; polyidx<npolys; polyidx++)
-		{
-			for (int i=0; i<vertsPerPoly; i++)
-			{
-				unsigned short idx = polys[polyidx*vertsPerPoly*2+i];
-				if (idx==0xffff)
-					break;
-				if (idx>maxidx)
-					maxidx=idx;
-			}
-		}
-		
-		//create navigation mesh verts
-		nverts = maxidx+1;
 		vertices = new float[nverts*3];
-		for (int vi=0; vi<nverts; vi++)
-		{
-			MVert *v = &mvert[vi];
-			copy_v3_v3(&vertices[3*vi], v->co);
-		}
-		
-		//create unique detailed mesh verts
-		ndvertsuniq = numverts - nverts;
+		ndvertsuniq = curIdx - nverts;
 		if (ndvertsuniq>0)
 		{
 			dvertices = new float[ndvertsuniq*3];
-			for (int vi=0; vi<ndvertsuniq; vi++)
-			{
-				MVert *v = &mvert[nverts+vi];
-				copy_v3_v3(&dvertices[3*vi], v->co);
-			}
 		}
-
-		for (int polyIdx=0; polyIdx<npolys; polyIdx++)
+		for (int vi=0; vi<nAllVerts; vi++)
 		{
-			unsigned short *dmesh = &dmeshes[4*polyIdx];
-			unsigned short minvert = 0xffff, maxvert = 0;
-			for (int j=0; j<dmesh[3]; j++)
+			int newIdx = verticesMap[vi];
+			if (newIdx!=0xffff)
 			{
-				unsigned short* dtri = &dtris[(dmesh[2]+j)*3*2];
-				for (int k=0; k<3; k++)
+				if (newIdx<nverts)
 				{
-					if (dtri[k]<nverts)
-						continue;
-					minvert = std::min(minvert, dtri[k]);
-					maxvert = std::max(maxvert, dtri[k]);
+					//navigation mesh vertex
+					memcpy(vertices+3*newIdx, allVerts+3*vi, 3*sizeof(float));
 				}
-			}
-			dmesh[0] = minvert; //vbase
-			dmesh[1] = minvert != 0xffff ? maxvert - minvert + 1 : 0; //vnum
-		}
-
-		//recalculate detailed mesh indices (they must be local)
-		for (int polyIdx=0; polyIdx<npolys; polyIdx++)
-		{
-			unsigned short * poly = &polys[polyIdx*vertsPerPoly*2];
-			int nv=0;
-			for (int vi=0; vi<vertsPerPoly; vi++)
-			{
-				if (poly[vi]==0xffff)
-					break;
-				nv++;
-			}
-			unsigned short *dmesh = &dmeshes[4*polyIdx];
-			for (int j=0; j<dmesh[3]; j++)
-			{
-				unsigned short* dtri = &dtris[(dmesh[2]+j)*3*2];
-				for (int k=0; k<3; k++)
+				else
 				{
-					if (dtri[k]<nverts)
-					{
-						//shared vertex from polygon
-						unsigned short idx = 0xffff;
-						for (int vi=0; vi<nv; vi++)
-						{
-							if (poly[vi]==dtri[k])
-							{
-								idx = vi;
-								break;
-							}
-						}
-						if (idx==0xffff)
-						{
-							printf("Can't find vertex in navigation polygon");
-							return false;
-						}
-						dtri[k] = idx;
-					}
-					else
-					{
-						dtri[k] = dtri[k]-dmesh[0]+nv;
-					}
-				}
+					//detailed mesh vertex
+					memcpy(dvertices+3*(newIdx-nverts), allVerts+3*vi, 3*sizeof(float));
+				}				
 			}
-			if (dmesh[1]>0)
-				dmesh[0] -= nverts;
 		}
 	}
 	else
@@ -468,13 +295,16 @@ bool KX_NavMeshObject::BuildNavMesh()
 	}
 	
 	MT_Point3 pos;
-	for (int i=0; i<nverts; i++)
-	{
-		flipAxes(&vertices[i*3]);
-	}
-	for (int i=0; i<ndvertsuniq; i++)
+	if (dmeshes==NULL)
 	{
-		flipAxes(&dvertices[i*3]);
+		for (int i=0; i<nverts; i++)
+		{
+			flipAxes(&vertices[i*3]);
+		}
+		for (int i=0; i<ndvertsuniq; i++)
+		{
+			flipAxes(&dvertices[i*3]);
+		}
 	}
 
 	buildMeshAdjacency(polys, npolys, nverts, vertsPerPoly);