7.6. Γράφοι Σκηνής

Παρά το γεγονός ότι έχουμε εισάγει πολλαπλά πρότυπα γραφικών, η ανάπτυξη μας ως τώρα έχει σε μεγάλο βαθμό βασιστεί σε μια εφαρμογή της λογικής του μοντέλου συνθετικής κάμερας. Η επιλογή αυτή γίνεται γιατί θέλουμε να στηρίξουμε διαδραστικές τρισδιάστατες εφαρμογές με το παρόν διαθέσιμο εξοπλισμό και λογισμικό. Ως εκ τούτου, έχουμε τονίσει έναν τρόπο γραφικής αναπαράστασης στην οποία τα γεωμετρικά αποστέλλονται στην GPU και εμφανίζονται στην οθόνη σχεδόν αμέσως μετά. Δεν έχουμε κάνει πλήρη χρήση του γεγονότος ότι αφού τα δεδομένα είναι στην GPU, μπορούν να επαναχρησιμοποιηθούν χωρίς να αναδημιουργηθούν εκ νέου στην εφαρμογή.

Τώρα προχωράμε σε ένα υψηλότερο επίπεδο αφαίρεσης και εισάγουμε δύο σημαντικές έννοιες. Πρώτον, έχουμε διευρύνει την έννοια του αντικειμένου από τα γεωμετρικά αντικείμενα, όπως απλά πολύγωνα και διανύσματα, ώστε να περιλαμβάνουμε τα περισσότερα από τα στοιχεία μέσα σε ένα πρόγραμμα γραφικών, όπως κάμερες/θεατές, φώτα, καθώς και οι ιδιότητες υλικών απεικόνισης και φυσικής. Δεύτερον, έχουμε επικεντρωθεί σε αντικείμενα που υφίστανται ακόμη και αν έχουν, ήδη, σχεδιαστεί οι αναπαραστάσεις τους ακόμη και αν δεν τα εμφανίσουμε ποτέ στην οθόνη. Στο παρόν κεφάλαιο θα ερευνήσουμε άλλες προσεγγίσεις, όπως η χρήση αντικειμενοστραφών κλάσεων σε C ++ ή δομές στο C και πώς ενσωματώνεται λειτουργικότητα μέσα στους κόμβους που αντιπροσωπεύουν αντικείμενα μιας σκηνής.

7.6.1. Μέθοδοι και Παράμετροι

Τα προγράμματά μας χειρίζονται δεδομένα. Τα δεδομένα μπορεί να είναι σε πολλές μορφές, που κυμαίνονται από αριθμούς, σε strings, μέχρι τις γεωμετρικές οντότητες που χτίζουμε στις εφαρμογές μας. Στο παραδοσιακό «διαδικαστικό» προγραμματισμό, ο προγραμματιστής γράφει κώδικα για να χειριστεί τα δεδομένα, συνήθως μέσω συναρτήσεων. Τα δεδομένα εισόδου μεταφέρονται στη συνάρτηση μέσω των ορισμάτων της συνάρτησης. Τα αποτελέσματα επιστρέφονται κατά παρόμοιο τρόπο. Για να χειριστεί τα δεδομένα που αποστέλλονται σε αυτή, η συνάρτηση πρέπει να είναι ενήμερη για το πώς οργανώνονται τα δεδομένα αυτά..

Ας σκεφτούμε, για παράδειγμα, την υλοποίηση ενός κύβου. Είδαμε ότι μπορούμε να τον μοντελοποιήσουμε με διάφορους τρόπους, μεταξύ άλλων και με δείκτες σε κορυφές, λίστες ακμών καθώς και λίστες των κορυφών του πολυγώνου. Ο προγραμματιστής δεν ενδιαφέρεται (στις περισσότερες περιπτώσεις) ποιος τρόπος μοντελοποίησης χρησιμοποιείται και μπορεί να προτιμά να θεωρεί τον κύβο ως ατομική οντότητα ή ένα αντικείμενο. Επιπλέον, μπορεί να μην τον απασχολούν οι λεπτομέρειες που αναφέρονται στον τρόπο που ο κύβος εμφανίζεται στην οθόνη, ποιο μοντέλο σκίασης χρησιμοποιείται ή ποιος αλγόριθμος πλήρωσης πολύγωνων. Μπορούμε να υποθέσουμε ότι ο κύβος "ξέρει πώς να αποτυπωθεί στην οθόνη" και ότι ουσιαστικά ο αλγόριθμος σχεδίασης και εμφάνισης συσχετίζεται με το ίδιο το αντικείμενο. Για παράδειγμα, το χρώμα του κύβου, ο προσανατολισμός του, και τα φώτα που εφαρμόζονται στις επιφάνειές του είναι όλα μέρος της κατάστασης του συστήματος γραφικών και δεν μπορεί να εξαρτώνται από το πώς ο κύβος είναι μοντελοποιημένος.

Ωστόσο, αν δουλεύουμε με έναν φυσικό κύβο, μπορούμε να βρούμε αυτή τη θεώρηση λίγο παράξενη. Η θέση ενός φυσικού κύβου είναι συνδεδεμένη με το φυσικό αντικείμενο, όπως είναι και το χρώμα, το μέγεθος και ο προσανατολισμός. Ο τρόπος που περιγράψαμε για το χειρισμό ιεραρχικών δομών με χρήση στοιβών όπου αποθηκεύουμε και ανακτούμε πίνακες μετασχηματισμού και χαρακτηριστικών δεν υποστηρίζει αυτές τις ιδέες καλά. Για παράδειγμα, μια συνάρτηση που εκτελεί κάποια ενέργεια στον κύβο θα πρέπει να γνωρίζει ακριβώς πώς αναπαριστάται ο κύβος και θα μπορούσε να λειτουργήσει όπως παρουσιάζεται στην Εικόνα 7.14 (α).

(α)	(β)

Εικόνα 7.14. Διαδικαστικός (α) και Αντικειμενοστραφής (β) προγραμματισμός

Ο προγραμματιστής θα έγραφε μια συνάρτηση που να λαμβάνει ως εισόδους του έναν δείκτη σε δεδομένα του κύβου και τις παραμέτρους του μετασχηματισμού. Η συνάρτηση στη συνέχεια αφού επεξεργαζόταν τα δεδομένα για τον κύβο θα επέστρεφε τον έλεγχο στην εφαρμογή πιθανώς επιστρέφοντας και νέες τιμές παραμέτρων.

7.6.2. Αντικειμενοστραφής Σχεδιασμός

Ο αντικειμενοστραφής σχεδιασμός και ο αντικειμενοστραφής προγραμματισμός αντιμετωπίζουν το χειρισμό των αντικειμένων με ένα ριζικά διαφορετικό τρόπο. Οι αντικειμενοστραφείς γλώσσες προγραμματισμού ορίζουν τα αντικείμενα ως ενότητες με τις οποίες χτίζουμε προγράμματα. Οι ενότητες αυτές περιλαμβάνουν τα στοιχεία που καθορίζουν τη ενότητα, όπως οι κορυφές κύβου μας, οι ιδιότητες της μονάδας (χαρακτηριστικά), και οι λειτουργίες (μέθοδοι) που χειρίζονται τη μονάδα και τα χαρακτηριστικά της. Για να καλέσουμε μια μέθοδο του αντικειμένου αποστέλλουμε ένα μήνυμα προς αυτό. Το μοντέλο αυτό φαίνεται στην Εικόνα 7.14 (β).

Το πλεονέκτημα για τον προγραμματιστή είναι ότι δε χρειάζεται να γνωρίζει τον τρόπο με τον οποίο αναπαριστάται το αντικείμενο, στην προκειμένη περίπτωση ο κύβος. Το μόνο που χρειάζεται να γνωρίζει είναι οι λειτουργίες που υποστηρίζει το αντικείμενο, δηλαδή τι είδους μηνύματα μπορεί να λάβει. Επομένως, σε μια αντικειμενοστραφή γλώσσα προγραμματισμού, όπως η C++, η C# και η Java μπορούμε να χρησιμοποιήσουμε τη δομή της κλάσης για να ορίσουμε ένα αντικείμενο και μέσα από αυτήν την κλάση να καλέσουμε τις μεθόδους που αυτό υποστηρίζει. Ας δούμε το παράδειγμα υλοποίησης της κλάσης του κύβου σε αντικειμενοστραφή ψευδοκώδικα (Λίστα 7.1).

1. class Cube
2. {
3. public:
4. void Cube(){}
5. void ~Cube(){}
6. void translate(Vector3 position);
7. void rotate(float angle, Vector3 axis);
8. void scale(float amount, Vector3, axis);
9. void draw();
10. void setColor(Vector4 color);
11. Vector4 getColor();
12. private:
13. Vector4 m_color;
14. Matrix4 m_mat;
15. }

Λίστα 7.1. Ψευδοκώδικας υλοποίησης της κλάσης του κύβου

Για να χειριστούμε ένα αντικείμενο της κλάσης cube αρκεί να δημιουργήσουμε ένα στιγμιότυπο και να καλέσουμε τις μεθόδους του γράφοντας ένα πρόγραμμα μέσα στα πλαίσια του παρακάτω ψευδοκώδικα (Λίστα 7.2).

1. Cube cube_instance;
2.
3. void initialize()
4. {
5. cube_instance = new Cube();
6. cube_instance-<setColor({1,0,0,1}); //Green (R,G,B,A)
7. cube_instance-<scale(sx,{1,0,0});
8. cube_instance-<scale(sy,{0,1,0});
9. cube_instance-<scale(sz,{0,0,1});
10. }
11.
12. void main ()
13. {
14. initialize();
15. while(application_running)
16. {
17. update();
18. }
19. }
20.
21. void update()
22. {
23. cube_instance-<translate({x,y,z});
24. cube_instance-<rotate(r,{x,y,z});
25. cube_instance-<draw();
26. }

Λίστα 7.2. Ψευδοκώδικας υλοποίησης της κλάσης του κύβου

Σύμφωνα με το παραπάνω πρόγραμμα δημιουργούμε το αντικείμενο cube_instance της κλάσης Cube και αφού το αρχικοποιήσουμε καλώντας τη συνάρτηση initialize() στον κύριο βρόχο του προγράμματος σε κάθε ανανέωση της οθόνης καλούμε τη συνάρτηση update() για να το τοποθετήσουμε στο τρισδιάστατο σύστημα συντεταγμένων και να το απεικονίσουμε στην οθόνη. Για να εκτελεστεί η αρχικοποίηση, η τοποθέτηση και η απεικόνιση καλούμε τις αντίστοιχες μεθόδους του αντικειμένου.

Αντίστοιχα μπορούμε να δημιουργήσουμε κλάσεις για να υλοποιήσουμε αντικείμενα άλλων ειδών που θα συμπεριλάβουμε στη σκηνή μας, για παράδειγμα φώτα, κάμερες κλπ. Επίσης, μπορούμε να δημιουργήσουμε συναθροίσεις αντικειμένων ώστε να μπορούμε να ορίζουμε μετασχηματισμούς και μεθόδους που να εφαρμόζονται σε όλα τα μέλη της συνάθροισης. Επεκτείνουμε έτσι την έννοια των κόμβων που περιγράψαμε ως τώρα ώστε να συμπεριλαμβάνουν τα νέα είδη αντικειμένων καθώς και τις συναθροίσεις αυτών.

7.6.3. Βασικές λειτουργίες του Γράφου Σκηνής

Επεκτείνοντας τις ιεραρχικές δομές που παρουσιάσαμε ώς τώρα για την αναπαράσταση των σχέσεων των επιμέρους αντικειμένων τα οποία αποτελούν ένα μοντέλο ώστε να καλύψουμε μια ολόκληρη σκηνή που περιέχει πολλαπλά μοντέλα βάσει της αντικειμενοστραφούς λογικής, καταλήγουμε στην έννοια του Γράφου Σκηνής [Clark, 1976]. Ως Γράφο Σκηνής (ΓΣ) ορίζουμε την ιεραρχία αντικειμένων συσχετιζόμενα με οντολογικό τρόπο και χωρική (γεωμετρική) εξάρτηση και τα οποία σχηματίζουν μια τρισδιάστατη σκηνή η οποία αποτελείται από κόμβους που αναπαριστούν:

• Γεωμετρικά στοιχεία (στατικά ή κινούμενα),
• Συναθροίσεις κόμβων,
• Μετασχηματισμούς,
• Εξαρτώμενες επιλογές,
• Άλλες οντότητες προς αναπαραγωγή (π.χ. ήχους),
• Κόμβους εργασιών προσομοίωσης,
• Γράφους άλλων σκηνών.

Οι ΓΣ είναι κατευθυνόμενοι, μη κυκλικοί γράφοι κόμβων, των οποίων οι ακμές ορίζουν γεωμετρικές ή λειτουργικές εξαρτήσεις ενός κόμβου παιδιού με τον γονέα του. Οι κόμβοι περιέχουν όλη την λειτουργικότητα που χρειάζεται για να οριστεί μια συμπεριφορά, δηλαδή η λειτουργικότητα είναι ενσωματωμένη σε ένα αντικείμενο κάνοντας χρήση μιας αντικειμενοστραφούς υλοποίησης.

Κάθε γράφος σκηνής ξεκινάει από τον κόμβο-ρίζα. Ο κόμβος ρίζα είναι μια αφηρημένη αναπαράσταση της σκηνής:

• Δίvει ένα σημείο έναρξης της διάσχισης του γράφου
• Διαδίδει στην ιεραρχία όλες τις λειτουργίες που πρέπει να εφαρμοστούν στα στοιχεία της

Μια λειτουργία σε ένα κόμβο επηρεάζει όλα τα παιδιά του, ενώ οι ομάδες (συναθροίσεις κόμβων) αντιμετωπίζονται σαν αυτοτελείς υπο-γράφοι σκηνής Αυτό κάνει εύκολη την μοντελοποίηση περίπλοκων περιβαλλόντων και των κινήσεων εντός αυτών ενώ επιτρέπει την επαναχρησιμοποίηση οντοτήτων. Περίπλοκες κινήσεις και συμπεριφορές αντικειμένων χωρίζονται σε απλούστερες δίνοντας τοπική συμπεριφορά στα στοιχεία που οργανώνονται ιεραρχικά. Οι τέσσερις κύριες διαδικασίες που εφαρμόζονται σε ένα γράφο σκηνής είναι οι ακόλουθες:

• Αρχικοποίηση,
• Προσομοίωση,
• Περικοπή,
• Σχεδίαση.

Την αρχικοποίηση την περιγράψαμε ήδη σε επίπεδο κόμβου. Σε επίπεδο γράφου σκηνής η αρχικοποίηση είναι μια αναδρομική διαδικασία στην οποία κάθε κόμβος δημιουργείται, παραμετροποιείται και παίρνει τη θέση του στο γράφο. Αυτό μπορεί να γίνει είτε διαβάζοντας ένα αρχείο που περιγράφει τη σκηνή και τα αντικείμενα που περιέχει καθώς και τις σχέσεις τους, είτε προγραμματιστικά μέσω μιας συνάρτησης που υλοποιεί το γράφο.

Η ενημέρωση αναφέρεται στην εφαρμογή μεθόδων που μεταβάλλουν την κατάσταση ενός κόμβου στο χρόνο. Καθορίζονται όλες οι παράμετροι των κόμβων του δέντρου για το παρόν καρέ ανανέωσης της οθόνης και ενημερώνονται οι μεταβλητές του προγράμματος που συνδέονται με τη συμπεριφορά του κόμβου Για παράδειγμα, μια κινηματική διαδικασία μεταφέρει τη θέση του σκαπτικού μέσα σε συγκεκριμένο χρόνο από ένα σημείο σε άλλο ή την κίνηση περπατήματος του ανθρώπινου μοντέλου. Σε κάθε καρέ μεταξύ της αρχικής και της τελικής θέσης ενημερώνονται όλοι οι κόμβοι ώστε να μετακινηθούν στην ενδιάμεση θέση για το παρόν καρέ.

Η περικοπή αναφέρεται στη διαδικασία που αποφασίζει το σύστημα γραφικών ποιοι κόμβοι θα εμφανιστούν στην οθόνη με βάση την ορατότητά τους, την κατάστασή τους και τους κανόνες έχει ορίσει ο προγραμματιστής. Η περικοπή αντικειμένων είναι πολύ σημαντικό κομμάτι της απεικόνισης τρισδιάστατων γραφικών γιατί επηρεάζει σε μεγάλο βαθμό τη δυνατότητα του συστήματος να ανανεώνει την απεικόνιση σε πραγματικό χρόνο. Η περικοπή σε ένα γράφο σκηνής συνδέεται με τις εξαρτήσεις κόμβων. Εφόσον κάθε κόμβος “περιέχει” όλα τα παιδιά του:

• Αν ο κόμβος ρίζα ενός υποδέντρου θεωρηθεί “αφανής”
  • Kάθε κόμβος παιδί του είναι επίσης αφανής
  • Oλόκληρο το υποδέντρο περικόπτεται
• Αν ένας συναθροιστικός κόμβος είναι ορατός
  • Tα παιδιά του ελέγχονται ξεχωριστά
  • Σε περίπτωση μερικής παρεμπόδισης του κόμβου γονέα, κάποιοι κόμβοι παιδιά μπορεί να είναι ορατοί

Το αποτέλεσμα της διαδικασίας περικοπής καθορίζεται από τον έλεγχο του περιβάλλοντα όγκου του κόμβου που έχει επιλεχθεί. Για έναν συναθροιστικό κόμβο, ο περιβάλλον όγκος αντικατοπτρίζει τις συγκεντρωτικές επεκτάσεις των παιδιών του.

Η σχεδίαση, όπως περιγράψαμε, σε επίπεδο κόμβου κατέρχεται αναδρομικά την ιεραρχία και εφαρμόζει αλγορίθμους σχεδίασης, φωτισμού, οπτικών εφέ και απεικόνισης εικόνας σε κάθε ορατό κόμβου. Στην απευθείας σχεδίαση εικόνας και τον αλγόριθμο εκπομπής ακτινών (ray casting) 1ου επιπέδου τα υποδέντρα που έχουν περικοπεί αγνοούνται.

Γενικεύοντας τον τρόπο με τον οποίο περιγράψαμε την κλάση που ορίζει ένα γεωμετρικό αντικείμενο όπως ο κύβος στην παράγραφο 7.6.2, ώστε να περιγράφει έναν γενικό κόμβο ανεξάρτητα από το γεωμετρικό αντικείμενο που περιέχει, καταλήγουμε στην κλάση Node∙ αυτή υλοποιείται στα πλαίσια του ψευδοκώδικα που παρατίθεται ακολούθως (Λίστα 7.3).

1. class Node
2. {
3. protected:
4. bool active;
5. bool culled;
6. public:
7. Node();
8. virtual void init();
9. virtual void update();
10. virtual void cull();
11. virtual void draw();
12. virtual void reset();
13. }

Λίστα 7.3. Ψευδοκώδικας υλοποίησης της κλάσης του γενικού κόμβου

Αντίστοιχα, η κλάση που ορίζει μια συνάθροιση κόμβων υλοποιείται στα πλαίσια του παρακάτω ψευδοκώδικα (Λίστα 7.4).

1. class Group : Node
2. {
3. protected:
4. vector children;
5. Bvolume extents;
6. public:
7. Group();
8. void add(Node *n);
9. void remove(int i);
10. Node * getChild(int i);
11. int getNumChildren();
12. virtual void init();
13. virtual void simulate();
14. virtual void cull();
15. virtual void draw();
16. }

Λίστα 7.4. Ψευδοκώδικας υλοποίησης της κλάσης της συνάθροισης κόμβων

Όπως βλέπουμε στον ψευδοκώδικα, όλοι οι κόμβοι ενός γράφου σκηνής αποτελούν επεκτάσεις της κλάσης Node και συνεπώς κληρονομούν τις 4 βασικές λειτουργίες αυτής. Οι συναθροιστικοί κόμβοι παράγονται από την κλάση Group και μοιράζονται έναν κοινό τρόπο λειτουργίας: διατηρούν μια λίστα απογόνων και διαθέτουν βασικές λειτουργίες μιας συλλογής. Πιο περίπλοκες υποκλάσεις της Group επεκτείνουν τη συμπεριφορά με την πρόσθεση ειδικών μεθόδων. Κοινό χαρακτηριστικό όλων των κόμβων της κλάσης Group είναι η διάσχιση των απογόνων τους. Αυτή εκδηλώνεται ως ένα αναδρομικό κάλεσμα όλων των αντικειμένων της κλάσης Node στην εσωτερική τους λίστα. Λόγω του πολυμορφισμού που επιτρέπει ο αντικειμενοστραφής προγραμματισμός, ένα αντικείμενο της κλάσης Group μπορεί καλέσει τις μεθόδους init(), draw(), cull(), update() χωρίς να γνωρίζει από ποιες υποκλάσεις προέρχεται το αντικείμενο. Όλοι οι κόμβοι του γράφου σκηνής μοιράζονται ένα κοινό interface.

1. void Geometry::draw() // Geometry: υποκλάση της Node
2. {
3. if (!enabled || culled)
4. return;
5. // ... Σχεδίαση της γεωμετρίας
6. }

Λίστα 7.6. Ψευδοκώδικας υλοποίησης της μεθόδου draw της κλάσης Geometry (υποκλάση της Node)

Ο τρόπος διάσχισης ενός γράφου σκηνής ορίζει τη σειρά εκτέλεσης κάθε μεθόδου. Η αρχικοποίηση και τα 3 επαναλαμβανόμενα βήματα εκτελούνται ιεραρχικά το ένα μετά το άλλο ξεκινώντας από τη ρίζα της σκηνής. Μετά την αρχικοποίηση, οι αρμοδιότητες ενός γράφου σκηνής περιλαμβάνουν:

1. Scene *myScene = new Scene(); // Scene: υποκλάση της Node
2. myScene -> load("village.scn"); //μεταφόρτωση από αρχείο
3. myScene -> init();
4. while (application_running)
5. {
6. //... Άλλες λειτουργίες
7. myScene -> update();
8. myScene -> cull();
9. myScene -> draw();
10. }

Λίστα 7.7. Ψευδοκώδικας υλοποίησης της οπτικοποίησης της σκηνή

Έτσι οι κόμβοι συγχρονίζονται σε σχέση με την κατάστασή τους και τις τιμές των παραμέτρων. Σε ορισμένες περιπτώσεις η ενημέρωση των δεδομένων των κόμβων εκτελείται με υστέρηση. Σε αυτή τη μέθοδο, οι αλλαγές στην κατάσταση μιας οντότητας δεν παράγουν άμεσο αποτέλεσμα: Μια φορά γίνεται ο υπολογισμός τιμής για όλων των χαρακτηριστικών για την παραγωγή μιας προσομοίωσης, περικοπής, ή οπτικού αποτελέσματος. Οι ενημερώσεις με υστέρηση είναι χρήσιμες όταν πρέπει να γίνεται μια υπολογιστικά ακριβή διαδικασία κάθε φορά που αλλάζει μια μεταβλητή. Παραδείγματα σε ένα γράφο σκηνής είναι η συνθετική κίνηση βασισμένη σε μηχανική προσομοίωση και ο υπολογισμός πολυέδρου σκιάς.

7.6.4. Μεταφορά Μηνυμάτων

Σε περιπτώσεις σύνθετων γράφων σκηνής δεν περιοριζόμαστε στον ιεραρχικό έλεγχο. Εφαρμόζουμε άμεση επικοινωνία μεταξύ των κόμβων. Οι κόμβοι μπορούν να επικοινωνήσουν μεταξύ τους:

• με άμεσο κάλεσμα μεθόδων άλλων κόμβων,
• με μηνύματα.

Στη δεύτερη περίπτωση (πιο εύκολη στο συγχρονισμό), κάθε κόμβος πρέπει να επεκταθεί για να υποστηρίζει μια ουρά μηνυμάτων και ένα χάρτη γεγονότων. Η κλάση του μηνύματος υλοποιείται στα πλαίσια του παρακάτω ψευδοκώδικα:

1. class NodeMessage
2. {
3. Node *from, *to;
4. int ID;
5. void * params;
6. ;
7. typedef EventID int

Λίστα 7.8. Ψευδοκώδικας υλοποίησης της κλάσης NodeMessage

Αντίστοιχα ενσωματώνουμε τη δυνατότητα διαχείρισης μηνυμάτων στην κλάση Node:

1. class Node
2. {
3. protected:
4. ...
5. vector msgQueue;
6. multimap eventMap;
7. // Επεξεργασία εισερχομένων μηνυμάτων
8. void processMessages();
9. // Αποστολή εξερχομένων μηνυμάτων
10. void dispatchMessages();
11. public:
12. ...
13. // Εισαγωγή μηνύματος στην ουρά του κόμβου
14. message( NodeMessage *msg );
15. registerEvent( EventID evt, Node* target,
16. int msgID, void* params );
17. }

Λίστα 7.9. Ψευδοκώδικας επέκτασης της κλάσης Node για υποστήριξη μηνυμάτων

Για να γίνεται σωστή διαχείριση των μηνυμάτων είναι απαραίτητη δημιουργία μίας ουράς μηνυμάτων καθώς ένας κόμβος μπορεί να λάβει πολλά μηνύματα εντολών από άγνωστο πλήθος κόμβων. Επίσης, δημιουργείται ένας χάρτης γεγονότων, ο οποίος δημιουργεί μια αντιστοίχιση για αντιδράσεις που ορίζονται από το χρήστη στις αλλαγές κατάστασης του κόμβου. Στην επεκταμένη κλάση Node προστίθενται 2 νέες μέθοδοι:

• processMessages()
• dispatchMessages()

Αυτές οι λειτουργίες εκτελούνται πριν & μετά από το βήμα προσομοίωσης. Ας δούμε ένα παράδειγμα χρήσης των μηνυμάτων για να εκτελούμε λειτουργίες σε κόμβους: Θεωρείστε ένα δωμάτιο γεμάτο έπιπλα. Αρχικά το φως είναι σβηστό και δε χρειάζεται να έχουν τα έπιπλα σκιές οπότε η σκίαση είναι αρχικά απενεργοποιημένη για αυτούς του κόμβους γεωμετρίας. Όταν ανάβει το φως τα έπιπλα θα πρέπει να αποκτήσουν σκιές. Επίσης, θέτουμε ένα αντικείμενο φωτοστέφανου με όνομα halo ορατό γύρω από τη λάμπα όταν αυτή ανάβει, για να είναι πιο ρεαλιστική η σκηνή:

1. Light * bulb; // Το Light επεκτείνει το Node
2. Geometry *furniture, *halo;
3. ...
4. bulb -> registerEvent( EVENT_ON, furniture, MSG_SHADOWS_ON, NULL);
5. bulb -> registerEvent( EVENT_ON, halo, MSG_ENABLE, NULL);

Λίστα 7.10. Ψευδοκώδικας υλοποίησης των μηνυμάτων ενεργοποίησης σκίασης και φωτοστέφανου

Σύμφωνα με τον παραπάνω ψευδοκώδικα καταχωρούμε το γεγονός EVENT_ON (ενεργοποίησης του κόμβου) έτσι ώστε στον κόμβο furniture να αποστέλλει το τον τύπο μηνύματος MSG_SHADOWS_ON, ενώ στον κόμβο halo να αποστέλλει τον τύπο μηνύματος MSG_ENABLE. Αντίστοιχα, στο αντικείμενο furniture θα έχουμε κάνει μια αντιστοίχιση του MSG_SHADOWS_ON με μια μέθοδο που ενεργοποιεί τη σκίαση του αντικειμένου, ενώ στο αντικείμενο halo θα έχουμε κάνει μια αντιστοίχιση του MSG_ENABLE με μια μέθοδο που ενεργοποιεί το αντικείμενο.

7.7. Ορατότητα Αντικειμένων και Χωρική Κατάτμηση

Σχετικά με την απόδοση μιας 3D μηχανής γραφικών πραγματικού χρόνου, το πιο σημαντικό συστατικό της αρχιτεκτονικής απεικόνισης είναι ο καθορισμός της ορατότητας αντικειμένων. Δεδομένης μιας συγκεκριμένης θέσης προσανατολισμού της κάμερας, κάθε μηχανή γραφικών πρέπει να είναι σε θέση να προσδιορίσει αποτελεσματικά ποια μέρη του κόσμου είναι δυνητικά ορατά και ως εκ τούτου θα πρέπει να αποδοθούν στην οθόνη. Αυτό το πρόβλημα συνήθως αντιμετωπίζεται από την αντίθετη πλευρά, η μηχανή καθορίζει ποια μέρη του κόσμου είναι σίγουρα μη ορατά και εμφανίζει ό,τι απομένει.

Οι περισσότερες μηχανές τρισδιάστατων γραφικών εκτελούν τον καθορισμό της ορατότητας σε πολλαπλά επίπεδα. Ο γενικός σκοπός είναι να καθοριστεί ποια γεωμετρία του κόσμου ενδεχομένως τέμνει τον όγκο θέασης της κάμερας. Στο χαμηλότερο επίπεδο, η κάρτα γραφικών εκτελεί αποκοπή οπίσθιων πολυγώνων για την εξάλειψη ατομικών τριγώνων που κοιτούν προς την αντίθετη πλευρά από την κάμερα. Σε ανώτερο επίπεδο, εκτελείται διαδικασία δοκιμής τομών μεταξύ του όγκου προβολής και αντικειμένων ώστε να καθοριστεί αν είναι μέσα ή έξω από αυτόν.

Η περικοπή αντικειμένων με βάση την ορατότητά τους απαιτεί τη χρήση περιβαλλόντων όγκων που ορίζουν με πιο απλοποιημένες γεωμετρίες το χώρο που καταλαμβάνει ένα αντικείμενο στο τρισδιάστατο περιβάλλον και κατά συνέπεια αν βρίσκεται μέσα ή έξω από τα όρια όγκου θέασης της κάμερας καθώς και εάν κρύβουν ή κρύβονται από άλλα αντικείμενα. Οι περιβάλλοντες όγκοι κατασκευάζονται έτσι ώστε να περικλείουν όλες τις κορυφές που ανήκουν σε ένα τριγωνοποιημένο γεωμετρικό αντικείμενο, εξασφαλίζοντας έτσι ότι κάθε τρίγωνο στο αντικείμενο, επίσης, περιέχεται στον περιβάλλοντα όγκο. Θα πρέπει να ελαχιστοποιηθεί ο περιβάλλοντας όγκος όσο το δυνατόν περισσότερο, έτσι ώστε να πέφτει εντελώς έξω από τον όγκο προβολής όσο το δυνατόν συχνότερα, επιτρέποντας έτσι την περικοπή του αντικειμένου που περιέχει από το ορατό σύνολο της γεωμετρίας.

Υπάρχουν πολλές γεωμετρίες που μπορούμε να χρησιμοποιήσουμε για να περικλείσουμε ένα γεωμετρικό αντικείμενο (π.χ. σφαίρα, παραλληλεπίπεδο, κύλινδρος κλπ.) αλλά στο κομμάτι της περικοπής χρησιμοποιούμε τα περιβάλλοντα παραλληλεπίπεδα (bounding box). Τα περιβάλλοντα παραλληλεπίπεδα με τη σειρά τους διακρίνονται ανάλογα με το αν είναι προσανατολισμένα με βάση τους άξονες του κόσμου ή με τους τοπικούς άξονες που ορίζουν οι μέγιστες διαστάσεις του αντικειμένου. Στην πρώτη περίπτωση μιλάμε για axis aligned bounding box (AABB) ενώ στη δεύτερη για object aligned bounding box (OABB).

Ολιγομελείς ομάδες της γεωμετρίας μπορούν να αποκοπούν από το ορατό σύνολο οργανώνοντας περιοχές του κόσμου σε δενδρικές δομές όπως τα δέντρα δυαδικής χωρικής κατάτμησης (Binary Space Partitioning - BSPtrees) [Fuchs, 1977] ή με μια άλλη δεντρική δομή χωρικής κατάτμησης την οποία αποκαλούμε Octrees [Meagher, 1980]. Κατά τη μεγαλύτερη κλίμακα, ολόκληρες περιοχές του κόσμου γεωμετρίας μπορούν να εξαλειφθούν με τη χρήση μιας τεχνικής γνωστής ως σύστημα πυλών (Portals) [Telleretal., 1991].

7.7.1. Ιεραρχίες περιβαλλόντων όγκων

Μια τεχνική που υιοθετείται όταν η ταχύτητα είναι πιο σημαντικός παράγοντας από την ακριβή ορατότητα είναι η προσαρμογή του περιβάλλοντα όγκου ενός συναθροιστικού κόμβου με βάση τα μετασχηματισμένα όρια των περιβαλλόντων όγκων των παιδιών του αντί για τα όρια των μετασχηματισμένων παιδιών του. Η παραπάνω λύση, όμως, δεν παράγει βέλτιστους περιβάλλοντες όγκους και τα όρια των μετασχηματισμένων περιβαλλόντων όγκων είναι, εν γένει, μεγαλύτερα από τα όρια της περικλειόμενης γεωμετρίας όπως φαίνεται στην Εικόνα 7.15. Για το λόγο αυτό χρησιμοποιούμε σε πολλές περιπτώσεις χωρική κατάτμηση. Με τη χωρική κατάτμηση είναι δυνατόν να αυξηθεί η αποτελεσματικότητα με την οποία καθορίζεται η ορατότητα ενός μεγάλου αριθμού αντικειμένων οργανώνοντάς τα σε μια δομή της οποίας οι ιδιότητες επιτρέπουν μεγάλες περιοχές του χώρου να αποκοπούν από το ορατό σύνολο της γεωμετρίας με τη χρήση πολύ απλούστερων ελέγχων. Συνήθως εφαρμόζουμε κάποιον από τους τρόπους που αναφέρθηκαν (BSPtrees και Octrees) ώστε να χειριστούμε την περικοπή.

Εικόνα 7.15. Περιβάλλοντα παραλληλεπίπεδα συνάθροισης κόμβων

Και οι δύο μέθοδοι, συχνά, εφαρμόζονται μόνο σε στατική γεωμετρία του τρισδιάστατου περιβάλλοντος. Αν ένας κόμβος σε μια δενδρική δομή περιέχει ένα ιεραρχικό παρακλάδι κόμβων που εκφράζουν κίνηση, τα όρια του περιβάλλοντος όγκου του πρέπει να διευθετούνται δυναμικά κάθε φορά που αλλάζουν τα όρια κάποιου από τα παιδιά του. Ο επανυπολογισμός των ορίων των κόμβων γεωμετρίας απαιτεί τουλάχιστον την επαναληπτική καταγραφή της μέγιστης και ελάχιστης συντεταγμένης στους τρεις άξονες για κάθε κόμβο. Για τα υποδέντρα κόμβων κίνησης που πρέπει να υπάρξει επαναληπτική επεξεργασία στα ακατέργαστα δεδομένα τους ούτως ή άλλως (πχ. Σκελετική Κίνηση), αυτό δεν επιβάλλει πρόσθετη δουλειά. Για την κίνηση στερεών σωμάτων, ο επανυπολογισμός σπαταλά αρκετό χρόνο και μπορεί να είναι απαγορευτικός για μεγάλα μοντέλα. Στη συνέχεια θα δούμε πώς λειτουργούν οι τρόποι χωρικής κατάτμησης αυτοί.

7.7.2. Κατάτμηση με Octrees

Ας υποθέσουμε ότι όλη η γεωμετρία που ανήκει σε έναν κόσμο ή σε μια συγκεκριμένη περιοχή του κόσμου περιέχεται μέσα σε ένα ορθογώνιο πλαίσιο Π, όπως στην Εικόνα 7.16. Ένα Octree είναι μία δομή που κατατέμνει αυτό το πλαίσιο σε οκτώ μικρότερα, ιδίου μεγέθους ορθογώνια κουτιά που ονομάζουμε οκταμόρια (Π₁₁₁-Π₂₂₂). Αυτά τα μικρότερα κουτιά υποδιαιρούνται περαιτέρω σε οκτώ ακόμη μικρότερα οκταμόρια, και η διαδικασία συνεχίζεται σε κάποιο μέγιστο αριθμό επαναλήψεων που ονομάζεται το βάθος του Octree. Κάθε οκταμόριο συνδέεται με το πλαίσιο από το οποίο υποδιαιρέθηκε, και κάθε αντικείμενο στον κόσμο συνδέεται με το μικρότερο οκταμόριο που το περιέχει πλήρως (που μπορεί να είναι το αρχικό πλαίσιο Π).

Εικόνα 7.16. Παράδειγμα Octree. Το πλαίσιο Π εμπεριέχει τα αντικείμενα Α και Β ενώ το Β εμπεριέχεται πλήρως στο οκταμόριο Π₂₂₁.

Η Εικόνα 7.17 (α) απεικονίζει το ανάλογο ενός Octree στο δισδιάστατο χώρο, που ονομάζεται τετραδικό δένδρο (quadtree), και κατασκευάστηκε για μια περιοχή που περιέχει ένα μόνο αντικείμενο. Η Εικόνα 7.17 (β) δείχνει πώς είναι οργανωμένη η αντίστοιχη δομή δεδομένων. Κάθε κόμβος σε μια δομή τετραδικού δένδρου έχει το πολύ τέσσερις υποκόμβους - τα Οctrees μπορεί να έχουν μέχρι και οκτώ.

Καθώς αυτό το παράδειγμα επιδεικνύει, αν καμια γεωμετρία του κόσμου δεν τέμνει ένα τεταρτημόριο (ή ένα οκταμόριο σε Octree), τότε αυτό το τεταρτημόριο δεν υποδιαιρείται. Επιπλέον, κάθε τεταρτημόριο που δεν περιέχει απολύτως κανένα αντικείμενο, διαγράφεται από το δέντρο. Πάντα υποθέτουμε ότι τα τεταρτημόρια που δεν συμπεριλαμβάνονται είναι άδεια.

(α) Τετραδικό δέντρο για μια περιοχή που περιέχει μόνο ένα αντικείμενο	(β) Δενδρική αναπαράσταση τετραδικού δέντρου

Εικόνα 7.17. Ένα παράδειγμα τετραδικού δέντρου και η αντίστοιχη δενδρική αναπαράστασή του

Η οργάνωση της γεωμετρίας σε μια δομή δέντρου έχει το πλεονέκτημα ότι κάθε φορά που προσδιορίζουμε ότι ένας κόμβος του δέντρου δεν είναι ορατός, τότε ξέρουμε αμέσως ότι κάθε κόμβος-παιδί του εν λόγω κόμβου δεν είναι επίσης ορατός και μπορεί αυτόματα να είναι περικοπεί. Ο καθορισμός ορατότητας για ένα Octree αρχίζει ελέγχοντας το πλαίσιο γύρω από τον κόμβο της ρίζας για τομή με τον όγκο θέασης της κάμερας. Εάν η κάμερα είναι γνωστό ότι κείται πάντοτε εντός των ορίων του Octree, τότε μπορεί να θεωρηθεί ότι ο κόμβος ρίζας είναι πάντοτε ορατός. Όταν ο με βάση τον περιβάλλοντα όγκο (AABB ή OABB) του κάθε κόμβου κριθεί πως το αντικείμενο είναι ορατό, τότε ελέγχουμε όλα τα αντικείμενα που συνδέονται με αυτόν τον κόμβο ως προς την ορατότητά τους, με τον ίδιο τρόπο. Στη συνέχεια, εκτελούμε τον ίδιο έλεγχο για όλους τους υποκόμβους του ορατού κόμβου. Όταν το ο περιβάλλων όγκος ενός κόμβου αποτυγχάνει στον έλεγχο ορατότητας μπορούμε να αγνοήσουμε όλα τα αντικείμενα που συνδέονται με τον κόμβο αυτόν και τυχόν υπόκομβους του.

7.7.3. Κατάτμηση με BSP Trees

Ένα Δυαδικό Δέντρο Χωρικής Κατάτμησης (Binary Space Partition – BSPtree ) αποτελεί μια δομή που χωρίζει το χώρο σε δύο υποπεριοχές σε κάθε επίπεδο. Σε αντίθεση με τα επίπεδα κατάτμησης τα Octrees που είναι προσανατολισμένα ως προς τους άξονες του κόσμου, τα επίπεδα κατάτμησης σε ένα δέντρο BSP μπορεί να έχουν αυθαίρετο προσανατολισμό. Ένα δέντρο BSP κατασκευάζεται για ένα σύνολο από αντικείμενα επιλέγοντας ένα επίπεδο κατάτμησης, που μερικές φορές ονομάζεται επίπεδο διαίρεσης, και διαχωρίζοντας τις γεωμετρίες σε δύο ομάδες: αντικείμενα που βρίσκονται στη θετική πλευρά του επιπέδου (που ονομάζεται, επίσης, ο θετικός ημιχώρος) και τα αντικείμενα που βρίσκονται στην αρνητική πλευρά του επιπέδου (αρνητικός ημιχώρος).

Τυπικά, τα επίπεδα κατάτμησης ενός BSP δέντρου έχουν ευθυγραμμιστεί με το πολύγωνα που συνθέτουν τον κόσμο της γεωμετρίας. Η Εικόνα 7‑18 απεικονίζει ένα δισδιάστατο παράδειγμα μιας περιοχής που περιλαμβάνει διάφορα πολύγωνα που καθορίζουν τη δομή του δέντρου BSP. Ένα πολύγωνο επιλέγεται να αντιπροσωπεύει το επίπεδο διάσπασης σε κάθε επίπεδο του δέντρου, και τα υπόλοιπα πολύγωνα ταξινομούνται σε θετικές και αρνητικές ομάδες. Τυχόν πολύγωνα που τέμνουν το επίπεδο διαίρεσης χωρίζονται σε δύο πολύγωνα που βρίσκονται το καθένα στο θετικό και αρνητικό ημιχώρο αντίστοιχα. Οι θετικές και αρνητικές ομάδες τότε κατατέμνονται, και η διαδικασία συνεχίζεται για κάθε ημιχώρο μέχρις ότου δεν απομένει κανένα πολύγωνο.

Εικόνα 7.18. Τυπική κατάτμηση κατά BSP (αριστερά) και η αντίστοιχη δενδρική αναπαράστασή της (δεξιά)

Ο μεγάλος αριθμός των πολυγώνων και καμπύλων επιφανειών που χρησιμοποιούνται στις σύγχρονες μηχανές 3D κάνει το παραδοσιακό δέντρο BSP να μην είναι πλέον πρακτικό. Σε μια κάπως διαφορετική προσέγγιση, δημιουργούμε μια διαίρεση για κάθε αντικείμενο αντί για κάθε πολύγωνο. Όπως παρουσιάζεται στην Εικόνα 7.19, το επίπεδο διαχωρισμού για ένα αντικείμενο είναι ευθυγραμμισμένο έτσι ώστε να είναι κάθετο προς τον κύριο άξονα T του αντικειμένου που αντιστοιχεί στη μικρότερη διάσταση του OABB του.

Αυτό ελαχιστοποιεί την απόσταση που το αντικείμενο εκτείνεται μακριά από το επίπεδο διαίρεσης.

Αφού ένα επίπεδο διαίρεσης έχει επιλεγεί για ένα αντικείμενο, τα υπόλοιπα αντικείμενα ταξινομούνται σε δύο ομάδες: σε εκείνα που είναι μέσα στα πλαίσια του θετικού υποχώρου και εκείνα που είναι μέσα στα πλαίσια του αρνητικού υποχώρου. Τυχόν αντικείμενα που τέμνουν το επίπεδο διαίρεσης προστίθενται και στη θετική και στην αρνητική ομάδα. Οι υποχώροι στη συνέχεια κατατέμνονται αναδρομικά μέχρι να μην υπάρχουν αντικείμενα που δεν ανήκουν σε κάποιον υποχώρο.

Εικόνα 7.19. Το επίπεδο διαίρεσης ενός αντικειμένου προσανατολίζεται έτσι ώστε να είναι κάθετο προς τον άξονα Τα, που αντιστοιχεί στη μικρότερη διάσταση του OABB του.

Για κάθε επίπεδο διαίρεσης ενός δέντρου BSP, θα πρέπει να καθοριστεί η ορατότητα του κάθε υποχώρου και η ορατότητα κάθε αντικειμένου που σχετίζεται με επίπεδο. Αυτό προϋποθέτει ότι έχουμε έναν τρόπο να ελέγξουμε αν ένα επίπεδο Κ τέμνει τον όγκο θέασης της κάμερας. Η απλούστερη προσέγγιση θα ήταν να ελέγξουμε τις συντεταγμένες των οκτώ κορυφών του όγκου θέασης στο σύστημα συντεταγμένων του κόσμου σε σχέση με το επίπεδο K υπολογίζοντας τα τετραδιάστατα εσωτερικά γινόμενα τους και συγκρίνοντάς τα με το μηδέν. Εάν όλα τα οκτώ εσωτερικά γινόμενα έχουν το ίδιο πρόσημο (που σημαίνει ότι όλα τα οκτώ σημεία βρίσκονται στην ίδια πλευρά του επιπέδου), τότε το επίπεδο δεν τέμνει την όγκο θέασης. Ευτυχώς, μπορούμε να βρούμε μια καλύτερη μέθοδο μετασχηματίζοντας το επίπεδο Κ σε ομογενή χώρο περικοπής και χρησιμοποιώντας την κυβική συμμετρία του όγκου θέασης σε αυτό το χώρο.

7.8. Κατανεμημένη Σχεδίαση

Απαιτητικές εφαρμογές ή πολλαπλών-χρηστών/πολλαπλών-οθονών χρειάζονται να κατανέμουν τα δεδομένα του γράφου σκηνής και να τα σχεδιάζουν σε πολλαπλούς επεξεργαστές χωρίς να είναι απαραίτητο η σκηνή να βρίσκεται σε κοινό χώρο στη μνήμη. Ένας επεξεργαστής μπορεί να είναι:

• Ένας ηλεκτρονικός υπολογιστής,
• Ένας ειδικός συνεπεξεργαστής,
• Ένα ή παραπάνω συστήματα παράλληλων επεξεργαστών.

Στις σύγχρονες κάρτες γραφικών, οι επεξεργαστές υποστηρίζουν την παράλληλη επεξεργασία πολλών αντικειμένων και δομών αναπαράστασης μιας σκηνής κάνοντας χρήση πολλαπλών πυρήνων. Για να εκτελεστεί κατανεμημένα η σχεδίαση μιας σκηνής, σε κάθε καρέ ανανέωσης της εικόνας η διαδικασία απεικόνισης μιας συνθετικής αναπαράστασης αποτελείται από 4 στάδια:

• διάσπαση (Splitting),
• κατανομή (Distribution),
• σχεδίαση (Rendering),
• σύνθεση (Compositing).

Μια διαδικασία κατανεμημένης σχεδίασης μιας σκηνής χωρίζεται σε 3 κατηγορίες ανάλογα με τον τρόπο χειρισμού της κατανομής:

• Κατανομή στο πεδίο του τρισδιάστατου χώρου,
• Κατανομή (Distribution),
• Κατανομή στο πεδίο του χρόνου,
• Κατανομή στο πεδίο της εικόνας.

7.8.1. Κατανομή στο πεδίο του τρισδιάστατου χώρου

Στην περίπτωση της κατανομής στο πεδίο του τρισδιάστατου χώρου τα στάδια εκτελούνται ως εξής:

• Διάσπαση: Η σκηνή διαιρείται σύμφωνα είτε με την ιεραρχία του γράφου σκηνής ή του μηχανισμού χωρικής κατάτμησης.
• Κατανομή: Τα τμήματα που δημιουργούνται κατανέμονται στους διαθέσιμους επεξεργαστές
• Σχεδίαση: Κάθε επεξεργαστής σχεδιάζει ένα τμηματικό αποτέλεσμα.
• Σύνθεση: Το κάθε τμηματικό αποτέλεσμα συνδυάζεται με τα υπόλοιπα αποτελέσματα ώστε να σχηματιστεί η ολοκληρωμένη εικόνα του παρόντος καρέ στην οθόνη. Στην περίπτωση της απεικόνισης σε πραγματικό χρόνο κατά τη σύνθεση προκύπτουν τα παρακάτω ζητήματα.

Οι ενδιάμεσες εικόνες-αποτελέσματα δεν είναι ταξινομημένες ως προς το βάθος οπότε επικαλύπτονται στο χώρο της εικόνας. Επομένως, οι προκύπτοντες τμηματικοί καταχωρητές εικόνας δεν μπορούν να συνδυαστούν άμεσα. Για το λόγο αυτό συνήθης πρακτική είναι η διατήρηση και μετάδοση των καταχωρητών βάθους κάθε τμήματος και η σχεδίαση με βάση το συγκριτικό βάθος μεταξύ όλων των τμημάτων. Οι διαδικασίες κατανεμημένης σχεδίασης, ονομάζονται μετα-ταξινόμηση (post-ordering) γιατί η απόφαση για το ποιο μέρος της τελικής εικόνας προκύπτει από ποιο κόμβο συμβαίνει στο τέλος της παραγωγής του καρέ (Εικόνα 7.20).

Εικόνα 7.20. Παράδειγμα της διααδικασίας μετα-ταξινόμησης (σχεδίαση – σύνθεση από δύο επεξεργαστές)

7.8.2. Κατανομή στο πεδίο του χρόνου

Η περίπτωση της κατανομής στο πεδίο του χρόνου μπορεί να εφαρμοστεί μόνο σε έμμεσες απεικονίσεις (offline) που δεν γίνονται σε πραγματικό χρόνο.

• Διάσπαση: Η σκηνή διαμοιράζεται ολόκληρη σε κάθε επεξεργαστή.
• Κατανομή: Κάθε καρέ της κινούμενης σκηνής κατανέμεται σε κάποιον από τους διαθέσιμους επεξεργαστές ενώ προϋπολογίζονται οι παράμετροι μεταβολής για όλα τα καρέ που έχουν δεσμευθεί.
• Σχεδίαση: Κάθε επεξεργαστής σχεδιάζει την πλήρη απεικόνιση της σκηνής για το καρέ που έχει αναλάβει.
• Σύνθεση: Το κάθε καρέ με το που ολοκληρώνεται η σχεδίασή του ταξινομείται στη σωστή σειρά εμφάνισής του και ο επεξεργαστής απελευθερώνεται για να αναλάβει το επόμενο καρέ που είναι διαθέσιμο.

7.8.3. Κατανομή στο πεδίο της εικόνας

Στην περίπτωση της κατανομής στο πεδίο της εικόνας, το σύστημα εκτελεί διαδικασίες προ-ταξινόμησης. Οι στρατηγικές προ-ταξινόμησης στο χώρο εικόνας είναι πιο κοινές. Η βάση δεδομένων της σκηνής αντιγράφεται στους επεξεργαστές, ή μοιράζεται από πολλαπλές διεργασίες που εκτελούν τη σχεδίαση. Σε κάθε επεξεργαστή ανατίθενται ένα ή περισσότερα τμήματα της τελικής εικόνας. Τα αποτελέσματα συντίθενται με την αντιγραφή των τμημάτων εικόνας σε έναν κοινό καταχωρητή.

Η κατανεμημένη σχεδίαση σε πραγματικό χρόνο που εκτελείται σε πολλαπλά συστήματα γραφικών στην ίδια μηχανή διαχειρίζεται από το υλικό των οθονών ενώ στην περίπτωση της έμμεσης (offline) σχεδίασης συνθετικής κίνησης κάθε επεξεργαστής διατηρεί ένα πλήρες αντίγραφο της βάσης δεδομένων της σκηνής καθώς και εξωτερικά χαρακτηριστικά (υφές). Με βάση τα παραπάνω οι τα στάδια της απεικόνισης υλοποιούνται ως ακολούθως:

• Διάσπαση: Εκτελείται μια προ-διαμέριση του πεδίου εξόδου (εικόνα). Η διαμέριση αυτή συνήθως γίνεται με μία από τις παρακάτω μεθόδους:
  • o εναλλαγή γραμμών σάρωσης (interlaced scanline),
  • o σε Ψηφίδες (Tiled),
  • o ολίσθηση ολόκληρης εικόνας.
• Κατανομή: Σε κάθε επεξεργαστή ανατίθεται ένα ή περισσότερα κομμάτια της συνολικής εικόνας.
• Σχεδίαση: Κάθε επεξεργαστής σχεδιάζει ένα κομμάτι της τελικής εικόνας και ενημερώνει όταν ολοκληρώσει πως το τμήμα είναι διαθέσιμο για σύνθεση.
• Σύνθεση: Η σύνθεση των τμημάτων προς σχεδίαση είναι τετριμμένη σε αυτούς τους αλγορίθμους γιατί τα κομμάτια εικόνας που μαζεύονται δεν έχουν επικαλύψεις
• Η διαδικασία προ-ταξινόμησης στην πραγματικότητα εκτελείται τετριμμένα παράλληλα: Δεν υφίσταται καμία επικοινωνία μεταξύ των επεξεργαστών εκτός από την αρχικοποίηση και τη συγκομιδή των τελικών τμημάτων εικόνας.

7.9. Προτεινόμενες Ασκήσεις και Προβλήματα

Άσκηση 1) Βρείτε τις εξισώσεις που υπολογίζουν τη θέση οποιουδήποτε σημείου στον εκσκαφέα που περιγράψαμε βάσει των γωνιών των αρθρώσεων. Μπορείτε να προσδιορίσετε τις γωνίες των αρθρώσεων γνωρίζοντας μόνο τη θέση του σκαπτικού; Εξηγήστε την απάντησή σας. Άσκηση 2) Θεωρήστε μια δομή δυαδικού δέντρου που περιγράφει τον αλγόριθμο QuickSort. Κάθε στοιχείο του συνόλου προς ταξινόμηση αποτελεί έναν κόμβο με δείκτες στο προηγούμενο και επόμενο στοιχείο του συνόλου. Γράψτε ένα πρόγραμμα σε OpenGL που να απεικονίζει γραφικά το δέντρο κατά τη διαδικασία ταξινόμησης. Άσκηση 3) Εκτός από το παράδειγμα του εκσκαφέα και του ανθρώπου που χρησιμοποιήσαμε για να περιγράψουμε τις αρθρωτές δομές κίνησης υπάρχουν αμέτρητα παραδείγματα σύνθετης κινηματικής που συνδυάζουν γραμμική και περιστροφική κίνηση μερών για να κινήσουν το συνολικό αντικείμενο. Επιλέξτε ένα παράδειγμα σύνθετης κινηματικής και υλοποιήστε ένα πρόγραμμα που να το απεικονίζει γραφικά. Άσκηση 4) Χρησιμοποιώντας το παράδειγμα του γράφου σκηνής που περιγράψαμε σε ψευδοκώδικα, υλοποιήστε στη γλώσσα προγραμματισμού που θέλετε ένα απλό σύστημα γράφου σκηνής που να χειρίζεται πολυγωνικά αντικείμενα, υφές, ένα σύστημα κάμερας και προβολής και πηγές φωτός Άσκηση 5) Επεκτείνετε το πρόγραμμα που υλοποιήσατε στην προηγούμενη άσκηση έτσι ώστε να μπορεί να αποθηκευθεί και ανακτηθεί η δομή του γράφου από ένα αρχείο μορφής XML.

7.10. Βιβλιογραφία/Αναφορές

• Clark J. H. (1976). Hierarchical geometric models for visible surface algorithms, Communications of the ACM19, 10 (October 1976), 547-554.
• Fuchs H. J. Duran, Johnson B. (1977). A System for Automatic Acquisition of Three-Dimensional Data, Proceedings of the 1977 NCC, AFIPS Press, 49–53, Montvale, NJ, 1977.
• Meagher D. (1980). Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer. Rensselaer Polytechnic Institute (Technical Report IPL-TR-80-111).
• Segal M., Akeley K. (1992). The OpenGL Graphics System: A Specification, ver. 1.0, Silicon Graphics, Mountain View, CA.
• Watt A., Watt M. (1992). Advanced Animation and Rendering Techniques, Addison-Wesley, Wokingham, England.

Κουίζ αυτοαξιολόγησης

Η συγγραφική ομάδα του βιβλίου