Accelerating geometric queries for computer graphics: algorithms, techniques and applications

Abstract

In the ever-evolving context of Computer Graphics, the demand for realistic and real-time virtual environments and interaction with digitised or born-digital content has exponentially grown. Whether in gaming, production rendering, computer-aided design, reverse engineering, geometry processing, and understanding or simulation tasks, the ability to rapidly and accurately perform geometric queries of any type is crucial. The actual form of a geometric query varies depending on the task at hand, application domain, input representation, and adopted methodology. These queries may involve intersection tests as in the case of ray tracing, spatial queries, such as needed for recovering nearest sample neighbours, geometry registration in order to classify polygonal primitive inputs, or even virtual scene understanding in order to suggest and embed configurations as in the case of light optimisation and placement. As the applications of these algorithms and, consequently, their complexity continuously grow, traditional geometric queries fall short, when na\"ively adopted and integrated in practical scenarios. Therefore, these methods face limitations in terms of computational efficiency and query bandwidth. This is particularly pronounced in scenarios, where vast amounts of geometric data must be processed in interactive or even real-time rates. More often than not, one has to inspect and understand the internal mechanics and theory of the algorithms invoking these geometric queries. This is particularly useful in order to devise appropriately tailored procedures to the underline task, hence maximise their efficiency, both in terms of performance and output quality. As a result, there is an enormous area of research that explores innovative approaches to geometric query acceleration, addressing the challenges posed. The primary focus of this research was to develop innovative methods for accelerating geometric queries within the domain of Computer Graphics. This entails a comprehensive exploration of algorithmic optimisations that include the development of advanced data structures and neural network architectures, tailored to efficiently handle geometric collections. This research addressed not only the computational complexity of individual queries, but also the adaptability of the proposed solutions to diverse applications and scenarios primary within the realm of Computer Graphics but also intersecting domains. The outcome of this research holds the potential to influence the fields that adopt these geometric query methodologies by addressing the associated computational challenges and unlocking novel directions for real-time rendering, interactive simulation, and immersive virtual experiences. More specifically, the contributions of this thesis are divided into two broad directions for accelerating geometric queries: a) global illumination-related, hardware-accelerated nearest-neighbour queries and b) application of deep learning to the definition of novel data structures and geometric query methods. In the first part, we consider the task of real-time global illumination using photon density estimators. In particular we investigate scenarios where complex illumination effects, such as caustics, that can mainly be handled from the illumination theory regarding progressive photon mapping algorithms, require vast amount of rays to be traced from both the eye sensor and the light sources. Photons emanating from lights are cached into the surface geometry or volumetric media and must be gathered at query locations on the paths traced from the camera sensor. To achieve real-time frame rates, gathering, an expensive operation, needs to be efficiently handled. This is accomplished by adapting screen space ray tracing and splatting to the hardware-accelerated rasterisation pipeline. Since the gathering phase is an inherent subcategory of nearest neighbours search, we also propose how to efficiently generalise this concept to any form of task by exploiting existing low-level hardware accelerated ray tracing frameworks. Effectively boosting the inference phase by orders of magnitude compared to the traditional strategies involved. In the second part, we shift our focus to a more generic class of geometric queries. The first work involves accurate and fast shape classification using neural networks architectures. We demonstrate that a hybrid architecture, which processes orientation and a voxel-based representation of the input, is capable of processing hard-to-distinguish solid geometry from the context of building information models. Second, we consider the form of geometric queries in the context of scene understanding. More precisely, optimising the placement and light intensities of luminaries in urban places can be a computationally intricate task especially for large inputs and conflicting constraints. Methodologies employed in the literature usually make assumptions about the input representation to mitigate the intractable nature of this task. In this thesis, we approach this problem with a holistic solution that can produce feasible and diverse proposals in real time by adopting a neural-based generative modelling methodology. Finally, we propose a novel and general approach to solve recursive cost evaluators for the construction of geometric query acceleration data structures. This work establishes a new research direction for the construction of data structures guided by recursive cost functions using neural-based architectures. Our goal is to overcome the exhaustive but intractable evaluation of the cost function, in order to generate a high-quality data structure for spatial queries.

Στο συνεχώς εξελισσόμενο τομέα των Γραφικών Υπολογιστών, η ζήτηση για ρεαλιστικά και σε πραγματικό χρόνο εικονικά περιβάλλοντα με αλληλεπίδραση σε ψηφιοποιημένα ή εκ γενετής ψηφιακά περιεχόμενα έχει εκθετικά αυξηθεί. Είτε πρόκειται για παιχνίδια, production rendering, computer-aided design reverse engineering, επεξεργασία και κατανόηση γεωμετρικής πληροφορίας ή διεργασίες προσομοίωσης, η ικανότητα γεωμετρικών αναζητήσεων οποιουδήποτε τύπου να εκτελούνται γρήγορα και με ακρίβεια είναι κρίσιμη. Η πραγματική μορφή ενός γεωμετρικού ερωτήματος ποικίλει ανάλογα με την εκάστοτε διεργασία, τον τομέα εφαρμογής, την αναπαράσταση της εισόδου και τη χρησιμοποιούμενη μεθοδολογία. Αυτά τα γεωμετρικά ερωτήματα μπορεί να περιλαμβάνουν ελέγχους τομής, όπως στην περίπτωση του ray tracing, χωρικά ερωτήματα, όπου χρειάζονται για την ανάκτηση πλησιέστερων γειτονικών δειγμάτων, γεωμετρική ανάκτηση, για την εξακρίβωση του τύπου των πολυγωνικών εισόδων ή ακόμα και κατανόηση μίας ολόκληρης εικονικής σκηνής για την ανάκτηση και ενσωμάτωση εναλλακτικών λύσεων, όπως στην περίπτωση βελτιστοποίησης και τοποθέτησης φωτιστικών πηγών. Καθώς οι εφαρμογές αυτών των αλγορίθμων και, συνεπώς, η πολυπλοκότητά τους αυξάνεται συνεχώς, τα βασικά αυτά γεωμετρικά ερωτήματα υστερούν όταν υιοθετούνται και ενσωματώνονται με απλοϊκό τρόπο σε πρακτικά σενάρια. Επομένως, αυτές οι μέθοδοι αντιμετωπίζουν περιορισμούς όσον αφορά την υπολογιστική αποδοτικότητα αυτών των αναζητήσεων. Αυτό είναι ιδιαίτερα έντονο σε σενάρια όπου πρέπει να ικανοποιηθεί ένας γιγάντιος αριθμός γεωμετρικών δεδομένων και ειδικότερα σε περιβάλλονται με διαδραστικό ή ακόμη και πραγματικό χρόνο απόδοσης. Τις περισσότερες φορές, πρέπει να εξετάσουμε και να κατανοήσουμε τους εσωτερικούς μηχανισμούς και τη θεωρία των αλγορίθμων που εκτελούν αυτά τα γεωμετρικά ερωτήματα. Αυτό είναι ιδιαίτερα χρήσιμο για την σχεδίαση κατάλληλων διαδικασιών προσαρμοσμένων στην εκάστοτε διεργασία, ώστε να μεγιστοποιηθεί η αποδοτικότητά τους, τόσο από άποψη ταχύτητας όσο και ποιότητας του αποτελέσματος. Αυτό έχει ως αποτέλεσμα, να υπάρχει ένας τεράστιος τομέας έρευνας που μελετά καινοτόμες προσεγγίσεις για την επιτάχυνση των γεωμετρικών αυτών αναζητήσεων, σε μία προσπάθεια να αντιμετωπίσει τις προκλήσεις που προκύπτουν.Ο κύριος στόχος αυτής της διατριβής ήταν να αναπτύξει καινοτόμες μεθόδους για την επιτάχυνση γεωμετρικών αναζητήσεων στο τομέα των Γραφικών Υπολογιστών. Η εργασία αυτή είχε μία ολιστική προσέγγιση στην διερεύνηση αλγοριθμικών βελτιστοποιήσεων που συντελούν στην ανάπτυξη προηγμένων δομών δεδομένων και αρχιτεκτονικών νευρωνικών δικτύων, ειδικά προσαρμοσμένων στην αποτελεσματική διαχείριση γεωμετρικών συλλογών. Η έρευνα αυτή όχι μόνο συμπεριέλαβε την υπολογιστική πολυπλοκότητα των αναζητήσεων αυτών, αλλά και την προσαρμοστικότητα των προτεινόμενων λύσεων σε διάφορες εφαρμογές και σενάρια, κυρίως στο πεδίο των Γραφικών Υπολογιστών αλλά και σε άλλους διασταυρούμενους τομείς. Τα αποτελέσματα αυτής της διατριβής έχουν τη δυνατότητα να επηρεάσουν τους τομείς και τις αντίστοιχες μεθοδολογίες που την υιοθετούν, αντιμετωπίζοντας τις σχετικές υπολογιστικές προκλήσεις και ανοίγοντας νέους ορίζοντες στην απεικόνιση πραγματικού χρόνου, την διαδραστική προσομοίωση και τις εμβυθιστικές τεχνολογίες εικονικής πραγματικότητας. Πιο συγκεκριμένα, οι συνεισφορές αυτής της διατριβής μπορούν να χωριστούν σε δύο κύριες κατευθύνσεις με στόχο την επιτάχυνση των γεωμετρικών αναζητήσεων: α) τεχνικές αναζήτησης πλησιέστερων δειγμάτων άμεσα επιταχυνόμενες από το, hardware στο πεδίο του ολικού φωτισμού και β) εφαρμογή τεχνικών βαθιάς μάθησης για τον ορισμό νέων δομών δεδομένων αλλά και γενικών μεθόδων γεωμετρικών αναζητήσεων. Οι μεθοδολογίες που ανήκουν στην πρώτη κατηγορία εξετάζουν την αλγοριθμική εφαρμογή ολικού φωτισμού σε πραγματικό χρόνο χρησιμοποιώντας εκτιμητές πυκνότητας των φωτονίων. Συγκεκριμένα, διερευνούμε σενάρια με δύσκολα φαινόμενα φωτιστικών ανακλάσεων, όπως αυτά των caustics που μπορούν να αντιμετωπιστούν κυρίως από την οικογένεια φωτιστικών μοντέλων του progressive photon mapping και απαιτούν την σκέδαση μεγάλου αριθμού ακτίνων τόσο από την κάμερα όσο και από τις φωτεινές πηγές. Τα φωτόνια που προέρχονται από τα φωτεινές πηγές, αποθηκεύονται στις επιφάνειες της γεωμετρίας ή σε κάποιο ογκομετρικό μέσο. Από εκεί θα πρέπει να συγκεντρωθούν μέσω αναζητήσεων που εκτελούνται κατά τις σκεδάσεις των ακτινών που προέρχονται από την κάμερα. Για την επίτευξη πραγματικού χρόνου απόκρισης ανά καρέ, η συγκέντρωση φωτονίων ανά αναζήτηση πρέπει να εκτελεστεί αποτελεσματικά παρά την χρονοβόρα λειτουργία που πρέπει να εκτελεστεί. Αυτό επιτυγχάνεται προσαρμόζοντας το tracing των ακτίνων σε μία screen space τεχνική και χρησιμοποιώντας το splatting ως μία μέθοδο άμεσα επιταχυνόμενη από το rasterisation. Τέλος, δεδομένου ότι η συγκέντρωση γειτόνων σε φραγμένο χώρο είναι μία εγγενής υποκατηγορία της αναζήτησης πλησιέστερων γειτόνων, προτείνουμε επιπλέον την αποτελεσματική γενίκευση αυτής της έννοιας σε οποιαδήποτε μορφή διεργασίας που εκμεταλλεύεται τα υπάρχοντα περιβάλλοντα ray tracing, και είναι άμεσα επιταχυνόμενα από το υπάρχον υλικό στις σημερινές κάρτες γραφικών. Έτσι, ενισχύουμε αποτελεσματικά τη φάση διεκπεραίωσης αυτών τον αναζητήσεων κατά πολλές τάξεις μεγέθους σε σύγκριση με τις υπάρχουσες παραδοσιακές στρατηγικές που συχνά υλοποιούνται.Όσον αφορά την δεύτερη κατηγορία των συνεισφορών μας, εστιάζουμε το ενδιαφέρον μας σε μια γενικότερη κατηγορία γεωμετρικών αναζητήσεων. Η πρώτη περιλαμβάνει την ακριβή και γρήγορη κατηγοριοποίηση γεωμετρικών σχημάτων χρησιμοποιώντας νευρωνικά δίκτυα. Συγκεκριμένα δείχνουμε ότι μια υβριδική μεθοδολογία επεξεργάζεται τον προσανατολισμό σε συνδυασμό με την voxelised γεωμετρική αναπαράσταση είναι ικανή να διεκπεραιώνει δύσκολα για κατηγοροιοποιήση στερεές γεωμετρίες που συναντούνται στο χώρο των κτιριακών κατασκευών. Δεύτερον, εξετάζουμε τη κλάση γεωμετρικών αναζητήσεων που σχετίζονται με την ανάλυση εικονικών σκηνών. Πιο συγκεκριμένα, μελετάμε την βελτιστοποίηση τοποθέτησης και ανάθεσης των φωτιστικών εντάσεων σε δρόμους αστικών οικισμών, που είναι εκ των πραγμάτων μια υπολογιστικά περίπλοκη διεργασία, ειδικά για μεγάλες εισόδους και αντιφατικούς περιορισμούς. Οι υπάρχουσες μεθοδολογίες που χρησιμοποιούνται στη πρόσφατη βιβλιογραφία συνήθως εισάγουν υποθέσεις ως προς την αναπαράσταση της εισόδου για να μετριάσουν τη πολυπλοκότητα αυτής της διεργασίας. Ωστόσο, σε αυτήν τη διατριβή, προσεγγίζουμε αυτό το πρόβλημα με μια ολιστική λύση που μπορεί να παράγει εφικτές και ποικίλες λύσεις σε πραγματικό χρόνο υιοθετώντας μία οικογένεια generative νευρωνικών δικτύων. Τέλος, προτείνουμε μια νέα και γενικευμένη προσέγγιση για την επίλυση αναδρομικών συναρτήσεων κόστους για την κατασκευή δομών επιτάχυνσης γεωμετρικών αναζητήσεων. Η συγκεκριμένη εργασία δείχνει προς μία νέα ερευνητική κατεύθυνση με σκοπό την κατασκευή δομών δεδομένων που καθοδηγούνται από αναδρομικές συναρτήσεις κόστους χρησιμοποιώντας μεθοδολογίες νευρωνικών δικτύων. Στόχος μας είναι να παρακάμψουμε την εξαντλητική αλλά και αδύνατη αναζήτηση του χώρου καταστάσεων δοσμένης της συνάρτησης κόστους, ώστε να δημιουργήσουμε υψηλής ποιότητας δομές δεδομένων για χωρικές αναζητήσεις.