<figure><img src="image_1.png" /></figure>

HAL
open science

# Structuration topologique pour le rendu et la visualisation 3D

Sébastien Horna

► To cite this version:

Sébastien Horna. Structuration topologique pour le rendu et la visualisation 3D. Informatique [cs]. université de Poitiers, 2022. tel-04037427

HAL Id: tel-04037427

https://hal.science/tel-04037427

Submitted on 20 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
UNIVERSITÉ DE POITIERS

ÉCOLE DOCTORALE SISMI

SCIENCES ET INGENIERIE DES SYSTEMES, MATHEMATIQUES, INFORMATIQUE

Secteur de recherche : Informatique Graphique

HABILITATION
À DIRIGER DES RECHERCHES

Présentée à L'Université de Poitiers par

Sébastien Horna

Structuration topologique pour le rendu et la
visualisation 3D.

Préparée à l'institut XLIM, UMR CNRS 7252

Soutenue le 22 septembre 2022 devant la Commission d'Examen

Jury :

Rapporteurs :

<table><tr><td>Jean Luc Mari - Professeur</td><td>Université d'Aix Marseille, LIS</td></tr><tr><td>Céline Loscos -Professeur</td><td>Université de Reims, CRESTIC</td></tr><tr><td>Christophe Renaud - Professeur</td><td>Université du Littoral, LISIC</td></tr></table>

Examinateurs :

<table><tr><td>Guillaume Damiand - Directeur de Recherche, CNRS</td><td>Université de Lyon, LIRIS</td></tr><tr><td>Philippe Meseure - Professeur</td><td>Université de Poitiers, XLIM</td></tr><tr><td>Daniel Meneveaux - Professeur</td><td>Université de Poitiers, XLIM</td></tr></table>
<figure><img src="image_2.png" /></figure>
... lointaine, très lointaine...
<figure><img src="image_3.png" /></figure>
REMERCIEMENTS

Nous y voilà... L'exercice aussi plaisant que périlleux d'écrire la page des remerciements. Sans aucun doute les lignes de ce mémoire qui seront les plus lues. Je me revois une quinzaine d'années en arrière, rédigeant les remerciements de mon mémoire de thèse et plaisantant avec mes compagnons doctorants sur une hypothétique *Habilitation à Diriger des Recherches*. Sans aucune prétention, je peux dire que depuis longtemps je réfléchis à ce que je pourrai écrire, à comment tourner les choses, à comment trouver les bons mots pour exprimer toute la gratitude que j'ai envers toutes les personnes qui m'ont accompagné jusqu'à aujourd'hui. Nous y voilà...

Je remercie l'ensemble des membres de mon jury. J'éprouve un profond respect pour leur travail et leur parcours. Je les ai choisis pour leur qualité scientifique, leur connaissance au plus proche de mes travaux de recherche, mais aussi et surtout pour leur qualité humaine. Les différents échanges que nous avons pu avoir tout au long de la préparation de cette habilitation m'ont conforté dans ce choix. J'ai vraiment ressenti une grande bienveillance et un soutien à chacune des étapes. C'est sans aucun doute l'une des particularités de la préparation de l'HDR, on se retrouve seul aux manettes administratives et organisationnelles. La réactivité et les petits mots gentils m'ont apporté beaucoup de réconfort dans ce timing de rédaction plutôt serré.

Le travail présenté lors d'une HDR n'est pas un travail individuel. C'est pour moi primordial de le souligner. Et je souhaite remercier toutes les personnes qui m'ont accompagné de près ou de loin dans mes différents projets scientifiques et pédagogiques. Les membres d'XLim Poitiers et plus particulièrement de l'équipe IG, mes collègues de la faculté de droit, l'ensemble des personnes que j'ai pu rencontrer au fil de ces années. Elles sont nombreuses et une grande difficulté tient dans le fait de n'oublier personne. C'est pourquoi je remercie par avance ceux dont le nom n'apparaît pas dans ces pages et qui m'ont aidé d'une manière ou d'une autre. Ils se reconnaîtront.

En premier lieu, un grand merci aux 5 doctorants que j'ai la chance d'encadrer (ou d'avoir encadré) : Maxime, Simon, Elsa, Sylvain et Hayssam. J'imagine qu'ils ont retrouvé les traces de leur travail à travers mon manuscrit et ma présentation. C'est une démonstration flagrante qu'ils sont les éléments moteurs de la recherche. J'ai pour ma part toujours éprouvé un immense plaisir à les suivre au jour le jour (un peu trop tous les jours peut-être), à les voir grandir et à les voir prendre certaines de mes bonnes ou mauvaises habitudes. "Toujours par deux, ils vont", cette relation encadrant / doctorant est très particulière, j'y accorde une grande importance, c'est une grande responsabilité. Finalement, c'est sans doute la seule activité de notre métier où nous sommes à la fois enseignant et chercheur.
Au fil des ans, on gagne en expérience, on apprend à se connaître. Pour ma part, je sais maintenant que j'ai besoin d'être entouré d'une équipe. J'accorde volontiers ma confiance à toutes les personnes avec qui je travaille. Ainsi, les barrières s'amenuisent, les relations professionnelles se transforment en liens d'amitié, et mon bureau devient officiellement la cafétéria du 3e étage... The place to be... Rita, Arthur, Hakim, Daniel, Philippe, Bruno, bien sur Mickaël, et tous les autres qui passent la porte pour boire un café, pour papoter, et même parfois pour bosser, surtout, faites que ça ne change pas !!! Mais je tiens également à tous vous remercier pour la confiance que vous m'avez donnée petit à petit. C'est sans aucun doute votre regard, votre reconnaissance, qui m'a m'y sur les rails de la rédaction de cette habilitation.

Et puis un grand merci à toute ma famille, mes parents, ma soeur Cyrielle, Thomas, et Lulu. Même si je me suis lancé dans ce travail d'HDR un peu en catimini, il était bien difficile de cacher ma joie et ma fierté de vous annoncer que c'était fait et que je vous attendais tous pour ma soutenance. Les moments que l'on passe tous ensemble sont sans aucun doute trop rares, cela les rend encore plus précieux. Il était pour moi inconcevable de passer cette étape sans vous avoir à mes côtés.

Enfin, comment trouver les mots... Que dire sur mes 3 princesses, mes 3 petits cœurs, mes 3 formules 1... Si mon boulot me donne l'impression d'avoir une vie à 100 à l'heure, alors à la maison on dépasse les 200. Nous formons une dream team prête à conquérir le monde. Ma petite Maëline, qui respire la joie de vivre à chaque seconde, pleine de fraîcheur, pleine de malice, tu me fais vivre un véritable feu d'artifice jour après jour. Ma grande Matilde, 10 ans déjà que tu as fait de moi un papa, j'ai à peine le temps de te voir grandir que tu passes aujourd'hui les portes du collège, ta petite vie est déjà tellement remplie et pourtant ta soif de tout connaître ne cesse de me surprendre. Et ma chérie, ma Magali, ma copilote depuis maintenant 26 ans... Tout un symbole pour nous. Il y a 26 ans, on se demandait où l'on serait en 2022, on en rigolait parce que c'était loin, c'était un autre monde. Certes, depuis le monde a beaucoup changé, mais nous, nous sommes restés ensemble. Une magnifique aventure qui a dépassé nos espérances les plus folles. Tu as toujours cru en moi, tu m'as toujours soutenu, tout est grâce à toi.

Merci,

Les choses, on les fait ou on ne les fait pas...
<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>
# SOMMAIRE

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Travaux réalisés</td><td>5</td></tr><tr><td>1.2</td><td>Collaborations et encadrements</td><td>7</td></tr><tr><td>1.3</td><td>Responsabilités</td><td>8</td></tr><tr><td>1.4</td><td>Structure du document</td><td>8</td></tr><tr><td>2</td><td>Contexte et positionnement</td><td>9</td></tr><tr><td>2.1</td><td>Gestion de scènes 3D en rendu réaliste par lancé de rayons</td><td>10</td></tr><tr><td>2.1.1</td><td>Structures accélératrices classiques</td><td>12</td></tr><tr><td>2.1.2</td><td>Partitionnement Spatial Contraint CSP</td><td>13</td></tr><tr><td>2.1.3</td><td>Gestion de détails fins, les arrondis</td><td>16</td></tr><tr><td>2.2</td><td>Modélisation à base topologique</td><td>17</td></tr><tr><td>2.2.1</td><td>Modèles topologiques usuels</td><td>18</td></tr><tr><td>2.2.2</td><td>Cartes généralisées concept et notations</td><td>21</td></tr><tr><td>2.3</td><td>Reconstruction de modèles 3D à partir de données</td><td>25</td></tr><tr><td>2.3.1</td><td>Reconstruction de maillages</td><td>25</td></tr><tr><td>2.3.2</td><td>Reconstruction à partir de donnée médicales</td><td>26</td></tr><tr><td>2.4</td><td>Positionnement des travaux</td><td>28</td></tr><tr><td>2.4.1</td><td>Structure topologique pour la simulation d'éclairage</td><td>28</td></tr><tr><td>2.4.2</td><td>Reconstruction topologique : application en imagerie médicale</td><td>30</td></tr><tr><td>3</td><td>Partition topologique contrainte pour le lancé de rayons</td><td>31</td></tr><tr><td>3.1</td><td>Modèle topologique dédié aux bâtiments : CCSP</td><td>32</td></tr><tr><td>3.1.1</td><td>Construction des volumes convexes</td><td>34</td></tr><tr><td>3.1.2</td><td>Correspondance de GMapArchi à une CCSP</td><td>34</td></tr><tr><td>3.2</td><td>Utilisation de la CCSP pour le rendu réaliste</td><td>35</td></tr><tr><td>3.2.1</td><td>Traversée de la CCSP</td><td>35</td></tr><tr><td>3.2.2</td><td>Utilisation étendue de la structure CCSP</td><td>39</td></tr><tr><td>3.2.3</td><td>Gestion du mobilier</td><td>40</td></tr><tr><td>3.3</td><td>Résultats et discussion</td><td>41</td></tr><tr><td>3.3.1</td><td>Système d'évaluation des performances</td><td>41</td></tr><tr><td>3.3.2</td><td>Etude de la complexité du calcul des rayons</td><td>43</td></tr><tr><td>3.3.3</td><td>Analyse comparative des méthodes</td><td>44</td></tr><tr><td>3.3.4</td><td>Bilan</td><td>45</td></tr><tr><td>3.4</td><td>Visualisation topologique : généralisation</td><td>45</td></tr><tr><td>3.4.1</td><td>Construction de la CDT</td><td>46</td></tr><tr><td>3.4.2</td><td>Traversée de la CDT</td><td>46</td></tr><tr><td>3.4.3</td><td>Résultats</td><td>48</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>3.4.4 Bilan</td>
      <td>50</td>
    </tr>
    <tr>
      <td>3.5 Conclusion</td>
      <td>50</td>
    </tr>
    <tr>
      <td><strong>4 Visualisation d'arrondis réalistes</strong></td>
      <td><strong>53</strong></td>
    </tr>
    <tr>
      <td>4.1 Construction de la structure accélératrice SREC-RT</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.1.1 Positionnement des surfaces arrondies</td>
      <td>56</td>
    </tr>
    <tr>
      <td>4.1.2 Structure de détection</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.1.3 Structure Topologique</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.2 Utilisation de SREC-RT en lancé de rayons</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.2.1 Processus détaillé</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.2.2 Utilisation de la structure topologique de détection</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.2.3 Cas particulier : sommets concaves</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.3 Représentation des arrondis</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.3.1 Representation et intersection des arêtes arrondies</td>
      <td>62</td>
    </tr>
    <tr>
      <td>4.3.2 Representation et intersection des sommets arrondis</td>
      <td>62</td>
    </tr>
    <tr>
      <td>4.4 Résultats</td>
      <td>64</td>
    </tr>
    <tr>
      <td>4.4.1 Temps de rendu et impact mémoire</td>
      <td>64</td>
    </tr>
    <tr>
      <td>4.4.2 Comparaison visuelle des arrondis</td>
      <td>66</td>
    </tr>
    <tr>
      <td>4.4.3 Interpolation des normales</td>
      <td>67</td>
    </tr>
    <tr>
      <td>4.5 Conclusion</td>
      <td>68</td>
    </tr>
    <tr>
      <td><strong>5 Reconstruction topologique d'imagerie médicale</strong></td>
      <td><strong>71</strong></td>
    </tr>
    <tr>
      <td>5.1 Correction et reconstruction topologique</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.1.1 Processus de reconstruction topologique</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.1.2 Corafinement 3D</td>
      <td>75</td>
    </tr>
    <tr>
      <td>5.1.3 Résultats et discussion</td>
      <td>76</td>
    </tr>
    <tr>
      <td>5.2 Reconstruction 3D de données médicales à multi label sémantiques</td>
      <td>78</td>
    </tr>
    <tr>
      <td>5.2.1 Méthodes de reconstruction étudiées</td>
      <td>79</td>
    </tr>
    <tr>
      <td>5.2.2 Etude comparative</td>
      <td>80</td>
    </tr>
    <tr>
      <td>5.2.3 Bilan</td>
      <td>82</td>
    </tr>
    <tr>
      <td>5.2.4 Modèle topologique pour le médical</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.2.5 Mise en oeuvre détaillée</td>
      <td>84</td>
    </tr>
    <tr>
      <td>5.3 Résultats et comparaisons</td>
      <td>91</td>
    </tr>
    <tr>
      <td>5.3.1 Statistiques et performances</td>
      <td>92</td>
    </tr>
    <tr>
      <td>5.3.2 Comparaison avec des méthodes de reconstruction classiques</td>
      <td>93</td>
    </tr>
    <tr>
      <td>5.3.3 Comparison avec FreeSurfer</td>
      <td>95</td>
    </tr>
    <tr>
      <td>5.4 Conclusion</td>
      <td>96</td>
    </tr>
    <tr>
      <td><strong>6 Conclusion</strong></td>
      <td><strong>99</strong></td>
    </tr>
    <tr>
      <td><strong>Annexes</strong></td>
      <td><strong>103</strong></td>
    </tr>
    <tr>
      <td><strong>A Collaborations et encadrements</strong></td>
      <td><strong>103</strong></td>
    </tr>
    <tr>
      <td><strong>B Publications Personnelles</strong></td>
      <td><strong>107</strong></td>
    </tr>
    <tr>
      <td><strong>C Responsabilités</strong></td>
      <td><strong>111</strong></td>
    </tr>
    <tr>
      <td><strong>Bibliographie</strong></td>
      <td><strong>115</strong></td>
    </tr>
  </tbody>
</table>
INTRODUCTION

Les applications de simulation numérique sont devenues incontournables dans de nombreux secteurs industriels : mécanique des solides, aérodynamique, écoulement de fluides, éclairement, etc. L'ensemble de ces applications nécessite de developer des modèles physiques et des processus de calculs lourds et coûteux en temps de calculs et en utilisation mémoire. Par exemple, dans l'étude des sous-sols géologiques, des méthodes de simulation d'écoulement sont utilisées pour détecter les réservoirs d'hydrocarbures (cf. figure 1.1.a). Dans le domaine de la synthèse d'image photoréaliste qui nous intéresse plus particulièrement, les calculs de simulation d'éclairage nécessitent une expression rigoureuse des phénomènes physiques (cf. figure 1.1.b). L'objectif est de calculer les échanges lumineux entre les surfaces d'un environnement en fonction du positionnement des objets, des types de sources lumineuses, des matériaux qui composent les surfaces. Ces travaux permettent la visualisation d'environnements virtuels utilisés dans de nombreux secteurs comme par exemple des études de conception (positionnement des éclairages dans un bâtiment, visualisation de carrosserie, etc.), le divertissement (films d'animation, jeux vidéo), la reconstitution de patrimoine (musées virtuels, études historiques) ou toute autre application de réalité virtuelle nécessitant la génération d'images photoréalistes.

Quel que soit le domaine d'application, avant de procéder aux processus de simulation, l'environnement virtuel doit être modélisé (cf. figure 1.2). La modélisation géométrique correspond à l'ensemble des outils mathématiques, numériques et informatiques qui permettent de construire la forme des objets virtuels. La géométrie est inévitablement fournie pour décrire la forme des objets. Elle est plus ou moins complexe, plus ou moins contrainte, et contient des informations spécifiques utilisées dans un second temps lors des algorithmes de simulation. Le processus de construction géométrique consiste à réaliser la construction et l'assemblage de formes élémentaires pour créer des objets de plus en plus complexes. Il peut également nécessiter de reconstruire des objets à partir de données existantes (modélisation architecturale à partir de plan, visualisation à partir d'imagerie médicale, photogrammétrie, etc.). Finalement, les traitements numériques et graphiques effectués sur des objets modélisés numériquement découlent du modèle de représentation choisi. Les résultats obtenus et la complexité des algorithmes tant en modélisation qu'en simulation sont grandement influencés par le choix de cette structure de données.
<figure><img src="image_6.png" /><figcaption>Figure 1.1 – Applications de simulation : (a) la suite logicielle GOCAD Mining Suite [1] est une planteforme pour la modélisation 3D qui intègre des données géologiques, géophysiques, géochimiques, structurales et géotechniques; (b) la simulation d'éclairage par lancé de rayon permet de produire des images au plus proche de la réalité. Ici une image générée avec le logiciel LuxRender, inspiré du moteur de rendu open source pbrt [127]</figcaption></figure>

Les *modeleurs géométriques* disposent de leur propre structure de données. Les modèles de description géométrique peuvent être de différentes natures en fonction des applications : un ensemble de triangles dépourvu de relation explicite (on parle de soupe de triangles), une liste de polygones, convexes ou non, liés afin de produire des surfaces, un maillage volumique structuré et agrémenté de relations de voisinage.

Pour mieux appréhender la structure de l'environnement, certains modeleurs disposent d'informations de voisinage entre les éléments, des informations dites "topologiques". Elles permettent de représenter des objets subdivisés, c'est-à-dire partitionnés en cellules de différentes dimensions (sommets, arêtes, faces, volumes). Cette structuration est primordiale pour de nombreux domaines d'application car elle fournit des informations qui permettent de manipuler efficacement les maillages. L'utilisation de ce type de représentation est appelée modélisation géométrique à base topologique. Elle permet la manipulation d'objets subdivisés, le contrôle de l'environnement produit (interpénétration d'objets, cohérence des voisinages), l'application d'opérations locales (intersections, opérations booléennes, chanfreinage, etc.), l'ajout d'informations sémantiques locales rattachées aux cellules. Par exemple, en géoscience, il est important de représenter les couches géologiques qui composent le sous-sol. Ces couches sont fracturées et composées de différents blocs correspondants géométriquement aux volumes, liés par leurs faces de contact. En architecture, pour des études de simulation thermique, acoustique, d'éclairage, il est important de représenter les différents volumes (pièces, murs, portes, etc.), de connaître les ouvertures ouvrant sur une pièce. Les cellules qui composent l'objet sont donc représentées, mais également leurs relations d'incidence et d'adjacence.

La géométrie seule n'est pas suffisante pour représenter un environnement virtuel. Divers attributs lui sont associés pour définir des propriétés sur les éléments géométriques. Dans le contexte du rendu, ces attributs peuvent par exemple correspondre aux données photométriques associées aux surfaces : couleur, texture, matériaux, réflectance, luminance, etc. Plus généralement, des informations sémantiques sont utilisées pour caractériser les objets et fournir des données utilisées dans des applications de simulation : composition d'un sous-sol géologique, concentration physiologique dans le médical, matériaux de construction utilisés dans un bâtiment.
Finalement, l'environnement 3D est produit à partir d'un processus qui reconstruit les informations à partir de données externes et/ou d'un ensemble d'opérations de construction et d'édition (cf. figure 1.3.a).

Parmi la multitude de contextes d'utilisation des environnements 3D, la génération d'images pho-
toréalistes par simulation d'éclairage est un domaine de recherche à part entière, très exigeant quand
au temps de traitement et à la qualité du résultat. L'objectif est de simuler le transport de la lumière
dans des environnements aux interactions complexes entre lumière et matière (transparence, translucidité, brillance, anisotropie, surfaces multicouches, etc.). Au cours des premières années de l'infographie,
dans les années 1970, les problèmes scientifiques concernaient des questions fondamentales comme les
algorithmes de visibilité et les représentations géométriques. Les ressources matérielles étaient particulièrement limitées et les ordinateurs capables d'effectuer un million d'opérations en virgule flottante par seconde coûtaient des centaines de milliers de dollars. Tout calcul de simulation précis de la physique pour le rendu était alors impossible.

<figure><img src="image_7.png" /><figcaption>Figure 1.2 – Dans le contexte du rendu réaliste, les environnements 3D sont modélisés dans un premier temps à l'aide d'un logiciel de modélisation (un modeleur) qui permet de définir la forme géométrique des objets et l'ensemble de leur attributs (matériaux, propriétés physiques, etc.) Dans un second temps, un processus de rendu est utilisé pour générer l'image de synthèse.</figcaption></figure>

L'étude des approches de rendu basées sur la physique a débuté dans les années 1980 avec l'introduc-
tion du lancé de rayons par Whitted [167]. Parallèlement, les premiers modèles de réflexion microfacette
ont été introduits pour améliorer l'apparence des matériaux métalliques [35]. Les premières méthodes de
simulation d'éclairage ont été proposées dans les années 1980 pour les effets d'éclairement indirect avec
la méthode de radiosité de Goral et al. en établissant le lien entre les transferts d'énergie et le rendu [63].
Mais bien que fortement basée sur les unités physiques et la conservation de l'énergie, la radiosité ne
conduit pas à des algorithmes de rendu viables. La complexité asymptotique des calculs, ou la nécessité
de tesseliser les modèles géométriques pour obtenir de bons résultats ont démontré que la radiosité est
limitée dans la pratique. En parallèle, les études concernant les approches physiques du rendu basées
sur le lancé de rayons et l'intégration de Monte-Carlo ont été poursuivies. Dans un premier temps, ces
méthodes produisaient des images contenant du bruit dû à la variance de l'intégration Monte-Carlo, donc
de moindres qualités que les méthodes de radiosité. En 1986, Kajiya a établi une formulation rigoureuse
du problème de rendu (l'équation intégrale du transport de la lumière) et a montré comment appliquer
l'intégration de Monte-Carlo pour résoudre le calcul [89].
À partir des années 2000, les processeurs étant de plus en plus performants et les capacités mémoire augmentant, de nombreux articles ont présenté des algorithmes de simulation d'éclairage de plus en plus efficaces basés sur des propriétés physiques [160, 163]. Avec la résolution de ces verrous scientifiques et l'évolution technologique, il est devenu possible d'envisager des approches de plus en plus précises et efficaces, mais exigeantes en temps de calcul. L'objectif du rendu photoréaliste est de créer une image d'une scène 3D très complexe (plusieurs millions de faces) qui soit indiscernable<fnref n="1" /> d'une photographie. Pour cela, le parcours de la lumière est simulé par le lancé de plusieurs milliards de rayons au travers de la scène. Pour répondre à cette problématique, une partie des recherches concerne le développement de structures accélératrices qui représentent l'environnement dans une organisation spatiale dédiée aux méthodes de simulation d'éclairage. Ces modèles de représentation ont ensuite été pensés et adaptés aux contraintes techniques des processeurs de cartes graphiques (GPU) et en exploitant uniquement les données géométriques de l'environnement.

<figure><img src="image_8.png" /><figcaption>Figure 1.3 – Processus de création d'images de synthèse : (a) l'environnement est créé avec un modeleur qui dispose d'une structure de données contenant des informations géométriques, topologiques et sémantiques. La scène 3D est créée par des opérations de construction et d'édition ; (b) le moteur de simulation construit une structure de données à partir de la géométrie fournie par le modeleur, une structure accélératrice dédiée est produite pour réduire les temps de traitement.</figcaption></figure>

La structure de données utilisée par le moteur de rendu est généralement construite uniquement à partir des informations géométriques des objets (cf. figure 1.3.b). Les informations sémantiques telles que les données photométriques sont conservées, mais non utilisées dans la construction de la structure

<footnote n="1">1. Notons que le terme "indiscernable" est imprécis car il implique un observateur humain, et différents observateurs peuvent percevoir la même image différemment.</footnote>
accélératrice. Ce procédé permet de s'abstraire du modèle de représentation utilisé lors de la phase de modélisation de l'environnement, rendant le processus de rendu indépendant des données d'entrée. La structure accélératrice produite est optimisée pour l'algorithme de simulation et peut être adaptée à la parallélisation sur GPU. Malheureusement le modèle de représentation utilisée au cours de l'étape de modélisation, aussi complet qu'il soit, est totalement édulcoré.

L'équipe de IG, spécialisée en informatique graphique au sein du laboratoire XLIM développe ses travaux de recherche dans le domaine de la synthèse d'images avec une partie importante concernant la modélisation géométrique, le rendu réaliste et la simulation d'éclairage. J'ai intégré cette équipe en décembre 2010 en tant que maître de conférence. Mon projet scientifique au sein de cette équipe est de mettre à contribution les structures topologiques et hiérarchiques pour améliorer les opérations de reconstruction 3D et optimiser les algorithmes de simulation d'éclairage par lancé de rayons. Au cours de ces années de recherche, j'ai participé à l'encadrement de 5 thèses de doctorat portant sur ces thématiques et j'ai contribué aux montages de plusieurs projets région et ANR. Je suis notamment le porteur du projet MEDIA-IRM 3D, un projet pluridisciplinaire impliquant des équipes de mathématiques, traitement d'images et informatique, des équipes du secteur biologie/santé et des médecins. La problématique centrale de ce projet réside dans la définition et l'utilisation d'un modèle de représentation globale et cohérente qui répond aux besoins de simulation statistique pour l'étude des données physiologiques cébrales.

### 1.1 Travaux réalisés

Le projet de recherche que je propose est en partie issu d'un modèle de représentation formel construit sur la base d'un ensemble de contraintes topologiques et sémantiques dédié à la modélisation de complexes architecturaux 3D. Nous avons proposé d'utiliser ce modèle pour une application de reconstruction de bâtiment en 3D à partir de plan 2D et nous avons démontré que cette même structure était directement utilisable pour les applications de simulation d'éclairage par lancé de rayons. Les travaux présentés dans ce document se placent dans la continuité de ces recherches. Nous souhaitons étudier l'apport des modèles de représentation utilisés lors de la phase de modélisation pour améliorer les algorithmes de simulation. Cette étude a permis de définir et d'utiliser des modèles géométriques et topologiques pour représenter et éditer des environnements complexes (scènes architecturales, espace géologique, objets complexes). L'objectif principal est de mettre directement à contribution ces informations topologiques et d'utiliser des structures hiérarchiques pour améliorer les opérations de modélisation et optimiser les méthodes de simulation en utilisant des structures de voisinage (cf. figure 1.4).

Les paragraphes suivants déclinent les principaux projets engagés ces dernières années dans l'utilisation des modèles à base topologique pour les processus de rendu réaliste et la modélisation géométrique à base topologique.

#### Processus de rendu et calculs d'éclairage

Les modèles topologiques étant plus riches que ceux habituellement employés dans les méthodes de simulation d'éclairage, nous avons étudié la mise à contribution des relations de voisinage souvent ignorées pour améliorer la rapidité des calculs en simulation d'éclairage. Nous avons proposé au cours de la thèse de Maxime Maria (2012-2016), une méthode permettant d'utiliser notre modèle topologique dédié à l'architecture comme structure accélératrice afin de calculer le parcours des rayons (correspondant aux photons) à travers une scène 3D. La méthode résultante nous a permis de développer une application de visualisation interactive de scènes d'intérieur de bâtiment composé de plusieurs centaines de millions de polygones.
<figure><img src="image_9.png" /><figcaption>Figure 1.4 – Notre objectif est de mettre à contribution les données topologiques pour améliorer les opérations de reconstruction 3D et optimiser les algorithmes de simulation d’éclairage par lancé de rayons.</figcaption></figure>

Nous avons ainsi mis en évidence que la répartition spatiale des primitives géométriques peut mettre en défaut certaines structures accélératrices usuelles (grandes faces occultantes, petits objets regroupés). Notre structure topologique et hiérarchique se trouvant plus efficace, nous avons étendu notre étude au rendu de détails fins présents dans les scènes complexes. L'objectif principal est d'aborder avec le plus d'exhaustivité possible l'ensemble des effets hautes fréquences produits par de petits objets dont la couverture sur l'image est inférieure à un pixel (par exemple des reflets lumineux sur le bord des objets). Ces effets sont difficiles à traiter de manière robuste et nous souhaitons mettre en évidence l'intérêt d'utiliser une structure hiérarchique et topologique dans ces contextes particuliers. Ce travail se place dans le cadre du projet Région SIMOREVA (2018) dont l'axe de recherche principal concerne la perception et le rendu réaliste de scènes virtuelles. Nos travaux sur le rendu de détails fins ont été réalisés en collaboration avec Pierre Poulin (Ligum de l'Université de Montréal), notamment avec le co-encadrement des thèses de Simon Courtin et Elsa Tamisier qui ont débuté respectivement en 2018 et 2019.

## Modélisation géométrique à base topologique

Pour mieux contrôler la production des scènes 3D, nous avons travaillé sur les méthodes de reconstruction d'environnement complexes 3D à partir de données numériques, et plus particulièrement dans les domaines de l'architecture et du médical. La reconstruction de bâtiments en 3D à partir de données vectorielles est le sujet principal de ma thèse de doctorat (2008). Par la suite, nous avons tout d'abord généralisé et étendu le processus proposé pour des problématiques de reconstruction et de visualisation de modèles 3D à partir des données médicales. Dans le cadre du projet région IMPROVED débuté en 2018, nous avons réalisé une première étude exploratoire pour comprendre et interpréter les données fournies par un procédé d'acquisition tel qu'une IRM. Nous avons ensuite approfondi ces travaux avec le projet région MEDIA-IRM 3D (MEDical Data Intelligent Analysis, Interpretation, Reconstruction and Manipulation in 3D - 2020) dont je suis porteur. Dans ce projet, l'objectif principal est de proposer une représentation formelle basée sur des contraintes géométriques, topologiques et sémantiques dédiées à la représentation d'un modèle médical 3D. Ce modèle doit être suffisamment riche pour : proposer une méthode de reconstruction automatique d'objets anatomiques 3D; réaliser des calculs statistiques de simulation de propagation de donnés métabolites (physiologiques); étudier la croissance de tumeurs cérébrales; visualiser les données multimodales. Dans le cadre de ce projet, la thèse de Sylvain Gerbaud traite de la reconstruction de modèles 3D topologiques à partir d'images, et de l'utilisation de ce modèle pour l'estimation des données métabolites au sein du cortex cérébral. La thèse de Hayssam Obeid qui vient de débuter traite de la visualisation multimodale des informations métabolites afin de proposer un outil d'analyse et de détection des tumeurs cérébrales.
### 1.2 Collaborations et encadrements

Depuis ma nomination en tant que maître de conférences à l'université de Poitiers, j'ai participé à l'encadrement des thèses et aux projets cités ci-dessous. Les travaux présentés dans ce manuscrit sont principalement associés aux projets [2 et 4] et aux encadrements [2, 3, 5 et 6]. Une liste plus complète des collaborations et encadrement est disponible en annexe A.

#### Collaborations Nationales et Internationales

[1] 2021 : Projet région ARTERIA
Partenaires : CHU de Poitiers, Siemens Healthineers, l'université de Poitiers.

[2] 2019 : Porteur du projet Région MEDIA IRM 3D
Partenaires : CHU de Poitiers et Limoges, Siemens Healthineers, les universités de Poitiers, Limoges et La Rochelle, ainsi que les partenaires internationaux de l'université de Balamand (Liban) et de Heriot Watt University (Ecosse).
Cotutelle de thèse : université de Balamand au Liban (Dr. Mohammad Khalil)

[3] 2018 : Projet région IMPROVED
Partenaires : CHU de Poitiers, les universités de Poitiers et La Rochelle.

[4] 2018 : Projet région SIMOREVA
Partenaires : universités de Poitiers (XLim), Montréal (LIGUM), l'INRIA, le L2PN de l'Institut d'Optique et le NTNU colorlab en Norvège
Cotutelle de thèse : université de Montréal, laboratoire LIGUM (Dr : Pierre Poulin)

#### Encadrements de thèse et post doctorat

[1] Hayssam Obeid (thèse débutée en 2021 en cotutelle avec l'université Libanaise).
Visualisation et interaction avec les informations anatomiques et métaboliques
Directeurs : P. Meseure et M. Khalil, encadrants : R. Zrour et S. Horna.

[2] Sylvain Gerbaud (thèse débutée en 2020).
Développement de nouvelles méthodes de reconstructions tissulaires basées sur le métabolisme sous-jacent exploré en spectroscopie par résonance magnétique multi-noyaux,
Directeur : P. Meseure, co-directeur : S. Horna (ACT<fnref n="2" />), encadrant : R. Zrour.

[3] Loubna Lecheleck (post doctorat de 18 mois 2020 - 2021).
Reconstruction de modèles 3D à partir de données médicales.
Encadrants : S. Horna et R. Zrour.

[4] Elsa Tamisier (thèse débutée en 2019 en cotutelle avec l'université de Montréal).
Représentations géométriques de détails fins pour la simulation d'éclairage
Directeurs : D. Meneveaux et P. Poulin, encadrants : M. Ribardière et S. Horna.

[5] Simon Courtin (thèse débutée en 2018 - soutenance prévue en septembre 2022).
Prise en compte des effets hautes fréquences en simulation d'éclairage,
Directeur : D. Meneveaux, co-directeur : S. Horna (ACT), encadrant : M. Ribardière.

[6] Maxime Maria (thèse soutenue en 2016).
Utilisation d'une partition spatiale contrainte et convexe pour la simulation basée rayons,
Directeur : L. Aveneau, co-directeur : S. Horna (ACT).

<footnote n="2">2. Attestation de Co-direction de Thèse</footnote>
## 1.3 Responsabilités

En parallèle de mes activités de recherche et d'enseignement, je me suis investi dans les différentes responsabilités collectives tant au sein de mon équipe de recherche (XLIM - ASALI), qu'au sein de ma composante de rattachement (la faculté de Droit). Sur le plan scientifique, j'ai participé à plusieurs projets et collaborations industriels. J'ai assuré pendant 8 ans la gestion financière de l'équipe IG du laboratoire XLim-ASALI. Je suis également très investi dans la gestion scientifique globale de XLim-ASALI en raison de ma position de représentant du corps MC au conseil de département SIC (de 2013 à 2016), puis membre du conseil scientifique de l'axe ASALI depuis 2019.

Sur le plan pédagogique, j'effectue des enseignements en Licence et Master au département d'informationique de la faculté de Droit et Sciences Sociales de l'université de Poitiers. Au fil des années, j'ai progressivement pris en charge la responsabilité complète des unités d'enseignements transverses (S2, S3 et S6 de licence Droit et AES). Les effectifs importants de ces formations (900 L1, 600 L2) impliquent une logistique conséquente. Depuis 2019, j'ai pris en charge le pilotage de la commission pédagogique de numérique de l'université de Poitiers. Cette commission a pour rôle d'organiser, harmoniser la mise en place et favoriser les échanges dans le cadre des enseignements transverses (numérique et recherche documentaire) pour toutes les composantes de l'université de Poitiers.

Une présentation détaillée de mes différentes responsabilités est donnée en annexe C.

## 1.4 Structure du document

Ce mémoire d'Habilitation à Diriger des Recherches se poursuit suivant le plan suivant. Le chapitre 2 présente une étude bibliographique des différentes structures de données utilisées pour les applications de rendu photoréaliste par lancé de rayon, ainsi que les différents modèles topologiques proposés dans la littérature pour la modélisation et la construction de scènes complexes. Le chapitre 3 détaille notre approach pour définir l'utilisation d'une partition de l'espace contrainte et convexe (CCSP) comme structure accélératrice pour une application de lancé de rayons interactif. Le chapitre 4 décrit l'utilisation d'une structure topologique et hiérarchique non invasive pour le rendu réaliste des bords arrondis. Le chapitre 5 traite des problématiques de reconstruction de modèles 3D de manière générale, puis plus précisément à partir de donnée IRM dans le but de réaliser des analyses de données pour détecter des tumeurs cérébrales. Enfin, le chapitre 6 établit le bilan général de mes travaux ainsi que mes objectifs scientifiques à moyen et long terme.
# CONTEXTE ET POSITIONNEMENT

## Sommaire

<table><tr><td>2.1</td><td>Gestion de scènes 3D en rendu réaliste par lancé de rayons</td><td>10</td></tr><tr><td>2.2</td><td>Modélisation à base topologique</td><td>17</td></tr><tr><td>2.3</td><td>Reconstruction de modèles 3D à partir de données</td><td>25</td></tr><tr><td>2.4</td><td>Positionnement des travaux</td><td>28</td></tr></table>

Les environnements virtuels sont produits à l'aide de logiciels de modélisation géométrique adaptés à la création des objets 3D : construction de formes élémentaires, opération d'assemblage pour créer des objets de plus en plus complexes, reconstruction à partir de données numériques. Pour représenter l'environnement, les structures de données comportent des informations géométriques, topologiques et sémantiques. La topologie consiste notamment à connaître les relations de voisinage entre les éléments de différentes dimensions (sommets, arêtes, faces, volumes), permettant ainsi de structurer les objets et proposer des opérations complexes (intersection, opérations booléennes, chanfreinage, etc.). Malheureusement, la richesse des informations disponibles durant l'étape de modélisation n'est que très rarement utilisée par les applications de simulation. Les structures de données sont souvent plus synthétiques, optimisées pour des algorithmes dédiés afin de réduire les temps de traitement et les besoins mémoires. Par exemple, en simulation d'éclairage, la propagation de la lumière est calculée par des méthodes dites "basées rayons" pour respecter fidèlement le système physique et produire ainsi des résultats au plus proche de la réalité. Dans ces applications, l'objectif est de calculer l'éclairement au travers d'une scène 3D virtuelle. Pour cela, le chemin de la lumière est assimilé à un ensemble de rayons traversant la scène jusqu'à atteindre un objet (souvent une face). Finalement, la structure de rendu est construite uniquement à partir des primitives géométriques.

La problématique scientifique abordée dans ce manuscrit traite de l'utilisation d'un même modèle de représentation pour des applications de modélisation et de rendu réaliste. Plus précisément, nous avons étudié comment les informations topologiques construites lors de la phase de modélisation peuvent être utilisées pour proposer des algorithmes de simulation. Dans ce chapitre, nous présentons les différents travaux existants pour identifier le contexte de cette thématique de recherche : les structures accélératrices dédiées aux algorithmes de lancé de rayons, les modèles géométriques à base topologique, la reconstruction de modèles 3D topologiques (en particulier dans le domaine médical).
Dans la suite de ce chapitre, nous étudions tout d'abord les différentes structurations de données pro-
posées dans le cadre de la simulation d'éclairage par lancé de rayons (cf. section 2.1). Nous distinguons
les structures classiques qui répartissent les primitives géométriques dans un partitionnement spatial.
Celles-ci sont utilisées depuis de nombreuses années et ont été largement étudiées. Nous présentons des
structures qui visent à utiliser certaines informations structurelles de l'environnement, les partitions spa-
tiales contraintes, où l'espace est subdivisé en incluant les primitives géométriques du modèle. Nous
discutons également de l'impact de la répartition spatiale des données qui peut mettre en défaut certaines
structures, par exemple pour la gestion des détails fins comme les arrondis aux bords des objets.

Nous présentons ensuite dans la section 2.2 différents modèles existants dits "topologiques" utilisés en modélisation géométrique, dont le principe est de subdiviser l'espace en cellules de différentes dimensions : sommets, arêtes, faces, volumes, etc. Notre objectif étant d'utiliser un modèle pertinent dans le cadre de la représentation d'objets réels en 3D, nous expliquons notre choix d'utiliser le modèle de représentation des cartes généralisées. Ce modèle étant fortement mis à contribution dans les travaux présentés dans ce manuscrit, nous présentons les notions et définitions nécessaires à la compréhension des termes.

Pour étudier les différents processus de reconstruction de modèles 3D à partir de données numérisées,
nous présentons dans la section 2.3.2 les différentes méthodes de reconstruction de modèles 3D et plus
particulièrement dans le contexte du domaine médical. Dans ce secteur, les technologies d'imagerie telles
que la tomographie par ordinateur (CT) et l'imagerie par résonance magnétique (IRM) se sont répandues
et sont désormais couramment utilisées en médecine pour visualiser les organes internes. Habituellement,
les praticiens basent essentiellement leur analyse sur des visualisations 2D, qui correspondent à
des coupes des organes. Les applications de reconstruction 3D à partir d'acquisitions médicales se sont
développées, car elles fournissent une représentation plus globale et permettent d'effectuer des analyses
supplémentaires de l'activité fonctionnelle anatomique.

Enfin, la section 2.4 décrit et motive les projets que j'ai développés dans ce manuscrit.

## 2.1 Gestion de scènes 3D en rendu réaliste par lancé de rayons

Le lancé de rayons est une méthode largement utilisée en synthèse d'image, connue pour sa capacité
à simuler la propagation de la lumière pour produire des images de haute qualité. Elle est apparue dans
les années 80 avec les approches de rendu basées sur la physique pour les effets d'éclairement. Cette
méthode consiste à suivre le parcours de la lumière entre la caméra et les sources de lumière tout en
tenant compte des interactions lumineuses entre les objets (réflexion, diffraction, calcul d'ombres –
figure 2.1). Elle est maintenant largement utilisée pour la réalisation de films d'animation produits par
de grands studios bien connus tels que DreamWorks ou encore Pixar.

Toutefois, le calcul de la trajectoire de la lumière par ces algorithmes de lancé de rayons est reconnu comme chronophage et coûteux en mémoire. En effet, pour converger vers une simulation du parcours de la lumière le plus réaliste, il est nécessaire de multiplier les calculs d'interaction lumineuse entre les objets. Ces traitements correspondent au parcours de milliards de rayons au travers de la scène 3D : rayons primaires issus de la caméra, rayons secondaires d'ombrage, rayons secondaires pour calculer les inter-réflexions. Autrement dit, plus le nombre de rayons est important, plus l'image a un rendu photoréaliste satisfaisant. Mais le nombre d'opérations nécessaires au calcul d'une image en 4K d'un film d'animation peut rapidement dépasser plusieurs milliards. De plus, avec l'augmentation des capacités mémoire, il est possible de modéliser des scènes 3D de plus en plus complexes, composées de plusieurs millions de faces. L'efficacité d'une telle technique réside donc principalement dans le calcul rapide du parcours des rayons et de leur interaction avec l'environnement, tout en minimisant l'utilisation mémoire pour gérer de grandes quantités de données.
<figure><img src="image_10.png" /><figcaption>Figure 2.1 – Le lancé de rayons consiste à lancer des rayons depuis le point de vue (la caméra) au travers de la scène 3D. Si un rayon atteint une face, le pixel correspondant est associé à un triplet *RVB* dépendant de la réflectance de l'objet. C'est le principe du *ray-casting*.</figcaption></figure>

Aujourd'hui, l'objectif principal reste la qualité visuelle des images photoréalistes (film d'animation, jeu vidéo, réalité virtuelle) et la rapidité de production. Les nouvelles technologies mises à disposition permettent de répondre au besoin en matière de ressources des algorithmes basés sur le lancé de rayons (grande capacité mémoire, ferme de calcul, GPU, etc.) De plus, les architectures parallèles qui se sont fortement démocratisées ces 10 dernière années, sont parfaitement adaptées pour ce genre de processus (cf. figure 2.2). Malgré ces progrès matériels, les exigences concernant le temps de calcul et qualité de rendu restent un sujet de recherche pleinement d'actualité. L'efficacité d'un moteur de rendu par lancé de rayons réside principalement sur l'utilisation de structures de données spatialement organisées et adaptées pour réduire les temps de calcul : on parle de structures accélératrices.

<figure><img src="image_11.png" /><figcaption>Figure 2.2 – "Reflections" : la première démonstration de lancé de rayon en temps réel dans Unreal Engine 4 utilisant le framework DXR de Microsoft et la technologie NVIDIA RTX pour les GPU Volta. La démo Reflections illustre les techniques expérimentales d'éclairage et de rendu de nouvelle génération dans Unreal Engine, développées en collaboration avec NVIDIA et ILMxLAB.</figcaption></figure>
## 2.1.1 Structures accélératrices classiques

Les structures accélératrices les plus couramment utilisées sont basées soit sur une partition de l'espace utilisant un schéma de grille, soit sur une organisation hiérarchique de l'espace/des objets, soit par un mixte de ces deux procédés. Ces approches bien connues ont été étudiées en profondeur depuis leur apparition et plusieurs structures permettent d'atteindre l'interactivité en exploitant la cohérence des rayons [113, 137, 162] ou la parallélisation GPU [2, 48, 74, 90, 134].

Nous proposons de classer les structures accélératrices les plus courantes selon le tableau 2.1. Pour éviter toute confusion, nous définissons qu'une partition spatiale correspond à une partition de l'espace euclidien de la scène $E^3$, et qu'une partition objet est une partition de l'ensemble des primitives de la scène $\partial$. Nous partons du principe que le lecteur est familiarisé avec les structures accélératrices classiques, pour plus d'informations, il peut se référer aux travaux de V. Havran [80]. D'autres méthodes se basent sur une approche différente notamment en incluant la géométrie de la scène dans la structure accélératrice, nous reviendrons sur ces structures dans la section 2.1.2.

<table><caption>TABLE 2.1 – Classification des structures accélératrices avec quelques exemples des plus répandues</caption><thead><tr><th rowspan="2"></th><th colspan="2">Type de partition</th></tr><tr><th>Partition spatiale</th><th>Partition objet</th></tr></thead><tbody><tr><th>Structure linéaire</th><td>Grille uniforme [56]<br>Grille non uniforme [79]</td><td>Volumes englobants [78]</td></tr><tr><th>Structure hiérarchique</th><td>BSP-tree [55]<br>Kd-tree [15]<br>Octree [61]<br>Grilles hiérarchiques [79]</td><td>BVH [91]</td></tr></tbody></table>

### Définition 1 (Partition spatiale)

Une partition spatiale $P = \{R_1, \dots, R_n\}$ subdivise l'espace euclidien $E^3$. Une primitive $\partial$ représentée dans $E^3$ par un ensemble de points $X \subset E^3$ est associée à une région $R$ si et seulement si $\exists x \in X | x \in R$.

Une partition spatiale correspond à une partition de l'espace euclidien de la scène $E^3$ (cf. Définition 1). Quelques exemples classiques de structures accélératrices basées sur une partition spatiale sont représentés (en 2D) sur la figure 2.3.

La grille uniforme [56] est probablement la structure accélératrice de partitionnement spatial la plus simple. Elle vise à partitionner l'espace en volumes identiques alignés sur des axes. Chaque objet partiellement ou totalement contenu dans un volume est associé à celui-ci. L'algorithme de traversée est un algorithme de type Bresenham, traversant la grille le long du rayon, un volume à la fois. Seuls les objets contenus par les volumes traversés sont testés. Les principaux inconvénients de cette approche apparaissent avec les scènes à densité hétérogène. Pour éviter ce problème, il est possible d'utiliser une grille hiérarchique qui raffine la subdivision en fonction de la distribution de la géométrie (cf. figure 2.3.a). En revanche, son algorithme de traversée est plus coûteux [79].

Les structures d'accélération telles que les Kd-tree [15], les arbres BSP (Binary Space Partitioning [55]), sont basées sur une organisation spatiale et hiérarchique de la géométrie dans un arbre binaire (cf. figure 2.3.b et c). Ces méthodes présentent une complexité de traversée qui dépend de la profondeur de l'arbre. En effet, leur traversée nécessite de commencer par la racine de la hiérarchie. Certains travaux se sont attachés à réduire cette restriction en l'enrichissant par des liens supplémentaires entre les feuilles de l'arbre [133] ou en incluant des niveaux de boîtes englobantes [81]. En revanche, le parcours de ces structures améliorées est plus coûteux puisque l'utilisation de ces extensions nécessite de calculer le point de sortie dans le noeud pour poursuivre la propagation du rayon au travers de la scène 3D.
<figure><img src="image_12.png" /><figcaption>Figure 2.3 – Illustration du parcours d’un rayon au travers de différentes structures accélératrices : (a) Quad-tree (b) BSP tree (c) Kd-tree (d) BVH. En haut, le partitionnement spatial correspondant. En bas, l’organisation de l’arbre avec en orange les noeuds visités.</figcaption></figure>

### **Définition 2 (Partition objet)**

Une partition objet $P = \{R_1, \dots, R_n\}$ subdivise l'espace des primitives géométriques de la scène $\partial^3$. Un point $x \in \mathbb{E}^3$ est associé à une région $R$ si et seulement si $\exists G \in R \mid x \in G$.

Une partition objet correspond à une partition de l'espace des primitives géométriques de la scène $\partial^3$ (cf. Définition 2). Dans une partition objet, la plus petite région correspond à une unique primitive (un élément de $\partial^3$). Le plus souvent, un volume fermé, dit englobant, est associé à chaque région contenant un ensemble non vide de primitives. Lorsqu'un rayon ne traverse pas un tel volume englobant, il ne traverse aucune primitive.

Un exemple typique de structure accélératrice basée sur une partition objet est la hiérarchie de volumes englobants, le BVH (Bounding Volumes Hierarchy [91, 140]). Le principe consiste à regrouper les primitives en volumes englobants organisés de manière hiérarchique sous la forme d'un arbre. La racine de l'arbre correspond au volume englobant de toute la scène. Chaque noeud interne représente un ensemble (i.e. un volume englobant contenant des primitives), lui même subdivisé par ses fils. Chaque feuille est une région de la partition, associée à une liste (non vide) de primitives entièrement contenues. La figure 2.3.d présente en 2D un exemple de BVH. Le parcours de l'arbre se fait alors de manière récurrente depuis sa racine. Si le rayon ne traverse pas le volume d'un noeud donné, alors le sous-arbre associé n'est pas traité.

### **2.1.2 Partitionnement Spatial Contraint CSP**

À l'instar d'une partition spatiale classique, une partition spatiale contrainte (CSP) subdivise l'espace euclidien de la scène $\mathbb{E}^3$ en un ensemble de régions disjointes et non vides mais les primitives géométriques sont obligatoirement confondues avec les bords (i.e. les faces) des volumes composant la partition.

On distingue alors deux types de faces : les faces appartenant à la géométrie de la scène et les faces non occultantes (i.e. qui permettent la propagation de la lumière sans l'interférer) créées pendant la construction de la partition. Fortune a introduit ce concept en proposant un traçage topologique de faisceau utilisant une subdivision convexe acyclique respectant les obstacles de la scène [49].
La recherche de l'intersection la plus proche entre un rayon et la géométrie consiste à parcourir la partition le long du rayon, volume par volume, jusqu'à rencontrer une face appartenant à la géométrie de la scène. Une seule opération est nécessaire : rechercher la face de sortie d'un rayon depuis l'intérieur d'un volume. Si cette face fait partie de la géométrie, alors l'intersection la plus proche est trouvée. Sinon, si la face est non occultante, alors le rayon est propagé dans le volume voisin. La relation de voisinage entre les volumes est utilisée (i.e. relation topologique de dimension 3). La complexité de l'algorithme est donc linéaire en nombre de volumes traversés par le rayon.

La stratégie de subdivision employée a donc logiquement un impact sur l'efficacité du parcours de la CSP, i.e. sur le nombre moyen de volumes traversés par les rayons. L'autre point influençant cette efficacité est l'algorithme de recherche de la face de sortie d'un rayon depuis l'intérieur d'un volume. Afin de faciliter cette recherche, une contrainte supplémentaire peut être ajoutée à la construction de la CSP : les volumes doivent être convexes. Ainsi, un rayon ne peut sortir d'un volume que par une et une seule face. On parle alors de partition spatiale contrainte et convexe (CCSP - Constrained Convex Space Partition).

Lagae propose une CCSP basée sur une tétrahédrisation qui respecte la géométrie de la scène [96]. Dans ce travail, plusieurs méthodes sont proposées afin de trouver la face de sortie d'un rayon à l'intérieur d'un tétraèdre : utilisation des intersections rayon/plan [60], classification de demi-espace en utilisant les coordonnées de Plücker [131, 147]. L'algorithme se révélant être le plus efficace utilise de 3 à 6 produits scalaires triples. Malheureusement, ces méthodes n'exploitent pas le fait qu'un rayon ne peut pas sortir d'un tétraèdre par sa face d'entrée.

Dans le contexte du rendu volumique, G. Marmitt [117] résout ce problème en exploitant les relations de voisinage entre les faces pour écarter automatiquement la face d'entrée. Le principal inconvénient de cette méthode est le nombre d'opérations nécessaires, qui varie avec les données d'entrée, ce qui entraîne une certaine divergence de calcul dans un environnement parallèle. En effet, la précision arithmétique insuffisante avec des flottants peut provoquer des échecs dans la traversée de la structure conduisant à des boucles infinies.

En comparaison avec les structures accélératrices classiques, les structures accélératrices de type CSP possèdent les propriétés suivantes :

* contrairement aux partitions spatiales, une CSP évite les problèmes de référencement multiple des primitives géométriques ; de plus, il est impossible de tester plusieurs fois la même primitive lors du parcours de la structure accélératrice ;

* contrairement aux partitions objets, il n'y a pas de chevauchement spatial ;

* contrairement aux structures linéaires telle qu'une grille uniforme, une CSP s'adapte parfaitement à la géométrie de la scène ;

* contrairement aux structures hiérarchiques, son parcours est totalement itératif et exploite implicitement la connectivité entre les rayons.

Malgré ces avantages apparents, lorsque nous nous sommes intéressés à ce type de partition, elle était encore peu utilisée dans le cadre des simulations d'éclairage basées rayons. À notre connaissance, lors du lancement de la thèse de M. Maria, il n'existait que deux exemples d'utilisation de CSP dans ce contexte : le graphe cellules et passages et la tétraédrisation de Delaunay contrainte.

## CSP dédiée à l'architecture

Les environnements architecturaux sont composés de grandes surfaces occultantes telles que des murs, des sols ou des plafonds. Ainsi, à partir d'un point de vue donné, seule une petite partie de la scène est visible. Par conséquent, les structures générales d'accélération souffrent de deux problèmes principaux. D'une part, les scènes meublées contiennent de petits objets très détaillés dans de grands
espaces vides, ce qui ralentit la traversée des structures régulières. D'autre part, étant donné que les murs des bâtiments ne sont pas nécessairement alignés, les structures d'accélération basées sur des plans de fractionnement ne sont pas adaptées; elles ne respectent pas la position des murs, ce qui entraîne un schéma de fractionnement complexe et donc de mauvaises performances.

Le calcul d'images de synthèse pour ces scènes est donc souvent traité à l'aide de structures particulières permettant de localiser les traitements pour des méthodes de simulation d'éclairage [4, 50, 51, 118, 155]. Les auteurs utilisent la notion de "cells and portals" (nommée cellules et passages dans la suite de ce chapitre). Pour cela, les cellules sont associées aux pièces du bâtiment et les passages correspondent aux faces incidentes à deux cellules (cf. figures 2.4.b et 2.4.c). Cette représentation correspond à une représentation topologique 3D du bâtiment : des pièces (des volumes 3D) et des relations de voisinage par les ouvertures (des faces 2D reliant les volumes). Le calcul de traversée d'un rayon au travers de la scène utilise les relations de voisinage entre les cellules, limitant de ce fait l'ensemble de volumes potentiellement parcourus. Comme tout autre CSP, pour un rayon émis à partir d'un volume V, l'ensemble des faces pouvant être atteintes correspond aux faces incidentes à V. Si la face est un passage, alors le rayon est propagé récursivement dans la cellule suivante, sinon il est stoppé (cf. figure 2.4.d). Par ailleurs, ces informations permettent de construire facilement et directement le PVS<fnref n="1" /> (pour Potentially Visible Set [157]) de chaque pièce. La consultation de ce graphe de voisinage localisé réduit d'autant plus les temps de traitement.

<figure><img src="image_13.png" /><figcaption>Figure 2.4 – Représentation et utilisation en 2D d'une structure cellules et passages : (a) représentation 2D d'un bâtiment; (b) les volumes de la scène correspondent aux cellules; (c) les faces incidentes à deux cellules correspondent aux passages; (d) propagation des rayons au travers de la scène. Les rayons entrants en collision avec un passage sont propagés dans la cellule voisine, les autres sont stoppés sur le bord des cellules.</figcaption></figure>

<footnote n="1">1. PVS : ensemble des cellules potentiellement visibles à partir d'une cellule principale.</footnote>
Dans la littérature, les structures de données type cellules et passages sont construites soit à partir d'un ensemble de polygones 3D représentant une scène [3, 116, 145], soit lors de la construction du bâtiment [49, 52]. Dans le premier cas, les informations topologiques sont déduites par un découpage de l'espace 3D. Les données calculées correspondent uniquement aux relations d'adjacence entre les cellules (i.e. des volumes). Aucune information topologique supplémentaire n'est définie. Dans le deuxième cas, la structure topologique est construite lors de la création du modèle. Cette structure topologique fournit des renseignements supplémentaires : adjacence entre éléments de dimensions 1 et 2 (arêtes et faces), volumes des murs, volume de la façade. Mais bien que le modèle soit plus complet (des cartes généralisées dans ces travaux), seules les relations d'adjacence entre les volumes sont employées lors du processus de rendu [51]. Les informations de dimensions inférieures ne sont pas utilisées pour l'application de simulation d'éclairage proposée.

Pour une scène architecturale 3D, la répartition spatiale des primitives géométriques peut mettre en défaut les structure accélératrices classiques (grandes faces occultantes, les murs et petites faces concentrées, le mobilier). Ce constat peut être généralisé pour des scènes quelconques composées d'objets aux détails fins : objets de très petite taille (fils, grillages, toiles d'araignée), bords arrondis des objets, etc.

### 2.1.3 Gestion de détails fins, les arrondis

Les objets réels qui nous entourent ne présentent presque jamais de bords parfaitement nets. Sur les bordures apparaissent des zones plus claires ou plus foncées en fonction des interactions lumineuses avec le reste de la scène. Comme l'illustre la figure 2.5, un élément clé du réalisme concerne la description de ces très petits détails qui ont un impact évident sur l'apparence globale de l'image. Même s'ils correspondent à des effets subpixels [41, 106, 134, 169], leur représentation est essentielle au réalisme, car leur apparence (reflets spéculaires, ombres propres et variations des normales) influence profondément la perception des formes [142]. Il est donc très important d'avoir une représentation géométrique fidèle à l'objet réel pour ces éléments de détails fins, et que le traitement appliqué lors du processus de rendu permette une visualisation photoréaliste.

<figure><img src="image_14.png" /><figcaption>Figure 2.5 – Exemples d'effets lumineux sur des bords arrondis (a) photographie d'un reflet spéculaire sur l'arête chanfreinée d'un meuble métallique (b) et (c) deux objets identiques sans arrondis de bords (b) et avec arrondis (c). Les arrondis permettent de mieux percevoir les délimitations des différentes pièces constituant l'objet.</figcaption></figure>

La modélisation des arrondis repose généralement sur un chanfreinage explicite [34, 153] ou sur des surfaces de subdivision [19, 30, 151], qui génèrent *in fine* des surfaces maillées complexes. Un maillage reste une représentation discrète d'une surface lisse, inévitablement sujette à des artefacts observables lorsque l'observateur et/ou la lumière se déplace(nt) autour de l'objet.
Malheureusement, la gestion de tels détails complexifie la géométrie et augmente les besoins en mémoire et en temps de calcul pour la génération d'une image. Par ailleurs, l'augmentation du nombre de petites faces sur des zones localisées met en défaut la plupart des structures accélératrices classiques. Il devient nécessaire de définir des heuristiques comme le SAH (Surface Area Heuristic) pour estimer le coût de recherche d'intersection pour un rayon [62, 111]. En partant du principe que les rayons sont uniformément distribués et qu'ils ne touchent aucune primitive de la scène, l'objectif est de choisir un plan de partitionnement parmi plusieurs possibilités dans le but de minimiser ce coût. Une structure accélératrice est alors considérée comme optimale lorsque son coût SAH est minimal [161].

Pour modéliser un arrondi continu avec une visualisation des effets de lumière plus précise, il est possible d'utiliser des surfaces paramétriques [88]. Ce procédé permet également de conserver une continuité entre les faces de l'objet et le chanfrein (une continuité G1 représente la tangence des courbes ou la continuité de la tangence entre deux courbes). Néanmoins, le coût d'intersection d'une telle représentation est supérieur à un ensemble polygonal fin approchant la même surface. Les éléments paramétriques sont également difficiles à intégrer dans les structures accélératrices et dans le processus de rendu. C'est pourquoi, le rendu des bords et des coins arrondis est souvent traité à l'aide d'une subdivision géométrique ou de shaders de biseau, évitant ainsi le processus d'arrondi et minimisant la complexité de la géométrie du maillage généré [18, 31, 142, 154, 164].

Finalement, les différentes solutions proposées consistent à réaliser un prétraitement au processus de simulation afin d'étudier la répartition spatiale des primitives géométriques de l'environnement (statistique de SAH), l'objectif étant de construire une structure accélératrice adaptée au mieux à cette répartition spatiale. Or, ces informations sont omniprésentes dans le domaine de la modélisation à base topologique qui permet de connaître la structure de l'environnement. Il serait donc judicieux d'utiliser la richesse du modèle topologique plutôt que d'opérer une étape supplémentaire dans le traitement.

## 2.2 Modélisation à base topologique

Dans le domaine de l'informatique graphique, la modélisation géométrique concerne la structuration d'un environnement 3D : la forme géométrique des objets ; les relations de voisinages entre les éléments ; les propriétés (physiques ou visuelles) qui caractérisent les objets. Ces informations sont utilisées pour structurer et manipuler les informations géométriques, appliquer des opérations complexes et améliorer les temps de traitement. Plus particulièrement, la modélisation à base topologique a pour objectif de modéliser des objets géométriques partitionnés en cellules de différentes dimensions (0 pour les sommets, 1 pour les arêtes, 2 pour les faces, 3 pour les volumes, etc.). Les cellules sont liées entre elles par des relations d'adjacence si elles sont de mêmes dimensions, d'incidence si elles sont de dimensions différentes [114]. Cette structuration facilite la manipulation des informations de voisinage entre objets. Elle permet par exemple de directement connaitre la liste des faces qui composent d'un volume, ou l'ensemble des arêtes incidentes à un même point. Ces informations sont importantes pour diverses applications telles que la modélisation de bâtiments ou l'étude des sous sols géologiques [25, 52, 99]. Le principe, issu de la représentation par les bords (cf. figure 2.6), est de représenter la topologie (structure) de la subdivision par un modèle combinatoire (par exemple : la structure d'arêtes ailées [12], les cartes combinatoires [42] ou les cartes généralisées [103]).
Dans la suite de cette section, nous décrivons les modèles topologiques de subdivision cellulaire usuels. Notre objectif étant d’utiliser un modèle pertinent dans le cadre de la représentation d’objets réels en 3D, nous expliquons notre choix d’utiliser le modèle de représentation des cartes généralisées et nous présenterons les notions de base à sa manipulation.

<figure><img src="image_15.png" /><figcaption>Figure 2.6 – Représentation par les bords : les objets sont décomposés en cellules de différentes dimensions : sommets, arêtes, faces et volumes. Chaque cellule est en relation avec son bord. (a) représentation par les bords d’un disque, la face (dimension 2) est associée à 2 arêtes (dimension 1), elles-mêmes associées à 2 sommets (dimension 0); (b) vue éclatée du même disque où les flèches représentent les relations de bord entre les cellules ; (c) modèle cellulaire composé de 3 faces, 8 arêtes, et 6 sommets.</figcaption></figure>

## 2.2.1 Modèles topologiques usuels

De nombreux modèles topologiques et leurs opérations associées ont été proposés afin de représenter et manipuler des objets subdivisés. Historiquement, les premiers travaux ont porté sur la représentation de subdivision de surfaces (variétés de dimension 2), puis sur les complexes (non-variétés) de dimension 2 (cf. figure 2.7). Il existe une grande diversité de modèles permettant de représenter des objets de dimensions quelconques, depuis des objets très généraux (complexes de dimension *n*) jusqu’à des sous-classes de ces derniers (variétés, variétés orientables sans bord, quasi-variétés, etc.).

### Complexes et variétés

Les modèles de représentation des objets réels sont tous des variétés de dimension 3, ils sont constitués de volumes. Par exemple, un bâtiment est composé de volumes (murs, pièces, sol, etc.). Plus formellement, une variété subdivisée de dimension *n* est un assemblage de cellules de dimension *n* le long de cellules de dimension *n* − 1. En dimension 2, les faces sont assemblées le long de leurs arêtes et une arête est partagée par au plus deux faces.

Un complexe (non-variété) est un objet plus général ne répondant pas au critère précédent. Il peut être construit par assemblage de cellules de dimension quelconque le long de cellules de dimensions inférieures et non de dimension *n* − 1 seulement. La figure 2.7 illustre les différences entre les assemblages complexes et variétés.

### Modèles simpliciaux et modèles cellulaires

Les modèles utilisant des cellules régulières (cubiques, simplex, etc.) sont couramment utilisés pour la représentation de maillages : la subdivision n’est pas liée à une sémantique particulière et la régularité de structuration des cellules peut simplifier des calculs complexes (simulation mécanique par exemple). Les différents modèles existants sont distingués suivant le type de cellules composant l’objet. Les modèles simpliciaux sont utilisés pour représenter des objets composés de simplexes (sommets, arêtes, faces triangulaires, volumes tétraédriques, etc.). Les modèles cellulaires permettent de représenter des subdivisions d’objets en cellules quelconques.
<figure><img src="image_16.png" /><figcaption>Figure 2.7 – Classification des subdivisions. Type de cellules : régulières (simplexes, simplexes cubiques ou quelconques. Type d’assemblage : quasivariété (caractérisé par des propriétés topologiques comme la multiincidence ou l’orientation) ou complexe (composé de cellules quelconques).</figcaption></figure>

Une partie importante des travaux en modélisation géométrique porte sur la définition des modèles cellulaires afin d'associer une sémantique et un plongement aux cellules. Cette sémantique correspond généralement à des informations supplémentaires comme la nature des objets ou le matériau utilisé pour leur construction. Par exemple, un volume de sémantique *MUR* dans un bâtiment, ou une face aux propriétés photométriques particulières utilisées dans le processus de rendu (couleur, texture, modèles d'apparence, etc.).

### Les graphes d'incidences et les modèles ordonnés

Pour définir les relations entre différents éléments, les graphes d'incidence et les modèles ordonnés sont utilisés. Les graphes d'incidence permettent de modéliser des objets très généraux, mais sans spécifier les relations de multi-incidences. En revanche, les modèles ordonnés ne présentent pas ces inconvénients. Les modèles ordonnés sont basés sur un élément plus "atomique" que les cellules et sur des opérateurs portant sur ces éléments.

<figure><img src="image_17.png" /><figcaption>Figure 2.8 – Exemple de graphes d'incidences. Ici le sommet *A* est incident au arête *a* et *b*, l'arête *c* est incidente aux faces $F_1$ et $F_2$.</figcaption></figure>
Les graphes d'incidence représentent les différentes cellules d'une subdivision par les noeuds d'un graphe, et les relations de bord entre cellules (relations d'incidence) par les arêtes de ce graphe (cf. figure 2.8). Bien qu'ils permettent d'identifier rapidement les relations d'adjacence et d'incidence entre les cellules, nous pouvons citer certains problèmes fondamentaux liés à la définition même des graphes d'incidence [105, 165] :

* il est difficile de choisir les contraintes de cohérence permettant de garantir la représentation d'un objet valide (un graphe d'incidence peut représenter une arête incidente à trois sommets);

* ils ne permettent pas de représenter sans ambiguïté, en particulier la multi-incidence;

* les relations d'ordre entre cellules (par exemple, l'ordre des arêtes autour d'un sommet) ne sont pas explicitement représentées.

Pour pallier ces différents problèmes, les modèles ordonnés ont été introduits. Ils ont pour avantage principal d'être spécifiés de manière algébrique à l'aide d'un unique type d'élément de base sur lequel des fonctions sont définies. Les modèles ordonnés représentent une relation d'ordre au sein des cellules incidentes. La détection de l'orientabilité de l'objet est facilitée. Les entités de base varient en fonction des modèles. L'un des premiers à avoir été proposé est celui des arêtes ailées [13, 72, 166]. Ce modèle est principalement utilisé pour la représentation de subdivisions de surfaces orientables. Les cartes combinatoires [42] sont définies sur des entités élémentaires appelées *brin*, correspondant intuitivement en 2D à des demi-arêtes. Ceci permet de représenter des subdivisions de surfaces orientables sans bord. Ce modèle a été étendu par Lienhardt [103] en dimension quelconque pour la représentation de variétés orientables ou non, avec ou sans bord. Monsieur Pascal Lienhardt a montré que tous ces modèles sont équivalents, au domaine de modélisation près [104].

De manière informelle, les quasi-variétés constituent une classe d'objets intermédiaires entre les pseudo-variétés et les variétés (cf. figure 2.9) [64]. De manière intuitive, une quasi-variété de dimension *n* est construite par assemblage de cellules de dimension *n* le long de cellules de dimension *n* − 1, de façon à ce qu'une (*n*-1)-cellule soit incidente à au plus deux n-cellules.

<figure><img src="image_18.png" /><figcaption>Figure 2.9 – Représentation de quasi-variété : (a) liaison de deux arêtes au niveau d'un sommet ; (b) liaison de deux faces au niveau d'une arête ; (c) liaison de deux volumes au niveau d'une face.</figcaption></figure>

Dans le contexte du rendu de scènes 3D, nous visualisons des objets réels et travaillons dans l'espace $\mathbb{R}^3$ subdivisé en cellules de dimension 0, 1, 2 et 3 (sommets, arêtes, faces et volumes). Ces modèles représentent des objets orientables 3D (les volumes), délimités par leurs frontières (leurs faces). De plus, dans la mesure où nous souhaitons avoir une représentation volumique, l'intégralité de l'espace doit être modélisée. Ainsi, deux objets ne peuvent pas occuper le même emplacement et l'espace entier est rempli, ce qui conduit à une partition de l'espace. C'est pourquoi le modèle doit être contraint afin de correspondre obligatoirement à une subdivision de l'espace fermée et composée de volumes, de faces et d'arêtes orientées. Par conséquent et topologiquement parlant, une scène doit correspondre à un maillage 3D orienté et fermé.
Plusieurs modèles topologiques ont été proposés dans la littérature pour composer différentes classes de subdivision (surfaces orientées, maillage, etc.) en toutes dimensions. Parmi ces structures nous trouvons : les graphes d'adjacence [139], les modèles ordonnés (comme défini dans [27]), modèle 2D et 3D d'arêtes ailées [12, 166] ou des modèles de dimension supérieure [27, 105].

Les graphes d'adjacence ne permettent pas les multi-incidences (voir [105]) et la validité topologique du modèle est difficile à exprimer [165], c'est pourquoi nous avons choisi un modèle ordonné pour les travaux présentés dans ce manuscrit. Les études ont montré que les maillages 2D et 3D (subdivision de surface et de volume), sont coûteux pour représenter un modèle ordonné tout comme les graphes d'incidence [53]. C'est encore plus vrai lorsqu'il s'agit de géométrie, photométrie et autres attributs pris en compte.

Les modèles définis pour représenter les maillages 3D sont comparables aux cartes 3D (pour les cartes orientables 3D sans bord) ou aux cartes généralisées 3D (pour les maillages orientables ou non et avec ou sans bord) [104]. Les G-cartes offrent une description implicite des cellules (sommets, arêtes, faces, volumes) avec des opérations locales efficaces automatiquement propagées aux cellules incidentes [9, 40]. Elles sont homogènes en toutes dimensions ce qui facilite la définition des opérations en 2D et 3D. L'utilisation d'un tel modèle associé à un plongement linéaire<fnref n="2" /> permet de mettre en place facilement des applications de construction et/ou reconstruction d'environnement 3D tout en contrôlant la structuration topologique du modèle.

L'ensemble de ces propriétés nous ont conduit à utiliser ce modèle de représentation pour les différents travaux de modélisation géométrique à base topologique décrits dans ce manuscrit. Nous détaillons dans la section suivante les définitions et notations utilisées dans nos travaux.

### 2.2.2 Cartes généralisées concept et notations

Le modèle des cartes généralisées (ou G-cartes) est une extension des cartes combinatoires [103]. Ce modèle est défini mathématiquement comme des algèbres, à l'instar des algèbres d'arêtes [73] et des structures cell-tuples [27]. Elles permettent de représenter la topologie de quasi-variétés subdivisées orientables ou non, avec ou sans bord [105]. Leur principal avantage est d'être définies de façon homogène en toutes dimensions, contrairement aux cartes combinatoires, ce qui simplifie les définitions et l'écriture des algorithmes. Une carte généralisée de dimension 3 - ou 3-G-carte représente la structure (i.e. la topologie) d'un objet en définissant ses frontières dans chaque dimension : un volume est représenté par ses faces, une face par ses arêtes, et une arête est définie par ses sommets.

À partir d'un élément simple de base (appelé le *brin*) et d'applications bijectives (appelée $\alpha$) définies sur ces brins, les cartes généralisées représentent des cellules et leurs relations d'adjacences et d'incidences. Chaque involution$^3 \alpha_i$, avec $0 \le i \le n$ ($n$ est la dimension de l'espace considéré), représente les relations d'adjacence entre les cellules de dimension $i$. $\alpha_0$ représente les liens entre deux sommets, $\alpha_1$ lie deux arêtes, $\alpha_2$ lie deux faces et $\alpha_3$ lie deux volumes (cf. Définition 3). Dans la suite de ce manuscrit, les relations topologiques en dimension $i$ sont notées $\alpha_i$. La figure 2.10 montre comment cette topologie est visualisée (pour plus de clarté, les sommets liés en dimension 0 pour constituer des arêtes ne sont pas représentés).

<footnote n="2">2. Représentation vectorielle des éléments, i. e. coordonnée des points selon 3 composantes $\vec{x}, \vec{y}, \vec{z}$ représentant chacune une dimension en 3D.</footnote>

<footnote n="3">3. Une involution $f$ est une bijection tel que : $f^2 = \text{Id}$.</footnote>
<figure><img src="image_19.png" /><figcaption>Figure 2.10 – Représentation des G-cartes : (a) un objet 2D composé de 3 faces, 6 arêtes et 5 sommets ; (b) G-carte correspondante : l’ensemble des brins $\{1,2,3,4\}$ représente l’arête $a_1$, l’ensemble des brins $\{3,4,5,6,7,8,9,10\}$ représente la face $F_1$ ; (c) objet 3D composé de deux volumes représentés avec les 3-G-cartes, les volumes sont liés par $\alpha_3$ ; (d) représentation symbolique couramment utilisée des involutions. Dans la plupart des schémas, les liens $\alpha_0$ ne sont pas représentés pour faciliter la lecture.</figcaption></figure>

**Définition 3 (Cartes Généralisées [105])**

Une carte généralisée de dimension $n \ge 0$ (ou n-G-carte) est une algèbre $G = (B, \alpha_0, ..., \alpha_n)$, où :

- $B$ est un ensemble fini de brins;

- $\alpha_0, ..., \alpha_n$ sont des involutions sur $B$;

- $\alpha_i\alpha_j$ est une involution, $\forall i, j$ tel que $0 \le i < i + 2 \le j \le n$.

Deux brins $b$ et $b'$ sont dits *i*-cousus si $\alpha_i(b) = b'$ avec $b \neq b'$. Le brin $b$ est dit *i*-libre si $\alpha_i(b) = b$. L'orbite associée à un brin $b$ et à un ensemble d'involutions ($< f_1, ..., f_k > (b)$) est composé de tous les brins obtenus à partir de $b$ en utilisant toutes compositions d'involutions de l'orbite.

Une *i*-cellule est une orbite particulière composée de toutes les involutions à l'exception de $\alpha_i$. Deux cellules sont disjointes quand leur intersection est vide, i. e. quand aucun brin n'est partagé par les cellules. Dans la figure 2.11, les *i*-cellules qui composent une 3-G-carte sont représentées avec leurs orbites correspondantes.

**Définition 4 (i-cellule)**

Soit $G$ une n-G-carte, $b$ un brin de cette carte, et $i \in \{0, ..., n\}$. La *i*-cellule incidente à $b$ est $\langle \alpha_0, ..., \alpha_{i-1}, \alpha_{i+1}, ..., \alpha_n \rangle(b)$.

Le degré d'une *i*-cellule $C$ est le nombre de $(i+1)$-cellules distinctes incidentes à $C$ (par exemple, le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes).

**Définition 5 (Éléments pendants)**

$\forall i \in [1, 2]$ une *i*-cellule $C_i$ est pendante si et seulement si le degré de $C$ est 1 et si l'une de ses $(i-1)$-cellules incidentes $C_{i-1}$ est également de degré 1.

Dans la figure 2.12.a, $A_1$ est une arête pendante. Son degré est 1 et elle est incidente à un sommet de degré 1. Au contraire, $A_2$ est de degré 1, mais n'est pas pendante, car elle n'est pas incidente à un sommet de degré 1 cf. figure 2.12.c.
<figure><img src="image_20.png" /><figcaption>Figure 2.11 – Chaque cellule est obtenue à partir d’un brin et d’une orbite : (a) < α₀, α₁, α₂ > pour les volumes ; (b) < α₀, α₁, α₃ > pour les faces ; (c) < α₀, α₂, α₃ > pour les arêtes ; (d) < α₁, α₂, α₃ > pour les sommets.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 2.12 – Eléments pendants : (a) A₁ est une arête pendante dans la face F₁. Son degré est 1 et elle est incidente à un sommet de degré 1 ; (b) représentation de A₁ en terme de G-carte ; (c) A₂ est une arête de degré 1 non-pendante ; (d) représentation de A₂ en terme de G-carte.</figcaption></figure>

### Représentation d'objets réels

Dans la représentation virtuelle d'objets réels, les éléments occupent chacun leur espace sans superposition et correspondent à une subdivision de l'espace en cellules (volumes, faces, arêtes et sommets) définies par leurs bords en toutes dimensions. Les G-cartes permettent de représenter des objets beaucoup plus génériques, notamment orientés et non orientés<fnref n="4" />. Nous devons définir un ensemble de propriétés pour identifier le modèle de représentation d'un objet réel. Nous utilisons notamment une subdivision de l'espace 3D qui nous aide à définir une partition 3D formellement fermée et orientée.

<footnote n="4">4. Les cellules orientables sont des cellules pour lesquelles nous pouvons définir un parcours en "sens horaire" de manière cohérente</footnote>
Le critère de partition de l'espace repose sur un mélange de géométrie et de topologie, où nous définissons $C_i$ comme l'espace géométrique d'une $i$-cellule (par exemple, $C_3$ définit l'espace d'un volume, $C_2$ définit une face, $C_1$ une arête, $C_0$ un sommet). Formellement, un objet 3D est bien formé si et seulement si une partition de l'espace P satisfait la définition 6. En d'autres termes, deux cellules $i$ ne doivent pas occuper le même espace et/ou doivent être reliées par des cellules de dimensions inférieures.

**Définition 6 (Partition de l'espace)**

$$ \forall i \in \{0, 1, 2, 3\}, \forall C_i^1, C_i^2 \in P, C_i^1 \cap C_i^2 = \emptyset \lor \exists j \in [0; i[, C_i^1 \cap C_i^2 = C_j \text{ où } C_j \in P. $$

La propriété de fermeture des objets est bien connue, mais avec des 3-G-map, cette propriété diffère et devient une fermeture topologique définie par la définition 7. De manière moins formelle, cela signifie qu'il n'y a pas d'auto-boucle dans le graphe et que les faces ouvertes sont interdites.

**Définition 7 (Fermeture)**

$$ \forall b \in G, \forall i \in [0; 3], b \cdot \alpha_i \neq b. $$

La dernière propriété est l'orientation : Les G-cartes peuvent représenter des objets orientés (ou non). Pour représenter l'orientation, nous incluons un booléen (souvent nommé *marque d'orientation*). Formellement, la propriété d'orientation est définie dans la définition 8 où deux brins adjacents ont une valeur opposée sur cette marque d'orientation pour toute dimension.

**Définition 8 (Orientation)**

$$ \forall b \in G, \forall i \in [0; 3], b \cdot \text{orient} \neq b \cdot \alpha_i \cdot \text{orient}. $$

**Mise en oeuvre**

À partir d'un noyau basé sur les G-cartes, le modeleur topologique 3D Moka a été développé au laboratoire XLim. Ce modeleur comprend plusieurs opérations comme la couture de deux cellules le long d'une face, ou d'autres applications plus complexes comme l'extrusion ou le corafinement [159]. Moka a été fortement mis à contribution dans les divers travaux présentés dans ce manuscrit (cf. figure 2.13).
<figure><img src="image_22.png" /><figcaption>Figure 2.13 – Interface du module de Moka [159] dédié à la modélisation de bâtiments.</figcaption></figure>

## 2.3 Reconstruction de modèles 3D à partir de données

La section précédente décrit les différents modèles de représentation utilisés en modélisation géométrique à base topologique. Lorsque les environnements 3D sont construits directement à l'aide des modèles géométriques par un assemblage d'éléments géométriques de base, la structuration topologique de la scène est directement définie au fil des opérations de construction. Il est donc facile de contrôler les cohérences topologiques du processus de construction. Mais dans divers domaines d'application, il est nécessaire de produire une scène virtuelle à partir de données numériques existantes : nuage de points issus de la numérisation d'un bâtiment, plan numérique d'architecte, sondage sismique pour la reconstruction de sous sol géologique, imagerie médicale pour la modélisation des organes internes, etc. La principale difficulté des méthodes de reconstruction réside dans la génération de modèles virtuels identiques (ou au plus proche) géométriquement de la donnée d'origine (réelle). Il est par ailleurs nécessaire de procéder à un calcul spécifique pour reconstruire les informations topologiques et sémantiques. Les résultats de ces posts-traitements sont fortement dépendants des données d'entrée qui sont généralement très bruitées.

### 2.3.1 Reconstruction de maillages

Basée sur des recherches antérieures [16, 17, 70, 120], une large étude des méthodes de reconstruction et de réparation de modèles est proposée dans l'ouvrage rédigé par M. Botsch & al. [23]. Les auteurs distinguent deux grandes catégories de méthodes : les approches volumiques et les approches surfaciques. Les approches volumétriques consistent à recalculer un nouveau maillage valide après transformation du maillage existant en un maillage intermédiaire. Ces méthodes sont souvent très chronophages et leurs performances reposent sur la structure intermédiaire choisie (variété orientée [70], arbre de partition d'espace binaire [120], polyèdres de Nef [75]). Les algorithmes sont robustes et produisent des modèles
cohérents. Mais la phase de reconstruction entraîne une déconnexion avec les données de départ et une perte des informations sémantiques difficiles à recalculer [23, 149]. Les approches surfaciques visent à modifier directement le maillage d'entrée pour réparer localement les intersections *une par une* [16, 149]. Ainsi, les modifications sont limitées aux parties incohérentes. Cependant, la résolution de la géométrie d'intersection est numériquement instable, ce qui peut produire des artefacts (faces non planes, arêtes nulles, etc.) et la reconstruction ne garantit pas la génération d'un modèle volumique.

Les procédés mentionnés ci-dessus ne peuvent pas respecter à la fois les propriétés de robustesse, de précision et d'efficacité. Des post-traitements sont proposés pour supprimer efficacement les incohérences simples (arêtes complexes ou sommets singuliers), mais ils ne sont pas entièrement automatiques [70, 120]. Finalement, seules les contraintes géométriques sont contrôlées, les notions topologiques de voisinages sont rarement utilisées et vérifiées par un modèle de subdivision formel.

### 2.3.2 Reconstruction à partir de donnée médicales

Dans le contexte de l'imagerie médicale, la reconstruction de surfaces 3D à partir de données joue un rôle important dans la production de modèles virtuels anatomiques. Le champ d'application de tels modèles est vaste : diagnostic, visualisation et planification de thérapies, biopsie virtuelle, formation, etc. Les technologies d'acquisition d'imagerie médicale, telles que la tomographie assistée par ordinateur (CT) et l'imagerie par résonance magnétique (IRM), fournissent des images de coupes transversales en 2D qui sont espacées uniformément sur des tranches individuelles. Ces données permettent la reconstruction d'un modèle 3D discret (on parle de modèle digital) qui est assimilé à une grille uniforme.

Cette grille contient des informations sur un espace 3D, et est composée d'un certain nombre de voxels dont la taille correspond à la résolution spatiale de l'acquisition. Pour identifier les différents éléments anatomiques - les substances - il est courant d'utiliser une méthode de segmentation permettant répartir les voxels de la grille dans des segments, c'est à dire des régions d'intérêt (ROI pour Region Of Interest) correspondant aux différentes substances. Les méthodes de reconstruction visent ensuite à construire une surface 3D correspondant aux limites d'une ROI [123]. Le maillage surfacique créé s'adapte à la limite d'un segment de la segmentation, mais pour répondre mieux aux besoins cliniques, il est nécessaire d'avoir une représentation volumique et de connaître les relations de voisinage entre les éléments.

De nombreuses méthodes de reconstruction 3D ont été proposées, qui peuvent être regroupées en plusieurs catégories. Les modèles déformables ont été largement utilisés dans les images médicales. Il existe essentiellement deux types de modèles déformables : les modèles paramétriques et les modèles géométriques. L'utilisation de modèles paramétriques [33, 110] génère un maillage initial continu qui est ensuite transformé géométriquement pour correspondre aux frontières de la ROI. La précision obtenue est inférieure au voxel initial, mais le temps de calcul nécessaire est souvent important notamment pour éviter les auto-intersections. L'utilisation des modèles géométriques offre des solutions pour palier ces limites. Ils sont basés sur la théorie de l'évolution des courbes [95] et des méthodes de level set [26, 94, 108], représentant les courbes et les surfaces de manière implicite. Ces modèles peuvent facilement empêcher l'auto-intersection [76, 172]. Cependant, ils ne peuvent être utilisés que dans le cas d'une topologie initialement connue (par exemple le nombre de volumes à reconstruire), ce qui limite leur application physiologique [170]. En particulier, les méthodes de level set sont utilisées pour la segmentation d'images médicales dans la reconstruction d'un volume unique de tumeur [92, 93]. Néanmoins, le volume reste discrétisé si une représentation de surface est nécessaire, un algorithme de construction d'isosurface est requis.

Historiquement, les techniques de reconstruction ont été introduites avec le célèbre algorithme d'expansion d'isosurfaces Marching Cubes (MC) [106]. La simplicité, la robustesse et la rapidité du MC en ont fait l'algorithme le plus utilisé pour la visualisation interactive de données médicales. Cependant,
un problème bien connu du MC réside dans la génération d'un maillage continu (sans discontinué topologique). L'association à des données volumiques est ainsi compromise. De nombreuses méthodes avec décideur asymptotique ont été proposées pour traiter ce problème [38, 68, 121]. En outre, de nouvelles approches sont apparues, telles que Dual Marching Cubes [122] qui remplace les triangles par des quadrilatères tendant à éliminer les triangles mal formés existants dans les surfaces MC. La continuité n'étant toujours pas entièrement résolue, des versions plus élaborées ont été proposées [69]. Malgré ces versions récentes, le MC ne fournit qu'un maillage de surface de la ROI, chaque surface produite est lissée indépendamment, ce qui peut conduire à une perte de connectivité ou à des superpositions lorsque plusieurs segments sont reconstruits et regroupés dans le même espace. Il est donc indispensable de gérer un maillage volumique contraint sur les relations de voisinages des volumes.

Outre les évolutions proposées du MC, de nombreuses techniques de reconstruction de surface basées sur les contours ont été développées, et peuvent être classées en deux grandes catégories : l'assemblage de contours qui est basé soit sur une représentation explicite de la surface [10, 22, 57, 59], soit sur une représentation volumétrique qui utilise des représentations implicites [26]. L'inconvénient de ces méthodes est qu'elles ne traitent pas de cas particuliers tels que les cavités. La deuxième classe de méthodes peut encore être subdivisée en deux classes. Les méthodes d'interpolation dans lesquelles les contours transversaux sont exprimés par des champs de distance 2D lisses et continus [58, 87, 100, 116, 173]. Les méthodes d'approximation qui tendent à ajuster une fonction implicite aux données d'entrée en utilisant des normales fournies telles que les modèles implicites MPU (Multi-level Partition of Unity) proposés par Braude et al. [26].

Plus récemment, les recherches sur la reconstruction 3D à partir d'images médicales se sont concentrées sur la croissance et l'amélioration des approches d'apprentissage profond et de réseaux neuronaux, avec des méthodes implicites et explicites. Les premières utilisent un réseau de neurones profond (DNN - Deep Neural Network) pour apprendre une représentation implicite de la surface [37, 82, 124], puis trianguler le maillage final à l'aide d'une méthode d'extraction des isosurfaces. Les méthodes explicites font appel à un DNN pour déformer un maillage initial vers une cible [98, 109], afin de produire directement un maillage explicite. Les approches d'apprentissage profond sont limitées dans leurs applications, car elles doivent s'entraîner sur une topologie connue. Par exemple, le réseau de neurones utilisé pour des méthodes de reconstruction corticale est entraîné à reproduire des mailles homéomorphes à une sphère, ce qui est une hypothèse erronée en présence d'une tumeur. Des recherches supplémentaires ont été menées afin de raffiner le maillage produit par les MC avec des réseaux de neurones. Ces approches restent limitées, car la phase d'apprentissage doit s'appuyer sur une topologie fixe [32, 102]. De plus, chaque maillage volumique produit est lissé indépendamment, ce qui conduit à une perte de connectivité ou a des superpositions lorsque plusieurs volumes sont reconstruits.

Par ailleurs, de nouvelles méthodes de reconstruction sont apparues, prenant en compte la connectivité et la topologie globale pour reconstruire des données avec des segments multiples. Elles ne sont pas limitées à la reconstruction corticale, comme les approches d'apprentissage profond [37, 82]. Ce type de méthodes de reconstruction permet de contrôler la topologie de la surface reconstruite en définissant la propriété exacte à respecter au cours du processus. Les méthodes de reconstruction à partir de nuages de points sont conçues pour produire, à partir d'une entrée partielle ou complète, un maillage multisegment qui nécessite de connaître la topologie résultante avant le traitement [97]. Sans utiliser de telles contraintes, Bruel et al. ont développé une méthode basée sur l'homologie persistante pour raffiner la fonction implicite à partir de laquelle la surface finale sera extraite [28]. Cette approche peut garantir le fonctionnement avec des modèles multisegment uniquement s'ils partagent les mêmes caractéristiques topologiques. Des tentatives récentes ont été faites pour effectuer une reconstruction de surface à partir d'une segmentation multilabels qui préserve la connectivité entre chaque élément. Basé sur le double contourage, le méthode proposée récemment par Frisken [54] conserve des frontières nettes pour produire des mailles lisses sans discontinuités, en préservant la topologie de la segmentation. Cependant, il n'applique aucun type de correction, et ne prend pas en compte les connaissances anatomiques.
## 2.4 Positionnement des travaux

Les travaux présentés dans cette habilitation à diriger des recherches visent à mettre à contribution les structures topologiques et hiérarchiques pour améliorer les opérations de reconstruction 3D et optimiser les algorithmes de simulation d'éclairage par lancé de rayons.

Mon projet de recherche s'articule autour de trois axes principaux. Tout d'abord, l'utilisation d'une structure topologique basée sur les cartes généralisées comme structure accélératrice pour un algorithme de lancé de rayons dans le contexte de la visualisation de scènes architecturales. Puis nous avons proposé une nouvelle structure hiérarchique et topologique permettant une meilleure gestion des détails fins tels que les arrondis dans le rendu de scènes 3D. Enfin, toujours dans l'idée d'utiliser un modèle homogène pour les phases de modélisation et de simulation, nous avons étudié les processus de reconstruction 3D avec pour objectif de proposer un processus basé sur la reconstruction automatique de la topologie à partir d'un modèle quelconque. Ce travail expérimental a ensuite été utilisé dans une application de reconstruction de modèles 3D à partir d'images IRM. L'objectif est de produire un modèle 3D continu complet du cortex cérébral directement utilisable pour des calculs de simulations physiologiques permettant de détecter la présence de tumeurs.

### 2.4.1 Structure topologique pour la simulation d'éclairage

Dans un premier axe de recherche, nous avons étudié l'utilisation des informations topologiques issues de la phase de modélisation comme structure accélératrice pour une méthode de lancé de rayons. Pour cela, nous avons exploré une voie peu étudiée jusqu'alors, en utilisant le modèle de représentation issu de la phase de modélisation de scènes architecturales pour produire directement une partition de l'espace contrainte et convexe (CCSP) (cf. figure 2.14). Cette CCSP est ensuite directement utilisée comme structure accélératrice lors du processus de rendu. Ce travail a été réalisé au cours de la thèse de Maxime Maria, l'idée principale consistant à placer toute la géométrie sur les frontières des volumes convexes vides composant une telle partition. En d'autres termes, la structure d'accélération est fusionnée avec la géométrie. Cette structure ressemble à la tétraédrisation contrainte de Lagae [96], mais en utilisant des volumes convexes généraux. Ce type de partition se distingue des structures classiques par plusieurs concepts apportant des propriétés uniques et intéressantes. Notre CCSP est composé d'un plus petit nombre de volumes généraux, mais convexes. De plus, la CCSP est directement déduite de l'étape de modélisation. Et surtout, nous accélérons l'analyse des CCSP en utilisant des informations topologiques de toutes les dimensions (de 0 à 3). Ce processus nous a permis de développer une application de rendu interactif de scènes architecturales complexes (plusieurs centaines de millions de polygones).

Nous utilisons ces résultats pour généraliser cette approche à des scènes quelconques. Nous nous concentrons notamment sur l'utilisation d'une tétraédrisation de Delaunay contrainte comme structure accélératrice et proposons un nouvel algorithme de parcours. Comme la méthode proposée par G. Mar-mitt [117], notre méthode exploite les relations de voisinage entre les faces. L'originalité est la manière spécifique de représenter un tétraèdre qui permet de fixer à strictement 2 le nombre d'opérations néces-saires au calcul de sa traversée. Ce nouvel algorithme est naturellement plus efficace puisqu'il nécessite moins d'opérations arithmétiques que les précédents. De plus, il est plus adapté au calcul parallèle puis-qu'il ne pose pas de problème de divergence d'exécution supplémentaire.

Nos travaux concernant le rendu de scènes architecturales ont mis en évidence l'intérêt de partitionner l'espace et de hiérarchiser son contenu notamment pour gérer des primitives géométriques de tailles très hétérogènes (grandes faces de murs, petit mobilier). Nous nous sommes donc intéressés dans un deuxième axe de recherche au rendu réaliste de détails fins. Dans ce contexte, nous avons proposé la thèse de Simon Courtin dont le sujet concerne le rendu des arrondis sur les bords des objets. Contrairement aux surfaces maillées qui discrétisent la courbure des arrondis, notre objectif est de garantir une apparence
<figure><img src="image_23.png" /><figcaption>Figure 2.14 – (a) Modèle topologique basé sur les G-Cartes, (b) image de résultat.</figcaption></figure>

arrondie et lisse, quel que soit le point de vue et la distance de l'observateur, ainsi que l'éclairage incident. Au cours de ces recherches nous avons proposé une méthode non invasive (c'est-à-dire qui contrairement aux méthodes de subdivision ne modifie pas la géométrie d'origine) pour la modélisation et le rendu de chanfreins. La figure 2.15 illustre quelques exemples de configurations d'arrondis d'arêtes et de sommets quelconques.

Au coeur de notre contribution se trouve une structure hiérarchique et topologique qui définit automatiquement et avec précision la géométrie des zones arrondies des bords et des sommets. Cette structure, appelée SREC-RT (pour Structure for Ray Tracing Rounded Edges and Corners), est construite automatiquement et est intégrée dans une structure d'accélération dédiée au lancé de rayons qui permet de déterminer la région d'intérêt de chaque chanfrein et d'y appliquer le traitement correspondant. Elle permet de visualiser les arrondis des bords et sommets sans augmenter la complexité géométrique de la scène 3D. L'intersection des rayons avec les surfaces arrondies est accélérée grâce aux liens topologiques définis par les arêtes et les sommets. SREC-RT est compatible avec tout type de représentation de géométrie arrondie. Nous proposons une solution avec des surfaces paramétriques. Notre méthode a été intégrée dans le modeleur Blender [20] avec les moteurs de rendu Cycles [21] et pbrt [127].

<figure><img src="image_24.png" /><figcaption>Figure 2.15 – Exemples de configurations avec différents cas d'arrondis gérés par notre méthode. Les arrondis d'arêtes convexes et concaves (en bleu) et d'angles (en rouge).</figcaption></figure>
2.4.2 Reconstruction topologique : application en imagerie médicale

Les différentes études que nous avons menées concernant l'utilisation de structures topologiques pour des algorithmes de simulation nous ont démontré que la meilleure stratégie consiste à construire directement la structure au cours de la phase de modélisation. Les objets 3D peuvent être entièrement produits par des opérations de construction, mais plus généralement, il est nécessaire de construire une structure à partir de données existantes (un ensemble de polygones désordonnés). C'est pourquoi, nous nous sommes intéressé au processus de reconstruction d'informations topologiques à partir de données géométriques. La problématique principale de ce type de processus réside dans le calcul automatique de l'ensemble des relations de voisinages afin de reconstruire un ensemble de volumes sans superposition spatiale à partir d'une soupe de polygones non contraints. Nous proposons un algorithme général pour reconstruire des objets 3D avec des informations topologiques 3D et sans incohérence géométrique. Tout d'abord, une subdivision cellulaire est effectuée en s'appuyant sur des données d'entrée géométriques, puis les relations topologiques entre les cellules sont explicitement définies. Le modèle des cartes généra- lisées est utilisé pour représenter la topologie de la scène 3D. Dans un second temps, les faces sont scin- dées le long de leurs intersections afin de satisfaire une contrainte de partition d'espace pour construire un ensemble de volumes sans se superposer. Une de nos contributions notables consiste à résoudre le problème d'intersection 3D en utilisant des informations topologiques pour améliorer les performances en vitesse et gérer l'imprécision géométrique.

<figure><img src="image_25.png" /><figcaption>Figure 2.16 – Processus de reconstruction topologique de modèle 3D à partir de données médicales.</figcaption></figure>

Nous avons ensuite intégré cet algorithme de reconstruction topologique dans un processus pour la reconstruction de maillage volumétrique à partir d'acquisitions médicales 3D discrètes telles que des IRM (cf. figure 2.16). Ce processus permet la reconstruction automatique d'objets composés de plusieurs substances anatomiques, afin d'assurer une visualisation globale, unique et cohérente d'un cortex céré- bral. Notre processus donne, sans aucune intervention de l'utilisateur, un modèle 3D topologique robuste et propre avec des relations d'adjacence explicites entre les volumes reconstruits. Le modèle résultant respecte les données sémantiques, sans les défauts topologiques et géométriques habituellement rencon- trés dans les autres approches de reconstruction 3D. Il est ainsi directement utilisable pour des calculs d'estimation des données métaboliques/physiologiques au sein des différentes parties du cerveau dans le cadre d'outils d'aide à la détection des tumeurs.
# PARTITION TOPOLOGIQUE CONTRAINTE POUR LE LANCÉ DE RAYONS

## Sommaire

<table><tr><td>3.1 Modèle topologique dédié aux bâtiments : CCSP</td><td>32</td></tr><tr><td>3.2 Utilisation de la CCSP pour le rendu réaliste</td><td>35</td></tr><tr><td>3.3 Résultats et discussion</td><td>41</td></tr><tr><td>3.4 Visualisation topologique : généralisation</td><td>45</td></tr><tr><td>3.5 Conclusion</td><td>50</td></tr></table>

Nous avons vu dans le chapitre 2 le fonctionnement d'un algorithme de lancé de rayon. Cette technique est utilisée pour simuler le parcours des ondes lumineuses en les assimilant à des rayons qui traversent la scène 3D. Dans les environnements dits complexes (i.e. composés de plusieurs millions de polygones), la mise en place de structures accélératrices (grille uniformes, Octree, Kd-tree, etc.) est indispensable pour réduire les temps de calcul des applications de simulations.

L'utilisation de structures accélératrices pour les applications de lancé de rayons est un domaine très largement étudié depuis plusieurs décennies (cf. section 2.1.1). Le principe généralement appliqué consiste à travailler à partir d'un ensemble de polygones pour construire la structure la plus adaptée à la scène 3D en cours de visualisation. Finalement, la structure obtenue est créée de manière complètement ad-hoc sans utiliser les informations disponibles dans les applications de modélisation. L'étape de rendu est ainsi décorrélée de l'étape de construction de l'environnement ou des informations utilisées dans la modélisation seraient très intéressantes à prendre en compte pour guider le processus de rendu. C'est le cas par exemple des relations de voisinage entre les éléments, les informations topologiques utilisées dans les modèles géométriques.
Pour ce premier axe de recherche, nous avons souhaité approfondir l'utilisation d'informations topo-
logiques dans le cadre des méthodes de simulation basées rayons. Pour cela, nous proposons un modèle
topologique formel représentant une partition spatiale contrainte et convexe (CCSP Constrained Convex
Space Partition). Une CCSP est un graphe représentant une partition spatiale pour laquelle la géométrie
de la scène est située à la limite des volumes convexes (cf. section 2.1.2). Par conséquent, un volume est
composé de deux types de faces : les faces occultantes, qui appartiennent à la géométrie de la scène et
sont associées à un matériau ou une texture spécifique, et les faces non occultantes (notées N.O), qui
n'existent que pour construire une partition convexe. Cette structure de données correspond à un graphe
$G = \langle V, E \rangle$, V étant un ensemble de volumes convexes vides et E l'ensemble des faces non occul-
tantes partagées par deux volumes. Le lancé de rayon est effectué en parcourant ce graphe, un volume à
la fois, jusqu'à ce qu'il rencontre une face occultante.

Les travaux présentés dans ce chapitre ont été réalisés au cours de la thèse de Maxime Maria où l'idée d'une CCSP est appliquée aux scènes architecturales en suivant le modèle topologique dédié aux environnements architecturaux proposés par Horna et al. dans [84]. Le modeleur associé fournit un ensemble d'opérations topologiques et sémantiques permettant de créer une scène 3D de bâtiment et de générer directement la CCSP correspondante (cf. section 3.1). Après avoir expliqué de manière détaillée comment les informations topologiques sont utilisées pour guider le lancé de rayons (cf. section 3.2), nous montrons que la CCSP fonctionne pour différentes stratégies de lancé de rayons ; elle permet de lancer plusieurs centaines de millions de rayons par seconde, spatialement cohérents ou non, pour de grands bâtiments meublés composés de centaines de millions de polygones et contenant des milliers de sources lumineuses (cf. section 3.3). Enfin, dans la section 3.4, nous proposons une généralisation de l'utilisation de la CCSP pour la visualisation d'objets quelconques (i.e. des scènes non-architecturales).

3.1 Modèle topologique dédié aux bâtiments : CCSP

Les travaux présentés dans ce chapitre se basent sur le modèle topologique dédié aux environne-
ments architecturaux proposé au cours de ma thèse de doctorat [83, 84]. Ce modèle que nous appelons
GMapArchi étend les cartes généralisées (cf. section 2.2.2) par un ensemble de contraintes topologiques,
géométriques et sémantiques. La principale contribution de ce travail consiste à définir un ensemble de
contraintes de cohérences permettant de contrôler la structure d'une scène architecturale 3D. Ainsi, le
modèle correspond à une subdivision de l'espace 3D orientée et fermée composée de volumes d'une
épaisseur significative et disjoints deux à deux. L'ensemble de l'espace est modélisé : les zones de «
vide » (e.g. les pièces ou l'extérieur) correspondent aussi à des volumes. Chaque volume est identifié
par une sémantique en fonction de sa nature (un plongement sur les cellules de dimension 3), telle que
PIÈCE, MUR, PLAFOND, etc. L'ensemble de ces contraintes de cohérence, formellement défini à partir
du modèle de cartes généralisées, permet de définir le modèle GMapArchi suivant :

**Définition 9 (n-GMapArchi)**

Une *n*-G-carte $G = (B, \alpha_0, \dots, \alpha_n)$ est une *n*-GMapArchi si :

- G représente une partition : $\forall C_i^1$ et $C_i^2$ deux $i$-cellules de G avec $i \in \{0, 1, 2, 3\}$ ; $C_i^1 \cap C_i^2 = \emptyset$
ou $C_i^1 \cap C_i^2 = \{C_j \mid j \in \{0, 1, 2\} \text{ et } j < i\}$ ; $C_j \in P$ ; $C_j$ est incidente à $C_i^1$ et à $C_i^2$

- G est fermée (i.e. G ne contient aucun brin libre et deux $i$-cellules adjacentes ont obligatoirement une ($i-1$)-cellule en commun) $\forall b \in G\alpha_i(b) \neq b, i \in \{0, \dots, n\}$

- G ne représente qu'une seule composante connexe : $\forall b \in B, B = (\alpha_0, \alpha_1, \alpha_2, \alpha_3)(b)$

- G ne contient pas d'éléments pendants $\forall b \in B, \alpha_1(b) \neq \alpha_2(b)$ et $\alpha_1(b) \neq \alpha_2(b)$

- Chaque volume est associé à une et une seule sémantique : sémantique(b) = sémantique(α₀, α₁α₂)(b)
<figure><img src="image_26.png" /><figcaption>Figure 3.1 – Présentation de l’interface du module de Moka [159] dédié à la modélisation de bâtiments. Communément appelé *MokaArchi*.</figcaption></figure>

Une application de modélisation architecturale, développée au sein du département ASALI du laboratoire XLIM, implémente ce modèle en se basant sur le noyau de manipulation de G-cartes Moka [159]. Cette application, que nous nommons *MokaArchi*, propose un ensemble d'opérations de modélisation basée sur le modèle GMapArchi. Elle permet la génération semi-automatique d'un bâtiment en 3D à partir de son plan d'architecte 2D [83] (cf. figure 3.1). Elle a été employée pour modéliser l'ensemble des scènes architecturales utilisées pour les expérimentations de la thèse de Maxime Maria. La génération se déroule en deux étapes. Dans un premier temps, la topologie 2D du plan est reconstruite en respectant les contraintes du modèle. Dans un second temps, le bâtiment 3D est construit par extrusion en ajoutant le sol et le plafond. Le résultat contient toutes les informations nécessaires à la génération du CCSP : il représente une partition d'espace orientée et fermée respectant parfaitement la géométrie, contient toutes les informations topologiques nécessaires, et identifie la nature de tous les volumes (et celle des faces par le voisinage des volumes).

Le processus de reconstruction produit des volumes composés d'un couple de faces horizontales inférieures et supérieures, et d'un ensemble de faces verticales (murs, ouvertures, etc.). Chaque face est également identifiée par une sémantique : les faces occultantes, dont la sémantique fait référence à un matériau ou à une texture spécifique (TAPISSERIE, SOL, PLAFOND, etc.); les faces non occultantes (N.O.) correspondent aux ouvertures (par exemple, une face incidente à un volume de pièce et un volume de porte). La figure 3.2 illustre la représentation topologique et sémantique d'un bâtiment en 2D respectant ces propriétés.
<figure><img src="image_27.png" /><figcaption>Figure 3.2 – Représentation topologique d'un bâtiment 2D par une GMapArchi de dimension 2. Dans cette partition les faces et les arêtes sont identifiées par une sémantique distincte (volumes et faces en 3D).</figcaption></figure>

### 3.1.1 Construction des volumes convexes

Par définition, les volumes composant une CCSP sont convexes (cf. section 2.1.2). Cependant, dans le modèle architectural utilisé, il n'y a a priori aucune raison pour que les volumes respectent cette contrainte. Pour respecter les contrainte d'une CCSP, il est donc nécessaire de subdiviser chaque volume concave en volumes convexes. Pour simplifier le problème, la décomposition en volumes convexes est effectuée en 2D, avant l'extrusion du modèle vers la 3D. Le polygone concave correspondant à la face inférieure du volume est subdivisé en régions convexes en utilisant la méthode présentée par Fernández et al. [44]. Les arêtes de subdivision créées sont par la suite extrudées verticalement. Les faces résultantes sont associées à une sémantique N.O. car elle n'appartiennent pas à la géométrie initiale de la scène et doivent donc être traversées par les rayons sans les dévier.

Cette méthode permet une décomposition convexe de polygones à la fois robuste et efficace. Cependant, elle peut générer de nombreux nouveaux polygones, notamment en présence de murs courbes concaves ou de piliers (cf. figure 3.3.a). Un rayon traversant une telle zone va parcourir un grand nombre de volumes, réduisant ainsi les performances des simulations. Pour diminuer l'impact de ce type de configuration, nous restreignons l'espace occupé par la sur-découpe en ajoutant préalablement des plans virtuels autour des courbes concaves (cf. figure 3.3.b). S'il en résulte un plus grand nombre de volumes, la probabilité qu'un rayon traverse un nombre de volumes important est réduite.

### 3.1.2 Correspondance de GMapArchi à une CCSP

Le modèle GMapArchi décrit entièrement la CCSP et pourrait être directement utilisé pour le lancé de rayons. La CCSP est déduite en balayant la GMapArchi. Chaque volume devient un noeud de la CCSP : il correspond à un sous-graphe décrivant la topologie du volume, c'est-à-dire qu'un volume est décrit par ses faces reliées par $\alpha_2$, et une face est décrite par ses arêtes reliées par $\alpha_0\alpha_1$. Les sommets ne sont pas explicitement représentés, puisqu'ils sont inutiles lors du lancé de rayons. Lors de la conversion, chaque face ayant une sémantique N.O. devient une arête reliant le volume courant à un voisin (connu grâce à la relation $\alpha_3$). Selon leur sémantique, les autres faces sont associées à un matériau spécifique.
<figure><img src="image_28.png" /><figcaption>Figure 3.3 – Convexification d’une pièce aux parois courbes : (a) convexification basée sur la méthode présentée par Fernández et al. [44] ; (b) application d’un prétraitement permettant une première découpe autour des éléments courbes.</figcaption></figure>

## 3.2 Utilisation de la CCSP pour le rendu réaliste

Cette section présente en détail l’utilisation de notre CCSP et des informations topologiques qu’elle contient pour calculer le parcours des rayons dans la scène 3D. Ce procédé permet de gérer le calcul de l’éclairage à partir de sources lumineuses ponctuelles. Pour évaluer la robustesse de notre structure, notamment son comportement en cas d’utilisation d’un grand nombre de rayons incohérents à travers des scènes architecturales meublées complexes, nous proposons un traitement spécifique permettant d’inculure du mobilier dans la scène.

### 3.2.1 Traversée de la CCSP

La recherche de la plus proche intersection entre un rayon et la géométrie de la scène s’effectue en deux étapes principales. Tout d’abord, la localisation du volume contenant l’origine du rayon. Ensuite, le rayon traverse la partition en parcourant un volume à la fois jusqu’à ce qu’il rencontre une face occultante.

<figure><img src="image_29.png" /><figcaption>Figure 3.4 – Traversée de la CCSP : tous les rayons primaires partent du même volume ($V_1$) contenant la caméra ; ils sont propagés s’ils touchent une face non occultante (N.O.) ou arrêtés sinon. Par exemple, le rayon $r_1$ frappe directement une face de $V_1$ ayant la sémantique WALLPAPER, tandis que $r_4$ passe par deux faces N.O. avant d’être propagé dans $V_3$.</figcaption></figure>
Traverser la structure et tester les intersections de rayons aboutit à la même opération : déterminer la face de sortie d'un rayon à l'intérieur d'un volume donné. Les volumes étant convexes, la face de sortie est unique. Si cette face est occultante, alors le rayon est arrêté et l'intersection est retournée. Si cette face est non occultante, le rayon se propage à travers le volume voisin, connu par $\alpha_3$ (information topologique de dimension 3). La figure 3.4 illustre le parcours de plusieurs rayons au travers d'une scène 3D. L'algorithme de traversée a une complexité temporelle qui est linéaire dans le nombre de volumes traversés par le rayon.

Par sa simplicité, cet algorithme cache en fait deux points essentiels. Le premier concerne la recherche du volume de départ du rayon. Le second problème, le plus important, réside dans la recherche de la face de sortie d'un rayon à l'intérieur d'un volume.

## Localisation du point d'origine des rayons

Dans un moteur de lancé de rayons, nous distinguons deux types de rayons distincts. Les rayons primaires issus de la caméra vers la scène 3D, et les rayons secondaires qui permettent de calculer les interactions lumineuses entre les objets (ombrage, réflexion, réfraction, etc.). Pour les rayons primaires, en supposant que la caméra se trouve dans le domaine de partition, plusieurs solutions sont envisageables pour localiser le volume contenant l'origine de la caméra (et donc l'origine de tous les rayons primaires). Une méthode naïve consiste à tester un à un tous les volumes de la partition. Cette méthode peut être accélérée en utilisant une grille de subdivision ou un Kd tree. Dans tous les cas, la localisation de l'origine du rayon dépend du nombre global de volumes composant la partition. Dans le cas d'un modèle de caméra avec des origines de rayon perturbées ou lorsque la caméra est déplacée, le mouvement correspond à une translation. Ainsi, une variante de l'algorithme de traversée CCSP résout efficacement ce problème.

Finalement, pour une application interactive, le temps de calcul pour la localisation du volume d'origine reste négligeable, d'autant plus que ce calcul n'est réalisé que pour la première image. Par ailleurs, que ce soit sur le CPU ou le GPU, les expériences montrent que les performances ne sont pas affectées lorsque la caméra est déplacée.

Pour les rayons non primaires, la localisation de l'origine du rayon est évitée en exploitant la connectivité implicite des rayons à l'intérieur de la CCSP. En effet, le point de départ et le volume correspondent tous deux à l'arrivée des rayons précédents. Comme indiqué dans la section 2.1.1, les structures d'acélération hiérarchiques nécessitent de recommencer la traversée depuis la racine, et l'exploitation de la connectivité des rayons reste une tâche difficile. Au contraire, à l'aide d'une CCSP, une fois l'origine des rayons primaires déterminée, le calcul d'un chemin de lumière ne consiste qu'à rechercher sa face de sortie à l'intérieur d'un volume.

## Recherche de la face de sortie

Les volumes qui composent la CCSP sont convexes, un rayon traverse au maximum une face orientée d'un volume donné. L'approche proposée est divisée en deux étapes (cf. Algorithme 3.1). Le volume est considéré comme un polyèdre infini, en ignorant les faces supérieures et inférieures. La première étape détermine la section infinie de sortie (ligne 2-5). Cette recherche balaie les arêtes incidentes à la face inférieure en utilisant les liaisons topologiques $\alpha_0$ et $\alpha_1$. Ainsi, les arêtes de la face inférieures sont balayées, chacune correspondant à une section verticale infinie délimitée par deux lignes orientées (cf. figure 3.5.a). Ces arêtes sont balayées linéairement, compte tenu du faible nombre de sections par volume, un balayage plus complexe (comme la recherche binaire) n'est pas nécessaire.
**Algorithme 3.1** Recherche de la face de sortie pour un rayon dans un volume

**ENTRÉE:** $V$: volume; $r$: rayon;

1. $\{1^{re}$ étape : section infinie de sortie\}

2. $i \leftarrow 0$;

3. **Tant que** ( side( $r$, $V.sec[i].left$ ) $\le$ 0 
               || side( $r$, $V.sec[i].right$ ) $> 0$ ) **faire**

4. $i \leftarrow i + 1$;

5. **Fin Tant que**

6. $\{2^{me}$ étape : face de sortie de la section infinie $i$\}

7. $f \leftarrow V.sec[i].faces$;

8. **Si** side( $r$, $f[0].line$ ) $< 0$ **alors**

9. **return** $f[0]$; $\{\text{traverse le sol}\}$

10. **Fin si**

11. **pour** $k = 1$ to $V.sec[i].nbFaces$ **faire**

12. **Si** side( $r$, $f[k].line$ ) $< 0$ **alors**

13. **return** $f[k]$;

14. **Fin si**

15. **fin pour**

16. $\{\text{Sortie par le plafond}\}$

17. **return** $V.plafond$;

La deuxième et dernière étape de l’algorithme consiste à trouver la face de sortie parmi celles qui composent la section verticale infinie de sortie (incluant le sol et le plafond). Chacune de ces faces est délimitée par deux lignes orientées de droite à gauche (direction trigonométrique depuis l’intérieur du volume). Encore une fois, une recherche non linéaire n’est pas nécessaire grâce au faible nombre de faces composant une section verticale. Ainsi, cette recherche se fait linéairement de bas en haut en utilisant les relations topologiques de dimension 2 qui connectent les faces, les $\alpha_2$, (cf. figure 3.5.b). La face de sortie est trouvée lorsque le rayon passe sous les lignes de délimitation supérieures.

<figure><img src="image_30.png" /><figcaption>Figure 3.5 – Recherche de la face de sortie d'un volume pour un rayon donné (a) recherche de la section verticale infinie contenant la face de sortie ; (b) Recherche de la face de sortie à l'intérieur de la section.</figcaption></figure>
En résumé, le parcours de la structure est optimisé en utilisant les relations topologiques dans toutes les dimensions :

* $\alpha_0$ et $\alpha_1$ pour balayer les arêtes incidentes à la face inférieure d'un volume et trouver la section infinie de sortie;

* $\alpha_2$ pour balayer les faces à l'intérieur d'une section infinie et déterminer la face de sortie;

* $\alpha_3$ pour propager un rayon d'un volume à son voisin lors de la traversée d'une face non occultante.

Pour réduire le nombre d'opérations nécessaire au calcul de la face de sortie, nous utilisons l'espace de Plücker, présenté par Julius Plücker au 19ème siècle [132]. Les coordonnées de Plücker sont une paramétrisation analytique des droites de l'espace tridimensionnel dans un espace projectif $\mathbb{P}^5$, appelé espace des droites ou encore espace de Plücker par abus de langage. Elles procurent un cadre analytique pour réaliser des calculs sur des droites et des ensembles de droites.

L'espace de Plücker est couramment utilisé en informatique graphique, car il permet notamment de spécifier facilement la position de vecteurs les uns par rapport aux autres dans l'espace 3D. Par exemple, dans [112, 156], cet espace est utilisé pour définir les intersections entre les rayons et des polygones convexes ou des boîtes englobantes d'objets. Nous souhaitons utiliser la paramétrisation de Plücker pour définir la position relative de deux droites dans l'espace 3D via l'opérateur *side* (cf. figure 3.6). Cet opérateur est défini comme le produit interne permuté des deux lignes de coordonnées de Plücker [147]. Les lignes délimitant une section infinie sont orientées de bas en haut. En utilisant les coordonnées de Plücker, le test d'intersection rayon/section est très rapide puisqu'il ne nécessite que deux tests d'orientation : un rayon passe par une section si et seulement s'il passe par la ligne de délimitation droite (*resp.* la gauche) ou gauche (*resp.* la droite) (cf. figure 3.5.a).

<figure><img src="image_31.png" /><figcaption>Figure 3.6 – Calcul de l'orientation relative de deux droites à partir de l'opérateur *side* et de leurs coordonnées de Plücker : (a) $\Pi_L \odot \Pi_M > 0$ ; (b) $\Pi_L \odot \Pi_M = 0$ ; (c) $\Pi_L \odot \Pi_M < 0$.</figcaption></figure>

Pour un cube simple composé de 6 faces, une méthode naïve effectuerait au pire 24 opérations *side* (4 × 6 faces) pour détecter la face de sortie d'un rayon donné. Avec notre stratégie, le pire cas est atteint en effectuant 10 opérations *side* (2 × 4 sections infinies + 2 lignes). L'ordonnancement de nos calculs, guidés par les relations topologiques contenu dans la CCSP, permet de réduire fortement le nombre d'opérations Plücker *side* nécessaire au calcul de la face de sortie.
### 3.2.2 Utilisation étendue de la structure CCSP

La gestion de rayons secondaires avec notre structure d'accélération est un problème simple. Chaque rayon suit le même algorithme de traversée (cf. section 3.2.1). Le coût de la traversée d'un rayon secondaire est identique au lancé d'un rayon primaire. La seule différence concerne le volume de départ qui est directement connu grâce à la connectivité implicite des rayons. À partir de ce constat, nous pouvons utiliser notre structure pour calculer l'éclairage direct à partir de sources lumineuses ponctuelles.

Nous proposons également d'ajouter du mobilier dans les scènes 3D. Pour cela, nous utilisons notre CCSP avec un niveau de hiérarchie pour gérer l'inclusion des objets. L'objectif principal de ces extensions est d'évaluer la robustesse de notre structure d'accélération, notamment son comportement en cas d'utilisation d'un grand nombre de rayons incohérents à travers des scènes architecturales meublées complexes.

#### Eclairement direct

Une approche naïve de l'éclairage direct implique de tracer autant de rayons d'ombre que de sources lumineuses ponctuelles dans la scène. Pour les environnements architecturaux, une telle approche conduit à des taux de rafraîchissement médiocres étant donné le nombre important de sources lumineuses. Néanmoins, étant donné qu'un bâtiment est composé de grandes surfaces occultantes, la plupart des tests de visibilité effectués sont inutiles. Pour éviter ce problème, l'ensemble potentiellement visible (PVS) des sources lumineuses de chaque volume est calculé [157].

<figure><img src="image_32.png" /><figcaption>Figure 3.7 – Calcul de visibilité et zones visibles (PVS) : (a) un bâtiment composé de neuf volumes et d'une source lumineuse L ; (b) calcul du PVS : la source lumineuse est ajoutée au PVS des volumes traversés par le faisceau issu de L ; le PVS des volumes $V_3$ et $V_4$ ne contient pas L.</figcaption></figure>

Le PVS des sources lumineuses doit être calculé pour chaque volume de la partition spatiale. Pour cette étape, nous avons résolu le calcul du PVS en inversant le problème pour réduire le temps de calcul. Ainsi, pour une source lumineuse donnée, un faisceau continu est projeté à travers chaque ouverture du volume qui la contient ; puis, ce faisceau est propagé dans la scène pour ajouter la source lumineuse au PVS de chaque volume traversé (cf. figure 3.7). Cette amélioration permet de connaître directement l'ensemble des sources lumineuses visible pour chacune des pièces.
3.2.3 Gestion du mobilier

Pour ajouter du mobilier dans les scènes architecturales, une méthode d'ameublement automatique a été ajoutée à MokaArchi. Les objets sont assimilés à leur boîte englobante et sont placés de manière cohérente dans les pièces. Par exemple : les étagères sont placées le long des murs, les chaises autour des tables, etc. La boîte englobante de l'objet est ajoutée dans le modèle comme un volume à part entière avec une sémantique distincte (OBJECT).

Pour respecter la contrainte de convexité, le volume initial (contenant la boîte englobante de l'objet) est subdivisé. Les volumes résultants conservent leur sémantique originale et sont séparés par des faces non occultantes pour produire la CCSP correspondante (cf. figure 3.8).

<figure><img src="image_33.png" /><figcaption>Figure 3.8 – Inclusion d'objets dans une CCSP : (a) illustration en 2D : le volume englobant $V_O$ de l'objet $O$ est inclus dans la région $R$ ; $R$ est subdivisée en régions convexes $R_1, R_2, R_3$ et $R_4$ ; (b) illustration en 3D : un volume vide ($V_O^v$) est créé au dessus de $V_O$ ; (c) graphe associé : le noeud correspondant à la région $R$ est subdivisé ; $R_O$ (représentant $V_O$) est associée à une structure accélératrice classique construite à partir des primitives de $O$.</figcaption></figure>

Pour un rendu rapide, la traversée des objets peut être optimisée en utilisant n'importe quelle structure accélératrice secondaire. Ainsi, une CCSP devient une structure accélératrice à plusieurs niveaux. Lorsqu'un rayon arrive dans un volume de sémantique OBJECT, nous effectuons un changement de système de coordonnées (selon la matrice de transformation de l'instance de l'objet) avant de traverser la structure accélératrice de l'objet. Si le rayon manque l'objet, la traversée continue jusqu'à ce qu'il atteigne un polygone de la scène.

L'utilisation d'un BVH comme une structure accélératrice secondaire est une solution suffisante pour avoir une application interactive de parcours de bâtiments meublés. Nous proposons dans la section 3.4 une méthode permettant d'associer une CCSP à un objet quelconque.
## 3.3 Résultats et discussion

Les scènes utilisées pour évaluer ce travail correspondent à des bâtiments réels conçus à partir de leurs plans architecturaux 2D. Ces environnements virtuels 3D sont directement générés à partir de notre modeleur topologique dédié aux environnements architecturaux (cf. section 3.1.2). Le tableau 3.1 résume leurs principales caractéristiques, notamment les temps de génération et l'occupation mémoire. Ce panel présente des scènes de test plus ou moins complexes en termes de nombre de polygones, de sources de lumière et d'objets (cf. figures 3.9 et 3.10).

<table><caption>TABLE 3.1 – Caractéristiques des scènes de tests : nombre de pièces, de volumes, de polygones, de lumières, temps de construction de la structure CCSP à partir de la GMapArchi (single core CPU) et occupation mémoire de la CCSP en Moctets.</caption><thead><tr><th rowspan="2">Scènes</th><th rowspan="2"># Pièces</th><th colspan="2"># Volumes</th><th colspan="2"># Polygones</th><th rowspan="2"># Lumières</th><th rowspan="2">Construction<br>en ms</th><th colspan="2"># Mémoire</th></tr><tr><th>(vide)</th><th>(meublé)</th><th>(vide)</th><th>(meublé)</th><th>(vide)</th><th>(meublé)</th></tr></thead><tbody><tr><td>ATRIUM</td><td>5</td><td>343</td><td>343</td><td>2,022</td><td>525,710</td><td>1</td><td>7.7</td><td>0.7</td><td>20.5</td></tr><tr><td>HOUSE</td><td>8</td><td>510</td><td>577</td><td>1,166</td><td>1,005,454</td><td>8</td><td>7.46</td><td>0.45</td><td>72.67</td></tr><tr><td>LAB</td><td>46</td><td>1,923</td><td>2,510</td><td>8,557</td><td>8,956,708</td><td>55</td><td>51.43</td><td>2.03</td><td>20.8</td></tr><tr><td>ADMIN</td><td>451</td><td>7,724</td><td>13,752</td><td>59,682</td><td>58,660,932</td><td>649</td><td>116.36</td><td>7.36</td><td>66.3</td></tr><tr><td>TOWER</td><td>2,209</td><td>94,345</td><td>120,534</td><td>496,057</td><td>356,242,576</td><td>3211</td><td>1929.9</td><td>108.9</td><td>173.6</td></tr></tbody></table>

Comme expliqué dans la section 3.1.2, la CCSP est directement déduite par un simple parcours d'une GMapArchi. Néanmoins, étant donné qu'elle contient beaucoup d'informations inutiles pour notre méthode, elle est allégée pour réduire le coût mémoire en conservant uniquement les informations nécessaires. La colonne "construction" de tableau 3.1 indique le temps correspondant à ce traitement.

<figure><img src="image_34.png" /><figcaption>Figure 3.9 – Exemple de rendu de nos scènes de test.</figcaption></figure>

### 3.3.1 Système d’évaluation des performances

Pour évaluer les performances et la robustesse de notre structure, nous l’avons utilisée pour huit méthodes de rendu soit sur CPU, soit sur GPU :

* Trois méthodes sur le CPU, (un seul coeur (S) ou parallélisées avec OpenMP (P) avec implémentation simple : *Ray casting* est un ray casting primaire. *Packets* exploite les instructions Intel SSE et regroupe les rayons primaires en paquets pour profiter de la cohérence spatiale. *Packets Lighting* utilise également des paquets pour les rayons primaires et les rayons d’ombre dure.

* Cinq méthodes sur GPU, parallélisées avec CUDA (en utilisant la technique des threads persistants [2]): *Ray casting* est un Ray casting primaire. *Lighting* utilise des rayons secondaires pour les ombres dures. *Traçage de chemin* qui implémente un traceur de chemin avec 5 rebonds par chemin (plus de détails dans section 3.3.3). *Objects* et *Objects Lighting* étendent respectivement *Ray casting* et *Lighting* pour les scènes meublées.
Les performances ont été évaluées sur une machine équipée d'un processeur Intel® Core™ i7-4930K CPU @ 3.40Ghz, 32 Go de RAM et une carte graphique NVidia® GeForce® GTX 680. Les images rendues ont une définition de 1024 × 1024 pixels sans anticrénelage (un seul rayon est lancé par pixel). Pour disposer de statistiques pertinentes, nous avons utilisé un système de way-point afin de conserver les mêmes points de vue pour chaque algorithme testé. Ces points de vue résultent d'un parcours dans chaque scène. Les performances sont mesurées en termes de :

* FPS : nombre d'images calculées par seconde comprenant la génération de rayons, le traçage de rayons, l'ombrage et le remplissage du tampon d'image (le temps d'affichage n'est pas inclus).

* Mrays/s : nombre de millions de rayons traités par seconde; correspond au nombre de rayons émis par image multiplié par FPS.

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /><figcaption>Figure 3.10 – Plans 2D correspondant à des étages de scènes de test; les meubles sont représentés ici par des boites englobantes en rouge : (a) un étage de la scène ADMIN; (b) un étage de la scène TOWER.</figcaption></figure>

<table><caption>TABLE 3.2 – Résultats : nombre moyen d'images par seconde (FPS) et moyenne en million du nombre de rayons traités par seconde (Mrays/s).</caption><thead><tr><th rowspan="2">Méthodes</th><th rowspan="2"></th><th colspan="2">HOUSE</th><th colspan="2">LAB</th><th colspan="2">ADMIN</th><th colspan="2">TOWER</th></tr><tr><th>FPS</th><th>Mrays/s</th><th>FPS</th><th>Mrays/s</th><th>FPS</th><th>Mrays/s</th><th>FPS</th><th>Mrays/s</th></tr></thead><tbody><tr><td rowspan="5">CPU</td><td>Ray casting (S)</td><td>21.57</td><td>22.62</td><td>24.11</td><td>25.28</td><td>21.09</td><td>22.11</td><td>17.66</td><td>18.51</td></tr><tr><td>Packet casting (P)</td><td>123.06</td><td>129.04</td><td>131.03</td><td>137.39</td><td>117.16</td><td>122.85</td><td>92.75</td><td>97.25</td></tr><tr><td>Packet casting (S)</td><td>135.94</td><td>142.54</td><td>136.51</td><td>143.14</td><td>128.13</td><td>130.16</td><td>132.64</td><td>139.08</td></tr><tr><td>Packet &amp; Lighting (P)</td><td>435.89</td><td>457.06</td><td>454.05</td><td>476.11</td><td>423.27</td><td>443.83</td><td>394.55</td><td>413.71</td></tr><tr><td>Packet &amp; Lighting (S)</td><td>47.21</td><td>154.56</td><td>24.53</td><td>135.09</td><td>8.63</td><td>146.68</td><td>21.52</td><td>154.07</td></tr><tr><td>Packet &amp; Lighting (P)</td><td>180.36</td><td>590.46</td><td>100.08</td><td>551.22</td><td>38.91</td><td>661.09</td><td>76.19</td><td>545.42</td></tr><tr><td rowspan="5">GPU</td><td>Ray casting</td><td>1,389.16</td><td>1,445.66</td><td>1,064.71</td><td>1,116.43</td><td>1,219.92</td><td>1,279.18</td><td>1,096.61</td><td>1,149.87</td></tr><tr><td>Lighting</td><td>439.47</td><td>1,438.59</td><td>179.54</td><td>988.88</td><td>64.99</td><td>1,104.61</td><td>145.49</td><td>1,041.96</td></tr><tr><td>Path tracing</td><td>18.57</td><td>218.87</td><td>9.79</td><td>206.34</td><td>12.01</td><td>533.58</td><td>9.08</td><td>211.11</td></tr><tr><td>Objects</td><td>191.39</td><td>200.69</td><td>245.77</td><td>257.7</td><td>456.57</td><td>478.75</td><td>237.32</td><td>248.85</td></tr><tr><td>Objects &amp; Lighting</td><td>58.28</td><td>163.48</td><td>28.13</td><td>183.12</td><td>19.06</td><td>289.85</td><td>25.63</td><td>163.21</td></tr></tbody></table>
3.3.2 Etude de la complexité du calcul des rayons

Une particularité des méthodes de lancé de rayons dans une CCSP est que la complexité du calcul de parcours est linéaire par rapport au nombre de volumes traversés par le rayon. Comparer la complexité de traversée de CCSP avec des structures accélératrices habituelles telles qu'un Kd-tree ou un BVH n'est pas une tâche triviale. En effet, la recherche de la plus proche intersection dans de telles structures hiérarchiques nécessite de traverser l'arbre depuis la racine avant de tester l'intersection des rayons pour chaque feuille visitée. Le nombre d'étapes de traversée est au mieux logarithmique à la taille de l'arbre. En revanche, avec un CCSP, aucun test d'intersection rayon/polygone n'est réellement effectué et la recherche de la face de sortie est suffisante pour déterminer la plus proche intersection. Cela suppose que le temps de localisation de l'origine du rayon est négligeable (cf. section 3.2.1). La complexité de la traversée est linéaire par rapport au nombre global de volumes composant la partition. Ainsi, dans le meilleur des cas, un seul volume doit être traversé. À l'inverse, une scène composée d'un long couloir fortement divisé à un temps de traitement un peu plus long. En pratique, le nombre de volumes traversés par rayon reste assez faible.

La figure 3.11 montre la relation entre le FPS et le nombre moyen de volumes traversés par les rayons (noté Φ). Les statistiques présentées sont mesurées sur GPU et extraites d'un parcours dans la scène AD-MIN. La courbe de tendance révèle clairement que les performances sont inversement proportionnelles au nombre de volumes traversés. Il est donc primordial d'utiliser une stratégie bien adaptée pour convexifier la scène tout en minimisant le nombre moyen de volumes traversés par un rayon.

<figure><img src="image_37.png" /><figcaption>Figure 3.11 – Temps de rendu en ms (T, courbe rouge) et nombre de volumes traversés exprimé en millions (Φ, histogramme gris) pour l’algorithme Ray casting avec 1 082 points de vue extraits durant une visite d’un étage du bâtiment ADMIN : depuis le point de vue (A), les rayons traversent un long couloir contenant des murs courbes concaves et donc beaucoup plus de volumes que depuis le point de vue (B).</figcaption></figure>
### 3.3.3 Analyse comparative des méthodes

#### Ray casting

Le tableau 3.3 révèle que notre structure CCSP permet une gestion des rayons primaire très efficace que ce soit sur le CPU ou sur le GPU. Elle projette près de cinq cents millions de rayons primaires par seconde sur le CPU (Packet casting (P)) et plus d'un milliard sur le GPU. Le tableau 3.3 compare ces résultats avec ceux mesurés avec le moteur Embree [168], et avec le moteur proposé par Aila de Nvidia [3].

<table><caption>TABLE 3.3 – Comparaisons entre notre raycasting et Embree [168] (CPU) et l'application de Aila et al. [3] (GPU) : performance en images par seconde et occupation mémoire en Moctet.</caption><thead><tr><th></th><th></th><th>HOUSE</th><th>LAB</th><th>ADMIN</th><th>TOWER</th></tr></thead><tbody><tr><td rowspan="3">CPU</td><td>Notre Ray Tracing</td><td>123.06</td><td>131.03</td><td>117.16</td><td>92.75</td></tr><tr><td>Notre Packets Tracing</td><td>435.89</td><td>454.05</td><td>423.57</td><td>394.55</td></tr><tr><td>Embree</td><td>≈ 32</td><td>≈ 21</td><td>≈ 29</td><td>≈ 14</td></tr><tr><td rowspan="2">GPU</td><td>Notre Ray Tracing</td><td>1,389.16</td><td>1,064.71</td><td>1,219.92</td><td>1,096.61</td></tr><tr><td>Aila</td><td>220-240</td><td>170-230</td><td>200-240</td><td>150-210</td></tr><tr><td rowspan="3">Mem.</td><td>Notre structure</td><td>0.45</td><td>2.03</td><td>7.36</td><td>108.9</td></tr><tr><td>Embree</td><td>0.5</td><td>1.8</td><td>6.7</td><td>77.7</td></tr><tr><td>Aila</td><td>0.49</td><td>3.44</td><td>9.28</td><td>135.73</td></tr></tbody></table>

Cette comparaison révèle clairement que notre approche est plus performante que ces moteurs de lancé de rayons de pointe, que ce soit sur le CPU ou sur le GPU. Cependant, elle doit être prise avec précaution. En effet, le CCSP est particulièrement bien adapté aux scènes architecturales : elles sont composées de grandes surfaces occultantes, de sorte qu'un rayon donné n'a qu'à traverser quelques volumes pour trouver la plus proche intersection de rayons. De plus, la recherche de face de sortie est conçue pour les scènes architecturales, et utilise des informations topologiques dans toutes les dimensions. Même si cette haute performance ne prouve pas que la partition d'espace sous contrainte est une structure d'accélération alternative, elle révèle que cette approche mérite d'être explorée davantage.

#### Path tracing

Le tableau 3.2 montre les résultats de notre algorithme utilisé pour du tracé de chemins sur GPU. Nous pouvons remarquer l'écart de performance entre l'éclairage direct et le tracé de chemin en ce qui concerne le nombre de rayons projetés par seconde (perte de près de 75 %). Cette perte s'explique d'une part parce que la performance mesurée inclut le temps nécessaire pour générer des directions aléatoires pour les rebonds et pour choisir aléatoirement la source lumineuse testée. D'autre part, elle est due à l'exécution divergente au sein de chaque warp GPU. En effet, notre moteur est assez naïf, puisqu'il calcule chaque chemin l'un après l'autre sans stratégie spécifique de distribution des tâches.

#### Visualisation de scènes meublées

Comme illustré dans section 3.2.3, n'importe quelle structure d'accélération secondaire peut être utilisée pour rendre des objets tels que des meubles. En pratique, nous utilisons un BVH. Étant donné qu'un même objet peut apparaître plus d'une fois dans une scène, nous utilisons un système d'instanciation des objets pour réduire la consommation de mémoire.
Nous comparons nos performances à l'application de lancé de rayons sur GPU proposée par Aila [3]. Si nous bénéficions d'un système d'instanciation des objets pour économiser la consommation de mémoire, leur implémentation n'en fournit pas. Par conséquent, nous ne pouvons comparer les performances que sur la scène HOUSE, seule scène logeable en mémoire sans installation et pour laquelle nous sommes plus performants. En ce qui concerne l'éclairage avec la prise en compte des objets, nous avons enregistré en moyenne 32,77 FPS et 199,91 Mrays/s. Une fois encore, en termes de Mrays/s, les performances de notre structure restent stables.

Même si l'utilisation d'une structure secondaire de type BVH est une solution suffisante pour disposer d'une application interactive de visite de bâtiments meublés, elle constitue également un inconvénient majeur de l'approche proposée. Dans le cas des scènes meublées, les performances des méthodes de lancé de rayons dépendent directement de la structure accélératrice utilisée pour le rendu des objets. De plus, le passage d'une structure d'accélération à l'autre entraîne une divergence sur le GPU, ce qui ralentit le rendu. Du côté positif, le CCSP permet d'éviter de gérer toute la géométrie du mobilier.

### 3.3.4 Bilan

L'utilisation d'une CCSP comme structure accélératrice pour les méthodes de lancé de rayons offre plusieurs propriétés intéressantes : sa traversée a une complexité linéaire en nombre de volumes traités ; la traversée du CCSP donne l'intersection la plus proche, et aucun autre test d'intersection n'est nécessaire ; elle exploite implicitement la connectivité entre les rayons dans la construction des chemins de lumière ; elle fournit des informations topologiques dans toutes les dimensions, optimisant la recherche de la face de sortie ; enfin, elle est bien adaptée à une utilisation parallèle sur CPU ou GPU.

Nos expérimentations montrent l'efficacité de la méthode, même pour des scènes meublées composées de plusieurs centaines de millions de polygones avec le calcul de centaines de millions de rayons par seconde.

## 3.4 Visualisation topologique : généralisation

Le principal inconvénient de l'approche proposée pour la visualisation de bâtiment est qu'elle nécessite la description complète de la topologie pour construire une structure CCSP. Même si le modeleur MokaArchi fournit toutes ces informations, notre structure ne peut pas être utilisée avec une entrée purement géométrique. Par conséquent, nous avons souhaité appliquer la CCSP à tout type d'environnement, décrit uniquement par sa géométrie.

Cette généralisation repose sur trois points clés principaux. Premièrement, il est nécessaire de reconstruire la topologie d'une scène à partir de sa description géométrique. Ce processus n'est pas une tâche triviale puisqu'il doit traiter les incohérences géométriques telles que les éléments dégénérés et les problèmes de corafinement 3D. Ensuite, une partition d'espace convexe contraint en 3D doit être construite, en utilisant la description topologique et géométrique, afin de l'utiliser comme structure d'accélération dédiée au lancé de rayons. Ce processus nécessitera la recherche d'une heuristique bien adaptée minimisant le coût moyen de traversée d'un rayon donné à travers la CCSP. Enfin, un algorithme de recherche de face de sortie efficace et général doit être conçu.

La généralisation de la CCSP aux objets quelconques nécessite une méthode de décomposition convexe de polyèdres 3D. Fortune a introduit ce concept en proposant un traçage topologique du faisceau utilisant une subdivision convexe acyclique respectant les obstacles de la scène [49]. En 2008, Lagae et Dutré ont proposé d'utiliser une tétraédrisation de Delaunay contrainte (que nous nommerons CDT dans la suite du manuscrit) comme structure d'accélération pour le lancer de rayons [96].
Au cours de la thèse de Maxime Maria, nous avons étendu ce dernier travail pour proposer un nou-
vel algorithme de traversée de CDT. Celui-ci est basé sur une manière spécifique de représenter et de
traverser les tétraèdres (issu de la description topologique). Il est intrinsèquement plus efficace puisqu’il
nécessite moins d’opérations arithmétiques. Ensuite, il est plus adapté à la programmation parallèle puis-
qu’il n’ajoute pas de divergence supplémentaire. Enfin, il est robuste et ne provoque aucune erreur due à
une instabilité numérique, que ce soit sur le CPU ou sur le GPU.

**3.4.1 Construction de la CDT**

Une CDT ne peut pas être construite à partir de tous les modèles géométriques d'entrée. Une condi-
tion suffisante est que le modèle géométrique d'entrée soit un complexe linéaire par morceaux (PLC) [119].
En 3D, toute intersection non vide entre deux faces d'un PLC doit correspondre à une arête ou un sommet
partagé. En d'autres termes, il n'y a pas d'intersection entre les primitives géométriques.

En infographie, une scène est généralement représentée comme un ensemble non structuré de poly-
gones, communément appelé soupe de polygones. Dans ce cas, certaines intersections peuvent exister.
Néanmoins, il est possible de construire un PLC à partir d'une telle représentation géométrique, en util-
sant une technique de réparation de maillage. Ce point sera traité dans le chapitre 5.

À partir d'un PLC, la CDT peut être construite en utilisant la bibliothèque *Tetgen* [77]<fnref n="1" />. Il en résulte un maillage tétraédrique, contenant deux types de faces : les faces occultantes, appartenant à la géométrie de la scène ; et de faces non occultantes, introduites pour construire la partition. Évidemment, un rayon donné doit traverser ces dernières, car une face non occultante n'appartient pas à la géométrie d'entrée.

**3.4.2 Traversée de la CDT**

Comme nous l'avons vu précédemment pour l'utilisation d'une CCSP comme structure d'accéléra-
tion, la recherche de l'intersection la plus proche entre un rayon et la géométrie de la scène s'effectue en
deux étapes principales : (1) le volume contenant l'origine du rayon est localisé (ici un tétraèdre) ; (2) le
rayon traverse la CDT en parcourant un tétraèdre à la fois jusqu'à ce qu'il rencontre une face occultante.

Pour une application interactive, la localisation de l'origine reste un problème négligeable, puis-
qu'elle n'apparaît que pour la première image. Ensuite, une variante de l'algorithme de traversée (prenant
en compte une distance maximale) résout efficacement ce problème lors du déplacement de la caméra.
La localisation de l'origine des rayons non primaires est évitée en exploitant la connectivité implicite
des rayons dans le CDT : le point de départ et le volume correspondent tous deux à l'arrivée du rayon
précédent.

L'algorithme de traversée de la CDT repose sur une boucle, et recherche la face de sortie d'un rayon depuis l'intérieur d'un tétraèdre. Nous proposons une nouvelle méthode rapide et robuste pour résoudre le problème de la face de sortie. Les tests sont ordonnancés en utilisant les informations topologiques du modèle et les calculs sont réduits en utilisant une nouvelle fois les coordonnées de Plücker (cf. section 3.2.1) pour déduire le positionnement du rayon par rapport aux bords des faces.

Recherche de la face de sortie

Notre algorithme suppose que la face d'entrée est connue, le rayon provient du tétraèdre précédent et
il traverse le tétraèdre actuel. C'est pourquoi, pour une face d'entrée donnée, son complémentaire dans
le tétraèdre est utilisé : un sommet, trois arêtes et trois faces.

<footnote n="1">1. *TetGen* est un programme permettant de générer des maillages tétraédriques à partir de données polyédrique 3D</footnote>
**Algorithme 3.2** Recherche de la face de sortie à l'intérieur d'un tétraèdre

**ENTRÉE:** $F_e = \{S, \Lambda_0, \Lambda_1, \Lambda_2\}$ : Face d'entrée ; $\Lambda_r$: rayon ;

**SORTIE:** $F_s$: face de sortie;

1. side $\leftarrow \Lambda_r \otimes F_e \cdot \Lambda_2$;

2. id $\leftarrow$ (side $\ge$ 0); $\{id \in \{0, 1\}\}$

3. side $\leftarrow \Lambda_r \otimes F_e \cdot \Lambda_{id}$;

4. id $\leftarrow$ id + (side < 0); $\{id \in \{0, 1, 2\}\}$

5. $F_s \leftarrow \text{getFace}(F_e,id)$;

6. **return** $F_s$;

$\Lambda_0, \Lambda_1$ et $\Lambda_2$ sont désignés pour représenter les arêtes complémentaires (qui ne sont pas incidentes à la face d'entrée), avec une orientation dans le sens antihoraire depuis l'intérieur du tétraèdre (cf. figure 3.12). Les faces complémentaires sont désignées par un identifiant local 0, 1 et 2, en utilisant la convention suivante : la face 0 est délimitée par les arêtes $\Lambda_2$ et $\Lambda_0$. La face 1 est délimitée par les arêtes $\Lambda_0$ et $\Lambda_1$. La face 2 est délimitée par les arêtes $\Lambda_1$ et $\Lambda_2$.

En utilisant l'opérateur de *side* de Plücker, la face traversée par $r$ est déterminée :

- face 0 si et seulement si $r \otimes \Lambda_2 < 0$ et $r \otimes \Lambda_0 \ge 0$ (cf. figure 3.12.d);

- face 1 si et seulement si $r \otimes \Lambda_0 < 0$ et $r \otimes \Lambda_1 \ge 0$;

- face 2 si et seulement si $r \otimes \Lambda_1 < 0$ et $r \otimes \Lambda_2 \ge 0$.

<figure><img src="image_38.png" /><figcaption>Figure 3.12 – Description et traversée d'un tétraèdre : (a) numérotation des sommets et des faces ; (b) à titre d'exemple, le sommet complémentaire de $F_3$ est $\{V_3\}$, et ses arêtes sont $\Lambda_0 = V_1V_3$, $\Lambda_1 = V_0V_3$ et $\Lambda_2 = V_2V_3$. (c) Le rayon $r$ entre dans le tétraèdre par la face arrière ; (d) $r \otimes \Lambda_2 < 0$ et $r \otimes \Lambda_0 \ge 0$, donc la face de sortie est identifiée par 0.</figcaption></figure>

Ces conditions sont organisées dans un arbre de décision (cf. figure 3.12.d). Chaque feuille correspond à une face de sortie, et chaque noeud intérieur répond à un opérateur *side* entre le rayon $r$ et les arêtes $\Lambda_i$. L'ordonnancement des tests est guidé par les informations topologiques de dimension 2, les liens entre les faces. Comme toutes les branches de l'arbre de décision ont une profondeur fixe de 2, l'algorithme répond en utilisant exactement deux opérations. De plus, il est optimisé pour fonctionner efficacement sans aucun *if* conditionnel (cf. Algorithme 3.2).

Cet algorithme se termine par le renvoi du numéro de la face du tétraèdre en fonction de la face d'entrée et de l'étiquette de la face de sortie $\in \{0, 1, 2\}$. Elle répond à l'aide d'une table de consultation, définie en utilisant une combinatoire simple (cf. tableau 3.4), en supposant un étiquetage cohérent des faces du tétraèdre (cf. figure 3.12.a).
<table><caption>TABLE 3.4 – Face de sortie en fonction de l'identifiant de la face d'entrée $\in \{0, 1, 2\}$, et selon une numérotation cohérente des faces (cf. figure 3.12.a).</caption><thead><tr><th rowspan="2">Identifiant de sortie</th><th colspan="4">Face d'entrée</th></tr><tr><th>F<sub>0</sub></th><th>F<sub>1</sub></th><th>F<sub>2</sub></th><th>F<sub>3</sub></th></tr></thead><tbody><tr><td>0</td><td>F<sub>1</sub></td><td>F<sub>0</sub></td><td>F<sub>0</sub></td><td>F<sub>0</sub></td></tr><tr><td>1</td><td>F<sub>2</sub></td><td>F<sub>3</sub></td><td>F<sub>1</sub></td><td>F<sub>2</sub></td></tr><tr><td>2</td><td>F<sub>3</sub></td><td>F<sub>2</sub></td><td>F<sub>3</sub></td><td>F<sub>1</sub></td></tr></tbody></table>

<table><thead><tr><th></th><th>BANANA</th><th>BUNNY</th><th>ARMADILLO</th></tr></thead><tbody><tr><td>Tetrahèdre</td><td>71,300</td><td>682,733</td><td>2,990,552</td></tr><tr><td>faces occultantes</td><td>24,568</td><td>222,775</td><td>1,105,218</td></tr><tr><td>faces non-occultantes</td><td>117,994</td><td>1,142,650</td><td>4,875,834</td></tr><tr><td>Memoire (MB)</td><td>6</td><td>62</td><td>273</td></tr><tr><td>Ray-casting CPU</td><td>9.76</td><td>10.5</td><td>6.75</td></tr><tr><td>GPU</td><td>428</td><td>289</td><td>123</td></tr></tbody></table>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /><figcaption>TABLE 3.5 – Caractéristiques des scènes et performances : nombre de tétraèdres, nombre de faces occultantes (les faces provenant du modèle), nombre de faces non occultantes (les faces créées pendant la tétraédrisation), mémoire occupée et performances de lancé de rayons en millions de rayons par seconde sur le CPU et le GPU.</figcaption></figure>

### 3.4.3 Résultats

Les performances sont évaluées à l'aide de trois scènes de test. Leurs principales caractéristiques ainsi que les performances sont présentées dans le tableau 3.5. La plus simple est une banane composée de 25k faces occultantes. Les deux autres correspondent à des versions raffinées de deux scènes bien connues de l'université de Standford : BUNNY et ARMADILLO. Elles comptent respectivement 200k et 1.1M de faces occultantes.

Les performances sont mesurées en termes de millions de rayons lancés par seconde (Mrays/s), pour des images d'une définition de 1024 × 1024 pixels et sans anti-aliasing. L'ordinateur utilisé possède un processeur Intel® Core™ i7-4930K CPU @ 3.40Ghz, 32 Gb de RAM et une NVidia® GeForce® GTX 680. Les algorithmes sont rendus parallèles sur le CPU (avec OpenMP) et le GPU (avec CUDA et la technique des threads persistants [2, 3]). Sur le CPU, le lancer de rayons atteint 9 Mrays/s en moyenne, et 280 Mrays/s sur le GPU.

#### Traversée de la structure

L'intersection rayon/scène la plus proche est trouvée en traversant le CDT d'un tétraèdre à la fois jusqu'à ce qu'il rencontre une face occultante. La complexité de la traversée pour un rayon donné est linéaire dans le nombre de tétraèdres traversés. La figure 3.13 montre la relation entre le temps d'exécution ($T$) et le nombre de tétraèdres traversés par image ($\Phi$). Les statistiques sont extraites en utilisant 1282 points de vue de la scène BUNNY, sur CPU.
<figure><img src="image_42.png" /><figcaption>Figure 3.13 – Temps de rendu sur le CPU en ms (T, courbe rouge) et nombre de traversées en millions (Φ, barres grises) en utilisant 1 282 points de vue et la scène BUNNY. Points de vue et la scène BUNNY ; (A) T = 40, 1 ms Φ = 9, 6 ; (B) T = 122 ms Φ = 22, 71.</figcaption></figure>

On constate que le temps d'exécution est proportionnel à Φ : sur le point de vue (A), près de 10 millions de tétraèdres sont parcourus en 40.1 ms ; sur le point de vue (B), près de 23 millions de tétraèdres sont parcourus en 122 ms. L'image faussement colorée du point de vue (B) révèle que les rayons qui vont près de la limite de l'objet traversent plus de tétraèdres. Ces mesures montrent que la configuration du CDT a un impact direct sur les performances de traversée, et que sa construction doit être bien contrôlée.

Comparaisons

Nous n'avons pas remarqué de divergence numérique avec notre méthode. Ceci est notamment expliqué par le nombre d'opérations arithmétiques effectuées. En effet, notre algorithme nécessite moins d'opérations que les autres méthodes utilisées, de sorte que moins d'erreurs numériques sont accumulées, ce qui conduit à un résultat plus précis. En raison de l'instabilité des autres méthodes, nous ne pouvons pas comparer facilement notre algorithme avec les précédents dans le contexte du rendu d'images. Ainsi, notre algorithme est comparé avec le traceur de rayons implémenté par Aila [3]. La structure d'accélération est un BVH, construit avec SAH. Cette implémentation est, au moment de la réalisation de ce travail, la plus rapide. Le tableau 3.6 résume cette comparaison. Il faut noter la différence d'amplitude des performances entre CDT et BVH. Cet écart peut être expliqué en analysant la complexité de traversée des deux structures. La traversée de CDT a une complexité en nombre de tétraèdres traversées, de sorte que
les performances dépendent fortement du point de vue. Au contraire, la complexité de BVH dépend du nombre global de primitives géométriques composant la scène. De plus, lorsqu'elle est construite suivant SAH, ses performances sont moins impactées par le point de vue, et l'amplitude des performances est plus faible.

Pour la scène ARMADILLO, les performances de BVH sont bien supérieures à celles de CDT. Cependant, ces résultats doivent être pris avec précaution. D'une part, le BVH et les autres structures d'accélération habituelles sont étudiées depuis plusieurs décennies, alors que le CDT a été beaucoup moins étudié. D'autre part, étant donné sa complexité de traversée, la CDT est particulièrement adaptée aux scènes fortement occultées (moins les tétraèdres sont traversés, plus les performances sont élevées), ce qui n'est pas le cas avec des scènes telles que ARMADILLO.

<table><caption>TABLE 3.6 – Comparaison des performances par rapport à [3], en nombre d'images par seconde.</caption><thead><tr><th></th><th>CDT</th><th>BVH<br>[3]</th></tr></thead><tbody><tr><td>BANANA</td><td>315-947</td><td>200-260</td></tr><tr><td>BUNNY</td><td>130-1040</td><td>160-260</td></tr><tr><td>ARMADILLO</td><td>82-160</td><td>130-260</td></tr></tbody></table>

### 3.4.4 Bilan

Dans cette section, nous proposons un nouvel algorithme pour le parcours de rayons au travers d'une tétraédrisation de Delaunay Contraintes (CDT). Grâce à une manière spécifique de représenter les tétraèdres, cet algorithme offre plusieurs avantages par rapport aux précédents. Premièrement, il est intrinsèquement plus efficace puisqu'il nécessite moins d'opérations arithmétiques. Ensuite, il est plus adapté au calcul parallèle, puisqu'il comporte un nombre fixe d'opérations, de sorte qu'il n'ajoute pas de divergence supplémentaire entre les fils. Enfin, il est robuste et fonctionne avec des flottants 32 bits, que ce soit sur le CPU ou le GPU.

La complexité de la traversée des rayons d'un CDT est linéaire par rapport au nombre de tétraèdres traversés : moins il y a de tétraèdres traversés, plus les performances sont élevées. Ainsi, l'efficacité de la traversée dépend fortement de la configuration du CDT.

Notre CDT est directement construite à partir des informations géométriques et topologiques disponibles lors de la phase de modélisation. Elle contient ainsi plus d'informations topologiques que les modèles habituellement employés. Nous mettons à contribution les relations topologiques inutilisées habituellement pour le calcul d'images de synthèse avec pour objectif de réduire fortement les temps de calcul.

## 3.5 Conclusion

Dans ce premier axe de recherche, nous avons présenté comment un modèle géométrique, topologique et sémantique dédié à la modélisation architecturale peut être utilisé directement comme structure accélératrice pour une application de lancé de rayons interactif. Cette structure est basée sur une partition spatiale contrainte et convexe (CCSP). La partition est dite contrainte, car elle respecte parfaitement la géométrie de la scène, au sens où les primitives géométriques sont confondues avec les bords des volumes constituant la partition. Le parcours de la CCSP est simple et optimisé par une stratégie d'ordonnancement des traitements utilisant les relations topologiques entre les primitives de la scène. Ses performances ont été évaluées à la fois sur CPU et sur GPU et les expérimentations montrent qu'elle
surpasse largement les structures accélératrices classiques. En effet, elle permet de lancer des centaines de millions de rayons à la seconde pour des scènes architecturales composées de plusieurs centaines de millions de polygones.

Toutefois, notre processus de construction de la CCSP est basé sur une application dédiée de re-construction de scènes architecturales 3D à partir de plans numériques 2D. La visualisation par lancé de rayons est donc conditionnée par le résultat de l'application de modélisation et la possession des plans numériques d'origine. Il n'est pas possible de l'utiliser pour des scènes construites directement en 3D par un autre outil de modélisation (par exemple les scènes SodaHall, Sponza, San Miguel, etc.). C'est pourquoi nous avons poursuivi notre étude pour la visualisations d'objets quelconques.

Après avoir étudié les méthodes existantes, nous avons choisi de construire une partition topologique de l'espace basée sur une tétraédrisation de Delaunay contrainte. Cette représentation particulière des tétraèdres nous permet de proposer un algorithme de recherche de la face de sortie d'un rayon depuis l'intérieur d'un tétraèdre. Cet algorithme est plus efficace que ceux présentés dans la littérature, il utilise notamment les liens topologiques entre les faces du tétraèdre pour ordonnancer les calculs et réduire les problèmes de stabilité numérique sur CPU et GPU. Bien que les performances restent modestes par rapport à l'utilisation de structures accélératrices classiques telle qu'une hiérarchie de volumes englobants, elles ont mis en avant des perspectives de recherche intéressantes. Tout d'abord, la méthode pourrait être enrichie par une construction d'une tétraédrisation se basant sur une heuristique selon le coût de traversée des tétraèdres (type SAH).

Récemment, de nouveaux travaux ont été réalisés par U. Güdükbay et I. Wald avec pour objectif de proposer un lancé de rayons volumique basée sur la traversé d'éléments tétraédriques [6, 141]. Ces méthodes assurent une meilleure gestion des caches GPU et du stockage en mémoire permettant de gérer des environnements plus complexes. Les performances sont comparables aux méthodes de traversée basées sur les structures d'accélération de l'état de l'art telles que les Kd-tree et BVH. Les auteurs précisent toutefois que la principale limitation de l'utilisation d'une partition basée sur des tétraèdres réside dans le processus de génération de maillage tétraédrique qui est coûteux en calcul et nécessite un prétraitement où les intersections géométriques doivent être résolues pour que la géométrie résultante soit un complexe linéaire par morceaux (PLC).

À partir de ces travaux, de nombreuses perspectives de recherche restent ouvertes. Par exemple, il serait intéressant d'étudier le comportement de la CCSP pour des environnements de simulations déformables et/ou dynamiques. Si les changements géométriques ne modifient pas la topologie de la partition et respectent la contrainte de convexité, alors aucune opération n'est nécessaire (excepté la mise à jour des coordonnées géométriques) et la CCSP reste valide. Dans le cas contraire, il est nécessaire de modifier la partition. Cependant, il est possible d'exploiter la structure de graphe de la CCSP pour la modifier localement et garantir sa validité. Ainsi, la CCSP unirait les structures utilisées en modélisation, simulation et animation.

L'ensemble de ce travail nous a permis également de mettre en évidence la pertinence d'utiliser une structure topologique et hiérarchique pour gérer la répartition des primitives géométriques dans la scène. En effet, la gestion du mobilier par localisation dans des boîtes englobantes, elle même inclues dans la structure du bâtiment, nous a permis de gérer un affichage interactif pour des scènes architecturales composées de plusieurs centaines de millions de polygones. Dans la suite de ce manuscrit, nous proposons d'approfondir cette utilisation avec les problématiques de visualisation des détails fins en synthèse d'images photoréalistes.
# Publications relatives au chapitre

## Revues internationales

*Constrained Convex Space Partition for ray-tracing.*

M. Maria, S.Horna, L. Aveneau.

Computer Graphics Forum, 2015, pp. Volume 36, pages 288-300.

## Conférences internationales avec comité de lecture

*Efficient Ray Traversal of Constrained Delaunay Tetrahedralisation.*

M. Maria, S.Horna, L. Aveneau.

Conference on Computer Graphics Theory and Applications (GRAPP), 2017.

*Topological Space Partition for Fast Ray Tracing in Architectural Models.*

S. Horna, G. Damiand, A. Diakité, D. Meneveaux.

Eurographics Workshop on Urban Data Modelling and Visualisation (UDMV), 2014, pp. 13–18.

*Topological Space Partition for Fast Ray Tracing in Architectural Models.*

M. Maria, S.Horna, L. Aveneau.

Conference on Computer Graphics Theory and Applications (GRAPP), 2014.

## Conférences nationales sans comité de lecture

*Visualisation interactive de grands bâtiments.*

M. Maria, S.Horna, L. Aveneau.

Journées Françaises de l’informatique Graphique, 2013. Limoges - Meilleur papier

*Visualisation interactive de grands bâtiments.*

M. Maria, S.Horna, L. Aveneau.

Groupe de Travail Rendu, 2013. Paris
# VISUALISATION D'ARRONDIS RÉALISTES

## Sommaire

<table><tr><td>4.1</td><td>Construction de la structure accélératrice SREC-RT</td><td>55</td></tr><tr><td>4.2</td><td>Utilisation de SREC-RT en lancé de rayons</td><td>59</td></tr><tr><td>4.3</td><td>Représentation des arrondis</td><td>61</td></tr><tr><td>4.4</td><td>Résultats</td><td>64</td></tr><tr><td>4.5</td><td>Conclusion</td><td>68</td></tr></table>

Nous n'y prêtons pas une attention particulière, mais les bords des objets qui nous entourent sont systématiquement arrondis. Mis à part les objets tranchants (couteaux, lame de cutter, etc.), les extrémités des objets ne sont pas composés d'arêtes franches, un chanfrein, même très léger est toujours présent. Ces courbures sont produites lors du processus de fabrication : moulage, pliage ou encore chanfreinage. L'arrondi à un effet plus ou moins prononcé, mais dans tous les cas, sur le plan visuel, il réfléchit la lumière d'une manière bien particulière à laquelle notre sensibilité visuelle est très attachée.

En effet, la variation de l'orientation de ces surfaces produit des détails d'ombrage qui sont visuellement essentiels au réalisme des scènes synthétiques. Plus la surface est spéculaire, plus ses reflets sont fins et saillants. Les effets de lumière sur le bord des objets doivent donc être traités avec une attention particulière pour ne pas entraîner d'incohérence visuelle lors de la génération d'images photoréalistes. Les reflets et les ombres qui apparaissent dans ces zones aident notamment l'observateur à distinguer clairement les silhouettes d'un objet. Par exemple, dans la figure 4.1, sans arrondi, le Rubik's cube semble être constitué d'un seul bloc, alors que les petits cubes sont visibles individuellement lorsque les bords et les coins sont arrondis.
<figure><img src="image_43.png" /><figcaption>Figure 4.1 – La présence des surfaces arrondies change la perception visuelle des objets : (a) masque d'une image illustrant les pixels concernés par un arrondi (b) image calculée par notre méthode (c) différence visuelle entre un modèle sans arrondi, ou avec un arrondi plus ou moins discrétisé.</figcaption></figure>

Nous avons vu dans la section 2.1.3 que dans la plupart des modeleurs géométriques, la représentation des arrondis est réalisée avec des maillages polygonaux denses. Cela a pour effet de discrétriser le chanfrein tout en augmentant considérablement la complexité des scènes. La répartition hétérogène des primitives géométriques peut mettre en défaut les structures accélératrices classiques (cf. section 2.1.1). De plus, la subdivision du maillage ne permet pas de simuler correctement les effets lumineux, même avec un niveau de subdivision élevé. Cela augmente fortement la quantité de mémoire nécessaire et lorsque la distance d'arrondi est grande ou lorsque les chanfreins sont observés de près, des discontinuités restent visibles. L'utilisation de surfaces paramétriques permet une meilleure visualisation des chanfreins. Néanmoins, ces éléments paramétriques sont difficiles à intégrer dans le processus de rendu et le coût d'intersection d'une telle représentation est supérieur à un ensemble polygonal.

L'axe de recherche présenté dans ce chapitre aborde le rendu des effets de chanfrein lisses avec un faible impact sur la complexité géométrique et avec une gestion des calculs d'intersections rayon-objet efficace. Il se place de manière plus général dans le projet région SIMOREVA (2018 - 2022) qui traite de la perception des environnements virtuels. Les travaux présentés dans la suite on été majoritairement réalisés par Simon Courtin au cours de sa thèse dont le sujet concerne le rendu réaliste des bords arrondis. Pour cela nous proposons une nouvelle structure de détection topologique et hiérarchique (dénommée SREC-RT) qui ne modifie pas la géométrie originale et qui permet d'éditer facilement les paramètres d'arrondi. Notre objectif principal est d'utiliser cette structure pour mieux repartir les calculs du lancé de rayons et de nous abstraire du modèle de représentation utilisé pour modéliser les chanfreins (discrétisation polygonale ou surfaces paramétriques). La figure 4.2 illustre une vue d'ensemble de ce travail avec la construction de la structure SREC-RT et son utilisation pendant le processus de rendu.

La construction de SREC-RT consiste à générer une structure de détection globale du type *domaine arrondi* pour chaque face d'un objet. Le domaine arrondi d'une face correspond à la zone le long d'un bord qui doit être remplacée par une géométrie de chanfrein. Chaque arête et sommet de la géométrie originale sont ainsi traités avec leur géométrie adjacente (faces adjacentes et arêtes incidentes) pour déterminer la position des surfaces arrondies et leur connexion sur la géométrie originale. Cette structure englobante est basée sur des volumes limites définis par des cylindres et des sphères, chacun délimitant avec précision le chanfrein. L'avantage d'utiliser cette hiérarchisation de l'espace est que le modèle de représentation des surfaces d'arrondi sous-jacentes peut être défini par n'importe quelles primitives géométriques (linéaire ou paramétrique). Pour améliorer la gestion de la propagation des rayons le long des chanfreins, des liens topologiques entre les volumes limites sont instanciés, construits à partir de la géométrie d'entrée et imbriqués dans la structure accélératrice utilisée pour le lancer de rayons.
<figure><img src="image_44.png" /></figure>

Figure 4.2 – SREC-RT est construite à partir (a) de la géométrie d'entrée, en positionnant (b) des zones d'arrondis sur les bords des polygones. Le résultat est une (c) structure de volumes englobants utilisée pendant le rendu pour déterminer efficacement les intersections des rayons avec la géométrie arrondie.

Enfin, SREC-RT est utilisée pendant le processus de rendu : (i) elle permet de déterminer efficacement si une intersection se produit avec un domaine arrondi, minimisant ainsi les calculs d'intersection de rayons ; (ii) le trajet du rayon est étendu jusqu'à l'intersection de la surface arrondie uniquement lorsque cela est nécessaire ; (iii) les liens topologiques assurent une propagation efficace du rayon à l'intérieur du domaine d'arrondi dans les cas où les rayons rasants n'intersectent pas immédiatement le chanfrein.

Dans la suite de ce chapitre, la section 4.1 détaille le processus de construction de la structure SREC-RT. La section 4.2 décrit le processus de lancé de rayons en utilisant cette nouvelle structure. La section 4.3 présente une solution de représentation des arrondis permettant une meilleure précision géométrique. Nous proposons ainsi une solution avec des surfaces paramétriques, basée sur des patchs de Béziers triangulaires modifiés de type Gregory pour les coins arrondis et des courbes de Béziers 2D extrudées pour les bords arrondis. La section 4.4 décrit les résultats obtenus. Notre méthode a été intégrée dans le modeleur *Blender* [20] avec les moteurs de rendu *Cycles* [21] et PBRT [127]. Nous analysons les comparaisons générées avec les méthodes existantes. Enfin, un bilan est présenté dans la section 4.5.

## 4.1 Construction de la structure accélératrice SREC-RT

Les arrondis sont définis à partir d'une distance d'arrondi *d* spécifiée par l'utilisateur pour chaque objet sélectionné. L'objectif est de construire une structure composée de volumes englobants qui entourent les régions concernées par des arrondis. Notre processus est générique et permet de construire la structure quelle que soit la configuration géométrique des données d'entrée.
4.1.1 Positionnement des surfaces arrondies

La figure 4.3.a illustre les notations utilisées et le positionnement d'un bord arrondi le long d'une
arête. Considérons deux faces adjacentes a et b avec leurs normales respectives Ñ_a et Ñ_b. L'arête
incidente est définie par deux sommets v₁ et v₂. Soit $\vec{E} = v_2 - v_1$ le vecteur orienté pour l'arête
($\vec{E}' = \vec{E} / |\vec{E}|$ est sa normalisation). Nous considérons $\vec{F}_a = \vec{N}_a \times \vec{E}'$ et $\vec{F}_b = \vec{N}_b \times -\vec{E}'$, les directions
de rétraction géométrique des faces a et b affectées par la surface arrondie. Les points $d_1 = v_1 + \vec{F}_a \cdot d$ et
$d_2 = v_1 + \vec{F}_b \cdot d$ définissent les limites de la surface arrondie le long du bord considéré à $v_1$. Les points
$d_3$ et $d_4$ sont définis de façon similaire en $v_2$.

<figure><img src="image_45.png" /><figcaption>Figure 4.3 – Positionnement des arrondis (a) spécification pour une arête. (b-c) arrondi d'un sommet soit (b) incident à des arêtes d'arrondi identiques ou (c) cas général ou les distances d'arrondi des arêtes sont hétérogènes.</figcaption></figure>

<figure><img src="image_46.png" /><figcaption>Figure 4.4 – Notre opération d’arrondi peut être utilisée pour les objets incluant des sommets arrondis incidents (a) à des arêtes convexes (b) des arêtes concaves et convexes. Les sommets arrondis (en rouge) sont délimités par les points d’ancrage $A_i$, positionnés sur les arêtes incidentes.</figcaption></figure>
Le processus est général, quel que soit le nombre d'arêtes incidentes et leur configuration (arêtes rentrantes ou sortantes). Pour assurer la connexion entre la surface des chanfreins et la face initiale, des points d'ancrage (notés $A_i$) sont calculés avant de créer une surface arrondie aux sommets (cf. figure 4.3.b). La frontière d'un sommet arrondi est définie en utilisant les points d'ancrage deux par deux dans le sens horaire. Cette méthode généralisée permet de traiter des sommets incidents à des arêtes arrondies de distances d'arrondi hétérogènes (cf. figure 4.3.c). Dans ce cas, la limite de l'arrondi ne définit pas une surface fermée et les points d'ancrage disjoints sont reliés à l'aide de segments droits (entre $A_1$ et $A_2$, ou $A_3$ et $A_4$ dans l'exemple illustré dans la figure 4.3.c. Ce procédé s'applique à n'importe quelle configuration de sommets, indépendamment de la distance d'arrondi $d$ des arêtes et de leur convexité (cf. figure 4.4).

La construction ci-dessus définit entièrement la limite des domaines d'arrondi. La surface arrondie sous-jacente peut être définie par n'importe quel processus et primitives d'arrondi (linéaire ou paramétrique). La section 4.3 propose une solution pratique basée sur les surfaces paramétriques.

## 4.1.2 Structure de détection

La structure définie dans cette section délimite avec précision le domaine arrondi pour toutes les surfaces de la géométrie originale (cf. figure 4.5). Elle correspond aux volumes englobants basés sur des cylindres et des sphères, appelés volumes de détection.

<figure><img src="image_47.png" /><figcaption>Figure 4.5 – Positionnement de la structure de détection constituée de cylindres et de sphères englobants autour des arrondis. (a) Surfaces arrondies pour les arêtes (bleu clair) et les sommets (orange). (b)-(c) Les cylindres (bleu) et les sphères (rouge) de détection sont placés autour des arêtes et des sommets, entourant exactement les surfaces arrondies.</figcaption></figure>

Chaque arête chanfreinée est délimitée par un cylindre dont l'axe est parallèle à l'arête. Le cylindre délimite précisément le domaine arrondi sur les deux faces adjacentes (c'est-à-dire qu'il définit exactement la limite de l'arrondi sur chaque face impactée par le processus d'arrondi). Les figures 4.6.b et 4.6.c illustrent le positionnement d'un cylindre de détection associé à une arête. Il est basé sur le vecteur de mi-distance $\vec{H} = (\vec{F}_a + \vec{F}_b)/\|\vec{F}_a + \vec{F}_b\|$ et sur le rayon du cylindre de détection $r$ tel que $r = \frac{d}{2\cos(\theta/2)}$, avec $\theta$ l'angle entre les deux faces adjacentes, et $d$ la distance d'arrondi (définie par l'utilisateur). Les points $P_1 = v_1 + \vec{H} \cdot 2r$ et $P_2 = v_2 + \vec{H} \cdot 2r$ correspondent à la limite de l'axe central du cylindre de détection.

Chaque sommet arrondi est délimité par une sphère, dont le barycentre est le centre de masse des points d'ancrage du sommet associé. Le rayon de la sphère est défini comme la distance maximale entre ce centre et les points d'ancrage (cf. figure 4.6.d et e), de manière à englober entièrement la surface du sommet arrondi.
<figure><img src="image_48.png" /><figcaption>Figure 4.6 – Positionnement des primitives de détection. (a) Surface arrondie pour une arête. (b) Cylindre de détection (en bleu) de rayon *r* passe par les points $v_1$, $d_1$, et $d_2$. (c) Le cylindre délimite exactement l'arrondi de l'arête. (d) Un sommet arrondi est délimité par une sphère (en rouge) et relié à ses cylindres de détection incidents (en bleu). (e) Le même processus est appliqué aux sommets sans qu'il soit nécessaire de distinguer les surfaces convexes et concaves correspondant aux arêtes arrondies incidentes.</figcaption></figure>

Comme nous visons à gérer des scènes comportant un grand nombre de chanfreins, nous avons choisi une organisation des primitives de détection basée sur un Kd-tree. Cette structure s'est avérée expérimentalement plus efficace qu'une hiérarchie de volumes englobants (BVH). Les feuilles de notre Kd-tree contiennent l'ensemble des primitives de détection (cylindres et sphères). Il est inséré dans la structure SREC-RT et est construit pour chaque objet ou groupe d'objets simples, de manière à bénéficier de profondeurs d'arbre modérées.

### 4.1.3 Structure Topologique

Pour un sommet *C* donné, le volume de détection est une sphère, et plusieurs cylindres de détection sont attachés pour gérer les arêtes incidentes *E*. Lorsqu'un rayon sort d'un volume de détection, son chemin doit être prolongé efficacement, soit à travers le volume de détection suivant, soit à l'extérieur de l'objet. Pour traiter la propagation des rayons, un graphe représentant les adjacences et les incidences entre les volumes de détection est directement déduit des connexions entre les arêtes et les sommets. Il définit la structure topologique employée lors du parcours des rayons, pour traverser les volumes de détection successifs (ce qui est fréquent dans le traitement des rayons rasants). Pour déterminer la propagation d'un rayon qui traverse un volume de detection, nous avons choisi de définir des interfaces planes (désignées par *I*) entre les volumes de détection. Une arête est liée à une interface à chacune de ses deux extrémités. Un sommet est lié à plusieurs interfaces, et dans la plupart des cas le nombre d'interfaces est égal au nombre d'arêtes qui lui sont incidentes. Une interface est reliée (selon la configuration géométrique) soit à deux volumes de détection, soit à un volume de détection et une sortie. La figure 4.7 illustre la configuration associée à un ensemble des arêtes et de sommets, ainsi que leurs interfaces.
<figure><img src="image_49.png" /><figcaption>Figure 4.7 – La structure topologique correspondant aux régions arrondies mises en évidence dans (a) est construite autour des arêtes et des sommets arrondis de l’objet. (b) Chaque arête E (en bleu) est reliée à deux sommets C (en rouge) par des interfaces planes I (en vert).</figcaption></figure>

## 4.2 Utilisation de SREC-RT en lancé de rayons

Notre structure est utilisable avec toutes méthodes de rendu basée sur du lancé de rayons. Les rayons peuvent provenir de l'observateur, de sources lumineuses, de la réflexion ou de la réfraction. Le processus de traversée de SREC-RT est général et peut donc être utilisé pour ces différents cas d'utilisation.

### 4.2.1 Processus détaillé

Pour un point d'intersection donné $P_i$ sur la géométrie originale, la structure de détection permet de déterminer s'il appartient au domaine arrondi (recherche dans le Kd-tree de l'objet intersecté). La figure 4.8.a illustre les différents cas. Si l'intersection n'est pas dans une primitive de détection (comme pour $P_a$), le rayon est directement utilisé dans le processus d'illumination. Sinon, l'intersection se trouve à l'intérieur d'au moins une primitive de détection (comme pour $P_b$) et la surface arrondie sous-jacente associée est utilisée pour calculer l'intersection des rayons.

Pour un point d'intersection $P'$ sur une surface arrondie (cf. figure 4.8.b), la normale associée est calculée pour poursuivre les processus de rendu. $P'$ étant placé sous la surface de l'objet, les rayons secondaires doivent partir du maillage de la géométrie d'origine au lieu de $P'$. Ils sont d'abord définis par leur origine $P'$ et une direction (réfléchie, réfractée, ombre, etc.) fixée par le tracé de chemins, mais tracés à partir d'une origine située sur la surface du maillage ($P''$ ou $P''''$ sur la figure).

### 4.2.2 Utilisation de la structure topologique de détection

L'avantage d'utiliser la structure SREC-RT réside dans le fait que la plupart des intersections sont en pratique calculées sur la géométrie d'origine de la scène (sans les arrondis). La complexité géométrique associée aux surfaces arrondies n'est pas prise en compte dans la structure accélératrice initiale. Une seule consultation du Kd-tree est effectuée pour un point d'intersection sur les objets arrondis. Nous verrons dans la section 4.4 que dans le cas de détails fins, seuls quelques rayons sont finalement impactés par la traversée de la structure topologique. Mais cette gestion entraîne un gain substantiel en temps de traitement.
La traversé d'un rayon pour une primitive de detection donnée n'entraîne pas systématiquement d'intersection avec la surface d'arrondi sous jacente. Dans ce cas, la structure topologique est utilisée pour propager efficacement le rayon, sans nouvelle recherche dans le Kd-tree (cf. figure 4.9). L'algorithme consiste à estimer quel plan d'interface correspond au changement de volume de détection (en utilisant l'intersection rayon-plan); ainsi, la structure topologique permet de directement sélectionner la prochaine primitive de détection à visiter. De même, si le rayon ne croise aucune surface arrondie, les plans d'interface permettent de déterminer le point de sortie (comme pour le rayon $ray_b$ dans les figures 4.9.a et 4.9.b).

<figure><img src="image_50.png" /><figcaption>Figure 4.8 – Intersection rayon-objet utilisant le maillage original. (a) Avec le rayon$_a$, l'intersection $P_a$ est située sur la géométrie d'origine et en dehors de la structure de détection. Le processus de traçage de rayons est effectué normalement. Avec le rayon$_b$, l'intersection $P_b$ se trouve à l'intérieur d'un cylindre de détection et le test d'intersection est effectué avec la surface arrondie. (b) Le rayon$_a$ intersecte la surface arrondie en $P'$, et l'origine du rayon réfléchi est fixée à $P'''$ sur le maillage original. Avec le rayon$_b$, aucune intersection n'est trouvée sur la surface arrondie sous-jacente, et l'origine du rayon$_b$ est déplacée à $P''$.</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>Figure 4.9 – Propagation du rayon au travers de la structure de détection grâce aux graphes topologiques. (a) ray$_a$ ne touche pas la surface arrondie dans le premier cylindre de détection. La structure topologique guide la recherche dans le volume de détection suivant (la sphère d'angle), et une intersection est trouvée sur l'angle arrondi. (b) Vue de la structure avec le parcours schématique des rayons : le rayon$_a$ touche un coin arrondi à C, tandis que le rayon$_b$ traverse différentes primitives de détection sans toucher la géométrie arrondie.</figcaption></figure>
4.2.3 Cas particulier : sommets concaves

Dans le cas des arrondis concaves, la géométrie d'origine n'englobe pas la surface de l'arrondi, et
les rayons rasants peuvent manquer l'intersection (cf. figure 4.10.a). Cette configuration est gérée dans
SREC-RT avec des *triangles portails* placés aux interfaces entre les jonctions arêtes-sommets concaves,
de manière à définir un point d'entrée dans la structure de détection. Un triangle est construit pour chaque
côté de bord arrondi, à partir de la courbure. Ces triangles sont ajoutés à la structure générale d'accé-
lération du rendu. Lorsqu'un rayon frappe l'un de ces triangles, SREC-RT est interrogé sans traitement
particulier. Les portails de triangles définissent de nouveaux points d'entrée dans SREC-RT pour garantir
que les rayons ne manquent jamais une géométrie arrondie.

<figure><img src="image_52.png" /></figure>

Figure 4.10 – Les rayons rasants peuvent manquer un chanfrein concave. (a) Un rayon *R* n’intersecte pas la géométrie d’origine, car il manque la zone d’arrondi qui n’est pas inclue par la géométrie d’origine, il n’explore donc pas SREC-RT. (b) Un portail triangulaire est ajouté à chaque coin concave, car les interfaces qui produisent des points *P*<sub>p</sub> activent l’exploration dans SREC-RT, pour déterminer le point d’intersection exact *P*<sub>s</sub>.

Remarque : les triangles portails sont considérés comme invisibles et ne modifient pas les maillages d'origine. Ils ajoutent des informations géométriques sur un petit ensemble de configurations spécifiques de coins concaves afin de définir un point d'entrée dans SREC-RT. Dans ce cas, l'étape de détection est évitée et la surface arrondie peut être directement intersectée.

4.3 Représentation des arrondis

SREC-RT est conçu indépendamment de la représentation des surfaces arrondies choisie. Idéalement,
pour un rendu visuel de qualité, une représentation compacte de ces surfaces est préférable, ainsi qu'une
continuité G¹ entre la géométrie arrondie et la géométrie d'origine. Il est également nécessaire que la
représentation de surface choisie soit facilement utilisable pour les méthodes de tracé de chemins, sans
discontinuité, pour tout point de vue et toute configuration d'éclairage.

Les opérations d'arrondi conduisent souvent à des ensembles complexes de surfaces courbes, gé-
néralement approchées par des méthodes de subdivision (par exemple, Catmull-Clark [30]). Avec cette
approche, la subdivision la plus fine (définie arbitrairement) résulte en un maillage polygonal qui est
gourmand en mémoire.
4.3.1 Representation et intersection des arêtes arrondies

Comme cela sera présenté dans la section 4.4, l’utilisation de répartition hiérarchique de SREC-RT permet de réduire le temps de traitement. Nous avons donc choisi de mettre à contribution ce gain de temps pour travailler sur l’amélioration visuelle et la précision dans les calculs de simulation. Nous proposons dans cette section une représentation basée sur les surfaces paramétriques (minimisant ainsi la consommation de mémoire). Elle s’appuie sur notre représentation topologique où les sommets arrondis, délimités par des sphères de détection, sont représentés par un ensemble minimal de patchs triangulaires de Gregory modifiés [65]. La continuité $G^0$ est assurée entre les chanfreins des arêtes et des sommets grâce à des patches basés sur des courbes de Bézier quadratiques extrudées et délimitées par deux courbes identiques. La surface de l’arrondi correspond donc à l’extrusion d’une courbe de Bézier le long de l’axe de l’arête (comme illustré sur la figure 4.11). Cette formulation nous permet de contrôler l’arrondi de l’arête avec un minimum de paramètres, tout en assurant la continuité avec les faces adjacentes et les sommets arrondis connectés.

Les patches ne sont pas approximés par des mailles polygonales ; ils sont directement utilisés par la procédure de lancé de rayons, offrant une qualité de lissage constante quel que soit le point de vue. Pour l'intersection des rayons, une première intersection 2D est calculée entre le rayon et la courbe de Bézier, fournissant le plan tangent 3D où l'intersection finale est déterminée. Le rayon intersecte l'angle arrondi si et seulement si le point d'intersection se trouve entre ses deux extrémités.

<figure><img src="image_53.png" /><figcaption>Figure 4.11 – Les sommets (à gauche) sont représentés par des patchs triangulaires. Les limites sont définies par trois courbes de Bézier (ADB, BEC et CFA), et la forme globale est contrôlée par trois points intérieurs ($D^+$, $E^+$ et $F^+$). Les arêtes (à droite) sont représentées par des courbes de Bézier linéairement extrudées.</figcaption></figure>

4.3.2 Representation et intersection des sommets arrondis

Représenter des surfaces courbes avec un ensemble de patches de Bézier est une approche cou-
rante [29]. Bien que des patches cubiques (ou de degré supérieur) puissent être utilisés pour contrôler la
courbure d'une surface, les tests d'intersection entre les rayons et les éléments paramétriques conduisent
à des calculs longs [88, 158]. De plus, pour un meilleur contrôle de la courbure il serait nécessaire d'aug-
menter soit le degré des patches, soit le nombre de points de contrôle intérieurs comme cela est fait
pour les patches de Gregory [65]. Malheureusement, ces deux solutions ont un impact sur les besoins en
mémoire. C'est pourquoi, nous proposons d'utiliser des patches triangulaires quadratiques. La représen-
tation par patchs qui en résulte permet une utilisation directe dans les systèmes de rendu par rayons ainsi
qu'un contrôle fin de la continuité entre les arêtes et les sommets.
Soit un patch triangulaire *ABC* dont les bords sont définis par trois courbes de Bézier *ADB*, *BEC* et *CFA*, comme illustré sur la figure 4.11, le patch triangulaire est défini comme une fonction à deux paramètres *X* :

$$
\begin{align*}
X(s,t) ={}& (1-s-t)^2 A + s^2 C + t^2 B \\
& + 2s(1-s-t) ((1-t)F + tF^+) \\
& + 2t(1-s-t) ((1-s)D + sD^+) \\
& + 2st ((s+t)E + (1-s-t)E^+) \tag{4.1}
\end{align*}
$$

ou $s, t \in [0, 1]$ et $s + t \le 1$. Les points $D^+, E^+, \text{et } F^+$ sont des points de contrôle intérieurs.

Pour un sommet relié à *n* = 3 arêtes, la définition d'un patch est directement utilisée pour décrire la surface arrondie. Dans les cas généraux (sommets arrondis avec plus de 3 arêtes incidentes i.e. *n* > 3), le patch polygonal est délimité par *n* courbes de Bézier. Dans la suite, une telle géométrie est appelée un domaine à *n* côtés. Notre approche consiste à trianguler le domaine à partir d'un point central, selon une version modifiée de la méthode de remplissage de régions [128, 146]. Cette opération construit *n* patches triangulaires. La figure 4.12 présente cette construction pour un domaine à 4 cotés.

Étant donné un sommet *V* de la géométrie d'entrée, le point central de la subdivision *P*<sub>c</sub> est défini comme suit :

$$
P_c = \tilde{P}_c + \lambda(V - \tilde{P}_c), \quad (4.2)
$$

où $\tilde{P}_c = \frac{1}{n} \sum_{i=0}^{n-1} P_i$ le centre de masse des points de contrôle de la courbe de Bézier environnante. Le scalaire $\lambda \in [0, 1]$ définit l'élévation de $P_c$, et nous permet de contrôler la netteté du domaine à $n$ côtés. La valeur de $\lambda$ est choisie par l'utilisateur (nous avons fixé $\lambda = 0, 4$ dans toutes nos expériences). La normale $\tilde{N}$ du plan tangent à la surface au point central $P_c$ est définie par :

$$
\tilde{N} = \left| \frac{1}{n} \sum_{i=0}^{n-1} (P_i - \tilde{P}) \times (P_{i+1} - \tilde{P}) \right|.
$$

<figure><img src="image_54.png" /><figcaption>Figure 4.12 – Construction d’un arrondi correspondant à un sommet V sur la géométrie originale avec quatre courbes de Bézier (a). (b) Le point central P<sub>c</sub> est calculé à partir de V et des points P<sub>i</sub> (points de contrôle des courbes de Bézier). (c) Les courbes de Bézier intermédiaires sont déterminées grâce au plan défini par la normale N&#773; et le segment P<sub>i</sub>V. (d) L’arrondi du sommet est un ensemble de patches de Bézier triangulaires.</figcaption></figure>

Le calcul de l'intersection des rayons que nous employons pour les patchs de Bézier est basé sur la
méthode de Kajiya [88]. Notre algorithme teste différentes configurations et sauvegarde celle qui présente
la plus petite erreur. Les détails mathématiques sont fournis dans notre article [36].