11-CG-Ray casting

Rendering

Rendering refers to the entire process that produces color values for pixels, given a 3D representation of the scene

Pixels correspond to rays; need to figure out the visible scene point along each ray

• Called "hidden surface problem" in older texts
• "Visibility" is a more modern term
• Also, we assume (for now) a single ray per pixel

Major algorithms: Ray casting and rasterization

Ray Casting

Ray Casting Basics

Ray Casting

• For every pixel
  • Construct a ray from the eye
  • For every object in the scene
    • Find intersection with the ray
    • Keep if closest

Shading

• For every pixel
  • Construct a ray from the eye
  • For every object in the scene
    • Find intersection with the ray
    • Keep if closest shade

Shading = What Surfaces Look Like

• Surface/Scene Properties
  • surface normal
  • direction to light
  • viewpoint
• Material Properties
  • Diffuse (matte)
  • Specular (shiny)
• Light properties
  • Position
  • Intensity, ...

Ray casting = eye rays only, tracing = also secondary

• Secondary rays are used for testing shadows, doing reflections, refractions, etc.

光线投射：通过数学方法模拟光线传播，解决三维场景到二维图像的投影问题，核心是可见性计算。 着色：在可见性基础上，结合物理光照模型和材质属性，为每个像素赋予真实感颜色，核心是光照模拟。

光线投射是光线追踪的子集：前者是后者的“第一步”（确定可见性），后者通过扩展次级光线实现更复杂的物理模拟。

Ray Representation

• Origin - Point
  • Direction - Vector
• normalized is better
• Parametric line
  • $P(t)=origin+t\ast direction$
  • 
  • $P(t)=R_0+td$

Camera and Ray Generation

Construct a ray from the eye For every object in the scene

Cameras

Construct a ray from the eye

• Box with a tiny hole
• Inverted image
• Similar triangles
• Perfect image if hole infinitely small
• Pure geometric optics
• No depth of field issue (everything in focus)

Simplified Pinhole Camera

• Eye-image pyramid (view frustum)

• Note that the distance/size of image are arbitrary

• Eye point $e$ (center)

• Orthobasis $u,v,w$ (horizontal, up, direction)

• Field of view angle

• Image rectangle aspect ratio

Ray Generation in 2D

then we just normalize r to get the ray

$$P(t)=e+td(d=\frac{r}{||r||})$$

3D Cases

1. 三维正交基与向量分解

• 视图坐标系的基向量：
  • $\mathbf{u}$：水平向右（Right），
  • $\mathbf{v}$：垂直向上（Up），
  • $\mathbf{w}$：视图方向（View Direction，指向图像平面的正前方）。
• 向量 $\mathbf{r}$ 的构造： 从视点 $\mathbf{e}$ 到图像平面点 $\mathbf{p}(x,y)$ 的向量可分解为：$$\mathbf{r}=x\cdot \mathbf{u}+(y\cdot \text{aspect})\cdot \mathbf{v}+D\cdot \mathbf{w}$$
  • $x\cdot \mathbf{u}$：水平方向的偏移（$x\in [-1,1]$ 为归一化坐标），
  • $y\cdot \text{aspect}\cdot \mathbf{v}$：垂直方向的偏移，通过纵横比缩放 $y$ 以匹配水平方向的单位长度，
  • $D\cdot \mathbf{w}$：视点到图像平面的距离（通常设为 $D=1$ 简化计算）。

2. 归一化方向向量 $\mathbf{d}$

• 目的：提取光线方向，忽略向量长度。
• 公式：$$\mathbf{d}=\frac{\mathbf{r}}{\parallel \mathbf{r}\parallel }=\frac{x\cdot \mathbf{u}+y\cdot \text{aspect}\cdot \mathbf{v}+D\cdot \mathbf{w}}{\sqrt{x^2+(y\cdot \text{aspect}{)}^2+D^2}}$$由于 $\mathbf{u},\mathbf{v},\mathbf{w}$ 是单位正交向量，模长计算简化为各分量平方和的平方根。

3. 光线方程

三维光线的参数方程与二维一致：

$$\mathbf{P}(t)=\mathbf{e}+t\cdot \mathbf{d}(t\ge 0)$$

其中 $\mathbf{d}$ 是归一化后的方向向量，$t$ 为参数。

Orthographic Camera

• $Origin=e+x\cdot size\cdot u+y\cdot size\cdot v$
• Direction is constant: $w$

Ray-Plane Intersection

Find intersection with the ray

• Ray representation $P(t)=origin+t\ast direction$

• 3D Plane Representation (Infinite) plane defined by

  • $P_0=(x_0,y_0,Z_0)$ point in the plane
  • $n=(A,B,C)$ normal vector of the plane

• Implicit plane equation

  • $H(P)=Ax+By+Cz+D=0=n•P+D=0$
  • $D=-A{x}_0-B{y}_0-C{z}_0$

• Point-Plane distance

  • If $n$ is normalized, distance to plane is $H(P)$
  • It is a signed distance!

• Ray equation is explicit $P(t)=R_0+t\cdot R_d$

  • Parametric
  • Generates points
  • Hard to verify that a point is on the ray

• Plane equation is implicit $H(P)=n\cdot P+D$

  • Solution of an equation
  • Does not generate points
  • Verifies that a point is on the plane

Intersection means both are satisfied So, insert explicit equation of ray into implicit equation of plane & solve for t

$$P(t)=R_o+t\cdot R_d$$$$H(P)=n\cdot P+D=0$$$$n\cdot (R_o+t\cdot R_d)+D=0$$$$t=-\frac{(D+n\cdot R_o)}{n\cdot R_d}$$

if $n·R_d=0$ then ray is parallel to plane

Additional Bookkeeping

• Verify that intersection is closer than previous
  • $t<t_{current}$
  • 确保交点为最近可见点
  • 正确处理遮挡关系，实现真实渲染
• Verify that it is not out of range (behind eye)
  • $t>t_{min}$
  • 排除视点后方的无效交点
  • 避免渲染不可见区域，提升正确性

$$(r_0+t\cdot d-a)\cdot n=0$$$$t=\frac{(a-r_0)\cdot n}{d\cdot n}$$

Ray-triangle intersection

光线与三角形相交的计算是计算机图形学的核心问题之一（如光线追踪、碰撞检测），其核心在于判断光线是否与三角形所在平面相交，且交点是否位于三角形内部。

$$((P_2-r_0)\times (P_1-r_o))\cdot d>0$$$$((P_3-r_0)\times (P_2-r_o))\cdot d>0$$$$((P_1-r_0)\times (P_3-r_o))\cdot d>0$$

重心坐标（Barycentric Coordinates）

核心思想

• 任意三角形内的点可表示为三个顶点的加权和，权重称为重心坐标（$\alpha ,\beta ,\gamma$），满足 $\alpha +\beta +\gamma =1$ 且 $\alpha ,\beta ,\gamma \ge 0$。
• 图示中，点 $p_{\theta }$ 可表示为：$$p_{\theta }=p_1+\alpha u+\beta v(\text{其中 }u=p_0-p_1,v=p_2-p_1)$$当 $\alpha >0,\beta >0,\alpha +\beta \le 1$ 时，点位于三角形内部。

作用

• 判断光线与平面的交点是否在三角形内部：通过求解重心坐标的权重，验证其是否满足非负且和为1的条件。

克拉默法则（Cramer's Rule）**

数学原理

• 用于求解线性方程组的变量，核心利用行列式比值计算唯一解。
• 对于方程组 $A\mathbf{x}=\mathbf{b}$，解为：$$x_i=\frac{det(A_i)}{det(A)},\text{其中 }{A}_i\text{ 是将 }A\text{ 的第 }i\text{ 列替换为 }\mathbf{b}\text{ 的矩阵}。$$

在光线追踪中的应用

• 求解交点参数： 在光线与三角形相交的Möller-Trumbore算法中，通过构建线性方程组：$$\{\begin{array}{l}t\cdot \mathbf{d}=\alpha u+\beta v\\ \alpha +\beta +\gamma =1\end{array}$$利用克拉默法则计算重心坐标 $\beta ,\gamma$ 和参数 $t$，避免直接求解矩阵逆，提升效率。

光线与三角形相交的两步法

步骤1：光线与平面相交

• 与三角形所在平面相交，求得参数 $t$ 和交点 $P$（同光线-平面相交算法）。

步骤2：判断交点是否在三角形内部

方法1：投影到2D平面判断

• 核心思路： 将三维三角形顶点和交点投影到二维坐标系（如选择平面内的x-y平面），转化为二维点与三角形的包含性检测。
• 投影方法： 选择平面法线方向作为投影轴（如法线的最大分量方向），忽略该轴坐标，保留二维坐标。
• 2D检测： 使用重心坐标或叉乘法判断二维点是否在三角形内（如之前讨论的三边内侧条件）。

方法2：三维空间直接判断（避免投影）

• 核心思路： 利用三角形边的正交法向量判断交点是否在边的内侧，无需显式投影。
• 关键公式： 对边 $e_1=p_2-p_1$，计算正交法向量：$$\mathbf{n}={\mathbf{e}}_1-\frac{{\mathbf{e}}_1\cdot {\mathbf{e}}_2}{\parallel {\mathbf{e}}_2{\parallel }^2}{\mathbf{e}}_2$$若 $(P-p_1)\cdot \mathbf{n}\ge 0$，则交点 $P$ 在边 $e_1$ 的内侧（朝向对顶点 $p_3$）。
• 优势： 避免投影带来的精度损失，直接在三维空间中通过向量点积完成判断，与Möller-Trumbore算法逻辑一致。

1. 重心坐标与克拉默法则的结合

• 通过克拉默法则求解重心坐标 $\beta ,\gamma$，若满足 $0\le \beta ,\gamma \le 1$ 且 $\beta +\gamma \le 1$，则点在三角形内。

2. 算法优化逻辑

• 投影法：直观但需处理坐标系转换，
• 三维直接法：高效，适合硬件加速（如SIMD指令），是实时渲染（如游戏引擎）的首选。

3. 与先前内容的关联

• 前序幻灯片中通过叉乘点积判断三边内侧，本质上是重心坐标条件的几何等效（$\alpha ,\beta >0,\alpha +\beta <1$）。

概念	作用	算法关联
重心坐标	用权重表示三角形内点，判断包含性	交点内侧条件
克拉默法则	高效求解线性方程组，得到交点参数	Möller-Trumbore算法
投影到2D检测	将三维问题降维，简化判断逻辑	传统几何方法
三维直接法（叉乘/点积）	避免投影，直接利用向量方向判断内侧	现代光线追踪算法

Ray-Sphere Intersection

• Explicit Ray: $\mathbf{P}(t)={\mathbf{R}}_o+t\cdot {\mathbf{R}}_d$

• Implicit Sphere $H(\mathbf{P})=\mathbf{P}\cdot \mathbf{P}-r^2=0$

• Insert explicit equation of ray into implicit equation of sphere & solve for $t$

  $$({\mathbf{R}}_o+t{\mathbf{R}}_d)\cdot ({\mathbf{R}}_o+t{\mathbf{R}}_d)-r^2=0$$

$$\underset{a}{\underbrace{{\mathbf{R}}_{\mathbf{d}}\cdot {\mathbf{R}}_{\mathbf{d}}}}{t}^2+\underset{b}{\underbrace{2{\mathbf{R}}_{\mathbf{d}}\cdot {\mathbf{R}}_{\mathbf{o}}}}t+\underset{c}{\underbrace{({\mathbf{R}}_{\mathbf{o}}\cdot {\mathbf{R}}_{\mathbf{o}}-r^2)}}=0$$

• Quadratic: $a{t}^2+bt+c=0$

  • $a=1$ (remember, $\parallel {\mathbf{R}}_d\parallel =1$)
  • $b=2{\mathbf{R}}_d\cdot {\mathbf{R}}_o$
  • $c={\mathbf{R}}_o\cdot {\mathbf{R}}_o-r^2$

• With discriminant:

  $$\mathrm{\Delta }=\sqrt{b^2-4ac}$$

• And solutions:

  $$t_{\pm }=\frac{-b\pm d}{2a}$$

• $\mathrm{\Delta }>0$：光线与球体相交于两点，
  • $t_{-}$ 和 $t_{+}$（假设 $t_{-}<t_{+}$），取最小正根作为有效交点（光线从外向内入射），
• $\mathrm{\Delta }=0$：光线与球体相切，仅有一个交点（$t=-b/2$），
• $\mathrm{\Delta }<0$：光线与球体无交点。

交点的有效性判断筛选有效参数 $t$

• 若 $t_{+}$ 和 $t_{-}$ 均为正：取较小的 $t$ 值（最近交点），
• 若 $t_{-}$ 为负、$t_{+}$ 为正：取 $t_{+}$（光线从外部入射，交点在球体表面），
• 若两者均为负：光线起点在球体外部且远离球体，无有效交点。

---

$$t_c=(\mathbf{c}-{\mathbf{r}}_0)\cdot \mathbf{d}$$$$b=\parallel {\mathbf{r}}_c-\mathbf{c}\parallel$$$$w=\sqrt{a^2-b^2}$$$$t_{rh}=t_c-w$$

Intersection Point

$$P=A+t_{int}D$$

Intersection Normal:

$$N=\frac{P-C}{|P-C|}$$

For spheres centered at origin

Sphere Normal $\frac{Q}{||Q||}$

$Q=P(t)$, intersection point