| Περίληψη: | Τα γραφικά στην σημερινή κοινωνία της «Πληροφορίας» παίζουν σημαντικό ρόλο και είναι από τους τομείς που δαπανούνται υπέρογκα ποσά για τη βελτίωση τους. Για να καταλάβουμε τη σημαντικότητα του ρόλου τους αρκεί να αναφέρουμε τους τομείς στους οποίους βρίσκουν εφαρμογή:
-Αλληλεπίδραση με το χρήστη
-Σχεδιασμός στις επιχειρήσεις, στην επιστήμη και στην τεχνολογία
-Αυτοματισμοί γραφείου και ηλεκτρονικές εκδόσεις
-Ο υπολογιστής σαν βοήθημα στη σχεδίαση
-Εξομοίωση και “animation” για επιστημονικές απεικονίσεις και
διασκέδαση
-Τέχνη και εμπόριο
-Διεξαγωγή ελέγχου
-Βοήθημα για εκμάθηση
-Χαρτογραφία
-Διασκέδαση
Ένα από τα στάδια λειτουργίας μιας μηχανής παραγωγής 3D γραφικών, το Rendering, που είναι ένα από τα πιο απαιτητικά σε ισχύ στάδια της, μπορεί και γεμίζει με χρώμα κάθε Pixel της οθόνης ανάλογα με τη 3D εικόνα που θέλουμε να παρουσιάσουμε στην οθόνη του υπολογιστή. Το στάδιο αυτό απαιτεί εκατοντάδες χιλιάδες υπολογισμούς και προσπελάσεις μνήμης το δευτερόλεπτο -για rendering πραγματικού χρόνου- συνεπώς απαιτεί σημαντική ποσότητα ισχύος. Η εφαρμογή της παραγωγής γραφικών 3D σε συσκευές που απαιτούν χαμηλή κατανάλωση ισχύος, όπως PDA, κινητά τηλέφωνα και άλλες φορητές συσκευές, έχει δημιουργήσει την ανάγκη για μείωση της κατανάλωσης ισχύος.
Το Clipping αποτελεί ένα από τα πέντε στάδια του Geometry Stage για την παραγωγή γραφικών. Το στάδιο αυτό το εφαρμόζεται για να καθοριστεί το μέρος της εικόνας το οποίο θα είναι ορατό μέσα σε μια δεδομένη περιοχή -το ορατό παράθυρο- γνωστή και ως viewing frustum ή viewport και να αποκοπούν εκείνα τα αντικείμενα που βρίσκονται έξω από αυτή. Αυτό που επιτυγχάνεται επομένως είναι να γίνεται rasterization μόνο στην ορατή περιοχή και αυτό είναι το βασικό πλεονέκτημα της χρήσης του Clipping. Επιτυγχάνεται καλύτερη απόδοση καθώς το στάδιο του rasterization είναι ιδιαίτερα απαιτητικό και μέσω του clipping βοηθάμε στην μείωση των αντικειμένων που θα απεικονισθούν άρα και στους μελλοντικούς υπολογισμούς και στην κατανάλωση ενέργειας.
Ο αλγόριθμος N-L-N είναι ένας από τους βασικούς αλγορίθμους που χρησιμοποιούνται ευρέως στον τομέα των 2D γραφικών καθώς αποφεύγει τις εξωτερικές τομές (τομές μεταξύ του ΑΒ και των προεκτάσεων των πλευρών του παραθύρου) διαιρώντας το χώρο σε περισσότερες από τον C-S (Cohen-Sutherland) περιοχές, έχει τις λιγότερες διαιρέσεις και τις λιγότερες συγκρίσεις (1/3 από τον C-S και 1/2 από τον L-B (Liang-Barsky) [2] ) άρα είναι ο πιο ταχύς και αποδοτικός και συνεπώς ο πιο επιθυμητός σε 2D περιβάλλοντα. Όμως πολύ μικρό ποσοστό των γραμμών υπόκεινται Clipping -μόλις το 6% κατά μέσο όρο [1]- έτσι για τη βελτίωση του αλγορίθμου επικεντρωθήκαμε στα προηγούμενα στάδια (μέχρι την απόφαση να κάνουμε Clip).Πιο συγκεκριμένα στο [1] υποστηρίζεται ότι τα 8/9 των γραμμών αυτών υπόκεινται “Reject” αφού είναι εξ’ολοκλήρου εκτός του ορατού παραθύρου και μόνο το 1/9 “Accept” ή “Clip”. Για το λόγο αυτό δημιουργήθηκε ο QuickClip, ένας αλγόριθμος που στοχεύει στο πολύ γρήγορο reject ενός μεγάλου αριθμού γραμμών, όχι όμως όλων όσων πρέπει να υποστούν reject.
Σκοπός λοιπόν του προτεινόμενου αλγορίθμου είναι να επιτευχθεί “Full Reject” (δηλαδή απόρριψη όλων των γραμμών που δεν είναι εξ’ ολοκλήρου ορατές) με όσο το δυνατόν λιγότερες πράξεις. Ο Quick Clip στη χειρότερη περίπτωση, μπορεί να κάνει έως και 3 άσκοπα Clipping, πριν αποφασίσει να αποκλείσει τη γραμμή. Αυτές οι άσκοπες πράξεις είναι κάτι ανεπιθύμητο, που προσπαθήσαμε να ελαχιστοποιήσουμε στον αλγόριθμό μας. Η οπτική γωνία από την οποία ο N-L-N αλγόριθμος αντιμετωπίζει το Clipping και o μηχανισμός των κλίσεων που χρησιμοποιεί μας βοήθησε στην δική μας υλοποίηση.
Αφού μελετήσαμε και κατανοήσαμε την οπτική γωνία και τον τρόπο σκέψης των αλγορίθμων των οποίων η χρήση έχει επικρατήσει στη διαδικασία του Polygon και Line Clipping, διαπιστώσαμε ότι οι περισσότεροι έχουν διαφορετικές φιλοσοφίες και παρουσιάζουν μειονεκτήματα και πλεονεκτήματα.
Το αποτέλεσμα ήταν η προσπάθεια σχεδίασης ενός αλγορίθμου, που εκμεταλλεύεται τα θετικά στοιχεία, προσπαθώντας παράλληλα να λύσει τα αρνητικά. Σύμφωνα με τις μετρήσεις της υπολογιστικής πολυπλοκότητας παρατηρούμε ότι κάνει λιγότερες πράξεις κυρίως στις περιπτώσεις απόρριψης των γραμμών (¨Full Reject¨), αλλά και αποδοχής (¨Full Accept¨) από τους κυρίαρχους αλγορίθμους. Επίσης σε συνολικό επίπεδο, ακόμα και στην χειρότερη περίπτωση (¨Worst case¨) όπου απαιτούνται οι περισσότερες πράξεις είναι ανταγωνιστικός με τους αλγόριθμους N-L-N και Quickclip. Σε συνδυασμό με τις μετρήσεις που έχουν προηγηθεί μεταξύ των αλγορίθμων που έχουν επικρατήσει ως τώρα στο Clipping ([1],[2],[3],[4],[5],[7]) μπορούμε να ισχυριστούμε ότι ο προτεινόμενος είναι ένας αλγόριθμος που θα είναι αποδοτικός λόγω των λιγότερων πράξεων του σε Low Power κατασκευές.
Συμπερασματικά λοιπόν αναφέρουμε ότι συγκριτικά με τους αλγορίθμους N-L-N και Quickclip μειώθηκαν οι απαραίτητοι υπολογισμοί και ειδικά στην περίπτωση των εξ’ολοκλήρου απορρίψεων (“Full Reject”) όπου δόθηκε ιδιαίτερη έμφαση. Αυτό προήλθε από την παρατήρηση ότι τα 8/9 των γραμμών υπόκεινται “Reject” αφού είναι εξ’ολοκλήρου εκτός του ορατού παραθύρου και μόνο το 1/9 “Accept” ή “Clip”. Έτσι η πολυπλοκότητα της διαδικασίας αυτής μειώνεται, κάτι χρήσιμο σε αυτό το πρώιμο στάδιο των γραφικών. Ο προτεινόμενος αλγόριθμός μπορεί να φανεί χρήσιμος σε συσκευές που έχουν ανάγκη από χαμηλή κατανάλωση ενέργειας και μικρή επιφάνεια. Ο σχεδιασμός του αλγορίθμου έχει γίνει για δισδιάστατο περιβάλλον (2D), χωρίς όμως να αποκλείεται και τρισδιάστατη (3D) επέκτασή του.
Με την κατάλληλη Low power και Low area υλοποίηση σε VLSI θα δώσει ένα αποτέλεσμα χαμηλής κατανάλωσης ενέργειας αλλά και μικρής επιφάνειας, στοιχεία που είναι καίρια για mobile συσκευές.
Οι αλγόριθμοι του point clipping υλοποιήθηκαν σε γλώσσα προγραμματισμού C με την προσθήκη μιας εφαρμογής που αναπαριστά γραφικά τις γραμμές πριν και μετά το στάδιο του clipping. Κατόπιν έγινε καταγραφή σε VHDL μιας ενδεικτικής αρχιτεκτονικής του προτεινόμενου αλγορίθμου ώστε να δειχθεί ότι είναι υλοποιήσιμος σε VLSI.
|
|---|
