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

外文翻译一种新的反走样画线算法1浙江师范大学本科毕业设计(论文)外文翻译译文：一种新的反走样画线算法摘要：考虑一条直线。在传统的画线算法中，若表示直线上点，则必须是一个整数，然后根据所定义的过滤器和的到帧缓冲器映射。在本文中，我们提出了一种由它周围的四个像素来模拟一个采样点，其中和没有必要的是整数。根据所提出的反走样方法，并且由于像素所接收的明暗度存在封闭性，我们可以实现沿着线段进行无限数量的点的采样的效果。此外，我们的这种连贯性的属性可以降低计算明暗度的成本。关键字：计算机图形学；画线算法；反走样1.简介计算机图形学中的线描转换算法是最基础的算法。目前，最常用的显示装置是光栅显示。在光栅显示中的每个像素都具有整数坐标并且可以显示灰度级的点。在光栅显示器上绘制一条直线y=f(x)的方法是通过模拟直线上的点的集合和相关联的灰度值。假设线段的斜率为。一个简单的画线方法是根据线段上每个整数点的坐标来计算值，其中，可以不是一个整数。一种“全有或全无”的方法是模拟线段轨迹像素的集合的值是或这取决于哪一个这两个点中哪个更接近真实点。传统DDA算法和Bresenham算法都是通过恒定加剧或者的亮度办法来绘制直线的。在这种情况下，光栅显示器所呈现的曲线呈阶阶梯状，而这令人讨厌的视觉效果就被称为走样。反走样技术中包括低通滤波。过滤器的功能是在确定曲线路径中指定适当明暗度的值，得到一个模糊的边缘像素。这种算法的一个例子是Wu[2]。在Wu提出的算法中，通过两个像素宽的边界采样点来模拟真实曲线。Wu的算法是类似于通过取整数点来计算的Bresenham算法。点和点的亮度强度与该点到实际点的距离I成反比(1)外文翻译一种新的反走样画线算法2上面的两个等式中右边是对点的“预期接收明暗值”的计算，左边值是对“实际接收明暗值”的计算。有很多人集中精力研究出了优秀的反走样技术。但是，很多时候，良好的反走样计算需要非常高的成本。比如Gupta,Sproul和Barkans使用了锥形渐函数和一个Hamming函数，它们分别预先计算出一组存储在查找表中的过滤值。每一个整数取样点的通过上述方法，根据自己的过滤器的值和与相邻点的距离，像素分配到相应的像素亮度强度。在本文中，我们将用实际采样点的周围的四个像素点来模拟真实点，其中和不一定是整数。基于这种方法，由于我们可以得到所接收封闭形式的像素明暗度的解决方案，所以证明了无限多的点进行采样沿一条线是可能的。在接下来的部分，我们将首先介绍所提出的反走样技术，并定义预期的明暗度。在第3节中我们将衍生像素明暗度的封闭形式的解决方案。第4节为本文小结。2.序言在本节中，我们提出了由采样点周围的四个像素来模拟采样点。在本节，我们还定义了预期的明暗度。(图1)外文翻译一种新的反走样画线算法3在光栅显示器中，点这四个点分别构成一个正方形的四个顶点。考虑点，设该点处于正方形中，其中和不是像图1中所示的整数。接下来我们用中的这四个点来模拟点。设表示为了模拟点的预期明暗度，设,(2),,,上面四个点所得到的像素明暗度值一方面由如图和的长度决定，和分别表示这四个点到实际点的垂直距离。四个点明暗度的推导等式是：,(3),(4),(5),(6)一个像素所接收的明暗值是采样点像素（图1）相对于矩形的倍面积。预期明暗值是用来表现不同斜率值的具有相同亮度值的直线段。设表示一条端点分别为线段。考虑两条直线段和，由于的欧几里德距离的长度等于的倍，所以用来模拟的像素的数目是用来模拟的像素的数量的倍。假设我们在区间中采样N个具有相同明暗值的像素点，那么这些用于模拟的像素点的明暗值会低于用于模拟的像素点的明暗值。这种情况下，我们可以给予采样线上不同斜率值的点以不同的明暗值来解决这个问题。设线段，我们接下来定义目标明暗值，表示一个单位正方形，外文翻译一种新的反走样画线算法4在上面等式中，表示的长度（欧几里德距离），表示在的长度。是以前任何扫描转换算法中采样点数目的最大值。假设我们用反走样方法画一条斜率值为的直线，在一个单位正方形中我们可以沿着轴的方向取相隔分别距离为的n个像素点，每一个点的目标明暗值则通过等式(3)-(6)来确定四个像素点的值。由于像素接收从许多采样点的贡献，一个像素所获得的明暗值是所有采样点的贡献求和得到的。这将表明，因为对所接收的明暗值具有封闭形式，所以通过增加对取样点数目可以达到预期的线段显示效果。3.封闭形式在本节中，我们推导像素所接收的明暗度的封闭形式。为了便于表述，我们只考虑绘制斜率的直线（其他情况可以根据对称性得到）。我们还假设，指点线段的两个端点都是整数坐标有整数坐标。至此，我们可以不失一般性的假设直线为，其斜率是，并且。设是直线上X轴方向上的整数点，每条线段表示其单位线段，记为。考虑，如果或者，即完全在单位正方形中，则这种情况记为情况一；当时，我们称之为情况二,在这些情况下经过和。在的条件限制下，直线段的情况肯定属于这两种情况之一。接下来我们讨论像素接收明暗度的封闭形式的两种情况。3.1.情况一当属于情况一的时候，处于入图2的单位正方形中，这里有有四个顶点接收来自的明暗度,设。外文翻译一种新的反走样画线算法5（图2）定理1如果我们在线段上面定义无数个点，这四个顶点接收到的明暗值是,,,.证明假设在上有n个点，每个点的目标明暗值则是，点接收到的明暗值是通过累计累积n个采样点相反的矩形的面积的。对像素点的明暗度贡献是：假设我们有无数个点，则有：外文翻译一种新的反走样画线算法6，和也可以通过相似的方法得到。外文翻译一种新的反走样画线算法7定理2假设属于情况二所述，其经过如图3所示的两个单位正方形和。表示与的相交点。令和，其中表示的x坐标，则六个坐标点接收的明暗度分别是：（图3）外文翻译一种新的反走样画线算法8证明完整的证明是一个漫长而繁琐的工作。所以，在这里我们只推导和两种情况。线段对单位正方形的四个顶点的明暗度产生贡献和线段对单位正方形的四个顶点的明暗度产生贡献。我们将线段分为n部分，分别假设到有r部分，到有s部分。因为，所以()的目标明暗值是()。还注意到，沿着()，每两个相邻点的距离是，即有。像素点得到的来自的明暗度贡献，有since1-c=Lm像素点得到的来自的明暗度贡献，有外文翻译一种新的反走样画线算法9像素点和分别接收来自和的贡献值，同样的，这些得到的明暗度可以根据上述方法得到。像素点和都接收来自和的贡献值，同样的，这些得到的明暗度可以根据上述方法得到。因此，这两个像素所接收的明暗度是两个的贡献的总和。定理1和2表明，所接收到的像素的强度依赖于直线的斜率，并且与采样点的数目无关。无我们可以通过取无限大数量的点并且通过简单的算术运算就可以实现我们想要的效果。上述定理给出了一个简单的画线算法。对于从0到x-1的每个元素我们首先确定该元素属于哪种情况。然后，我们从上面给出的封闭形式的元素的顶点计算贡献。此实现的效率不取决于实际的采样点的数目。在下面的内容中我们将给你展示上述算法可以进一步提高效率，如果前一个像素点是属于第一种情况的情况下可以以更低的运算成本来计算出当前属于第一种情况的像素点。对于属于第二种情况下的情况我们的6个顶点接收到的强度可以通过简单的算术题来使之变得更简单。设两个点属于第一种情况的两个连续点，并且对四个顶点的贡献度都是已经算出来的，则对四个点的贡献值得算法如下面的定理。外文翻译一种新的反走样画线算法10（图4）推论3假设有两条平行的直线段，和都在同一个单位正方形中，设h是这两条线段在y轴方向上的距离（如图4）。点接收到的来自于和的贡献值不相同，记为证明类似于定理1推论3展示了两个属于情况一的距离且距离相隔为h的点对明暗值贡献的不同，如果第一个点时属于情况一的元素，我们就可以通过减去的贡献值来计算属于情况一中的点的贡献值。在下面的推论中展现了一个属于情况二种的计算贡献值的更有效的计算方法：推论4对于一个属于情况二中的穿过两个单位正方形和的直线段的贡献值有外文翻译一种新的反走样画线算法11证明类似于定理2但是通过推论4来计算和会消耗大量的资源。4.结论在本文中，我们提出了一种新的反走样画线的方法。该方法是基于一种低通滤波功能。根据所提出的反走样方法，并且由于像素所接收的明暗度存在封闭形式，我们可以实现沿着线段进行无限数量的点的采样的效果。我们表明，通过应用简单的规则，可以降低的成本，用于计算所接收的像素强度。此外，我们建议的方式来定义预期的明暗度，可以确保以相同的亮度显示的不同斜率的线段。（图5）很难用数学的方法来验证图像质量的反走样效果。此外，还有许多因素，例如伽马校正，可能对反走样技术产生影响。反走样的效果一般由人类感知的判断。如图5展示出了使用不同的算法得到的线。上左部分显示的图像，在绘制线段过程中没有使用任何反走样技术；右上方的图像中包含的线段，使用Sproll和Gupta的方法。左下角的图像显示的线段，使用的是外文翻译一种新的反走样画线算法12Wu的算法。利用我们所提出的算法得到的线段是右下部分图像。在参考文献7中的Gamma校正方法也被使用了，其中，。这样可以起到很好的反走样效果。参考文献[1]BresenhamJE.Algorithmforcomputercontrolofdigitalplotter.IBMSystemsJournal1965;4(1):25-30.[2]WuX.Anefficientantialiasingtechnique.ComputerGraphics1991;25(4):143-52.[3]BarkansAC.Highspeedhighqualityantialiasedvectorgeneration.ComputerGraphics1990;24(4):319-26.[4]CrowF.Thealiasingproblemincomputer-generatedshadedimages.CommunicationsoftheACM1977;20:11.[5]GuptaS,SproullR.Filteringedgesforgray-scaledisplays.ComputerGraphics1981;15(3):1-5.[6]HearnD,BakerMP.Computergraphics.EnglewoodCliffs,NJ:Prentice-Hall,1986.[7]WattA.Fundamentalsofthree-dimensionalcomputergraphics.Reading,MA:Addision-Wesley,1991.p.350.原文如下：外文翻译一种新的反走样画线算法13外文翻译一种新的反走样画线算法14外文翻译一种新的反走样画线算法15外文翻译一种新的反走样画线算法16外文翻译一种新的反走样画线算法17外文翻译一种新的反走样画线算法18外文翻译一种新的反走样画线算法19