Return to search

Implantation de structures de données compactes pour les triangulations

La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens l'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à compresser le volume au maximum, et l'élaboration de structures théoriques compactes qui minimisent la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter de<br />façon compacte les triangulations. Pour ce faire, deux issues sont explorées : modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des indices sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'exécution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des micro-triangulations, et de représenter la triangulation comme un ensemble de ces micro-triangulations. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont <br />prometteurs, sachant que le temps d'exécution n'est pas dramatiquement altéré par la modification des méthodes d'accés aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage de l'information géométrique des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00336178
Date15 April 2008
CreatorsMebarki, Abdelkrim
PublisherUniversité de Nice Sophia-Antipolis
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0018 seconds