cs638 12

Today : Today Kd-trees BSP Trees


Kd-trees : Kd-trees A kd-tree is a tree with the following properties Each node represents a rectilinear region (faces aligned with axes) Each node is associated with an axis aligned plane that cuts its region into two, and it has a child for each sub-region The directions of the cutting planes alternate with depth First cut perpendicular to x-axis, then perpendicular to y, then z and then back to x (some variations apparently ignore this rule) Kd-trees generalize octrees by allowing splitting planes at variable positions Note that cut planes in different sub-trees at the same level do not have to be the same


Kd-tree Example : Kd-tree Example 1 1 2 3 2 3 4 5 6 7 4 5 6 7 8 9 10 11 12 13 8 9 10 11 12 13


Kd-tree Node Data Structure : Kd-tree Node Data Structure What needs to be stored in a node? Children pointers (always two) Parent pointer - useful for moving about the tree Extents of cell - xmax, xmin, ymax, ymin, zmax, zmin List of pointers to the contents of the cell Neighbors are useful in some algorithms Typically only store neighbors at leaf nodes Cells can have many neighboring cells


Building a Kd-tree : Building a Kd-tree Define a function, buildNode, that: Takes a node with its cell defined and a list of its contents Sets the splitting plane, creates the children nodes, divides the objects among the children, and recurses on the children, or Sets the node to be a leaf node Find the root cell (how?), create the root node and call buildNode with all the objects When do we choose to stop creating children? What is the hard part?


Choosing a Splitting Plane : Choosing a Splitting Plane Two common goals in selecting a splitting plane for each cell Minimize the number of objects cut by the plane Balance the tree: Use the plane that equally divides the objects into two sets (the median cut plane) One possible global goal is to minimize the number of objects cut throughout the entire tree (intractable) One method (assuming splitting on plane perpendicular to x-axis): Sort all the vertices of all the objects to be stored according to x Put plane through median vertex, or locally search for low cut plane


Kd-tree Applications : Kd-tree Applications Kd-trees work well when axis aligned planes cut things into meaningful cells What are some common environments with rectilinear cells? Everything you can do with octrees you an also do with kd-trees View frustum culling Fast ray intersections … Specific applications: Soda Hall Walkthrough project (Teller and Sequin) Splitting planes came from large walls and floors Real-time Pedestrian Rendering (University College London)


BSP Trees : BSP Trees Binary Space Partition trees A sequence of cuts that divide a region of space into two Cutting planes can be of any orientation A generalization of kd-trees, and sometime a kd-tree is called an axis-aligned BSP tree Divides space into convex cells The industry standard for spatial subdivision in game environments General enough to handle most common environments Easy enough to manage and understand Easy to hack and fool to improve performance


BSP Example : BSP Example Notes: Splitting planes end when they intersect their parent node’s planes Internal node labeled with planes, leaf nodes with regions 1 4 2 3 7 5 B A out 8 D out 6 C out 1 2 3 4 5 6 7 8 out A out B C D


BSP Tree Node Data Structure : BSP Tree Node Data Structure What needs to be stored in a node? Children pointers (always two) Parent pointer - useful for moving about the tree If a leaf node: Extents of cell How might we store it? If an internal node: The split plane List of pointers to the contents of the cell Neighbors are useful in many algorithms Typically only store neighbors at leaf nodes Cells can have many neighboring cells Portals are also useful - holes that see into neighbors


Building a BSP Tree : Building a BSP Tree Define a function, buildNode, that: Takes a node with its cell defined and a list of its contents Sets the splitting plane, creates the children nodes, divides the objects among the children, and recurses on the children, or Sets the node to be a leaf node Create the root node and call buildNode with all the objects Do we need the root node’s cell? What do we set it to? When do we choose to stop creating children? What is the hard part?


Choosing Splitting Planes : Choosing Splitting Planes Goals: Trees with few cells Planes that are mostly opaque (best for visibility calculations) Objects not split across cells Some heuristics: Choose planes that are also polygon planes Choose large polygons first Choose planes that don’t split many polygons Try to choose planes that evenly divide the data Let the user select or otherwise guide the splitting process Random choice of splitting planes doesn’t do too badly


Drawing Order from BSP Trees : Drawing Order from BSP Trees BSP tress can be used to order polygons from back to front, or visa-versa Descend tree with viewpoint Things on the same side of a splitting plane as the viewpoint are always in front of things on the far side Can draw from back to front Removes need for z-buffer, but few people care any more Gives the correct order for rendering transparent objects with a z-buffer, and by far the best way to do it Can draw front to back Use info from front polygons to avoid drawing back ones Useful in software renderers (Doom?)


BSP in Current Games : BSP in Current Games Use a BSP tree to partition space as you would with an octree or kd-tree Leaf nodes are cells with lists of objects Cells typically roughly correspond to “rooms”, but don’t have to The polygons to use in the partitioning are defined by the level designer as they build the space A brush is a region of space that contributes planes to the BSP Artists lay out brushes, then populate them with objects Additional planes may also be specified Sky planes for outdoor scenes, that dip down to touch the tops of trees and block off visibility Planes specifically defined to block sight-lines, but not themselves visible


Dynamic Lights and BSPs : Dynamic Lights and BSPs Dynamic lights usually have a limited radius of influence to reduce the number of objects they light The problem is to find, using the BSP tree, the set of objects lit by the light (intersecting a sphere center (x,y,z) radius r) Solution: Find the distance of the center of the sphere from each split plane What do we do if it’s greater than r distance on the positive side of the plane? What do we do if it’s greater than r distance on the negative side of the plane? What do we do if it’s within distance r of the plane? Any leaf nodes reached contain objects that might be lit


BSP and Frustum Culling : BSP and Frustum Culling You have a BSP tree, and a view frustum With near and far clip planes At each splitting plane: Test the boundaries of the frustum against the split plane What if the entire frustum is on one side of the split plane? What if the frustum intersects the split plane? What do you test in situations with no far plane? What do you do when you get to a leaf?