|
|
|
|
|
|
|---|
La modélisation géométrique est devenue un domaine de recherche et de développement central à un vaste champ d'applications. Avec la forte croissance de la puissance de calcul des ordinateurs, la simulation par ordinateur a commencé à jouer un rôle important dans plusieurs domaines de recherche reliés à la modélisation géométrique, de l'ingénierie traditionnelle à la simulation de chirurgie virtuelle.À cause de l'usage de représentations de précision finie, l'absence de robustesse numérique en calcul scientifique est un phénomène bien connu et répandu. De nombreuses approches différentes ont été proposées pour résoudre ce problème. Les nombres en virgule flottante (IEEE 754/854) [PH98, Ove01] sont les substituts standards pour les nombres réels en calculs informatisés, et la plupart des logiciels de modélisation de solides, incluant les systèmes de conception assistée par ordinateur (CAO), sont basés sur des méthodes de modélisation géométrique qui fonctionnent en utilisant l'arithmétique en virgule flottante. Mais cette dernière, appliquée naïvement, peut causer l'échec d'axiomes géométriques. L'analyse inverse d'erreur (backward error analysis), maintenant standard, est un outil très utile qui peut nous aider à surmonter ce problème : elle nous permet de distinguer les algorithmes qui, en présence d'incertitudes dans les données, ont produit des résultats aussi bien que nous pouvions espérer.
L'impact de l'absence de robustesse dans le domaine de la modélisation géométrique a été ouvertement reconnu et il y a eu beaucoup d'attention pour améliorer la fiabilité. D'un autre côté, il existe plusieurs représentations en modélisation géométrique et, mêeme si chacune parvient à bien modéliser certaines propriétés, aucune d'elles n'est suffisamment générale pour satisfaire tous les prérequis qui pourraient être souhaitables d'une représentation. Ainsi, pour des problèmes géométriques différents, l'absence de robustesse tend à se manifester de différentes façons et nous devons chercher la méthode appropriée pour chaque problème : une solution universelle n'existe pas
Le but de cette thèse est d'étudier le calcul informatisé fiable en modélisation géométrique. En particulier, nous abordons trois problèmes reliés à la robustesse en modélisation géométrique :
1. L'arithmétique en virgule flottante pour des problèmes de géométrie informatique avec des données incertaines.
2. Jonction fiable de surfaces pour des modèles combinant maillages et surfaces paramétriques.
3. Robustesse d'opérations booléennes sur les modèles de surface de subdivision.
Geometric modeling has become a central area of research and development that involves diverse applications. In fact, because of greatly increased computer power, computer simulation has started playing an important role in many geometric-modeling related research domains, from traditional engineering design to virtual surgery simulation.Due to the use of finite-precision representation, numerical nonrobustness in scientific computing is a well-known and widespread phenomenon. Several different approaches have been proposed for this problem. Floating-point numbers (IEEE 754/854) are the standard substitute for real numbers in computations, and most solid modelers, including CAD (Computer Aided Design) systems, are based on geometric-modeling methods that operate using floating-point arithmetic. But naively applied floating-point arithmetic can cause axioms of geometry to fail. The now-standard backward error analysis is a very useful tool that can help us overcome this problem: it permits us to distinguish those algorithms which, given the presence of uncertainties in the data, have done as well as we can hope for.
The impact of nonrobustness in the domain of geometric modeling has been widely acknowledged, and much attention has been paid to improving reliability. On the other hand, many different geometric modeling representations exist, and although each succeeds in modeling certain properties well, none of them is general enough to satisfy all the requirements that could be demanded of a representation. Therefore, for different geometric problems, nonrobustness tends to manifest itself in different ways, and we must seek an appropriate method for each problem: a universal solution does not exist.
The goal of this thesis is to study reliable computation for geometric models. In particular, we will address three related robustness problems in geometric modeling:
1. Floating-point arithmetic for computational-geometry problems with uncertain data.
2. Reliable joining of surfaces for combined mesh-surface models.
3. Robustness of Boolean operations on subdivision-surface models.
@PhdThesis{Jiang:2008:PHD,
author = "Di Jiang",
title = "Reliable Computation for Geometric Models",
month = nov,
year = 2008,
type = "Ph.D. Thesis",
school = "D{\'e}partement d'Informatique et Recherche
Op{\'e}rationnelle, Universit{\'e} de Montr{\'e}al",
}