Точный алгоритм рисования субпиксельных линий (алгоритм растеризации)

Если вам нужен только постоянный цвет (не интерполированный по используемой области пикселя), используйте 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) с помощью color col. Источник находится на C ++

Я думаю, что это прямолинейно, но в любом случае

DDA используйте параметрическое линейное уравнение y=k*x+q или x=ky+q в зависимости от разницы (если разница больше x или y, значит нет отверстий). k равно dy/dx или dx/dy, и все деление сводится к вычитанию + сложению внутри цикла (последняя строка каждого цикла). Его можно легко изменить на любое количество измерений (я обычно использую с ним 7D или больше). На современных машинах скорость иногда лучше, чем у Брезенхэма (зависит от платформы и использования).

Вот как это выглядит по сравнению с простым 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 заполняет субпиксели ...

Если ваша линия тонкая, а пиксели прямоугольные (квадратные):

затем рассмотрите возможность использования алгоритмов обхода сетки вокселей, например, см. статью "Fast Voxel Алгоритм обхода ... "Ву и Аманатидес.

Практическая реализация (в разделе обхода сетки)

Ответ на комментарий:
Правильная инициализация переменных 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

пример в моем ответе здесь