Comment j'ai ray-tracé toute une ville en temps réel

Cet article est la suite technique de Mappy Hour. Si tu veux le pitch et le contexte, commence par là. Ici on parle maths, structures de données et benchmarks.

Le problème de performance

Un rayon solaire, un point sur la carte, une question : le soleil est-il visible ? Simple. Sauf que Lausanne compte environ 50’000 bâtiments, un terrain alpin avec des dénivelés brutaux, et des arbres partout. Tester chaque obstacle pour chaque point de la grille, c’est 2.85 points par seconde. Inutilisable.

Il fallait passer de “techniquement correct” à “utilisable en temps réel”. Spoiler : on a fini à 155.8 points par seconde. Un facteur 54.6x.

Le corridor : ne tester que ce qui compte

Premier réflexe d’optimisation : pourquoi tester un bâtiment à 2 km à l’est quand le soleil vient du sud ?

Le filtrage se fait en trois étapes, de la plus grossière à la plus fine :

D’abord, par cellule de 64m :

1. AABB — Un rectangle englobant aligné sur les axes (AABB, pour “Axis-Aligned Bounding Box” : un rectangle toujours horizontal/vertical, jamais tourné, ce qui le rend extrêmement rapide à calculer) entoure le rayon avec un padding de 148m. Les cellules hors du rectangle sont éliminées.
2. Dot product cellule — La cellule est-elle derrière l’observateur ? Le produit scalaire (la position de la cellule projetée sur la direction du rayon) donne la réponse : si négatif, éliminée.
3. Distance latérale cellule — La cellule est-elle trop loin du rayon sur les côtés ? Même dans l’AABB, une cellule peut être à 100m du rayon. Éliminée.
4. Altitude culling cellule — Le bâtiment le plus haut de cette cellule est-il assez haut pour bloquer le soleil à cette distance ? Si le toit le plus haut est sous la ligne de visée, on saute toute la cellule d’un coup. Cette optimisation donne 39-54% d’amélioration à elle seule.

Ensuite, par bâtiment individuel dans les cellules retenues :

1. Dot product bâtiment — Même test, mais sur le centre du bâtiment.
2. Distance latérale bâtiment — Le bâtiment est-il trop loin du rayon ? Un filtre plus serré que celui des cellules (demi-diagonale du bâtiment au lieu de la cellule).
3. Altitude culling bâtiment — Le toit de ce bâtiment spécifique est-il assez haut ?
4. Ray-tracing — Pour chaque candidat restant, on vérifie si le bâtiment bloque réellement le rayon. En mode prisme, c’est une comparaison d’angle. En mode mesh, une intersection rayon-triangle.

L’AABB est donc une enveloppe de recherche, pas un test de blocage — comme chercher dans un annuaire par code postal avant de vérifier l’adresse exacte. On pourrait le remplacer par un rectangle orienté le long du rayon (OBB), mais les benchmarks montrent que ça ne change rien : 1.02x de speedup. Les bâtiments éliminés par un corridor plus serré ne déclenchent jamais le ray-tracing de toute façon.

La grille spatiale 64m

Le corridor réduit les candidats, mais il faut encore les trouver vite. J’ai découpé la ville en cellules de 64m x 64m. Chaque cellule maintient un index des bâtiments qui la touchent.

La carte ci-dessus montre les 225 bâtiments réels (données SwissBUILDINGS3D) autour de la terrasse du Great Escape. Chaque bâtiment est coloré selon l’étape qui l’élimine : gris foncé = hors AABB, orange = éliminé par le dot product (derrière l’observateur), turquoise = candidat retenu pour le ray-tracing. Bougez le slider pour voir comment le filtrage change avec la direction du soleil.

Sans grille : 962 obstacles testés par rayon. Avec grille : environ 1. Le corridor + la grille ensemble donnent un speedup de 4.25x (Lot A).

Le contexte partagé par tuile

La carte est divisée en tuiles de 250m x 250m. Observation clé : deux points dans la même tuile voient essentiellement les mêmes bâtiments candidats et le même horizon.

Le contexte d’évaluation — bâtiments candidats, profil de terrain, masque d’horizon — est calculé une seule fois au centre de la tuile, puis réutilisé pour chaque point. Speedup : 45.8x (Lot B). C’est de loin l’optimisation la plus rentable.

Le masque d’horizon

Pour chaque zone, je précalcule un masque d’horizon à 360 degrés : un tableau de 360 cases, une par degré d’azimut (l’angle de la boussole : 0° = nord, 90° = est, 180° = sud, 270° = ouest). Pour chaque direction, un rayon est lancé le long du sol jusqu’à 120 km. Tous les 250 mètres, on échantillonne l’altitude du terrain (DEM Copernicus à 30 m de résolution), on corrige pour la courbure terrestre et la réfraction atmosphérique, et on garde l’angle d’élévation maximal. Le résultat : un profil d’obstruction complet autour du point. Si le soleil est en-dessous de cet angle pour un azimut donné, il est masqué par le relief — et oui, le Jura français à 80 km projette des ombres sur Lausanne en fin de journée.

Pourquoi 360° alors que le soleil ne parcourt qu’un demi-cercle ? Parce que le masque est calculé une seule fois et mis en cache pour toute l’année. En hiver, le soleil reste bas au sud (~130° à ~230°). En été, il se lève au nord-est (~50°) et se couche au nord-ouest (~310°) — la course couvre presque les trois quarts du cercle. Basculez entre les deux saisons ci-dessous pour voir la différence.

Le diagramme polaire ci-dessus montre le masque d’horizon vu depuis la terrasse du Great Escape. Les pics en vert correspondent aux bâtiments proches (immeuble ouest, bloc nord) et aux reliefs lointains (Jura au nord-ouest, Alpes au sud-est). Quand le soleil (point jaune) passe sous la ligne verte, la terrasse est à l’ombre.

Les masques sont partagés de manière adaptative via des macro-cells de 2000m x 500m. En pratique, environ 20 tuiles partagent un même masque, et seulement 4 nécessitent un calcul local (Lot C).

Trois modes de calcul pour les bâtiments

Le ray-tracing des bâtiments a évolué en trois itérations, chacune toujours disponible via MAPPY_BUILDINGS_SHADOW_MODE. La différence est plus facile à comprendre en la voyant. Voici les environs du Great Escape (Rue Madeleine 18, Lausanne) modélisés avec chacune des approches :

Prism — Le footprint 2D extrudé en hauteur. Rapide, mais les toits complexes et les formes irrégulières génèrent des faux positifs. Le bâtiment en L du Great Escape ? Le prisme le voit comme un rectangle plein. Résultat : la terrasse est déclarée à l’ombre alors qu’elle ne l’est pas.

Two-level — Le prisme tourne en premier. Si le prisme dit “ombre”, on regarde la marge : de combien de degrés le sommet du prisme dépasse-t-il le soleil ? Si la marge est faible (< 2°), c’est un cas douteux — on vérifie avec le mesh 3D. Si la marge est grande, on fait confiance au prisme sans vérifier. Le fantôme rouge montre la bounding box du prisme, le mesh détaillé corrige à l’intérieur.

Detailed — Mesh 3D complet, 32 passes de raffinement. Le plus précis, et le défaut actuel. Les optimisations du corridor et de la grille rendent ce mode viable en temps réel.

Pourquoi le mode detailed a gagné

Le two-level a l’air d’un bon compromis, mais il garde des faux positifs. Le problème : quand un bâtiment a un fill ratio faible (le bâtiment en L ne remplit que 33% de sa bounding box), le prisme peut être confiant et faux en même temps. Le soleil passe dans le vide du L, mais le prisme voit un rectangle plein et dit “ombre avec 5° de marge”. Comme la marge est au-dessus du seuil, le two-level ne vérifie jamais avec le mesh.

Concrètement, sur la zone du Great Escape à 17h30 :

Même à 3° de seuil, il reste 38 faux positifs. Pour les éliminer tous, il faudrait monter le seuil tellement haut qu’on vérifierait presque tout avec le mesh — autant l’utiliser directement. Et les optimisations (grille spatiale, corridor, contexte partagé) ont rendu le mesh suffisamment rapide : le speedup du two-level par rapport au detailed n’est que de 1.02x à 1.07x. Pas assez pour justifier 38 terrasses déclarées à l’ombre à tort.

Le pipeline de données

Avant de ray-tracer quoi que ce soit, il faut ingérer des téraoctets de données publiques suisses.

Le pipeline :

1. Terrain — SwissALTI3D (2m) via l’API STAC de Swisstopo + Copernicus DEM 30m pour l’horizon transfrontalier
2. Bâtiments — Fichiers DXF de SwissBUILDINGS3D, parsés pour extraire footprints, hauteurs et bounding boxes. Deduplication par footprint+hauteur identiques. Indexation dans la grille spatiale 64m
3. Végétation — swissSURFACE3D, raster GeoTIFF à 0.5m. Chaque pixel = élévation sol + arbres. Échantillonné par interpolation bilinéaire le long du rayon. La visualisation ci-dessus montre le principe : les points jaunes sont les échantillons le long du rayon solaire, les rouges indiquent une intersection avec la canopée.

Le tout est précalculé et caché en tuiles de 250m avec invalidation automatique.

Les chiffres

Ce qui n’a pas marché

Le prisme seul avait trop de faux positifs — des terrasses déclarées à l’ombre alors qu’elles ne l’étaient pas. Le mesh seul était trop lent — 30 secondes pour une tuile. L’horizon calculé par point individuel était redondant à 98%. Chaque optimisation est née d’un échec mesuré. Trial-and-error, mais avec des benchmarks.

Le plus efficace dans tout ça : mesurer d’abord, optimiser ensuite. Chaque lot a été isolé, benchmarké, et validé indépendamment. Pas de devinettes.