Computer Graphics 1996

Exercises 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.

(b) Classify each of the following points as in front, behind or on the plane of the polygon:

(i) (2,4,5)
(ii) (3,3,3)
(iii) (1,0,3)
(iv) (-1,-1,-1)

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

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.

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).