LINE CLIPPING

• Want to clip lines to the window
• (xmin, ymin, xmax, ymax)

• Some cases trivial:
1) Trivial Accept
xmin <= x0, x1 <= xmax &&
ymin <= y0, y1 <= ymax

2) Trivial Reject :
x0, x1 <= xmin
y0, y1 <= ymin
x0, x1 >= xmax
y0, y1 >= ymax

• Other cases:
• 1 inside window, 1 outside - intersect line with window and accept intersected line

• Both outside (but not above cases) : Intersect with window, may or may not accept.

• Line Clipping Algorithms:

• 1) Brute Force
2) Cohen-Sutherland
3) Liang-Barsky
4) Sutherland-Hodgman (closure clipping)

1) Brute Force

• Use parametric equation of line:

• x = x0 + t* (x1-x0)
y = y0 + t*(y1-y0)

• Calculate intersection of line with window boundaries if not one of the trivial cases.

• Have 4 unknowns and 4 equations, solve to get t and twindow_edge.

• Example: Horizontal edge y =ymin:
• y=y1 + t(y2-y1)=ymin
t=(ymin - y1)/(y2 -y1)
xint = x1 + (ymin -y1)/y2-y1) *(x2-x1)
make sure that 0<=t<=1 and
xmin<=xint<=xmax

• Computationally very expensive

2) Cohen-Sutherland Algorithm

• Based on calculation of outcodes for each end point :
• Calculation of outcodes:

• Bit1: y> ymax or sign(ymax-y)
Bit2: y < ymin or sign(ymin -y)
Bit3: x > xmax or sign(xmax -x)
Bit4: x < xmin or sign(xmin -x)

• If (outcode(pnt1) OR outcode(pnt2))=0, then
• trivially accept (logical OR -> all zeros)

• if (outcode(pnt1) AND outcode(pnt2)) =1,
• then trivially reject (if any bitwise and =1, then both point on same halfplane)
• Else,

• intersect line with a clip boundary and either trivially accept or reject one (or both) of the two parts.
• Which clip edge do we intersect it with?
• Well, if a outcode bit is 1, and we didn't reject the line, the line must cross that boundary.

• Processing order is top, bottom, right, left.
• So, The algorithm is essentially:

• Calculate outcode(p1), outcode(p2)
• Loop
• Test for trivial rejection, acceptance. If so, exit loop
• Else, choose one of the points that lies outside, call it P1 and see which boundary it crosses.
• Intersect P1, P2 with the clip edge to get Pcl.
• Through away (P1, Pcl), keep (Pcl, P2).
• Compute outcode for Pcl.
• end loop

• Example: P1: 0001 P2: 0100
• can't trivially accept or reject, so clip against an edge
• outcode[0] OK
• Outcode[1] P2 outside, clip and keep P1,Pcl
• calculate outcode(Pcl)= [0 0 0 0],
• test Outcode[3], OK
• Outcode[4], P1 outside c=> clip. keep Pcl, Pcl2.
• Outcode(Pcl2)=[0 0 0 0], so draw (Pcl, Pcl2)

• The final Cohen-Sutherland Clipping Algorithm
• define TOP=1, BOTTOM=2, RIGHT=3 , LEFT=4

```  CS-Clip(x0,y0, x1,y1)
calc_code(x0, y0, outcode0)
calc_code(x1, y1, outcode1)
loop forever
if (outcode0 = outcode1 = [0 0 0 0])
drawline(p0,p1)
return
if (outcode0 & outcode1 != [0 0 0 0])
return  /* trivial reject */
if outcode0 = [0 0 0 0]
/* which one is outside */
code= outcode1
calc_intersect(code, x0, x1,
y0, y1, x, y)
x1=x, y1=y
calc_code(x1,y1, outcode1)
else
code = outcode0
calc_intersect(code, x0, x1, y0, y1)
x0=x, y0=y
calc_code(x0,y0, outcode0)
end loop

calc_intersect(code, x0,x1,y0,y1, x,y)
if (code[TOP]) /* intersect top */
x = x0 + (x1-x0)*(ymax - y0)/(y1-y0)
y=ymax
else if (code[BOTTOM])
x = x0 + (x1-x0)*(ymin - y0)/(y1-y0)
y=ymin
else if(code[RIGHT])
x=xmax
y= y0 + (y1-y0)*(xmax - x0)/(x1-x0)
else if(code[LEFT])
x=xmin
y= y0 + (y1-y0)*(xmin - x0)/(x1-x0)```

3) Liang-Barsky Algorithm
• Based on the parametric representation of the line:

• x = x0 + t*(x1-x0)
y = y0 + t* (y1-y0)

• Want the following restrictions on the solution:
• ```        1)      x >= xmin       xmin <= x0 + t (x1-x0)
2)      x <= xmax       xmax >= x0 + t (x1-x0)
3)      y >= ymin       ymin <= y0 + t (y1-y0)
4)      y <= ymax       ymax >= y0 + t (y1-y0)
5)      0 <= t <= 1```
• Now, lets put all of these in the form t*m <= c
• ```      1) t*( x0-x1)<= x0 -xmin      t*(-dx)
2) t* (x1-x0)<= xmax - x0     t*dx
3) t*(y0-y1)<= y0 -ymin       t*(-dy)
4) t* (y1-y0)<= ymax - y0     t*(dy)```
• Range of t that satisfies these 5 inequalities is exactly where the line is visible.

• So, we find Tmin and Tmax such that Tmin <= t <= Tmax and we have our endpoints for visible portion of the line.

• How do we use the above equations to find Tmin & Tmax?

• First, set Tmin =0, Tmax = 1.

• Now, we use the above inequalities to adjust Tmin and Tmax.

• Remember,
• 1) t*(x0-x1)  <= x0-xmin
2) t* (x1-x0) <= xmax - x0
3) t*(y0-y1)  <= y0 -ymin
4) t* (y1-y0) <= ymax - y0

• For each inequality (t*m <=c), calculate m & c:

• If m > 0 then t <= c/m
• Case 1: c/m < Tmin, so the line is invisible
Case 2: c/m > Tmax , doesn't change the range of t ( t < something bigger than Tmax , but t is < Tmax anyway.)

Case 3: Tmin <= c/m² Tmax, so set Tmax = c/m

• If m < 0 then t >= c/m
• Case 1: c/m > Tmax, so the line is invisible
Case 2: c/m <= Tmin , doesn't change the range of t ( t >= something less than Tmin , but t is < Tmin anyway.)
Case 3: Tmin <= c/m <= Tmax, so set Tmin = c/m

• If m=0, line is parallel to this clipping edge, so if c < 0, reject the line, otherwise do nothing.

• If you didn't determine that the line was invisible, stick Tmin and Tmax in for t in the equations to get the endpoints for the visible portion of the line and draw it.

• The Algorithm:
• ```L-B_Clip(x0,y0,x1,y1, xmin, xmax, ymin, ymax)

Tmin =0; Tmax=1
dx = x1-x0;

if ( (RangeTest(-dx, x0-xmin,Tmin, Tmax)) == false)
return;
if ( (RangeTest(dx, xmax-x0,tmin, tmax)) == false)
return;
dy =y1-y0
if ( (RangeTest(-dy, y0-ymin,Tmin, Tmax)) == false)
return;
if ( (RangeTest(dy, ymax-y0,Tmin, Tmax)) == false)
return;

/* line visible */
if (Tmax ­ 1)
x1 = round(x0 + Tmax *dx)
y1 = round(y0 + Tmax*dy)
if (Tmin ­ 0)
x0 = round(x0 + Tmin *dx)
y0 = round(y0 + Tmin*dy)
drawline(x0,y0, x1,y1)
end L-B_Clip

Boolean RangeTest(m,c, Tmin,Tmax)
if(m >0)
r=c/m
if(r< Tmin)
return(false)
if( r < Tmax)
Tmax=r
return(true)
if (m< 0)
r=c/m
if(r > Tmax)
return(false)
if( r > Tmin)
Tmin=r
return(true)
if( c < 0)
return(false)
return(true)
end RangeTest```
• Example: Line from (1,1) to (9,6), Clip boundary (2,3) to (8,7)

• RangeTest1 sets Tmin=1/8,
RangeTest2 sets Tmax=7/8
RangeTest3 sets Tmin=2/5
RangeTest4 calculates r=6/5, but changes nothing

4) Sutherland-Hodgman

• This algorithm clips a polygon into polygons. (the previous ones, clip lines to lines)

• The approach is to clip the polygon to each of the infinite clipping edges in succession.

• Cohen-Sutherland only clips a line against a boundary if necessary.

• Assume we have a triangle of 3 line segments. Sutherland Hodgman clips the 3lines against 1 clip boundary, then the results against the next clip boundary,... . The result is always closed polygons

• Cohen-Sutherland would clip line 1 against the clip boundaries (if necessary), then clip line2, then line3. The result will probably not be a closed a polygon.

• Clip (vn, v0) ,(v0, v1), (v1, v2),....(vn-1,vn) against boundary1. Then the results against boundary2, etc.

• Given the edge (s,p), where s's visibility has been handled before, there are 4 cases:
• 1) s in, p in => output p
2) s in, p out => output intersection
3) s out, p out => output nothing
4) s out,p in => output intersection, p

• The generic algorithm takes an input vertex array and outputs the vertex array clipped to one edge.
• For window clipping, make the inside routine test for inside of the 4 window edges, and call the clipper for each edge.
• ```        Clip(InVert, OutVert, inlength, outlength,
clipedges)
for i=0 to 3
SH_CLIP(InVert, OutVert, inlength,
outlength, i, clipedges)
InVert=Outvert
inlength=outlength
end clip```
• Diagram

• Algorithm to clip to 1 boundary
• ```    SH_CLIP(InVert, OutVert, inlength, outlength,
clipboundary, clip)
outlength=0
s = InVert[inlength -1]
for (j=0 to inlength -1)
p = InVert[j]
if( Inside(p, clipboundary, clip))
/* case 1 &4 */
if (Inside(s, clipboundary,
clip)  /* case 1*/
output(p, outlength, OutVert)
else  /* case 4*/
Intersect(s,p, clipboundary, clip, i)
output(i, outlength, OutVert)
output( p, outlength, OutVert)
else /* case 2 & 3 */
if(Inside(s, Clipboundary, clip))
/* case 2 */
Intersect(s,p, clipboundary,clip, i)
output(i, outlength, OutVert)
s=p
end for
end

boolean Inside(p, clipboundary, clip)
case clipboundary of
top:    return( p.y <= clip.top)
bottom: return( p.y >= clip.bottom)
left:   return( p.x >= clip.left)
right:  return( p.x <= clip.right)
end```