Journal Computer Graphics de Scratch de Gabriel Gambetta

J'ai acheté l'ebook de Computer Graphics de Gabriel Gambetta. (et en écrivant ce journal, je découvre que le contenu est gratuitement accessible sur son site).

J'ai toujours été intéressé par les images générées par ordinateur et j'ai voulu comprendre comment ça marche. Comment avec plein de ma~~gie~~ths, on pouvait réussir à générer des pixels ? C'est quoi exactement une carte graphique ? Que voulez vous dire par accélération 3D matérielle ? Par opposition à logicielle ? Expliquez moi. Je suis né en 1990, Je n'ai pas connu l'avènement des cartes 3D. Mon premier ordinateur était déjà équipé d'une nVidia GeForce4 MX 440. Il aura aussi connu mes débuts avec Linux et Debian Sarge, mais c'est une autre histoire. Je vie dans un monde où l’accélération matérielle 3D est la norme et où elle propulse la 2D. J'ai longtemps pas tous compris à ces histoires de framebuffer et d'adresse 0xA0000. Tellement de connaissances à combler !

Depuis que j'ai commencé à programmer (calculatrice Casio Graph 25 à 14 ans et python à 15 ans grâce à jujun<), j'ai plusieurs fois tenté d'implémenter un raycaster à la wolfenstein3D. Au cours des années, plus d'une fois je suis tombé sur ce (site)[https://lodev.org/cgtutor/raycasting.html], et bloqué sur l'algorithme de lancé de rayons et la détection avec les murs. Je refusais de copier son code, je voulais réussir à comprendre et retrouver l'algorithme par moi même.

J'ai profité de mes vacances de Noël 2021 pour lire Game Engine Black Book: Wolfenstein 3D sur le moteur de Wolfeinstein 3D et Game Engine Black Book DOOM sur le moteur de Doom par Fabien Sanglard. (les sources TeX des deux livres sont disponibles ici GEBB Wolfenstein GEBB Doom. des versions PDF sont disponibles sur Archive.org là GEBB Wolfenstein GEBB Doom.). C'est aussi très instructif sur l'informatique de ces années là, le matériel, comment interagir avec, comment optimiser au mieux pour générer de la 3D avec le CPU, pixel par pixel, dans un framebuffer. Du coup, j'ai compris pourquoi on appelé ça des "cartes accélératrices 3D", parce que c'est des cartes, et qu'elles accélère les calculs mathématiques relatifs à la 3D. Tout était dans le nom. Mais je me

En quelques soirs, en rust, je réussi à créer un raycaster à la Wolfenstein.

C'est moche, y'a des aberrations optiques, y'a que 3.5 couleurs gérés, mais je m'en fou. C'est l'accomplissement de ma vie de développeur. Il m'aura fallu 15 ans pour intégrer toutes les connaissances nécessaires afin d'y arriver en quelques heures à lancer des rayons virtuels sur des murs pour afficher des pixels coloriés.

Comme dit précédemment le projet a été écrit initialement en rust. Au taf, j'ai été désigné volontaire pour évaluer typescript. Comme ce n'est pas mon cœur de compétences, que ça fait longtemps que je n'ai pas touché au front et que je déteste ça, si j'arrivais à sortir quelque chose, tout le monde dans l'équipe devrait pouvoir y arriver :P

Refusant de faire un truc demandant trop d'interaction avec le DOM, mais voulant quand même faire des trucs rigolos notamment avec les objets et les maths, je décida de porter le moteur vers ce langage. Cela ne prit que quelques heures. Pas de mauvaises surprises. Juste l'écriture d'un nouveau backend pour dessiner sur un canvas au lieu de dessiner sur une surface sdl. Pour le fun, j'ai aussi ajouté un backend SVG ainsi qu'un multiplixeur de backends. Ça veut dire que quand l'engin va faire appel à une primitive de dessin, celle ci peut être réalisé par plusieurs backends afin d'avoir en même temps un affichage dans un canvas HTML et 2 SVG. Ça sert à rien, mais je pouvais le faire pour à peines quelques lignes de code de plus (et une agonie de mon CPU), alors je l'ai fait

Une démo est disponible ici. C'est auto-hébergé à la maison, ne tuez pas mon netbook^serveur boosté à la poudre verte :)

Les deux "Black Books" de Fabien Sanglard cités plus haut m'ont beaucoup aidé pour l'écriture du moteur. J'utilise la technique du raycasting : pour chaque colonne de pixels de l'écran, je lance un "rayon" pour mesurer la distance du mur le plus proche. Puis je détermine la hauteur que devrait avoir cette section de mur à l'écran grâce à une formule de projection (1 / distance * cos(ray_direction) pour les curieux) et la dessine sous la forme d'une ligne verticale bleue large de un pixel. J'ai rien inventé, c'est grosso modo le fonctionnement de wolfenstein3D et doom.

TL;DR:

pour chaque colonne de pixels de l'écran faire
   calculer la distance au mur le plus proche dans cette direction
   calculer la hauteur de que cela représente sur l'écran
   déterminer la couleur à afficher # TODO: en attendant on va utiliser un bleu moche
   dessiner une ligne verticale sur cette colonne
finpour

Vous pouvez analysez le SVG de la démo avec les outils Web Developer de votre navigateur et constatez qu'une frame est toujours composée de

• 1 rectangle gris foncé, occupant la moitié haute de l'écran et représentant le plafond
• 1 rectangle gris clair, occupant la moitié basse de l'écran et représentant le sol
• 800 lignes verticales bleues de 1 pixel représentant toutes les sections de murs visibles

C'est une manière inefficiente de dessiner une scène là où un moteur polygonal s'en serait sorti avec 2 polygones pour les sols et plafonds et 5 polygones pour les murs visibles.

Mais c'est une manière très simple de faire le rendu d'une scène en utilisant uniquement de la 2D. Car voyez-vous, mon moteur 3D n'est en réalité qu'un moteur "2.5D" : absolument tous mes calculs se font dans un univers en deux dimensions. Je n'ai même pas de classe Vector3, juste Vector2… La logique est faite en utilisant uniquement une vue de dessus. La notion de 3D n’apparaît vraiment qu'au tout dernier moment, quand il faut déterminer la hauteur de la ligne pour représenter le mur en fonction de sa distance.

Il est aussi à noter que ma scène n'est pas composé par des polygones. En réalité, j'utilise des SDF (signed distance functions). Ma scène est "vectorielle" : elle est représenté par des fonctions mathématiques donnant la distance entre un point arbitraire (la caméra) et le point le plus proche de la forme représenté par la fonction ainsi que d'opérateurs ensemblistes. Pour résumé, la scène que vous voyez là haut a pour formule level(pos) = 0 - (rect_salle_1(pos) + rect_salle_2(pos) + rect_salle_3(pos)). Par défaut, les rectangles sont "pleins". Je les additionnes pour créer la forme du niveau et je les soustrais à un univers "plein" (distance de 0 car en tout point je suis dans "quelque chose") pour me retrouver avec un univers "plein" avec un "trou" de la forme de mon niveau dans lequel évolue la caméra. Avec une combinaison de fonctions mathématiques plutôt simples, on peut représenter des formes très complexes. Pis ça simplifie aussi pas mal l'import des fichiers de niveau (<rect3> <rect2> union <rect1> union 0 diff (je vous ai déjà parlé de mon amour pour les machines à stack et de la notation post fixé ? (et de mon amour des parenthèses ?)).

J'ai beaucoup été aidé par cet article de Jamie Wong. Lui utilise les SDF dans des shaders pour faire des jolies trucs en 3D. Mais c'était "close enougth" pour qu'avec son travail, j'ai pu utiliser les SDF pour mes cercles et rectangle afin de dessiner dans un framebuffer à l'ancienne avec mon cpu comme on faisant avant dans le temps quand c'était mieux avant. D'ailleurs, saviez vous que la formule du cercle était bien plus simple que le rectangle ? Un cercle, c'est simple, c'est tous les points de l'espaces situés à une certaine distance appelée rayon d'un point appelé centre. Et du coup, qu'elle est la plus petite distance entre un point quelconque et le plus proche point sur le cercle ? Facile, la distance entre le point et le centre du cercle, moins le rayom. C'est simple le cercle, j'aime le cercle. Adoptez le cercle dans votre vie.

export function circle_sdf(center: Vector2, radius: number, point: Vector2): number {
    return point.sub(center).length() - radius;
}

Si vous aimez la souffrance, choisissez le rectangle. Par ce qu'après tout, qu'est-ce qu'un rectangle ? C'est l'ensemble des points situés à une certaine distance de quoi ? Ben j'ai pas trouvé comment l'exprimer mathématiquement, mais en code ça donne ça :

export function rect_sdf(center: Vector2, size: Vector2, point: Vector2): number {
    // Compute the relative position of the point to the center of the box
    let a = point.sub(center).abs().sub(size.div(2));

    // Measure the distance of the point to the exterior of the rect
    let outside_distance = a.max(0).length();

    // Measure the distance of the point to the interior of the rect
    let inside_distance = Math.min(Math.max(a.x, a.y), 0);

    // compute the final distance
    let sdf = outside_distance + inside_distance;

    return sdf;

}

Et cela que je suis content de ne pas être en 3D et de ne pas avoir à gérer les deux faces en plus :P

Et donc voila, juste avec la formule level(pos) = 0 - (rect_salle_1(pos) + rect_salle_2(pos) + rect_salle_3(pos)), je peux facilement calculer la position de tous les points visibles de "murs" (techniquement, les bordures des rectangles composant les limites du niveau) de ma scène, calculer leur distance à la caméra, déterminer leur hauteur sur l'écran, et dessiner plein de colonnes de pixels. J'vous jure. C'est aussi simple que ça. Voyez par vous même :

export function render(scene: Scene, camera: Camera, drawer: Drawer, viewport_size: Vector2) {
    // Clear the screen
    drawer.clear();

    // Draw the ceil and floor
    drawer.draw_floor();
    drawer.draw_ceil();

    // Draw the walls, column of pixel per column of pixel
    // We start by the left side of the view port and scan
    // the scene to right side
    let start_direction = camera.left();
    let fov_per_column = camera.fov / viewport_size.x;
    for (let column = 0; column < viewport_size.x; ++column) {
        // Compute the direction of the ray for the current column
        let ray_direction = start_direction.rotate_by(fov_per_column * column);
        //console.log(`ray direction: ${ray_direction.to_str()}`);

        // Get the distance to the nearest
        let wall_distance = ray_marching(scene, camera.position, ray_direction);
        //console.log(`column: ${column}, distance: ${wall_distance}`);

        // Only draw the segment if the wall is visible
        if (wall_distance > 0 && wall_distance < Infinity) {
            // Compute the color
            let color = `rgb(0, 0, ${255 - (2 * wall_distance) ** 2})`;

            // Try to map the sphere projection of the ray marching algo to
            // a planar one. Doesn't work for fov > 90°. Kind of work for fov <= 90°
            let angle_from_center = ray_direction.angle() - camera.direction.angle();
            wall_distance = wall_distance * Math.cos(angle_from_center);

            // Compute the scale ratio
            // the nearest, the biggest
            let scale_ratio = 1.0 / wall_distance; // Basic persupective transformation

            // Compute the final height and do the the drawing
            let wall_height = viewport_size.y * scale_ratio;


            drawer.draw_wall(column, wall_height, color);
        }
    }
}

Sinon, j'ai bien aimé typescript, moins tous les à côtés nécessaires pour que ça marche (genre les "packers", j'aimerai vraiment être dans une timelime parallèle, naif, innocent et ignorant de l'existance de gulp). Le langage et l'IDE (vscodium) ont vraiment rattrapés pleins de petites erreurs d’inattention dès l'étape de codage, là où je les aurais probablement découvert à l’exécution avec javascript. Je pense qu'il faut vraiment utiliser le langage par défaut à la place de javascript si il est possible d'intégrer cette horreur de nodejs dans votre environement de développement (désolé, je n'ai vraiment rien aimé de l'écosystème nodejs à part typescript et peut-être viteuf un vuejs parce que j'ai pu faire des SVG rigolos dont je te parlerai une autre fois). Heureusement, il n'a pas besoin de souiller votre immaculé production qui peut ainsi rester pure et innocente. De plus, il est possible de l'adopter graduellement. On l'utilise sur du pur javascript pour attraper les plus grosses erreurs (typescript étant un sur-ensemble de javascript, tout code javascript valide est un code typescript valide), puis d'ajouter les annotations de type, puis … et au fur et à mesure des temps morts, vous pourrez migrez votre base de code.

Le raycasting, c'est bien, c'est simple. Mais pourquoi lancer un rayon par colonne de pixels à l'écran quand on peut lancer un rayon PAR pixel visible à l'écran ? Et le faire rebondir sur les surfaces brillantes ? Avec le raytracing, vous pouvez ! Et c'est l'un des sujets du livre présenté en introduction de ce journal.

Le livre explique comment écrire deux moteurs de rendu, l'un basé sur le raytracing et l'autre sur la rasterization. Les explications sont claires. Ils donnent toutes les maths impliqués et les expliquent de manière suffisament claire pour que je les comprenne. Il y a de nombreuses illustrations pour visualiser les concepts mathématiques. L'auteur donne aussi des exemples d'implémentations en pseudo-c des algorithmes importants, tout en laissant en exercice au lecteur l'écriture du backend qui s'occupe du dessin, ce qui ne limite pas le livre à une bibliothèque ou un cadriciel particulier. J'aurai pu choisir typescript et SVG, mais j'ai préféré rust et framebuffer (qui est ensuite écrit sous forme de png sur le disque ou utilisé en tant que texture opengl).

En suivant le livre, j'ai pu obtenir cette scène composée de 4 sphères (sauras-tu trouver la 4ème ?). Il n'y a pas encore le support des ombres, mais ça avance bien.

Les performances ne sont pas terribles, 50fps en 640x480 chez moi. Nais que vous voulez vous, je tiens à utiliser un framebuffer pour faire comme au temps d'avant, et les calculs ne scalent pas très avec le nombre de pixel quand ton code est purement monothreadé…

Pour les curieux, le code est là.

À la base, j'étais venu vous dire d'acheter le bouquin, il est bien. Mais je crois que j'ai un peu divergé. Pis il s'avère que le bouquin est gratuit. Bon ben bonne lecture!