56
3.5.2 Σάρωση κελιών
Ως συνέπεια του παραπάνω διαχωρισμού, μειώνεται το σύνολο των κελιών των οποίων
υπολογίζονται οι μετρήσεις για κάθε διεργασία σε σχέση με την σειριακή σάρωση των κελιών.
Επομένως, τροποποιείται και ο τρόπος που υπολογίζονται τα κελιά για την κάθε διεργασία.
Σχήμα 38 Παράδειγμα σάρωσης ενός τομέα για την παράλληλη εκτέλεση του αλγορίθμου. Μόνο τα αριθμημένα
κελιά υπολογίζονται και η σάρωση πραγματοποιείται με την σειρά της αρίθμησης με βάση το τεταρτημόριο.
Όπως φαίνεται στο παραπάνω σχήμα (
), για την παράλληλη επεξεργασία, η σάρωση
διαφέρει από τη σειριακή, καθώς κάθε διεργασία υπολογίζει μόνο τα κελιά που περιέχει το
κομμάτι που έχει αναλάβει. Συνεπώς, για να υπολογιστούν τα κελιά, απαιτείται ο υπολογισμός
των ορίων του κομματιού κάθε διεργασίας. Ο υπολογισμός των ορίων πραγματοποιείται με την
χρήση των γωνιών που υπολογίστηκαν στο κεφάλαιο 3.5.1 σε συνδυασμό με την εξίσωση της
ευθείας και τη θέση του παρατηρητή. Για κάθε κομμάτι υπολογίζονται τα κελιά που βρίσκονται
μεταξύ των δυο ευθειών. Τα κελιά στα όρια του κάθε κομματιού που δεν βρίσκονται μεταξύ
των ευθειών, αλλά τέμνονται τουλάχιστον από μία από τις ευθείες, περιλαμβάνονται στα κελιά
που υπολογίζει η διεργασία. Ο υπολογισμός των ορίων των κομματιών, με την χρήση της
εξίσωσης της ευθείας έχει ως αποτέλεσμα τα όρια να υπολογίζονται σε πραγματικούς αριθμούς,
ενώ οι θέσεις των κελιών να αντιστοιχούν σε ακέραιους αριθμούς. Επομένως, για όλα τα
κομμάτια υπολογίζεται κομμάτι μεγαλύτερο από το απαιτούμενο κατά ένα κελί στον άξονα χ
και ψ για τα άκρα του κομματιού. Η αύξηση αυτή εφαρμόζεται και για τους δύο άξονες, καθώς
σφάλματα προκύπτουν όταν η γωνία περιστροφής προσεγγίζει τις γωνίες π και 3π/2 και για τον
άξονα των ψ, και όταν η γωνία περιστροφής προσεγγίζει τις γωνίες μηδέν και π και για τον
άξονα των χ. Η παραπάνω διαδικασία πραγματοποιείται ώστε να μην παραληφθεί κάποιο κελί,
ενώ ταυτόχρονα γίνεται έλεγχος ώστε να μην υπάρχουν διπλότυπα για τα κελιά στα όρια των
κομματιών. Για την αφαίρεση των διπλότυπων γεγονότων πραγματοποιούνται δύο ενέργειες.
Τα γεγονότα που συμβαίνουν σε μικρότερη γωνία από αυτή της γωνίας εκκίνησης
παραλείπονται, ενώ ταυτόχρονα η ανάγνωση της λίστας σάρωσης διακόπτεται αν ξεπεραστεί
η γωνία τερματισμού της κάθε διεργασίας.