Simplification polyédrique optimale pour le rendu, Optimal polyhedral simplification for rendering

Emilie Charrier

Description

Sous la direction de Gilles Bertrand
Thèse soutenue le 04 décembre 2009: Paris Est
En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c’est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s’avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s’agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d’autre d’une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l’épaisseur d’un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure
-Géométrie discrète
-Géométrie algorithmique
-Polyédrisation
-Plan discret
-Enveloppe convexe
-Théorie des nombres
-Grille (analyse numérique)
In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension
-Digital geometry
-Computational geometry
-Polyhedrisation
-Digital plane
-Convex hull
-Number theory
-Lattice
Source: http://www.theses.fr/2009PEST1011/document

Sujets

• Géométrie discrète
• Géométrie algorithmique
• Enveloppe convexe
• Théorie des nombres

Informations

• Publié par: Thesee
• Nombre de lectures: 47
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

´UNIVERSITE PARIS-EST
ECOLE DOCTORALE ICMS
Th`ese pour obtenir le grade de docteur de l’universit´e PARIS-EST
Sp´ecialit´e : Informatique
pr´esent´ee par
´Emilie CHARRIER
le 4 d´ecembre 2009
Bourse DGA (DGA/D4S/MRIS)
´SIMPLIFICATION POLYEDRIQUE OPTIMALE
POUR LE RENDU
Directeur de th`ese : Gilles BERTRAND
Encadrant de th`ese : Lilian BUZER
Composition du jury :
Rapporteurs :
R´emy MALGOUYRES, Professeur, Universit´e d’Auvergne
´Val´erie BERTHE, Directrice de Recherche CNRS, Universit´e Montpellier II
Examinateurs :
Jacques-Olivier LACHAUD, Professeur, Universit´e de Savoie
David COEURJOLLY, Charg´e de recherche CNRS, Universit´e Lyon I
Lilian BUZER, Professeur associ´e, ESIEE-PARIS
Directeur de th`ese :
Gilles BERTRAND, Professeur, ESIEE-PARIS
tel-00532792, version 1 - 4 Nov 2010tel-00532792, version 1 - 4 Nov 2010`A Julien
i
tel-00532792, version 1 - 4 Nov 2010ii
tel-00532792, version 1 - 4 Nov 2010Cette th`ese a ´et´e pr´epar´ee `a :
Universit´e PARIS-EST
´Equipe A3SI du Laboratoire d’Informatique de l’Institut Gaspard Monge
CNRS, UMR 8049
ESIEE-PARIS
´2, bd Blaise Pascal, CITE DESCARTES, BP 99
93162 NOISY LE GRAND CEDEX
Grˆace `a une bourse de la DGA :
D´el´egation G´en´erale pour l’Armement
Direction des syst`emes de forces et des strat´egies industrielles, technologiques et de
coop´eration
Mission pour la recherche et l’innovation scientifique
D4S/MRIS – 00303 Arm´ees
8, bd Victor – 75015 PARIS
iii
tel-00532792, version 1 - 4 Nov 2010iv
tel-00532792, version 1 - 4 Nov 2010Remerciements
Jetienstoutd’abord`aremerciertr`eschaleureusementMonsieurLilianBuzerquia´et´e
pendant ces trois ann´ees mon encadrant de th`ese. Je lui suis extrˆemement reconnaissante
de la confiance qu’il m’a accord´ee depuis le premier jour. Il m’a guid´ee durant ma th`ese
tout en me laissant suffisamment d’autonomie et j’ai ´enorm´ement appris `a ses cˆot´es.
J’adresse ´egalement mes remerciements les plus sinc`eres `a Gilles Bertrand qui a ac-
cept´e d’ˆetre mon directeur de th`ese.
J’exprime ma gratitude `a tous les membres du jury qui ont bien voulu juger mes tra-
vaux de th`ese. Je remercie donc vivement Monsieur R´emy Malgouyres et Madame Val´erie
Berth´equiontaccept´elarudechargederapporteur.Unimmensemerci´egalement`aMon-
sieur Jacques-Olivier Lachaud et Monsieur David Coeurjolly qui ont bien voulu ´evaluer
mon travail.
Je suis tr`es reconnaissante envers la DGA qui m’a fait confiance en m’accordant une
allocation de recherche. Ma th`ese aurait ´et´e impossible sans ce financement.
Je remercie Monsieur Fabien Feschet de m’avoir propos´e de collaborer avec lui durant
ma troisi`eme ann´ee de th`ese, ce fut une exp´erience tr`es enrichissante.
Je tiens `a exprimer toute ma gratitude `a l’ensemble des membres de l’´equipe A3SI
pour leur bonne humeur et l’accueil chaleureux qu’ils m’ont r´eserv´e `a mon arriv´ee. Je
remercie en particulier Monsieur Denis Bureau et Monsieur Michel Couprie qui m’ont
donn´e l’opportunit´e d’enseigner en parall`ele de ma th`ese et qui, par la mˆeme occasion,
m’ont form´ee au m´etier d’enseignante.
Un immense merci `a tous mes coll`egues doctorants pour leur sympathie et leur in-
croyable capacit´e `a supporter mes humeurs changeantes. Concernant ce dernier point,
toutes mes f´elicitations `a John et Yohan qui ont duˆ partager le mˆeme bureau que moi
pendant presque trois ans!
Enfin, j’adresse toute mon affection `a ma famille qui, malgr´e les quelques centaines
de kilom`etres qui nous s´eparent, ont toujours ´et´e d’un tr`es grand soutien pour moi. Un
´enorme merci donc `a ma m`ere, mon p`ere, mon fr`ere et mes grands parents! Je remercie
affectueusement mon compagnon Julien pour sa patience et son soutien au quotidien.
v
tel-00532792, version 1 - 4 Nov 2010vi
tel-00532792, version 1 - 4 Nov 2010R´esum´e
En informatique, les images sont num´eriques et donc compos´ees de pixels en 2D et
de voxels en 3D. Dans une sc`ene virtuelle 3D, il est impossible de manipuler directement
les objets comme des ensembles de voxels en raison du trop gros volume de donn´ees. Les
objets sont alors poly´edris´es, c’est-`a-dire remplac´es par une collection de facettes. Pour ce
faire,ilestprimordialdesavoird´ecidersiunsous-ensembledevoxelspeutˆetretransform´e
en une facette dans la repr´esentation poly´edrique. Ce probl`eme est appel´e reconnaissance
de plans discrets. Pour le r´esoudre, nous mettons en place un nouvel algorithme sp´e-
cialement adapt´e pour les ensembles de voxels denses dans une boite englobante. Notre
m´ethode atteint une complexit´e quasi-lin´eaire dans ce cas et s’av`ere efficace en pratique.
En parall`ele, nous nous int´eressons `a un probl`eme algorithmique annexe intervenant dans
notrem´ethodedereconnaissancedeplansdiscrets.Ils’agitdecalculerlesdeuxenveloppes
2convexes des points de Z contenus dans un domaine vertical born´e et situ´es de part et
d’autre d’une droite quelconque. Nous proposons une m´ethode de complexit´e optimale et
adaptative pour calculer ces enveloppes convexes. Nous pr´esentons le probl`eme de ma-
ni`ere d´etourn´ee : d´eterminer le nombre rationnel `a d´enominateur born´e qui approxime
au mieux un nombre r´eel donn´e. Nous ´etablissons le lien entre ce probl`eme num´erique et
son interpr´etation g´eom´etrique dans le plan. Enfin, nous proposons ind´ependamment un
dnouvel algorithme pour calculer l’´epaisseur d’un ensemble de points dans le r´eseau Z .
Notre m´ethode est optimale en 2D et gloutonne mais efficace en dimension sup´erieure.
Mots cl´es
G´eom´etrie discr`ete, g´eom´etrie algorithmique, poly´edrisation, plan discret, enveloppe
convexe, th´eorie des nombres, grilles (analyse num´erique)
vii
tel-00532792, version 1 - 4 Nov 2010viii
tel-00532792, version 1 - 4 Nov 2010