Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/geometric-modelling/3/g/solution

Insert the points in their given order, starting from . Use outward face orientation and regard as the interior side. The initial tetrahedron is nondegenerate because
Thus its volume is . The following table gives consistently oriented faces, conveniently scaled plane equations, and the omitted old vertex of a polyhedron test:
Face orderInterior inequalityValue at the opposite vertex
Every opposite vertex of a polyhedron is strictly on the interior side, so these orientations are correct. The intersection of these four half-spaces is exactly the initial tetrahedron.
Now test . In the same row order the face expressions give
Therefore and are visible and must be removed; and are retained. The common edge lies inside the deleted patch and is removed. The directed horizon is
Cone this cycle to , giving outward face orders . Their equations and tests of the two old vertices of a polyhedron not belonging to each face are:
New faceInterior inequalityTests of the other vertices
Each new plane contains its three named vertices of a polyhedron and has all remaining input points strictly on the interior side. Together with the two retained half-spaces, these six supporting inequalities describe the final convex hull:
Equivalently assemble the closed oriented boundary from , with adjacent face loops traversing shared edges in opposite directions. It is a triangular bipyramid with base triangle and apices ; is internal, so it is not a boundary face. There are five vertices of a polyhedron, nine edges and six faces, giving the check . The initial tetrahedron similarly has .
Figure 1.
Initial tetrahedron, the two faces visible from E and their horizon, and the final six-face convex hull
. Details.

New to topics? Read the docs here!