Algoritmo di disegno della linea subpixel preciso (algoritmo di rasterizzazione)

Question

Ho bisogno di un algoritmo che può essere (un po ') più lento dello Bresenham line drawing algorithm ma deve essere molto più preciso. Con "esatto" intendo: ogni pixel sfiorato dovrebbe essere stampato. Non più, ma anche niente di meno! Ciò significa che l'utilizzo di una linea più spessa o simile non è un'opzione in quanto saranno coinvolti troppi pixel. Inoltre non ho bisogno di un quadro grafico o simile come fosse askedbefore, ho bisogno dell'algoritmo! L'applicazione non è propriamente nella 'grafica' è nello geography area dove i pixel sono 'tessere'.

Il problema principale per me è che ho bisogno di precisione subpixel, il che significa che una linea potrebbe iniziare a 0,75/0,33 e non solo a 0/0, come nel caso dei valori interi. Ho provato a creare una soluzione funzionante per le ultime ore ma non riesco a farlo funzionare - ci sono troppi casi limite.

primo momento ho pensato una versione anti-aliasing, come l'algoritmo da Wu dovrebbe fare, ma esso stampa troppi pixel (soprattutto per i punti iniziali e finali) e, in alcuni casi manca ancora qualche pixel per esempio per linee molto brevi

Poi ho provato a far funzionare Bresenham dove ho sostituito il secondo 'se' con 'else if' come indicato here, ed è più vicino ma non ancora lì. Poi ho provato a spostare il Bresenham da intero a precisione a virgola mobile che ha provocato un loop infinito (mentre i valori x, y saltavano sopra la condizione di fine if (y1 == y2 && x1 == x2)).

Posso usare la soluzione naive line drawing ma quale delta devo usare? Per esempio. se uso 0.1 mi mancheranno ancora alcuni pixel e usando valori più piccoli probabilmente impiegheranno troppo tempo (e mancheranno ancora i pixel).

Una soluzione di lavoro in C/Java/... sarebbe apprezzata. Almeno dovrebbe funzionare per l'ottante 1, ma una soluzione completa sarebbe ancora più bella.

Aggiornamento: Mi è venuta in mente la seguente idea: utilizzando la rasterizzazione della linea naive è possibile calcolare 4 candidati pixel per ogni punto. Quindi controlla quei 4 pixel se la linea li incrocia davvero. Ma non sono sicuro che l'intersezione di linea/riquadro possa essere abbastanza veloce.

Answer 1

Se la linea è sottile e pixel sono rettangolari (quadrato):

poi considerare l'utilizzo di algoritmi di attraversamento griglia voxel, per esempio, vedere l'articolo "Fast Voxel Traversal Algorithm..." di Woo e Amanatides.

Practical implementation (nella griglia trasversale sezione)

Risposta al commento:
inizializzazione corretta per coordinata X variabili (uguale per 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 

esempio nella mia risposta here

Answer 2

Se hai bisogno di un colore costante (non interpolato dall'area di pixel utilizzata), utilizza 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); } 
     } 
    } 

dove:

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

è routine che rasterize pixel (x,y) con il colore col la sorgente è in C++

Penso che sia stretto in avanti, ma in ogni caso

DDA uso equazione linea parametrica y=k*x+q o x=ky+q dipendente dalla differenza (se è più grande x o y differenza quindi non ci sono buchi). Lo è dy/dx o dx/dy e l'intera divisione viene ridotta alla sottrazione + anello aggiuntivo interno (ultima riga di ciascun ciclo). Questo può essere facilmente modificato in qualsiasi numero di dimensioni (io di solito uso 7D o più con questo). Sulle macchine moderne è la velocità a volte meglio di Bresenham (dipende dalla piattaforma e dall'uso).

Questo è come sembra rispetto al semplice DDA

[EDIT2] doppie coordinate // originariamente [edit1]

OK qui è nuovo codice:

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; 
     } 
    } 

Ed è così che sembra:

angolo dovrebbe essere in double precisione, ma ora PNT (x, y, col) è ancora in interi !!!

[edit3] attraversamento griglia di pixel

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); } 
    } 

Infine aveva qualche tempo per questo in modo ottimizzato DDA poco ma id portare a molti if cosi cambio rasterizzazione un po '. Ora vengono calcolati tutti i passaggi a griglia dei pixel (intersezioni) e poi per ognuno viene aggiunto il sub-pixel destro.Questo è come sembra (non sbagliate sub-pixel):

Per ogni x o y linee della griglia è il primo punto croce calcolato (a,b) e step è in un asse 1 pixel e nella seconda il resto in base a dy/dx o dx/dy. Dopodiché il ciclo for riempie i sub-pixel ...