Depth sorting Quake style BSP geometry

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

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 on other sites
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 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 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 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"];

[color="#339933"]Cheers!

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 24
• 43
• 75