svn merge -r40075:40104 https://svn.blender.org/svnroot/bf-blender/trunk/blender

13 files changed, 1345 insertions, 91 deletions

diff --git a/source/blender/editors/include/ED_navmesh_conversion.h b/source/blender/editors/include/ED_navmesh_conversion.h
new file mode 100644
index 00000000000..71b60cc4e4a
--- /dev/null
+++ b/source/blender/editors/include/ED_navmesh_conversion.h
@@ -0,0 +1,96 @@
+/**
+* $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
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct DerivedMesh;
+
+/* navmesh_conversion.cpp */
+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 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;
+}
+
+#ifdef __cplusplus
+}
+#endif
+#endif //NAVMESH_CONVERSION_H
diff --git a/source/blender/editors/include/ED_object.h b/source/blender/editors/include/ED_object.h
index 2cda5e070d3..5a2a4765c74 100644
--- a/source/blender/editors/include/ED_object.h
+++ b/source/blender/editors/include/ED_object.h
@@ -139,8 +139,8 @@ void ED_setflagsLatt(struct Object *obedit, int flag);
 /* object_modifier.c */
 enum {
 	MODIFIER_APPLY_DATA=1,
-	MODIFIER_APPLY_SHAPE,
-} eModifier_Apply_Mode;
+	MODIFIER_APPLY_SHAPE
+};
 
 struct ModifierData *ED_object_modifier_add(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, const char *name, int type);
 int ED_object_modifier_remove(struct ReportList *reports, struct Main *bmain, struct Scene *scene, struct Object *ob, struct ModifierData *md);
diff --git a/source/blender/editors/interface/interface_widgets.c b/source/blender/editors/interface/interface_widgets.c
index c06e26eecaa..d9d75c34a94 100644
--- a/source/blender/editors/interface/interface_widgets.c
+++ b/source/blender/editors/interface/interface_widgets.c
@@ -79,10 +79,10 @@
 /* it has outline, back, and two optional tria meshes */
 
 typedef struct uiWidgetTrias {
-	int tot;
+	unsigned int tot;
 	
 	float vec[32][2];
-	int (*index)[3];
+	unsigned int (*index)[3];
 	
 } uiWidgetTrias;
 
@@ -146,7 +146,7 @@ static float jit[8][2]= {{0.468813 , -0.481430}, {-0.155755 , -0.352820},
 static float num_tria_vert[3][2]= { 
 {-0.352077, 0.532607}, {-0.352077, -0.549313}, {0.330000, -0.008353}};
 
-static int num_tria_face[1][3]= {
+static unsigned int num_tria_face[1][3]= {
 {0, 1, 2}};
 
 static float scroll_circle_vert[16][2]= {
@@ -155,7 +155,7 @@ static float scroll_circle_vert[16][2]= {
 {-0.382683, -0.923880}, {0.000000, -1.000000}, {0.382684, -0.923880}, {0.707107, -0.707107},
 {0.923880, -0.382684}, {1.000000, -0.000000}, {0.923880, 0.382683}, {0.707107, 0.707107}};
 
-static int scroll_circle_face[14][3]= {
+static unsigned int scroll_circle_face[14][3]= {
 {0, 1, 2}, {2, 0, 3}, {3, 0, 15}, {3, 15, 4}, {4, 15, 14}, {4, 14, 5}, {5, 14, 13}, {5, 13, 6}, 
 {6, 13, 12}, {6, 12, 7}, {7, 12, 11}, {7, 11, 8}, {8, 11, 10}, {8, 10, 9}};
 
@@ -163,13 +163,13 @@ static float menu_tria_vert[6][2]= {
 {-0.41, 0.16}, {0.41, 0.16}, {0, 0.82}, 
 {0, -0.82}, {-0.41, -0.16}, {0.41, -0.16}};
 
-static int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}};
+static unsigned int menu_tria_face[2][3]= {{2, 0, 1}, {3, 5, 4}};
 
 static float check_tria_vert[6][2]= {
 {-0.578579, 0.253369}, 	{-0.392773, 0.412794}, 	{-0.004241, -0.328551}, 
 {-0.003001, 0.034320}, 	{1.055313, 0.864744}, 	{0.866408, 1.026895}};
 
-static int check_tria_face[4][3]= {
+static unsigned int check_tria_face[4][3]= {
 {3, 2, 4}, {3, 4, 5}, {1, 0, 3}, {0, 2, 3}};
 
 GLubyte checker_stipple_sml[32*32/8] =
@@ -533,12 +533,9 @@ static void widget_scroll_circle(uiWidgetTrias *tria, rcti *rect, float triasize
 static void widget_trias_draw(uiWidgetTrias *tria)
 {
 	glEnableClientState(GL_VERTEX_ARRAY);
-	glEnableClientState(GL_INDEX_ARRAY);
-	glIndexPointer(GL_INT, 0, tria->index);
 	glVertexPointer(2, GL_FLOAT, 0, tria->vec);
-	glDrawArrays(GL_TRIANGLES, 0, tria->tot*3);
+	glDrawElements(GL_TRIANGLES, tria->tot*3, GL_UNSIGNED_INT, tria->index);
 	glDisableClientState(GL_VERTEX_ARRAY);
-	glDisableClientState(GL_INDEX_ARRAY);
 }
 
 static void widget_menu_trias(uiWidgetTrias *tria, rcti *rect)
diff --git a/source/blender/editors/object/CMakeLists.txt b/source/blender/editors/object/CMakeLists.txt
index 58496a914cb..27308bc9e07 100644
--- a/source/blender/editors/object/CMakeLists.txt
+++ b/source/blender/editors/object/CMakeLists.txt
@@ -34,6 +34,7 @@ set(INC
 	../../render/extern/include
 	../../windowmanager
 	../../../../intern/guardedalloc
+	../../../../extern/recastnavigation/Recast/Include
 )
 
 set(INC_SYS
@@ -59,8 +60,18 @@ set(SRC
 	object_intern.h
 )
 
+if(WITH_GAMEENGINE)
+	list(APPEND SRC
+		object_navmesh.cpp
+	)
+endif()
+
 if(WITH_PYTHON)
 	add_definitions(-DWITH_PYTHON)
 endif()
 
+if(WITH_GAMEENGINE)
+	add_definitions(-DWITH_GAMEENGINE)
+endif()
+
 blender_add_lib(bf_editor_object "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/editors/object/SConscript b/source/blender/editors/object/SConscript
index d3e7df92471..4607cc4b1bf 100644
--- a/source/blender/editors/object/SConscript
+++ b/source/blender/editors/object/SConscript
@@ -1,12 +1,13 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('*.c')
+sources = env.Glob('*.c') + env.Glob('*.cpp')
 
 incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf'
 incs += ' ../../windowmanager #/intern/guardedalloc ../../blenloader'
 incs += ' ../../makesrna ../../python ../../ikplugin ../../bmesh'
 incs += ' ../../render/extern/include ../../gpu' # for object_bake.c
+incs += ' #extern/recastnavigation/Recast/Include'
 
 defs = []
 
@@ -19,5 +20,8 @@ if env['OURPLATFORM'] in ('win32-vc', 'win32-mingw', 'linuxcross', 'win64-vc'):
 
 if env['WITH_BF_PYTHON']:
     defs.append('WITH_PYTHON')
+  
+if env['WITH_BF_GAMEENGINE']:
+    defs.append('WITH_GAMEENGINE')
 
 env.BlenderLib ( 'bf_editors_object', sources, Split(incs), defs, libtype=['core'], priority=[35] )
diff --git a/source/blender/editors/object/object_intern.h b/source/blender/editors/object/object_intern.h
index efcb618b868..44cf3adcd32 100644
--- a/source/blender/editors/object/object_intern.h
+++ b/source/blender/editors/object/object_intern.h
@@ -224,5 +224,10 @@ void OBJECT_OT_group_remove(struct wmOperatorType *ot);
 /* object_bake.c */
 void OBJECT_OT_bake_image(wmOperatorType *ot);
 
+/* object_navmesh.cpp */
+void OBJECT_OT_create_navmesh(struct wmOperatorType *ot);
+void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot);
+void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot);
+
 #endif /* ED_OBJECT_INTERN_H */
 
diff --git a/source/blender/editors/object/object_navmesh.cpp b/source/blender/editors/object/object_navmesh.cpp
new file mode 100644
index 00000000000..d0768d30236
--- /dev/null
+++ b/source/blender/editors/object/object_navmesh.cpp
@@ -0,0 +1,628 @@
+/**
+* $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) 2004 by Blender Foundation
+* All rights reserved.
+*
+* The Original Code is: all of this file.
+*
+* Contributor(s): none yet.
+*
+* ***** END GPL LICENSE BLOCK *****
+*/
+
+#include <math.h>
+#include "Recast.h"
+
+extern "C"
+{
+#include "MEM_guardedalloc.h"
+
+#include "DNA_scene_types.h"
+#include "DNA_object_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_ID.h"
+
+#include "BKE_library.h"
+#include "BKE_depsgraph.h"
+#include "BKE_context.h"
+#include "BKE_mesh.h"
+#include "BKE_modifier.h"
+#include "BKE_scene.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_cdderivedmesh.h"
+#include "BLI_editVert.h"
+#include "BLI_listbase.h"
+#include "BLI_utildefines.h"
+#include "ED_object.h"
+#include "BLI_math_vector.h"
+
+#include "RNA_access.h"
+
+#include "ED_mesh.h"
+
+/*mesh/mesh_intern.h */
+extern struct EditVert *addvertlist(EditMesh *em, float *vec, struct EditVert *example);
+extern struct EditFace *addfacelist(EditMesh *em, struct EditVert *v1, struct EditVert *v2, struct EditVert *v3, struct EditVert *v4, struct EditFace *example, struct EditFace *exampleEdges);
+extern void free_vertlist(EditMesh *em, ListBase *edve);
+extern void free_edgelist(EditMesh *em, ListBase *lb);
+extern void free_facelist(EditMesh *em, ListBase *lb);
+
+#include "WM_api.h"
+#include "WM_types.h"
+
+static void createVertsTrisData(bContext *C, LinkNode* obs, int& nverts, float*& verts, int &ntris, int*& tris)
+{
+	MVert *mvert;
+	int nfaces = 0, *tri, i, curnverts, basenverts, curnfaces;
+	MFace *mface;
+	float co[3], wco[3];
+	Object *ob;
+	LinkNode *oblink, *dmlink;
+	DerivedMesh *dm;
+	Scene* scene = CTX_data_scene(C);
+	LinkNode* dms = NULL;
+
+	nverts = 0;
+	ntris = 0;
+	//calculate number of verts and tris
+	for (oblink = obs; oblink; oblink = oblink->next) 
+	{
+		ob = (Object*) oblink->link;	
+		DerivedMesh *dm = mesh_create_derived_no_virtual(scene, ob, NULL, CD_MASK_MESH);
+		BLI_linklist_append(&dms, (void*)dm);
+
+		nverts += dm->getNumVerts(dm);
+		nfaces = dm->getNumFaces(dm);
+		ntris += nfaces;
+
+		//resolve quad faces
+		mface = dm->getFaceArray(dm);
+		for (i=0; i<nfaces; i++)
+		{
+			MFace* mf = &mface[i];
+			if (mf->v4)
+				ntris+=1;
+		}
+	}
+
+	//create data
+	verts = (float*) MEM_mallocN(sizeof(float)*3*nverts, "verts");
+	tris = (int*) MEM_mallocN(sizeof(int)*3*ntris, "faces");
+
+	basenverts = 0;
+	tri = tris;
+	for (oblink = obs, dmlink = dms; oblink && dmlink; 
+			oblink = oblink->next, dmlink = dmlink->next)
+	{
+		ob = (Object*) oblink->link;
+		dm = (DerivedMesh*) dmlink->link;
+
+		curnverts = dm->getNumVerts(dm);
+		mvert = dm->getVertArray(dm);
+		//copy verts	
+		for (i=0; i<curnverts; i++)
+		{
+			MVert *v = &mvert[i];
+			copy_v3_v3(co, v->co);
+			mul_v3_m4v3(wco, ob->obmat, co);
+			verts[3*(basenverts+i)+0] = wco[0];
+			verts[3*(basenverts+i)+1] = wco[2];
+			verts[3*(basenverts+i)+2] = wco[1];
+		}
+
+		//create tris
+		curnfaces = dm->getNumFaces(dm);
+		mface = dm->getFaceArray(dm);
+		for (i=0; i<curnfaces; i++)
+		{
+			MFace* mf = &mface[i]; 
+			tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v3;	tri[2]= basenverts + mf->v2; 
+			tri += 3;
+			if (mf->v4)
+			{
+				tri[0]= basenverts + mf->v1; tri[1]= basenverts + mf->v4; tri[2]= basenverts + mf->v3; 
+				tri += 3;
+			}
+		}
+		basenverts += curnverts;
+	}
+
+	//release derived mesh
+	for (dmlink = dms; dmlink; dmlink = dmlink->next)
+	{
+		dm = (DerivedMesh*) dmlink->link;
+		dm->release(dm);
+	}
+	BLI_linklist_free(dms, NULL);
+}
+
+static bool buildNavMesh(const RecastData& recastParams, int nverts, float* verts, int ntris, int* tris,
+								 rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh)
+{
+	float bmin[3], bmax[3];
+	rcHeightfield* solid;
+	unsigned char *triflags;
+	rcCompactHeightfield* chf;
+	rcContourSet *cset;
+
+	rcCalcBounds(verts, nverts, bmin, bmax);
+
+	//
+	// Step 1. Initialize build config.
+	//
+	rcConfig cfg;
+	memset(&cfg, 0, sizeof(cfg));
+	{
+/*
+		float cellsize = 0.3f;
+		float cellheight = 0.2f;
+		float agentmaxslope = M_PI/4;
+		float agentmaxclimb = 0.9f;
+		float agentheight = 2.0f;
+		float agentradius = 0.6f;
+		float edgemaxlen = 12.0f;
+		float edgemaxerror = 1.3f;
+		float regionminsize = 50.f;
+		float regionmergesize = 20.f;
+		int vertsperpoly = 6;
+		float detailsampledist = 6.0f;
+		float detailsamplemaxerror = 1.0f;
+		cfg.cs = cellsize;
+		cfg.ch = cellheight;
+		cfg.walkableSlopeAngle = agentmaxslope/M_PI*180.f;
+		cfg.walkableHeight = (int)ceilf(agentheight/ cfg.ch);
+		cfg.walkableClimb = (int)floorf(agentmaxclimb / cfg.ch);
+		cfg.walkableRadius = (int)ceilf(agentradius / cfg.cs);
+		cfg.maxEdgeLen = (int)(edgemaxlen/cellsize);
+		cfg.maxSimplificationError = edgemaxerror;
+		cfg.minRegionSize = (int)rcSqr(regionminsize);
+		cfg.mergeRegionSize = (int)rcSqr(regionmergesize);
+		cfg.maxVertsPerPoly = vertsperpoly;
+		cfg.detailSampleDist = detailsampledist< 0.9f ? 0 : cellsize * detailsampledist;
+		cfg.detailSampleMaxError = cellheight * detailsamplemaxerror;
+*/
+		cfg.cs = recastParams.cellsize;
+		cfg.ch = recastParams.cellheight;
+		cfg.walkableSlopeAngle = recastParams.agentmaxslope/((float)M_PI)*180.f;
+		cfg.walkableHeight = (int)ceilf(recastParams.agentheight/ cfg.ch);
+		cfg.walkableClimb = (int)floorf(recastParams.agentmaxclimb / cfg.ch);
+		cfg.walkableRadius = (int)ceilf(recastParams.agentradius / cfg.cs);
+		cfg.maxEdgeLen = (int)(recastParams.edgemaxlen/recastParams.cellsize);
+		cfg.maxSimplificationError = recastParams.edgemaxerror;
+		cfg.minRegionSize = (int)rcSqr(recastParams.regionminsize);
+		cfg.mergeRegionSize = (int)rcSqr(recastParams.regionmergesize);
+		cfg.maxVertsPerPoly = recastParams.vertsperpoly;
+		cfg.detailSampleDist = recastParams.detailsampledist< 0.9f ? 0 : 
+								recastParams.cellsize * recastParams.detailsampledist;
+		cfg.detailSampleMaxError = recastParams.cellheight * recastParams.detailsamplemaxerror;
+
+	}
+
+	// Set the area where the navigation will be build.
+	vcopy(cfg.bmin, bmin);
+	vcopy(cfg.bmax, bmax);
+	rcCalcGridSize(cfg.bmin, cfg.bmax, cfg.cs, &cfg.width, &cfg.height);
+
+	//
+	// Step 2. Rasterize input polygon soup.
+	//
+	// Allocate voxel heightfield where we rasterize our input data to.
+	solid = new rcHeightfield;
+	if (!solid)
+		return false;
+
+	if (!rcCreateHeightfield(*solid, cfg.width, cfg.height, cfg.bmin, cfg.bmax, cfg.cs, cfg.ch))
+		return false;
+
+	// Allocate array that can hold triangle flags.
+	triflags = (unsigned char*) MEM_mallocN(sizeof(unsigned char)*ntris, "triflags");
+	if (!triflags)
+		return false;
+	// Find triangles which are walkable based on their slope and rasterize them.
+	memset(triflags, 0, ntris*sizeof(unsigned char));
+	rcMarkWalkableTriangles(cfg.walkableSlopeAngle, verts, nverts, tris, ntris, triflags);
+	rcRasterizeTriangles(verts, nverts, tris, triflags, ntris, *solid);
+	MEM_freeN(triflags);
+	MEM_freeN(verts);
+	MEM_freeN(tris);
+
+	//
+	// Step 3. Filter walkables surfaces.
+	//
+	rcFilterLedgeSpans(cfg.walkableHeight, cfg.walkableClimb, *solid);
+	rcFilterWalkableLowHeightSpans(cfg.walkableHeight, *solid);
+
+	//
+	// Step 4. Partition walkable surface to simple regions.
+	//
+
+	chf = new rcCompactHeightfield;
+	if (!chf)
+		return false;
+	if (!rcBuildCompactHeightfield(cfg.walkableHeight, cfg.walkableClimb, RC_WALKABLE, *solid, *chf))
+		return false;
+
+	delete solid; 
+
+	// Prepare for region partitioning, by calculating distance field along the walkable surface.
+	if (!rcBuildDistanceField(*chf))
+		return false;
+
+	// Partition the walkable surface into simple regions without holes.
+	if (!rcBuildRegions(*chf, cfg.walkableRadius, cfg.borderSize, cfg.minRegionSize, cfg.mergeRegionSize))
+		return false;
+
+	//
+	// Step 5. Trace and simplify region contours.
+	//
+	// Create contours.
+	cset = new rcContourSet;
+	if (!cset)
+		return false;
+
+	if (!rcBuildContours(*chf, cfg.maxSimplificationError, cfg.maxEdgeLen, *cset))
+		return false;
+
+	//
+	// Step 6. Build polygons mesh from contours.
+	//
+	pmesh = new rcPolyMesh;
+	if (!pmesh)
+		return false;
+	if (!rcBuildPolyMesh(*cset, cfg.maxVertsPerPoly, *pmesh))
+		return false;
+
+
+	//
+	// Step 7. Create detail mesh which allows to access approximate height on each polygon.
+	//
+
+	dmesh = new rcPolyMeshDetail;
+	if (!dmesh)
+		return false;
+
+	if (!rcBuildPolyMeshDetail(*pmesh, *chf, cfg.detailSampleDist, cfg.detailSampleMaxError, *dmesh))
+		return false;
+
+	delete chf;
+	delete cset;
+
+	return true;
+}
+
+static Object* createRepresentation(bContext *C, rcPolyMesh*& pmesh, rcPolyMeshDetail*& dmesh, Base* base)
+{
+	float co[3], rot[3];
+	EditMesh *em;
+	int i,j, k;
+	unsigned short* v;
+	int face[3];
+	Main *bmain = CTX_data_main(C);
+	Scene *scene= CTX_data_scene(C);
+	Object* obedit;
+	int createob = base==NULL;
+	zero_v3(co);
+	zero_v3(rot);
+	if (createob)
+	{
+		//create new object
+		obedit = ED_object_add_type(C, OB_MESH, co, rot, FALSE, 1);
+	}
+	else
+	{
+		obedit = base->object;
+		scene_select_base(scene, base);
+		copy_v3_v3(obedit->loc, co);
+		copy_v3_v3(obedit->rot, rot);
+	}
+
+	ED_object_enter_editmode(C, EM_DO_UNDO|EM_IGNORE_LAYER);
+	em = BKE_mesh_get_editmesh(((Mesh *)obedit->data));
+
+	if (!createob)
+	{
+		//clear
+		if(em->verts.first) free_vertlist(em, &em->verts);
+		if(em->edges.first) free_edgelist(em, &em->edges);
+		if(em->faces.first) free_facelist(em, &em->faces);
+		if(em->selected.first) BLI_freelistN(&(em->selected));
+	}
+
+	//create verts for polygon mesh
+	for(i = 0; i < pmesh->nverts; i++) {
+		v = &pmesh->verts[3*i];
+		co[0] = pmesh->bmin[0] + v[0]*pmesh->cs;
+		co[1] = pmesh->bmin[1] + v[1]*pmesh->ch;
+		co[2] = pmesh->bmin[2] + v[2]*pmesh->cs;
+		SWAP(float, co[1], co[2]);
+		addvertlist(em, co, NULL);
+	}
+
+	//create custom data layer to save polygon idx
+	CustomData_add_layer_named(&em->fdata, CD_RECAST, CD_CALLOC, NULL, 0, "recastData");
+
+	//create verts and faces for detailed mesh
+	for (i=0; i<dmesh->nmeshes; i++)
+	{
+		int uniquevbase = em->totvert;
+		unsigned short vbase = dmesh->meshes[4*i+0];
+		unsigned short ndv = dmesh->meshes[4*i+1];
+		unsigned short tribase = dmesh->meshes[4*i+2];
+		unsigned short trinum = dmesh->meshes[4*i+3];
+		const unsigned short* p = &pmesh->polys[i*pmesh->nvp*2];
+		int nv = 0;
+		for (j = 0; j < pmesh->nvp; ++j)
+		{
+			if (p[j] == 0xffff) break;
+			nv++;
+		}
+		//create unique verts 
+		for (j=nv; j<ndv; j++)
+		{
+			copy_v3_v3(co, &dmesh->verts[3*(vbase + j)]);
+			SWAP(float, co[1], co[2]);
+			addvertlist(em, co, NULL);
+		}
+
+		EM_init_index_arrays(em, 1, 0, 0);
+		
+		//create faces
+		for (j=0; j<trinum; j++)
+		{
+			unsigned char* tri = &dmesh->tris[4*(tribase+j)];
+			EditFace* newFace;
+			for (k=0; k<3; k++)
+			{
+				if (tri[k]<nv)
+					face[k] = p[tri[k]]; //shared vertex
+				else
+					face[k] = uniquevbase+tri[k]-nv; //unique vertex
+			}
+			newFace = addfacelist(em, EM_get_vert_for_index(face[0]), EM_get_vert_for_index(face[2]), 
+									EM_get_vert_for_index(face[1]), NULL, NULL, NULL);
+
+			//set navigation polygon idx to the custom layer
+			int* polygonIdx = (int*)CustomData_em_get(&em->fdata, newFace->data, CD_RECAST);
+			*polygonIdx = i+1; //add 1 to avoid zero idx
+		}
+		
+		EM_free_index_arrays();
+	}
+
+	delete pmesh; pmesh = NULL;
+	delete dmesh; dmesh = NULL;
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+
+	ED_object_exit_editmode(C, EM_FREEDATA); 
+	WM_event_add_notifier(C, NC_OBJECT|ND_DRAW, obedit);
+
+	if (createob)
+	{
+		obedit->gameflag &= ~OB_COLLISION;
+		obedit->gameflag |= OB_NAVMESH;
+		obedit->body_type = OB_BODY_TYPE_NAVMESH;
+		rename_id((ID *)obedit, "Navmesh");
+	}
+	
+	ModifierData *md= modifiers_findByType(obedit, eModifierType_NavMesh);
+	if (!md)
+	{
+		ED_object_modifier_add(NULL, bmain, scene, obedit, NULL, eModifierType_NavMesh);
+	}
+
+	return obedit;
+}
+
+static int create_navmesh_exec(bContext *C, wmOperator *op)
+{
+	Scene* scene = CTX_data_scene(C);
+	int nverts, ntris;
+	float* verts;
+	int* tris;
+	rcPolyMesh* pmesh;
+	rcPolyMeshDetail* dmesh;
+	LinkNode* obs = NULL;
+	Base* navmeshBase = NULL;
+	//CTX_DATA_BEGIN(C, Base*, base, selected_editable_bases) //expand macros to avoid error in convertion from void*
+	{
+		ListBase ctx_data_list;
+		CollectionPointerLink *ctx_link;
+		CTX_data_selected_editable_bases(C, &ctx_data_list);
+		for(ctx_link = (CollectionPointerLink *)ctx_data_list.first; 
+				ctx_link; ctx_link = (CollectionPointerLink *)ctx_link->next) {
+		Base* base= (Base*)ctx_link->ptr.data;
+	{
+		if (base->object->body_type==OB_BODY_TYPE_NAVMESH)
+		{
+			if (!navmeshBase || base==CTX_data_active_base(C))
+				navmeshBase = base;
+		}
+		else
+			BLI_linklist_append(&obs, (void*)base->object);
+	}
+	CTX_DATA_END;
+	createVertsTrisData(C, obs, nverts, verts, ntris, tris);
+	BLI_linklist_free(obs, NULL);
+	buildNavMesh(scene->gm.recastData, nverts, verts, ntris, tris, pmesh, dmesh);
+	createRepresentation(C, pmesh, dmesh, navmeshBase);
+
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_create_navmesh(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Create navigation mesh";
+	ot->description= "Create navigation mesh for selected objects";
+	ot->idname= "OBJECT_OT_create_navmesh";
+
+	/* api callbacks */
+	ot->exec= create_navmesh_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+
+static int assign_navpolygon_poll(bContext *C)
+{
+	Object *ob= (Object *)CTX_data_pointer_get_type(C, "object", &RNA_Object).data;
+	if (!ob || !ob->data)
+		return 0;
+	return (((Mesh*)ob->data)->edit_mesh != NULL);
+}
+
+static int assign_navpolygon_exec(bContext *C, wmOperator *op)
+{
+	Object *obedit= CTX_data_edit_object(C);
+	EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
+
+	//do work here
+	int targetPolyIdx = -1;
+	EditFace *ef, *efa;
+	efa = EM_get_actFace(em, 0);
+	if (efa) 
+	{
+		if (CustomData_has_layer(&em->fdata, CD_RECAST))
+		{
+			targetPolyIdx = *(int*)CustomData_em_get(&em->fdata, efa->data, CD_RECAST);
+			targetPolyIdx = targetPolyIdx>=0? targetPolyIdx : -targetPolyIdx;
+			if (targetPolyIdx>0)
+			{
+				//set target poly idx to other selected faces
+				ef = (EditFace*)em->faces.last;
+				while(ef) 
+				{
+					if((ef->f & SELECT )&& ef!=efa) 
+					{
+						int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+						*recastDataBlock = targetPolyIdx;
+					}
+					ef = ef->prev;
+				}
+			}
+		}		
+	}
+	
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_assign_navpolygon(struct wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Assign polygon index";
+	ot->description= "Assign polygon index to face by active face";
+	ot->idname= "OBJECT_OT_assign_navpolygon";
+
+	/* api callbacks */
+	ot->poll = assign_navpolygon_poll;
+	ot->exec= assign_navpolygon_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+
+static int compare(const void * a, const void * b){  
+	return ( *(int*)a - *(int*)b );
+}
+static int findFreeNavPolyIndex(EditMesh* em)
+{
+	//construct vector of indices
+	int numfaces = em->totface;
+	int* indices = new int[numfaces];
+	EditFace* ef = (EditFace*)em->faces.last;
+	int idx = 0;
+	while(ef) 
+	{
+		int polyIdx = *(int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+		indices[idx] = polyIdx;
+		idx++;
+		ef = ef->prev;
+	}
+	qsort(indices, numfaces, sizeof(int), compare);
+	//search first free index
+	int freeIdx = 1;
+	for (int i=0; i<numfaces; i++)
+	{
+		if (indices[i]==freeIdx)
+			freeIdx++;
+		else if (indices[i]>freeIdx)
+			break;
+	}
+	delete indices;
+	return freeIdx;
+}
+
+static int assign_new_navpolygon_exec(bContext *C, wmOperator *op)
+{
+	Object *obedit= CTX_data_edit_object(C);
+	EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
+
+	EditFace *ef;
+	if (CustomData_has_layer(&em->fdata, CD_RECAST))
+	{
+		int targetPolyIdx = findFreeNavPolyIndex(em);
+		if (targetPolyIdx>0)
+		{
+			//set target poly idx to selected faces
+			ef = (EditFace*)em->faces.last;
+			while(ef) 
+			{
+				if(ef->f & SELECT ) 
+				{
+					int* recastDataBlock = (int*)CustomData_em_get(&em->fdata, ef->data, CD_RECAST);
+					*recastDataBlock = targetPolyIdx;
+				}
+				ef = ef->prev;
+			}
+		}
+	}		
+
+	DAG_id_tag_update((ID*)obedit->data, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
+
+	BKE_mesh_end_editmesh((Mesh*)obedit->data, em);
+	return OPERATOR_FINISHED;
+}
+
+void OBJECT_OT_assign_new_navpolygon(struct wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name= "Assign new polygon index";
+	ot->description= "Assign new polygon index to face";
+	ot->idname= "OBJECT_OT_assign_new_navpolygon";
+
+	/* api callbacks */
+	ot->poll = assign_navpolygon_poll;
+	ot->exec= assign_new_navpolygon_exec;
+
+	/* flags */
+	ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
+}
+}
diff --git a/source/blender/editors/object/object_ops.c b/source/blender/editors/object/object_ops.c
index 11d64882f29..7cfc7618415 100644
--- a/source/blender/editors/object/object_ops.c
+++ b/source/blender/editors/object/object_ops.c
@@ -215,6 +215,11 @@ void ED_operatortypes_object(void)
 
 	WM_operatortype_append(OBJECT_OT_test_multires);
 
+#ifdef WITH_GAMEENGINE
+	WM_operatortype_append(OBJECT_OT_create_navmesh);
+	WM_operatortype_append(OBJECT_OT_assign_navpolygon);
+	WM_operatortype_append(OBJECT_OT_assign_new_navpolygon);
+#endif
 }
 
 void ED_operatormacros_object(void)
diff --git a/source/blender/editors/space_logic/logic_window.c b/source/blender/editors/space_logic/logic_window.c
index 20b001965aa..43a8747e942 100644
--- a/source/blender/editors/space_logic/logic_window.c
+++ b/source/blender/editors/space_logic/logic_window.c
@@ -718,6 +718,8 @@ static const char *actuator_name(int type)
 		return "State";
 	case ACT_ARMATURE:
 		return "Armature";
+	case ACT_STEERING:
+		return "Steering";		
 	}
 	return "unknown";
 }
@@ -4345,6 +4347,48 @@ static void draw_actuator_visibility(uiLayout *layout, PointerRNA *ptr)
 	uiItemR(row, ptr, "apply_to_children", 0, NULL, ICON_NONE);
 }
 
+static void draw_actuator_steering(uiLayout *layout, PointerRNA *ptr)
+{
+	uiLayout *row;
+	uiLayout *col;
+
+	uiItemR(layout, ptr, "mode", 0, NULL, 0);
+	uiItemR(layout, ptr, "target", 0, NULL, 0);
+	uiItemR(layout, ptr, "navmesh", 0, NULL, 0);	
+
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "distance", 0, NULL, 0);
+	uiItemR(row, ptr, "velocity", 0, NULL, 0);
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "acceleration", 0, NULL, 0);
+	uiItemR(row, ptr, "turn_speed", 0, NULL, 0);
+
+	row = uiLayoutRow(layout, 0);
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "facing", 0, NULL, 0);
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "facing_axis", 0, NULL, 0);
+	if (!RNA_boolean_get(ptr, "facing"))
+	{
+		uiLayoutSetActive(col, 0);
+	}
+	col = uiLayoutColumn(row, 0);
+	uiItemR(col, ptr, "normal_up", 0, NULL, 0);
+	if (!RNA_pointer_get(ptr, "navmesh").data)
+	{
+		uiLayoutSetActive(col, 0);
+	}
+
+	row = uiLayoutRow(layout, 0);
+	uiItemR(row, ptr, "self_terminated", 0, NULL, 0);
+	if (RNA_enum_get(ptr, "mode")==ACT_STEERING_PATHFOLLOWING)
+	{
+		uiItemR(row, ptr, "update_period", 0, NULL, 0);	
+		row = uiLayoutRow(layout, 0);
+	}
+	uiItemR(row, ptr, "show_visualization", 0, NULL, 0);	
+}
+
 static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C)
 {
 	uiLayout *box;
@@ -4406,6 +4450,8 @@ static void draw_brick_actuator(uiLayout *layout, PointerRNA *ptr, bContext *C)
 		case ACT_VISIBILITY:
 			draw_actuator_visibility(box, ptr);
 			break;
+		case ACT_STEERING:
+			draw_actuator_steering(box, ptr);
 	}
 }
 
diff --git a/source/blender/editors/space_view3d/drawarmature.c b/source/blender/editors/space_view3d/drawarmature.c
index ecf5df4af7c..4aec1a8e61c 100644
--- a/source/blender/editors/space_view3d/drawarmature.c
+++ b/source/blender/editors/space_view3d/drawarmature.c
@@ -85,7 +85,7 @@ enum {
 	PCHAN_COLOR_SPHEREBONE_BASE,	/* for the 'stick' of sphere (envelope) bones */
 	PCHAN_COLOR_SPHEREBONE_END,		/* for the ends of sphere (envelope) bones */
 	PCHAN_COLOR_LINEBONE			/* for the middle of line-bones */
-};	
+};
 
 /* This function sets the color-set for coloring a certain bone */
 static void set_pchan_colorset (Object *ob, bPoseChannel *pchan)
@@ -437,43 +437,64 @@ static void draw_bonevert_solid(void)
 	glCallList(displist);
 }
 
+static float bone_octahedral_verts[6][3]= {
+    { 0.0f, 0.0f,  0.0f},
+    { 0.1f, 0.1f,  0.1f},
+    { 0.1f, 0.1f, -0.1f},
+    {-0.1f, 0.1f, -0.1f},
+    {-0.1f, 0.1f,  0.1f},
+    { 0.0f, 1.0f,  0.0f}
+};
+
+static unsigned int bone_octahedral_wire_sides[8]= {0, 1, 5, 3, 0, 4, 5, 2};
+static unsigned int bone_octahedral_wire_square[8]= {1, 2, 3, 4, 1};
+
+static unsigned int bone_octahedral_solid_tris[8][3]= {
+    {2, 1, 0}, /* bottom */
+    {3, 2, 0},
+    {4, 3, 0},
+    {1, 4, 0},
+
+    {5, 1, 2}, /* top */
+    {5, 2, 3},
+    {5, 3, 4},
+    {5, 4, 1}
+};
+
+/* aligned with bone_octahedral_solid_tris */
+static float bone_octahedral_solid_normals[8][3]= {
+    { 0.70710683f, -0.70710683f,  0.00000000f},
+    {-0.00000000f, -0.70710683f, -0.70710683f},
+    {-0.70710683f, -0.70710683f,  0.00000000f},
+    { 0.00000000f, -0.70710683f,  0.70710683f},
+    { 0.99388373f,  0.11043154f, -0.00000000f},
+    { 0.00000000f,  0.11043154f, -0.99388373f},
+    {-0.99388373f,  0.11043154f,  0.00000000f},
+    { 0.00000000f,  0.11043154f,  0.99388373f}
+};
+
 static void draw_bone_octahedral(void)
 {
 	static GLuint displist=0;
 	
 	if (displist == 0) {
-		float vec[6][3];	
-		
 		displist= glGenLists(1);
 		glNewList(displist, GL_COMPILE);
-		
-		vec[0][0]= vec[0][1]= vec[0][2]= 0.0f;
-		vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f;
-		
-		vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f;
-		vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f;
-		vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f;
-		vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f;
-		
+
 		/*	Section 1, sides */
-		glBegin(GL_LINE_LOOP);
-		glVertex3fv(vec[0]);
-		glVertex3fv(vec[1]);
-		glVertex3fv(vec[5]);
-		glVertex3fv(vec[3]);
-		glVertex3fv(vec[0]);
-		glVertex3fv(vec[4]);
-		glVertex3fv(vec[5]);
-		glVertex3fv(vec[2]);
-		glEnd();
-		
+		glEnableClientState(GL_VERTEX_ARRAY);
+		glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts);
+		glDrawElements(GL_LINE_LOOP,
+		               sizeof(bone_octahedral_wire_sides)/sizeof(*bone_octahedral_wire_sides),
+		               GL_UNSIGNED_INT,
+		               bone_octahedral_wire_sides);
+
 		/*	Section 1, square */
-		glBegin(GL_LINE_LOOP);
-		glVertex3fv(vec[1]);
-		glVertex3fv(vec[2]);
-		glVertex3fv(vec[3]);
-		glVertex3fv(vec[4]);
-		glEnd();
+		glDrawElements(GL_LINE_LOOP,
+		               sizeof(bone_octahedral_wire_square)/sizeof(*bone_octahedral_wire_square),
+		               GL_UNSIGNED_INT,
+		               bone_octahedral_wire_square);
+		glDisableClientState(GL_VERTEX_ARRAY);
 		
 		glEndList();
 	}
@@ -484,59 +505,34 @@ static void draw_bone_octahedral(void)
 static void draw_bone_solid_octahedral(void)
 {
 	static GLuint displist=0;
-	
+
 	if (displist == 0) {
-		float vec[6][3], nor[3];	
-		
+		int i;
+
 		displist= glGenLists(1);
 		glNewList(displist, GL_COMPILE);
-		
-		vec[0][0]= vec[0][1]= vec[0][2]= 0.0f;
-		vec[5][0]= vec[5][2]= 0.0f; vec[5][1]= 1.0f;
-		
-		vec[1][0]= 0.1f; vec[1][2]= 0.1f; vec[1][1]= 0.1f;
-		vec[2][0]= 0.1f; vec[2][2]= -0.1f; vec[2][1]= 0.1f;
-		vec[3][0]= -0.1f; vec[3][2]= -0.1f; vec[3][1]= 0.1f;
-		vec[4][0]= -0.1f; vec[4][2]= 0.1f; vec[4][1]= 0.1f;
-		
-		
-		glBegin(GL_TRIANGLES);
-		/* bottom */
-		normal_tri_v3( nor,vec[2], vec[1], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[2]); glVertex3fv(vec[1]); glVertex3fv(vec[0]);
-		
-		normal_tri_v3( nor,vec[3], vec[2], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[3]); glVertex3fv(vec[2]); glVertex3fv(vec[0]);
-		
-		normal_tri_v3( nor,vec[4], vec[3], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[4]); glVertex3fv(vec[3]); glVertex3fv(vec[0]);
 
-		normal_tri_v3( nor,vec[1], vec[4], vec[0]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[1]); glVertex3fv(vec[4]); glVertex3fv(vec[0]);
+#if 1
+		glBegin(GL_TRIANGLES);
+		for(i= 0; i < 8; i++) {
+			glNormal3fv(bone_octahedral_solid_normals[i]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][0]]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][1]]);
+			glVertex3fv(bone_octahedral_verts[bone_octahedral_solid_tris[i][2]]);
+		}
 
-		/* top */
-		normal_tri_v3( nor,vec[5], vec[1], vec[2]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[1]); glVertex3fv(vec[2]);
-		
-		normal_tri_v3( nor,vec[5], vec[2], vec[3]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[2]); glVertex3fv(vec[3]);
-		
-		normal_tri_v3( nor,vec[5], vec[3], vec[4]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[3]); glVertex3fv(vec[4]);
-		
-		normal_tri_v3( nor,vec[5], vec[4], vec[1]);
-		glNormal3fv(nor);
-		glVertex3fv(vec[5]); glVertex3fv(vec[4]); glVertex3fv(vec[1]);
-		
 		glEnd();
-		
+
+#else	/* not working because each vert needs a different normal */
+		glEnableClientState(GL_NORMAL_ARRAY);
+		glEnableClientState(GL_VERTEX_ARRAY);
+		glNormalPointer(GL_FLOAT, 0, bone_octahedral_solid_normals);
+		glVertexPointer(3, GL_FLOAT, 0, bone_octahedral_verts);
+		glDrawElements(GL_TRIANGLES, sizeof(bone_octahedral_solid_tris)/sizeof(unsigned int), GL_UNSIGNED_INT, bone_octahedral_solid_tris);
+		glDisableClientState(GL_NORMAL_ARRAY);
+		glDisableClientState(GL_VERTEX_ARRAY);
+#endif
+
 		glEndList();
 	}
 
diff --git a/source/blender/editors/util/CMakeLists.txt b/source/blender/editors/util/CMakeLists.txt
index 843af272362..c1e618fd4cb 100644
--- a/source/blender/editors/util/CMakeLists.txt
+++ b/source/blender/editors/util/CMakeLists.txt
@@ -24,6 +24,7 @@ set(INC
 	../../blenkernel
 	../../blenlib
 	../../blenloader
+	../../../../extern/recastnavigation/Recast/Include
 	../../bmesh
 	../../makesdna
 	../../makesrna
@@ -63,6 +64,7 @@ set(SRC
 	../include/ED_markers.h
 	../include/ED_mball.h
 	../include/ED_mesh.h
+	../include/ED_navmesh_conversion.h
 	../include/ED_node.h
 	../include/ED_numinput.h
 	../include/ED_object.h
@@ -89,4 +91,10 @@ set(SRC
 	../include/UI_view2d.h
 )
 
+if(WITH_GAMEENGINE)
+	list(APPEND SRC
+		navmesh_conversion.cpp
+	)
+endif()
+
 blender_add_lib(bf_editor_util "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/editors/util/SConscript b/source/blender/editors/util/SConscript
index 2d5ee84333b..04d783e1ee1 100644
--- a/source/blender/editors/util/SConscript
+++ b/source/blender/editors/util/SConscript
@@ -1,11 +1,15 @@
 #!/usr/bin/python
 Import ('env')
 
-sources = env.Glob('*.c')
+sources = env.Glob('*.c') + env.Glob('*.cpp')
 
 incs = '../include ../../blenlib ../../blenkernel ../../makesdna ../../imbuf'
 incs += ' ../../windowmanager #/intern/guardedalloc #/extern/glew/include'
 incs += ' ../../makesrna ../../bmesh'
+incs += ' #extern/recastnavigation/Recast/Include'
 incs += ' ../../blenloader'
 
-env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core'], priority=[130] )
+if not env['WITH_BF_GAMEENGINE']:
+    sources.remove('navmesh_conversion.cpp')
+
+env.BlenderLib ( 'bf_editors_util', sources, Split(incs), [], libtype=['core','player'], priority=[330,210] )
diff --git a/source/blender/editors/util/navmesh_conversion.cpp b/source/blender/editors/util/navmesh_conversion.cpp
new file mode 100644
index 00000000000..8b3fee59e1a
--- /dev/null
+++ b/source/blender/editors/util/navmesh_conversion.cpp
@@ -0,0 +1,454 @@
+/**
+* $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 <math.h>
+#include "Recast.h"
+
+
+extern "C"{
+#include "ED_navmesh_conversion.h"
+
+#include "DNA_meshdata_types.h"
+#include "BKE_cdderivedmesh.h"
+#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);
+	if (nverts>=0xffff)
+	{
+		printf("Converting navmesh: Error! Too many vertices. Max number of vertices %d\n", 0xffff);
+		return false;
+	}
+	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] = (unsigned short) face->v1;
+		tri[3*triIdx+1] = (unsigned short) face->v3;
+		tri[3*triIdx+2] = (unsigned short) face->v2;
+		trisToFacesMap[triIdx++]=fi;
+		if (face->v4)
+		{
+			tri[3*triIdx+0] = (unsigned short) face->v1;
+			tri[3*triIdx+1] = (unsigned short) face->v4;
+			tri[3*triIdx+2] = (unsigned short) face->v3;
+			trisToFacesMap[triIdx++]=fi;
+		}
+	}
+
+	//carefully, recast data is just reference to data in derived mesh
+	recastData = (int*)CustomData_get_layer(&dm->faceData, CD_RECAST);
+	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)
+{
+	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;
+		int dtrisNum = dmeshes[polyidx*4+3];
+		int dtrisBase = dmeshes[polyidx*4+2];
+		unsigned char *traversedTris = new unsigned char[dtrisNum];
+		memset(traversedTris, 0, dtrisNum*sizeof(unsigned char));
+		for (int j=0; j<dtrisNum && btri==-1;j++)
+		{
+			int curpolytri = dtrisBase+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;
+		traversedTris[tri-dtrisBase] = 1;
+		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;
+				traversedTris[tri-dtrisBase] = 1;
+			}
+		}
+
+		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;
+
+		bool allBorderTraversed = true;
+		for (size_t i=0; i<(size_t)dtrisNum; i++)
+		{
+			if (traversedTris[i]==0)
+			{
+				//check whether it has border edges
+				int curpolytri = dtrisBase+i;
+				for (int k=0; k<3; k++)
+				{
+					unsigned short neighbortri = dtris[curpolytri*3*2+3+k];
+					if ( neighbortri==0xffff || dtrisToPolysMap[neighbortri]!=polyidx+1)
+					{
+						allBorderTraversed = false;
+						break;
+					}
+				}
+			}				
+		}
+
+		if (nv<=vertsPerPoly && allBorderTraversed)
+		{
+			for (int i=0; i<nv; i++)
+			{
+				polys[polyidx*vertsPerPoly*2+i] = newPoly[i];
+			}
+		}
+	}
+
+returnLabel:
+	delete newPoly;
+	return true;
+}
+
+struct SortContext
+{
+	const int* recastData;
+	const int* trisToFacesMap;
+};
+#if defined(_MSC_VER)
+static int compareByData(void* data, const void * a, const void * b)
+#elif defined(__APPLE__) || defined(__FreeBSD__)
+static int compareByData(void* data, const void * a, const void * b)
+#else
+static int compareByData(const void * a, const void * b, void* data)
+#endif
+{
+	const SortContext* context = (const 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;
+#if defined(_MSC_VER)
+	qsort_s(trisMapping, ntris, sizeof(int), compareByData, &context);
+#elif defined(__APPLE__) || defined(__FreeBSD__)
+	qsort_r(trisMapping, ntris, sizeof(int), &context, compareByData);
+#else
+	qsort_r(trisMapping, ntris, sizeof(int), compareByData, &context);
+#endif
+	//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 and renumber for continuous indices
+	int prevPolyIdx=-1, curPolyIdx, newPolyIdx=0;
+	dtrisToPolysMap = new int[ndtris];
+	for (int i=0; i<ndtris; i++)
+	{
+		curPolyIdx = recastData[trisToFacesMap[dtrisToTrisMap[i]]];
+		if (curPolyIdx!=prevPolyIdx)
+		{
+			newPolyIdx++;
+			prevPolyIdx=curPolyIdx;
+		}
+		dtrisToPolysMap[i] = newPolyIdx;
+	}
+
+
+	//build adjacency info for detailed mesh triangles
+	buildMeshAdjacency(dtris, ndtris, 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] = (unsigned short)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;
+}