- 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:
- 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
- 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:
- The line segment is entirely outside:
- The line segment is partially inside
and partially outside:
Generate new line to represent
- 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:
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
- 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
- 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
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.
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)
B = A + t*(B-A)
- Liang-Barsky Algorithm can clip lines to
any convex window.
- Optimizations can be made for the special case of
horizontal and vertical window edges.
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,
CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab