3. 图元生成算法

线画图元生成算法

• 输出图元 (Output Primitive)
  • 线画图元：矢量表示
  • 填充图元：点阵表示
• 输出图元生成：图像的设备级算法
• 点
  • 随机扫描：电子束定位于指定位置
  • 光栅扫描：根据帧缓冲器设置电子脉冲强度
• 线
  • 随机扫描：按 $x$ 和 $y$ 方向线性增量改变水平和垂直偏转电压
  • 光栅扫描：绘制两端点间的离散点
• 线画图元生成：线段通过像素绘制
• 扫描转换：按光栅扫描显示原理对数学表示的线段离散取样的方法
• 像素网格坐标：对象与像素中心对准，像素点区域坐标在像素点中心
• 屏幕网格坐标：物体边界与像素边界对准，像素点坐标有像素区域左下角整数网格坐标指定

数值差分析算法 DDA

• $y=kx+b$
• $|k|\leq 1$：取 $\Delta x=1$，$y_{i+1}=y_i+k$，坐标取整
• $|k|>1$: 取 $\Delta y=1$，$x_{i+1}=x_i+\frac{1}{k}$
• 优点：加法计算速度快
• 缺点：像素位置需取整
  • 累积误差
  • 取整操作和浮点预算耗时

直线图元生成算法 Bresenham

• $y=mx+b$
  • 屏幕坐标：$x_{k+1}=x_k+1,y_{k+1}=y_k+1$
  • 像素位置 $x_{k+1}$ 处线段的数学点坐标：$y=m(x_k+1)+b$
  • 垂直偏移
    • $d_1=y-y_k=m(x_k+1)+b-y_k$
    • $d_2=y_{k+1}-y=y_{k+1}-m(x_k+1)-b$
  • 距离差：$d_1-d_2=2m(x_k+1)-2y_k+2b-1$
  • $\Delta x(d_1-d_2)=2\Delta yx_k-2\Delta xy_k+c$
• 决策参数：$p_k=\Delta x(d_1-d_2)=2\Delta yx_k-2\Delta xy_k+c$
  • $p_k>0,d_2<d_1$，选择 $(x_{k+1},y_{k+1})$
  • $p_k<0,d_2>d_1$，选择 $(x_{k+1},y_{k})$
• 增量计算：$p_{k+1}=p_k+2\Delta y-2\Delta x(y_{k+1}-y_k)$
• 增量选择
  • $|m|<1$：沿 $x$ 方向
  • $|m|>1$：沿 $y$ 方向
  • 直线生成方向与坐标轴同：坐标增量为正
  • 直线生成方向与坐标轴反：坐标增量为负
  • 水平线和垂直线直接装载

void Bresenham(int x_0, int y_0, int delta_x, int delta_y){
    //|m|<1,直线生成方向与坐标轴同
    int p = 2*delta_y-delta_x;
    int x = x_0, y = y_0;
    Draw(x, y);
    for (int k=1;k<=delta_x;++k){
        x += 1;
        if (p<0){
            p += 2*delta_y;
        } else {
            y += 1;
            p += 2*delta_y-2*delta_x;
        }
        Draw(x,y);
    }
}

曲线图元生成算法

中点圆算法

• $f(x,y)=x^2+y^2-r^2$
  • $y_{k+1}=y_k-1$
  • 平移：圆心 $(x_c,y_c)$
  • 对称：$x=0$ 到 $x=y$ 八分之一
• 决策参数：$p_k=f(x_{k+1},\frac{y_k+y_{k+1}}{2})=f(x_{k+1},y_k-\frac{1}{2})$
  • $p_k>=$：圆周外/上，$y_{k-1}$
  • $p_k<0$：圆周内，$y_k$

void drawCircle(int x_c, int y_c, int r){
    int x = 0, y = r;
    int p =5/4-r;
    while (x>=y){
        x += 1;
        if (p<0) {
            p += 2*x+1;
        } else {
            y -= 1;
            p += 2*x+1-2*y;
        }
        P = getSymmetryPoints(x,y);
        moveToCenter(P, x_c, y_c);
        drawSet(P);
    }
}

椭圆生成算法

• $f(x,y)=r_y^2x^2+r_x^2y^2-r_x^2r_y^2$
• 斜率：$\frac{dy}{dx}=-\frac{2r_y^2x}{2r_x^2y}$
  • 第一象限分为斜率<-1 和>-1 两个区域，分别为区域 1 和区域 2
• $p1=f(x_{k+1},y_k-\frac{1}{2})=r_y^2(x_k+1)^2+r_x^2(y_k-\frac{1}{2})^2-r_x^2r_y^2$
  • $p1<0,y_{k+1}=y_k$
  • $p\geq 0,y_{k+1}=y_k-1$
• $p2=f(x+\frac{1}{2},y_k-1)=r_y^2(x_k+\frac{1}{2})^2+r_x^2(y_k-1)^2-r_x^2r_y^2$
  • $p2>0,x_{k+1}=x_k$
  • $p2\leq0,x_{k+1}=x_k+1$

其它曲线

• 圆锥曲线，三角和指数函数，概率分布，多项式核样条函数
• 直接逼近法
• 直线拟合法
• 中点法
• 利用对称性

线画图元生成的帧缓冲器地址计算

• 单色系统
  • $\text{addr}(x,y)=\text{addr}(0,0)=y(x_{\max}+1)+x$
  • $\text{addr}(x+1,y)=\text{addr}(x,y)+1$
  • $\text{addr}(x+1,y+1)=\text{addr}(x,y)+x_{\max}+2$
• 彩色系统：乘以像素位数 $n$

线画图元生成的并行处理算法

• 将直线分割成多个子段，每个子段用 Bresenham 算法，同时生成线段
  • 子段分割分配：按处理器数目分段；宽度可能不同
  • 扫描线/像素列像素分配：顺序算法可能较慢
  • 区域像素分配

线画图元生成的反走样技术

• 走样：低频取样不充分造成信息失真
• 将直线段看做具有一定长度的矩形，根据与像素的相交区域确定像素亮度级
• 直线段过取样
  • 像素亮度等级 = 像素区域内子像素总数
• 区域取样：像素亮度正比于像素与有限宽线的重迭区域（线宽被覆盖的像素数目）
• 线亮度差矫正
  • 水平和垂直线：最低亮度
  • 45 度线：最高亮度
• 加权区域采样
  • 像素亮度对直线段的贡献程度正比于相交区域与像素中心的距离
• 加权掩膜：指定子像素相对重要性值的数组
• 过滤技术：连续加权曲面或过滤函数覆盖像素
• 硬件反走样（像素位移）：移动像素区域的显示位置

填充图元生成算法

• 顶点表示
  • 扫描填充：求出位于内部的各个像素
  • 扫描线求交：多边形边界转换为像素
  • 区域连通性：多边形内部转换为有效连通区域
• 点阵表示
  • 区域填充：从区域的一个内点出发，将颜色扩展到整个区域
  • 区域连通性：区域内部像素有效连通
  • 内外点测试：起始种子为内点
• 填充格式
  • 颜色边界空心区域
  • 实心区域
  • 图案区域

扫描转换算法

• 顶点表示 -> 点阵表示

• 扫描线与区域边界求交

  • 求交增量：$x_k=x_0+\frac{k}{m}$

  • 整数增量求交

    • $m=\frac{\Delta y}{\Delta x}$
    • 直接舍入取整法

    设定计数器，每移动一条扫描线，计数器增加 $\Delta$，若大于 $\Delta y$ 则得到一个新交点（$x$增加 1，计数器减去 $\Delta$ ）

    • 细化取整法：增加 $2\Delta x$

• 区域边界顶点求交

  • 异侧：顺序连接边的端点 $y$ 值单调，交点数记为 1

    • 顶点分离

    顺/逆时针方向处理多边形边界中的非水平边，对任一条边，检测该边与下一条非水平边共享顶点时是否有单调递增或递减的端点 $y$ 值

    若有，则将较低的一条边缩短一个单位值

  • 同侧：否则交点数记为 2

• 扫描转换填充的数据结构

  • $Y$ 桶：储存每条扫描线
  • 有序边表：按下端点 $y$ 坐标值放入桶中
    • 链表：同类边按 $x$ 递增排列，每个节点包括最大 $y$ 值，下端点 $x$ 值，边斜率倒数
  • 活化边表：记录多边形沿扫描线的交点序列
    • 将有序边表中当前扫描线以下的边加入，删除 $y_{\max}<y_k$ 的边，其它边确定交点
    • 每个节点：最大 $y$ 值，交点坐标 $x$，边斜率倒数

区域填充算法

• 16 连通：马字步
• 像素4连通区域边界只需8连通
• 像素8连通区域必须4连通
• 区域内外点测试
  • 奇偶规则：射线与区域多边形边界交点，奇内偶外
  • 非零环绕数桂策：区域内部点环绕数非零
    • $e=V_B-V_A$, $u$ 为 $P$ 点出发的穿越$AB$的射线向量，$v$ 为垂直与 $u$ 的向量
    • 叉乘法 $u\times e>0$ 环绕数加一
    • 点积法 $v\times e>0$ 环绕数加一
• 边界填充算法：边界以单一颜色指定
  • 递归边界填充：从区域种子点开始，根据连通性检测相邻位置与边界颜色不同的像素，用填充颜色涂色
    • 需要较大的栈空间
    • 内部像素颜色与填充颜色相同会导致递归分支终止
  • 扫描边界填充：填充种子点像素所在扫描行的连续像素段，再将相邻扫描线上起始点入栈
• 泛滥填充算法：区域内部单一颜色填充
  • 递归填充：种子点开始，按像素颜色及连通性，递归检测和扩展内部区域
  • 扫描转换填充：每个水平区间第一个位置开始，按扫描线逐步将区域内扫描线上像素颜色替换为填充颜色

图像填充算法

• 均匀着色区域：像素的颜色由用户指定
  • 扫描填充图元
  • 区域谭崇图元
• 图像填充区域：像素的颜色从图像中获得
  • 位图不透明方式
  • 位图透明方式
  • 像素图填充方式

字符的表示与生成

• 点阵字符：由像素图表示和保存
  • 字型：像素图的尺寸
• 矢量字符：记录字符的笔画信息