# Construction efficace de la surface de systèmes moléculaires complexes sur GPU

Cyprien Plateau-Holleville, Matthieu Montes, Maxime Maria, Stéphane Mérillou

► To cite this version:

Cyprien Plateau-Holleville, Matthieu Montes, Maxime Maria, Stéphane Mérillou. Construction efficace de la surface de systèmes moléculaires complexes sur GPU. J.FIG 2023 - Journées Françaises de l'Informatique Graphique, Nov 2023, Montpellier, France. hal-04633888

HAL Id: hal-04633888

https://hal.science/hal-04633888v1

Submitted on 3 Jul 2024

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.

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

Distributed under a Creative Commons Attribution 4.0 International License
Construction efficace de la surface de systèmes moléculaires
complexes sur GPU

C. Plateau-Holleville<fnref n="1" />, M. Montes<fnref n="2" />,<fnref n="3" />, M. Maria<fnref n="1" />, S. Mérillou<fnref n="1" />

<figure><img src="image_2.png" /><figcaption>Figure 1: Rendu de la Surface Exclue au Solvant (SES) de la capside complète du VIH-1 (PDB: 3J3Q) de plus de 2.4 millions d'atomes. Sa géométrie est calculée avec notre méthode en 700ms sur une NVIDIA RTX 2080. Comme illustré avec cette grande structure, la SES permet de représenter de façon précise les détails locaux tout en conservant une bonne lisibilité des formes générales à plus grande échelle.</figcaption></figure>

Abstract

La surface exclue au solvant est une représentation moléculaire intéressante dans un cadre de visualisation grâce à sa capacité à illustrer les potentielles interactions. Son calcul reste cependant difficile en raison de la complexité de sa définition géométrique, mais aussi de la difficulté à paralléliser les opérations requises. Dans cet article, nous présentons une méthode de génération de cette surface, basée sur une récente analyse mathématique, permettant de s'affranchir des limitations précédentes, notamment grâce à des traitements GPU adaptés.

CCS Concepts

•Computing methodologies → Massively parallel algorithms; Parametric curve and surface models;

1. Introduction

La visualisation moléculaire est outil particulièrement intéressant pour l'analyse et la compréhension de la géométrie des protéines.

À travers le développement d'outils adaptés et depuis son introduc-
tion, l'informatique graphique a contribué à de multiples reprises
aux outils disponibles pour faciliter la visualisation, mais aussi
l'illustration et la mise en valeur des observations [KKF*16].

Avec l'amélioration des méthodes d'acquisition, les études de
plus grandes échelles sont devenues plus courantes mettant à
l'épreuve les stratégies de visualisation existantes. Même si de ré-

centes méthodes ont permis d'utiliser la répétition de motifs au sein
de la géométrie afin d'améliorer les performances de visualisation
de très grandes structures [MAPV15], le support de dynamiques
moléculaires empêche tout à priori géométrique.

Dans ce contexte et depuis sa définition analytique par
Richards [Ric77], la Surface Exclue au Solvant (SES) s'est instal-
lée comme une représentation essentielle dans le travail d'analyse
des biochimistes. Elle est définie par l'interaction entre la surface
de van der Walls (vdW), où chaque atome est représenté par une
sphère d'un rayon égal à son rayon de vdW, et une sphère appelée

<footnote n="1">¹Laboratoire XLIM, UMR CNRS 7252, Université de Limoges, France</footnote>

<footnote n="2">²GBCM - Laboratoire Génomique, Bioinformatique et Chimie Moléculaire, EA7528, Conservatoire National des Arts et Métiers, Hésam Université, France</footnote>

<footnote n="3">³Institut Universitaire de France (IUF)</footnote>
probe, comme illustrée sur la figure 2. Elle décrit donc l'interaction
potentielle avec d'autres entités comme des solvants ou autres
molécules. Ainsi, elle est utile dans des contextes de tailles de pro-
téines très variées, comme illustrée sur la figure 1, pour la visuali-
sation de caractéristiques externes, mais aussi internes comme des
cavités au sein de la géométrie.

<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration de la surface de van der Walls (vdW), de la Surface Accessible au Solvant (SAS) et de la Surface Exclue au Solvant (SES). Le centre du probe, en roulant sur la surface de vdW, décrit la SAS tandis que sa frontière avec la surface de vdW décrit la SES.</figcaption></figure>

Le calcul analytique de la SES pour de grandes structures en
des temps réduits pour le support de dynamiques moléculaires reste
difficile malgré différents travaux originaux. Dans cet article, nous
présentons une méthode adaptée à ces contraintes à partir des con-
tributions suivantes :

* Nous proposons l'utilisation de la dernière analyse mathématique de la SES [QS16, QS17] permettant de diminuer les besoins mémoires requis pour les calculs.

* Nous proposons un processus de construction adapté aux architectures modernes de GPU permettant le calcul de la surface complète dans des temps similaires à la méthode la plus rapide de l'état de l'art, elle-même limitée à la surface extérieure.

* Nous montrons qu'à partir de nos développements, il est possible de calculer la SES de grandes structures sur des cartes graphiques grand public.

## 2. Travaux antérieurs

À partir des travaux introductifs de Richards [Ric77], différentes études ont été présentées sur la SES. Nous proposons de les diviser en trois catégories : fondamentale, approximant et analytique. Le premier type s'est principalement concentré sur l'analyse de la surface et la construction d'algorithme théorique, tandis que les deuxième et troisième se sont intéressés à sa construction de façon adaptée à des besoins de visualisation.

**Analyses fondamentales** Les premiers éléments fondamentaux de calculs de la SES ont été présentés par Connolly [Con83]. C'est sur cette base que deux algorithmes, Reduced-Surface [SOS96] et Contour-Buildup [TA96], ont été introduits. Le premier est basé sur un traitement des cercles résultant de l'intersection des sphères des atomes alors que le second propose de construire une α-shape [EM94] à partir de laquelle la surface peut être reconstruite. Enfin, Quan & Stamm [QS16, QS17] ont plus récemment proposé

une analyse mathématique de la surface permettant de s'affranchir
des singularités géométriques des précédentes représentations.

**Approximant** Les besoins en visualisation rapide de la SES ont conduit au développement de méthodes l'approximant. Notamment, l'utilisation de champs scalaire a permis l'introduction de visualisation interactive [HKG*17]. D'autres surfaces moléculaires ont été aussi considérées, comme la surface gaussienne [Bru19], approchant la forme générale de la SES et permettant de meilleure performance, mais sans bénéficier d'un niveau de détail similaire.

**Analytique** Les liens induits entre consommation mémoire et niveau de détail des méthodes approximant ont poussé les développements des stratégies visant le calcul analytique de la surface. Notamment, des méthodes performantes de visualisation de l'extérieur de la SES [KBE09] ont été proposées en masquant certaines parties non souhaitées à l'intérieur du volume de la surface. Des implémentations parallèles d'algorithmes fondamentaux [KDE10, KGE11] ont été développées sur cette base pouvant cependant nécessiter de grandes allocations mémoires. Des travaux permettant le calcul de la géométrie complète de la surface ont ensuite été présentés afin de permettre la représentation de l'intérieur de la surface [JPSK16, RZK*19], mais proposant des temps de calcul et une consommation mémoire plus importants.

## 3. Représentation géométrique

Notre méthode repose sur la représentation géométrique de la SES proposée par Quan & Stamm [QS16]. Celle-ci est basée sur un découpage de la surface en primitives, appelée patchs, reposant sur des éléments géométriques de la SAS à partir desquels on peut définir les fonctions distance signée (SDF) illustrées sur la figure 3. Cette description permet de définir une structure de données compacte permettant le rendu des patchs que nous décrivons dans cette partie. Les SDFs sont données dans l'annexe A.

**Primitives de la SAS.** Comme illustré dans les figures 2 et 3, on peut définir les patchs de la SES à partir de primitives géométriques de la SAS. Cette dernière est décrite comme l'union des sphères de vdW dont le rayon aurait été agrandi par celui du probe. Le chemin du probe est donc décrit par la surface de la SAS que l'ont peut découper en trois types de primitives : la surface des sphères de la SAS, les cercles dérivés de l'intersection de deux sphères de la SAS et enfin les intersections de trois sphères de la SAS en un ou deux points.

**Patch convexe $P_+$**. Un patch convexe propose deux degrés de liberté au probe roulant sur sa surface. Il peut être représenté avec une sphère de vdW dont les limites sont décrites par les cercles de la SAS. Un patch $P_+$ est totalement représenté à partir d'une position, un rayon et une liste de cercles de la SAS.

**Patches toroïdaux $P_{tf}$ et $P_t$.** Lorsque le centre du probe est localisé sur un cercle de la SAS, il dispose d'un seul degré de liberté. La surface décrite par la frontière entre le probe et la surface de vdW est alors similaire à celle de l'intérieur d'un tore. Puisqu'un cercle de la SAS peut être intersecté par un autre, résultant en une intersection de la SAS, nous différencions les cercles complets donnant des patches toroïdaux complets $P_{tf}$ et les cercles intersectés donnant des patches toroïdaux partiels $P_t$. Ils sont représentables à partir des
<figure><img src="image_4.png" /><figcaption>Figure 3: Illustration de la décomposition en patch de la SES ainsi que des éléments structurels de la SAS permettant de calculer leurs SDFs. En vert : cercles complets. En jaune : cercles intersectés.</figcaption></figure>

deux sphères et du cercle à leur origine en plus des intersections de la SAS dans le cas de patches toroïdaux partiels $P_t$.

**Patch concave $P_-$**. Enfin, lorsque le probe est localisé sur une intersection de la SAS, il ne possède plus de degré de liberté. Les patchs associés $P_-$ sont donc représentables à partir de la position de l'intersection de la SAS. Cependant, lorsque la sphère du probe dépasse le tétraèdre englobant du patch décrit par la position de l'intersection et celle des trois sphères de la SAS à son origine, il est possible qu'il intersecte un autre patch comme illustré sur la figure 3. Afin de correctement décrire sa surface, il est nécessaire, en plus des informations précédentes, de connaître les intersections de la SAS voisines donnant lieu à des intersections entre les patchs.

## 4. Calcul structurel

La définition des patchs présentée dans la partie précédente permet de calculer la SES de façon complète à partir des primitives de la SAS. Celles-ci représentent donc la cible de notre processus de construction et leurs liens hiérarchiques ordonnent les étapes de notre méthode que nous décrivons dans cette partie.

**Calcul et classification des cercles de la SAS.** Les cercles de la SAS sont obtenus à partir des voisinages $\mathcal{N}(a_i)$ de chacun des atomes en sélectionnant ceux dont la distance est inférieure à $r_i + r_j + 2r_p$, avec $r_i$ et $r_j$ les rayons des atomes $a_i$ et $a_j$, et $r_p$ le rayon du probe. Pour cela, nous utilisons une grille accélératrice alliant rapidité de construction et vitesse de requête. Une fois cette donnée obtenue, chaque cercle est classifié en fonction de sa nature selon les types suivants : complet, intersecté et caché [QS17]. Les cercles complets et intersectés vont contribuer aux patches convexes $P_+$ et respectivement produire des patches toroïdaux $P_{if}$ et $P_t$ tandis que les patchs cachés sont localisés à l'intérieur d'atomes voisins et ne contribuent donc pas à la surface.

**Calcul des intersections de la SAS.** Afin de construire les intersections de la SAS, il est nécessaire de parcourir l'ensemble des cercles intersectés identifiés à l'étape précédente. Cette étape est difficile puisqu'il est nécessaire de s'assurer que chaque intersection trouvée n'est pas localisée à l'intérieur d'un autre atome. Pour cela, nous cherchons les atomes présents dans deux voisinages $a_k \in \mathcal{N}(a_i) \cap \mathcal{N}(a_j)$ [QS17]. On assure enfin la visibilité des intersections trouvées en vérifiant qu'elles ne sont pas à l'intérieur d'un autre atome du voisinage.

**Calcul des segments de la SAS.** Une fois les intersections de la SAS obtenues, nous disposons de toutes les informations nécessaires au calcul des segments de la SAS. La liste des intersections de chaque cercle est triée de façon angulaire, ce qui permet de créer un patch $P_t$ par couple d'intersections [MJK16, QS17].

## 5. Implémentation GPU

Les étapes présentées dans la partie précédente permettent d'obtenir la géométrie de la SES. Cependant, elles intègrent un nombre important d'opérations sur les graphes de voisinage des atomes et des cercles pouvant ralentir de façon importante le traitement, spécifiquement sur GPU, où la cohérence des opérations effectuées en parallèle est particulièrement critique. Dans cette partie, nous présentons donc différents traitements adaptés à ces contraintes. Nous faisons référence aux sous-groupes de fils d'exécutions exécutant la même instruction avec des données différentes sous le terme de warp.

**Traitement coopératif des intersections.** Les opérations nécessaires pour traiter une seule intersection entre deux cercles représentent à elles seules une charge importante. Ainsi, nous utilisons un warp dédié pour le traitement de chacun des cercles in-

<figure><img src="image_5.png" /><figcaption>Figure 4: Schéma du traitement coopératif des intersections de la SAS. En pointillés : opérations intrawarp effectuées en parallèle, mais itérativement sur les entrées de $\mathcal{K}$.</figcaption></figure>
<table><caption>Table 1: Comparaison entre notre méthode et l'implémentation publique de Contour-Buildup sur GPU [KGE11] dans le framework Megamol [GBB*19] pour un probe de rayon standard [D'A78] de 1.4 Å. Les temps sont donnés en millisecondes (ms) et représentent une moyenne sur 1000 itérations par cas, tandis que la mémoire maximale utilisée est donnée en mégaoctets (Mo).</caption><thead><tr><th rowspan="2">PDB Id</th><th rowspan="2">#Atome</th><th colspan="2">Gralka et al. [GBB*19] - ext.</th><th colspan="2">Notre méthode</th><th colspan="2">Notre méthode - ext.</th></tr><tr><th>Temps (ms)</th><th>Mém. (Mo)</th><th>Temps (ms)</th><th>Mém. (Mo)</th><th>Temps (ms)</th><th>Mém. (Mo)</th></tr></thead><tbody><tr><td>101M</td><td>1413</td><td>4.51</td><td>133.55</td><td>3.75</td><td>4.50</td><td>2.51</td><td>1.76</td></tr><tr><td>7DBB</td><td>17733</td><td>7.00</td><td>1675.43</td><td>5.80</td><td>56.18</td><td>4.49</td><td>25.50</td></tr><tr><td>7RGD</td><td>65008</td><td>16.86</td><td>6123.51</td><td>18.06</td><td>214.33</td><td>14.64</td><td>105.35</td></tr><tr><td>3JC8</td><td>107640</td><td>-</td><td>-</td><td>14.99</td><td>324.03</td><td>11.60</td><td>147.57</td></tr><tr><td>6U42</td><td>1358547</td><td>-</td><td>-</td><td>200.79</td><td>4287.12</td><td>157.23</td><td>2162.99</td></tr><tr><td>3J3Q</td><td>2440800</td><td>-</td><td>-</td><td>700.17</td><td>7631.24</td><td>324.22</td><td>3744.73</td></tr></tbody></table>

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

tersectés de l'atome courant. Comme illustré sur la figure 4, nous traitons de façons différentes les tâches simples et lourdes du traitement des intersections. Les tâches simples, comme le calcul de la position de l'intersection, sont traitées à partir d'un seul fil tandis que les tâches lourdes, comme les tests de visibilité des intersections, sont traitées de façon séquentielle en utilisant tous les fils du warp. Ce processus permet ainsi un compromis localisé entre parallélisme et puissance de calcul. Nous utilisons de plus un masque binaire afin de conserver les informations sur les tâches au cours du traitement, ce qui permet une communication efficace entre les fils d'exécution du warp.

**P**_ intersectés. Les patchs concaves P_ intersectant leurs tétraèdres respectifs sont identifiés pendant leur construction et marqués comme tels. Ils sont ensuite rassemblés sous la forme d'un sous-ensemble au début du tableau les stockant ce qui permet d'effectuer les tests de collision de façon performante et localisée.

**Trajetement coopératif des segments.** À la suite du calcul des intersections, nous retrouvons les intersections participant à la SES de chacun des cercles intersectés de la SAS à l'origine des segments de la SES. De la même façon que pour les intersections, nous utilisons ensuite un traitement coopératif. Ainsi nous construisons d'abord la liste d'intersection de chacun des cercles intersectés que l'on trie de façon parallèle pour plusieurs cercles à l'intérieur d'un warp. Cela permet notamment de ne pas souffrir des divergences induites par les algorithmes de tri séquentiels.

**Estimation des besoins mémoires.** Il est difficile de prévoir le nombre d'intersections #X de la SAS [KGE11, SK19]. Nous proposons de l'estimer à partir du nombre de cercles intersectés #I :

$$ \#X \le \#I \max (\#X(\{c_{ij}\})) \quad (1) $$

195

196

197

198

199

200

201

Expérimentalement, nous bornons la moyenne maximale du nombre d'intersections par cercle avec max (\#X(c_{ij})) = 2. Celle-ci n'est pas restrictive en pratique puisque notre implémentation permet à un cercle unique d'avoir jusqu'à 16 intersections. De plus, de nombreux cercles intersectés ne produisent finalement pas d'intersection contribuant à la surface, puisque positionnée à l'intérieur d'un atome voisin.

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

## 6. Résultats et performances

Afin d'évaluer les performances de notre méthode, nous comparons sa vitesse d'exécution et sa consommation mémoire à celles de la méthode la plus rapide de l'état de l'art selon nos tests [KGE11, GBB*19] dans le tableau 1. Ces tests sont effectués sur une NVIDIA RTX 2080 8GB et un AMD Ryzen 5 1600. La méthode comparée est limitée à la construction de la surface extérieure, et donc uniquement au calcul des P<sub>tf</sub> et P<sub>-</sub>, et sa principale limite est sa consommation mémoire [RZK*19, SK19]. Nous proposons de plus les résultats de notre méthode adaptée au calcul extérieur pour une évaluation dans des conditions similaires.

Nos résultats montrent que notre méthode propose des temps de calcul similaires à celle de Krone et al. [KGE11] tout en réduisant de façon importante la consommation mémoire. Plus précisément, dans le cas de la construction limitée à la surface extérieure, notre méthode adaptée consomme 60 fois moins de mémoire. À la différence de la méthode comparée, la notre permet aussi de calculer la surface complète tout en consommant 30 fois moins de mémoire. Cela rend ainsi possible le calcul de la surface complète de molécules de plusieurs millions d'atomes sur des GPUs grand public.

Comme observé par des travaux précédents [SK19] et visibles sur nos résultats, la géométrie de la protéine influe sur les performances. Ainsi, on peut remarquer que la surface de 3JC8 est calculée plus rapidement que celle de 7RDG alors même que son nombre d'atomes est plus important. En effet, le nombre de cercles intersectés affecte les temps de calcul de manière plus significative que le nombre d'atomes. Une molécule dense comporte beaucoup de cercles intersectés dont les intersections seront localisées à l'intérieur d'atomes voisins et ne participeront pas à la surface.

## 7. Conclusion et travaux futurs

À partir de notre méthode, le calcul de la géométrie complète de la SES de grandes molécules est rendu possible avec des performances similaires aux méthodes précédentes. De plus, nous montrons que nos optimisations permettent une réduction très importante de la consommation mémoire du processus. Notre méthode pourra donc faciliter l'utilisation des méthodes de calcul analytique de la SES sur des cartes graphiques plus grand public ainsi que le traitement de grandes structures. Cependant, notre méthode
241

242

243

244

requiert un recalcul complet en cas de changement de la taille du rayon du probe parfois nécessaire à certaines applications. Nous orientons donc nos travaux pour pallier cette limitation majeure tout en conservant des niveaux de performances importants.

245

## References

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

[Bru19] BRUCKNER S.: Dynamic visibility-driven molecular surfaces. Computer Graphics Forum 38, 2 (May 2019), 317–329. URL: https://doi.org/10.1111/cgf.13640, doi: 10.1111/cgf.13640.2

[Con83] CONNOLLY M. L.: Analytical molecular surface calculation. Journal of Applied Crystallography 16, 5 (oct 1983), 548–558. doi: 10.1107/s0021889883010985.2

[D'A78] D'ARRIGO J. S.: Screening of membrane surface charges by divalent cations: an atomic representation. American Journal of Physiology-Cell Physiology 235, 3 (sep 1978), C109–C117. doi: 10.1152/ajpcell1.1978.235.3.c109.4

[EM94] EDELSBRUNNER H., MÜCKE E. P.: Three-dimensional alpha shapes. ACM Transactions on Graphics 13, 1 (jan 1994), 43–72. doi: 10.1145/174462.156635.2

[GBB*19] GRALKA P., BECHER M., BRAUN M., FRIESS F., MÜLLER C., RAU T., SCHATZ K., SCHULZ C., KRONE M., REINA G., ERTL T.: MegaMol – a comprehensive prototyping framework for visualizations. The European Physical Journal Special Topics 227, 14 (Mar. 2019), 1817–1829. URL: https://doi.org/10.1140/epjst/e2019-800167-5, doi:10.1140/epjst/e2019-800167-5.4

[HKG*17] HERMOŞILLA P., KRONE M., GUALLAR V., VÁZQUEZ P.-P., VINACUA À., ROPINSKI T.: Interactive GPU-based generation of solvent-excluded surfaces. The Visual Computer 33, 6–8 (May 2017), 869–881. URL: https://doi.org/10.1007/s00371-017-1397-2, doi:10.1007/s00371-017-1397-2.2

[JPSK16] JURCIK A., PARULEK J., SOCHOR J., KOZLIKOVA B.: Accelerated visualization of transparent molecular surfaces in molecular dynamics. In 2016 IEEE Pacific Visualization Symposium (PacificVis) (Apr. 2016), IEEE. URL: https://doi.org/10.1109/pacificvis.2016.7465258, doi:10.1109/pacificvis.2016.7465258.2

[KBE09] KRONE M., BIDMON K., ERTL T.: Interactive visualization of molecular surface dynamics. IEEE Transactions on Visualization and Computer Graphics 15, 6 (Nov. 2009), 1391–1398. URL: https://doi.org/10.1109/tvcg.2009.157, doi:10.1109/tvcg.2009.157.2

[KDE10] KRONE M., DACHSBACHER C., ERTL T.: Parallel computation and interactive visualization of time-varying solvent excluded surfaces. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology (Aug. 2010), ACM. URL: https://doi.org/10.1145/1854776.1854840, doi: 10.1145/1854776.1854840.2

[KGE11] KRONE M., GROTTEL S., ERTL T.: Parallel contour-buildup algorithm for the molecular surface. In 2011 IEEE Symposium on Biological Data Visualization (BioVis). (Oct. 2011), IEEE. URL: https://doi.org/10.1109/biovis.2011.6094043, doi: 10.1109/biovis.2011.6094043.2, 4

[KKF*16] KOZLIKOVÁ B., KRONE M., FALK M., LINDOW N., BAADEN M., BAUM D., VIOLA I., PARULEK J., HEGE H.-C.: Visualization of biomolecular structures: State of the art revisited. Computer Graphics Forum 36, 8 (Nov. 2016), 178–204. URL: https://doi.org/10.1111/cgf.13072, doi:10.1111/cgf.13072.1

[MAPV15] MUZIC M. L., AUTIN L., PARULEK J., VIOLA I.: CELIVIEW: a Tool for Illustrative and Multi-Scale Rendering of Large Biomolecular Datasets. In Eurographics Workshop on Visual Computing for Biology and Medicine (2015), Bühler K., Linsen L., John

N. W., (Eds.), The Eurographics Association. doi:10.2312/vcbm.20151209.1

[MJK16] MANAK M., JIRKOVSKY L., KOLINGEROVA I.: Interactive analysis of connolly surfaces for various probes. Computer Graphics Forum 36, 6 (May 2016), 160–172. URL: https://doi.org/10.1111/cgf.12870, doi:10.1111/cgf.12870.3

[QS16] QUAN C., STAMM B.: Mathematical analysis and calculation of molecular surfaces. Journal of Computational Physics 322 (Oct. 2016), 760–782. URL: https://doi.org/10.1016/j.jcp.2016.07.007, doi:10.1016/j.jcp.2016.07.007.2, 5

[QS17] QUAN C., STAMM B.: Meshing molecular surfaces based on analytical implicit representation. Journal of Molecular Graphics and Modelling 71 (Jan. 2017), 200–210. URL: https://doi.org/10.1016/j.jmgm.2016.11.008, doi:10.1016/j.jmgm.2016.11.008.2, 3

[Ric77] RICHARDS F. M.: Areas, volumes, packing and protein structure. Annual Review of Biophysics and Bioengineering 6, 1 (jun 1977), 151–176. doi:10.1146/annurev.bb.06.060177.001055.1, 2

[RZK*19] RAU T., ZAHN S., KRONE M., REINA G., ERTL T.: Interactive cpu-based ray tracing of solvent excluded surfaces. Eurographics Workshop on Visual Computing for Biology and Medicine (2019). URL: https://diglib.eg.org/handle/10.2312/vcbm20191249, doi:10.2312/VCBM.20191249.2, 4, 5

[SK19] SCHÄFER M., KRONE M.: A massively parallel cuda algorithm to compute and visualize the solvent excluded surface for dynamic molecular data. Workshop on Molecular Graphics and Visual Analysis of Molecular Data (2019). URL: https://diglib.eg.org/handle/10.2312/molva20191094, doi:10.2312/MOLVA.20191094.4

[SOS96] SANNER M. F., OLSON A. J., SPEHNER J.-C.: Reduced surface: An efficient way to compute molecular surfaces. Biopolymers 38, 3 (1996), 305–320. doi:10.1002/(SICI)1097-0282(199603)38:3<305::AID-BIP4>3.0.CO;2-Y.2

[TA96] TOTROV M., ABAGYAN R.: The contour-buildup algorithm to calculate the analytical molecular surface. Journal of Structural Biology 116, 1 (Jan. 1996), 138–143. URL: https://doi.org/10.1006/jsbi.1996.0022, doi:10.1006/jsbi.1996.0022.2

## Appendix A: Définitions des fonctions distance signée

Nous décrivons dans cette partie les fonctions distance signée proposées par Quan & Stamm [QS16], utilisées dans ces travaux. Celles-ci permettent d'obtenir la distance entre un point *p* et la SES en fonction de la SAS.

**Patch convexe $P_+$** Si $p$ n'appartient pas à la SAS, son point le plus proche sur la SES se situe sur un patch convexe $P_+$. Sa distance avec la SES est donc obtenue à partir de :

$$ 
\begin{aligned}
d(P_+, p) &= ||p - c_i|| - r_i, \quad p \notin s, \forall s \in S_i \\
c_i &= \arg\min_{\forall c_j \in M} ||p - c_j||
\end{aligned} 
\quad (2) $$

avec $M$ la molécule, $c_i$ et $r_i$ les centre et rayon d'un atome $a_i$, et $S_i$ ses cercles de la SAS. Afin de tester si $p$ appartient à un des cercles de la SAS, nous traduisons ces cercles en secteurs [RZK*19] à partir desquels nous effectuons un test d'inclusion.

**Patch toroïdaux $P_{tf}$ et $P_t$** Si $p$ est localisé dans la SAS et plus particulièrement dans le triangle $\triangle(p'c_ic_j)$ décrit par les centres des atomes $a_i$ et $a_j$, et $p'$, sa projection sur leur cercle de la SAS
$\mathscr{C}_{ij}$, alors son point le plus proche sur la SES est localisé sur un patch toroidal dont la distance $d(P_t, p)$ est obtenue avec :

$$ 
\begin{aligned}
d(P_t, p) &= -||p' - p|| + r_p, \quad p \in \Delta(p'c_i c_j) \\
p' &= c_{ij} + r_{ij} \frac{v}{||v||} \\
v &= p + ((c_{ij} - p) \cdot n_{ij})n_{ij} - c_{ij}
\end{aligned}
\quad (3) $$

avec $c_{ij}$ et $r_{ij}$ les centre et rayon du cercle $\mathscr{C}_{ij}$ et $n_{ij}$ sa normale

orientée de $c_i$ à $c_j$.

Si le patch associé est un patch toroïdal partiel $P_t$, il est de plus nécessaire de tester si le point appartient au segment visible à partir de :

$$ \angle (x^l - c_{ij}, p' - c_{ij}) < \angle (x^l - c_{ij}, x^m - c_{ij}) \quad (4) $$

avec $x^l$ et $x^m$ les intersections du patch $P_t$.

**Patch concave $P_-$** Enfin, si $p$ appartient à la SAS et ne correspond à aucun autre type de patch, son point le plus proche est localisé sur un patch concave $P_-$. Sa distance avec la SES $d(P_-, p)$ est alors obtenue avec :

$$ 
\begin{aligned}
d(P_-, p) &= -||p - x^u|| + r_p \\
x^u &= \arg \min_{\forall x^s \in \mathcal{X}} ||p - x^s||
\end{aligned}
\quad (5) $$

avec $\mathcal{X}$ l'ensemble des intersections de la SAS.