Available nodes

 Génération procédurale

La génération procédurale est une méthode générale consistant à produire des objets en utilisant des outils algorithmiques, plutôt que de les créer à la main. Un exemple foisonnant de techniques de génération procédurale se trouve dans la génération de textures graphiques, des objets utilisés traditionnellement pour "habiller" des objets 3D.
(image tirée d'un article sur l'esthétique des textures, de Jacob et. al. sur ResearchGate)

L' étude récente de Dong et. al. fournit de nombreux exemples de techniques de génération procédurale, parmi lesquelles on peut compter (entre autres, la liste n'est pas exhaustive) :
  • les automates cellulaires,
  • les équations de réaction-diffusion,
  • les diagrammes de Voronoï,
  • les techniques à base de bruit comme le bruit de Perlin,
  • les fractales ...
Ce projet propose de mettre en place un ensemble de bibliothèques de fonctions permettant de générer des textures, mais aussi de les transformer et de les composer. Chacun de ces algorithmes doit pouvoir être appliquable de manière indépendante grâce à la bibliothèque, mais une des finalités du projet sera de produire une interface permettant de paramétrer ces algorithmes et d'afficher le résultat produit.

 Génération d'image

Autant l'affichage d'images dans un navigateur est un problème trivial, autant la génération d'image demande un tout petit peu de travail. Le code suivant permet de construire une image bariolée dans votre navigateur, à l'intérieur d'un élément HTML canvas ayant pour id drawing_board12:
function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

const width = 350, height = 250;
let canvas = document.getElementById('drawing_board');
canvas.width = width; canvas.height = height;
let context = canvas.getContext("2d");
let image = context.createImageData(width, height);
let n = 0; // Index inside the image array
for (let y = 0; y < canvas.height; y++) {
    for (let x = 0; x < canvas.width; x++, n += 4) {
        image.data[n]   = getRandomInt(256);
        image.data[n+1] = getRandomInt(256);
        image.data[n+2] = getRandomInt(256);
        image.data[n+3] = 255;
    }
}
context.putImageData(image, 0, 0);
Dans le code précédent, il existe 3 valeurs intéressantes:
  • un noeud HTML canvas servant de canevas3 et dans lequel l'image va être dessinée;
  • un contexte associé au canevas, qui sert d'objet intermédiaire permettant de créer l'image, et ensuite de la dessiner à l'intérieur du canevas;
  • une image obtenue à l'aide du contexte, sous la forme d'un tableau de taille width * height * 4 prenant des valeurs entières comprises entre 0 et 255; le tableau est une suite de quadruplets (R,G,B,A), autant que de pixels dans l'image, représentant les composantes rouges, vertes et bleues du pixel, ainsi que son niveau de transparence4.
Le projet se propose de faire de la génération d'image à la fois dans et hors du navigateur. Il est possible de générer l'image suivant à l'aide d'une bibliothèque Node.js qui simule le fonctionnement des canevas:
npm install canvas
Le code est quasiment équivalent à celui utilisé sur le navigateur, et accessible dans le fichier suivant . La petite différence tient dans le fait d'exporter l'image dans un fichier.

 Description du projet

Le projet se propose de réaliser à la fois une bibliothèque permettant de générer de manière procédurale un ensemble de textures, et de visualiser les effets des différents algorithmes dans une page HTML. Une décomposition des tâches possibles est discutée ici, et une liste d'algorithmes à implémenter est proposée dans la section suivante
  1. Écrire le code nécessaire pour définir précisément ce qu'est une couleur, une image et un filtre. On pourra s'inspirer des techniques vues en cours parlant de types abstraits de données.
    Il pourra être ainsi envisageable de représenter les images comme des fonctions, comme des tableaux, ou comme des dictionnaires contenant les éléments précédents et d'éventuelles méta-informations.
  2. Proposer une façon d'arranger dans votre code des ensembles de générateurs et de filtres. On pourra s'inspirer des techniques vues en cours de programmation dirigée par les fonctions. Les fonctions devraient pouvoir se composer aisément pour permettre de construire des images plus complexes. Par exemple:
    tileBoard()
    chessBoard()
    lerp(tileBoard(), chessBoard())
  3. Proposer une manière de gérer les paramètres des différents générateurs et filtres. Par exemple, un générateur de gradient devrait pouvoir être paramétré en fonction des couleurs utilisées dans le gradient, et de la direction du gradient. Au vu des nombreux filtres et de leurs paramètres riches et variés, il s'agira de penser un système aussi générique que possible. En particulier, on pourra imaginer un système pour associer des valeurs par défaut aux générateurs et autres filtres.
    gradient(color2: yellow, dir: 45)
    (color1 defaults to red)
  4. Proposer une manière de gérer les textures complexes, comme des compositions partant de textures simples et de filtres. L'idée serait de pouvoir construire des arbres de scène que l'on puisse construire soit de manière algorithmique, soit à partir d'une description au format JSON 5.
    lerp:
        inputs: [
            chessboard,
            noise:
                input: tileboard
        ]

 Générateurs et filtres

Cette section propose un ensemble de générateurs et de filtres implémentables dans le cadre du projet. Elle n'a pas vocation à être forcément exhaustive, et elle pourrait être étendue au fur et à mesure des propositions. Chaque proposition est associée à un niveau de difficulté6. Il est demandé d'implémenter dans ce projet plusieurs éléments de cet ensemble, au choix, en partant des éléments étiquetés comme "très faciles". Toutefois, l'évaluation finale du projet pourra dépendre des niveaux de difficulté des générateurs implémentés.
L'ensemble des propositions est ici extrêmement varié. Ne vous attendez pas à ce que vos encadrants soient à même de vous expliquer tous les problèmes instantanément. N'hésitez pas à vous documenter et à poser des questions.

Générateurs

  1. Textures très faciles : réaliser une texture monochrome, paramétrée par la couleur de la texture
  2. Textures basées sur les pavages:
    • (Facile) Pavages réguliers (n'utilisant qu'un seul type de polygone régulier);
    • (Normal) Pavage semi-régulier (combinaisons de différents polygones réguliers, une liste est disponible);
    • (Normal) Transformations isométriques des pavages (rotation, translation, symétrie);
    • (Normal) Pavage par des polygones concaves ou étoilés;
    • (Difficile) Pavage pentagonal;
    • (Difficile) Ajouter des déformations quelconques (transformations non isométriques) pour obtenir, par exemple, des motifs similaires aux gravures d'Escher;
    • (Très difficile) Implémenter les mêmes modèles que ci-dessus, mais en remplaçant l'espace du plan cartésien par un espace hyperbolique (par exemple, le disque de Poincaré, voir aussi cette page).
  3. Textures basées sur la génération de bruit spatial:
  4. Textures basées sur les calculs de distance:
    • (Facile) Reprendre les pavages réguliers et semi-réguliers et rajouter un calcul de distance (distance euclidienne ou distance de Manhattan) entre le pixel courant et la bordure du carreau dans lequel il se trouve;
    • (Normal) Diagrammes de Voronoi et/ou triangulations de Delaunay (cf. ce lien);
    • (Normal) Interpolation à base de fonctions radiales (RBF = Radial Basis Functions)
    • (Difficile) Interpolation à base de distance signées (SDF = Signed Distance Functions) ;
    • (Difficile) Utiliser les calculs de distance pour générer un anticrénelage des textures générées par interpolation (bilinéaire ou bicubique) des pixels voisins (cf. ici, , et ).
  5. Textures basées sur des simulations numériques:
    • (Difficile)Textures obtenues par les automates cellulaires (modèles d'automates donnant des textures intéressantes: forest fire, Boltzmann, Greenberg-Hastings, voir aussi ce lien);
    • (Très difficile) Textures par réaction/diffusion (modèle de Gray-Scott, cf. ici et ).

Filtres

  • (Très facile) Un filtre qui fasse la composition de deux images (multiply, screen, divide, plus, minus …)
  • (Facile) Toutes les techniques à base de convolution (détection et/ou renforcement des contours ou au contraire, ajout de flou)
  • (Facile) Toutes les techniques de transformations colorimétriques qu'on peut trouver dans les logiciels de manipulation d'images (augmentation/diminution du contraste, de la luminosité, de la saturation …);
  • (Normal) Déformations spatiales (contraction ou dilatation de l'espace, déformations en sphère ou en spirale, transformations conformes, techniques de warping);
  • (Difficile) Amélioration des bordures de la texture pour atténuer l'effet de répétition visuelle (seamless textures) lorsqu'on répète la texture plusieurs fois en vertical ou en horizontal.

 Détails techniques

Pour les besoins du projet, les fichiers devront être organisés de la manière suivante dans le dépôt :
    /               -- Base directory
      Makefile      -- Global Makefile
    /src            -- Source files
    /public         -- Web files (should be empty in the repository)
Le Makefile doit contenir une règle test permettant d'exécuter les tests propres au projet, ainsi que d'une règle gen pour générer un ensemble de fichiers dans le répertoire public. Le fichier principal doit pouvoir être démarré en utilisant la commande suivante :
node src/main.js
Les paramètres passés à cet exécutable sont laissés à la liberté des programmeurs, néanmoins ils doivent être décrits précisément dans la documentation. A part les répertoires src et public, d'autres fichiers peuvent se trouver dans le dépôt s'ils sont indispensables au projet. La commande make gen doit générer une page public/index.html valide, ainsi qu'un ensemble de fichiers js dans le même répertoire.
Le dépôt ne devra en aucun cas contenir les modules Node.js utilisés dans le code. Toute présence d'un quelconque répertoire node_modules d'une taille strictement positive dans le dépôt à un instant du développement verra attribuer un malus de -2 à la note finale du projet, ce malus étant cumulatif.
Les paquetages Node.js nécessaires au fonctionnement du code doivent se restreindre à la liste suivante: canvas, typescript, eslint, browserify et parcel.
La page public/index.html ne devra en aucun cas faire appel à une quelconque ressource sur le réseau, et devra donc pouvoir s'exécuter sans accès à Internet.

 Recommandations

Pour l'ensemble du projet, il est recommandé de systématiquement :
  • Définir formellement les éléments nécessaires pour représenter le jeu, et les relier à leur implémentation.
  • Définir formellement les algorithmes proposés, et étudier leur complexité (temps/mémoire).
  • Caractériser dans les algorithmes et structures de données ce qui ressort de la programmation fonctionnelle et ce qui n'en est pas.
  • Suivre les standards de codage développés dans le cours de programmation fonctionnelle et disponibles à l'adresse suivante.

 Contact

Pour toute information complémentaire, contacter : David RENAULT et Christophe SCHLICK.

1.La documentation de ces fonctions est accessible sur la page de Mozilla.
2.En fait, miracle de la technologie (!), le code de gauche est exactement celui utilisé pour calculer l'image de droite au chargement de cette page.
3.Les dictionnaires anglais-français semblent préférer le mot 'toile' comme traduction en français, mais admettent le mot 'canevas', qui a des origines venant des deux bords.
4.Il existe d'autres formats d'image supportés, mais on se contentera de celui-ci dans ce projet.
5.Il est explicitement hors-sujet d'écrire une quelconque forme de parseur. Si jamais vous vous trouvez dans le besoin de charger des informations sous un format particulier, seul le JSON (à travers JSON.parse est autorisé. Toute présence dans le code d'une quelconque fonction eval sera violemment réprimée.
6.Aussi objectif que possible.