Linjeritningsalgoritm

Två rastrerade linjer. De färgade pixlarna visas som cirklar. Ovan: monokrom screening; nedan: Gupta-Sproull kantutjämning; den ideala linjen betraktas här som en yta.

I datorgrafik är en linjeritningsalgoritm en algoritm för att approximera ett linjesegment på diskreta grafiska media, såsom pixelbaserade skärmar och skrivare . På sådana medier kräver linjeteckning en uppskattning (i icke-triviala fall). Grundläggande algoritmer rastrar linjer i en färg. En bättre representation med flera färggraderingar kräver en avancerad process, rumslig kantutjämning .

På kontinuerliga medier, däremot, behövs ingen algoritm för att dra en linje. Till exempel katodstråleoscilloskop analoga fenomen för att rita linjer och kurvor.

Lista över linjeritningsalgoritmer

Linjer som använder Xiaolin Wus algoritm, som visar ett "roligt" utseende.

Följande är en ofullständig lista över linjeritningsalgoritmer:

• Naiv algoritm
• Digital Differential Analyzer (grafikalgoritm) — Liknar den naiva linjeritningsalgoritmen, med mindre variationer.
• Bresenhams linjealgoritm — optimerad för att endast använda additioner (dvs inga divisionsmultiplikationer); det undviker också flyttalsberäkningar.
• Xiaolin Wus linjealgoritm — kan utföra rumslig kantutjämning, verkar "ropey" från ljusstyrka som varierar längs linjens längd, även om denna effekt kan reduceras kraftigt genom att förkompensera pixelvärdena för målskärmens gammakurva, t.ex. i ^ (1/2,4).
• Gupta-Sproull algoritm

En naiv linjeritningsalgoritm

Den enklaste metoden för screening är den direkta ritningen av ekvationen som definierar linjen.

 dx = x2 − x1 dy = y2 − y1  för  x  från  x1  till  x2  gör  y = y1 + dy × (x − x1) / dx plot(x, y) 

Det är här som punkterna redan har ordnats så att $x_{2}>x_{1}$ . Den här algoritmen fungerar alldeles utmärkt när $dx\geq dy$ (dvs lutning är mindre än eller lika med 1), men om $dx<dy$ (dvs. lutning större än 1) blir linjen ganska gles med många luckor, och i begränsningsfallet $dx=0$ kommer en division med noll undantag att inträffa.

Den naiva linjeritningsalgoritmen är ineffektiv och därför långsam på en digital dator. Dess ineffektivitet härrör från antalet operationer och användningen av flyttalsberäkningar. Algoritmer som Bresenhams linjealgoritm eller Xiaolin Wus linjealgoritm är att föredra istället.

Gupta och Sproll-algoritm

Gupta-Sproll-algoritmen är baserad på Bresenhams linjealgoritm men lägger till kantutjämning .

En optimerad variant av Gupta-Sproull-algoritmen kan skrivas i pseudokod enligt följande:

 DrawLine(x1, x2, y1, y2) { x = x1; y = yl;  dx = x2 − x1;  dy = y2 - y1;  d = 2 * dy − dx;  // diskriminator // Euklidiskt avstånd från punkt (x,y) från linje (tecken) D = 0;  // Euklidiskt avstånd mellan punkterna (x1, y1) och (x2, y2) längd = sqrt(dx * dx + dy * dy);  sin = dx / längd;  cos = dy / längd;   while  (x <= x1) { IntensifyPixels(x, y − 1, D + cos); IntensifyPixels(x, y, D);  IntensifyPixels(x, y + 1, D − cos);  x = x + 1   om  (d <= 0) { D = D + sin; d = d + 2 * dy;  }   annat  { D = D + sin − cos; d = d + 2 * (dy - dx);  y = y + 1;  } } }  

Funktionen IntensifyPixel(x,y,r) tar en radiell linjetransformation och ställer in intensiteten för pixeln (x,y) med värdet av ett kubiskt polynom som beror på pixelns avstånd r från linjen.

• Fundamentals of Computer Graphics, 2nd Edition, AK Peters av Peter Shirley