❄ Fraktale IFS — systemy funkcji iterowanych

System IFS to skończony zbiór kurczących przekształceń afinicznych płaszczyzny. Każde przekształcenie zmniejsza i przemieszcza przestrzeń, a suma wszystkich przekształceń stosowanych wielokrotnie definiuje unikalny zbiór fraktalny zwany atraktorem. Paproć Barnsleya, trójkąt Sierpińskiego i krzywa smoka są atraktorami różnych systemów IFS.

Zaczynasz od dowolnego punktu, a następnie w każdym kroku losowo wybierasz jedno z przekształceń, ważone jego prawdopodobieństwem p, i stosujesz je do bieżącego punktu. Rysowanie każdego nowego punktu stopniowo wypełnia atraktor. Kilka pierwszych punktów jest pomijanych jako rozgrzewka, aby nie rysować przejściowych pozycji leżących poza atraktorem.

Przyciski presetów wybierają, który zestaw map IFS jest aktywny. Suwak Points-per-frame (od 500 do 30 000) ustala, ile iteracji jest rysowanych w każdej klatce, kontrolując szybkość rysowania. Suwak Fade speed (od 0 do 0,05) przygasza starsze punkty, dzięki czemu płótno może się odświeżać. Clear zeruje liczbę punktów i czyści płótno, a Pause zatrzymuje lub wznawia iterację.

Ponieważ wszystkie przekształcenia są kurczące, ich wielokrotne stosowanie przyciąga dowolny punkt startowy coraz bliżej atraktora. Jest to konsekwencja twierdzenia Banacha o punkcie stałym zastosowanego do operatora IFS na zbiorach zwartych, dzięki czemu różne punkty startowe zbiegają do tego samego fraktala.

Każde przekształcenie ma postać W(x,y) = (a·x + b·y + e, c·x + d·y + f). Współczynniki a, b, c, d odpowiadają za obrót, skalowanie i ścinanie, natomiast e i f przesuwają punkt. Paproć Barnsleya wykorzystuje na przykład cztery takie przekształcenia z prawdopodobieństwami 0,01, 0,85, 0,07 i 0,07.

Pierwsze przekształcenie (prawdopodobieństwo 0,01) ściąga punkty na pionową łodygę i obejmuje niewielki obszar, więc rzadko musi być stosowane. Dominujące przekształcenie o prawdopodobieństwie 0,85 buduje główny liść. Prawdopodobieństwa są dobrane tak, by odpowiadały powierzchni atraktora pokrywanej przez każde przekształcenie, co daje równomierne, fotorealistyczne wypełnienie.

To wymiar fraktalny atraktora — niecałkowita miara tego, jak skaluje się szczegółowość struktury. Trójkąt Sierpińskiego ma wymiar log3/log2 ≈ 1,585, natomiast krzywa smoka wypełnia powierzchnię i zbliża się do 2. Wyświetlane wartości to charakterystyczne oszacowania dla każdego presetu.

Współczynniki przekształceń i prawdopodobieństwa to standardowe, opublikowane wartości dla każdego systemu, a arytmetyka afiniczna jest dokładna w zapisie zmiennoprzecinkowym. Obraz jest jednak skończonym próbkowaniem, więc bardzo drobna struktura ujawnia się dopiero wraz z narastaniem liczby punktów, choć zbieżny obraz wiernie odwzorowuje rzeczywisty atraktor.

Udowodnione przez Barnsleya i Demko w 1986 roku, gwarantuje ono, że każdy IFS złożony z przekształceń kurczących ma jedyny zwarty atraktor A spełniający A = suma wszystkich Wᵢ(A). Pokazuje też, jak znaleźć IFS, którego atraktor przybliża zadany kształt, co stanowi podstawę kompresji obrazu metodą fraktalną.

Wykorzystuje się je w kompresji obrazów metodą fraktalną, gdzie obrazy są kodowane jako przekształcenia IFS zamiast jako piksele, a także w proceduralnym generowaniu roślin, chmur, terenu i naturalnych tekstur do grafiki i gier. Ich zwięzłość sprawia, że są efektywnym sposobem reprezentowania bogato szczegółowych, samopodobnych kształtów.