Graphics Reference
In-Depth Information
CHAPTER 3
Clipping
Prerequisites: Basic vector algebra
3.1
Introduction
Planar clipping algorithms rank as probably the second most important type of algo-
rithm in computer graphics, following right behind line-drawing algorithms in impor-
tance. 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 prede-
fined 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 line-
clipping algorithms, which clip single line segments against rectangular or convex
regions, and polygon-clipping algorithms, which clip whole polygons against other
polygons. The following terminology is used:
Definition. The polygon being clipped is called the subject polygon and the polygon
that one is clipping against is called the clip polygon.
The choice of algorithms to discuss was motivated by the following
considerations:
(1) It is currently one of the best algorithms of its type.
(2) It is not the best algorithm but still used a lot.
(3) The algorithm was interesting for historical reasons and easy to describe.
(4) It involved the use of some interesting techniques, even though it itself is no
longer a recommended method.
Below we list the algorithms described in this chapter and categorize them by con-
siderations (1)-(4) above. We also state any assumption regarding their clip polygon
and make some comments about them. Some of the algorithms will be discussed in
great detail. Others are only described very briefly, especially if they fall under heading
(3) or (4) above.
Search WWH ::




Custom Search