BSP Frustum Culling
Author
I've written a BSP tree generator and it works great. I can loop through the entire tree and draw every node and everything renders great. So now I'm wanting to start doing so optimisations like frustrum culling. I've read a load of tutorials on BSP tree use and they all end with sentances like "And then just test if your camera is inside a node" without an explanation of how to do this. I'm using DirectX, so I havea camera with a position, a target, near and far clipping planes etc.
So should I just create a cube that roughly represents the viewing frustum and test if that cube is wholly on one side of a divider of a node, or spanning. Obviously if that cube is completely on one side or the other only one child node needs to be explored, and if it is spanning then both do.
My tree currently stores the dividing triangle inside the node where the divison took place. I am curious as to how to handle these rouge triangles, since I will have a triangle in every node of the tree, how do I know if each triangle needs to be drawn without doing any tests? or do I need to see if every dividing triangle is within the viewing frustum as well ?
Thanks
Chris
For each node you could generate a bounding volume, either a box or a sphere, around all triangles on the node itself and all it's children. When drawing, check to see whether this volume is entirely outside/insida the frustum. If it is, the entire subtree can be trivially rejected/accepted. This is a more or less standard technique, used in Quake for instance. You may want to check out the "Ramblings in Realtime"-articles by Michael Abrash, in the Graphics-section here on Gamedev.
I'm not sure I understand your second question entirely, but in simple terms: You can't! Using the technique described above, you can probably reject and accept large groups of triangles in relatively few tests, but this is different from doing none at all. And you still don't know which parts of your scene are occluded by other parts without additional information (PVS, portals, beam-tree etc...)
I'm not sure I understand your second question entirely, but in simple terms: You can't! Using the technique described above, you can probably reject and accept large groups of triangles in relatively few tests, but this is different from doing none at all. And you still don't know which parts of your scene are occluded by other parts without additional information (PVS, portals, beam-tree etc...)
Author
Ah that sounds like a good idea! What I meant was, during the construction of my tree I stored the polygons I choose to be the divider in the node, not in one of the child nodes. So I guess that causes problems with the bounding box idea.
Not neccesarily. During construction of the tree you know exactly which triangles will be either on the node you're constructing or on one of it's subnodes, as this is simply the list you choose the dividing plane from. So it shouldn't matter where you store the triangles.
- Detecting if the camera is inside a node: in a BSP tree, every subtree is a convex volume defined by all the nodes above it (each node contains information about a plane, and the position of each child in relationship with this plane). For each node, starting with root, detect which side of the splitting plane the camera is on. The camera then belongs to the child node that is on the same side of the splitting plane as the camera. Repeat recursively until you reach a leaf: you now have a list of nodes the camera is in.
- Easy frustum culling: when you render your tree, for each node, there will be at least one child node that your camera will not be in. For each such child node, check if the camera is facing away from the separation plane using a dot product between the camera's direction vector and the plane normal.
If the camera is looking away, don't draw the side of the plane that it doesn't see.
- Occlusion culling: when you build your BSP tree, you could add an additional step that is performed once the tree has been built. Then, for each leaf in the tree, determine which other leaves can be seen from there, using an occlusion detection of your choice. Once you got a visible-leaf-list in each leaf, "compact" it: if two adjacent leaves or nodes are visible, make their entire father node visible *instead*. You should now have a list of visible nodes for each leaf. Now, you can compact it even more: if two leaves or nodes share a portion of a list, move that portion to their parent node.
When rendering, determine the entire list of nodes that the camera is in, and from there, load the entire list of "visible" nodes, which should have been saved to the file and apply it to the nodes. Good, now you can render everything: render the root first (always visible), then, for each node (including the root) : if the node has one visible child, draw that child and only that child (you may also check for frustum culling before drawing it). If the node has no children marked as visible, draw both children (although counter-intuitive, this is because we decided to mark only their parent as visible, to save space).
- Advanced frustum culling: additional culling you can perform consists in actually checking if the frustum is inside or outside the node you are rendering. For each node, consider the plane, and the frustum (which is defined by its eight corners), and determine which sides of the plane contain frustum corners. Draw these.
The above is not optimal, it will never allow "holes" (false positive culling) but it will sometimes not cull invisible polygons (false negative). If you want polygon-perfect accuracy, you'll have to split the frustum by the splitting plane (generating more vertices) before culling children of a node.
EDIT: concerning the detection of the polygon stored in the node, if you're only drawning one child, don't draw it. If you're drawing both children, don't bother trying to clip it out, it's just a polygon.
- Easy frustum culling: when you render your tree, for each node, there will be at least one child node that your camera will not be in. For each such child node, check if the camera is facing away from the separation plane using a dot product between the camera's direction vector and the plane normal.
If the camera is looking away, don't draw the side of the plane that it doesn't see.
- Occlusion culling: when you build your BSP tree, you could add an additional step that is performed once the tree has been built. Then, for each leaf in the tree, determine which other leaves can be seen from there, using an occlusion detection of your choice. Once you got a visible-leaf-list in each leaf, "compact" it: if two adjacent leaves or nodes are visible, make their entire father node visible *instead*. You should now have a list of visible nodes for each leaf. Now, you can compact it even more: if two leaves or nodes share a portion of a list, move that portion to their parent node.
When rendering, determine the entire list of nodes that the camera is in, and from there, load the entire list of "visible" nodes, which should have been saved to the file and apply it to the nodes. Good, now you can render everything: render the root first (always visible), then, for each node (including the root) : if the node has one visible child, draw that child and only that child (you may also check for frustum culling before drawing it). If the node has no children marked as visible, draw both children (although counter-intuitive, this is because we decided to mark only their parent as visible, to save space).
- Advanced frustum culling: additional culling you can perform consists in actually checking if the frustum is inside or outside the node you are rendering. For each node, consider the plane, and the frustum (which is defined by its eight corners), and determine which sides of the plane contain frustum corners. Draw these.
The above is not optimal, it will never allow "holes" (false positive culling) but it will sometimes not cull invisible polygons (false negative). If you want polygon-perfect accuracy, you'll have to split the frustum by the splitting plane (generating more vertices) before culling children of a node.
EDIT: concerning the detection of the polygon stored in the node, if you're only drawning one child, don't draw it. If you're drawing both children, don't bother trying to clip it out, it's just a polygon.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
