Next: Geometries Up: Clipping Previous: Clipping

# Point and Line 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.
• Liang-Barsky 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 Liang-Barsky to clip points.

Parametric representation of line:

or equivalently

• A and B are non-coincident 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.
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:
1. The line segment is entirely inside:
Keep it.
2. The line segment is entirely outside:
3. 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(B-A).
Do the easy stuff first:

We can devise easy (and fast!) tests for the first two cases:
• AND Outside
• AND Inside
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 non-trivial 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.
Pseudo-code:
```	Given line segment (A,B), clip in-place:
for each edge (P,n)
wecA = (A-P) . n
wecB = (B-P) . 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*(B-A)
else
B = A + t*(B-A)
endif
endfor```

Note:
• Liang-Barsky 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 window-to-viewport mapping?

Line-clip Algorithm generalizes to 3D:
• Half-space 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 6-5 through 6-7, 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