精确的亚像素线绘制算法（光栅化算法） [英] Precise subpixel line drawing algorithm (rasterization algorithm)
问题描述
我需要一种算法，比（ Bresenham画线算法但必须更精确。与'确切'我的意思是：每个被触摸的像素应该被打印。没有更多，但也不会少！这意味着使用更粗的线或类似物并不是一种选择，因为会涉及太多的像素。此外，我不需要图形框架或类似的图像，它是询问 之前，我需要算法！该应用程序并非真正处于图形中，而是位于 geography area ，其中像素为tiles。子像素的精度，这意味着一条线可以从0.75 / 0.33开始，而不仅仅是在0/0，就像整数值的情况一样。我试图在过去几个小时内创建一个工作解决方案，但无法使其工作 - 边缘案例太多。
首先，我认为一个反锯齿版本来自 Wu 的算法应该可以实现，但它会打印太多的像素（特别是对于开始和结束点），在某些情况下，它仍然会丢失一些像素，例如然后我试着让Bresenham工作，我用另一个'if'代替了第二个'if'，正如指出的那样这里，它更接近但仍然不存在。然后我试着将Bresenham从整型转换为浮点型精度，导致了一个无限循环（因为x，y值超过了完成条件 if（y1 == y2&& x1 =我可以使用 rel =nofollow noreferrer>幼稚线条绘制解决方案，但是我应该使用 delta ？例如。如果我使用0.1，我仍然会错过一些像素，使用较小的值可能会花费太长时间（并且仍然会错过像素）。
C / Java / ...将不胜感激。至少它应该适用于八分圆1，但一个完整的解决方案会更好。
更新：我提出了以下想法：使用天真的线栅格化，您可以计算每个点的4个候选像素。然后检查这4个像素是否真的穿过它们。但是我不确定line / box的交集是否足够快。如果你只需要常量颜色（不是插值的）然后使用 DDA ：
void line_DDA_subpixel （int x0，int y0，int x1，int y1，int col）// DDA子像素 - >厚
{
int kx，ky，c，i，xx，yy，dx，dy;
x1- = x0; KX = 0;如果（x1> 0）kx = + 1;如果（x1 <0）{kx = -1; X1 = -x1; } x1 ++;
y1- = y0; KY = 0;如果（y1> 0）ky = + 1;如果（y1 <0）{ky = -1; Y1 = -y1; } y1 ++; （x1，y1）
（x = 0，i = 0; i if（x0，y0，列）; //这是正常像素，下面两个是子像素
c- = y1;如果（c <= 0）{if（i！= x1-1）pnt（x0 + kx，y0，col）; C + = X1; Y0 + = KY; if（i！= x1-1）pnt（x0，y0，col）; （c = y1，i = 0; i {
pnt（x0，y0，列）; //这是正常像素，下面两个是子像素
c- = x1;如果（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）
y = k * x + q 或 x = ky + q dependent （如果更大 x 或 y 差异，所以没有漏洞）。 k 是 dy / dx 或 dx / dy 和整个划分被缩减为内部循环内的减法+加法（每个循环的最后一行）。这可以很容易地修改为任意数量的维度（我通常使用 7D 或更多）。在现代机器上，速度有时比Bresenham更好（取决于平台和使用情况）。
与简单的 DDA
[edit2] double coordinates //原文[edit1]
$ b
void line_DDA_subpixel1（double x0，double y0，double x1，double y1，int col）/ / DDA子像素 - >厚
{
int i，n，x，y，xx，yy;
//准备数据n像素，x1，y1是行dx，dy每步像素步数
x1- = x0; I =小区（FABS（X1））;
y1- = y0; N =小区（FABS（Y1））;
if（n
y1 / = double（n）;的n ++;
//对于（xx = x0，yy = y0，i = 0; i <= n; i ++，x0 + = x1，y0 + = y1）
（$ b $）光栅化DDA线
b //直接像素
pnt（x，y，col）;
//两个轴上变化的子像素
x = x0; Y = Y0; （（i
xx = x; YY = Y;
这就是它的样子：
角度现在应该在 像素网格交叉 终于有一段时间了，所以我调整了 DDA <但是如果 s会导致许多 x 或 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'. 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. 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. 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 I could use the naive line drawing solution but which 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. 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. If you need just constant color (not interpolated by used area of pixel) then use DDA: where: is routine that rasterize pixel I think it is strait forward but anyway DDA use parametric line equation This is how it looks like compared to simple DDA [edit2] double coordinates // originally [edit1] OK here is new code: And this is how it looks like: Angle should be in [edit3] pixel grid crossing Finally had some time for this so I tweaked DDA a little but id lead to many For each 这篇关于精确的亚像素线绘制算法（光栅化算法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！ double 精度中，但 pnt（x，y，col）仍然是整数!!!
DDA子像素 - >厚
{
int i，n; float a，a0，a1，aa，b，d;
//终点
pnt（x0，y0，col）;
pnt（x1，y1，col）;
// x轴像素交叉
a0 = 1; A1 = 0; N = 0;
if（x0
// y轴像素交叉
a0 = 1; A1 = 0; N = 0;
if（y0
。 pnt（b，a，col）; }
}
，所以我会相当多地改变光栅化。现在计算所有像素网格交叉点（交叉点），然后为每个右侧子像素添加。这是它的样子（没有错误的子像素）：
y ， code> grid lines是第一个计算出的交叉点（a，b）和 step 位于一个坐标轴中根据 dy / dx 或 dx / dy 。在这之后，for循环填充子像素...... if (y1 == y2 && x1 == x2)).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).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) with color col The source is in C++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).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 precision now but pnt(x,y,col) is still on integers !!!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); }
}
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 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 ...
