1000-9825/2002/13(04)0637-06
2002 Journal of Software 软 件 学 报
Vol.13, No.4
自适应多步位移码直线绘制算法
苗兰芳 1,2, 刘新国 1, 彭群生 1, 鲍虎军 1
1 2
(浙江大学 CAD&CG 国家重点实验室,浙江 杭州 (浙江师范大学 计算机科学与工程学院,浙江 金华
310027); 321004)
E-mail: zjmlf@163.net http://www.zju.edu.cn 摘要: 直线绘制是光栅图形学中一个最为基本的任务,加速传统直线绘制算法有着重要的实际意义.提出了一 种新的直线绘制算法.与传统的直线绘制算法不同的是,该算法将直线直接表达成一串由 0 或 1 组成的位移码, 并给出一个直线位移码的快速计算公式;在此基础上,通过对直线位移码周期性的分析,提出了一种新的自适 应多步绘制算法.实验和理论分析表明,该算法能够大大减少生成直线的计算量,提高直线的绘制速度. 关 键 词: 图形系统;扫描转换;位移码;绘制;自适应算法 中图法分类号: TP391 文献标识码: A
直线是图形中最基本的元素之一,直线绘制算法的好坏对图形应用系统的效率和质量有着直接而又重 要的关系.早在图形学诞生时,人们就开始研究基于随机扫描显示器的直线绘制算法.随着光栅扫描显示器的 出现,出现了基于像素的逐点绘制方法[1].最著名的直线绘制方法是 20 世纪 60 年代中期出现的 Bresenham[2] 算法.在 Bresenham 算法中,所有的运算都是整数运算,绘制一个点的运算量是 1 次整数加法运算和 1 次符号 判断.Bresenham 非常适合于硬件实现.为了进一步提高直线的绘制速度,后续的研究工作主要集中在如何 1 次生成位于直线上多个像素点[3~7].二步法[3~5]1 次判断生成两个点,该类算法首先将斜率小于 1 的直线分成两 类,即小于 1/2 和大于 1/2 类.取二进制链码表示直线上当前采样点对前一采样点的位移,1 表示前一采样点在 X 方向和 Y 方向均前进一个单位(像素)步长,0 表示仅在 X 方向前进一个单位步长.对于斜率小于 1/2 的直线, 位移链码中 1 之后必跟着 0,后一步不用判断即可确定,该算法对斜率接近 1/2 的直线效果较好,对趋于平坦的 直线效果不够显著.四步法 [6] 将直线中可能会出现的所有四步行进码(18 种形式)事先作为一个矩阵存起来, 再通过判断所画直线的形式来确定四步行进码,因此,该算法是以增加代码的复杂度和存储容量来提高速度 的.多步法[7] 则提出了一个更加一般的 8,16,…,2n 步算法(N-Step),但是该算法代码复杂度和存储容量更高.双 向算法 [8]则根据直线的对称性,从直线的两端同时生成两个点,从而提高绘制速度.上述多步法的共同特点是: 每一次有效的特征判断都是生成固定数目的像素点.本文提出了一种自适应的多步位移直线算法,该算法首 先将待绘制的直线直接表达成一串由 0,1 组成的位移码,根据该位移码的组成特点,自适应地确定一次生成 的像素数目,从而获得更高的绘制效率,算法也十分简洁. 本文第 1 节给出直线位移码的定义和计算公式.第 2 节介绍一种基于直线位移码的单步绘制算法.第 3 节将进一步讨论直线位移码的一些有用的性质.第 4 节介绍本文提出的自适应的多步快速直线绘制算法.最 后是结论和未来工作.
收稿日期: 2000-07-23; 修改日期: 2001-01-03 基金项目: 国家自然科学基金资助项目(69823003) 作者简介: 苗兰芳(1963-),女,浙江慈溪人,副教授,主要研究领域为计算机图形学,中文信息处理;刘新国(1972-),男,江西 九江人,博士,主要研究领域为计算机图形学,虚拟现实;彭群生(1947-),男,湖南新化人,博士,教授,博士生导师,主要研究领域为真 实感图形,虚拟现实,科学计算可视化,计算机辅助设计;鲍虎军(1966-),男,浙江温州人,博士,教授,博士生导师,主要研究领域为计 算机动画,虚拟现实.
638
Journal of Software
软件学报 2002,13(4)
1
直线位移码
所有的光栅图形输出设备都可以等价地看成是一个二维的像素网格,每一个像素都对应于一个网格点.
绘制直线的任务就是确定位于给定的直线上的像素采样点.由于采样的离散性,这是一个逼近的过程.如图 1 所示,其中的直线 L 除了两个端点之外,直线并不经过像素网格点.一般常取位于直线附近的像素来逼近.例 如,像素 P 来逼近直线 L 与网格的交点 C.下面,我们先简单叙述一下直线的逼近方法.不失一般性,假设直线的 斜率在[0,1]之间. 如 图 1 所 示,直 线 L 的 两 个 端 点 A,B 的 坐 标 分 别 为 ( xa , ya ) , ( xa , ya ) .直 线 和 网 格 线 x = xi = xa + i ( i = 0,1, 2,..., xb xa )的交点的 Y 坐标值为 Y ( xi ) = x a + yb y a ( xi xa ). xb x a

下一页