山东大学计算机图形学期末复习10——CG12下

CG12下

Sutherland-Hodgman Clipping

Sutherland–Hodgman 算法介绍(简单易懂)_sutherland-hodgman-CSDN博客

算法思想（核心思想）

逐条边裁剪：

1. 裁剪多边形的每一条边（从顶点A到顶点B）；
2. 针对裁剪窗口的每一条边，遍历原多边形的每一条边，判断：
   • 起点和终点是否在窗口内
   • 如果有交点就加进去
   • 如果顶点在窗口内就加进去
3. 每处理一条裁剪边（如左边、右边、上边、下边），就更新一次多边形。
4. 最终得到一个新多边形，完全处于裁剪区域内。

---

可视化概念图（逻辑）

多边形在裁剪窗口中可能：

• 完全在内部 → 原样保留
• 完全在外部 → 被完全裁掉
• 部分在内部 → 生成一个新的多边形（用交点替换被切掉的部分）

我们将原多边形按顺序绕一圈处理，然后根据裁剪边来判断每一条边的两个顶点是否在边的内外。

---

四种情况（Sutherland–Hodgman 核心规则）

设一条多边形边为 $\text{from}\to \text{to}$

from	to	动作
in	in	只输出 to
in	out	输出与裁剪边的交点
out	in	输出交点 和 to
out	out	什么也不输出

裁剪流程（以矩形窗口为例）

假设裁剪窗口是矩形：

• 左边界 $x=x_{\text{min}}$
• 右边界 $x=x_{\text{max}}$
• 下边界 $y=y_{\text{min}}$
• 上边界 $y=y_{\text{max}}$

裁剪顺序通常是：

左 → 右 → 下 → 上

对于每一条边，我们将原多边形顶点当作输入列表，裁剪一次输出新的顶点列表，传给下一步使用。

光栅化与DDA算法

一、什么是光栅化（Rasterization）？

基本定义：

光栅化是把几何图形（如线段、三角形等）转换为**像素点（像素/片段）**的过程，是从“数学描述”到“图像像素”的关键步骤。

举例：一条直线 y = x + 1，在数学上是连续的，我们要决定哪些像素该被“点亮”来表示这条直线。

输出结果：

光栅化会输出许多片段（fragment），每个片段包含：

• 像素位置 (x, y)
• 插值得到的颜色、深度、纹理坐标等

二、传统光栅设备的工作方式（Raster Display）

显示器原理（以 CRT 显示器为例）：

• 电子枪依次扫描屏幕每一行（光栅扫描），从左到右、从上到下。
• 隔行扫描：先扫描奇数行，再扫描偶数行，减少闪烁。
• 图像显示原理就是——哪个像素该亮、亮多亮？

帧缓冲区（Frame Buffer）：

• 是内存中的一个二维数组，每个元素存储一个像素的信息：
  • 颜色（RGB）
  • 深度值（z-buffer）
• 显卡会把帧缓冲区的内容通过 DAC（数字-模拟转换器） 传给显示器。

三、光栅化中的扫描转换（Scan Conversion）

目标：

将“线段”转化为一串最接近的像素点。

也叫“线段光栅化”，用于绘制几何图元在像素网格上的近似表示。

基本假设：

• 线段起点/终点已转换为窗口坐标系中的整数坐标。
• 使用一个函数：write_pixel(x, y, color) 将像素(x, y)设为某种颜色。

四、DDA算法（Digital Differential Analyzer）

基本思路：

从起点 $(x_1,y_1)$ 沿 x 轴每次走一步，用浮点步长更新 y。

算法步骤：

1. 计算斜率 $m=\Delta y/\Delta x$

2. 对每个 x：
   $$y=y+m$$
   $\text{画点：}\text{writepixel(x, round(y))}$

特点：

• 简单易实现
• 每次只需一次加法和一次四舍五入

五、DDA 的问题与对称性优化

问题：

当线段很陡峭（|m| > 1）时：

• 每次 x 只加 1，但 y 要跳很多像素
• 可能会漏掉中间像素，造成“断线”现象

解决办法：利用对称性

对陡峭线段，交换 x 和 y，改为沿 y 方向遍历：

• 如果 |m| ≤ 1：x += 1, y += m
• 如果 |m| > 1：y += 1, x += 1/m（x 和 y 角色互换）

画点时注意也要交换：write_pixel(round(x), y)

Bresenham 算法

一、Bresenham 算法的动机与优势

为什么需要 Bresenham？

• DDA（Digital Differential Analyzer） 虽然原理简单，但需要：
  • 浮点加法
  • 浮点取整
• 在早期计算机或图形芯片中，这些操作代价昂贵。

Bresenham 的目标：

• 完全使用整数运算。
• 每个像素只需一次加法 + 一次比较。
• 尤其适合低成本硬件和高性能绘图。

二、基本假设与适用范围

为便于分析，先限定一种情况：

• 线段起点 $(x_0,y_0)$、终点 $(x_1,y_1)$
• 只考虑：斜率 $0\le m\le 1$（其他情况通过对称处理）
• 沿 x 轴递增，逐像素绘制

其他斜率如 $m>1$、$m<0$ 等可通过坐标交换或反转处理。

三、像素选择策略：两种候选像素

在绘图中，当前像素为 $(x_k,y_k)$，下一个像素只可能是：

• 右边像素：$(x_k+1,y_k)$
• 右上像素：$(x_k+1,y_k+1)$

要选择哪个像素？靠近线段的那个。

四、引入决策变量（Decision Variable）

核心思想：

用一个变量 d 判断哪一个候选像素更接近真实的线段。

几何解释：

• 设当前像素为 $(i,j)$，像素中心是 $(i+0.5,j+0.5)$
• 计算线段在 $x=i+1$ 处的真实 y 值 $y_{\text{line}}$
• 若 $y_{\text{line}}<j+0.5$，靠下像素
• 若 $y_{\text{line}}\ge j+0.5$，靠上像素

构造决策变量 d：

定义：
$$d=2\Delta y\cdot x-2\Delta x\cdot y+\text{常数}$$
但我们不每次都重新算，而是用**增量更新（incremental update）**来高效计算。

---

五、Bresenham 核心算法逻辑

设：

• $\Delta x=x_1-x_0$
• $\Delta y=y_1-y_0$
• 初始点为 $(x_0,y_0)$

初始决策变量（d）：

$$d_0=2\Delta y-\Delta x$$

每次迭代：

• 如果 $d<0$：
  • 选择下像素 $(x+1,y)$
  • 更新：$d=d+2\Delta y$
• 如果 $d\ge 0$：
  • 选择上像素 $(x+1,y+1)$
  • 更新：$d=d+2(\Delta y-\Delta x)$

六、完整伪代码

void drawLine(int x0, int y0, int x1, int y1) {int dx = x1 - x0;int dy = y1 - y0;int d = 2*dy - dx;int y = y0;for (int x = x0; x <= x1; x++) {write_pixel(x, y);  // 画当前像素if (d > 0) {y += 1;d += 2*(dy - dx);} else {d += 2*dy;}}
}

推导 Bresenham 算法中的 决策变量的构造、更新公式及增量更新方式

背景：我们要解决的问题

我们希望在屏幕上绘制一条线段，从 $(x_0,y_0)$ 到 $(x_1,y_1)$，其中斜率满足 $0\le m\le 1$。这意味着：

• 主方向是 x 增加
• 对每个 $x_k$，我们希望确定对应的最合适的 像素 y 坐标

目标是用 整数加法和判断，替代 DDA 中的 浮点加法和取整。

核心思想：每步选择两个像素中的一个

设当前绘制像素为 $(x_k,y_k)$，下一个像素只能是：

1. 右边像素：$(x_k+1,y_k)$
2. 右上像素：$(x_k+1,y_k+1)$

我们要判断线段在 $x=x_k+1$ 处更靠近哪一个像素 —— 这就需要构造一个决策依据，也就是所谓的决策变量 $d_k$。

第一步：直线的真实位置

假设直线是：
$$y=mx+b$$
那么在 $x=x_k+1$ 处，真实的 y 值为：
$$y_{\text{line}}=m(x_k+1)+b$$

第二步：构造一个“判断”变量

我们想知道：

• $y_{\text{line}}$ 更接近哪个像素？是 $y_k$ 还是 $y_k+1$？

设当前像素中心为 $(x_k+1,y_k+0.5)$

于是，我们定义一个变量：
$$\delta =y_{\text{line}}-(y_k+0.5)$$

• 如果 $\delta <0$：直线在像素中心下方 → 选 右边像素
• 如果 $\delta >0$：直线在像素中心上方 → 选 右上像素

但是这个 $\delta$ 是浮点数！我们不能直接用 —— 所以我们要构造一个整数形式的决策变量 $d_k$，它的符号等价于 $\delta$。

第三步：放大消除小数，构造整数决策变量

将 $\delta$ 乘以 $2\Delta x$ 得到整数形式：
$$d_k=2\Delta y(x_k+1)-2\Delta x(y_k+0.5)$$
整理：
$$d_k=2\Delta y\cdot x_k-2\Delta x\cdot y_k+C$$
其中 C 是常数（来自 b、0.5 等项）

我们只关心的是 d_k 的正负号，所以 C 无关紧要，我们可以简化为：
$$d_k=\text{某种形式的整数表达式}\propto \text{是否选上像素}$$

第四步：递推式（增量公式）推导

为了避免每次都从头计算 $d_k$，我们希望递推计算 $d_{k+1}$：

情况一：选择右边像素（不变 y）

• 当前：$(x_k,y_k)$，下一个：$(x_{k+1},y_k)$
• 决策变量更新公式：

$$d_{k+1}=d_k+2\Delta y$$

情况二：选择右上像素（y 增 1）

• 当前：$(x_k,y_k)$，下一个：$(x_{k+1},y_k+1)$
• 决策变量更新公式：

$$d_{k+1}=d_k+2\Delta y-2\Delta x$$

统一更新逻辑（总结）

我们设置：
$$\{\begin{array}{l}d=2\Delta y-\Delta x\text{（初始值）}\\ \text{如果 }d<0,\text{选右边像素}\Rightarrow d\leftarrow d+2\Delta y\\ \text{否则，选右上像素}\Rightarrow d\leftarrow d+2(\Delta y-\Delta x)\end{array}$$

伪代码实现（只用整数！）

void bresenham_line(int x0, int y0, int x1, int y1) {int dx = x1 - x0;int dy = y1 - y0;int d = 2 * dy - dx;  // 初始决策变量int y = y0;for (int x = x0; x <= x1; x++) {write_pixel(x, y);if (d < 0) {d += 2 * dy;} else {y += 1;d += 2 * (dy - dx);}}
}