Clipping Lines – Cohen-Sutherland
Graphics Tutorial
By Hexar
Introduction
Now that we already know how to scan-convert lines using the
Bresenham/Midpoint algorithm, it's going to be useful to know how to clip them
against a rectangular screen or viewport so that we can draw lines with any
endpoints and avoid writing outside of our window.
Problem
It’s relatively easy to modify the Bresenham algorithm to take into consideration
the x,y coordinates and to not write pixels outside of XMIN – XMAX or YMIN –
YMAX. Unfortunately that's not an optimal solution; surely there's an easier way
to clip lines.
Figure 1. Clipping Cases
There are four basic cases to cover:
1) Green – Line is completely inside window
2) Blue – Line is completely outside window
3) Purple – Line has one intersection with window
4) Red – Line has two intersections with the window
Parametric Equations of Lines
Most of us are familiar with the line equation
b
mx
y
+
=
. Another way to define
a line is via two separate equations that describe both x and y over time t. If the
line segment goes from (x1, y1) to (x2, y2) then we can define x and y as a
function of time t (
1
0
≤
≤ t
):
)
1
2
(
*
1
x
x
t
x
x
−
+
=
)1
2
(
*
1
y
y
t
y
y
−
+
=
Figure 2. Parametric Line
Left-Clip
Given these parametric equations, let's perform a left-clip on our window; x = u1.
For now assume that x2 > x1.
)
1
2
(
*
1
1
x
x
t
x
u
x
−
+
=
=
1
2
1
1
x
x
x
u
t
−
−
=
Now, if t is less than zero or more than one, then the line doesn't even cross the
left clip boundary and no clip is performed. Otherwise, plug this in to y and you
get:
)
1
2
(
*
1
2
1
1
1
y
y
x
x
x
u
y
yClip
−
−
−
+
=
Then simply replace (x1, y1) with (u1, yClip).
Cohen-Sutherland
The left-clipping we just performed was a good start, but we have to clip against
four different boundaries, even when the clipping is unnecessary. The Cohen-
Sutherland algorithm eliminates these unnecessary tests by assigning bitcodes