Générateur d'images fractales (9)

14 04 2009 In: Pas à pas

Quand on zoome on avant, notre ensemble fractal n'est plus très détaillé. Nous allons ajouter le réglage du nombre maximal d'itérations.

Modification de la couche Modèle

Jusqu'à présent, le nombre maximal d'itérations était codé en dur:

#define MAX_ITERATIONS  18

Nous remplaçons cette définition par la variable d'instance maxIterations

@interface CFRMandelbrotRender : NSObject {

            …
    unsigned char maxIterations; 
}

Je l'ai typée en unsigned char, pour qu'elle soit comprise entre 0 et 255. En effet, notre bitmap en 256 niveaux de gris ne saurait de toute façon pas stocker l'image avec plus de précision. Inutile donc de calculer plus de 255 itérations. Cependant, ce paramètre étant réglable par binding, il va être accédé par Key-Value Coding, qui ne gère que les entiers signés. J'ai donc rusé en utilisant des int pour les accesseurs:

- (void) setMaxIterations:(int)iterations
{
    if(iterations > 255)
        NSLog(@"-[CFRMandelbrotRender setMaxIterations:].
Le nombre d'itération doit être <= 255.");
    maxIterations = iterations;
}

- (int) maxIterations
{
    return maxIterations;   
}

On n'oublie pas de l'initialiser dans la méthode -init:

maxIterations = 18;

J'ai conservé cette valeur de 18 par défaut.

Ajout des contrôles

Ouvrez MyDocument.nib. Ajoutez à la fenêtre un NSLabel, un NSSlider et un NSTextField.

Edition du NIB

Réglez-les (avec le troisième onglet de l'Inspecteur) pour qu'ils restent scotchés au coin supérieur droit.

Configuration du NSSlider

  • Réglez son minimum à 3
    moins de trois itérations ne procure pas un résultat intéressant.
  • Réglez son maximum à 255
  • J'ai réglé Current à 10
    Peu importe, une fois bindé, il prendra la valeur par défaut du modèle, soit 18.

Configuration du NSTextField

  • J'ai tapé la valeur 255 dedans… pour m'assurer qu'elle y rentre bien.
  • Glissez un NSNumberFormatter sur le champ éditable.
    Réglez ses contraintes: minimum à 3 et maximum à 255. Décochez Allows Float, nous ne voulons que des valeurs entières.

Binding

Contrôleur

Tout d'abord, pour binder, il nous faut un objet Contrôleur qui soit compatible avec les bindings. Comme nous gérons une seule instance du Modèle, nous utiliserons un NSObjectController:

  • Glissez un NSObjectController dans MyDocument.nib
  • Renommez-le en MandelbrotRenderController.
  • Dans le premier onglet de l'inspecteur, réglez Class Name à CFRMandelbrotRender.
  • En maintenant la touche Contrôle appuyée, tirez son l'outlet content vers l'instance de Mandelbrot Render (le cube bleu).

Binding du NSSlider

Sélectionnez le slider et passez sur le 4ème onglet de l'Inspecteur ("Bindings"). Pour binder la clé Value:

  • Bind to: MandelbrotRenderController
  • Controller Key = selection
  • Model Key Path = maxIterations

Binding du NSTextField

Bindez le text field exactement de la même façon.

Résultat

Vous pouvez maintenant lancer le programme. Glissez le curseur Itérations maximales: l'ensemble reste le même. Allez sur la vue, et déplacez le repère ou zoomez: enfin, la nouvelle valeur est prise en compte.

Ce qui se passe est que le binding modifie effectivement maxIterations dans le CFRMandelbrotRender, mais cela ne provoque ni le recalcul de l'ensemble, ni l'affichage du nouvel ensemble.

Observation

Il faut un moyen pour que la vue sache que les paramètres ont été modifiés, que l'ensemble doit être recalculé, puis la vue rafraîchie. Une technique pourrait être de relier les actions du NSSlider et du NSTextField à la vue. Cependant, je pense ajouter par la suite des NSTextField pour permettre l'édition des autres paramètres, et cela va commencer à faire beaucoup d'actions. C'est pourquoi nous utiliserons ici la technique plus sophistiquée du Key-Value Observing.

Signaler le besoin d'une mise à jour

L'idée est que le CFMandelbrotRender sait quand il doit être recalculé: dès qu'un de ses paramètres de calcul est modifié. Nous allons lui ajouter une variable d'instance besoinMAJ, indiquant qu'une mise à jour est nécessaire:

@interface CFRMandelbrotRender : NSObject {

            …

    BOOL    besoinMAJ;  // Indique qu'une mise à jour est nécessaire

}

Ensuite, dès qu'un paramètre de calcul est modifié, nous mettrons besoinMAJ à YES:

- (void) setLargeurBitmap:(NSUInteger)largeurPixels
{
    largeurBitmap = largeurPixels;

    [self willChangeValueForKey:@"besoinMAJ"];
    besoinMAJ = YES;
    [self didChangeValueForKey:@"besoinMAJ"];

}

Notez l'encadrement par willChangeValueForKey: et didChangeValueForKey:. Ceux-ci sont indispensables au Key-Value Observing pour savoir que la variable besoinMAJ a changé.

Il faut faire de même dans les méthodes setHauteurBitmap:, zoomerDuFacteur:, decalerCentreX:y: puisqu'on y modifie les paramètres de calcul. Pour cette même raison, modifiez le setter de maxIterations:

- (void) setMaxIterations:(int)iterations
{
    if(iterations > 255)
        NSLog(@"-[CFRMandelbrotRender setMaxIterations:]. Le nombre d'itération doit être <= 255.");
    maxIterations = iterations;

    [self willChangeValueForKey:@"besoinMAJ"];
    besoinMAJ = YES;
    [self didChangeValueForKey:@"besoinMAJ"];
}

À la fin du rendu, repositionnez la variable:

- (NSBitmapImageRep*) bitmapImageRep
{
            …

    [self willChangeValueForKey:@"besoinMAJ"];
    besoinMAJ = NO;
    [self didChangeValueForKey:@"besoinMAJ"];

    return bitmapRep;
}

Observer les besoins de mise à jour

Passons maintenant à la vue.

Contexte

Créons d'abord un contexte. De quoi s'agit-il ? D'objets uniques qui permettent d'identifier quel keypath a changé par une rapide comparaison de pointeurs, plutôt qu'une lente comparaison de chaînes de caractères:

static void* ContexteMAJRendu = (void*) @"ContexteMAJRendu";

Le contenu de la chaîne n'a aucune importance, puisque c'est le pointeur de l'objet que nous allons utiliser. On utilise habituellement une chaîne parce que c'est plus simple pour le débogage, mais n'importe quel autre objet peut faire l'affaire, pourvu que son pointeur soit unique.

Changements

Pour être tenu au courant des changements des clés observées, implémentons la méthode:

- (void)observeValueForKeyPath:(NSString *)keyPath
    ofObject:(id)object
    change:(NSDictionary *)change
    context:(void *)context
{
    if(context == ContexteMAJRendu)
    {
        [self setNeedsDisplay:YES]; 
    }

}

Nous identifions le contexte et demandons l'affichage de la vue le cas échéant. Pour l'instant, il n'y a qu'une variable à observer, donc qu'un seul contexte, mais ça peut évoluer.

Nous n'avons plus besoin d'appeler setNeedsDisplay: ailleurs. Retirez-le des deux autres endroits.

Commencer l'observation

Ajoutez la méthode:

- (void) awakeFromNib
{
    [render addObserver:self forKeyPath:@"besoinMAJ" options:0 context:ContexteMAJRendu];   
}

Elle est appelée dès que tous les objets du NIB sont prêts. En particulier, ici, c'est l'objet render qui doit l'être. Nous ajoutons un observateur (=la vue), du keyPath besoinMAJ. Nous laissons les options par défaut, et fournissons le contexte à passer lors des changements.

Arrêter l'observation

Arrêter l'observation est toujours délicat, car il faut qu'elle ait cessé avant que l'objet observé reçoive un message -[dealloc]. Nous allons le faire quand la fenêtre se ferme.

- (void)viewWillMoveToWindow:(NSWindow *)newWindow
{
    if(newWindow == nil)
        [render removeObserver:self forKeyPath:@"besoinMAJ"];
}

Cette méthode est habituellement appelée lorsque la vue est insérée dans la fenêtre. Cependant, quand newWindow est nulle, cela signifie que la fenêtre va être close.

Et là ça marche ?

Vous pouvez essayer de lancer à nouveau l'appli. Cette fois-ci, ça fonctionne. À la prochaine !

Le projet Xcode complet à télécharger.

Renaud Pradenc
Céroce

Générateur d'images fractales (8)

11 03 2009 In: Pas à pas

À force de jouer avec le générateur, quelque chose me chagrine: un nouvel utilisateur ne saurait même pas qu'il peut agir sur la vue à la souris. Nous allons donc modifier son pointeur pour apporter cette information.

Comportement voulu

Voici le fonctionnement que j'attends:

  • Fèches haut/basQuand on appuie sur la touche Contrôle, le curseur de la souris doit se transformer en flèches. Ceci, dès que le pointeur se trouve dans la vue.
  • Main ouverte Sinon, si le bouton n'est pas appuyé, le curseur est une main ouverte.
  • Main ferméeS'il est appuyé, une main fermé.

Changer le pointeur

Je vais déjà vous expliquer comment fonctionne ce système de curseurs sous Cocoa, la doc d'Apple me semblant assez indigeste pour quelque chose d'aussi simple.

La classe NSCursor dispose d'un ensemble de méthodes de classes qui renvoient un nouvel NSCursor, ayant des apparences diverses (croix, main, flèches, etc.). Fixer le pointeur est aussi simple que ceci:

[[crosshairCursor] set];

Qui donnera une apparence de croix au pointeur.

Cependant, NSCursor possède un mécanisme plus élaboré, basé sur une pile:

  • Quand une instance de NSCursor reçoit un appel à -[NSCursor push], cette instance devient le curseur courant, et l'ancien curseur est empilé.
  • Quand la classe NSCursor reçoit un appel à +[NSCursor pop], le curseur sur le haut de la pile est retiré et devient le nouveau curseur.

C'est ce mécanisme que nous allons utiliser, puisqu'il nous simplifie la vie, en mémorisant dans quel état il faut remettre le curseur.

Événements clavier

Il nous faut surveiller l'appui sur la touche Contrôle:

- (void)flagsChanged:(NSEvent *)theEvent
{
    if(pointeurDansLaVue)
    {

-[NSResponder flagsChanged:] est appelée dès qu'une touche spéciale est appuyée, que le pointeur soit dans la vue ou non.
J'ai donc créé une variable d'instance pointeurDansLaVue. Nous fixerons sa valeur dans les méthodes indiquant l'entrée ou la sortie du pointeur de la vue.

        if([theEvent modifierFlags] & NSControlKeyMask)

On regarde si la touche Contrôle est appuyée.

            [[NSCursor resizeUpDownCursor] push];

On change le curseur (en mémorisant l'ancien).

        else
            [NSCursor pop];

Sinon, Contrôle n'est plus appuyée: il faut rétablir le curseur précédent.

    }
}

Il faut également rajouter ce code:

- (BOOL) acceptsFirstResponder
{
    return YES;
}

Autrement, nous ne recevrions pas les événements clavier.

Entrée et sortie de la vue

Tracking Area

Cocoa propose de surveiller la position du pointeur par le biais de la classe NSTrackingArea, qui représente un rectangle de la vue. Ajoutons les variables d'instance:

@interface CFRFractalView : NSView {
    IBOutlet CFRMandelbrotRender* render;

    NSTrackingArea* trackingArea;   
    BOOL pointeurDansLaVue; 
}

Et initialisons-les:

- (id)initWithFrame:(NSRect)frame {
    self = [super initWithFrame:frame];
    if (self)
    {
        trackingArea = nil;
        pointeurDansLaVue = NO;
    }
    return self;
}

Apple conseille de créer les tracking areas lorsque la vue est insérée dans la fenêtre:

- (void)viewDidMoveToWindow
{
    trackingArea = [[NSTrackingArea alloc] initWithRect:[self bounds] 
        options:(NSTrackingMouseEnteredAndExited 
        | NSTrackingInVisibleRect | NSTrackingActiveInKeyWindow) 
        owner:self 
        userInfo:nil];

Nous fournissons à la méthode d'initialisation:

  • le rectangle définissant la tracking area
    Nous lui passons le rectangle définissant la vue. Il s'agit du rectangle de départ, la tracking area changeant de dimensions lors des redimensionnements de la vue.
  • Des options, combinées par l'opérateur OU:
    • NSTrackingMouseEnteredAndExited indique que nous voulons que les méthodes -mouseEntered: et -mouseExited: soient appelées lors de l'entrée, respectivement de la sortie du pointeur.
    • NSTrackingInVisibleRect nous permet de ne pas nous préoccuper de redimensionner la tracking area.
    • NSTrackingActiveInKeyWindow dit de ne surveiller le pointeur que quand la fenêtre est active.
  • owner est le propriétaire de la tracking area. Il est possible de déléguer cette gestion, mais ici c'est notre vue qui s'en occupe.
  • userInfo permet de passer des informations à l'intérieur du NSEvent reçues par les méthodes d'événement. Inutile pour nous.
    [self addTrackingArea:trackingArea];
    

    }

Nous associons ensuite la tracking area à la vue.

Événements mouseEntered et mouseExited

- (void)mouseEntered:(NSEvent *)theEvent
{
    [[NSCursor openHandCursor] push];
    pointeurDansLaVue = YES;
}

Quand le pointeur entre dans la vue, nous changeons le curseur en une main ouverte, et mettons à jour pointeurDansLaVue, nécessaire à la méthode -flagsChanged: décrite plus haut.

- (void)mouseExited:(NSEvent *)theEvent
{
    pointeurDansLaVue = NO;
    [NSCursor pop];
}

Quand le pointeur sort de la vue, nous rétablissons le curseur précédent, a priori la flèche normale.

Événements mouseDown et mouseUp

- (void)mouseUp:(NSEvent *)theEvent
{
    [NSCursor pop]; 
}

Lorsque le bouton de la souris est relâché, nous rétablissons le curseur précédent.

Pour les clics:

- (void)mouseDown:(NSEvent *)theEvent
{

Lors d'un clic…

    if([theEvent modifierFlags] & NSControlKeyMask)
    {

… si la touche Contrôle est appuyée…

        [[NSCursor resizeUpDownCursor] push];

Utiliser un curseur en formes de doubles-flèches. À vrai dire, ce curseur est déjà le curseur actuel (puisque la touche Contrôle a été enfoncée avant le clic), mais cet appel permet de contrebalancer le [NSCursor pop] de la méthode -mouseDown:…

    }
    else
    {
        [[NSCursor closedHandCursor] push];

… appel lui même nécessaire pour contrebalancer cet appel à adopter un curseur en main fermée.

    }
}

Nous en avons fini avec ces histoires de curseurs. Je vous accorde que ça semble un peu bricolé, mais on ne peut guère faire autrement.

Résultat

Il n'y a plus qu'à essayer: ça fait tout de suite beaucoup plus pro !

Version de Mac OS X

La classe NSTrackingArea fut introduite avec Mac OS 10.5. Autrefois, on utilisait le mécanisme des tracking rectangles, qui est similaire mais plus compliqué à mettre en œuvre. Toujours est-il que nous perdons la compatibilité avec les anciens systèmes, alors prévenons leurs utilisateurs avec un joli message d'erreur. Pour cela:

  • Clic droit sur Info.plist > Open As > Plain Text File
  • avant la balise </dict> finale, insérez:
    <key>LSMinimumSystemVersion</key>
    <string>10.5.0</string>

À bientôt pour la suite.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (7)

05 03 2009 In: Pas à pas

Aujourd'hui nous allons permettre — enfin ! — de se déplacer dans l'ensemble de Mandelbrot.

Retirer la mesure de performance

Commencez par ouvrir MyDocument.xib et retirez l'instance de CFRMesurePerf qui ne nous est plus nécessaire.

Navigation

L'utilisateur naviguera de la façon suivante:

  • se déplacer sur le repère se fait en glissant la souris avec le bouton principal (gauche) appuyé.
  • le zoom se fait grâce à la molette de la souris, ou pour les souris qui n'en seraient pas pourvues, en maintenant la touche Contrôle appuyée, et en glissant la souris avec le bouton appuyé.

Le déplacement

Rappelez-vous que la classe CFRMandelbrotRender contient une variable d'instance centre:

Complexe_t centre;  // Centre du repère

De fait, se déplacer dans l'ensemble consiste à déplacer le centre du repère, à recalculer la bitmap et à l'afficher.

Glissé de la souris

Je vous rappelle que NSView hérite de NSResponder. Or, la méthode -[NSReponder mouseDragged:] est appelée lorsque la souris est glissée sur la vue, avec le bouton principal appuyé :

- (void)mouseDragged:(NSEvent *)theEvent
{

    // Déplacer le centre de la vue
    [render decalerCentreX:-[theEvent deltaX] 
                        y:[theEvent deltaY]];

Je vais revenir tout de suite sur la méthode decalerCentreX:y:. Les méthodes -[NSEvent deltaX] et -[NSEvent deltaY] permettent d'obtenir le nombre de points dont s'est déplacé le pointeur de la souris pendant le glissé.

    [self setNeedsDisplay:YES];
}

Cette méthode demande à la vue se réafficher dans la prochaine boucle d'affichage : la méthode -drawRect: sera appelée à nouveau.

Décaler le centre

Venons-en à la méthode -[CRFMandelbrotRender decalerCentreX:y:]. Nous avons ici une conversion d'échelle à faire. En effet, les décalages lui sont exprimés en pixels, et il nous faut les exprimer en coordonnées "repère":

- (void) decalerCentreX:(NSInteger)pixelsHoriz
                    y:(NSInteger)pixelsVerti
{
    double facteurReperePixel = largeur / largeurBitmap;

D'abord, nous calculons le rapport d'échelle entre la largeur du repère, et celle de la bitmap (en pixels, comme la vue).

    double deltaX = pixelsHoriz * facteurReperePixel;
    double deltaY = pixelsVerti * facteurReperePixel;

Nous appliquons alors ce facteur aux décalages en pixels pour obtenir les décalages en coordonnées "repère".

    centre.reel += deltaX;
    centre.imag += deltaY;
}

Enfin, nous translatons le centre du repère.

Et voilà, lancez le programme, ça fonctionne.

Le zoom à la molette

Zoomer

Zoomer consiste à modifier la variable largeur de CFRMandelbrotRender, qui représente la largeur de l'intervalle de calcul:

double largeur;

Ainsi, si vous divisez la largeur par 2, vous zoomez de 200%; si vous multipliez la largeur par 2, vous dézoomez de 50%:

- (void) zoomerDuFacteur:(double)facteur
{
    largeur = largeur * facteur;

    // Corriger les valeurs extrêmes
    if(largeur < 0.0001)
        largeur = 0.0001;
    else if(largeur > 8.0)
        largeur = 8.0;
}

J'ai ajouté la correction des valeurs extrêmes après quelques essais . Les limites sont empiriques; d'ailleurs, nous changerons sans doute la limite basse un jour.

Gestion de la molette

Quand la molette est actionnée, la méthode -[NSResponder scrollWheel:] est appelée:

- (void)scrollWheel:(NSEvent *)theEvent
{
    // deltaY est > 0 quand la molette est tournée en avant.
    //  Il vaut +/- 0.1 pour un petit mouvement et +/- 10 pour un grand.
    double deltaY = [theEvent deltaY];

Il m'a fallu faire quelques essais pour régler l'amplitude du zoom. J'ai mesuré que tourner lentement la molette vers l'avant donnait un deltaY aux alentours de 0,1, et la tourner vite, autour de 10.
deltaY est négatif quand on la molette est tournée vers l'arrière.

    [render zoomerDuFacteur: 1.0 + deltaY/20.0];

La division par 20 de deltaY est là encore empirique. Par exemple, en tournant rapidement la molette vers l'arrière, vous obtenez un facteur de zoom de l'ordre de 1+ (-10)/20) = 0.5, soit un zoom x2.

    [self setNeedsDisplay:YES];
}

Lancez le programme: ça zoome !

Le zoom par Contrôle + glissé

Modifions la méthode -mouseDragged:

- (void)mouseDragged:(NSEvent *)theEvent
{
    // La touche Contrôle est-elle appuyée ?
    if([theEvent modifierFlags] & NSControlKeyMask)
    {

Il nous faut d'abord savoir si la touche Contrôle est appuyée pour distinguer les deux type de glissés.

        // Zoomer/dézoomer
        double deltaRelatif = 2.0 * ([theEvent deltaY] / [self bounds].size.height);

Par soucis d'ergonomie, ce qui nous intéresse, n'est pas le déplacement absolu de la souris, mais son déplacement relatif. D'où le calcul de deltaY/(hauteur de la vue). J'ai ensuite ajouté un facteur 2, déterminé — vous l'aurez deviné — de façon empirique.

        [render zoomerDuFacteur: 1.0 + deltaRelatif];
    }
    else
    {
        // Déplacer le centre de la vue
        [render decalerCentreX:-[theEvent deltaX] y:[theEvent deltaY]];     
    }
    [self setNeedsDisplay:YES];
}

Le reste a déjà été expliqué.

Le résultat

Lancez le programme, et admirez le résultat. Personnellement, je trouve l'affichage encore un peu lent.

En zoomant loin en avant, on reconnaît enfin la structure "fractale" de l'ensemble (le même motif se répétant à des échelles différentes).

Répétitions de la structure fractale

Zoom sur un détail Cependant, les détails ne sont alors plus très présents. C'est parce que nous avons fixé le nombre d'itérations maximales trop bas. Heureusement, nous permettrons prochainement de modifier ce seuil.

À bientôt.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (6)

03 03 2009 In: Pas à pas

Nous continuons aujourd'hui l'optimisation de la génération de l'image.

Les bitmaps

J'ai vaguement expliqué ce qu'était une bitmap, me contentant de dire qu'il s'agissait d'une grille de pixels. Intéressons-nous à leur organisation en mémoire.

32 bits par pixel

Utiliser 32 bits pour stocker les composantes d'un pixel est des plus classiques:

Mode 32 bits/pixel

Chaque composante utilise un octet, et peut donc contenir une valeur de 0 à 255. Doser les quantités de rouge, de vert et de bleu permet de choisir la teinte du pixel; la composante alpha correspond à l'opacité du pixel.

256 niveaux de gris

Notre générateur utilise une bitmap en 256 niveaux de gris:

Mode 8 bits/pixel

C'est le même principe: la valeur de l'octet fournit la nuance; 0 correspond au noir et 255 au blanc, voilà pourquoi nous utilisons la ligne:

NSUInteger nuance = n * 255 / MAX_ITERATIONS;

pour déterminer la nuance du pixel calculé.

Organisation en mémoire

Voyons maintenant la relation entre les pixels et les coordonnées:

Bitmap en 256 niveaux de gris

Dans cet exemple, la bitmap mesure 400 pixels de large et 300 de haut. Ce qui est intéressant, c'est que les pixels se suivent en mémoire. Ainsi, si nous disposons de l'adresse à laquelle est stockée la bitmap, adresseBitmap:

  • Le pixel de coordonnées (0,0) se trouve à l'adresse adresseBitmap.
  • Le dernier pixel de la première ligne (399, 0) se trouve à l'adresse adresseBitmap + 399 (puisqu'un pixel prend exactement un octet).
  • Le premier pixel de la deuxième ligne (0, 1), se trouve à l'adresse adresseBitmap + 400.
  • etc.

En généralisant nous obtenons:

adressePixel = adresseBitmap + (400 * y) + x

ou en généralisant d'avantage:

adressePixel = adresseBitmap + (largeurBitmap * y) + x

Il nous suffit d'écrire la nuance à cette adresse pour modifier le point. Vous devez maintenant avoir une bonne idée du fonctionnement de la méthode -[NSBitmapImageRep setPixel:atX:y];

Row Bytes

À vrai dire, j'ai simplifié la figure précédente, en omettant un détail. Voici une figure plus juste:

Bitmap en 256 niveaux de gris + rowBytes

En effet, pour des raisons de performances, des octets inutilisés (row bytes) sont ajoutés à la fin de chaque ligne. Ils servent à aligner la bitmap en mémoire. On ne connaît pas leur nombre a priori: cela dépend de plusieurs paramètres.

Toujours est-il qu'il faut en tenir compte.

L'optimisation

Dans notre boucle de rendu, il ne nous reste plus grand chose que nous puissions améliorer si ce n'est cette ligne:

[bitmapRep setPixel:&nuance atX:x y:y];

Cette méthode est tout de même appelée un million de fois (pour notre rendu en 1000 x 1000 pixels). Les bénéfices attendus en écrivant directement dans la bitmap sont les suivants:

  • Ne plus appeler la méthode [setPixel:atX:y:]. Les appels de méthodes sont encore plus lents que les appels de fonctions. Nous ferons entre-autres l'économie de l'exécution de la fonction objc_msgSend_rtp().
  • La méthode [setPixel:atX:y:] est forcément plus compliquée qu'un écriture directe dans la bitmap, ne serait-ce que par son côté généraliste. De plus, si vous vous rappelez l'article précédent, Shark listait des appels aux méthodes
    -[NSBitmapImageRep _setCGImageRef:]
    -[NSBitmapImageRep getBitmapDataPlanes:]
    -[NSBitmapImageRep _acquireRetainesCGImageRef]
    Je pense que ceci va nous permettre de nous en passer.

Le code

Inverser les énumérations des x et y

À cause de la manière dont est stockée la bitmap, il est nécessaire les énumérations de x et y :

for(y = 0; y < hauteurBitmap; y++)
{       
    for(x = 0; x < largeurBitmap; x++)
    {

                …

        c.reel += incX;
    }

    c.reel = premierPoint.reel;
    c.imag += incY;
}

Adresser la bitmap

Avant le calcul:

// Obtenir la bitmap
unsigned char* bitmapPtr = [bitmapRep bitmapData];

On demande l'adresse de la bitmap.

unsigned int rowBytes = [bitmapRep bytesPerRow] - largeurBitmap;

La méthode [bitmapRep bytesPerRow] renvoie le nombre d'octets utilisés pour stocker une ligne. Comme nous savons que largeurBitmap octets sont utiles, nous en déduisons le nombre d'octets d'alignement (rowBytes).

for(y = 0; y < hauteurBitmap; y++)
{       
    for(x = 0; x < largeurBitmap; x++)
    {

                    …

        // Donner le niveau de gris au pixel
        *bitmapPtr = n * 255 / MAX_ITERATIONS;

Nous conservons la formule du calcul de la nuance, que nous écrivons dans la bitmap à l'adresse du pixel courant.

        bitmapPtr++;

Puis nous passons au pixel suivant.

        c.reel += incX;
    }

    c.reel = premierPoint.reel;
    c.imag += incY;
    bitmapPtr += rowBytes;  // Sauter les octets inutilisés en fin de ligne

À la fin de chaque ligne, nous sautons les octets inutilisés.

}

Résultat

50 images rendues en 12.864695 secondes.
Moyenne = 3.886606 images/s

Nous tournons aux alentours de 4 images/s. Je vous rappelle que la première mesure donnait 0,79 images/s… la vitesse a été multipliée par 5 !

Nous arrivons aux limites de ce que nous pouvons ainsi optimiser. Nous allons nous arrêter là.

Et si ce n'était que le début ?

Améliorer la vitesse demanderait maintenant de recourir à des astuces.

Voici une idée: vous pouvez remarquer que deux pixels qui se suivent sont très souvent de la même nuance. On pourrait ne calculer qu'un pixel sur deux:

  • Si le pixel n°3 n'est pas de la même nuance que le pixel n°1, alors on calcule le pixel 2
  • Sinon, on lui donne la nuance du pixel 3.

On ne manquerait que des variations brusques (<1 pixel), peu perceptibles.

Cependant, tout cela est sans intérêt, parce que la vraie façon d'améliorer la vitesse est de déléguer le calcul… à la carte graphique! Je crois que n'importe quelle carte est aujourd'hui capable de faire ce calcul en temps réel. Ce sera peut-être pour une prochaine fois (quand j'aurais appris à me servir d'OpenGL Shading Language). En attendant, l'application est utilisable. Nous allons pouvoir nous balader dans l'ensemble de Mandelbrot.

À bientôt pour la suite.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (5)

23 02 2009 In: Pas à pas

Nous étions restés la fois précédente sur une version un peu lente de notre générateur. Nous allons tenter d'améliorer cela.

Une mise au point s'impose

Je lis fréquemment des gens qui tiennent à peu près ce discours: "Les programmeurs ne tirent pas partie de la puissance des machines, s'ils programmaient en assembleur, les programmes iraient super vite. Ils programment comme des porcs, uniquement pour des raisons financières".

Premièrement, les raisons financières restent de bonnes raisons. Deuxièmement, il faut toujours faire des compromis: programmer efficacement en assembleur est très long, exige des connaissances pointues et le code n'est absolument pas portable, ce qui pose problème quand un logiciel doit être maintenu pendant des années.

Mais surtout, troisièmement, le postulat que les programmes tout-assembleur seraient bien plus rapides est faux ! Dans une application habituelle, 90% du temps est passé dans 10% du code. Cela signifie qu'améliorer ces 10% du code va suffire à accélérer grandement le programme. La bonne stratégie est d'écrire de la façon la plus lisible possible et de n'optimiser que les parties les plus critiques.

L'optimisation… dans l'ordre

  • Choisissez les bons algorithmes
    C'est le moyen le plus sûr d'accélérer un programme. À quoi bon programmer au plus près de la machine s'il existe un algorithme plus efficace par son principe ?
  • Exploitez au mieux le matériel
    Utilisez tous les cœurs de votre micro-processeurs, déléguez les traitements à la carte graphique, profitez des instructions vectorielles
  • Sachez comment fonctionne votre Unix
    C'est le système d'exploitation qui gère les ressources de votre applications, en particulier la mémoire et les fichiers. Ses contraintes peuvent avoir un impact important sur les performances.
  • En dernier recours seulement, travaillez sur le bas niveau
    Dans certaines applications (jeux, calculs 3D), tailler le code au plus près du microprocesseur reste nécessaire.

Dans tous les cas: ME-SU-REZ !
Optimisez seulement après avoir localisé les sources de lenteurs: elles ne sont pas toujours évidentes. En outre, seules les mesures valident l'efficacité des optimisations.

Mesurons notre appli

Commençons donc par mesurer les temps d'exécution:

Mesure avec Shark

  • Sous Xcode, Choisissez l'article du menu Run > Start with Performance Tool > Shark.
  • Cliquez sur le bouton Start.
  • Une fenêtre apparaît (le chemin de notre exécutable est déjà réglé). Cliquez sur OK.
  • L'appli se lance. Redimensionnez la fenêtre continuellement pendant 30 secondes, jusqu'à ce que Shark prenne la main.

Shark avant optimisation

Le résultat n'est pas très surprenant, on trouve en tête nos fonctions qui génèrent l'image. Nous savons où attaquer: ces cinq premières méthodes totalisent plus de 80% du temps d'exécution.

Ensuite, on trouve objc_msgSend_rtp. Il s'agit de la fonction du runtime Objective-C qui permet d'envoyer des messages entre les objets. On peut éventuellement le réduire en envoyant moins de messages…
À vrai dire, ce qui m'étonne sont les 2,7% de setPixel:atX:y:, je pensais que ce serait plus. Il me paraît aussi assez surprenant que _setCGImageRef: apparaisse si haut dans le classement. Voilà pourquoi vous devez mesurer: où les optimisations doivent être faîtes n'est pas toujours évident.

Principe de mesure de Shark
Shark utilise une interruption. Chaque fois qu'elle est déclenchée (toutes les millisecondes, par défaut), Shark note quelle fonction ou méthode est en train d'être exécutée. À la fin, il n'a plus qu'à compter pour établir un classement. Notez qu'il s'agit d'une approche statistique: évaluer le même programme plusieurs fois ne donnera pas les mêmes résultats (les interruptions ne sont pas synchronisées avec le lancement du programme). Il faut admettre une marge d'environ 2%.

Une mesure absolue

L'inconvénient de la mesure avec Shark, c'est qu'elle nous fournit des proportions du temps passé. Ce qui serait intéressant serait d'avoir une mesure du temps de rendu pour mesurer l'amélioration. J'ai donc créé une nouvelle classe, CFMesurePerf pour cela:

#import "CFRMesurePerf.h"

#define IMAGES_A_RENDRE     50

Nous calculons la même image 50 fois de suite. Le temps d'exécution varie: notre programme ne tourne pas tout seul, il y a d'autres processus en parallèle, il faut du temps pour que le système décide de sortir du mode économie d'énergie, etc. . Calculer plusieurs fois permet de lisser les différences.

@implementation CFRMesurePerf

- (id) init
{
    if(self = [super init])
    {
        CFRMandelbrotRender* render = [[CFRMandelbrotRender alloc] init];
        [render setLargeurBitmap:1000];
        [render setHauteurBitmap:1000];

Nous créons un CFRMandelbrotRender. Il ne sera pas affiché à l'écran; ce qui nous intéresse est son temps de calcul. Nous demandons le calcul d'un million de points.

        NSDate* dateDepart = [NSDate date];

        // Rendre l'image IMAGES_A_RENDRE fois
        int image;
        for(image = 0; image < IMAGES_A_RENDRE; image++)
        {
            [render bitmapImageRep];
        }

        NSDate* dateFin = [NSDate date];

Nous notons la date de début, rendons les 50 images, puis notons la date de fin.

        float secondesEcoulees = [dateFin timeIntervalSinceDate:dateDepart];
        int imagesARendre = IMAGES_A_RENDRE;
        NSLog(@"%d images rendues en %f secondes.", imagesARendre, secondesEcoulees);
        NSLog(@"Moyenne = %f images/s", IMAGES_A_RENDRE/secondesEcoulees);

La différence entre les deux dates nous fournit la durée du calcul. Nous pouvons en déduire la moyenne.

    }

    return self;
}

@end

J'ai choisi d'instancier cette classe à partir de MyDocument.xib. Je vous laisse faire.

Dorénavant, lorsque le programme se lance, il va calculer 50 images. C'est assez long, soyez patients! Il faut plus d'une minute sur mon G5, avec une moyenne de 0,79 images/seconde.

Appels à complexeAvecCoordBitmapX:y:

Passons maintenant à une optimisation de l'algorithme. La méthode -[complexeAvecCoordBitmapX:y] est actuellement appelée pour chaque point. Ce n'est absolument pas nécessaire. Il nous suffit de calculer de combien il faut incrémenter les coordonnées pour passer d'un point à un autre du plan.

Ainsi:
incrementX = (dernierPoint.reel - premierPoint.reel) / largeurBitmap;
incrementY = (dernierPoint.imag - premierPoint.imag) / hauteurBitmap;

Nous obtenons alors la méthode de rendu suivante:

// Créer la bitmap
NSBitmapImageRep* bitmapRep = [[NSBitmapImageRep alloc]
    initWithBitmapDataPlanes:NULL
    pixelsWide:largeurBitmap
    pixelsHigh:hauteurBitmap
    bitsPerSample:8
    samplesPerPixel:1
    hasAlpha:NO
    isPlanar:NO
    colorSpaceName:NSDeviceWhiteColorSpace
    bytesPerRow:0
    bitsPerPixel:8];

// Déterminer les incréments des coordonnées
Complexe_t premierPoint, dernierPoint;
premierPoint = [self complexeAvecCoordBitmapX:0 y:0];
dernierPoint = [self complexeAvecCoordBitmapX:largeurBitmap-1 y:hauteurBitmap-1];

Calculer les coordonnées des points extrêmes se fait encore avec notre bonne vieille méthode.

double incX = (dernierPoint.reel - premierPoint.reel) / largeurBitmap;
double incY = (dernierPoint.imag - premierPoint.imag) / hauteurBitmap;

Voir la formule plus haut.

// Calculer l'ensemble de Mandelbrot:
// Parcourir tous les points de la bitmap
double x, y;
Complexe_t c = premierPoint;

c est maintenant initialisé avec le premier point.

for(x = 0; x < largeurBitmap; x++)
{
    for(y = 0; y < hauteurBitmap; y++)
    {       
        // Initialiser z[0]
        Complexe_t z = {0.0, 0.0};

        NSUInteger n;
        for(n=0; n < MAX_ITERATIONS; n++)
        {
            // z[n+1] = z[n+1]^2 + c
            z = Additionner(Carre(z), c);

            // La suite diverge si |z| > 2
            if(ModuleAuCarre(z) > 4.0)
                break;
        }

        // Donner le niveau de gris au pixel
        NSUInteger nuance = n * 255 / MAX_ITERATIONS;
        [bitmapRep setPixel:&nuance atX:x y:y];

        c.imag += incY;

Nous incrémentons donc l'ordonnée ici.

    }

    c.imag = premierPoint.imag;
    c.reel += incX;

Il ne faut pas oublier de replacer l'ordonnée en haut du plan. Ensuite, nous incrémentons l'abscisse.

}

[bitmapRep autorelease];
return bitmapRep;

Au niveau des performances, j'atteins maintenant les 1,06 images/s, soit un gain de 34%. Pas mal !

Placer les fonctions mathématiques "en ligne"

En mettant un compteur dans la boucle for, vous sauriez qu'elle est exécutée 4 239 692 fois. Autant dire que tout ce qui s'y trouve est critique. Or, un appel de fonction réserve de la mémoire sur la pile et copie les paramètres. Il ne s'agit pas d'opérations particulièrement lourdes, mais quand on le fait 4 millions de fois, cela devient très significatif. Nous n'allons donc plus faire d'appels aux fonctions, mais les incorporer:

Complexe_t z = {0.0, 0.0};
Complexe_t zCarre;
NSUInteger n;
for(n=0; n < MAX_ITERATIONS; n++)
{
    // z[n+1] = z[n+1]^2 + c
        // Mettre z au carré
    zCarre.reel = z.reel*z.reel - z.imag*z.imag;
    zCarre.imag = 2.0 * z.reel * z.imag;  
        // Ajouter c
    z.reel = zCarre.reel + c.reel;
    z.imag = zCarre.imag + c.imag;

    // La suite diverge si |z| > 2
    if( (z.reel*z.reel + z.imag*z.imag) > 4.0)
        break;
}

Le résultat est sans appel: il ne faut plus que 24 s pour rendre les 50 images, soit une moyenne de 2,06 images/s — quasiment deux fois plus vite. La méthode est par contre moins lisible: c'est habituel dès que l'on optimise. Il s'agit toujours d'un compromis entre la vitesse et la maintenabilité du code.

La suite

Il nous reste une dernière optimisation à faire, mais comme elle nécessite des explications, je m'arrête là pour cette fois. À bientôt.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (4)

16 02 2009 In: Pas à pas

Cet épisode sera consacré au redimensionnement de la vue qui affiche l'image fractale.

Redimensionnement de la vue

Ajoutons naïvement la possibilité de redimensionner la vue, sans trop penser aux conséquences.

CFRMandelbrotRender

Ajoutons deux variables d'instance pour savoir à quelles dimensions faire le rendu:

@interface CFRMandelbrotRender : NSObject {

    // Dimensions de la bitmap
    NSUInteger largeurBitmap;   
    NSUInteger hauteurBitmap;       
}

- (void) setLargeurBitmap:(NSUInteger)largeurPixels;
- (void) setHauteurBitmap:(NSUInteger)hauteurPixels;

- (NSBitmapImageRep*) bitmapImageRep;

@end

N'oublions pas de les initialiser:

- (id) init
{
    if(self = [super init])
    {
        largeurBitmap = 400;
        hauteurBitmap = 300;
    }

    return self;
}

Il faut également ajouter les setters de ces deux variables d'instance:

- (void) setLargeurBitmap:(NSUInteger)largeurPixels
{
    largeurBitmap = largeurPixels;  
}

- (void) setHauteurBitmap:(NSUInteger)hauteurPixels
{
    hauteurBitmap = hauteurPixels;  
}

À vous maintenant de modifier le code de -bitmapImageRep où sont utilisées ces dimensions.

CFRFractalView

C'est la vue qui va dire au CFRMandelbrotRender à quelle taille il doit générer la bitmap:

- (void)drawRect:(NSRect)rect
{

            …

    // Afficher la bitmap
    [render setLargeurBitmap:[self bounds].size.width];
    [render setHauteurBitmap:[self bounds].size.height];
    NSBitmapImageRep* bitmapRep = [render bitmapImageRep];
    [bitmapRep drawAtPoint:NSMakePoint(0,0)];

}

[self bounds] renvoie un NSRect définissant les limites de la vue. Nous fixons les dimensions de la bitmap pour qu'elles collent à celles de la vue.

Redimensionnement de la vue en même temps que la fenêtre.

Filez éditer MyDocument.xib sous Interface Builder:

  • sélectionnez la vue
  • dans l'inspecteur, dans l'onglet qui représente une règle, activez les flèches intérieures à la vue, ainsi que les ergots extérieurs (tout doit être activé).

Enregistrez, puis lancez le programme.

La bitmap s'est agrandie mais l'ensemble reste collé dans le coin supérieur gauche! En fait, notre programme calcule la partie droite de l'ensemble, alors que ce que nous voulons est que l'ensemble remplisse tout la vue.

Redimensionnement et intervalles

Nous voilà de retour à la planche à dessin. Posons déjà le comportement attendu lors d'un redimensionnement:

  1. La vue reste complètement remplie
  2. Le point situé au centre de la vue doit y rester
  3. La figure grandit ou rétrécit, on ne cadre pas plus large ou plus étroit

Pour la génération de la bitmap, il faut utiliser les mêmes proportions que la vue: je fais le choix de privilégier la largeur, qui sera complètement affiché. La hauteur sera, elle, déterminée en fonction de la largeur et des proportions de la vue.

Nouvelles variables d'instance

Deux variables d'instance deviennent nécessaires:

@interface CFRMandelbrotRender : NSObject {

    // Dimensions de la bitmap
    NSUInteger largeurBitmap;   
    NSUInteger hauteurBitmap;

    // Intervalle de calcul
    double largeur;     // Largeur de l'intervalle du repère calculé
    Complexe_t centre;  // Centre du repère

}

Il faut penser à initialiser ces variables:

- (id) init
{
    if(self = [super init])
    {
        largeurBitmap = 400;
        hauteurBitmap = 300;

        largeur = 4.0;
        centre.reel = 0.7;
        centre.imag = 0.0;
    }

    return self;
}

Conversion des coordonnées (2)

Nous allons devoir reprendre la formule de conversion des coordonnées entre la bitmap et le repère mathématique. Voici la représentation du problème:

Conversion des coordonnées

Nous voulons déterminer la position de point.

Calcul de la hauteur du repère

On a les relations:

échelle = largeur / largeurBitmap = hauteur / hauteurBitmap
=> hauteur = (largeur / largeurBitmap) * hauteurBitmap

Position du point

Le plus simple est de réfléchir en localisant "point" en fonction du point inférieur gauche du repère, puis de translater (dans ce qui suit, pointLocal est le point intermédiaire).

Pour l'abscisse:

pointBitmap.x / largeurBitmap = pointLocal.x / largeur
=> pointLocal.x = largeur * (pointBitmap.x / largeurBitmap)

Pour l'ordonnée, c'est à peine plus difficile:

(hauteurBitmap - pointBitmap.y) / hauteurBitmap = pointLocal.y / hauteur
=> pointLocal.y = hauteur * (1 - pointBitmap.y/hauteurBitmap)

Maintenant, il faut translater par rapport au coin inférieur gauche:

coinInférieurGauche.x = centre.x - largeur/2
coinInférieurGauche.y = centre.y - hauteur/2

Au final:

point = pointLocal + coinInférieurGauche

point.x = largeur * (pointBitmap.x/largeurBitmap.x - 1/2) + centre.x point.y = hauteur * (1/2 - pointBitmap.y/hauteurBitmap) + centre.y

La méthode de conversion

Une fois les formules converties en code:

- (Complexe_t) complexeAvecCoordBitmapX:(NSUInteger)bitmapX y:(NSUInteger)bitmapY
{
    Complexe_t point;

    double hauteur = (largeur/(double)largeurBitmap) * (double)hauteurBitmap;

    point.reel = largeur * ((double)bitmapX/(double)largeurBitmap - 0.5) + centre.reel;
    point.imag = hauteur * (0.5 - (double)bitmapY/(double)hauteurBitmap) + centre.imag;

    return point;
}

Nous utilisons dorénavant cette méthode pour fournir les coordonnées de c:

c = [self complexeAvecCoordBitmapX:x y:y];

Résultat

Essayons maintenant de lancer notre application. Ça marche !

Vous pouvez changer l'intervalle de calcul. Mettez, dans la méthode -init, largeur à 2: ça zoome.
Essayez de modifier les coordonnées du centre: on peut se déplacer.

La fenêtre de rendu

La suite

Nous sommes presque prêts à permettre la navigation dans l'ensemble de Mandelbrot. Presque. En effet, je ne sais pas chez vous, mais mon iMac G5 se fait un peu vieux et le redimensionnement de la fenêtre est loin d'être fluide. Nous nous attaquerons donc à l'optimisation dans le prochain épisode.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (3)

10 02 2009 In: Pas à pas

Après la génération de notre premier image dans l'article précédent, nous allons remanier notre programme pour le rendre plus propre.

Remaniement

Le remaniement (en anglais: Refactoring) est une opération qu'il est bon de faire continuellement. Il s'agit :

  • de changer l'architecture de l'application
  • d'améliorer la documentation
  • ou simplement de renommer certaines classes, méthodes ou variables.

Le but est de faciliter les modifications à venir, en gardant le code le plus propre possible tout au long de la vie du logiciel. Notez bien que nous n'ajoutons pas de fonctionnalités.

Isoler les fonctions sur les nombres complexes

Les fonctions mathématiques peuvent être réutilisées à divers endroits de notre programme, et pas seulement pour la calcul de l'image fractale, nous allons donc les séparer:

  • Créez un nouveau source C, appelé CFRComplexe.c (menu File > New File > C and C++ > C File).
  • Déplacez la définition de la structure ainsi que le prototype de Carre() dans CFRComplexe.h.
  • Déplacez la fonction Carre() dans CFRComplexe.c.

Pendant que nous y sommes, nous créons la fonction ModuleAuCarre():

double ModuleAuCarre(Complexe_t z)
{
    return z.reel*z.reel + z.imag*z.imag;
}

N'oubliez pas de rajouter son prototype dans le .h.

Isoler le calcul de l'image fractale

Les calculs appartenant à la couche Modèle, nous allons créer un objet CFRMandelbrotRender qui ne fait que générer la bitmap:

@interface CFRMandelbrotRender : NSObject {

}

- (NSBitmapImageRep*) bitmapImageRep;
@end

Déplaçons dans CFRMandelbrot.m tout le code qui fait le calcul de la bitmap:

- (NSBitmapImageRep*) bitmapImageRep
{
    // Créer la bitmap
    NSBitmapImageRep* bitmapRep = 
        [[NSBitmapImageRep alloc]
        initWithBitmapDataPlanes:NULL
        pixelsWide:400
        pixelsHigh:300
        bitsPerSample:8
        samplesPerPixel:1
        hasAlpha:NO
        isPlanar:NO
        colorSpaceName:NSDeviceWhiteColorSpace
        bytesPerRow:0
        bitsPerPixel:8];

    // Calculer l'ensemble de Mandelbrot:
    // Parcourir tous les points de la bitmap
    double x, y;
    for(x = 0; x < 400; x++)
    {
        for(y = 0; y < 300; y++)
        {
            // Convertir les coordonnées
            Complexe_t c;
            c.reel =  x/100.0 - 2;
            c.imag   = -y/100.0 + 1.5;

            // Initialiser z[0]
            Complexe_t z = {0.0, 0.0};

            NSUInteger n;
            for(n=0; n < MAX_ITERATIONS; n++)
            {
                // z[n+1] = z[n+1]^2 + c
                Complexe_t zCarre = Carre(z);
                z.reel = zCarre.reel + c.reel;
                z.imag = zCarre.imag + c.imag;

                // La suite diverge si |z| > 2
                if(ModuleAuCarre(z) > 4.0)
                    break;
            }

            // Donner le niveau de gris au pixel
            NSUInteger nuance = n * 255 / MAX_ITERATIONS;
            [bitmapRep setPixel:&nuance atX:x y:y];
        }
    }

    [bitmapRep autorelease];
    return bitmapRep;
}

Les modifications sont les suivantes:

  • la nouvelle fonction ModuleAuCarre() est appelée au lieu de faire le calcul en ligne.
  • la méthode [bitmapRep autorelease] est appelée pour que la mémoire occupée par la bitmap soit libérée, mais seulement après que la vue ait pu l'afficher.

Remaniement de la vue

Renommer

La vue pourrait maintenant servir à afficher autre chose que l'ensemble de Mandelbrot, par exemple celui de Julia. Ceci nous pousse à la renommer. Nous allons utiliser l'outil de Refactoring de XCode pour cela:

  • Ouvrez CFRMandelbrotView.m
  • Sur la ligne @implementation CFRMandelbrotView, sélectionnez le texte CFRMandelbrotView
  • Choisissez l'article de menu Edit > Refactor…
  • Le menu pop-up étant sur Rename, tapez le nouveau nom: CFRFractalView
  • Cliquez sur Preview, puis Apply.

Voilà un outil bien pratique, d'autant plus qu'il renomme la classe y-compris dans le fichier XIB !

Fixer la classe de rendu

Mettre à part le code qui fait le rendu nous impose maintenant de créer un lien pour récupérer la bitmap. Ajoutons une outlet à CFRFractalView:

#import "CFRMandelbrotRender.h"

@interface CFRFractalView : NSView {
    IBOutlet CFRMandelbrotRender* render;
}

@end

Basculez sous Interface Builder. Instanciez un exemplaire de CFRMandelbrotRender, et reliez l'outlet render de la vue à cet objet.

Méthode drawRect:

Retournons sous XCode, dans CFRFractalView.m. Ajoutons à la méthode drawRect: le nécessaire pour obtenir la bitmap et l'afficher:

- (void)drawRect:(NSRect)rect
{
    if(render)  // L'outlet est fixée
    {
        // Afficher la bitmap
        NSBitmapImageRep* bitmapRep = [render bitmapImageRep];
        [bitmapRep drawAtPoint:NSMakePoint(0,0)];       
    }

    else    // L'outlet "render" n'est pas fixée
    {
        [[NSColor blueColor] set];
        NSRectFill(rect);
    }

}

J'ai ici gérer le cas où l'on aurait oublier de relier l'outlet render. La vue serait alors emplie de bleu.

Résultat

Nous pouvons à présent lancer le programme: le résultat est très exactement le même. Mission accomplie !

Nous disposons dorénavant d'une bonne base pour poursuivre le développement. À bientôt pour la suite.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (2)

05 02 2009 In: Pas à pas

Cet article est le deuxième d'une série. Je vous recommande de commencer par le premier article, et même de le laisser ouvert pour pouvoir suivre au mieux celui-ci.

Cette fois-ci, nous entrons dans le vif du sujet, avec une première version du générateur. C'est parti !

Mise en place du projet

  • Créez un projet de type Cocoa Document-Based.
    Notre application devra tôt ou tard enregistrer et charger des documents.

  • Créez un fichier source de type Objective-C NSView subclass, appelé CFRMandelbrotView.
    Cette vue personnalisée effectuera le calcul et l'affichage.

  • Ouvrez MyDocument.nib dans Interface Builder. Dans la fenêtre Window se trouve un texte. Effacez-le.

  • Glissez une Custom View dans la fenêtre. Vous la trouverez dans la palette Library > Cocoa > Views & Cells.

  • Dans l'onglet View Size de l'Inspecteur, réglez les dimensions (W et H) de la vue à 400 x 300 pixels.

  • Dans l'onglet View Identity mettez la classe à CFRMandelbrotView.

Enregistrez, et revenez à XCode.
Pour simplifier, c'est la vue qui effectuera le calcul. Nous brisons le paradigme MVC, mais ce n'est pas bien grave pour ce programme d'essai.

Gestion des nombres complexes

Le langage Objective-C ne gère pas les nombres complexes. Nous allons devoir coder cela nous même. Pour commencer, déclarons dans CFRMandelbrotView.h un type "nombre complexe", basé sur une structure:

typedef struct Complexe_s
{
    double reel;    // Partie réelle
    double imag;    // Partie imaginaire
} Complexe_t;

Ajoutez également le prototype de la fonction qui permet d'élever un nombre complexe au carré:

Complexe_t Carre(Complexe_t z);

Passons maintenant à CFRMandelbrotView.m, pour y écrire la fonction:

Complexe_t Carre(Complexe_t z)
{
    Complexe_t carre;

    carre.reel = z.reel*z.reel - z.imag*z.imag;
    carre.imag = 2.0 * z.reel * z.imag;

    return carre;
}

Génération et affichage

Nous allons maintenant écrire la méthode -drawRect:. Cette méthode est appelée à chaque fois qu'il faut rafraîchir la vue. En pratique, dans ce premier programme, elle ne sera appelée que lors du premier affichage.

Création de la bitmap

Les bitmaps sont représentées par la classe NSBitmapRep. Créons une instance et initialisons-là:

NSBitmapImageRep* bitmapRep = [[NSBitmapImageRep alloc]
    initWithBitmapDataPlanes:NULL
    pixelsWide:400
    pixelsHigh:300
    bitsPerSample:8
    samplesPerPixel:1
    hasAlpha:NO
    isPlanar:NO
    colorSpaceName:NSDeviceWhiteColorSpace
    bytesPerRow:0
    bitsPerPixel:8];

Voilà une méthode avec beaucoup de paramètres !

  • Le premier paramètre est mis à NULL. Nous voulons que la méthode réserve la mémoire pour la bitmap elle-même.
  • pixelsWide et pixelsHigh sont les dimensions de la bitmap, en pixels.
  • samplesPerPixel (échantillons/pixel)
    Un échantillon est une composante de la couleur. Par exemple, une image RVB possède trois échantillons: un Rouge, un Bleu et un Vert. Comme nous générons une image en niveaux de gris, il n'y a qu'un échantillon par pixel.
  • bitsPerSample (bits/échantillon)
    Nous générons une image en 256 niveau de gris, ce qui requiert 8 bits/échantillon.
  • hasAlpha
    Indique si l'image possède une couche alpha (opacité). Dans notre cas, non.
  • isPlanar
    Il est possible de gérer plusieurs couches de couleurs séparément (une couche rouge, une verte, une bleu, une alpha). Pas dans notre cas.
  • colorSpaceName (nom de l'espace de couleur)
    Nous utilisons l'espace de couleur NSDeviceWhiteColorSpace, qui nous permet d'avoir la valeur maximale blanche. Vous pourrez essayer avec NSDeviceBlackColorSpace si vous voulez.
  • bytesPerRow (octets par ligne) Nous mettons à 0 pour que la méthode calcule cette valeur elle-même en fonction des autres paramètres.
  • bitsPerPixel
    C'est toujours 8 bits/pixel.

Calcul de l'ensemble

// Parcourir tous les points de la bitmap
double x, y;
for(x = 0; x < 400; x++)
{
    for(y = 0; y < 300; y++)
    {

Nous parcourons tous les pixels de la bitmap.

        // Convertir les coordonnées
        Complexe_t c;
        c.reel =  x/100.0 - 2;
        c.imag = -y/100.0 + 1.5;

Nous convertissons les coordonnées x et y du repère de la bitmap vers celui du plan mathématique.

        // Initialiser z[0]
        Complexe_t z = {0.0, 0.0};

Le calcul de chaque pixel commence par la mise à zéro de c.

        NSUInteger n;
        for(n=0; n < MAX_ITERATIONS; n++)
        {
            // z[n+1] = z[n+1]^2 + c
            Complexe_t zCarre = Carre(z);
            z.reel = zCarre.reel + c.reel;
            z.imag = zCarre.imag + c.imag;

            // La suite diverge si |z| > 2
            double moduleAuCarre = z.reel*z.reel + z.imag*z.imag;
            if(moduleAuCarre > 4.0)
                break;
        }

Nous recherchons ensuite combien il faut d'itérations pour que la suite diverge. Remarquez une optimisation ici: au lieu de tester si le module
√(a^2 + b^2) > 2
nous testons si
(a^2 + b^2) > 4

une racine carrée étant un calcul très coûteux en temps machine. Le code reste toutefois peu efficace: son amélioration est prévue dans un prochain article. La priorité est ici donnée à sa lisibilité.

        // Donner le niveau de gris au pixel
        NSUInteger nuance = n * 255 / MAX_ITERATIONS;

J'ai remanié la formule donnée dans l'article précédent. La division est faite en dernier, ce qui permet de faire tous les calculs sur des entiers (ce qui évite les casts et accélère un peu).

        [bitmapRep setPixel:&nuance atX:x y:y];
    }
}

Et enfin, nous écrivons la nuance dans la bitmap. Vous remarquerez que le premier paramètre de setPixel: est un tableau d'entiers. Étant donné que nous travaillons avec un seul échantillon par pixel, le tableau n'a qu'un seul indice, et il revient donc au même de passer un pointeur sur nuance.

Affichage

Affichons la bitmap dans la vue:

// Afficher la bitmap
[bitmapRep drawAtPoint:NSMakePoint(0,0)];

Rappelez-vous que l'origine de la vue se trouve dans le coin inférieur gauche.

Et finalement, il ne faut pas oublier de libérer la mémoire:

[bitmapRep release];

Le résultat

Lancez le programme. La fenêtre doit s'ouvrir avec l'ensemble dessiné.

L'ensemble généré

C'est beau !

La suite

Essayez différentes valeurs de MAX_ITERATIONS. Le rendu sera différent. Nous ajouterons bientôt des contrôles pour changer les paramètres du calcul.

Pour l'instant, la nature fractale de l'ensemble ne saute pas aux yeux, mais en observant attentivement, on retrouve tout de même un peu la forme de la "tête" sur les deux "ailes".
Une des améliorations à apporter sera justement la possibilité de se déplacer dans le plan, en particulier, de zoomer.

Le projet XCode complet à télécharger.

Renaud Pradenc
Céroce.com

Générateur d'images fractales (1)

03 02 2009 In: Pas à pas

Cet article est le premier d'une série consacrée à la réalisation d'une application complète: un générateur d'images fractales.

Les fractals

Broccoli fractal

Les fractals sont des objets géométriques qui présentent des motifs similaires lorsqu'ils sont observés à des échelles différentes. On ne peut les évoquer sans parler de l'incontournable Benoît Mandelbrot, polytechnicien français, qui ne les a certes pas inventé, mais leur a donné leur nom, et fut le premier à leur trouver des applications: calculs du périmètres des côtes bretonnes, statistiques, et surtout — ce qui a vraiment permis leur exposition au grand public — l'imagerie informatique.

Quelques rappels sur les nombres complexes

Le calcul de l'image s'appuyant sur les nombres complexes, je vais vous rappeler les principes nécessaires ici.

Nombres complexes

Un nombre complexe est de la forme:

z = a + ib
avec i^2 = -1

  • a est appelé partie réelle
    quand z représente les coordonnées d'un point, a est l'abscisse de ce point.

  • b est appelé partie imaginaire
    b représente l'ordonnée du point

Mise au carré

Mettons z au carré:
z * z = (a+ib)(a+ib) = a^2 + 2iab - b^2

Module

Le module de z est noté |z|.

|z|=√(a^2 + b^2).

L'ensemble de Mandelbrot

Beaucoup de gens ont déjà programmé des générateurs d'images fractales; le nôtre n'aura rien de révolutionnaire. On retrouve habituellement dans ces programmes deux ensembles: celui de Julia et celui de Mandelbrot, tous deux faciles à implémenter. Nous allons nous concentrer sur ce dernier.

Je suis bien incapable de vous expliquer le principe mathématique, mais peu importe, ce qui nous intéresse est le résultat !

La méthode de calcul

L'ensemble se calcule grâce à la suite:

z[n+1] = z[n]^2 + c
Avec z[0] = 0

z et c sont des nombres complexes:

  • c représente les coordonnées du point du plan en cours de calcul.

  • la suite z diverge après un certain nombre d'itérations — ou pas. Ce qui nous intéresse est le nombre n d'itérations nécessaire pour diverger, sachant que la suite diverge quand |z| > 2.
    Il sera nécessaire de limiter le calcul à un certain nombres d'itérations.

Conversions des coordonnées

Nous utiliserons une bitmap pour composer l'image. Une bitmap est une grille de pixels. Pour notre premier exemple, j'ai choisi d'adopter des dimensions de 400 par 300 pixels.
Le calcul de l'ensemble de Mandelbrot se fait lui sur un plan mathématique. J'ai choisi de faire évoluer ses abscisses entre -2 et +2. Par conséquent ses ordonnées évolueront entre -1,5 et +1,5 pour conserver les mêmes proportions que la bitmap.

Conversion des coordonnées

Grâce à la figure, on peut déterminer que les coordonnées se convertissent ainsi:

c.réelle = bitmapX/100 - 2  
c.imaginaire = -bitmapY/100 + 1,5

La couleur

Tous les exemples d'images que vous avez dû voir sont très colorés, cependant, c'est uniquement le nombre d'itérations n qui nous donne la teinte. Pour commencer nous allons donc produire une image en niveaux de gris, 256 niveaux exactement (de 0 à 255).

nuance = (n/MaxIterations) * 255

MaxIterations est le nombre maximal d'itération. J'ai choisi après plusieurs essais que MaxIterations = 18.

La suite

Dans le prochain billet, nous mettrons au point la première version du générateur. Ne zappez pas !

Renaud Pradenc
ceroce.com