Récemment, j’ai fouillé dans quelques vieux projets et j’ai redécouvert un de mes vieux projets de lycée qui tentait de rendre de très grandes images de la fractale de Buddhabrot. Je ne savais pas grand-chose sur l’écriture de code rapide à l’époque, et sans surprise, ce projet n’a pas été couronné de succès. Cependant, je n’aime pas laisser les choses inachevées, et ces derniers mois, j’ai écrit une implémentation GPU moderne d’un moteur de rendu Buddhabrot pour voir où je pourrais l’utiliser.

Au lieu de rendre une seule grande image, j’ai pensé qu’une séquence d’animation serait plus intéressante à regarder. Le Buddhabrot vit dans un espace 4D, et la rotation de différentes projections sur un écran 2D rend mieux justice à ses formes complexes. Cependant, les fonctionnalités se sont mises en place, et cela s’est avéré beaucoup plus complexe à faire qu’initialement prévu – un simple panoramique de caméra n’était pas assez intéressant, et j’ai commencé à écrire beaucoup d’outils jetables pour configurer des plans de caméra 4D synchronisés à la musique. J’étais également réglé sur le rendu en résolution 4K, et les temps de rendu ont atteint des sommets. Beaucoup de temps a été consacré à l’importance du code d’échantillonnage et des méthodes de débruitage pour garder les coûts de rendu sous contrôle.

La programmation et l’installation de la caméra ont pris plus de deux mois, et le rendu de l’animation finale a pris plus de 10 jours. Ma pauvre GTX480 a également fini par mourir d’une mort brûlante aux mains de la fractale, et j’ai dû emprunter un ordinateur pour terminer le travail. Je ne suis pas convaincu que ça en valait la peine, mais je suis heureux d’avoir enfin mis le projet à l’arrêt 🙂

Un Bouddha quoi ?

Le Bouddhabrot est une curieuse fractale qui produit de merveilleuses images de nébuleuses nuageuses et colorées, et est étroitement lié à l’ensemble de Mandelbrot. Les pages de Wikipédia sur le Mandelbrot et le Buddhabrot sont une meilleure ressource, mais brièvement, l’ensemble de Mandelbrot fonctionne en choisissant des points sur le plan complexe, en les transformant à plusieurs reprises avec une formule simple et en vérifiant si les points s’échappent finalement vers l’infini ou pas. Les points qui ne s’échappent pas font partie de l’ensemble.

La fractale de Mandelbrot est fascinante parce qu’elle génère une complexité époustouflante à partir de quelques règles très simples. Cette complexité émergente semble être une propriété funky du plan complexe, et de nombreuses autres fractales ont été faites en utilisant des règles aussi simples sur les nombres complexes. L’une de ces fractales est le Bouddhabrot.

Le Bouddhabrot utilise les mêmes règles d’itération que le Mandelbrot : Les points sont échantillonnés sur le plan complexe, transformés de façon répétée à l’aide d’une fonction simple et filtrés selon qu’ils s’échappent à l’infini ou non. La principale différence, cependant, est de savoir quels points sont conservés : Si un point ne s’échappe pas, il est jeté ; mais s’il s’échappe, le point et toutes ses versions transformées sont stockés. Les versions transformées du point correspondent à sa “trajectoire” à travers l’espace alors qu’il s’échappe à l’infini.

Si nous le faisons plusieurs fois, nous nous retrouverons avec une longue liste de points qui ne figurent pas dans l’ensemble de Mandelbrot et leurs trajectoires en route vers l’infini. Pour obtenir un Bouddhabrot, nous construisons simplement une image représentant un histogramme de ces trajectoires : Nous commençons par une image noire, et chaque fois qu’une trajectoire passe à travers un pixel, nous l’incrémentons d’un pixel. Si nous continuons à le faire, nous obtiendrons finalement une image où les pixels clairs montreront des régions qui sont souvent visitées par des trajectoires d’échappement, et les pixels sombres à ceux qui sont rarement visités. C’est le Bouddhabrot.

Comment mapper les trajectoires en pixels est une question de projection, et Melinda Green (la découvreuse du Bouddhabrot) a plus de ressources sur le sujet. Il est intéressant de noter que le Bouddhabrot contient la totalité du Mandelbrot et qu’avec les bonnes projections, nous pouvons faire des allers-retours entre les deux.

Rotation entre le Bouddhabrot et la fractale de Mandelbrot

Échantillonnage important

Rendre le Bouddhabrot de manière efficace pose un certain défi. Le principal problème est que nous ne pouvons pas calculer directement la valeur du Bouddhabrot à un pixel, mais que nous devons échantillonner de nombreuses trajectoires aléatoires et espérer qu’elles passent à travers les pixels auxquels nous tenons. Cette approche “spray and pray” fonctionne raisonnablement bien pour les images zoomées, mais les zooms avant et les transformations sont très difficiles à rendre dans un délai raisonnable, car de nombreuses trajectoires atterrissent à l’extérieur du cadre et leur calcul est inutile.

Cependant, si nous sommes un peu plus intelligents quant à la façon dont nous échantillonnons les points de départ des trajectoires, nous pouvons atténuer ce problème. Les trajectoires sont entièrement déterminées par leur point de départ, et l’utilité d’une trajectoire est déterminée par le nombre de cases d’histogramme qu’elle touche avant de s’échapper. Les trajectoires longues à l’intérieur du cadre sont bien meilleures que les trajectoires courtes ou les trajectoires complètement hors écran. On peut donc noter chaque point de départ par une valeur d’importance, qui est égale au nombre de bacs qu’il a touchés avant de s’échapper.

Nous ne connaissons pas a priori la distribution d’importance, et au départ nous n’avons pas d’autre choix que d’échantillonner les points de départ de façon aléatoire et uniforme. Cependant, si nous enregistrons les valeurs d’importance des points générés dans une image d’importance séparée, avec le temps, nous commençons à avoir une bonne idée des zones qui ont tendance à contenir des points de départ qui produisent des trajectoires importantes, et des zones qui sont sans rapport avec la région que nous rendons.

L’image ci-dessous montre l’importance de la carte (image de droite) pour le rendu d’un Buddhabrot zoomé. Notez que la carte d’importance est presque équivalente à une image de l’ensemble de Mandelbrot : D’importantes trajectoires commencent presque toutes à la limite de l’ensemble de Mandelbrot.

Le Bouddhabrot (à gauche) et sa carte d’importance estimée pour générer des trajectoires (à droite). Notez que la carte d’importance correspond à la fractale de Mandelbrot.

Les choses commencent à paraître un peu plus intéressantes pour les versions zoomées. Les points importants ont maintenant tendance à provenir de la moitié inférieure de l’ensemble de Mandelbrot, mais des bassins rectangulaires déformés de points importants sont répartis sur tout le territoire.

Une version zoomée du Buddhabrot (à gauche) et la carte d’importance estimée pour générer des trajectoires (à droite).

Après avoir généré une carte d’importance convergente décemment, nous pouvons appliquer l’échantillonnage d’importance 2D standard de Monte Carlo pour en tirer des échantillons. Au lieu de générer des trajectoires uniformément aléatoires, nous choisissons leurs points de départ de sorte que nous partons plus souvent de trajectoires dans des régions qui, à notre avis, contiennent de nombreux points importants. Dans les images zoomées, cette stratégie d’échantillonnage crée déjà des accélérations impressionnantes, et les zoom-ins profitent énormément de cette méthode.

Il convient de noter que nous devons modifier les poids des trajectoires en conséquence – au lieu d’incrémenter les boîtes d’histogrammes d’une unité, nous devons les incrémenter de la probabilité inverse de l’échantillonnage d’une trajectoire. Cela correspond à l’estimateur standard de Monte Carlo.

Je dois mentionner qu’Alexander Boswell a découvert une technique d’échantillonnage similaire. Il utilise la même fonction d’importance, mais plutôt que de la représenter explicitement et de l’échantillonner à l’aide d’une carte 2D, il utilise l’algorithme Metropolis-Hastings pour en tirer des échantillons. Bien que cela fonctionne, Metropolis-Hastings a l’inconvénient que les échantillons qu’il génère sont corrélés. Cela se manifeste sous la forme d’un bruit “tacheté”, plutôt que d’un bruit blanc, dans l’image, et pose d’énormes problèmes dans l’animation. De plus, comme on l’a vu plus haut, la fonction d’importance peut être assez complexe avec de grandes régions noires, et il est difficile pour Metropolis-Hastings de l’explorer correctement. Puisque le domaine d’entrée est en 2D, nous pouvons nous permettre de garder une trace explicite de la carte d’importance, et dans mon cas cette méthode était mieux adaptée que Metropolis-Hastings.

Estimation de la variance et débruitage

L’échantillonnage d’importance nous permet de réduire considérablement le temps de rendu des images fixes. Cependant, les animations sont une bête complètement différente : Les animations de taille décente nécessitent des milliers d’images, pas une seule, et nous n’avons pas assez de temps pour rendre chaque image à la convergence, même avec un échantillonnage intelligent. De plus, la compression vidéo se mélange très mal avec des données bruyantes, et les vidéos bruyantes deviennent presque inutilisables après que Youtube en ait fini avec elles. D’une manière ou d’une autre, nous devons transformer les images bruyantes en quelque chose avec quoi nous pouvons travailler, sans passer plus de temps à les rendre.

Pour résoudre ce problème, je me suis tourné vers la littérature à la recherche d’un algorithme de débruitage qui fonctionnerait avec le bruit de Monte Carlo. Heureusement, c’est quelque chose que l’industrie cinématographique a déjà traité auparavant, et il y a beaucoup de littérature sur le sujet. Pour ce projet particulier, j’ai choisi une méthode de débruitage des moyens non locaux basée sur le travail de Rouselle et al. dans Robust Denoising en utilisant Feature and Color Information.

Une image générée à partir d’un milliard de trajectoires est encore trop bruyante pour l’animation (à gauche). Après le débruitage des moyens non locaux, la qualité de l’image est suffisante pour la vidéo 4K (à droite).

Non-Local Means est un peu comme un flou très sélectif. Il recherchera les quartiers de pixels et fusionnera les pixels qu’il pense être similaires, mais laissera les pixels très différents les uns des autres. La mesure de la différence est basée ici sur des distances par zones, qui ont tendance à être très robustes dans la pratique et nous permettent d’injecter des informations supplémentaires sur le bruit dans l’image.

Pour fonctionner efficacement, Non-Local Means a besoin d’une estimation de la variance à chaque pixel. La variance mesure le niveau de bruit d’un pixel, ce qui rendra le dénudeur plus prudent avec les pixels qui sont presque convergents, mais plus agressif avec les pixels qui sont très bruyants.

Le calcul direct de la variance du Bouddhabrot est un peu délicat à cause de l’approche par histogramme. Pour obtenir une estimation robuste, j’ai utilisé une méthode multi-tampons : Au lieu d’un seul histogramme, le moteur de rendu garde la trace de plusieurs histogrammes à la fois. Quand on trace une trajectoire, on ne l’envoie qu’à un seul des histogrammes. A la fin du rendu, cela nous donne plusieurs rendus statistiquement indépendants d’une même scène. La moyenne de ces histogrammes produit l’image de sortie normale, et le fait de prendre la variance de l’échantillon pour tous les histogrammes donne une estimation de la variance.

Un rendu du Buddhabrot (à gauche) après un milliard de trajectoires et la variance estimée à chaque pixel (à droite).

Pour les images fixes, cela donne déjà de bons résultats. Cependant, pour les animations, il y a une question supplémentaire de cohérence temporelle. Monte Carlo génère un bruit blanc, c’est-à-dire un bruit réparti également sur toutes les fréquences. Non-Local Means fonctionne à l’intérieur d’une fenêtre de filtre spatial fini (ici, 31×31 pixels), et ne peut donc supprimer que le bruit de haute à moyenne fréquence. Le bruit à basse fréquence est laissé de côté.

Dans les images fixes, ce n’est pas un problème énorme, car la vision humaine n’est pas très bonne pour reconnaître les variations spatiales de la luminosité dans les basses fréquences. Cependant, c’est différent dans les animations : Chaque image a un modèle de bruit différent, et le bruit à basse fréquence change dans chaque image. Des régions entières de l’image sautent de haut en bas en luminosité au fil du temps, ce qui a un aspect épouvantable et consomme une bande passante vidéo importante.

Pour faire face à ce problème, j’ai mis en place une extension temporelle du filtre des moyens non locaux. En plus de l’image courante, les 5 images précédentes et les 5 images suivantes de la séquence d’animation sont également utilisées pour aider à dénuder l’image courante. Nous ne cherchons pas seulement des pixels voisins similaires dans l’espace, mais aussi dans le temps (cela semble plus sophistiqué qu’il ne l’est). D’une part, cela permet d’éliminer davantage le bruit spatial. D’un autre côté, cela permet de lisser le motif de bruit sur plusieurs images, ce qui rend les artefacts temporels beaucoup moins apparents.

Le débruitage des moyens non locaux standard (à gauche) laisse derrière lui des bruits de basse fréquence gênants. Temporal Non-Local Means denoising (à droite) permet de lisser le bruit entre les images et réduit considérablement ce problème.

Relation avec le Jacobien

Il est intéressant de noter que le Bouddhabrot est intimement lié au déterminant jacobien inverse de l’itération de Mandelbrot, et j’ai d’abord étudié cette relation pour trouver un algorithme de rendu plus efficace. Bien que j’aie trouvé une méthode de rendu alternative, elle est beaucoup plus bruyante à des nombres d’itérations élevés et pas vraiment faisable. Cependant, j’ai quand même pensé que c’était intéressant, alors je vais le résumer brièvement ici.

Une description grossière du déterminant jacobien inverse d’une fonction est qu’il s’agit d’une mesure de la façon dont une fonction étire et comprime l’espace dans lequel elle opère. La valeur de l’inverse est grande lorsque la fonction comprime l’espace d’entrée, et petite lorsqu’elle l’étire.

L’itération de Mandelbrot elle-même est une série de fonctions allant du plan complexe au plan complexe. Par exemple, itérer un point une fois, itérer un point deux fois et itérer trois fois sont trois fonctions différentes (polynomiales) qui transforment des points complexes en d’autres points complexes. Pour le Mandelbrot, ces fonctions ne sont généralement pas données explicitement, mais sont écrites comme une règle récursive ; cependant, si nous continuons à étendre et à multiplier les termes, nous arrivons finalement à une fonction polynomiale simple pour chaque itération.

Nous pouvons calculer le déterminant jacobien inverse de ces fonctions pour comprendre comment elles compriment et étirent le plan complexe. Si nous faisons cela pour chaque itération du Mandelbrot et additionnons les déterminants inverses de tous ces Jacobiens, nous obtenons une nouvelle fonction qui mesure comment l’espace autour d’un point est déformé lorsqu’il est exécuté dans l’itération de Mandelbrot. Le Buddhabrot calcule exactement cette fonction.

Le jacobien de l’itération de Mandelbrot peut être dérivé analytiquement. Pour arriver à une méthode de rendu alternative, au lieu de compter le nombre de trajectoires qui traversent un pixel, on peut calculer le déterminant jacobien moyen de toutes les trajectoires passant par un pixel. Après le rendu, on prend l’inverse de chaque valeur de pixel, en calculant le déterminant jacobien moyen inverse.

Cela générera exactement le même Buddhabrot que l’approche de l’histogramme, jusqu’à un facteur d’échelle global. Au début, j’espérais que cela serait beaucoup plus efficace que l’approche par histogramme, et c’est le cas pour de faibles nombres d’itérations. Cependant, l’inversion à la fin gonfle considérablement la variance lorsque le nombre d’itérations est plus élevé, et cette approche se révèle beaucoup moins efficace que l’histogramme standard.

Traduit avec www.DeepL.com/Translator

Source : https://benedikt-bitterli.me/buddhabrot/

Ma playlist de méditation que vous pouvez entendre aussi en cérémonie :