精确的亚像素画线算法(光栅化算法) [英] Precise subpixel line drawing algorithm (rasterization algorithm)

问题描述

我需要一种比 Bresenham 画线算法慢的算法 但必须更准确.使用精确"我的意思是:应该打印每个触摸的像素.不多，也不少！这意味着使用更粗的线条或类似的线条不是一种选择，因为会涉及太多像素.此外，我不需要图形框架或类似的框架 询问 之前，我需要算法！该应用程序实际上并不是在图形"中，而是在 地理区域，其中像素是瓷砖".

I need an algorithm which can be (a bit) slower than the Bresenham line drawing algorithm but has to be a lot more exact. With 'exact' I mean: every touched pixel should be printed. No more, but also no less! Which means using a more thick line or similar is not an option as too many pixels will be involved. Also I don't need a graphic framework or similar like it was asked before, I need the algorithm! The application is not really in 'graphics' it is in the geography area where pixels are 'tiles'.

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

The main problem for me is that I need subpixel precision which means that a line could start at 0.75/0.33 and not just at 0/0 like it is the case for integer values. I tried to create a working solution for the last several hours but cannot make it working - there are too many edge cases.

首先，我认为像 Wu 的算法这样的抗锯齿版本应该可以它但它打印了太多像素(特别是对于起点和终点)，并且在某些情况下它仍然会丢失一些像素，例如用于非常短的行.

First I thought an anti-aliased version like the algorithm from Wu should make it but it prints too many pixels (especially for start and end points) and in certain cases it still misses some pixels e.g. for very short lines.

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

Then I tried to make Bresenham working where I replaced the second 'if' with 'else if' as pointed out here, and it is closer but still not there. Then I tried to move the Bresenham from integer- to float-precision which resulted in an endless loop (as the x,y values jumped over the finish condition if (y1 == y2 && x1 == x2)).

我可以使用 朴素的画线 解决方案，但是 delta 我应该使用吗?例如.如果我使用 0.1，我仍然会丢失一些像素，而使用较小的值可能会花费太长时间(并且仍然会丢失像素).

I could use the naive line drawing solution but which delta should I use? E.g. if I use 0.1 I will still miss some pixels and using smaller values it will probably take too long (and still miss pixels).

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

A working solution in C/Java/... would be appreciated. At least it should work for octant 1 but a full blown solution would be even nicer.

更新:我想出了以下想法:使用简单的线光栅化，您可以为每个点计算 4 个像素候选.然后检查这 4 个像素，如果线真的穿过它们.但我不确定线/框相交是否足够快.

Update: I came up with the following idea: using the naive line rasterization and you can calculate 4 pixel-candidates for every point. Then check for those 4 pixels if the line really crosses them. But I'm not sure if line/box intersection can be fast enough.

推荐答案

如果你只需要恒定的颜色(不是用像素的使用区域插值)，那么使用 DDA:

If you need just constant color (not interpolated by used area of pixel) then use 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++

is routine that rasterize pixel (x,y) with color col The source is in C++

我认为这是困难的，但无论如何

I think it is strait forward but anyway

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

DDA use parametric line equation y=k*x+q or x=ky+q dependent on the difference (if is bigger x or y difference so there are no holes). The k is dy/dx or dx/dy and the whole division is reduced to substraction+addition inside loop (last line of each loop). This can be easily modified to any number of dimensions (I usually use 7D or more with this). On modern machines is the speed sometimes better then Bresenham (depends on the Platform and usage).

与简单的 DDA

[edit2] 双坐标//原来是 [edit1]

[edit2] double coordinates // originally [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) 仍然是整数！！！

Angle should be in double precision now but pnt(x,y,col) is still on integers !!!

[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，所以我对光栅化进行了相当多的更改.现在计算所有像素网格交叉(交叉点)，然后为每个正确的子像素添加.这是它的样子(没有错误的子像素):

Finally had some time for this so I tweaked DDA a little but id lead to many ifs so I change rasterization quite a bit. Now all pixel grid crossing (intersections) are computed and then for each the right sub-pixel is added. This is how it looks like (no wrong sub-pixels):

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

For each x or y grid lines is the first cross point computed (a,b) and step is in one axis 1 pixel and in second the rest according to dy/dx or dx/dy. After this the for loop fill the sub-pixels ...

这篇关于精确的亚像素画线算法(光栅化算法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！