Algoritmo di disegno di linee: Padroneggiare le tecniche per il rendering di immagini di precisione

Di Fouad Sabry

Che cos'è l'algoritmo di disegno di linea

Nella computer grafica, un algoritmo di disegno di linea è un algoritmo per approssimare un segmento di linea su supporti grafici discreti, come display basati su pixel e stampanti. Su tali supporti, il disegno al tratto richiede un'approssimazione. Gli algoritmi di base rasterizzano le linee in un colore. Una rappresentazione migliore con più gradazioni di colore richiede un processo avanzato, l'anti-aliasing spaziale.

Come trarrai vantaggio

(I) Approfondimenti e convalide su i seguenti argomenti:

Capitolo 1: Algoritmo di disegno di linee

Capitolo 2: Algoritmo di linee di Bresenham

Capitolo 3: Algoritmo di linee di Xiaolin Wu

Capitolo 4: Analizzatore differenziale digitale (algoritmo grafico)

Capitolo 5: Algoritmo del cerchio del punto medio

Capitolo 6: Computer grafica 2D

Capitolo 7: Geometria digitale

Capitolo 8: Trasformata di Hough

Capitolo 9: Ray casting

Capitolo 10: Funzione gaussiana

(II) Rispondere alle domande più importanti del pubblico sull'algoritmo di disegno al tratto.

(III) Esempi reali dell'utilizzo dell'algoritmo di disegno al tratto 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 di disegno al tratto.

 

 

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

Anteprima del libro

Capitolo 1: Algoritmo di disegno al tratto

Un algoritmo di disegno al tratto nella grafica computerizzata è un algoritmo che approssima un segmento di linea su supporti grafici discreti, come schermi e stampanti basati su pixel. Su tali superfici, il disegno al tratto richiede un'approssimazione (in casi non banali). Semplici algoritmi rasterizzano le linee in un'unica tonalità. L'anti-aliasing spaziale è una procedura avanzata necessaria per una rappresentazione più accurata di numerose gradazioni di colore.

Su un supporto continuo, il disegno di una linea non richiede un algoritmo. Ad esempio, gli oscilloscopi a raggi catodici creano linee e curve utilizzando fenomeni analogici.

Di seguito è riportato un elenco parziale di algoritmi per il disegno di linee:

Algoritmo ingenuo

Digital Differential Analyzer (algoritmo grafico) — Paragonabile all'algoritmo naïve di disegno delle linee, con alcune lievi differenze.

L'algoritmo di linea di Bresenham è sintonizzato per impiegare solo addizioni (cioè nessuna divisione o moltiplicazione) ed evita calcoli in virgola mobile.

L'algoritmo di linea di Xiaolin Wu – che può eseguire l'anti-aliasing spaziale – sembra cordoso a causa della luminosità fluttuante lungo la lunghezza della linea; Tuttavia, questo effetto può essere significativamente ridotto al minimo pre-compensando i valori dei pixel per la curva di gamma del display di destinazione, ad esempio out = in (1/2,4).

Formula di Gupta-Spruill

Disegnare direttamente l'equazione che determina la linea è il metodo più semplice di vagliatura.

dx = x2 − x1

dy = y2 − y1

per x da x1 a x2 do

y = y1 + dy × (x − x1) / dx

Traccia(x, y)

È qui che i punti sono già stati ordinati in modo che x_{2}>x_{1} .

Questo algoritmo funziona bene quando {\displaystyle dx\geq dy} (cioè il gradiente è minore o uguale a 1), ma se dx

L'algoritmo primitivo per disegnare le linee è inefficiente e di conseguenza lento su un computer digitale. La quantità di operazioni e l'uso di calcoli a virgola mobile contribuiscono alle sue inefficienze. Invece, sono favoriti algoritmi come l'algoritmo di linea di Bresenham o l'algoritmo di linea di Xiaolin Wu.

Basato sull'algoritmo di linea di Bresenham, l'algoritmo di Gupta-Sproll aggiunge l'antialiasing.

Lo pseudocodice per una forma ottimizzata dell'algoritmo di Gupta-Sproull è il seguente:

DrawLine(x1, x2, y1, y2) {

x = x1;  y = y1;  dx = x2 − x1;  dy = y2 − y1;  d = 2 * dy − dx; discriminatore

Distanza euclidea del punto (x,y) dalla retta (con segno)

D = 0;  Distanza euclidea tra i punti (x1, y1) e (x2, y2)

lunghezza = sqrt(dx * dx + dy * dy);  sin = dx / lunghezza;  cos = dy / lunghezza;  while (x <= x2) {

IntensificarePixel(x, y − 1, D + cos);  IntensificaPixel(x, y, D);  IntensificarePixel(x, y + 1, D − cos);  x = x + 1

if (d <= 0) {

D = D + sin;  d = d + 2 * dy;  } else {

D = D + sin − cos;  d = d + 2 * (dy − dx);  y = y + 1; } }}

La funzione IntensifyPixel(x,y,r) accetta una trasformazione di linea radiale e imposta l'intensità del pixel (x,y) con un polinomio cubico il cui valore dipende dalla distanza del pixel r dalla linea.

{Fine Capitolo 1}

Capitolo 2: 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