Recast: upgrade library.

- Upgrade Recast library to latest portable version
- Implement recast_qsort based on FreeBSD qsort.c to have 
  portable thread safe quick sort for use in conversion routine.
- Better default value for the Build Navigation Mesh operator

4 files changed, 22 insertions, 18 deletions

diff --git a/source/blender/blenkernel/intern/navmesh_conversion.c b/source/blender/blenkernel/intern/navmesh_conversion.c
index 8a2ec1e5169..04f6ff19564 100644
--- a/source/blender/blenkernel/intern/navmesh_conversion.c
+++ b/source/blender/blenkernel/intern/navmesh_conversion.c
@@ -328,14 +328,10 @@ struct SortContext
 	const int* trisToFacesMap;
 };
 
-/* XXX: not thread-safe, but it's called only from modifiers stack
-        which isn't threaded. Anyway, better to avoid this in the future */
-static struct SortContext *_qsort_context;
-
-static int compareByData(const void * a, const void * b)
+static int compareByData(void *ctx, const void * a, const void * b)
 {
-	return ( _qsort_context->recastData[_qsort_context->trisToFacesMap[*(int*)a]] -
-			_qsort_context->recastData[_qsort_context->trisToFacesMap[*(int*)b]] );
+	return (((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int*)a]] -
+			((struct SortContext *)ctx)->recastData[((struct SortContext *)ctx)->trisToFacesMap[*(int*)b]] );
 }
 
 int buildNavMeshData(const int nverts, const float* verts, 
@@ -367,8 +363,7 @@ int buildNavMeshData(const int nverts, const float* verts,
 		trisMapping[i]=i;
 	context.recastData = recastData;
 	context.trisToFacesMap = trisToFacesMap;
-	_qsort_context = &context;
-	qsort(trisMapping, ntris, sizeof(int), compareByData);
+	recast_qsort(trisMapping, ntris, sizeof(int), &context, compareByData);
 
 	//search first valid triangle - triangle of convex polygon
 	validTriStart = -1;
diff --git a/source/blender/blenkernel/intern/scene.c b/source/blender/blenkernel/intern/scene.c
index d8ae36b4ab5..1a72405ad5e 100644
--- a/source/blender/blenkernel/intern/scene.c
+++ b/source/blender/blenkernel/intern/scene.c
@@ -526,7 +526,7 @@ Scene *add_scene(const char *name)
 	sce->gm.recastData.agentradius = 0.6f;
 	sce->gm.recastData.edgemaxlen = 12.0f;
 	sce->gm.recastData.edgemaxerror = 1.3f;
-	sce->gm.recastData.regionminsize = 50.f;
+	sce->gm.recastData.regionminsize = 8.f;
 	sce->gm.recastData.regionmergesize = 20.f;
 	sce->gm.recastData.vertsperpoly = 6;
 	sce->gm.recastData.detailsampledist = 6.0f;
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index ce4fb85fef3..482a78007fb 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -12101,7 +12101,7 @@ static void do_versions(FileData *fd, Library *lib, Main *main)
 			if(sce->gm.recastData.edgemaxerror == 0.0f)
 				sce->gm.recastData.edgemaxerror = 1.3f;
 			if(sce->gm.recastData.regionminsize == 0.0f)
-				sce->gm.recastData.regionminsize = 50.f;
+				sce->gm.recastData.regionminsize = 8.f;
 			if(sce->gm.recastData.regionmergesize == 0.0f)
 				sce->gm.recastData.regionmergesize = 20.f;
 			if(sce->gm.recastData.vertsperpoly<3)
diff --git a/source/blender/editors/mesh/mesh_navmesh.c b/source/blender/editors/mesh/mesh_navmesh.c
index 1cd5dcdb241..e4b884744e1 100644
--- a/source/blender/editors/mesh/mesh_navmesh.c
+++ b/source/blender/editors/mesh/mesh_navmesh.c
@@ -174,7 +174,7 @@ static int buildNavMesh(const RecastData *recastParams, int nverts, float *verts
 	struct recast_compactHeightfield* chf;
 	struct recast_contourSet *cset;
 	int width, height, walkableHeight, walkableClimb, walkableRadius;
-	int minRegionSize, mergeRegionSize, maxEdgeLen;
+	int minRegionArea, mergeRegionArea, maxEdgeLen;
 	float detailSampleDist, detailSampleMaxError;
 
 	recast_calcBounds(verts, nverts, bmin, bmax);
@@ -183,8 +183,8 @@ static int buildNavMesh(const RecastData *recastParams, int nverts, float *verts
 	walkableHeight= (int)ceilf(recastParams->agentheight/ recastParams->cellheight);
 	walkableClimb= (int)floorf(recastParams->agentmaxclimb / recastParams->cellheight);
 	walkableRadius= (int)ceilf(recastParams->agentradius / recastParams->cellsize);
-	minRegionSize= (int)(recastParams->regionminsize * recastParams->regionminsize);
-	mergeRegionSize= (int)(recastParams->regionmergesize * recastParams->regionmergesize);
+	minRegionArea= (int)(recastParams->regionminsize * recastParams->regionminsize);
+	mergeRegionArea= (int)(recastParams->regionmergesize * recastParams->regionmergesize);
 	maxEdgeLen= (int)(recastParams->edgemaxlen/recastParams->cellsize);
 	detailSampleDist= recastParams->detailsampledist< 0.9f ? 0 :
 			recastParams->cellsize * recastParams->detailsampledist;
@@ -212,13 +212,14 @@ static int buildNavMesh(const RecastData *recastParams, int nverts, float *verts
 	MEM_freeN(triflags);
 
 	/* ** Step 3: Filter walkables surfaces ** */
+	recast_filterLowHangingWalkableObstacles(walkableClimb, solid);
 	recast_filterLedgeSpans(walkableHeight, walkableClimb, solid);
 	recast_filterWalkableLowHeightSpans(walkableHeight, solid);
 
 	/* ** Step 4: Partition walkable surface to simple regions ** */
 
 	chf= recast_newCompactHeightfield();
-	if(!recast_buildCompactHeightfield(walkableHeight, walkableClimb, RECAST_WALKABLE, solid, chf)) {
+	if(!recast_buildCompactHeightfield(walkableHeight, walkableClimb, solid, chf)) {
 		recast_destroyHeightfield(solid);
 		recast_destroyCompactHeightfield(chf);
 
@@ -226,6 +227,13 @@ static int buildNavMesh(const RecastData *recastParams, int nverts, float *verts
 	}
 
 	recast_destroyHeightfield(solid);
+	solid = NULL;
+
+	if (!recast_erodeWalkableArea(walkableRadius, chf)) {
+		recast_destroyCompactHeightfield(chf);
+
+		return 0;
+	}
 
 	/* Prepare for region partitioning, by calculating distance field along the walkable surface */
 	if(!recast_buildDistanceField(chf)) {
@@ -235,7 +243,7 @@ static int buildNavMesh(const RecastData *recastParams, int nverts, float *verts
 	}
 
 	/* Partition the walkable surface into simple regions without holes */
-	if(!recast_buildRegions(chf, walkableRadius, 0, minRegionSize, mergeRegionSize)) {
+	if(!recast_buildRegions(chf, 0, minRegionArea, mergeRegionArea)) {
 		recast_destroyCompactHeightfield(chf);
 
 		return 0;
@@ -293,7 +301,8 @@ static Object* createRepresentation(bContext *C, struct recast_polyMesh *pmesh,
 	Object* obedit;
 	int createob= base==NULL;
 	int nverts, nmeshes, nvp;
-	unsigned short *verts, *meshes, *polys;
+	unsigned short *verts, *polys;
+	unsigned int *meshes;
 	float bmin[3], cs, ch, *dverts;
 	unsigned char *tris;
 	ModifierData *md;
@@ -348,7 +357,7 @@ static Object* createRepresentation(bContext *C, struct recast_polyMesh *pmesh,
 
 	for(i= 0; i<nmeshes; i++) {
 		int uniquevbase= em->totvert;
-		unsigned short vbase= meshes[4*i+0];
+		unsigned int vbase= meshes[4*i+0];
 		unsigned short ndv= meshes[4*i+1];
 		unsigned short tribase= meshes[4*i+2];
 		unsigned short trinum= meshes[4*i+3];