Premier défi Qt : le Buddhabrot

Thibaut Cuvelier

Les défis Qt sont des petits exercices à faire soi-même ou en équipe sur un sujet précis. Le sujet de ce premier défi est le dessin de fractales, précisément de Buddhabrot.

Retrouvez ce défi sur le forum.

- Titre : Premier défi Qt : le Buddhabrot

- Auteur : Thibaut Cuvelier

- Parution : 22 novembre 2009

- Mise à jour : 15 décembre 2009

- Licence : Copyright ® 2009 Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Présentation

- II. Le Buddhabrot

- III. Consignes

- III-A. Fonctionnement du programme

- III-B. Fichier à rendre

- III-C. Environnements cibles

- IV. Évaluation

- IV-A. Critères

- IV-B. Jury

- IV-C. Grille de cotation

I - Présentation

L'équipe Qt vous souhaite la bienvenue sur la page du premier défi Qt.

Les défis Qt sont des petits exercices à faire soi-même ou en équipe sur un sujet précis, à la manière des examens ou des exercices de livres. Ces codes à écrire sont étudiés de sorte que tous y trouvent leur compte : parfois de l'algorithmique, mais pas uniquement, car Qt ne fait pas que dans ce domaine spécifique. Il s'agit d'un framework complet : les défis essayent d'exploiter cette richesse. Ceci ne signifie pas qu'aucune réflexion n'est nécessaire : il faut connaître Qt, il ne s'agit pas d'écrire quelques lignes sans y réfléchir.

Retrouvez ce défi sur le forum.

II - Le Buddhabrot

Le but général est de proposer une application qui génère une fractale de type Buddhabrot et qui l'affiche. Le but de ce défi n'est donc pas l'implémentation en elle-même des routines de génération de la fractale, il s'agit uniquement de la représenter. Cependant, ceux qui parviendront à générer la même fractale plus rapidement sans utiliser de bibliothèque externe ou en l'adaptant auront des points bonus.

Ainsi, nous vous proposons un module de génération de fractales. Celui-ci est minimaliste, mais permet de générer plusieurs types de fractales : un bateau en feu, le Mandelbrot, le Buddhabrot (évidemment), le Tricorn et bien d'autres. Vous pouvez sans problème si l'envie vous en dit ajouter le support d'autres fractales : le module est prévu pour cela. Il est aussi simple à utiliser, l'exemple fourni devrait vous en convaincre facilement.

Le Buddhabrot en couleurs (cliquer pour zoomer)

(cliquez ici pour aggrandir l'image)

Version haute qualité.

La suite de la section est extraite de l'article Wikipédia sur le sujet (page consultée le 4 novembre 2009). En tant que telle, son contenu est disponible sous les termes de la licence Creative Commons.

Le Buddhabrot est une technique particulière pour représenter une fractale de Mandelbrot.

Mathématiquement, l'ensemble de Mandelbrot est l'ensemble des points c du plan complexe tels que la suite (zn) définie par z_{n+1} = {z_n}^2 + c avec z0 = 0 ne tende pas vers l'infini en module (on dit que le point ne s'échappe pas).

La méthode traditionnelle pour tracer l'ensemble de Mandelbrot est de colorier en noir les points appartenant à l'ensemble, et les autres dans une couleur dépendant du nombre d'itérations nécessaires pour qu'ils s'échappent. Pour obtenir le Buddhabrot, on utilise un tableau à deux dimensions, chaque case représentant un pixel. Pour des points c choisis au hasard (ou, alternativement, régulièrement espacés) dans le plan, si ces points s'échappent après un certain nombre d'itérations (donc n'appartiennent pas à l'ensemble de Mandelbrot), on incrémente le tableau aux points correspondant aux valeurs successives de z prises par la suite (zn) (on suit le parcours des points). Après un certain nombre d'itérations, l'image obtenue en affectant une couleur à chaque point du tableau se stabilise sur le Buddhabrot.

Le nombre d'itérations a un effet décisif sur le résultat visuel. De plus grandes valeurs donnent un aspect plus complexe, alors que des valeurs plus faibles donneront une image plus géométrique.

La technique peut être exécutée pour différents nombres d'itérations et différentes couleurs, qui peuvent ensuite être combinées pour des résultats spectaculaires en plusieurs couleurs.

III - Consignes

À l'aide du module de génération de fractales proposées, vous devez créer un programme avec une interface utilisateur graphique (GUI) qui permet d'afficher une fractale, le Buddhabrot, en permettant de changer les paramètres passés au générateur.

Il faudra également améliorer le module de rendu : algorithmiquement, il est correct. Par contre, il n'est pas optimisé, cette partie vous étant laissée. Vous ne pouvez utiliser que la librairie standard du C++ pour ce faire, pas d'autre bibliothèque comme GMP ou MKL, à moins que Qt ne l'utilise. Au même titre, le code assembleur n'est pas autorisé, tout comme le Fortran ou le C.

Le défi durera 3 mois. Il débute le lundi 30 novembre 2009 à minuit et se termine le dimanche 28 février 2010 à minuit. Les dernières participations pourront être rendues jusque ce dimanche 28 février 2010 à minuit, la date et l'heure de la fin du téléversement faisant foi.

Le plus important est de fournir un programme totalement fonctionnel !

Votre code sera présentable : c'est-à-dire lisible, bien présenté, aéré, indenté d'une manière homogène, commenté en suffisance pour une compréhension rapide du code.

Il est possible, et même conseillé, de travailler en équipe, vu les critères à respecter.

Les règles générales des défis sont d'application, mais, le cas échéant, seront supplantées par les règles précises de ce défi.

Vous pouvez télécharger le générateur (550 ko). Que Yan trouve ici nos remerciements pour l'avoir écrit spécialement pour ce défi !

III-A - Fonctionnement du programme

Le programme doit posséder une interface graphique créée à l'aide de Qt et d'aucune autre bibliothèque, même si cette autre bibliothèque repose entièrement sur Qt (comme Qwt, Qxt...). Il est interdit d'afficher la fractale dans une console, mais une console peut être présente pour afficher, par exemple, l'avancement dans la génération de la fractale ou des messages d'erreurs.

Si votre programme supporte plusieurs fractales, l'utilisateur doit pouvoir la choisir au lancement de l'application. Optionnellement, il pourra en changer après le lancement.

Le programme pourra résister à toute tentative de l'utilisateur de le faire planter.

Le programme ne semblera jamais "planté" : il y aura un indicateur pour afficher l'état d'avancement de la génération ou de toute autre activité nécessitant des calculss pouvant ralentir considérablement le programme.

III-B - Fichier à rendre

Le fichier que vous rendrez au jury par l'intermédiaire de la page prévue à cet effet devra impérativement contenir un fichier de projet .pro. Si vous utilisez un IDE qui ne supporte pas ces fichiers, vous pouvez fournir le fichier de projet pour cet IDE en supplément.

Les fichiers source de votre application seront rangés dans un répertoire spécifique. Ceux du générateur seront inclus dans l'archive. Par contre, tout autre fichier dans l'archive du générateur n'y trouvera pas sa place.

La documentation pourra être rangée à la racine si elle tient en un seul fichier (fichier texte, TEX, PDF...), mais devra être dans un sous-dossier dans l'autre cas (documentation Doxygen...).

Aussi, vous fournirez un fichier de type README, dans lequel vous marquerez votre accord pour une éventuelle diffusion sur les pages Sources de Developpez.com. Vos sources seront libres de droits (open source). Vous y marquerez aussi votre environnement de développement (version de Qt, compilateur et version, système d'exploitation et version) pour en faciliter la correction.

Dans un autre fichier, vous décrirez brièvement votre projet et comment vous l'avez mené à bien (problèmes rencontrés, difficultés surmontées sans problème, recherche d'idées, idées abandonnées, le temps approximatif de développement, choix de tel algorithme, paradigme de conception...). Si vous utilisez d'autres algorithmes pour calculer les fractales, vous y ajouterez la description des algorithmes employés.

Toute proposition ne respectant pas ce point pourra être rejetée !

III-C - Environnements cibles

Votre programme devra fonctionner avec l'une de ces versions de Qt. Vous devrez l'indiquer dans l'archive rendue.

Versions de Qt

- 4.5.3 (Windows, Linux, Mac OS X)

- 4.6 (Windows, Linux, Mac OS X)

Un de ces environnements devra être supporté. Qt est déjà porté pour l'ensemble de ces plateformes. Aucune plateforme mobile n'est supportée, vu la nature du défi.

Compilateurs pour Windows 32 bits

- GNU GCC 3.4.5 (port MinGW)

- GNU GCC 4.4.0 (port MinGW)

- Microsoft Visual C++ 2008 SP1 (édition Express gratuite incluse)

- Intel C++ Compiler 11.1

Compilateurs pour Windows 64 bits

- Microsoft Visual C++ 2008 SP1 (édition Express gratuite incluse)

- Intel C++ Compiler 11.1

Compilateurs pour Linux 32 bits

- GNU GCC 4.4.2

Compilateurs pour Mac OS X 32 bits

- GNU GCC 4.4.2

Nous essayerons autant que possible de tester vos propositions avec la même configuration que vous. Mais cela ne sera pas toujours possible.

Qt supportant par nature plusieurs compilateurs et systèmes d'exploitation, il est possible que votre code soit testé sous un autre environnement que celui que vous utilisez. Ceci ne doit changer en rien les parties qui utilisent directement Qt dans votre code.

IV - Évaluation

IV-A - Critères

Ces critères sont obligatoires : toute participation sera jugée selon ceux-qui au minimum.

- Qualité du code C++ (lisible, modulaire, commenté, bien présenté...),

- Qualité du code Qt (exploitation de Qt, multiplateforme...),

- Qualité de la gestion mémoire (pas de fuite mémoire, mémoire bien gérée...),

- Internationalisation,

- Documentation,

- Optimisation du générateur,

- Respect des consignes du défi.

Les critères suivants sont, quant à eux, optionnels : ils vont par paire, et seul l'un des deux sera retenu pour la cote finale. En effet, tout le monde n'a pas les mêmes capacités, par exemple en design d'interface graphique : il ne serait pas juste de défavoriser ceux qui produisent facilement des interfaces ergonomiques sans design particulier, par exemple.

- Interface graphique : ergonomie ou design ;

- Optimisation du calcul : multithread, calcul distribué sur plusieurs machine ou méthode de rendu.

Il est aussi possible de dépasser le minimum demandé : évidemment, cela sera récompensé à sa juste valeur. Ces critères peuvent vous mettre sur la piste pour dépasser nos attentes.

- Génération de fractale autre que Buddhabrot,

- Génération d'autres fractales que celles proposées par le module de génération,

- Animation de la génération,

- Colorisation de la fractale générée,

- Génération réagissant aux changements de paramètres en temps réel (sans regénération complète).

IV-B - Jury

Voici la constitution du jury. En cas de problème pour remettre votre candidature ou d'incompréhension des règles, vous pouvez les contacter.

- alp,

- dourouc05,

- ikipou,

- johnlamericain,

- superjaja,

- yan.

IV-C - Grille de cotation

Critère

Points à accumuler
(40 au total)

Fonctionnement minimal du programme

Total : 19

Affichage de la fractale Buddhabrot

8

Changement des paramètres de génération

4

Internationalisation

3

Efficacité de l'optimisation du générateur

4

Qualité du code

Total : 13

Qualité d'un point de vue C++

4

Qualité d'un point de vue Qt

4

Gestion de la mémoire

4

Documentation minimale

1

Interface graphique (critère optionnel)

Total : 4

Ergonomie

(4)

Design

(4)

Optimisation du générateur (critère optionnel)

Total : 4

Multithreading

(4)

Calcul distribué

(4)

Autre méthode de rendu, de calcul

(4)

Autre type d'optimisation

(4)

Bonus (critères facultatifs)

Total : +24

Génération d'autres fractales (supportées par le module)

1

Génération d'autres fractales (non supportées par le module)

2

Documentation en suffisance

3

Animation de la génération

4

Colorisation de la (des) fractale(s)

4

Changement des paramètres en temps réel

4

Surprenez-nous !

6

Malus

Total : -16

Utilisation d'un autre langage (C, Fortran, assembleur...)

-4

Utilisation d'une autre bibliothèque non utilisée par Qt (GMP, Qwt...)

-4

Application peu robuste

-2

Application semblant plantée

-2

Erreurs à la compilation

-2

Avertissements à la compilation (sauf si justification dans le README)

-1

Fichiers inutiles dans l'archive

-1

Retour à l'article