- added new modifier to create navigation mesh (it's empty now)

- added parameters for navmesh modifier

5 files changed, 303 insertions, 0 deletions

diff --git a/source/blender/makesdna/DNA_modifier_types.h b/source/blender/makesdna/DNA_modifier_types.h
index 51f23ef210f..23d95c3f273 100644
--- a/source/blender/makesdna/DNA_modifier_types.h
+++ b/source/blender/makesdna/DNA_modifier_types.h
@@ -66,6 +66,7 @@ typedef enum ModifierType {
 	eModifierType_ShapeKey,
 	eModifierType_Solidify,
 	eModifierType_Screw,
+	eModifierType_NavMesh,
 	NUM_MODIFIER_TYPES
 } ModifierType;
 
@@ -336,6 +337,7 @@ typedef struct DecimateModifierData {
 	int faceCount;
 } DecimateModifierData;
 
+
 /* Smooth modifier flags */
 #define MOD_SMOOTH_X (1<<1)
 #define MOD_SMOOTH_Y (1<<2)
@@ -722,4 +724,23 @@ typedef struct ScrewModifierData {
 // #define MOD_SCREW_OBJECT_ANGLE	(1<<4)
 
 
+typedef struct NavMeshModifierData {
+	ModifierData modifier;
+	char pad[4];
+	float cellsize;
+	float cellheight;
+	float agentmaxslope;
+	float agentmaxclimb;
+	float agentheight;
+	float agentradius;
+	float edgemaxlen;
+	float edgemaxerror;
+	float regionminsize;
+	float regionmergesize;
+	int vertsperpoly;
+	float detailsampledist;
+	float detailsamplemaxerror;
+
+} NavMeshModifierData;
+
 #endif
diff --git a/source/blender/makesrna/intern/rna_modifier.c b/source/blender/makesrna/intern/rna_modifier.c
index d2bf791fb67..b08432c4315 100644
--- a/source/blender/makesrna/intern/rna_modifier.c
+++ b/source/blender/makesrna/intern/rna_modifier.c
@@ -60,6 +60,7 @@ EnumPropertyItem modifier_type_items[] ={
 	{eModifierType_Solidify, "SOLIDIFY", ICON_MOD_SOLIDIFY, "Solidify", ""},
 	{eModifierType_Subsurf, "SUBSURF", ICON_MOD_SUBSURF, "Subdivision Surface", ""},
 	{eModifierType_UVProject, "UV_PROJECT", ICON_MOD_UVPROJECT, "UV Project", ""},
+	{eModifierType_NavMesh, "NAVMESH", ICON_MOD_DECIM, "Navigation mesh", ""},
 	{0, "", 0, "Deform", ""},
 	{eModifierType_Armature, "ARMATURE", ICON_MOD_ARMATURE, "Armature", ""},
 	{eModifierType_Cast, "CAST", ICON_MOD_CAST, "Cast", ""},
@@ -168,6 +169,8 @@ static StructRNA* rna_Modifier_refine(struct PointerRNA *ptr)
 			return &RNA_SolidifyModifier;
 		case eModifierType_Screw:
 			return &RNA_ScrewModifier;
+		case eModifierType_NavMesh:
+			return &RNA_NavMeshModifier;
 		default:
 			return &RNA_Modifier;
 	}
@@ -2190,6 +2193,84 @@ static void rna_def_modifier_screw(BlenderRNA *brna)
 	RNA_def_property_update(prop, 0, "rna_Modifier_update");*/
 }
 
+static void rna_def_modifier_navmesh(BlenderRNA *brna)
+{
+	StructRNA *srna;
+	PropertyRNA *prop;
+
+	srna= RNA_def_struct(brna, "NavMeshModifier", "Modifier");
+	RNA_def_struct_ui_text(srna, "NavMesh Modifier", "NavMesh modifier");
+	RNA_def_struct_sdna(srna, "NavMeshModifierData");
+	RNA_def_struct_ui_icon(srna, ICON_MOD_DECIM);
+
+	prop= RNA_def_property(srna, "cellsize", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 1, 0.01, 2);
+	RNA_def_property_ui_text(prop, "Cell size", "Rasterized cell size");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "cellheight", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 1, 0.01, 2);
+	RNA_def_property_ui_text(prop, "Cell height", "Rasterized cell height");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "agentheight", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 5, 0.1, 2);
+	RNA_def_property_ui_text(prop, "Agent height", "Minimum height where the agent can still walk");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "agentradius", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 5, 0.1, 2);
+	RNA_def_property_ui_text(prop, "Agent radius", "Radius of the agent");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "agentmaxclimb", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 5, 0.1, 2);
+	RNA_def_property_ui_text(prop, "Max climb", "Maximum height between grid cells the agent can climb");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "agentmaxslope", PROP_FLOAT, PROP_ANGLE);
+	RNA_def_property_ui_range(prop, 0, 90, 1, 2);
+	RNA_def_property_ui_text(prop, "Max slope", "Maximum walkable slope angle in degrees");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+
+	prop= RNA_def_property(srna, "regionminsize", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0, 150, 1, 2);
+	RNA_def_property_ui_text(prop, "Min region size", "Minimum regions size. Smaller regions will be deleted");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "regionmergesize", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0, 150, 1, 2);
+	RNA_def_property_ui_text(prop, "Merged region size", "Minimum regions size. Smaller regions will be merged");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "edgemaxlen", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0, 50, 1, 2);
+	RNA_def_property_ui_text(prop, "Max edge length", "Maximum contour edge length");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "edgemaxerror", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.1, 3.0, 0.1, 2);
+	RNA_def_property_ui_text(prop, "Max edge error", "Maximum distance error from contour to cells");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "vertsperpoly", PROP_INT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 3, 12, 1, 0);
+	RNA_def_property_ui_text(prop, "Verts per poly", "Max number of vertices per polygon");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "detailsampledist", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.0, 16.0, 1, 2);
+	RNA_def_property_ui_text(prop, "Sample Distance", "Detail mesh sample spacing");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+	prop= RNA_def_property(srna, "detailsamplemaxerror", PROP_FLOAT, PROP_NONE);
+	RNA_def_property_ui_range(prop, 0.0, 16.0, 1, 2);
+	RNA_def_property_ui_text(prop, "Max Sample Error", "Detail mesh simplification max sample error");
+	RNA_def_property_update(prop, 0, "rna_Modifier_update");
+
+}
+
 void RNA_def_modifier(BlenderRNA *brna)
 {
 	StructRNA *srna;
@@ -2280,6 +2361,7 @@ void RNA_def_modifier(BlenderRNA *brna)
 	rna_def_modifier_smoke(brna);
 	rna_def_modifier_solidify(brna);
 	rna_def_modifier_screw(brna);
+	rna_def_modifier_navmesh(brna);
 }
 
 #endif
diff --git a/source/blender/modifiers/MOD_modifiertypes.h b/source/blender/modifiers/MOD_modifiertypes.h
index bd10b4aa6fc..a55b5934f7d 100644
--- a/source/blender/modifiers/MOD_modifiertypes.h
+++ b/source/blender/modifiers/MOD_modifiertypes.h
@@ -67,6 +67,7 @@ extern ModifierTypeInfo modifierType_Smoke;
 extern ModifierTypeInfo modifierType_ShapeKey;
 extern ModifierTypeInfo modifierType_Solidify;
 extern ModifierTypeInfo modifierType_Screw;
+extern ModifierTypeInfo modifierType_NavMesh;
 
 /* MOD_util.c */
 void modifier_type_init(ModifierTypeInfo *types[], ModifierType type);
diff --git a/source/blender/modifiers/intern/MOD_navmesh.c b/source/blender/modifiers/intern/MOD_navmesh.c
new file mode 100644
index 00000000000..72fd1c40133
--- /dev/null
+++ b/source/blender/modifiers/intern/MOD_navmesh.c
@@ -0,0 +1,198 @@
+/*
+* $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) 2005 by the Blender Foundation.
+* All rights reserved.
+*
+* Contributor(s): 
+*
+* ***** END GPL LICENSE BLOCK *****
+*
+*/
+
+#include "DNA_meshdata_types.h"
+#include "BLI_math.h"
+#include "BKE_cdderivedmesh.h"
+#include "BKE_mesh.h"
+#include "BKE_modifier.h"
+#include "BKE_particle.h"
+
+
+static void initData(ModifierData *md)
+{
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+
+	nmmd->cellsize = 0.3f;
+	nmmd->cellheight = 0.2f;
+	nmmd->agentmaxslope = 45.0f;
+	nmmd->agentmaxclimb = 0.9f;
+	nmmd->agentheight = 2.0f;
+	nmmd->agentradius = 0.6f;
+	nmmd->edgemaxlen = 12.0f;
+	nmmd->edgemaxerror = 1.3f;
+	nmmd->regionminsize = 50.f;
+	nmmd->regionmergesize = 20.f;
+	nmmd->vertsperpoly = 6;
+	nmmd->detailsampledist = 6.0f;
+	nmmd->detailsamplemaxerror = 1.0f;
+}
+
+static void copyData(ModifierData *md, ModifierData *target)
+{
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+	NavMeshModifierData *tnmmd = (NavMeshModifierData*) target;
+
+}
+
+static DerivedMesh *createNavMesh(NavMeshModifierData *mmd,DerivedMesh *dm)
+{
+	int i;
+	DerivedMesh *result;
+	int numVerts, numEdges, numFaces;
+	int maxVerts = dm->getNumVerts(dm);
+	int maxEdges = dm->getNumEdges(dm);
+	int maxFaces = dm->getNumFaces(dm);
+
+	numVerts = numEdges = numFaces = 0;
+
+	result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2);
+
+	for(i = 0; i < maxVerts; i++) {
+		MVert inMV;
+		MVert *mv = CDDM_get_vert(result, numVerts);
+		float co[3];
+
+		dm->getVert(dm, i, &inMV);
+
+		copy_v3_v3(co, inMV.co);
+		DM_copy_vert_data(dm, result, i, numVerts, 1);
+		*mv = inMV;
+		numVerts++;
+
+
+		{
+			MVert *mv2 = CDDM_get_vert(result, numVerts);
+			DM_copy_vert_data(dm, result, i, numVerts, 1);
+			*mv2 = *mv;
+			co[2] +=.5f;
+			copy_v3_v3(mv2->co, co);
+			numVerts++;
+		}
+
+	}
+
+	for(i = 0; i < maxEdges; i++) {
+		MEdge inMED;
+		MEdge *med = CDDM_get_edge(result, numEdges);
+
+		dm->getEdge(dm, i, &inMED);
+
+		DM_copy_edge_data(dm, result, i, numEdges, 1);
+		*med = inMED;
+		numEdges++;
+
+		med->v1 = inMED.v1*2;
+		med->v2 = inMED.v2*2;
+		//med->flag |= ME_EDGEDRAW | ME_EDGERENDER;
+
+		{
+			MEdge *med2 = CDDM_get_edge(result, numEdges);
+
+			DM_copy_edge_data(dm, result, i, numEdges, 1);
+			*med2 = *med;
+			numEdges++;
+
+			med2->v1 += 1;
+			med2->v2 += 1;
+		}		
+	}
+
+	for(i = 0; i < maxFaces; i++) {
+		MFace inMF;
+		MFace *mf = CDDM_get_face(result, numFaces);
+
+		dm->getFace(dm, i, &inMF);
+
+		DM_copy_face_data(dm, result, i, numFaces, 1);
+		*mf = inMF;
+		numFaces++;
+
+		mf->v1 = inMF.v1*2;
+		mf->v2 = inMF.v2*2;
+		mf->v3 = inMF.v3*2;
+		mf->v4 = inMF.v4*2;
+
+		{
+			MFace *mf2 = CDDM_get_face(result, numFaces);
+			DM_copy_face_data(dm, result, i, numFaces, 1);
+			*mf2 = *mf;
+
+			mf2->v1 += 1;
+			mf2->v2 += 1;
+			mf2->v3 += 1;
+			if(inMF.v4) mf2->v4 += 1;
+
+			//test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
+			numFaces++;
+		}
+	}
+
+/*
+	CDDM_lower_num_verts(result, numVerts);
+	CDDM_lower_num_edges(result, numEdges);
+	CDDM_lower_num_faces(result, numFaces);*/	
+
+	return result;
+}
+
+
+static DerivedMesh *applyModifier(ModifierData *md, Object *ob, DerivedMesh *derivedData,
+								  int useRenderParams, int isFinalCalc)
+{
+	DerivedMesh *result;
+
+	NavMeshModifierData *nmmd = (NavMeshModifierData*) md;
+
+	result = createNavMesh(nmmd, derivedData);
+
+	return result;
+}
+
+
+ModifierTypeInfo modifierType_NavMesh = {
+	/* name */              "NavMesh",
+	/* structName */        "NavMeshModifierData",
+	/* structSize */        sizeof(NavMeshModifierData),
+	/* type */              eModifierTypeType_Constructive,
+	/* flags */             eModifierTypeFlag_AcceptsMesh,
+	/* copyData */          copyData,
+	/* deformVerts */       0,
+	/* deformVertsEM */     0,
+	/* deformMatricesEM */  0,
+	/* applyModifier */     applyModifier,
+	/* applyModifierEM */   0,
+	/* initData */          initData,
+	/* requiredDataMask */  0,
+	/* freeData */          0,
+	/* isDisabled */        0,
+	/* updateDepgraph */    0,
+	/* dependsOnTime */     0,
+	/* foreachObjectLink */ 0,
+	/* foreachIDLink */     0,
+};
diff --git a/source/blender/modifiers/intern/MOD_util.c b/source/blender/modifiers/intern/MOD_util.c
index 24b907dcfa8..0e9fe81ffdc 100644
--- a/source/blender/modifiers/intern/MOD_util.c
+++ b/source/blender/modifiers/intern/MOD_util.c
@@ -182,5 +182,6 @@ void modifier_type_init(ModifierTypeInfo *types[], ModifierType type)
 	INIT_TYPE(ShapeKey);
 	INIT_TYPE(Solidify);
 	INIT_TYPE(Screw);
+	INIT_TYPE(NavMesh);
 #undef INIT_TYPE
 }