algorithm - 精确亚像素画线算法(光栅化算法)

Question

我需要一个比 Bresenham line drawing algorithm 慢一点的算法但必须更准确。我的意思是“精确”:应该打印每个触摸的像素。不多也不少!这意味着使用更粗的线或类似的线不是一种选择，因为会涉及太多像素。我也不需要图形框架或类似的 asked before ，我需要算法!该应用程序实际上并不在“图形”中，而是在 geography area 中。其中像素是“图 block ”。

我的主要问题是我需要亚像素精度，这意味着一条线可以从 0.75/0.33 开始，而不是像整数值那样仅从 0/0 开始。在过去的几个小时里，我试图创建一个可行的解决方案，但无法使其发挥作用 - 边缘情况太多。

首先我想到了像Wu 中的算法那样的抗锯齿版本。应该成功但是它打印了太多像素(尤其是起点和终点)并且在某些情况下它仍然会遗漏一些像素，例如对于非常短的行。

然后我尝试让 Bresenham 工作，正如指出的那样，我用“else if”替换了第二个“if”here , 它更近了，但仍然不存在。然后我尝试将 Bresenham 从整数精度移动到浮点精度，这导致了无限循环(因为 x、y 值跳过了完成条件 if (y1 == y2 && x1 == x2)).

我可以使用 naive line drawing解决方案，但我应该使用哪个 delta？例如。如果我使用 0.1，我仍然会错过一些像素，使用较小的值可能会花费太长时间(并且仍然会错过像素)。

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

更新:我想到了以下想法:使用简单的线栅格化，您可以为每个点计算 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);

是用颜色 col 光栅化像素 (x,y) 的例程源代码在 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 做了一些调整，但 id 导致了许多 if，所以我对光栅化做了很多改动。现在计算所有像素网格交叉点(交叉点)，然后为每个正确的子像素添加。这是它的样子(没有错误的子像素):

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