07-12-2012, 12:17 PM
Clipping
clipping.pdf (Size: 477.24 KB / Downloads: 71)
Introduction
Planar clipping algorithms rank as probably the second most important type of algorithm
in computer graphics, following right behind line-drawing algorithms in importance.
Mathematically, to clip one set against another means to find their intersection.
In practice, one usually wants also to get this intersection in terms of some predefined
data structure.
This chapter discusses some of the well-known clipping algorithms along with
some newer and more efficient ones. The algorithms fall into two types: the lineclipping
algorithms, which clip single line segments against rectangular or convex
regions, and polygon-clipping algorithms.
Polygon-clipping algorithms:
Line-clipping algorithms fall into two types: those that use encoding of the endpoints
of the segment (Cohen-Sutherland) and those that use a parameterization of
the line determined by the segment (Cyrus-Beck, Liang-Barsky, and Nicholl-Lee-
Nicholl). In Section 4.6 we discuss a hybrid of the two approaches that works well for
the clipping needed in the graphics pipeline.
Frequently, one needs to clip more than one edge at a time, as is the case when
one wants to clip one polygon against another. One could try to reduce this problem
to a sequence of line-clipping problems, but that is not necessarily the most
efficient way to do it, because, at the very least, there would be additional bookkeeping
involved. The clipped figure may involve introducing some vertices that were
not present in the original polygon.
Line-Clipping Algorithms
Cohen-Sutherland Line Clipping
This section describes an algorithm that solves the following planar clipping
problem:
Given a segment [P1, P2], clip it against a rectangular window and return the clipped segment
[Q1, Q2] (which may be empty if the original segment lies entirely outside the window).
The Cohen-Sutherland line-clipping algorithm is probably the most popular of
such algorithms because of its simplicity. It starts out by encoding the nine regions
into which the boundary lines of the window divide the whole plane with a 4-bit binary
code. See Figure 3.2. If P is an arbitrary point, then let c(P) = x3x2x1x0, where xi is
either 0 or 1, define this encoding. The bits xi have the following meaning.
Liang-Barsky Polygon Clipping
This section gives a brief outline of the Liang-Barsky polygon-clipping algorithm
([LiaB83]). The algorithm is claimed to be twice as fast as the Sutherland-Hodgman
clipping algorithm. This algorithm and the next one, the Maillot algorithm, base their
success on their ability to detect turning points efficiently. Before we get to the algorithm,
some comments on turning points are in order.