Clipping
December 8, 2021 1
Learning outcomes for this lecture
You will
understand
What is meant by ‘clipping’
2D clipping concepts
3D clipping concepts
Different kinds of clipping
The Cohen-Sutherland 2D region-coding clipping technique
Be able to
calculate Cohen-Sutherland 2D region-coding
Clipping means
Identifying portions of a scene that are inside (or outside) a
specified region
December 8, 2021 2
Requirements for clipping
Is (x, y) inside or outside a given region
For 2D graphics the region defining what is to be
clipped is called
The clip window
Clip window
December 8, 2021 3
Interior and exterior clipping
interior clipping
what is to be saved is inside the clip window
exterior clipping
what is to be saved is outside clip window
Interior clipping
- keep point P2
P2
(x2, y2)
December 8, 2021 4
Interior and exterior clipping
Exterior clipping Clip window
- keep point P1
P1
(x1, y1)
We shall assume interior clipping for now
But you must be aware of exterior clipping too
December 8, 2021 5
Overview of types of clipping
All-or-none clipping
If any part of object outside clip window
whole object is rejected
Point clipping
Only keep points inside clip window
Line clipping
Only keep segment of line inside clip window
Polygon clipping
Only keep sub-polygons inside clip window
December 8, 2021 6
Before and after POINT clipping
Before P2
P3 P1
P4
After
P3 P1
December 8, 2021 7
Before and after LINE clipping
Before P2
After P1
P2’
P1’
December 8, 2021 8
Before and after POLYGON clipping
Before
After
December 8, 2021 9
Cohen-Sutherland 2D clipping
4 regions are defined – outside the clip window
TOP
BOTTOM
LEFT
RIGHT P2
P1
December 8, 2021 10
The 4-bit codes
A 4-bit code is assigned to each point
This code is sometimes called a Cohen-
Sutherland region code
LEFT bit 1 = binary 0001
RIGHT bit 2 = binary 0010
BOTTOM bit 3 = binary 0100
TOP bit 4 = binary 1000
So a point coded 0001 is LEFT of the clip window, etc.
December 8, 2021 11
Cohen-Sutherland region codes
The point (65, 50) is above and to the right of the
clip window,
Therefore gets the code: 1010
(65, 50)
(10, 40)
(60, 40)
(10, 10) (60, 10)
December 8, 2021 12
Cohen-Sutherland region codes
1000 indicates the TOP region
0010 indicates the RIGHT region
the 4 bit Cohen-Sutherland code
is formed by a logical OR of all region codes
1000 TOP
OR 0010 RIGHT
------------------
= 1010
December 8, 2021 13
How the codes are useful
Why bother encoding points with 4-bit Cohen-Sutherland
region codes?
Can make some quick decisions
If code is zero (0000) point is inside window
If code is non-zero point is outside window
For the two endpoints of a line
If codes for both endpoints are zero,
whole line is inside window
If (logical) AND of codes for endpoints is non-zero,
the endpoints must have a region in common …
So the whole line must be outside clip window
December 8, 2021 14
Some lines and their endpoint codes
TOP BOTTOM RIGHT LEFT
Line1 codes are 1001 and 0000
Line2 codes are 0000 and 0000 << inside
Line3 codes are 1000 and 0100
Line4 codes are 1010 and 0110 << outside
Line1
Line4
Line2
Line3
December 8, 2021 15
Clipping from region codes
To clip a line based on region codes:
Choose an endpoint that is OUTSIDE clip window (I.e.
non-zero code)
Check first bit (TOP) – if set, clip intersection from point
to TOP of clip window
Check second bit (BOTTOM) and so on
December 8, 2021 16
Line Clipping Algorithms
Goal: avoid drawing primitives that are outside the
viewing window.
The most common case: clipping line segments
against a rectangular window
December 8, 2021 17
Line Clipping Algorithms
Three cases:
Segment is entirely inside the window - Accept
Segment is entirely outside the window - Reject
Segment intersects the boundary - Clip
December 8, 2021 18
Point Classification
How can we tell if a point is inside a rectangular
window?
ymax
ymin
xmin xmax
December 8, 2021 19
Line Segment Clipping
If both endpoints are inside the window, the entire
segment is inside: trivial accept
If one endpoint is inside, and the other is outside,
line segment must be split.
What happens when both endpoints are outside?
December 8, 2021 20
Cohen-Sutherland Algorithm
Assign a 4-digit binary outcode to each of the 9
regions defined by the window:
1001 1000 1010
ymax
0001 0000 0010
ymin
0101 0100 0110
xmin xmax
December 8, 2021 21
Cohen-Sutherland Algorithm
1001 1000 1010
bit condition
ymax
1 y > ymax
0001 0000 0010
2 y < ymin
ymin
3 x > xmax
0101 0100 0110
4 x < xmin
xmin xmax
December 8, 2021 22
Cohen-Sutherland Algorithm
Compute the outcodes C1 and C2 corresponding to
both segment endpoints.
If ((C1 | C2) == 0): Trivial Accept
If ((C1 & C2) != 0): Trivial Reject
Otherwise, split segment into two parts. Reject one
part, and repeat the procedure on the remaining
part.
What edge should be intersected ?
December 8, 2021 23
Example
D
C
ymax
B
Outcode(A) = 0000 A
ymin
Outcode(D) = 1001
No trivial accept/reject xmin xmax
Clip (A,D) with y = ymax, splitting it into (A,B) and (B,D)
Reject (B,D)
Proceed with (A,B)
December 8, 2021 24
Example
E
ymax
C D
Outcode(A) = 0100
B ymin
Outcode(E) = 1010
No trivial accept/reject xmin A xmax
Clip (A,E) with y = ymax, splitting it into (A,D) and (D,E)
Reject (D,E)
Proceed with (A,D)
December 8, 2021 25
Example
ymax
C D
Outcode(A) = 0100
B ymin
Outcode(D) = 0010
No trivial accept/reject xmin A xmax
Clip (A,D) with y = ymin, splitting it into (A,B) and (B,D)
Reject (A,B)
Proceed with (B,D)
December 8, 2021 26
Example
ymax
C D
Outcode(B) = 0000
B ymin
Outcode(D) = 0010
No trivial accept/reject xmin xmax
Clip (B,D) with x = xmax, splitting it into (B,C) and (C,D)
Reject (C,D)
Proceed with (B,C)
December 8, 2021 27
Clipping a line
Choose point P2 (code is 1000)
P2
P1
Clip from point to TOP of clip window
P1
December 8, 2021 28
Clipping a line
Choose point P1 (code is 0110)
Bit 1 (TOP) not set P1
Bit 2 (BOTTOM) set – so clip bottom
December 8, 2021 29
Clipping a line
Bit 3 (RIGHT) set – so clip right
Bit 4 (LEFT) not set – so clipping finished
December 8, 2021 30
How to clip a line
Need to know
xmin
End points of line
(x1, y1) – (x2, y2)
(x2, y2)
X or Y value defining (x1, y1)
clip window edge
(newx, newy)
(similar triangles and line gradient)
m = (y2 – y1) / (x2 – x1); // (gradient)
newx = xwmin;
newy = y1 + m*(xwmin – x1)
December 8, 2021 31
Clipping Lines
(xl, yt) (xr, yt)
A point is visible if
(x, y) xl < x < xr
and
yb < y < yt
(xl, yb) (xr, yb)
A line is completely visible if both of its end points are in the window.
Brute Force Method - Solve simultaneous equations for intersections
of lines with window edges.
December 8, 2021 32
Cohen-Sutherland Clipping
Region Checks: Trivially reject or accept lines and points.
Fast for large windows (everything is inside) and for small
windows (everything is outside).
Each vertex is assigned a four-bit outcode.
December 8, 2021 33
Cohen-Sutherland Clipping (cont.)
1001 1000 1010
Bit 1: Above
Bit 2: Below
Bit 3: Right 0001 0000 0010
Bit 4: Left
0101 0100 0110
Bit 1: 1 if y > yt, else 0
Bit 2: 1 if y < yb, else 0
Bit 3: 1 if x > xr, else 0
Bit 4: 1 if x < xl, else 0
December 8, 2021 34
Cohen-Sutherland Clipping (cont.)
1001 1000 1010
Bit 1: Above
Bit 2: Below
Bit 3: Right 0001 0000 0010
Bit 4: Left
0101 0100 0110
A line can be trivially accepted if both endpoints have an
outcode of 0000.
A line can be trivially rejected if any corresponding bits in the
two outcodes are both equal to 1. (This means that both
endpoints are to the right, to the left, above, or below the
window.)
if (outcode 1 & outcode 2) != 0000, trivially reject!
December 8, 2021 35
Clipping Lines Not Accepted or Rejected
In the case where a line can be neither trivially accepted
nor rejected, the algorithm uses a “divide and conquer”
method.
Line AD:
1) Test outcodes of A and D --> can’t
accept or reject.
D
2) Calculate intersection point B, which C
B
is on the dividing line between the
window and the “above” region. A
Form new line segment AB and H
discard BD because above the E F G
window.
3) Test outcodes of A and B. Reject.
Line EH: ??
December 8, 2021 36
Polygon Clipping
Polygons can be clipped against each edge of the
window one edge at a time. Window/edge
intersections, if any, are easy to find since the X or Y
coordinates are already known.
Vertices which are kept after clipping against one
window edge are saved for clipping against the
remaining edges. Note that the number of vertices
usually changes and will often increase.
December 8, 2021 37
Polygon Clipping Algorithm
P4 P4
I2 I2
P3
I1 I1
P1 P2 P1
The window boundary determines a visible and invisible
region.
The edge from vertex i to vertex i+1 can be one of four
types:
Exit visible region - save the intersection
Wholly outside visible region- save nothing
Enter visible region - save intersection and endpoint
Wholly inside visible region - save endpoint
December 8, 2021 38
Polygon clipping
issues
The final output, if any, is always
considered a single polygon.
The spurious edge may not be a problem
since it always occurs on a window
boundary, but it can be eliminated if
necessary.
December 8, 2021 39
Pipelined Polygon Clipping
Clip Clip Clip Clip
Top Right Bottom Left
Because polygon clipping does not depend on any other
polygons, it is possible to arrange the clipping stages in a
pipeline. the input polygon is clipped against one edge
and any points that are kept are passed on as input to the
next stage of the pipeline.
This way four polygons can be at different stages of the
clipping process simultaneously. This is often
implemented in hardware.
December 8, 2021 40
Clipping in the openGL pipeline
A figure illustrating the openGL graphics
pipeline:
clipping is done here
December 8, 2021 41
Text clipping
strategies for dealing with text objects
Consider following example:
Assume interior
clipping
ABC
Clip window
December 8, 2021 42
Student Exercise
Draw three possible results of interior
clipping of the string “ABC”
Try to name what type
of clipping you have
done in each case
ABC
Clip window
December 8, 2021 43
Student Exercise
All-or-none string clipping
No text is retained after clipping
since part of text is outside clip window
Whole String “ABC” is clipped as a single object
Before clipping After clipping
ABC
Clip window Clip window
December 8, 2021 44
Student Exercise
All-or-none character clipping
Only “B” and “C” are retained after clipping
since part of “A” is outside clip window
Each character is clipped as a separate object
Before clipping After clipping
ABC BC
Clip window Clip window
December 8, 2021 45
Student Exercise
Character component clipping
All of “B” and “C” are retained, and those parts
of “A” inside clip window are also retained
Each component of each character is clipped as a separate
object
Before clipping After clipping
ABC ABC
Clip window Clip window
December 8, 2021 46
Introduction to 3D clipping
In 3D a clip volume needs to be defined
Example for “perspective” 3D
We define
Point to project to
(viewer’s “eye”)
Projection ref. point
December 8, 2021 47
Introduction to 3D clipping
In 3D a clip volume needs to be defined
Example for “perspective” 3D
We define
Window to define direction
and amount of view
View plane window
Projection ref. point
December 8, 2021 48
Introduction to 3D clipping
In 3D a clip volume needs to be defined
Example for “perspective” 3D
We define
2 clip planes to define
Rear clip plane
max and min distance
to viewer
Front clip plane
Projection ref. point
December 8, 2021 49
Introduction to 3D clipping
In 3D a clip volume needs to be defined
Example for “perspective” 3D
Rear clip plane
Front clip plane
View plane window
Projection ref. point
December 8, 2021 50
Introduction to 3D clipping
Result is a finite clip volume of space
This shape is a named a frustum
December 8, 2021 51
Canonical View Volume
3-D Extension of 2-D Cohen-Sutherland Algorithm,
Outcode of six bits. A bit is true (1) when the
appropriate condition is satisfied
Bit 1 - Point is above view volume y > -z
Bit 2 - Point is below view volume y<z
Y axis
Bit 3 - Point is right of view volume x > -z
+1
Bit 4 - Point is left of view volume x<z
y=-z
Bit 5 - Point is behind view volume z < -1
Front
Clipping Bit 6 - Point is in front of view volume z > zmin
Plane
-Z
-1
Back
Clipping
Plane
y=z
z=-1
-1
December 8, 2021 52
3D Line Clipping
A line is trivially accepted if both endpoints have a code of
all zeros.
A line is trivially rejected if the bit-by-bit logical AND of the
codes is not all zeros.
Otherwise Calculate intersections.
On the y = z plane from parametric equation of the line:
y0 + t( y1 - y0) = z0 + t( z1 + z0)
Solve for t and calculate x and y. Already know z = y
December 8, 2021 53
Summary – clipping in general
Clipping means
Identifying portions of a scene that are inside (or
outside) a specified region
Clipping is defined using a clip window
Interior clipping keep things inside clip window /
Exterior cl. outside
December 8, 2021 54
Types of clipping
All-or-none (AON) clipping
if any part of object outside clip area then
reject whole object
Point / line / polygon / text clipping (AON
string/char, component)
December 8, 2021 55
3D clipping involves defining a clip volume
A finite volume of space defined by front and
back clipping planes, the view plane window and
projection method
(more details in lecture on 3D)
December 8, 2021 56
Summary
A 4-bit encoding for regions related to clip window
TOP
BOTTOM
LEFT
RIGHT
Code can be used to easily
To determine if a point in inside clip window
If endpoints of a line mean whole line
is fully inside or fully outside clip window
Can implement in C++ using char
8-bit, unsigned, data type
December 8, 2021 57
