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

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.