Präziser Subpixel-Linienzeichnungsalgorithmus (Rasterisierungsalgorithmus)

Question

Ich brauche einen Algorithmus, der (ein bisschen) langsamer sein kann als der Bresenham line drawing algorithm, muss aber viel genauer sein. Mit 'genau' meine ich: Jeder berührte Pixel sollte gedruckt werden. Nicht mehr, aber auch nicht weniger! Das bedeutet, dass die Verwendung einer dickeren Linie oder ähnlichem keine Option ist, da zu viele Pixel beteiligt sind. Auch brauche ich kein Grafikframework oder ähnliches wie es war asked, ich brauche den Algorithmus! Die Anwendung ist nicht wirklich in "Grafiken" ist es in der geography area, wo Pixel "Kacheln" sind.

Das Hauptproblem für mich ist, dass ich Subpixel-Präzision brauche, was bedeutet, dass eine Linie bei 0,75/0,33 und nicht nur bei 0/0 beginnen könnte, wie es bei ganzzahligen Werten der Fall ist. Ich habe versucht, eine funktionierende Lösung für die letzten Stunden zu erstellen, kann aber nicht funktionieren - es gibt zu viele Randfälle.

Zuerst dachte ich, eine Anti-Alias-Version wie der Algorithmus von Wu sollte es machen, aber es druckt zu viele Pixel (vor allem für Start- und Endpunkte) und in bestimmten Fällen fehlen noch einige Pixel z. für sehr kurze Zeilen.

Dann habe ich versucht, Bresenham arbeiten, wo ich das zweite "wenn" mit "else if" ersetzt, wie here, und es ist näher, aber immer noch nicht da. Dann habe ich versucht, den Bresenham von Integer- auf Float-Präzision zu bewegen, was zu einer Endlosschleife führte (als die x, y-Werte über die Endbedingung if (y1 == y2 && x1 == x2) gesprungen sind).

Ich könnte die naive line drawing Lösung verwenden, aber welche delta sollte ich verwenden? Z.B. Wenn ich 0.1 verwende, verpasse ich immer noch einige Pixel und benutze kleinere Werte, es wird wahrscheinlich zu lange dauern (und immer noch Pixel vermissen).

Eine funktionierende Lösung in C/Java/... wäre willkommen. Zumindest sollte es für Octant 1 funktionieren, aber eine ausgewachsene Lösung wäre noch schöner.

Update: Ich kam auf folgende Idee: Mit der naiven Linienrasterisierung können Sie für jeden Punkt 4 Pixel-Kandidaten berechnen. Überprüfen Sie dann diese 4 Pixel, wenn die Linie sie wirklich kreuzt. Aber ich bin mir nicht sicher, ob die Linie/Kasten-Kreuzung schnell genug sein kann.

Answer 1

Wenn Ihre Linie ist dünn und Pixel sind rechteckig (quadratisch):

dann prüfen, unter Verwendung von Voxelraster traversal Algorithmen, siehe zum Beispiel der Artikel „Fast Voxel Traversal Algorithm...“ von Woo und Amanatides.

Practical implementation (in Raster-Traversal-Bereich)

Antwort Kommentar:
Proper Initialisierung für X-Koordinatenvariablen (das gleiche für 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 

Beispiel in meiner Antwort here

Answer 2

Wenn Sie nur konstante Farbe benötigen (nicht interpoliert durch den verwendeten Pixelbereich), verwenden Sie 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); } 
     } 
    } 

wo:

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

Routine ist, dass rasterize Pixel (x,y) mit Farbe col Die Quelle ist in C++

Ich denke, es Straße nach vorne ist aber trotzdem

DDA Einsatz parametrische Liniengleichung y=k*x+q oder x=ky+q abhängig von der Differenz (wenn größer x oder y Unterschied, so dass es keine Löcher gibt). Die k ist dy/dx oder dx/dy und die gesamte Division reduziert sich auf Subtraktion + Addition innerhalb der Schleife (letzte Zeile jeder Schleife). Dies kann leicht auf eine beliebige Anzahl von Dimensionen geändert werden (ich verwende normalerweise 7D oder mehr damit). Bei modernen Maschinen ist die Geschwindigkeit manchmal besser als bei Bresenham (abhängig von der Plattform und der Nutzung).

Dies ist, wie es wie // ursprünglich [edit1]

hier einfach DDA

[edit2] Doppel Koordinaten Vergleich sieht

OK wird neuer Code:

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

Und so sieht es aus:

Winkel nun in double Präzision sein sollte, aber pnt (x, y, col) ist immer noch auf ganze Zahlen !!!

[EDIT3] Pixelraster Kreuzung

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

hatte schließlich einige Zeit dafür, damit ich DDA ein wenig, aber id führen zu vielen if gezwickt s so Rasterung ziemlich viel ich ändern. Jetzt werden alle Pixelgitter-Kreuzungen (Schnittpunkte) berechnet und dann wird für jeden der rechte Subpixel hinzugefügt.Dies ist wie es sein (keine falsche Unterpixel) aussieht:

Für jede x oder y Gitterlinien ist der erste Kreuzungspunkt berechnet (a,b) und step ist in einer Achse 1 Pixel und in zweiten der Rest nach dy/dx oder dx/dy. Danach füllen die for-Schleife die Sub-Pixel ...