CSCE 441 Lecture 6

From Notes
Jump to navigation Jump to search

« 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y)} , clipping window is a rectangle from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_{min}, y_{min})} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_{max}, y_{max})} , we check Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \left[ x_{min}, x_{max} \right]} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} boundary): Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{int} = y_1 + m(x_{max} - x_1)r} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = \frac{y_2 - y_1}{x_2 - x_1}}
  • (e.g. with bottom Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} boundary): Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0, p_1} using region codes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[ t_{min}, t_{max} \right] = \left[ 0, 1 \right]} .

For each boundary,

  • find parametric intersection Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} with boundary
  • If moving in-to-out, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{max} = \min{\left( t_{max}, t \right)}}
  • If moving out-to-in, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{min} = \max{\left( t_{min}, t \right)}}
  • If at any point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_{max} < t_{min}} , we reject the line.

Review: Parametric Lines

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases}x(t) = x_0 + (x_1 - x_0) \, t \\ y(t) = y_0 + (y_1 - y_0) \, t\end{cases}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} x(t) = x_2 + (x_3 - x_2) \, t \\ y(t) = y_2 + (y_3 - y_2) \, t \end{cases}}

Set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} equations equal, replacing parameters to prevent conflict, and then solve for parameters.

Classifying Direction

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} boundaries, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 < x_0} , then we classify as in-to-out (even if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0 < x_{max}} ).

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} boundaries, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1 < y_0} , then we classify as in-to-out (even if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_0 < y_{max}} ).

Summary

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

Liang-Barsky: computing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_441_Lecture_6&oldid=4941"