Transcript Game Programming Practice

Hierarchical Data
Structure in Game
Programming
Yanci Zhang
Game Programming Practice
Outline
 Overview of hierarchical data structures
 Spatial partition
 Bounding volume hierarchies
Game Programming Practice
Basic Data Structures
 STL and Boost provide excellent implementations for
most of basic data structures
 Dynamic array, list, queue, hash table, graph…
 Do not implement these data structures by yourself
 Basic data structures are far from meeting all the
requirements in game programming
Game Programming Practice
Tree and Graph
 Bases for many advanced data structures in game
programming
 Typical applications





Scene graph
State graph
Decision tree
Kd-tree, quad tree
…
Game Programming Practice
Hierarchical Data Structure
 Tree data structure
 Organize spatial data to implement querying, searching
efficiently
 Widely used in game: collision detection, ray tracing…
 An example in our daily life
 University -> College -> Grade -> Major
Game Programming Practice
Example 1/2
 Task: find the closest intersection between a ray and
multiple objects
 Solution1: for-loop
t_min = MAX_FLT;
FOR EACH object
{
float t = computeIntersection(object);
if (t < t_min) t_min = t;
}
 Simple
 Low efficiency
Game Programming Practice
Example 2/2
 Solution2: organize objects wisely
 Complicate solution
 High efficiency
 Not necessary to compute intersections
between ray and all objects
 Early exit
Game Programming Practice
Two Ways to Build HDS
 Spatial partition
 Typical data structures: quadtree, octree, BSP, KD-tree…
 Object-based partition
 Typical data structures: AABB, OBB…
Game Programming Practice
Spatial Partition
 Partition the space occupied by objects
 Uniform partition
 Adaptive partition
 One object might belong to multiple nodes
Game Programming Practice
Object-based Partition
 Partition according to objects themselves
 Space occupied by objects might overlap
Game Programming Practice
Quadtree
 Each node has 4 children nodes at most
 Features
 Uniform partition
 Not balanced
Game Programming Practice
Example: Terrain Rendering
 Terrain rendering is very important in many games
 Size of terrain data is always huge
 Inefficient to render all terrain data
 How to cull invisible parts?
Game Programming Practice
Culling
 Suppose terrain is divided to 16x16 blocks
 Solution 1: check every block one by one
 All blocks have to be checked
 Very inefficient
Game Programming Practice
Building Quadtree 1/2
 Solution 2: use quadtree to organize data
 Uniformly divide terrain to four sub-blocks
 Root node with four children nodes
1
2
3
4
5
Game Programming Practice
Building Quadtree 2/2
 Keep dividing each children node
 Until each child node only contains one block
Game Programming Practice
Culling With Quadtree 1/3
 Node 2,3,4 are invisible
 Not necessary to check offspring nodes of 2,3,4
 Node 5 is visible
 Keep testing children node of 5
1
2
3
4
5
Game Programming Practice
Culling With Quadtree 2/3
 Node a, b, c are invisible
 Not necessary to check offspring nodes of a,b,c
 Node d is visible
 Keep testing children node of d
5
a
b
c
d
Game Programming Practice
Culling With Quadtree 3/3
 Continue check node d until leaf nodes are reached
 Performance comparison
 Solution 1: 16*16 = 256 visibility tests
 Solution 2: 1 + 4 + 4 + 16 = 29 visibility tests
Game Programming Practice
Route Planning With Quadtree
 Adaptively build quadtree
 Connect centers of empty block to form a graph
 Route planning based on graph
Game Programming Practice
Octree
 Quadtree is defined in 2D space
 Extend quadtree to 3D space to get octree
 Each node has 8 children nodes at most
 Uniform subdivision
Game Programming Practice
Disadvantages
 Produce very unbalanced tree from unevenly
distributed objects
 Consequence of uniform subdivision
 High memory cost
 Lots of wasted memory because
empty space
Game Programming Practice
KD-tree
 Stands for K-Dimensional Tree
 Organize data stored in k-dimensional space
 Use a clever way to split space
 Quadtree/Octree: fixed split strategy (uniform subdivision)
 KD-tree: determine split according to data distribution
 Widely adopted in ray tracing, collision detection
Game Programming Practice
KD-tree
 Binary tree
 Every non-leaf node split its space to two sub space by
a split plane
 Split plane is perpendicular to some axis
X
Y
Game Programming Practice
Building KD-tree
 Determine a split axis and split position p
 Split space occupied by current node into two subspace
 Split plane is a hyper plane in K-dimensional space which is
perpendicular to the split axis
 Suppose X axis is chosen as split axis
 Object belongs to left child if its x coordinate is smaller than px
 Object belongs to right child if its x coordinate is larger than px
Game Programming Practice
Building KD-tree: Example
4
6
1
10
8
2
11
3
13
2
3
4
5
6
7
12
8
9
5
1
9
10
11
12
13
7
Game Programming Practice
Building KD-tree: Example
Game Programming Practice
Building KD-tree
 How to determine split axis?
 Use every axis in turn
 Choose the longest axis
 Not necessary to use the same axis for brother nodes
 How to determine split position?
 Center of split axis
 Center of data inside current node
 Make the number of data in two children node equal
 When to stop splitting?
Game Programming Practice
KNN Query
 KNN: K-Nearest Neighbor
 Given data set P{p1,p2,…} in N-dimensional space, find
the k-closest points in P to point q
 Widely used in many applications (like fluid simulation)
 Consider a simplified problem: K=1, N=2
 Two solutions
 Quadtree
 KD-tree
Game Programming Practice
Solution 1: Quadtree
R = ∞;
stack.push(RootNode);
While (!stack.empty()) {
T = stack.pop();
for each children nodes C of T {
if (C is leaf node) {
d = minimum distance from q to points in C;
if (d < R) R = d;
}
else {
if (C has intersection with circle centered at q with
radius R)
stack.push(C);
}
}
}
Game Programming Practice
Solution 2: KD-tree 1/4
 Start from root node A
 Depth-first traversal
 Initial estimation of the nearest distance Dmin = dis(q, A)
Game Programming Practice
Solution 2: KD-tree 2/4
 Check left child node B
 d = dis(q, B)
 Dmin is updated to d because d < Dmin
 Check children nodes of B (left to right)
Game Programming Practice
Solution 2: KD-tree 3/4
 Check left child node D
 d = dis(q, D)
 Dmin is not updated because d > Dmin
 D is a leaf node, then E is checked
Game Programming Practice
Solution 2: KD-tree 4/4
 Check for left sub-tree of A is finished
 The region occupied by right sub-tree of A has no
intersection with the best-estimate sphere
 The whole right sub-tree can be safely ignored
Game Programming Practice
BSP Tree 1/2
 BSP = Binary Space Partition
 Binary tree
 Similar to KD-tree, using a hyper-plane to split current
space into two sub-space
 Different from KD-tree, hyper-plane is not required to
perpendicular to axis
Game Programming Practice
BSP Tree 2/2
 Selection of hyper-plane is very important
 Build a good BSP tree is not easy
 Choosing best hyper-plane from multiple candidates
 Not suitable for dynamic scene
Game Programming Practice
Summary: Space Partition
 Organize data by partitioning space
 The whole sub tree is skipped if its root fails test
 Different partition methods produce different data
structures
 Fixed partition way: quadtree, octree
 Perpendicular to axis: KD-tree
 Arbitrary way: BSP-tree
 One object may belong to different nodes
Game Programming Practice
Object-based Partition
 Core idea: bounding volume
 Typical application: collision detection
 Input: objects A, B representing by two triangle sets
respectively S={S1,S2,…,Sn｝and T=｛T1,T2,…,Tm}
 Question: How to efficiently determine whether A collides
with B?
 Simple solution: check all {Si, Tj} pairs
 Better solution: use bounding volume technique to accelerate
Game Programming Practice
How to Choose BV
 Conflict targets
 Bound objects as tight as possible
 Low update cost when objects are moved or deformed
 Fast intersection test
Game Programming Practice
Bounding Volume Tree
 Binary tree
 How to create?
 Root node is the bounding volume for whole object
 Recursively split object in current node to two sub-objects
 Create two children bounding volume for the two sub-objects
Game Programming Practice
Bounding Sphere
 The sphere enclosing object with minimum radius
 Features
 Good: quick intersection test
 Bad: Not tight enough
 Representation: center point c and radius r
Game Programming Practice
AABB
 AABB = Axis Aligned Bounding Box
 Features
 Good: quick intersection test
 Bad: cannot rotate with objects, not tight enough…
 Representation: min and max values along each axis
Game Programming Practice
OBB
 OBB = Oriented Bounding Box
 Features
 Arbitrary orientation
 No recomputation when object is rotated
 More expensive to construct
Game Programming Practice
OBB Construction
 Top-down construction
 Root node: OBB for whole object
 Split plane:
 Perpendicular to the longest axis of current OBB
 Pass the center of OBB
Game Programming Practice
How to Determine OBB Axis
 Want OBB to be aligned with the best fit plane of
model
 Achieve this by examining the principle components of
statistical distribution of geometry
 PCA: Principle Component Analysis
 A very important feature extraction method in patter
recognition field
Game Programming Practice
Feature Extraction
 Object/Data is represented by features
 Number of features is too big to analysis
 Can we reduce the number of features so that the
smaller number still represents the data accurately?
 Definition of accurate representation: the large feature
vector can be reconstructed from small one with a
small error in the least square sense
Game Programming Practice
Principle Component Analysis
 D-dimensional feature vectors x
 Transform x to y= A(x -μ) where μ is the mean of all x
 A is a M x D orthogonal matrix, with M < D so y is an
M-dimensional vector
 Reconstruct x by xappr= μ+ Aty
 For which A is E[||x-xappr||2] minimal?
Game Programming Practice
Principle Component Analysis
 If we want to represent this 2-D data by 0-D data (a
point), which point is the best?
Game Programming Practice
Principle Component Analysis
 So the 0-D best representation of a data set, in terms of
least square error, is the mean
Game Programming Practice
Principle Component Analysis
 If we want to represent this 2-D data by 1-D data (a
line), which line is the best?
 It must be a line going through the mean
Game Programming Practice
Computing OBB Axis
 Input: 3D point set P{p1,p2,…,pn}
 Compute the mean of point set
1 n k
m i   pi
n k 1
 Compute covariance matrix C
1 n
Cij   (( pik  mi )( p kj  m j ))
n k 1
Game Programming Practice
Computing OBB Axis
 Compute eigenvalues λ of C
| λE - C | =0
 Compute eigenvectors X
(λE – C)X = 0
 Three eigenvectors are OBB’s axes
Game Programming Practice
Issues
Game Programming Practice
Exercises
 Implement a binary tree CBinaryTree with the following
functions:
 Add child to the specified node;
 Get child of the specified node;
 Implement a KD-tree, which is derived from CBinaryTree
 Implement a AABB tree, which is derived from CBinaryTree
Game Programming Practice