Computer Graphics 1996

Answers on Polygons, Planes and Vertex-Face Data Structure

These are for the exercise classes. Questions that have a * besides them are more difficult and should be considered at some time, but not necessarily now.

1. A polygon has three points (0,1,0), (1,2,2) and (2,1,2) given in anti-clockwise order when looking from the front.

(a) Find the plane equation.

We use the formula [(p1-p0)*(p2-p0)].(p-p0) = 0 where p = (x,y,z) an arbitrary point on the plane.

n = (p1-p0)*(p2-p0) = (1,1,2)*(2,0,2) = (2,2,-2).

n.p0 = (2,2,-2).(0,1,0) = 2.

Therefore the plane equation is:

2x + 2y - 2z = 2 or x + y - z = 1.
(As a check substitute each of the 3 points into this equation).
(b) Classify each of the following points as in front, behind or on the plane of the polygon:
(i) (2,4,5) 
Let l(x,y,z) = x + y - z - 1. Then l(X,Y,Z) > 0 is in "front", < 0 "behind", = 0 "on".

l(2,4,5) = 0, so "on".
(ii) (3,3,3) 
l(3,3,3) = 2 so "front".
(iii) (1,0,3) 
l(1,0,3) = -3 so "behind"
(iv) (-1,-1,-1) 
l(-1,-1,-1) = -2, so "behind".

2. Where does the line that joins (1,1,1) to (2,4,6) intersect this plane?

The equation of the line is p(t) = (1 + t, 1 + 3t, 1 + 5t). This point, to be on the plane must satisfy: x + y - z = 1. So,

(1+t) + (1+3t) - (1+5t) = 1,
therefore,
1 - t = 1, so t = 0.
Therefore the intersection point is (1,1,1) (at the very start of the line segment).
3. Give the complete specification of of the Vertex-Face data structure for a cube with edge lengths 1, with one corner at the origin, and with edges parallel to the (positive) principal axes. Make sure that you specify the polygons with vertices in the correct order. 

The vertex list is:

v0 (0,0,0)
v1 (1,0,0)
v2 (1,1,0)
v3 (0,1,0)
v4 (0,0,1)
v5 (1,0,1)
v6 (1,1,1)
v7 (0,1,1)

Then the faces are:

0,1,5,4
1,2,6,5
4,5,6,7
3,7,6,2
0,3,2,1
0,4,7,3

Each is given in anti-clockwise order when looking from outside the cube.
4*. Given a plane equation ax + by + cz = d and a convex planar polygon p[0], p[1], ..., p[n-1], there are a number of possible relationships between the plane and the polygon:

  1. The entire polygon might be in front of the plane;

  2. The entire polygon might be behind the plane;

  3. The polygon might be on the plane;

  4. The plane might split the polygon into a front polygon and a back polygon.

Construct an algorithm that computes the classification of the polygon with respect to the plane. The algorithm will always return a front and a back polygon, except that in case 1 the back polygon is null, in case 2 the front is null, in case 3 both are null, and in case 4 neither are null. (This algorithm is for the construction of Binary Space Partition trees, which is used as a method of hidden surface removal).