fractales - Page 1

Bonjour!
Je fais des recherches sur les fractales en générale pour mes TIPE(il est temps que je m'y mette ) et il y a des programmes, comme "Pomme" qui sont réputés pour avoir de super performances. Sauf qu'après recherche, je ne trouve rien du tout à ce sujet. En fait, je ne trouve que des sources de programme qui calculent point par point est-ce que le point appartient à la fractale, ce qui est(d'après mon humble avis) pas du tout optimisé, puisque c'est la méthode la plus naturelle. En utilisant ce programme(ou d'autres comme "Fractal Forge"), j'ai l'impression que ça divise l'écran en zones rectangulaire et que ça avancerait en calculant quelquechose dans chacune de ces zones séparément. De plus, on ne peut pas zoomer autant qu'on veut: à un moment en zoomant beaucou beaucoup, les paroies sont toutes lisse, mais ça je ne sais pas si c'est la faute à l'optimisation ou à un problème de mémoire(l'histoir que le PC peut pas retenir des nombres avec plus de n chiffres).
Donc est-ce que vous auriez des infos sur cet optimisation?comment ça marche? se défaults?ses qualités(à part la vitesse)?etc...?
merci

J'oubliais: ces programmes marchent juste pour des ensembles de Madelbrot, mais est-ce adaptable pour d'autres fractales(Julia, flocon de Koch, cote bretonne, etc...)

joli

très joli.
Tu as programmé le rendu toi même?

merci

oui, tout est fait à la main

Une autre en deux versions :




à terme, j'avais prévu de générer des vidéos


il fallait que j'ajoute la reflexion spéculaire (entre autres choses) et surtout que j'améliore le filtrage de la texture...

c'est vrai que c'est bien jolie ces formes. Ce sont d'es ensembles d'ensembles de Julia? C'est remarquablement bien réalisé.
J'avais vu ça sur un dossier sur une vision quaternionique des fractales, et effectivement pour toutes les représenter, il nécéssitais une 4ème dimension. Donc ils utilisaient des vidéos, que bien sure j'avais pas dans le dossier.
D'ailleurs, par simple préjugé, je me dis qu'il peut être intéréssant de définir c (dans l'equation z(n+1)=z(n)^2+c) par sa notation polaire, et donc de mettre |c| sur l'axe verticale et arg(c) pour le temps,comme ça, la vidéo a une durée finie et affiche réelement tous les cas. Enfin, c'est qu'une intuition. Et puis si ce ne sont pas des ensembles de Julia, ce que j'ai dit est ridicule.

euh...up? Pen^2, tu semblait avoir des réponses à mes intérogations...

ah oui, j'avais totalement oublié, dsl.
Bon je ne connais pas ces programmes, mais

ilos (./1) :
De plus, on ne peut pas zoomer autant qu'on veut: à un moment en zoomant beaucou beaucoup, les paroies sont toutes lisse, mais ça je ne sais pas si c'est la faute à l'optimisation ou à un problème de mémoire(l'histoir que le PC peut pas retenir des nombres avec plus de n chiffres).

C'est un problème de précision des nombres réels : au bout d'un moment, on atteint la limite de précision des nombres flottants.

Donc est-ce que vous auriez des infos sur cet optimisation?comment ça marche? se défaults?ses qualités(à part la vitesse)?etc...?

ben comme je l'ai dit, je ne connais pas ces programmes, toutefois, d'après ce que tu décris, je suppose qu'ils calculent une image approchée de la fractale, et qu'ils calculent l'image finale de la fractale à partir de cette image approchée. Du coup le résultat est obtenu plus rapidement (les calculs lents utilisés pour obtenir l'image précise ne part pas de zéro).

(En gros, c'est aussi ce que j'utilisais pour calculer mes fractales)

sinon faut GMP ou MAPM

(ou java.math.BigDecimal : c'est quand même pratique, le Java )

Bon, si je comprends bien ce que tu veux dire, c'est que pour construire la fractale, le programme utilise la même méthode que pour le flocon de Koch, mais avec une sorte de carioïde à la place d'un triangle? Alors je ne vois pas coment ces logiciels peuvent avec cette méthode montrer la vitesse de divergence et donc calculer les jolies couleurs.
De plus, quand je dis que l'image est fabriquée par bloc, j'ai l'impression que ça avance diagonalement comme ceci, mais pas toujours exactement de la même manière:

Par contre, je crois avoir bien saisi le problème de précision de la courbe.
Merci de toutes ces réponses

(faut que je fasse un test pour voir si le multicore accélère vraiment un truc comme ça)

De plus, quand je dis que l'image est fabriquée par bloc, j'ai l'impression que ça avance diagonalement comme ceci, mais pas toujours exactement de la même manière:

Dans le temps j'avais programmé ça sur HP48.

Par exemple, disons qu'on veut dessiner l'ensemble de Mandelbrot (ou un ensemble de Julia connexe):

1) On peut tester (avec une bonne approximation) si un point appartient à l'ensemble : il suffit de voir si la suite z(n+1)=z(n)^2+c diverge (en voyant si son module dépasse une certaine borne B en moins d'un certain nombre N d'itérations).

2) Si tous les points des quatre côtés d'un rectangle sont dans l'ensemble, alors tout l'intérieur du rectangle est dans l'ensemble.
Si tous les points des quatre côtés d'un rectangle (pas trop grand le rectangle) sont à l'extérieur de l'ensemble, alors tout l'intérieur du rectangle est à l'extérieur de l'ensemble.

Donc l'algorithme est :
On part d'un rectangle qui couvre toute l'image qu'on veut dessiner. On calcule tous les points des bords. S'ils sont tous à l'intérieur, ou tous à l'extérieur du Mandelbrot, on remplit uniformément le rectangle. Sinon on coupe le rectangle en deux et on continue récursivement, jusqu'à ce que le rectangle soit réduit à un pixel.

C'est pas trop compliqué à programmer et ça économise une grosse quantité de calcul.

Une autre méthode très efficace (mais par contre qui ne permet pas de rajouter des jolies couleurs flashy), c'est de faire le tour de l'ensemble.



On commence par choisir un point du bord.

A chaque étape, on se déplace d'une petite longueur x fixée le long du bord de l'ensemble. Pour ça, on teste dans laquelle des 8 directions (nord, nord ouest, ouest, sud ouest, sud....... nord est) il faut aller pour rester le plus près du bord.

... et on s'arrête quand on a fait le tour.

Sur HP48 (calculatrice avec pas beaucoup de puissance de calcul) c'était suffisamment rapide pour tracer un mandelbrot sans passer par l'assembleur, et en genre 1 minute.

A l'intérieur de l'ensemble ça veut dire quoi? que pour ce point la suite diverge en moins de N itérations?
A l'extérieur ça veut donc dire que la suite ne diverge pas avant N itérations. ce point est noir alors?

les points noirs sont donc plus "longs" à peindre que les points colorés.

et ta règle c'est que si tous les points des cotés du rectangle sont noirs, tous ceux de l'intérieur du rectangle le seront aussi, donc on a pas besoin de tester leur convergence?

OK je vois le gain de temps alors.

Hmmm d'abord à la base ya pas de points "colorés" : l'ensemble de Mandelbrot (ou les ensembles de Julia...) est une partie du plan complexe. Chaque point du plan est dans l'ensemble (noir), ou en dehors de l'ensemble (blanc), c'est tout.
(Bon ensuite les logiciels rajoutent de belles couleurs pour l'esthétique, mais c'est un autre sujet...)

squalyl (./16) :
A l'intérieur de l'ensemble ça veut dire quoi? que pour ce point la suite diverge en moins de N itérations?

Rigoureusement ça veut dire :

Le point c est dans l'ensemble de Mandelbrot si et seulement si la suite
z(0)=0
z(n+1)=z(n)^2+c
ne diverge pas.

En pratique, pour tester la non divergence, il suffit de tester que |z(n)|<2 pour tout n<256. (Par exemple. Ensuite on augmente ce nombre 256 quand on zoome sur l'ensemble...)

A l'extérieur ça veut donc dire que la suite ne diverge pas avant N itérations. ce point est noir alors?

Non, si elle ne diverge pas, le point est dans l'ensemble. Et oui il est noir.
(Au passage, les logiciels colorient les points extérieurs à l'ensemble, c'est plus pratique)

les points noirs sont donc plus "longs" à peindre que les points colorés.

Oui tout à fait.
Un point de l'ensemble est long à tester parce qu'il faut aller jusqu'au bout des 256 itérations (voire plus que 256).
Alors que pour un point extérieur à l'ensemble, on quitte la boucle bien avant les 256. (pour la plupart des points, 10 itérations suffisent à constater la divergence)

et ta règle c'est que si tous les points des cotés du rectangle sont noirs, tous ceux de l'intérieur du rectangle le seront aussi, donc on a pas besoin de tester leur convergence?

Oui.
Et c'est vrai aussi pour un rectangle extérieur à l'ensemble d'ailleurs. (si tous les points des cotés du rectangle sont blancs, tous ceux de l'intérieur du rectangle le seront aussi - enfin il faut quand même un rectangle pas trop grand)

Si les dimensions du rectangle sont (n,m) alors on aura besoin de tester 2(n+m) points au lieu de n*m, économie énorme.

Concrètement, pendant le tracé on aura beaucoup de "gros rectangles", les petits rectangles seront concentrés seulement près du bord du Mandelbrot. Ca fait donc un gros gain de temps.

Merci beaucoup Hippopotame et Pen^2, j'ai tout compris complétement entièrement en totalité!

oui, moi aussi, mais j'attendais de l'avoir programmé pour poster. mais bon vu que c'est pas encore fait, oué, merci hippo pour cet éclairage.

Hippopotame (./14) :
2) Si tous les points des quatre côtés d'un rectangle sont dans l'ensemble, alors tout l'intérieur du rectangle est dans l'ensemble.Si tous les points des quatre côtés d'un rectangle (pas trop grand le rectangle) sont à l'extérieur de l'ensemble, alors tout l'intérieur du rectangle est à l'extérieur de l'ensemble.

Cette propriété n’est-elle pas à mettre en relation avec la définition d’ouvert ou de fermé (je ne sais pas vraiment, j’ai du mal à saisir l’essence de ces notions) ?

Or ce n’est pas le cas de tous les fractales.
Par exemple, pour le tapis de Sierpinski (cf. image ci-dessous : les points blancs font partie de l’ensemble, les points noirs n’en font pas partie), il est possible d’avoir, tout au moins si on ne va pas trop loin dans la récurrence (ie. si on s’arrête à l’échelle du pixel), un carré dont les bords sont constitués de pixels blancs mais entourant un carré noir.
L’algorithme des rectangles donné par Hippo’ ne marche pas dans ce cas.

Ethaniel (./20) :
Cette propriété n’est-elle pas à mettre en relation avec la définition d’ouvert ou de fermé (je ne sais pas vraiment, j’ai du mal à saisir l’essence de ces notions) ?

Nan c'est pas ça.
Par exemple l'ensemble de Mandelbrot est fermé, mais si on voulait tracer son intérieur (ouvert), ça marcherait aussi.

L'idée derrière l'algo c'est plutôt que si le bord d'un convexe est inclus dans l'ensemble alors l'intérieur du convexe aussi.
Mais bon on en discutait au bureau ce matin et on n'a pas su donner un nom à cette notion

Or ce n’est pas le cas de tous les fractales.
Par exemple, pour le tapis de Sierpinski (cf. image ci-dessous : les points blancs font partie de l’ensemble, les points noirs n’en font pas partie), il est possible d’avoir, tout au moins si on ne va pas trop loin dans la récurrence (ie. si on s’arrête à l’échelle du pixel), un carré dont les bords sont constitués de pixels blancs mais entourant un carré noir.L’algorithme des rectangles donné par Hippo’ ne marche pas dans ce cas.

Yep!
L'algo est fait plutôt pour Mandelbrot, Julia et tous leurs dérivés.

Comme je l’ai précisé, je n’ai jamais bien compris ces définitions d’ouvert et de fermé ^^"…

Par contre, pas besoin que ce soit un convexe (même si un rectangle est convexe, le choix de cette forme est pour des raisons pratiques, puisqu’il est très simple de faire des rectangles avec des pixels).

Si cet algorithme marche pour Mandelbrot, Julia et dérivés, c’est parce que pour ces fractales, l’ensemble et son complémentaire (l’intérieur et l’extérieur, mais au sens commun et intuitif du terme, peut-être pas au sens mathématique) sont tous les deux d’un seul tenant (je pensait que c’était cette notion qui était couverte par les définition d’ouvert et de fermé, mais en fait non ^^").
Quand je dis « d’un seul tenant », c’est qu’on peut joindre n’importe quelle paire de point de l’ensemble en restant dans cet ensemble (mais pas forcément par un segment, ça c’est la définition d’un convexe), et de même, on peut joindre n’importe quelle paire de point du complémentaire de l’ensemble en restant dans ce complémentaire.
Maintenant que j’y pense, le terme « compact » me vient en tête, mais je dois sans doute me tromper encore ^^"…

a mon avis, si un emsemble est un convexe "d'un seul tenant" son complémentaire ne l'est pas...

"D'un seul tenant" = "connexe".

Et c'est en rapport avec les ouverts et les fermés: un ouvert O est dit connexe si (et seulement si) tout sous-ensemble A de O à la fois relativement ouvert dans O (c'est-à-dire qu'il existe un ouvert B tel que B inter O = A, c'est-à-dire encore que A est ouvert parce que A est sous-ensemble de O) et relativement fermé dans O (c'est-à-dire qu'il existe un fermé B tel que B inter O = A) est soit O soit l'ensemble vide.

squalyl (./23) :
a mon avis, si un emsemble est un convexe "d'un seul tenant" son complémentaire ne l'est pas...

Faux, |R⁺ est convexe et connexe, mais son complémentaire aussi.

En revanche, si ton ensemble est convexe et borné, alors son complément ne sera effectivement pas convexe (il y aura un "trou" laissé par ton ensemble convexe, "plusieurs trous" s'il n'est pas connexe). Démonstration: Soit C ton ensemble, soit O un point de C. C est borné, donc il existe un cercle K de centre O tel que K et C sont disjoints (il suffit de prendre un rayon suffisamment grand). N'importe quel diamètre de K est un segment dont les bornes sont dans le complément de C, mais un point à l'intérieur (le point O) ne l'est pas => le complément de C n'est pas convexe.

ok je pensais seulement aux ensembles bornés.

strop dur pour moi les maths

Ethaniel (./22) :
Par contre, pas besoin que ce soit un convexe (même si un rectangle est convexe, le choix de cette forme est pour des raisons pratiques, puisqu’il est très simple de faire des rectangles avec des pixels).

La notion mathématique pertinente est sans doute plutôt celle avec la convexité.

Si cet algorithme marche pour Mandelbrot, Julia et dérivés, c’est parce que pour ces fractales, l’ensemble et son complémentaire (l’intérieur et l’extérieur, mais au sens commun et intuitif du terme, peut-être pas au sens mathématique) sont tous les deux d’un seul tenant

"d'un seul tenant" = "connexe".

Nan ce n'est pas la connexité qui est la bonne raison.
Contre exemple : le disque de centre O, de rayon 2, auquel on a enlevé le disque de centre O, de rayon 1.
Autre contre-exemple : le tapis de Sierpinski (qui est connexe!)....

Maintenant que j’y pense, le terme « compact » me vient en tête, mais je dois sans doute me tromper encore ^^"…

Yep c'est pas ça non plus

Compact = fermé borné (dans un espace vectoriel de dimension finie en tout cas ; plus généralement un espace est compact si de tout recouvrement ouvert on peut extraire un recouvrement fini, mais c'est assez technique).

En fait les notions d'ouverts, de fermés, de compacts ou de connexes sont des notions de topologie pure, qui ne font pas intervenir de métrique ou de structure linéaire ; donc elles sont insuffisantes pour notre problème présent.

strop dur pour moi les maths

Ouais mais la topologie ça overpoutre !


(edit de bêtises)

L'idée derrière l'algo c'est plutôt que si le bord d'un convexe est inclus dans l'ensemble alors l'intérieur du convexe aussi.
Mais bon on en discutait au bureau ce matin et on n'a pas su donner un nom à cette notion

En fait ça doit correspondre à peu près à :

L'ensemble est simplement connexe, et les composantes connexes de son intérieur sont convexes.

Et pour l'algo on a besoin de la même chose pour le complémentaire de l'ensemble (dans le plan compactifié).

Mouais.
Enfin bon bref.

Hippopotame (./27) :
Le complémentaire d'un point dans le plan est convexe.

Euh, c'est quoi ta définition de convexe? Je n'ai pas l'impression que ce soit la même que la mienne... Cet ensemble est clairement "troué", il n'est même pas simplement connexe, c'est une aberration de le traîter de "convexe"!

Euh, oui oui oui, confusion convexe/connexe !

Le complémentaire d'une partie bornée non vide ne peut pas être convexe !