Διαφορά μεταξύ του DDA και του αλγορίθμου του Bresenham Η διαφορά μεταξύ των
ο Αλγόριθμος του Bresenhams είναι οι αλγόριθμοι σχεδίασης ψηφιακών γραμμών και χρησιμοποιούνται σε γραφικά υπολογιστών για την κατάρτιση εικόνων. Προηγουμένως, χρησιμοποιούσαμε αναλυτικούς αναλυτές για να υπολογίσουμε τα εικονοστοιχεία και έτσι έγιναν δυνατά σχέδια γραμμών. Αλλά αυτές οι αναλυτικές μέθοδοι δεν είναι τόσο ακριβείς όσο οι ψηφιακές μέθοδοι που με τη χρήση αυτών των ψηφιακών αλγορίθμων τώρα και όπως συμβαίνει με κάθε πεδίο, επινοούμε μεθόδους υψηλότερης ποιότητας και στα γραφικά των υπολογιστών. Η εφεύρεση αυτών των αλγορίθμων είναι ένα τέλειο παράδειγμα. Πριν προχωρήσουμε, ας δούμε την ιδέα πίσω από αυτούς τους αλγορίθμους. Παρόλο που φαίνεται ότι δεν εμπίπτει στο πεδίο της συζήτησής μας, είναι σημαντικό να επισημάνουμε τις βασικές διαφορές μεταξύ των δύο. Εάν γνωρίζετε πραγματικά τους αλγόριθμους, μπορείτε να μεταβείτε στις πραγματικές διαφορές που βρίσκονται στο τέλος αυτής της σελίδας.
Τι είναι ο Ψηφιακός Διαφορικός Αλγόριθμος (DDA);
Μια DDA χρησιμοποιείται κυρίως για την σχεδίαση γραμμών σε γραφικά υπολογιστή και χρησιμοποιεί πραγματικές τιμές, ενώ προβλέπει τις επόμενες τιμές εικονοστοιχείων. Ας υποθέσουμε ότι η αρχική τιμή εικονοστοιχείου ως (X0, Y0) (X0, Y0) και το εικονοστοιχείο προορισμού ως (X1, Y1) (X1, Y1). Θα μάθουμε πώς να υπολογίζουμε τις τιμές των pixel προορισμού από την γνωστή τιμή εικονοστοιχείου (X0, Y0) (X0, Y0) όπως παρακάτω.
- Πώς να υπολογίσετε την τιμή του σημείου προορισμού χρησιμοποιώντας το DDA;
Τώρα έχουμε προσδιορίσει τη διαφορά και θα πρέπει να σχεδιάσουμε τη γραμμή κατά μήκος του άξονα x, αν το 'dx' είναι μηδέν. dx = X1 - X0
dy = Y1 - Y0 < διαφορετικά, θα πρέπει να σχεδιάσουμε την γραμμή παράλληλη προς τον άξονα y. Εδώ είναι ο πραγματικός υπολογισμός από την άποψη της γλώσσας του υπολογιστή.
(Dx)> απόλυτη (dy))
βήματα = απόλυτη (dx); άλλο
Βήματα = απόλυτα (dy);Βήμα-3:
Τώρα, ήρθε η ώρα να προσδιορίσετε την τρέχουσα συντεταγμένη «x» ή τις συντεταγμένες «y» συντεταγμένων εικονοστοιχείων για να σχεδιάσετε τη γραμμή.
Χ προσαύξηση = dx / (float) βήματα.
Ενίσχυση Y = βήματα dy / (float)
Βήμα-4: Αυτό πρέπει να υπολογιστεί μέχρι να φτάσουμε στο pixel προορισμού. Ο αλγόριθμος DDA στρογγυλοποιεί την τιμή του εικονοστοιχείου στην πλησιέστερη ακέραια τιμή ενώ κάνει τον υπολογισμό. Εδώ είναι το δείγμα κώδικα αυτού που έχουμε συζητήσει τώρα.
Για (int v = 0, v <βήματα, v ++)
{ x = x +
y = y + αύξηση Y, putpixel (Γύρος (x), Γύρος (y));
}
Τελειώσαμε να σχεδιάζουμε τη γραμμή χρησιμοποιώντας το DDA και ας προχωρήσουμε τώρα στο Bresenham's!
Τι είναι ο αλγόριθμος του Bresenham;
Είναι επίσης ένας αλγόριθμος σχεδίασης ψηφιακής γραμμής και εφευρέθηκε από το Bresenham το έτος 1962 και γι 'αυτό έχει το ίδιο όνομα. Αυτός ο αλγόριθμος είναι πιο ακριβής και χρησιμοποίησε την αφαίρεση και την προσθήκη στον υπολογισμό της τιμής των εικονοστοιχείων κατά την κατάρτιση της γραμμής. Η ακρίβεια του αλγόριθμου του Bresenham είναι αξιόπιστη, ενώ ταυτόχρονα σχεδιάζει καμπύλες και κύκλους. Ας δούμε πώς λειτουργεί αυτός ο αλγόριθμος.
Βήμα-1:
Οι αλγόριθμοι του Bresenham υποθέτουν την αρχική συντεταγμένη των εικονοστοιχείων ως (x
a + 1
, y
a
). Βήμα 2: Αυτό υπολογίζει αυτόματα την επόμενη τιμή pixel ως (x a + 1 , y a + 1
και ο αλγόριθμος το υπολογίζει προσθέτοντας ή αφαιρώντας τις εξισώσεις που είχε σχηματίσει. Αυτός ο αλγόριθμος υπολογίζει ακριβείς τιμές χωρίς στρογγυλοποίηση και φαίνεται πιο εύκολη! Ας υποθέσουμε τώρα τα σημεία (0, 0) και (-8, -4) και ας σχεδιάσουμε μια γραμμή μεταξύ αυτών των σημείων χρησιμοποιώντας τον αλγόριθμο του Bresenham. Λαμβάνοντας υπόψη τα δεδομένα, (x1, y1) = (0, 0) και (x2, y2) = (-8, -4). Ας υπολογίσουμε τώρα τις διαφορικές τιμές όπως παρακάτω. Δx = x2-x1 = -8-0 = 8
Επομένως, η επαυξητική τιμή για το x = Δx / x2 = 8 / -8 = -1.
- Δy = y2-y1 = -4-0 = 4
Επομένως, η αυξητική τιμή για y = Δy / y2 = 4 / -4 = -1.
Η μεταβλητή απόφασης = e = 2 * (Δy) - (Δx)
Επομένως, e = 2 * (4) - (8) = 8-8 = 0
μας καταγράφουμε τις προκύπτουσες τιμές. Οι τιμές της συντεταγμένης y προσαρμόζονται με βάση μια μεταβλητή απόφασης και απλώς αγνοούμε τον υπολογισμό της εδώ.
Pixel
x
y
Μεταβλητή απόφασης
(0, 0)
0
| 0 | 0 | 1 | 0 |
| Μια τιμή | (- 2, -1) | -2 | -1 |
| Μια τιμή | (- 4, -2) | -4 | -2 |
| 0 | > -2 | Μια τιμή | (- 6, -3) |
| -6 | -3 | 0 | -3 |
| Αξία | (- 8, -4) | -8 | -4 |
| 0 | Η DDA χρησιμοποιεί πραγματικές τιμές στους υπολογισμούς της με τη χρήση πλωτών σημείων. Οι επόμενες τιμές εικονοστοιχείων ή σημείων προσδιορίζονται με διαφορικές εξισώσεις | X increment = dx / (float) βήματα | |
| Y increment = dy / (float) | Εδώ δεν χρησιμοποιούνται σταθερές σταθερές αλλά στα σταθερά σημεία του αλγόριθμου Bresenham χρησιμοποιούνται σε αριθμητικούς υπολογισμούς. Ο αλγόριθμος του Bresenham χρησιμοποιεί αριθμητική ακεραιότητα, σε αντίθεση με την DDA. | Τύπος ενέργειας που χρησιμοποιείται: | Το DDA επιλύει τις διαφορικές εξισώσεις με πολλαπλασιασμό και διαίρεση. Θα μπορούσατε να παρατηρήσετε το ίδιο εδώ, X increment = dx / (float) βήματα. Ο αλγόριθμος του Bresenham χρησιμοποιεί λειτουργίες προσθήκης και αφαίρεσης και μπορείτε να το παρατηρήσετε στην επόμενη εξίσωση υπολογισμού εικονοστοιχείων (x |
| a + 1 | , y | a + 1 | ). Η αριθμητική είναι απλούστερη στο Bresenham σε σύγκριση με το DDA. |
| Αποδοτικότητα: | Όπως έχουμε συζητήσει προηγουμένως, ο αλγόριθμος του Bresenham χρησιμοποιεί απλούστερη αριθμητική από την DDA και οδηγεί σε αποτελεσματικά αποτελέσματα. | Ταχύτητα: | Καθώς η DDA χρησιμοποιεί ακεραίους με κυμαινόμενο σημείο μαζί με πολλαπλασιασμό και διαιρέσεις, είναι συγκριτικά πιο αργή ενώ ο αλγόριθμος του Bresenham χρησιμοποιεί μόνο ακέραια αριθμητική μαζί με προσθήκες και αφαιρέσεις μόνο του. Αυτό μειώνει σημαντικά το χρόνο που απαιτείται για τους υπολογισμούς του και ως εκ τούτου είναι ταχύτερο από το DDA. |
Ακρίβεια: Αν και η DDA χρησιμοποιεί τιμές κυμαινόμενου σημείου, η ακρίβεια του DDA δεν είναι τόσο καλή όσο το Bresenham's. Μια ποικιλία παραγόντων επηρεάζει αυτή την έννοια και επομένως το Bresenham's είναι ακριβέστερο από το DDA.
- Στρογγυλοποίηση:
Δείτε μόνο τον υπολογισμό του DDA εδώ.
Βήματα increment = dx / (float)
Θα παρατηρήσετε το 'float' και συνεπώς δεν ολοκληρώνει τις τιμές, ενώ ο αλγόριθμος του Bresenham στρογγυλοποιεί τις τιμές στον πλησιέστερο ακέραιο αριθμό. Επομένως, οι τιμές που χρησιμοποιούνται είναι απλούστερες στον αλγόριθμο του Bresenham.
Τι αντλεί;
- Το DDA είναι ικανό να σχεδιάζει κύκλους και καμπύλες εκτός από γραμμές γραμμής. Ο αλγόριθμος του Bresenham είναι επίσης ικανός να αντλεί όλα αυτά που αναφέρονται παραπάνω και η ακρίβειά του είναι πραγματικά υψηλότερη από αυτή του DDA. Ομοίως, ο αλγόριθμος του Bresenham θα μπορούσε να παρουσιάσει αποτελεσματικές καμπύλες από αυτές που παράγει η DDA. Και οι δύο αλγόριθμοι μπορούν να σχεδιάσουν τρίγωνα και πολύγωνα.
Ποιο είναι ακριβό; Καθώς η DDA περιλαμβάνει και στρογγυλοποίηση, είναι δαπανηρή από τη χρήση του αλγορίθμου του Bresenham. Ποιος είναι ένας βελτιστοποιημένος αλγόριθμος; Από την παραπάνω συζήτησή μας, είναι πολύ σαφές ότι ο αλγόριθμος του Bresenham είναι βελτιστοποιημένος όσον αφορά την ταχύτητα, το κόστος και τη χρήση των λειτουργιών. Ας δούμε τις διαφορές σε μορφή πίνακα.
- S. Όχι
Διαφορές στο
- Ψηφιακός Διαφορικός Αλγόριθμος Αλγόριθμος του Bresenham
- 1. Γιατί το όνομα;
- Ακριβώς επειδή ήταν η ψηφιακή εφαρμογή των εξισώσεων, πήρε το όνομα. Ανακαλύφθηκε από τον J.E. Bresenham το 1962 και ως εκ τούτου το όνομα.
2.
Υπολογισμοί
- Περιλαμβάνει σκληρότερους υπολογισμούς.
Οι υπολογισμοί που χρησιμοποιούνται είναι πολύ απλούστεροι.
- 3.
Τύποι λειτουργιών που χρησιμοποιήθηκαν
- Χρησιμοποίησε πολλαπλασιασμούς και διαιρέσεις. Οι διαφορικές εξισώσεις δειγμάτων που χρησιμοποιούνται εδώ είναι τα βήματα Xincrement = dx / (float), τα βήματα
Yincrement = dy / (float).
Χρησιμοποιεί προσθήκες και αφαιρέσεις. Ο υπολογισμός του δείγματος εδώ μπορεί να συμβολίζεται όπως (x
