Transcript Lecture notes.

Last Time
• Octrees
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Today
•
•
•
•
Kd-trees
BSP trees
BVHs
Cell Structures (Graph-Based)
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Octree Problems
• Octrees become very
unbalanced if the objects are
far from a uniform
distribution
– Many nodes could contain no
objects
• The problem is the
requirement that cube always
be equally split amongst
children
A bad octree case
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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 – height 0
cuts on x, height 1 cuts on y, height 2 cuts on z, height 3 cuts on x, …
• Kd-trees generalize octrees by allowing splitting planes at
variable positions
– Note that cut planes in different sub-trees at the same level need not
be the same
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Kd-tree Example
4
6
1
10
8
2
11
3
13
2
3
4
5
6
7
12
8
9
5
10/02/03
1
9
7
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
10
11
12
13
Kd-tree Node Data Structure
• What needs to be stored in a node?
–
–
–
–
–
10/02/03
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 complicated in kd-trees, so typically not stored
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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?
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Kd-tree Applications
• Kd-trees work well when axis aligned planes cut things into
meaningful cells
– What are some common environments with rectilinear cells?
• View frustum culling extents trivially to kd-trees
• Kd-trees are frequently used as data structures for other
algorithms – particularly in visibility
• Specific applications:
– Soda Hall Walkthrough project (Teller and Sequin)
• Splitting planes came from large walls and floors
– Real-time Pedestrian Rendering (University College London)
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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 sometimes 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
– Big performance gains
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
BSP Example
1
1
2
2
A
3
4
out
5
7
3
6
A
C5B
out
B
6
C
8
10/02/03
out
D
out
out
• Notes:
D
4
8
7
– Splitting planes end when they intersect their parent
node’s planes
– Internal node labeled with planes, leaf nodes with
regions
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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?
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Choosing Splitting Planes
• Goals:
– Trees with few cells
– Planes that are mostly opaque (best for visibility calculations)
– Objects not split across cells
• Some heuristics:
–
–
–
–
–
–
10/02/03
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
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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 zbuffer, 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?)
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
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?
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Bounding Volume Hierarchies
• So far, we have had subdivisions that break the world into
cell
• General Bounding Volume Hierarchies (BVHs) start with a
bounding volume for each object
– Many possibilities: Spheres, AABBs, OBBs, k-dops, …
– More on these later
• Parents have a bound that bounds their children’s bounds
– Typically, parent’s bound is of the same type as the children’s
– Can use fixed or variable number of children per node
• No notion of cells in this structure
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
BVH Example
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
BVH Construction
• Simplest to build top-down
– Bound everything
– Choose a split plane (or more), divide objects into sets
– Recurse on child sets
• Can also be built incrementally
– Insert one bound at a time, growing as required
– Good for environments where things are created dynamically
• Can also build bottom up
– Bound individual objects, group them into sets, create parent,
recurse
– What’s the hardest part about this?
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
BVH Operations
• Some of the operations we’ve looked at so far work with
BVHs
– Frustum culling
– Collision detection
• BVHs are good for moving objects
– Updating the tree is easier than for other methods
– Incremental construction also helps (don’t need to rebuild the whole
tree if something changes)
• But, BVHs lack some convenient properties
– For example, not all space is filled, so algorithms that “walk”
through cells won’t work
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Cell-Portal Structures
• Cell-Portal data structures dispense with the hierarchy and
just store neighbor information
– This make them graphs, not trees
• Cells are described by bounding polygons
• Portals are polygonal openings between cells
• Good for visibility culling algorithms, OK for collision
detection and ray-casting
• Several ways to construct
– By hand, as part of an authoring process
– Automatically, starting with a BSP tree or kd-tree and extracting
cells and portals
– Explicitly, as part of an automated modeling process
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Cell Portal Example
A
B
A
• Portals can be one way
(directed edges)
B • Graph is normally stored in
adjacency list format
– Each cell stores the edges
(portals) out of it
C
D
C
D
E
F
E
F
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin
Todo
• By Monday, Oct 13, Stage 2 demo
10/02/03
CS679 - Fall 2003 - Copyright Univ. of Wisconsin