Transcript Material Chart and Spatial Data Structures

Spatial Data Structures
Jason Goffeney, 4/26/2006
from
Real Time Rendering
Material Recipes
• As previously mentioned there are several
different components used in the creation
of a material for an object
– Ambient
– Diffuse
– Specular
– Shininess
– Emissive
Material Recipes
Use
Shininess
value
times 128
Spatial Data Structures
• One of the important topics for performing
real time graphics applications are data
structures for efficient queries to do:
– Graphics Culling
– Intersection Testing
Spatial Data Structure
• Spatial Data Structures organize geometry
in some n - dimensional space (generally
2 or 3 but can work in higher dimensional
space).
• The list is the simplest data structure and
fairly slow for large data sets but
reasonable for smaller ones.
Spatial Data Structures
• Most spatial data structures are
hierarchical as a tree like structure nested
and recursive.
• Searching a list is O(n) while searching a
tree is O(log n).
• Usually constructing a spatial data
structure is fairly slow and is done as
preprocessing.
Spatial Data Structures
• There are several types of spatial data
structures:
– Bounding Volume Hierarchies
– BSP Trees
– Octrees
– Scene Graphs
Bounding Volume Hierarchies
• The most common
bounding volume is the
bounding box.
• Other common types are
sphere and cylinders.
• The idea is that the
bounding volume is
simpler than the more
complex shapes it
contains.
Bounding Volume Hierarchies
• A Bounding Volume Hierarchy (BVH) is the
most common kind of spatial data
structure for rendering real-time 3-d
scenes.
• Each object in a scene is bound by a
volume and then groups of objects are
bounded and eventually the entire scene
is bounded.
Bounding Volume Hierarchies
Root
Simple Scene of Objects
Tree of Objects
Bounding Volume Hierarchies
• For a tree where each node has k children
then the height of the tree is logk n where n
is the number of nodes in the tree.
• A binary tree is the simplest choice but a
higher number of children per node can
give slightly better results.
Bounding Volume Hierarchies
• In the example of ray casting you search
each subtree recursively.
If the ray hits the outer volume check
each the children
If a child node is not hit
then skip the rest of its
subtree
Bounding Volume Hierarchies
• Speed up comes from simple intersection
tests with bounding volumes and also from
culling subtrees
• If objects move around then first check is it
still fits in its current bounding volume.
Otherwise remove it and change the
parent bounding volume and drop the
node in the root of the tree and reinsert it.
Binary Space Partitioning Trees
• These trees are created by using a plane
to split space into two pieces and sorting
the geometry into each side.
• There are two flavors of BSP trees.
– Axis-Aligned
– Polygon-Aligned
Binary Space Partitioning Trees
• Axis-Aligned BSP Tree
– The whole scene is enclosed in an axisaligned bounding box (AABB).
– The idea is to subdivide that box into smaller
and smaller boxes.
– For each split an axis is chosen and a plane
perpendicular to that axis is generated that
divides the space into two boxes
Binary Space Partitioning Trees
0
0
1a
2
0
1a
1b
1b
Binary Space Partitioning Trees
0
2
0
1b
1a
1b
1a
2
Binary Space Partitioning Trees
• Axis-Aligned BSP Tree
– Space is usually split until some criteria has
been reached (height of tree)
– One of the strategies of splitting is to rotate
through the axes each turn.
– One of the benefits of the BSP tree is that it
provides a rough front to back sorting based
on the position of the viewer.
Binary Space Partitioning Trees
x2
• Traverse the tree by first moving down the subtrees
defined by the side of the plane the user is one.
2
0
y1a
1a
1b
• For plane 0 is the viewer’s x position > x0?
y1b
- Yes, so take right subtree.
• For plane 1b is viewer’s y position > y1b?
- No, so take the left subtree.
x0
• Test against objects in that subtree and go back to
parent if no collision.
Binary Space Partitioning Trees
• Polygon-Aligned BSP Trees
– In this version a polygon from the scene is
chosen and the plane it lies in becomes the
splitting plane.
– The other polygons in the scene are divided
by the plane and any polygons the plane
intersects are cut by the plane
Binary Space Partitioning Trees
C
A
B
A
A
B
F
C
C
G
D
B
E
A
D
E
F
G
Binary Space Partitioning Trees
• Polygon-Aligned BSP Trees
– Constructing this kind of tree is very
expensive and is general done and then
saved in a file.
– Traversing this tree based on the position of
the camera will provide a strict back to front
(or front to back) sorting of the polygons
Binary Space Partitioning Trees
F
• Determine which side of the plane the
camera lies on by a point/plane comparison
C
G
B
D
A
• The polygon set on the far side of the plane is
is beyond the near side set
E
• From the far side set again do the comparison
and determine the far side of its splitting plane
A
B
D
• Back to front order is for this example is:
F - G- A - D - B- E
C
E
F
• This does not tell which polygon is closest but
which polygon occludes (hides) another polygon.
G
Octrees
• Similar to an AA-BSP tree a box is split
simultaneously along all 3 axes and the
split point is in the center of the box
creating 8 new boxes.
• Enclose the entire space in an AABB and
split until you meet a stopping criteria.
• The 2D version of the octree is the
quadtree.
Octrees
Objects that cross boundaries are either:
• Split
• Stored in multiple nodes
• Stored in the largest box that contains it
Scene Graphs
• BVHs, BSP tree and Octrees all use some
sort of tree to partition space and store
geometry.
• Scene graphs are higher level structures
that that are augmented with textures,
transforms, levels-of-detail, material
properties, light sources, etc.
Scene Graphs
• Every graphics application has some sort
of scene graph even if it is a root node
with a set of children to display.
• A node in a scene graph often has a
bounding volume while leaves store
geometry.
• A leaf may contain an entire spatial data
structure (such as a BSP Tree) to encode
the geometry.
Scene Graphs
• Transformations can be placed in any
internal node and effects the entire
subtrees of that node.
Draw the star
Save the current matrix
Apply a rotation
Draw Planet One
Save the current matrix
Apply a second rotation
Draw Moon A
Draw Moon B
Reset the matrix we saved
Draw Planet two
Save the current matrix
Apply a rotation
Draw Moon C
Draw Moon D
Reset the matrix we saved
Reset the matrix we saved
Scene Graphs
• A single leaf node can have multiple
parents.
Car Chassis
Transform
Transform Transform Transform
Wheel
Scene Graph
• Maintenance
– The most intuitive method is to alter a scene
graph through a GUI (Maya, 3DMax)
– Otherwise design a scripting “language” to
insert and delete nodes from the graph
Scene Graphs
• Open Source Scene Graphs:
– Open Scene Graph
– Open SG
• These are two semi-competing scene
graphs which have somewhat specialized.
References
• Tomas Akenine-Moller and Eric Haines.
Real Time Rendering. 2nd Edition. A. K.
Peters. 2002.
• http://www.gamedev.net/reference/progra
mming/features/scenegraph/