APPLICATION DES CARTES COMBINATOIRES À LA
MODÉLISATION GÉOMÉTRIQUE ET SÉMANTIQUE
DES BÂTIMENTS

 prétraitements

Il est rare de pouvoir prétendre à une reconstruction topologique correcte directement à partir des données brutes d’un modèle bâtiment. En effet bon nombre d’entités géométriques sont sources de corruption pour les informations topologiques. Ce problème est très bien connu dans le domaine et est sans doute la raison pour laquelle une quantité conséquente de modèles disponibles restent le plus souvent intégralement ou en partie inexploitables pour des applications d’analyses et de calculs. Nous qualifions ainsi de modèles propres ceux qui ne présentent pas ces défauts, ou qui en contiennent en nombre assez négligeable pour ne pas perturber les opérations requises pour une bonne reconstruction topologique. Par conséquent, pour obtenir des résultats optimaux lors de notre processus d’enrichissement d’informations de modèles bas niveaux, quelques étapes de nettoyage des fichiers d’entrée semblent donc incontournables. 3.3 prétraitements 57 À travers l’exploitation des différents types de modèles, nous avons identifié plusieurs types de problèmes récurrents. Ils sont souvent involontaires, mais peuvent tout aussi être intentionnels. En effet dans le but de produire des effets visuels ciblés, les designers peuvent faire usage d’astuces leur permettant de faire ressortir ou dissimuler des formes ou composants du modèle. Ils peuvent ainsi rajouter des géométries qui faussent la description topologique d’un composant ainsi que l’interprétation qui pourrait en être faite lors d’opérations de simulation par exemple. Par ailleurs, les méthodes de création des modèles contribuent de manière conséquente à la présence de géométrie dégénérées. Des procédés comme la reconstruction à partir de nuages de points par exemple sont plus à même d’inclure des erreurs de géométrie, qui sont les conséquences de données manquantes (occlusion lors des scans) ou de reconstruction approximatives. Bien que plus précis et détaillés, les modèles bâtiments créés avec des outils CAAO peuvent aussi présenter les symptômes précédemment cités. En effet, il n’est pas rare que des opérations de simplifications automatiques résultent sur des pertes de données qui sont cruciales à l’interprétation topologique et sémantique. Dans cette section, nous traitons la géométrie chargée dans le EBM-LCC à l’issue de la phase précédente (cf. section 3.2). Un ensemble d’opérations de correction de ces entités géométriques est défini afin d’éviter un maximum d’erreurs lors de la reconstruction topologique. L’objectif est de réduire les problèmes au point de les rendre négligeables à défaut de totalement les supprimer. Ces opérations spécifiques se sont montrées nécessaires à travers nos diverses expériences et sont effectuées dans l’ordre suivant : — fusion des 0-cellules proches ; — suppression des 2-cellules dégénérées ; — correction des 2-cellules complexes ; — suppression des clones ; — fusion des 2-cellules coplanaires. La dernière étape constitue plus une phase d’optimisation que de correction, car elle permet de réduire le nombre de faces avant le reconstruction de leurs liens β2. Nous proposons dans les sous sections suivantes une explication détaillée de l’ensemble de ces opérations de prétraitement. 

Fusion des 0-cellules proches

Souvent dû à des problèmes d’imprécision, certains sommets du modèle ont des valeurs très proches, mais ne sont pas confondus dans l’espace. Cela a pour conséquence de créer de petits espaces qui s’avèrent problématiques pour reconstruire une topologie correcte. Une illustration de ce problème est présentée 58 reconstruction topologique de bâtiments 3d dans la figure 43. Un grossissement au niveau du point commun à FA, FB et FC permet de mettre en évidence un petit espace entre FA et FB (cf. figure 43b) du fait des coordonnées des sommets pA et pB qui sont légèrement différentes. FA FB FC (a) pA pB pC (b) pA pB pC (c) Figure 43 – (a) Exemple de trois faces voisines FA, FB et FC. (b) Les sommets pB et pC sont confondus, tandis que pA leur est très proche mais pas confondu. (c) pA est légèrement déplacé pour être fusionné avec pB et pC. Pour corriger ce problème, l’approche adoptée consiste à déplacer légèrement certains sommets du modèle afin d’uniformiser leur position avec les sommets voisins (cf. figure 43c). Pour toute paire de brins {b1, b2} ⊂ B avec 0-attr(b1) = p1(x1, y1, z1) et 0-attr(b2) = p2(x2, y2, z2), si la distance L qui sépare p1 et p2 est telle que : L = ||−p−→ 1p2|| =  (x2 − x1)2 + (y2 − y1)2 + (z2 − z1)2  0 (1) alors 0-attr(b2) ← p1. En d’autres termes nous procédons à un réajustement des 0-cellules proches de leurs voisins en modifiant les 0-attributs qui leur sont associés. Une opération de tri sur l’ensemble des 0-cellules de C est effectuée en fonction de leurs coordonnées, pour faciliter la recherche de voisins. À l’issue de cette opération de prétraitement, seul les 0-attributs de certains brins de C auront subit des modifications, mais le nombre de 0-cellules, 1-cellules et 2-cellules ne change pas.

Suppression des 2-cellules dégénérées

Tout polygone présentant une surface nulle ou quasi-nulle est considéré comme dégénéré. En effet, il arrive souvent que bon nombre de polygones soient décrits par des ensembles de points alignés ou confondus, résultant sur des faces à superficie négligeable ou nulle. La figure 44 illustre le genre de configurations typiques dans lequel des 2-cellules dégénérées s’imiscent parmi d’autres qui sont valides. La présence de FD dans le lot de polygones (cf. figure 44) fausse les liens topologiques entre les faces et constitue un obstacle à la méthode de reconstruction des liens β2 que nous pouvons déduire entre les 2-cellules (cf. section 3.4.1). Un test de contact entre FA et FB peut ainsi s’avérer négatif du fait de la 1-cellule) Quatres faces FA, FB, FC et FD partageant des arêtes. (b) Cacher FC fait apparaitre une partie de FD. (c) En cachant toutes les faces, il apparait que FD est un polygone dégénéré avec des 0-cellules quasi alignées p1, p2 et p3. De ce fait, les 2-cellules dégénérées doivent être supprimées de la 3-carte afin de favoriser une interprétation correcte des liens topologiques. Leur détection peut se faire soit par le calcul de leur vecteur normal dont la norme sera logiquement nulle ou par le calcul de leur aire qui sera également nulle. Sachant que les 2-cellules présentes dans C peuvent être des polygones irréguliers, nous discutons dans le paragraphe suivant de l’approche que nous avons adopté pour un calcul robuste de la normale ainsi que de l’aire d’une face quelconque. normale et aire d’une 2-cellule La méthode classique pour déterminer le vecteur normal d’une 2-cellule consiste à récupérer trois de ses 0-cellules non alignées et de déterminer le produit vectoriel des deux vecteurs formés par ces 0-cellules. Par exemple, considérons le polygone de la figure 45a, les points p1, p2 et p4 n’étant pas alignés, nous pouvons considérer les vecteurs −→V 1,2 et −→V 1,4 et en déduire la formule suivante : −→N = −→V 1,2 ∧ −→V 1,4 (2) Cependant, cette manière de déterminer la normale est limitée dans la mesure où, en plus de nécessiter une vérification de l’alignement des points choisis pour le calcul, la 2-cellule doit être convexe et parfaitement planaire pour garantir un résultat robuste. Dans nos travaux il arrive fréquemment d’avoir affaire à des faces concaves ou comportant des points alignés et rien ne garanti leur planarité au chargement des données d’entrée. Par exemple, dans le polygone de la 60 reconstruction topologique de bâtiments 3d p1 p4 p3 p2 (a) p1 N p2 p3 p4  (b) Figure 45 – (a) Calcul du vecteur normal sur un polygone simple. (b) Vecteur normal →− N obtenu par le produit vectoriel des vecteurs →− V 1,2 et →− V 1,4. figure 46 qui est concave en p5, appliquer l’equation 2 aux trois points p4, p5 et p6 en considérant p5 comme le point central donnerait un vecteur normal de direction opposée à celui obtenu en utilisant les points p5, p6 et p7. Et pour le trio de points alignés p1, p2 et p3, nous obtiendrions une normale nulle. p1 p2 p3 p4 p5 p6 p8 p7 Figure 46 – Exemple de polygone concave pour lequel l’usage du produit vectoriel pour déterminer robustement la normale nécessiterait plusieurs vérifications. Pour pallier à ces problèmes, nous utilisons une méthode bien plus robuste numériquement, connue sous le nom de méthode de Newell [107]. Cette méthode, en plus de pouvoir gérer la concavité, et la colinéarité des points d’une même face, traite aussi les polygones pas tout à fait planaires, produisant la meilleure approximation possible le cas échéant [139]. Soit →− N = (nx, ny, nz) la normale de Newell d’une 2-cellule formée par une séquence de 0-cellules p1, …, pn, avec pi = (xi, yi, zi) ∈ R3 et pn+1 = p1. Les composantes de →− N sont calculées de la manière suivante : nx = 2Ayz = n i=1 (yi − yi+1)(zi + zi+1) ny = 2Azx = n i=1 (zi − zi+1)(xi + xi+1) nz = 2Axy = n i=1 (xi − xi+1)(yi + yi+1) (3)  avec Ayz, Azx et Axy les aires respectives des projections de la 2-cellule sur les plans Cartésiens yz, zx et xy. Il est prouvé que ces aires sont proportionnelles aux coefficients du vecteur normal de la face en question [140]. La méthode de Newell définie ainsi chaque composante de →− N comme la somme des aires signées des surfaces formées par chaque segment du polygone et un point extérieur, projetées sur un des plans Cartésiens. Par ailleurs, grâce à sa définition, cette approche permet en plus d’obtenir directement l’aire de la 2-cellule concernée. En effet, comme démontré dans [138], la valeur de la surface d’un polygone donné correspond à la moitié de la norme de son vecteur normal de Newell obtenu avec l’équation 3. Soit F une 2-cellule dont le vecteur normal de Newell équivaut à −→NF = (nx, ny, nz). L’aire de F est obtenue de la manière suivante : AF = 1 2 ||→− N|| = 1 2  n2 x + n2 y + n2 z (4) Ainsi, toute 2-cellule F ∈ C, telle que AF  0 est supprimée de l’EBM-LCC. Puisque chaque face est, pour le moment, isolée des autres, cette suppression se réalise simplement en retirant de B tous les brins de la 2-cellule identifiée comme dégénérée. 

Correction des 2-cellules non simples

Un polygone simple est un polygone dont chaque arête est formée par deux points distincts et aucune arête n’en croise une autre tout au long de la séquence d’arête qui délimite sa surface. La frontière d’un tel polygone est donc formée par une ligne polygonale fermée du plan [162]. À contrario, une 2-cellule non simple, que nous appelons ici 2-cellule complexe, possède une frontière mal définie. Ce type de faces pose problème sur bon nombre d’opérations géométriques, particulièrement quand il est nécessaire de distinguer l’intérieur du polygone de son extérieur. Nous avons pu recenser deux types de polygones complexes qui interviennent plus ou moins régulièrement dans les données récupérées en entrée de nos modèles de bâtiments : — les polygones ayant des doublons dans leur séquence de 0-cellules ; — les polygones possédant des extensions géométriques insignifiantes par rapport à leur surface globale. Une solution triviale à une partie de ces problèmes de 2-cellules complexes serait la triangulation de toutes les faces de plus de trois sommets. Mais le revers d’une telle approche serait une augmentation importante du nombre de 2-cellules qui augmenterait le temps de calcul consacré à la méthode de recons- 62 reconstruction topologique de bâtiments 3d truction topologique (cf. section 3.4). Nous présentons ici les solutions adoptées pour faire face aux problèmes précédemment cités. Doublons et mauvaises séquences des 0-cellules Certaines 2-cellules présentent des problèmes dans la séquence de leur sommets. Ce sont les cas les moins problématiques, se manifestant par plusieurs 0-cellules ayant des 0-attributs égaux dans la même séquence d’une 2-cellule. Un ensemble de situations possibles est illustré à travers les figures 47 et 48. p1 p2 p3 p4 p5 p6 (a) p1 p2 p3 p6 p7 p5 p4 (b) p1 p2 p3 p4 p6 (c) p1 p2 p3 p7 p4 (d) Figure 47 – (a) Les 0-cellules p4 et p5 sont confondues formant ainsi une 1-cellule invalide. (b) p4 et p6 sont confondues et les 1-cellules [p4p5] et [p5p6] s’intersectent. (c) Correction de (a) par la suppression de p5. (c) Correction de (b) par la suppression de p5 et p6. Pour corriger ces problèmes et obtenir des frontières simples sur les 2-cellules, la solution adoptée consiste à conserver la première 0-cellule considérée comme l’originale puis à supprimer celles qui constituent les doublons et qui complexifient les séquences. Cependant, afin de garantir une modification géométrique lègère des 2-cellules, les doublons ne sont supprimés que s’ils sont séparés de l’original par au plus une 0-cellule différente dans la séquence. Soit la 2-cellule F = (BF, β1) ∈ C contenant k 0-cellules et k brins distincts tel que BF = (b1, b2, …, bk) ⊂ B et définie par la séquence de sommets SF = {p1, p2, …, pk} avec bk+1 = bk et pk+1 = pk. Pour toute paire de brins {bi, bi+1} ∈ BF, si 0- attr(bi) = 0-attr(bi+1) = 0-attr(bi+2), alors seul bi+1 est supprimé et pi+1 retiré de SF (cf. figure 47c). Par ailleurs si 0-attr(bi) = 0-attr(bi+2) alors bi+1 et bi+2 sont supprimés de BF. Les points pi+1 et pi+2 correspondants sont aussi retirés 3.3 prétraitements 63 de la séquence SF (cf. figure 47d). En limitant ainsi la suppression des doublons à deux brins au delà du brin de la 0-cellule originale, les modifications géométriques engendrées sont invisibles dans le cas où l’original et le doublon se suivent dans la séquence, comme illustrée par la figure 47a. En supprimant le brin b5 correspondant à p5, la frontière de la face est débarrassée de la 1-cellule de longueur nulle formée par p4 et p5 (cf. figure 47c). Dans le cas où il y a un brin qui sépare l’original et le doublon, la configuration qui se présente constitue un « aller-retour » résultant sur deux 1-cellules confondues, à l’image des segments [p4p5] et [p5p6] de la face de la figure 47b. En supprimant b5 et b6, la surface intérieure est débarrassée de ces segments n’apportant pas d’information utile (cf. figure 47d). p1 p2 p3 p4 p5 p6 (a) p1 p2 p3 p4 p6 (b) p1 p2 p3 p4 p5 p6 (c) p1 p2 p3 p4 p5 p6 p7 p8 (d) p1 p2 p3 p6 p5 p4 p8 (e) Figure 48 – (a) La 2-cellule est quasiment coupée en deux du fait que les points de p2 et p5 soient égaux. (b) Résultat après la suppression de p5. (c) Autre correction possible impliquant de séparer la faces en deux. (d) Cas d’une face décrivant un trou fermé en un même point à la frontière (p4 et p7). (e) Résultat de la correction par suppression de p7. Par contre, lorsqu’il y a plus d’un brin entre la 0-cellule originale et un de ses doublons, la correction par la suppression résulte très souvent sur des modifications géométriques importantes. La figure 48 montre quelques exemples permettant d’exposer les différences engendrées par l’opération. Il s’avère même dans certains cas que d’autres solutions semblent plus adéquates que la suppression, comme c’est le cas pour la face de la figure 48a.