Special Topics in CG: Ray Tracing, Fractals, Animation & Advanced Rendering

1. Ray Tracing: The Physics of Light Simulation

Ray tracing simulates the path of light by tracing rays from the camera backward into a scene, calculating intersections with objects and applying reflection/refraction laws. Unlike rasterization (which paints pixels), it models global illumination by recursively bouncing rays to simulate indirect lighting.

How It Works

1. Primary rays: Shot from the camera through each pixel.
2. Intersection tests: For each ray, check against geometric primitives (spheres, triangles) using:
   • Ray-sphere intersection: Solve quadratic equation for closest hit.
   • Ray-triangle intersection: Use barycentric coordinates or Möller-Trumbore algorithm.
3. Shading: At intersection points, compute:
   • Local illumination: Phong/Blinn-Phong models.
   • Global effects: Reflection (mirrors), refraction (glass), shadows (occlusion tests).
4. Recursion: For reflective/refractive surfaces, spawn secondary rays.

Mathematical Core: Ray-Sphere Intersection

For a ray $\mathbf{R}(t)=\mathbf{O}+t\mathbf{D}$ and sphere centered at $\mathbf{C}$ with radius $r$: $$\Vert \mathbf{R}(t)-\mathbf{C}{\Vert }^2=r^2⟹(\mathbf{O}+t\mathbf{D}-\mathbf{C})\cdot (\mathbf{O}+t\mathbf{D}-\mathbf{C})=r^2$$ Expanding yields a quadratic in $t$: $$t^2(\mathbf{D}\cdot \mathbf{D})+2t(\mathbf{D}\cdot (\mathbf{O}-\mathbf{C}))+(\mathbf{O}-\mathbf{C})\cdot (\mathbf{O}-\mathbf{C})-r^2=0$$ Solve for $t\ge 0$ to find intersection points.

Example: Simple Scene

Setup:

• Camera at $(0,0,5)$, looking at origin.
• Red sphere: center $(0,0,0)$, radius $1$, color $(1,0,0)$.
• White floor: plane $z=-1$.

Trace a ray through pixel $(2,3)$ (normalized device coordinates):

1. Convert to world space: $\mathbf{O}=(0,0,5)$, $\mathbf{D}=(2,3,-5)/\sqrt{4+9+25}$.
2. Intersect with sphere: $$t=\frac{-(5\cdot {\mathbf{D}}_z)\pm \sqrt{(5{\mathbf{D}}_z{)}^2-(\mathbf{O}\cdot \mathbf{O}-r^2)}}{\mathbf{D}\cdot \mathbf{D}}$$ Plugging in values gives $t\approx 4.5$ (hit sphere) and $t\approx 6.2$ (hit floor).
3. Color: At $t=4.5$, normal $\mathbf{N}=\mathbf{R}(t)-\mathbf{C}$. Compute lighting using Phong model.

Advantages/Disadvantages

Optimizations:

• Spatial partitioning: BVH (Bounding Volume Hierarchy) or kd-trees to cull empty space.
• Acceleration: Embree (Intel), OptiX (NVIDIA) use GPU ray tracing.
• Approximations: Path tracing (Monte Carlo) for stochastic sampling.

2. Procedural Generation: Fractals and L-Systems

Procedural content generation (PCG) creates data algorithmically. Fractals and L-systems enable infinite complexity from simple rules.

Fractals: Infinite Detail from Recursion

A fractal is a set of points with self-similarity at all scales, defined by iterative functions. Key types:

• Geometric fractals: Koch snowflake, Sierpiński triangle.
• Random fractals: Perlin noise (used in terrain generation).
• Fractional Brownian motion (fBm): Sum of octaves for natural-looking textures.

Example: Mandelbrot Set Define $z_{n+1}=z_n^2+c$, where $c$ is a complex parameter. The set is all $c$ for which $|z_n|$ remains bounded.

def mandelbrot(c, max_iter):
    z = 0
    for n in range(max_iter):
        if abs(z) > 2: return n
        z = z*z + c
    return max_iter

Visualization:

![Mandelbrot set fractal](/media/96dac60fcbb3c4ffa10a.png "A Julia set variant showing recursive self-similarity. (Image: Aokoroko, CC0, via Wikimedia Commons)")

Applications:

• Terrain generation (e.g., Minecraft biomes).
• Texture synthesis (e.g., clouds, wood grain).
• Antialiasing (fractal noise for smoother edges).

L-Systems: Formal Grammars for Growth

Lindenmayer systems define growth via rewriting rules. Example: Plant growth:

• Alphabet: F (draw forward), + (turn left), - (turn right), [ (push), ] (pop).
• Axiom: F.
• Rules: F → F[+F]F[-F]+F.

Iteration:

1. Start: F
2. After 1 iteration: F[+F]F[-F]+F
3. After 2 iterations: F[+F[+F]F[-F]+F]F[-F[+F]F[-F]+F]+F

Visualization:

graph TD
    A[F] --> B[F[+F]F[-F]+F]
    B --> C[F[+F[+F]F[-F]+F]F[-F[+F]F[-F]+F]+F]
    C --> D[Complex plant structure]
    style A fill:#f9f, B fill:#bbf, C fill:#f99, D fill:#f66

Applications:

• Botanical modeling (e.g., Spore creatures).
• Architectural designs (e.g., Gothic arches).
• Animation rigging (e.g., hair/fur simulation).

3. Animation Techniques: Keyframes and Inverse Kinematics

Animation brings static scenes to life via motion synthesis. Two core methods:

A. Keyframe Animation

Define keyframes (critical poses) and interpolate between them. Steps:

1. Pose keyframes: Animate character at frames 1, 10, 20 (e.g., walk cycle).
2. Interpolation: Use splines (e.g., Bézier, B-splines) to smooth transitions.
   • Linear interpolation: $\mathbf{P}(t)=(1-t){\mathbf{P}}_0+t{\mathbf{P}}_1$.
   • Cubic interpolation: $\mathbf{P}(t)=\mathbf{A}{t}^3+\mathbf{B}{t}^2+\mathbf{C}t+\mathbf{D}$.
3. Hierarchical rigging: Parent-child relationships (e.g., arm → hand → fingers).

Example: 2D Bézier Curve for Arm Motion Given control points ${\mathbf{P}}_0,{\mathbf{P}}_1,{\mathbf{P}}_2,{\mathbf{P}}_3$: $$\mathbf{B}(t)=(1-t{)}^3{\mathbf{P}}_0+3(1-t{)}^{2}t{\mathbf{P}}_1+3(1-t)t^2{\mathbf{P}}_2+t^3{\mathbf{P}}_3$$ Visualization:

flowchart TD
    A["Keyframe 1\n(t=0)"] -->|Bézier Curve| B["Keyframe 2\n(t=1)"]
    A --> C["Control Point 1"]
    A --> D["Control Point 2"]
    B --> E["Control Point 3"]
    B --> F["Control Point 4"]
    style A fill:#f96, B fill:#6f9, C fill:#9f6, D fill:#f96, E fill:#6f9, F fill:#9f6

B. Inverse Kinematics (IK)

Solves for joint angles to achieve a goal position (e.g., hand touching an object). Steps:

1. Define end effector (e.g., hand) and target.
2. Use Fabrik (Forward And Backward Reaching IK) or CCD (Cyclic Coordinate Descent).
3. Iteratively adjust joints to minimize distance to target.

Example: 2-Link Arm IK Given:

• Joint 1 at $(0,0)$, length $L_1$.
• Joint 2 at $(L_1,0)$, length $L_2$.
• End effector target $(x,y)$.

Solution:

1. Compute angle ${\theta }_2$ for the second joint: $${\theta }_2=\text{atan2}(y,x-L_1)$$
2. Compute angle ${\theta }_1$: $${\theta }_1=\text{atan2}(y,x)-\text{atan2}(L_2\sin {\theta }_2,L_1+L_2\cos {\theta }_2)$$

Applications:

• Character animation (e.g., Final Fantasy combat).
• Robotics (e.g., industrial arms).
• Game AI (e.g., NPC interactions).

4. Advanced Illumination: Global Illumination vs. Local Models

Shadow Detection Challenges

1. Hard shadows: Simple ray occlusion (Phong model).
2. Soft shadows: Multiple light samples (e.g., percentage-closer filtering).
3. Global shadows: Require ray recursion (e.g., shadow rays in ray tracing).
4. Complex geometries: Portals or lightmaps for static scenes.

Example: Shadow Mapping

1. Render scene from light’s POV to depth buffer.
2. For each fragment, compare depth to stored shadow map.
3. If $z_{\text{fragment}}>z_{\text{shadow}}$, it’s in shadow.

5. Graphics Standards: APIs and File Formats

Standards ensure interoperability across hardware/software.

A. Hardware Standards (APIs)

B. Software Standards (File Formats)

Why Standards Matter

• Portability: Code runs on any compliant GPU.
• Abstraction: Hide hardware details (e.g., OpenGL’s glBegin()/glEnd()).
• Optimization: Vendors implement standards efficiently (e.g., NVIDIA’s CUDA for GPU compute).

6. Special Topics in Modern CG

A. Non-Photorealistic Rendering (NPR)

Simulates artistic styles (e.g., cel-shading, watercolor). Techniques:

• Toon shading: Flat colors with outlines (e.g., The Legend of Zelda).
• Stylized lighting: Cel shading uses ramp textures for edges.
• Procedural textures: Hand-painted effects (e.g., Disney’s "The Princess and the Frog").

B. Volumetric Rendering

Models participating media (smoke, fog, clouds) via:

• Ray marching: Step along rays, accumulate color/transparency.
• Sparse voxel octrees: Compress 3D textures.

C. Machine Learning in CG

• Neural radiance fields (NeRF): 3D scenes from 2D images.
• GANs for super-resolution: Upscale low-res textures.
• Style transfer: Apply artistic styles to 3D models.

Exam Tip: How to Score Full Marks

1. For derivations (e.g., rotation matrix, ray-sphere intersection):

   • Show all steps with clear labels (e.g., "Step 1: Expand the quadratic equation").
   • Use LaTeX for equations (even if handwritten, write neatly).
   • Example: For 2D rotation, start with: $$\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\end{array}\right]=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]$$ Then substitute $\theta =45^{\circ }$, $\cos 45^{\circ }=\sin 45^{\circ }=\frac{\sqrt{2}}{2}$.

2. For comparisons (e.g., raster vs. vector, local vs. global illumination):

   • Use tables with Pros/Cons/Applications.
   • Highlight key differences in bold (e.g., "Vector graphics are scalable but not resolution-independent for anti-aliasing").

3. For algorithms (e.g., flood fill, ray tracing):

   • Write pseudocode or step-by-step traces.
   • Example for flood fill:

     ALGORITHM FloodFill(x, y, target_color, replacement_color)
     1. IF pixel(x,y) != target_color: RETURN
     2. SET pixel(x,y) = replacement_color
     3. FloodFill(x+1, y, target_color, replacement_color)
     4. FloodFill(x-1, y, target_color, replacement_color)
     5. FloodFill(x, y+1, target_color, replacement_color)
     6. FloodFill(x, y-1, target_color, replacement_color)
     

   • Trace: Show how it fills a 3×3 grid starting at (1,1).

4. For definitions:

   • Be precise. Avoid vague terms like "very detailed."
     • ❌ "Ray tracing is very accurate."
     • ✅ "Ray tracing models global illumination via recursive ray-object intersection, enabling physically accurate reflections, refractions, and soft shadows."

5. For applications:

   • Link to real-world examples (e.g., "Photon mapping is used in Unreal Engine 5 for cinematic lighting").
   • Mention trade-offs (e.g., "While ray tracing is photorealistic, it’s not suitable for real-time games without hardware acceleration").

6. Diagrams:

   • Sketch flowcharts for pipelines (e.g., 3D viewing pipeline: World → View → Projection → Screen).
   • Use Mermaid-style text in exams (e.g., flowchart TD: A-->B for transformations).

7. Common Pitfalls:

   • Confusing raster/vector: Raster = pixels (e.g., JPEG), vector = math (e.g., SVG).
   • Global vs. local illumination: Local (Phong) ignores indirect light; global (path tracing) simulates it.
   • Rotation matrices: Remember clockwise vs. counter-clockwise conventions (TU exams often use math convention: positive θ is counter-clockwise).

Quick Revision Table