Algoritmo di linea semplificato di Bresenham: cosa fa esattamente * esattamente *?

Question

basa su articolo di Wikipedia algoritmo online di Bresenham Ho implementato il simplified version descritta lì, la mia implementazione Java assomiglia a questo:

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

Ora capisco che err controlla il rapporto tra i passaggi su l'asse x confronto ai passi sull'asse y - ma ora che dovrei documentare ciò che fa il codice non riesco a esprimere chiaramente, a cosa serve e perché esattamente le if-statement sono, come sono e perché err è cambiato nel modo visto nel codice.

Wikipedia non punta ad alcun spiegazioni più detagli riguardo o sorgenti, quindi mi chiedo:

Che cosa significa esattamente err fare e perché sono dx e dy utilizzato esattamente nel modo dimostrato di mantenere il corretto rapporto tra i passaggi orizzontali e verticali utilizzando questa versione semplificata dell'algoritmo di linea di Bresenham?

Answer 1

Esistono varie forme di equazioni per una linea, una delle più familiari è y=m*x+b. Ora se m=dy/dx e c = dx*b, quindi dx*y = dy*x + c. Scrivendo f(x) = dy*x - dx*y + c, abbiamo f(x,y) = 0 iff (x,y) è un punto su una determinata linea.

Se si anticipa x una unità, f(x,y) modifiche da dy; se si anticipa una unità, f(x,y) modifiche da dx. Nel codice, err rappresenta il valore attuale del funzionale lineare f(x,y), e l'istruzione sequenze

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

e

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

rappresentare avanzare x o y un'unità (in sx o sy direzione), con conseguente effetto sul valore della funzione. Come notato prima, lo f(x,y) è zero per i punti sulla linea; è positivo per i punti su un lato della linea e negativi per quelli sull'altro. I test if determinano se l'avanzamento di x rimarrà più vicino alla linea desiderata rispetto all'avanzamento di y o viceversa o entrambi.

L'inizializzazione err = dx - dy; è progettata per ridurre al minimo l'errore di offset; se esplodi la tua scala di tracciamento, vedrai che la tua linea calcolata potrebbe non essere centrata sulla linea desiderata con diverse inizializzazioni.

Answer 2

Voglio solo aggiungere un po 'di informazioni "perché" alla risposta eccellente di jwpat.

Il punto di utilizzo della formulazione f(x) = dy*x - dx*y + c è di velocizzare il calcolo. Questa formulazione utilizza l'aritmetica intera (più veloce), mentre la tradizionale formulazione y = mx + b utilizza l'aritmetica in virgola mobile (più lenta).