计算机图形学【二】

三、基本图形生成算法


基本图形:指基本二维图形元素,包括点、直线、圆、椭圆、多边形域、字符串等。

对于随机扫描显示器和向量绘图仪:将输出指令保存在显示文件中,再由指令把坐标值转换为偏转电压,并在每个刷新周期内,使电子束偏转到相应位置。

对于光栅扫描显示器,图形的输出是输出平面。若把光栅扫描显示平面看作是像素的矩阵,则图形的输出就是在该矩阵上确定一个像素的集合来逼近该图形。具体地,输出时在指定的屏幕位置上控制Z轴辉亮,使该位置上的荧光点发亮。因此,图形的生成主要是研究图形的光栅化,即图形的扫描转换。

为什么找点?注意!后面的虚方格网中,每个方格代表一个像素,方格中心设置坐标得到红色的坐标系。这样每个点对应背后的像素,可看到绿色是覆盖了虚方格网中的方格。

1、直线的扫描转换

(1)微分数值法(DDA)

DDA算法原理:由于直线的一阶导数是连续的,而且对于△x和△y是成比例的,因此,可通过在当前位置(xi,yi)上分别加上小增量εΔx和εΔy(c为无穷小的正数)来求出下一点的坐标(xi+1,yi+1)。

xi+1=xi+εΔx

yi+1=yi+εΔy

通常选择: ε=1/max(|△x|,|△y|) ,这样保证了位移偏移最大为1,像素不会断裂,必定会有点相接或者边相接保证连续。

特点:

  • 增量算法(最大位移方向+1或-1)
  • 直观、易实现
  • x、y、k必须是float,且每一步都必须对x、y进行舍入取整,不利于硬件实现。

(2)中点Bresenham算法

核心思想:在最大位移方向上走一步时,在另一个方向上是否走步取决于误差项的判断。

改进后去除浮点运算增加速度。

为什么乘上2△x后更新的时候还是d+…?因为d 初始就乘上2△x了 后面的d也包含这个意思。具体看证明过程。

0≤K≤1K≥1-1≤K≤0K≤-1
d0=△x-2△yd0=2△x-△yd0=-△x-2△yd0=-2△x-△y
di>0:di+1=di-2△ydi>0:di+1=di+2△x-2△ydi>0:di+1=di-2△y-2△xdi>0:di+1=di-2△x
di<0:di+1=di-2△y+2△xdi<0:di+1=di+2△xdi<0:di+1=di-2△ydi<0:di+1=di-2△x-2△y

全部类型证明

证明过程(0≤k≤1),k其它范围使用同样方法同样可证相应的d:

(3)改进的中点Bresenham算法

1、改为判断d和下一个中点的距离

例如:0≤k≤1,根据DDA算法启发,我们知道x+1时,y+k。

2、令e=d-0.5,消除大小比较改为符号比较。

3、改进摆脱小数、除法运算2e△x来替换e

最终得到0≤k≤1时Bresenham算法改进

2、圆的扫描转换

画圆,画出1/8即可,通过y轴y轴、直线y=x、y=-x的对称变换关系,可以得到其余部分。默认在原点设计即可,实现想要换位置直接在x、y上平移原点即可

  • 笛卡尔方程直接计算:
  • 极坐标直接计算:

上面都是一整个圆,画1/8个圆调整取值域即可。但是上述算法有乘除开根号三角函数,效率低。下面是更高效的算法

(1)圆的DDA算法

使用和差公式:

移项:xi-xi+1=yi·ε,因为移动最大间距为1,所以 yi·ε≤1,ε≤1/yi,因为y最大为R,所以ε≤1/R

同理,xi也最终推出ε≤1/R

ε选取的值越小,计算的点越多,但执行时间越长。为了在光栅系统上得到连续的边界,可选取ε﹦1/R,这样绘制的象素位置大约为一个单位间隔。此算法也被称为DDA圆的生成算法。

此圆的生成算法中仍包含浮点数和乘法运算,影响速度。

(2)圆的Bresenham算法

移项得到隐函数——>带入中点,>0圆内选上<0圆外选下—>算大于0和小于0的递推项,算出初始项。

注意:计算初始值,带入第一个中点,不是原点。

使用d-0.25代替d消除小数:

3、椭圆的扫描转换

椭圆的中点Bresenham算法

椭圆根据对称性,只需要画1/4即可。

第一象限,先是X方向是最大位移方向,之后转换为Y,需要找到分界点。即切线斜率为-1的点。

1.输入椭圆的长半轴a和短半轴b;

2.计算初始值:d=b2+a2 (-b+0.25),x=0,y=b;

3.绘制点(x,y)及其在四分象限上的另外3个对称点;

4.判断d的符号。若d≤0,则先将d更新为d+b2(2x+3),再将(x,y)更新为(x+1,y);否则先将d更新为d+b2(2x+3)+a2(-2y+2),再将(x,y)更新为(x+1,y-1) ;

5.当b2(x+1)<a2(y-0.5)时,重复步骤(3)和(4),否则转(6);

6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值:d=b2(x+0.5)2+a2(y-1)2-a2b2 ;

7.绘制点(x,y)及其在四分象限的另外3个对称点;

8.判断d的符号.若d<=0,则先将d更新为d+b2(2x+2)+a2(-2y+3),再将(x,y)更新为(x+1,y-1);否则先将d更新为d+a2(-2y+3),再将(x,y)更新为(x,y-1);

9.当y>=0时,重复步骤(7)和(8),否则结束。

4、多边形的扫描转换和区域填充

多边形的两种表示方法

  • 顶点表示:用多边形的顶点序列来刻划多边形。
  • 点阵表示:是用位于多边形内的像素的集合来刻划多边形。(占内存)

既然大多数图形应用采用顶点序列表示多边形,而顶点表示又不能直接用于显示,那么就必须有从多边形顶点表示到点阵表示的转换,这种转换就称为扫描转换多边形或多边形的填充。

(1)改进的有效边表算法(y连贯性算法)

(1)初始化:构造边表ET,AET表置空;

(2)将第一个不空的ET表中的边与AET表合并;

(3)由AET表中取出交点对进行填充。

填充时设一布尔变量b(初值为假),令指针从AET中第一个结点到最后一个结点遍历一次,每访问一个结点,把b取反一次,若b为真,则把从当前结点的x值到下一结点的x值结束的区间用多边形色填充。填充之后删除y=ymax的边。

(4) y_(i+1)=y_i+1,根据x_(i+1)=x_i+1/k计算并修改AET表,同时合并ET表中〖y=y〗_(i+1)桶中的边,按次序插入到AET表中,形成新的AET表;

(5)AET表不为空则转(3),否则结束。

(2)区域填充

区域是指已经表示成点阵形式的填充图形,它是像素集合。

区域填充是指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。

区域的表示方法:通常有内点表示和边界表示两种形式。

  • 边界表示法:把位于给定区域的边界上像素一一列举出来的方法。
    • 在边界表示法中,区域边界上的像素着同一颜色,而区域内的像素点不能着这种颜色。
    • 由于边界以特殊颜色指定,填充算法可逐个像素地向外处理,直到遇到边界颜色为止。以此为基础的区域填充算法称为边界填充算法(Boundary-fill Algorithm)
  • 内点表示法:枚举出给定区域内所有像素的表示方法。在内点表示法中,区域内的所有像素点着同一颜色,而区域边界上的像素着不同的颜色。
    • 以内点表示法为基础的区域填充算法称为泛填充算法(Flood-fill Algorithm)

区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它点。

区域通常分为4-连通区域和8-连通区域两类。

扫描转换与区域填充的区别

基本思想不同

  • 多边形扫描转换是指将多边形的顶点表示转化为点阵表示;

    它改变了表示方法。

  • 区域填充只改变区域的填充颜色,不改变区域表示方法。

    它已经是点阵表示了,只是涂色。

基于的条件不同

  • 在区域填充算法中,要求给定区域内一点作为种子点,然后从这一点根据连通性将新的颜色扩散到整个区域;
  • 扫描转换多边形是从多边形的边界(顶点)信息出发,利用多种形式的连贯性进行填充的。

当以边界表示时,4-连通边界填充算法只能填充4-连通区域,8-连通边界填充算法也只能填充8-连通区域。

当以内点表示肘,8连通泛填充算法可以填充8-连通区域也可以填充4-连通区域,当然连通泛填充算法还是只能填充4连通区域。

因为边界表示的算法选择涂色点的条件为,不是边界色且未置为填充色

内点表示时算法选择涂色点的条件为,是给定的内部点的颜色且未置为填充色

(3)反走样

走样:用离散量表示连续量引起的失真,就叫做走样(Aliasing)。

光栅图形的走样现象

  • ①阶梯(锯齿)状边界

  • ②图形细节失真

  • ③狭小图形遗失:动画序列中时隐时现,产生闪烁

反走样方法:

  • 硬件方法:提高分辨率的反走样方法

    • 显示器的水平、竖直分辩率各提高一倍,则显示器的点距减少一倍,帧缓存容量则增加到原来的4倍,而扫描转换同样大小的图元却要花4倍时间。方法简单,但代价非常大。
  • 软件方法

    • 过取样:在高于显示分辨率的较高分辨率下用点取样方法计算,然后对几个像素的属性进行平均得到较低分辨率下的像素属性。

      • 重叠过取样
      • 基于加权模板的过取样
    • 区域采样 :在整个像素区域内进行采样,这种技术称为区域采样。又由于像素的亮度是作为一个整体被确定的,不需要划分子像素,故也被称为前滤波。

      • 简单区域取样
      • 加权区域取样
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~