Flame Maker – Etape 3 – Dessinateur Flame
Introduction
Le but de cette étape est de modifier le programme de l'étape précédente pour qu'il puisse générer des images de fractales Flame en niveaux de gris.
Fractales Flame
Introduction
Les fractales Flame sont une évolution des fractales IFS. La version simplifiée de ces fractales utilisée dans ce projet diffère des fractales IFS en deux points :
- Les transformations caractérisant ces fractales ne sont plus de simples transformations affines mais incluent également des transformations non-linéaires, décrites plus bas.
- Le dessin des fractales est plus sophistiqué et permet de produire des images en niveaux de gris. (Ce dessin sera d'ailleurs encore affiné lors de l'étape suivante afin de produire des images en couleur.)
Tout comme une fractale IFS, une fractale Flame est donc caractérisée par un ensemble de \(n\) transformations \(\{ F_1, \ldots, F_n \}\). Toutefois, chacune de ces transformations n'est plus une simple transformation affine comme dans le cas des fractales IFS, mais la somme pondérée de la composition d'une transformation affine et de différentes transformations non-linéaires prédéfinies nommées variations. Chacune de ces transformations a donc la forme suivante : \[ F_i(x, y) = \sum_{j=0}^{5}{w_{i,j} \cdot V_j(G_i(x, y))} \] où \(G_i\) est une transformation affine, \(w_{i,j}\) est le poids de la variation d'indice \(j\) et \(V_0\) à \(V_5\) sont les six variations, nommées et définies ainsi (dans ces formules, \(r\) est la coordonnée polaire \(r\) du point, c-à-d \(r = \sqrt{x^2 + y^2}\)) :
- Linear
- Sinusoidal
- Spherical
- Swirl
- Horseshoe
- Bubble
Etant donné que la variation \(V_0\), Linear, est l'identité, il est possible de retomber sur une fractale IFS en définissant tous les poids à 0 sauf le premier, qu'on définit à 1. En d'autres termes, on obtient une fractale IFS en définissant les poids ainsi : \[ w_{i,j} = \begin{cases} 1 & \mbox{si $j = 0$}\\ 0 & \mbox{sinon} \end{cases} \]
Mise en œuvre Java
Introduction
Les classes à écrire pour cette étape sont très similaires aux classes écrites pour l'étape précédente. Pour gagner du temps, il est donc souvent judicieux de s'inspirer de ces dernières. Toutefois, les classes de ces deux étapes sont indépendantes et aucune tentative ne sera faite de les lier entre-elles par des relations d'héritage, par exemple.
Variations
La classe abstraite Variation
du paquetage ch.epfl.flamemaker.flame
modélise les variations. Une variation étant une transformation, cette classe implémente l'interface Transformation
de l'étape 1.
Les variations sont nommées et indexées, et la classe Variation
possède donc deux champs privés et non modifiables. Le premier, de type int
, contient l'indice de la variation. Le second, de type String
, contient son nom. Le constructeur de la classe Variation
prend ces deux valeurs en argument et les stocke dans les champs correspondants.
Chacune des six variations définies ci-dessus est placée dans une sous-classe concrète de la classe Variation
. Il serait bien entendu possible de nommer les classes représentant les différentes variations. Toutefois, étant donné que seule une instance de ces classes est nécessaire, il est plus élégant d'utiliser des classes imbriquées anonymes.
Ces instances uniques des différentes variations doivent être stockées dans le champ public statique et non modifiable ALL_VARIATIONS
de la classe Variation
. Ce champ est une liste de variations, et chaque variation doit être à la position correspondant à son index. Par exemple, la variation Linear a l'indice 0 et doit donc se trouver à la position 0 de la liste.
En résumé, la classe Variation
a la structure suivante :
public abstract class Variation implements Transformation { private final String name; private final int index; private Variation(int index, String name) { /* … */ } public String name() { /* … */ } public int index() { /* … */ } abstract public Point transformPoint(Point p); public final static List<Variation> ALL_VARIATIONS = Arrays.asList(new Variation(0, "Linear") { public Point transformPoint(Point p) { // … } }, // … ); }
La méthode statique asList
de la classe Arrays
prend un nombre variable d'arguments et retourne une liste non modifiable avec les éléments reçus. La méthode garantit que cette liste offre un accès en O(1) à n'importe lequel de ses éléments.
Transformation Flame
La classe FlameTransformation
du paquetage ch.epfl.flamemaker.flame
modélise une transformation Flame, c'est-à-dire la composition pondérée d'une transformation affine avec plusieurs variations. Comme il s'agit d'une transformation, elle implémente l'interface Transformation
définie lors de la première étape.
Cette classe possède deux champs privés et non modifiables. Le premier, de type AffineTransformation
contient la composante affine de la transformation. Le second, de type double[]
, est le tableau des poids des différentes variations.
FlameTransformation
est équipée d'un seul constructeur public :
FlameTransformation(AffineTransformation affineTransformation, double[] variationWeight)
, qui construit une transformation Flame composée de la transformation affine et des poids donnés. Le tableau des poids doit absolument être copiée par le constructeur (au moyen de la méthodeclone
), pour garantir l'immuabilité de la transformation. Lève l'exceptionIllegalArgumentException
si le tableau de poids n'a pas la bonne taille.
Finalement, la classe FlameTransformation
est équipé d'une unique méthode, transformPoint
, qui est celle de l'interface Transformation
. Comme d'habitude, cette méthode transforme le point passé en argument, d'après la formule donnée plus haut.
Fractale
La classe Flame
du paquetage ch.epfl.flamemaker.flame
, très similaire à la classe IFS
de l'étape précédente, modélise les fractales Flame. Elle est équipée d'un seul champ privé et non modifiable de type List<FlameTransformation>
contenant les transformations caractérisant la fractale.
La classe Flame
possède un unique constructeur public :
Flame(List<FlameTransformation> transformations)
, qui construit une fractale Flame étant donné sa liste de transformations. La liste de transformation doit absolument être copiée par le constructeur, pour garantir l'immuabilité de la fractale.
Elle est de plus équipée d'une unique méthode publique :
FlameAccumulator compute(Rectangle frame, int width, int height, int density)
, qui calcule la fractale dans la région du plan délimitée par le cadreframe
et stocke le résultat dans un nouvel accumulateur de largeurwidth
et de hauteurheight
, qui est retourné. Le nombre d'itérations à effectuer est calculé de la même manière que précédemment, c-à-d en multipliant les paramètreswidth
,height
etdensity
.
Dessin
Introduction
Pour mémoire, lors du dessin d'une fractale IFS, la seule information qui est retenue pour une case de l'accumulateur est un booléen spécifiant si la case en question contient au moins un point de la fractale. Ensuite, tous les pixels correspondant aux cases contenant au moins un point sont coloriées, et on obtient ainsi une image monochrome.
Pour dessiner les fractales Flame, un algorithme plus sophistiqué est utilisé. Cet algorithme compte le nombre de points de la fractale qu'une case de l'accumulateur contient et utilise cette information pour déterminer la luminosité du pixel correspondant. Ainsi, le pixel correspondant à une case ne contenant aucun point est coloriée en noir, et plus une case contient de points, plus le pixel correspondant est blanc.
Une manière simple de mettre cette idée en pratique est d'utiliser une relation linéaire pour calculer la luminosité \(l_p\) d'un pixel \(p\) – allant de 0 (noir) à 1 (blanc) – en fonction du nombre de points \(n_p\) contenus par la case correspondante : \[ l_p = \frac{n_p}{m} \] où \(m\) est le nombre maximal de points contenus par une case de l'accumulateur.
Malheureusement, cette technique produit des images très sombres car beaucoup de cases ne contiennent qu'un faible nombre de points alors que d'autres en contiennent énormément. Dès lors, il est préférable d'utiliser une fonction logarithmique pour calculer l'intensité d'un pixel en fonction du nombre de points que la case correspondante contient : \[ l_p = \frac{\log(n_p + 1)}{\log(m + 1)} \]
Mise en œuvre Java
Accumulateur
L'accumulateur utilisé pour l'étape précédente était très simple et n'enregistrait qu'une information booléenne pour chaque case. Pour cette étape, un accumulateur capable de compter le nombre de points de la fractale contenus dans chaque case est utilisé.
Comme pour l'étape précédente, la représentation de l'accumulateur est répartie sur deux classes : la première, FlameAccumulator
, est non modifiable ; la seconde, FlameAccumulator.Builder
, est un bâtisseur permettant de construire un accumulateur en plusieurs étapes.
La classe FlameAccumulator
possède l'unique constructeur privé suivant :
FlameAccumulator(int[][] hitCount)
, qui construit un accumulateur avec le tableau bi-dimensionnelhitCount
donné. Ce tableau doit absolument être copié en profondeur par le constructeur afin de garantir l'immuabilité de l'accumulateur.
Contrairement au constructeur de IFSAccumulator
, qui était public, ce constructeur peut être privé car dans cette étape la classe du bâtisseur (Builder
) est imbriquée à l'intérieur de la classe FlameAccumulator
. Rendre le constructeur privé garantit que le seul moyen de construire un accumulateur est de passer par un bâtisseur.
La classe FlameAccumulator
est équipée des méthodes publiques suivantes :
int width()
, qui retourne la largeur (en nombre de cases) de l'accumulateur.int height()
, qui retourne la hauteur (en nombre de cases) de l'accumulateur.double intensity(int x, int y)
, qui retourne l'intensité de la case de l'accumulateur aux coordonnées données. L'intensité est calculée au moyen de la formule logarithmique décrite ci-dessus. A noter que le dénominateur de cette formule est constant et doit, pour des raisons de performance, être calculé à la construction de la classe et stocké dans un champ privé et non modifiable. Lève l'exceptionIndexOutOfBoundsException
si l'une des deux coordonnées est invalide.
La classe FlameAccumulator.Builder
, imbriquée (statiquement) dans la classe FlameAccumulator
, modélise le bâtisseur d'accumulateur. Elle est équipée d'un seul constructeur public :
Builder(Rectangle frame, int width, int height)
, qui construit un bâtisseur d'accumulateur pour la région du plan délimitée par le cadreframe
, de largeurwidth
et de hauteurheight
(en nombre de cases). Lève l'exceptionIllegalArgumentException
si la largeur ou la hauteur n'est pas strictement positive (c-à-d supérieure à zéro).
Cette classe possède de plus les méthodes publiques suivantes :
void hit(Point p)
, qui incrémente le compteur de la case correspondant au pointp
donné. Ne fait rien si le point est en dehors du cadre de l'accumulateur (c-à-d le paramètreframe
passé au constructeur).FlameAccumulator build()
, qui retourne un accumulateur contenant les points collectés jusqu'à présent.
Images PGM
Introduction
Les images PBM utilisées lors de l'étape précédente sont monochromes et ne conviennent donc pas à cette étape. Heureusement, une généralisation des images PBM, appelé PGM, permet de représenter des images en niveaux de gris. Ces deux formats sont très proches l'un de l'autre.
Format de fichier
Tout comme le format PBM, le format PGM est textuel et structuré de manière quasi-identique :
- La première ligne contient la chaîne
P2
qui identifie ce type de fichiers. - La seconde ligne contient la largeur et la hauteur de l'image, séparés par une espace.
- La troisième ligne contient la valeur maximale de luminosité, c'est-à-dire la valeur qui encode la couleur blanc (la couleur noir étant toujours encodée par la valeur 0). Un bon choix pour cette valeur maximale est 100.
- Les lignes qui suivent contiennent les lignes de l'image. Chaque ligne est constituée d'une suite d'entiers allant de 0 (noir) à la valeur maximale (blanc), séparés par une ou plusieurs espaces.
Mise en œuvre Java
Comme pour l'étape précédente, vous devez écrire une classe de test équipée d'une méthode main
qui calcule quelques fractales de test et produit les fichiers PGM correspondants.
Visualisation des images
Pour visualiser les images produites par votre générateur, vous pouvez utiliser les mêmes programmes que ceux mentionnés dans l'énoncé de l'étape précédente.
Test
Comme pour les étapes précédentes, une manière de tester votre programme consiste à lui faire générer des fractales connues et vérifier que vous obtenez l'image attendue.
Shark fin
La fractale Shark fin est caractérisée par les trois transformations suivantes (pour chaque transformations, la partie affine est donnée sous forme matricielle comme précédemment, et les poids non-nuls des variations sont énumérés) :
\[ A_1 = \begin{pmatrix} -0.4113504 & -0.7124804 & -0.4\\ 0.7124795 & -0.4113508 & 0.8\\ 0 & 0 & 1 \end{pmatrix}\\ w_{1,0} = 1, w_{1,1} = 0.1 \] \[ A_2 = \begin{pmatrix} -0.3957339 & 0 & -1.6\\ 0 & -0.3957337 & 0.2\\ 0 & 0 & 1 \end{pmatrix}\\ w_{2,4} = 0.8, w_{2,5} = 1 \] \[ A_3 = \begin{pmatrix} 0.4810169 & 0 & 1\\ 0 & 0.4810169 & 0.9\\ 0 & 0 & 1 \end{pmatrix}\\ w_{3,0} = 1 \]En dessinant cette fractale dans le cadre centré en (-0.25, 0), de largeur 5 et de hauteur 4, dans un accumulateur de 500 sur 400 cases et une qualité de 50, on obtient l'image ci-dessous.
Shark fin
Turbulence
La fractale Turbulence est caractérisée par les trois transformations suivantes :
\[ A_1 = \begin{pmatrix} 0.7124807 & -0.4113509 & -0.3\\ 0.4113513 & 0.7124808 & -0.7\\ 0 & 0 & 1 \end{pmatrix}\\ w_{1,0} = 0.5, w_{1,3} = 0.4 \] \[ A_2 = \begin{pmatrix} 0.3731079 & -0.6462417 & 0.4\\ 0.6462414 & 0.3731076 & 0.3\\ 0 & 0 & 1 \end{pmatrix}\\ w_{2,0} = 1, w_{2,2} = 0.1 \] \[ A_3 = \begin{pmatrix} 0.0842641 & -0.314478 & -0.1\\ 0.314478 & 0.0842641 & 0.3\\ 0 & 0 & 1 \end{pmatrix}\\ w_{3,0} = 1 \]En dessinant cette fractale dans le cadre centré en (0.1, 0.1), de largeur et hauteur 3, dans un accumulateur de 500 sur 500 cases et une qualité de 50, on obtient l'image ci-dessous.
Turbulence
Fougère de Barnsley
Comme expliqué plus haut, toute fractale IFS est également une fractale Flame pour laquelle tous les poids sont définis à 0 sauf le poids de la variation Linear qui est défini à 1. On peut donc dessiner la fougère de Barnsley comme une fractale Flame, et avec les mêmes paramètres que pour l'étape précédente, on obtient l'image ci-dessous. Il est intéressant de comparer les deux versions de l'image pour constater l'impact de l'algorithme de dessin.
La fougère de Barnsley (version Flame)
Résumé
Pour cette étape, vous devez :
- Ecrire les classes
Flame
,FlameTransformation
,FlameAccumulator
,FlameAccumulator.Builder
etVariation
du paquetagech.epfl.flamemaker.flame
en fonction des spécifications ci-dessus. - Ecrire une classe principale (nommée p.ex.
FlamePGMMaker
) dans le même paquetage, équipée d'une méthodemain
qui calcule les fractales Flame de test décrites ci-dessus et produise les images correspondantes dans des fichiers au format PGM. - Vérifier que ces images correspondent à celles données ci-dessus et corriger les éventuels problèmes.
Mises à jour
- 26/02: Le fait que la classe
FlameAccumulator.Builder
soit une classe imbriquée statique est clarifié.