Algoritmo della linea di Bresenham: Rendering delle linee efficiente e pixel perfetto per la visione artificiale

Di Fouad Sabry

Che cos'è l'algoritmo della linea di Bresenham

L'algoritmo della linea di Bresenham è un algoritmo di disegno di linee che determina i punti di un raster n-dimensionale che dovrebbero essere selezionati per formare una chiusura approssimazione ad una retta tra due punti. È comunemente usato per disegnare primitive di linea in un'immagine bitmap, poiché utilizza solo addizione, sottrazione e spostamento di bit di numeri interi, che sono tutte operazioni molto economiche nelle architetture di computer storicamente comuni. È un algoritmo di errore incrementale e uno dei primi algoritmi sviluppati nel campo della computer grafica. Per disegnare cerchi è possibile utilizzare un'estensione dell'algoritmo originale chiamato algoritmo del cerchio del punto medio.

Come trarne vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Algoritmo della linea di Bresenham

Capitolo 2: Algoritmo del disegno della linea

Capitolo 3: Algoritmo della linea di Xiaolin Wu

Capitolo 4: Analizzatore differenziale digitale (algoritmo grafico)

Capitolo 5: Algoritmo del cerchio del punto medio

Capitolo 6: Regola della catena

Capitolo 7: Derivata

Capitolo 8: Pendenza

Capitolo 9: Calcolo differenziale

Capitolo 10: Algoritmi di tracciamento per l'insieme di Mandelbrot

(II) Risposte al pubblico domande principali sull'algoritmo della linea di Bresenham.

(III) Esempi reali dell'utilizzo dell'algoritmo della linea di Bresenham in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di algoritmo della linea Bresenham.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 5 mag 2024

Anteprima del libro

Capitolo 1: Algoritmo di linea di Bresenham

L'algoritmo di linea di Bresenham è una procedura di disegno al tratto che identifica i punti raster n-dimensionali che devono essere selezionati per approssimare una linea retta tra due punti. Viene spesso utilizzato per disegnare primitive di linea in un'immagine bitmap (ad esempio, sullo schermo di un computer) poiché richiede solo l'addizione di numeri interi, la sottrazione e lo spostamento di bit, che sono tutte operazioni abbastanza economiche nelle architetture di computer storicamente prevalenti. È uno dei primi algoritmi creati nel campo della computer grafica ed è un algoritmo di errore incrementale. Una modifica dell'algoritmo originale può essere utilizzata per creare cerchi.

Mentre le tecniche in grado di antialiasing come l'algoritmo di Wu sono ampiamente utilizzate anche nella moderna computer grafica, l'algoritmo di linea di Bresenham rimane significativo grazie alla sua velocità e semplicità. L'algoritmo è utilizzato nei plotter e nei chip grafici delle schede grafiche contemporanee. Presente anche in numerose librerie di grafica software. A causa della sua semplicità, l'algoritmo viene spesso implementato nell'hardware grafico o nel firmware delle schede grafiche attuali.

Oggi, il termine Bresenham si riferisce a una famiglia di algoritmi che estendono o alterano l'approccio originale di Bresenham.

L'algoritmo di linea di Bresenham prende il nome da Jack Elton Bresenham, il dipendente IBM che lo creò nel 1962. Nel 2001, Bresenham ha pubblicato:

Lavoravo nel laboratorio di calcolo del laboratorio di sviluppo IBM di San Jose. Attraverso il terminale della macchina da scrivere 1407, un plotter Calcomp era collegato a un IBM 1401. L'algoritmo fu utilizzato in produzione nell'estate del 1962, o forse un mese prima. Calcomp (Jim Newland e Calvin Heft) aveva copie dei programmi perché le aziende li condividevano apertamente all'epoca. Quando tornai a Stanford nell'autunno del 1962, ne donai una copia alla biblioteca del centro di calcolo di Stanford. Alla convention nazionale dell'ACM del 1963 a Denver, in Colorado, fu accettata una descrizione della routine di disegno al tratto. In quell'anno, solo l'agenda dei relatori e gli argomenti furono pubblicati in un numero di Comunicazioni dell'ACM. Dopo la mia presentazione, qualcuno dell'IBM Systems Journal mi ha chiesto se potevano pubblicare il lavoro. Acconsentii volentieri e fu pubblicato nel 1965.

L'approccio di Bresenham è stato ampliato per generare cerchi, ellissi, curve di Bézier cubiche e quadratiche, nonché versioni native anti-aliasing di queste curve.

Verranno utilizzate le convenzioni successive:

La coordinata in alto a sinistra è (0,0), in modo tale che le coordinate dei pixel crescano nelle direzioni destra e in basso (ad esempio, il pixel in (7,4) è direttamente sopra il pixel in (7,5)), mentre la coordinata in basso a destra è (1,1).

I centri dei pixel hanno coordinate intere.

I punti finali della linea sono i pixel in corrispondenza (x_{0},y_{0}) e (x_{1},y_{1}) , dove la prima coordinata rappresenta la colonna e la seconda coordinata rappresenta la riga.

L'algoritmo verrà inizialmente presentato solo per l'ottante in cui il segmento scende e verso destra ( x_{0}\leq x_{1} e y_{0}\leq y_{1} ), e la sua proiezione orizzontale x_{1}-x_{0} è più lunga della proiezione verticale y_{1}-y_{0} (la linea ha una pendenza positiva inferiore a 1).

In questo ottavo, per ogni colonna x compresa tra x_{0} e x_{1} , La tecnica calcola esattamente una riga y che contiene un pixel della linea, mentre ogni riga compresa tra y_{0} e y_{1} può contenere più pixel rasterizzati.

La tecnica di Bresenham seleziona l'intero y che corrisponde al centro del pixel più vicino all'ideale (frazionario) y per lo stesso x; Nelle colonne successive, y può rimanere invariato o aumentare di 1. L'equazione generale della retta che passa per i punti finali è:

{\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} .

Poiché abbiamo la colonna, x, possiamo ottenere la riga del pixel, y, arrotondando questo numero all'intero più vicino:

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}

.

La pendenza (y_{1}-y_{0})/(x_{1}-x_{0}) dipende solo dalle coordinate del punto finale e può essere precalcolata, e l'ideale y per i valori interi successivi di x può essere calcolato a partire dalla y_{0} pendenza e aggiungendo ripetutamente.

In pratica, l'algoritmo non mantiene le informazioni sulle coordinate y, che aumentano di m = ∆y/∆x ogni volta che la x aumenta di uno; Mantiene un limite di errore a ogni livello, che mostra la distanza tra (a) il punto in cui la linea esce dal pixel e (b) il bordo superiore del pixel.

Questo valore viene prima impostato su {\displaystyle y_{0}-0.5} (a causa dell'utilizzo delle coordinate centrali del pixel), ogni volta che la coordinata x viene incrementata di uno, m viene aggiunto.

Ogni volta che l'imprecisione è maggiore di 0,5, siamo consapevoli che la linea si è spostata di un pixel verso l'alto, dobbiamo incrementare la coordinata y e sottrarne una dall'errore per riflettere la distanza dalla parte superiore del nuovo pixel.

L'algoritmo di Bresenham deve essere derivato in due passaggi. La prima fase consiste nel tradurre la forma dell'equazione di una retta in una forma diversa, e quindi utilizzare questa nuova equazione per tracciare una linea basata sul concetto di accumulo di errori.

La forma dell'intercetta di pendenza di una linea è scritta come

y=f(x)=mx+b

dove m è la pendenza e b è l'intercetta y.

Poiché questa è una funzione di solo x , non può simboleggiare una linea verticale.

Pertanto, sarebbe utile rendere questa equazione scritta in funzione di entrambi x e y , in grado di disegnare linee con qualsiasi angolo.

L'angolo (o pendenza) di una linea può essere indicato come salita su corsa o . \Delta y/\Delta x

Quindi, usando operazioni algebriche,

{\begin{aligned}y&=mx+b\\y&={\frac {(\Delta y)}{(\Delta x)}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}

Lasciando che quest'ultima equazione sia una funzione di x e y , può anche essere scritto come

{\displaystyle f(x,y):=Ax+By+C=0}

dove si trovano le costanti

{\displaystyle A=\Delta y=y_{1}-y_{0}}{\displaystyle B=-\Delta x=-(x_{1}-x_{0})}{\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}

La linea viene quindi definita per alcune costanti A , B , e C ovunque f(x,y)=0 .

Cioè, per tutti coloro che (x,y) non sono in linea, f(x,y)\neq 0 .

Questa forma coinvolge solo i numeri interi se x e y sono interi, poiché le costanti A , B , e C sono definite come interi.

Ad esempio, la riga {\textstyle y={\frac {1}{2}}x+1} potrebbe essere scritta come f(x,y)=x-2y+2 .

Il punto (2,2) è in gioco.

f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0

Inoltre, il punto (2,3) non è in discussione.

f(2,3)=(2)-2(3)+2=2-6+2=-2

nessuno dei due è il punto (2,1)

f(2,1)=(2)-2(1)+2=2-2+2=2

Si noti che i punti (2,1) e (2,3) si trovano sui lati opposti della linea e f(x,y) valutano positivo o negativo.

Una linea divide un piano a metà e il mezzo piano che ha un f(x,y) negativo può essere chiamato semipiano negativo, l'altra metà è nota come semipiano positivo.

Questa osservazione è cruciale per il resto della derivazione.

Ovviamente, il punto di partenza è sulla linea.

f(x_{0},y_{0})=0

Solo perché la linea è definita per iniziare e terminare in coordinate intere può essere disegnata (anche se è del tutto ragionevole voler disegnare una linea con punti finali non interi).

Tenendo presente che la pendenza è al massimo 1 , si pone ora il problema se il punto successivo debba essere a (x_{0}+1,y_{0}) o (x_{0}+1,y_{0}+1) .

Forse intuitivamente, il punto dovrebbe essere scelto in base a quale è più vicino alla linea in x_{0}+1 .

Se è più vicino al punto precedente, aggiungilo sulla linea, se il secondo allora il secondo.

Per risolvere questo problema, valutare la funzione di linea tra queste due posizioni:

{\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}

Se il valore di questo è positivo, allora la linea ideale è al di sotto del punto medio e più vicina al punto candidato (x_{0}+1,y_{0}+1) ; Di conseguenza, la coordinata y è andata avanti.

In caso contrario, la linea ottimale si trova a metà o al di sopra di essa, inoltre la coordinata y non si è spostata; in questo caso scegliere il punto (x_{0}+1,y_{0}) .

In questo punto medio, il valore della funzione linea è l'unico determinante di quale punto deve essere scelto.

La figura a destra mostra il punto selezionato (2,2) in blu, insieme a due punti potenziali (3,2) in verde (3,3). Il punto nero (3, 2,5) si trova al centro dei due punti candidati.

Invece di valutare f(x,y) nei punti medi, in alternativa, si può utilizzare la differenza tra i punti. Questo metodo alternativo consente l'aritmetica solo intera, che è