09-CG-Clipping

---

Clipping

Eliminate portions of objects outside the viewing frustum

View Frustum

• boundaries of the image plane projected in 3D
• a near & far clipping plane

User may define additional clipping planes

Why Clip?

• Avoid degeneracies
  • Don’t draw stuff behind the eye
  • Avoid division by 0 and overflow
• Efficiency
• Other graphics applications (often non-convex)

Clipping Strategies

Don't clip (and hope for the best)

• 完全不进行裁剪，直接渲染所有物体，依赖后续阶段（如光栅化或深度测试）处理不可见部分。

• 优缺点：

  • 优点：实现简单，无需额外计算。
  • 缺点：
    • 效率极低：浪费资源渲染不可见物体。
    • 可能引发错误：如近平面内物体导致投影失真（透视除法分母趋近于0）。

• 适用场景：

  • 极简单场景或调试阶段（如仅测试少量图元）。

Clip on-the-fly during rasterization

• 在光栅化阶段（即生成像素时）实时判断像素是否在视锥体内，仅绘制可见像素。

• 优缺点：

  • 优点：
    • 无需提前处理几何，逻辑简单。
    • 适用于动态变化的裁剪区域（如实时调整的裁剪框）。
  • 缺点：
    • 所有几何（包括完全不可见的）仍需经过顶点变换、光照等阶段，效率仍有浪费。
    • 对复杂模型（如高多边形网格）性能影响显著。

• 适用场景：

  • 2D图形或简单3D场景（如手机游戏中的轻量级渲染）。

Analytical clipping: alter input geometry

在几何处理阶段（如顶点着色器后），通过数学分析提前裁剪掉视锥体外的部分，修改输入几何（如截断线段、分割多边形）。

• 典型算法：

  • 线段裁剪：Sutherland-Hodgman算法（逐平面裁剪线段，保留可见部分）。
  • 多边形裁剪：Weiler-Atherton算法（处理复杂多边形的裁剪与重建）。

• 优缺点：

  • 优点：
    • 高效：提前剔除不可见几何，减少后续阶段（如光栅化、片元着色）的工作量。
    • 精确：几何级裁剪，避免像素级冗余计算。
  • 缺点：
    • 实现复杂：需处理几何求交（如线段与平面交点、多边形分割）。
    • 依赖几何类型：对非多边形图元（如曲线）处理困难。

• 适用场景：

  • 主流3D渲染管线（如游戏引擎、CAD软件），是图形流水线的标准阶段。

Point & Line Clipping

Implicit 3D Plane Equation

Plane defined by:

• point $p$ & normal $n$
• normal $n$ & offset $d$
• 3 points

Implicit plane equation

$Ax+By+Cz+D=0$

Homogeneous Coordinates

Homogenous point: $(x,y,z,w)$

• infinite number of equivalent homogenous coordinates: $(sx,sy,sz,sw)$

Homogenous Plane Equation:

$Ax+By+Cz+D=0\to H=(A,B,C,D)$

Infinite number of equivalent plane expressions:

$sAx+sBy+sCz+sD=0\to H=(sA,sB,sC,sD)$

Point-to-Plane Distance

If $(A,B,C)$ is normalized:

$$d=H\cdot p=H^{T}p=Ax+By+Cz+D$$

d is a signed distance

• If $d=H^T\cdot p\ge 0$ pass through
• If $d=H^T\cdot p<0$ clip

Clipping with respect to View Frustum

• Test against each of the 6 planes

  • Normals oriented towards the interior

• Clip point $p$ if any $H^T•p<0$

$$H_{near}=\left(\begin{array}{cccc}0& 0& -1& -\text{near}\end{array}\right)$$$$H_{far}=\left(\begin{array}{cccc}0& 0& 1& \text{far}\end{array}\right)$$$$H_{bottom}=\left(\begin{array}{cccc}0& \text{near}& \text{bottom}& 0\end{array}\right)$$$$H_{top}=\left(\begin{array}{cccc}0& -\text{near}& -\text{top}& 0\end{array}\right)$$$$H_{left}=\left(\begin{array}{cccc}\text{near}& 0& \text{left}& 0\end{array}\right)$$$$H_{right}=\left(\begin{array}{cccc}-\text{near}& 0& -\text{right}& 0\end{array}\right)$$

Clipping & Transformation

Transform M (e.g. from world space to NDC)

Role of Transformation Matrix $M$

• $M$ represents a composite transformation (e.g., model → view → projection) that maps vertices from world space to clip space (or NDC, normalized device coordinates).
• Example: $M=M_{\text{proj}}\times M_{\text{view}}\times M_{\text{model}}$.

Transformation of Points vs. Planes

• Points/Vertices: Transformed directly by $M$:$$P^{\prime }=M\cdot P$$
• Clipping Planes: Plane equations (e.g., view frustum planes) cannot be transformed with $M$ directly. Instead, they require the inverse transpose matrix $(M^{-1}{)}^T$ to preserve their geometric relationship with points.

Mathematical Reason: Duality of Points and Planes

• A plane $\mathbf{H}$ and a point $P$ satisfy $\mathbf{H}\cdot P=0$ (point lies on plane).
• After transformation, we need ${\mathbf{H}}^{\prime }\cdot P^{\prime }=0$ to imply $\mathbf{H}\cdot P=0$. This leads to:$${\mathbf{H}}^{\prime }=\mathbf{H}\cdot M^{-1}\text{(or as a column vector: }{\mathbf{H}}^{\prime T}=(M^{-1}{)}^T\cdot {\mathbf{H}}^T\text{)}$$

The inverse undoes the effect of $M$ on the plane, and the transpose ensures the transformation works in the dual space of planes (preserving dot product consistency).

Practical Example: View Frustum to NDC

• View frustum planes (defined in view space) are transformed to NDC using $(M_{\text{proj}}^{-1}{)}^T$, where $M_{\text{proj}}$ is the projection matrix.
• This ensures that the clipping condition (e.g., $\mathbf{H}\cdot P\ge 0$ for interior points) remains valid in the new coordinate space (e.g., NDC’s $[-1,1{]}^3$ cube).

Line Segment Clipping (4 cases)

If $H\cdot p>0$ and $H\cdot q<0$

• clip q to plane

---

If $H\cdot p<0$ and $H\cdot q>0$

• clip p to plane

---

If $H\cdot p>0$ and $H\cdot q>0$

• pass through

---

If $H\cdot p<0$ and $H\cdot q<0$

• clipped out

Line – Plane Intersection

Explicit (Parametric) Line Equation

$$L(t)=P_0+t\cdot (P_1,-P_0)$$$$L(t)=(1-t)\ast P_0+t\cdot P_1$$

How do we intersect?

Insert explicit equation of line into implicit equation of plane: $Ax+By+Cz+D=0$

1. Line Parametric Equation: A line through points $P_0$ and $P_1$ is $L(t)=P_0+t(P_1-P_0)$, where $t\in \mathbb{R}$ (or $t\in [0,1]$ for a segment).

2. Plane Implicit Equation: A plane with normal vector $\mathbf{n}=(A,B,C)$ is $Ax+By+Cz+D=0$.

3. Intersection Calculation:

   • Substitute $L(t)$ into the plane equation to solve for $t$:$$t=\frac{-(\mathbf{n}\cdot P_0+D)}{\mathbf{n}\cdot (P_1-P_0)}$$
   • If $\mathbf{n}\cdot (P_1-P_0)\ne 0$, the line intersects the plane at $L(t)$.

4. Validity for Segments:

   • For a line segment, check if $t\in [0,1]$.

5. Graphics Application:

   • Use $t$ to interpolate attributes (color, normals) at the intersection point for rendering/clipping.

Acceleration using outcodes

Efficiency Problem:

• The computation of the intersections, and any corresponding interpolated values is unnecessary

Improve Efficiency: Outcode

Compute the sidedness of each vertex with respect to each bounding plane (0 = valid)

Combine into binary outcode using logical AND

• Outcodes的优势仅体现在完全不可见线段的快速剔除，可节省大量无效计算；
  • 比如
    • 
• 对于部分可见或完全可见线段，计算量与传统方法相当，无法进一步优化。
  • 比如
    •