Jump to content
  • Advertisement
Sign in to follow this  
DanielWilkins

Depth sorting Quake style BSP geometry

This topic is 2587 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi.
I am trying to implement blending into my Quake map rendering engine. I realize that I need to sort my polygons or use z buffering when rendering. The Quake 3 format uses a BSP tree and a PVS and I utilize both in my rendering. I am now looking for a way to sort the faces so I don't have to have any problems with overlap. Does anyone have any code or examples of depth sorting a BSP tree?

Thanks.

Edit: Let me try and be more specific here. I start by finding the leaf node I am in. That leaf node is associated with a PVS which is the other regions I can see. From here, what kind of algorithm should I use. An online article says render opaque list from front to back and then transparent list from front to back. Does this mean if I have say, one transparent polygon, I don't have to sort it at all? How does the sorting algorithm work? Check the furthest point from the camera of each polygon?

Share this post


Link to post
Share on other sites
Advertisement
I think you mean transparent from back to front, after the opaque polys are drawn.

You render by simply storing all polys in the leafs, and go through the BSP, at each plane recursively rendering the child on the same side as the camera first, and then the one on the other side. For back to front it's the other way around.

Something like this:

struct Node{
Type type;

Plane plane;// Either the node has a plane, _or_ it has polys (leaf)
Polys polys;

Node *front;
Node *back;
};

void renderBSP(Node *node, Point camera) {
if(node->type == leaf) {
renderPolys(node->polys);
return;
}

if( side(camera, node->plane) == in front) {
if(node->front)
renderBSP(node->front);
if(node->back)
renderBSP(node->back);
}
else {
if(node->back)
renderBSP(node->back);
if(node->front)
renderBSP(node->front);
}
}


It works since whenever the camera is on one side of a plane, any geometry on the same side of that plane can never be occluded by any geometry on the other side of the plane. You don't have to render what is actually closest first, just everything that could possibly be in front of something else.
The BSP leafs will always be convex, so polys in the same leaf can never occlude each other.

Share this post


Link to post
Share on other sites
Fantastic. Thank you. Now, I see that will work for rendering all polygons back to front. Could I use that specifically for transparent polygons, or should I expand that be my entire rendering process.

My current rendering process:
1. Find what leaf node I am in.
2. Grab the PVS from that node (list of nodes I can potentially see)
3. Check and see if each of those nodes are in my frustum.
4. Render each texture group in each leaf node with a vertex array.

Now this works great. It renders the zone perfectly. What if I was to not render the transparent polygons on the first pass and then in a second pass, iterate through the tree with your method of traversal, and render transparent polygons. This should do it correctly in order from back to front.

Is this a good method?

Share this post


Link to post
Share on other sites
Yes that should work well, just keep the z-buffer enabled so the transparent polygons are not drawn over any opaque geometry it should be occluded by.

Share this post


Link to post
Share on other sites

Yes that should work well, just keep the z-buffer enabled so the transparent polygons are not drawn over any opaque geometry it should be occluded by.


How do I keep the Z buffer enabled? I wasn't sure it was enabled? Sorry if this is a dumb question.

Edit: The z buffer is apparently another name for depth testing which is done with:

glEnable[color="#009900"](GL_DEPTH_TEST[color="#009900"])[color="#339933"];
glDepthMask[color="#009900"](GL_TRUE[color="#009900"])[color="#339933"];


[color="#339933"]Cheers!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!