Clipping Algorithms
Lecture: 7
Fall 2016
Computer Graphics (CS3388) Department of Computer Science
University of Western Ontario
Clipping
Outline
Need for clipping
Cohen-Sutherland clipping algorithm window-viewport mapping Liang-Barsky clipping algorithm
Polygon clipping
(materials from R. Yang (Kentucky univ.), A.J.P Gomes (Universidade da Beira Interior))
1
Line Clipping
What happens when one or both endpoints of a line segment are not inside the specified drawing area?
2
Strategies for clipping
Check if each point is inside: very slow
if (x>= xmin and x<=xmax and y>=ymin and y<=ymax)
drawPoint(x,y,c);
Find intersection of line with boundary
3
Line Clipping in 2D
4
Line Clipping: possible configurations
Both endpoints are inside the region (line AB) No clipping necessary
One endpoint in, one out (line CD) Clip at intersection point
Both endpoints outside the region No intersection (lines EF, GH) Line intersects the region (line IJ)
Clip line at both intersection points
5
Cohen-Sutherland clipping algorithm
Basic idea:
Accept lines that have both endpoints inside the region
Reject lines that have both endpoints less than xmin or ymin or greater than xmax or ymax
Clip the remaining lines at a region boundary & repeat the previous steps on the clipped line segments.
6
Cohen-Sutherland: Accept-Reject test
Assign a 4-bit code to each endpoint c0, c1 based on its position: 1st bit (1000): if y > ymax
2nd bit (0100): if y < ymin
3rd bit (0010): if x > xmax
4th bit (0001): if x < xmin Test using bitwise functions
if c0 | c1 = 0000
accept (draw)
else if c0 & c1 != 0000
reject (don’t draw)
else clip and retest
7
Cohen-Sutherland algorithm
Computing the intersections: Say a line has endpoints (x1, y1), (x2, y2) With a vertical boundary, x is either xmin or xmax . Hence,
or
y = y1 + y2 − y1 (xmin − x1) x2 − x1
y = y1 + y2 − y1 (xmax − x1) x2 − x1
With a horizontal boundary, y is either ymin or ymax . Hence, x = x1 + x2 − x1 (ymin − y1)
or
y2 − y1
x = x1 + x2 − x1 (ymax − y1) y2 − y1
8
Details of window-viewport mapping
(next few slides are from A.J.P Gomes, Universidade da Beira Interior)
9
Details of window-viewport mapping
10
Details of window-viewport mapping
11
Details of window-viewport mapping
12
Cohen-Sutherland
Intersection algorithm
if(c0 != 0000) then c=c0;
else c=c1;
dx=x1-x0; dy=y1-y0;
if(c & 1000 != 0) //ymax
x = x0+dx*(ymax-y0)/dy;
elseif(c & 0100 != 0) //ymin
x = x0+dx*(ymin-y0)/dy; y = ymin;
elseif(c & 0010 != 0) //xmax
y = y0+dy*(xmax-x0)/dx;
else //xmin
y = y0+dy*(xmin-x0)/dx;
if(c=c0)
x0=x; y0=y;
else
x = xmax;
x = xmin;
x1=x; y1=y;
y = ymax;
13
Cohen-Sutherland: example
c = 1010, dx = 250, dy = 150 x = 233, y = 200
14
Cohen-Sutherland algorithm
Disadvantages
Clipping window must be rectangular
Can generate more efficient rejection tests Can improve using more regions
Advantages
Simple to implement
Oriented for most simple window/viewport systems Extends to 3D cubic volumes
15
Liang-Barsky clipping algorithm
First developed by Cyrus & Beck, later modified by Lian & Barsky Called parametric line clipping.
Less calculations than Cohen-Sutherland algorithm
Non-iterative algorithm - faster
16
Liang-Barsky clipping algorithm
Consider a line segment with end points (x1, y1), (x2, y2)
The parametric form of the line is,
x = x1 + u∆x
y = y1 + u∆y
where ∆x = x2 − x1, ∆y = y2 − y1 0≤u≤1
17
Liang-Barsky clipping algorithm
The following inequalities should be satisfied when the line is completely inside the clipping window,
Xmin ≤x1 +u∆x ≤Xmax Ymin ≤ y1 + u∆y ≤ Ymax
These inequalities can be written as,
upk ≤ qk
k = 1, 2, 3, 4
18
Liang-Barsky clipping algorithm
k=1
p1 = −∆x
q1 = x1 − Xmin
Left boundary
k=2
p2 = ∆x
q2 =Xmax −x1
Right boundary
k=3
p3 = −∆y
q3 = y1 − Ymin
Bottom boundary
k=4
p4 = ∆y
q4 =Ymax −y1
Top boundary
If pk = 0: parallel line to one of the kth boundary
If p1 = ∆x = 0: the line is vertical and parallel to the left and right
boundaries
If q1 ≤ 0 or q2 ≤ 0: the line segment is completely outside the window
If (p1 = 0) ∧ (q1 ≤ 0 ∨ q2 ≤ 0), the line segment is completely outside
Thesameruleforp3,q3,q4: If(p3 =0)∧(q3 ≤0∨q4 ≤0),theline segment is outside
If pk < 0: from outside to inside If pk > 0: from inside to outside
19
Liang-Barsky clipping algorithm
Clipping conditions: summary
pk = 0: parallel line to one of the kth boundary qk < 0: outside (reject)
qk ≥ 0: inside
If pk < 0: from outside to inside (compute intersection point) If pk > 0: from inside to outside (compute intersection point)
20
Liang-Barsky clipping algorithm
Compute intersection point:
pk < 0: outside to inside point
rk = qk pk
intersection point: t1 = max(rk,0) pk > 0: inside to outside point
rk = qk pk
intersection point: t2 = min(rk , 1)
If t1 > t2: completely outside (Reject) Else: clipped line is between (t1, t2)
21
Liang-Barsky clipping algorithm
The Algorithm: Computing t1:
forallpk <0do rk = qk
pk
t1 = max(rk,0)
end for
Computing t2: forallpk >0do
rk = qk pk
t2 =min(rk,1) end for
22
Liang-Barsky clipping algorithm
The main body of the algorithm:
compute pk and qk, for k = 1,2,3,4
if [(p1 =0)∧(q1 ≤0∨q2 ≤0)]∨[(p3 =0)∧(q3 ≤0∨q4 ≤0)]then
Reject the segment
else
Compute t1 Compute t2
if (t1 > t2) then
Reject the segment
else
Clipped line segment is
(x1 + ∆xt1, y1 + ∆yt1), (x1 + ∆xt2, y1 + ∆yt2))
end if end if
23
Polygon clipping
How to clip polygons?
(Examples from Ruigang Yang, Univ. of Kentucky)
24
Polygon clipping
Polygon clipping algorithm:
Clip polygon to Ymin and Ymax
Create empty output vertex list
Process input list (v0, v1, · · · , vn) where v0 = vn Foreachinputvertexvi where(0≤i≤n−1)
If vi is inside region, add vi to output list
If the line between vi and vi+1 intersects clipping boundaries, add
intersection point(s) to output list
Repeat: clip to Xmin and Xmax Post process:
Remove degenerate sections that have collapsed to region boundary
25
Polygon clipping example
26
Polygon clipping example
27
Polygon clipping example
28
Polygon clipping example
29
Polygon clipping example
30
Polygon clipping example
31
Polygon clipping example
32
Polygon clipping example
33
Polygon clipping example
34
Polygon clipping example
35
Polygon clipping example
36
Polygon clipping example
37
Polygon clipping example
38