Graphics Reference
In-Depth Information
Geometric intersection
Conservative intersection
Figure 37.3: (Left) The geometric intersection of a ball with a set of boxes in 2D. (Right) A
conservative result that may be more efficient to compute.
Figure 37.3, left) or conservatively to return
all
primitives containing the intersec-
tion geometry (see Figure 37.3, right). The latter is important because the inter-
sections between simple shapes may be hard to represent efficiently. For example,
consider the intersection of a set of triangles with a ball about a point light. The
intersection probably contains many triangles that are cut by the surface of the
ball. The resultant shapes are not representable as triangles. However, the render-
ing system that will use this information likely operates on triangles, since that
was the representation chosen for the underlying scene. Creating a representation
for triangles-cut-by-curves will create complexity in the system that only results
in shapes that the renderer can't directly process anyway. In this case, a conser-
vative query that returns all triangles that intersect the ball is more useful than a
precise query that returns the geometric intersection of the scene and the ball.
To make the structures useful, traditional set operations such as insert, remove,
and is-member are generally provided along with geometric intersection. The
algorithms for those tend to be straightforward applications of nonspatial data
structure techniques. In contrast, the intersection queries depend on the geometry.
They are the core of what makes
spatial
data structures unique, so we'll focus on
those.
Some of the most common methods of spatial data structures are those that are
used to find the intersection of a set of primitives with a ball (the solid interior
bounded by a sphere), an axis-aligned box, and a ray. Listing 37.1 gives a sample
C++ interface for these.
Listing 37.1: Typical intersection methods on all spatial data structures.
1
2
3
4
5
6
7
template
<
class
Value
>
class
SpatialDataStructure {
public
:
void
getBallIntersection (
const
Ball
& ball, std::vector<
Value
*
>& result)
const
;
void
getAABoxIntersection(
const
AABox& box, std::vector<
Value
*
>& result)
const
;
bool
firstRayIntersection(
const
Ray
& ray,
Value
*
& value,
float
& distance)
const
;
};