|
|
|
|
|
|
|---|
Un des problèmes fondamentaux dans l'étude de la robustesse des méthodes numériques en modélisation des solides est que les données fournies à l'algorithme présentent souvent des incohérences géométriques (comme des décalages ou superpositions de surfaces). Ces problèmes sont dus aux erreurs provoquées par:
- une incertitude dans les données de départ,
- l'arithmétique en virgule flottante,
- l'approximation des frontières des faces d'un objet par des courbes de bas degré, par exemple de degré 3.Notre premier objectif était d'analyser l'erreur dans le contexte des opérations géométriques entre solides soumis à ces trois erreurs. Mais nous nous sommes heurtés à un problème préalable important : que représentent les données incoh érentes supposées décrire les objets soumis à la méthode numérique ? Quelle est leur réalisation ? Comment s'assurer que les données géométriques concordent avec les propriétés topologiques de l'objet ?
Il est donc primordial de définir rigoureusement les sous-ensembles de R3 (objets) présentés à l'algorithme. Le but de cette thèse est donc de résoudre ce premier problème d'incohérence et d'incertitude sur les données apportant ainsi une contribution à la solution du problème global de définition de la robustesse des méthodes numériques en modélisation des solides.
Nous proposons [4] une solution basée sur le théorème deWhitney. Ce théorème nous permet de définir des ensembles QuasiNURBS qui seront la réalisation des données incohérentes de départ pour chaque objet. Nous illustrons le problème et discutons de la solution proposée sur un exemple. Une approche analogue pour les surfaces subdivisées est aussi décrite [74].
L'introduction dans notre solution des patches de surface découpées (trimmed patches), permet de résoudre le problème pour des modèles dont les frontières ne peuvent pas être décrites en utilisant des courbes de bas degré et d'éviter donc la troisième erreur citée ci-dessus.
Dans cette étude, nous nous intéressons donc à la qualité géométrique et topologique de la réalisation en démontrant la validité des données auquel cas sera défini l'ensemble QuasiNURBS correspondant. Nous énonçons à cet effet, des théorèmes précisant les hypothèses pour que ces ensembles soient bien formés, i.e., qu'ils correspondent aux données et que leurs frontières ne s'autointersectent pas. Les critères de la détection de l'autointersection sont discutés et illustrés [5]. La détection d'autointersection est un sujet délicat, qui se complique par le fait que les sous-ensembles de R3 considérés sont des trimmed patches mais dans tous les cas, le test de détection nécessitera de borner la variation des normales. Nous énonçons et démontrons à cet effet un théorème permettant d'obtenir ces bornes.
Nous concluons par une brève description de la qualité numérique, i.e., la stabilité numérique, d'un algorithme effectuant une opération entre deux objets (c'est-à-dire entre leur représentation) par le biais de l'analyse inverse de l'erreur. Nous pensons que notre définition rigoureuse d'une représentation valide permettra maintenant de faire cette analyse.
One of the fundamental problems in the study of robustness of numerical methods in solid modelling is that the data provided to the algorithm is often inconsistent (including gaps and overlaps of surfaces). These problems are due to error caused by :
- uncertainty in the input data,
- the use of floating-point arithmetic,
- the approximation of the boundaries of object faces by low degree curves (say, of degree 3).Our principal goal was to perform error analysis in the context of geometric operations on solids, in the presence of the types of error mentioned above. Immediately, however, we encountered an important preliminary problem : what set is actually represented by the inconsistent data provided to the method ? What is their actual realisation ? How can we be sure that they are consistent with the topological data associated with the object ?
Consequently, it is fundamental to define rigorously the subsets of R3 (the objects) presented to the algorithm. The goal of this thesis is to solve this preliminary problem of inconsistent and uncertain data, thus making a contribution to the solution of the overall problem of defining robustness of numerical methods in solid modelling.
We propose a solution [4] based on the Whitney Extension Theorem. This theorem allows us to define what we call QuasiNURBS sets, which will be the realisation of the inconsistent data for each input object. We illustrate the problem and discuss the proposed solution in an example. An analogous approach is also proposed for combined subdivision surfaces [74].
The fact that our approach deals with trimmed patches means that we deal with patches for which the boundary cannot be represented by low-degree curves, and thus with the third source of error itemized above.
In this study, we are concerned with the geometric and topological quality of the realisation i.e., with well-formedness. In the case of well-formed objects, the data can be considered valid, and there will exist a corresponding QuasiNURBS set. We give theorems which will guarantee various aspects of well-formedness, i.e., that there exist sets with non-selfintersecting boundaries that correspond to the given data. The criteria for non-selfintersection are presented in [5]. In fact, this problem of non-selfintersection is made more complicated by the fact that we are dealing with trimmed patches, but however these difficulties are resolved, it will be necessary to find bounds on the variation of the face normals. We give a theorem which provides such bounds.
We conclude with a brief description of the question of the quality of computed answers, as reflected in the numerical stability of an algorithm to effect an operation on two objects (or, more precisely, their representations) by using a backward error analysis. We think that our rigorous definition of a valid representation will now permit such an analysis. Keywords : Data uncertainty, QuasiNURBS, Bézier, trimmed patches, realisation, well-formed, Whitney extension, Lipschitz constant, selfintersection, normal vector.
Mots clefs: incertitude des données, QuasiNURBS, Bézier, trimmed patches, réalisation, valide, extension de Whitney, constante de Lipschitz, autointersection, vecteur normal.Keywords: Data uncertainty, QuasiNURBS, Bézier, trimmed patches, realisation, well-formed, Whitney extension, Lipschitz constant, selfintersection, normal vector.
@PhDThesis{Zidani:2006:PHD,
author = "Malika Zidani Boumedien",
title = "Validit\'e d'un mod\`ele QuasiNURBS interpolant des donn\'ees g\'eom\'etriques incertaines",
month = mar,
year = 2006,
type = "Ph.D. Thesis",
school = "D{\'e}partement d'Informatique et Recherche
Op{\'e}rationnelle, Universit{\'e} de Montr{\'e}al",
}