---
title: 计算机图形学-基本图形生成算法
abbrlink: 10deed37
date: "2025-09-20 12:35:52"
updated: "2025-09-20 13:29:36"
desc: 在光栅设备（如显示器、打印机）上如何生成基本二维图形（点、直线、圆、椭圆、多边形、字符等）？
categories:
    - 计算机图形学
tags:
    - 计算机图形学
    - 图形生成
---

## 第四章 基本图形生成算法

### 4.1 引言

**问题提出**
在光栅设备（如显示器、打印机）上如何生成基本二维图形（点、直线、圆、椭圆、多边形、字符等）？

**图形生成（扫描转换）**
将连续的几何描述转换为离散像素集合，即在数字设备上确定哪些像素最能逼近目标图形。

**关键目标**

- 保持图形逼真度
- 端点和轮廓准确
- 颜色与灰度均匀
- 算法执行效率高
- 支持绘制属性（颜色、线型、线宽等）

---

### 4.2 直线的扫描转换

#### 4.2.1 数值微分法（DDA 算法）

**算法原理**

- 给定起点 $(x_0, y_0)$ 和终点 $(x_1, y_1)$，计算差分 $dx = x_1 - x_0$，$dy = y_1 - y_0$
- 确定步数 $N = \max(|dx|, |dy|)$
- 计算增量 $incX = dx / N$，$incY = dy / N$
- 从 $(x, y) = (x_0, y_0)$ 开始，循环 $N$ 次：
    - 绘制像素点 $(\mathrm{round}(x), \mathrm{round}(y))$
    - $x += incX$，$y += incY$

<canvas id="canvas-dda" width="300" height="150" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvas = document.getElementById('canvas-dda');
  const ctx = canvas.getContext('2d');
  // 暗色背景
  ctx.fillStyle = '#333';
  ctx.fillRect(0, 0, canvas.width, canvas.height);
  // 白色线条
  ctx.fillStyle = 'white';
  function drawLineDDA(x0, y0, x1, y1) {
    let dx = x1 - x0, dy = y1 - y0;
    let steps = Math.max(Math.abs(dx), Math.abs(dy));
    let incX = dx / steps, incY = dy / steps;
    let x = x0, y = y0;
    for (let i = 0; i <= steps; i++) {
      ctx.fillRect(Math.round(x), Math.round(y), 1, 1);
      x += incX;
      y += incY;
    }
  }
  drawLineDDA(10, 10, 200, 100);
});
</script>

```javascript
// DDA 算法实现
function drawLineDDA(x0, y0, x1, y1) {
    // 1. 计算差分 dx 和 dy
    let dx = x1 - x0,
        dy = y1 - y0;
    // 2. 确定步数 steps 为 max(|dx|, |dy|)
    let steps = Math.max(Math.abs(dx), Math.abs(dy));
    // 3. 计算增量 incX = dx / steps, incY = dy / steps
    let incX = dx / steps,
        incY = dy / steps;
    // 4. 从起点开始，循环 steps 次，每次累加增量并绘制像素
    let x = x0,
        y = y0;
    for (let i = 0; i <= steps; i++) {
        ctx.fillRect(Math.round(x), Math.round(y), 1, 1); // 绘制像素点
        x += incX;
        y += incY;
    }
}
// 优点：简单直观，易实现
// 缺点：浮点运算，开销大
```

- 原理
    - 直线方程增量形式：以 $x$ 或 $y$ 为主方向，每步累加微分增量
    - 设起点 $(x_0, y_0)$、终点 $(x_1, y_1)$，$\Delta x = x_1 - x_0$，$\Delta y = y_1 - y_0$
    - 取步数 $N = \max(|\Delta x|, |\Delta y|)$
    - 增量：
      $$ x*{\text{inc}} = \frac{\Delta x}{N},\quad y*{\text{inc}} = \frac{\Delta y}{N} $$
    - 从起点出发，每步 $x += x_{\text{inc}}$，$y += y_{\text{inc}}$，并取整绘点

- 特点
    - 简单直观，易于理解与实现
    - 浮点运算开销大，不利于硬件实现

#### 4.2.2 中点 Bresenham 算法

**算法原理**

- 当 $|dx| \geq |dy|$ 时，以 $x$ 为主增量方向，初始误差 $e = 2 \cdot dy - dx$
- 每步 $x$ 增 1，同时根据误差调整 $y$：
    - 如果 $e > 0$，则 $y$ 增 1，误差 $e += 2 \cdot (dy - dx)$
    - 否则 $y$ 不变，误差 $e += 2 \cdot dy$
- 在每步绘制像素 $(x, y)$

<canvas id="canvas-bresenham" width="300" height="150" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvas2 = document.getElementById('canvas-bresenham');
  const ctx2 = canvas2.getContext('2d');
  // 暗色背景
  ctx2.fillStyle = '#333';
  ctx2.fillRect(0, 0, canvas2.width, canvas2.height);
  // 白色线条
  ctx2.fillStyle = 'white';
  function drawLineBresenham(x0, y0, x1, y1) {
    let dx = Math.abs(x1 - x0), dy = Math.abs(y1 - y0);
    let sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1;
    let err = dx - dy;
    let x = x0, y = y0;
    while (true) {
      ctx2.fillRect(x, y, 1, 1);
      if (x === x1 && y === y1) break;
      let e2 = 2 * err;
      if (e2 > -dy) { err -= dy; x += sx; }
      if (e2 < dx)  { err += dx; y += sy; }
    }
  }
  drawLineBresenham(10, 10, 200, 100);
});
</script>

```javascript
// Bresenham 算法实现
function drawLineBresenham(x0, y0, x1, y1) {
    // 1. 计算 dx 和 dy 的绝对值
    let dx = Math.abs(x1 - x0),
        dy = Math.abs(y1 - y0);
    // 2. 确定方向 sx 和 sy
    let sx = x0 < x1 ? 1 : -1,
        sy = y0 < y1 ? 1 : -1;
    // 3. 初始化误差 err = dx - dy
    let err = dx - dy;
    // 4. 循环绘制像素，根据误差调整 x 和 y
    let x = x0,
        y = y0;
    while (true) {
        ctx.fillRect(x, y, 1, 1); // 绘制像素
        if (x === x1 && y === y1) break;
        let e2 = 2 * err;
        if (e2 > -dy) {
            err -= dy;
            x += sx;
        }
        if (e2 < dx) {
            err += dx;
            y += sy;
        }
    }
}
// 5. 使用整数运算，避免浮点
// 优点：高效，纯整数运算
// 缺点：仅适用于 |dx| >= |dy| 的情况
```

- 原理
    - 利用中点判别思想选择下一个像素，保持整数运算
    - 以斜率 $m = \frac{\Delta y}{\Delta x} \leq 1$ 的情形为例：
        - 判别函数 $d = f(x+1, y+\frac{1}{2}) = \Delta y (x+1) - \Delta x (y+\frac{1}{2})$
        - 初始 $d_0 = \Delta y - \frac{1}{2} \Delta x$
        - 若 $d < 0$，则下一个像素为 $(x+1, y)$，更新 $d += \Delta y$；
          否则为 $(x+1, y+1)$，更新 $d += \Delta y - \Delta x$。

- 特点
    - 纯整数运算，无乘除法
    - 高效，适合硬件

#### 4.2.3 改进 Bresenham 算法

- 在中点算法基础上，进一步将判别式常量化，避免半像素累加
- 令误差项 $e = 2 \Delta y - \Delta x$
- 更新：
    - 若 $e < 0$：$e += 2 \Delta y$；
    - 否则：$y += 1$，$e += 2 (\Delta y - \Delta x)$；
    - 每步 $x += 1$

- 特点
    - 更简洁的整数累加方式
    - 广泛用于图形硬件

<canvas id="canvas-improved-bresenham" width="300" height="150" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvasImp = document.getElementById('canvas-improved-bresenham');
  const ctxImp = canvasImp.getContext('2d');
  // 暗色背景
  ctxImp.fillStyle = '#333';
  ctxImp.fillRect(0, 0, canvasImp.width, canvasImp.height);
  // 白色线条
  ctxImp.fillStyle = 'white';
  function drawLineImprovedBresenham(x0, y0, x1, y1) {
    let dx = Math.abs(x1 - x0), dy = Math.abs(y1 - y0);
    let sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1;
    let e = 2 * dy - dx;
    let x = x0, y = y0;
    for (let i = 0; i <= dx; i++) {
      ctxImp.fillRect(x, y, 1, 1);
      if (e < 0) {
        e += 2 * dy;
      } else {
        y += sy;
        e += 2 * (dy - dx);
      }
      x += sx;
    }
  }
  drawLineImprovedBresenham(10, 10, 200, 100);
});
</script>

```javascript
// 改进 Bresenham 算法实现
function drawLineImprovedBresenham(x0, y0, x1, y1) {
    // 1. 初始化误差 e = 2*dy - dx
    let dx = Math.abs(x1 - x0),
        dy = Math.abs(y1 - y0);
    let sx = x0 < x1 ? 1 : -1,
        sy = y0 < y1 ? 1 : -1;
    let e = 2 * dy - dx;
    // 2. 循环 dx 次，每次 x 增 1
    let x = x0,
        y = y0;
    for (let i = 0; i <= dx; i++) {
        ctx.fillRect(x, y, 1, 1); // 绘制像素
        // 3. 根据 e 判断是否调整 y
        if (e < 0) {
            e += 2 * dy;
        } else {
            y += sy;
            e += 2 * (dy - dx);
        }
        // 4. 更新误差 e
        x += sx;
    }
}
// 优点：更简洁的整数累加，广泛用于硬件
// 缺点：需要处理方向
```

---

### 4.5 多边形扫描转换与区域填充

#### 4.5.1 多边形表示

- **顶点表示（Vertex List）**：存储顶点坐标和边连接顺序，适合几何变换。
- **边界表示（Edge List）**：存储边的端点信息，便于扫描线求交。

#### 4.5.2 X-扫描线填充算法（Basic Scanline Fill）

**算法步骤**：

1. 对多边形各边，根据边的 ymin 和 ymax 构建边表（Edge Table, ET）。
2. 从 ymin 到 ymax 逐行扫描，维护有效边表（Active Edge Table, AET）。
3. 在每条扫描线 y：
    - 将 ET[y] 中所有起始于 y 的边插入 AET，按照当前 x 坐标升序排序。
    - 从 AET 中删除所有 ymax == y 的边。
    - 对 AET 中每条边，根据当前 y 计算交点 x，并更新边的 x 增量（1/m）。
    - 将交点 x 值两两配对，形成填充区间，对区间内像素进行绘制。
4. 更新每条边的 x 交点： x += Δx/Δy。

<canvas id="canvas-scanline" width="400" height="300" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvasSL = document.getElementById('canvas-scanline');
  const ctxSL = canvasSL.getContext('2d');
  // 暗色背景
  ctxSL.fillStyle = '#333';
  ctxSL.fillRect(0, 0, canvasSL.width, canvasSL.height);
  // 白色填充
  ctxSL.fillStyle = 'white';

  // 定义多边形顶点
  const polygon = [{x:50,y:50},{x:300,y:80},{x:350,y:200},{x:100,y:250}];

  // 构建边表
  function buildEdgeTable(poly) {
    const ET = {};
    for (let i = 0; i < poly.length; i++) {
      const p1 = poly[i], p2 = poly[(i+1)%poly.length];
      let ymin = Math.min(p1.y, p2.y), ymax = Math.max(p1.y, p2.y);
      if (ymin === ymax) continue; // 忽略水平边
      let x = (p1.y < p2.y) ? p1.x : p2.x;
      let invSlope = (p2.x - p1.x) / (p2.y - p1.y);
      if (!ET[ymin]) ET[ymin] = [];
      ET[ymin].push({ymax, x, invSlope});
    }
    return ET;
  }

  // 扫描线填充
  function scanlineFill(poly) {
    const ET = buildEdgeTable(poly);
    let AET = [];
    const ymin = Math.min(...poly.map(p=>p.y));
    const ymax = Math.max(...poly.map(p=>p.y));
    for (let y = ymin; y <= ymax; y++) {
      // 插入新边
      if (ET[y]) AET.push(...ET[y]);
      // 删除过期边
      AET = AET.filter(edge => edge.ymax > y);
      // 计算交点并排序
      const intersections = AET.map(edge => {
        return { x: edge.x, invSlope: edge.invSlope, ymax: edge.ymax };
      }).sort((a,b) => a.x - b.x);
      // 填充像素
      for (let i = 0; i < intersections.length; i += 2) {
        const xStart = Math.ceil(intersections[i].x);
        const xEnd = Math.floor(intersections[i+1].x);
        for (let x = xStart; x <= xEnd; x++) {
          ctxSL.fillRect(x, y, 1, 1);
        }
      }
      // 更新 x
      AET.forEach(edge => edge.x += edge.invSlope);
    }
  }

  // 绘制多边形边框（白色）
  ctxSL.strokeStyle = 'white';
  ctxSL.beginPath();
  ctxSL.moveTo(polygon[0].x, polygon[0].y);
  polygon.forEach(p => ctxSL.lineTo(p.x, p.y));
  ctxSL.closePath();
  ctxSL.stroke();

  // 填充多边形
  scanlineFill(polygon);
});
</script>

```javascript
// 扫描线填充算法实现
function scanlineFill(poly) {
    // 1. 构建边表 ET，按 ymin 分桶存储边信息
    const ET = {};
    for (let i = 0; i < poly.length; i++) {
        const p1 = poly[i],
            p2 = poly[(i + 1) % poly.length];
        let ymin = Math.min(p1.y, p2.y),
            ymax = Math.max(p1.y, p2.y);
        if (ymin === ymax) continue;
        let x = p1.y < p2.y ? p1.x : p2.x;
        let invSlope = (p2.x - p1.x) / (p2.y - p1.y);
        if (!ET[ymin]) ET[ymin] = [];
        ET[ymin].push({ ymax, x, invSlope });
    }
    // 2. 初始化有效边表 AET
    let AET = [];
    const ymin = Math.min(...poly.map((p) => p.y));
    const ymax = Math.max(...poly.map((p) => p.y));
    // 3. 对每条扫描线 y：
    for (let y = ymin; y <= ymax; y++) {
        // - 插入新边到 AET
        if (ET[y]) AET.push(...ET[y]);
        // - 删除过期边
        AET = AET.filter((edge) => edge.ymax > y);
        // - 计算交点并排序
        const intersections = AET.map((edge) => ({ x: edge.x })).sort((a, b) => a.x - b.x);
        // - 两两配对填充区间
        for (let i = 0; i < intersections.length; i += 2) {
            const xStart = Math.ceil(intersections[i].x);
            const xEnd = Math.floor(intersections[i + 1].x);
            for (let x = xStart; x <= xEnd; x++) {
                ctx.fillRect(x, y, 1, 1); // 填充像素
            }
        }
        // - 更新边的 x 坐标
        AET.forEach((edge) => (edge.x += edge.invSlope));
    }
}
// 优点：高效，适合复杂多边形
// 缺点：需要预处理边表
```

#### 4.3 圆的扫描转换

**中点 Bresenham 画圆算法原理**

- 初始点 $(x, y) = (0, R)$，初始误差 $d = 1 - R$
- 每步沿 $x$ 增 1，根据误差判断是否减 $y$：
    - 如果 $d < 0$，则 $d += 2x + 3$
    - 否则 $y -= 1$，$d += 2(x - y) + 5$
- 在八分对称的 8 个位置绘制像素

<canvas id="canvas-circle" width="300" height="300" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvas3 = document.getElementById('canvas-circle');
  const ctx3 = canvas3.getContext('2d');
  // 暗色背景
  ctx3.fillStyle = '#333';
  ctx3.fillRect(0, 0, canvas3.width, canvas3.height);
  // 白色线条
  ctx3.fillStyle = 'white';
  function drawCircleMidpoint(R, xc, yc) {
    let x = 0, y = R;
    let d = 1 - R;
    plotCirclePoints(xc, yc, x, y);
    while (x < y) {
      if (d < 0) {
        d += 2*x + 3;
      } else {
        d += 2*(x - y) + 5;
        y--;
      }
      x++;
      plotCirclePoints(xc, yc, x, y);
    }
  }
  function plotCirclePoints(xc, yc, x, y) {
    const pts = [
      [xc + x, yc + y], [xc - x, yc + y],
      [xc + x, yc - y], [xc - x, yc - y],
      [xc + y, yc + x], [xc - y, yc + x],
      [xc + y, yc - x], [xc - y, yc - x]
    ];
    pts.forEach(p => ctx3.fillRect(p[0], p[1], 1, 1));
  }
  drawCircleMidpoint(100, 150, 150);
});
</script>

```javascript
// 中点 Bresenham 画圆算法实现
function drawCircleMidpoint(R, xc, yc) {
    // 1. 初始化 x=0, y=R, d=1-R
    let x = 0,
        y = R;
    let d = 1 - R;
    // 2. 绘制八分对称点
    plotCirclePoints(xc, yc, x, y);
    // 3. 循环直到 x >= y：
    while (x < y) {
        // - 根据 d 判断是否减 y
        if (d < 0) {
            d += 2 * x + 3;
        } else {
            d += 2 * (x - y) + 5;
            y--;
        }
        // - 更新 d
        // - x++
        x++;
        // - 绘制对称点
        plotCirclePoints(xc, yc, x, y);
    }
}
function plotCirclePoints(xc, yc, x, y) {
    const pts = [
        [xc + x, yc + y],
        [xc - x, yc + y],
        [xc + x, yc - y],
        [xc - x, yc - y],
        [xc + y, yc + x],
        [xc - y, yc + x],
        [xc + y, yc - x],
        [xc - y, yc - x],
    ];
    pts.forEach((p) => ctx.fillRect(p[0], p[1], 1, 1));
}
// 优点：纯整数运算，高效
// 缺点：需要对称映射
```

#### 4.3.1 八分对称绘制

- 圆具有八次对称性，只需计算第一象限从 $(R,0)$ 到 $(R/\sqrt2,R/\sqrt2)$ 的像素，其他象限对称映射

#### 4.3.2 简单方程法

- 利用圆的方程 $x^2 + y^2 = R^2$ 或极坐标参数：
  $$ x = R \cos \theta,\quad y = R \sin \theta $$
- 缺点：需调用三角函数或开方，计算量大

#### 4.3.3 中点 Bresenham 画圆

- 判别函数：
  $$ d = f(x+1, y-\frac{1}{2}) = (x+1)^2 + (y-\frac{1}{2})^2 - R^2 $$
- 初始 $d_0 = 1 - R$
- 每步：
    - 若 $d < 0$：选择 $(x+1, y)$，更新 $d += 2x + 3$；
    - 否则：选择 $(x+1, y-1)$，更新 $d += 2(x - y) + 5$；
    - 同时 $x += 1$，视情况 $y -= 1$

- 特点：纯整数累加，效率高

---

### 4.4 椭圆的扫描转换

**算法原理**

- 椭圆标准方程：$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$，具有四象限对称性。
- 使用中点 Bresenham 思想，将绘制分为两个区域：
    1. 区域1（斜率 $|dy/dx| \leq 1$）：以 $x$ 为主增量方向，判别函数
       $d_1 = b^2 (x + 1/2)^2 + a^2 (y - 1)^2 - a^2 b^2$。
        - 若 $d_1 < 0$，仅 $x++$，更新 $d_1 += b^2 (2x + 1)$；
        - 否则 $x++$，$y--$，更新 $d_1 += b^2 (2x + 1) + a^2 (-2y + 1)$。
    2. 区域2（斜率 $|dy/dx| > 1$）：以 $y$ 为主变化方向，判别函数
       $d_2 = b^2 (x + 1)^2 + a^2 (y - 1/2)^2 - a^2 b^2$。
        - 若 $d_2 > 0$，仅 $y--$，更新 $d_2 += a^2 (-2y + 1)$；
        - 否则 $x++$，$y--$，更新 $d_2 += b^2 (2x + 2) + a^2 (-2y + 1)$。
- 在每一步中，基于八象限对称性，绘制点 $(\pm x_c \pm x, \pm y_c \pm y)$。

<canvas id="canvas-ellipse" width="300" height="200" style="border:1px solid #ccc;"></canvas>

<script>
document.addEventListener('DOMContentLoaded', function() {
  const canvas4 = document.getElementById('canvas-ellipse');
  const ctx4 = canvas4.getContext('2d');
  // 暗色背景
  ctx4.fillStyle = '#333';
  ctx4.fillRect(0, 0, canvas4.width, canvas4.height);
  // 白色线条
  ctx4.fillStyle = 'white';

  function drawEllipseMidpoint(a, b, xc, yc) {
    let x = 0, y = b;
    let a2 = a * a, b2 = b * b;
    // 初始判别函数 d1 区域1
    let d1 = b2 - a2 * b + 0.25 * a2;
    let dx = 2 * b2 * x, dy = 2 * a2 * y;

    // 区域1
    while (dx < dy) {
      plotEllipsePoints(xc, yc, x, y);
      if (d1 < 0) {
        x++;
        dx += 2 * b2;
        d1 += dx + b2;
      } else {
        x++; y--;
        dx += 2 * b2; dy -= 2 * a2;
        d1 += dx - dy + b2;
      }
    }

    // 区域2 初始判别函数
    let d2 = b2 * (x + 0.5) * (x + 0.5) + a2 * (y - 1) * (y - 1) - a2 * b2;
    // 区域2
    while (y >= 0) {
      plotEllipsePoints(xc, yc, x, y);
      if (d2 > 0) {
        y--;
        dy -= 2 * a2;
        d2 += a2 - dy;
      } else {
        x++; y--;
        dx += 2 * b2; dy -= 2 * a2;
        d2 += dx - dy + a2;
      }
    }
  }

  function plotEllipsePoints(xc, yc, x, y) {
    const pts = [
      [xc + x, yc + y], [xc - x, yc + y],
      [xc + x, yc - y], [xc - x, yc - y]
    ];
    pts.forEach(p => ctx4.fillRect(p[0], p[1], 1, 1));
  }

  drawEllipseMidpoint(120, 80, 150, 100);
});
</script>

```javascript
// 中点 Bresenham 椭圆算法实现
function drawEllipseMidpoint(a, b, xc, yc) {
    // 1. 初始化 x=0, y=b, 计算 a2, b2
    let x = 0,
        y = b;
    let a2 = a * a,
        b2 = b * b;
    let d1 = b2 - a2 * b + 0.25 * a2;
    let dx = 2 * b2 * x,
        dy = 2 * a2 * y;
    // 2. 区域1：斜率 <=1，以 x 为主
    while (dx < dy) {
        plotEllipsePoints(xc, yc, x, y);
        // - 根据 d1 判断是否减 y
        if (d1 < 0) {
            x++;
            dx += 2 * b2;
            d1 += dx + b2;
        } else {
            x++;
            y--;
            dx += 2 * b2;
            dy -= 2 * a2;
            d1 += dx - dy + b2;
        }
        // - 更新 d1
    }
    // 3. 区域2：斜率 >1，以 y 为主
    let d2 = b2 * (x + 0.5) * (x + 0.5) + a2 * (y - 1) * (y - 1) - a2 * b2;
    while (y >= 0) {
        plotEllipsePoints(xc, yc, x, y);
        // - 根据 d2 判断是否增 x
        if (d2 > 0) {
            y--;
            dy -= 2 * a2;
            d2 += a2 - dy;
        } else {
            x++;
            y--;
            dx += 2 * b2;
            dy -= 2 * a2;
            d2 += dx - dy + a2;
        }
        // - 更新 d2
    }
}
function plotEllipsePoints(xc, yc, x, y) {
    const pts = [
        [xc + x, yc + y],
        [xc - x, yc + y],
        [xc + x, yc - y],
        [xc - x, yc - y],
    ];
    pts.forEach((p) => ctx.fillRect(p[0], p[1], 1, 1));
}
// 4. 绘制四象限对称点
// 优点：整数运算，高效
// 缺点：复杂，需要两个区域
```

---

### 4.5 多边形扫描转换与区域填充

#### 4.5.1 多边形表示

- 顶点表示（Vertex List）：存储顶点坐标和边连接顺序
- 点阵表示（Bitmap）：预先离散化边界，便于直接填充

#### 4.5.2 X-扫描线填充

- 对每条扫描线与多边形各边求交点
- 将交点按 x 坐标排序，成对填充区间
- 需处理顶点共享与交点重合特殊情况

#### 4.5.3 有效边表算法（AET）

- 边表（Edge Table，ET）：按最小 y 值分桶存储所有边
- 有效边表（Active Edge Table，AET）：当前扫描线可见的边，按 x 递增排序
- 算法流程：
    1. 初始化 ET 和空 AET
    2. 对每条扫描线 y：
        - 将 ET 中 y 为起点的边插入 AET
        - 从 AET 中删除扫描线终点已过的边
        - 对 AET 中每条边计算交点 x，并按 x 排序
        - 两两配对填充区间像素
        - 更新每条边的 x 增量（$x += 1/m$）

#### 4.5.4 区域填充算法

- 边界填充（Edge Flag）：遇到边界像素时切换填充状态
- 种子填充（Seed Fill）：从种子点扩展，递归或栈方式，四连通或八连通
- 扫描线种子填充：按行扩展，减少栈深度和重复访问

#### 4.5.5 内外测试规则

- 奇偶规则（Even–Odd Rule）：交点数为奇则内部
- 非零环绕规则（Nonzero Winding Number）：环绕计数非零则内部

---

### 4.6 字符处理

#### 字符编码

- ASCII（英文字符、控制码）
- GB2312/GBK/UTF-8（中文及多语言）

#### 字库类型

- 点阵字库（Bitmap Font）：按像素矩阵存储，简单快速但占用存储
- 矢量字库（Vector Font）：用线段、曲线描述笔画，支持缩放与变换

---

### 4.7 属性处理

#### 线型与线宽

- 线型：用像素模板（如 11110000）控制虚线、点划线
- 线宽：
    - 刷子（Brush）算法：用矩形或圆形刷子覆盖线条
    - 区域填充：对扩展后的多边形边界进行填充

#### 字符属性

- 字体、字号、颜色、对齐方式（左/居中/右对齐）

#### 区域填充属性

- 填充颜色、图案、透明度
- 图案对齐：全局对齐或局部对齐

---

### 4.8 反走样（Anti-Aliasing）

#### 走样现象

- 锯齿、波纹、闪烁、细节丢失

#### 反走样方法

1. 提高分辨率（Superresolution）
2. 超采样（Supersampling）：在高分辨率下采样并平均
3. 区域采样（Area Sampling）：按像素与图形覆盖区域比例加权
4. 过滤器（Filter）方法：应用低通滤波器平滑边缘

---


---

**作者：**xingwangzhe

**本文链接：**[https://xingwangzhe.fun/posts/10deed37/](https://xingwangzhe.fun/posts/10deed37/)

本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。