Reconstruction et Correction de Modèles Urbains à l'Aide de Structures de Données Cinétiques

Compact and accurate digital 3D models of buildings are commonly used by practitioners for the visualization of existing or imaginary environments, the physical simulations or the fabrication of urban objects. Generating such ready-to-use models is however a difficult problem. When created by designers, 3D models usually contain geometric errors whose automatic correction is a scientific challenge. When created from data measurements, typically laser scans or multiview images, the accuracy and complexity of the models produced by existing reconstruction algorithms often do not reach the requirements of the practitioners. In this thesis, I address this problem by proposing two algorithms: one for repairing the geometric errors contained in urban-specific formats of 3D models, and one for reconstructing compact and accurate models from input point clouds generated from laser scanning or multiview stereo imagery. The key component of these algorithms relies upon a space-partitioning data structure able to decompose the space into polyhedral cells in a natural and efficient manner. This data structure is used to both correct geometric errors by reassembling the facets of defect-laden 3D models, and reconstruct concise 3D models from point clouds with a quality that approaches those generated by Computer-Aided-Design interactive tools.My first contribution is an algorithm to repair different types of urban models. Prior work, which traditionally relies on local analysis and heuristic-based geometric operations on mesh data structures, is typically tailored-made for specific 3D formats and urban objects. We propose a more general method to process different types of urban models without tedious parameter tuning. The key idea lies on the construction of a kinetic data structure that decomposes the 3D space into polyhedra by extending the facets of the imperfect input model. Such a data structure allows us to re-build all the relations between the facets in an efficient and robust manner. Once built, the cells of the polyhedral partition are regrouped by semantic classes to reconstruct the corrected output model. I demonstrate the robustness and efficiency of the algorithm on a variety of real-world defect-laden models and show its competitiveness with respect to traditional mesh repairing techniques from both Building Information Modeling (BIM) and Geographic Information Systems (GIS) data.My second contribution is a reconstruction algorithm inspired by the Kinetic Shape Reconstruction method, that improves the later in different ways. In particular, I propose a data fitting technique for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the technique refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. The solution is found by an exploration mechanism guided by a multi-objective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. I demonstrate its potential, not on buildings only, but on a variety of scenes, from organic shapes to man-made objects.Les modèles numériques 3D compacts et précis de bâtiments sont couramment utilisés par les praticiens pour la visualisation d’environnements existants ou imaginaires, les simulations physiques ou la fabrication d’objets urbains. La génération de tels modèles prêts à l’emploi est cependant un problème difficile. Lorsqu’ils sont créés par des designers, les modèles 3D contiennent généralement des erreurs géométriques dont la correction automatique est un défi scientifique. Lorsqu’ils sont créés à partir de mesures de données, généralement des balayages laser ou des images multivues, la précision et la complexité des modèles produits par les algorithmes de reconstruction existants n’atteignent souvent pas les exigences des praticiens. Dans cette thèse, j’aborde ce problème en proposant deux algorithmes : l’un pour réparer les erreurs géométriques contenues dans les formats spécifiques de modèles de bâtiments, et l’autre pour reconstruire des modèles compacts et précis à partir de nuages de points générés à partir d’un balayage laser ou d’images stéréo multivues. Le composant clé de ces algorithmes repose sur une structure de données de partitionnement d’espace capable de décomposer l’espace en cellules polyédriques de manière naturelle et efficace. Cette structure de données permet à la fois de corriger les erreurs géométriques en réassemblant les facettes de modèles 3D chargés de défauts, et de reconstruire des modèles 3D à partir de nuages de points avec une précision et complexité proche de celles générées par les outils interactifs de Conception Assistée par Ordinateur.Ma première contribution est un algorithme pour réparer différents types de modèles urbains. Les travaux antérieurs, qui reposent traditionnellement sur une analyse locale et des heuristiques géométriques sur des maillages, sont généralement conçus sur-mesure pour des formats 3D et des objets urbains spécifiques. Nous proposons une méthode plus générale pour traiter différents types de modèles urbains sans réglage fastidieux des paramètres. L’idée clé repose sur la construction d’une structure de données cinétiques qui décompose l’espace 3D en polyèdres en étendant les facettes du modèle d’entrée imparfait. Une telle structure de données permet de reconstruire toutes les relations entre les facettes de manière efficace et robuste. Une fois construites, les cellules de la partition polyédrique sont regroupées par classes sémantiques pour reconstruire le modèle de sortie corrigé. Je démontre la robustesse et l’efficacité de l’algorithme sur une variété de modèles réels chargés de défauts et montre sa compétitivité par rapport aux techniques traditionnelles de réparation de maillage à partir de données de modélisation des informations du bâtiment (BIM) et de systèmes d’information géographique (SIG).Ma deuxième contribution est un algorithme de reconstruction inspiré de la méthode Kinetic Shape Reconstruction, qui améliore cette dernière de différentes manières. En particulier, je propose une technique pour détecter des primitives planaires à partir de nuages de points 3D non organisés. Partant d’une configuration initiale, la technique affine à la fois les paramètres du plan continu et l’affectation discrète de points d’entrée à ceux-ci en recherchant une haute fidélité, une grande simplicité et une grande complétude. La solution est trouvée par un mécanisme d’exploration guidé par une fonction énergétique à objectifs multiples. Les transitions dans le grand espace des solutions sont gérées par cinq opérateurs géométriques qui créent, suppriment et modifient les primitives. Je démontre son potentiel, non seulement sur des bâtiments, mais sur une variété de scènes, des formes organiques aux objets fabriqués par l’homme