Updated Recast to 4fef044

In some cases Godot can generate input parameters to Recast that cause it to crash.  Specifically when baking NavigationMeshes for input meshes that have axis extents less than half the NavigationMesh CellSize.

This has been fixed upstream in Recast (in https://github.com/recastnavigation/recastnavigation/commit/3901c5854c958593443859fd1214162452ff2982).  Updating Godot's Recast integration fixes this crash issue in Godot as well.

7 files changed, 29 insertions, 25 deletions

diff --git a/thirdparty/README.md b/thirdparty/README.md
index 9a58c928cc..0823c9f7ac 100644
--- a/thirdparty/README.md
+++ b/thirdparty/README.md
@@ -591,7 +591,7 @@ in 10.40, it can be found in the `patches` folder.
 ## recastnavigation
 
 - Upstream: https://github.com/recastnavigation/recastnavigation
-- Version: git (5a870d427e47abd4a8e4ce58a95582ec049434d5, 2022)
+- Version: git (4fef0446609b23d6ac180ed822817571525528a1, 2022)
 - License: zlib
 
 Files extracted from upstream source:
diff --git a/thirdparty/recastnavigation/Recast/Include/Recast.h b/thirdparty/recastnavigation/Recast/Include/Recast.h
index 4d557389b5..246376bbee 100644
--- a/thirdparty/recastnavigation/Recast/Include/Recast.h
+++ b/thirdparty/recastnavigation/Recast/Include/Recast.h
@@ -22,13 +22,16 @@
 /// The value of PI used by Recast.
 static const float RC_PI = 3.14159265f;
 
+/// Used to ignore unused function parameters and silence any compiler warnings.
+template<class T> void rcIgnoreUnused(const T&) { }
+
 /// Recast log categories.
 /// @see rcContext
 enum rcLogCategory
 {
 	RC_LOG_PROGRESS = 1,	///< A progress log entry.
 	RC_LOG_WARNING,			///< A warning log entry.
-	RC_LOG_ERROR,			///< An error log entry.
+	RC_LOG_ERROR			///< An error log entry.
 };
 
 /// Recast performance timer categories.
@@ -101,7 +104,6 @@ enum rcTimerLabel
 class rcContext
 {
 public:
-
 	/// Contructor.
 	///  @param[in]		state	TRUE if the logging and performance timers should be enabled.  [Default: true]
 	inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {}
@@ -140,31 +142,30 @@ public:
 	inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; }
 
 protected:
-
 	/// Clears all log entries.
-	virtual void doResetLog() {}
+	virtual void doResetLog();
 
 	/// Logs a message.
 	///  @param[in]		category	The category of the message.
 	///  @param[in]		msg			The formatted message.
 	///  @param[in]		len			The length of the formatted message.
-	virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {}
+	virtual void doLog(const rcLogCategory category, const char* msg, const int len) { rcIgnoreUnused(category); rcIgnoreUnused(msg); rcIgnoreUnused(len); }
 
 	/// Clears all timers. (Resets all to unused.)
 	virtual void doResetTimers() {}
 
 	/// Starts the specified performance timer.
 	///  @param[in]		label	The category of timer.
-	virtual void doStartTimer(const rcTimerLabel /*label*/) {}
+	virtual void doStartTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
 
 	/// Stops the specified performance timer.
 	///  @param[in]		label	The category of the timer.
-	virtual void doStopTimer(const rcTimerLabel /*label*/) {}
+	virtual void doStopTimer(const rcTimerLabel label) { rcIgnoreUnused(label); }
 
 	/// Returns the total accumulated time of the specified performance timer.
 	///  @param[in]		label	The category of the timer.
 	///  @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
-	virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; }
+	virtual int doGetAccumulatedTime(const rcTimerLabel label) const { rcIgnoreUnused(label); return -1; }
 	
 	/// True if logging is enabled.
 	bool m_logEnabled;
@@ -564,7 +565,7 @@ static const int RC_AREA_BORDER = 0x20000;
 enum rcBuildContoursFlags
 {
 	RC_CONTOUR_TESS_WALL_EDGES = 0x01,	///< Tessellate solid (impassable) edges during contour simplification.
-	RC_CONTOUR_TESS_AREA_EDGES = 0x02,	///< Tessellate edges between areas during contour simplification.
+	RC_CONTOUR_TESS_AREA_EDGES = 0x02	///< Tessellate edges between areas during contour simplification.
 };
 
 /// Applied to the region id field of contour vertices in order to extract the region id.
@@ -595,11 +596,6 @@ static const int RC_NOT_CONNECTED = 0x3f;
 /// @name General helper functions
 /// @{
 
-/// Used to ignore a function parameter.  VS complains about unused parameters
-/// and this silences the warning.
-///  @param [in] _ Unused parameter
-template<class T> void rcIgnoreUnused(const T&) { }
-
 /// Swaps the values of the two parameters.
 ///  @param[in,out]	a	Value A
 ///  @param[in,out]	b	Value B
@@ -996,6 +992,7 @@ void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
 ///  @ingroup recast
 ///  @param[in]		verts		The vertices of the polygon [Form: (x, y, z) * @p nverts]
 ///  @param[in]		nverts		The number of vertices in the polygon.
+///  @param[in]		offset		How much to offset the polygon by. [Units: wu]
 ///  @param[out]	outVerts	The offset vertices (should hold up to 2 * @p nverts) [Form: (x, y, z) * return value]
 ///  @param[in]		maxOutVerts	The max number of vertices that can be stored to @p outVerts.
 ///  @returns Number of vertices in the offset polygon or 0 if too few vertices in @p outVerts.
diff --git a/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h b/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h
index 071278d659..8b166d736d 100644
--- a/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h
+++ b/thirdparty/recastnavigation/Recast/Include/RecastAlloc.h
@@ -112,7 +112,7 @@ class rcVectorBase {
 	typedef rcSizeType size_type;
 	typedef T value_type;
 
-	rcVectorBase() : m_size(0), m_cap(0), m_data(0) {};
+	rcVectorBase() : m_size(0), m_cap(0), m_data(0) {}
 	rcVectorBase(const rcVectorBase<T, H>& other) : m_size(0), m_cap(0), m_data(0) { assign(other.begin(), other.end()); }
 	explicit rcVectorBase(rcSizeType count) : m_size(0), m_cap(0), m_data(0) { resize(count); }
 	rcVectorBase(rcSizeType count, const T& value) : m_size(0), m_cap(0), m_data(0) { resize(count, value); }
@@ -142,8 +142,8 @@ class rcVectorBase {
 
 	const T& front() const { rcAssert(m_size); return m_data[0]; }
 	T& front() { rcAssert(m_size); return m_data[0]; }
-	const T& back() const { rcAssert(m_size); return m_data[m_size - 1]; };
-	T& back() { rcAssert(m_size); return m_data[m_size - 1]; };
+	const T& back() const { rcAssert(m_size); return m_data[m_size - 1]; }
+	T& back() { rcAssert(m_size); return m_data[m_size - 1]; }
 	const T* data() const { return m_data; }
 	T* data() { return m_data; }
 
diff --git a/thirdparty/recastnavigation/Recast/Source/Recast.cpp b/thirdparty/recastnavigation/Recast/Source/Recast.cpp
index 1b71710cdc..4cf145c981 100644
--- a/thirdparty/recastnavigation/Recast/Source/Recast.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/Recast.cpp
@@ -94,6 +94,11 @@ void rcContext::log(const rcLogCategory category, const char* format, ...)
 	doLog(category, msg, len);
 }
 
+void rcContext::doResetLog()
+{
+	// Defined out of line to fix the weak v-tables warning
+}
+
 rcHeightfield* rcAllocHeightfield()
 {
 	return rcNew<rcHeightfield>(RC_ALLOC_PERM);
diff --git a/thirdparty/recastnavigation/Recast/Source/RecastMesh.cpp b/thirdparty/recastnavigation/Recast/Source/RecastMesh.cpp
index e99eaebb79..ea09ee1de0 100644
--- a/thirdparty/recastnavigation/Recast/Source/RecastMesh.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/RecastMesh.cpp
@@ -566,7 +566,6 @@ static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned sho
 	const int nvp = mesh.nvp;
 	
 	// Count number of polygons to remove.
-	int numRemovedVerts = 0;
 	int numTouchedVerts = 0;
 	int numRemainingEdges = 0;
 	for (int i = 0; i < mesh.npolys; ++i)
@@ -586,7 +585,6 @@ static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned sho
 		}
 		if (numRemoved)
 		{
-			numRemovedVerts += numRemoved;
 			numRemainingEdges += numVerts-(numRemoved+1);
 		}
 	}
diff --git a/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp b/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp
index 1999200c1a..40bfc9b4bc 100644
--- a/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp
@@ -284,7 +284,7 @@ static unsigned short getHeight(const float fx, const float fy, const float fz,
 enum EdgeValues
 {
 	EV_UNDEF = -1,
-	EV_HULL = -2,
+	EV_HULL = -2
 };
 
 static int findEdge(const int* edges, int nedges, int s, int t)
diff --git a/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp b/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
index a4cef74909..673550e79e 100644
--- a/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
+++ b/thirdparty/recastnavigation/Recast/Source/RecastRasterization.cpp
@@ -264,7 +264,8 @@ static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
 	// Calculate the footprint of the triangle on the grid's y-axis
 	int y0 = (int)((tmin[2] - bmin[2])*ics);
 	int y1 = (int)((tmax[2] - bmin[2])*ics);
-	y0 = rcClamp(y0, 0, h-1);
+	// use -1 rather than 0 to cut the polygon properly at the start of the tile
+	y0 = rcClamp(y0, -1, h-1);
 	y1 = rcClamp(y1, 0, h-1);
 	
 	// Clip the triangle into all grid cells it touches.
@@ -283,7 +284,7 @@ static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
 		dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2);
 		rcSwap(in, p1);
 		if (nvrow < 3) continue;
-		
+		if (y < 0) continue;
 		// find the horizontal bounds in the row
 		float minX = inrow[0], maxX = inrow[0];
 		for (int i=1; i<nvrow; ++i)
@@ -293,7 +294,10 @@ static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
 		}
 		int x0 = (int)((minX - bmin[0])*ics);
 		int x1 = (int)((maxX - bmin[0])*ics);
-		x0 = rcClamp(x0, 0, w-1);
+		if (x1 < 0 || x0 >= w) {
+			continue;
+		}
+		x0 = rcClamp(x0, -1, w-1);
 		x1 = rcClamp(x1, 0, w-1);
 
 		int nv, nv2 = nvrow;
@@ -305,7 +309,7 @@ static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
 			dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0);
 			rcSwap(inrow, p2);
 			if (nv < 3) continue;
-			
+			if (x < 0) continue;
 			// Calculate min and max of the span.
 			float smin = p1[1], smax = p1[1];
 			for (int i = 1; i < nv; ++i)