一种新的反走样画线算法--外文翻译.doc

浙江师范大学本科毕业设计(论文)外文翻译 译文： 一种新的反走样画线算法 摘要：考虑一条直线。在传统的画线算法中，若表示直线上点，则必须是一个整数，然后根据所定义的过滤器和的到帧缓冲器映射。在本文中，我们提出了一种由它周围的四个像素来模拟一个采样点，其中和没有必要的是整数。根据所提出的反走样方法，并且由于像素所接收的明暗度存在封闭性，我们可以实现沿着线段进行无限数量的点的采样的效果。此外，我们的这种连贯性的属性可以降低计算明暗度的成本。 关键字：计算机图形学；画线算法；反走样 简介 计算机图形学中的线描转换算法是最基础的算法。目前，最常用的显示装置是光栅显示。在光栅显示中的每个像素都具有整数坐标并且可以显示灰度级的点。在光栅显示器上绘制一条直线y=f(x)的方法是通过模拟直线上的点的集合和相关联的灰度值。 假设线段的斜率为。一个简单的画线方法是根据线段上每个整数点的坐标来计算值，其中，可以不是一个整数。一种“全有或全无”的方法是模拟线段轨迹像素的集合的值是或这取决于哪一个这两个点中哪个更接近真实点。传统DDA算法 和Bresenham算法都是通过恒定加剧 或者的亮度办法来绘制直线的。在这种情况下，光栅显示器所呈现的曲线呈阶阶梯状，而这令人讨厌的视觉效果就被称为走样。 反走样技术中包括低通滤波。过滤器的功能是在确定曲线路径中指定适当明暗度的值，得到一个模糊的边缘像素。这种算法的一个例子是Wu[2]。在Wu提出的算法中，通过两个像素宽的边界采样点来模拟真实曲线。Wu的算法是类似于通过取整数点来计算的Bresenham算法。点 和点的亮度强度与该点到实际点的距离I成反比 (1) 上面的两个等式中右边是对点 的“预期接收明暗值”的计算，左边值是对“实际接收明暗值”的计算。 有很多人集中精力研究出了优秀的反走样技术。但是，很多时候，良好的反走样计算需要非常高的成本。比如Gupta, Sproul和 Barkans使用了锥形渐函数和一个Hamming函数，它们分别预先计算出一组存储在查找表中的过滤值。 每一个整数取样点的通过上述方法，根据自己的过滤器的值和与相邻点的距离，像素分配到相应的像素亮度强度。 在本文中，我们将用实际采样点的周围的四个像素点来模拟真实点，其中和不一定是整数。基于这种方法，由于我们可以得到所接收封闭形式的像素明暗度的解决方案，所以证明了无限多的点进行采样沿一条线是可能的。 在接下来的部分，我们将首先介绍所提出的反走样技术，并定义预期的明暗度。在第3节中我们将衍生像素明暗度的封闭形式的解决方案。第4节为本文小结。 序言 在本节中，我们提出了由采样点周围的四个像素来模拟采样点。在本节，我们还定义了预期的明暗度。 (图1) 在光栅显示器中，点这四个点分别构成一个正方形的四个顶点。考虑点，设该点处于正方形中，其中和不是像图1中所示的整数。接下来我们用中的这四个点来模拟点。设表示为了模拟点的预期明暗度，设 , (2) , , , 上面四个点所得到的像素明暗度值一方面由如图和的长度决定，和分别表示这四个点到实际点的垂直距离。四个点明暗度的推导等式是： , (3) , (4) , (5) , (6) 一个像素所接收的明暗值是采样点像素（图1）相对于矩形的倍面积。 预期明暗值是用来表现不同斜率值的具有相同亮度值的直线段。设表示一条端点分别为线段。考虑两条直线段和，由于的欧几里德距离的长度等于的倍，所以用来模拟的像素的数目是用来模拟的像素的数量的倍。假设我们在区间中采样N个具有相同明暗值的像素点，那么这些用于模拟的像素点的明暗值会低于用于模拟的像素点的明暗值。这种情况下，我们可以给予采样线上不同斜率值的点以不同的明暗值来解决这个问题。 设线段，我们接下来定义目标明暗值，表示一个单位正方形， 在上面等式中，表示的长度（欧几里德距离），表示在的长度。是以前任何扫描转换算法中采样点数目的最大值。 假设我们用反走样方法画一条斜率值为的直线，在一个单位正方形中我们可以沿着轴的方向取相隔分别距离为的n个像素点，每一个点的目标明暗值则通过等式(3)-(6)来确定四个像素点的值。由于像素接收从许多采样点的贡献，一个像素所获得的明暗值是所有采样点的贡献求和得到的。这将表明，因为对所接收的明暗值具有封闭形式，所以通过增加对取样点数目可以达到预期的线段显示效果。 封闭形式 在本节中，我们推导像素所接收的明暗度的封闭形式。为了便于表述，我们只考虑绘制斜率的直线（其他情况可以根据对称性得到）。我们还假设，指点线段的两个端点都是整数坐标有整数坐标。至此，我们可以不失一般性的假设直线为，其斜率是，并且。 设是直线上X轴方向上的整数点，每条线段表示其单位线段，记为。考虑，如果或