Uproszczony algorytm linii Bresenhama: co to * dokładnie * robi?

Question

podstawie artykułu Wikipedii na algorytm bresenhama Mam wdrożyła simplified version opisane tam, mój wykonania Java wygląda następująco:

int dx = Math.abs(x2 - x1); 
int dy = Math.abs(y2 - y1); 

int sx = (x1 < x2) ? 1 : -1; 
int sy = (y1 < y2) ? 1 : -1; 

int err = dx - dy; 

while (true) { 
    framebuffer.setPixel(x1, y1, Vec3.one); 

    if (x1 == x2 && y1 == y2) { 
     break; 
    } 

    int e2 = 2 * err; 

    if (e2 > -dy) { 
     err = err - dy; 
     x1 = x1 + sx; 
    } 

    if (e2 < dx) { 
     err = err + dx; 
     y1 = y1 + sy; 
    } 
} 

Teraz rozumiem, że err reguluje stosunek między kroków na osi x w porównaniu do kroków na osi Y - ale teraz, gdy mam udokumentować, co robi kod, nie wyrażam jednoznacznie, do czego to służy i dlaczego są one takie, jak są i dlaczego są err została zmieniona w sposób przedstawiony w kodzie.

Wikipedia nie wskazuje jakichkolwiek bardziej zobaczyć szczegółowe wyjaśnienia lub źródeł, więc zastanawiam się:

Co dokładnie robi err zrobić i dlaczego dx i dy wykorzystywane w taki sposób pokazany w celu utrzymania prawidłowej proporcji między krokami poziomymi i pionowymi, używając tej uproszczonej wersji algorytmu linii Bresenhama?

Answer 1

Istnieją różne formy równań dla linii, jedną z najbardziej znanych jest y=m*x+b. Teraz, jeśli m=dy/dx i c = dx*b, to dx*y = dy*x + c. Zapisywanie f(x) = dy*x - dx*y + c, mamy f(x,y) = 0 iff (x,y) jest punktem na danej linii.

Jeśli wykonasz jedną z następujących czynności: x, f(x,y) zmian przez dy; jeśli wykonasz jeden krok, y jedną jednostkę, f(x,y) zmian przez dx. W kodzie err przedstawia bieżącą wartość liniowego funkcjonalnej f(x,y) i zestawienie sekwencji

err = err - dy; 
    x1 = x1 + sx; 

i

err = err + dx; 
    y1 = y1 + sy; 

stanowią postęp x lub y jednej jednostki (w sx lub sy kierunku), z konsekwentnym wpływem na wartość funkcji. Jak wspomniano wcześniej, f(x,y) wynosi zero dla punktów na linii; jest dodatni dla punktów po jednej stronie linii, a ujemnych dla tych z drugiej. Testy if określają, czy przesuwanie x pozostanie bliżej żądanej linii niż przejście dalej: y lub odwrotnie, lub oba.

Inicjalizacja err = dx - dy; została zaprojektowana w celu zminimalizowania błędu przesunięcia; jeśli wysadzisz swoją skalę drukowania, zobaczysz, że twoja obliczona linia nie może być wyśrodkowana na żądanej linii z różnymi inicjalizacjami.

Answer 2

Po prostu chcę dodać jeden kawałek "dlaczego" do doskonałej odpowiedzi jwpat.

Punktem zastosowania formuły f(x) = dy*x - dx*y + c jest przyspieszenie obliczeń. Ta formuła wykorzystuje arytmetykę całkowitą (szybszą), podczas gdy tradycyjna formuła wykorzystuje arytmetykę zmiennoprzecinkową (wolniejszą).