Clipping and Hidden Surface Determination Exercises

Exercise 21

Use the Cyrus-Beck algorithm to clip the lines \(\mathbf{a} \to \mathbf{b}\), \(\mathbf{c} \to \mathbf{d}\) and \(\mathbf{e} \to \mathbf{f}\) to the visible region shown in the diagram below.

Solution to Exercise 21

Line \(\mathbf{a} \to \mathbf{b}\): clip to bottom edge

\[\begin{split} \begin{align*} d(\mathbf{a}) &= (\mathbf{a} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 2 \\ -1 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \end{pmatrix} \right) \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix} = -1, \\ d(\mathbf{b}) &= (\mathbf{b} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \end{pmatrix} \right) \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 1, \end{align*} \end{split}\]

\(d(\mathbf{a}) < 0\) and \(d(\mathbf{b}) > 0\) so clip \(\mathbf{a}\) to bottom edge

\[\begin{split} \begin{align*} t &= \frac{d(\mathbf{a})}{d(\mathbf{a}) - d(\mathbf{b})} = \frac{-1}{-1-1} = \frac{1}{2}, \\ \mathbf{a} &= \mathbf{a} + t(\mathbf{b} - \mathbf{a}) = \begin{pmatrix} 2 \\ -1 \end{pmatrix} + \frac{1}{2} + \left( \begin{pmatrix} 2 \\ -1 \end{pmatrix} - \begin{pmatrix} 2 \\ 1 \end{pmatrix} \right) = \begin{pmatrix} 2 \\ 0 \end{pmatrix}. \end{align*} \end{split}\]

Clip \(\mathbf{c} \to \mathbf{d}\) to right edge

\[\begin{split} \begin{align*} d(\mathbf{c}) &= (\mathbf{c} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 5 \\ 2 \end{pmatrix} - \begin{pmatrix} 4 \\ 3 \end{pmatrix} \right) \cdot \begin{pmatrix} -1 \\ 0 \end{pmatrix} = -1, \\ d(\mathbf{d}) &= (\mathbf{d} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 3 \\ 1 \end{pmatrix} - \begin{pmatrix} 4 \\ 3 \end{pmatrix} \right) \cdot \begin{pmatrix} -1 \\ 0 \end{pmatrix} = 1, \end{align*} \end{split}\]

\(d(\mathbf{c}) < 0\) and \(d(\mathbf{d}) > 0\) so clip \(\mathbf{c}\) to right edge

\[\begin{split} \begin{align*} t &= \frac{d(\mathbf{c})}{d(\mathbf{c}) - d(\mathbf{d})} = \frac{-1}{-1-1} = \frac{1}{2}, \\ \mathbf{c} &= \mathbf{c} + t(\mathbf{d} - \mathbf{c}) = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \frac{1}{2} \left( \begin{pmatrix} 5 \\ 2 \end{pmatrix} - \begin{pmatrix} 3 \\ 1 \end{pmatrix} \right) = \begin{pmatrix} 4 \\ 3/2 \end{pmatrix}. \end{align*} \end{split}\]

Clip \(\mathbf{e} \to \mathbf{f}\) to top edge

\[\begin{split} \begin{align*} d(\mathbf{e}) &= (\mathbf{e} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} -1 \\ 1 \end{pmatrix} - \begin{pmatrix} 1 \\ 1 \end{pmatrix} \right) \cdot \begin{pmatrix} 0 \\ -1 \end{pmatrix} = 2, \\ d(\mathbf{f}) &= (\mathbf{f} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 3 \\ 4 \end{pmatrix} - \begin{pmatrix} 1 \\ 1 \end{pmatrix} \right) \cdot \begin{pmatrix} 0 \\ -1 \end{pmatrix} = -1, \end{align*} \end{split}\]

\(d(\mathbf{e}) > 0\) and \(d(\mathbf{f}) < 0\) so clip \(\mathbf{f}\) to top edge

\[\begin{split} \begin{align*} t &= \frac{d(\mathbf{e})}{d(\mathbf{e}) - d(\mathbf{f})} = \frac{2}{2 - (-1)} = \frac{2}{3}, \\ \mathbf{f} &= \mathbf{e} + t (\mathbf{f} - \mathbf{e}) = \begin{pmatrix} -1 \\ 1 \end{pmatrix} + \frac{2}{3} \left( \begin{pmatrix} 3 \\ 4 \end{pmatrix} - \begin{pmatrix} -1 \\ 1 \end{pmatrix} \right) = \begin{pmatrix} 5/3 \\ 3 \end{pmatrix}. \end{align*} \end{split}\]

Clip \(\mathbf{e} \to \mathbf{f}\) to left edge

\[\begin{split} \begin{align*} d(\mathbf{e}) = (\mathbf{e} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} -1 \\ 1 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \end{pmatrix} \right) \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} = -1, \\ d(\mathbf{f}) = (\mathbf{f} - \mathbf{p}) \cdot \mathbf{n} = \left( \begin{pmatrix} 5/3 \\ 3 \end{pmatrix} - \begin{pmatrix} 0 \\ 0 \end{pmatrix} \right) \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{5}{3},\\ \end{align*} \end{split}\]

\(d(\mathbf{e}) < 0\) and \(d(\mathbf{f}) > 0\) so clip \(\mathbf{e}\) to left edge

\[\begin{split} \begin{align*} t &= \frac{d(\mathbf{e})}{d(\mathbf{e}) - d(\mathbf{f})} = \frac{-1}{-1 - \frac{5}{3}} = \frac{3}{8}, \\ \mathbf{e} &= \mathbf{e} + t (\mathbf{f} - \mathbf{e}) = \begin{pmatrix} -1 \\ 1 \end{pmatrix} + \frac{3}{8} \left( \begin{pmatrix} 5/3 \\ 3 \end{pmatrix} - \begin{pmatrix} -1 \\ 1 \end{pmatrix} \right) = \begin{pmatrix} 0 \\ 7/4 \end{pmatrix}. \end{align*} \end{split}\]

Exercise 22

Use the Sutherland-Hodgman algorithm to clip the polygon with vertices \(\mathbf{v}_1\), \(\mathbf{v}_2\) and \(\mathbf{v}_3\) to the rectangle shown below

Solution to Exercise 22

Bottom edge: \(inputlist = \{ \mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \}\), \(outputlist = \emptyset\)

• \(\mathbf{v}_1\) is behind and \(\mathbf{v}_3\) is in front so clip \(\mathbf{v}_3 \to \mathbf{v}_1\) to \(\mathbf{i}_1\) and add to \(outputlist\)

• \(\mathbf{v}_2\) is in front and \(\mathbf{v}_1\) is behind so clip \(\mathbf{v}_1 \to \mathbf{v}_2\) to \(\mathbf{i}_2\) and add \(\mathbf{i}_2\) and \(\mathbf{v}_2\) to \(outputlist\)

• \(\mathbf{v}_3\) is in front so add to \(outputlist\)

\[ outputlist = \{ \mathbf{i}_1, \mathbf{i}_2, \mathbf{v}_2, \mathbf{v}_3 \}. \]

Right edge:

• \(\mathbf{i}_1\) is in front so add to \(outputlist\)

• \(\mathbf{i}_2\) is in front so add to \(outputlist\)

• \(\mathbf{v}_2\) is in front so add to \(outputlist\)

• \(\mathbf{v}_3\) is in front so add to \(outputlist\)

\[ outputlist = \{ \mathbf{i}_1, \mathbf{i}_2, \mathbf{v}_2, \mathbf{v}_3 \}. \]

Top edge:

• \(\mathbf{i}_1\) is in front and \(\mathbf{v}_3\) is behind so clip \(\mathbf{v}_3 \to \mathbf{i}_1\) to \(\mathbf{i}_3\) and add \(\mathbf{i}_3\) and \(\mathbf{i}_1\) to \(outputlist\)

• \(\mathbf{i}_2\) is in front so add to \(outputlist\)

• \(\mathbf{v}_2\) is in front so add to \(outputlist\)

• \(\mathbf{v}_3\) is behind and \(\mathbf{v}_2\) is in front so clip \(\mathbf{v}_2 \to \mathbf{v}_3\) to \(\mathbf{i}_4\) and add to \(outputlist\)

\[ outputlist = \{ \mathbf{i}_3, \mathbf{i}_1, \mathbf{i}_2, \mathbf{v}_2, \mathbf{i}_4 \}. \]

Left edge:

• \(\mathbf{i}_3\) is behind and so is \(\mathbf{i}_4\) so do nothing

• \(\mathbf{i}_1\) is behind and so is \(\mathbf{i}_3\) so do nothing

• \(\mathbf{i}_2\) is in front and \(\mathbf{i}_1\) is behind so clip \(\mathbf{i}_1 \to \mathbf{i}_2\) to \(\mathbf{i}_5\) and add \(\mathbf{i}_5\) and \(\mathbf{i}_2\) to \(outputlist\)

• \(\mathbf{v}_2\) is in front so add to \(outputlist\)

• \(\mathbf{i}_4\) is behind and \(\mathbf{v}_2\) is in front so clip \(\mathbf{v}_2 \to \mathbf{i}_4\) to \(\mathbf{i}_6\) and add to \(outputlist\)

\[ outputlist = \{ \mathbf{i}_5, \mathbf{i}_2, \mathbf{v}_2, \mathbf{i}_6 \}. \]

Exercise 23

A tetrahedron object is defined by the vertex and face matrices

\[\begin{split} \begin{align*} V &= \begin{pmatrix} 1 & 2 & 0 & 1 \\ 1 & 2 & 3 & 0 \\ -7 & -6 & -5 & -4 \\ 1 & 1 & 1 & 1 \end{pmatrix}, & F &= \begin{pmatrix} 3 & 2 & 1 \\ 2 & 3 & 4 \\ 1 & 2 & 4 \\ 3 & 1 & 4 \end{pmatrix}. \end{align*} \end{split}\]

The object is viewed from the origin. Determine which faces of the tetrahedron are front facing.

Solution to Exercise 23

Face 1:

\[\begin{split} \begin{align*} \mathbf{n} &= (\mathbf{v}_2 - \mathbf{v}_3) \times (\mathbf{v}_1 - \mathbf{v}_2) \\ &= \left( \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} - \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} \right) \times \left( \begin{pmatrix} 1 \\ 1 \\ -7 \end{pmatrix} - \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} \right) \\ &= \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ 2 & -1 & -1 \\ -1 & -1 & -1 \end{vmatrix} = \begin{pmatrix} 0 \\ 3 \\ -3 \end{pmatrix}, \\ \mathbf{n} \cdot (\mathbf{v}_3 - \mathbf{p}) &= \begin{pmatrix} 0 \\ 3 \\ -3 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} = 24. \end{align*} \end{split}\]

Since \(\mathbf{n} \cdot (\mathbf{v}_3 - \mathbf{p}) > 0\) then face 1 is back facing.

Face 2:

\[\begin{split} \begin{align*} \mathbf{n} &= (\mathbf{v}_3 - \mathbf{v}_2) \times (\mathbf{v}_4 - \mathbf{v}_3) \\ &= \left( \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} - \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} \right) \times \left( \begin{pmatrix} 1 \\ 0 \\ -4 \end{pmatrix} - \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} \right) \\ &= \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ -2 & 1 & 1 \\ 1 & -3 & 1 \end{vmatrix} = \begin{pmatrix} 4 \\ 3 \\ 5 \end{pmatrix}, \\ \mathbf{n} \cdot (\mathbf{v}_2 - \mathbf{p}) &= \begin{pmatrix} 4 \\ 3 \\ 5 \end{pmatrix} \cdot \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} = -16. \end{align*} \end{split}\]

Since \(\mathbf{n} \cdot (\mathbf{v}_2 - \mathbf{p}) < 0\) then face 2 is front facing.

Face 3:

\[\begin{split} \begin{align*} \mathbf{n} &= (\mathbf{v}_2 - \mathbf{v}_1) \times (\mathbf{v}_4 - \mathbf{v}_2) \\ &= \left( \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} - \begin{pmatrix} 1 \\ 1 \\ -7 \end{pmatrix} \right) \times \left( \begin{pmatrix} 1 \\ 0 \\ -4 \end{pmatrix} - \begin{pmatrix} 2 \\ 2 \\ -6 \end{pmatrix} \right) \\ &= \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ 1 & 1 & 1 \\ -1 & -2 & 2 \end{vmatrix} = \begin{pmatrix} 4 \\ -3 \\ -1 \end{pmatrix}, \\ \mathbf{n} \cdot (\mathbf{v}_1 - \mathbf{p}) &= \begin{pmatrix} 4 \\ -3 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ -7 \end{pmatrix} = 8. \end{align*} \end{split}\]

Since \(\mathbf{n} \cdot (\mathbf{v}_1 - \mathbf{p}) > 0\) then face 3 is back facing.

Face 4:

\[\begin{split} \begin{align*} \mathbf{n} &= (\mathbf{v}_1 - \mathbf{v}_3) \times (\mathbf{v}_4 - \mathbf{v}_1) \\ &= \left( \begin{pmatrix} 1 \\ 1 \\ -7 \end{pmatrix} - \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} \right) \times \left( \begin{pmatrix} 1 \\ 0 \\ -4 \end{pmatrix} - \begin{pmatrix} 1 \\ 1 \\ -7 \end{pmatrix} \right) \\ &= \begin{vmatrix} \mathbf{i} & \mathbf{j} & \mathbf{k} \\ 1 & -2 & -2 \\ 0 & -1 & 3 \end{vmatrix} = \begin{pmatrix} -8 \\ -3 \\ -1 \end{pmatrix}, \\ \mathbf{n} \cdot (\mathbf{v}_3 - \mathbf{p}) &= \begin{pmatrix} -8 \\ -3 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 3 \\ -5 \end{pmatrix} = -4. \end{align*} \end{split}\]

Since \(\mathbf{n} \cdot (\mathbf{v}_3 - \mathbf{p}) < 0\) then face 4 is front facing.

Exercise 24

A plan view of a map of a computer game is shown in the diagram below. Assuming all vectors are facing towards the interior, construct a BSP tree of the map.

Solution to Exercise 24

Note that this solution is not unique.

Exercise 25

A solution to Exercise 24 is shown below.

Determine the rendering order of the polygons when the world is viewed from the positions \(\mathbf{p}\), \(\mathbf{q}\) and \(\mathbf{r}\).

Solution to Exercise 25

Position \(\mathbf{p}\):

\[\begin{split} \begin{align*} & \{W_1,X_2\}, \{T\}, \{U,W_2\}, \{V\}, \{O_2,P,Q\}, \{R\}, \{N,O_1\}, \{M\}, \\ & \{H_2,I\}, \{J\}, \{L\}, \{K,S\}, \{X_1\}, \{Y\}, \{A_1,Z\}, \{D\}, \{G,H_1\}, \\ & \{F\}, \{E\}, \{C\}, \{A_2,B\} \end{align*} \end{split}\]

Position \(\mathbf{q}\):

\[\begin{split} \begin{align*} & \{W_1,X_2\}, \{T\}, \{U,W_2\}, \{V\}, \{O_2,P,Q\}, \{R\}, \{N,O_1\}, \{M\}, \\ & \{L\}, \{J\}, \{H_2,I\}, \{K,S\}, \{A_1,Z\}, \{Y\}, \{X_1\}, \{D\}, \{A_2,B\}, \\ & \{C\}, \{E\}, \{F\}, \{G,H_1\} \end{align*} \end{split}\]

Position \(\mathbf{r}\):

\[\begin{split} \begin{align*} & \{A_2,B\}, \{C\}, \{G,H_1\}, \{F\}, \{E\}, \{D\}, \{A_1,Z\}, \{Y\}, \{X_1\}, \\ & \{K,S\}, \{H_2,I\}, \{J\}, \{L\}, \{M\}, \{N,O_1\}, \{R\}, \{O_2,P,Q\}, \{V\}, \\ & \{U,W_2\}, \{T\}, \{W_1,X_2\} \end{align*} \end{split}\]