CS 488 (Exam Review)

No shader questions, probably no coding questions. Set of Sample Exam Questions, likely that a few appear on the exam. Questions that have not showed up on an exam in a long time are less likely to be asked.

2. History (Nothing).
3. Devices (Nothing).
4. Device Interfaces (Nothing).
5. Geometries (Won’t be tested in depth).
6. Affine Geometries & Transformations.
7. Windows, Viewports, NDC.
8. Line Clipping.
9. Projections.
10. A2 (Nothing).
11. Polygons.
    • At least clipping, scan conversion (concept).
12. Hidden Surface Removal.
    • Backface Culling, Painter’s Algorithm, Warnock, Z-Buffer.
13. Hierarchical Models & Transformations.
14. Rotations About Arbitrary Axis.
    • Focused on Euler vs. Trackball.
15. Picking (Nothing)
16. Colour (Minor things).
17. Lighting.
    • Diffuse, Specular.
18. Shading.
    • Flat, Gouraud, Phong.
19. Graphics Hardware (Nothing).
20. ++ Ray Tracing ++
    • Around 30% of the exam.
    • Shadows, CSG, Texture / Bump Mapping.
21. Aliasing.
22. Bidirectional Tracing (Not tested in depth).
23. Radiosity (Not tested in depth).
24. Photon Mapping (Not tested in depth).
25. Shadows, Projective, Shadow Maps, Volumes (Not tested in depth).
26. Modelling Stuff (Short answers only if anything).
27. Polyhedral Data Structures (Nothing).
28. Splines, De Casteljau’s Algorithm (Lightly tested).
    • Know De Casteljau’s.
29. Non-Photorealistic Rendering (Very lightly tested).
30. Volume Rendering (Nothing).
31. Animation (Might be short questions).
32. Computational Geometry (Nothing).

Geometries

Vector Spaces

Set of vectors V with two operations.

1. Addition: u + v \in V.
2. Scalar Multiplication: \alpha v \in V, where \alpha is a member of some field \mathbb{F}.

Axioms.

• Addition Commutes: u + v = v + u.
• Addition Associates: (u + v) + w = u + (v + w).
• Scalar Multiplication Distributes: \alpha(u + v) = \alpha u + \alpha v.
• Unique Zero Elements: 0 + u = u.
• Field Unit Element: 1 u = u.

Span

Suppose B = \{v_1, v_2, ..., v_n\}. B spans V if and only if any v \in V can be written as v = \sum_{i=1}^n \alpha_i v_i (linear combination of the vectors in B).

• Any minimal spanning set is a basis. All bases are the same size.
• The number of vectors in any basis is the dimension.

Affine Spaces

Now we use a set of points P in addition to the set of vectors V.

• Points can be combined with vectors to make new points. P + v \to Q, with P, Q \in P and v \in V.
• Basis now requires an affine extension. Frame is a vector basis plus a point O (origin), with the same dimension as the basis.

Inner Product Spaces: Binary operator which is commutative, associative, scalar multiplication distributes, u \cdot u \ge 0 if and only if u = 0.

Euclidean Spaces

Metric Space: Space with a distance metric d(P, Q) defined. Requires distance be non-negative, zero if and only if the points are identical, commutative, and satisfy triangle inequality.

Euclidean Space: Metric space based on a dot (inner) product, d^2(P, Q) = (P - Q) \cdot (P - Q).

• Norm: |u| = \sqrt{u \cdot u}.
• Angle: cos(\angle u v) = \frac{u \cdot v}{|u||v|}.
• Perpendicularity: u \cdot v = 0 \Rightarrow u \perp v. Perpendicularity is not an affine concept.

Cartesian Space

An Euclidean Space with a standard orthonormal frame (i, j, k, O).

• Orthogonal: i \cdot j = j \cdot k = k \cdot i = 0.
• Normal: |i| = |j| = |k| = 1.

For notation, we specify the Standard Frame F_s = (i, j, k, O).

Since points and vectors are different objects with different operations and behave differently under transformations how do we handle them?

Coordinates: We use an extra coordinate.

• v = (v_x, v_y, v_z, 0).
• P = (p_x, p_y, p_z, 1).

Why Do We Need Affine Spaces?

• No metric, but we can add a metric to vector space.
• We want to represent objects efficiently, and we want to be able to translate, rotate, scale our objects in their representation. This is difficult to do with vectors.
  • For example, suppose we represent a position by the sum of two vectors. We cannot naively apply a translation to both vectors to translate the position.

Affine Geometries & Transformations

Linear Combinations

• Vector-Vector addition.
• T(u + v) = T(u) + T(v). T(u) = T(u).
• Point-Vector addition.

Affine Combinations

• Point Subtraction: Q - P = v \in V such that Q = P + v, for P, Q \in P. So \sum a_i P_i is a vector if and only if \sum a_i = 0.
• Point Blending: Q = (1 - \alpha)Q_1 + \alpha Q_2 such that Q = Q_1 + \alpha(Q_2 - Q_1) \in P. So \sum a_i P_i is a point if and only if \sum a_i = 1.
  • \frac{|Q - Q_1|}{|Q - Q_2|} = \frac{1 - \alpha}{\alpha}.
• So when combining points, the result is a point if the coefficients sum to 1, and the result is a vector if the coefficients sum to 0.

Affine Transformations

Let T: A_1 \to A_2, where A_1, A_2 are affine spaces.

• T maps vectors to vectors and points to points.
• T is a linear trasformation on the vectors.
• T(P + u) = T(P) + T(u), where P \in P, v \in V.

Then T is an affine transformation. Preserves affine combinations on the points.

Suppose T is only defined on P. Then T(v) = T(Q) - T(R), where v = Q - R.

Mapping Through an Affine Transformation

Let A, B be affine spaces, with T: A \to B be an affine transformation. Let F_A = (v_1, v_2, O_v) be a frame for A, let F_B = (w_1, w_2, O_w) be a frame for B. LetP be a point in A whose coordinates relative to F_A = (p_1, p_2, 1). What are the coordinates (p_1^\prime, p_2^\prime, 1) of T(P) relative to frame F_B?

\begin{aligned} T(P) &= T(p_1 v_1 + p_2 v_2 + O_v) \\ &= p_1T(v_1) + p_2 T(v_2) + T(O_v) \\ \end{aligned}

Geometric Transformations

• Rotation: \begin{bmatrix}\cos(\theta) & -\sin(\theta) & 0 \\ \sin(\theta) & \cos(\theta) & 0\\ 0 & 0 & 1\end{bmatrix}.
• Shear: \begin{bmatrix}1 & \beta & 0 \\ \alpha & 1 & 0\\ 0 & 0 & 1\end{bmatrix}.
• Translation is a shear in the next dimension.

Change of Basis

Suppose we want to change coordinates relative to F_1 to coordinates relative to F_2. We know that P = [x, y, 1]^T relative to F_1 = (w_1, w_2, O_w). Solve F_1 = F_2 M_{1, 2}.

• When F_2 is orthonormal, f_{i,j} = w_j \cdot v_i, f_{i,3} = (O_w - O_v) \cdot v_i.
• Points “mapped” by a change of basis do not change, they are just represented in a different frame.
• To fully specify a transformation, we need a matrix, a domain space, a range space, and a coordinate frame in each space.

World and Viewing Frames

• Standard frame is the world frame.
• Viewer may be anywhere and looking anywhere. Specified as z, y with z as the view direction and z is the up vector.
• We change basis from the world frame to the viewers frame.

After we are in viewing coordinates, we place a clipping box around the scene relative to the viewing frame.

• The screen is 2D, so an orthographic projection is made by removing the z-coordinate.

Transforming Normals

• Consider a non-uniform scale of a circle and the effect on the normal vector. The normal vector will be scaled as well which is incorrect.
• This is because normal vectors are not the difference in points.
  • But tangent vectors are, and normals are vectors perpendicular to all tangents at a point.
  • We can prove we should transform normals by the inverse transpose of the linear part of the transformation (upper 3 x 3 submatrix).
  • This is only an issue if there is a non-uniform scale or a shear transformation.

Windows, Viewports, NDC

• Window: Rectangular area of interest in the scene.
• Viewport: Rectangular region on device.

Window to Viewport mapping is simple a scale based on the ratios and an offset based on their positions.

• When the ratios between the heights and lengths of the two regions are not the same, the image will be distorted.

Normalized Device Coordinates

We want to specify the viewport in a generalized way so that it works on all plaforms / devices. So we use Normalized Device Coordinates as an intermediate coordinate system.

Line Clipping

Clipping is removing points outside a region of interest.

• Point clipping: Points are either entirely inside the region or not.
• Line clipping: Halfspaces can be combined to bound a convex region.
  • Liang-Barsky algorithm efficiently clips line segments to a halfspace.
  • When a line segment is parially inside and partially outside a halfspace, we generate a new line to represent the part inside.

for P, n in edges: # Halfspaces
    wecA = dot(A - P, n)
    wecB = dot(B - P, n)

    if wecA < 0 and wecB < 0:
        reject # Outside
    if wecA >= 0 and wecB >= 0:
        next # Inside

    t = wecA / (wecA - wecB)

    if wecA < 0:
        A = A + t * (B - A)
    else:
        B = A + t * (B - A)

Projections

Perspective Projection

• Identify all points with a line through the eyepoint.
• Take intersection with viewing plane as projection.
• This is not an affine transformation, but a perspective projection.
• Angles and distances are not preserved, but they are not preserved under affine transformations.
• Ratios of distances are not preserved, affine combinations are not preserved.
• Straight lines are mapped to straight lines.
• Cross ratios are preserved. \frac{|AC| / |CD}{|AB| / |BC|}.
• Compared to affine transformations, they require 1 extra point or vector (n + 2) to define a projection map in n dimensional space.

Perspective Map

For projection plane z = d.

• By similar triangles, P = \left(\frac{xd}{z}, \frac{yd}{z}, d\right)
• We need to know what is in front, which is impossible because the map loses z information.
• \begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\begin{bmatrix}x \\y\\z\\1\end{bmatrix} = \begin{bmatrix}x\\y\\z+1\\z\end{bmatrix} maps x, y to \frac{x}{z}, \frac{y}{z}, and maps z to 1 + \frac{1}{z}. So we retain depth information.
• \begin{bmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\\0 & 0 & \frac{f+n}{f-n} & \frac{-2fn}{f-n} \\ 0 & 0 & 1 & 0 \end{bmatrix}\begin{bmatrix}x \\y\\z\\1\end{bmatrix} = \begin{bmatrix}x\\y\\\frac{z(f + n) - 2fn}{f - n}\\z\end{bmatrix} is used for mapping the near and far clipping planes to [-1, 1].
• When fov-y is given, we need to include this in the matrix as \cot(\theta / 2).

3D Clipping

• We should clip the near plane before projection to avoid divide by 0.
• Clipping to other planes could be done before projection but it is easier to clip after projection because we will have a cube instead of the truncated viewing pyramid.

Polygons

Area primitive.

• Simple polygon is planar set of ordered points, no holes, no crossing.
• Convention is to have points ordered in counter-clockwise order, so we have a defined interior and exterior.
• Affine transformations may introduce degeneracies. Orthographic projection may project entire polygon to a line segment.

Polygon Clipping

• Window must be a convex polygon. Polygon to be clipped does not need to be convex.
• Given a polygon represented as v_1,..., v_n, we process all polygon edges in succession against a window edge, w_1, ..., w_n. Repeat for every window edge.

Algorithm: Four cases to consider.

1. Polygon edge is entirely inside the window edge.
2. Polygon edge crosses window edge going out.
   • Intersection point i is the next vertex of the resulting polygon.
3. Polygon edge is entirely outside the window edge.
   • No output.
4. Polygon edge crosses window going in.
   • Intersection point i and p are the next two vertices of the resulting polygon.

Polygon Scan Conversion

• Complicated in general, we look at scan conversion of triangle.
• Split triangle with horizonal line at middle y value, so we have an axis-aligned edge.
• Scan convert the triangle by calculating slopes and iterating over every horizontal line (floating point algorithm).

Hidden Surface Removal

When we have a lot of polygons, we want to draw only those visible to the viewer.

Backface Culling

• Remove all backfacing polygons. Polygons are backfacing if their normal is facing away from the viewer. So cull the polygon if N \cdot V > 0.
• Not a complete solution (used in conjuction with more complete algorithm), but easy to integrate into hardware and usually improves performance by a factor of 2.

Painter’s Algorithm

• Sort polygons on farthest z.
• Resolve ambiguities where z’s overlap.
• Scan convert from largest z to smallest z.
• Some cases are simple but others are not. \Omega(n^2) algorithm.

Warnock’s Algorithm

Divide and conquer algorithm.

• Draw the polygon-list if it is simple in the viewport, otherwise split the viewport vertically and horizontally then recursively draw.
• Simple means there is no more than one polygon in the viewport, or that the viewport is only 1 pixel in size (shade pixel based on closest polygon).
• O(pn), where p, n are the number of pixels and polygons.

Z-Buffer Algorithm

• Perspective transformatoin maps polygons to polygons.
• Scan convert while also stepping in z.
• In addition to framebuffer, have a depth buffer (z buffer) to write z values.
• Update colour in framebuffer if the z value is less than current.
• O(p_c + n), where p_c, n are the number of scan converted pixels and polygons.
• Easy to implement (hardware too), online algorithm.
• Doubles memory requirements (memory is cheap).
• Scale / device dependent.

Hierarchical Models & Transformations

How do we model complex objects and scenes?

• Define basic 3D primitives in some nice way in their own space.
• Use transformations to put primitives together.
• Use hierarchy of spaces to build complex models (DAG).
  • DFS of the DAG, using a matrix stack.
  • Primitives occur at leaf nodes, transformations occur at internal nodes.

Rotations About Arbitrary Axis

Rotation given by a = (x, y, z) and \theta. Map a onto one of the canonical axes, rotate by \theta, then map back.

1. Pick closest axis to a. Assume we chose the x-axis.
2. Project a onto b in the xz plane.
3. Compute \cos(\phi) = \frac{x}{\sqrt{x^2 + z^2}}, \sin(\phi) = \frac{z}{\sqrt{x^2+z^2}}.
4. Create R(-\phi).
5. Rotate a onto the xy plane using R(-\phi). c = R_y(-\theta)a.
6. Compute \cos(\gamma), \sin(\gamma), where \gamma is the angle of c with the x axis.
7. Use \cos(\gamma) and \sin(\gamma) to create R_z(-\gamma).
8. Rotate c onto the x-axis using R_z(-\gamma).
9. Rotate around the x-axis by \theta, R_x(\theta).
10. Reverse z-axis rotation.
11. Reverse y-axis rotation.

So the overall transformation is R(\theta, a) = R_y(\phi)R_z(\gamma)R_x(\theta)R_z(-\gamma)R_y(-\phi).

3D Rotation User Interfaces

• Virtual Sphere: Given two sequential samples of mouse position S, T, map S to point on sphere, map ST to tangential velocity. Use to rotate. When S is outside of the sphere we do z-axis rotation.
• Arcball: Rather than using T as tangent, map T to point on the sphere as well and rotate the ball so that S moves to T.

Colour

• Light sources emit intensity I(\lambda), assigns intensity to each wavelength of light.
• Humans perceive I(\lambda) as colour. Normal human retina has three types of colour receptors which respond most strongly to short, medium, or long wavelengths.

Tri-Stimulus Colour Theory

• Model visual system as linear map, from wavelength to three dimensional vector space.

Colour Systems

• RGB (Red, Green, Blue) Additive.
• CMY (Cyan, Magenta, Yellow) Subtractive. Complement of RGB.
• HSV (Hue, Saturation, Value). Cone shaped colour space.
• CIE XYZ. More complete colour space.
• YIQ. Backwards compatible with black-and-white TV.

Lighting

Given a point on the surface visible through a pixel, what colour should we assign it?

• Want to smoothly shade objects in the scene.
• Shading done quickly (interactive speeds).

Initial Assumptions

• Linearity of reflection.
• Energy conservation.
• Full spectrum of light is representable by three floats (RGB).

Lambertian Reflection

Assume that incoming light is partially absorbed, then the remainder of energy is propogated equally in all directions.

• Approximates matte materials.
• L_{out}(v) = \rho(v, l)E_{in}(l). We assumed that outgoing radiance is equal in all directions so \rho is a constant.
• L_{out}(v) = k_d E_{in}(l) = k_d L_{in}(l) l \cdot n. For the complete environment we take the integral over all possible directions. Taken as the sum over all light sources in practice.

Attenuation

• No attenuation for directional lights, because the energy goes not spread out.
• For point light sources, L_{in}(l) \propto \frac{1}{r^2}, where r is the distance from light to P.
  • Too harsh in practice because real lighting is from area sources, multiply reflections in environment.
  • We use L_{in}(l) = \frac{I}{c_1 + c_2r + c_3r^2}. We do not attenuate light from P to the screen.

Ambient Light

• Lambertian only models direct illumination.
• Ambient illumination is a simple approximation to global illumination.
• Assume everything gets uniform illumination in addition to direct illumination. L_{out}(v) = k_a I_a + \sum_i \rho(v, l_i) I_i \frac{l_i \cdot n}{c_1 + c_2 r_i + c_3 r_i^2}.

Specular Reflection

• Lambertian models matte but not shiny.
• Shiny surfaces have highlights.
• Phong Bui-Tuong developed empirical model. L_{out}(v) = k_a I_a + k_d (l \cdot n) I_d + k_s (r \cdot v)^p I_s. Classic Phong lighting model.
  • Vector r is l reflected by the surface. r = -l + 2(l \cdot n)n.
  • Exponent p controls sharpness of highlight. Small p gives wide highlight, large p gives narrow highlight.
• Blinn introduced variation, Blinn-Phong lighting model. L_{out} k_a I_a + k_d(l \cdot n) I_d + k_s (h \cdot n)^p I_s, with h = \frac{v + l}{|v + l|} measuring deviation from the ideal mirror configuration.

Shading

• We have lighting calculation for a point, so we need surface normals at every point.
• Surface is often polygonal.

Flat Shading

• Shade entire polygon one colour.
• Surface will look faceted. This is acceptable if it really is a polygonal model, not good if it is an approximation of a curved surface.

Gouraud Shading

• Interpolate colours across a polygon from the vertices.
• Lighting calculation only performed at vertices.
• Well-defined for triangles. Extends to convex polygons but better to just convert to triangles.
  • We could slice convex polygon horizontally then interpolate colours along each scanline. This will not produce consistent shading after rotations.
  • Triangluation is expensive and it will be visible to the viewer.

Phong Shading

• Interpolate lighting model parameters instead of colours.
• Normal is specified at every vertex of a polygon, interpolated using the Gouraud technique.
• Simulated with programmable vertex and fragment shaders on modern graphics hardware.

Ray Tracing

• Want more realistic images with shadows and reflections.

for pixel in pixels:
    ray = (eye, pixel - eye)
    Intersect(Scene, ray)

• Setting: eyepoint, virtual screen (array of virtual pixels).
• Ray: Half-line determined by eyepoint and a point associated with a chosen pixel.
• Interpretations: Ray is a path of photons that reach the eye.

Intersection Computations

• Express ray in parametric form E + t(P - E), t > 0.
• Direct Implicit Form: Express object as f(Q) = 0 when Q is a surface point, intersection equation is solving for t such that f(E + t(P - E)) = 0.
• Procedural Implicit Form: f is defined procedurally.

Quadratic Surfaces.

• Ellipsoid: \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1.
• Elliptic Paraboloid: \frac{x^2}{p^2} + \frac{y^2}{q^2} = 1.
• Hyperboloid of One Sheet: \frac{x^2}{a^2} + \frac{y^2}{b^2} - \frac{z^2}{c^2} = 1.
• Elliptic Cone: \frac{x^2}{p^2} + \frac{y^2}{q^2} - \frac{z^2}{r^2} = 0.
• Elliptic Cylinder: \frac{x^2}{p^2} + \frac{y^2}{q^2} = 1.
• Instead of solving generally, we can solve for simpler versions then just scale results (intersections in model space).

Shading

• At closest intersection point, perform Phong shading.
• Before adding contribution from a light, cast a ray to the light. If the ray hits an object before the light, then don’t shade. This gives shadows.

Reflections

• Cast ray in the mirror direction.
• Add colour coming from this ray to the shade of the initial ray.

Recursive Ray Tracing

• Eye-screen ray is the primary ray.
• Generate secondary rays for light sources, reflections, refractions, and recurse.
• Accumulate averaged information for primary ray.

Ray Casting

• Stop before generating secondary rays.

Surface Normals

• Illumination models require surface normal vectors at intersection points.
• Normals to polygons are provided by planar normal or cross product of adjacent edges.
• Normals to any implicit surface use calculus.

Normal Transformations

How do affine transformations affect surface normals?

• Recall from Affine Geometrics & Transformations that normals are transformed by the inverse transpose of the upper 3 x 3 portion of the transformation matrix.

Modeling and CSG

• Hierarchical modeling works for ray tracer too.
• In Constructive Solid Geometry all primitives are solids.
• New type of internal node in DAG, boolean operations (Intersection, Union, Difference).
  • Complete ray intersect object with every primitive, then perform boolean operations on the set of resulting line segments.
  • Segments must be transformed on the way back up the DAG similar to how the ray is transformed.

Texture Mapping

Adding detail by increasing model complexity is costly. When the detail is surface detail, we can use texture mapping.

• Scan a photo of the detail and paste it onto objects.
• Associate texture with polygon.
• Map pixel onto polygon then into texture map.
• Use weighted average of covered texture to compute colour.

Bump Mapping

• Textures will still appear smooth (no shadows).
• We perturb the normal, use for lighting calculation.

Solid Textures

• Hard to texture map onto curved surfaces.
• Use a 3D texture instead. Usually procedural.

Bounding Boxes, Spatial Subdivision

• Ray tracing is slow, often because of ray intersect object.
• Improvements come in two forms; reduce the cost of ray intersect object or intersect the ray with fewer objects.
• Bounding Boxes: Place bounding box around complicated geometry. Only compute ray intersect object if the ray intersects the bounding box. Cheap to compute if the box is axis-aligned.

Spatial Subdivision

• Divide space into subregions.
• When tracing ray, only interesect with objects in sub-regions the ray passes through.
• Useful when there are a lot of small objects in the scene.

Aliasing

• Images sample a continuous function. When the samples are spaced too far apart, don’t get a true representation of the scene.
  • Stairsteps.
  • Moire Patterns.
  • Loss of small objects.

Nyquist Limit

• Sampling rate which is twice the highest frequency.
• Avoids aliasing.
• Doesn’t work for man made objects because they have distinct edges with infinite frequency.

Area Sampling

• Instead of sampling, we could integrate.

Weighted Sampling

• Unweighted is just I = \int_{x \in Box} I_x dI.
• Weighted gives different weights depending on position in the pixel. For example, positions closer to the center of the pixel may be weighted higher than positions near the edge.

Anti-aliasing in Ray Tracing

• Integration not possible, instead we point sample the image.
• Super Sampling: Take more samples and weight with filter. Sampling pattern should not be regular or we will still get aliasing.
• Stochastic Sampling: Jitter samples.

Bidirectional Tracing

Some effects such as caustics require tracing lights from light back to eye.

Radiosity

• Model diffuse interaction of light only in steady state.
• Discretize scene into polygons and assume polygons emit constant light over surface.
• Determine interaction between pairs of polygons.
• Solve a large linear system which is expensive but the result is reusable.

Distribution Ray Tracing

• Ray trace, but at every reflection cast multiple rays based on a distribution function that represents reflection properties.
• Distribution over reflected direction gives soft reflections, over light area gives soft shadows, over aperature gives depth of field, over time gives motion blur.
• Can handle caustics in theory but needs a lot of rays.

Bidirectional Path Tracing

Trace paths from eye and from light and connect them. Trace paths (single reflected ray).

• Reflect with distribution function.
• Lots of rays, low error, high noise.
• Less expensive than distribution ray tracing.

Photon Maps

• Cast rays from lights, create a photon map wherever light hits.
• Use standard ray casting to determine lighting.
  • Density estimation to convert photon map to intensity.
• Fast, easy to program, high noise.

Metropolis Algorithm

• Take one path from light to eye, perturb the path and see if it still reaches the eye.

Radiosity

• Ambient term approximates diffuse interaction of light, want to find a better model.
• Discretize environment and find interactions between pairs of pieces.
• After lighting interactions computed once, multiple views can be rendered easily.
  • No mirror or specular reflectoins.

Radiance: Total energy flux comes from flux at each wavelength L(x, \theta, \phi) = \int_{\lambda_{min}}^{\lambda_{max}} L(x, \theta, \phi, \lambda)d\lambda.

Radiosity: Total power leaving a surface point per unit area \int_0^{\frac{\pi}{2}}\int_0^{2\pi} L(x, \theta, \phi) \cos(\theta) \sin(\theta) d\phi d\theta.

Bidirectional Reflectance Distribution Function

• Surface property at a point, relates energy in to energy out.

Simple Energy Balance (Hemisphere Based)

• General energy balance equation is a long triple integral equation over the hemisphere above the point based on the BRDF, radiance, radiance emitted from surfaces from a given point, and the incident radiance impinging on a given point.
• Series of assumptions are made to get a simpler approximation.
  • All wavelengths act independently.
  • All surfaces are pure Lambertian.

B(x) = E(x) + p_d(x) \int_{\Omega} L^i(x) \cos(\theta^i_x) d \omega

In general we have L^i(x, \theta^i_x, \phi^i_x) = L^o(y, \theta^o_y, \phi^o_u) for some y. In other words, the radiance comes from some incident radiance. So we simplify with \theta^i_x = \theta_{xy}, \theta^o_y = \theta_{yz} and L^i(x) = \frac{B(y)}{\pi}.

• Visibility: We use H(x, y) as an indicator variable with H(x, y) = 1 if y is visible from x.
• Area: Convert d\omega to surface area d\omega = \frac{\cos(\theta_{yx})}{||x - y||^2} dA(y).

B(x) = E(x) + p_d(x) \int_{y \in S} B(y) \frac{\cos(\theta_{xy})\cos(\theta_{yx})}{\pi ||x - y||^2} H(x, y) dA(y)

Piecewise Constant Approximation

• We approximate this integral by breaking into a summation over patches.
• Assume constant radiosity on each patch.

B(x) \approx E(x) + p_d(x) \sum_j B_j \int_{y \in P_j}\frac{\cos(\theta_{xy})\cos(\theta_{yx})}{\pi ||x - y||^2} H(x, y) dA(y)

• Solve with per-patch average density. So p_d(x) \approx p_i for x \in P_i, B_i \approx \frac{1}{A_i} \int_{x \in P_i} B(x)d A(x), E_i \approx \frac{1}{A_i} \int_{x \in P_i} E(x) dA(x).

B_i = E_i + p_i \sum_j B_j \frac{1}{A_i} \int_{x \in P_i} \int_{y \in P_j} \frac{\cos(\theta_{i})\cos(\theta_{j})}{\pi ||x - y||^2} H(i, j) dA_j dA_i

• Form Factor: F_{ij} = \frac{1}{A_i} \int_{x \in P_i} \int_{y \in P_j} \frac{\cos(\theta_{i})\cos(\theta_{j})}{\pi ||x - y||^2} H(i, j) dA_j dA_i. By symmetry, A_i F_{ij} = A_j F_{ji}.

So given all of the form factors, we have linear equations B_i = E_i + p_i \sum_j F_{ij} B_j, B_i = E_i + p_i \sum_j F_{ji} \frac{A_j}{A_i} B_j.

Matrix Form

• Equations are B_i - p_i \sum_{1 \le j \le n} B_j F_{ij} = E_i. B_i's are the only unknowns, solve 3 times to get RGB values of B_i.

Calculating Form Factors

• Differential form factor is ddF_{di,d_j} = \frac{\cos(\theta_i)\cos(\theta_j)}{\pi r^2} H_{i,j} dA_j dA_i.
• Form factor from A_i to A_j is an area average over the integral over A_i. F_{i,j} = \frac{1}{A_i} \int_{A_i} \int_{A_j} \frac{\cos(\theta_i)\cos(\theta_j)}{\pi r^2} H_{i,j} dA_j dA_i.
  • We approximate this integral though ray tracing, hemi-sphere, hemi-cube.
  • Lots of F_{i,j} may be zero, so we have sparse matrix.

Hemi-sphere Form Factors

• Place hemisphere around patch i and project patch j onto it.
• Still non-trivial to project onto hemisphere.

Hemi-cube Form Factors

• Project onto a hemi-cube.
• Subdivide faces into smaller squares.

Delta Form Factors

• Every hemi-cube cell P has pre-computed delta form factor \Delta F_P = \frac{\cos(\theta_i)\cos(\theta_P)}{\pi r^2} \Delta A_P. Approximate d F_{dj, i} by summing delta form factors.

Progressive Refinement

• Continuously choose a patch and shoot its radiosity to all other patches.

def shoot(i):
    For all j, calculate F_ji
    For every j:
        d_rad = pj * dB_i * F_ji * A_i / A_j
        dB_j += d_rad
        Bj += d_rad
    dB_i = 0

while unshot > EPS:
    Choose patch i with highest d_B
    shoot(i)

• Able to stop and look at partial results.

Meshing in Radiosity

Adaptive Subdivision

• Make initial meshing guess.
• Point sample a patch.
• Radiosity has O(n^2) runtime but subdivision increases n.
• We could shoot from big patches and receive at small patches.

Stochastic Methods

• Rather than computing form factor, estimate by sampling.
• Cast N_i rays cosine-distributed from patch i. Let N_{ij} be the number of particles that reach patch j. Then \frac{N_{ij}}{N_i} \approx F_{ij}.
• Let \Delta P_i^{(j)} be unshot radiosity. Select source patch randomly based on unshot radiosity, select patch j by casting stochastic rays.
• Much faster than form factor methods but lots of noise.

Photon Mapping

• Trace rays from lights, bounce off shiny surfaces.
• Store lights hitting diffuse surfaces, use stored light to achieve global illumination effects.

1. Emit photons.
2. Trace photons, store in data structure.
3. Estimate irradiance with k nearest neighbour search.
4. Ray trace, using estimated irradiance.

Shadows, Projective, Shadow Maps, Volumes

• Shadows are important to help viewer locate objects.

Projective Shadows

For drawing shadows on a plane.

• After drawing scene, draw ray from light through corners of polygon and intersect with plane.
• Draw projected polygon as a dark colour with alpha blending.
• Fast and simple but only works for shadows on a plane.

Shadow Maps

• Render scene from light’s view and store the z-map.
• Render from eye’s viewpoint. For a point P that the eye sees, convert to light’s frame and look up distance to light using shadow map. When distance is equal, the object is unblocked, so do lighting calculation. When distance is not equal, it is in shadow.
• No need to rerender shadow maps every frame if light and objects are not moving.
• Works best with directional and spot lights.

Shadow Volumes

• Use stencil buffer to determine where shadows are. Stencil buffer stores per pixel data.
• For every point P on surface, consider shadow planes cast by silhouette edges. Count front facing shadow planes as +1, rear facing plane as -1. Take the sum of shadow planes, if it is positive then the object is in shadow.

1. Draw scene normally.
2. Draw in stencil buffer, front facing shadow polygons using previous depth buffer. Increment stencil buffer on draws.
3. Draw in stencil buffer, backfacing polygons. Decrement stencil buffer on draws.
4. Redraw scene with light off, but only update pixels with exact depth match and non-zero stencil value.

Modelling Stuff

Fractal Mountains

• Start with triangle, refine and adjust vertices. At every step of refinement, adjust height of vertices. Use scaled random numbers to adjust height.

L-system Plants

• Model as CFG.

Buildings

• Model as CFG.

Partical Systems

• Aim for overall effects by having many simple particles.
• At each time step based on state, update attributes of particles, delete old particles, create new particles, display current state of all particles.

Splines, De Casteljau’s Algorithm

• Linear blend: Line segment from an affine combination of the points.
• Quadratic blend: Quadratic segment from an affine combination of line segments.
  • \begin{aligned}P_0^1(t) &= (1 - t)P_0 + tP_1 \\ P_1^1(t) &= (1 - t)P_1 + tP_2 \\ P_0^2(t) &= (1 - t)P_0^1(t) + tP_1^1(t)\end{aligned}
• Cubic blend: Cubic segment from affine combination of quadratic segments.

de Casteljau Algorithm

Geometric view.

• Join P_i by line segments.
• Join the t: (1 - t) points of those line segments by line segments.
• Repeat as necessary.
• t: (1-t) point on the final line segment is a point on the curve, final line segment is tangent to the curve at t.

Expanding Terms (Basic Polynomials)

• P^n_0(t) = \sum_{i=0}^n P_i B^n_i(t), where B^n_i(t) = \frac{n!}{(n-i)!i!}(1 - t)^{n-i}t^i = {n \choose i}(1 - t)^{n-i}t^i.
• Bernstein polynomials of degree n form a basis for the space of all degree-n polynomials.

Bernstein Polynomials

• \sum_{i=0}^n B_i^n(t) = 1
• B_i^n (t) \ge 0, for t \in [0, 1].

Bezier Splines

• Degree n (order n + 1) Bezier curve segment is P(t) = \sum_{i=0}^n P_i B^n_i(t).
• P_i are the k-dimensional control points.
• P(t) is a convex combination of the P_i for t \in [0, 1].
• So P(t) lies within the convex hull of P_i.
• Since the Bezier curve is an affine combination of its control points, any affine transformation of a curve is the curve of the transformed control points.

Interpolation

• B^n_0(0) = 1, B^n_n(1) = 1, so B_i^n(0) = 0 if i \neq 0, B_i^n(1) = 0, if i \neq n.
• P(0) = P_0, P(1) = P_n.

Derivatives

\frac{d}{dt} B_i^n(t) = n(B^{n-1}_{t-1}(t) - B_i^{n-1}(t)), so P^\prime(t) = n(P_1 - P_0), P^\prime(1) = n(P_n - P_{n-1}).

Smoothly Joined Segments (C^1)

• Let P_{n-1}, P_n be the last two control points of one segment. Let Q_0, Q_1 be the nest two control points of the next sequence.
• P_n = Q_0.
• P_n - P_{n-1} = Q_1 - Q_0.

Smoothly Joined Segments (C^1)

• P_n = Q_0.
• P_n - P_{n-1} = \beta(Q_1 - Q_0), for some \beta > 0.

C^2 Continuity

• C^0: P_n = Q_0.
• C^1: P_n - P_{n-1} = Q_1 - Q_0.
• C^2: (P_n - P_{n-1}) - (P_{n-1} - P_{n-2}) = (Q_2 - Q_1) - (Q_1 - Q_0).

Recurrence, Subdivision

• Since B^n_i(t) = (1 - t)B_i^{n-1} + t B_{i-1}^{n-1}(t),

\begin{aligned} P(t) &= P_0^n(t) \\ P_i^k(t) &= (1 - t)P^{k-1}_i(t) + tP_{i+1}^{k-1} \\ P^0_i(t) &= P_i \end{aligned} Use to evaluate point at t, subdivide into two new curves.

Spline Continuity

• Weierstrass Approximation Theorem: We can approximate any C^0 curve to any tolerance with polynomials, but may require a high degree.
• High degree are non-local, expensive to evaluate, and slow to converge.

Piecewise Polynomials

• Instead of one high degree polynomial, piece together lots of low degree polynomials.
• Issue is continuity between pieces.

C^0 Piecewise Cubic Bezier

• Use last control point of one segment to be first control point of the next segment, so the curves will meet at the endpoints.

C^1 Piecewise Cubic Bezier

We also need P_3 - P_2 = Q_1 - Q_0.

• Cubic Hermite Interpolation: Given points P_0, ... P_N and vectors v_0, ..., v_N, we want to find a piecewise C^1 cubic polynomial such that P(i) = P_i, P^\prime(i) = v_i.
  • Create one cubic Bezier segment per interval.

\begin{aligned} P_{i,0} &= P_i \\ P_{i,1} &= P_i + \frac{v_i}{3} \\ P_{i,2} &= P_{i+1} - \frac{v_{i + 1}}{3} \\ P_{i,3} &= P_{i+1} \end{aligned}

• Catmull-Rom Splines: Annoying to give derivatives, we want to just specify points.
  • Make up derivatives, v^i = \frac{P_{i+1} - P_{i-1}}{2}.

C^2 Piecewise Cubic Bezier

• A-frame construction gives C^2 constraints on Bezier segments.
• Hard to place points, so user places four control pounts, program places next tree.

Tensor Product Patches

• Control polgon is polygonal mesh with vertices P_{i,j}.
• Patch blending functions are the products of curve basis functions. P(s, t) = \sum_{i=0}^n\sum_{j=0}^n P_{i,j} B^n_{i,j}(s, t), where B^n_{i,j}(s, t) = B^n_i(s) B^n_j(t).

Smoothly Joined Patches

• Ensure that P_{i,n} - P_{i, n-1} = \beta (Q_{i,1} - Q_{i,0}).

Rendering

• Divide up into polygons by stepping over s, t \in [0, 1] with some small \delta.
• Join up sides and diagonals to produce triangular mesh.
• Alternatively, subdivide and render control polygon.

Tensor Product B-splines

• Could use B-splines instead of Bezier. Automatic continuity between patches.

Problems with tensor product patches arise when data is non-rectangular.

Triangular de Casteljau

• Join adjacently indexed P_{ijk} by triangles. Use barycentric coordinates to generalize the algorithm.
• Patch interpolates corner control points.
• Boundary curves are Bezier curves.
• Patches will be joined smoothly if pairs of boundary triangles are affine images of domain triangles.

Continuity between two patches is easy, hard for n patches. In general, joining things together with tensor product or triangular patches is hard.

Subdivision Surfaces

• Start with a description of polyhedron. Assume triangle or quad meshes.

Topological Subdivision

• Split faces into new faces. For triangular meshes insert new vertices at midpoints and join. For quad meshes insert new vertices at midpoints and join opposite vertices.
• Compute centroid c_f of every face f for quad meshes. For every vertex v of subdivided mesh, v = \frac{\sum_{f \in n(v)} c_f}{|n(v)|}.
• For triangle meshes, do something similar except c_f is a function of the other two vertices.

Implicit Surfaces

• Algebraic surfaces: seen in ray tracing, set of points P such that F(P) = 0.
  • Root finding is easy.
  • Modelling is hard, CSG or hierarchical modeling helps.

Rendering Implicit Surfaces

• Ray tracing.
• Sphere tracing (ray marching).
• Marching cubes. Sample function on uniform grid, make decisions based on adjacent samples.
• A-Patches (Algebraic patches). Use multivariate Bernstein to tessellate algebraics.

Wavelets

1-D Haar

• Given an array, represent in a different form by taking the average of adjacent elements and storing both the average and the difference between the average and the actual values.
  • Expect a lot of adjacent values to be close. Truncating the values to 0 gives a lossy compression technique.

2D Haar and Image Compression

• Apply 1-D Haar to every row, then apply 1-D Haar to every column.

Non-Photorealistic Rendering

Painterly Rendering

• Start with source image, apply model of strokes to approximate it.

Pencil Rendering

• Simulation of pencil lead and paper, derived from close observation.
• Model geometry of pencil tip, pressure on page.

Silhouettes

• For smooth objects, silhouettes are points where the vector from the camera just grazes the point.
• Meshes: Mesh with face normals is not smooth. Approximate silhouettes by finding mesh edges that separate a front and back face.
• Need to decide for every silhouette edge which parts are visible. Implementation with depth buffering and colouring of silhouette edges.

Toon Shading

• Ray tracing: Quantize by diffuse attenuation to two or three colours.
• OpenGL: Use diffuse brightness as parameter to a one-dimensional texture map with two or three colours.

Animation

• Rapid display of slightly different images to create the illusion of motion.
• Conventional approach: Keyframed animation.

Automated Keyframing

• Replace human inbetweener with interpolation algorithms.
• Provides repeatability and automatic managemet of keyframes but not as smart as human inbetweener.

Functional Animation

• Independent scalar function specified for every keyframed parameter.

Linear Interpolation

• Discontinuities in derivative exist at all keyframe points.
• Rate of change within a segment is constant.

Spline Interpolation

• Continuity control can be obtained and fewer keyframes may be required for the same quality.
• Extra information may be required, such as computation of control points and tangent vectors.

Transformation Matrix Animation

• Interpolate a transformed matrix.
• Keyframes are poses of objects given by animator.

Rigid Body Animation

• Lower degrees of freedom compared to general affine transformations (12 \to 6).

Motion Path Animation

• Want to translate a point through space along a given path, controlling velocity and continuity.

Motion Path Spline Interpolation Problems

Spline position interpolation gives continuity control over changes position but.

• Visually notice discontinuities.
• Different segments of the spline with same parametric length can have different physical lengths.
• Parameterizing spline directly with time objects will move at a non-uniform speed.

Arc Length Parameterization

1. Given spline path P(u) = [x(u), y(u), z(u)], compute arclength of spline as a function of u, s = A(u).
2. Find inverse of A(u).
3. Substitute u = A^{-1}(s) into P(u) to find motion path parameterized by arclength.

• Let s = f(t) specify distance along the spline as a function of time t.
• Motion path is given by P(A^{-1}(f(t))).

There is no analytic solution if the motion path is a cubic spline. So exact arc-length parameterization is not reasible.

Approximate Arc Length Parameterization

• Compute points on spline at equally-spaced parameteric values, use linear interpolation.
• Linear interpolation should consider distance between samples.

Orientation and Interpolation

• Interpolate angles rather than transformation matrix.
• Euler Angles: Three angles, x-roll, y-roll, z-roll.
  • Hard to find the angles given the desired orientation. But widely used in practice and easy to implement.
  • Order of axes and orientation of coordiante axes are important.
• Quaternions: Four-dimensional analogy of complex numbers.
  • Inverse problem is easy to solve and the UI tends to be simpler, but it is harder mathematically and computationally.

Quaternions

Four-dimensional analogs of complex numbers. Used to represent orientation. Recall that multiplication of complex numbers represents orientation and rotation in the plane (e^{i\theta}).

• q = a + bi + cj + dk.

\begin{aligned}i^2 = j^2 = k^2 &= -1\\ ij = -ji &= k\\ jk = -kj &= i\\ ki = -ik &= j\end{aligned}

Multiplication does not commpute.

• Broken down into scalar and vector part, q = (s, v) = s + v_1 i + v_2 j + v_3 k.
• Product of two quaternions is q_1q_2 = (s_1s_2 - v_1 \cdot v_2, s_1 v_2 + s_2 v_1 + v_1 \times v_2).
• Conjugate: \overline{q} = (s, -v).
• |(s, v)| = \sqrt{s^2 + |v|^2}.

Unit Quaternions

• Unit normals, isomorphic to orientations.
• q_r = (\cos(\theta), \sin(\theta)v), equiavlent to rotation by an angle of 2\theta around unit v.

Rotations

• Points in space represented by quaternions with zero scalar part.
• q_p = (0, P).
• Rotation of point P by q_r is q_{P^\prime} = q_r q_P q_r^{-1}, where inverse is equal to conjugate for unit quaternions.
• Allows for independent definition of axis of rotate and angle.
• Spherical interpolation of quaternions gives better results than interpolation of Euler angles.

Interpolating Unit Quaternions

• Spherical linear interpolation.
  • Want the angle between quaternions, \omega = \cos^{-1}(q_1 \cdot q_2).
  • q(u) = \frac{1}{\sin(\omega)}\left(q_1 \sin((1 - u)\omega) + q_2 \sin(u \omega)\right), for u \in [0, 1].

Tools for Shape Animation

• Skeleton: Group vertices and manipulate as unit.
• Free-Form Deformations: Changes the space around an object with nonlinear transformation.

Kinematics and Inverse Kinematics

Kinematics: Study of motion independent of the forces that cause the motion.

• Forward kinematics: Positions, velocities, accelerations.
• Inverse kinematics: Derivation of motion of intermediate links in an articulated body given the motion of some key links.

Physically-Based Animation

• Simulate laws of Newtonian physics in contrast to kinematics.
• Control objects by manipulating forces and torque.
• Inverse dynamics is difficult. How do we find forces to move a physical object along a desired path?
• Useful for secondary effects in keyframe animation.

Spring-Mass Models

• Compose of mesh of point masses connected with springs.
• Compute motion according to differential equations.

Morphing

• Linear interpolation between images.
• Nice effects at low cost.
• Hardest part is partitioning images into pieces that correspond.

Motion Capture

• Keyframing complex actions is hard, instead capture motion from real objects.

Flocking

• Animate a group of animals.
• Motion of individuals is semi-independent.
• Collision Avoidance: Avoid hitting objects and one another.
• Flock Centering: Member trying to remain a member of flock. Control flock member with local behaviour rules.
• Perception: Objects aware of itself and a few neighbours. Doesn’t follow a designated leader.