Transcript Eric Etheridge slide..

BSP Trees
Binary Space Partitioning Trees
variants from many papers
Eric Etheridge
Introduction: Space Partitionings

What are space partitionings?

Divide space semantically using a data structure

Same general goal as bounding-box hierarchies

Usually a tree structure

Nodes store or implicitly define spatial boundaries
Nodes / Cells

Nodes, or “cells”, refer to regions of space

Each object in the world is in one or more cells

Some options for data stored at a cell:


objects entirely in a cell / also those partly in a cell

data in leaves only / data in all nodes in a tree

store references to the objects in a cell

store polygons from the parts of objects in the cell
The exact data stored depends on the algorithm
Simpler Space Partitionings

Grid:

multidimensional
array over a fixed
maximum space

fixed-size cells

axis-aligned
Simpler Space Partitionings

Quad- / Oct-Trees:




tree structure over a
fixed maximum space
each node divides the
parent cell into four or
eight sub-cells
the tree is not
balanced
axis-aligned
Simpler Space Partitionings

K-D Trees




tree structure over an
unbounded space
each node divides the
parent into two cells
axis-aligned
usually rotates the
choice of dimension to
split at each level
General Space Partitioning Uses

Fast approximate object intersection detection:
possibly intersecting vs. definitely not

line / object: efficient ray-tracing

volume / object: volume culling for rendering

object / object: avoid many collision detection
checks
Binary Space Partitioning

BSP Trees




tree structure over an
unbounded space
each node divides the
parent into two cells
NOT axis-aligned
polygons that
intersects planes are
split along the plane
BSP Tree Original Purpose



Avoid the overhead of
the painter's algorithm
and Z-buffer for
graphical display
First used for this
purpose in the game
Doom by Id Software,
released in 1993
Uses trees that cut
along polygon faces
Viewpoint
1
2
3
BSP Trees For Rendering

Tree created once

Each node stores a polygon in the environment




Space is divided into 'in front' and 'behind' that
polygon
A viewpoint is chosen for rendering
The planes in the nodes are tested against the
viewpoint, each time determining the near side
Objects on near sides are before far objects
BSP Trees vs. Other Partitionings



Allows exact ordering of polygons for rendering
Able to pre-compute “visibility lists”, i.e. what
objects are visible from what locations
Less nodes are needed than for axis-aligned
structures:


http://portal.acm.org/citation.cfm?id=1115371
Allows simple Level-of-Detail approximations by
picking tree order to match detail level
Specific BSP Abilities

Simple exact object intersection, returning the
point or space of collision, many uses:

Exact ray tracing with a single data structure

Exact collision detection, single structure


And returning the volume of the collision, not just a point
Approximate intersections within specified error


Can make a partial tree that approximates an object
Number of nodes required is linear in object size,
vs. quadratic when using axis-aligned partitionings
BSP Trees vs. Other Structures


BSP Trees can quickly model or approximate
non-rectangular objects
Compare modeling a pyramid (next slides):

Axis-Aligned Bounding Boxes

Non-Axis-Aligned Bounding Boxes

Oct-Tree

BSP Tree
Non-Rectangular: AA BB
Axis Aligned Bounding Boxes
Box #
Min X
0
1
2
3
Max X Min Y Max Y Min Z
0
8
0
8
1
7
1
3
2
6
2
4
3
5
3
5
Max Z
0
2
4
6
2
4
6
8
Non-Rectangular: Grid
Grid (Whole Grid Not Depicted)
Z X Y In
0 0 0Y
0 0 1Y
0 0 2Y
0 0 3Y
0 1 0Y
0 1 1Y
0 1 2Y
0 1 3Y
0 2 0Y
0 2 1Y
0 2 2Y
0 2 3Y
0 3 0Y
0 3 1Y
0 3 2Y
0 3 3Y
Z X Y In
1 0 0Y
1 0 1Y
1 0 2Y
1 0 3Y
1 1 0Y
1 1 1Y
1 1 2Y
1 1 3Y
1 2 0Y
1 2 1Y
1 2 2Y
1 2 3Y
1 3 0Y
1 3 1Y
1 3 2Y
1 3 3Y
Z X Y In
2 0 0N
2 0 1N
2 0 2N
2 0 3N
2 1 0N
2 1 1Y
2 1 2Y
2 1 3N
2 2 0N
2 2 1Y
2 2 2Y
2 2 3N
2 3 0N
2 3 1N
2 3 2N
2 3 3N
Z X Y In
3 0 0N
3 0 1N
3 0 2N
3 0 3N
3 1 0N
3 1 1Y
3 1 2Y
3 1 3N
3 2 0N
3 2 1Y
3 2 2Y
3 2 3N
3 3 0N
3 3 1N
3 3 2N
3 3 3N
Non-Rectangular: Oct-Tree
Oct
Bas e
ULF
URF
ULR URR
LLF
LRF
LLR
LRR
LRF
LLR
LRR
S ubOct
ULF
URF
ULR URR
LLF
Non-Rectangular: BSP Tree
BS P
Left Child: Ins ide
Right Child: Outs ide
(arbitrary choice)
Bas e
Note: This tree is an
EXACT model.
X
Back
X
Front
X
Left
X
Right
X
X
Creating BSP Trees

Usually done by pre-processing

Artist does not have to specify anything

When splitting an object, it must be a hull

Needs a clear 'inside' and 'outside' for intersection

Does not have to be convex

When splitting space, objects are often not split

Heuristics used to make nearly-optimal trees

(Perfect Binary Decision Trees are NP-Complete)
BSP Trees: Intersection Basics

Intersection types:

Return Values:

Point


Ray


Plane

Bounding Box

BSP Tree / BSP Tree

Simple Yes / No
Contents lists for
intersected cells
Exact space of the
intersection
Some Other BSP Applications

medical image compression:


shadow computation:


http://portal.acm.org/citation.cfm?id=949685.94971
4
http://portal.acm.org/citation.cfm?id=199412
general set operations on polyhedra:

http://portal.acm.org/citation.cfm?id=97880.97892
BSP Tree Limitations


Deformation of objects stored in a BSP Tree:

Deformations move polygons across planes

Can't recompute the tree or re-cut faces quickly

Exact collision using BSP Trees is impractical
Moving objects stored in a BSP Tree:

Simple BSP Tree algorithms do not handle this well

Complex algorithms can:

http://portal.acm.org/citation.cfm?id=97880.97892
BSP Tree General References

Compiled BSP Tree FAQ:


“Classic” BSP Tree Starting Point Mentioned:


http://portal.acm.org/citation.cfm?id=807481
Bruce Naylor's Doctoral Thesis at UTD:


ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
http://portal.acm.org/citation.cfm?id=909951
Wikipedia Article:

http://en.wikipedia.org/wiki/Binary_space_partitioning