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

外文翻译 一种新的反走样画线算法浙江师范大学本科毕业设计(论文)外文翻译译文：一种新的反走样画线算法摘要：考虑一条直线fx=mx+b,0m1。在传统的画线算法中，若 x,fx表示直线上点，则x必须是一个整数，然后根据所定义的过滤器和fx的到帧缓冲器映射x,fx。在本文中，我们提出了一种由它周围的四个像素来模拟一个采样点x,fx，其中x和fx没有必要的是整数。根据所提出的反走样方法，并且由于像素所接收的明暗度存在封闭性，我们可以实现沿着线段进行无限数量的点的采样的效果。此外，我们的这种连贯性的属性可以降低计算明暗度的成本。关键字：计算机图形学；画线算法；反走样1. 简介计算机图形学中的线描转换算法是最基础的算法。目前，最常用的显示装置是光栅显示。在光栅显示中的每个像素都具有整数坐标并且可以显示灰度级的点。在光栅显示器上绘制一条直线y=f(x)的方法是通过模拟直线上的点的集合和相关联的灰度值。假设线段的斜率为m(0m1)。一个简单的画线方法是根据线段上每个整数点x的坐标来计算值y=f(x)，其中，y可以不是一个整数。一种“全有或全无”的方法是模拟线段y=f(x)轨迹像素的集合(x,g(f(x)的值是f(x)或f(x)这取决于哪一个这两个点中哪个更接近真实点f(x)。传统DDA算法 和Bresenham算法都是通过恒定加剧 (x,fx) 或者(x,fx)的亮度办法来绘制直线的。在这种情况下，光栅显示器所呈现的曲线呈阶阶梯状，而这令人讨厌的视觉效果就被称为走样。反走样技术中包括低通滤波。过滤器的功能是在确定曲线路径中指定适当明暗度的值，得到一个模糊的边缘像素。这种算法的一个例子是Wu2。在Wu提出的算法中，通过两个像素宽的边界采样点来模拟真实曲线y=f(x)。Wu的算法是类似于通过取整数点来计算y=f(x)的Bresenham算法。点(x,fx) 和点(x,fx)的亮度强度与该点到实际点的距离I成反比 Ix,fx=Ifx-fx, (1) Ix,f(x)=Ifx-f(x), 上面的两个等式中右边是对点x,fx 的“预期接收明暗值”的计算，左边值Ix，f(x)是对“实际接收明暗值”的计算。有很多人集中精力研究出了优秀的反走样技术。但是，很多时候，良好的反走样计算需要非常高的成本。比如Gupta, Sproul和 Barkans使用了锥形渐函数和一个Hamming函数，它们分别预先计算出一组存储在查找表中的过滤值。每一个整数取样点的x通过上述方法，根据自己的过滤器的值和与相邻点x,fx的距离，像素分配到相应的像素亮度强度。在本文中，我们将用实际采样点x,y的周围的四个像素点来模拟真实点，其中x和y不一定是整数。基于这种方法，由于我们可以得到所接收封闭形式的像素明暗度的解决方案，所以证明了无限多的点进行采样沿一条线是可能的。在接下来的部分，我们将首先介绍所提出的反走样技术，并定义预期的明暗度。在第3节中我们将衍生像素明暗度的封闭形式的解决方案。第4节为本文小结。 2. 序言在本节中，我们提出了由采样点周围的四个像素来模拟采样点。在本节，我们还定义了预期的明暗度。(图1)在光栅显示器中，点i,j,i,j+1,i+1,j,(i+1,j+1)这四个点分别构成一个正方形U(i,j)的四个顶点。考虑点p=(x,y)，设该点处于正方形U(x,y)中，其中x和y不是像图1中所示的整数。接下来我们用U(x,y)中的这四个点来模拟点p。设I表示为了模拟点p的预期明暗度，设ya=y-y, (2)yb=y-y,xa=x-x,xb=x-x,上面四个点所得到的像素明暗度值一方面由如图t1.和t2的长度决定，t1.和t2分别表示这四个点到实际点的垂直距离。四个点明暗度的推导等式是：Ixy=Ixbyb, (3)Ixy=Ixbya, (4)Ixy=Ixaya, (5)Ixy=Ixayb, (6)一个像素所接收的明暗值是采样点像素p（图1）相对于矩形的I倍面积。预期明暗值是用来表现不同斜率值的具有相同亮度值的直线段。设I(x0,y0,(x1,y1)表示一条端点分别为x0,y0,(x1,y1)线段。考虑两条直线段S1=l(0,0,(X,0)和S2=l(0,0,(X,X)，由于S2的欧几里德距离的长度等于S1的2倍，所以用来模拟S2的像素的数目是用来模拟S1的像素的数量的2倍。假设我们在区间x0,x1中采样N个具有相同明暗值I的像素点，那么这些用于模拟S2的像素点的明暗值会低于用于模拟S1的像素点的明暗值。这种情况下，我们可以给予采样线上不同斜率值的点以不同的明暗值来解决这个问题。设线段p1,p2=l(x1,y1,(x2y2)，我们接下来定义目标明暗值，I0表示一个单位正方形，I0=p1,p22p1,p2 在上面等式中，p1,p22表示p1,p2的长度（欧几里德距离），p1,p2表示p1,p2在L的长度。p1,p2是以前任何扫描转换算法中采样点数目(x2-x1,y2-y1)的最大值。假设我们用反走样方法画一条斜率值为m(0m1)的直线p1,p2，在一个单位正方形中我们可以沿着x轴的方向取相隔分别距离为x的n个像素点，每一个点的目标明暗值I0n则通过等式(3)-(6)来确定四个像素点的值。由于像素接收从许多采样点的贡献，一个像素所获得的明暗值是所有采样点的贡献求和得到的。这将表明，因为对所接收的明暗值具有封闭形式，所以通过增加对取样点数目可以达到预期的线段显示效果。3. 封闭形式在本节中，我们推导像素所接收的明暗度的封闭形式。为了便于表述，我们只考虑绘制斜率m(0m1)的直线（其他情况可以根据对称性得到）。我们还假设，指点线段的两个端点都是整数坐标有整数坐标。至此，我们可以不失一般性的假设直线为l0,0,x,y,x0,y0，其斜率是m=yx，并且0m1,xy。设(i,f(i)|i=0,1,x是直线l0,0,x,y上X轴方向上的整数点，每条线段li,f(i),i+1,f(i+1)表示其单位线段，记为Si。考虑Si，如果f(i+1)=f(i)或者f(i+1)=f(i)，即Si完全在单位正方形中，则这种情况记为情况一；当f(i+1)=f(i)+1时，我们称之为情况二,在这些情况下Si经过u(i,f(i)和u(i,f(i)。在xy,fi+1-fi1的条件限制下，直线段的情况肯定属于这两种情况之一。接下来我们讨论像素接收明暗度的封闭形式的两种情况。3.1. 情况一当Si属于情况一的时候，Si处于入图2的单位正方形中，这里有有四个顶点接收来自Si=l(i,fi,(i+1,f(i+1)的明暗度,设h=fi-f(i)。（图2）定理1 如果我们在线段Si上面定义无数个点，这四个顶点接收到的明暗值u(i,f(i)是I(i,f(i)=I0(12-m6-h2),I(i,f(i)=I0(m6+h2),I(i+1,f(i)=I0(m3+h2),I(i+1,f(i)=I0(12-m3-h2).证明 假设在Si上有n个点，每个点的目标明暗值则是I0n，点u(i,f(i)接收到的明暗值是通过累计累积n个采样点相反的矩形的面积的I0n。Si对像素点(i,f(i)的明暗度贡献是：Ii,fi=k=0n-1I0n1-kx1-kmx-h=I0nk=0n-11-kx-kmx+k2x2m-h+hkx=I0n(n-nn-12x-nn-12mx+nn-12n-16x2m-nh+nn-12hx)假设我们有无数个点，则有：Ii,fi=limnI0nn-nn-12x-nn-12mx+nn-12n-16x2m-nh+nn-12hx=I01-12-m2+m3-h+h2 since x=1n=I012-m6-h2I(i,f(i)， I(i+1,f(i+1)和I(i+1,f(i+1)也可以通过相似的方法得到。Ii,f(i)=limnk=0n-1I0n1-kxkmx+h=limnI0nk=0n-1(h-kx+kmx-k2x2m)=limnI0nnh-nn-12hx+nn-12mx-nn-12n-16x2m=I0h-h2+m2-m3=I0m6+h2Ii+1,f(i)=limnk=0n-1I0nkx1-kmx-h=limnI0nk=0n-1(kx-khx-k2x2m)=limnI0nnn-12x-nn-12hx-nn-12n-16x2m=I012-h2-m3Ii+1,f(i)=limnk=0n-1I0nkxkmx+h=limnI0nk=0n-1(khx+k2x2m)=limnI0nnn-12hx+nn-12n-16x2m=I0h2+m3定理2 假设Sj=q1,q3属于情况二所述，其经过如图3所示的两个单位正方形u(j,f(j)和u(j,f(j)。q2表示q1,q3与y=f(j)的相交点。令L=Xq2-j和c=fj-f(j)，其中Xqi表示qi的x坐标，则六个坐标点接收的明暗度分别是：I(j,f(j)=I0(m2L2-m6L3)I(j,f(j)=I0L-m2L2-L22+m6L3+I0(1-L22-m6(1-L)3)I(j,fj+1)=I0(m6(1-L)3)I(j+1,fj+1)=I0(m6L3)I(j+1,fj)=I0L22-m6L3+I0(L1-L+1-L22-m2L1-L2-m3(1-L)3)I(j+1,f(j)=I0(m2L(1-L)2-m3(1-L)3)（图3）证明 完整的证明是一个漫长而繁琐的工作。所以，在这里我们只推导(j,f(j)和(j,fj+1)两种情况。线段q1,q2对单位正方形u(j,f(j)的四个顶点的明暗度产生贡献和线段q2,q3对单位正方形u(j,f(j)的四个顶点的明暗度产生贡献。我们将线段q1q3分为n部分，分别假设q1到q2有r部分，q2到q3有s部分。因为L=Xq2-X(q1)(1-L=Xq3-X(q2)，所以q1,q2(q2,q3)的目标明暗值是I0=LI0(I0=(1-L)I0)。还注意到，r(s)沿着q1,q2(q2,q3)，每两个相邻点的距离是x，即有L=rx(1-L=sx)。像素点(j,f(j)得到的来自q1,q2的明暗度贡献，有I(j,f(j)=limrI0r(k=0r-11-c+kmx(1-kx)=limrI0r(k=0r-11-kx-c+ckx-kxm+k2x2m=limrI0r(r-xrr-12-rc+cxrr-12-xmrr-12+x2mr(r-1)(2r-1)6)=I0(1-L2-c+cL2-mL2+mL23)=I0 (L-L22-cL+cL22-mL22+mL33)=I0 (L(1-c)-L22(1-c)-mL22+mL33)=I0 (LLm-L22Lm-mL22+mL33) since 1-c=Lm=I0 (mL22-mL36) 像素点(j,fj+1)得到的来自q2,q3的明暗度贡献，有I(j,fj+1)=limsI0r(k=0s-11-(L+kx)kmx)=limsI0sk=0s-1kmx-Lkmx-k2mx2=limsI0s(mxss-12-xmLss-12+x2ms(s-1)(2s-1)6)=I0 (m1-L22-mL(1-L)22+m(1-L)33)=I0 (m6(1-L)3) 像素点(j+1,fj+1)和(j+1,f(j)分别接收来自q2,q3和q1,q2的贡献值，同样的，这些得到的明暗度可以根据上述方法得到。像素点(j,fj)和j+1,fj都接收来自q2,q3和q1,q2的贡献值，同样的，这些得到的明暗度可以根据上述方法得到。因此，这两个像素所接收的明暗度是两个的贡献的总和。定理1和2表明，所接收到的像素的强度依赖于直线的斜率，并且与采样点的数目无关。无我们可以通过取无限大数量的点并且通过简单的算术运算就可以实现我们想要的效果。上述定理给出了一个简单的画线算法。对于从0到x-1的每个元素我们首先确定该元素属于哪种情况。然后，我们从上面给出的封闭形式的元素的顶点计算贡献。此实现的效率不取决于实际的采样点的数目。在下面的内容中我们将给你展示上述算法可以进一步提高效率，如果前一个像素点是属于第一种情况的情况下可以以更低的运算成本来计算出当前属于第一种情况的像素点。对于属于第二种情况下的情况我们的6个顶点接收到的强度可以通过简单的算术题来使之变得更简单。设si，sj两个点属于第一种情况的两个连续点，并且si对四个顶点的贡献度都是已经算出来的，则sj对四个点的贡献值得算法如下面的定理。（图4）推论3 假设有两条平行的直线段，p1,p2和q1,q2都在同一个单位正方形uv0中，设h是这两条线段在y轴方向上的距离（如图4）。点vi接收到的来自于p1,p2和q1,q2的贡献值不相同，记ih,i=0,1,2,3为0h=-h21h=h22h=h23h=-h2证明 类似于定理1推论3展示了两个属于情况一的距离且距离相隔为h的点对s0明暗值贡献的不同，如果第一个点时属于情况一的元素，我们就可以通过减去s0的贡献值来计算属于情况一中的点的贡献值。在下面的推论中展现了一个属于情况二种的计算贡献值的更有效的计算方法：推论 4 对于一个属于情况二中的穿过两个单位正方形u(j,f(j)和u(j,f(j)的直线段的贡献值有I02=I(j,f(j)+I(j,f(j)+I(j,fj+1)=I(j+1,f(j)+I(j+1,f(j)+I(j+1,fj+1)证明 类似于定理2但是通过推论4来计算I(j,f(j)和I(j+1,f(j)会消耗大量的资源。4. 结论在本文中，我们提出了一种新的反走样画线的方法。该方法是基于一种低通滤波功能。根据所提出的反走样方法，并且由于像素所接收的明暗度存在封闭形式，我们可以实现沿着线段进行无限数量的点的采样的效果。我们表明，通过应用简单的规则，可以降低的成本，用于计算所接收的像素强度。此外，我们建议的方式来定义预期的明暗度，可以确保以相同的亮度显示的不同斜率的线段。（图5）很难用数学的方法来验证图像质量的反走样效果。此外，还有许多因素，例如伽马校正，可能对反走样技术产生影响。反走样的效果一般由人类感知的判断。如图5展示出了使用不同的算法得到的线。上左部分显示的图像，在绘制线段过程中没有使用任何反走样技术；右上方的图像中包含的线段，使用Sproll和Gupta的方法。左下角的图像显示的线段，使用的是Wu的算法。利用我们所提出的算法得到的线段是右下部分图像。在参考文献7中的Gamma校正方法也被使用了，其中I=I(1)，=2.3。这样可以起到很好的反走样效果。参考文献1 Bresenham JE. Algo