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 :

  1. 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.
  2. 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
\[ V_0(x, y) = \left(x, y\right) \]
Sinusoidal
\[ V_1(x, y) = \left(\sin x, \sin y\right) \]
Spherical
\[ V_2(x, y) = \left(\frac{x}{r^2}, \frac{y}{r^2}\right) \]
Swirl
\[ V_3(x, y) = \left(x\sin(r^2) - y\cos(r^2), x\cos(r^2) + y\sin(r^2)\right) \]
Horseshoe
\[ V_4(x, y) = \left(\frac{(x - y)(x + y)}{r}, \frac{2 x y}{r}\right) \]
Bubble
\[ V_5(x, y) = \left(\frac{4x}{r^2 + 4}, \frac{4y}{r^2 + 4}\right) \]

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éthode clone), pour garantir l'immuabilité de la transformation. Lève l'exception IllegalArgumentException 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 cadre frame et stocke le résultat dans un nouvel accumulateur de largeur width et de hauteur height, 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ètres width, height et density.

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-dimensionnel hitCount 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'exception IndexOutOfBoundsException 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 cadre frame, de largeur width et de hauteur height (en nombre de cases). Lève l'exception IllegalArgumentException 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 point p donné. Ne fait rien si le point est en dehors du cadre de l'accumulateur (c-à-d le paramètre frame 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 :

  1. La première ligne contient la chaîne P2 qui identifie ce type de fichiers.
  2. La seconde ligne contient la largeur et la hauteur de l'image, séparés par une espace.
  3. 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.
  4. 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.

images/flame_2.png

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.

images/turbulence.png

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.

images/fern.png

La fougère de Barnsley (version Flame)

Résumé

Pour cette étape, vous devez :

  1. Ecrire les classes Flame, FlameTransformation, FlameAccumulator, FlameAccumulator.Builder et Variation du paquetage ch.epfl.flamemaker.flame en fonction des spécifications ci-dessus.
  2. Ecrire une classe principale (nommée p.ex. FlamePGMMaker) dans le même paquetage, équipée d'une méthode main qui calcule les fractales Flame de test décrites ci-dessus et produise les images correspondantes dans des fichiers au format PGM.
  3. 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é.
Michel Schinz – 2013-04-08 18:00