Differenza tra DDA e Bresenham's Algorithm

Digital Differential Algorithm (DDA) e l'Algorithm di Bresenhams sono gli algoritmi di disegno di linee digitali e sono utilizzati in computer grafica per disegnare immagini. In precedenza, stavamo usando analizzatori analitici per calcolare i pixel e quindi i disegni lineari erano resi possibili. Ma questi metodi analitici non sono accurati come i metodi digitali che con l'uso di questi algoritmi digitali ora e come in ogni campo, abbiamo anche inventato metodi di alta qualità in computer grafica. L'invenzione di questi algoritmi è un esempio perfetto. Prima di procedere, esaminiamo il concetto alla base di questi algoritmi. Anche se sembra fuori dalla portata della nostra discussione, è essenziale sottolineare le differenze fondamentali tra i due. Se hai davvero familiarità con gli algoritmi, puoi saltare alle differenze effettive situate alla fine di questa pagina.

Che cos'è Digital Differential Algorithm (DDA)?

Un DDA è usato principalmente per disegnare linee in computer grafica e usa valori reali mentre predice i valori dei pixel successivi. Assumiamo il valore iniziale del pixel come (X0, Y0) (X0, Y0) e il pixel di destinazione come (X1, Y1) (X1, Y1). Impareremo come calcolare i valori dei pixel di destinazione dal valore di pixel noto (X0, Y0) (X0, Y0) come sotto.

  • Come calcolare il valore del punto di destinazione usando DDA?

Step-1: Qui abbiamo l'input (X0, Y0) (X0, Y0) e dovremmo identificare se la linea è parallela all'asse x o all'asse y . Per trovarlo, calcoliamo ora la differenza tra i valori dei pixel iniziale e di destinazione.

dx = X1 - X0

dy = Y1 - Y0

Step-2: Ora abbiamo identificato la differenza e dovremmo disegnare la linea lungo l'asse x se 'dx' è zero altrimenti, dovremmo disegnare la linea parallela all'asse y. Ecco il calcolo effettivo in termini di linguaggio del computer.

if (assoluto (dx)> assoluto (dy))

Passi = assoluto (dx);

altro

Passi = assoluto (dy);

Step-3: Ora, è il momento di identificare la coordinata 'x' effettiva o la 'y' coordina i valori dei pixel per disegnare la linea.

X incrementi = dx / (float) passi;

Y incremento = dy / (float) passi;

Step-4: Questo deve essere calcolato fino a raggiungere il pixel di destinazione. L'algoritmo DDA arrotonda il valore del pixel al valore intero più vicino mentre esegue il calcolo. Ecco il codice di esempio di ciò che abbiamo discusso ora.

Per (int v = 0; v

{

x = x + X incremento;

y = y + incremento Y;

putpixel (Round (x), Round (y));

}

Abbiamo finito con il disegnare la linea usando la DDA e ora passiamo al Bresenham!

Cos'è l'algoritmo di Bresenham?

È anche un algoritmo di disegno di linee digitali ed è stato inventato da Bresenham nell'anno 1962 ed è per questo che ha lo stesso nome. Questo algoritmo è più accurato e ha utilizzato la sottrazione e l'aggiunta per calcolare il valore del pixel mentre si disegna la linea. La precisione dell'algoritmo di Bresenham è affidabile durante il disegno di curve e cerchi. Vediamo come funziona questo algoritmo.

Step-1: Gli algoritmi di Bresenham assumono la coordinata iniziale del pixel come (x a + 1 , y a ).

Passaggio 2: Calcola automaticamente il valore del pixel successivo come (x a + 1 , y a + 1 ), Qui 'a' è il valore incrementale e l'algoritmo lo calcola sommando o sottraendo le equazioni che aveva formato.

Questo algoritmo calcola valori precisi senza arrotondamenti e sembra anche più semplice!

  • Esempio numerico dell'algoritmo di Bresenham:

Consideriamo ora i punti (0, 0) e (-8, -4) e tracciamo una linea tra questi punti usando l'algoritmo di Bresenham.

Dati dati, (x1, y1) = (0, 0) e (x2, y2) = (-8, -4).

Calcoliamo ora i valori differenziali come sotto.

Δx = x2-x1 = -8-0 = 8

Pertanto, il valore incrementale per x = Δx / x2 = 8 / -8 = -1.

Δy = y2-y1 = -4-0 = 4

Pertanto, il valore incrementale per y = Δy / y2 = 4 / -4 = -1.

Variabile di decisione = e = 2 * (Δy) - (Δx)

Pertanto, e = 2 * (4) - (8) = 8-8 = 0

Con il calcolo sopra, lasciare noi tabulare i valori risultanti. I valori della coordinata y sono regolati in base a una variabile decisionale e stiamo semplicemente ignorando il suo calcolo qui.

Pixel x y Variabile di decisione
(0, 0) 0 0 0
(- 1, 0) - 1 0 Un valore
(- 2, -1) -2 -1 0
(- 3, -1) -3 < -1 Un valore (- 4, -2)
-4 -2 0 (- 5, -2)
-5 > -2 Un valore (- 6, -3) -6
-3 0 (- 7, -3) -7
-3 Un valore (- 8, -4) -8
-4 0 Differenze tra DDA e Bresenham's Algorithm :

Calcolo aritmetico: La DDA utilizza i valori reali nei suoi calcoli con l'uso di punti mobili. I successivi valori di pixel o punti sono determinati con equazioni differenziali

  • X incrementi = dx / (float) passi

Y increment = dy / (float) passi

Qui non vengono utilizzate costanti fisse ma nell'algoritmo di Bresenham punti fissi sono usati nei calcoli aritmetici. L'algoritmo di Bresenham utilizza l'aritmetica Integer, a differenza della DDA.

Tipo di operazione utilizzata:

La DDA risolve le equazioni differenziali con operazioni di moltiplicazione e divisione. Si potrebbe notare lo stesso qui, passi X incremento = dx / (float). L'algoritmo di Bresenham utilizza le operazioni di addizione e sottrazione e puoi notare lo stesso qui nella sua successiva equazione di calcolo del valore del pixel (x

  • a + 1

, y a + 1 ). L'aritmetica è più semplice in Bresenham rispetto alla DDA. Efficienza: Come abbiamo discusso in precedenza, l'algoritmo di Bresenham utilizza l'aritmetica più semplice della DDA e risulta in risultati efficienti.

  • Velocità:

Dato che DDA utilizza gli interi in virgola mobile insieme alle operazioni di moltiplicazione e divisione, è relativamente più lento mentre l'algoritmo di Bresenham utilizza solo l'aritmetica dei numeri interi insieme alle sole aggiunte e sottrazioni. Ciò riduce considerevolmente il tempo necessario per i suoi calcoli e quindi più veloce della DDA.

  • Precisione: Sebbene DDA utilizzi valori in virgola mobile, la precisione di DDA non è migliore di quella del Bresenham. Una varietà di fattori influisce su questo concetto e, pertanto, Bresenham's è più accurato del DDA.
  • Arrotondamento: Basta osservare il calcolo della DDA qui.
  • X incremento = dx / (float) passi Si potrebbe notare il 'float' e quindi non arrotondare i valori mentre l'algoritmo di Bresenham arrotonda i valori al numero intero più vicino. Pertanto, i valori utilizzati sono più semplici nell'algoritmo di Bresenham.

Che cosa disegna?

La DDA è in grado di disegnare cerchi e curve a parte le linee del disegno. L'algoritmo di Bresenham è anche in grado di disegnare tutti quelli sopra menzionati e la sua accuratezza è davvero superiore a quella della DDA. Allo stesso modo, l'algoritmo di Bresenham potrebbe fornire curve efficienti rispetto a quelle prodotte dalla DDA. Entrambi gli algoritmi possono disegnare anche triangoli e poligoni.

  • Quale è costoso?

Poiché DDA include anche arrotondamenti, è costoso rispetto all'utilizzo dell'algoritmo di Bresenham.

  • Qual è un algoritmo ottimizzato?

Dalla nostra discussione precedente, è molto chiaro che l'algoritmo di Bresenham è ottimizzato in termini di velocità, costi e utilizzo delle operazioni.

  • Vediamo le differenze in una forma tabellare.

S. No

Differenze in

Algoritmo differenziale digitale Algoritmo di Bresenham 1. Perché il nome?
Proprio perché era l'implementazione digitale delle equazioni, ha ottenuto il nome. Fu inventato da J. E. Bresenham nell'anno 1962 e da qui il nome. 2. Calcoli
Si tratta di calcoli più difficili. I calcoli utilizzati sono molto più semplici. 3. Tipi di operazioni utilizzate
Ha usato moltiplicazioni e divisioni. Le equazioni differenziali di esempio utilizzate qui sono passaggi Xincrement = dx / (float), Yincrement = dy / (float). Usa aggiunte e sottrazioni. Il calcolo del campione qui può essere denotato come (x

a + 1

, y a + 1 ). 4. Valori di calcolo aritmetico
Utilizza valori a virgola mobile. Usa solo i valori interi. 5. Efficienza
Risultati aritmetici complessi in minore efficienza. Semplici risultati aritmetici in una maggiore efficienza. 6. Velocità
L'utilizzo di moltiplicazioni e operazioni di divisione richiede molto tempo per i suoi processi di calcolo. L'utilizzo delle operazioni di addizione e sottrazione richiede meno tempo del DDA. 7. Precisione
È di precisione inferiore. È più preciso. 8. Arrotondamento
Utilizza valori reali e non arrotonda mai i valori. Arrotonda i valori ai valori interi più vicini. 9. Capacità di disegno
È in grado di disegnare linee, cerchi e curve ma con minore precisione. Possiamo anche disegnare triangoli e poligoni con questo algoritmo. È in grado di disegnare linee, cerchi e curve con maggiore efficienza. Triangoli e poligoni sono anche disegnabili con questo algoritmo. 10. Costo dei calcoli
È costoso poiché comporta anche arrotondamenti. L'utilizzo dell'algoritmo di Bresenham è più economico della DDA. 11. Algoritmo ottimizzato
Non è un algoritmo ottimizzato È un algoritmo ottimizzato. Abbiamo affrontato ogni possibile differenza tra il DDA e l'algoritmo di Bresenham. Potrebbe anche sembrare ripetitivo, ma c'è qualche motivo valido per menzionare di nuovo quei punti e verrebbe da sapere quando lo capisci completamente. Se senti ancora che esiste un'ambiguità, ti preghiamo di lasciarci un commento. Impariamo insieme condividendo la giusta conoscenza!