 |
 |
| 2 | 'ΓΡΑΦΙΚΑ ΚΑΙ ΕΙΚΟΝΙΚΗ ΠΡΑΓΜΑΤΙΚΟΤΗΤΑ' | Μουστάκας Κ., Παλιόκας Ι., Τσακίρης Α., Τζοβάρας Δ. |
|
|
Πατήστε πάνω στους τίτλους των υποκεφαλαίων ή μεταφερθείτε στην αρχική σελίδα.
|
2015 |
|
ΚΕΦΑΛΑΙΟ 2: ΣΧΕΔΙΑΣΗ
|
|
|
ΣύνοψηΣτον τομέα των γραφικών, υπάρχει από τη μια μεριά η μαθηματική περιγραφή των σχημάτων που χαρακτηρίζεται από την ανάλογη αυστηρότητα και από την άλλη οι περιορισμοί της πλεγματικής οθόνης πάνω στην οποία τελικά θα γίνει η σχεδίαση. Στο κεφάλαιο αυτό γίνεται ανάλυση αυτών των περιορισμών της πλεγματικής οθόνης σε σχέση με τις ανάγκες σχεδίασης. Θα μελετηθούν οι πιο γνωστοί αλγόριθμοι σχεδίασης βασικών σχημάτων, όπως είναι το ευθύγραμμο τμήμα, ο κύκλος, τα πολύγωνα και οι ελεύθερες καμπύλες. Τα τρίγωνα και άλλα πολύγωνα προσεγγίζονται σχεδιαστικά με την επαναληπτική εφαρμογή των αλγορίθμων σχεδίασης ευθύγραμμων τμημάτων. Οι καμπύλες περιγράφονται ως καμπύλες Bezier και τα κλειστά σχήματα γεμίζονται με χρώμα, ενώ ελέγχεται αν κάθε εικονοστοιχείο βρίσκεται εντός ή εκτός του κλειστού σχήματος. Τα παραπάνω σε συνδυασμό με τις τεχνικές αντι-ταύτισης ολοκληρώνουν το κεφάλαιο δίνοντας μια πλήρη εικόνα της σύγχρονης στάθμης της τεχνικής αναφορικά με το πρόβλημα της σχεδίασης. Προαπαιτούμενη γνώσηΓνώσεις μαθηματικής περιγραφής των βασικών σχημάτων (παραμετρικές εξισώσεις). Βασικές γνώσεις δομών δεδομένων όπως λίστες, πίνακες, κτλ. Άνεση στην ανάγνωση κώδικα για την κατανόηση των αλγοριθμικών λύσεων που προτείνονται. |
Στον τομέα των γραφικών, υπάρχει από τη μια μεριά η μαθηματική περιγραφή των σχημάτων που έχει την ανάλογη αυστηρότητα και από την άλλη οι περιορισμοί της πλεγματικής οθόνης πάνω στην οποία τελικά θα γίνει η σχεδίαση. Η οθόνη συμμετέχει στο πρόβλημα της σχεδίασης ως καμβάς πάνω στον οποίο θα σχηματιστούν οι μορφές κάθε σκηνής. Από πρακτικής πλευράς, η οθόνη προσεγγίζεται με έναν ορθογωνικό πίνακα εικονοστοιχείων πάνω στον οποίο οι αλγόριθμοι σχεδίασης εξάγουν τα αποτελέσματά τους με γνώμονα την προσεγγιστική ακρίβεια και την αποδοτικότητα.
Από την πλευρά της πρακτικής χρήσης των τεχνικών που θα μελετηθούν, πολλά από τα θέματα που πραγματεύεται αυτό το κεφάλαιο, όπως για παράδειγμα οι αλγόριθμοι σχεδίασης, θεωρούνται ήδη υλοποιημένα στα σύγχρονα συστήματα γραφικών και τα διαθέσιμα προγραμματιστικά εργαλεία που έχει για χρήση ο προγραμματιστής, προσφέρουν έτοιμες συναρτήσεις σχεδιασμού. Το αντικείμενο της αλγοριθμικής της σχεδίασης προσεγγίζεται για ακαδημαϊκούς λόγους, ενώ η γνώση που προκύπτει από την τριβή με το συγκεκριμένο αντικείμενο θεωρείται προθάλαμος για πιο πολύπλοκες διαδικασίες της γραφικής με υπολογιστές. Επιπρόσθετα, η γνώση αυτή μπορεί να φανεί χρήσιμη μελλοντικά στην κατανόηση πιο σύνθετων προβλημάτων και των προτεινόμενων λύσεών τους.
Οι οθόνες είναι δισδιάστατες επιφάνειες πάνω στις οποίες προβάλλεται η οπτική πληροφορία. Έχουν πεπερασμένες διαστάσεις και συγκεκριμένες τεχνικές προδιαγραφές (π.χ. μέγιστη ανάλυση). Έτσι, λοιπόν, μοιάζουν σαν ένα πλέγμα από εικονοστοιχεία ή αλλιώς pixels (Picture Element) με το καθένα να είναι χρωματικά ανεξάρτητο από τα υπόλοιπα. Το πρόβλημα της σχεδίασης ξεκινάει από την ανάγκη να αναπαρασταθούν σχήματα στις πλεγματικές οθόνες λαμβάνοντας υπόψη τους περιορισμούς που αναφέρθηκαν παραπάνω. Ένα υπολογιστικό σύστημα δεν έχει όλους τους πόρους και τις δυνατότητες που θα θέλαμε για να αναπαραστήσει ένα ευθύγραμμο τμήμα, έναν κύκλο ή μια ελεύθερη καμπύλη. Η προβληματική της σχεδίασης αναφέρεται στην επιλογή ενός υποσυνόλου από τα διαθέσιμα εικονοστοιχεία της οθόνης τα οποία σε κάθε στιγμή (καρέ) θα πρέπει να επιλεγούν, ώστε να αποδοθεί σε αυτά ένας διαφορετικός χρωματισμός από τα άλλα εικονοστοιχεία που αναπαριστούν το υπόβαθρο. Στην πιο απλή μορφή υπάρχει σε ένα περιβάλλον μονοχρωματικής απεικόνισης βασικών σχημάτων όπου το υπόβαθρο είναι λευκού χρώματος, ενώ στα εικονοστοιχεία που ανήκουν στο απεικονιζόμενο σχήμα αποδίδεται το μαύρο χρώμα.
Το ανθρώπινο οπτικό σύστημα χρειάζεται έναν μεγάλο αριθμό από εικονοστοιχεία για να αντιληφθεί μια εικόνα με ενιαίο τρόπο. Η ανάλυση της οθόνης φτάνει σήμερα στα επίπεδα της υψηλής και πολύ υψηλής ανάλυσης (HD) και ένα πλήθος εικονοστοιχείων 1920 στο πλάτος επί 1080 στο ύψος θεωρείται συνηθισμένο για ένα μέτριο υπολογιστικό σύστημα γραφείου. Επίσης, τα εικονοστοιχεία δεν είναι πάντοτε τετραγωνικά, αλλά χαρακτηρίζονται από το λόγο διάστασης που εκφράζει το κατά πόσο πλησιάζει το σχήμα του ένα κανονικό τετράγωνο. Για παράδειγμα, ένας λόγος 1.2:1, δηλώνει ότι το πλάτος του εικονοστοιχείου είναι 1.2 φορές πιο μεγάλο από το ύψος του.
Στην Εικόνα 2.1, απεικονίζεται ένα παράδειγμα μονοχρωματικής εικόνας σε άσπρο-μαύρο και ο αντίστοιχος πίνακας με τις τιμές των εικονοστοιχείων της. Επειδή το βάθος χρώματος της εικόνας είναι 1, οι πιθανές τιμές που προκύπτουν για το χρώμα είναι 0 ή 1. Το 0, συνήθως, αντιστοιχεί στο λευκό το οποίο εδώ εξυπηρετεί ως χρώμα υποβάθρου, ενώ το 1 αντιστοιχεί στο μαύρο το οποίο χρησιμοποιείται ως χρώμα για τα περιγράμματα των σχημάτων, αλλά και ως χρώμα γεμίσματος. Σε μια εικόνα που αποδίδεται σε κλίμακα του γκρι, στον πίνακα bitmap εισάγονται τιμές χρώματος 8 bit που κυμαίνονται στο διάστημα [0, 255]. Τα περισσότερα από τα παραδείγματα του κεφαλαίου βασίζονται σε μονοχρωματικές εικόνες ή εικόνες στην κλίμακα του γκρι. Για μεγαλύτερα βάθη χρώματος, το μήκος της λέξης του χρώματος αυξάνεται έως τα 64bit (48bit για το χρώμα και 16bit για το alpha channel).
 |
Εικόνα 2.1. Μια μονοχρωματική εικόνα (δεξιά) και ο αντίστοιχος πίνακας τιμών (αριστερά)
Ένα δεύτερο μεγάλο θέμα που απασχολεί τη σχεδίαση στον υπολογιστή είναι η αντιστοίχιση των μαθηματικά ορισμένων σημείων πάνω στην οθόνη, με δεδομένο ότι τα εικονοστοιχεία έχουν κάποιο σεβαστό μέγεθος. Στη θέση της οθόνης θεωρούμε ένα δισδιάστατο ορθογωνικό πλέγμα τετραγωνικών εικονοστοιχείων, το κέντρο των οποίων μπορεί να είναι είτε πάνω στις ακέραιες συντεταγμένες είτε πάνω σε ημίσειες συντεταγμένες. Στην πρώτη περίπτωση, το κάτω αριστερά εικονοστοιχείο (που συχνά θεωρείται το ‘μηδενικό’ εικονοστοιχείο καθώς βρίσκεται κοντά στο κέντρο των ημιαξόνων που ορίζουν το δισδιάστατο χώρο), έχει συντεταγμένες [0, 0], ενώ στη δεύτερη περίπτωση έχει συντεταγμένες [0.5, 0.5]. Σε κάποιο άλλο σύστημα αναφοράς που θεωρεί αντεστραμμένο τον άξονα των Y, το μηδενικό εικονοστοιχείο βρίσκεται πάνω αριστερά, όπως συμβαίνει συχνά σε περιβάλλοντα ψηφιακής επεξεργασίας εικόνας. Για λόγους απλότητας, στη συνέχεια του βιβλίου θα θεωρείται ότι τα εικονοστοιχεία έχουν ακέραιες συντεταγμένες στο ορθοκανονικό σύστημα αναφοράς (xΟy) και ότι κάθε εικονοστοιχείο καλύπτει επιφάνεια από (x-0.5, y-0.5) έως (x+0.5, y+0.5) όπως φαίνεται στην Εικόνα 2.2.
Εικόνα 2.2. Πλεγματική οθόνη όπου τα εικονοστοιχεία έχουν ακέραιες συντεταγμένες
Οι ποιοτικοί παράγοντες που χαρακτηρίζουν κάθε λύση του προβλήματος της σχεδίασης είναι η ακρίβεια και η απόδοση. Με λίγα λόγια, αυτό που καθιστά μια μέθοδο ή έναν αλγόριθμο σχεδίασης προτιμητέο από κάποιον άλλον είναι: α. η δυνατότητα σχεδίασης όσο το δυνατόν πιο κοντά στην πραγματικότητα (στην ελάχιστη δυνατή απόσταση από την μαθηματικά ορισμένη πραγματικότητα), β. η ταχύτητα σχεδίασης (αποδοτικότητα) και γ. η ελαχιστοποίηση της κατανάλωσης πόρων (π.χ. μνήμη RAM). Σε ένα βιντεοπαιχνίδι για παράδειγμα, είναι επιθυμητό η σχεδίαση πολύπλοκων σκηνών που αποτελούνται από πολλά σχήματα και χρώματα, να γίνεται σε πραγματικό χρόνο που σημαίνει τουλάχιστον 25 με 30 fps (frames per second).
Αν για μια συνάρτηση δύο μεταβλητών f(x,y) θεωρηθεί ότι ισχύει η ισότητα με το μηδέν, τότε μπορεί για ένα δεδομένο χ0 να υπολογιστεί μέσα από τη σχέση f(x,y)=0, μία τιμή για το y0. Με την επανάληψη αυτής της διαδικασίας για τα σημεία ενός συνόλου τιμών Α, ορίζεται μια συνάρτηση f(x,y)=0 που ονομάζεται Πεπλεγμένη συνάρτηση.
Ωστόσο, ο προαναφερόμενος δεν είναι ο μόνος τρόπος να οριστεί ένα σχήμα. Αν τα x και y μπορούν να εκφραστούν με συναρτήσεις μιας ανεξάρτητης μεταβλητής t, δηλαδή x=f(t) και y=g(t), τότε το παραπάνω ζεύγος εξισώσεων ονομάζεται παραμετρική εξίσωση της καμπύλης C. Γενικά, ο παραμετρικός ορισμός καμπυλών παρουσιάζει ορισμένα πλεονεκτήματα, όπως η δυνατότητα περιγραφής κλειστών καμπυλών, η δυνατότητα επέκτασης σε περισσότερες διαστάσεις (π.χ. από τις δισδιάστατες καμπύλες στις τρισδιάστατες), ευκολότερη χρήση συσχετισμένων μετασχηματισμών (λόγω ανεξαρτησίας των συντεταγμένων) και ανεξαρτησία από το ίδιο το σύστημα συντεταγμένων.
Στην απλή περίπτωση της ευθείας, αυτή μπορεί να οριστεί είτε από δύο σημεία P1 και P2 (Εικόνα 2.3), είτε από ένα σημείο P και ένα διάνυσμα, ή συντελεστή διεύθυνσης, ενώ μπορεί ακόμη να οριστεί με βάση μια άλλη ευθεία. Κάθε ευθεία χωρίζει τα σημεία του χώρου σε δύο σύνολα: τα σημεία που ανήκουν στην ευθεία και αυτά που δεν ανήκουν σε αυτή. Ορισμένες φορές στον καθημερινό λόγο χρησιμοποιείται ο όρος ‘ευθεία’ για να προσδιορίσει ένα ευθύγραμμο τμήμα, πράγμα που δεν ισχύει. Στο πρόβλημα της σχεδίασης υπάρχει πάντοτε ένα αρχικό και ένα τελικό σημείο, ακόμη κι αν αυτά είναι τα όρια της οθόνης. Μια ευθεία ορίζεται ως:
{Εξ. 2.1} |
όπου |a| + |b| ≠ 0.
Στην περίπτωση του ευθύγραμμουευθύγραμμου τμήματος (Εικόνα 2.3) έχουμε ένα σημείο αρχής, έστω το P1 με συντεταγμένες (x1, y1) και ένα σημείο τερματισμού, έστω το P2 με συντεταγμένες (x2, y2). Με δεδομένα αυτά τα δύο σημεία ορίζεται η παραμετρική εξίσωση:
{Εξ. 2.2} |
Έτσι, για κάθε τιμή του t προκύπτει ένα ζεύγος τιμών (x, y) που επιτρέπει τη δημιουργία σημείων πάνω στην καμπύλη, δυνατότητα που δεν προσφέρεται από την Πεπλεγμένη μορφή. Επίσης, επειδή συνήθως έχουμε να κάνουμε με ευθύγραμμα τμήματα που είναι τμήματα κάποιας ευθείας, είναι πιο βολική η παραμετρική μορφή για τις δύο μεταβλητές Χ και Υ που εκφράζονται έτσι ανεξάρτητα η μία από την άλλη [Blundell, 2008].
Εικόνα 2.3. Το ευθύγραμμο τμήμα που διέρχεται από τα σημεία P1 και P2
Το ευθύγραμμο τμήμα Τ διαγράφεται καθώς το t λαμβάνει τις τιμές από το 0 έως το 1. Αν οι τιμές του t επεκταθούν εκτός των ορίων (t R), τότε ορίζεται η ευθεία που διέρχεται από τα σημεία P1 και P2. Οι συντεταγμένες του ευθύγραμμου τμήματος δίνονται ως:
{Εξ. 2.3} |
Για τις ακραίες τιμές (t=0 και t=1), η παραμετρική εξίσωση επιστρέφει τα άκρα του ευθύγραμμου τμήματος P1(x1,y1) και P2(x2,y2), ενώ για t=1/2 επιστρέφεται το μέσον του ευθύγραμμου τμήματος.
Κωνικές τομές ονομάζονται οι καμπύλες που προκύπτουν από την τομή ενός κώνου με ένα επίπεδο. Το σύνολο των καμπυλών έως δευτέρου βαθμού είναι κωνικές τομές. Λαμβάνονται υπόψη δύο γωνίες που χαρακτηρίζουν τη σχετική τοποθέτηση του επιπέδου με τον κώνο: η φ γωνία που είναι το ‘άνοιγμα’ του κώνου και η θ που είναι η γωνία που σχηματίζεται ανάμεσα στο επίπεδο και τον άξονα του κώνου (Εικόνα 2.4). Η πλήρης περιγραφή θεωρεί διπλό κώνο με μη-πεπερασμένες διαστάσεις όπου ο δεύτερος κώνος είναι αντεστραμμένος σε σχέση με τον πρώτο, αλλά διατηρείται πάνω στον ίδιο κοινό άξονα (Εικόνα 2.5).
Εικόνα 2.4. Γωνίες που προσδιορίζουν τη σχετική θέση του επιπέδου με τον κώνο
Στη γενική της μορφή μια κωνική τομή περιγράφεται από την εξίσωση:
{Εξ. 2.4} |
Με διάφορες τοποθετήσεις του επιπέδου σε σχέση με τον κώνο προκύπτουν οι εξής περιπτώσεις:
Κύκλος. Αν το επίπεδο είναι κάθετο στο άξονα του κώνου, τότε από την τομή προκύπτει ο κύκλος.
Έλλειψη. Όταν ισχύει φ<θ, τότε η ημι-γωνία της κορυφής του κώνου είναι μικρότερη από την κλίση του επιπέδου με αποτέλεσμα από την τομή να προκύπτει το σχήμα της έλλειψης. Το σχήμα της έλλειψης προκύπτει όταν στην ax2 + bxy + cy2 + dx + ey + f = 0 {Εξ. 2.4} ισχύει η ανισότητα 4ac-b2>0.
Παραβολή. Όταν ισχύει η ισότητα φ=θ, τότε από την ισότητα των γωνιών μεταξύ του επιπέδου και του κώνου παράγεται μια παραβολή. Από τη γενική μορφή της κωνικής τομής ισχύει 4ac=b2 και ένας τουλάχιστον εκ των παραγόντων a και c πρέπει να είναι μη μηδενικός.
Υπερβολή. Προκύπτει, όταν ισχύει η αντίθετη ανισότητα που δημιουργεί την έλλειψη, δηλαδή όταν φ>θ.
Κάθε καμπύλη μπορεί να περιγραφεί από μια καρτεσιανή εξίσωση που συνδέει τις συντεταγμένες της και ορίζεται ως ένα σύνολο σημείων για τα οποία ισχύει:
{Εξ. 2.5} |
Όπου f, είναι η συνάρτηση των x και y και c είναι μια σταθερά. Στα παρακάτω εδάφια θα περιγραφούν ορισμένα βασικά σχήματα. Με αφετηρία την Πεπλεγμένη εξίσωση καθενός σχήματος, εξηγούνται ορισμένες πολύ βασικές ιδιότητες πριν δοθεί τελικά ο παραμετρικός ορισμός του σχήματος.
Κύκλος είναι ο γεωμετρικός τόπος των σημείων του επιπέδου που ισαπέχουν από το κέντρο του κύκλου κατά απόσταση r. Αν C(xc,yc) είναι το κέντρο του κύκλου, τότε η σχέση που συνδέει τις συντεταγμένες των σημείων του κύκλου περιγράφεται από την εξίσωση:
{Εξ. 2.6} |
όπου r είναι η ακτίνα του κύκλου. Σε αντιστοιχία με τα προηγούμενα, η παραμετρική εξίσωση κύκλου με κέντρο το σημείο (0,0) του συστήματος συντεταγμένων δίνεται από το ζεύγος παραμετρικών εξισώσεων:
{Εξ. 2.7} |
όπου r είναι η ακτίνα του κύκλου και t [0, 1]. Ο κύκλος ομοίως διαγράφεται καθώς το t λαμβάνει τις τιμές από το 0 έως το 1, με τη διαφορά ότι για επέκταση των ορίων του t προκύπτει επανασχεδιασμός του κύκλου.
 |
 |
| α) Κύκλος | b) Έλλειψη |
 |
 |
| γ) Παραβολή | δ) Υπερβολή |
Εικόνα 2.5. Κωνικές τομές
Έλλειψη είναι η κωνική τομή που δημιουργείται όταν ένα επίπεδο τέμνει πλάγια έναν κώνο (υπό γωνία με τον άξονά του). Ο κύκλος που εξετάστηκε πρωτύτερα μπορεί να θεωρηθεί ειδική περίπτωση της έλλειψης όπου το επίπεδο τέμνει τον κώνο κάθετα στον άξονα του κώνου. Με δεδομένα δύο σταθερά σημεία στο επίπεδο, έστω τα Ε1 και Ε2 (εστίες) που έχουν απόσταση c μεταξύ τους (εστιακή απόσταση), η έλλειψη ορίζεται ως ο γεωμετρικός τόπος των σημείων που δίνουν σταθερό άθροισμα αποστάσεων από τα σημεία αυτά, και ισχύει ότι a>c (Εικόνα 2.6). Αν το κέντρο είναι η αρχή των αξόνων Ο(0,0), τότε η εξίσωση:
{Εξ. 2.8} |
ορίζει πεπλεγμένα την έλλειψη όπου 2a είναι ο μεγάλος άξονας συμμετρίας, και 2b ο μικρός άξονας συμμετρίας και ισχύει b2=a2-c2. Η παραμετρική περιγραφή της έλλειψης δίνεται από το ζεύγος εξισώσεων:
{Εξ. 2.9} |
Εικόνα 2.6. Γραφική αναπαράσταση έλλειψης όπου Ε1,Ε2: εστίες, a: μικρός άξονας, b: μεγάλος άξονας και χ:οποιοδήποτε σημείο που έχει σταθερό άθροισμα αποστάσεων από τις εστίες
Παραβολή λέγεται ο γεωμετρικός τόπος των σημείων που ισαπέχουν από μια ευθεία E και από ένα σημείο P που βρίσκεται εκτός της ευθείας (Εικόνα 2.7). Η ευθεία Ε που ονομάζεται Διευθέτουσα, όπως και το σημείο P που ονομάζεται Εστία της παραβολής, είναι και τα δύο σταθερά και δε μεταβάλλονται. Η παραβολή είναι ανοιχτή καμπύλη και εκτείνεται απεριόριστα στο δισδιάστατο επίπεδο. Η εξίσωση που την ορίζει είναι η δευτεροβάθμια συνάρτηση:
{Εξ. 2.10} |
Αν η αρχή των αξόνων (0,0) είναι η κορυφή της παραβολής και ο άξονας των τετμημένων είναι ο άξονας συμμετρίας της, τότε η παραβολή περιγράφεται από την εξίσωση:
{Εξ. 2.11} |
όπου 2a είναι η παράμετρος της παραβολής, η απόλυτη τιμή της οποίας είναι η απόσταση της Εστίας από τη Διευθέτουσα. Τέλος, η παραμετρική εξίσωση της παραβολής δίνεται από το ζεύγος εξισώσεων:
{Εξ. 2.12} |
ή
{Εξ. 2.13} |
Εικόνα 2.7. Γραφική αναπαράσταση Παραβολής όπου Ε: μια σταθερή ευθεία, P: ένα σταθερό σημείο και χ1, χ2 : σημεία που ισαπέχουν από την ευθεία E και το σημείο P
Υπερβολή είναι η κωνική τομή που ορίζεται από δύο σταθερά σημεία Ε1 και Ε2 που ονομάζονται εστίες, και περιλαμβάνει τα σημεία των οποίων η απόλυτη διαφορά της απόστασής τους από τις εστίες είναι σταθερή και μικρότερη του Ε1-Ε2 (Εικόνα 2.8). Για την υπερβολή ισχύει:
{Εξ. 2.14} |
όπου 2a είναι η απόσταση μεταξύ των κορυφών και 2c η εστιακή απόσταση. Ο λόγος ε=c/a ονομάζεται εκκεντρότητα της υπερβολής. Μια ισοσκελής υπερβολή xy=c2 με κορυφές τα σημεία Α(c,c) και B(-c,-c) δίνεται από τις παραμετρικές εξισώσεις:
{Εξ. 2.15} |
ή
{Εξ. 2.16} |
όπου t ∈ R-{0}
Εικόνα 2.8. Γραφική αναπαράσταση Υπερβολής όπου Ε1, Ε2: δύο σταθερά σημεία (εστίες), χ: σημεία των οποίων η απόλυτη διαφορά της απόστασής από τις εστίες είναι σταθερή και μικρότερη του Ε1-Ε2.
Οι καμπύλες Μπεζιέ (Bézier) είναι παραμετρικές καμπύλες, πολύ γνωστές στο χώρο των διανυσματικών γραφικών και αποτελούν ένα χρήσιμο εργαλείο για την περιγραφή καμπυλών ελεύθερης μορφής. Πριν οριστεί παραμετρικά η καμπύλη Μπεζιέ, είναι σκόπιμο να γίνει μια μικρή εισαγωγή στην έννοια της Γραμμικής Παρεμβολής. Όπως είχε αναφερθεί και προηγούμενα, η παραμετρική μορφή της εξίσωσης ευθυγράμμου τμήματος είναι:
{Εξ. 2.17} |
όπου t ∈ [0, 1].
Η Γραμμική Παρεμβολή είναι η ένωση δύο γνωστών σημείων P1(x1,y1) και P2(x2,y2) με μια ευθεία γραμμή. Έτσι, για κάθε x που ανήκει στο διάστημα (x0,x1) οι τιμές του y προκύπτουν από την εξίσωση:
{Εξ. 2.18} |
η οποία αν αποδοθεί ως προς y, δίνει:
{Εξ. 2.19} |
Για ένα δεδομένο σύνολο σημείων P0, P1,…,Pn μπορούμε να εκτελέσουμε μια σειρά από γραμμικές παρεμβολές μεταξύ των σημείων ανά ζεύγη, αφού προσδιοριστούν τα ενδιάμεσα σημεία που προκύπτουν από την παρεμβολή. Καθώς το t διατρέχει το διάστημα από 0 έως 1, τα σημεία της γραμμικής παρεμβολής του υψηλότερου βαθμού σχηματίζουν μια καμπύλη. Αυτή η καμπύλη ονομάζεται καμπύλη Μπεζιέ n βαθμού και στη δισδιάστατη μορφή της δίνεται από τη σχέση:
{Εξ. 2.20} |
όπου t ᶓ [0, 1] και
είναι οι διωνυμικοί συντελεστές.
Τα σημεία P0, P1,…,Pn ονομάζονται Σημεία Ελέγχου. Αυτά είναι που προσδιορίζουν την καμπυλότητα κατά μήκος της καμπύλης. Στην περίπτωση που τα σημεία ελέγχου βρίσκονται πάνω στην ίδια ευθεία, τότε δεν υπάρχει καμία καμπυλότητα και προκύπτει ευθύγραμμο τμήμα με αρχή και τέλος το πρώτο και τελευταίο από τα σημεία ελέγχου. Πάντως, σε κάθε περίπτωση, η καμπύλη διέρχεται από τα ακραία σημεία, ενώ κατά κανόνα δε διέρχεται από τα ενδιάμεσα.
Το n δίνει το βαθμό της καμπύλης Μπεζιέ. Για μεγάλες τιμές του n αυξάνεται σε μεγάλο βαθμό η πολυπλοκότητα και ταυτόχρονα το υπολογιστικό κόστος, πράγμα μη επιθυμητό για ένα γραφικό σύστημα. Για την περιγραφή πιο πολύπλοκων καμπυλών, η ενδεδειγμένη λύση είναι η συνένωση μικρότερων και πιο απλών καμπυλών και επιφανειών, όπως θα δούμε στο κεφάλαιο 4. Όταν n=2 προκύπτει μια δευτέρου βαθμού (τετραγωνική) καμπύλη Μπεζιέ, ενώ για υψηλότερες τιμές του n προκύπτουν υπερτετραγωνικές μορφές. Μια καμπύλη Μπεζιέ βαθμού n, που συμβολίζεται ως Pn(t), μπορεί να παραχθεί από n+1 σημεία ελέγχου P0, P1,…,Pn που την προσδιορίζουν πλήρως. Ένας ενδεχόμενος μετασχηματισμός, δηλαδή, της καμπύλης Μπεζιέ, το μόνο που θα απαιτούσε θα ήταν ο μετασχηματισμός των σημείων ελέγχου της. Επίσης, η φορά ανάγνωσης των σημείων ελέγχου είναι αδιάφορη, δηλαδή αν χρησιμοποιηθούν τα σημεία ελέγχου με αντίστροφη σειρά, προκύπτει ακριβώς η ίδια καμπύλη.
Στην Εικόνα 2.9 φαίνονται δύο παραδείγματα, ένα με δευτέρου βαθμού (τετραγωνική) καμπύλη Μπεζιέ στα αριστερά και μια τρίτου βαθμού (κυβική) στα δεξιά. Καθώς το t μετακινείται από το 0 στο 1, τα σημεία παρεμβολής μετακινούνται και αυτά πάνω στα τμήματά τους (π.χ. το P01 κατά μήκος του ευθύγραμμου τμήματος P0P1). Το σημείο γραμμικής παρεμβολής υψηλότερου βαθμού (π.χ. το P02 στην κυβική καμπύλη Μπεζιέ) διαγράφει την καμπύλη που περιγράφεται από την εξίσωση με βάση τα σημεία ελέγχου.
Εικόνα 2.9. Καμπύλες Bezier: α) Δευτέρου βαθμού ή τετραγωνική καμπύλη (αριστερά), β) Τρίτου βαθμού ή κυβική καμπύλη (δεξιά)
Το πρόβλημα της σχεδίασης ενός ευθύγραμμου τμήματος μεταξύ δύο γνωστών σημείων στο καρτεσιανό επίπεδο είναι πρωτίστως η αναζήτηση εκείνων των εικονοστοιχείων που βρίσκονται ανάμεσα στα άκρα του ευθύγραμμουευθύγραμμου τμήματος, προσεγγίζουν καλύτερα το επιθυμητό σχήμα και ταυτόχρονα διατηρούν σταθερό πλάτος γραμμής καθόλο το διάστημα σχεδίασης (Εικόνα 2.10). Οι αλγόριθμοι σχεδίασης δε θα πρέπει να αφήνουν κενά ανάμεσα στα επιλεγμένα εικονοστοιχεία. Πιο πολύπλοκα σχήματα, όπως τα πολύγωνα, χρησιμοποιούν επαναληπτικά τους αλγορίθμους σχεδίασης ευθύγραμμων τμημάτων και γι’ αυτό το λόγο θα πρέπει να είναι αρκετά γρήγοροι στην εκτέλεσή τους.
Ένα ευθύγραμμο τμήμα σε μια σκηνή περιγράφεται από τις συντεταγμένες των άκρων του. Για να εμφανιστεί, όμως η ευθεία σε μια πλεγματική οθόνη πρέπει να υλοποιηθεί ένας αλγόριθμος σχεδίασης γραμμών. Κατά την εκτέλεση αυτού του αλγορίθμου θα αποφασίζεται σε κάθε βήμα ποιο εικονοστοιχείo θα σχεδιαστεί. Σε γενικές γραμμές είναι αδύνατον να επιλεγούν τα εικονοστοιχεία τα οποία βρίσκονται ακριβώς πάνω στη μαθηματική ευθεία, καθώς το πλέγμα απεικόνισης έχει πεπερασμένη ανάλυση, οπότε και πρέπει να βρεθεί μια προσεγγιστική λύση.
Έστω ότι ζητείται η σχεδίαση της ευθείας μεταξύ των σημείων (x0, y0) και (x1, y1). Λαμβάνοντας υπόψη την εξίσωση ευθείας y = mx + b, στη συνέχεια παρουσιάζονται τέσσερις βασικοί αλγόριθμοι σχεδίασης σε αύξουσα σειρά ακρίβειας [Sproull, 1982] [Rauber, 1993] [Θεοχάρης και άλλοι, 1999, 2010].
Εικόνα 2.10. Αναζήτηση των εικονοστοιχείων που πρέπει να επιλεγούν ανάμεσα στα σημεία αρχής και τέλους
Μια πρώτη λύση στο πρόβλημα της σχεδίασης ευθύγραμμου τμήματος είναι η χρήση της εξίσωσης ευθείας, η οποία όταν λύνεται ως προς y δίνει:
{Εξ. 2.21} |
Υπάρχουν δύο παράγοντες που μένουν σταθεροί, οι α και b και που μπορούν να υπολογιστούν εκ των προτέρων για να εισαχθούν στον αλγόριθμο σχεδίασης ως σταθερές. Επίσης, υπάρχει ο περιορισμός για σχεδίαση στο πρώτο ογδοημόριο, δηλαδή με κλίση μέχρι 45 μοίρες (0 ≤ a ≤ 1) και η πορεία της σχεδίασης είναι από το σημείο (x0, y0) προς το σημείο (x1, y1) με x0 <x1. Ο ψευδοκώδικας του αλγορίθμου σχεδίασης παρουσιάζεται στη Λίστα 2.1.
|
1. int x, x0, x1, y0, y1 |
 Αλγόριθμοι σχεδίασης ευθυγράμμου τμήματος
|
Λίστα 2.1. Ο κώδικας του αλγορίθμου σχεδίασης με βάση την εξίσωση ευθείας
Ο αλγόριθμος αυτός παρουσιάζει ορισμένα προβλήματα που συνοψίζονται ακόλουθα:
Ο δεύτερος αλγόριθμος που εξετάζεται βασίζεται στον αυξητικό υπολογισμό ημιτόνων (Digitizer Differential Analyzer-DDA). Ο σκοπός είναι να αποφευχθεί η υπολογιστικά δαπανηρή πράξη του πολλαπλασιασμού μέσα στο βρόγχο σχεδίασης. Ουσιαστικά, είναι γνωστή η τιμή του x σε κάθε βήμα, λαμβάνει τιμές από x0 έως x1 και το μόνο πρόβλημα είναι πλέον η αναζήτηση της καλύτερης αριθμητικής τιμής για το y. Με την επιλογή του συγκεκριμένου αλγόριθμου αποφεύγεται η υπολογιστικά χρονοβόρα διαδικασία του πολλαπλασιασμού με τον παράγοντα α σε κάθε επανάληψη (Λίστα 2.2).
1. int x, y, x0, x1, y0, y1
2. float a
3. a = (y1 - y0) / (x1 - x0)
4. y=y1
5. for (x = x0; x <= x1; ++x)
6. {
7. setpixel(x, round(y))
8. y=y+a
9. }
Λίστα 2.2. Ο κώδικας του αυξητικού αλγορίθμου σχεδίασης
Ωστόσο, με την εφαρμογή του αυξητικού υπολογισμού ημιτόνων παραμένουν ορισμένα προβλήματα όπως:
Προκειμένου να απαλλαχθεί ο αλγόριθμος από την υπολογιστικά ακριβή διαδικασία της στρογγυλοποίησης (εντολή round) μέσα στο βρόγχο, διαχωρίζεται το δεκαδικό μέρος του y και εισάγεται μέσα στη μεταβλητή που συγκρατεί το λάθος (error). Η νέα μεταβλητή error αντιστοιχεί στην κάθετη απόσταση ανάμεσα στο κέντρο του εικονοστοιχείου και την ακριβή θέση του σημείου.
Συμπερασματικά, σε κάθε επανάληψη του βρόγχου σημαντικός παράγοντας σχετικά με την επιλογή του y είναι αν η μεταβλητή error είναι μεγαλύτερη ή όχι από το ήμισυ του μεγέθους ενός εικονοστοιχείου. Στην οριακή συνθήκη της ισότητας, δηλαδή όταν το συσσωρευμένο λάθος είναι ίσο με τη μισή απόσταση προς το κέντρο του εικονοστοιχείου (τιμή 0.5 της γραμμής 10 στη Λίστα 2.3), τότε ο αλγόριθμος κλίνει προς την επιλογή του υψηλότερου κατά y εικονοστοιχείου (y=y+1).
1. int x, x0, x1, y0, y1
2. float m, error, y
3. error=0
4. m = (y1 - y0) / (x1 - x0)
5. x=x0
6. y=y0
7. while ( x <= x1)
8. {
9. setpixel(x, y)
10. x = x + 1
11. error = error + m
12. if (error >= 0.5)
13. {
14. y = y + 1
15. error = error – 1
16. }
17. }
Λίστα 2.3. Ο κώδικας του αλγορίθμου υπολογισμού σφάλματος
Ο αλγόριθμος αυτός διατηρεί το y σταθερό έως ότου το σφάλμα προσέγγισης που συσσωρεύεται σε κάθε επανάληψη ξεπεράσει το ½, οπότε και ανανεώνεται η τιμή του y. Τα προβλήματα που παρουσιάζει ο αλγόριθμος είναι:
Ο αλγόριθμος που είναι ευρύτερα γνωστός με το όνομα ‘Aλγόριθμος του Bresenham’ [1965] είναι ένας αποδοτικός αλγόριθμος που χρησιμοποιείται ευρύτατα στα σύγχρονα συστήματα γραφικών για τη σχεδίαση ευθύγραμμων τμημάτων. Μπορεί να υλοποιείται σε περισσότερες γραμμές κώδικα (Λίστα 2.4), αλλά παρουσιάζει το πλεονέκτημα ο εσωτερικός του βρόγχος να είναι απαλλαγμένος από δαπανηρούς υπολογισμούς. Το μόνο που έχει να εκτελέσει ο αλγόριθμος σε κάθε βήμα είναι υπολογιστικά οικονομικές πράξεις, όπως απλές πράξεις πρόσθεσης και κάποιες συγκρίσεις μεταβλητών. Πρακτικά, τα οφέλη του προκύπτουν από την αντικατάσταση των πραγματικών μεταβλητών που υπήρχαν σε προηγούμενες λύσεις από ακέραιες. Κατά αυτόν τον τρόπο καλύπτονται ικανοποιητικά οι απαιτήσεις ενός αποδοτικού αλγορίθμου σχεδίασης. Αφετέρου παρουσιάζει το μειονέκτημα ότι περιορίζει τις συντεταγμένες των δύο άκρων σε ακέραιες τιμές (integer) και έτσι αντί για το πραγματικό ευθύγραμμο τμήμα σχεδιάζει αυτό που προκύπτει μετά από στρογγυλοποίηση των άκρων του, με μέγιστο λάθος ένα εικονοστοιχείο.
Όπως και οι υπόλοιποι αλγόριθμοι, ο αλγόριθμος του Bresenham είναι κατάλληλος για απεικόνιση στο πρώτο ογδοημόριο, δηλαδή για περιπτώσεις ευθύγραμμων τμημάτων με κλίση μεταξύ 0 και 1 και x1<x2. Για τις υπόλοιπες περιπτώσεις πρέπει να γίνει κατάλληλη χρήση του x ή του y ως ανεξάρτητη μεταβλητή και εναλλαγή του σημείου εκκίνησης της σχεδίασης (εναλλαγή του αρχικού και τελικού σημείου). Παρακάτω (Πίνακας 2.1) παρουσιάζονται τα οκταμόρια αριθμημένα και σχολιασμένα ως προς τον άξονα ταχύτερης κίνησης και εναλλαγής της ανεξάρτητης μεταβλητής. Σε κάθε περίπτωση αυτό που απαιτείται είναι η μεταφορά του ευθύγραμμου τμήματος από την τρέχουσα θέση του στο πρώτο οκταμόριο και με σημείο εκκίνησης την αρχή των αξόνων. Μετά το σχεδιασμό γίνεται η αντίστροφη μεταφορά του στην αρχική θέση.
1. int x, y x0, x1, y0, y1, dx, dy
2. float e
3. color c
4. dx = x1 - x0
5. dy = y1 - y0
6. e = -dx / 2
7. x = x0
8. y = y0
9. while ( x <= x1)
10. {
11. setpixel(x, y, c)
12. x = x + 1
13. e = e + dy
14. if (e >= 0)
15. {
16. y = y + 1
17. e = e - dx
18. }
19. }
Λίστα 2.4.Ο κώδικας του αλγορίθμου υπολογισμού σφάλματος
Πίνακας 2.1. Εναλλαγές ανεξάρτητης μεταβλητής και άξονες ταχύτερης κίνησης
| Περιοχές οκταμορίων στο καρτεσιανό επίπεδο | Οκταμόριο | Άξονας Ταχύτερης Κίνησης | Άξονας Αργής Κίνησης |
|---|---|---|---|
 |
1 | X | Αυξάνεται |
| 2 | Y | Αυξάνεται | |
| 2 | Y | Αυξάνεται | |
| 3 | Y | Μειώνεται | |
| 4 | Χ | Αυξάνεται | |
| 5 | Χ | Μειώνεται | |
| 6 | Y | Μειώνεται | |
| 7 | Y | Αυξάνεται | |
| 8 | Χ | Μειώνεται |
Στη σχεδίαση έχει σημασία να διατηρείται και το πάχος της γραμμής σταθερό κατά μήκος του ευθύγραμμου τμήματος που σχεδιάζεται. Έστω το παράδειγμα του ευθύγραμμου τμήματος που φαίνεται στην Εικόνα 2.11. Στην αριστερή πλευρά αναπαρίσταται μια πλεγματική οθόνη και ένα ευθύγραμμο τμήμα που προέκυψε από επιλογή όλων των εικονοστοιχείων πάνω από τα οποία διέρχεται η γραμμή. Στη δεξιά εικόνα φαίνεται η περίπτωση που έχουν επιλεγεί μόνο τα πλησιέστερα στη γραμμή εικονοστοιχεία και μάλιστα μόνο ένα ανά στήλη. Η επιλογή ενός μόνο εικονοστοιχείου ανά στήλη (δεύτερη περίπτωση) θεωρείται προτιμότερη από τους περισσότερους καθώς διατηρεί πάχος γραμμής 1 εικονοστοιχείο.
Από την άλλη πλευρά, η πυκνότητα των εικονοστοιχείων (αριθμός επιλεγμένων εικονοστοιχείων ανά μονάδα επιφανείας) εξαρτάται όχι μόνο από τον αλγόριθμο σχεδίασης αλλά και από την κλίση της ευθείας. Οι οριζόντιες και κάθετες γραμμές εμφανίζουν την υψηλότερη πυκνότητα εικονοστοιχείων, ενώ τη μικρότερη πυκνότητα έχει η γραμμή που διέρχεται από τα όρια του πρώτου από το δεύτερο ογδοημόριο (κλίση ίση με τη μονάδα) όπως φαίνεται στην Εικόνα 2.12. Στο παράδειγμα αυτό υπάρχουν έξι (6) εικονοστοιχεία στις οριζόντιες και κάθετες διαδρομές (κλίσεις μέγιστης πυκνότητας). Αυτά τα έξι εικονοστοιχεία επιλέγονται για τη σχεδίαση ενός τμήματος, μήκους έξι φορές το μέγεθος του εικονοστοιχείου. Στην ευθεία που έχει κλίση ίση με τη μονάδα (διαγώνια γραμμή), υπάρχουν πάλι έξι εικονοστοιχεία επιλεγμένα, αλλά για μεγαλύτερο μήκος ευθύγραμμου τμήματος. Αυτή η πυκνότητα αντιστοιχεί περίπου στο 70% της μέγιστης. Ο Πίνακας 2.2 αναφέρει πυκνότητες για διάφορες κλίσεις της ευθείας [Klawonn, 2008].
Ένα άλλο θέμα που επηρεάζει άμεσα την πυκνότητα των εικονοστοιχείων είναι το είδος (στυλ) της γραμμής που σχεδιάζεται. Μια διακεκομμένη (dashed) γραμμή για παράδειγμα (π.χ. τομή σε μηχανολογικό εξάρτημα) είναι εντελώς διαφορετική από τη συνεχόμενη γραμμή που θεωρούσαμε μέχρι τώρα. Ο Πίνακας 2.3 παρουσιάζει ένα παράδειγμα όπου η δεύτερη γραμμή (Επιλογή) αναφέρει το αποτέλεσμα του αλγορίθμου σχεδίασης, δηλαδή τη σειρά των εικονοστοιχείων που πρέπει να επιλεγούν (από το 1ο έως το 13ο). Εφαρμόζεται η μέθοδος της μάσκας που αποτυπώνει το επιθυμητό στυλ σχεδίασης σε μορφή μονοδιάστατου πίνακα εικονοστοιχείων, όπου το 1 σημαίνει αποδοχή του αποτελέσματος του αλγορίθμου σχεδίασης, ενώ το 0 σημαίνει απόρριψη. Η τελευταία γραμμή είναι το αποτέλεσμα της λογικής πράξης AND μεταξύ των δύο παραπάνω γραμμών και είναι αυτή που δείχνει τελικά ποια εικονοστοιχεία θα ‘ανάψουν’ στη γραμμή της οθόνης και ποια όχι. Παρατηρείται ότι τα δύο τελευταία εικονοστοιχεία του πίνακα δεν έχουν επιλεγεί (διότι η σχεδίαση ολοκληρώνεται στο 13ο) με αποτέλεσμα η εφαρμογή της μάσκας να δημιουργεί μια αλλοίωση της διακεκομμένης γραμμής κοντά στην περιοχή του σημείου τερματισμού.
Εικόνα 2.11. Σχεδίαση ευθυγράμμου τμήματος: α) με επιλογή όλων των εικονοστοιχείων που διαπερνά η γραμμή (αριστερά) και β) με επιλογή μόνο των πλησιέστερων εικονοστοιχείων, 1 ανά στήλη (δεξιά)
Εικόνα 2.12. Η πυκνότητα εικονοστοιχείων εξαρτάται από την κλίση της ευθείας
Ένα άλλο πρόβλημα που δημιουργείται στη σχεδίαση των διακεκομμένων γραμμών είναι με τις μη οριζόντιες ή κάθετες γραμμές. Στις περιπτώσεις αυτές η εφαρμογή της μάσκας πάνω στα αποτελέσματα του αλγορίθμου σχεδίασης δημιουργεί τμήματα γραμμών τα οποία είναι μεγαλύτερα σε μήκος από τα αντίστοιχα τμήματα που είναι παράλληλα με τους άξονες. Στο τρέχον παράδειγμα (Πίνακας 2.3), αν η γραμμή έπρεπε να σχεδιαστεί με κλίση ίση με τη μονάδα, δηλαδή με κλίση 45 μοιρών, τότε το μήκος του καθενός τμήματος δε θα ήταν ίσο με 3 όπως θα ήταν αναμενόμενο στην περίπτωση της οριζόντιας γραμμής, αλλά μεγαλύτερο.
Πίνακας 2.2. Πυκνότητες εικονοστοιχείων για χαρακτηριστικές κλίσεις ευθείας σχεδίασης
| a | Κλίση (σε μοίρες) | Μήκος | Πυκνότητα |
|---|---|---|---|
| 0 ή 1 | ∝ | n | 1 |
| n/4 | 1/4 | ||
| n | 1 | ||
| m | m/n | n | 1 |
Στην πράξη οι αλγόριθμοι σχεδίασης εφαρμόζουν διορθωτικά μέτρα στη σχεδίαση γραμμών που δεν είναι παράλληλες με τους άξονες και κοντά στα όρια των ευθύγραμμων τμημάτων, προκειμένου να διατηρείται σταθερό το πάχος της γραμμής σχεδίασης.
Πίνακας 2.3. Εφαρμογή μάσκας στυλ για το παράδειγμα της διακεκομμένης (dashed) γραμμής
| Μήκος | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Επιλογή | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| Μάσκα | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| AND | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| Οθόνη |
Η σχεδίαση σχημάτων δε γίνεται μόνο με γραμμές πάχους ενός εικονοστοιχείου (Το πάχος μετράται στον ‘αργό’ άξονα). Για μεγαλύτερα πάχη υπάρχουν γενικά δύο προσεγγίσεις: α) με χρήση μετατόπισης και αντιγραφής εικονοστοιχείων και β) με χρήση πλαισίου nxn εικονοστοιχείων. Άλλες τεχνικές αντιμετωπίζουν το πάχος της γραμμής ως ένα ορθογώνιο παραλληλόγραμμο και σχεδιάζουν πολύγωνα το ένα δίπλα στο άλλο.
Παρόμοια με τη σχεδίαση λεπτής γραμμής πάχους ενός εικονοστοιχείου, η σχεδίαση με μεγαλύτερα πάχη δεν είναι απαλλαγμένη από προβλήματα. Υπάρχουν τεχνικές που μειώνουν τη διακύμανση πάχους, αποφεύγουν το χρωματισμό εικονοστοιχείων που έχουν ήδη χρωματιστεί από προηγούμενα βήματα και ομαλοποιούν τις συνδέσεις μεταξύ ευθύγραμμων τμημάτων.
Στην πρώτη περίπτωση, η μέθοδος που ακολουθείται είναι η αντιγραφή εικονοστοιχείων εκτός της λεπτής γραμμής που ορίζεται ως έξοδος του εκάστοτε χρησιμοποιούμενου αλγορίθμου σχεδίασης. Η γραμμή αποκτάει πάχος με αντιγραφή των επιλεγμένων εικονοστοιχείων προς τα πάνω και προς τα κάτω (Εικόνα 2.13, αριστερά). Το τελικό αποτέλεσμα είναι μια γραμμή που έχει τόσο πάχος, όσες και οι θέσεις που έχουν ρυθμιστεί για τη μετατόπιση. Αξιοσημείωτο είναι ότι η μετατόπιση δίνει καλύτερο αποτέλεσμα όταν είναι συμμετρική, στην περίπτωση δηλαδή που χρωματίζονται στο ίδιο βάθος τα εικονοστοιχεία πάνω και κάτω από την αρχική γραμμή.
Εικόνα 2.13. Απόδοση πάχους με τη μέθοδο της αντιγραφής εικονοστοιχείων (αριστερά) και με τη μέθοδο της κινούμενης πένας (δεξιά)
Στη δεύτερη περίπτωση εφαρμόζεται μια μάσκα nxn πάνω σε κάθε επιλεγμένο από τον αλγόριθμο σχεδίασης εικονοστοιχείο. Το n είναι κάθε φορά το επιθυμητό πάχος της γραμμής και αντιστοιχεί στο πάχος της ‘πένας’. Έτσι το ευθύγραμμο τμήμα αποκτάει γύρω του μια ‘αύρα’ που το εμφανίζει στην πλεγματική οθόνη με μεγαλύτερο πάχος.
Η μέθοδος αυτή στηρίζεται στην αρχή της συνδεσιμότητας, σύμφωνα με την οποία για κάθε εικονοστοιχείο είναι γνωστά τα γειτονικά του μέχρι ένα δεδομένο βάθος. Έτσι είναι δυνατή η αντικατάσταση του χρωματισμού ενός εικονοστοιχείου με μια νέα τιμή, η οποία μπορεί να δίνεται εκ των προτέρων ή να προκύπτει από πράξεις μεταξύ των χρωματισμών άλλων εικονοστοιχείων που ανήκουν στην ίδια ‘γειτονιά’.
Η εφαρμογή της μάσκας, που είναι ένας δισδιάστατος μοναδιαίος πίνακας μεγέθους n, γίνεται επαναληπτικά σε κάθε εικονοστοιχείο για να χρωματίσει τα γειτονικά του σε μια περιοχή 8 εικονοστοιχείων. Το μέγεθος της περιοχής ή ‘γειτονιάς’ του κάθε εικονοστοιχείου εξαρτάται από το μέγεθος της μάσκας. Στη μέθοδο της κινούμενης πένας, συνήθως, η μάσκα είναι τετραγωνικής μορφής με μονό αριθμό διάστασης (π.χ. 3x3, 5x5, 7x7 κτλ.). Το τελικό αποτέλεσμα της μεθόδου φαίνεται στο παράδειγμα της Εικόνας 2.13 στα δεξιά. Για λόγους μείωσης του υπολογιστικού κόστους σε κάθε βήμα του αλγορίθμου χρωματίζονται μόνο τα εικονοστοιχεία που δεν αλληλο-επικαλύπτονται από το προηγούμενο βήμα.
Τα ευθύγραμμα τμήματα δεν αποτελούν τα μόνα σχήματα που καλούνται να αποτυπωθούν πάνω σε πλεγματικές οθόνες. Τα περισσότερα από τα τελικά σχήματα που σχεδιάζονται, είναι σύνθετα και αποτελούνται μεταξύ άλλων και από πολύγωνα. Παρακάτω εξετάζονται τα πιο συνήθη πολύγωνα και κάποιοι ενδεικτικοί αλγόριθμοι σχεδίασης.
Πολύγραμμα είναι τα σχήματα που ορίζονται από μια σειρά διαδοχικών ευθύγραμμων τμημάτων. Εύκολα γίνεται αντιληπτό ότι τα πολύγραμμα σχεδιάζονται καλώντας επαναληπτικά τον αλγόριθμο σχεδίασης ευθύγραμμου τμήματος. Όταν, όμως, ένα πολύγραμμο είναι κλειστό, τότε αποτελεί πολύγωνο.
Το πιο απλό πολύγωνο είναι το τρίγωνο και αποτελείται από τρία ευθύγραμμα τμήματα που τέμνονται στις άκρες τους σχηματίζοντας ένα κλειστό σχήμα. Άρα το τρίγωνο ικανοποιεί τα κριτήρια της επιπεδότητας και της κυρτότητας (κλειστή επίπεδη περιοχή). Το τρίγωνο είναι πολύ σημαντικό σχήμα για το χώρο των γραφικών καθώς πολλές διαδικασίες εξετάζουν τις επιφάνειες ως τριγωνικά πλέγματα (τριγωνοποίηση).
Ως επίπεδα σχήματα, τα πολύγωνα ορίζονται με βάση τις κορυφές τους οι οποίες όταν ενώνονται μεταξύ τους με ακμές ορίζουν: α) ένα τριγωνικό πλέγμα, ή β) μια τριγωνική επιφάνεια. Στην πρώτη περίπτωση τα σημεία του σχήματος είναι αυτά που ανήκουν στις ακμές, ενώ στη δεύτερη περίπτωση χρειάζεται ένας έλεγχος εσωτερικότητας των σημείων για να διαπιστωθεί αν αυτά ανήκουν ή όχι στην επιφάνεια που ορίζεται από τις ακμές. Ο χρωματισμός εσωτερικού πολυγώνου καλύπτεται πιο αναλυτικά σε παρακάτω κεφάλαιο.
Ο αλγόριθμος του Bresenham, ως ένας αποδοτικός αλγόριθμος σχεδίασης ευθύγραμμου τμήματος χρησιμοποιείται τρεις φορές, για να σχεδιαστούν οι ακμές του τριγώνου. Ο συγχρονισμός των τριών εκτελέσεων του αλγορίθμου επιτρέπει τη σχεδίαση ανά γραμμή σάρωσης. Για κάθε θέση της γραμμής σάρωσης υπολογίζεται εκ νέου το ευθύγραμμο τμήμα που περιέχει τα εσωτερικά σημεία του τριγώνου και στη συνέχεια χρωματίζονται αυτά τα σημεία αποκαλύπτοντας σταδιακά το επιθυμητό σχήμα (Εικόνα 2.14).
Εικόνα 2.14. Σχεδιασμός τριγώνου με περιπάτηση ακμών
Ο αλγόριθμος που υλοποιεί αυτήν την προσέγγιση παρατίθεται στη Λίστα 2.5. Στην αρχή τοποθετούνται οι δύο κορυφές πάνω στον οριζόντιο άξονα και υπολογίζονται οι κλίσεις των ευθύγραμμων τμημάτων από την άνω κορυφή προς τη βάση του τριγώνου. Σε κάθε νέα θέση η γραμμή σάρωσης υπολογίζει με βάση τις κλίσεις slope1 και slope2, τις νέες θέσεις των σημείων που ορίζουν την εσωτερική γραμμή. Η drawline (π.χ. Bresenham) είναι η συνάρτηση που καλείται, για να χρωματίσει τα σημεία της γραμμής σάρωσης από το x1 έως το x2.
1. vertex v1, v2, v3;
2. float slope1 = (v2.x - v1.x) / (v2.y - v1.y);
3. float slope2 = (v3.x - v1.x) / (v3.y - v1.y);
4. float x1 = v1.x;
5. float x2 = v1.x;
6. for (int slineY = v1.y; sline <= v2.y; sline++)
7. {
8. drawline((int)x1, sline, (int)x2, sline);
9. x1+ = slope1;
10. x2+ = slope2;
11. }
12.}
Λίστα 2.5. Ο κώδικας του αλγορίθμου σχεδίασης τριγώνου
Το παραπάνω παράδειγμα παρουσίαζε τη βολική περίπτωση οι δύο κορυφές του τριγώνου να είναι παράλληλα τοποθετημένες πάνω σε μια οριζόντια ευθεία. Στη γενική περίπτωση, ένα τρίγωνο είναι τοποθετημένο στο 2Δ επίπεδο, όπως φαίνεται στην Εικόνα 2.15. Η λύση είναι να χωριστεί το τρίγωνο σε δύο μικρότερα τρίγωνα με βάση την οριζόντια γραμμή που διέρχεται από την ενδιάμεση ως προς το ύψος (άξονας y) κορυφή. Το πάνω τρίγωνο σχεδιάζεται με τη βοήθεια του αλγορίθμου που παρουσιάστηκε στη Λίστα 2.5, ενώ το κάτω τρίγωνο σχεδιάζεται με μια παραλλαγή του αλγορίθμου που θεωρεί ότι οι πάνω ακμές βρίσκονται στο ίδιο ύψος. Το ποιος αλγόριθμος θα εκτελεστεί κάθε φορά καθορίζεται από τον έλεγχο του τεμαχισμού (Λίστα 2.6).
Στην αρχή θεωρείται μια λίστα με τις κορυφές του τριγώνου ταξινομημένες ως προς τον άξονα Y. Στη συνέχεια γίνονται μια σειρά έλεγχοι για να διαπιστωθεί αν το τρίγωνο ανήκει ή όχι σε μια από τις βολικές περιπτώσεις (όρθιο ή ανάστροφο τρίγωνο). Αν όχι, τότε τεμαχίζει το τρίγωνο και καλεί τους δύο κατάλληλους αλγορίθμους.
Εικόνα 2.15. Τεμαχισμός τριγώνου
1. // Ταξινόμηση των κορυφών ως προς y
2. sortVerticesByY();
3. // Έλεγχος αν το τρίγωνο είναι ‘οριζοντίως όρθιο’
4. if (v2.y == v3.y)
5. {
6. fillUpRightTriangle(v1, v2, v3);
7. }
8. // Έλεγχος αν το τρίγωνο είναι ‘ανάστροφο’
9. else if (vt1.y == vt2.y)
10. {
11. fillReverseTriangle(v1, v2, v3);
12. }
13. else
14. {
15. //Αν δεν ισχύει καμία από τις παραπάνω
16. //περιπτώσεις, τότε κατάτμησε πρώτα το τρίγωνο
17. Vertice v4 = new Vertice((int)(vt1.x +
18. ((float)(vt2.y - vt1.y) / (float)(vt3.y - vt1.y))
19. * (vt3.x - vt1.x)), vt2.y);
20. //…και γέμισε τα δύο τρίγωνα που προέκυψαν.
21. fillUpRightTriangle(g, vt1, vt2, v4);
22. fillReverseTriangle(g, vt2, v4, vt3);
23. }
24. }
Λίστα 2.6. Ο κώδικας του αλγορίθμου τεμαχισμού του τριγώνου
Σύμφωνα με μια άλλη προσέγγιση, κάθε τρίγωνο περικλείεται από ένα ορθογώνιο παραλληλόγραμμο (Εικόνα 2.16) του οποίου τα εικονοστοιχεία ελέγχονται αν ανήκουν ή όχι στο τρίγωνο. Με αυτήν την απλή σχετικά τεχνική σχεδιάζεται ένα τρίγωνο χωρίς ταξινόμηση των κορφών του και χωρίς κατάτμηση. Ο έλεγχος εσωτερικότητας των εικονοστοιχείων που περικλείονται από το ορθογώνιο παραλληλόγραμμο καθορίζει ποια εικονοστοιχεία θα χρωματιστούν και ποια όχι (Λίστα 2.7). Πιο λεπτομερή στοιχεία για τον έλεγχο εσωτερικότητας δίνονται σε επόμενο υποκεφάλαιο.
Εικόνα 2.16. Ανάκτηση πλαισίου οριοθέτησης του τριγώνου και έλεγχος εσωτερικότητας των εικονοστοιχείων
1. //Υπολογισμός ορθογωνίου παραλληλογράμμου
2. //που περικλείει το τρίγωνο
3. int maxX = max(v1.x, v2.x v3.x)
4. int minX = min(v1.x, v2.x, v3.x)
5. int maxY = max(v1.y, v2.y, v3.y)
6. int minY = min(v1.y, v2.y, v3.y)
7. //Έλεγχος για όλα τα εικονοστοιχεία
8. for (int x = minX; x <= maxX; x++)
9. {
10. for (int y = minY; y <= maxY; y++)
11. {
12. if (checkInternal(x,y))
13. {
14. drawPixel(x, y);
15. }
16. }
17. }
Λίστα 2.7. Ο κώδικας σχεδίασης τριγώνου με έλεγχο εσωτερικότητας των εικονοστοιχείων
Ο Αλγόριθμος Σάρωσης Πολυγώνου (Scanline polygon fill algorithm) χρησιμοποιείται για να γεμίσει το εσωτερικό ενός πολυγώνου. Η προβληματική αναφέρεται στο ποια εικονοστοιχεία (με βάση τις συντεταγμένες του κέντρου τους) πρέπει να χρωματιστούν για να προκύψει η επιφάνεια που ορίζεται από το πολύγωνο, ή η γραμμή της περιμέτρου στην περίπτωση που δε μας ενδιαφέρουν τα εσωτερικά σημεία. Η σάρωση πολυγώνου βασίζεται στον έλεγχο των σημείων τομής μεταξύ των ακμών του πολυγώνου και της γραμμής σάρωσης. Θεωρούμε γραμμή σάρωσης εκείνη που σαρώνει το πολύγωνο από τη χαμηλότερη θέση (κατά y) έως την υψηλότερη. Ο αλγόριθμος σάρωσης πολυγώνου ακολουθεί τα παρακάτω βήματα:
Βήμα 1: Για κάθε θέση της γραμμής σάρωσης βρες τα σημεία τομής της γραμμής σάρωσης με τις ακμές του πολυγώνου.
Βήμα 2: Ταξινόμησε τα σημεία τομής ως προς x.
Βήμα 3: Χρωμάτισε τα εικονοστοιχεία που βρίσκονται ανάμεσα σε ζεύγη σημείων τομής [(x1,y1), (x2,y2)] δηλαδή για όσα ισχύει y = y1 = ysl και x1 <= x<= x2, όπου ysl είναι η τρέχουσα θέση της γραμμής σάρωσης.
Τα ζεύγη σημείων τομής που προκύπτουν από το δεύτερο βήμα είναι ταξινομημένα ως προς χ, προκειμένου να εφαρμοστεί ο κανόνας των μονών-ζυγών σημείων (έλεγχος ισοτιμίας – Parity check). Σύμφωνα με αυτόν τον κανόνα, ξεκινώντας από το αριστερότερο άκρο έχουμε αρχικά μηδέν σημεία τομής. Ο αλγόριθμος χρωματίζει τα σημεία που βρίσκονται στις περιοχές μονού αριθμού σημείων τομής και δεξιότερα (Εικόνα 2.17).
Εικόνα 2.17. Αποτέλεσμα της σάρωσης πολυγώνου για τη γραμμή σάρωσης y=3
Υπάρχουν περιπτώσεις που ο παραπάνω αλγόριθμος αποτυγχάνει να αποδώσει με επιτυχία. Τέτοιες περιπτώσεις συμβαίνουν, όταν έχουμε π.χ. μια κορυφή πολυγώνου που βρίσκεται πάνω στη γραμμή σάρωσης. Πόσες τομές πρέπει να θεωρήσει ο αλγόριθμος για να λειτουργήσει σωστά; Δεν υπάρχει κάποια προφανής λύση που να ισχύει σε όλες τις περιπτώσεις, καθώς άλλοτε μια κορυφή πρέπει να μετρήσει για ένα, δύο ή κανένα σημείο τομής. Στο προηγούμενο παράδειγμα (Εικόνα 2.17), η κορυφή Ε πρέπει να μετρήσει ως καμία ή δύο κορυφές, αλλιώς αν μετρήσει ως μία κορυφή, τότε το τμήμα από το σημείο Ε έως το δεξί άκρο δε θα χρωματιστεί.
Για να αντιμετωπιστούν αυτές οι ιδιάζουσες καταστάσεις, γίνεται μια σειρά από παραδοχές. Δεδομένου ότι κάθε ακμή έχει δύο κορυφές, μόνο η χαμηλότερη κορυφή (κορυφή με το μικρότερο y) θεωρείται έγκυρη. Με αυτόν τον τρόπο θεωρείται ότι υπάρχει μια μικρή μετατόπιση της κορυφής ως προς τον άξονα y, τόσο αμελητέα, ώστε να μην αλλοιώνει την ποιότητα του τελικού αποτελέσματος. Μια δεύτερη παραδοχή θέλει τις οριζόντιες γραμμές να μη μετράνε. Έτσι τα σημεία Α και Γ μετράνε για ένα σημείο τομής το καθένα, τα σημεία Β και Ε μετράνε για μηδέν σημεία τομής και τέλος, τα σημεία Ζ και Δ μετράνε για δύο σημεία.
Το μειονέκτημα που εισάγει το παραπάνω σύνολο παραδοχών είναι ότι τα εικονοστοιχεία που βρίσκονται πάνω πάνω σε ένα πολύγωνο δε χρωματίζονται. Το λάθος αυτό θεωρείται ανεκτό, ενώ στην περίπτωση δύο πολυγώνων που μοιράζονται την ίδια ακμή, η αποφυγή χρωματισμού της κοινής ακμής για το κάτω πολύγωνο δεν αποτελεί ουσιαστικό πρόβλημα. Στην περίπτωση που δύο πολύγωνα μοιράζονται την ίδια κάθετη ακμή, τότε η ακμή χρωματίζεται δύο φορές με υπερισχύον το χρώμα του δεύτερου πολυγώνου.
Παρατηρούμε ότι στον αλγόριθμο σάρωσης πολυγώνου τα σημεία τομής των ακμών με τη γραμμή σάρωσης i δε διαφέρουν πολύ από την αμέσως υψηλότερη γραμμή i+1. Αυτό μπορούμε να το εκμεταλλευτούμε για να κάνουμε τον αλγόριθμο πιο γρήγορο και αποδοτικό. Ως παράδειγμα δίνεται το πολύγωνο που φαίνεται στην Εικόνα 2.18.
Δύο διαδοχικά στιγμιότυπα της γραμμής σάρωσης, τα yn και yn+1 διαφέρουν κατά ένα εικονοστοιχείο ως προς τον κάθετο άξονα. Ζητούμενο είναι το πόσο διαφέρουν κατά τον οριζόντιο άξονα. Με βάση την κλίση της ευθείας που δίνεται από τον τύπο: m=(yn+1-yn)/(xn+1-xn) μπορούμε να υπολογίσουμε την οριζόντια μετατόπιση κατά xn+1=χn+1/m. Η παραπάνω συλλογιστική στην πλεγματική οθόνη μπορεί να γραφτεί ως:
xn+1=round(xn+1/m), όπου m=ΔΥ/ΔΧ {Εξ. 2.22}
Έτσι, λοιπόν, μπορούμε να διατηρούμε τις τιμές της κάθε γραμμής σάρωσης με τις ακμές του πολυγώνου στη Λίστα Ενεργών Ακμών (ΛΕΑ) και να ελέγχουμε κατά τη μετάβαση από τη μία γραμμή σάρωσης στην επόμενη για το ποιες αλλαγές έχουν επέλθει λόγω της κλίσης της ακμής. Όλες οι ακμές του πολυγώνου διατηρούνται στον Πίνακα Ακμών (ΠΑ).
Εικόνα 2.18. Ο πίνακας ακμών του πολυγώνου και οι γραμμές σάρωσης
Μετά τη δημιουργία του Πίνακα Ακμών, ο αλγόριθμος ακολουθεί τα παρακάτω βήματα:
1) Θέσε το Y στο χαμηλότερο Y των εγγραφών του πίνακα ΠΑ
2) Αρχικοποίησε την ΛΕΑ (κενή)
3) Επανάλαβε μέχρι η ΛΕΑ και ο ΠΑ να είναι κενοί (από το Ymin έως το Ymax):
Μια ιδέα για υλοποίηση του συγκεκριμένου αλγορίθμου παρουσιάζεται στη Λίστα 2.8. Ο αλγόριθμος σάρωσης πολυγώνου (Scan-fill Polygon) μπορεί να γενικευτεί για να χειρίζεται σύνολα πολυγώνων, όταν αυτά είναι ταξινομημένα κατά προτεραιότητα (κατά βάθος zindex).
1. Array ET = readData(edges[])
2. Ymin=min(ET[])
3. AET=null
4. for (y=Ymin; y<=Ymax; y++)
5. {
6. MergeSortbyX(ET[y], AET)
7. FillPairsofX(AET)
8. for (int j=0; j=AET.length; j++)
9. {
10. if (edge[j].Ymax=Y)
11. {
12. remove(adge[j], AET)
13. }
14. else
15. {
16. Edge[j].X=edge[j].X+dx/dy
17. }
18. sortbyX(AET)
19. }
Λίστα 2.8. Ο ψευδοκώδικας του αλγορίθμου Scanfill Polygon
Οι αλγόριθμοι σχεδίασης βασίζονται στον έλεγχο του αν ένα σημείο (εικονοστοιχείο) είναι εσωτερικό ή όχι ενός πολυγώνου. Μια μέθοδος για τον έλεγχο αν το σημείο P ανήκει ή όχι στην επιφάνεια του πολυγώνου Π, το οποίο ορίζεται από την ακολουθία n κορυφών (n1, n2, … n-1 με n ακμές), πραγματοποιείται με την αρίθμηση των τομών της ημιευθείας από το P προς το άπειρο. Σύμφωνα με αυτήν την τεχνική ελέγχου ισοτιμίας (parity test), με αφετηρία το σημείο P, θεωρείται μια ημιευθεία προς οποιαδήποτε κατεύθυνση και μετράται ο αριθμός των τομών με τις ακμές του πολυγώνου (Εικόνα 2.19). Αν αυτός ο αριθμός είναι περιττός, τότε το σημείο P βρίσκεται εντός του πολυγώνου Π. Σε αντίθετη περίπτωση, ένας ζυγός αριθμός τομών σημαίνει ότι το σημείο P ανήκει στην εξωτερική περιοχή του Π.
Η δεύτερη μέθοδος βασίζεται στην καταμέτρηση του αριθμού των περιελίξεων μιας ακτίνας που ενώνει το σημείο Ρ με την περίμετρο μιας κλειστής καμπύλης Κ για μια πλήρη περιδιάβαση (
Εικόνα 2.20). Οι περιελίξεις ορίζονται ως:
{Εξ. 2.23} |
Για κάθε περιστροφή προς τη θετική φορά (δηλαδή αντίθετα με τους δείκτες του ρολογιού) το Ω(Κ,Ρ) αυξάνεται κατά μία μονάδα. Αντίθετα, η περιστροφή προς την αρνητική φορά (σύμφωνα με τους δείκτες του ρολογιού) αφαιρεί από το Ω (Κ,Ρ) μία μονάδα. Αν στο τέλος ο αριθμός των περιελίξεων είναι περιττός αριθμός, τότε το σημείο Ρ βρίσκεται εντός της κλειστής καμπύλης Κ, διαφορετικά είναι εκτός.
Εικόνα 2.19. Έλεγχος εσωτερικότητας σημείου με έλεγχο ισοτιμίας (parity test)
Εικόνα 2.20. Έλεγχος εσωτερικότητας σημείου με καταμέτρηση του αριθμού των περιελίξεων
Το πρόβλημα του χρωματισμού του εσωτερικού ενός πολυγώνου, δηλαδή σχεδιασμού της επιφάνειας που προσδιορίζεται με βάση μια κλειστή πολυγραμμή μπορεί να διατυπωθεί ως το πρόβλημα επιλογής των εικονοστοιχείων της περιμέτρου και του συνόλου των εσωτερικών εικονοστοιχείων. Για να γεμίσουμε το εσωτερικό ενός πολυγώνου μπορούμε να χρησιμοποιήσουμε τον αλγόριθμο σάρωσης πολυγώνου για να προσδιορίσουμε τα σημεία τομής με τη γραμμή σάρωσης και σε κάθε βήμα σχεδιάζουμε το ευθύγραμμο τμήμα που ενώνει δύο σημεία τομής (PolygonScan-Conversion). Εναλλακτικά μπορούμε να ξεκινήσουμε με ένα εικονοστοιχείο που γνωρίζουμε ότι είναι εσωτερικό του πολυγώνου κα γεμίζουμε τη γειτονική περιοχή μέχρι να συναντήσουμε τα όρια του πολυγώνου.
Ο αλγόριθμος εσωτερικού γεμίσματος θεωρεί ότι έχει σχεδιαστεί πρώτα η περίμετρος του πολυγώνου και έχει βρεθεί ένα εσωτερικό σημείο που θα θεωρηθεί ως το σημείο εκκίνησης. Ο ψευδοκώδικας του αλγορίθμου φαίνεται στη Λίστα 2.9. Η επαναληπτική κλήση της συνάρτησης fillPolygon γίνεται για τα γειτονικά σημεία. Εδώ μπορεί να οριστεί μια γειτονιά είτε πέντε (5) είτε εννέα (9) σημείων (Εικόνα 2.21). Η λίστα του ψευδοκώδικα έχει γραφτεί για μια περιοχή οκτώ σημείων που περιλαμβάνει και τα διαγώνια.
1. fillPolygon(x,y)
2. {
3. Color c
4. C=getColor(x,y)
5. If (c<>fill_color)
6. {
7. setPixel(x,y,color)
8. fillPolygon(x-1,y-1)
9. fillPolygon(x,y+1)
10. fillPolygon(x+1,y+1)
11. fillPolygon(x+1,y)
12. fillPolygon(x+1,y+1)
13. fillPolygon(x,y+1)
14. fillPolygon(x-1,y+1)
15. fillPolygon(x-1,y)
16. }
17. }
Λίστα 2.9. Ο κώδικας χρωματισμού της εσωτερικής περιοχής πολυγώνου
Εικόνα 2.21. Περιοχές εικονοστοιχείων: α) 4 σημείων (αριστερά) και β) 8 σημείων (δεξιά)
Εικόνα 2.22. Πρόωρος τερματισμός αλγορίθμου: η τετραπλή αναδρομική κλήση σταματάει στο στένωμα (πάνω), ενώ η οκταπλή καταφέρνει και ολοκληρώνει το γέμισμα (κάτω)
Για περιοχές με τετραπλή σύνδεση, οι τέσσερις αναδρομικές κλήσεις της fill- Polygon κρίνονται επαρκείς. Σε διαφορετική περίπτωση οι περιοχές με οκταπλή σύνδεση χρειάζονται και τις οκτώ αναδρομικές κλήσεις για να καλύψουν τη γειτονιά των 9 σημείων. Υπάρχουν, όμως, και μειονεκτήματα των δύο προσεγγίσεων. Η τετραπλή σύνδεση ενδέχεται σε ορισμένες περιπτώσεις να σταματά πρόωρα, όπως η περίπτωση στην Εικόνα 2.22 (πάνω) όπου το πολύγωνο συνεχίζεται προς την πάνω δεξιά κατεύθυνση, αλλά το στένωμα στη μέση κάνει τον αλγόριθμο που βασίζεται στην τετραπλή σύνδεση να σταματήσει, ενώ η οκταπλή σύνδεση του εικονοστοιχείου θα μπορούσε να ολοκληρώσει το γέμισμα. Αντίστοιχα, ούτε η οκταπλή σύνδεση δεν είναι απαλλαγμένη από προβλήματα καθώς η περίπτωση στην Εικόνα 2.22 (κάτω) δείχνει το φαινόμενο της διαρροής προς ένα γειτονικό σχήμα.
Μέχρι στιγμής έχουμε εξετάσει τη σχεδίαση ευθύγραμμων τμημάτων και πολυγώνων. Μια άλλη μεγάλη κατηγορία βασικών σχημάτων είναι οι κωνικές τομές. Ξεκινώντας με τον κύκλο που είναι το πιο απλό παράδειγμα κωνικής τομής, τότε από τη γνωστή εξίσωση του κύκλου αν λύσουμε ως προς y:
{Εξ. 2.24} |
Με αυτόν τον τρόπο υπολογίζονται ζεύγη σημείων (x, y) που χρωματίζονται για να σχεδιαστεί η περίμετρος του κύκλου. Εξετάζοντας τώρα το πρόβλημα της σχεδίασης π.χ. στο δεύτερο οκταμόριο, ο άξονας που μεταβάλλεται γρηγορότερα είναι ο χ. Δηλαδή, αν ένα σημείο διατρέχει τον κύκλο σύμφωνα με τους δείκτες του ρολογιού, τότε η κάθε επόμενη θέση του θα διαφέρει κατά ένα εικονοστοιχείο ως προς τον οριζόντιο άξονα, ενώ ο κάθετος άξονας θα μειώνεται κατά ένα σε κάποιες περιπτώσεις. Η εφαρμογή μιας λύσης που βασίζεται στην εξίσωση του κύκλου αφήνει κενά στη σχεδίαση, πράγμα μη επιτρεπτό. Μάλιστα, όσο αυξάνεται η κλίση, τόσο αυξάνονται και τα κενά που προκύπτουν ενδιάμεσα. O Πίνακας 2.4 για παράδειγμα, παρουσιάζει έναν κύκλο ακτίνας r=10 στον οποίο προκύπτουν μη συνεχόμενες για το y τιμές.
Πίνακας 2.4. Βήματα εκτέλεσης του αλγορίθμου σχεδίασης με βάση την εξίσωση του κύκλου από όπου φαίνεται ότι η σχεδίαση δε δίνει ικανοποιητικό αποτέλεσμα διότι δημιουργούνται κενά
| Σχεδίαση με βάση την καρτεσιανή εξίσωση της περιφέρειας του κύκλου | Βήματα | Χ | Y | Επιλεγμένο Εικονοστοιχείο |
|---|---|---|---|---|
|
||||
| 1 | 1 | 9.95 | (1, 10) | |
| 2 | 2 | 9.8 | (2, 10) | |
| 3 | 3 | 9.54 | (3, 10) | |
| 4 | 4 | 9.17 | (4, 9) | |
| 5 | 5 | 8.66 | (5, 9) | |
| 6 | 6 | 8.00 | (6, 8) | |
| 7 | 7 | 7.14 | (7, 7) | |
| 8 | 8 | 6.00 | (8, 6) | |
| 9 | 9 | 4.36 | (9, 4) | |
| 10 | 10 | 0.00 | (10, 0) |
Στη συνέχεια θα παρουσιαστούν τρόποι σχεδίασης της περιμέτρου με βάση την οκταπλή συμμετρία που παρουσιάζει το σχήμα του κύκλου. Αυτό σημαίνει ότι αν σχεδιαστεί ένα από τα οκταμόριά του, τα υπόλοιπα τμήματα του κύκλου μπορούν να προκύψουν με εναλλαγή προσήμων στις τιμές των x και y. Αν έχουμε έναν κύκλο ακτίνας r=1 και κέντρο την αρχή των αξόνων, τότε με δεδομένο ένα σημείο (x,y) που ανήκει στον κύκλο μπορούμε να θεωρήσουμε με βεβαιότητα ότι και τα σημεία: [(y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)] ανήκουν επίσης στον ίδιο κύκλο. Αυτό είναι απόρροια της οκταπλής συμμετρίας του κύκλου.
Παρατηρούμε ότι σε κάθε μετατόπιση προς τα δεξιά, κατεύθυνση αύξησης του Χ κατά μία μονάδα σε κάθε βήμα, το επόμενο σημείο προς επιλογή είναι είτε το διπλανό του (Xn+1,Yn), είτε το διαγωνίως πιο κάτω (Xn+1,Yn+1), ανάλογα με το πιο από τα δύο βρίσκεται κοντύτερα στον κύκλο (Εικόνα 2.23).
Εικόνα 2.23. Σχεδίαση με βάση την εξίσωση του κύκλου
Αν τώρα θέσουμε έναν παράγοντα μετατόπισης κατά μισό εικονοστοιχείο προς τα πάνω, η συνάρτηση κύκλου γράφεται:
{Εξ. 2.25} |
Αυτή είναι η μεταβλητή σφάλματος που δίνει την απόφαση για την επιλογή του καταλληλότερου εικονοστοιχείου. Αν η παραπάνω ποσότητα προκύψει μικρότερη του μηδενός, τότε το σημείο ανήκει στο εσωτερικό του κύκλου. Αν είναι μεγαλύτερη του μηδενός, τότε δεν ανήκει στον κύκλο και είναι εξωτερικό σημείο. Τέλος, αν ισούται με μηδέν, τότε είναι σημείο της περιφέρειας του κύκλου.
{Εξ. 2.26} |
Αν και η μεταβλητή σφάλματος υπολογίζεται ότι πρέπει να αρχικοποιηθεί στην τιμή:
{Εξ. 2.27} |
είναι τελικά δυνατόν -χωρίς σημαντικό σφάλμα- η αρχικοποίηση να πραγματοποιηθεί στην τιμή –r. Συνολικά η λύση αυτή εκφρασμένη σε ψευδοκώδικα φαίνεται στη Λίστα 2.10.
1. int x=0
2. int y=r
3. int e=-r
4. while (x <= y)
5. {
6. setPixel(y, x)
7. setPixel (y, -x)
8. setPixel (x, -y)
9. setPixel (-x, -y)
10. setPixel (-y, -x)
11. setPixel (-y, x)
12. setPixel (-x, y)
13. e=e+2*x+1
14. x=x+1
15. if (e >= 0)
16. {
17. e=e-2y+2
18. y=y-1
19. }
20. }
Λίστα 2.10. Ο ψευδοκώδικας του αλγορίθμου σχεδίασης κύκλου που βασίζεται στην οκταπλή συμμετρία και στην ιδέα του Bresenham για μείωση του υπολογιστικού κόστους
Οι καμπύλες ελεύθερης μορφής χρησιμοποιούνται κατά κόρον στα γραφικά για να αποδώσουν ποικίλα σχήματα και αντικείμενα σε περιβάλλοντα διανυσματικής σχεδίασης, αλλά και για περιγραφή της κίνησης σε περιβάλλοντα σχεδιοκίνησης (animation). Το πρόβλημα της σχεδίασης καμπυλών μπορεί να λυθεί εφόσον μιλάμε για μοντέλα ομαλών καμπυλών που ορίζονται με μαθηματικό τρόπο. Οι εύκαμπτες καμπύλες (splines) ορίζονται με βάση ένα σύνολο από σημεία ελέγχου όπως είναι οι παραμετρικές καμπύλες Bezier.
Ένας αλγόριθμος σχεδίασης, προκειμένου να σχεδιάσει μια καμπύλη Bezier, χρειάζεται να δέχεται ως είσοδό του τη λίστα των σημείων ελέγχου τα οποία θα ορίζουν μοναδικά το σχήμα της καμπύλης (ή της επιφάνειας όταν πρόκειται για γενίκευση σε περισσότερες της μίας διάστασης). Στις καμπύλες Bezier, η μορφή της καμπύλης εξαρτάται μόνο από τα σημεία ελέγχου που ορίζουν την καμπύλη και άρα υπάρχει η επιθυμητή σταθερότητα. Συνήθως χρειάζεται να λυθεί το πρόβλημα της σχεδίασης κυβικής καμπύλης (τέσσερα σημεία ελέγχου) καθώς μεγαλύτερης πολυπλοκότητας καμπύλες προκύπτουν από συνδυασμούς διασυνδεμένων καμπυλών Bezier με επιβολή συνθηκών συνέχειας μεταξύ των τμημάτων (συνέχεια θέσης, κλίσης, καμπυλότητας).
Η καμπύλη Bezier βρίσκεται εντός του κυρτού κελύφους ή περιβλήματος (convexhull) που ορίζεται από τα σημεία ελέγχου της, ενώ παρεμβάλλεται στο πρώτο και στο τελευταίο σημείο διότι P(0)=p0 και P(n)=pn. Αυτό για το πρόβλημα της σχεδίασης σημαίνει ότι το πρώτο και το τελευταίο σημείο της καμπύλης είναι γνωστά, ενώ αναζητούνται τα ενδιάμεσα. Σε περίπτωση συγγραμμικών σημείων ελέγχου προκύπτει ευθύγραμμο τμήμα.
Η πολυπλοκότητα της καμπύλης και επομένως και της σχεδίασης είναι ανάλογες με τον αριθμό των σημείων ελέγχου. Έτσι, με n σημεία ελέγχου προκύπτουν n-1 διαδοχικά επίπεδα γραμμικής παρεμβολής για να σχεδιαστεί μια καμπύλη Bezier βαθμού n. Αν B(t) είναι μια καμπύλη Bezier που ορίζεται με βάση τα P0, P1, P2, P3 σημεία ελέγχου και το t παίρνει τιμές στο διάστημα [a, b], τότε για 0 ≤ t ≤ 1 τα διαστήματα t-a ισούνται με t (το πρώτο τμήμα κάθε ευθύγραμμου τμήματος που ενώνει δύο διαδοχικά σημεία ελέγχου) και το b-t γίνεται 1-t που αντιστοιχεί στο δεύτερο τμήμα (Εικόνα 2.24 & Εικόνα 2.25). Ο ψευδοκώδικας του αλγορίθμου deCasteljau παρατίθεται στη Λίστα 2.11. Για να σχεδιάσουμε ολόκληρη την καμπύλη, υπολογίζουμε ένα-ένα τα σημεία και τα συνδέουμε με ευθύγραμμα τμήματα.
Εικόνα 2.24. Το τρίγωνο του de Casteljau
Εικόνα 2.25. Γεωμετρική απόδοση του αλγορίθμου του de Casteljau για σχεδιασμό καμπύλης Bezier
1. point tmpPoint
2. double step=0.001
3. //Φόρτωση σημείων ελέγχου σε πίνακα σημείων
4. array Points[]=getControlPoints
5.
6. //Για όλα τα σημεία από την αρχή (0) μέχρι το τέλος (1) με βήμα όσο το step
7. for (double t=0; t<=1; t+=step)
8. {
9. //Υπολογισμός νέου σημείου de Casteljau
10. tmpPoint=getCasteljauPoint(length(Points)-1, 0, t);
11. //Χρωματισμός του νέου σημείου στον καμβά
12. setPixel(tmpPoint.X, tmpPoint.Y);
13. }
14.
15. //Υπολογισμός νέου σημείου με αναδρομικές κλήσεις
16. point getCasteljauPoint (int r, int I, double t)
17. {
18. if (r==0) return Points[i]
19. point p1 = getCasteljauPoint(r-1, i, t)
20. point p2 = getCasteljauPoint(r-1, i+1, t)
21. point resPoint
22. resPoint.X = int((1-t)*p1.X+t*p2.X)
23. resPoint.Y = int((1-t)*p1.Y+t*p2.Y))
24. return resPoint
25. }
Λίστα 2.11. Ο ψευδοκώδικας του αλγορίθμου de Casteljau
Η δειγματοληψία είναι η μετατροπή συνεχούς σήματος σε διακριτό, όπου δείγμα του σήματος είναι μια τιμή του σήματος που λήφθηκε σε συγκεκριμένη χρονική στιγμή. Στη διαδικασία της δειγματοληψίας σημαντικό ρόλο παίζει ο δειγματολήπτης, δηλαδή το σύστημα λήψης δειγμάτων σε σταθερά χρονικά διαστήματα (περίοδος T) με την επιθυμητή συχνότητα (fs συχνότητα δειγματοληψίας). Η δειγματοληψία έχει νόημα για χρονικά μεταβαλλόμενα σήματα μίας διάστασης (π.χ. ήχος) ή περισσότερων διαστάσεων (π.χ. εικόνα) όπου το ανακτώμενο σήμα περιγράφεται από τη σχέση:
{Εξ. 2.28} |
Το βασικό ερώτημα είναι με ποια συχνότητα πρέπει να γίνει η δειγματοληψία έτσι ώστε να μην υπάρχει απώλεια. Το ανακατασκευασμένο σήμα έχει καλή πιστότητα όσο η συχνότητα δειγματοληψίας είναι μεγάλη. Αντίθετα, η πιστότητα του ανακτώμενου σήματος μειώνεται όσο μειώνεται η συχνότητα λήψης δειγμάτων (Εικόνα 2.26).Το θεώρημα δειγματοληψίας του Nyquist προβλέπει ότι το ανακτώμενο σήμα προσεγγίζει πολύ καλά το αρχικό σήμα και έχει ανεκτή απώλεια, όταν η συχνότητα δειγματοληψίας είναι υπερδιπλάσια της μέγιστης συχνότητας του αρχικού σήματος, δηλαδή όταν:
{Εξ. 2.29} |
όπου:
fs: η συχνότητα δειγματοληψίας και
fn: η συχνότητα του αρχικού σήματος.
Οι παραβιάσεις του παραπάνω κανόνα, όπως θα δούμε παρακάτω, έχουν συνέπειες στην ποιότητα του εξαγόμενου αποτελέσματος, τόσο στο πεδίο του χώρου όσο και στο πεδίο του χρόνου.
Εικόνα 2.26. Δειγματοληψία ενός σήματος υψηλής συχνότητας (μπλε γραμμή) με μικρή συχνότητα οδηγεί σε ανάκτηση λάθος σήματος (κόκκινη γραμμή)
Εικόνα 2.26. Δειγματοληψία ενός σήματος υψηλής συχνότητας (μπλε γραμμή) με μικρή συχνότητα οδηγεί σε ανάκτηση λανθασμένου σήματος (κόκκινη γραμμή).
Τα αντικείμενα που θέλουμε να αναπαραστήσουμε σε πλεγματικές οθόνες είναι συνεχή σήματα, ενώ αντίθετα οι οθόνες αποτελούνται από διακριτά στοιχεία (εικονοστοιχεία). Σε μια εικόνα για παράδειγμα, η ψηφιακή αναπαράσταση της πραγματικότητας (συνεχές δισδιάστατο σήμα) αποτελείται από δειγματοληπτικές μετρήσεις (εικονοστοιχεία). Η πιστότητα της αναπαραγωγής σύμφωνα με το θεώρημα Nyquist απαιτεί συχνότητα δειγματοληψίας τουλάχιστον διπλάσια της μέγιστης παρατηρούμενης για την αποφυγή του φαινομένου της ταύτισης. Δηλαδή, ανάλογα με το τι αναπαρίσταται στην εικόνα (μέγεθος αντικειμένων) χρειαζόμαστε μεγαλύτερη πυκνότητα εικονοστοιχείων (ανάλυση φωτογραφικής μηχανής).
Από την άλλη πλευρά, στη συνθετική εικόνα, η οπτική απόδοση σχημάτων με εικονοστοιχεία, δηλαδή ψηφίδες χρώματος με συγκεκριμένες διαστάσεις προκαλεί απώλειες στις λεπτομέρειες των σχημάτων. Όσο μικρά και αν είναι τα εικονοστοιχεία, πάντοτε θα υπάρχει μια διαφορά ανάμεσα στη μαθηματική έκφραση των σχημάτων και την οπτική απόδοση σε πλεγματικές οθόνες. Το πρόβλημα της απώλειας της λεπτομέρειας εξαιτίας του μη-μηδενικού πάχους των εικονοστοιχείων ονομάζεται ταύτιση.
Στην Εικόνα 2.27 φαίνονται μια σειρά από βασικά σχήματα που σε άπειρη ανάλυση (μηδενικές διαστάσεις του σημείου) θα φαινόταν όπως οι κόκκινες γραμμές. Στην πραγματικότητα όμως, επειδή τα εικονοστοιχεία έχουν διαστάσεις και η ανάλυση είναι πεπερασμένη, τα σχήματα εμφανίζονται όπως φαίνεται από το γκρι χρώμα. Έτσι για παράδειγμα μια ευθεία μπορεί να εμφανίζεται ως τεθλασμένη γραμμή, ο κύκλος πάνω αριστερά εμφανίζεται ως τετράγωνο, η έλλειψη ως ένα ορθογώνιο παραλληλόγραμμο ή μια γραμμή, ενώ το τρίγωνο και η καμπύλη επιφάνεια στα δεξιά εμφανίζονται οδοντωτά. Αντικείμενα που είναι μικρότερα του ενός εικονοστοιχείου μπορεί να μην εμφανίζονται καθόλου, ή να εμφανίζονται σταδιακά καθώς κινούνται στο πλάνο. Η κατάσταση χειροτερεύει όσο τα λεπτομερή αντικείμενα είναι επαναλαμβανόμενα σε μικρή απόσταση το ένα από το άλλο. Παρατηρούμε, λοιπόν, ότι η λανθασμένη εμφάνιση αφορά περισσότερο τις λεπτομέρειες, δηλαδή τις υψηλές συχνότητες της εικόνας.
Στα κινούμενα γραφικά (π.χ. ο κινηματογράφος, το animation κτλ.) το φαινόμενο της ταύτισης εμφανίζεται σε δύο μορφές: μία στο πεδίο του χώρου όπως εξετάστηκε προηγούμενα και μία στο πεδίο του χρόνου. Η δεύτερη περίπτωση μπορεί να φανεί πολύ χαρακτηριστικά στον τρόπο που εμφανίζεται η κίνηση των τροχών σε μια άμαξα, ή στην κίνηση ενός έλικα σε έργα του κινηματογράφου.
Στην Εικόνα 2.28 ο τροχός της άμαξας περιστρέφεται σύμφωνα με τους δείκτες του ρολογιού (τρέχει προς τα δεξιά). Στην πρώτη γραμμή, η συχνότητα δειγματοληψίας είναι μικρότερη της συχνότητας περιστροφής του τροχού με αποτέλεσμα να φαίνεται ότι η κίνηση είναι προς τα πίσω. Στη δεύτερη περίπτωση (δεύτερη γραμμή), οι συχνότητες περιστροφής και δειγματοληψίας είναι ακριβώς ίδιες με αποτέλεσμα ο τροχός να φαίνεται ακίνητος. Στην τελευταία περίπτωση (κατώτερη γραμμή) η δειγματοληψία συμβαίνει με μεγαλύτερη συχνότητα από ότι η περιστροφή, με αποτέλεσμα να φαίνεται μεν η σωστή η φορά περιστροφής αλλά να γίνεται λάθος εκτίμηση της ταχύτητας περιστροφής.
Εικόνα 2.27. Το πρόβλημα της ταύτισης στο πεδίο του χώρου
Εικόνα 2.28. Το πρόβλημα της ταύτισης στο πεδίο του χρόνου
Στην περίπτωση βάθους χρώματος ίσου με 1, δηλαδή χρήσης μόνο ενός χρώματος στην πλεγματική οθόνη (π.χ. μαύρο πάνω σε λευκό φόντο) δεν υπάρχουν πολλές επιλογές για αντιμετώπιση του φαινομένου της ταύτισης. Με τη χρήση περισσοτέρων χρωμάτων μπορούν να εφαρμοστούν κάποιες τεχνικές για να μειωθούν οι αρνητικές επιπτώσεις της ταύτισης.
Για παράδειγμα θα μπορούσαμε να χρησιμοποιήσουμε τον αποδοτικό αλγόριθμο του Bresenham για σχεδίαση ευθύγραμμου τμήματος λαμβάνοντας υπόψη και την απόσταση του εικονοστοιχείου από τη γραμμή (Weighted area sampling). Η απόσταση από το κέντρο του εικονοστοιχείου D μέχρι το κέντρο της γραμμής είναι κατά απόλυτη τιμή μικρότερη ή το πολύ ίση με 0.5. Αντίστοιχα, αν η κλίση της ευθείας είναι a, τότε η απόσταση του πιο πάνω εικονοστοιχείου είναι |D-cosa|<=1.5 και του πιο κάτω |D+cosa|<=1.5. Παρομοίως, προσθαφαιρώντας το ημίτονο του a στην απόσταση D προκύπτουν οι αποστάσεις των γειτονικών αριστερά και δεξιά. Αν ο χρωματισμός του εικονοστοιχείου προκύπτει Χp, τότε μπορούμε να τροποποιήσουμε την απόχρωση κατά Χp*(1-D/1.5) [Chen, 2008]. Έτσι όταν ένα εικονοστοιχείο βρίσκεται ακριβώς πάνω στη γραμμή (D=0), τότε ο χρωματισμός του δεν αλλάζει. Όταν βρίσκεται πολύ μακριά από το κέντρο της γραμμής (D=1.5), τότε ο χρωματισμός του μηδενίζεται. Όλα τα ενδιάμεσα τροποποιούν τον χρωματισμό τους έτσι ώστε να είναι ανάλογος της απόστασής τους από την ευθεία (Εικόνα 2.29).
Παρακάτω θα εξετάσουμε δύο γενικές κατευθύνσεις στην αντιμετώπιση του προβλήματος της ταύτισης. Η πρώτη εφαρμόζει τεχνικές αντιταύτισης με προ-φιλτράρισμα, όπου κάθε εικονοστοιχείο θεωρείται ένα παράθυρο μέσα στο οποίο αποκόπτονται όλες οι επιφάνειες που έχουν επικάλυψη με αυτό. Ο άλλος τρόπος αντιμετώπισης είναι η αντιταύτιση με μετα-φιλτράρισμα κατά την οποία αυξάνεται η συχνότητα δειγματοληψίας για να υποβιβαστεί στη συνέχεια η ανάλυση του αποτελέσματος με την τεχνική της συνέλιξης.
Εικόνα 2.29. Υπολογισμός της απόχρωσης ανάλογα με την απόσταση από την ευθεία
Ο αλγόριθμος του Catmull σχεδιάζει πολύγωνα με αντιταύτιση θεωρώντας το κάθε εικονοστοιχείο μια περιοχή όπου ένα ή περισσότερα πολύγωνα έχουν επικάλυψη. Το τελικό χρώμα του εικονοστοιχείου προκύπτει από την ποσοστιαία συνδρομή όλων των σχημάτων που έχουν ορατή παρουσία. Στην ποσόστωση κάθε χρώματος συνυπολογίζεται και το φόντο. Το τελικό χρώμα του εικονοστοιχείου i, για n πολύγωνα C1, C2, …Cn που καταλαμβάνουν επιφάνεια A1, A2, …An αντίστοιχα υπολογίζεται με βάση τον τύπο:
{Εξ. 2.30} |
όπου Cb είναι το χρώμα υποβάθρου (φόντο) και Ab η επιφάνεια δεν καλύφθηκε από κανένα άλλο χρώμα. Τα βήματα του αλγορίθμου είναι:
Βήμα 1: Αποκοπή πολυγώνων στο παράθυρο του εικονοστοιχείου
Βήμα 2: Ταξινόμηση επιφανειών κατά βάθος και προβολή τους (αποκοπή) κατά αντίστροφη σειρά βάθους έτσι ώστε να αποκρύπτονται τα κρυμμένα τμήματα.
Βήμα 3: Υπολογισμός του τελικού χρωματισμού
Στην Εικόνα 2.30 φαίνεται ένα παράδειγμα εικονοστοιχείου στην περιοχή του οποίου προβάλλονται τμήματα 4 σχημάτων με διάφορα χρώματα το καθένα και σε διάφορα βάθη z-index (απόσταση από τον παρατηρητή). Για κάθε σχήμα υπολογίζεται το ποσοστό κάλυψης της συνολικής επιφάνειας του εικονοστοιχείου για να υπολογιστεί το ποσοστό συμμετοχής του χρώματός του στη διαμόρφωση του τελικού χρώματος. Η αριθμητική επίλυση του τρέχοντας παραδείγματος (Πίνακας 2.5) υπολογίζει την τιμή του τελικού χρώματος σε:
C = round( [255,0,0]*0.059 + [0,255,0]*0.2078 + [255,29,162]*0.1891 + [0,0,255]*0.1949 + [249,232,91]*0.3490 ) =[150, 139, 112].
Εικόνα 2.30. Παράδειγμα περιοχής εικονοστοιχείου (αριστερά) που ο αλγόριθμος Catmull θα υπολογίσει το εμβαδό κάθε περιοχής για να εξάγει το τελικό χρώμα (δεξιά)
Ο αλγόριθμος του Catmull εξάγει πολύ καλής ποιότητας αποτελέσματα, αλλά είναι υπολογιστικά ακριβός λόγω του μεγάλου αριθμού υπολογισμών που απαιτεί η αλγοριθμική του. Επίσης, στην κριτική που δέχεται, προστίθεται το γεγονός ότι θεωρεί επιφάνειες με σταθερή χρωματική απόχρωση και δεν μπορεί να αποδώσει επιφάνειες που είναι υπενδεδυμένες με υφή.
Πίνακας 2.5. Χρωματικές περιοχές του τρέχοντος παραδείγματος και το ποσοστό κάλυψης επιφανείας τους επί του εικονοστοιχείου
| Περιοχή | Χρώμα RGB | Επιφάνεια % |
|---|---|---|
| Κόκκινη | [255, 0, 0] | 5.90 |
| Πράσινη | [0, 255, 0] | 20.78 |
| Ρόζ | [255, 29, 162] | 18.91 |
| Μπλε | [0, 0, 255] | 19.49 |
| Κίτρινο | [249, 232, 91] | 34.90 |
Ο αλγόριθμος A-buffer είναι γρηγορότερος από τον αλγόριθμο του Catmull διότι αποφεύγει τον υπολογιστικά ακριβό λεπτομερή υπολογισμό του εμβαδού κάθε επιφάνειας και μάλιστα ο υπολογιστικός φόρτος είναι ανάλογος της πολυπλοκότητας που επικρατεί στο παράθυρο κάθε εικονοστοιχείου. Ο A-buffer ουσιαστικά προσθέτει δυνατότητες αντιταύτισης στον z-buffer με αποδοτικό τρόπο.
Για να επεξεργαστεί τα πολύγωνα που αλληλεπικαλύπτονται εντός του παραθύρου του εικονοστοιχείου, προηγείται η ταξινόμηση ως προς το Z (βάθος) και αρχίζει την επεξεργασία από το πλησιέστερο. Έστω ότι η επιφάνεια του εικονοστοιχείου χωρίζεται από μια τετραγωνική περιοχή 8χ8 δυαδικών ψηφίων (64 bit). Αυτό ονομάζεται λογικό πεδίο. Ο αλγόριθμος ξεκινάει υπολογίζοντας για κάθε πλευρά του πολυγώνου μια μάσκα ίσου μεγέθους με το λογικό πεδίο όπου οι θέσεις από την πλευρά και δεξιότερα λαμβάνουν την τιμή 1, ενώ οι άλλες θέσεις έχουν τιμή 0.
Η μάσκα του κάθε πολυγώνου προκύπτει εφαρμόζοντας τη λογική πράξη XOR μεταξύ των μασκών κάθε πλευράς πολυγώνου (Εικόνα 2.31). Το τελικό αποτέλεσμα είναι κάθε πολύγωνο να αποτυπώνεται πάνω στη μάσκα του με έναν αριθμό από 1 στο εσωτερικό του, ενώ τα 0 δείχνουν σημεία που ανήκουν στην εξωτερική πλευρά (το χρώμα του φόντου ή το υπάρχον χρώμα από άλλο πολύγωνο).
Εικόνα 2.31. Παράδειγμα υπολογισμού μάσκας πολυγώνου με 64bit λογικό πεδίο
Η μάσκα κάλυψης Μ αποτυπώνει σε κάθε βήμα του αλγορίθμου τις περιοχές του εικονοστοιχείου που έχουν καλυφθεί ήδη εξαιτίας κάποιου άλλου πολυγώνου. Αρχικοποιείται στην τιμή 1 σε κάθε θέση του, πράγμα που σημαίνει ότι αρχικά δεν έχει καλυφθεί καμία θέση από κανένα πολύγωνο (επικρατεί παντού το χρώμα υποβάθρου). Για κάθε ένα πολύγωνο από το πλησιέστερο προς το πιο απομακρυσμένο θα υπολογιστούν η μάσκα κάλυψης Μi και η μάσκα πολυγώνου Πi.
Σε κάθε βήμα υπολογίζεται και η ορατή επιφάνεια πολυγώνου Oi και η νέα κατάσταση της μάσκας κάλυψης Μi, όπου i είναι το πολύγωνο που μόλις επεξεργάστηκε ο αλγόριθμος (ο Πίνακας 2.6 παρουσιάζει ένα αναλυτικό παράδειγμα). Η μάσκα κάλυψης προκύπτει από τον υπολογισμό της λογικής πράξης AND (ΚΑΙ) μεταξύ της υφιστάμενης μάσκας κάλυψης και της αντίστροφης μάσκας πολυγώνου που μόλις επεξεργάστηκε ο αλγόριθμος:
{Εξ. 2.31} |
όπου Mi = Ι για i=0. Η ορατή επιφάνεια του κάθε πολυγώνου προκύπτει από τη λογική πράξη AND μεταξύ της μάσκας κάλυψης και της μάσκας πολυγώνου:
{Εξ. 2.32} |
Αν Ci είναι το χρώμα του πολυγώνου i, τότε ο αριθμός των 1 στην ορατή περιοχή του πολυγώνου (Ai) εκφρασμένου ως ποσοστό επί του συνόλου των σημείων n εκφράζει τη συμμετοχή του χρώματος στην διαμόρφωση του τελικού χρώματος του εικονοστοιχείου. Η μάσκα κάλυψης μας δίνει το ποσοστό συμμετοχής του χρώματος υποβάθρου σαν να ήταν ένα τρίτο σχήμα. Έτσι, συνολικά έχουμε:
{Εξ. 2.33} |
Η εφαρμογή του παραπάνω τύπου στο τρέχον παράδειγμα, αν το πολύγωνο 1 έχει χρώμα κόκκινο (255,0,0) και το πολύγωνο 2 έχει χρώμα πράσινο (0,255,0) με γκρι φόντο (126,126,126), τότε το τελικό χρώμα προκύπτει από τον παρακάτω υπολογισμό (Εικόνα 2.32):
Χ = 18/64 * (255,0,0)+21/64 * (0,255,0) + 25/64 * (255,255,255) = (171, 183, 100).
Εικόνα 2.32. Παράδειγμα εφαρμογής του αλγορίθμου A-Buffer: α. περιοχή του παραθύρου σύγκλισης πολλών σχημάτων (αριστερά), β. το τελικό χρώμα του εικονοστοιχείου (δεξιά)
Πίνακας 2.6. Μάσκες κάλυψης, πολυγώνων και ορατές επιφάνειες του τρέχοντος παραδείγματος.
| Βήμα | Μάσκα Κάλυψης | Μάσκες Πολυγώνων | Ορατές Επιφάνειες |
|---|---|---|---|
| 1 |
|
|
|
| 2 |
|
|
|
| 3 |
|
Οι τεχνικές αντιταύτισης που μελετήθηκαν μέχρι τώρα εφαρμόζονται πριν από τη ψηφιοποίηση και άρα μπορούν να χειριστούν μεγάλες συχνότητες χωρίς περιορισμούς. Άλλες διαδεδομένες μέθοδοι που ενεργούν μετά την ψηφιοποίηση είναι απλές στην υλοποίησή τους και ονομάζονται μέθοδοι αντιταύτισης με υπερδειγματοληψία.
Ως τεχνική, η υπερδειγματοληψία βασίζεται στην ιδέα της αύξησης της ανάλυσης της οθόνης και τον υπολογισμό των μέσων χρωματικών όρων για κάθε περιοχή τελικού εικονοστοιχείου. Έτσι επιτυγχάνεται η μετατόπιση του ορίου Nyquist σε μεγαλύτερες συχνότητες. Αυτή αποτελεί την πιο διαδεδομένη μέθοδο αντιταύτισης λόγω της απλότητάς της στην υλοποίηση. Το βασικό μειονέκτημα είναι ότι όσο αυξάνεται η υποδιαίρεση του εικονοστοιχείου, τόσο αυξάνονται οι οικονομικές και τεχνικές απαιτήσεις διότι η ενδιάμεση εικόνα υψηλής ανάλυσης υπολογίζεται πρώτα στη μνήμη του συστήματος και στη συνέχεια προβάλλεται στην οθόνη ως τελική εικόνα χαμηλότερης ανάλυσης.
Το κάθε εικονοστοιχείο διαιρείται σε μια γειτονιά εικονοστοιχείων κατά πλήθος στοιχείων S (όπου S=2k+1). Η περιοχή αυτή έχει μονό αριθμό εικονοστοιχείων προς την οριζόντια και κάθετη κατεύθυνση για να εφαρμόζεται πιο εύκολα ως μάσκα για τον υπολογισμό του τελικού εικονοστοιχείου. Για παράδειγμα, για μια τελική εικόνα υψηλής ευκρίνειας 1280*720 (921.600 εικονοστοιχεία) δημιουργείται κατά τη δειγματοληψία μια ενδιάμεση εικόνα διαστάσεων 3840*2160 (8294.400 εικονοστοιχεία). Στη συνέχεια απομακρύνονται οι υψηλές συχνότητες που ευθύνονται για το πρόβλημα της ταύτισης και τέλος παράγεται η τελική εικόνα στην επιθυμητή μικρότερη ανάλυση.
Αντί για τον υπολογισμό μέσου όρου, συνήθως η μάσκα εφαρμόζεται ως φίλτρο συνέλιξης που δίνει βαρύτητα στο κεντρικό εικονοστοιχείο λαμβάνοντας υπόψη και το χρώμα των γειτονικών εικονοστοιχείων αλλά με μικρότερους συντελεστές. Η συνέλιξη της εικόνας p με το φίλτρο h υπολογίζεται από τον τύπο:
{Εξ. 2.34} |
όπου ισχύει:
{Εξ. 2.35} |
Η τελευταία συνθήκη (Εξ. 2.35) κρίνεται απαραίτητη ως διόρθωση στους πολλαπλασιαστές των στοιχείων, προκειμένου το άθροισμα των βαρών του πίνακα SxS να είναι ίσο με τη μονάδα και να μην προκύπτουν τιμές μεγαλύτερες από τα επιτρεπτά όρια. Αυτό σημαίνει ότι κάθε τιμή βάρους στη μάσκα της συνέλιξης θα πρέπει να διαιρείται με το άθροισμα των βαρών.
Ας δούμε ένα παράδειγμα όπου η μάσκα της συνέλιξης είναι ένας πίνακας 3x3 και εφαρμόζεται πάνω στην ενδιάμεση εικόνα υψηλής ανάλυσης (που προέκυψε από δειγματοληψία σε υψηλότερη συχνότητα) όπως φαίνεται στην Εικόνα 2.33.
Εικόνα 2.33. Παράδειγμα συνέλιξης με μάσκα 3x3
Η μάσκα εφαρμόζεται διαδοχικά πάνω στα εικονοστοιχεία της εικόνας (από αριστερά προς τα δεξιά και από πάνω προς τα κάτω) για να υπολογίσει την τιμή του κεντρικού εικονοστοιχείου με βάση όχι μόνο το δικό του χρώμα αλλά και αυτά των γειτονικών εικονοστοιχείων. Το τελικό αποτέλεσμα της συνέλιξης για την περιοχή του εικονοστοιχείου (4,4) υπολογίζεται σε:
C(4,4) = 1*255+2*224+1*192+2*224+4*192+2*192+1*224+2*192+1*192=206
Αυτήν την τιμή χρώματος θα αποκτήσει η περιοχή του εικονοστοιχείου (4,4) της ενδιάμεσης εικόνας. Να σημειωθεί ότι το τελικό αποτέλεσμα είναι η περιοχή του (4,4) να θεωρείται ένα μόνο εικονοστοιχείο και να κρατείται η τιμή του στο bitmap μειωμένης ανάλυσης.
|
2.6. Προτεινόμενες Ασκήσεις και Προβλήματα |
|
Άσκηση 1)
να βρείτε την Πεπλεγμένη εξίσωση της καμπύλης που προκύπτει από τα παραπάνω. β) Με δεδομένη μια καμπύλη με παραμετρικές εξισώσεις:
να βρείτε την καρτεσιανή έκφραση της καμπύλης.
Άσκηση 2)
Άσκηση 3)
Άσκηση 4)
Άσκηση 5)
Άσκηση 6)
Άσκηση 7)
|
|
