HW 2D CGA - PPT 6 - Polygon Clipping

-
Question 1

Solution:

Sutherland-Hodgman Method
We will be solving this problem with visual clipping so there will be no calculations. Below is the graph of the polygon before any clipping is done:
Polygon before clipping
First step is to clip at the top edge of the clipping window to get rid of any excess polygon above the window. The given polygon is polygon P with it's members p1, p2, p3, p4, p5, p6, p7, p8, and p9. Below is the first step we take to clip the top edge:
First clipping at TOP EDGE
Firstly we check vector p1p2 on the graph, both of the start point and end point are inside of top edge so we will be taking the ending point as the new point of q1. We'll do that for all vectors of polygon P until the last vector p9p1, the start point is outside and end point is inside so we will be taking the intersection and end point as q8 and q9. From the first clipping we get a new Polygon Q with it's members q1, q2, q3, q4, q5, q6, q7, q8, and q9 in it's respective coordinate as shown in the graph. Below is the second clipping to find polygon R from polygon Q:
Second clipping at RIGHT EDGE
Now we check vector q1q2 and we see both of the start and end point are inside right edge so we will be taking the end point as the new point r1, we will be checking every vector of polygon Q until vector q9q1 and we see both start and end point are inside right edge so we will be taking the end point as the new r9. From the second clipping we get polygon R with it's members r1, r2, r3, r4, r5, r6, r7, r8, and r9. Below is the graph to find polygon S from polygon R:
Third clipping at BOTTOM EDGE
Now we check vector r1r2 and we can see the start point is outside and the end point is inside of bottom edge so we will be taking the intersection as new point s1 and end point as new point s2, we will check with every vector of polygon R until vector r9r1 and we can see the starting point is inside and end point is outside of bottom edge so we will be taking the intersection as new point s10. From the third clipping we got polygon S with it's members s1, s2, s3, s4, s5, s6, s7, s8, s9, and s10. Below is the graph for finding polygon T from polygon S:
Fourth clipping at LEFT EDGE
First, we check vector s1s2 and we can see that both of the start and end point is inside of left edge so we will be taking the end point as new point t1, we will continue checking for every vector in polygon S until vector s10s1 and we can see that the start point is outside and end point is inside of left edge, so we will be taking the intersection as new point t9 and end point as new point t10. From the fourth clipping we will get polygon T with it's members t1, t2, t3, t4, t5, t6, t7, t8, t9, and t10. Below is the finished graph of clipped Polygon P with output of Polygon T:
Polygon after clipping
This polygon T contains degenerate lines since there are overlapping in it's vectors. Polygon P after clipped should generate 2 polygons but since we are using Sutherland-Hodgman method, there's only 1 output polygon and that causes degenerate lines.

Weiler-Atherton Method
Below is the graph containing polygon P with it's members p1, p2, p3, p4, p5, p6, p7, p8, and p9. By using Weiler-Atherton Method we first of all need to declare the intersections of all the edges of polygon P with edges of clipping window W. This results in 4 intersections i1, i2, i3, and i4 as stated in the graph below:
Polygon graph

After declaring the intersections, we need to mark whether the intersection is entering or leaving. Below in the solution graph we differentiate entering intersection with double circle and leaving intersection with regular circle. We need to consider the polygon as Circular List of Polygon (CLP) and the clipping window as Circular List of Window (CLW). Also the intersection in the middle. And then we link each vertex of the polygon and direct the next to an intersection if there are any in the edge.

These are basically the rules to follow to determine the directions of each vertex:
  1. Start at "entering" intersection.
  2. Traverse on CLP (black arrow) until encounter "leaving" intersection. Then traverse on blue arrow.
  3. Traverse on CLW (blue arrow) until encounter "entering" intersection. Then traverse on black arrow.
  4. Repeat until we reach initial "entering" intersection.
Solution using Weiler-Atherton Method
Results from the graph above are:
  • i2 - p4 - i3 - w3 - i2
  • i4 - p1 - i1 - w1 - i4
There you have it, 2 output polygons. Polygon 1 with it's members i2, p4, i3, w3, and return to i2. Polygon 2 with it's members i4, p1, i1, w1, and return to i4. Here we can see the advantage of using Weiler-Atherton Method where there aren't any degenerate lines and the output can be more than 1 polygon.

Question 2

Solution:

Here's the basic calculations we need down this solution:
$$
\begin{array}
aP_1(0, 0), \ P_2(0, 6), \ P_3(6, 6), \ P_4(3, 3), \ P_5(6, 0) \\
W_1(4, 9), \ W_2(12, 1), \ W_3(4, 1)
\end{array}
$$
Next up are the vectors of window clipping edges and their normal
$$
\overrightarrow {E_1} = \overrightarrow {w_1 w_2} = \begin{bmatrix} 12 - 4\\1 - 9 \end{bmatrix} = \begin{bmatrix} 8\\-8 \end{bmatrix}, \overrightarrow {N_1} = \begin{bmatrix} dy\\-dx \end{bmatrix} = \begin{bmatrix} -8\\-8 \end{bmatrix}
$$
Because of dx > 0 and dy < 0, vector \( \overrightarrow {E_1}\) is going downwards right bottom), so \(\overrightarrow {N_1}\) is facing right \( [dy \ -dx]^T \)

$$
\overrightarrow {E_2} = \overrightarrow {w_2 w_3} = \begin{bmatrix} 4 - 12\\1 - 1 \end{bmatrix} = \begin{bmatrix} -8\\0 \end{bmatrix}, \overrightarrow {N_2} = \begin{bmatrix} dy\\-dx \end{bmatrix} = \begin{bmatrix} 0\\8 \end{bmatrix}
$$
Because of dx < 0 and dy = 0, vector \( \overrightarrow {E_2}\) is going left, so \(\overrightarrow {N_2}\) is facing upwards \( [dy \ -dx]^T \)

$$
\overrightarrow {E_3} = \overrightarrow {w_3 w_1} = \begin{bmatrix} 4 - 4\\9 - 1 \end{bmatrix} = \begin{bmatrix} 0\\8 \end{bmatrix}, \overrightarrow {N_2} = \begin{bmatrix} dy\\-dx \end{bmatrix} = \begin{bmatrix} 8\\0 \end{bmatrix}
$$
Because of dx = 0 and dy > 0, vector \( \overrightarrow {E_3}\) is going upwards, so \(\overrightarrow {N_3}\) is facing right \( [dy \ -dx]^T \). After the basics are laid out, we can continue to the first method:

Sutherland-Hodgman Method
This method basically clips the polygon in sequence based on each window clipping edge, so we're going to clip the polygon based on \( \overrightarrow {E_1}, \overrightarrow {E_2}, and \ \overrightarrow {E_3}\) respectively.

Clipping edge \( \overrightarrow {E_1} \)
$$
\begin{align}

\overrightarrow {w_1 p_1} \cdot \overrightarrow {N_1} &= \begin{bmatrix}0-4\\0-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-4\\-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 32 + 72 = 104 \\

\overrightarrow {w_1 p_2} \cdot \overrightarrow {N_1} &= \begin{bmatrix}0-4\\6-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-4\\-3\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 32 + 24 = 56 \\

\overrightarrow {w_1 p_3} \cdot \overrightarrow {N_1} &= \begin{bmatrix}6-4\\6-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}2\\-3\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = -16 + 24 =8 \\

\overrightarrow {w_1 p_4} \cdot \overrightarrow {N_1} &= \begin{bmatrix}3-4\\3-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-1\\-6\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 8 + 48 =56 \\

\overrightarrow {w_1 p_5} \cdot \overrightarrow {N_1} &= \begin{bmatrix}6-4\\0-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}2\\-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = -16 + 72 = 56

\end{align}
$$
From the results above, if it's positive then the point is inside \(\overrightarrow {E_1}\), if negative then the point is outside. Below is the table generated as the result of the calculation above:
$$
\begin{array} {|r|r|}\hline
Edge & p_1 & p_2 & p_3 & p_4 & p_5 \\ \hline
\overrightarrow {E_1} & in & in & in & in & in \\ \hline  \end{array}
 $$
From the table above we can also assign new points for next clipping edge to process as defined below:
$$
\begin{array} {|r|r|}\hline
Edge & Status & Take & As \\ \hline
\overrightarrow {p_1 p_2} & in \ in & endpoint \ p_2 & q_1(0, 6) \\ \hline
\overrightarrow {p_2 p_3} & in \ in & endpoint \ p_3 & q_2(6, 6) \\ \hline
\overrightarrow {p_3 p_4} & in \ in & endpoint \ p_4 & q_3(3, 3) \\ \hline
\overrightarrow {p_4 p_5} & in \ in & endpoint \ p_5 & q_4(6, 0) \\ \hline
\overrightarrow {p_5 p_1} & in \ in & endpoint \ p_1 & q_5(0, 0) \\ \hline
\end{array}

$$

Clipping edge \( \overrightarrow {E_2} \)
$$
\begin{align}

\overrightarrow {w_2 q_1} \cdot \overrightarrow {N_2} &= \begin{bmatrix}0-12\\6-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-12\\5\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 40 = 40 \\

\overrightarrow {w_2 q_2} \cdot \overrightarrow {N_2} &= \begin{bmatrix}6-12\\6-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-6\\5\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 40 = 40 \\

\overrightarrow {w_2 q_3} \cdot \overrightarrow {N_2} &= \begin{bmatrix}3-12\\3-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-9\\2\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 16 = 16 \\

\overrightarrow {w_2 q_4} \cdot \overrightarrow {N_2} &= \begin{bmatrix}6-12\\0-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-6\\-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + (-8) = -8 \\

\overrightarrow {w_2 q_5} \cdot \overrightarrow {N_2} &= \begin{bmatrix}0-12\\0-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-12\\-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + (-8) = -8

\end{align}
$$
From the results above, if it's positive then the point is inside \(\overrightarrow {E_2}\), if negative then the point is outside. Below is the table generated as the result of the calculation above:
$$
\begin{array} {|r|r|}\hline
Edge & q_1 & q_2 & q_3 & q_4 & q_5 \\ \hline
\overrightarrow {E_2} & in & in & in & out & out \\ \hline  \end{array}
 $$
From the table above we can also assign new points for next clipping edge to process as defined below:
$$
\begin{array} {|r|r|}\hline
Edge & Status & Take & As \\ \hline
\overrightarrow {q_1 q_2} & in \ in & endpoint \ q_2 & r_1(6, 6) \\ \hline
\overrightarrow {q_2 q_3} & in \ in & endpoint \ q_3 & r_2(3, 3) \\ \hline
\overrightarrow {q_3 q_4} & in \ out & intersection \ i_1 & r_3(..., ...) \\ \hline
\overrightarrow {q_4 q_5} & out \ out &  do \ nothing &  \\ \hline
\overrightarrow {q_5 q_1} & out \ in & intersection i_2 & r_4(..., ...) \\
&& endpoint \ q_1 & r_5(0, 0) \\ \hline

\end{array}
$$
We must find \(i_1\) and \(i_2\) so we can find out \(r_3\) and \(r_4\)
$$
t_1 = \frac {\overrightarrow {q_3 w_2} \cdot \overrightarrow {N_2}}{\overrightarrow {q_3 q_4} \cdot \overrightarrow {N_2}}= \frac {\begin{bmatrix} 12-3\\1-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} {\begin{bmatrix} 6-3\\0-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}=\frac {\begin{bmatrix} 9\\-2 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} {\begin{bmatrix} 3\\-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}=\frac{0+(-16)}{0+(-24)}=\frac {2}{3}
$$
We know that \(q_3\)(3, 3) and \(q_4\)(6, 0)
$$
\begin{align}
Ox &= q_3 x + t_1 (q_4 x - q_3 x)\\
&=3 + \frac {2}{3}(6 - 3)\\
&=3 + \frac {2}{3}(3) \\
&=3 + 2\\
Ox &= 5
\end{align}

$$
$$
\begin{align}
Oy &= q_3 y + t_1 (q_4 y - q_3 y)\\
&=3 + \frac {2}{3}(0 - 3)\\
&=3 + \frac {2}{3}(-3) \\
&=3 + (-2)\\
Oy &= 1
\end{align}$$
We got \(i_1\)(5, 1). Now for \(i_2\)
$$
t_2 = \frac {\overrightarrow {q_5 w_2} \cdot \overrightarrow {N_2}}{\overrightarrow {q_5 q_1} \cdot \overrightarrow {N_2}}= \frac {\begin{bmatrix} 12-0\\1-0 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} {\begin{bmatrix} 0-6\\6-0 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}=\frac {\begin{bmatrix} 12\\1\end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} {\begin{bmatrix} 0\\6 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}=\frac{0+8}{0+48}=\frac {1}{6}
$$
We know that \(q_5\)(0, 0) and \(q_1\)(0, 6)
$$
\begin{align}
Ox &= q_5 x + t_2 (q_1 x - q_5 x)\\
&=0 + \frac {1}{6}(0 - 0)\\
&=\frac {1}{6}(0) \\
Ox &= 0
\end{align}

$$
$$
\begin{align}
Oy &= q_5 y + t_2 (q_1 y - q_5 y)\\
&=0 + \frac {1}{6}(6 - 0)\\
&=\frac {1}{6}(6) \\
Oy &= 1
\end{align}$$
So we've got \(i_2\)(0, 1). \(r_3\) is \(i_1\) so \(r_3\)(5, 1) and \(r_4\) is \(i_2\) so \(r_4\)(0, 1). Below is the final table for \(\overrightarrow {E_2}\) clipping edge
$$
\begin{array} {|r|r|}\hline
Edge & Status & Take & As \\ \hline
\overrightarrow {q_1 q_2} & in \ in & endpoint \ q_2 & r_1(6, 6) \\ \hline
\overrightarrow {q_2 q_3} & in \ in & endpoint \ q_3 & r_2(3, 3) \\ \hline
\overrightarrow {q_3 q_4} & in \ out & intersection \ i_1 & r_3(5, 1) \\ \hline
\overrightarrow {q_4 q_5} & out \ out &  do \ nothing &  \\ \hline
\overrightarrow {q_5 q_1} & out \ in & intersection i_2 & r_4(0, 1) \\
&& endpoint \ q_1 & r_5(0, 0) \\ \hline

\end{array}
$$

Clipping edge \( \overrightarrow {E_3} \)
$$
\begin{align}

\overrightarrow {w_3 r_1} \cdot \overrightarrow {N_3} &= \begin{bmatrix}6-4\\6-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}2\\5\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = 16 + 0 = 16 \\

\overrightarrow {w_3 r_2} \cdot \overrightarrow {N_3} &= \begin{bmatrix}3-4\\3-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-1\\2\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -8 + 0 = -8 \\

\overrightarrow {w_3 r_3} \cdot \overrightarrow {N_3} &= \begin{bmatrix}5-4\\1-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}1\\0\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = 8 + 0 = 8 \\

\overrightarrow {w_3 r_4} \cdot \overrightarrow {N_3} &= \begin{bmatrix}0-4\\1-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-4\\0\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -32 + 0 = -32 \\

\overrightarrow {w_3 r_5} \cdot \overrightarrow {N_3} &= \begin{bmatrix}0-4\\6-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-4\\5\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -32 + 0 = -32 \\

\end{align}
$$
From the results above, if it's positive then the point is inside \(\overrightarrow {E_3}\), if negative then the point is outside. Below is the table generated as the result of the calculation above:
$$
\begin{array} {|r|r|}\hline
Edge & r_1 & r_2 & r_3 & r_4 & r_5 \\ \hline
\overrightarrow {E_3} & in & out & in & out & out \\ \hline  \end{array}
 $$
From the table above we can also assign new points for next clipping edge to process as defined below:
$$
\begin{array} {|r|r|}\hline
Edge & Status & Take & As \\ \hline
\overrightarrow {r_1 r_2} & in \ out & intersection \ i_1 & s_1(..., ...) \\ \hline
\overrightarrow {r_2 r_3} & out \ in & intersection \ i_2 & s_2(..., ...) \\
&& endpoint \ r_3 & s_3(5, 1)\\ \hline
\overrightarrow {r_3 r_4} & in \ out & intersection \ i_3 & s_4(..., ...) \\ \hline
\overrightarrow {r_4 r_5} & out \ out &  do \ nothing &  \\ \hline
\overrightarrow {r_5 r_1} & out \ in & intersection \ i_4 & s_5(..., ...) \\
&& endpoint \ r_1 & s_6(6, 6) \\ \hline

\end{array}
$$
We must find \(i_1\), \(i_2\), \(i_3\), and \(i_4\) so we can find out \(s_1\), \(s_2\), \(s_4\), and \(s_5\)
$$
t_1 = \frac {\overrightarrow {r_1 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {r_1 r_2} \cdot \overrightarrow {N_3}}= \frac {\begin{bmatrix} 4-6\\1-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 3-6\\3-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac {\begin{bmatrix} -2\\-5\end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} -3\\-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac{-16+0}{-24+0}=\frac {2}{3}
$$
We know that \(r_1\)(6, 6) and \(r_2\)(3, 3)
$$
\begin{align}
Ox &= r_1 x + t_1 (r_2 x - r_1 x)\\
&=6 + \frac {2}{3}(3 - 6)\\
&=6 + \frac {2}{3}(-3) \\
&=6 + (-2)\\
Ox &= 4
\end{align}

$$
$$
\begin{align}
Oy &= r_1 y + t_1 (r_2 y - r_1 y)\\
&=6 + \frac {2}{3}(3 - 6)\\
&=6 + \frac {2}{3}(-3) \\
&=6 + (-2)\\
Oy &= 4
\end{align}$$
We got \(i_1\)(4, 4). Now for \(i_2\)
$$
t_2 = \frac {\overrightarrow {r_2 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {r_2 r_3} \cdot \overrightarrow {N_3}}= \frac {\begin{bmatrix} 4-3\\1-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 5-3\\1-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac {\begin{bmatrix} 1\\-2\end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 2\\-2 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac{8+0}{16+0}=\frac {1}{2}
$$
We know that \(r_2\)(3, 3) and \(r_3\)(5, 1)
$$
\begin{align}
Ox &= r_2 x + t_2 (r_3 x - r_2 x)\\
&=3 + \frac {1}{2}(5 - 3)\\
&=3 + \frac {1}{2}(2) \\
&=3 + 1\\
Ox &= 4
\end{align}

$$
$$
\begin{align}
Oy &= r_2 y + t_2 (r_3 y - r_2 y)\\
&=3 + \frac {1}{2}(1 - 3)\\
&=3 + \frac {1}{2}(-2) \\
&=3 + (-1)\\
Oy &= 2
\end{align}$$
So we've got \(i_2\)(4, 2). Now for \(i_3\)
$$
t_3 = \frac {\overrightarrow {r_3 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {r_3 r_4} \cdot \overrightarrow {N_3}}= \frac {\begin{bmatrix}4-5\\1-1 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 0-5\\1-1 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac {\begin{bmatrix} -1\\0\end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} -5\\0 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac{-8+0}{-40+0}=\frac {1}{5}
$$
We know that \(r_3\)(5, 1) and \(r_4\)(0, 1)
$$
\begin{align}
Ox &= r_3 x + t_3 (r_4 x - r_3 x)\\
&=5 + \frac {1}{5}(0 - 5)\\
&=5 + \frac {1}{5}(-5) \\
&=5 + (-1)\\
Ox &= 4
\end{align}

$$
$$
\begin{align}
Oy &= r_3 y + t_3 (r_4 y - r_3 y)\\
&=1 + \frac {1}{5}(1 - 1)\\
&=1 + \frac {1}{2}(0) \\
&=1 + 0\\
Oy &= 1
\end{align}$$
So we've got \(i_3\)(4, 1). Now for \(i_4\)
$$
t_4 = \frac {\overrightarrow {r_5 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {r_5 r_1} \cdot \overrightarrow {N_3}}= \frac {\begin{bmatrix}4-0\\1-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 6-0\\6-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac {\begin{bmatrix} 4\\-5\end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} {\begin{bmatrix} 6\\0 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}=\frac{32+0}{48+0}=\frac {2}{3}
$$
We know that \(r_5\)(0, 6) and \(r_1\)(6, 6)
$$
\begin{align}
Ox &= r_5 x + t_4 (r_1 x - r_5 x)\\
&= 0 + \frac {2}{3}(6 - 0)\\
&= \frac {2}{3}(6) \\
Ox &= 4
\end{align}

$$
$$
\begin{align}
Oy &= r_5 y + t_4 (r_1 y - r_5 y)\\
&=6 + \frac {2}{3}(6 - 6)\\
&=6 + \frac {2}{3}(0) \\
&=6 + 0\\
Oy &= 6
\end{align}$$
So we've got \(i_4\)(4, 6). \(s_1\) is \(i_1\) so \(s_1\)(4, 4), \(s_2\) is \(i_2\) so \(s_2\)(4, 2), \(s_4\) is \(i_3\) so \(s_4\)(4, 1), and \(s_5\) is \(i_4\) so \(s_5\)(4, 6). Below is the final table for \(\overrightarrow {E_3}\) clipping edge
$$
\begin{array} {|r|r|}\hline
Edge & Status & Take & As \\ \hline
\overrightarrow {r_1 r_2} & in \ out & intersection \ i_1 & s_1(4, 4) \\ \hline
\overrightarrow {r_2 r_3} & out \ in & intersection \ i_2 & s_2(4, 2) \\
&& endpoint \ r_3 & s_3(5, 1)\\ \hline
\overrightarrow {r_3 r_4} & in \ out & intersection \ i_3 & s_4(4, 1) \\ \hline
\overrightarrow {r_4 r_5} & out \ out &  do \ nothing &  \\ \hline
\overrightarrow {r_5 r_1} & out \ in & intersection \ i_4 & s_5(4, 6) \\
&& endpoint \ r_1 & s_6(6, 6) \\ \hline

\end{array}
$$
The result of Sutherland-Hodgman Method for this polygon is \(s_1\)(4, 4), \(s_2\)(4, 2), \(s_3\)(5, 1), \(s_4\)(4, 1), \(s_5\)(4, 6), and \(s_6\)(6, 6).

Weiler-Atherton Method
First of all we need to create the table
$$
\begin{align}

\overrightarrow {w_1 p_1} \cdot \overrightarrow {N_1} &= \begin{bmatrix}0-4\\0-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-4\\-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 32 + 72 = 104 \\

\overrightarrow {w_1 p_2} \cdot \overrightarrow {N_1} &= \begin{bmatrix}0-4\\6-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-4\\-3\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 32 + 24 = 56 \\

\overrightarrow {w_1 p_3} \cdot \overrightarrow {N_1} &= \begin{bmatrix}6-4\\6-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}2\\-3\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = -16 + 24 = 8 \\

\overrightarrow {w_1 p_4} \cdot \overrightarrow {N_1} &= \begin{bmatrix}3-4\\3-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}-1\\-6\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = 8 + 48 = 56 \\

\overrightarrow {w_1 p_5} \cdot \overrightarrow {N_1} &= \begin{bmatrix}6-4\\0-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = \begin{bmatrix}2\\-9\end{bmatrix} \cdot \begin{bmatrix}-8\\-8\end{bmatrix} = -16 + 72 = 56

\end{align}
$$

$$
\begin{align}

\overrightarrow {w_2 p_1} \cdot \overrightarrow {N_2} &= \begin{bmatrix}0-12\\0-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-12\\-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + (-8) = -8 \\

\overrightarrow {w_2 p_2} \cdot \overrightarrow {N_2} &= \begin{bmatrix}0-12\\6-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-12\\5\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 40 = 40 \\

\overrightarrow {w_2 p_3} \cdot \overrightarrow {N_2} &= \begin{bmatrix}6-12\\6-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-6\\5\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 40 = 40 \\

\overrightarrow {w_2 p_4} \cdot \overrightarrow {N_2} &= \begin{bmatrix}3-12\\3-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-9\\2\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + 16 = 16 \\

\overrightarrow {w_2 p_5} \cdot \overrightarrow {N_2} &= \begin{bmatrix}6-12\\0-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = \begin{bmatrix}-6\\-1\end{bmatrix} \cdot \begin{bmatrix}0\\8\end{bmatrix} = 0 + (-8) = -8

\end{align}
$$


$$
\begin{align}

\overrightarrow {w_3 p_1} \cdot \overrightarrow {N_3} &= \begin{bmatrix}0-4\\0-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-4\\-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -32 + 0 = -32 \\

\overrightarrow {w_3 p_2} \cdot \overrightarrow {N_3} &= \begin{bmatrix}0-4\\6-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-4\\5\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -32 + 0 = -32 \\

\overrightarrow {w_3 p_3} \cdot \overrightarrow {N_3} &= \begin{bmatrix}6-4\\6-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}2\\5\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = 16 + 0 = 16 \\

\overrightarrow {w_3 p_4} \cdot \overrightarrow {N_3} &= \begin{bmatrix}3-4\\3-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}-1\\2\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = -8 + 0 = -8 \\

\overrightarrow {w_3 p_5} \cdot \overrightarrow {N_3} &= \begin{bmatrix}6-4\\0-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = \begin{bmatrix}2\\-1\end{bmatrix} \cdot \begin{bmatrix}8\\0\end{bmatrix} = 16 + 0 = 16 \\

\end{align}
$$

$$
\begin{array} {|r|r|}\hline
Edge & p_1 & p_2 & p_3 & p_4 & p_5 \\ \hline
\overrightarrow {E_1} & in & in & in & in & in \\ \hline
\overrightarrow {E_2} & out & in & in & in & out \\ \hline
\overrightarrow {E_3} & out & out & in & out & in \\ \hline  \end{array}
$$

Now we create the intersection table by choosing the edge of a polygon with at least 2 in's for each of their starting and ending points. Intersection occurs whenever the starting point and ending point have different status. See below for the table

$$
\begin{array} {|r|r|}\hline
Edge Poly & Status & Edge Window & Intersection \\ \hline
\overrightarrow {p_2 p_3} & out \ in & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_1(..., ...) \\ \hline
\overrightarrow {p_3 p_4} & in \ out & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_2(..., ...) \\ \hline
\overrightarrow {p_4 p_5} & out \ in & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_3(..., ...) \\ \hline
\overrightarrow {p_4 p_5} & in \ out & \overrightarrow {E_2} \ or \ \overrightarrow {w_2 w_3} & i_4(..., ...) \\ \hline  \end{array}
$$

From the table above we can also tell the sequence of polygon including the intersections and window clipping including the intersections.

$$
\begin{array} a
Polygon: \ p_1 \rightarrow p_2 \rightarrow i_1 \rightarrow p_3 \rightarrow i_2 \rightarrow p_4 \rightarrow i_3 \rightarrow i_4 \rightarrow p_5 \rightarrow p_1 \\
Window: \ w_1 \rightarrow w_2 \rightarrow i_4 \rightarrow w_3 \rightarrow i_3 \rightarrow i_2 \rightarrow i_1 \rightarrow w_1
\end{array}

$$
From the pattern we also can see that because of the clockwise direction for each shape (polygon and window clipping) the sequence for intersection for each shape is reversed. Now for finding the intersection of each we'll do some calculation

$$
t_1 = \frac {\overrightarrow {p_2 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {p_2 p_3} \cdot \overrightarrow {N_3}} = \frac {\begin{bmatrix} 4-0\\1-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} 6-0\\6-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {\begin{bmatrix} 4\\-5 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} 6\\0 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {32+0}{48+0}= \frac {2}{3}
$$
We know that \(p_2\)(0, 6) and \(p_3\)(6, 6)
$$
\begin{align}
Ox &= p_2 x + t_1 (p_3 x - p_2 x) \\
&= 0 + \frac {2}{3} (6-0) \\
&= \frac {2}{3}(6) \\
Ox &= 4
\end{align}
$$

$$
\begin{align}
Oy &= p_2 y + t_1 (p_3 y - p_2 y) \\
&= 6 + \frac {2}{3} (6-6) \\
&= 6 + \frac {2}{3}(0) \\
Oy &= 6
\end{align}
$$
So we've got \( i_1 \)(4, 6). Next is \( i_2 \)

$$
t_2 = \frac {\overrightarrow {p_3 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {p_3 p_4} \cdot \overrightarrow {N_3}} = \frac {\begin{bmatrix} 4-6\\1-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} 3-6\\3-6 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {\begin{bmatrix} -2\\-5 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} -3\\-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {-16+0}{-24+0}= \frac {2}{3}
$$
We know that \(p_3\)(6, 6) and \(p_4\)(3, 3)
$$
\begin{align}
Ox &= p_3 x + t_2 (p_4 x - p_3 x) \\
&= 6 + \frac {2}{3} (3-6) \\
&= 6 + \frac {2}{3}(-3) \\
&= 6 + (-2) \\
Ox &= 4
\end{align}
$$

$$
\begin{align}
Oy &= p_3 y + t_2 (p_4 y - p_3 y) \\
&= 6 + \frac {2}{3} (3-6) \\
&= 6 + \frac {2}{3}(-3) \\
&= 6 + (-2) \\
Oy &= 4
\end{align}
$$
So we've got \( i_2 \)(4, 4). Next is \( i_3 \)

$$
t_3 = \frac {\overrightarrow {p_4 w_3} \cdot \overrightarrow {N_3}}{\overrightarrow {p_4 p_5} \cdot \overrightarrow {N_3}} = \frac {\begin{bmatrix} 4-3\\1-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} 6-3\\0-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {\begin{bmatrix} 1\\-2 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}}{\begin{bmatrix} 3\\-3 \end{bmatrix} \cdot \begin{bmatrix} 8\\0 \end{bmatrix}} = \frac {8+0}{24+0}= \frac {1}{3}
$$
We know that \(p_4\)(3, 3) and \(p_5\)(6, 0)
$$
\begin{align}
Ox &= p_4 x + t_3 (p_5 x - p_4 x) \\
&= 3 + \frac {1}{3} (6-3) \\
&= 3 + \frac {1}{3}(3) \\
&= 3 + 1 \\
Ox &= 4
\end{align}
$$

$$
\begin{align}
Oy &= p_4 y + t_3 (p_5 y - p_4 y) \\
&= 3 + \frac {1}{3} (0-3) \\
&= 3 + \frac {1}{3}(-3) \\
&= 3 + (-1) \\
Oy &= 2
\end{align}
$$

So we've got \( i_3 \)(4, 2). Next is \( i_4 \)


$$
t_4 = \frac {\overrightarrow {p_4 w_2} \cdot \overrightarrow {N_2}}{\overrightarrow {p_4 p_5} \cdot \overrightarrow {N_2}} = \frac {\begin{bmatrix} 12-3\\1-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}{\begin{bmatrix} 6-3\\0-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} = \frac {\begin{bmatrix} 9\\-2 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}}{\begin{bmatrix} 3\\-3 \end{bmatrix} \cdot \begin{bmatrix} 0\\8 \end{bmatrix}} = \frac {0+(-16)}{0+(-24)}= \frac {2}{3}
$$
We know that \(p_4\)(3, 3) and \(p_5\)(6, 0)
$$
\begin{align}
Ox &= p_4 x + t_4 (p_5 x - p_4 x) \\
&= 3 + \frac {2}{3} (6-3) \\
&= 3 + \frac {2}{3}(3) \\
&= 3 + 2 \\
Ox &= 5
\end{align}
$$

$$
\begin{align}
Oy &= p_4 y + t_4 (p_5 y - p_4 y) \\
&= 3 + \frac {2}{3} (0-3) \\
&= 3 + \frac {2}{3}(-3) \\
&= 3 + (-2) \\
Oy &= 1
\end{align}
$$
So we've got \(i_4\)(5, 1). Now let's see what we've got so far, \(i_1\)(4, 6), \(i_2\)(4, 4), \(i_3\)(4, 2), and \(i_4\)(5, 1). Let's put them into this table

$$
\begin{array} {|r|r|}\hline
Edge Poly & Status & Edge Window & Intersection \\ \hline
\overrightarrow {p_2 p_3} & out \ in & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_1(4, 6) \\ \hline
\overrightarrow {p_3 p_4} & in \ out & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_2(4, 4) \\ \hline
\overrightarrow {p_4 p_5} & out \ in & \overrightarrow {E_3} \ or \ \overrightarrow {w_3 w_1} & i_3(4, 2) \\ \hline
\overrightarrow {p_4 p_5} & in \ out & \overrightarrow {E_2} \ or \ \overrightarrow {w_2 w_3} & i_4(5, 1) \\ \hline  \end{array}
$$
The last step would be to determine the final polygon, we can do that by drawing the graph of Circular List of Polygon (CLP) and Circular List of Window (CLW) based on the sequence we've found earlier, refer to the graph below:
$$
\begin{array} a
Polygon: \ p_1 \rightarrow p_2 \rightarrow i_1 \rightarrow p_3 \rightarrow i_2 \rightarrow p_4 \rightarrow i_3 \rightarrow i_4 \rightarrow p_5 \rightarrow p_1 \\
Window: \ w_1 \rightarrow w_2 \rightarrow i_4 \rightarrow w_3 \rightarrow i_3 \rightarrow i_2 \rightarrow i_1 \rightarrow w_1
\end{array}

$$
From the sequence above we turn it into a graph just like below, and we can determine whether an intersection is entering or leaving from the last table.
Final graph
Rules to determining output polygon:
  1. Start at entering \(i\) (double circle)
  2. Traverse on CLP line until encounter leaving \(i\), and change to CLW line (3) 
  3. Traverse on CLW line until encounter entering \(i\), and change to CLP line (2)
  4. Repeat until encounter starting \(i\) (1)

From the graph and rules above, we can conclude the output polygons as:
  1. \(i_1 (4, 6) \rightarrow p_3 (6, 6) \rightarrow i_2 (4, 4) \Rightarrow i_1 (4, 6) \)
  2. \( i_3 (4, 2) \rightarrow i_4 (5, 1) \Rightarrow w_3 (4, 1) \Rightarrow i_3 (4, 2) \)


Comments

Post a Comment

Popular posts from this blog

2D CGA - Midtest 2014

-
Image
COMPUTER GRAPHICS AND ANIMATION MID TEST 150 minutes. Open book. No electronic devices allowed. Answer the questions below. You can score more than 100, but the maximum score is capped to 100. There are a lot of questions and you might not have enough time to answer all of them. Start by answering the questions that you think are easy to answer. The questions are not too hard to answer; if you paid attention during class, tried doing the review questions and exercises at the end of each PPT file, and did the homeworks without mindlessly copying them from someone else, you should not have too much trouble answering the questions. But should you become frustrated during the test, feel free to create your own handmade graphics on your answer sheet. The basics Explain the difference between Computer Graphics, Image Processing, and Image Interpretation. Give an example for each. (10 points) Answer Computer graphics is a field that focused on
Read more

HW 2D CGA - PPT 5 - Clipping 2

-
Image
Question 1 Solution: We need to declare:  $$A=\begin{bmatrix}2\\7\end{bmatrix}, B=\begin{bmatrix}10\\2\end{bmatrix}, C=\begin{bmatrix}7\\4\end{bmatrix}$$ And then find \(\overrightarrow {AB}\) and \(\vec N\): $$\overrightarrow {AB}=\begin{bmatrix}10-2\\2-7\end{bmatrix}=\begin{bmatrix}8\\-5\end{bmatrix}$$ Here are some basic rule you need to know to easily define \(\vec N\): $$if \ \vec N \ is \ to \ the \ left \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}$$  $$if \ \vec N \ is \ to \ the \ right \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}dy\\-dx\end{bmatrix}$$ From the rule above, we can see that because \(\vec N\) is facing to the left (up as stated in the question) of \(\overrightarrow {AB}\), we can conclude as stated below: $$\vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}=\begin{bmatrix}5\\8\end{bmatrix}$$ Variable \(dx\) and \(dy\) is taken from \(\overrightarrow {AB}\). After that the question requires us to find \(\o
Read more

HW 2D CGA - PPT 8 - Polygon Fill

-
Image
Question Solution: First of all, we need to know the element to be inserted into SET and AEL. The element must contain \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Also carry but only in AEL, carry doesn't need to be inserted into SET. With that said, let's begin with the first polygon. Polygon 1 A(1, 6), B(5,4), C(3,1) From these 3 vertices we need to find the edges element containing \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Let's take a look at edge AB , the \(y_{max}\) is 6, the \(x \ of \ y_{min}\) is 5, the \(dx\) is 4, and the \(dy\) is -2. Now if we found \(dy < 0\) we need to make it positive, by multiplying \(dx\) and \(dy\) with -1, so we got \(dx\) = -4 and \(dy\) = 2. The same rule applies with edges BC and CA. After we've found all of the elements then, we put it into the SET just like below. SET y Edges \(y_{max}\) 6 5 4 \( \rightarrow AB \) 6 5 -4 2 3 2 \(y_{min}\) 1 \( \rightarrow
Read more