Chapter06

xdmax xdmin ( xv xmin ) xd xdmin x x max min yd ydmin yd ydmin max ( yv ymin ) ymax ymin
xd y M WV d 1 xv yv 1
Cohen-Sutherland Line Clipping Algorithm
Region code: (0: inside; 1: outside) • bit 1: left • bit 2: right • bit 3: below • bit 4: above
1001 0001 0101 1000 0000 0100 1010 0010 0110
2. Trivial reject. both end points are outside any one of the clipping boundaries
If trivial tests fail, then intersection calculations need to be done to determine the portion of the line that lies inside the clipping window.
• Point clipping • Line clipping • Polygon clipping • Text clipping
Inside and outside of clipping boundaries
Outside Inside
left boundary Inside x xmin Outside x < xmin
In matrix form:
xd xn y M yn viewport d 1 1
M viewport
xdmax xdmin 2 0 0
0 ydmax ydmin 2 0
xdmax xdmin 2 ydmax ydmin 2 1
Clipping Window to Viewport transformation
Device coordinates
Clipping
Some graphics systems have normalized coordinates between viewing coordinates and device coordinates. Normalized coordinates: Coordinate values are normalized between –1 and 1 (0 and 1 for some systems.)
Two-Dimensional Viewing
Two-Dimensional Viewing Pipeline
Local coordinates Modeling transformation World coordinates Viewing transformation
Viewing coordinates
v y M view R view Tview v x 0 vx vy 0 x0 v y y0 v x x0 v x y0 v y 1
Clipping Window to Viewport Transformation Clipping Window: An area in viewing coordinates selected for display. Viewport: An area on display device in which the clipping window is mapped onto. The terminology “window” here is different than the concept of a window in a windows GUI system.
head
body
left arm
right arm
left leg
right leg
Translation
Translation
Rotation and Translation
Translation
Viewing Transformation y v (x0, y0) u xv yv xy: xvyv: World coordinates Viewing coordinates
Inside
Outside
right boundary Inside x xmax Outside x > xmax
bottom boundary Inside y ymin Outside y < ymin
Inside
Outside
top boundary Inside y ymax Outside y > ymax
Slope
y m , x x xe xs y ye ys
Parametric equation: Trivial tests:
x xs ux 0 u 1 y ys uy
1. Trivial accept. Both end points are inside the clipping window
2 xn 1 ( xv xmin ) xmax xmin 2 yn 1 ( yv ymin ) ymax ymin
In matrix form:
xn xv y M yv norm n 1 1
MWV Mviewport Mnorm
Clipping
Clipping: Identify portions of a picture that are either inside or outside of a specific region. y ymax ymin xmin xmax y
In matrix form:
MWV
xdmax xdmin xmax xmin 0 0
0 ydmax ydmin ymax ymin 0
xdmax xdmin xdmin xmin xmax xmin ydmax ydmin ydmin ymin ymax ymin 1
R1, R2: Region codes for the two endpoints.
Trivial tests:
If R1 = R2 = 0 then trivial accept; If R1 & R2 0 then trivial reject;
Cohen-Sutherland Line Clipping Algorithm
Device coordinates
Clipping
Modeling Transformation Transform objects (models) from local (modeling) coordinate system to world (global) coordinate system.
x
(x0, y0): v: u: Origin of viewing coordinate system View up vector (unit vector in yv direction) unit vector in xv direction
vx v v y
u x v y u u y v x
yv
ymax
yd
ydmax
ymin
xmin xmax xv
ydmin
xdmin xdmax Viewport in Device coordinates xd
Clipping Window in Viewing coordinates
Clipping Window to Viewport transformation:
M norm
2 xmax xmin 0 0
0 2 ymax ymin 0
xmax xmin xmax xmin ymax ymin ymax ymin 1
Viewport Transformation yn
Translation
Rota0 )
uy vy 0 0 v y 0 v x 1 0 vx vy 0 0 0 1
u x Rview v x 0
Viewing transformation: xv x y M y view v 1 1
done = false; while (!done) { Generate region codes R1, R2 for the endpoints; if (R1 = R2 = 0) {done = true; accept = true;} else if (R1 & R2 0) {done = true; accept = false;} else { Find a clipping boundary of which one endpoint is inside while the other is outside; Clip the line against this boundary; Update endpoint coordinates; } }
Outside
Inside
Point clipping
xmin x xmax ymin y ymax
Line clipping
Line endpoints: (xs, ys) (xe, ye) Slope-intercept equation: y m ( x xs ) ys