Past exam of the computer science course of the University of Oxford / 2015 / Computer graphics / 3

At a surface point $p$, let $\hat{N}$ be the outward unit normal vector, $\hat{V}$ the unit vector from $p$ toward the viewer, and $\hat{L}$ the unit vector from $p$ toward the light. The incoming propagation direction is therefore $-\hat{L}$. The specular reflection direction $\hat{R}$ points away from the surface along the ideal reflected ray.

Resolve $\hat{L}$ into its normal and tangential components:Reflection of the incoming direction preserves its tangential component and reverses its normal component. Equivalently, the outgoing direction has the same normal component as $\hat{L}$ and the opposite tangential component, givingThe dot product identity shows $\Vert \hat{R}\Vert =1$ when $\Vert \hat{L}\Vert =\Vert \hat{N}\Vert =1$.

In the Phong reflection model, ambient lighting approximates unmodelled indirect illumination and is independent of these directions. The diffuse term models Lambertian reflectance and varies as $\max (0,\hat{N}\cdot \hat{L})$. The specular term models a highlight around $\hat{R}$ and varies as $\max (0,\hat{R}\cdot \hat{V}{)}^n$, where $n>0$ controls its sharpness. For a visible front surface, a convenient per-colour-channel equation iswhere $I_a$ is ambient illumination, $I_L$ is the source strength at the surface including any chosen attenuation, $k_a,k_d,k_s\ge 0$ are material weights, and $\chi$ is one when $\hat{N}\cdot \hat{L}>0$ and zero otherwise. The weights can be colour-dependent. An idealized point source's incident strength decreases as inverse distance squared; the empirical equation can also use a prescribed attenuation law.

In degenerate geometric cases the effective weights switch off. A light behind or tangent to the surface contributes neither direct diffuse nor specular illumination. If $\hat{R}\cdot \hat{V}\le 0$, the specular term is zero. A viewpoint on the back side is rejected by back-face culling for a one-sided surface. A material with no highlight has $k_s=0$; with no diffuse response, $k_d=0$; without ambient illumination the ambient term vanishes. These zeros do not require renormalizing the other weights, and the empirical Phong reflection model does not impose a universal condition $k_a+k_d+k_s=1$. At coincident light/surface or eye/surface positions a direction cannot be normalized; such singular configurations require a separate convention, rather than substituting an undefined unit vector into the formula.

A bidirectional reflectance distribution function, or BRDF, describes how a surface scatters incident illumination into each outgoing direction. At a fixed surface point $p$ and wavelength, its inputs are two directions above the surface, ${\omega }_i$ toward the incident source and ${\omega }_o$ toward the observer; equivalently these are two pairs of angular coordinates. Its output is the ratio of differential reflected radiance to differential incident irradiance:Position and wavelength may be additional arguments when material properties vary. A colour implementation can return one value per colour channel. The BRDF is a material response, not the final outgoing light value: it must be combined with the incident illumination and the projected-angle factor.^[ref]

For incident radiance $L_i$, the reflection part of the rendering equation isEmission is added separately if the surface itself emits. This integral explains how a BRDF replaces the assumed material response of a local lighting model. For Lambertian reflectance, $f_r={\rho }_d/\pi$, so the cosine factor yields the diffuse term from part (a). A directional specular lobe supplies a highlight. The empirical Phong reflection model is an approximate angular-response model of this kind; its original direct specular term is not automatically a normalized, energy-conserving BRDF. The ambient term approximates missing illumination and is not itself a third direction-independent material scattering mechanism. More general BRDFs can reproduce measured surface behaviour, while illumination from other surfaces supplies indirect light in the rendering equation.

Let the oriented vertices be $a,b,c$, in an order such that $n=(b-a)\times (c-a)$ points out of the front face. The given nondegeneracy guarantees $n\ne 0$. A ray with nonzero direction $r$ approaches the front face only ifReject $n\cdot r\ge 0$. This combines back-face culling with rejection of parallel rays, including the coplanar case for this ordinary surface-hit test. The ray-plane intersection parameter isReject $\lambda <0$; for rays launched from existing surfaces use a positive lower cutoff to avoid counting the launch surface. Form $p=o+\lambda r$.

Finally determine whether $p$ lies inside the triangle. For $u=b-a$, $v=c-a$, $w=p-a$, computeThese solve $p=a+\beta u+\gamma v$. The barycentric coordinates are $(1-\beta -\gamma ,\beta ,\gamma )$, so the complete acceptance criterion isThe inequalities include the edges and vertices. A renderer sharing edges between triangles should use a consistent numerical edge convention; small floating-point arithmetic errors near a shared boundary should not create cracks. Normalizing $n$ is unnecessary for this intersection calculation because its scale cancels.

For single-shot ray tracing, construct one primary ray per pixel, normally through its centre on the image plane, with the camera centre as origin for perspective projection. Transform the ray into the scene's coordinates, or consistently transform all the scene geometry into camera coordinates.

Intersect that primary ray with the scene's triangles, using part (c), and retain the accepted hit with the smallest nonnegative parameter $\lambda$. This nearest-hit selection supplies visibility: farther surfaces cannot show through the first opaque surface. If there is no hit, write the background colour. At a hit $p$, obtain its material colour and front unit normal vector and set $\hat{V}$ toward the camera.

For each point light at ${\ell }_j$, form ${\hat{L}}_j=({\ell }_j-p)/\Vert {\ell }_j-p\Vert$, calculate the specular reflection direction, and evaluate its diffuse and specular contributions using the Phong reflection model. Sum the contributions and add ambient illumination once:The coloured surface can supply colour-dependent diffuse weights, and each source can have its own colour. Convert the result into the output image's colour encoding and range. Single-shot here means direct local shading after one primary visibility ray; no reflected or transmitted secondary viewing rays are followed. Part (e) adds secondary visibility queries for the lights.

At each primary hit $p$, send a shadow ray toward each point light. An especially clear parameterization isIf an opaque scene surface intersects this open segment, the source is hidden. The finite interval is essential: an object beyond the light must not cast a shadow at $p$. Exclude the launch surface with a small geometrically appropriate origin offset or positive minimum parameter, so floating-point arithmetic does not create a false self-intersection.

Introduce a visibility factor $V_j(p)$ equal to zero when blocked and one otherwise. The modified equation isA blocked light loses both its diffuse and specular contributions. The simple ambient approximation remains. Opaque point lights produce hard shadow boundaries. Use a consistent sidedness policy for occluders: an opaque closed solid blocks from either crossing side, so a two-sided blocker test is appropriate even when primary visibility uses back-face culling. An any-hit query can stop as soon as it finds one blocker before the light.

A bounding volume hierarchy is a tree whose leaves contain geometric primitives, here triangles, and whose internal nodes store cheap-to-test bounding volumes containing all descendant geometry. A bounding volume may be an axis-aligned bounding box or a sphere. The key containment guarantee isTraverse from the root. Reject a whole subtree when its bounding volume is missed; otherwise visit its children and perform the full ray-triangle intersection test only at surviving leaves. Hitting a bounding volume is only permission to investigate, not evidence of hitting an enclosed triangle.

For nearest-hit queries, visit the nearer child first and keep the current nearest parameter. A second child whose volume begins farther away than this parameter can be pruned. For a shadow ray, restrict the traversal to the segment before the source and terminate at any blocker.

A flat list of $N$ triangles needs up to $N$ detailed tests per primary ray or shadow ray. A well-built bounding volume hierarchy can reject large groups with a few cheap tests and substantially reduce the average work. A balanced, well-separated scene often gives traversal resembling a short root-to-leaf search, but balance alone does not guarantee logarithmic query time: extensive overlap or an unfortunate ray can force examination of most or all leaves. Its advantage is spatial rejection, not a universal worst-case bound.

Path tracing estimates the rendering equation by a Monte Carlo method. Launch camera rays; at each surface hit sample an outgoing continuation direction according to a chosen probability density function, trace to the next hit, and continue through successive reflections. Accumulate emitted light or environment light with the product of scattering, cosine and inverse-density factors along the path. A bounce sampled with density $p(\omega )$ updates the path weight byAverage many independently sampled paths per pixel. Multiple bounces account for indirect illumination, including colour bleeding between surfaces, instead of approximating all of it by one ambient constant. Termination can use Russian roulette: continue with probability $q>0$ and divide surviving weights by $q$, preserving the expected contribution. A fixed bounce cutoff is simpler but truncates transport.

The elementary strategy that obtains illumination only when a randomly continued path hits an emitter fails for ideal point lights. From a surface point, an ideal point source occupies zero solid angle; sampling a direction from an ordinary continuous probability density function hits that one direction with probability zero. Thus this strategy almost surely never discovers the light, regardless of the number of samples. An area emitter occupies nonzero solid angle and can be hit.

The qualification matters: practical path tracing can use point lights by explicitly sampling a source and connecting the current surface to it with a shadow ray, a technique called next-event estimation. For a point source the connection direction is known exactly, rather than discovered by a random hemisphere hit. Thus the restriction applies to naive emitter-hit path tracing, not to all path tracing algorithms.^[ref]