Quadtree & Barnes-Hut

Dompter l'Infini

Imaginez que vous vouliez simuler une galaxie. Des milliards d'étoiles, chacune attirant toutes les autres par la gravité. Pour calculer la force sur une seule étoile, il faut considérer l'attraction de toutes les autres. Pour $n$ étoiles, cela représente $n \times (n-1)$ calculs de force à chaque instant.

O(n^2) \text{ calculs par frame}

Avec 10 000 étoiles, c'est 100 millions de calculs par image. À 60 FPS, votre ordinateur doit effectuer 6 milliards d'opérations par seconde juste pour la physique. C'est le problème des $n$ -corps, et il a longtemps semblé insoluble pour les simulations en temps réel.

« La clé n'est pas de calculer plus vite, mais de calculer moins intelligemment. » — Josh Barnes & Piet Hut, 1986

En 1986, Josh Barnes et Piet Hut ont publié un algorithme révolutionnaire qui réduit cette complexité de $O(n^2)$ à $O(n \log n)$ . Leur secret ? Une structure de données appelée Quadtree et une approximation astucieuse : si un groupe d'étoiles est suffisamment loin, on peut le traiter comme une seule masse ponctuelle.

L'Anatomie du Quadtree

Un Quadtree est une structure de données qui divise récursivement l'espace en quatre quadrants. Chaque nœud représente une région rectangulaire et peut contenir soit des points, soit quatre enfants (Nord-Ouest, Nord-Est, Sud-Ouest, Sud-Est).

Le Principe de Subdivision

Le fonctionnement est simple : chaque nœud a une capacité maximale de points. Quand cette capacité est dépassée, le nœud se subdivise en quatre enfants, et les points sont redistribués.

Boundary : Les limites rectangulaires du nœud (x, y, largeur, hauteur)
Capacity : Nombre maximum de points avant subdivision (généralement 4)
Points : Liste des points contenus dans ce nœud
Children : Les quatre sous-nœuds (NW, NE, SW, SE) créés lors de la subdivision

Cette structure permet de localiser rapidement les voisins d'un point : au lieu de parcourir tous les points, on descend dans l'arbre en ne visitant que les branches pertinentes.

Une Structure Adaptative

La force du Quadtree réside dans sa nature adaptative. Contrairement à une grille uniforme où chaque cellule a la même taille, le Quadtree se subdivise uniquement là où c'est nécessaire. Les régions denses de l'espace — comme le cœur d'une galaxie ou un amas d'étoiles — génèrent de nombreuses subdivisions, créant une mosaïque de petits carrés. À l'inverse, les régions vides ou peu peuplées restent représentées par de grands carrés uniques, économisant mémoire et calculs.

Cette adaptabilité est cruciale pour les simulations réalistes : une galaxie spirale a un centre très dense et des bras de plus en plus clairsemés. Une grille uniforme gaspillerait des ressources sur le vide interstellaire, tandis que le Quadtree concentre sa résolution exactement là où se trouvent les étoiles.

Algorithme d'Insertion

L'insertion d'un point suit une logique récursive élégante :

quadtree.jsjavascript
class Quadtree {
  constructor(boundary, capacity) {
    this.boundary = boundary;  // { x, y, w, h }
    this.capacity = capacity;
    this.points = [];
    this.divided = false;
  }

  insert(point) {
    // Ignorer si le point est hors limites
    if (!this.boundary.contains(point)) {
      return false;
    }

    // S'il y a de la place, ajouter le point
    if (this.points.length < this.capacity) {
      this.points.push(point);
      return true;
    }

    // Sinon, subdiviser si nécessaire
    if (!this.divided) {
      this.subdivide();
    }

    // Insérer dans l'enfant approprié
    return this.nw.insert(point) || 
           this.ne.insert(point) ||

La Subdivision

Quand un nœud atteint sa capacité, il crée quatre enfants qui divisent son espace en quadrants égaux :

quadtree.jsjavascript
subdivide() {
  const { x, y, w, h } = this.boundary;
  const hw = w / 2;  // Demi-largeur
  const hh = h / 2;  // Demi-hauteur

  // Créer les quatre quadrants
  this.nw = new Quadtree({ x: x, y: y, w: hw, h: hh }, this.capacity);
  this.ne = new Quadtree({ x: x + hw, y: y, w: hw, h: hh }, this.capacity);
  this.sw = new Quadtree({ x: x, y: y + hh, w: hw, h: hh }, this.capacity);
  this.se = new Quadtree({ x: x + hw, y: y + hh, w: hw, h: hh }, this.capacity);

  this.divided = true;

  // Redistribuer les points existants
  for (const p of this.points) {
    this.nw.insert(p) || this.ne.insert(p) || 
    this.sw.insert(p) || this.se.insert(p);
  }
  this.points = [];  // Vider le nœud parent
}

Démo : Construction d'un Quadtree

Cliquez dans la zone ci-dessous pour ajouter des points et observer la subdivision dynamique du Quadtree. Remarquez comment les zones denses se subdivisent davantage.

L'Application Barnes-Hut

Le génie de Barnes-Hut est d'utiliser le Quadtree non pas pour trouver des voisins, mais pour approximer les forces gravitationnelles. L'idée centrale : si un groupe d'étoiles est suffisamment loin, on peut le traiter comme une seule masse ponctuelle située au centre de masse du groupe.

Centre de Masse et Masse Totale

Chaque nœud du Quadtree stocke deux informations supplémentaires :

Masse totale : La somme des masses de toutes les étoiles contenues
Centre de masse : La position moyenne pondérée par les masses

\vec{r}_{cm} = \frac{\sum_{i} m_i \vec{r}_i}{\sum_{i} m_i}

Ces valeurs sont calculées récursivement : le centre de masse d'un nœud parent est la moyenne pondérée des centres de masse de ses enfants.

Il est crucial de comprendre que le centre de masse n'est pas le centre géométrique du nœud. Si un quadrant contient une étoile très massive dans un coin et plusieurs petites étoiles ailleurs, le centre de masse sera "tiré" vers l'étoile massive. Imaginez une balançoire avec un éléphant d'un côté et une souris de l'autre : le point d'équilibre n'est pas au milieu, mais très proche de l'éléphant. Cette distinction est essentielle pour la précision de l'approximation Barnes-Hut : c'est la position du centre de masse, pas le centre du carré, qui détermine la direction de la force gravitationnelle.

barnes-hut.jsjavascript
// Extension du Quadtree pour Barnes-Hut
class BarnesHutNode extends Quadtree {
  constructor(boundary, capacity) {
    super(boundary, capacity);
    this.totalMass = 0;
    this.centerOfMass = { x: 0, y: 0 };
  }

  // Calculer masse totale et centre de masse
  computeMassDistribution() {
    if (!this.divided) {
      // Nœud feuille : calculer directement
      this.totalMass = 0;
      let cx = 0, cy = 0;
      
      for (const star of this.points) {
        this.totalMass += star.mass;
        cx += star.x * star.mass;
        cy += star.y * star.mass;
      }
      
      if (this.totalMass > 0) {
        this.centerOfMass.x = cx / this.totalMass;
        this.centerOfMass.y = cy / this.totalMass;

Le Paramètre θ (Theta)

Comment décider si un groupe est "suffisamment loin" ? C'est le rôle du paramètre $\theta$ (theta), qui contrôle le compromis entre précision et performance.

Pour chaque nœud, on calcule le ratio entre sa taille $s$ et la distance $d$ au point pour lequel on calcule la force :

\frac{s}{d} < \theta \Rightarrow \text{utiliser l'approximation}

L'intuition derrière ce ratio est géométrique : $s/d$ représente l'angle sous-tendu par le groupe d'étoiles. Pensez aux étoiles dans le ciel nocturne : bien qu'elles soient des soleils gigantesques, leur distance immense les fait apparaître comme de simples points lumineux. De même, si un amas d'étoiles sous-tend un angle suffisamment petit depuis notre point de vue (c'est-à-dire si $s/d$ est petit), il est raisonnable de le traiter comme une masse ponctuelle unique. Plus le groupe est loin ou petit, plus l'approximation est justifiée.

$\theta = 0$ : Aucune approximation, calcul exact $O(n^2)$
$\theta = 0.5$ : Bon compromis précision/performance (valeur classique)
$\theta = 1.0$ : Approximations agressives, moins précis mais très rapide
$\theta > 1.0$ : Approximations extrêmes, peut devenir instable

En pratique, $\theta = 0.5$ donne des résultats visuellement indiscernables du calcul exact tout en offrant une accélération massive.

Calcul de Force avec Barnes-Hut

L'algorithme de calcul de force parcourt le Quadtree récursivement. À chaque nœud, il décide soit d'utiliser l'approximation, soit de descendre dans les enfants :

barnes-hut.jsjavascript
const G = 6.674e-11;  // Constante gravitationnelle

function calculateForce(star, node, theta) {
  // Nœud vide : pas de force
  if (node.totalMass === 0) {
    return { x: 0, y: 0 };
  }

  const dx = node.centerOfMass.x - star.x;
  const dy = node.centerOfMass.y - star.y;
  const dist = Math.sqrt(dx * dx + dy * dy);

  // Éviter la division par zéro (même étoile)
  if (dist === 0) return { x: 0, y: 0 };

  // Ratio taille/distance
  const ratio = node.boundary.w / dist;

  // Si le nœud est une feuille OU si le ratio est acceptable
  if (!node.divided || ratio < theta) {
    // Utiliser l'approximation : traiter comme masse ponctuelle
    const softening = 10;  // Éviter les singularités

Esthétique et Stabilité

Une simulation de galaxie n'est pas qu'un problème de physique — c'est aussi un défi visuel et numérique. Deux techniques sont essentielles pour obtenir un résultat à la fois beau et stable.

Le Softening : Éviter l'Éjection

La loi de la gravitation de Newton pose un problème : quand deux corps se rapprochent, la force tend vers l'infini ( $F \propto 1/r^2$ ). Dans une simulation discrète, cela peut propulser des étoiles à des vitesses absurdes.

Le softening résout ce problème en modifiant légèrement la formule :

F = \frac{G \cdot m_1 \cdot m_2}{r^2 + \epsilon^2}

Le paramètre $\epsilon$ (epsilon) empêche la force de devenir infinie. Une valeur typique est de l'ordre de la taille d'une étoile dans la simulation.

Rendu Visuel : Densité et Bloom

Pour un rendu esthétique, plusieurs techniques sont combinées :

Couleurs selon la densité : Les zones denses apparaissent plus brillantes et plus chaudes (blanc/jaune)
Effet bloom : Un halo lumineux autour des étoiles brillantes, simulé par un shader de post-processing
Taille variable : Les étoiles plus massives sont rendues plus grandes
Transparence additive : Les étoiles superposées s'additionnent en luminosité

Ces effets sont implémentés efficacement avec WebGL, permettant de rendre des milliers d'étoiles à 60 FPS.

Démo : Simulation de Galaxie

Observez une galaxie spirale simulée avec l'algorithme Barnes-Hut. Utilisez le slider $\theta$ pour voir l'impact sur les performances et la précision. Activez l'affichage du Quadtree pour visualiser la structure sous-jacente.

Analyse de Complexité

Pourquoi Barnes-Hut est-il si efficace ? Analysons la complexité :

Construction du Quadtree : $O(n \log n)$ — chaque insertion traverse au plus $\log n$ niveaux
Calcul des centres de masse : $O(n)$ — une passe sur tous les nœuds
Calcul des forces : $O(n \log n)$ — chaque étoile visite $O(\log n)$ nœuds en moyenne
Total : $O(n \log n)$ au lieu de $O(n^2)$

Pour 10 000 étoiles, on passe de 100 millions à environ 130 000 opérations — une amélioration de près de 1000×.

\frac{n^2}{n \log n} = \frac{n}{\log n} \approx \frac{10000}{13} \approx 770\times

Pourquoi Diviser Rend Plus Fort

Le Quadtree et l'algorithme Barnes-Hut illustrent un principe fondamental en informatique : la division spatiale. En organisant les données selon leur position dans l'espace, on peut ignorer intelligemment les calculs inutiles.

Cette idée s'étend bien au-delà des simulations de galaxies :

Détection de collisions dans les jeux vidéo
Rendu de scènes 3D (culling, LOD)
Recherche géospatiale (trouver les restaurants proches)
Compression d'images (Quadtree image compression)

En 3D, le Quadtree devient un Octree (huit enfants au lieu de quatre), utilisé dans les moteurs de jeux modernes comme Unreal Engine et Unity pour optimiser le rendu et la physique.

L'extension du Quadtree à trois dimensions est naturelle : au lieu de diviser un carré en 4 quadrants, l'Octree divise un cube en 8 sous-cubes (2×2×2). Chaque nœud a donc huit enfants au lieu de quatre. Cette structure est omniprésente dans les applications 3D : les moteurs de jeux l'utilisent pour le culling (ne pas rendre ce qui est hors caméra), la détection de collisions, et le calcul de l'éclairage global. L'algorithme Barnes-Hut s'adapte directement à l'Octree pour simuler des systèmes gravitationnels en 3D, comme les amas globulaires ou les collisions de galaxies.

« Diviser pour régner n'est pas qu'une stratégie militaire — c'est le cœur de l'algorithmique efficace. »

La prochaine fois que vous verrez une simulation de galaxie fluide ou un jeu avec des milliers d'objets interagissant en temps réel, vous saurez qu'un arbre invisible structure l'espace pour rendre l'impossible possible.