GAMES101_notes_04

GAMES101: 现代计算机图形学入门

笔记04:Ray-Tracing

Lecture 13 Ray Tracing 1(Whitted-Style Ray Tracing)

Why Ray Tracing

  • Rasterization couldn’t handle global effects well
    • (soft) shadows
    • especially when the light bounces more than once
  • Rasterization is fast, but directions is very slow
    • Rasterization: real-time, ray tracing: offline
    • ~10K CPU core hours to render one frame in production

Basic Ray Tracing Algorithm

Three ideas about light rays

  1. Light travels in straight lines(though this is wrong)
  2. Light rays do not “collide” with each other if they cross(though this is still wrong)
  3. Light rays travel from the light sources to the eye(but the physics is invariant under path reversal - reciprocity)

Ray Casting

  1. Generate an image by casting one ray per pixel
  2. Check for shadows by sending a ray to the light

Recursive(Whitted-Style) Ray Tracing

  • 考虑每个从眼睛出发的光线到每个物体处发生的折射和反射的结果;
  • 对于每个折射和反射的结果,分别计算其到光源的点的着色结果,加总后得到最后的着色值
  • 每次折射后的结果都会发生一定的能量损耗

Ray-Surface Intersection

Ray is defined by its origin and a direction vector

\[\mathbf{r}(t) = \mathbf{o} + t\mathbf{d}, \quad 0 \le t < \infty\]

Ray Intersection With Sphere

\[\mathrm{Ray: } \mathbf{r}(t) = \mathbf{o} + t\mathbf{d}, \quad \\ \mathrm{Sphere: } \mathbf{p} : (\mathbf{p} - \mathbf{c})^2 - R^2 = 0\]

Ray Intersection With Implicit Surface

\[\mathrm{Ray: }\quad \mathbf{r}(t) = \mathbf{o} + t\mathbf{d}, \quad \\ \mathrm{General\ implicit\ surface: }\quad \mathbf{p} : f(\mathbf{p}) = 0\\ \mathrm{Substitute\ ray\ equation: }\quad f(\mathbf{o} + t\mathbf{d}) = 0\]

Ray Intersection With Triangle Mesh

Why?

  • Rendering: visibility, shadows, lighting
  • Geometry: inside/outside test

How?

  • Simple idea: just intersect ray with each triangle
  • Simple, but slow(acceleration? – later)
  • Note: can have 0, 1 intersections(ignoring multiple intersections)

Ray Intersection With Triangle

Triangle is in a plane

  • Ray-plane intersection
  • Test if hit point is inside triangle

Plane is defined by normal vector and a point on plane

\[\mathbf{p}: (\mathbf{p} - \mathbf{p}')\cdot\mathbf{N} = 0\qquad ax + by + cz + d = 0\]

Moller Trumbore Algorithm

A fast approach, giving barycentric coordinate directly

Derivation in the discussion section!

\[\mathbf{O} + t\mathbf{D} = (1 - b_1 - b_2)\mathbf{P}_0 + b_1 \mathbf{P}_1 + b_2\mathbf{P}_2\]

Accelerating Ray-Surface Intersection

Simple ray-scene intersection

  • Exhaustively test ray-intersection with every object
  • Find the closest hit(with minimum t)

Bounding Volumes

Quick way to avoid intersections: bound complex object with a simple volume

  • Object is fully contained in the volume
  • If it doesn’t hit the volume, it doesn’t hit the object
  • So test BVol first, then test object if it hits

Ray-Intersection with Box

  • Understanding: box is the intersection of 3 pairs of slabs
  • Specifically, we often use an Axis-Aligned Bounding Box(AABB)

Key ideas

  • The ray enters the box only when it enters all pairs of slabs
  • The ray exits the bos as long as it exits any pair of slabs

具体操作方法:

  • 考虑光线通过分别通过每个方向的两个平面的时间$t_{\min},\ t_{\max}$
  • 如果进入时间的最大值小于射出时间的最小值,则说明光线同包围盒有交点
  • 对于时间为负值的情况
    • 如果进入时间为负,离开时间为正,则可以说明光源在盒中;
    • 如果离开时间为负,说明盒子沿光路在光源后面
  • In summary, ray and AABB intersect iff
    • $t_{enter} < t_{exit}\ \mathrm{and}\ t_{exit} \ge 0$

Lecture 14 Ray Tracing 2(Acceleration & Radiometry)

本讲内容:

  • Using AABBs to accelerate ray tracing
    • Uniform grids
    • Spatial partitions
  • Basic radiometry(辐射度量学)

Uniform Spatial Partitions(Grids)

Preprocess - Build Acceleration Grid

  • Find bounding box
  • Create grid
  • Store each object in overlapping cells

Step through grid in ray traversal order, for each grid cell test intersection with all objects stored at that cell.(类似分治的想法)

存在的问题:当场景中的物体分布过于稀疏的时候,会存在冗余运算的情况。

Spatial Partitions

Examples:

  • Oct-Tree 每次沿每个维度进行分割
  • KD-Tree 每次只沿一个维度进行分割
  • BSP-Tree 每次沿一个方向进行分割

考虑到AABB的结构,采用KD-Tree是较为合适的解决方法

Data Structure for KD-Trees

  • Internal nodes store
    • split axis: x-, y- or z-axis
    • split position: coordinate of split plane along axis
    • children: pointers to child nodes
    • No objects are stored in internal nodes
  • Leaf nodes store
    • list of objects

对于构建好的数据结构,只要进行遍历,判断光线经过每个结构时是否可能相交,就可以进行下一步的判断。

但是KD-Tree(还有八叉树)来说,还有如下两个问题难以解决:

  • 同一个物体可能存在多个盒子里
  • 判断三角形是否和盒子相交很困难

因此提出了如下的解决方法:

Object Partitions & Bounding Volume Hierarchy(BVH)

采取和KD-Tree相反的思路,不再对空间进行划分,而是对物体进行划分,然后构建新的子包围盒,这样得到的结构,虽然包围盒可能彼此相交且空间划分并不完全均匀,但是可以保证每个物体只存在于一个包围盒中,且不需要担心盒子和物体的相交问题(因为盒子是由包围关系确定的)

Summary: Building BVHs

  • Find bounding box
  • Recursively split set of objects in two subsets
  • Recompute the bounding box of the subsets
  • Stop when necessary
  • Store objects in each leaf node

细节问题:

  • How to subdivide a node?
    • Choose a dimension to split
    • Heuristic #1: Always choose the longest axis in node(保证盒子尽可能是方的)
    • Heuristic #2: Split node at location of median object
  • Termination criteria?
    • Heuristic: stop when node contains few elements(e.g. 5)

Data Structure for BVHs

  • Internal nodes store
    • Bounding box
    • Children: pointers to child nodes
  • Leaf nodes store
    • Bounding box
    • List of objects
  • Nodes represent subset of primitives in scene
    • All objects in subtree

BVH Traversal(pseudocode)

Intersect(Ray ray, BVH node){
  if(ray misses node.bbox) return;

  if(node is a leaf node)
    test intersection with all objs;
    return closest intersection;

  hit1 = Intersect(ray, node.child1);
  hit2 = Intersect(ray, node.child2);

  return the closer of hit1, hit2;
}

Spatial vs. Object Partitions

  • Spatial partition(e.g. KD-Tree)
    • Partition space into non-overlapping regions
    • An object can be contained in multiple regions
  • Object partition(e.g. BVH)
    • Partition set of objects into disjoint subsets
    • Bounding boxes for each set may overlap in space

Basic Radiometry

Motivation

之前提到的Blinn-Phong模型并没有给出I的物理意义,对于Whitted光线追踪来说,也是缺少一些变量的定义。

All the answers can be found in radiometry!

Radiometry

  • Measurement system and unit for illumination
  • Accurately measure the spatial properties of light
    • New terms: Radiant flux, intensity, irradiance, radiance
  • Perform lighting calculations in a physically correct manner

Radiant Energy and Flux(Power)

Definition: Radiant energy is the energy of electromagnetic radiation. It is measured in units of joules, and denoted by the symbol:

\[Q[\mathrm{J} = \mathrm{Joule}]\]

Definition: Radiant flux(power) is the energy emitted, reflected, transmitted or received, per unit time.

\[\Phi \equiv \frac{\mathrm{d}Q}{\mathrm{d}t} [\mathrm{W} = \mathrm{Watt}] [\mathrm{lm} = \mathrm{lumen}]\]

Flux - # photons flowing through a sensor in unit time

Important Light Measurements of Interest

  • Radiant Intensity - Light Emitted From A Source
  • Irradiance - Light Falling On A Surface
  • Radiance - Light Traveling Along A ray

Radiant Intensity

Definition: The radiant(luminous) intensity is the power per unit solid angle(立体角) emitted by a point light source.

\[I(\omega) \equiv \frac{\mathrm{d}\Phi}{\mathrm{d}\omega}\] \[\left[\frac{\mathrm{W}}{\mathrm{sr}}\right]\left[\frac{\mathrm{lm}}{\mathrm{sr}} = \mathrm{cd} = \mathrm{candela}\right]\]

Angles and Solid Angles

  • Angle: ratio of subtended arc length on circle to radius
    • $\theta = \frac{l}{r}$
    • Circle has $2\pi$ radians
  • Solid angle: ratio of subtended area on sphere to radius squared
    • $\Omega = \frac{A}{r^2}$
    • Sphere has $4\pi$ steradians

Differential Solid Angles

\[\mathrm{d}A = (r\mathrm{d}\theta)(r\sin\theta\mathrm{d}\phi) = r^2\sin\theta\mathrm{d}\theta\mathrm{d}\phi\]

单位立体角

\[\mathrm{d}\omega = \frac{\mathrm{d}A}{r^2} = \sin\theta\mathrm{d}\theta\mathrm{d}\phi\]

如果对一个球各个方向的单位立体角进行积分,

\[\Omega = \int_{S^2}\mathrm{d}\omega = \int_{0}^{2\pi}\int_{0}^\pi \sin\theta \mathrm{d}\theta\mathrm{d}\phi = 4\pi\]

这同之前立体角的定义相符合;对于均匀照射的点光源,我们沿各个单位立体角对Radiant Intensity进行积分,可得

\[\Phi = \int_{S^2}I\mathrm{d}\omega = 4\pi I\\\]

因此对于均匀的点光源而言,

\[I = \frac{\Phi}{4\pi}.\]

Lecture 15 Ray Tracing 3(Light Transport & Global Illumination)

本讲内容

  • Radiometry cont.
  • Light transport
    • The reflection equation
    • The rendering equation
  • Global illumination
  • Probability review

Irradiance

Definition: The irradiance is the power per(perpendicular/projected) unit area incident on a surface point.

\[E(\mathbf{x}) \equiv \frac{\mathrm{d}\Phi(\mathbf{x})}{\mathrm{d}A}\] \[\left[\frac{\mathrm{W}}{\mathrm{m}^2}\right]\left[\frac{\mathrm{lm}}{\mathrm{m}^2} = \mathrm{lux}\right]\]

Lambert’s Cosine Law

Irradiance at surface is proportional to cosine of angle between light direction and surface normal.

Correction: Irradiance Falloff

  • Assume light is emitting power $\Phi$ in a uniform angular distribution
  • 计算从光源出发,沿$\Phi$方向在两个不同距离的球面上的Radiant Intensity,由于其只与单位立体角有关,而其始终是$\Phi$,因此两处的Radiant Intensity是相同的;而由于Irradiance计算的是单位面积上的能量,因此Irradiance会随着距离的增加按距离的平方反比逐渐衰减。

Radiance

Radiance is the fundamental field quantity that describes the distribution of light in an environment

  • Radiance is the quantity associated with a ray
  • Rendering is all about computing radiance

Definition: The radiance(luminance) is the power emitted, reflected, transmitted or received by a surface, per unit solid angle, per projected unit area.

\[L(p, \omega) \equiv \frac{\mathrm{d}^2\Phi(p, \omega)}{\mathrm{d}\omega\mathrm{d}A\cos\theta},\]

where $\cos \theta$ accounts for projected surface area.

\[\left[\frac{\mathrm{W}}{\mathrm{sr}\ \mathrm{m}^2}\right]\left[\frac{\mathrm{cd}}{\mathrm{m}^2} =\frac{\mathrm{lm}}{\mathrm{sr\ m}^2} = \mathrm{nit}\right]\]

Recall

  • Irradiance: power per projected unit area
  • Intensity:power per solid angle

So

  • Radiance: Irradiance per solid angle
  • Radiance: Intensity per projected unit area

所以可以进一步得到如下新的定义:

Incident Radiance

  • Incident radiance is the irradiance per unit solid angle arriving at the surface.
  • i.e., it is the light arriving at the surface along a given ray(point on surface and incident direction)
\[L(p, \omega) = \frac{\mathrm{d}E(p)}{\mathrm{d}\omega \cos \theta}\]

Exiting Radiance

  • Exiting radiance is the intensity per unit projected area leaving the surface.
  • e.g., for an area light it is the light emitted along a given ray(point on surface and exit direction).
\[L(p, \omega) = \frac{\mathrm{d}I(p, \omega)}{\mathrm{d}A \cos \theta}\]

这里之所以用的分别是Irradiance和Intensity进行微分,是因为对于一个反射问题,我们需要考虑的两件事分别是

  • 给定方向的光照打在单位面上吸收多少能量
  • 从单位面发出的光照会打到任意方向,落在特定方向上的能量是多少

这两件事就决定了对于Incident Radiance和Exiting Radiance,分别采取不同的格式来定义。

Irradiance vs. Radiance

  • Irradiance: total power received by area $\mathrm{d} A$
  • Radiance: power received by area $\mathrm{d} A$ from “direction” $\mathrm{d}\omega$
\[\mathrm{d}E(p, \omega) = L_i(p, \omega) \cos \theta \mathrm{d}\omega\] \[E(p) = \int_{H^2}L_i(p, omega)\cos\theta\mathrm{d}\omega\]

差别就是一个方向性。

BRDF: Bidirectional Reflectance Distribution Function 双向反射分布函数

用来说明如果一个能量,从某个方向进来,将会沿指定方向分布多少能量。

Reflection at a Point

  • Radiance from direction $\omega_i$ turns into the power $E$ that $\mathrm{d}A$ receives
  • Then the power $E$ will become the radiance to any other direction $\omega_o$

BRDF

  • The Bidirectional Reflectance Distribution Function(BRDF) represents how much light is reflected into each outgoing direction $\omega_r$ from each incoming direction
\[f_r(\omega_i\rightarrow \omega_r) = \frac{\mathrm{d}L_r(\omega)}{\mathrm{d}E_i(\omega_i)} = \frac{\mathrm{d}L_r(\omega_r)}{L_i(\omega_i)\cos\theta_i\mathrm{d}\omega_i}\quad \left[\frac{1}{\mathrm{sr}}\right]\]

描述了光线和物体是如何作用的,因此$f$定义了不同的材质

The Reflection Equation

\[L_r(p, \omega_r) = \int_{H^2}f_r(p, \omega\rightarrow \omega_r)L_i(p, \omega_i)\cos\theta_i \mathrm{d}\omega_i\]

The Rendering Equation

  • Re-write the reflection equation by adding an Emission term to make it general:
\[L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i) \mathrm{d}\omega_i\]

Note: now, we assume that all directions are pointing outwards.

对于渲染方程,如果我们仅考虑一次反射,则$L_i$与$L_o$并无关联。但是当我们递归考虑,即经过光源照射后的每个面都会照射其他面,则此时的渲染方程可以写作

\[L_r(x, \omega_r) = L_e(p, \omega_r) + \int_{\Omega}L_r(x', -\omega_i)f_r(x, \omega_i, \omega_r) \cos\theta_i \mathrm{d}\omega_i\]

此时在渲染方程的结构中未知项仅为$L_r$,发现其实际上是一个第二类Fredholm Integral Equation,其一般形式为

\[l(u) = e(u) + \int l(v) K(u, v)\mathrm{d}v\]

如果进一步用算子$L, E, K$来替代上述表示,则有

\[L = E + KL,\]

which can be discretized to a simple matrix equation($L, E$ are vectors, $K$ is the light transport matrix)

  • General class numerical Monte Carlo methods
  • Approximate set of all paths of light in scene
\[L = E + KL \Rightarrow (I-K)L = E \\ \Rightarrow L = (I-K)^{-1}E = E + KE + K^2E + \cdots\]

由此得到的便是全局光照结果,具体来说,$E$是光源项,$KE$是直接光照项(一次反射,能够体现阴影),$K^2E$及以后是间接光照项(镜子和其他非光源的反射)。对于光栅化这种方法,对于光源和直接光照会有很好的刻画,对于间接光照部分比较难处理。

Probability Review

  • $X$: random variable. Represents a distribution of potential values
  • $X\sim p(x)$: probability density function(PDF). Describes relative probability of a random process choosing value $x$
  • $E[x]$: Expected Value of a Random Variable. The average value that one obtains if repeatedly drawing samples from the random distribution.
\[E[X] = \int xp(x)\mathrm{d}x \\ E[f(X)] = \int f(x)p(x)\mathrm{d}x\]

Lecture 16 Ray-Tracing 4(Monte Carlo Path Tracing)

本讲内容

  • A Brief Review
  • Monte Carlo Integration
  • Path Tracing

Review

Review - The Rendering Equation

Describing the light transport

\[L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i) \mathrm{d}\omega_i\]

Review - Probabilities

  • Continuous Variable and Probability Density Functions
  • Understanding: randomly pick an $X$ –> more likely to be a number closer to 0(in this case)

Monte Carlo Integration

  • Why: we want to solve an integral, but it can be too difficult to solve analytically.
  • What & How: estimate the integral of a function by averaging random samples of the function’s value.

Let us define the Monte Carlo estimator for the definite integral of given function $f(x)$

  • Definite integral: $\int_a^b f(x)\mathrm{d}x$
  • Random variable: $X_i \sim p(x)$
  • Monte Carlo estimator: $F_N = \frac{1}{N}\sum_{i = 1}^N\frac{f(X_i)}{p(X_i)}$

$p$提供了采样${X_i}$的规则,对于概率密度大的位置,可以采样的次数也会变多,因此分母需要除以$p(X_i)$

Some notes

  • The more samples, the less variance.
  • Sample on x, integrate on x.

Path Tracing

Motivation: Whitted-Style Ray Tracing:

  • Always perform specular reflections/refractions
  • Stop bouncing at diffuse surfaces

which are not absolutely right. Whitted-style ray tracing is wrong. But the rendering equation is correct. But it involves

  • Solving an integral over the hemisphere, and
  • Recursive execution

A Simple Monte Carlo Solution(Direct Illumination)

We want to compute the radiance at $p$ towards the camera

\[L_o(p, \omega_o) = \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i) \mathrm{d}\omega_i\]

Monte Carlo integration:

\[\int_a^b f(x)\mathrm{d}x \approx \frac{1}{N}\sum_{i = 1}^N\frac{f(X_i)}{p(X_k)},\qquad X_i \sim p(x)\]

What’s our “$f(x)$”?

\[L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i)\]

What’s our pdf?

\[p(\omega_i) = \frac{1}{2\pi}\]

(assume uniformly sampling the hemisphere)

So, in general

\[L_o(p, \omega_o) = \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i) \mathrm{d}\omega_i\\ \approx \frac{1}{N}\sum_{i = 1}^N\frac{ L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) (n \cdot \omega_i)}{p(\omega_i)}\]

What does it mean? A correct shading algorithm for direct illumination!

Algorithm:

shade(p, wo)
  Randomly choose N directions wi~pdf
  Lo = 0.0
  For each wi
    Trace a ray r(p, wi)
    If ray r hit the light
      Lo += (1 / N) * L_i * f_r * cosine / pdf(wi)
  Return Lo

Introducing Global Illumination

One more step forward: what if a ray hits an object?

shade(p, wo)
  Randomly choose N directions wi~pdf
  Lo = 0.0
  For each wi
    Trace a ray r(p, wi)
    If ray r hit the light
      Lo += (1 / N) * L_i * f_r * cosine / pdf(wi)
    Else If ray r hit an object at q
      Lo += (1 / N) * shade(q, -wi) * f_r * cosine / pdf(wi)
  Return Lo

Problem 1: Explosion of #rays as #bounces go up

From now on, we always assume that one 1 ray is traced at each shading point:

shade(p, wo)
  Randomly choose ONE directions wi~pdf
  Lo = 0.0
  For each wi
    Trace a ray r(p, wi)
    If ray r hit the light
      Lo += L_i * f_r * cosine / pdf(wi)
    Else If ray r hit an object at q
      Lo += shade(q, -wi) * f_r * cosine / pdf(wi)
  Return Lo

This is path tracing(Distributed Ray Tracing if $N != 1$)

But this will be noisy!

  • No problem, just trace more paths through each pixel and average their radiance!

Ray Generation

Very similar to ray casting in ray tracing

ray_generation(camPos, pixel)
  Uniformly choose N sample positions within the pixel
  pixel_radiance = 0.0
  For each sample in the pixel
    Shoot a ray r(camPos, cam_to_sample)
    If ray r hit the scene at p
      pixel_radiance += 1 / N * shade(p, sample_to_cam)
  Return pixel_radiance

Problem 2: The recursive algorithm will never stop

Solution: Russian Roulette(RR)

  • Russian Roulette is all about probability
    • With probability $0 < P < 1$, you will fine
    • With probability $1 - P$, otherwise
  • How to do
    • Previously, we always shoot a ray at a shading point and get the shading result $Lo$
    • Suppose we manually set a probability $P(0 < P < 1)$
    • With probability $P$, shoot a ray and return the shading result divided by $P$: $Lo / P$
    • With probability $1-P$, don’t shoot a ray and you’ll get $0$

In this way, you can still expect to get $Lo$:

\[E = P * (Lo / P) + (1 - P) * 0 = Lo\]

Modified Algorithm

shade(p, wo)
  Manually specify a probability P_RR
  Randomly select ksi in a uniform dist. in [0, 1]
  If(ksi > P_RR) return 0.0;

  Randomly choose ONE directions wi~pdf
  Lo = 0.0
  For each wi
    Trace a ray r(p, wi)
    If ray r hit the light
      Lo += L_i * f_r * cosine / pdf(wi) / P_RR
    Else If ray r hit an object at q
      Lo += shade(q, -wi) * f_r * cosine / pdf(wi) / P_RR
  Return Lo

Sampling the light(pure math)

Now we already have a correct version of path tracing! But it’s not really efficient.

The reason of being inefficient: A lot of rays are “wasted” if we uniformly sample the hemisphere at the shading point.

Monte Carlo methods allows any sampling methods, so we can sample the light(therefore no rays are “wasted”)

  • Assume uniformly sampling on the light:
    • $pdf = 1 / A$(because $\int pdf \mathrm{d}A = 1$)
    • But the rendering equation integrates on the solid angle: $Lo = \int Li fr \cos \mathrm{d}\omega$
  • Recall Monte Carlo Integration: Sample on $x$ & integrate on $x$
    • Can we sample on the light, can we integrate on the light?
  • Need to make the rendering equation as an integral of $\mathrm{d}A$
    • Need the relationship between $\mathrm{d}\omega$ and $\mathrm{d}A$
    • Recall the alternative def. of solid angle: Projected area on the unit sphere
    • $\mathrm{d}\omega = \frac{\mathrm{d}A\cos\theta’}{|x’ - x|^2}$
  • Then we can rewrite teh rendering equation as
\[L_o(p, \omega_o) = \int_{\Omega^+}L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) \cos \theta \mathrm{d}\omega_i \\ = \int_A L_i(p, \omega_i)f_r(p, \omega_i, \omega_o) \frac{\cos\theta\cos\theta'}{\|x' - x\|^2} \mathrm{d}A\]

Now the modified Monte Carlo integration:

  • “$f(x)$”: everything inside
  • pdf: $1 / A$

Now we consider the radiance coming from two parts:

  1. light source(direct, no need to have RR)
  2. other reflectors(indirect, RR)

Modified Algorithm:

shade(p, wo)
  // Contribution from the light source.

  Uniformly sample the light at x' (pdf_light = 1 / A)
  L_dir = L_i * f_r * cos theta * cos theta' / |x' - p|^2 / pdf_light

  // Contribution from other reflectors.

  L_indir = 0.0
  Test Russian Roulette with probability P_RR
  Uniformly sample the hemisphere toward wi(pdf_hemi = 1 / 2pi)
  Trace a ray r(p, wi)
  If ray r hit a non-emitting object at q
    L_indir = shade(q, -wi) * f_r * cos theta / pdf_hemi / P_RR

  Return L_dir + L_indir

One final thing: how do we know if the sample on teh light is not blocked or not?

  L_dir = 0.0
  Uniformly sample the light at x' (pdf_light = 1 / A)
  Shoot a ray from p to x'
  If the ray is not blocked in the middle
    L_dir = ...

Is Path Tracing Correct?

Yes, almost 100% correct, a.k.a PHOTO-REALISTIC.

Is Path Tracing “Introductory”?

This time, yes. Fear the science, my friends.