Poisson Engine — Quand les algorithmes CPU deviennent les pires sur GPU

L'erreur du premier jour

Ma première implémentation du spatial hashing sur GPU était un portage direct de l'algorithme CPU. Un quadtree. Avec des pointeurs. Et de la récursion.

Résultat : plus lent que le CPU. Comment est-ce possible avec 10 000 threads parallèles ?

Le GPU ne fonctionne pas comme le CPU

Le quadtree viole toutes les règles du GPU : branches imprévisibles, accès mémoire dispersés, récursion, structures dynamiques.

La solution : Blelloch prefix-sum sur spatial hash grid

Au lieu d'un arbre, Poisson Engine utilise un spatial hash grid avec un Blelloch parallel prefix-sum. L'algorithme se décompose en 3 passes compute :

Passe 1 : Binning atomique

Chaque thread calcule la cellule de son entité et incrémente un compteur atomique :

@compute @workgroup_size(256)
fn bin_entities(@builtin(global_invocation_id) id: vec3<u32>) {
    let entity_id = id.x;
    if (entity_id >= entity_count) { return; }

    let pos = positions[entity_id];
    let cell = vec2<i32>(floor(pos / cell_size));
    let cell_idx = cell.y * grid_width + cell.x;

    atomicAdd(&cell_counts[cell_idx], 1u);
}

Passe 2 : Prefix-sum (Blelloch scan)

Transforme les compteurs [3, 1, 4, 1] en offsets [0, 3, 4, 8] — en O(n) sur le GPU, avec une phase up-sweep et une phase down-sweep.

Passe 3 : Réordonnancement

Chaque entité est placée dans un tableau trié par cellule. Résultat : pour trouver les voisins, on regarde la cellule courante et ses 8 voisines. O(1) au lieu de O(n²).

Le pipeline complet en 8 passes

Chaque frame, Poisson Engine exécute 8 compute shaders séquentiels :

1. Biologie — métabolisme, faim, énergie
2. Grid Clear — reset du spatial hash
3. Grid Bin — binning atomique dans les cellules
4. Prefix Sum — Blelloch scan pour les offsets (GPU ou fallback CPU)
5. Reorder — tri des entités par cellule pour accès cache-cohérent
6. Flocking — séparation, alignement, cohésion (Boids) + forces environnementales
7. Physics Integration — drag, speed clamp, position update, edge behavior
8. Hunt — détection de proies (optionnel)

La fallback chain

WebGPU n'est pas universel. Poisson détecte automatiquement les capacités et bascule :

L'architecture SoA (Structure-of-Arrays) — 40+ typed arrays plats pré-alloués — est partagée entre les 3 renderers. Seul le code compute change. Zéro garbage collection.

L'émergence : la sélection naturelle sur GPU

Chaque entité a un génome stocké dans des typed arrays : vitesse max, rayon de perception, taille, métabolisme. Ces gènes mutent lors de la reproduction.

Après 1 000 générations, l'évolution est visible à l'œil nu : les poissons rapides dominent les zones à prédateurs, les poissons économes colonisent les zones pauvres en nourriture. La sélection naturelle émerge spontanément — sans être programmée explicitement. C'est la preuve que l'architecture est correcte.

Ce que j'en retiens

1. Ne portez jamais un algorithme CPU sur GPU tel quel. Repensez-le en tableaux plats, accès coalescents et passes parallèles.

2. Le Blelloch prefix-sum est le couteau suisse du GPU. Tri, histogrammes, filtrage, compaction — tout passe par le prefix-sum.

3. La fallback chain est obligatoire. Un produit qui ne fonctionne que sur Chrome 113+ n'est pas un produit. La dégradation gracieuse (WebGPU → WebGL → Canvas2D) est non négociable.

4. L'émergence valide l'architecture. Quand un comportement complexe (l'évolution) naît de règles simples (mutation + sélection), c'est la meilleure preuve que le système est correctement conçu.