Page 1 of 1

Quake III BSP PVS

Posted: Tue Mar 20, 2012 5:50 pm
by N64vSNES
Lately I've been studying a lot of Id Software's work, and I started on Quake III's BSP maps.

I've got pretty much everything to work fine, I've got it rendering with frustum culling / material sorting and even lightmaps. But the PVS (Potentially visible set?) is being a real pain.

From what I understand, a cluster is a group of leaves, and each cluster has visibility information for each other cluster?

So we can take two leaves, get the cluster index A and cluster index B and check if A is visible from B.

I've found a few guides documenting the Q3's BSP format, and here is what I've got so far:

Loading the PVS:

Code: Select all

fseek(file, lumps[LMP_VISDATA].offset, SEEK_SET);
    if ( lumps[LMP_VISDATA].size > 0 ) {
	VisData = new bsp_visdata_t;
	fread(&VisData->numVecs, sizeof(int), 1, file);
	fread(&VisData->vecSize, sizeof(int), 1, file);
	VisData->bytes = new unsigned char[VisData->numVecs * VisData->vecSize];
	fread(VisData->bytes, sizeof(unsigned char) * (VisData->numVecs * VisData->vecSize), 1, file);
    }
I've added output from within this if statement, it's getting executed so there is definitely visibility information available (I've heard there isn't always).

To get the current leaf the camera is located within, I use this function:

Code: Select all

int Eternal::Scene::BspMap::FindLeaf(Core::Vector3 &v) const
{
    int index = 0;
    bsp_plane_t *plane;
    bsp_node_t *node;

    while(index >= 0) {
	node = &Nodes[index];
	plane = &Planes[node->plane];

	const float dist = plane->normal[0] * v.x +
			    plane->normal[1] * v.y +
			    plane->normal[2] * v.z - plane->d;

	if ( dist >= 0.0f ) {
	    index = node->front;
	}
	else {
	    index = node->back;
	}
    }

    return -index - 1;
}
^This function outputs extremely large values, or mostly -1. I think this could be the problem? :/

Also, one more function of relevance:

Code: Select all

int Eternal::Scene::BspMap::ClusterVisible(int a, int b) const
{
    // a < 0 (camera out of map)
    // VisData = NULL ( No visibility information)
    if(VisData == NULL || a < 0) {
	return 1;
    }

    int i = (a * VisData->vecSize) + (b >> 3);
    unsigned char visSet = VisData->bytes[i];

    return (visSet & (1 << (b & 7))) != 0;
}

This checks if the cluster b is visible from cluster a.
I checked the if statement, VisData is definitely not NULL and a is sometimes -1 but I'm sure that's not supposed to happen.


And I render the map like so:

Code: Select all

    // Take a copy of the camera position
    Core::Vector3 pos = *Camera->GetPosition();

    // Find the current leaf we're in
    const int curLeaf = FindLeaf(pos);

    for ( unsigned int l = 0;l < i_NumLeaves;l++ ) {

                /* This doesn't work- It's only ever said EVERYTHING is visible or NOTHING is visible. */
		if ( !ClusterVisible(Leaves[curLeaf].cluster, Leaves[l].cluster ) ) {
			continue;
		}

                /* Checks if the leaf is in the frustum */
		if ( !Frustum->BoxInFrustum((float)Leaves[l].min[0], (float)Leaves[l].min[1], (float)Leaves[l].min[2],
						(float)Leaves[l].max[0], (float)Leaves[l].max[1], (float)Leaves[l].max[2]) )
		{
			continue;
		}
		numFaces = Leaves[l].numleaffaces;
		while(numFaces--) {
                   /* This just adds indices to the faces needed to be drawn */
		   n = LeafFaces[Leaves[l].leafface + numFaces];
		   if ( drawnFaces[n] == true ) {
			   continue;
		   }
		   const int c = listIndices[Faces[n].glTexID].count;
		   listIndices[Faces[n].glTexID].Indices[c] = n;
		   listIndices[Faces[n].glTexID].count++;
		   drawnFaces[n] = true;
		}
   }
I know this isn't a very basic question, but if anyone can offer any advice as to where I may be going wrong, or more precious documentation I would MUCH appreciate it! :)

Also, I know Quake III uses X/Z/Y coords instead of X/Y/Z coords, this gets handled when the map is loaded.
And it's also worth mentioning, I know Quake III is GPL'd now, but the code is so unclear I can barely make any sense out of it. :|

Thanks!

Re: Quake III BSP PVS

Posted: Wed Mar 21, 2012 6:47 pm
by qpHalcy0n
You have not laid out precisely WHAT the problem IS.

What you have labelled as "this does not work, either everything is visible or nothing is visible". This is precisely how the PVS check is supposed to work. You're testing the leaf you're IN versus every other leaf in the map to see if its visible. Clearly it will either be visible or not. Given the coupling of the loop, you can see that its NOT saying that EVERYTHING is visible or NOTHING is visible. It's saying that THIS cluster to THAT cluster has no visibility (is completely occluded by opaque geom).

Given that I don't know what the problem is, I cannot help you. It appears okay at a cursory glance.

Re: Quake III BSP PVS

Posted: Thu Mar 22, 2012 9:15 am
by N64vSNES
qpHalcy0n wrote:You have not laid out precisely WHAT the problem IS.

What you have labelled as "this does not work, either everything is visible or nothing is visible". This is precisely how the PVS check is supposed to work. You're testing the leaf you're IN versus every other leaf in the map to see if its visible. Clearly it will either be visible or not. Given the coupling of the loop, you can see that its NOT saying that EVERYTHING is visible or NOTHING is visible. It's saying that THIS cluster to THAT cluster has no visibility (is completely occluded by opaque geom).

Given that I don't know what the problem is, I cannot help you. It appears okay at a cursory glance.
I don't think I explained as clearly as I could have done. It will report visible or not visible, of course. But it will say the same thing for EVERY leaf.

So it's culling nothing at all, or the entire map. It doesn't partially cull the map, as it should.

What's causing this, is a complete mystery. Everything looks fine to me.

Sorry if that still didn't make sense.

EDIT:
I just noticed, FindLeaf() nearly always returns -1. I'm not entirely sure why this is, although this is at least one major problem... :|

Re: Quake III BSP PVS

Posted: Thu Mar 22, 2012 6:23 pm
by Rebornxeno
Hi N64. Looks like a toughy! If you don't mind me asking, why does the findleaf function return the negative of the index? Are your nodes/clusters initialized? Well, apart from those questions, with the given information, it doesn't look like something is wrong with that code to me. I say the only way for us to help you solve this is for you to post all the hundreds of page of source code here and let us read all of it. Then, surely, we will have your answer!

Re: Quake III BSP PVS

Posted: Thu Mar 22, 2012 8:46 pm
by qpHalcy0n
The -1 leaf is a null (invalid) one. You need to check your splitting planes and your traversal code.

Re: Quake III BSP PVS

Posted: Fri Mar 23, 2012 3:28 pm
by N64vSNES
Hmm, I've been trying really hard with this, I've found numerous other open sourced examples and I've been studying a lot about BSP trees, but I swear I still have no idea what the problem is.

My traversal code looks okay (to me).. I'm very unsure what to even look for anymore. FindLeaf() doesn't seem to be returning -1 anymore (no idea what I changed), but it's definitely returning something invalid.

If anyone is brave enough to take a look, here's the full source:

q3bsp.h: http://pastebin.com/3UKLAy3j
q3bsp.cpp: http://pastebin.com/MBmufvrt

bsp_types.h: http://pastebin.com/maaNtD2r

The camera, if it's any help to anyone (yeah I know, gimbal lock):
camera.h: http://pastebin.com/yjHHZdcR
camera.cpp: http://pastebin.com/0JTbt7bB

Really right now I'm just looking for a nudge in the right direction, if anyone can find anything at all that might be of help, I'll be eternally grateful!