Additions à la bibliothèque
Le programme dans cet article a besoin de la souris.
J'ai modifié System.cpp pour gérer les évènements de souris de SDL.
Et j'ai ajouté ces variables à la classe CSystem:
// mouse buttons
#define BUT_LEFT (1 << 0)
#define BUT_RIGHT (1 << 1)
class CSystem
{
public:
[...]
Uint8 buttons; // true while a button is pressed
Uint8 buttonsDown; // true only at the frame the button is pressed
Uint8 buttonsUp; // true only at the frame the button is released
int mouseX;
int mouseY;
mouseX et mouseY contiennent les coordonnées de la souris en pixels.
buttons, buttonsDown et buttonsUp sont des champs de bits qui contiennent 1 bit pour chaque bouton.
Les 2 boutons qui sont gérés pour l'instant sont BUT_LEFT et BUT_RIGHT respectivement pour les boutons gauche et
droit de la souris.
Les bits dans button sont mis à 1 tant qu'un bouton est pressé.
Les bits dans buttonsDown sont mis à 1 juste pendant la frame où l'on appuie sur le bouton.
Les bits dans buttonsUp sont mis à 1 juste pendant la frame où l'on relâche le bouton.
Toutes ces variables sont mises à jour dans processEvents()
Vous verrez un exemple d'utilisation dans le programme.
Pour gérer les calculs sur le polynôme, on va écrire une classe Polynomial.
Cette classe va contenir un polynôme de la forme:
p(z) = c0*zn + c1*zn-1 + ... + cn-1*z + cn
Ainsi que ses racines.
Alors on va stocker une liste de coefficients et une liste de racines.
J'ai utilisé un std::vector que vous pouvez simplement voir comme un tableau illimité, où vous pouvez ajouter
autant d'éléments que vous voulez.
class Polynomial
{
private:
std::vector<Complex> coefficients;
public:
std::vector<Complex> roots;
Une fonction degree() va simplement renvoyer le degré du polynôme qui est le nombre de coefficients moins 1.
int Polynomial::degree()
{
return coefficients.size() - 1;
}
2 fonctions nous permettent d'ajouter une racine ou de retirer la dernière.
void Polynomial::addRoot(Complex r)
{
roots.push_back(r);
coefficients.resize(roots.size() + 1);
}
void Polynomial::remRoot()
{
roots.pop_back();
coefficients.resize(roots.size() + 1);
}
Une fonction nous permet d'évaluer la valeur du polynôme pour un z donné.
Ici on additionne simplement chaque puissance de z par son coefficient.
Complex Polynomial::evaluate(Complex z)
{
Complex result = Complex(0, 0);
Complex zn = Complex(1, 0);
for (int i = degree(); i >= 0; i--)
{
result = result + zn * coefficients[i];
zn = zn * z;
}
return result;
}
Le calcul de la dérivée est facile aussi.
On applique la règle classique qui dit que la dérivée de z
n est n*z
n-1
void Polynomial::derivative(Polynomial& result)
{
result.coefficients.clear();
for (int i = 0; i <= degree()-1; i++)
{
Complex coef = coefficients[i] * (degree() - i);
result.coefficients.push_back(coef);
}
}
L'autre fonction incluse dans la classe Polynomial est findCoefficients().
Elle est utilisée pour calculer les coefficients du polynôme à partir de ses racines.
Comme on l'a vu avant le polynôme a cette forme:
p(z) = c0*zn + c1*zn-1 + ... + cn-1*z + cn
Quand on connait ses racines, il peut être écrit sous une forme factorisée:
p(z) = (z - r0)(z - r1)...(z - rn-1)
Si on développe cette forme, voici ce qu'on trouve:
c0 = 1
c1 = (-r0) + (-r1) + ...
c2 = (-r0)*(-r1) + (-r0)*(-r2) + ... + (-r1)*(-r2) + (-r1)*(-r3) + ...
...
cn = (-r0)*(-r1)*(-r2)...
Chaque coefficient c
m est la somme de toutes les combinaisons de m racines prises parmi toutes les racines.
Pour calculer ça on va avoir besoin d'une liste d'index
std::vector<int> idx;
Chacun de ces index va représenter le numéro d'une racine.
Vous pouvez les voir comme des index de boucle.
Pour calculer c
1 on aura besoin d'1 index qui parcourera les racines de r
0 à r
n-1.
Pour c2 on va utiliser 2 index, chacun pointant sur une racine séparée, pour former tous les couples de racines
qu'on a besoin d'additionner ensemble.
Mais ces index vont suivre certaines contraintes.
D'abord on ne veut pas compter 2 fois la même combinaison. Par exemple on ne veut pas à la fois (-r
0)*(-r
1) et (-r
1)*(-r
0).
Les index doivent tous être différents aussi. On ne veut pas de (-r
0)*(-r
0).
Pour suivre ces règles, on va s'assurer qu'on a toujours:
idx[0] < idx[1] < ... < idx[n-1]
Pour respecter ça, au départ, on va les initialiser de façon à ce que chacun soit égal au précédent plus 1.
idx[0] = 0;
idx[1] = id[0] + 1;
idx[2] = id[1] + 1;
...
Les index n'iront pas tous jusqu'à n-1 non plus. Comme ils doivent être tous différents, ça implique que le dernier
ira jusqu'à n-1, le précédent n'ira que jusqu'à n-2, le précédent s'arrêtera à n-3, etc.
Pour incrémenter ces index, on va commencer par le dernier.
On va lui ajouter 1. Et s'il dépasse le nombre de racines, on va considérer le précédent.
On incrémente l'index précédent, et s'il dépasse le maximum, on continue à remonter jusqu'à ce qu'on atteigne un
index qui ne déborde pas.
Puis, après avoir augmenté cet index, on ré-initialise les suivants avec la règle qu'on a vue précédemment.
Voici un exemple avec 4 index et n racines.
Au départ on a:
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
idx[3] = 3;
On incrémente idx[3]. Il pointe maintenant sur la racine numéro 4:
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
idx[3] = 4;
Au tour suivant, on l'incrémente encore.
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
idx[3] = 5;
Et on continue jusqu'à ce qu'on atteigne n-1.
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
idx[3] = n-1;
Maintenant, si on l'incrémente, il sera à n, ce qui dépasse le nombre de racines.
idx[0] = 0;
idx[1] = 1;
idx[2] = 2;
idx[3] = n;
Alors on remonte d'un niveau et on incrémente idx[2].
idx[0] = 0;
idx[1] = 1;
idx[2] = 3;
idx[3] = n;
Puis on réinitialise idx[3] à idx[2] + 1:
idx[0] = 0;
idx[1] = 1;
idx[2] = 3;
idx[3] = 4;
Et on utilise cette configuration.
On continue jusqu'à ce qu'on atteigne cet état:
idx[0] = 0;
idx[1] = 1;
idx[2] = n-2;
idx[3] = n-1;
Maintenant, si on incrémente idx[3], il dépasse encore une fois son maximum:
idx[0] = 0;
idx[1] = 1;
idx[2] = n-2;
idx[3] = n;
Donc on remonte d'un niveau et on incrémente idx[2], mais il atteint aussi son maximum qui est n-1.
idx[0] = 0;
idx[1] = 1;
idx[2] = n-1;
idx[3] = n;
Alors on doit remonter d'un niveau de plus et incrémenter idx[1].
idx[0] = 0;
idx[1] = 2;
idx[2] = n-1;
idx[3] = n;
Puis on ré-initialise idx[2] et idx[3] et on continue le processus:
idx[0] = 0;
idx[1] = 2;
idx[2] = 3;
idx[3] = 4;
Implémentation de findCoefficients
On a déjà parlé de la liste d'index.
void Polynomial::findCoefficients()
{
std::vector<int> idx;
idx.resize(roots.size() + 1);
Le premier coefficient sera toujours 1.
coefficients[0] = 1;
Maintenant on va faire une boucle pour calculer chacun des autres coefficients:
j est une variable pratique qui sera utilisée comme compteur de boucle à différents endroits.
for (int i = 1; i <= degree(); i++)
{
coefficients[i] = Complex(0, 0);
int j;
On initialise les index. Remarquez que le nombre d'index dépend du numéro du coefficient qu'on calcule.
for (j = 0; j < i; j++)
idx[j] = j;
On démarre une boucle où on va calculer chaque terme du coefficient l'un après l'autre.
while(true)
{
On calcule le terme ici en multipliant toutes les racines qu'on a sélectionnées ensemble.
Complex c = Complex(1, 0);
for (j = 0; j < i; j++)
c = c * (-roots[idx[j]]);
Et on ajoute le terme au coefficient.
coefficients[i] = coefficients[i] + c;
Maintenant on va incrémenter les index en suivant nos règles pour obtenir la combinaison suivante.
j va représenter le "niveau" courant. Au départ il pointe sur le dernier index de notre liste.
j = i - 1;
On démarre une boucle parce qu'on va peut-être remonter de plusieurs niveaux avant de trouver un index qui ne
déborde pas.
while(true)
{
On essaye d'incrémenter l'index courant.
idx[j]++;
Si cet index a atteint sa limite, on monte d'un niveau.
A moins qu'on ne soit déjà au premier index, auquel cas on sort de la boucle.
if (idx[j] == roots.size() - ((i-1) - j))
{
j--;
if (j < 0)
break;
}
Si on n'a pas atteint de limite cet index a été incrémenté avec succès, alors on ré-initialise tous les index
suivants.
else
{
for (int k = j + 1; k < i; k++)
idx[k] = idx[k - 1] + 1;
break;
}
}
Si pendant qu'on remontait les niveaux on s'est retrouvé au-dessus du premier index, on sort de la boucle.
Et on retombe sur la boucle des coefficients où on va calculer le coefficient suivant.
if (j < 0)
break;
}
Pour être capable de voir le dessin de la fractale en temps réel, on va utiliser un motif de tramage comme on l'a
fait pour
l'ensemble de Mandelbrot.
La fonction de dessin va seulement afficher un point tous les 8 pixels dans les directions x et y:
void drawNewton(int offsetX, int offsetY, std::vector<Color>& palette)
{
for (int yy = 0; yy < SCREEN_HEIGHT; yy += 8)
{
for (int xx = 0; xx < SCREEN_WIDTH; xx += 8)
{
Le reste de la fonction est la même que la fonction de dessin qu'on a utilisé dans
l'article précédent.
Puis dans la boucle principale, on va appeler cette fonction avec un offset x/y venant d'une table pour modifier le
point de départ du dessin..
static Uint8 pattern[64] =
{
0, 36, 4, 32, 18, 54, 22, 50,
2, 38, 6, 34, 16, 52, 20, 48,
9, 45, 13, 41, 27, 63, 31, 59,
11, 47, 15, 43, 25, 61, 29, 57,
1, 37, 5, 33, 19, 55, 23, 51,
3, 39, 7, 35, 17, 53, 21, 49,
8, 44, 12, 40, 26, 62, 30, 58,
10, 46, 14, 42, 24, 60, 28, 56
};
[...]
while (sys.isQuitRequested() == false)
{
// draw the fractal
if (frameCount < 64)
{
drawNewton(pattern[frameCount] % 8,
pattern[frameCount] / 8,
palette);
frameCount++;
}
