Computer graphics (A10403W1)

a

Solution

Three advantages of integer arithmetic for raster graphics are:

Cheap, fast operations. Historically, integer addition, subtraction and shifts needed much less hardware and execution time than floating-point arithmetic, especially on machines without a floating-point unit. An incremental Bresenham's line algorithm needs only a few additions and a decision per pixel.
Exact decisions. Provided integer overflow is excluded, the scaled midpoint line decision is exact. There is no accumulated rounding error that can move a decision across a half-pixel boundary; equality has a reproducible tie rule.
Simple storage and hardware. Integer coordinates already identify pixels. An implementation can keep coordinates and decision variables in ordinary registers and use a small add/compare datapath, avoiding conversion between floating-point numbers and integer screen addresses.

These are historical and structural advantages, not a claim that every modern processor executes every integer operation faster. An integer implementation still needs sufficient width for its intermediate results. The compact answer is

fast elementary operations; exact decisions; simple hardware and storage .

b

Solution

By exchanging axes, reversing endpoint order and reflecting coordinate signs where necessary, reduce a general line segment to the first octant:

Δ x = x_{1} - x_{0} > 0, 0 \leq Δ y = y_{1} - y_{0} \leq Δ x, m = \frac{Δ y}{Δ x} \in [0, 1] .

The vertical case is handled by exchanging axes. In this octant, increasing

x

by one requires increasing

y

by either zero or one. Thus, from the currently plotted pixel

(x, y)

the candidates are

E = (x + 1, y)

and

NE = (x + 1, y + 1)

Use the implicit equation of the line

f (X, Y) = Δ y (X - x_{0}) - Δ x (Y - y_{0}) .

At a fixed

X

f (X, Y) > 0

means that

(X, Y)

lies below the exact line. The midpoint line decision evaluates

M = (x + 1, y + 1/2)

, halfway between the two candidate pixel centres. If

f (M) < 0

, the exact line lies below

M

, so choose

E

; if

f (M) > 0

, choose

NE

. At equality either candidate is equally near, but a fixed tie rule is essential. We choose

NE

on a tie throughout these solutions:

f (x + 1, y + 1/2) < 0 \Rightarrow E; f (x + 1, y + 1/2) \geq 0 \Rightarrow NE .

This chooses the closest vertical-grid pixel centre in each column, with ties rounded upward. Since

0 \leq m \leq 1

, the result has one pixel per column and consecutive pixels share an edge or a corner.

c

Solution

Multiply the midpoint line decision by two to remove the fraction. At the current pixel

(x, y)

, maintain

d = 2 f (x + 1, y + 1/2) = 2Δ y (x + 1 - x_{0}) - 2Δ x (y - y_{0}) - Δ x .

At the initial endpoint this is

d_{0} = 2Δ y - Δ x

. If

E

is chosen, the next decision midpoint is displaced by

(1, 0)

and

d

increases by

2Δ y

. If

NE

is chosen, its displacement is

(1, 1)

and

d

increases by

2 (Δ y - Δ x)

. Both increments are constant, so the per-pixel work uses only integer arithmetic:

d_{0} = 2Δ y - Δ x, incrE = 2Δ y, incrNE = 2 (Δ y - Δ x) .

The completed code, using the tie rule of part (b), is:

void midpointLine(int x0, int y0, int x1, int y1)
{
    int dx, dy, incrE, incrNE, d, x, y;
    x = x0; y = y0;
    dx = x1 - x0;
    dy = y1 - y0;
    incrE = 2 * dy;
    incrNE = 2 * (dy - dx);
    d = 2 * dy - dx;
    drawPoint(x, y);

    while (x < x1) {
        if (d < 0) {
            d += incrE;
        } else {
            d += incrNE;
            y++;
        }
        x++;
        drawPoint(x, y);
    }
    return;
}

Thus guard1 is x < x1, and guard2 is d < 0. Multiplication by two is the only multiplication. Signed decision variables are convenient because

d

and incrNE can be negative; this remains an integer arithmetic algorithm. A strictly unsigned hardware representation would need an equivalent biased or separated-sign encoding. As with the printed int skeleton, assume all intermediate values fit the chosen type; integer overflow would invalidate the mathematical decisions.

To verify the geometry, write

k = x - x_{0}

. The chosen ordinate is

y (x) = y_{0} + ⌊ \frac{2Δ y k + Δ x}{2Δ x} ⌋ .

The midpoint line decision selects exactly this nearest integer, rounding halves upward. Its increment between successive columns is zero or one. At

k = 0

and

k = Δ x

, it gives exactly

y_{0}

and

y_{1}

, respectively, so both endpoints are included and the line segment has precisely

Δ x + 1

distinct pixels.

Figure 1.
Bresenham pixels for a slope of 3/8, with the upper pixel selected at the midpoint tie
. **Details**.

For the illustrated endpoints

(1, 1)

and

(9, 4)

, the ordinates are

1, 1, 2, 2, 3, 3, 3, 4, 4

. In particular the exact ordinate at

x = 5

5/2

, and the chosen pixel is

(5, 3)

d

Solution

The verifier can check the final geometric criterion directly, independently of the incremental decision variable. Set

d x = x_{1} - x_{0}

d y = y_{1} - y_{0}

, and define the scaled vertical residual

e = 2 d y (x - x_{0}) - 2 d x (y - y_{0}) .

The exact line ordinate is

y_{*} = y_{0} + d y (x - x_{0}) / d x

, so

e = 2 d x (y_{*} - y)

. Nearest-integer selection with upward ties is precisely

x_{0} \leq x \leq x_{1}, - d x \leq e < d x .

The strictness matters: at a half-integer ordinate the upper pixel has

e = - d x

and passes, whereas the lower pixel has

e = d x

and fails. Each column has exactly one accepted integer ordinate.

With reject() terminating verification unsuccessfully, suitable outline code is:

void checkPoint(int x, int y)
{
    Wide a = Wide(x) - x0;
    if (a < 0) reject();                    // inequality 1
    Wide b = Wide(x1) - x;
    if (b < 0) reject();                    // inequality 2

    Wide dx = Wide(x1) - x0;
    Wide dy = Wide(y1) - y0;
    Wide e = 2 * dy * a - 2 * dx * (Wide(y) - y0);
    Wide lower = e + dx;
    if (lower < 0) reject();                // inequality 3
    Wide upper = dx - e;
    if (upper <= 0) reject();               // inequality 4

    counter[x]++;
}

Wide denotes a signed integer type large enough for the products and differences, with conversion before subtraction. These are exactly four inequalities against zero, all applied to named integer variables. The arithmetic restriction on the drawing loop in part (c) does not restrict multiplication in this verifier. The screen endpoints are assumed valid, with

0 \leq x_{0} < x_{1} < MAX_SCREEN_WIDTH

and valid endpoint ordinates, so indexing is safe after the first two checks. These endpoint and screen preconditions belong in initialization if they are not guaranteed by the caller.

No separate

y

-range tests are needed: for

x

between the endpoints,

y_{*}

lies in

[y_{0}, y_{1}]

, and its nearest integer lies in the same interval because both bounds are integers. The counters defer detection of omissions and repetitions to part (e). As for every finite counter, use adequate capacity or a sticky failure on overflow; saturating each counter at two also suffices because only zero, one, and “more than one” matter.

e

Solution

After every proposed pixel has passed part (d), insist on exactly one call in every column of the closed endpoint interval:

void final()
{
    for (int x = x0; x <= x1; x++) {
        if (counter[x] != 1) reject();
    }
    accept();
}

Part (d) already rejected every out-of-range column and every incorrect ordinate. A zero counter now detects an omitted column; a counter greater than one detects a repeated call in that column. Because the residual interval in part (d) allows exactly one integer ordinate in each column, accepted calls in a repeated column must address the same pixel. Conversely, a counter of one in every column forces the complete set of nearest pixels, including both endpoints. Consecutive correct columns differ in ordinate by at most one, which proves that there are no gaps in the resulting thin line segment.

The verifier certifies the final plotted set; it need not require calls to arrive in increasing

x

order. Its final condition is simply

counter [x] = 1 for every x = x_{0}, \dots, x_{1} .

2

a

i

Solution

Represent a point by the column of homogeneous coordinates

(X, Y, Z, 1)^{T}

. The actions of the four matrices are:

Matrix	Geometric action and parameters
$G (θ)$	A proper rotation about the $x$ -axis: $(X, Y, Z) \mapsto (X, Y cos θ - Z sin θ, Y sin θ + Z cos θ)$ . The angle $θ$ is in radians, with the usual right-hand sense.
$H (x, y, z)$	A translation by $(x, y, z)$ : $(X, Y, Z) \mapsto (X + x, Y + y, Z + z)$ .
$J (λ)$	Uniform scaling by $λ$ : $(X, Y, Z) \mapsto (λ X, λY, λ Z)$ . Positive $λ$ gives a uniform dilation; $λ = 0$ collapses the object to the origin; negative $λ$ additionally reverses its direction through the origin.
$K (f)$	Perspective projection from the origin onto the plane $Z = f$ , where $f \neq = 0$ is the focal length in the chosen coordinate units.

The last operation produces

(X, Y, Z, Z / f)^{T}

. It requires a perspective divide: divide the first three components by the last. For

Z \neq = 0

K (f) : (X, Y, Z) ⟼ (\frac{f X}{Z}, \frac{f Y}{Z}, f) .

This is why the last component of homogeneous coordinates cannot simply be discarded. Points with

Z = 0

have no finite projected position, and a visible scene normally uses

Z > 0

under this forward-axis convention. The first three transformations leave the last component equal to one and need no nontrivial divide. The displayed

K

retains no depth variation after division; it describes projection onto the image plane, rather than a complete depth-buffer mapping.

ii

Solution

Interpret the given focal point as the centre of perspective projection,

C = (0, 6, - 8)

. First translate it to the origin with

H (0, - 6, 8)

. The direction from

C

to the world origin is then

(0, - 6, 8)

, of length 10. Choose the rotation matrix

G (θ)

so that this direction becomes

(0, 0, 10)

cos θ = \frac{4}{5}, sin θ = - \frac{3}{5}, θ = - arctan \frac{3}{4} .

Indeed, the transformed

y

component is

- 6 (4/5) - 8 (- 3/5) = 0

, and the transformed

z

component is

(- 6) (- 3/5) + 8 (4/5) = 10

. Thus the required mapping, followed by the perspective divide, is

M = K (5) G (- arctan \frac{3}{4}) H (0, - 6, 8) .

For a world point

(x, y, z)

, its camera coordinates and projected device coordinates are

X = x, Y = \frac{4}{5} y + \frac{3}{5} z, Z = 10 - \frac{3}{5} y + \frac{4}{5} z,

(u, v) = (\frac{5 x}{10 - 3 y /5 + 4 z /5}, \frac{4 y + 3 z}{10 - 3 y /5 + 4 z /5}), Z > 0.

(4)

The world origin projects to

(0, 0)

and lies at camera depth 10. A point five units along the unit viewing direction from

C

has camera coordinates

(0, 0, 5)

, so it lies on the central image plane as expected. Here device coordinates are image-plane coordinates centred on the optical axis; an actual pixel viewport would require its own specified scale and offset.

Only rotations about the

x

-axis are available. Consequently the camera's horizontal axis stays parallel to the world

x

-axis; the viewing direction lies in the world

yz

plane. The available orientation has pitch but no independent yaw or roll. Translations move the camera and the projected origin but cannot supply the missing orientation degrees of freedom.

b

i

Solution

In the solid-modelling convention used here, a rigid-body transformation is an orientation-preserving rigid transformation, represented by a proper rotation and a translation. The proposed upper-left block

S

is orthogonal but has

S = 010100001, S^{T} S = I, det S = - 1.

It is a reflection in the plane

x = y

. It preserves distances, but reverses handedness, so it cannot describe continuous motion of a rigid solid through proper rotations and translations. Some mathematical uses of rigid transformation include this orientation-reversing case; the determinant is the distinction relevant to the warning.

In a solid modeller, triangle winding and outward normal vectors must agree. A reflection reverses the winding: for edge vectors

a, b

(S a) \times (S b) = det (S) S (a \times b) = - S (a \times b) .

Simply transforming stored normal vectors by

S

while retaining the original vertex order therefore makes the geometric and stored normals disagree. Back-face culling, inside/outside tests and Phong reflection model calculations can then use the wrong side. Code assuming a positive oriented volume can likewise interpret the reflected solid incorrectly. A modeller can support reflections if it deliberately corrects these orientation conventions.

A suitable alternative rotates by

- π /2

about

z

and then translates upward by height. Writing

h = height

T = 0 - 1 00 10000010 0 h 01, (x, y, z) \mapsto (y, h - x, z) .

Its rotation matrix has determinant

+ 1

. The source bounds

0 \leq x \leq h

0 \leq y \leq w

z = 0

become

0 \leq x^{'} \leq w

0 \leq y^{'} \leq h

z^{'} = 0

, where

w = width

. A horizontal stripe

y = k step

becomes the vertical stripe

x^{'} = k step

, so even the stripe positions from the left edge are preserved. The face's

+ z

normal vector is also preserved.

ii

Solution

The call constructs dimensions

(d, w, h)

along the old

(x, y, z)

axes. To obtain target dimensions

(w, h, d)

and make an old layer

z = k step

become a new layer

y^{'} = k step

, use the cyclic permutation

P = 0010100001000001, (x, y, z) \mapsto (y, z, x) .

The new coordinate ranges are immediately

[0, w]

[0, h]

[0, d]

. Its spatial block is orthogonal with determinant

+ 1

, since a three-cycle is an even permutation. Hence this is a proper rotation, through

- 2 π /3

about the axis in direction

(1, 1, 1)

under the right-hand convention. No translation is required.

iii

Solution

The multiplication order needs care. Use the standard right-hand rotation matrices, consistent with the printed

G

and the stated positive

z

rotation. For column vectors, direct multiplication of the two products in the order printed gives

R_{y} (- π /2) R_{z} (- π /2) = 0 - 1 0 001 - 1 00, (x, y, z) \mapsto (- z, - x, y),

R_{y} (π /2) R_{z} (π /2) = 010001100, (x, y, z) \mapsto (z, x, y) .

Both permute the dimensions

(d, w, h)

into

(h, d, w)

, rather than the required

(w, h, d)

. Therefore, with ordinary column-vector matrix multiplication, neither printed product is the permutation in part (ii). A translation can correct the position of a cuboid, but cannot correct these permuted side lengths for general

w, h, d

. This order mismatch is present in the original printed question.^[ref]

The apparent intended comparison is obtained if “chain” means apply the

y

rotation first, then the

z

rotation. Under that interpretation the actual column-vector products have the reverse order:

R_{z} (- π /2) R_{y} (- π /2) = 001100010 = P_{3 \times 3} .

Thus the negative-angle sequence is correct when read as operations performed from left to right. The positive-angle sequence gives

R_{z} (π /2) R_{y} (π /2) = 00 - 1 - 1 00 010, (x, y, z) \mapsto (- y, z, - x) .

(4)

It occupies

[- w, 0] \times [0, h] \times [- d, 0]

. Apply the world-space translation

t = (w, 0, d), (x^{'}, y^{'}, z^{'}) = (w - y, z, d - x) .

(5)

This puts the cuboid in

[0, w] \times [0, h] \times [0, d]

and still maps

z = k step

y^{'} = k step

. The distinction is purely the action order: ordinary products act rightmost first, while a library may describe an ordered sequence of operations in application order. Giving the coordinate maps makes either convention explicit. If one merely wanted to place the literal printed negative product in the positive octant, its translation would instead be

(h, d, 0)

, producing dimensions

(h, d, w)

and still failing the requested general bounds.

3

a

Solution

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:

\hat{L} = (\hat{N} \cdot \hat{L}) \hat{N} + (\hat{L} - (\hat{N} \cdot \hat{L}) \hat{N}) .

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, giving

\hat{R} = 2 (\hat{N} \cdot \hat{L}) \hat{N} - \hat{L} .

The dot product identity shows

∥ \hat{R} ∥ = 1

when

∥ \hat{L} ∥ = ∥ \hat{N} ∥ = 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 is

I = k_{a} I_{a} + I_{L} [k_{d} max (0, \hat{N} \cdot \hat{L}) + k_{s} χ max (0, \hat{R} \cdot \hat{V})^{n}],

where

I_{a}

is ambient illumination,

I_{L}

is the source strength at the surface including any chosen attenuation,

k_{a}, k_{d}, k_{s} \geq 0

are material weights, and

χ

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} \leq 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.

b

Solution

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,

ω_{i}

toward the incident source and

ω_{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:

f_{r} (p, ω_{i}, ω_{o}) = \frac{d L _{o} ( p , ω _{o} )}{d E _{i} ( p , ω _{i} )}, [f_{r}] = sr^{- 1} .

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 is

L_{o} (p, ω_{o}) = \int_{Ω^{+}} f_{r} (p, ω_{i}, ω_{o}) L_{i} (p, ω_{i}) (\hat{N} \cdot ω_{i}) d ω_{i} .

Emission 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} = ρ_{d} / π

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

c

Solution

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 \neq = 0

. A ray with nonzero direction

r

approaches the front face only if

n \cdot r < 0.

Reject

n \cdot r \geq 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 is

λ = \frac{n \cdot ( a - o )}{n \cdot r} .

Reject

λ < 0

; for rays launched from existing surfaces use a positive lower cutoff to avoid counting the launch surface. Form

p = o + λ r

Finally determine whether

p

lies inside the triangle. For

u = b - a

v = c - a

w = p - a

, compute

D = (u \cdot u) (v \cdot v) - (u \cdot v)^{2} > 0,

β = \frac{( v \cdot v ) ( w \cdot u ) - ( u \cdot v ) ( w \cdot v )}{D}, γ = \frac{( u \cdot u ) ( w \cdot v ) - ( u \cdot v ) ( w \cdot u )}{D} .

(4)

These solve

p = a + β u + γ v

. The barycentric coordinates are

(1 - β - γ, β, γ)

, so the complete acceptance criterion is

n \cdot r < 0, λ \geq 0, β \geq 0, γ \geq 0, β + γ \leq 1; p = o + λ r .

(5)

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

d

Solution

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

λ

. 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

ℓ_{j}

, form

\hat{L}_{j} = (ℓ_{j} - p) /∥ ℓ_{j} - p ∥

, 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:

I (p) = k_{a} I_{a} + j \sum I_{j} (p) [k_{d} max (0, \hat{N} \cdot \hat{L}_{j}) + k_{s} χ_{j} max (0, \hat{R}_{j} \cdot \hat{V})^{n}] .

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.

e

Solution

At each primary hit

p

, send a shadow ray toward each point light. An especially clear parameterization is

s_{j} (t) = p + t (ℓ_{j} - p), 0 < t < 1.

If 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 is

I (p) = k_{a} I_{a} + j \sum V_{j} (p) I_{j} (p) [k_{d} max (0, \hat{N} \cdot \hat{L}_{j}) + k_{s} χ_{j} max (0, \hat{R}_{j} \cdot \hat{V})^{n}] .

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

f

Solution

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 is

ray misses a node’s bounding volume \Rightarrow ray misses every triangle below that node .

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

g

Solution

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 (ω)

updates the path weight by

β \leftarrow β \frac{f _{r} ( ω , ω _{o} ) ∣ N ^ \cdot ω ∣}{p ( ω )} .