Past exam of the computer science course of the University of Oxford / 2015 / Geometric modelling / 3 / g

Insert the points in their given order, starting from $ABCD$. Use outward face orientation and regard $f\le 0$ as the interior side. The initial tetrahedron is nondegenerate becauseThus its volume is $|2|/6=1/3$. The following table gives consistently oriented faces, conveniently scaled plane equations, and the omitted old vertex of a polyhedron test:

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 $E=(1,0,0)$. In the same row order the face expressions giveTherefore $ACB$ and $ABD$ are visible and must be removed; $ADC$ and $BCD$ are retained. The common edge $AB$ lies inside the deleted patch and is removed. The directed horizon isCone this cycle to $E$, giving outward face orders $ACE,CBE,BDE,DAE$. Their equations and tests of the two old vertices of a polyhedron not belonging to each face are:

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 $ADC,BCD,ACE,CBE,BDE,DAE$, with adjacent face loops traversing shared edges in opposite directions. It is a triangular bipyramid with base triangle $CDE$ and apices $A,B$; $CDE$ is internal, so it is not a boundary face. There are five vertices of a polyhedron, nine edges and six faces, giving the check $5-9+6=2$. The initial tetrahedron similarly has $4-6+4=2$.