La plupart des algorithmes qui traitent des objets polygonaux en 3D utilisent des coordonnées où la précision est fixée pour les données d’entrée et de sortie. Cependant, les opérations géométriques produisent souvent des coordonnées de sortie qui nécessitent une précision supérieure à celle des données d’entrée. Cet écart implique la nécessité d’arrondir les nouvelles coordonnées pour qu’elles correspondent à la précision des données d’entrée, tout en préservant l’intégrité du modèle. Le problème critique que nous abordons est la suppression des auto-intersections dans les modèles 3D, obtenue en subdivisant les faces le long de leurs intersections et en arrondissant les coordonnées résultantes, tout en veillant à ce que le modèle reste exempt d’auto-intersections. Ce problème est connu sous le nom de « snap rounding problem ». Dans cette thèse, nous présentons le premier algorithme pratique et certifié de snap rounding en 3D, qui élimine avec succès les auto-intersections dans 94% des modèles présentants des auto-intersections de l’ensemble de données Thingi10K, et démontrant ainsi son effictivité dans les applications du monde réel. En outre, nous introduisons une heuristique non certifiée mais très efficace pour ce problème, qui surpasse l’état de l’art actuel en résolvant avec succès toutes les auto-intersections dans l’ensemble de données Thingi10K.

Abstract: Most algorithms for processing 3D polygonal objects use fixed-precision coordinates for both input and output data. However, geometric operations often produce output coordinates that require higher precision than the input. This discrepancy implies the need for rounding new coordinates to match the precision of the input, while preserving the integrity of the model. The critical problem we address is the removal of self-intersections in 3D models, achieved by subdividing faces along their intersections and rounding the resulting coordinates, while ensuring that the model remains free from self-intersections. This problem is known as the snap rounding problem. In this thesis, we present the first practical and certified local 3D snap rounding algorithm, which successfully eliminates self-intersections in 94% of the self-intersecting models in the Thingi10K dataset, demonstrating its effectiveness in real-world applications. Additionally, we introduce an uncertified yet highly efficient heuristic for this problem, which outperforms previous state-of-the-art methods by successfully resolving all self-intersections in the Thingi10K dataset.