Algorytm rysowania linii

Dwie rastrowe linie. Kolorowe piksele są pokazane jako okręgi. Powyżej: ekran monochromatyczny; poniżej: antyaliasing Gupta-Sproull; idealna linia jest tutaj uważana za powierzchnię.

W grafice komputerowej algorytm rysowania linii to algorytm aproksymacji segmentu linii na dyskretnych nośnikach graficznych , takich jak wyświetlacze i drukarki oparte na pikselach . Na takich nośnikach rysowanie linii wymaga przybliżenia (w nietrywialnych przypadkach). Podstawowe algorytmy rasteryzują linie w jednym kolorze. Lepsze odwzorowanie z wieloma gradacjami kolorów wymaga zaawansowanego procesu przestrzennego antyaliasingu .

Z kolei w mediach ciągłych żaden algorytm nie jest potrzebny do narysowania linii. Na przykład oscyloskopy katodowe wykorzystują zjawiska analogowe do rysowania linii i krzywych.

Lista algorytmów rysowania linii

Linie wykorzystujące algorytm Xiaolin Wu, przedstawiające wygląd „liny”.

Poniżej znajduje się częściowa lista algorytmów rysowania linii:

Algorytm naiwny
Cyfrowy analizator różnicowy (algorytm graficzny) — podobny do naiwnego algorytmu rysowania linii, z niewielkimi różnicami.
Algorytm liniowy Bresenhama — zoptymalizowany do używania tylko dodatków (tj. bez dzielenia Mnożenia); unika również obliczeń zmiennoprzecinkowych.
Algorytm liniowy Xiaolin Wu — może wykonywać przestrzenne wygładzanie krawędzi, pojawia się „sznurek” z jasności zmieniającej się wzdłuż linii, chociaż efekt ten można znacznie zmniejszyć poprzez wstępną kompensację wartości pikseli dla krzywej gamma wyświetlacza docelowego, np. out = w ^ (1/2,4). ^{[ oryginalne badania? ]}
Algorytm Gupty-Sproulla

Naiwny algorytm rysowania linii

Najprostszą metodą przesiewania jest bezpośrednie wykreślenie równania wyznaczającego linię.

 dx = x2 − x1 dy = y2 − y1  dla  x  od  x1  do  x2  do  y = y1 + dy × (x − x1) / dx wykres(x, y)

$uporządkowane$ tutaj punkty zostały już Ten algorytm działa dobrze, gdy (tj. $nachylenie$ jest mniejsze lub równe 1), ale jeśli $dx <dy}$ . nachylenie większa niż 1), linia staje się dość rzadka z wieloma przerwami, aw granicznym przypadku ${\ displaystyle dx = 0}$ , wystąpi wyjątek dzielenia przez zero.

Naiwny algorytm rysowania linii jest nieefektywny, a zatem powolny na komputerze cyfrowym. Jego nieefektywność wynika z liczby operacji i stosowania obliczeń zmiennoprzecinkowych. algorytmy, takie jak algorytm liniowy Bresenhama lub algorytm liniowy Xiaolina Wu .

Algorytm Gupty i Sprolla

Algorytm Gupta-Sproll jest oparty na algorytmie liniowym Bresenhama , ale dodaje antyaliasing .

Zoptymalizowany wariant algorytmu Gupta-Sproull można zapisać w pseudokodzie w następujący sposób:

 RysujLinia(x1, x2, y1, y2) { x = x1; y = y1;  dx = x2 − x1;  dy = y2 − y1;  re = 2 * dy - dx;  // dyskryminator // Odległość euklidesowa punktu (x,y) od prostej (ze znakiem) D = 0;  // odległość euklidesowa między punktami (x1, y1) i (x2, y2) length = sqrt(dx * dx + dy * dy);  grzech = dx / długość;  cos = dy / długość;   while  (x <= x1) { IntensifyPixels(x, y − 1, D + cos); IntensifyPixels(x, y, D);  IntensifyPixels(x, y + 1, D − cos);  x = x + 1   jeśli  (d <= 0) { re = re + grzech; re = re + 2 * dy;  }   inaczej  { re = re + grzech - sałata; re = re + 2 * (dy - dx);  y = y + 1;  } } }

Funkcja IntensifyPixel(x,y,r) przyjmuje transformację linii promieniowej i ustawia intensywność piksela (x,y) na wartość wielomianu sześciennego, który zależy od odległości piksela r od linii.

Podstawy grafiki komputerowej, wydanie 2, AK Peters autorstwa Petera Shirleya