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

For solid modelling, a polyhedron is a solid whose boundary consists of finitely many planar polygons, called faces, meeting along straight edges and at vertices of a polyhedron. A face is not merely a list of arbitrary spatial points: its boundary must lie in one plane and bound a valid planar region. The boundary is closed and consistently oriented so that inside and outside are defined.

For example, a tetrahedron has four triangular faces, six edges and four vertices of a polyhedron. A more general polyhedron need not be convex and can have handles or cavities. The concise definition is

For an ordinary closed manifold boundary representation, three requirements are:

Together these support the answerFor a connected orientable closed boundary of genus $g$, the Euler characteristic provides an additional check, $V-E+F=2-2g$, when faces are disk-like. The familiar value $2$ applies to a sphere-like shell; it must not be imposed blindly on every polyhedron. Correct counts alone do not exclude intersections or invalid local incidence.

A boundary representation separates geometry, which supplies locations and supporting planes, from topology, which specifies incidence and orientation. A practical winged-edge data structure uses three related record types:

This explicitly stores adjacency rather than recovering it by searching all faces. A half-edge data structure expresses much the same information with two oppositely directed records per undirected edge: each has an origin vertex of a polyhedron, an incident face, its next boundary record and its opposite record; a previous record is often stored as well. The destination can be obtained from the opposite record's origin. This mesh record is distinct from a dangling half-edge of a graph.

The compact implementation answer isThere is deliberate redundancy: the same adjacency can be reached from both an edge and a face, a stored previous edge is recoverable by walking the loop, and a face normal vector can be computed from its ordered noncollinear vertices of a polyhedron. These copies make neighbourhood queries and local edits cheap, and cached plane equations speed geometric tests. They impose consistency obligations: an edit must update reciprocal references, loops, orientations and affected geometric caches together. A half-edge data structure should share the undirected edge's geometry or keep its paired records synchronized.

For a finite nonempty collection $X=\{p_1,\dots ,p_n\}\subset {\mathbb{R}}^3$, its convex hull is the smallest convex set containing all the points. Equivalently, it is the set of all convex combinations:Every convex set containing the $p_i$ must contain these combinations; the displayed set is itself convex and contains each $p_i$, proving the equivalence. For a full-dimensional finite collection this is a convex polyhedron. A collinear or coplanar collection instead has a lower-dimensional convex hull, so the solid case needs a separate dimensionality assumption.

Use the straightforward incremental three-dimensional convex hull algorithm. Assume distinct input points, at least four noncoplanar points, and general position with no four coplanar. Use exact orientation decisions, or robust predicates that certify the same signs. These assumptions avoid the separate bookkeeping for flat faces, points on the boundary and lower-dimensional initial data.

The determinant ${\sigma }_f$ is six times the oriented volume of the tetrahedron $abcp$; only its sign matters. A zero value needs a declared degeneracy policy if the general-position assumption is relaxed.

The data structure update is a separate local operation. Mark visible faces and walk their adjacency to collect the horizon cycle before deleting anything. Remove edges with two visible incident faces; retain horizon edges and their retained-face links. Insert a vertex of a polyhedron record for $p$ and a new edge from $p$ to each horizon vertex of a polyhedron. Add one face per horizon edge, connect its other two edges to its neighbours in the cone, and replace the deleted face reference on each horizon edge. Restore the cyclic boundary references and each retained vertex of a polyhedron's incident-edge reference; remove any old vertices of a polyhedron left without incident faces.

For an outward visible face with boundary edge $a\to b$ on the horizon, the new outward face can be ordered $(a,b,p)$. Its retained neighbour already traverses that edge as $b\to a$. As an independent orientation check, an interior point of the old hull must evaluate negatively against the new face.

The correctness step is geometric: the nonvisible part of a convex polyhedron remains supporting, while sight lines from $p$ to the horizon create precisely the new supporting faces. Replacing the visible cap by its cone therefore givesInduction from the initial tetrahedron yields the convex hull of all input points.

With $i$ processed points, a triangulated three-dimensional convex hull has $O(i)$ faces and edges. For a sphere-like triangular boundary, the Euler characteristic and $3F=2E$ give $F=2V-4$ and $E=3V-6$, with $V\le i$. The complete face scan, horizon construction and adjacency update in the implementation of part (e) therefore cost $O(i)$ per insertion. Consequently,The quadratic worst case really occurs for this implementation. Choose all input points in strictly convex position, for example distinct points $(t,t^2,t^3)$ on the three-dimensional moment curve. Each processed point remains a hull vertex of a polyhedron, so the hull has $2i-4$ triangular faces after $i$ insertions. Scanning every face at every next insertion takes $\Theta (n^2)$ sign tests. This argument does not require every insertion to delete most faces: the repeated global scans already force the bound. More elaborate convex hull algorithms with different search machinery are not the implementation being analysed here.

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