Mutual exclusion (ME) is used to coordinate access to shared resources by concurrent processes. We investigate several new N-process shared-memory algorithms for variants of ME, each of which uses only reads and writes, and is local-spin, i.e., has bounded remote memory reference (RMR) complexity. We study these algorithms under two different shared-memory models: the distributed shared-memory (DSM) model, and the cache-coherent (CC) model. In particular, we present the first known algorithm for first- come-first-served (FCFS) ME that has O(log N) RMR complexity in both the DSM and CC models, and uses only atomic reads and writes. Our algorithm is also adaptive to point contention, i.e., the number of processes that are simultaneously active during a passage by some process. More precisely, the number of RMRs a process makes per passage in our algorithm is \Theta(min(c, log N)), where c is the point contention. We also present the first known FCFS abortable ME algorithm that is local-spin and uses only atomic reads and writes. This algorithm has O(N) RMR complexity in both the DSM and CC models, and is in the form of a transformation from abortable ME to FCFS abortable ME. In conjunction with other results, this transformation also yields the first known local-spin group mutual exclusion algorithm that uses only atomic reads and writes. Additionally, we present the first known local-spin k-exclusion algorithms that use only atomic reads and writes and tolerate up to k − 1 crash failures. These algorithms have RMR complexity O(N) in both the DSM and CC models. The simplest of these algorithms satisfies a new fairness property, called k-FCFS, that generalizes the FCFS fairness property for ME algorithms. A modification of this algorithm satisfies the stronger first-in-first-enabled (FIFE) fairness property. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our k-exclusion algorithms is inspired by Lamport’s famous Bakery algorithm.

Mutual exclusion (ME) is used to coordinate access to shared resources by concurrent processes. We investigate several new N-process shared-memory algorithms for variants of ME, each of which uses only reads and writes, and is local-spin, i.e., has bounded remote memory reference (RMR) complexity. We study these algorithms under two different shared-memory models: the distributed shared-memory (DSM) model, and the cache-coherent (CC) model. In particular, we present the first known algorithm for first- come-first-served (FCFS) ME that has O(log N) RMR complexity in both the DSM and CC models, and uses only atomic reads and writes. Our algorithm is also adaptive to point contention, i.e., the number of processes that are simultaneously active during a passage by some process. More precisely, the number of RMRs a process makes per passage in our algorithm is \Theta(min(c, log N)), where c is the point contention. We also present the first known FCFS abortable ME algorithm that is local-spin and uses only atomic reads and writes. This algorithm has O(N) RMR complexity in both the DSM and CC models, and is in the form of a transformation from abortable ME to FCFS abortable ME. In conjunction with other results, this transformation also yields the first known local-spin group mutual exclusion algorithm that uses only atomic reads and writes. Additionally, we present the first known local-spin k-exclusion algorithms that use only atomic reads and writes and tolerate up to k − 1 crash failures. These algorithms have RMR complexity O(N) in both the DSM and CC models. The simplest of these algorithms satisfies a new fairness property, called k-FCFS, that generalizes the FCFS fairness property for ME algorithms. A modification of this algorithm satisfies the stronger first-in-first-enabled (FIFE) fairness property. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our k-exclusion algorithms is inspired by Lamport’s famous Bakery algorithm.

La maquette numérique de bâtiment est un outil nouveau et en plein essor dans les métiers de la construction. Elle centralise les informations et facilite la communication entre les acteurs : évaluation des coûts, simulations physiques, présentations virtuelles, suivis de travaux, etc. Si une maquette numérique est désormais utilisée pour les grands chantiers de bâtiments nouveaux, il n'en existe pas en revanche pour la plupart des bâtiments déjà construits. Or, avec le vieillissement du parc immobilier et le développement du marché de la rénovation, la maquette numérique serait une aide considérable pour des bâtiments anciens. Des techniques de reconstruction plus ou moins automatique ont été développées ces dernières années, à base de mesures laser ou de photogrammétrie. Les lasers, précis et denses, sont chers mais restent abordables pour les industriels, tandis que la photogrammétrie, souvent moins précise et moins fiable dans les zones uniformes (p.ex. les murs), est beaucoup plus bon marché. Mais la plupart des approches s'arrêtent à la reconstruction de surfaces, sans produire de maquettes numériques. À la géométrie doit cependant s'ajouter des informations sémantiques décrivant les éléments de la scène. L'objectif de cette thèse est de fournir un cadre de reconstruction de maquettes numériques, à la fois en ce qui concerne la géométrie et la sémantique, à partir de nuages de points. Pour cela, plusieurs étapes sont proposées. Elles s'inscrivent dans un processus d'enrichissement des données, depuis les points jusqu'à la maquette numérique finale. Dans un premier temps, un estimateur de normales pour les nuages de points est défini. Basé sur une transformée de Hough robuste, il permet de retrouver correctement les normales, y compris dans les zones anguleuses et s'adapte à l'anisotropie des données. Dans un second temps, des primitives géométriques sont extraites du nuage de points avec leur normales. Afin d'identifier les primitives identiques existantes en cas de sur-segmentation, nous développons un critère statistique robuste et général pour l'identification de formes, ne requérant qu'une fonction distance entre points et formes. Ensuite, une surface planaire par morceaux est reconstruite. Des hypothèses de plans pour les zones visibles et les parties cachées sont générées et insérées dans un arrangement. La surface est extraite avec une nouvelle régularisation sur le nombre de coins et la longueur des arêtes. L'utilisation d'une formulation linéaire permet, après relaxation continue, d'extraire efficacement une surface proche de l'optimum. Enfin, nous proposons une approche basée sur des grammaires attribuées avec contraintes pour l'enrichissement sémantique de modèles 3D. Cette méthode est bottom-up : nous partons des données pour construire des objets de complexité croissante. La possible explosion combinatoire est gérée efficacement via l'introduction d'opérateurs maximaux et d'un ordre pour l'instanciation des variables / The interest for digital models in the building industry is growing rapidly. These centralize all the information concerning the building and facilitate communication between the players of construction : cost evaluation, physical simulations, virtual presentations, building lifecycle management, site supervision, etc. Although building models now tend to be used for large projects of new constructions, there is no such models for existing building. In particular, old buildings do not enjoy digital 3D model and information whereas they would benefit the most from them, e.g., to plan cost-effective renovation that achieves good thermal performance. Such 3D models are reconstructed from the real building. Lately a number of automatic reconstruction methods have been developed either from laser or photogrammetric data. Lasers are precise and produce dense point clouds. Their price have greatly reduced in the past few years, making them affordable for industries. Photogrammetry, often less precise and failing in uniform regions (e.g. bare walls), is a lot cheaper than the lasers. However most approaches only reconstruct a surface from point clouds, not a semantically rich building model. A building information model is the alliance of a geometry and a semantics for the scene elements. The main objective of this thesis is to define a framework for digital model production regarding both geometry and semantic, using point clouds as an entry. The reconstruction process is divided in four parts, gradually enriching information, from the points to the final digital mockup. First, we define a normal estimator for unstructured point clouds based on a robust Hough transform. It allows to estimate accurate normals, even near sharp edges and corners, and deals with the anisotropy inherent to laser scans. Then, primitives such as planes are extracted from the point cloud. To avoid over-segmentation issues, we develop a general and robust statistical criterion for shape merging. It only requires a distance function from points to shapes. A piecewise-planar surface is then reconstructed. Planes hypothesis for visible and hidden parts of the scene are inserted in a 3D plane arrangement. Cells of the arrangement are labelled full or empty using a new regularization on corner count and edge length. A linear formulation allow us to efficiently solve this labelling problem with a continuous relaxation. Finally, we propose an approach based on constrained attribute grammars for 3D model semantization. This method is entirely bottom-up. We prevent the possible combinatorial explosion by introducing maximal operators and an order on variable instantiation