《基于直线特性的直线生成集成算法》由会员分享，可在线阅读，更多相关《基于直线特性的直线生成集成算法（4页珍藏版）》请在金锄头文库上搜索。
1、第6卷(A版) 第4期 2001年4月中国图象图形学报 Journal of I mage and GraphicsVol . 6(A ),No. 4 Apr. 2001基金项目: 863?C I M S主题资助项目(8632511298422006)收稿日期: 2000203202;改回日期: 2000206201基于直线特性的直线生成集成算法程 锦 陆国栋 谭建荣(浙江大学CAD若直线的斜率接近于0,则一 次循环生成两个点的概率几乎为零.显然,出现直线 斜率接近1?2的机会远比出现8个特殊方向的机会小,因而实际上,用这种方法来绘制8个特殊方向的 直线时,由于只出现一个基码,而没有另一个单独
2、出 现的基码,因此生成直线所需的循环次数与Bresen2ham算法完全相同.图11. 2 集成算法描述 现有的各种直线生成算法,很少考虑直线的方向性,即对水平方向、 垂直方向、45 方向、- 45 方向 这8种特殊方向的直线均采用与一般位置直线相同的绘制方法. Bresenham算法及文献2、3所描述 的两种改进算法,在绘制8个特殊方向的直线时,每循环一次,都要进行一次更新决策参数e所需的整数加减法运算和判断e符号所需的判断操作.实际上,绘制8个方向的特殊直线时,只需判断一次直线方向,即可循环多次,直至生成整条直线, 而不必根据决策参数e的符号来判断下一次循环的走向,从而可以省去每次循环中更新
3、e所需的整数 加减运算和判断e符号所需的判断操作,并能使得生成这8种特殊方向直线的速度大大提高. 以直线位于图1所示区域的情况为例进行说明,其他区域的直线可以由区域对称性获得.在初始化变量后,先判断所要绘制的直线方向是否为特殊 方向,并作相应的处理.若直线方向为特殊方向,则利用特殊直线的方向性,一次性生成整条直线,即, 若dy= 0(直线为0方向),则进行dx次循环,每循环一次使x增1,y不变;若dx= dy(直线为1方向),则进行dx次循环,每循环一次使x和y都增1,即可生成整条直线(dx、dy分别表示直线两端点的水平和垂直差值).若直线不属于特殊方向,则采用将文献2、3两种方法集成的算法进
4、行绘制,这样,由于在绘制一般位置直线时,直线的生成是由两 端向中间进行的,且直线一端通过单独出现的方向走到下一点时,下一个点的方向也是已知的(必定是另一个方向),因此,集成算法一次循环最多可能生 成4个点.以下为集成算法具体描述:算法开始:x1= xstart; y1= ystart; x2= xend; y2= yend; flag= 0;求dx, dy及每走一步的增量sx, sy;if dy dx then交换dx与dy, flag= 1; if dy= = 0 then? ? 绘制水平直线或垂直线 for i= 1 to dx plot(x1, y1);根据flag值更新x1或y1; i
5、f dy= = dx then? ? 绘制斜率为1的直线 for i= 1 to dx plot(x1, y1);更新x1和y1; dx2= 2dx; dy2= 2dy; e= dy2- dx;dyx1= dy2- dx2; dyx2= dyx1+ dy2;393第4期程 锦等:基于直线特性的直线生成集成算法if dx dy2then for i= 1 to(dx- dy+ 1)?2根据flag更新x1, x2或y1, y2;if e 0, dy= 0)算法名称Bresenham 算法对称算法基于链码 理论的算法集成算法更新e所用 加减运算dx(dx+ 1)?2; dx+ 1为偶数(dx+ 3
6、)?2; dx+ 1为奇数dx0对e符号 判断操作dx(dx+ 1)?2; dx+ 1为偶数(dx+ 3)?2; dx+ 1为奇数dx0x坐标运算 总次数dxdx+ 1dxdxy坐标运算 总次数0000表2 几种不同算法运算量比较(直线为1方向, dx= dy 0)算法名称Bresenham 算法对称算法基于链码 理论的算法集成算法更新e所用 加减运算dx(dx+ 1)?2; dx+ 1为偶数 (dx+ 3)?2; dx+ 1为奇数dx0对e符号 判断操作dx(dx+ 1)?2; dx+ 1为偶数 (dx+ 3)?2; dx+ 1为奇数dx0x坐标运算 总次数dxdx+ 1dxdxy坐标运算
7、总次数dydy+ 1dydy由表1和表2可以看出,用集成算法绘制8种 特殊方向的直线,可以使更新e所需的加减运算次 数和判断符号e所需的判断操作次数为零.至于使x坐标和y坐标变化所需的加减法运算,则对每种 算法都是相同的. 另外,由于一般位置直线必然会出现两个相邻 的基元方向,且其中必定有一个方向是单独出现的, 因此,集成算法在绘制一般位置直线过程中,一定会 出现一次循环生成4个点的情况(一般情况下每一 次循环可生成两个点).可见,用集成算法绘制一般 位置直线可获得比对称算法更快的速度. 综上所述可见,集成算法不仅能提高绘制任意 方向(尤其是特殊方向)直线的速度,而且,整幅图形 中特殊方向直线
8、所占比例越大、 所需绘制的直线越长、 生成直线所需的循环次数越多,其节省的运算量 就越大,也越能体现算法的优越性.由于工程图样的 图线绝大部分为特殊方向直线,据统计,其比例超过90,因此,将集成算法应用在工程图样中必将极大 地加快直线绘制的速度.2 实验结果分析与比较表3给出了分别用Bresenham算法、 对称算法、 基于链码理论算法及集成算法绘制5 000根随机直线 所用的时间(其中,水平线、 垂直线、45 方向、- 45 方 向直线及一般位置直线各1 000根,其中特殊方向直表3 几种不同算法绘制时间比较算法名称Bresenham 算法对称算法基于链码 理论算法集成算法画线所用时间(m
9、s)490330440244与Bresenham算法 相比效率提高(% )32. 6510. 2050. 20(CPU: PENT I UM2S 133MHz)493中国图象图形学报第6卷(A版)线占80% ).由于各种算法绘制相同直线时所生成 的点数相同,所以表3中记录的时间未包括画点时 间,以便能更清楚地比较各种算法画线相对速度. 由表3可以看出,与Bresenham算法、 对称算 法、 基于链码理论算法相比,集成算法明显提高了直线的生成速度.3 结 论由于现有的图形学及CAD算法在追求处理对象的完备性与普适性的同时,必须充分考虑处理对 象的特殊性与整体性,因此本文即在完备普适的Brese
10、nham算法基础上,融直线的对称性、 方向性与 连续性为一体,提出了直线生成的集成算法.实验结 果也说明,集成算法离直线生成计算量最小的极限更近了,而且直线生成集成算法作为CAD和CG领 域的基本算法若能实施商品化的固化,将有助于CAD系统图形生成速度的进一步提高. 鉴于工程图样中的直线绝大部分为水平线、 垂 直线和斜率为1的直线,因此本文提出的集成算法将极大地加速工程图样中直线段的绘制.由此可 见,针对工程图样的特点进行相关算法的特殊处理, 是面向工程图样对现有图形学与CAD算法进行改 进的有效途径.参 考 文 献1 Bresenham J E.A lgorithm s for comput
11、er control of a digitalplotter.I BM system s Journal, 1965, 4(1): 2530.2 唐荣锡,汪嘉业,彭群生等编著.计算机图形学教程.北京:科学出版社, 1990.3 金廷赞著.计算机图形学.杭州:浙江大学出版社, 1988.4 刘勇奎.一个对称的快速直线生成算法.微计算机应用, 1993,14(2): 4251.5 刘勇奎.一个基于直线链码理论的快速直线绘制算法,微计算机应用, 1994, 15(6): 2931.程 锦 1978年生,博士研究生.主要研究方向为计算机辅助设计与计算机图形学.陆国栋 1963年生,博士,教授,浙江大学工程及计算机图学研究所副所长.主要研究领域为智能CAD、 三维重建、 工程图样计算机理解等.谭建荣 1954年生,教授,博士生导师,浙江大学机械工程与自动化系主任,中国图象图形学报编委.主要研究领域为产品信息建模、 计算机辅助设计、 计算机图形学等.593第4期程 锦等:基于直线特性的直线生成集成算法
