CSCE 441 Lecture 6

« previous | Monday, January 27, 2014 | next »

Clipping Lines

Don't waste time drawing things that aren't on the screen.

Clipping Points is easy: given a point $(x,y)$, clipping window is a rectangle from $(x_{min},y_{min})$ to $(x_{max},y_{max})$, we check $x\in \left[x_{min},x_{max}\right]$ and $y\in \left[y_{min},y_{max}\right]$. If both conditions meet, we draw the point.

Lines are determined by their endpoints. What if one or both endpoints are outside the window?

Simple Algorithm

If both end-points are inside the clipping window, then we can draw the line. Otherwise, we have to intersect the line with all edges of the clipping rectangle and draw using the intersection(s) as the new endpoint(s).

Checking intersection

• (e.g. with right $x$ boundary): $y_{int}=y_{1}+m(x_{max}-x_{1})r$, where $m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$
• (e.g. with bottom $y$ boundary): $x_{int}=x_{1}+{\frac {y_{min}-y_{1}}{m}}$

Boundary cases: intersecting lines that are parallel to boundary line.

This algorithm can be computationally expensive.

A Better Way: Cohen-Sutherland Algorithm

Trivial accepts/rejects

How can we quickly decide whether line segment is entirely inside the window? Test if both endpoints are on the same side (outside) a single boundary (e.g. $x_{1},x_{2}<x_{min}$

Use 4-bit region codes to represent edges:

top

bottom

left

right

1001	1000	1010
0001	0000	0010
0101	0100	0110

Classify $p_{0},p_{1}$ using region codes $c_{0},c_{1}$, respectively

• if c0 & c1 != 0, then trivially reject
• if c0 | c1 == 0, then trivially accept
• Otherwise reduce to trivial cases by splitting into two segments
  • compute $c0|c1$ and clip each boundary as determined by bits

Even Better: Liang-Barsky Algorithm

• Use parametric form of line for clipping
• Lines are oriented (moving in-to-out or out-to-in)
• We don't need to find actual intersection points, but only the parameter values for which the line is within the window.

Initialize interval to $\left[t_{min},t_{max}\right]=\left[0,1\right]$.

For each boundary,

• find parametric intersection $t$ with boundary
• If moving in-to-out, $t_{max}=\min {\left(t_{max},t\right)}$
• If moving out-to-in, $t_{min}=\max {\left(t_{min},t\right)}$
• If at any point $t_{max}<t_{min}$, we reject the line.

Review: Parametric Lines

${\begin{cases}x(t)=x_{0}+(x_{1}-x_{0})\,t\\y(t)=y_{0}+(y_{1}-y_{0})\,t\end{cases}}\quad \quad t\in \left[0,1\right]$

Intersecting parametric lines:

Given two lines ${\begin{cases}x(t)=x_{0}+(x_{1}-x_{0})\,t\\y(t)=y_{0}+(y_{1}-y_{0})\,t\end{cases}}$ and ${\begin{cases}x(t)=x_{2}+(x_{3}-x_{2})\,t\\y(t)=y_{2}+(y_{3}-y_{2})\,t\end{cases}}$

Set $x$ and $y$ equations equal, replacing parameters to prevent conflict, and then solve for parameters.

Classifying Direction

For $x$ boundaries, if $x_{1}<x_{0}$, then we classify as in-to-out (even if $x_{0}<x_{max}$).

For $y$ boundaries, if $y_{1}<y_{0}$, then we classify as in-to-out (even if $y_{0}<y_{max}$).

Summary

Cohen-Sutherland is best used when trivial accept/reject is possible for most lines.

Liang-Barsky: computing $t$ values is cheap.

Both can be used together.

Clipping Polygons

Why is this hard?

1. Added edges: When clipping a triangle within a rectangle, the clipped polygon can have up to 7 new edges!
2. Drawing a concave polygon can result in multiple polygons on the screen

Sutherland-Hodgman Clipping

• Consider each edge of the view window individually
• Clip polygon against view window edge's equation.