7.1 DDA 与 Bresenham
站内的 后处理 讲的是后处理链的 API 与性能：全屏 pass 怎么排、带宽怎么省、何时该用 compute。本节落在它上游很远的地方——线段的整数判定与误差界证明。三角形覆盖有边函数这一把统一的尺子（第 6 章），线段没有：两个端点之间要落哪一组像素，是一个必须逐算法说清楚的离散决策。
问题：哪一组像素「看起来是直线」
给定整数端点 (x0, y0) 与 (x1, y1)，要求输出一串像素。三条约束立刻就能写出来：
- 端点精确：第一个像素就是起点所在像素，最后一个就是终点所在像素。
- 8-邻接连通：相邻两个像素在横竖斜八个方向之一相邻，中间不许断开。
- 主轴单值：沿较长的那根轴，每个坐标值恰好对应一个像素。
第三条决定了像素总数：max(|dx|, |dy|) + 1。剩下的自由度只有「另一根轴上取哪个值」，而这正是 DDA 与 Bresenham 的分歧所在。
八分圆归一化：把方向折成一个八分之一
平面上的有向线段有八个方向类别（八分圆）。归一化把任意方向折进第一个八分圆，只留三个比特：sx、sy（两根轴的正负）与 swap（主轴是不是 y）。归一化之后 major >= minor >= 0，代码里只剩一种循环。
这一步是纯整数：abs、比较、取反，没有三角函数，也没有开方。
两种取整：floor 与半像素偏置
定点 DDA 把 minor 坐标做成累加器：步长 step = fdiv(minor<<16, major<<16) 是 Q16.16 的 minor/major，第 i 步的累加值是 acc = i * step。取整方式决定一切：
(acc + 0) >> 16是 floor。它把每个像素都往下压，误差恒为负，最坏接近 1 个像素；更要命的是终点会漏——累加值的截断误差累积到最后一步，major步之后累计亏损可能刚好让最后一格掉下去。(acc + 32768) >> 16是半像素上偏置，即「四舍五入到最近像素中心」。实测 10 条线段里它每次都精确落在终点，而 floor 版有 6 条少走一格。
注意 step 本身是用 fdiv 向零截断得到的（BRIEF §3.3：定点除法禁用裸 / 与 //），所以累加值比真值 i*minor*65536/major 每步最多低 1 个 Q16 单位。这个偏差小到 0.001 像素以下，却在平局点上决定了往哪边倒——后面会看到它恰恰救了 Bresenham 的一致性。
Bresenham：把判定写成整数
Bresenham 换了个思路：不累加浮点，只维护一个整数判定量 d = 2*minor - major，每步要么 d += 2*minor（不动），要么 k += 1; d += 2*(minor - major)（进一格）。乘 2 是为了把「半步」变成整数比较。
d > 0 才进格，意味着平局（d == 0）时不动——平局被推向下方的像素。这个选择与半像素上偏置的 DDA 恰好相反，所以两者在平局处可能分叉。
实测：分歧只出现在平局且步长无截断处
穷举 major in [1,63]、minor in [0,major] 共 2079 组：
- Bresenham vs floor DDA：1922 组分歧。floor 的误差界就不是 1/2 像素，分歧是常态。
- Bresenham vs 半像素 DDA：129 组分歧，且这 129 组恰好等于「存在平局（651 组）且步长无截断（
major | minor*2^16）」的交集。脚本里这条等式是硬断言。
为什么步长无截断才分叉？因为只要 fdiv 的截断亏损非零，累加值就永远差一点点够不到平局，于是被 floor 压到下方——与 Bresenham 的 d > 0 同向。只有当步长精确（major 整除 minor*2^16）时，累加值才会精确命中平局，此时半像素偏置往上、Bresenham 往下，两边才分开。
还有一个容易被忽略的事实：固定平局方向的 Bresenham 不是端点交换对称的。把 (x0,y0) 与 (x1,y1) 对调，sx、sy 同时翻转，平局方向在归一化坐标系里被镜像——10 条线段里有 1 条（6 个像素）因此分叉。想要严格对称，平局规则必须定义在与方向无关的量上（这正是第 13 章 top-left rule 要处理的）。
可跑的 S 层
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_07_1_line.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_07_1_line.py
"""7.1 DDA 与 Bresenham：八分圆归一化、两种取整语义、像素集合一致性。
八分圆归一化把任意方向折到 major >= minor >= 0，只留 3 位符号/交换信息；
DDA 用 Q16.16 增量 + 算术右移取整（bias=0 是 floor，bias=32768 是半像素上偏置）；
Bresenham 只用整数加减与一次符号判定 d = 2*minor - major（flip=True 是符号反了的负例）。
穷举 major in [1,63]、minor in [0,major] 共 2079 组比对三者，并断言连通/主轴单值/计数/去重。
产物：out/cg_raster_07_1_mask.bin/.png、out/cg_raster_07_1_line.json。
"""
import hashlib
import json
import os
import sys
import numpy as np
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
W, H = 48, 32
SEGMENTS = [(2, 3, 44, 3), (2, 6, 44, 20), (2, 20, 44, 6), (2, 29, 44, 2), (4, 2, 20, 29),
(24, 2, 4, 29), (40, 28, 6, 4), (46, 16, 10, 16), (30, 2, 30, 29), (8, 16, 40, 16)]
def octant(x0, y0, x1, y1):
"""八分圆归一化：返回 (sx, sy, swap, major, minor)，major >= minor >= 0。"""
dx, dy = x1 - x0, y1 - y0
sx = 1 if dx >= 0 else -1
sy = 1 if dy >= 0 else -1
ax, ay = abs(dx), abs(dy)
return (sx, sy, True, ay, ax) if ay > ax else (sx, sy, False, ax, ay)
def _emit(x0, y0, sx, sy, swap, i, k):
"""第 i 步、minor 偏移 k 时的像素：swap 时主轴是 y，否则是 x。"""
return (x0 + k * sx, y0 + i * sy) if swap else (x0 + i * sx, y0 + k * sy)
def dda(x0, y0, x1, y1, bias):
"""定点 DDA：step = fdiv(minor<<16, major<<16)，累加后 (acc + bias) >> 16 取整。"""
sx, sy, swap, major, minor = octant(x0, y0, x1, y1)
if major == 0:
return [(x0, y0)]
step = cglib.fdiv(minor << 16, major << 16) # Q16.16 的 minor/major，向零截断
out, acc = [], 0
for i in range(major + 1):
out.append(_emit(x0, y0, sx, sy, swap, i, (acc + bias) >> 16))
acc += step
return out
def bresenham(x0, y0, x1, y1, flip=False):
"""整数 Bresenham：d > 0 时 minor 坐标 +1（平局不动）；flip=True 即判定符号反了。"""
sx, sy, swap, major, minor = octant(x0, y0, x1, y1)
if major == 0:
return [(x0, y0)]
d, k, out = 2 * minor - major, 0, []
for i in range(major + 1):
out.append(_emit(x0, y0, sx, sy, swap, i, k))
if (d < 0) if flip else (d > 0):
k += 1
d += 2 * (minor - major)
else:
d += 2 * minor
return out
def check(px, x0, y0, x1, y1):
"""连通、主轴单值、计数、去重四条不变量。"""
sx, sy, swap, major, minor = octant(x0, y0, x1, y1)
assert len(px) == major + 1, "像素数必须等于 max(|dx|,|dy|) + 1"
assert len(set(px)) == len(px), "同一像素不得重复落笔"
assert len({p[1 if swap else 0] for p in px}) == major + 1, "主轴坐标必须严格单值递增"
for a, b in zip(px, px[1:]):
assert abs(a[0] - b[0]) <= 1 and abs(a[1] - b[1]) <= 1, "必须 8-邻接连通"
def render(segs, fn):
"""把线段集合画进 W x H 的覆盖掩码（每像素 1 字节，0/1）。"""
mask = bytearray(W * H)
for x0, y0, x1, y1 in segs:
for px, py in fn(x0, y0, x1, y1):
if 0 <= px < W and 0 <= py < H:
mask[py * W + px] = 1
return mask
def main():
pairs = diff_floor = diff_round = ties = tie_exact = 0
for major in range(1, 64):
for minor in range(0, major + 1):
pairs += 1
b = bresenham(0, 0, major, minor)
diff_floor += b != dda(0, 0, major, minor, 0)
diff_round += b != dda(0, 0, major, minor, 32768)
# 平局：某一步 i*minor/major 的小数部分恰为 1/2
if any((2 * i * minor) % (2 * major) == major for i in range(1, major + 1)):
ties += 1
# 步长无截断（major 整除 minor*2^16）时累加值精确命中平局 -> 分歧
tie_exact += (minor * 65536) % major == 0
assert diff_round == tie_exact, "分歧组数必须恰等于「平局且步长无截断」的组数"
floor_miss = asym_b = asym_r = asym_px = 0
for x0, y0, x1, y1 in SEGMENTS:
for px in (bresenham(x0, y0, x1, y1), dda(x0, y0, x1, y1, 0), dda(x0, y0, x1, y1, 32768)):
check(px, x0, y0, x1, y1)
assert bresenham(x0, y0, x1, y1)[-1] == (x1, y1), "Bresenham 必须精确落在终点"
assert dda(x0, y0, x1, y1, 32768)[-1] == (x1, y1), "半像素偏置的 DDA 必须精确落在终点"
floor_miss += dda(x0, y0, x1, y1, 0)[-1] != (x1, y1)
back = bresenham(x1, y1, x0, y0)[::-1]
if back != bresenham(x0, y0, x1, y1):
asym_b += 1
asym_px += len(set(bresenham(x0, y0, x1, y1)) ^ set(back))
asym_r += dda(x1, y1, x0, y0, 32768)[::-1] != dda(x0, y0, x1, y1, 32768)
mask = render(SEGMENTS, bresenham)
flip = render(SEGMENTS, lambda a, b, c, d: bresenham(a, b, c, d, True))
floor = render(SEGMENTS, lambda a, b, c, d: dda(a, b, c, d, 0))
digest = hashlib.sha256(bytes(mask)).hexdigest()
out = os.path.join(ROOT, "out")
with open(os.path.join(out, "cg_raster_07_1_mask.bin"), "wb") as fh:
fh.write(bytes(mask))
color = np.zeros((H, W, 3), dtype=np.int64)
color[:, :] = (16, 16, 20)
color[np.frombuffer(bytes(mask), dtype=np.uint8).reshape(H, W) == 1] = (232, 232, 240)
png = cglib.save_png(os.path.join(out, "cg_raster_07_1_mask.png"), color)
with open(os.path.join(out, "cg_raster_07_1_line.json"), "w", encoding="utf-8") as fh:
json.dump({"canvas": [W, H], "segments": [list(s) for s in SEGMENTS], "sweep_pairs": pairs,
"diff_bresenham_vs_dda_floor": diff_floor, "diff_bresenham_vs_dda_round": diff_round,
"tie_pairs": ties, "tie_with_exact_step": tie_exact, "covered_pixels": sum(mask),
"mask_sha256": digest, "floor_dda_endpoint_miss": floor_miss,
"asym_bresenham": asym_b, "asym_dda_round": asym_r, "asym_pixels": asym_px,
"flip_diff_pixels": sum(a != b for a, b in zip(mask, flip)),
"floor_diff_pixels": sum(a != b for a, b in zip(mask, floor)),
"png_bytes": png}, fh, ensure_ascii=False, indent=2)
print(f"canvas : {W}x{H}，{len(SEGMENTS)} 条线段，覆盖 {sum(mask)} 像素")
print(f"穷举对照 : {pairs} 组 (major in [1,63], minor in [0,major])")
print(f" Bresenham vs DDA(floor) 分歧 {diff_floor} 组")
print(f" Bresenham vs DDA(+32768) 分歧 {diff_round} 组")
print(f" 平局组 {ties}，其中步长无截断（major | minor*2^16）的 {tie_exact} 组 == 分歧组数")
print(f"不变量 : 连通/主轴单值/计数/去重 —— {len(SEGMENTS)}x3 条全部通过")
print(f"端点 : Bresenham 与 DDA(+32768) 精确落点；floor DDA 有 {floor_miss}/{len(SEGMENTS)} 条少走一格")
print(f"交换端点对称 : Bresenham 破例 {asym_b}/{len(SEGMENTS)} 条（共 {asym_px} 像素），"
f"DDA(+32768) 破例 {asym_r}/{len(SEGMENTS)} 条")
print(f"覆盖掩码 : {sum(mask)} 像素 sha256={digest}")
print(f"负例(判定反转) : 与金标准差 {sum(a != b for a, b in zip(mask, flip))} 像素")
print(f"对照(floor DDA) : 与金标准差 {sum(a != b for a, b in zip(mask, floor))} 像素")
print(f"产物 : mask.bin / mask.png {png} bytes")
if __name__ == "__main__":
main()
P 层定点直线内核（与 Python 侧的 octant / dda / bresenham 逐字对齐，判定符号可反转以构造负例）：
// file: lantern/core/src/lantern/cg_raster_07_line.ts
// tier: P
// verify: node --test 'core/test/cg_raster_07_1_line.test.ts'
// 7.1 的定点直线内核：与 Python 侧 sim/cg_raster_07_1_line.py 的 octant/dda/bresenham 逐字对齐。
// DDA 的累加值用 BigInt（与 Python 的 int 语义一致，不溢出）；取整一律用算术右移 `>> 16n`。
// 定点除法用 fixed.ts 的 fdiv（向零截断），禁用裸 `/` 与 `//`。
import { fdiv } from "./fixed.ts";
export type XY = [number, number];
export type Seg = [number, number, number, number];
export type Octant = { sx: number; sy: number; swap: boolean; major: number; minor: number };
/** 八分圆归一化：把任意方向折到 major >= minor >= 0，只留 3 位符号/交换信息。 */
export function octant(x0: number, y0: number, x1: number, y1: number): Octant {
const dx = x1 - x0;
const dy = y1 - y0;
const ax = Math.abs(dx);
const ay = Math.abs(dy);
const sx = dx >= 0 ? 1 : -1;
const sy = dy >= 0 ? 1 : -1;
return ay > ax
? { sx, sy, swap: true, major: ay, minor: ax }
: { sx, sy, swap: false, major: ax, minor: ay };
}
const emit = (x0: number, y0: number, o: Octant, i: number, k: number): XY =>
o.swap ? [x0 + k * o.sx, y0 + i * o.sy] : [x0 + i * o.sx, y0 + k * o.sy];
/** 定点 DDA：step = fdiv(minor<<16, major<<16)，累加后 (acc + bias) >> 16 取整。 */
export function ddaLine(x0: number, y0: number, x1: number, y1: number, bias: number): XY[] {
const o = octant(x0, y0, x1, y1);
if (o.major === 0) return [[x0, y0]];
const step = fdiv(BigInt(o.minor) << 16n, BigInt(o.major) << 16n);
const out: XY[] = [];
let acc = 0n;
for (let i = 0; i <= o.major; i += 1) {
out.push(emit(x0, y0, o, i, Number((acc + BigInt(bias)) >> 16n)));
acc += step;
}
return out;
}
/** 整数 Bresenham：d > 0 时 minor 坐标 +1（平局不动）；flip 是判定符号反了的负例。 */
export function bresenhamLine(x0: number, y0: number, x1: number, y1: number, flip = false): XY[] {
const o = octant(x0, y0, x1, y1);
if (o.major === 0) return [[x0, y0]];
let d = 2 * o.minor - o.major;
let k = 0;
const out: XY[] = [];
for (let i = 0; i <= o.major; i += 1) {
out.push(emit(x0, y0, o, i, k));
if (flip ? d < 0 : d > 0) {
k += 1;
d += 2 * (o.minor - o.major);
} else {
d += 2 * o.minor;
}
}
return out;
}
/** 把一批线段画进 w*h 的覆盖掩码（每像素 1 字节，0/1）。 */
export function plotMask(
segs: Seg[], w: number, h: number, fn: (a: number, b: number, c: number, d: number) => XY[],
): Uint8Array {
const mask = new Uint8Array(w * h);
for (const [x0, y0, x1, y1] of segs) {
for (const [px, py] of fn(x0, y0, x1, y1)) {
if (px >= 0 && px < w && py >= 0 && py < h) mask[py * w + px] = 1;
}
}
return mask;
}
真跑（S 层 + P 层）：
# snippet: 复现命令（在 lantern 工作区根执行）
cd $HOME/.cgbook/lantern
/opt/homebrew/bin/python3 sim/cg_raster_07_1_line.py
node --test 'core/test/cg_raster_07_1_line.test.ts'
S 侧输出：
canvas : 48x32，10 条线段，覆盖 291 像素
穷举对照 : 2079 组 (major in [1,63], minor in [0,major])
Bresenham vs DDA(floor) 分歧 1922 组
Bresenham vs DDA(+32768) 分歧 129 组
平局组 651，其中步长无截断（major | minor*2^16）的 129 组 == 分歧组数
不变量 : 连通/主轴单值/计数/去重 —— 10x3 条全部通过
端点 : Bresenham 与 DDA(+32768) 精确落点；floor DDA 有 6/10 条少走一格
交换端点对称 : Bresenham 破例 1/10 条（共 6 像素），DDA(+32768) 破例 1/10 条
覆盖掩码 : 291 像素 sha256=6755ffc1f109ab31ef63d2d102cb20c4cd6494d0ea232142727de6620f6648c4
负例(判定反转) : 与金标准差 450 像素
对照(floor DDA) : 与金标准差 184 像素
产物 : mask.bin / mask.png 428 bytes
覆盖掩码是 48×32 的逐像素字节缓冲，sha256 = 6755ffc1…f6648c4 就是 P 层的金标准：TypeScript 侧用 BigInt 重写同一套 octant / ddaLine / bresenhamLine，把同一批线段画进同尺寸缓冲，node --test 断言两个 sha256 相等。判定符号反转的负例差 450 像素、floor DDA 差 184 像素——同一个判据必须同时拒绝这两个。
阅读导航：上一节：6.3 深度插值与 z-buffer · 下一节：7.2 直线光栅化的误差界 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。