精确的子像素线绘制算法(光栅化算法)

Question

我需要一种比Bresenham线绘制算法慢一点的算法,但必须更精确.使用'exact'我的意思是:应该打印每个触摸的像素.不多也不少!这意味着使用更粗的线或类似物不是一种选择,因为将涉及太多的像素.此外,我并不需要一个图形框架或类似就像是问 之前,我需要的算法!应用程序实际上不是"图形",它位于像素为"图块" 的地理区域.

对我来说主要的问题是我需要子像素精度,这意味着一条线可以从0.75/0.33开始,而不仅仅是0/0,就像整数值的情况一样.我尝试在过去几个小时内创建一个可行的解决方案,但无法使其正常工作 - 边缘情况太多了.

首先,我认为抗锯齿的版本就像从算法吴应,但它打印像素过多(尤其是起点和终点),并在某些情况下,还惦记着,例如在非常短的线条一些像素.

然后我试着让Bresenham在我用'else if'取代第二个'if'的地方工作,这里指出了它,但它更接近但仍然不存在.然后我尝试将Bresenham从整数移动到浮点精度,这导致无限循环(因为x,y值跳过完成条件if (y1 == y2 && x1 == x2)).

我可以使用天真的线条绘图解决方案,但delta我应该使用哪个？例如,如果我使用0.1,我仍然会错过一些像素并使用较小的值,它可能会花费太长时间(仍然会错过像素).

C/Java/...中的工作解决方案将不胜感激.至少它应该适用于八分之一,但一个完整的解决方案会更好.

更新:我提出了以下想法:使用朴素行光栅化,您可以为每个点计算4个像素候选.然后检查这4个像素,如果该线真正穿过它们.但我不确定线/盒交叉点是否足够快.

Answer 1

如果您只需要恒定的颜色(不使用像素的使用区域进行插值),那么使用DDA:

void line_DDA_subpixel(int x0,int y0,int x1,int y1,int col) // DDA subpixel -> thick
    {
    int kx,ky,c,i,xx,yy,dx,dy;
    x1-=x0; kx=0; if (x1>0) kx=+1; if (x1<0) { kx=-1; x1=-x1; } x1++;
    y1-=y0; ky=0; if (y1>0) ky=+1; if (y1<0) { ky=-1; y1=-y1; } y1++;
    if (x1>=y1)
     for (c=x1,i=0;i<x1;i++,x0+=kx)
        {
        pnt(x0,y0,col); // this is normal pixel the two below are subpixels 
        c-=y1; if (c<=0) { if (i!=x1-1) pnt(x0+kx,y0,col); c+=x1; y0+=ky; if (i!=x1-1) pnt(x0,y0,col); }
        }
    else
     for (c=y1,i=0;i<y1;i++,y0+=ky)
        {
        pnt(x0,y0,col); // this is normal pixel the two below are subpixels 
        c-=x1; if (c<=0) { if (i!=y1-1) pnt(x0,y0+ky,col); c+=y1; x0+=kx; if (i!=y1-1) pnt(x0,y0,col); }
        }
    }

哪里:

void pnt(int x,int y,int col);

是(x,y)使用颜色col 光栅化像素的例程源是C++

无论如何,我认为它是向前发展的

DDA使用参数线方程y=k*x+q或x=ky+q取决于差异(如果更大x或y差异,所以没有孔).的k是dy/dx或dx/dy和整个分裂降低到减法+除了内循环(每个循环的最后一行).这可以很容易地修改为任意数量的维度(我通常使用7D或更多).在现代机器上,速度有时比Bresenham更好(取决于平台和使用情况).

与简单的DDA相比,这就是它的样子

[edit2]双坐标 //最初[edit1]

好的,这是新代码:

void line_DDA_subpixel1(double x0,double y0,double x1,double y1,int col)    // DDA subpixel -> thick
    {
    int i,n,x,y,xx,yy;
    // prepare data n-pixels,x1,y1 is line dx,dy step per pixel
    x1-=x0; i=ceil(fabs(x1));
    y1-=y0; n=ceil(fabs(y1));
    if (n<i) n=i; if (!n) n=1;
    x1/=double(n);
    y1/=double(n); n++;
    // rasterize DDA line
    for (xx=x0,yy=y0,i=0;i<=n;i++,x0+=x1,y0+=y1)
        {
        // direct pixel
        pnt(x,y,col);
        // subpixels on change in both axises
        x=x0; y=y0;
        if ((i<n)&&(x!=xx)&&(y!=yy)) { pnt(xx,y,col); pnt(x,yy,col); }
        xx=x; yy=y;
        }
    }

这就是它的样子:

角度double现在应该精确,但pnt(x,y,col)仍然是整数!

[edit3]像素网格交叉

void DDAf_line_subpixel(float x0,float y0,float x1,float y1,int col)    // DDA subpixel -> thick
    {
    int i,n; float a,a0,a1,aa,b,d;
    // end-points
    pnt(x0,y0,col);
    pnt(x1,y1,col);
    // x-axis pixel cross
    a0=1; a1=0; n=0;
    if (x0<x1) { a0=ceil(x0); a1=floor(x1); d=(y1-y0)/(x1-x0); a=a0; b=y0+(a0-x0)*d; n=fabs(a1-a0); } else
    if (x0>x1) { a0=ceil(x1); a1=floor(x0); d=(y1-y0)/(x1-x0); a=a0; b=y1+(a0-x1)*d; n=fabs(a1-a0); }
    if (a0<=a1) for (aa=a,i=0;i<=n;i++,aa=a,a++,b+=d) { pnt(aa,b,col); pnt( a,b,col); }
    // y-axis pixel cross
    a0=1; a1=0; n=0;
    if (y0<y1) { a0=ceil(y0); a1=floor(y1); d=(x1-x0)/(y1-y0); a=a0; b=x0+(a0-y0)*d; n=fabs(a1-a0); } else
    if (y0>y1) { a0=ceil(y1); a1=floor(y0); d=(x1-x0)/(y1-y0); a=a0; b=x1+(a0-y1)*d; n=fabs(a1-a0); }
    if (a0<=a1) for (aa=a,i=0;i<=n;i++,aa=a,a++,b+=d) { pnt(b,aa,col); pnt(b, a,col); }
    }

终于有了一些时间,所以我稍微调整了DDA但是导致了很多ifs因此我更改了光栅化.现在计算所有像素网格交叉(交叉点),然后为每个添加右子像素.这是它的样子(没有错误的子像素):

对于每个x或y网格线是计算的第一个交叉点(a,b),step并且在一个轴1像素中,在第二个交叉点中,其余部分根据dy/dx或dx/dy.在此之后,for循环填充子像素......

Answer 2

如果您的线条很细并且像素是矩形（正方形）：

然后考虑使用体素网格遍历算法，例如，参见 Woo 和 Amanatides 的文章“快速体素遍历算法... ”。

实际实现（网格遍历部分）

评论答案：
X坐标变量的正确初始化（Y坐标相同）

  DX = X2 - X1
  tDeltaX = GridCellWidth / DX
  tMaxX = tDeltaX * (1.0 - Frac(X1 / GridCellWidth)) 
  //Frac if fractional part of float, for example, Frac(1.3) = 0.3

我的回答中的示例在这里