Bug when culling out off-mesh start locations?

[prjoh]

We are using RecastDetour for a project as a central part of our AI system. While creating debug draw tools for off-mesh connection placement, we found some odd behavior in how the connections are culled.

The dtCreateNavMeshData function seems to perform a height bounds check based on agent walkable climb as well as cell height:

bool dtCreateNavMeshData(dtNavMeshCreateParams* params, unsigned char** outData, int* outDataSize)
{
	// ...

	if (params->offMeshConCount > 0)
	{
		// ...

		// Find tight heigh bounds, used for culling out off-mesh start locations.
		float hmin = FLT_MAX;
		float hmax = -FLT_MAX;
		
		if (params->detailVerts && params->detailVertsCount)
		{
			for (int i = 0; i < params->detailVertsCount; ++i)
			{
				const float h = params->detailVerts[i*3+1];
				hmin = dtMin(hmin,h);
				hmax = dtMax(hmax,h);
			}
		}
		else
		{
			for (int i = 0; i < params->vertCount; ++i)
			{
				const unsigned short* iv = &params->verts[i*3];
				const float h = params->bmin[1] + iv[1] * params->ch;
				hmin = dtMin(hmin,h);
				hmax = dtMax(hmax,h);
			}
		}
		
		hmin -= params->walkableClimb;
		hmax += params->walkableClimb;
		float bmin[3], bmax[3];
		dtVcopy(bmin, params->bmin);
		dtVcopy(bmax, params->bmax);
		bmin[1] = hmin;
		bmax[1] = hmax;

		for (int i = 0; i < params->offMeshConCount; ++i)
		{
			const float* p0 = &params->offMeshConVerts[(i*2+0)*3];
			const float* p1 = &params->offMeshConVerts[(i*2+1)*3];
			offMeshConClass[i*2+0] = classifyOffMeshPoint(p0, bmin, bmax);
			offMeshConClass[i*2+1] = classifyOffMeshPoint(p1, bmin, bmax);

			// Zero out off-mesh start positions which are not even potentially touching the mesh.
			if (offMeshConClass[i*2+0] == 0xff)
			{
				if (p0[1] < bmin[1] || p0[1] > bmax[1])
					offMeshConClass[i*2+0] = 0;
			}

			// Cound how many links should be allocated for off-mesh connections.
			if (offMeshConClass[i*2+0] == 0xff)
				offMeshConLinkCount++;
			if (offMeshConClass[i*2+1] == 0xff)
				offMeshConLinkCount++;

			if (offMeshConClass[i*2+0] == 0xff)
				storedOffMeshConCount++;
		}
	}

	// ...
}

When debugging the memory locations for bmin[1]/bmax[1] (i.e. the height bounds), we noticed that the values are not what we would expect. We are providing a simple cube model in this report to reproduce the numbers we found using the RecastDemo. The model is a 10x1x10 cube.

cube.obj.zip

How to reproduce:

1. Download the cube.obj and place it inside RecastDemo\Bin\Meshes
2. Launch RecastDemo
3. Choose Sample Solo Mesh
4. Choose Mesh cube.obj
5. Set Cell Height to 1.0
6. Set agent max climb to 1.0
7. Select Tools Create Off-Mesh Connections and select One-Way
8. Place a connection on the mesh
9. Build the mesh

Please take a look at the following variables:
hmin = ~2.0
hmax = ~4.0

The original bmin and bmax values are calculated like so:
bmin = -mh (in our case -1.0)
bmax = mh + ah * ch (in our case 3.0)

As the model has a height of mh=1.0, the cell height is set to ch=1.0 and the agent climb height is set to ach=1.0, we would assume the following bounding box for off-mesh connection culling:
hmin = mh + ch - ach = 1.0
hmin = mh + ch + ach = 3.0

Instead the bounding box seems to be offset too much in y direction, thereby falsely culling correctly placed off-mesh connections. An interesting observation that we have made is, that if we offset our off-mesh connection height by the cell height configuration, then the check is passed correctly.

That being said, we would like to point to a suspicious comment in RecastMeshDetail in line 1314, where a cell height offset is added to the detail mesh vertices (Note that this is the actual value used when overriding hmin!). While we don't know if this is the actual culprit of the issue, we also don't know why this offset is being added (and it seems neither did the author). We would also like to point out, that removing this addition of cell height will let the off mesh connection pass the check correctly.

Please also compare the bound checks of dtCreateNavMeshData to the supposedly less corse check in DetourNavMesh once the off-mesh connection has passed the culling check.

We hope these pointers can help to elimiate this issue quickly. If we have misunderstood some usage of the tool, or some numbers, we would be equally glad if the authors could give us some insight into the way the checks are performed.