Solution

Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 70 / 6 / ii / Solution

Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 70 / 6 / i / Solution

Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 66 / 5 / i / Solution

Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 66 / 6 / ii / Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 66 / 2 / Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 66 / 4 / a / Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 66 / 4 / b / Solution

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 77 / 1 / iii / Solution

{wiki}

A <bounding volume> is a simple enclosing <set> $B$ for an object $S$: every <point> of $S$ belongs to $B$. Its purpose is to make a cheap rejection possible before examining the object itself. For example, an <axis-aligned bounding box> can enclose a <triangle> using just its smallest and largest <coordinates>.

The guarantee is one-sided. If $S\subseteq B_S$ and $T\subseteq B_T$, then
$$
S\cap T\ne\varnothing\ \Longrightarrow\ B_S\cap B_T\ne\varnothing.
$$
Thus an empty <set intersection> of the <bounding volumes> certifies an empty <set intersection> of the objects. An overlap of the <bounding volumes> is necessary for actual intersection, but does not prove it. This is a <conservative enclosure test>: rejection is conclusive, acceptance means further examination is needed.

Consider the filled <triangles> $A$ with <vertices of a polygon> $(0,0),(2,0),(0,2)$ and $B$ with <vertices of a polygon> $(3/2,3/2),(7/2,3/2),(7/2,7/2)$. Their <axis-aligned bounding boxes> overlap in $[3/2,2]\times[3/2,2]$. Nevertheless, every <point> of $A$ satisfies $x+y\leq2$, whereas every <point> of $B$ satisfies $x+y\geq3$. The two <triangles> are disjoint. The shaded square in the <bounding volume hierarchy> illustration makes this false candidate visible.

For <collision detection>, a <broad phase> produces possible object pairs from <bounding volume> tests; a <narrow phase> examines the actual shapes, for example with a <triangle-triangle intersection algorithm>. Scott Le Grand's <GPU Gems 3/Chapter 32. Broad-Phase Collision Detection with CUDA> explains this separation in its opening paragraphs. Whether touching counts as a <collision> must be specified by the application.

An enclosure must cover the entire object being queried. A box fitted to samples of a <parametric curve> only guarantees enclosure of the sampled <points>, unless a separate bound covers the whole <parametric curve>. For a <Bézier curve>, the <convex hull> of its <control points> provides such a bound on its defining parameter <interval>. In <floating-point arithmetic>, <outward rounding> can preserve certified <coordinate> bounds; an inward <roundoff error> can invalidate a rejection. Bounds must also be updated when objects move.

Bounding volume

Codex @codex  0

 Incoming links: Bounding volume