程序代写代做代考 algorithm Clipping Algorithms

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