BSPTrees06

a lion in the desert : a lion in the desert How do you find a lion in the desert? How about when you have a predicate that tells you if the lion is in front or behind a separating plane?


a lion in the desert : a lion in the desert Cut the desert in two and ask in which part is the lion. Repeat the process for the part that the lion is in.


BSP Trees : BSP Trees Binary Spatial Partitioning (BSP) means: Partition (or split) a space (like the desert) into Binary (two) parts using a separating plane. Repeat the process for both resulting subspaces and you will get a BSP tree.


Occlusion : Occlusion Objects 'behind' the splitting plane cannot hide objects 'in front' of the plane, regardless the relative location of the observer.


Splitting Planes : Splitting Planes What we see in this example is a simple model with four polygons. We will choose the splitting planes so that they lay on a polygon of the model.


Creating the tree : Creating the tree We choose a splitting plane a split the space in two. Chosen Splitting Plane Associated Splitting Plane


Creating the tree : Creating the tree L Node R Node Chosen Splitting Plane Associated Splitting Plane


Creating the tree : Creating the tree Chosen Splitting Plane


Creating the tree : Creating the tree Chosen Splitting Plane


Creating the tree : Creating the tree The leaves of the tree are convex regions.


Traversing the Tree : Traversing the Tree We want to render the scene from this point of view. In what order should we render the regions?


Traversing the Tree : Traversing the Tree Test against the splitting plane Traverse the R subtree before the L subtree Rendering order: Test against the splitting plane


Creating the tree : Creating the tree Test against the splitting plane Traverse the L subtree before the R subtree Rendering order: Test against the splitting plane


Creating the tree : Creating the tree Rendering order: Traverse the L subtree before the R subtree Test against the splitting plane Test against the splitting plane


Creating the tree : Creating the tree Rendering order: Test against the splitting plane Traverse the R subtree before the L subtree Test against the splitting plane


Creating the tree : Creating the tree Rendering order: Test against the splitting plane Test against the splitting plane Traverse the L subtree before the R subtree


Convex Cells : Convex Cells The cells can be ordered back to front, or front to back.


F2B Order : F2B Order 1 2 3 4 5 6


F2B Order : F2B Order 1 2 3 4 5 6


Hidden Surface Removal : Hidden Surface Removal Display: Traverse the BSP tree back to front, drawing polygons in the order they are encountered in the traversal. Construct a BSP tree: Pick a polygon, let its supporting plane be the root of the tree. Create two lists of polygons: these in front, and those behind (splitting polygons as necessary). Recurse on the two lists to create the two sub-trees.


BSP Construction : BSP Construction 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6


BSP Trees : BSP Trees BSP-Trees are view-independent A good splitting plane minimize the number of polygon intersections, and aims at a balanced tree. How to choose the order of splitting planes during construction?


Point Location : Point Location Given p, in which cell it resides?


Ray Traversal : Ray Traversal Given R, which cells, and in which order it traverses?