Kawałek Kodu

Może już widziałeś ten piękny graficzny wzór, choć nie wiesz, że miałeś do czynienia z fraktalem. Fraktal to obiekt nieskończenie powtarzalny, albo samopodobny. Oznacza to, że w jego fragmencie jest zawarta całość. Mamy do czynienia z nimi nie tylko w formie komputerowej grafiki, ale również w otaczającym świecie (choć nie są to nieskończenie powtarzalne konstrukcje). Fraktalem jest kalafior czy brokuł, którego kawałek wyglądem przypomina całość. Banknoty niestety nie są fraktalami. Drzewo jest fraktalem. Wygląda na to, że cały wszechświat jest również fraktalem, którego odwzorowanie możemy znaleźć w żywej komórce.

Z fraktalami nieodłącznie wiąże się rekurencja. Dzięki niej powstaje trójkąt Sierpińskiego, kiedy to w duży trójkąt wrysowujemy odwórcony mniejszy, a pozostałe trzy miejsca są zapełniane w ten sam sposób jak duży. I tak dopóki starczy sił albo czasu.
Ale nie zawsze się wiąże. Możemy skorzystać z innej cechy liczb jaką jest możliwość ich reprezentacji binarnej i operacji logicznych na nich. W ten sposób możemy stworzyć fraktal Sierpińskiego oparty na trójkącie prostokątnym.

Ten ładny wzór osiągnęliśmy poniższym, krótkim kodem:

<canvas width="256" height="256"></canvas>

+

for(var y=0; y<256; y++){
    for(var x=0; x<256; x++){
        if(!(x & y)){
            document.querySelector('canvas').getContext('2d').fillRect(x, y, 1, 1);
        }
    }
}

Pętlę są jasne. Iterujemy po wysokości i szerokości CANVAS. W każdym punkcie sprawdzamy czy iloczyn logiczny ze współrzędnej x i y daje 0 (false). Jeśli tak, to rysujemy punkt.

Co to jest iloczyn logiczny?

Jest to operacja logiczna na bitach dająca następujące wyniki:

a b a AND b
0 0 0
0 1 0
1 0 0
1 1 1

Jeśli obliczamy iloczyn logiczny z dwóch liczb, to taką operację przeprowadzamy na każdym z bitów z osobna - czyli bit 0 liczby x AND bit 0 liczby y, bit 1 liczby x AND bit 1 liczby y.

Przyglądając się naszemy trójkątowi widzimy, że pierwsza linia jest pełna (wszystkie piksele czarne). Stało się tak dlatego, ponieważ w tej linii była przeprowadzona operacja AND każdej współrzędnej x ze współrzędną y=0, co dawało wynik 0.
W drugiej linii mam co drugi piksel czarny.

Dlaczego tak się dzieje, pokazuje poniższa tabela:

x y x AND y
0=00000000 1=00000001 00000000
1=00000001 1=00000001 00000001
2=00000010 1=00000001 00000000
3=00000011 1=00000001 00000001
4=00000100 1=00000001 00000000
5=00000101 1=00000001 00000001
6=00000110 1=00000001 00000000

Dla trzeciej linii (y=2) wynik będzie następujący:

x y x AND y
0=00000000 2=00000010 00000000
1=00000001 2=00000010 00000000
2=00000010 2=00000010 00000001
3=00000011 2=00000010 00000001
4=00000100 2=00000010 00000000
5=00000101 2=00000010 00000000
6=00000110 2=00000010 00000001

Ale to jednak wciąż trójkąt prostokątny!

Nie da się tego ukryć. Prawdziwy trójkąt Sierpińskiego jest trójkątem równobocznym. A gdyby kopnąć lekko trójkąt, aby się przekrzywił? No dobrze, jednak kiedy kopniemy go w wierzchołek, to i tak trójkąt będzie do góry nogami. Od czegoś jednak trzeba zacząć, więc zacznimy od odwrócenia trójkąta prostokątnego.

Skoro maksymalna wartość współrzędnej y to 255, a dla y=0 chcemy osiągnąć 255 i dla y=255 chcemy 0, to wprowadzić drobną zmianę:

document.querySelector('canvas').getContext('2d').fillRect(x, 255-y, 1, 1);

Połowa sukcesu za nami. Jak jednak przechylić trójkąt tak, aby wierzchołek znalazł się w połowie podstawy?
Zadanie mamy nieco ułatwione, bo dopieszczamy trójkąt w kwadratowym obszarze, tak więc jego podstawa jest równa wysokości. Skoro tak, to wierzchołek ma być przesunięty o 128 pikseli, a piksele w połowie wysokości o 64. 128 to 256/2 (czyli połowa pełnej wysokości), a 64 to 128/2 czyli połowa połowy wysokości. Wynika z tego, że musimy przesuwać wierzchołek, czyli współrzędną x, o połowę aktualnej wysokości czyli y/2.

Linia odpowiedzialna za stawianie pikseli, wygląda teraz tak:

document.querySelector('canvas').getContext('2d').fillRect(x + y / 2, 255-y, 1, 1);

A trójkąt tak:

Oprócz pikseli czarnych pojawiły się szare... Jest to wynikiem antialiasingu przy rysowaniu pikseli połówkowych (czyli np. na współrzędnej x=1.5). Trzeba się tego pozbyć. Możemy to zrobić poprzez użycie funkcji parseInt na ilorazie, ale skoro jesteśmy przy operacjach bitowych, to użyjemy dzielenia logicznego, zwanego przesunięciem logicznym w lewo.

Doc! What the hell is logical shift?!

Znów niech za przykład posłuży tabelka:

a a >> 1
0=00000000 0=00000000
1=00000001 0=00000000
2=00000010 1=00000001
3=00000011 1=00000001
4=00000100 2=00000010
5=00000101 2=00000010
6=00000110 3=00000011

Przy reprezentacji binarnej liczb wszystko powinno stać się jasne. Przesuwamy bity o jeden w lewo (dzielimy przez 2), przez co najbardziej skrajny z prawej (bit 0) wypada. Jako, że operujemy na liczbach całkowitych, to wynik też mamy całkowity i nie musimy się przejmować czy coś pojawi się po przecinku. Nie pojawi się.
Tu można się pokusić o ciekawostkę. Wystarczy, że dorysujesz wirtualną kropkę za ostatnim bitem wyniku i ginące bity będziesz wpisywał na pozycje za kropką (będa one odpowiadać wartościom: 1/2, 1/4, 1/8, 1/16, itd.). Sprawdź co otrzymasz w ten sposób dla liczby 3.

Korzystając z przesunięcia logicznego w lewo, przekształćmy więc sławetną linię:

document.querySelector('canvas').getContext('2d').fillRect(x + (y >> 1), 255-y, 1, 1);

Luks! Ale fajnie by było naszego kopniętego trójkąta wyprowadzić na dobrą drogę i zrobić z niego równiachę. No... czyli trójkąt równoboczny.
Musimy obliczyć jak bardzo zrobić z niego konusa, czyli znaleźć stosunek wysokości trójkąta równobocznego o podstawie jak nasz, do wysokości naszego trójkąta. Wysokość trójkąta równobocznego opisuje wzór: h=a*SQRT(3)/2. Przy podstawie 256px, otrzymamy h=128*SQRT(3).

Znów pomęczmy naszą linię (tu już nie unikniemy parseInt, bo znów byśmy mieli szare piksele):

document.querySelector('canvas').getContext('2d').fillRect(x + (y >> 1), parseInt((255 - y) * ((128 * Math.sqrt(3)) / 256)), 1, 1);

Miodzio!

Mam nadzieję, że ten wpis pozwoli Ci na zmianę jednokierunkowego myślenia o trójkącie i zafascynuje mnogością jego możliwości.

 

Przydatne linki:
Czym jest fraktal?
Zbiór Mandelbrota
Trójkąt Sierpińskiego