计算机图形学-基本图形生成算法

发布时间：
更新时间：
🕒 阅读时间：22 min read 👀 阅读量：Loading...

第四章 基本图形生成算法

4.1 引言

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

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

关键目标

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

4.2 直线的扫描转换

4.2.1 数值微分法（DDA 算法）

算法原理

  • 给定起点 (x0,y0)(x_0, y_0) 和终点 (x1,y1)(x_1, y_1)，计算差分 dx=x1−x0dx = x_1 - x_0，dy=y1−y0dy = y_1 - y_0
  • 确定步数 N=max⁡(∣dx∣,∣dy∣)N = \max(|dx|, |dy|)
  • 计算增量 incX=dx/NincX = dx / N，incY=dy/NincY = dy / N
  • 从 (x,y)=(x0,y0)(x, y) = (x_0, y_0) 开始，循环 NN 次：
    • 绘制像素点 (round(x),round(y))(\mathrm{round}(x), \mathrm{round}(y))
    • x+=incXx += incX，y+=incYy += incY

// 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;
  }
}
// 优点：简单直观，易实现
// 缺点：浮点运算，开销大

  • 原理

    • 直线方程增量形式：以 xx 或 yy 为主方向，每步累加微分增量
    • 设起点 (x0,y0)(x_0, y_0)、终点 (x1,y1)(x_1, y_1)，Δx=x1−x0\Delta x = x_1 - x_0，Δy=y1−y0\Delta y = y_1 - y_0
    • 取步数 N=max⁡(∣Δx∣,∣Δy∣)N = \max(|\Delta x|, |\Delta y|)
    • 增量： xinc=ΔxN,yinc=ΔyNx_{\text{inc}} = \frac{\Delta x}{N},\quad y_{\text{inc}} = \frac{\Delta y}{N}
    • 从起点出发，每步 x+=xincx += x_{\text{inc}}，y+=yincy += y_{\text{inc}}，并取整绘点

  • 特点

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

4.2.2 中点 Bresenham 算法

算法原理

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

// 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=ΔyΔx≤1m = \frac{\Delta y}{\Delta x} \leq 1 的情形为例：
      • 判别函数 d=f(x+1,y+12)=Δy(x+1)−Δx(y+12)d = f(x+1, y+\frac{1}{2}) = \Delta y (x+1) - \Delta x (y+\frac{1}{2})
      • 初始 d0=Δy−12Δxd_0 = \Delta y - \frac{1}{2} \Delta x
      • 若 d<0d < 0，则下一个像素为 (x+1,y)(x+1, y)，更新 d+=Δyd += \Delta y； 否则为 (x+1,y+1)(x+1, y+1)，更新 d+=Δy−Δxd += \Delta y - \Delta x。

  • 特点

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

4.2.3 改进 Bresenham 算法

  • 在中点算法基础上，进一步将判别式常量化，避免半像素累加

  • 令误差项 e=2Δy−Δxe = 2 \Delta y - \Delta x

  • 更新：

    • 若 e<0e < 0：e+=2Δye += 2 \Delta y；
    • 否则：y+=1y += 1，e+=2(Δy−Δx)e += 2 (\Delta y - \Delta x)；
    • 每步 x+=1x += 1

  • 特点

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

// 改进 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。

// 扫描线填充算法实现
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)(x, y) = (0, R)，初始误差 d=1−Rd = 1 - R
  • 每步沿 xx 增 1，根据误差判断是否减 yy：
    • 如果 d<0d < 0，则 d+=2x+3d += 2x + 3
    • 否则 y−=1y -= 1，d+=2(x−y)+5d += 2(x - y) + 5
  • 在八分对称的 8 个位置绘制像素

// 中点 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,0) 到 (R/2,R/2)(R/\sqrt2,R/\sqrt2) 的像素，其他象限对称映射

4.3.2 简单方程法

  • 利用圆的方程 x2+y2=R2x^2 + y^2 = R^2 或极坐标参数： x=Rcos⁡θ,y=Rsin⁡θx = R \cos \theta,\quad y = R \sin \theta
  • 缺点：需调用三角函数或开方，计算量大

4.3.3 中点 Bresenham 画圆

  • 判别函数： d=f(x+1,y−12)=(x+1)2+(y−12)2−R2d = f(x+1, y-\frac{1}{2}) = (x+1)^2 + (y-\frac{1}{2})^2 - R^2

  • 初始 d0=1−Rd_0 = 1 - R

  • 每步：

    • 若 d<0d < 0：选择 (x+1,y)(x+1, y)，更新 d+=2x+3d += 2x + 3；
    • 否则：选择 (x+1,y−1)(x+1, y-1)，更新 d+=2(x−y)+5d += 2(x - y) + 5；
    • 同时 x+=1x += 1，视情况 y−=1y -= 1

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

4.4 椭圆的扫描转换

算法原理

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

// 中点 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/mx += 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

本文采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

留言评论
2000年1月1日星期六
00:00:00

文章目录

本文分类

计算机图形学 (4)

文章标签

计算机图形学 (4) 图形生成 (1)