Next: Geometries
Up: Clipping
Previous: Clipping
 Clipping:
 Remove points outside a region of interest.
 Discard (parts of) primitives outside our window...
 Point clipping:
 Remove points outside window.
 A point is either entirely inside the region or not.
 Line clipping:
 Remove portion of line segment outside window.
 Line segments can straddle the region boundary.
 LiangBarsky algorithm efficiently clips
line segments to a halfspace.
 Halfspaces can be combined to bound a convex region.
 Use outcodes to better organize combinations of halfspaces.
 Can use some of the ideas in LiangBarsky to clip points.
 Parametric representation of line:

or equivalently
 A and B are noncoincident points.
 For , L(t) defines an infinite line.
 For , L(t) defines a line segment from
A to B.
 Good for generating points on a line.
 Not so good for testing if a given point is on a line.
 Implicit representation of line:

 P is a point on the line.
 is a vector perpendicular to the line.
 gives us the signed distance
from any point Q to the line.
 The sign of tells us if Q is on the
left or right of the line, relative to the direction of .
 If is zero, then Q is on the line.
 Use same form for the implicit representation of a
halfspace.
\
 Clipping a point to a halfspace:

 Represent window edge as implicit line/halfspace.
 Use the implicit form of edge to classify a point Q.
 Must choose a convention for the normal:
points to the inside.
 Check the sign of :
 If , then Q is inside.
 Otherwise clip (discard) Q:
It is on the edge or outside.
May want to keep things on the boundary.
 Clipping a line segment to a halfspace:
There are three cases:
 The line segment is entirely inside:
Keep it.
 The line segment is entirely outside:
Discard it.
 The line segment is partially inside
and partially outside:
Generate new line to represent
part inside.
\
 Input Specification:

 Window edge: implicit,
 Line segment: parametric, L(t) = A + t(BA).
 Do the easy stuff first:

We can devise easy (and fast!) tests for the first two cases:
Need to decide: are boundary points
inside or outside?
 Trivial tests
 are important in computer graphics:
 Particularly if the trivial case is the most common one.
 Particularly if we can reuse the computation for the
nontrivial case.
 Do the hard stuff only if we have to:

If line segment partially inside and partially
outside, need to clip it:
 Line segment from A to B in
parametric form:
 When t=0, L(t)=A. When t=1, L(t)=B.
 We now have the following:
\
 We want t such that :
 Solving for t gives us
 NOTE:
The values we use for our simple test can be reused
to compute t:
 Clipping a line segment to a window:
Just clip to each of four halfspaces in turn.
 Pseudocode:

Given line segment (A,B), clip inplace:
for each edge (P,n)
wecA = (AP) . n
wecB = (BP) . n
if ( wecA < 0 AND wecB < 0 ) then reject
if ( wecA > 0 AND wecB > 0 ) then next
t = wecA / (wecA  wecB)
if ( wecA < 0 ) then
A = A + t*(BA)
else
B = A + t*(BA)
endif
endfor
 Note:

 LiangBarsky Algorithm can clip lines to
any convex window.
 Optimizations can be made for the special case of
horizontal and vertical window edges.
 Question:
Should we clip before or after windowtoviewport mapping?
 Lineclip Algorithm generalizes to 3D:

 Halfspace now lies on one side of a plane.
 Plane also given by normal and point.
 Implicit formula for plane in 3D is same as
that for line in 2D.
 Parametric formula for line to be clipped is unchanged.
Reading: Hearn and Baker, Sections 65 through 67,
Red book: 3.9,
White Book: 3.11,
Blinn: 13.
Next: Geometries
Up: Clipping
Previous: Clipping
CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab
cs488@cgl.uwaterloo.ca