Binary Space Partitions, or, Doom in 20 minutes
The preceding structures required the hyperplanes which
partition space to be parallel to the axes of the space. Often, it is benificial
to allow partitioning planes with arbitrary orientation.
Constructing the tree:
Consider polygons in space or line segments in the plane,
S a set of segments (or polygons, ...)
ConstructBSP( S )
if card( S ) < 1
then
create a tree T consisting of a single
leaf node storing S
return T
else
Use l( s1
) as the splitting line (or plane, ...)
S+
<- the set of elements in S on the + side of l(
s1 )
S-
<- the set of elements in S on the - side of l(
s1 )
Create node v, storing the objects in S
which intersect l( s1
)
Create a BSP tree T with root node
v, left subtree T-,
right subtree T+
return T
If the points are ordered badly, then we will get a large
tree. Below, in A, the first node in the tree contains s1, s2 and s3. In
B, each node contains only one segment.
It is hard to find a good ordering. We can settle for
randomizing the order, and hoping for the best.
BSP Trees for Ray Tracing:
It is easy to find the first object which intersects a ray,
using a BSP tree. In this case, we want to store objects in leaves of the
tree, rather than in the internal nodes.
Let v be a node, r a ray
Intersect( v, r )
if v
is leaf
then
intersect r with each object in v
and return closest or nil if none found
near = child node in half space containing the
origin of ray
far = the other child
hit = Intersect( near, r )
if hit is
nil and ray intersects plane defined by v
then
hit = Intersect( far, r )
return hit
BSP Trees for Polygons
We can represent a polygon (or polytope) with a BSP tree.
Let each face of the polygon coincide with a partitioning plane of the
tree.
Now, each node of the tree encodes a face of the polygon.
Each leaf of the tree is either inside or outside of the polygon.
It is easy to find out if a given point is inside the
polygon; put it in the tree and see if it ends up in a + or - leaf (also
have case of point exactly on a plane)
Let v be a node, p a point
point_classify( v, p
)
if v
is a leaf
return leaf's value ("in" or "out")
else
if p
is on negative side of plane( v )
return point_classify( v.left,
p )
else
if p
is on positive side of plane( v )
return point_classify( v.right,
p )
else (p is
on the plane)
l = point_classify( p, v.left
)
r = point_classify( p, v.right
)
if l
= r
else
Also can do boolean operations on polygons: union, intersection.
[Start] [Back][Next]
Douglas De Couto
decouto@graphics.lcs.mit.edu
Joshua Napoli
napoli@mit.edu
Last modified: Tue Mar 17 09:49:35 1998