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

´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