一、 中点画线算法与 Bresenham 画线算法#

1. 【中点画线算法原理推导】 已知直线方程为 $F(x, y) = ax + by + c = 0$，其中 $a = y_0 - y_1$，$b = x_1 - x_0$。假定 $x$ 正向是最大位移方向（斜率在 $0 < k < 1$ 之间）。请完成以下推导：

(1) 简述中点画线算法的几何判别准则与算法基本思想。(2分)

【参考答案】

• 基本思想：在最大位移方向 $x$ 轴上每次递增一个像素的同时，计算下一像素列的两个备选像素中心的中点 $M(x_p+1, y_p+0.5)$，通过计算中点 $M$ 代入直线方程的函数值符号来判断直线与这两个备选像素的相对距离。
• 几何判别准则：
  • 当 $F(M) < 0$ 时，中点位于直线下方，表明直线更靠近上方像素 $P_u(x_p+1, y_p+1)$，故选取右上像素；
  • 当 $F(M) \ge 0$ 时，中点位于线上方或直线上，表明直线更靠近下方像素 $P_d(x_p+1, y_p)$，故选取右下像素。

(2) 设当前列已绘制像素点为 $(x_p, y_p)$，推导中点判别式递推公式，指出在决策变量 $d \ge 0$ 与 $d < 0$ 时，下一列决策变量 $d_{\text{next}}$ 的更新算式。(4分)

【参考答案】

• 决策变量定义：

  $$d_i = F(x_i+1, y_i+0.5) = a(x_i+1) + b(y_i+0.5) + c$$

• 当 $d_i < 0$ 时：选择右上像素 $(x_i+1, y_i+1)$。下一决策变量为：

  $$d_{i+1} = F(x_i+2, y_i+1.5) = a(x_i+2) + b(y_i+1.5) + c = d_i + a + b$$

  递增变化量为 $a + b$。

• 当 $d_i \ge 0$ 时：选择右下像素 $(x_i+1, y_i)$。下一决策变量为：

  $$d_{i+1} = F(x_i+2, y_i+0.5) = a(x_i+2) + b(y_i+0.5) + c = d_i + a$$

  递增变化量为 $a$。

(3) 推导为消除浮点运算而经过整数双倍放大后的判别式初值 $d_0$ 公式，并给出下一个像素位置选择的决策依据。(4分)

【参考答案】

• 初始中点：首个点为 $(x_0, y_0)$，下一个测试中点为 $(x_0+1, y_0+0.5)$。

• 浮点判别式初值：

  $$d_{\text{start}} = F(x_0+1, y_0+0.5) = a(x_0+1) + b(y_0+0.5) + c$$

  由于 $F(x_0, y_0) = ax_0 + by_0 + c = 0$，展开后得 $d_{\text{start}} = a + 0.5b$。

• 双倍放大消除浮点：定义整数决策变量 $d_i = 2 \cdot F(x_i+1, y_i+0.5)$，则其初值为：

  $$d_0 = 2a + b$$

  代入 $a = -\Delta y$，$b = \Delta x$，可得：

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

• 像素选择的决策依据：

  • 若 $d_i < 0$，选右上像素 $(x_i+1, y_i+1)$，且下一轮判别式更新为 $d_{i+1} = d_i + 2\Delta x - 2\Delta y$；
  • 若 $d_i \ge 0$，选右下像素 $(x_i+1, y_i)$，且下一轮判别式更新为 $d_{i+1} = d_i - 2\Delta y$。

2. 【Bresenham 画线算法原理推导】 已知直线起点为 $P_0(x_0, y_0)$，终点为 $P_1(x_1, y_1)$。假定 $x$ 正向是最大位移方向，且斜率满足 $0 < k < 1$。请完成以下推导：

(1) 简述 Bresenham 画线算法通过跟踪误差来逼近理想直线的算法基本思想。(2分)

【参考答案】

• 核心思想：Bresenham 算法通过跟踪和累积理想直线与实际像素网格点之间的偏差量（误差）来决定像素选取。
• 基本思想：
  • 在斜率满足 $0 < k < 1$ 时，$x$ 为最大位移方向。因此 $x$ 每步递增 $1$，而 $y$ 坐标的理论值增加 $k$。
  • 实际像素坐标必须为整数，故下一步绘制像素的纵坐标只能选择保持不变 $y_i$（右侧像素）或递增 $1$ $y_i+1$（右上像素）。
  • 算法在每一步通过计算理想直线当前位置到上方和下方两个候选像素中心点的距离之差，构造一个误差决策变量。当累积误差超过临界值时，像素向 $y$ 正方向递增 $1$ 并减去误差修正值，否则保持不变，以此使绘制的离散折线最逼近理想直线。

(2) 设当前列决策变量为 $d_i$，推导下一列决策变量 $d_{i+1}$ 的误差判别递推公式。(4分)

【参考答案】 设直线的起点为 $(x_0, y_0)$，终点为 $(x_1, y_1)$，直线的斜截式方程为：

$$y = kx + b$$

其中 $k = \frac{\Delta y}{\Delta x}$，$\Delta x = x_1 - x_0$，$\Delta y = y_1 - y_0$。

假设已确定第 $i$ 步的像素位置为 $(x_i, y_i)$，在下一步 $x_{i+1} = x_i + 1$ 处，理想直线上的 $y$ 值为：

$$y = k(x_i + 1) + b$$

理想直线与下方候选像素 $y_i$ 及上方候选像素 $y_i + 1$ 的垂直距离分别为 $d_{\text{down}}$ 和 $d_{\text{up}}$：

• $d_{\text{down}} = y - y_i = k(x_i + 1) + b - y_i$
• $d_{\text{up}} = (y_i + 1) - y = y_i + 1 - [k(x_i + 1) + b]$

构造两者差值作为决策变量 $d_i$：

$$d_i = d_{\text{down}} - d_{\text{up}} = 2k(x_i + 1) + 2b - 2y_i - 1$$

将 $k = \frac{\Delta y}{\Delta x}$ 代入上式得：

$$d_i = 2\frac{\Delta y}{\Delta x}(x_i + 1) + 2b - 2y_i - 1$$

同理，写出下一步（$i+1$ 步）的决策变量 $d_{i+1}$（其中 $x_{i+1} = x_i + 1$）：

$$d_{i+1} = 2\frac{\Delta y}{\Delta x}(x_{i+1} + 1) + 2b - 2y_{i+1} - 1$$

用 $d_{i+1}$ 减去 $d_i$ 进行递推计算：

$$d_{i+1} - d_i = 2\frac{\Delta y}{\Delta x}(x_{i+1} - x_i) - 2(y_{i+1} - y_i) = 2\frac{\Delta y}{\Delta x} - 2(y_{i+1} - y_i)$$

故决策变量的递推公式为：

$$d_{i+1} = d_i + 2\frac{\Delta y}{\Delta x} - 2(y_{i+1} - y_i)$$

(3) 说明如何通过消去分母与常数项，将算法改造为纯整数加减与移位运算，并给出整数型初值 $d_0$、决策更新增量以及下一步像素位置的选择依据。(4分)

【参考答案】

• 1. 消除分母（整数化）： 由于递推公式中含有分数分母 $\Delta x$，为了消除分母，可以对 $d_i$ 同乘以不改变其符号的放大因子 $\Delta x$（因为 $\Delta x > 0$），定义新的整数型决策变量 $D_i = \Delta x \cdot d_i$。 两边同乘 $\Delta x$ 改造递推式：

  $$D_{i+1} = D_i + 2\Delta y - 2\Delta x(y_{i+1} - y_i)$$

• 2. 下一步像素位置的选择依据与增量更新：

  • 若 $D_i < 0$（即理想直线更接近下方像素）：
    • 像素选择：$x_{i+1} = x_i + 1$，$y_{i+1} = y_i$
    • 决策变量更新：$D_{i+1} = D_i + 2\Delta y$
  • 若 $D_i \ge 0$（即理想直线更接近上方像素）：
    • 像素选择：$x_{i+1} = x_i + 1$，$y_{i+1} = y_i + 1$
    • 决策变量更新：$D_{i+1} = D_i + 2\Delta y - 2\Delta x$

• 3. 整数型初值 $D_0$ 的推导： 将起点 $P_0(x_0, y_0)$ 代入初始决策变量 $d_0$ 算式。因为该点在理想直线上满足 $y_0 = kx_0 + b$：

  $$d_0 = 2(kx_0 + b) + 2k - 2y_0 - 1 = 2y_0 + 2k - 2y_0 - 1 = 2k - 1$$

  代入 $k = \frac{\Delta y}{\Delta x}$ 且同乘 $\Delta x$，得到整数型初值 $D_0$：

  $$D_0 = \Delta x \cdot \left(2\frac{\Delta y}{\Delta x} - 1\right) = 2\Delta y - \Delta x$$

  经此改造，公式中只包含 $2\Delta y$ 和 $2\Delta y - 2\Delta x$。由于乘以 2 可以通过左移位运算（<< 1）实现，整个算法内部循环完全转化为纯整数的加减与移位操作，极大地提升了计算机的图形渲染效率。

3. 【直线上栅化计算（1,1 至 5,2）】 已知需要绘制从起点 $P_0(1, 1)$ 到终点 $P_1(5, 2)$ 的直线段。请分别使用中点画线算法和 Bresenham 算法进行光栅化离散点列计算：

(1) 采用中点画线算法（双倍放大形式），写出直线方程系数 $a, b$，计算决策变量初值 $d_0$，列出各步决策变量 $d$ 的值与选点结果坐标。(5分)

【参考答案】

• 直线方程系数计算：
  • $\Delta x = 5 - 1 = 4$，$\Delta y = 2 - 1 = 1$
  • 系数：$a = y_0 - y_1 = -1$，$b = x_1 - x_0 = 4$
• 决策变量初值 $d_0$： $$d_0 = 2a + b = 2(-1) + 4 = 2$$
• 递推计算过程：
  • 第 $0$ 步：$x = 1, y = 1$。因为 $d_0 = 2 \ge 0$，选择右下点 $(2, 1)$。 更新：$d_1 = d_0 + 2a = 2 - 2 = 0$。
  • 第 $1$ 步：$x = 2, y = 1$。因为 $d_1 = 0 \ge 0$，选择右下点 $(3, 1)$。 更新：$d_2 = d_1 + 2a = 0 - 2 = -2$。
  • 第 $2$ 步：$x = 3, y = 1$。因为 $d_2 = -2 < 0$，选择右上点 $(4, 2)$。 更新：$d_3 = d_2 + 2a + 2b = -2 - 2 + 8 = 4$。
  • 第 $3$ 步：$x = 4, y = 2$。因为 $d_3 = 4 \ge 0$，选择右下点 $(5, 2)$。
  • 最终绘制的离散像素点列为：$(1,1), (2,1), (3,1), (4,2), (5,2)$。

(2) 采用 Bresenham 算法（整数优化形式），写出误差决策变量初值 $d'_0$、增量项，并列表计算出各步的 $d$ 值判定与最终绘制的离散像素坐标点列 $(x,y)$。(5分)

【参考答案】

• 决策初值及增量项：

  • $\Delta x = 4$, $\Delta y = 1$
  • 误差初值：$d'_0 = 2\Delta y - \Delta x = 2(1) - 4 = -2$
  • 增量项：
    • 若 $d \ge 0$，更新增量为 $2\Delta y - 2\Delta x = 2 - 8 = -6$；
    • 若 $d < 0$，更新增量为 $2\Delta y = 2$。

• Bresenham 递推计算表：

  步数	绘制像素点$(x, y)$	误差判别项$d$	判定条件	下一步纵坐标更新
  0	$(1, 1)$	$-2$ (初值)	$d < 0$	$y$ 不变 ($y=1$)
  1	$(2, 1)$	$-2 + 2 = 0$	$d \ge 0$	$y$ 增 $1$ ($y=2$)
  2	$(3, 2)$	$0 - 6 = -6$	$d < 0$	$y$ 不变 ($y=2$)
  3	$(4, 2)$	$-6 + 2 = -4$	$d < 0$	$y$ 不变 ($y=2$)
  4	$(5, 2)$	—	已达终点	—

• 最终生成的离散点列为：$(1,1), (2,1), (3,2), (4,2), (5,2)$。

4. 【直线上栅化计算（0,0 至 5,2）】 已知直线起点为 $P_0(0,0)$，终点为 $P_1(5,2)$。请分别使用中点画线算法和 Bresenham 算法进行光栅化离散点列计算：

(1) 采用中点画线算法（双倍放大形式），写出直线方程系数 $a, b$，计算决策变量初值 $d_0$，列出各步决策变量 $d$ 的值与选点结果坐标。(5分)

【参考答案】

• 直线参数计算：
  • $\Delta x = 5$, $\Delta y = 2$
  • 直线系数：$a = y_0 - y_1 = -2$，$b = x_1 - x_0 = 5$
• 中点判别式初值 $d_0$： $$d_0 = \Delta x - 2\Delta y = 5 - 2(2) = 1$$
• 递推更新算式：
  • 当 $d_i \ge 0 \implies$ 下一步选右下点，且 $d_{i+1} = d_i + 2a = d_i - 4$；
  • 当 $d_i < 0 \implies$ 下一步选右上点，且 $d_{i+1} = d_i + 2a + 2b = d_i + 6$。
• 递推计算过程：
  • 第 $0$ 步：$x = 0, y = 0$。因为 $d_0 = 1 \ge 0$，选择右下点 $(1,0)$。 更新：$d_1 = 1 - 4 = -3$。
  • 第 $1$ 步：$x = 1, y = 0$。因为 $d_1 = -3 < 0$，选择右上点 $(2,1)$。 更新：$d_2 = -3 + 6 = 3$。
  • 第 $2$ 步：$x = 2, y = 1$。因为 $d_2 = 3 \ge 0$，选择右下点 $(3,1)$。 更新：$d_3 = 3 - 4 = -1$。
  • 第 $3$ 步：$x = 3, y = 1$。因为 $d_3 = -1 < 0$，选择右上点 $(4,2)$。 更新：$d_4 = -1 + 6 = 5$。
  • 第 $4$ 步：$x = 4, y = 2$。因为 $d_4 = 5 \ge 0$，选择右下点 $(5,2)$。
  • 最终中点画线法的点列为：$(0,0), (1,0), (2,1), (3,1), (4,2), (5,2)$。

(2) 采用 Bresenham 算法（整数优化形式），写出误差项初值 $d'_0$，列出各步的 $d$ 值更新与绘制点坐标 $(x,y)$ 的完整递推计算过程表格。(5分)

【参考答案】

• Bresenham 参量：

  • $\Delta x = 5$, $\Delta y = 2$
  • 误差初值：$d_0 = 2\Delta y - \Delta x = 2(2) - 5 = -1$
  • 决策更新增量：当 $d \ge 0$ 时为 $2\Delta y - 2\Delta x = -6$；当 $d < 0$ 时为 $2\Delta y = 4$。

• Bresenham 递推计算表：

  步数	绘制像素点坐标$(x, y)$	误差项$d$	判定条件	下一步纵坐标更新
  0	$(0, 0)$	$-1$	$d < 0$	$y$ 不变 ($y=0$)
  1	$(1, 0)$	$-1 + 4 = 3$	$d \ge 0$	$y$ 递增 $1$ ($y=1$)
  2	$(2, 1)$	$3 - 6 = -3$	$d < 0$	$y$ 不变 ($y=1$)
  3	$(3, 1)$	$-3 + 4 = 1$	$d \ge 0$	$y$ 递增 $1$ ($y=2$)
  4	$(4, 2)$	$1 - 6 = -5$	$d < 0$	$y$ 不变 ($y=2$)
  5	$(5, 2)$	—	已达终点	—

• 最终离散点列为：$(0,0), (1,0), (2,1), (3,1), (4,2), (5,2)$。

---

知识总结：中点画线法与 Bresenham 画线算法对比#

Bresenham 画线算法和中点画线法是计算机图形学中绘制光栅化直线（以第一象限、斜率 $0 \le k \le 1$ 为主）的两种最经典算法。它们的核心思想都是利用前一步的计算结果进行增量递推，从而避免浮点运算，仅用整数加减和移位完成像素选择。

下面从核心原理、递推公式、初始值以及算法联系等方面进行详细对比。

1. 核心原理与判别式定义#

假设当前已确定像素点为 $P_i(x_i, y_i)$，下一个像素的步进方向必定是 $x_{i+1} = x_i + 1$，而纵坐标 $y$ 方向有两个候选点：$P_1(x_i + 1, y_i)$（不往上走）或 $P_2(x_i + 1, y_i + 1)$（往上走）。

• 中点画线法：计算候选两点的中点 $M(x_i + 1, y_i + 0.5)$。构造直线隐式方程 $F(x, y) = Ax + By + C = 0$。通过中点 $M$ 代入方程后的符号判别式 $d = F(M)$ 来判断理想直线与中点 $M$ 的上下相对位置。
• Bresenham 算法：计算理想直线在 $x_i + 1$ 处的精确 $y$ 值，并计算它与上下两个候选像素中心的垂直距离差值 $d_{\text{down}}$ 和 $d_{\text{up}}$。通过判别式 $p = \Delta x \cdot (d_{\text{down}} - d_{\text{up}})$ 的正负符号来决定像素选取。

2. 核心参数与公式对比表#

以下对比基于理想直线起点 $(x_0, y_0)$，终点 $(x_1, y_1)$，其中 $\Delta x = x_1 - x_0$，$\Delta y = y_1 - y_0$，斜率 $k = \frac{\Delta y}{\Delta x} \in [0, 1]$。

对比维度	中点画线法 (Midpoint)	Bresenham 画线算法
原始方程与距离表示	$F(x,y) = \Delta y \cdot x - \Delta x \cdot y + C = 0$（其中 $A = \Delta y, B = -\Delta x$）	y = k(x - x_0) + y_0$$d_{\text{down}} = y - y_i,\quad d_{\text{up}} = (y_i + 1) - y
整数判别式初值	$d_0 = \Delta x - 2\Delta y$	$p_0 = 2\Delta y - \Delta x$
判别式符号含义	$d < 0$：中点在直线下方 $\rightarrow$ 选上方 P_2$$d \ge 0：中点在直线上方或线上 $\rightarrow$ 选下方 $P_1$	$p \ge 0$：直线更靠近上方像素 $\rightarrow$ 选上方 P_2$$p < 0：直线更靠近下方像素 $\rightarrow$ 选下方 $P_1$
选下方像素 $P_1$ 时的更新递推式	$d_{i+1} = d_i - 2\Delta y$	$p_{i+1} = p_i + 2\Delta y$
选上方像素 $P_2$ 时的更新递推式	$d_{i+1} = d_i + 2(\Delta x - \Delta y)$	$p_{i+1} = p_i + 2(\Delta y - \Delta x)$

3. 初始值推导逻辑说明#

• 中点画线法的 $d_0$： 在第一列测试中点 $M(x_0+1, y_0+0.5)$ 代入隐式方程 $F(x, y) = \Delta y \cdot x - \Delta x \cdot y + C$。由于起点 $(x_0, y_0)$ 在直线上，代入求得连续型判别式初值 $d_{\text{raw}} = \Delta y - 0.5\Delta x$。为完全消除浮点数，将其同乘以 $2$，并配合符号方向对调（中点在下方时 $d < 0$ 对应选右上像素），最终得到标准的整数形式： $$d_0 = \Delta x - 2\Delta y$$
• Bresenham 算法的 $p_0$： 在 $x_0 + 1$ 处精确纵坐标 $y = k + y_0$。理想直线到下方和上方像素中心偏差之差为 $d_{\text{down}} - d_{\text{up}} = 2k - 1$。为消去分母将其乘以 $\Delta x$，得到整数判别式初值： $$p_0 = \Delta x(d_{\text{down}} - d_{\text{up}}) = 2\Delta y - \Delta x$$

4. 算法的本质等价性#

尽管两者的几何直观出发点不同（一个看中点相对于直线的上下位置，一个看直线离像素中心的垂直偏差距离），但它们在数学上是完全等价的。 如果将中点画线法的判别式 $d_i$ 乘以 $-1$（即取反以对齐符号决策规则），则其初始值、步进累加值与 Bresenham 算法的决策变量 $p_i$ 完全一致。两者是同一数学内核在图形学上的两种不同直观解释。在实际开发和底层硬件流水线中，Bresenham 算法的累加表达式由于极度简明，被应用 and 提及得更为广泛。

---

二、 改进的活动边表填充算法#

5. 【改进的活动边表（AET）多边形填充】 已知某多边形的顶点坐标分别为：$A(2, 1)$、$B(6, 1)$、$C(6, 5)$、$D(4, 3)$、$E(2, 5)$、$F(1, 4)$。若采用多边形扫描转换的改进活动边表算法进行填充，且边表与活动边表的结点结构统一规定为：[y_max | x_ymin | 1/k | next]（其中 $y_{\max}$ 为边最大纵坐标，$x_{ymin}$ 为边最小纵坐标处的横坐标，$1/k$ 为边斜率的倒数）。请完成以下设计计算：

(1) 构建该多边形的完整边表（ET 表），标明每个扫描线链表的挂接边及其具体参数。(5分)

【参考答案】

• 各边参数提取分析：
  • $AB$ 边：端点 $(2,1)$ 和 $(6,1)$，水平边，不装入边表 ET。
  • $BC$ 边：端点 $(6,1)$ 和 $(6,5)$，$y_{min}=1, y_{max}=5, x_{ymin}=6, 1/k=0$。
  • $FA$ 边：端点 $(1,4)$ 和 $(2,1)$，$y_{min}=1, y_{max}=4, x_{ymin}=2, 1/k = \frac{1-2}{4-1} = -1/3$。
  • $CD$ 边：端点 $(4,3)$ 和 $(6,5)$，$y_{min}=3, y_{max}=5, x_{ymin}=4, 1/k = \frac{6-4}{5-3} = 1$。
  • $DE$ 边：端点 $(4,3)$ 和 $(2,5)$，$y_{min}=3, y_{max}=5, x_{ymin}=4, 1/k = \frac{2-4}{5-3} = -1$。
  • $EF$ 边：端点 $(1,4)$ 和 $(2,5)$，$y_{min}=4, y_{max}=5, x_{ymin}=1, 1/k = \frac{2-1}{5-4} = 1$。
• 按 $y_{\min}$ 挂接并排序构建 ET 表：
  • $ET[1] \to [4 \mid 2 \mid -1/3] \to [5 \mid 6 \mid 0]$
  • $ET[2] \to \text{null}$
  • $ET[3] \to [5 \mid 4 \mid -1] \to [5 \mid 4 \mid 1]$
  • $ET[4] \to [5 \mid 1 \mid 1]$
  • $ET[5] \to \text{null}$

(2) 写出扫描线从下往上递增到 $y = 3$ 时的活动边表（AET 表）的各个结点参数状态（按 $x$ 值从小到大排序）。(3分)

【参考答案】

• 递推过程：

  • $y=1$ 时：调入 $ET[1]$，AET 为 $[4 \mid 2 \mid -1/3] \to [5 \mid 6 \mid 0]$。

  • $y=2$ 时：更新交点横坐标 $x_{y=2} = x_{y=1} + 1/k$。

    • $FA$ 边：$x = 2 - 1/3 = 5/3 \approx 1.67$；
    • $BC$ 边：$x = 6 + 0 = 6$。 AET 为 $[4 \mid 5/3 \mid -1/3] \to [5 \mid 6 \mid 0]$。

  • $y=3$ 时：

    • 递增更新：$FA$ 边 $x = 5/3 - 1/3 = 4/3 \approx 1.33$；$BC$ 边 $x = 6 + 0 = 6$。
    • 调入 $ET[3]$ 新边：$DE[5 \mid 4 \mid -1]$ 和 $CD[5 \mid 4 \mid 1]$。
    • 合并后按当前 $x$ 值升序重排：$FA$ ($x=4/3$) $\to$ $DE$ ($x=4$) $\to$ $CD$ ($x=4$) $\to$ $BC$ ($x=6$)。

  • $y=3$ 时的 AET 状态为：

    $$AET \to [4 \mid 4/3 \mid -1/3] \to [5 \mid 4 \mid -1] \to [5 \mid 4 \mid 1] \to [5 \mid 6 \mid 0]$$

    （或小数记为：$[4 \mid 1.33 \mid -0.33] \to [5 \mid 4 \mid -1] \to [5 \mid 4 \mid 1] \to [5 \mid 6 \mid 0]$）

(3) 写出扫描线 $y = 3$ 时的有效填充像素区间。(2分)

【参考答案】

• AET表对应 $y=3$ 时的 $x$ 轴四个交点为：$x_1 = 4/3 \approx 1.33$，$x_2 = 4$，$x_3 = 4$，$x_4 = 6$。
• 配对填充段：$[1.33, 4]$ 和 $[4, 6]$。
• 按扫描线像素取整规则（通常为左闭右开原则 $[x_i, x_{i+1})$，即区间右端交点处像素不着色）：
  • 区间一 $[1.33, 4)$ 填充像素横坐标为：$x = 2, 3$。
  • 区间二 $[4, 6)$ 填充像素横坐标为：$x = 4, 5$。
• 综合所得，扫描线 $y=3$ 时的有效填充像素横坐标区间为 $[2, 6)$ 内的整数，即像素横坐标为： $$x = 2, 3, 4, 5$$

---

三、 Liang-Barsky 算法直线裁剪#

6. 【Liang-Barsky 直线段裁剪算法计算】 已知裁剪窗口为一个矩形区域，其边界值分别为：$x_{w\min} = 0$，$x_{w\max} = 2$，$y_{w\min} = 0$，$y_{w\max} = 2$。待裁剪直线段的起点坐标为 $A(1, -1)$，终点坐标为 $B(2, 3)$。请完成以下分析与计算：

(1) 写出 Liang-Barsky 算法的参数化线段表达式，并计算出直线段与四个裁剪边界对应的参数组 $p_k$ 与 $q_k \quad (k=1,2,3,4)$。(4分)

【参考答案】

• 参数化线段表达式：
  • 直线起点 $A(1,-1)$，终点 $B(2,3)$，横纵坐标位移量为：$\Delta x = 2 - 1 = 1$，$\Delta y = 3 - (-1) = 4$。
  • 直线的参数化方程为： $$\begin{cases} x = 1 + u \cdot 1 \\ y = -1 + u \cdot 4 \end{cases} \quad (0 \le u \le 1)$$
• 边界参数组 $p_k$ 与 $q_k$ 的计算（根据公式 $u \cdot p_k \le q_k$）：
  • 左边界 ($k=1$, $x_{w\min}=0$): $$p_1 = -\Delta x = -1, \quad q_1 = x_0 - x_{w\min} = 1 - 0 = 1$$
  • 右边界 ($k=2$, $x_{w\max}=2$): $$p_2 = \Delta x = 1, \quad q_2 = x_{w\max} - x_0 = 2 - 1 = 1$$
  • 下边界 ($k=3$, $y_{w\min}=0$): $$p_3 = -\Delta y = -4, \quad q_3 = y_0 - y_{w\min} = -1 - 0 = -1$$
  • 上边界 ($k=4$, $y_{w\max}=2$): $$p_4 = \Delta y = 4, \quad q_4 = y_{w\max} - y_0 = 2 - (-1) = 3$$

(2) 计算得出入点参数 $u_{\max}$ 与出点参数 $u_{\min}$，写出详细的边界相交类型判定过程。(4分)

【参考答案】

• 判定规则：
  • 若 $p_k < 0$，该边界对应的交点为由外到内的“入点”，用于更新 $u_{\max}$；
  • 若 $p_k > 0$，该边界对应的交点为由内到外的“出点”，用于更新 $u_{\min}$；
  • 若 $p_k = 0$ 且 $q_k < 0$，线段完全在窗口外部平行，直接拒绝。
• 计算各交点参数并分类：
  • 入点组 ($p_k < 0$):
    • 左边界交点 ($k=1$): $u_1 = q_1/p_1 = -1$
    • 下边界交点 ($k=3$): $u_3 = q_3/p_3 = -1/(-4) = 0.25$
    • 入点决策参数： $$u_{\max} = \max(0, u_1, u_3) = \max(0, -1, 0.25) = 0.25$$
  • 出点组 ($p_k > 0$):
    • 右边界交点 ($k=2$): $u_2 = q_2/p_2 = 1$
    • 上边界交点 ($k=4$): $u_4 = q_4/p_4 = 3/4 = 0.75$
    • 出点决策参数： $$u_{\min} = \min(1, u_2, u_4) = \min(1, 1, 0.75) = 0.75$$

(3) 根据 Liang-Barsky 算法的裁剪准则，判定该线段是否被接受，并求出窗口内部裁剪后的端点实际坐标值。(2分)

【参考答案】

• 线段可接受判定：
  • 因为 $u_{\max} = 0.25 \le u_{\min} = 0.75$，所以该线段在窗口内存在可见段，应该接受该线段。
  • 其有效的可见参数段范围为：$u \in [0.25, 0.75]$。
• 裁剪后端点实际坐标计算：

  • 将 $u = u_{\max} = 0.25$ 代入参数方程，求得裁剪后起点 $P_1$：

    $$x_1 = 1 + 0.25 \times 1 = 1.25, \quad y_1 = -1 + 0.25 \times 4 = 0$$

    即 $P_1(1.25, 0)$。

  • 将 $u = u_{\min} = 0.75$ 代入参数方程，求得裁剪后终点 $P_2$：

    $$x_2 = 1 + 0.75 \times 1 = 1.75, \quad y_2 = -1 + 0.75 \times 4 = 2$$

    即 $P_2(1.75, 2)$。

  • 最终裁剪窗口内部的线段端点坐标分别为：$(1.25, 0)$ 和 $(1.75, 2)$。