Brsenham加速算法.pdfVIP

2011 年 第 20 卷 第 4 期 计 算 机 系 统 应 用 基于循环减法加速的多像素Bresenham 直线绘制算法① 李 向 (郑州航空工业管理学院 计算机科学与应用系，郑州 450015) 摘 要：直线生成算法是图形的基本元素，也是计算机图形学基础理论的重要内容。Bresenham 算法是直线生成 算法中最经典的算法，但是它一次计算只能生成一个像素点，效率低下。为了提高直线生成效率，充分利用待 生成线段的起点和终点坐标及线段自身的对称性，对 Bresenham 算法进行改进，一次计算生成一个像素行。讨 论硬件实现该算法的加速方法。 关键词：直线；Bresenham ；计算机图形学；多像素；算法 Accelerated Multi-Pixel Bresenham Line Drawing Algorithm Based on Circular Subtraction LI Xiang (Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015, China) Abstract: Line drawing algorithm is very important in the computer graphics. It is the most famous algorithm that Bresenham Algorithm uses to draw a straightness line in a smooth fashion. The advantage of classic Bresenham Algorithm is that the operations are all integer numeric without division and decimal fraction. Meanwhile, the disadvantage of the algorithm is that it can just generate one pixel in a computation time and its low in efficiency. In this paper, an accelerated algorithm was proposed, which give full attention to the initiative relation between generation model of line and its linear slope, and it does generate more than one pixel of a line through row of raster display device. The core principle of the improved algorithm is utilizing the coordinate position of both ends of line and the symmetry characteristic for segments. After discussing theory and structure of the improved algorithm, the algorithm implementation and simulation are given at last. And finally, the hardware acceleration in the use of circular subtraction technology based on shift register was briefly described. Keywords: line; bresenham; computer graphics; multi-pixel; algorithm 直线是图形中最基本的元素之一，直线生成算法 和 1 次符号判断。其缺点在于效率不高，一次计算只 是其他各类图形算法的基础，直线绘制算法的好坏对