Archived

This topic is now archived and is closed to further replies.

weasalmongler

Quake3 visibility culling

Recommended Posts

Hello, I posted something about this a while back but peoples advice was to implement the bsp tree before getting into this. Now my tree is implemented I am trying to use the Visdata part of the Q3 bsp file to cull out the leafs that I don't need to draw. However I am running into troubles. I have found out that cluster 'A' is visible from cluster 'B' if the '(1 << B % 8)' bit of 'Visdata->vecs[ A * Visdata->sz_vecs + B / 8]' is set. When I try and implement this it culls the wrong polygons, and I end up with a level that randomly stops drawing triangles depending on where you are in the map. Here is my Visibility testing function
    
int CQuakeWorld::BSP_TESTVIS(int indexto, int indexfrom)
{

	return levelBody.visdata->vecs[(indexfrom * levelBody.visdata->sz_vecs) 
		+ (indexto / 8)] & ( 1 << (indexto % 8));

}
    
If this function returns zero, then I skip the current leaf and do not draw it. Does anyone have any ideas? -Weasalmongler P.S. - Sorry, I think I posted this twice!! Edited by - weasalmongler on March 24, 2002 8:11:09 AM

Share this post


Link to post
Share on other sites
I''m not sure that''s the problem. If you mean that the wrong parts of the map get drawn, perhaps you''re not using the leaf faces data properly.

If I remember correctly, each leaf has an index into a leaf faces array, which in turn indexes into the faces.

I can''t be any more specific though, it''s been a while since I did Q3 BSP work.


Helpful links:
How To Ask Questions The Smart Way | Google can help with your question | Search MSDN for help with standard C or Windows functions

Share this post


Link to post
Share on other sites
Sorry.. my mistake, the incorrect parts being drawn is due to something else which I have fixed. Now however, ALL the faces are being drawn, and none are being culled at all. I am not sure if that function is the problem, but it is the most promising part of the program that could be wrong. Could anybody else try and help please, I've been trying for AGES!

-Weasalmongler

P.S. - I am pretty sure that the faces are drawn right, because they are all drawn correctly when this function is turned off, its just there is no culling.

[edited by - weasalmongler on March 24, 2002 8:40:05 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by weasalmongler
Sorry.. my mistake, the incorrect parts being drawn is due to something else which I have fixed. Now however, ALL the faces are being drawn, and none are being culled at all. I am not sure if that function is the problem, but it is the most promising part of the program that could be wrong. Could anybody else try and help please, I''ve been trying for AGES!

[quote]

This function looks correct. The bug is either in your leaf drawing code, or it''s in your find cluster code.

[quote]
P.S. - I am pretty sure that the faces are drawn right, because they are all drawn correctly when this function is turned off, its just there is no culling.



I wouldn''t be so sure. I had a problem when I first did PVS where the wrong things got drawn. It turned out I was drawing the wrong faces when I drew a leaf. W/O culling, though, the fact that I was drawing _all_ the leaves covered up the error.

Share this post


Link to post
Share on other sites
Would it help if I posted this part of the bsp tree code?


  

void CQuakeWorld::WalkBSPLeaf(int n, int accept)
{
leaf_t *leaf = &levelBody.leafs[n];
int i;

/* Test visibility before bounding box */
if (eyecluster >= 0)
{
if (! BSP_TESTVIS(leaf->cluster, eyecluster)) return;
}

for (i=0; i < leaf->n_leaffaces; ++i)
{
WalkBSPFace(levelBody.leaffaces[i + leaf->leafface].face);
}
}


void CQuakeWorld::WalkBSPFace(int n)
{
face_t *face = &levelBody.faces[n];

if(face->type == 1) //Triangles

{

glActiveTextureARB(GL_TEXTURE0_ARB);
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, texID[face->texture]);

glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE);


glActiveTextureARB(GL_TEXTURE1_ARB);
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, lightmapID[face->lm_index]);

glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);


glBegin(GL_TRIANGLE_FAN);

for(int j=0; j<face->n_vertices; j++)
{
glMultiTexCoord2fARB(GL_TEXTURE0_ARB, -levelBody.vertices[face->vertex + j].texcoord[0][0], -levelBody.vertices[face->vertex + j].texcoord[0][1]);
glMultiTexCoord2fARB(GL_TEXTURE1_ARB, levelBody.vertices[face->vertex + j].texcoord[1][0], levelBody.vertices[face->vertex + j].texcoord[1][1]);

//Invert Y and Z coords!

glVertex3f(levelBody.vertices[face->vertex + j].position[0],
levelBody.vertices[face->vertex + j].position[2],
levelBody.vertices[face->vertex + j].position[1]);
}

glEnd();

}

}



Sorry, I don''t know how readable this code will be. I hope you can make sense of it, and could anybody work out what is wrong please?

Thx again.

-Weasalmongler

Share this post


Link to post
Share on other sites
ARRGGHHH!! It still doesn''t work!

I don''t suppose anyone could have a look at these two code posts to see if they can see a problem? I really am stuck here. If u want more code then just ask.

- Weasalmongler

Share this post


Link to post
Share on other sites
Right, I've finally found which part of the program is causing the problem. The problem is that every time the function which determines which cluster the player is in is called, it returns -1 rather than the index to the cluster (no its not just outside the level! It returns -1 when you are moving about the level too). This means that the TEST_VIS() function is never called because its always an invalid index. Can anybody see anything wrong with this function if I post it, because I'm having a hard time locating the problem.


    

int CQuakeWorld::find_cluster(vec3_t pos)
{
node_t *node;
int cluster = -1;
int leaf = -1;

node = &levelBody.nodes[0];

/* Find the leaf/cluster containing the given position */

while (1)
{
if (classify_point(pos, node->plane) > 0)
{
if (node->children[0] < 0)
{
leaf = -(node->children[0] + 1);
break;
}
else
{
node = &levelBody.nodes[node->children[0]];
}
}
else
{
if (node->children[1] < 0)
{
leaf = -(node->children[1] + 1);
break;
}
else
{
node = &levelBody.nodes[node->children[1]];
}
}
}

if (leaf >= 0)
cluster = levelBody.leafs[leaf].cluster;
return cluster;
}



By the way, classify_point() works out which side of the plane the point is on, and returns 1 for one side and -1 for the other.

Anybody who can solve this problem will be showered with praise from me for all eternity, I've been trying to sort if for ages now and its making my head hurt. Least I isolated the problem!

-Weasalmongler

[edited by - weasalmongler on March 26, 2002 12:57:45 PM]

Share this post


Link to post
Share on other sites

If it can help you I am using this peace of code

Int32 nLeaf = FindLeaf(camera.GetPosition());
m_CurrentCluster = m_pLeaves[nLeaf].cluster;

int Q3BSP::FindLeaf(const vector3& v)
{
Int32 i = 0;

while(i>=0)
{
const fNode& n = m_pNodes;
const fPlane& p = m_pPlanes[n.plane];

float d;
// f(x,y,z) = Ax+Ay+Az-D
d = p.normal[0]*v.x
+p.normal[1]*v.z
+p.normal[2]*v.y
-p.dist;

if(d >= 0) // in front or on the plane
{
i = n.front;
}
else // behind the plane
{
i = n.back;
}
}
return ~i;
}

Share this post


Link to post
Share on other sites
YOUR CODE WORKS!!!!!

THANK YOU! THANK YOU! THANK YOU! THANK YOU!

There are a few problems elsewhere in my program that I can soon fix, so my renderer is not working perfectly yet but its getting there. I should be able to finish the visibility part of the engine soon on my own.

Eweber, Thank you very much, I''ve been trying to sort this for ages, and now you''ve done it.

Thanks to EVERYBODY who has helped with this, I really appreciate it.

-Weasalmongler

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I also implemented a BSP renderer, in D3D however. However I am very concerned about performance and want to get this part working with very high FPS as base.

Now my problem. How did you perform frustum culling? The problem I have is that my occlusion culling actually slows down my rendering.

When rendering q3dm1 I get ~60-100fps, but with my occlusion it drops to 30-50. This is because my traversal is CPU intensive and my GPU is much more powerful than my CPU.

Now let me rephrase my rendering approach.
1. I quickly find the camera cluster by traversing the BSP tree by deciding on which side of the planes the camera position is own
2. I traverse the front side and then the back side of the tree (when the node/leaf is within the frustum)
3. Once I hit a leaf I check if the cluster is visible and then render it

The part that I have trouble with is the bounding box check against the view frustum planes with the mins/maxs of the nodes/leaves.

Also a stack based traversal for 2. seems slower than a simple recursive approach. I already used a iterative solution fos 1. I use a static Vertexbuffer and a static Indexbuffer for world geometry and use the Indexoffset of the faces to rendering everything and only transform (and light) geometry that is rendered.

I have not yet sorted by shaders before rendering, but that is my next step.

Btw, mesh types in the level are tessellated with N-Patches (TrueForm), but I have not yet found an easy way for rendering patch types (the Bezier stuff). I thought about rendering them with RT-Patches, but they have become obsolete.

I would appreciate any help here. Probably a second Vertexbuffer that is filled once with tessellated geometry that is calculated with the control points would be great, but I have no experience with Bezier splines etc.

Share this post


Link to post
Share on other sites