Past exam of the computer science course of the University of Oxford / 2015 / Geometric modelling (A12074W1)

Solutions to all three questions of the paper dated 10 June 2015. The constructive solid geometry calculations use closed half-spaces with nonpositive defining functions inside; the B-spline calculations use unit-spaced simple spline knots and explicitly oriented parameters.^[ref]

Set $\Delta x=x_B-x_A$ and $\Delta y=y_B-y_A$. A displacement from $A$ lies along the straight line precisely when its two-dimensional determinant with $(\Delta x,\Delta y)$ vanishes. Thus an implicit equation isEquivalently, write $ax+by+c=0$, with $a=\Delta y$, $b=-\Delta x$ and $c=\Delta x{y}_A-\Delta y{x}_A$. The vector $(a,b)$ is a normal vector. The formula handles vertical and horizontal straight lines without division. It presupposes $A\ne B$: coincident points do not determine a unique straight line.

Solving the implicit equation for $y$ when $\Delta x\ne 0$ givesHere “gradient” means the slope $dy/dx$, rather than the gradient $(a,b)$ of an implicit defining function. If $\Delta x=0$ and $A\ne B$, the straight line is vertical and has no finite slope. If $\Delta y=0$ and $\Delta x\ne 0$, its slope is zero.

For $ax+by+c=0$, substitute $y=0$ or $x=0$, respectively:In terms of the original coordinates, these arewith each expression used only when its denominator is nonzero. If $a=0$, the straight line is horizontal: it misses the horizontal axis unless $c=0$, in which case it is that entire axis. If $b=0$, it is vertical: it misses the vertical axis unless $c=0$, in which case it is that entire axis. A straight line through the origin has both finite intercepts equal to the origin whenever neither axis is coincident with it.

Put $a_0=2-\sqrt{3}$ and define six closed half-spaces $H_i=\{(x,y):f_i(x,y)\le 0\}$. Their implicit equations and outward normal vectors are:

The six vertices of a polygon traverse the boundary counterclockwise. Each displayed normal vector therefore points to the right of the corresponding directed boundary line segment; it need not be a unit vector. The zero level sets are full straight lines, while the actual boundary retains only the appropriate line segments.

The inward corner at $C$ prevents using the set intersection of all six half-spaces: that would incorrectly discard the upper-left part of the seat. Instead takeThe last factor permits either $y\le 1$ or $x\le 1$, removing only the upper-right region. Another way to understand the same constructive solid geometry model is as the set union of two convex polygons, obtained by distributing the last set intersection over this set union. Its constructive solid geometry tree has an intersection at the root and a union child for $H_2,H_3$.

The tight axis-aligned bounding box is $Q=[0,2]\times [0,2]$. Bisect vertically at $x=1$, giving a right child $R=[1,2]\times [0,2]$. For a scalar implicit function representing the same constructive solid geometry solid, useWith the convention $f_i\le 0$ inside, set intersection corresponds to the maximum, and set union to the minimum. These operations encode membership; $\Phi$ is not a signed distance function.

Since every $f_i$ is an affine function, its extreme values on $R$ occur at corners. Exact real-arithmetic interval arithmetic gives:

Each leaf range is exact, but combining independent intervals forgets that the expressions share $x,y$. The final enclosure need not be the exact range of $\Phi$. For example, equality $\Phi =-1$ would require both $f_6\le -1$, hence $y\ge 1$, and $\min (f_2,f_3)\le -1$, hence $y\le 0$ on $R$, which is impossible. The enclosure is still sufficient for a reliable three-way decision:Here the result is unresolved. This is a real mixed box, rather than only a pessimistic test: $(5/4,3/4)$ is strictly inside, whereas $(3/2,3/2)$ is outside. A zero endpoint alone can also mean contact with the boundary, so equality must not be treated as proof of strict interior or strict exterior. In floating-point arithmetic, certified bounds require outward rounding.

Continue splitting unresolved boxes, normally alternating axes or splitting the longest side. Propagate the interval arithmetic results through the constructive solid geometry tree, discard exterior boxes and stop refining strict interior boxes. In sufficiently small boundary boxes, locate crossings of the active implicit equations with box edges and connect them into boundary line segments. Retain corners and resolve ambiguous multiple crossings by further refinement; here every genuine boundary piece is straight, so its supporting implicit equation allows exact intersection rather than a curved approximation. A maximum boundary-box diagonal $\epsilon$ gives spatial localization at that scale, provided no boundary components are discarded; corner-sign sampling alone provides no such guarantee.

The tight box saves empty-space work, but it is awkward for extracting facets. Entire boundary line segments, notably $EO$, $OA$ and $DE$, lie on the initial box boundary, and $CD$ lies on the first splitting straight line. A sign-change-only method may have no exterior sample on the other side and lose such pieces; exact zeros also persist through refinement. A slightly padded initial axis-aligned bounding box, together with an explicit rule for boundary-coincident pieces, makes the faceting more robust. The tight box is therefore economical for enclosure but not the best unqualified choice for a simple faceting implementation.

Choose a circular fillet that removes the sharp convex tip at $B$. The unit directions from $B$ toward $A$ and $C$ are $(-\sqrt{3}/2,-1/2)$ and $(-1,0)$. Therefore the prescribed tangent points areThe circle centre $K$ lies on the normal line to $BC$ through $N$, so $K=(3/2,k)$. Its radius to $M$ must be perpendicular to $AB$, whose direction vector is $(\sqrt{3},1)$. ThusConsequentlyIndeed $|M-K|=|N-K|=r$. The interior angle $ABC$ is $30^{\circ }$, and the same radius follows from $r=\frac{1}{2}\tan 15^{\circ }$. The selected circular arc runs from $M$ to $N$ through angles $-60^{\circ }\le \theta \le 90^{\circ }$ around $K$:The $150^{\circ }$ circular arc facing $B$ is the rounding; the complementary arc is not part of the boundary.

Define the disk and a half-plane through the chord $MN$ byBoth $M,N$ satisfy $g=0$, and $g(B)=1/2>0$. The clipping half-space $H_g$ retains the part away from $B$, while the disk restores the rounded cap. The required local constructive solid geometry tree isOnly the portion of $P$ on the $B$ side of $MN$ can be removed. To see the locality, $g$ is negative at every original vertex of a polygon except $B$, and vanishes on the two adjacent sides exactly at $M,N$. In the resulting triangle $BMN$, the disk keeps the curved cap next to $MN$ and discards the tip at $B$. A global set intersection with $D_r$ alone would destroy most of the seat. The outward normal vector on the new boundary is $\nabla f_c=2((x,y)-K)$; at $M,N$ it has the same direction as the outward normal vectors of $AB,BC$.

The tangent constraints alone do not insist on a circle; other conic sections can give different bulges. For example, a positive-weight rational quadratic Bézier curve with handles $M,B,N$ has the required tangent directions:Varying $w$ changes the bulge while fixing the tangent points; the circular choice has $w=\cos 75^{\circ }$. Once a circular fillet and these two tangent points are chosen, its centre and radius have no remaining freedom. The half-plane sign and arc selection are also essential: reversing them chooses a different retained region. This construction gives matching tangent directions, or first-order geometric continuity, at $M,N$; the curvature jumps from zero on each straight side to $1/r$ on the circle.

Insert the union subtree from part (f) as another child of the original intersection:Thus the constructive solid geometry tree has one intersection root, four original half-space leaves and two union children. The first union handles the inward corner at $C$; the second embeds the circular fillet at $B$. The line segments $AB$ and $BC$ now end at $M$ and start at $N$, with the chosen circular arc between them. All other boundary line segments are retained.

For a fixed $t\in [0,1]$, De Casteljau's algorithm first takes the same fractional position along both adjacent sides of the control polygon:It then applies another linear interpolation with that same $t$:This is the degree-two Bernstein basis representation of a quadratic Bézier curve. Its coordinate polynomials areThe degree is exactly two, since its second derivative $(-4,-4)$ is nonzero. As a check on the construction, at $t=1/2$ the two intermediate points are $(-1,1/2)$ and $(0,1/2)$ and their midpoint is $F(1/2)=(-1/2,1/2)$.

Three useful geometric properties, with their concrete consequences here, are:

These give the compact answerThe same sum-to-one calculation also explains affine equivariance of a geometric basis: applying an affine map to the handles applies that map to the curve.

Use a row of descending monomials $T(t)=[t^{2}t1]$ and a matrix with one control point per row. Expanding $(1-t{)}^2,2t(1-t),t^2$ gives their coefficients in the three columns of the basis matrix:The matrix multiplication isIn particular, $T(t)M_B=[(1-t{)}^{2}2t(1-t)t^2]$, so multiplying the geometric matrix takes exactly the weighted control point sum in part (a). The two output entries are $F_x(t),F_y(t)$. The basis matrix depends only on the degree and ordering convention; $G_B$ holds the particular geometry.

Choose a quadratic uniform B-spline segment on a unit spline knot interval. This choice is useful because adjacent pieces can later share de Boor points at simple, equally spaced spline knots. Its three active basis pieces on local $t\in [0,1]$ areThey follow from the Cox-de Boor recurrence for degree two and consecutive integer spline knots. If the three de Boor points are $D_0,D_1,D_2$, then the equivalent Bézier curve handles areOne can verify this conversion simply by substituting these expressions into the Bernstein basis formula and collecting each $D_i$. Solving givesThe desired matrix representation is thereforeThe left row is again the monomial row, the middle matrix contains the monomial coefficients of $b_0,b_1,b_2$, and the right matrix lists the de Boor points. Unlike the Bézier curve basis matrix, the constant row averages two handles. A clamped B-spline with repeated end spline knots could instead reuse $A,B,C$ directly; the simple uniform convention above specifies which representation is being used and supplies the shared handles required for the extension.

Rotating the geometry through $180^{\circ }$ sends every point $p$ to $-p$. To start the extension at the origin, also reverse the parameter:Then $E(0)=(0,0)=F(1)$ and $E(1)=(2,0)$. Merely using $-F(t)$ would trace the same rotated image toward the origin, instead of away from the join.

The reversed and rotated de Boor points are $-D_2,-D_1,-D_0$, namely $(0,1),(0,-1),(4,1)$. The first two are already $D_1,D_2$, so there is only one new de Boor point, $\boxed{D_3=(4,1)}$. Using the same uniform basis matrix,Equivalently, the Bézier curve handles are $C=(0,0)$, $-B=(0,-1)$ and $-A=(2,0)$, which gives the same polynomials immediately.

Assign one unit parameter interval to each piece. ThenThere is no ambiguity at $u=1$, since both pieces give the origin. For a single B-spline representation take degree two, the four de Boor pointsand the equally spaced spline knot vector $\tau =(-2,-1,0,1,2,3,4)$. With $N_{i,2}$ denoting the normalized degree-two B-spline on this vector, the complete valid parameter interval is $[{\tau }_2,{\tau }_4]=[0,2]$ andOn $[0,1]$ the active handles are $D_0,D_1,D_2$, and on $[1,2]$ they are $D_1,D_2,D_3$. Shared handles and a simple interior spline knot are what merge the two pieces into one uniform B-spline. The exterior spline knots support the basis; they do not extend the interval being drawn.

In particular, the requested horizontal pieces and their vertical counterparts are

The join has matching positions and first derivatives:Because both pieces have unit parameter intervals, these are also the one-sided derivatives of $S$ at $u=1$. Thus $S$ has first-order parametric continuity, and hence first-order geometric continuity, with no corner or cusp. Its nonzero tangent vector points vertically downward.

The second derivatives do not agree:So this is $C^1$ but not $C^2$ parametric continuity. The signed planar curvature $\kappa =(x^{\prime }{y}^{\prime \prime }-y^{\prime }{x}^{\prime \prime })/(x^{\prime 2}+y^{\prime 2}{)}^{3/2}$ has one-sided valuesThe unsigned curvatures agree, but the bending switches sides; there is no second-order geometric continuity through a regular orientation-preserving reparametrization. The join is a reversal of bending with a curvature jump, rather than a smooth zero-curvature inflection.

For the “gradient” compute $dy/dx=y^{\prime }/x^{\prime }$ away from the join:HenceThe zero horizontal derivative is not a stationary point of the parametric curve, since its vertical derivative is $-2$. It means that the locally regular curve has a vertical tangent line and cannot have a finite graph derivative as $y(x)$ there.

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