Graphics Reference
In-Depth Information
typical goal was to determine the set triangles visible to the camera. None of those
algorithms are in common use today for primary visibility on triangles. They've
been replaced by the brute force
z
-buffer and by coarse hierarchical occlusion
culling. However, it is worth familiarizing yourself with the algorithms Suther-
land and Sproul surveyed for other potential applications. For example, we saw
that BSP trees [SBGS69, FKN80] were originally designed to order polygons by
depth so that they could be rendered perfectly using a variant of the painter's algo-
rithm. BSP trees became popular for computing polygon-level visibility in game
rendering engines in the 1990s and they are at the heart of a popular illumination
algorithm [Jen01] used on most CG film effects today. Instead of ordering poly-
gons for back-to-front rendering, BSP trees were found to be an effective way
of carving up 3D space for O
(
log n
)
access to surfaces and creating convex cells
between which visibility determination is efficient. We anticipate that today's vis-
ible surface algorithms and data structures will find similar new uses in another
30 years, while newer and better approaches to visibility determination evolve as
well.
Exercise 36.1:
Typically in Sutherland-Hodgman clipping, the polygon to be
clipped is small compared to the boundary polygon, and it intersects at most
one side of the boundary polygon; often the input polygon starts on the inside,
crosses the boundary, remains outside for a while, and then recrosses the same
boundary edge and returns inside. In this case, clipping an input polygon with
n
edges against a boundary with
k
edges involves generating and inserting only two
intersection points, although it involves testing
O
(
nk
)
edge pairs for intersections.
Build an example input in which there are
O
(
nk
)
intersection points computed and
inserted.
