Compact and efficient implicit representations

Abstract

In the perspective of manipulating geometric objects, there exists two main representations of curves and surfaces: parametric and implicit representations. Both are useful for different purposes and thus complement each other. Parametric representations are efficient in sampling points on an object; implicit representations are efficient in determining whether a point belongs to an object or not. Because of that, having both representations of the same objects at the same time maximizes the range of operations one can do with geometric objects. Switching from one representation to another is not an easy task. It usually requires the use of algebraic properties. Thus, there is a strong link between algebra and geometry, symbolised by the algebraic varieties: they are geometric objects described by an algebraic structure. This thesis explores new kinds of implicit representations and algorithms for computing implicit representations. We show that different methods are adapted to different situations even when it comes to the choice of an implicit representation amongst several possibilities. Space curves can thus be described implicitly by conical surfaces, moving lines and/or moving quadrics… each description having different geometrical properties and practical usage. As there is not one implicit representation or implicitization algorithm that would be the best in any situation, we develop methods that fit to different kinds of informations known about the object we want to represent. As we show, objects constructed by sweeping a rigid body can be represented using the knowledge of that nature. Similarly, very particular curves may have a complicated algebraic structure. Depending on our tolerance to approximation, such curves can thus be perturbed to simplify greatly their algebraic structure or, on the contrary, be represented by a rich implicit representation format.

Στην προοπτική του χειρισμού γεωμετρικών αντικειμένων, υπάρχουν δύο κύριες αναπαραστάσεις καμπυλών και επιφανειών: παραμετρικές και αλγεβρικές αναπαραστάσεις. Και οι δύο είναι χρήσιμες για διαφορετικούς σκοπούς και έτσι αλληλοσυμπληρώνονται. Οι παραμετρικές αναπαραστάσεις είναι αποτελεσματικές στα σημεία δειγματοληψίας ενός αντικειμένου. Οι αλγεβρικές αναπαραστάσεις είναι αποτελεσματικές για τον προσδιορισμό του αν ένα σημείο ανήκει σε ένα αντικείμενο ή όχι. Εξαιτίας αυτού, η κατοχή και των δύο αναπαραστάσεων για το ίδιο αντικείμενο μεγιστοποιεί το εύρος των λειτουργιών που μπορούν να πραγματοποιηθούν με το αντικείμενο αυτό. Η μετάβαση από μία αναπαράσταση σε άλλη δεν είναι εύκολη υπόθεση. Απαιτεί συνήθως τη χρήση αλγεβρικών ιδιοτήτων. Έτσι, υπάρχει μια ισχυρή σχέση μεταξύ άλγεβρας και γεωμετρίας, που συμβολίζεται από τα αλγεβρικά σύνολα: είναι γεωμετρικά αντικείμενα που περιγράφονται από αλγεβρικές εξισώσεις. Η μετάβαση από την παραμετρική στην αλγεβρική αναπαράσταση καλείται αλγεβρικοποίηση. Αυτή η εργασία εξετάζει νέα είδη αλγεβρικών αναπαραστάσεων και αλγορίθμων για τον υπολογισμό αλγεβρικών αναπαραστάσεων. Δείχνουμε ότι διάφορες μέθοδοι προσαρμόζονται σε διαφορετικές καταστάσεις, ακόμη και όταν πρόκειται για την επιλογή μιας αλγεβρικής αναπαράστασης μεταξύ διαφόρων αλγεβρικών αναπαραστάσεων. Οι καμπύλες στον χώρο μπορούν έτσι να περιγραφούν αλγεβρικά με κωνικές επιφάνειες, κινούμενες γραμμές και/ή κινούμενη τετραγωνική επιφάνεια… όπου κάθε περιγραφή έχει διαφορετικές γεωμετρικές ιδιότητες και πρακτική χρήση. Εφόσον δεν υπάρχει βέλτιστη αναπαράσταση ή βέλτιστος αλγόριθμος αλλαγής αναπαράστασης για όλες τις περιπτώσεις, επιλέγουμε να αναπτύξουμε μεθόδους που ταιριάζουν σε διάφορα είδη γνωστών πληροφοριών σχετικά με το αντικείμενο που θέλουμε να αντιπροσωπεύουμε. Όπως δείχνουμε, τα αντικείμενα που κατασκευάζονται με τη μετατόπιση ενός άκαμπτου σώματος (swept volumes) μπορούν να αναπαρίστανται χρησιμοποιώντας τη γνώση αυτής της φύσης. Ομοίως, πολύ συγκεκριμένες καμπύλες μπορεί να έχουν περίπλοκη αλγεβρική δομή. Ανάλογα με την ανοχή μας στην προσέγγιση, τέτοιες καμπύλες μπορούν έτσι να διαταραχθούν για να απλουστεύσουν σε μεγάλο βαθμό την αλγεβρική δομή τους ή, αντίθετα, να αναπαρασταθούν από ένα σχήμα πλούσιας αλγεβρικής δομής.