Τα γραφικά στην σημερινή κοινωνία της «Πληροφορίας» παίζουν σημαντικό ρόλο και είναι από τους τομείς που δαπανούνται υπέρογκα ποσά για τη βελτίωση τους. Για να καταλάβουμε τη σημαντικότητα του ρόλου τους αρκεί να αναφέρουμε τους τομείς στους οποίους βρίσκουν εφαρμογή:
-Αλληλεπίδραση με το χρήστη
-Σχεδιασμός στις επιχειρήσεις, στην επιστήμη και στην τεχνολογία
-Αυτοματισμοί γραφείου και ηλεκτρονικές εκδόσεις
-Ο υπολογιστής σαν βοήθημα στη σχεδίαση
-Εξομοίωση και “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. / Graphics in the society of "Information" play an important role, as they are one of the sectors where great sums of money are consumed for their improvement. In order to understand the importance of their role it is enough to mention the sectors in which they are applied:
- Interaction with the user
- Planning in enterprises, science and technology
- Office automations and electronic publications
- The computer as an aid in designing
- Simulation and "animation" for scientific representations and entertainment
- Art and trade
- Conduct of control
- Aid in learning
- Cartography
- Entertainment
One of the stages of a 3D graphics production machine, Rendering, which is one of the most demanding in power, fills with color each Pixel of the screen depending on the 3D picture that we want to present in the screen of the computer. This stage requires hundreds of thousands calculations and memory accesses per second - for real time rendering -, so it requires an important quantity of power. The implementation of 3D graphics production at devices that require low consumption of power, as PDAs, mobile phones and other portable devices, has created the need of reducing the power consumption.
The Clipping stage is one of the five stages of Geometry Stage in the graphics production. This stage is applied in order to determine the part of the picture that will be visible in a given region - called the visible window -also known as viewing frustum or viewport and cut away those objects that are detected outside this region. Consequently what is achieved is applying rasterization only in the visible region which is the main advantage of using Clipping. Better performance is achieved as the rasterization stage is too demanding and clipping helps the reduction of objects that will be drawn, hence the reduction of the future calculations and the consumption of energy.
Algorithm N-L-N is one of the basic algorithms that are used widely in the section of 2D graphics as it avoids the exterior traces (traces between the AB line segment and the extensions of the sides of the window) dividing the space in more regions than the C-S (Cohen-Sutherland), it has the less divisions and less comparisons (1/3 of C-S and 1/2 of the L-B (Liang-Barsky) [ 2 ]) hence is quicker and more efficient so consequently the most desirable in 2D environments. However a very small percentage of lines is being Clipped - just the 6% in average [ 1 ] - so for the improvement of the algorithm we are focused in the previous stages (up to the decision of making Clipping). Specifically in [ 1 ] is mentioned that the 8/9 of this lines are being "Rejected" as being wholly outside the visible window and only the 1/9 are being "Accepted" or "Clipped". For this reason the QuickClip algorithm was created, a algorithm that aims in the very fast rejection of a large amount of lines, no however all of which should go through rejection.
Aim of the proposed algorithm is to achieve "Full Reject" (that is to say reject of all lines that is not entirely visible) with as less operations as possible. The QuickClip algorithm at the worst case, will make up to 3 unnecessary Clippings, before deciding to exclude the line. These pointless operations are undesirable, that we tried to minimize in the proposed algorithm. The way which the N-L-N algorithm faces Clipping and the mechanism of slopes that it uses helped us in our implementation.
After we studied and comprehended the ideas and the ways of the algorithms of which the use has dominated in the process of Polygon and Line Clipping, we realized that most have different philosophies and have disadvantages and advantages.
The result was the effort of designing an algorithm that takes advantage of the positive elements, trying at the same time to reduce the negatives. According to the measurements of calculating complexity we observe that it mainly makes less operations in the cases of rejecting lines (¨Full Reject¨), but also acceptance (¨Full Accept¨) from the dominant algorithms. Also in a overall level, even in the worst case (¨Worst case¨) where the most operations are required is competitive with the algorithms N-L-N and QuickClip. In combination with the measurements that have preceded between the algorithms that have dominated until now in Clipping ([1], [2], [3], [4], [5], [7 ]) we can claim that the proposed algorithm will be efficient in Low Power devices because of the less operations.
Deductively therefore we report that comparatively with the algorithms N-L-N and QuickClip the necessary calculations were decreased and specifically in the case of wholly rejected lines ("Full Reject") where proper emphasis was given. This came from the observation that the 8/9 of lines that go through "Reject" while they are wholly outside the visible window and only the 1/9 go through "Accept" or "Clip". Thus the complexity of this process is decreased, something useful in this early stage of graphics' pipeline. The proposed algorithm can be useful in devices that have the need of low consumption of energy and small surface. The planning of the algorithm has become for two-dimensions environment (2D), without however excluding the three-dimensions (3D) extension.
With the suitable Low power and Low area implementation in VLSI it will give a result of low consumption of energy but also small surface, elements that are vital for mobile devices.
The algorithms of point clipping were written in C Code with the addition of an application that represent graphically the lines before and afterwards the stage of clipping. Then a suggestive architecture of the proposed algorithm was designed in VHDL so as to show that it can be implemented in VLSI.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/744 |
| Date | 31 March 2008 |
| Creators | Εμμανουήλ, Παναγιώτης, Μιχαλόπουλος, Δημήτριος |
| Contributors | Στουραΐτης, Αθανάσιος, Emmanouil, Panagiotis, Michalopoulos, Dimitrios, Παλιουράς, Βασίλειος, Στουραΐτης, Αθανάσιος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
Page generated in 0.0045 seconds