Notes de Deckard du 17/04/2007:
Fractal-Ware : voici une
production underground atypique fort sympatique et ce pour au
moins 2 raisons:
- son sujet touche aux mathématiques et à la
programmation du graphisme sur Apple II (DHGR), ce qui est
extrèmement rare (pour les maths c'est d'ailleurs le seul
à ma connaissance, avec en plus la volonté
d'expliquer ce qui a été fait). Quand les
études et l'informatique "plaisir" se rejoignent, on obtient
de jolies choses.
- l'auteur, Perfect Bugs du
groupe de hackers The $FF59 Connection
(aidé par son comparse The Last
Jedi pour la 1ère routine de
dessin DHGR),
adopte un profil
modeste et admet d'emblée la possibilité
d'erreurs dans ses explications, son travail étant
expérimental. On est bien loin de l'esprit crâneur
d'autres
personnes de cette époque pour des sujets bien plus terre
à terre...
Le logiciel prend 2 faces (qui ne sont pas sous le même
système d'exploitation).
Sur la 1ère (DOS 3.3) se trouve des fichiers explicatifs et
les programmes permettant de s'amuser avec des fractales.
La face 2 est un slide show sous ProDOS utilisant
l'interpréteur graphique Arlequin
copyrighté Le
Chat Mauve.
C'est aussi ce programme qui a été
utilisé pour créer les images correspondantes
(les commandes avec ampersand de l'interface DHGR).
A noter qu'il est possible de trouver d'autres programmes abordant les
fractales mais le plus souvent, c'est le fruit d'une programmation sur
Apple IIGS et pas sur la gamme 8 bits.
Par exemple: Mandelbrot II GS
de Lim Thye Chean, un
programme intitulé FractalMagic
pour lequel la
société Sintar
Software a fait de la
publicité ou encore Fractal
Explorer signé Eclat
Microproducts (pour IIGS avec moniteur couleur).
Voici le package commercial de ce dernier (image d'ebay de Vintage
Micros, le produit étant mis aux
enchères
à 10 dollars US):
Plus récemment, j'ai découvert aussi la page de
Lazarus I. Long avec ses
réalisations sur les
fractales.
Les joueurs sur Apple II se rappelleront plus facilement quelques
parties du jeu d'arcade Rescue on
Fractalus! de LucasFilm
Games & TMQ Software.
Ce jeu d'action vous emmenait sur une planète
étrangère, et vous dirigiez un
vaisseau devant récupérer des
pilotes (en évitant de
récupérer des aliens
déguisés). Le paysage affiché
(montagnes) résultait du calcul de fractales.
Quelques clichés du jeu sous émulateur:
Quelques snapshots de Fractal-Ware:

|
DOS 3.3 |
Download Fractal-Ware side 1 (gzipped)
|

|
ProDOS |
Download Fractal-Ware side 2
(bootable slide show) (gzipped)
|
SIDE 1: BOOT FROM SLOT 6. DO NOT DEFINE SLOT 7 AS A BOOTABLE DEVICE
(HARD DRIVE, ...)
Disk : Fractal_Ware-f1.dsk
"-" files are DELETED files | "*" files are LOCKED files
----------------------------------------------------------------------
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000) 000
FRACTAL-WARE
T A$0000 (000000) L$0000 (000000)
000
BY
T A$0000 (000000) L$0000 (000000) 000
PERFECT
BUGS
T A$0000 (000000) L$0000 (000000)
000
SEP.89
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$1C00 (007168) 028
INTRODUCTION
T A$0000 (000000) L$1400 (005120) 020 PART
1
T A$0000 (000000) L$2000 (008192) 032 PART
2
T A$0000 (000000) L$1100 (004352) 017 PART
3
T A$0000 (000000) L$1500 (005376) 021 PART
4
T A$0000 (000000) L$1900 (006400) 025 PART
5
T A$0000 (000000) L$2C00 (011264) 044 PART
6
T A$0000 (000000) L$1E00 (007680) 030
COMP.GRAPHIQUES
T A$0000 (000000) L$0800 (002048) 008
WHAT
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
PROGRAMMES
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
A A$0000 (000000) L$0948 (002376) 011
OL-SYSTEM
A A$0000 (000000) L$0B29 (002857) 013
FM2D
A A$0000 (000000) L$0C12 (003090) 014
MIDPOINT
A A$0000 (000000) L$0321 (000801) 005
LSMASS
A A$0000 (000000) L$01C2 (000450) 003
JULIASET
A A$0000 (000000) L$01AA (000426) 003
LSM
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
ROUTINES
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
B A$8000 (032768) L$03FE (001022) 006
DHGR
B A$0300 (000768) L$00A9 (000169) 002
COMMUT_2_HIRES
B A$9000 (036864) L$00FF (000255) 003
MOVE
B A$8000 (032768) L$0448 (001096) 006
DHGR3
B A$0901 (002305) L$011A (000282) 003
DETER.S
B A$1000 (004096) L$002C (000044) 002
DETER
B A$1000 (004096) L$023E (000574) 004
MSET3
B A$0901 (002305) L$0953 (002387) 011
MSET3.S
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000) 000
PRODOC
READER
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
A A$0000 (000000) L$01C9 (000457) 003
PRODOC
B A$1500 (005376) L$0430 (001072) 006
DATAS
B A$6000 (024576) L$0C00 (003072) 014
LOGO.TBT
B A$4000 (016384) L$060B (001547) 008
PI.PAK
B A$7000 (028672) L$0812 (002066) 010
PRODOC.CTN
B A$1A00 (006656) L$05E2 (001506) 007
PRODOC.NOMS
B A$5000 (020480) L$010E (000270) 003
TYPE.PRONTODOS
B A$8000 (032768) L$0091 (000145) 002
UN-PACK
B A$2000 (008192) L$2C81 (011393) 046
MAN3D
B A$8000 (032768) L$03C1 (000961) 005
DECOMP.EXTASIE
B A$2800 (010240) L$06D2 (001746) 008
M.MIDNIGHT
B A$0300 (000768) L$00D0 (000208) 002
PLAYER
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000) 000 A FEW
PICTURES
T A$0000 (000000) L$0000 (000000)
000
T A$0000 (000000) L$0000 (000000)
000
A A$0000 (000000) L$00BE (000190) 002 SLIDE
SHOW
B A$4000 (016384) L$0B9F (002975) 013
PI.MANDEL1.PAK
B A$4000 (016384) L$0D2E (003374) 015
PI.MANDEL2.PAK
B A$4000 (016384) L$0EF5 (003829) 016
PI.MANDEL3.PAK
B A$4000 (016384) L$0E4B (003659) 016
PI.MANDEL4.PAK
This catalog contains 67 files. 0 were DELETED.
----------------------------------------------------------------------
PRODOS --> /FRAC
PRODOS
| SYS | A$2000 | L$3A00 | B$001E
*ARLEQUIN.SYSTEM | SYS | A$2000 | L$2800 | B$0015
*GLI16.2
| BIN | A$0800 | L$37F0 | B$001D
*GLIDATA
| BIN | A$4000 | L$0385 | B$0003
*GLI.ERRORS | BIN |
A$4400 | L$0400 | B$0003
STARTUP
| BAS | A$6001 | L$012D | B$0001
MAN2H
| $F8 | A$0385 | L$080E | B$0006
MANDEL
| $F8 | A$0385 | L$1428 | B$000C
FM2D
| BAS | A$0801 | L$0B20 | B$0007
FRAC
| $F8 | A$0385 | L$1367 | B$000B
MAN
| $F8 | A$0385 | L$0B2A | B$0007
MAN0
| $F8 | A$0385 | L$1082 | B$000A
SP
| BAS | A$6001 | L$01BE | B$0001
MAN1
| $F8 | A$0385 | L$171D | B$000D
SP2
| BAS | A$6001 | L$01BC | B$0001
LSMEX
| BAS | A$6001 | L$02E1 | B$0003
MSETE
| BIN | A$8000 | L$01E9 | B$0001
Sommaire
Lien
|
Fichier
|
 |
Introduction.
|
 |
Explications: partie 1.
|
 |
Explications: partie 2.
|
 |
Explications: partie 3.
|
 |
Explications: partie 4.
|
 |
Explications: partie 5.
|
 |
Explications: partie 6.
|
 |
Compléments graphiques.
|
 |
Contenu du disk.
|
Introduction.
+-----------------------------------------------------------------------------+
!
Perfect
Bugs
!
!
From The
$FF59-Connection
!
!
presents
!
!
The Fractal Images on the Apple
II
!
+-----------------------------------------------------------------------------+
Ca fait un peu pompeux comme titre, mais que
voulez-vous, on fait ce que
l'on peut avec ce qu'on a.
Pour commencer, je tiens à avertir que
ce qui suit peut etre sujet à
caution. Il me semble avoir compris, non pas la théorie des
fractales, laquelle
n'est pas très compliquée mais
nécessite néammoins de très solides
bases en
maths, mais tout au moins le principe qui permet de calculer et
d'afficher ces
fractales. Mais encore une fois, je peux m'etre trompé
à certains endroits (je
suis sur qu'un matheux va me lire et va dire : 'Mais qu'est ce que
c'est que ce
plouc qui s'est planté partout, et qui en plus n'est
mème pas clair dans ces
explications. Ce n'est pas rigoureux tout cela !!!' . Si c'est le cas,
j'apprécierai vivement qu'il me contacte sur RTEL, Bal
PERFECT BUGS, pour me
dire où le bat blesse.). D'autre part, les programmes
fournis sont loins d'ètre
parfaits pour deux raisons : La première est que la plupart
des fractales sont
assez faciles à programmer en langage
évolué tel que le PASCAL, mais tout le
monde connait la rapidité de calcul d'un Apple travaillant
sous PASCAL, et
quant à les programmer en assembleur, basta...La seconde
étant que je ne suis
pas vraiment une bète en assembleur, justement, et en plus
je suis flemmard, ce
qui fait deux choses incompatibles à la production de
programmes corrects.
Bien, maintenant, on y va...
La première chose à savoir
est-ce qu'est une fractale. Il existe en fait
plusieurs types de fractales, mais toutes ont en commun une
caratéristique que
l'on appelle 'auto-similarité' (ou 'self-similarity', si
vous préférez). Ce nom
barbare désigne en fait une propriété
très simple : lorsque vous observez un
fractale à n'importe quel niveau d'observation, n'importe
quel agrandissement,
on peut constater la répétition d'un
mème motif géométrique, ce qui ne veut
pas
dire que l'image observée est exactement la mème
qu'à une autre échelle, mais
il y a certaines similitudes. Les reliefs de cotes ont une
self-similarity
moins prononcée que la courbe de Von Koch,
expliquée ci-après. Si vous avez le
mème bouquin de PASCAL que moi (APPLE PASCAL sur le bout des
doigts), un gros
bouquin bleu, ouvrez le page 618. En haut de la page se trouve un
schéma qui
résume la courbe de Von Koch. Pour les autres, qu'ils
prennent un papier et un
crayon et suivent mes indications : imaginez un segment de droite de
longueur l
que vous partagez en trois segments égaux. A partir du
segment central vous
tracez un triangle équilatéral dont les
cotés ont donc pour longueur l/3, et
vous effacez la base du triangle (je résume en donnant cette
formule en
'langage tortue' qui sera utilisée plus loin: F-F++F-F, ou F
désigne le segment
de droite ,- un rotation de la tortue de (-60°) et + une
rotation de (+60°)).
Maintenant, sur chaque segment ainsi obtenu (segments hors triangle y
compris),
vous répétez le processus. Au bout d'un certain
nombre de cycles, vous
obtiendrez une figure qui ressemble vaguement à un flocon de
neige. Dans la
théorie, le nombre de subdivisions est infini, et vous
pouvez constatez que
quelle que soit l'échelle, on retrouve le mème
motif, à savoir un triangle
equilatéral fixé à un segment. Bien
sùr, cette courbe est très
particulière car
elle se reproduit exactement semblable à elle
mème. On dit qu'elle possède une
auto-similarité 'exacte' (par opposition au relief de cotes
qui possèdent une
auto-similarité 'statistique'). C'est bien joli tout cela,
me direz vous, mais
comment fait-on pour afficher toutes ces belles images? Patience, on y
arrive.
Laissez moi au moins terminer les définitions. Tout ceci
nous montre les
différences fondamentales existant entre la
géométrie Euclidienne et les
fractales. Si vous observez un cercle un à un niveau
d'observation de plus en
plus grand, vous aurez l'impression que le rayon de courbure augmente
de plus
en plus. La géométrie Euclidienne n'est pas apte
à définir avec précision les
objets dans la nature (vous avez déja essayé de
définir un nuage à partir de
triangles, de cercles, etc... Bonne chance si vous voulez essayez !!!).
Je
résume tout ça :
Géométrie
Euclidienne
Fractales
-
Valable pour
objets
- Valables pour les objets
géométriques
et formes naturelles
-
Aspect dépend
de
- Pas d'échelle
l'échelle
-
Peut s'exprimer
sous
- Nécessite le plus souvent
forme de
formules
l'utilisation de la
récursivité
Comme on l'a vu plus haut, deux grandeurs sont
importantes dans la
définition d'un fractale : le nombre de subdivisions par
cycle et ce qu'on
appelle le 'ratio', c'est-à-dire le rapport de la longueur
obtenue d'un segment
de base après avoir fait 1 division sur la longueur de
départ. Mouais...C'est
pas très clair tout ça. Je reprends : dans la
courbe de Von Koch, on divisait
par trois, puis on prenait les segments obtenus, et on divisait
à nouveau par
trois. Le nombre de subdivisions est 4 (et oui !!! Un segment, puis les
deux
cotés du triangle équilatéral, plus un
autre segment). La longueur du segment
final après 1 division était l/3. On fait le
rapport (l/3)/l et on obtient donc
r=1/3. C'est la ratio. Comprendo? Ces deux grandeurs
définissent ce que l'on
appelle la dimension fractale, et qui est donnée par la
formule :
D = (Log N)/(Log (1/r)) (cette formule se déduit
de N*r^ D=1)
Notez que la base du logarithme n'a pas
d'importance puisque l'on fait un
rapport.
Dans le cas de la courbe de Von Koch, on obtient D
= Log 4/Log 3 = 1.26
Quand cette dimension est proche de 1, la fractale
est proche d'une droite.
Si D est proche de 2, la fractale est proche du plan. Si D est proche
de 3, la
fractale est proche de l'espace. Il existe des cas où
D>3, mais les modes de
représentation sont différents. Nous aborderons
ce cas en dernier.
Voilà, les bases sont en place et on va
étudier maintenant les différents
modes de calcul et leur mode de représentation. A tout de
suite...
+-----------------------------------------------------------+ Perfect
Bugs +--+
Retour sommaire
Explications: partie 1.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Part I : Les fractales auto-similaires exactes
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Bon, nous voilà au pied du mur,
à savoir calculer et afficher ces fractales.
Comme le titre du chapitre vous l'a sans doute
suggéré, on va commencer par les
fractales auto-similaires exactes, telle la courbe de Von Koch. Dans
l'intro,
j'avais abordé une sorte de langage tortue. En fait, pour ce
type de fractales,
deux méthodes s'offrent à vous : utilisez des
programmes récursifs, et donc le
PASCAL, et là vous allez vous marrez parce que la
programmation récursive est
extrèmement compliquée à mettre en
place (Quand on a les algorithmes, no
problem... Mais quand on doit faire soi-mème ces
algorithmes, alors là
Bonjour.). La deuxième méthode, que j'aborde ici,
est donc d'utiliser un
langage tortue. Cette méthode a un énorme
avantage sur la première, qui est
qu'elle est générale et qu'elle permet d'afficher
n'importe quelle fractale
auto-similaire exacte, ce qui n'est pas le cas de la programmation
récursive,
qui nécéssite un programme différent
pour chaque fractale.
Cette méthode est d'une
simplicité extrème :
- Toute fractale
'exacte' (j'abrège...) est définie par un axiome
de
départ et par des règles de transformations. Ex.:
Et zou, on reprend la courbe
de Von Koch.
L'axiome de départ est F (on part d'un
segment) et la règle de
transformation est F ==> F-F++F-F (On remplace tout segment par
cette suite.
Reportez vous à l'intro pour avoir la signification des
symboles). A chaque
cycle on remplace ainsi chaque segment (codé F) par cette
suite. On ne se
préoccupe pas de la longueur des segments. A noter que selon
les fractales, on
peut avoir plusieurs règles de transformation. La
méthode consiste donc à
partir d'une chaine de base, qui est l'axiome, et de remplacer tous les
caractères de cette chaine par leur règle de
transformation, et ce à chaque
cycle. Ainsi, pour la courbe de Von Koch, voici ce que l'on obtient :
Cycle:
1
F-F++F-F
Cycle:
2
(F-F++F-F)-(F-F++F-F)++(F-F++F-F)-(F-F++F-F)
J'ai mis des parenthèses de
façon à ce que vous voyez bien le principe, mais
elles n'apparaissent normalement pas.
Comme vous pouvez le voir, c'est
évident. Un conseil de programmation
cependant : cette méthode peut générer
de très longue chaine de caractères
(plus de 5000 dans certains cas), ce qui dépasse de loin le
maximum de 255
caractères pour une chaine. Stockez donc vos
caractères sous forme d'octets
directement dans la mémoire, à partir de $4000
par exemple (attention au DOS en
$9600 !!).
Quand à l'interprétation
graphique, elle est très simple : vous définissez
un angle de départ (dans mon programme, pour simplifier, 0
radian correspond à
la tortue orientée vers la droite de l'écran), et
un incrément pour l'angle à
chaque rotation. Les formules du nouveau point en fonction de l'angle,
de la
longueur d'un segment et des coordonnées de l'ancien point
s'expriment comme
suit :
X' = L * Cos (TH) + X
Y' = L * Sin (TH) + X
Voici les ordres que comprend le programme OL-SYSTEM :
F : Tracé d'un segment
+ : Rotation à droite d'un nombre de radians
prédéfinis
- : Rotation à gauche
< : On sauvegarde l'état de la tortue dans
une pile (dans le prgm en $9100)
> : On récupère
l'état de la tortue de la pile
On peut bien sur rajouter des ordres, en
particulier en ce qui concerne la
couleur. A vous de jouer...
Enfin, pour terminer ce chapitre, voici quelques
fractales à essayer :
- Courbe de Von Koch:
Axiome : F
Transformation : F ==> F-F++F-F
Angle : PI/3
- Courbe d'Hilbert :
Axiome : X
Transformation : X ==> -YF+XFX+FY-
Y ==> +XF-YFY-FX+
Angle : PI/2
- Courbe de Sierpinsky :
Axiome : FXF--FF--FF
Transformation : F ==>
--FXF++FXF++FXF--
Angle : PI/3
- Courbe de Peano :
Axiome : X
Transformation : X ==>
XFYFX+F+YFXFY-F-XFYFX
Y ==> YFXFY-F-XFYFX+F+YFXFY
Angle : PI/2
- Quelques buissons et arbres :
Axiome : F
Transformation : F ==>
F<+F>F<-F>F
Angle : PI/7
Axiome : G
Transformation : G ==>
GFX<+G><-G>
X ==> X<-FFF><+FFF>FX
Angle : PI/7
Axiome : F
Transformation : F ==>
FF+<+F-F-F>-<-F+F+F>
Angle : PI/8
Axiome : SLFFF
Transformation : S ==>
<+++G><---G>TS
G ==> +H<-G>L
H ==> -G<+H>L
T ==> TL
L ==> <-FFF><+FFF>F
Angle : PI/10
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Explications: partie 2.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Part II : Les fractales aléatoires
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
On aborde maintenant des fractales assez
différentes de celles évoquées dans
le premier chapitre : ce sont les fractales à
auto-similarité statistique, ou
fractales aléatoires. Avant toute chose, il faut
définir le terme 'aléatoire'
dans le sens où il est utilisé dans les calculs.
Imaginez que vous fassiez une
succession de RND que vous logez dans une table. Supposons maintenant
que vous
fassiez correspondre à chaque valeur de la table une
altitude et que vous
reliez les points deux à deux entre eux. Vous obtenez un
courbe assez fouillie,
avec de fortes distorsions. Les fractales nécessitent
l'utilisation d'un autre
type de système aléatoire. Celui ci est
appelé 'Mouvement Brownien' . Ce
système est d'autre part basé sur l'utilisation
de nombres aléatoires Gaussian,
dont la formule est donnée ci-dessous :
Z = (1/A) * SQR (12/n) * SUM -SQR(3*n)
Où n désigne le nombre de
nombres aléatoires purs à prendre et A
l'intervalle dans lequel seront choisis ces nombres (fonction RND. On
choisit
d'habitude A = 2^31 - 1 ). SUM désigne la somme de 1
à n des nombres
aléatoires.
Voici un petit programme basic pour vous aider
à mieux comprendre :
n=4
10 SUM = 0
20 FOR I= 1 TO n
30 SUM = SUM + RND(1)
40 NEXT I
50 Z=(1/A)*SQR(12/n)*SUM-SQR(3*n)
Un truc extrèmement
intéressant au passage. Wozniak (un des mecs les plus
géniaux de la terre) a vraiment créé
un petit chef d'oeuvre avec nos chers
Apple. Quand vous faites RND(-S) où S est un nombre positif,
vous initialisez
une suite aléatoire de la machine, c'est-à-dire
que quand vous ferez ensuite
RND(1) et que à n'importe quel moment vous refassiez
RND(-S), puis RND(1), vous
obtenez les mèmes nombres. Assez giga, car cela permet de
définir un monde
entier uniquement avec un nombre.
On continue. L'une des méthodes les
plus couramment employées pour calculer
des surfaces fractales consiste à utiliser la
méthode du déplacement Gaussian
des milieux. Imaginez une grille carrée de coté
n, représentée ci dessous (on a
pris n=8)
o . . . ° . . .
o Les 'o' ont des altitudes
calculées en utilisant la
.
. méthode ci-dessus. Le
principe consiste
à prendre
.
. le milieu de ces quatre points, de
faire le moyenne
.
. des altitudes et d'ajouter un nombre
Gaussian. On
°
x
° obtient
alors le point x, centre du carré. Ensuite,
.
. on calcule les altitudes des points des
bords,
points
.
. ° (en faisant la moyenne des
trois points
voisins o
.
. et x, et un ajoutant un nbre Gaussian).
Et on
o . . . ° . . .
o reboucle (les grilles suivantes sont
représentées ci-
Grilles I et
II après, avec pour
notations o les anciens points et X
les nouveaux).
o . . . o . . .
o
o . . . o . . .
o La grille I représentant
.
.
.
. en fait deux grilles,
.
X
X
.
. o X
o
. on constate qu'il faut
.
.
.
. 8 grilles, avec pour les
o
o
o
o
X o X
o grilles
paires le calcul
.
.
.
. des points milieux de
.
X
X
.
. o X
o
. points situés
.
.
.
. verticalement ou
o . . . o . . .
o
o . . . o . . .
o horizontalement les uns
III
IV
rapport aux autres et
pour les grilles impaires
le calcul des points
o . X . o . X .
o
o . o . o . o .
o milieux de points situés
.
.
. X
X X X
. en diagonale les uns
par
X
o o
o
X
o o o
o
o rapport aux autres. Quand
.
.
. X
X X X
. aux grilles Bis, elles
o
o o
o
o
o o o
o
o calculent les points des
.
.
. X
X X X
. bordures, lesquelles
ne
X
o o
o
X
o o o
o
o sont calculées
qu'à partir
.
.
. X
X X X
. de trois points
seulement,
o . X . o . X .
o
o . o . o . o .
o dont deux situés sur
IV
Bis
V
les
bords. On remarque
aussi qu'il y a une
exception au calcul dans
o X o X o X o X
o
o o o o o o o o
o la première grille. En
X o
o o o
X
o o X o X o X o
o effet, on passe
o
o o
o
o
o
X o X o X o X o directement du calcul des
X o
o o o
X
o o X o X o X o
o points de bordure aux
o
o o
o
o
o
X o X o X o X o au calcul des points
X o
o o o
X
o o X o X o X o
o diagonaux, car il n'y a
o
o o
o
o
o
X o X o X o X o pas de points verticaux
X o
o o o
X
o o X o X o X o
o à calculer au premier
o X o X o X o X
o
o o o o o o o o
o cycle, ce qui explique la
V
Bis
VI
numérotation particulière
sans Bis.
Ah, j'allais oublier quelque chose de
très important. Pour éviter d'avoir
des pics montagneux en très grand nombre ce qui donnerait
une surface peu
harmonieuse, il faut que la variation d'altitude (donc en fait le nombre
Gaussian que l'on ajoute) soit multipliée par un facteur qui
diminue deux fois
par cycle. On demande la déviation standard initiale, qui
est en fait le
facteur de départ (2 est largement suffisant pour 4 ou 5
cycles). Deux fois par
cycle, on modifie ce facteur selon la formule :
delta = delta * (0.5)^(0.5*H), ou H est
donné et correspond à D = 3 - H
(Souvenez vous de la dimension fractale). Si H est proche de 1, on
obtient D
proche de 2 , et l'on obtient une surface fractale assez plate.
La taille de la grille est
déterminée par le nombre N de cycles
souhaité.
Elle est de 2^ N +1 , le +1 étant présent pour
des nécéssités d'affichage.
C'est-à-dire que l'on arrive à une grille de 33 *
33 pour N=5 (multipliez par 4
pour avoir la taille en mémoire, car ce sont des
réels). Un cycle de calcul tel
que le fait le programme MIDPOINT est décomposé
comme suit (après avoir
initialisé les quatre coins) :
- Calcul de delta
- Calcul des milieux diagonaux
- Calcul de delta
- Calcul de milieux de bordure
- Calcul des milieux verticaux et horizontaux (Si l'on n'est
pas au premier
cycle).
De plus, il a été
rajouté au programme une option qui modifie encore une
fois les altitudes 'aléatoirement' (Addition à 0
ou 1).
On obtient en fin de calcul une grille de taille
(2^N +1)^2 dans laquelle
se trouvent stockées en fonction de coordonnées X
et Y des altitudes. Nous
aborderons le mode de representation avec parties cachées
dans le chapitre
'Compléments Graphiques'.
Dans le prochain chapitre, je vais mettre en place
quelques compléments
mathématiques extrèmement importants pour la
suite : ce sont les Complexes.
Ceux qui les connaissent bien peuvent sauter le chapitre et passer
directement
au chapitre IV.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Explications: partie 3.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Part III : Compléments mathématiques
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Et oui, je n'y peux rien, mais je suis
obligé de passez par là, sinon vous
allez rien comprendre à ce qui suit. Première
question : Qu'est ce qu'un
Complexe? En fait, c'est très simple : imaginez le nombre
-1. Ce nombre n'a pas
de racine carrée dans les réels (puisque une
racine est toujours positive).
C'est pourquoi on a été amené
à définir un ensemble, appelé ensemble
des
Complexes, où l'équation x^2=-1 avait une
solution. On appelle i tel que
i^2=-1. On ne cherche pas à calculer ce nombre (J'insiste),
mais il
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
sert à la définition des nombres complexes. Un
nombre complexe est alors défini
comme suit :
z = a + bi , où a et b sont des
réels, et a représente la partie
réelle et b
la partie imaginaire (i est défini
précédemment). On voit alors que tous les
nombres dont la partie imaginaire est nulle sont en fait des
réels. L'ensemble
des réels est inclus dans l'ensemble des Complexes.
Gràce à cet ensemble, on
peut calculer des 'racines' carrées négatives.
Pour ce faire, on introduit une
deuxième notation : comme un Complexe est
représenté par deux réels a et b, on
peut représenter ce Complexe dans un plan
rapporté à un repère avec a et b
comme coordonnées (Par exemple, le Complexe z = 2 + i est
représenté dans le
plan par le point de coord. (2,1) ). Inversement, à tout
point du plan on peut
associer un nombre complexe appelé 'affixe' du point. C'est
là que les choses
se corsent. Imaginez un trait reliant l'origine du repère
(origine que l'on va
dorénavant appeler O ) au point M d'affixe z. Ce point peut
aussi ètre défini
autrement qu'avec les coordonnées, gràce
à la représentation polaire. On
appelle Theta l'angle (orienté) entre l'axe des abscisses et
le segment OM et r
la distance OM. Alors z s'écrit sous la forme :
z = r * EXP (i*Theta)
ce qui est égal à z = r*(Cos (Theta) + i*sin
(Theta)).
On appelle la première notation 'forme
trigonométrique' et la deuxième
notation (sous forme de somme d'un nombre réel et d'un
nombre imaginaire)
'forme algébrique'. On voit d'autre part que a = r * Cos
(Theta) et b = r * Sin
(Theta). On passe donc très facilement de la
première à la seconde. Pour
obtenir Theta et r à partir de a et b, on applique les
formules suivantes :
r = SQR (a^2 + b^2) ( r est positif )
°°°°°°°°°°°°°
Si a
est différent de 0 et positif, alors Theta = ARCTAN (b/a).
Si a=0, alors Theta=PI/2.
Si a
est différent de 0 et négatif, alors Theta = Pi +
ARCTAN
(b/a)
L'avantage de la formule
trigonométrique est énorme : Moivre a
démontré
cette formule :
Soient z = r * EXP (i*Theta) et n
élément des réels, on a
z^n = r^n * EXP (i*Theta*n)
Or on sait que SQR (S) = S^0.5. On tire donc
Racine de z = SQR (z) * EXP (i*Theta/2).
On définit d'autre part le
'conjuqué de z' (noté z avec une barre au dessus,
mais en texte, c'est assez balaise, donc je le noterai Z).
z = a + bi = r * EXP (i*Theta)
Z = a - bi = r * EXP (-i*Theta)
On voit alors bien que z + Z = 2a, qui est un
nombre réel (Vous verrez,
c'est très important pour la suite).
Autre chose : Elevons au carré le
nombre complexe z=a+bi.
z^2 = (a+bi)^2 = a^2 + i^2* b^2 + 2abi.
Or i^2=-1.
Donc z^2 = a^2 - b^2 + 2ab.
Si on pose Z = A + Bi = z^2, on obtient finalement
A = a^2 -
b^2
B = 2ab
Ceci sert essentiellement dans le calcul de
l'ensemble de Mandelbrot ou des
ensembles de Julia.
Bien, je crois que je n'ai rien oublié
d'essentiel pour l'utilisation des
Complexes dans les fractales, et on va maintenant pouvoir passer
à la suite.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Explications: partie 4.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
PART IV : Surfaces fractales via les séries de Fourier
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Accrochez-vous à vos baskets,
ça se complique sérieusement. Vous savez qu'il
existe des fonctions dans les réels (j'espère que
vous savez ça, parce que
sinon, vous ètes mal barré). Bien, jusque
là, pas de problème. Maintenant, les
physiciens se sont heurtés à un
problème de taille : imaginez une courbe sur un
oscilloscope représentant la variation d'un courant
électrique. Si ce courant
est alternatif, no problem, on obtient une sinusoide. Mais si plusieurs
sources
sont mixées, on obtient une courbe qui si elle
présente de nombreuses
similitudes avec une sinusoide, n'en est pas une. Le probleme est :
comment
écrire cette fonction sous une forme simple? (Dans le genre
y=3x+2...un peu
plus compliqué quand mème!!) C'est là
où intervient Fourier : celui-ci a
démontré au début du siècle
que toute fonction 'continue' (référez vous
à votre
bouquin de maths) et périodique (il y d'autres conditions,
mais je saute...)
pouvait s'écrire sous la forme d'une somme de cosinus et de
sinus affectés de
certains coefficients. Ceci donne, sous la forme complexe :
N-1
X (t) = Sigma a(k)
* exp (2*pi*kt*i)
k=0
avec a(k) complexe.
Sigma désigne la somme du
terme suivant en fonction de k de 0 à N-1.
Ceci nous donne la fonction réelle,
dans le plan. Mais certains me diront
que le terme à droite du Sigma (que je noterai
dorénavant K) est complexe. En
fait non, car n'oubliez pas que les coefficients a(k)
répondent à certains
critères. Souvenez vous, qu'un complexe plus son
conjugué donne un réel. Les
coefficients vérifient donc
a(k)=A(N-k) , où A(N-k)
représente le conjugué de a(N-k). Il y a une autre
condition, que voici :
Le module M de a(k) doit vérifier M
voisin de 1/(k^(Beta/2)) , où Beta
détermine la dimension fractale (1<Beta<3).
La méthode consiste donc tout
simplement à choisir les coefficients
aléatoirement en respectant ces règles, et de
transformer sous forme réelle.
Développons X(t) sous forme
algébrique :
X(t) = Sigma (A+Bi)(Cos(2*pi*k*t) + i*Sin(2*pi*k*t))
On note dorénavant Th=2*pi*k*t
X(t) = Sigma (A+Bi)(Cos(Th)+i*Sin(Th))
= Sigma
(A*Cos(Th)+i*A*Sin(Th)+B*i*Cos(Th)+B*i*i*Sin (Th))
= Sigma
(A*Cos(Th)-B*Sin(Th) +i ( A*Sin(Th) + B*Cos(Th) ))
Comme les coefficients pour k> N/2 sont les
conjugués, dans la somme, on
peut démontrer que les parties imaginaires s'annulent
(N'essayez pas, j'ai pas
trouvé, et mon prof de maths non plus), et on obtient
finalement une fonction
réelle.
En formule finale, on obtient :
N/2
X(t) = Sigma (A(k)*Cos (kt) + B(k)*Sin
(kt))
k=1
avec A et
B parties imaginaires des coefficients a(k).
On notera que t doit varier entre 0 et 2*Pi
puisque la fonction est
périodique. Supposons que l'on doive établir la
courbe pour 280 points. t ne
peut pas varier entre 0 et 280 sinon on aurait une courbe
périodique de
période... 3 pixels !! (c'est-à-dire qu'au bout
de 3 pixels la courbe se répète
identique à elle mème.). Pour éviter
ceci, il suffit d'appliquer la formule
avec
t'=t +
2*Pi/N
où N est
égal à 280 dans ce cas, et t la valeur
précédente de t. t' devient la nouvelle valeur de
t qui sera utilisée pour le
prochain calcul (J'espère que vous avez compris, parce que
à expliquer, c'est
coton..).
Ceci nous donne une courbe à deux
dimensions. Mais on peut généraliser à
trois dimensions avec la formule suivante :
N-1 N-1
X(x,y)= Sigma Sigma a(k,l)*EXP (2*Pi(kx+ly))
k=0 l=0
Je vous laisse le soin de développer
tout ça (j'en ai marre de ce truc,
moi...). Je vous ai pondu un programme qui fonctionne, avec tous les
commentaires, alors m'emmerdez pas... (Les coefficients doivent aussi
répondre
à certains critères, qui sont d'ailleurs les
mèmes que précédemment).
Restons polis.
L'intérèt de cette
méthode, qui est
bien plus compliquée que la précédente,
est le suivant : supposons que vous calculiez 64 coefficients. Pour
afficher
votre surface, vous n'en utilisez au début que 0, puis 4,
puis 8, puis autant
que vous voulez. Que va t-il se passer? On aura d'abord une surface
plane,
puis une colline surgira, qui se transformera peu à peu en
montagne (vous
n'avez qu'à imaginer le processus inverse de
l'érosion). Si le programme est
assez rapide, vous pouvez ainsi obtenir une animation assez giga...
De plus, avec peu de coefficients, on obtient des
surfaces assez
harmonieuses qui rappellent irrésistiblement... Non, vous
verrez par vous mème,
sinon Florence va encore venir m'em...bèter en disant que je
ne pense qu'à ça,
ce qui n'est par ailleurs pas si faux.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Explications: partie 5.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
PART V : Introduction aux ensembles de Julia
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Qu'est ce qu'on se marre, hein?
Je précise que Julia n'est
pas une fille, mais une homme dont le nom était
Gaston Julia. Et oui, on choisit pas toujours son nom.
Bon, on repart. On aborde maintenant ce
que l'on appelle les fractales
calculées, qui sont fixes pour une zone donnée.
Ces fractales sont à priori
dans le plan, mais on verra qu'il existe un moyen de les transformer de
façon à
les afficher dans l'espace et en 3D (Sauf que cela ne rend qu'en
couleurs, et
avec 140*192 points en DHGR, on ira pas très loin. Mais ceux
qui ont un IIGS
vont pouvoir se régaler...).
On va devoir maintenant aborder la notion de
Chaos. Imaginez la suite
définie par
u(n+1) = (u(n))^2
Etudions le comportement de cette suite pour différentes
valeurs u(0).
- Si u(0)=1, pas de problème, quelque
soit n, u(n)=1.
- Si u(0)<1, alors la suite converge vers 0.
- Si u(0)>1, alors la suite tend vers
l'infini.
Etendons maintenant ceci à une suite complexe
défini comme suit:
z(n+1) = (z(n))^2 , où z(n) est un
complexe.
Si on représente z par le point M tel que z soit l'affixe de
M, étudions de
mème cette suite pour différentes valeurs de z(0)
(On posera z(0) = a+bi).
- Si le module de z(0) (qui est égal, rappelons
le à SQR(a^2+b^2)) est
inférieur à 1, le point M(n) tend vers l'origine
du repère.
- Si le module est supérieur à 1, le
point M(n) s'éloigne indéfiniment de
l'origine (on dit qu'il s'échappe).
- Si le module est égal à 1, le point
M(n) reste à une distance constante de
l'origine, distance qui vaut 1, c'est-à-dire que le point
M(n) appartient au
cercle unité.
Et bien ce cercle unité
représente l'ensemble chaotique de la fonction
F(z)=z^2. Pourquoi chaotique? Car il est instable. Mais pourquoi
instable? Car
après tout, on sait exactement ce qui se passe. Si le module
de z(0) est égal à
1, le point M(n) reste sur le cercle. Mais supposez que vous fassiez
une légère
erreur d'entrée, et que le module de z(0) soit
très proche de 1, mais pas tout
à fait égal à 1. Dans ce cas, soit le
point s'échappe, soit il se rapproche de
l'origine. C'est pourquoi le cercle unité est ditt instable.
Ce cercle unité est l'ensemble de Julia
pour la fonction F(z)=z^2. D'une
manière purement mathématique, en supposant que
l'on n'ait pas connu le
résultat, on voit bien que pour trouver ce cercle, il aurait
fallu pour une
valeur quelconque, prendre la racine du complexe z un grand nombre de
fois
(Référez vous au chapitre III). Exemple :
J'opère dans les réels pour
des raisons de commodités, mais le résultat est
le mème dans les complexes.
z = 50
z1 = 7.07
z2 = 2.659
z3 = 1.63
z4 = 1.27
z5 = 1.13
z6 = 1.06
etc...
On voit bien que la suite tend vers 1.
On peut ainsi représenter l'ensemble de
Julia pour n'importe quelle fonction
F(z)=z^2 + c , où c désigne bien naturellement un
complexe.
Pour trouver cet ensemble, il suffit de
procéder de la mème manière que
précédemment, à savoir on
résoud l'équation Z=z^2+c (dans le cas du cercle
du
paragraphe précédent, c=0, et on
résolvait Z=z^2, soit z=+ ou - SQR (z)) en
exprimant z en fonction de Z.
On obtient alors
z = SQR (z-c) où z
= - SQR (z-c)
On choisit une des deux racines
aléatoirement, et on recommence en prenant
pour Z la nouvelle valeur.
Ceci nous donne alors le petit programme suivant :
10 INPUT "CX,CY ";CX,CY On
demande la partie réelle et imaginaire de c
20 INPUT
"X,Y";X,Y
On demande le premier point (partie relle et ima)
30 FOR I=1 TO 6000
40
WX=X-CX
On calcule la partie réelle (WX) et la partie ima
50
WY=Y-CY
(WY) de z-c.
60 IF WX>0 THEN
theta=ATN(WY/WX)
On exprime z-c sous forme
70 IF WX<0 THEN theta=3.14159 + ATN
(WY/WX)
trigonométrique.
80 IF WX=0 THEN THETA=1.57079
90
Theta=Theta/2
On applique la formule de Moivre avec n=1/2
100
R=SQR(WX*WX+WY*WY)
On calcule le module de z-c
110 IF RND<0.5 THEN R=SQR(R):GOTO
120 On choisit une des deux racines
115
R=-SQR(R)
aléatoirement.
120
X=R*COS(Theta)
On calcule les coordonnées du point en
130
Y=R*SIN(Theta)
fonction de Theta (Ce qui revient à passer
de la forme trigo. à la forme algébrique )
140 HPLOT
X*10+140,Y*10+90
Et on affiche en centrant et en agrandissant
150 NEXT
I
Et zou, c'est reparti
Voilà. Clair, net et précis.
Cependant, si cette méthode est simple, elle
n'est pas très performante. En effet, au bout d'un certain
nombre d'itérations,
on retombe sur des racines déja obtenues. Certains points
sont ainsi plusieurs
fois affichés alors que d'autres le sont très
rarement (la densité de
distribution est très variable). Un truc pour
accelérer tout ça, est de tester
si le point choisi est déja allumé. Si oui, on
choisit l'autre point. Pour ce
faire, mon programme utilise la routine DETER qui détermine
si un point est
allumé ou éteint (routine écrite par
mon très estimé confrère Oliver Twist).
C'est loin d'ètre parfait, mais ça fonctionne.
Une autre méthode consiste à
tester tous les points de l'écran, en les
itérant plusieurs fois selon la formule
X = a^2 - b^2 + CX
Y = 2ab + CY
(on calcule en fait le terme z(n), avec z(n+1) = (z(n))^2 + c, z(0)
étant
l'affixe du point à tester).
En effet, si ce point reste pour un grand nombre
d'itérations (en pratique 30
est largement suffisant) à l'intérieur d'un
disque de rayon 3 (il suffit de
tester le module), alors il se trouve à
l'intérieur de l'ensemble de Julia (ce
qui ne veut pas dire qu'il appartient à cet ensemble).
Il existe d'autres méthodes, mais qui
sont un peu plus complexes, et surtout
qui sont pratiquement les mèmes pour l'ensemble de
Mandelbrot. Rendez-vous donc
au chapitre VI.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Explications: partie 6.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
PART VI : Ensembles de Mandelbrot et de Julia
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
L'ensemble de Mandelbrot est un truc super. La
bordure de cet ensemble est
d'une richesse inouie. Agrandissez n'importe quelle zone de la bordure
et vous
aurez des dessins absolument magnifiques.
Cet ensemble est défini comme suit :
On considère la suite complexe z(n+1)=z(n)^2 + c. La
différence avec les
ensembles de Julia est que cette fois z(0)=0, et que c
représente l'affixe du
point à tester. D'autre part, le processus
d'itération est différent. En effet,
on ne peut pas rechercher les racines successives. Plusieurs
algorithmes sont
possibles. Ces algorithmes sont aussi valables pour les ensembles de
Julia,
mais la valeur maximale (vous comprendrez plus loin) doit
ètre égale à 3 et non
pas à 10000 (N'oubliez pas de changez le programme, de
façon que c soit fixé
pour un ensemble de Julia donné, et que soit z(0) qui
représente l'affixe du
point à tester).
Je rappelle que l'affixe d'un point sont ses
coordonnées écrites sous forme
complexe ( Soit M de coord. X et Y, son affixe est alors z = X + Y*i ).
Premier Algorithme : On scanne l'écran pour trouver les
points appartenant à
°°°°°°°°°°°°°°°°°°°
l'ensemble. C'est-à-dire que l'on itère plusieurs
fois la fonction
F(z) = z^2 + c. Si à un moment quelconque, le
module de Z est supérieur à
10000, alors on peut prouver que ce point n'appartient pas à
l'ensemble de
Mandelbrot, auquel cas on ne l'affiche pas. Cette méthode
présente toutefois un
inconvénient : pour avoir une belle image, un
très grand nombre d'itérations
est nécessaire (30 environ pour l'ensemble vu en entier - En
effet, plus on
agrandit, et donc plus on se rapproche de l'ensemble, plus les points
s'échappent lentement, c'est-à-dire que le nombre
d'itérations nécessaire
augmente de façon dramatique - ), ce qui est plutot lent. De
toutes façons,
tous les algorithmes sont lents, alors.
Deuxieme algorithme : Cet algorithme est dérivé
du précédent. En fait, on
°°°°°°°°°°°°°°°°°°°°
constate que plus un point est loin de l'ensemble de Mandelbrot, plus il
s'échappe vite (Par exemple, il peut s'échapper
à la première itération),
tandis que les points proches s'échappent beaucoup plus
lentement. On peut
définir alors une valeur k qui représente le
nombre d'itérations nécessaire
pour que le point s'échappe. N'oubliez cependant pas que si
un point appartient
à l'ensemble, il ne s'échappe jamais. Il faut
donc définir une valeur maximale
de k pour laquelle le programme considère que le point
appartient à l'ensemble.
Cet algorithme donne de magnifiques résultats, car il suffit
de représenter
tous les points dont la vitesse d'échappement est paire,
où impaire, au choix,
pour obtenir des 'courbes de niveau'. Si on dispose de la
couleur, on peut
affecter une couleur à une valeur d'échappement,
ce qui donne des résultats
très intéressants. Pratiquement toutes les images
de l'ensemble de Mandelbrot
données en exemple dans ce cours ont
été obtenues de cette manière. Les
dessins
sont plus beaux que ceux obtenus avec l'algorithme
précédent, car la présence
des courbes de niveau 'noye' un peu la bordure de l'ensemble, et donc
on voit
moins les défauts de l'image pour un mème nombre
d'itérations (15 environ pour
une vue complète) par rapport au premier algorithme. Je l'ai
programmé en
assembleur (Et oui! Je me suis quand mème un peu
cassé), mais le résultat au
point de vue vitesse n'est pas très probant (et pour cause,
car on utilise en
permanence des routines de l'interpréteur puisqu'on manipule
des réels, ce qui
est obligatoirement plutot lent) : on obtient environ un facteur 2 par
rapport
au Basic compilé (Remarquez que le programme est surement
améliorable : que
ceux qui en ont le courage et qui arrive à obtenir une image
gràce à leur
programme en moins de 15 minutes m'en informent tout de suite. Ils
auront
gagné... ma reconnaissance éternelle - Note : les
images doivent ètre en 280 *
192, et doivent ètre calculées sur un IIe ou IIc
sans carte accélératrice, non
mais, pour pas que les GS'maniaques viennent m'emmerder avec leur 2,8
Mhz).
D'autre part, comme on obtient des entiers, à la sortie, il
est très beau de
calculer en 3D tout ce bazar. Je vous donne le programme BASIC
commenté, en
plus (Bon sang, qu'est ce qu'elle est mignonne Florence) :
10 INPUT "NX,NY
";NX,NY
; Résolution en X et Y
20 INPUT "XMIN,XMAX
";XIN,XAX ; XAX et
XIN car AppleSoft confond les
30 INPUT "YMIN,YMAX
";YIN,YAX ; variables
dont les deux premières
; lettres sont semblables.
35 INPUT "MAXITER ";MAXITER
40 FOR IY=0 TO NY-1
50 CY=YIN + IY*(YAX-YIN)/(NY-1) ; Calcul
de CY en fonction des bornes, du
; pixel à tester et de la résolution.
60 FOR IX=0 TO NX-1
70 CX=XIN + IX*(XAX-XIN)/(NX-1)
80 GOSUB
1000
; Appel de la sous-routine
90 IF INT(ITER/2)=ITER/2 THEN HPLOT IX,IY ; Si ITER
est pair, on affiche
100 NEXT IX
110 NEXT IY
1000
X=0:Y=0:X2=0:Y2=0:ITER=0
; Initialisation
1010 IF ITER>MAXITER OR X2+Y2>10000 THEN 1100
1020
TEMP=X2-Y2+CX
; On itère une fois. Référez vous au
1030
Y=2*X*Y+CY
; chapitre sur les complexes.
1040 X=TEMP
1050
X2=X*X
; On calcule X^2 et Y^2 qui sera utilisé
1060
Y2=Y*Y
; dans le prochain calcul.
1070 ITER=ITER+1
1080 GOTO 1010
1100
RETURN
; Et hop ! Retour
Ce programme n'est ici que pour bien vous expliquer l'algorithme. Une
version
assembleur se trouve sur la disquette.
Troisième algorithme : Une autre méthode,
très utilisée pour afficher
°°°°°°°°°°°°°°°°°°°°°
l'ensemble en 3D, est celle qui utilise les potentiels. Chaque point du
plan
peut ètre affecté d'un potentiel qui varie
suivant sa distance par rapport
l'ensemble. On procède de la mème
manière que précédemment, et si le
point
s'échappe, alors on calcule son potentiel suivant la formule
:
Pot = (LOG (Module de
z(n)))/(2^n)
où n représente le nombre d'itérations
nécessaire pour que le point s'échappe.
Je dois avouer que je n'ai pas testé cet algorithme, car il
ne rend rien en 2D,
et la résolution de l'Apple est insuffisante pour rendre
quelque chose en 3D,
en grande partie à cause du fait que le potentiel est un
nombre réel
extrèmement petit, ce qui donne des résultats
bizarres (N'oublions pas que
l'utilisation de la couleur est indispensable pour voir quelque chose.
Sinon,
vous obtenez un écran...blanc).
Quatrième algorithme : On aborde ici un algorithme
très intéressant, mais
°°°°°°°°°°°°°°°°°°°°
°°°°
assez difficile à mettre en place. Cet algorithme consiste
à calculer la
distance du point à tester par rapport à
l'ensemble. Pour ce faire, toujours la
mème chose, on itère, mais cette fois on sauve
les coordonnées (qu'on appelle
orbite) dans une table. Dans le cas où le point
s'échappe (pour un nombre
d'itération égal à n), on calcule la
distance selon la formule :
Dist = (2 * (Module de z(n)) *LOG
(Module de z(n)))/(Module de z'(n))
Ici, z'(n) représente le complexe
dérivé de z(n). Je ne peux pas
développer ici
la notion de dérivée, mais voici au moins la
formule qui permet de calculer ce
complexe dérivé :
On applique la suite définie par :
z'(k+1) = 2*z(k)*z'(k) , avec z'(0)=0
On itère jusqu'à k = n - 1 (Pas plus !!! Sinon,
vous obtiendrez des résultats
très bizarres). Je vous laisse calculer les formules en
fonction des
coordonnées (n'oubliez pas que l'on a affaire à
des complexes), de toutes
façons, tout est indiqué dans mon programme.
Note très importante: Dans le programme, on a
Dist= Log ( X2+Y2 ) etc...
et non pas Dist= 2*Log (SQR(X2+Y2))
etc...
(le module de z(n) est égal à
SQR(X*X+Y*Y)=SQR(X2+Y2)).
Ceci pour une excellente raison, qui découle de l'une des
propriétés du
logarithme, à savoir :
Log(x^n)=n*Log(x). Attention donc !
Mais pourquoi cet algorithme est-il
intéressant, car en fait il est plus
lent que le précédent : Et ben non, justement!!
(Vais-je vous dire pourquoi?
Je me tate, j'en sais trop rien, ca dépendra de vous, et de
bien d'autres
choses, en particulier de la date à laquelle je pourrai me
taper Florence, euh
là je dévie. Reprenons). Car en fait cet
algorithme permet de calculer la
distance minimale du point à l'ensemble, ce qui nous permet
donc de tracer un
disque plein (plus exactement une ellipse puisque l'écran
n'est pas carré) dans
lequel aucun des points n'appartiennent à l'ensemble. Ces
points n'ont donc pas
besoin d'ètre testés, ce qui économise
pas mal de calculs. Pour obtenir cette
distance minimale, il suffit de diviser la distance obtenue par la
formule
précédente par 4. Si cette distance est
inférieure à une valeur fixée
à
l'avance, on n'affiche pas. Si elle est inférieure
à un pixel, on se casse pas
la tète, on affiche un point. Sinon,et zou c'est parti pour
le tracé de
l'ellipse. Mais me direz-vous, comment tracer une ellipse? Et bien
là, vous
vous démmerdez, non mais, faut pas abuser. C'est
relativement facile quand on a
un minimum de connaissances en assembleur (j'ai juste eu la flemme de
programmer la routine. No comment ...).
En tout cas, ce truc est assez giga. Je
précise que j'utilise tout
naturellement pour tester l'état du point la routine DETER,
écrite par mon très
éstimé (je me répète)
,honorable, intelligent, et o combien rapide confrère
Oliver Twist (Rayez les mentions inutiles, c'est à dire -
God pardon me - à mon
sens presque toutes... Non, là, je délire -
quoique, comme dirait Devos..-).
Avouez que c'est boooo, quand mème.
Pour afficher tout ces trucs en 3D,
reportez vous au chapitre intitulé 'Compléments
graphiques'.
Very, very important note : là, j'ai un
gros problème avec les ensembles de
Julia. En effet, prenons pour valeur particulière c=0. Si on
applique
strictement les algorithmes, on trouvera que tous les points
à l'intérieur du
cercle unité ne s'échappent jamais (logique...).
Le problème est : l'ensemble
de Julia, c'est uniquement la bordure, qui peut ètre
très complexe dans
certains cas. Or si on affiche tous les points ne
s'échappant pas, on obtient
une surface pleine au lieu des magnifiques dessins que l'on se serait
attendu à
trouver. Si quelqu'un me résoud ce problème,
qu'il me contacte immédiatement
sur RTEL, Bal : PERFECT BUGS, j'en serai ravi.
Et bien, nous voilà presque
arrivé au bout. Encore un petit chapitre sur les
méthodes d'affichages en 3D, et on aura bouclé la
boucle.
See you on the next Part....
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Compléments graphiques.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Compléments graphiques
(Oh combien indispensable....)
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Bon, là, on quitte les fractales pour
aborder la géométrie dans l'espace,
qui vous sera indispensable pour obtenir de boooo dessins. En fait,
comme vous
allez le voir, c'est très simple, du moment que vous ne
voulez pas démontrer
les formules. Pour afficher une surface fractale en 3D, deux
méthodes de
projection sont possibles :
- La première qui consiste à calculer
à partir des coordonnées d'un point dans
l'espace ses coordonnées sur l'écran en utilisant
pour cela une perspective
cavalière. Voici les formules pour un point de
coordonnées X,Y,Z avec U et V
les coordonnées du point à l'écran :
U = X + K * Y * Cos (Th)
V = Z + K * Y * Sin (Th)
où K est le coefficient de réduction et
Th l'angle de vue (avec un angle égal
à 0 ou à Pi/2, vous ne verrez bien entendu rien
du tout).
Ca marche très bien quand vous avez une fractale
dont les points sont cote à
cote (exemple : Mon superbe ensemble de Mandelbrot en 3D), car pour las
parties
cachées, il suffit de partir de la ligne la plus
éloignée par rapport à
l'observateur, les lignes suivantes effacant automatiquement les parties
cachées. En revanche, ça foire pour les surfaces
fractales (montagnes and co.),
car il est bien évident que pour des raisons de place
mémoire, on ne peut pas
avoir une grille énorme (en fait : Supposons que la
mémoire de $4000 à $9600
soit libre, ce qui fait 22016 octets, soit assez de place pour 5500
réels à peu
près, ce qui donne au maximum une grille de 74 sur 74, et
encore, car il ne
faut pas oublier que le programme utilise aussi des variables, et que
d'autre
part l'on est obligé d'utiliser la DHGR pour obtenir des
dessins potables). La
solution consiste alors à définir ce que l'on
appelle un réseau, qui relie les
points entre eux par des traits. Pour les parties cachées
par contre, bingo.
Heureusement, ne reculant devant aucun sacrifice (et avec
l'aide et le soutien
moral de Florence), j'ai élaboré un algorithme
dont je suis assez fier :
imaginez que cette fois vous partiez de la ligne de points qui est la
plus
proche de l'observateur (c'est-à-dire celle qui est en bas
de l'écran). Vous
l'affichez en reliant les point M1(i,j,z(i,i)) avec les points
M2(i+1,j,z(i+1,j)) et M3(i,j+1,z(i,j+1)). Toute cette ligne est
visible. Les
points qui constituent la ligne suivante (tous les pixels, pas
seulement les
points de la grille dimensionnée) ne sont visibles que s'ils
se trouvent au-
dessus des points de la ligne précédente, et
ainsi de suite. En fait, on
initialise une ligne de crète et l'on
décrète que des points ne sont visibles
que s'ils sont au-dessus de cette ligne de crète
(ça fait beaucoup de crète,
ça...). Comprendo? Sinon, je n'y peux rien, j'ai fait tout
mon possible. Bon,
pour faire tout ça, il est bien évident que l'on
doit reprogrammer entièrement
la routine de Line de l'Apple, où alors la recopier quelque
part en mémoire et
la détourner. Quand à moi, j'ai repris la routine
de ligne en DHGR écrite par
The Last Jedi (qui fait o surprise partie de The $FF59 Connection) et
à chaque
affichage de point, je teste ses coordonnées, à
savoir je compare son abscisse
à une table quelque part en mémoire, table de 560
octets qui contient la ligne
de crète. Si l'ordonnée est inférieure
à celle pointée par la table (n'oubliez
pas que le point 0,0 est en haut à gauche sur l'Apple), on
affiche le point et
on remet la table à jour. Sinon, on affiche pas et on
continue.
Attention cependant : Vous devez toujours faire en
sorte que les droites
tracer soient tracer de bas en haut. Pourquoi? En voici la
raison :
imaginez que l'on trace de haut en bas et que les points soient
à des altitudes
très différentes mais des abscisses proches.
Voici ce qui va se passer : le +
représente le point de départ, le o le point
d'arrivée.
+
+
.
Car au moment d'afficher le
deuxième point
.
au lieu
de
... qui est visible,
l'ordinateur le considère
. comme invisible
puisque il est en
dessous
o
o du point
précédent, ce qui
à réinitialisé
la ligne de crète. Il faut donc afficher dans
l'autre sens. Un bète test d'altitude entre le point
d'arrivée et le point de
départ permet d'y remédier. Le programme MIDPOINT
utilise la routine DHGR3 qui
est la version modifiée de DHGR, permettant ainsi
l'affichage des parties
cachées. D'autre part, ce programme se livre aussi
à une modification des
échelles. En effet, les variations d'altitude sont infimes,
et pour voir
quelque chose, il faut en conséquence multiplier les
altitudes par un nombre
donné, ce nombre étant calculé par mon
programme de façon à ce que l'image
tienne entièrement à l'écran.
- D'autres formules de projection donnent :
U = X
V = Y * Sin (Th) + Z * Cos (Th)
Appliquez les mèmes règles
que ci-dessus.
Bien, on continue. Dans mon infini
bonté (ça prend un 'e' je crois infini
?), je vous ai flanqué sur la seconde façe
l'interpréteur Arlequin (DHGR), et
comme je suis bon (si,si, je suis bon), je vous file la plupart des
ordres
disponibles. Here we go :
&BACK
(C)
Couleur fixée à C
&BOX (G,D,B,H) Remplit un
rectangle de point supérieur gauche G,D et de
point inférieur droit B,H dans la couleur de fond.
&COL
(C)
Fixe la couleur du crayon
&DISPLAY (V)
Affiche une page selon la valeur de V :
0 : TEXT Page 1
1 : DHGR Monochrome
2 : DHGR Couleur
3 : Affichage mixte
&DOT
(X,Y)
Trace un point aux coordonnées X et Y.
&FILL (C1,C2,C3,C4) Remplit la surface à la position
courante du curseur dans
la couleur composée des quatre couleurs C1 etc...
&LINE (XD,YD,XB,YB) J'espere que vous comprenez,
là...
&LOAD (X,Y,pathname) Charge l'image aux coordonnées
X et Y (n'oubliez pas que
vous ètes en ProDos, d'où le pathname)
&MODE
(M)
Fixe le mode de travail, couleur ou monochrome (1=Mono,2=Cou)
&ON
Réinitialise le système Arlequin
&PIXEL (X,Y,C) Ramène
dans C la couleur du pixel X,Y
&POS
(X,Y)
Positionne le curseur à la position X,Y
&SAVE (pathname) Sauve l'image courante
&WINDOW (G,D,B,H,P) Définit une fenètre
selon le mème procédé que BOX. P est la
page graphique choisie (il ya deux pages DHGR sous Arlequin)
Voilà, je n'ai pas mis tous les ordres
car sinon on en aurait pour un
disquette entière pour tout expliquer.
Je connais la méthode pour reproduire
un survol de surfaces fractales (style
le survol de planètes dans l'Arche du Capitaine Blood), mais
faute de temps (et
oui, j'ai des cours, moi), je ne peux m'en occuper. Pour ceux que
ça interesse,
qu'il me contacte sur RTEL, Bal : PERFECT BUGS, et je leur
explicationnerai
(pas mal comme mot) le principe.
Ah, une derniere chose : Quand mes programmes FM2D
et MIDPOINT demandent la
dimension, il s'agit en fait de H, qui donne D=3-H. Donc ne vous
plantez pas...
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Retour sommaire
Contenu du disk.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Ce que vous trouverez sur ce disque
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Hormis les fichiers concernant les fractales, vous
trouverez :
Les programmes évoqués dans ce cours :
-
MIDPOINT
Surfaces fractales, par déplacement des milieux
-
FM2D
' ' ' ' ' '
, par Séries de
Fourier
-
OL-SYSTEM
Fractales auto-similaires
-
LSM.JULIA
Ensembles de Julia par algorithme II
-
LSM.MANDELBROT
' ' ' ' Mandelbrot
par algorithme II
-
LSM.ASS
' ' ' ' ' '
' ' en
assembleur.
et des routines :
-
DHGR
Routines de double haute résolution
-
DHGR3
Routines de DHGR modifiées
Je remercie toute la classe de TC2 pour le magnifique
bouquin qui m'a permis
en grande partie de pondre tout ça, et plus
particulièrement Florence et Ariane
que j'embrasse joyeusement (elles le font moins joyeusement, il est
vrai, mais
enfin...).
Ceci étant dit, bonne chance avec les
fractales, et si vous avez un problème
de compréhension, n'hésitez pas à me
contacter sur RTEL, Bal: PERFECT BUGS
(Note: les délais peuvent ètre longs vu que je
n'ai pas de Minitel, donc pas
d'impatience).
Ah, d'autre part, je recherche FRACTAL EXPLORER,
version Apple IIc.
Bye !!
+---------------+ Perfect Bugs +--------------+ The Last Jedi
+---------------+
/// from The $FF59 Connection. ///
+-----------------------------------------------------------------------------+
Retour sommaire