Extracting clip node data from BSP Created 2 years ago2022-09-22 12:12:30 UTC by Neoptolemus

Hi everyone,

I have a bit of a challenge. I want to generate a navmesh for HL maps as I'm creating a bot for some HL1 mods (especially Natural Selection) which have limited or no bot support.

To do this, I'm currently extracting all of the vertices from the BSP file and rendering them into a triangle mesh. Vertices exist for all visible entities in the BSP file, but I am excluding func_illusionary entities since these do not collide and therefore should be excluded from navmesh generation.

The challenge I have is clip brushes. These are used for things like chain-link fences and railings where the visual brush is a func_illusionary and then a brush with the CLIP texture is added to prevent players walking through them. The problem is that brushes with the CLIP texture are special cases and do NOT appear in the list of vertices (presumably because they're never rendered): they exist only as collision hulls.

The result is that right now, I only have two choices: include func_illusionary entities in navmesh generation, and have the AI unable to walk through things like the cs_747 curtains and other decorative features, or exclude them and have the AI try to walk through the chain-link fence in cs_militia.

The preferred option of course is to have the clip brushes retrieved and added to the list of vertices, but currently I have no idea how to do this. I've had a look at the hlbsp project's breakdown of the v30 map format here and the map optimisation tutorial here, but I'm still unsure how to convert the planes into a set of triangles. As far as I can see, they're defined as a set of infinitely wide and tall planes with a normal and distance from origin.

Has anyone managed to do this before?

I am also curious about generating a triangle mesh from clipnodes.
I think the answer can be found in BspGuy's source code, since that one renders clipnodes. Or at least seems to.
https://github.com/wootguy/bspguy/blob/master/src/editor/BspRenderer.cpp#L755

You could look into the original Quake compiler sources to see maybe how they're generated, but TL;DR you definitely gotta do some form of plane intersection to get polygons in the end.

I think the answer can be found in BspGuy's source code, since that one renders clipnodes. Or at least seems to.

Yes, you're right! It does. The actual collision hulls don't match the original brushwork however, as you can see, the collision hull is considerably larger than the original brush:I wonder if this is because it actually does a point test for player collision at the centre of the player hull, and simply expands the collision hulls to account for player height and width. It may be possible to retrieve the original collision hull by scaling it down by player radius and half height.

Looks like I need to do some digging now. I'll update if I find anything!

It indeed expands the hulls because the player hull is like, 36x36x72 units I think. Similarly, cliphull2 would be larger, and cliphull3 would be the smallest.

Ok so I've been having a play with it, but I've noticed something strange. The BSP viewer tool takes models and their collision planes and uses a "Clipper" object to carve each model into a mesh object by its various planes. The mesh holds a set of vertices, edges and faces. What I'm finding though is that the vertices produced in the meshes have insanely high or low values (e.g. -1317821 for an X coordinate).

The BSP viewer produces the exact same results as me, so it's not a mistake on my part. It must be doing something in the clipnode buffer to reduce the coordinates back down to something sane, but I can't see where it's doing it. As far as I can see, it's loading those huge values into the buffer for rendering. Any ideas on what I'm missing here?

Here's my thoughts:

BspRenderer.cpp
L770:

vector<NodeVolumeCuts> solidNodes = map->get_model_leaf_volume_cuts(modelIdx, i);

What's interesting is the return type of get_model_leaf_volume_cuts. NodeVolumeCuts is the BSP planes that "define the leaf boundaries when applied to a bounding box". So these aren't just some random planes, these are effectively the planes that form the convex volume of a BSP node or well, leaf in this case.

L772:

vector<CMesh> meshes;
for (int k = 0; k < solidNodes.size(); k++) {
    meshes.push_back(clipper.clip(solidNodes[k].cuts));
    clipnodeLeafCount++;
}

A CMesh is just a bunch of vertices, edges and faces, nothing special there.
What clipper.clip does is create a box CMesh that is the max size of a map (-131k to +131k units), which actually explains the thing you were seeing there, with -1317821 for the X coordinate. It then proceeds to chop up the box with cuts - the BSP planes that define that node's volume. It removes verts/edges/faces that are below the plane, and retains the ones above the plane, I believe. Or vice-versa. Doesn't really matter, you get the idea.

Basically works the exact same as the clipping tool in Hammer.

L790:

for (int m = 0; m < meshes.size(); m++) {
    CMesh& mesh = meshes[m];

    for (int i = 0; i < mesh.faces.size(); i++) {

        if (!mesh.faces[i].visible) {
            continue;
        }

For the next few dozen lines, it is basically optimising the mesh, removing redundant vertices etc.
And that's... it I think? Get BSP planes that define the convex volume of a leaf, and create the mesh of that convex volume by chopping up the planes against a huge bounding box. Alternatively you can create a polygon object for each plane and cut those polygons up, instead of using a big cube as your starting clipping object.

NGL I did not think it was that simple, just getting the bounding volume of each solid BSP node per hull. Obtaining the list of solid BSP nodes isn't hard either.
Can I see your code? Maybe there's a tiny oversight somewhere.

Thanks Admer456! Here is my code, which is mostly lifted from the BSP viewer, hopefully the comments make sense:

Bsp* map = new Bsp(filename);

	if (map->isValid())
	{

		int numTris = 0;
		int vertCounter = 0;
		int triCounter = 0;

		Clipper clipper;

		int clipnodeLeafCount = 0;

		vector<NodeVolumeCuts> solidNodes = map->get_model_leaf_volume_cuts(0, 1);

		vector<CMesh> meshes;
		vector<vec3> allVerts;
		vector<int> modelIndices;

		int indicesOffset = 0;

		// This bit is the same as the BSP viewer
		for (int k = 0; k < solidNodes.size(); k++)
		{
			meshes.push_back(clipper.clip(solidNodes[k].cuts));
			clipnodeLeafCount++;
		}

		for (int m = 0; m < meshes.size(); m++)
		{
			CMesh& mesh = meshes[m];

			for (int face = 0; face < mesh.faces.size(); face++)
			{

				if (!mesh.faces[face].visible)
				{
					continue;
				}

				// First add all the vertices to the vertex pool, then in a moment we'll define the indices that form each triangle
				for (int v = 0; v < mesh.verts.size(); v++)
				{
					allVerts.push_back(mesh.verts[v].pos);
				}


				// My understanding is that the indices held in the edges index into the verts array for that mesh, so if we want to combine
				// all meshes into a single soup, we need to offset the index number by the total number of indices already present
				for (int edge = 0; edge < mesh.faces[face].edges.size(); edge++)
				{
					modelIndices.push_back(mesh.edges[mesh.faces[face].edges[edge]].verts[0] + indicesOffset);
					modelIndices.push_back(mesh.edges[mesh.faces[face].edges[edge]].verts[1] + indicesOffset);
				}

				int indexCounter = 1;
				int totalIndices = (mesh.faces[face].edges.size() - 2);

				numTris += totalIndices;

				// Now we need to break the convex shape into triangles, fanning out from the first index and adding them into the
				// total indices array
				for (int x = 0; x < totalIndices; x++)
				{

					TriData->tris[triCounter++] = modelIndices[0];
					TriData->tris[triCounter++] = modelIndices[++indexCounter];
					TriData->tris[triCounter++] = modelIndices[indexCounter - 1];

				}

			}

			indicesOffset += mesh.verts.size();
		}


		// Add the verts into the float array
		TriData->ntris = numTris;

		for (int i = 0; i < allVerts.size(); i++)
		{
			TriData->verts[vertCounter++] = allVerts[i].x;
			TriData->verts[vertCounter++] = allVerts[i].y;
			TriData->verts[vertCounter++] = allVerts[i].z;
		}

		TriData->nverts = vertCounter / 3;

		return true;

}

Basically, TriData is a structure which contains an array of raw floats representing each vertex and an array of integers representing the indices that form the triangles. Effectively, it's the same format as an OBJ model.

The above approach works fine if I'm just extracting the vertices and edges direct from the map itself, but falls apart when trying to do it with the clip nodes. I'm not sure if this is because my approach isn't compatible with the way clip nodes are represented, or if it's incompatible with wootguy's mesh setup (or both...)

Might wanna check this too:

int vertIdx = mesh.edges[mesh.faces[i].edges[k]].verts[v];
if (!mesh.verts[vertIdx].visible) {
    continue;
}
uniqueFaceVerts.insert(vertIdx);

Vertices can be visible/invisible too, it appears.

Yeah I've already filtered those out. I also noticed that the BSP viewer code doesn't do anything with indices, so presumably it already just pushes the vertices in the order in which they're meant to be rendered, so the triangle indices would just be 1,2,3,4,5,6,7 etc. I've added that to my code.

This is what the code looks like now, it's mostly just a copy of the BSP viewer code, except I arbitrarily scale down everything by 1000 so at least the resulting map isn't insanely big:

if (map->isValid())
	{

		int numTris = 0;
		int vertCounter = 0;
		int triCounter = 0;

		Clipper clipper;

		int clipnodeLeafCount = 0;

		vector<NodeVolumeCuts> solidNodes = map->get_model_leaf_volume_cuts(0, 1);

		vector<CMesh> meshes;
		vector<vec3> allVerts;
		vector<int> modelIndices;
		int IndiceCounter = 0;

		int indicesOffset = 0;

		// This bit is the same as the BSP viewer
		for (int k = 0; k < solidNodes.size(); k++)
		{
			meshes.push_back(clipper.clip(solidNodes[k].cuts));
			clipnodeLeafCount++;
		}

		for (int m = 0; m < meshes.size(); m++)
		{
			CMesh& mesh = meshes[m];

			for (int face = 0; face < mesh.faces.size(); face++)
			{

				if (!mesh.faces[face].visible)
				{
					continue;
				}
				set<int> uniqueFaceVerts;

				for (int edge = 0; edge < mesh.faces[face].edges.size(); edge++)
				{
					for (int v = 0; v < 2; v++)
					{
						int vertIdx = mesh.edges[mesh.faces[face].edges[edge]].verts[v];
						if (!mesh.verts[vertIdx].visible)
						{
							continue;
						}
						uniqueFaceVerts.insert(vertIdx);
					}
				}

				vector<vec3> faceVerts;
				for (auto vertIdx : uniqueFaceVerts)
				{
					faceVerts.push_back(mesh.verts[vertIdx].pos);
				}

				faceVerts = getSortedPlanarVerts(faceVerts);

				if (faceVerts.size() < 3)
				{
					//logf("Degenerate clipnode face discarded\n");
					continue;
				}

				vec3 normal = getNormalFromVerts(faceVerts);

				if (dotProduct(mesh.faces[face].normal, normal) > 0)
				{
					reverse(faceVerts.begin(), faceVerts.end());
					normal = normal.invert();
				}

				// convert from TRIANGLE_FAN style verts to TRIANGLES
				for (int k = 2; k < faceVerts.size(); k++)
				{
					allVerts.push_back(faceVerts[0]);
					modelIndices.push_back(IndiceCounter++);
					allVerts.push_back(faceVerts[k - 1]);
					modelIndices.push_back(IndiceCounter++);
					allVerts.push_back(faceVerts[k]);
					modelIndices.push_back(IndiceCounter++);

					numTris++;
				}
			}
		}


		// Add the verts into the float array
		TriData->ntris = numTris;

		for (int i = 0; i < allVerts.size(); i++)
		{
			TriData->verts[vertCounter++] = allVerts[i].x * 0.001f;
			TriData->verts[vertCounter++] = allVerts[i].y * 0.001f;
			TriData->verts[vertCounter++] = allVerts[i].z * 0.001f;
		}

		for (int i = 0; i < modelIndices.size(); i++)
		{
			TriData->tris[triCounter++] = modelIndices[i];
		}

		TriData->nverts = vertCounter / 3;

		return true;

	}

What is missing though is the conversion from clip local units to world units. When I render the resulting mesh it looks like this regardless of which map I use as an input (the below is meant to be de_dust):For reference, to rule out the possibility of the issue being with the rendering of the mesh itself, this is what it looks like when I render it by extracting the faces and edges from the BSP tree (but of course that's missing CLIP brushes):

An additional thought to the above: the BSP renderer seems to have some issues with heavy artifacting of clipnodes as well. Looking at this section of map from ns_eclipse:Given that all I really want to do here is determine if a func_illusionary is solid or not, I wonder if it would be enough to perhaps query the BSP with a trace through the func_illusionary brush location to see if it hits something? Might save a lot of headaches. Problem is doing that from outside of GoldSrc...

Hmm, I'll need to download BspGuy's code tomorrow and experiment. This was so far just me interpreting the code from its GitHub.

I wonder if it would be enough to perhaps query the BSP with a trace through the func_illusionary brush location to see if it hits something?

Ah! You can actually borrow HLRAD's BSP raycast code... I think... it's meant for hull 0, but could be adapted for cliphull123 perhaps.

Thank you for the help so far! Looking forward to what you can dig up. Using a trace is one idea, but the preference of course is to just be able to extract all the world clip vertices so that invisible walls are also taken into account.

For example, tracing func_illusionary won't help with the barricade at CT spawn in cs_militia: the AI will still think it can crouch under the barriers if the invisible wall can't be detected.