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

Count scalar additions, subtractions, multiplications and divisions for the specific triangle-triangle intersection algorithm above; comparisons and index selection are separate. Computing one plane normal vector uses two vector differences, costing six subtractions, and one cross product, costing six multiplications and three subtractions. The three vertex-to-plane evaluations use nine further coordinate subtractions and three dot products, each with three multiplications and two additions. The first rejection test therefore costsFor randomly located triangles of characteristic size $a$ in a box of size $H\gg a$, a second triangle straddles the first triangle's plane only when its position is in a slab of relative thickness $O(a/H)$. Consequently the first plane test rejects almost every pair: the expected arithmetic count for this implementation is $39+O(a/H)$, with the constant in the remainder determined by the subsequent branches. This is an average count, rather than the assertion that every input needs 39 operations.

For a generic surviving noncoplanar pair, the symmetric plane test costs another 39 operations, the cross product $N_A\times N_B$ costs nine, and each of the four slice endpoints needs five scalar operations in the selected coordinate: one subtraction and division for the interpolation fraction, then one subtraction, multiplication and addition for the coordinate. Thus this branch usesA fully executed coplanar test can use six planar edge directions. Each needs two subtractions to form its perpendicular and six two-dimensional dot products, costing $2+6(3)=20$ operations. Including both plane tests and the parallelism cross product gives an upper count $78+9+120=207$ before any early exit. Contact and degeneracy can shorten or change these counts. Precomputed normal vectors or a preliminary axis-aligned bounding box test also change the answer: the latter uses only comparisons after its coordinate extrema are available. The relevant small-triangle average is 39 operations for the specified plane-first implementation; a generic complete test uses 107.