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.
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) :
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.
![]() |
(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 ...
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 :
Dans le code précédent, il existe 3 valeurs intéressantes :
:
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.
canvas
ayant pour
id drawing_board
12
|
- 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 entre0
et255
; 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.
Node.js
qui simule le
fonctionnement des canevasnpm install canvas
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
-
É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. -
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())→ -
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 tored
) -
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
- Textures très faciles : réaliser une texture monochrome, paramétrée par la couleur de la texture
- 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).
- Textures basées sur la génération de
bruit spatial
: - (Facile) Bruit blanc et bruit blanc limité en fréquence
- (Normal) Bruit de Perlin et variantes (value noise, gradient noise, simplex noise, cf. aussi ce lien et ce document)
- (Normal) Bruit fractal (FBM = fractional brownian motion) (cf. aussi ce lien et celui-ci);
- (Difficile) Bruit par densité spectrale (ou bruits colorés)
- (Difficile) Bruit de Worley et variantes (cellular noise, cf. ce lien);
- (Très difficile) Bruit de Gabor
- 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, là, là et là).
- 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 là).
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 :
Le
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 / -- Base directory Makefile -- Global Makefile /src -- Source files /public -- Web files (should be empty in the repository)
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
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
Les paquetages Node.js nécessaires au fonctionnement du code doivent se restreindre à la liste suivante :
La page
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. |