Kawałek Kodu

Ostatnio trochę deszczowo i mokro się zrobiło, więc podejmiemy temat na czasie. Pokażę Ci skąd się biorą kółka na wodzie, a może dowiemy się również dlaczego cegła wrzucona do wody tworzy kręgi. A to wszystko w efektownej formie ubranej w JS oraz Canvas. I co najważniejsze, każdy z Was będzie mógł takie kółka tworzyć na ekranie własnego komputera bez potrzeby oczekiwania na deszcz. Chcesz być Rainman'em? Czytaj dalej!

Wynajdywanie okręgu na nowo.

Water ripple to efekt graficzny symulujący kółka/zmarszczki na wodzie po uderzeniu w taflę wody jakiegoś obiektu. Symulacja prezentuje efekt widziany z góry. Być może w rzeczywistości spotkałeś się z nim osobiście, kiedy wrzucałeś kamienie z mostu do jeziora czy rzeki. Kamień robił "plum", a wokół miejsca gdzie wpadł rozchodziły się promieniście fale. Z efektem spotkałem się kilkanaście lat temu, choć tylko w formie algorytmu. Ostatnio na niego trafiłem ponownie, ale również z ciekawym wyjaśnieniem. Autor algorytmu pozostaje nieznany. Istnieje, albo w sumie istniała, bo obecnie dostępna tylko w archiwum webowym, wzmianka o efekcie, której to autorem jest Hugo Elias (link znajdziesz w przydatnych na końcu wpisu).

Cała rzecz opiera się na podpatrywaniu natury, bo aby osiagnąć realistyczny efekt trzeba stworzyć mu odpowiednie warunki. Autor obserwował sobie fale na wodzie i zauważył, że:

  • fala porusza się w lewo na lewo od punktu źródłowego (bo przecież zmarszczki rozchodzą się od centrum),
  • prędkość pionowa w czasie t danym punkcie fali może być obliczona na podstawie wartości punktu w czasie t-1 (kolejna klatka wynika z poprzedniej).

Wyobraźmy sobie falę stojącą:

Strzałki wskazują kierunek ruchu punktów fali. W kolejnej klatce sinusoida spłaszczy się, a następnie wywinie się na "lewą stronę", tzn. będzie swoim lustrzanym odbiciem względem osi X. Cały cykl będzie się powtarzał. Tak to mniej więcej wygląda:

Należy pamiętać, że nasza fala będzie się przesuwać w lewo poprzez efekt rozchodzenia się fal. Nie będziemy więc odejmować wartości w tym samym punkcie osi X, ale delikatnie przesuniętego względem niego (z czasu t-1). Nie będzie to już fala stojąca. Będzie też słabnąć, więc z każdym cyklem amplituda (te górki) będą coraz mniejsze. Aby móc przechowywać informację o bieżącej fali oraz klatkę wcześniej, potrzebne są dwa bufory. Załóżmy, że będą to: buffer1 oraz buffer2. I co ważna rzecz teraz już możemy te bufory przełożyć na przestrzeń 2D.

Według drugiego założenia prędkość pionowa danego punktu wynika z wartości fali w czasie t-1, tak więc:
predkosc(x,y)=-buffer2(x,y).

Należy również zauważyć, że zmarszczki rozchodzą się od środka we wszystkich kierunkach (założenie 1):

rozchodzenie(x,y)=(buffer1(x-1,y)+buffer1(x+1,y)+buffer1(x,y-1)+buffer1(x,y+1))/4

co oznacza, że nowy punkt jest średnią z otaczających go czterech punktów (sąsiednie punkty mają na niego wpływ - patrząc już na efekt z góry w przestrzeni 2D).

Łącząc prędkość i rozchodzenie, otrzymujemy:

zmarszczka(x,y)=2*rozchodzenie(x,y)+predkosc(x,y)

Wartość rozchodzenia się fal została pomnożona przez 2, aby zniwelować nieco wartość prędkości.

Ponieważ zmarszczki zanikają wraz z czasem, to należy pomnożyć wartość poprzez liczbę z zakresu [0,1]:

zmarszczka(x,y)=zmarszczka(x,y)*zanikanie

Możemy to zapisać również w postaci:

zmarszczka(x,y)=zmarszczka(x,y)-zmarszczka(x,y)*(1-zanikanie)

Dlaczego tak? Bo to oznacza, że teraz zamiast mnożenia możemy użyć przesunięcia bitowego, co będzie zdecydowanie szybsze przy dużej ilości wartości, które należy obliczyć. Zakładając, że będziemy przesuwać o 5 bitów w prawo, czyli dzielić przez 32, czyli mnożyć przez 1/32, to wynika z tego, że zanikanie=31/32, czyli 0.96875, co jest całkiem przyzwoitą wartością i oczywiście mieści się w przedziale [0,1].

Jeszcze jedna ważna rzecz, to zamiana buforów co klatkę. Gdybyśmy tego nie zrobili, to nie uzyskalibyśmy efektu ruchu, bo wciąż liczylibyśmy wartości dla jednej klatki na podstawie niezmiennej drugiej klatki.

Podstawiając wzory prędkości i rozchodzenia, do ostatniego wzoru, w pseudokodzie wygląda to tak:

dla każdego punktu x,y:

 buffer2(x,y) = (
                (buffer1(x-1,y)+
                 buffer(x+1,y)+
                 buffer(x,y-1)+
                 buffer(x,y+1)
                 ) / 4
                ) * 2 - buffer2(x, y)
 buffer2(x,y) = buffer2(x,y) * zanikanie

wyświetl buffer2
zamień zawartości buforów

Falula rasa.

Zanim przejdziemy do implementacji i dumania nad efektem, jeszcze wizualizacja kilku klatek takiego efektu na tablicy 10x10. Wartością 255 zasiany jest punkt środkowy tablicy.
Po pierwszej iteracji mamy taki stan (jeden krąg):

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 124 0 0 0 0 0
0 0 0 124 0 124 0 0 0 0
0 0 0 0 124 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Iteracja 2 (dwa kręgi, jeden ponad poziomem 0, drugi pod):

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 61 0 0 0 0 0
0 0 0 121 0 121 0 0 0 0
0 0 61 0 -6 0 61 0 0 0
0 0 0 121 0 121 0 0 0 0
0 0 0 0 61 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Iteracja 3 (dwa kręgi już nad poziomem 0):

0 0 0 0 0 0 0 0 0 0
0 0 0 0 30 0 0 0 0 0
0 0 0 89 0 89 0 0 0 0
0 0 89 0 24 0 89 0 0 0
0 30 0 24 0 24 0 30 0 0
0 0 89 0 24 0 89 0 0 0
0 0 0 89 0 89 0 0 0 0
0 0 0 0 30 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

To co się rzuca w oczy, to że faktycznie widać jak kręgi się rozchodzą. Widać tez, że czasem z obliczeń otrzymujemy wartość ujemną (fala jest poniżej poziomu 0). Tą wartością nie musimy się przejmować i tak zostanie wrysowana na CANVAS jako czarny punkt.

No to teraz kod:

/* będziemy działać
   na obrazie 320x320
*/
let width = 320;
let height = 320;
let buffer1 = new Array(width * height).fill(0);
let buffer2 = new Array(width * height).fill(0);

/* przyda nam się kontekst <canvas>
*/
const canvas = document.querySelector("canvas");
canvas.width = width;
canvas.height = height;
const ctx = canvas.getContext("2d");

/* na razie bez
   żadnej interakcji
*/
let mousePressed = false;

/* jeśli wciśnięto mysz
   to zapisujemy tą informację
   (pamiętaj o dodaniu obsługi
    dotyku)
*/
canvas.addEventListener("mousedown", function(e) {
  mousePressed = true;
});

/* jeśli mysz się porusza
*/
canvas.addEventListener("mousemove", function(e) {

/* i przycisk wciśnięty
*/
  if (mousePressed) {

/* to wrzucamy cegłę do wody,
   tu okazuje się, że wizualnie
   lepiej działa zasianie punktu 7x7
   niż 1x1, stąd taka pętla
*/
    for (let j = e.offsetY - 3; j < e.offsetY + 3; j++) {
      for (let k = e.offsetX - 3; k < e.offsetX + 3; k++) {
        if (j >= 0 && j < height && k >= 0 && k < width) {
          buffer1[j * width + k] += 128;
        }
      }
    }
  }
});

/* jeśli zwolniono przycisk
   myszy
*/
canvas.addEventListener("mouseup", function(e) {
  mousePressed = false;
});

/* co 25 ms kreślimy
   to co mamy w buforze
*/
setInterval(function() {

/* czyścimy <canvas>
*/
  ctx.fillStyle = "#000";
  ctx.fillRect(0, 0, width, height);

/* pobieramy piksele
   z <canvas>
*/
  const imageData = ctx.getImageData(0, 0, width, height);

/* tu się zaczyna najbardziej
   interesujący fragment,
   iterujemy po każdym punkcie
*/
  for (let i = width; i < (height - 1) * width; i++) {

/* zmarszczka = rozchodzenie + predkosc
   ponieważ wartość rozchodzenia to średnia
   z 4-ech, czyli dzielenie przez 4,
   ale i pomnożona przez 2,
   możemy ją podzielić przez 2
   dla uproszczenia (x/4*2=x/2),
   a 2 to przesunięcie
   w prawo o jeden bit
*/
    buffer2[i] =
      (
       (buffer1[i - 1] +
        buffer1[i + 1] +
        buffer1[i - width] +
        buffer1[i + width]
       ) >> 1
      ) - buffer2[i];

/* zanikanie
   x = x - x / 32;
   czyli
   x = x * 1 - x * (1/32);
   czyli
   x = x * (31/32);
*/
    buffer2[i] -= buffer2[i] >> 5;

/* wartość zmarszczki używamy
   jako składową R, G oraz B,
   bez przezroczystości
*/
    imageData.data[i << 2] = buffer2[i];
    imageData.data[(i << 2) + 1] = buffer2[i];
    imageData.data[(i << 2) + 2] = buffer2[i];
    imageData.data[(i << 2) + 3] = 255;

    //ctx.fillStyle = "rgb(" + buffer2[i] + "," + buffer2[i] + "," + buffer2[i] + ")";
    //ctx.fillRect(i % width, parseInt(i / width), 1, 1);
  }

/* dane pikseli wstawiamy
   z powrotem do <canvas>
*/
  ctx.putImageData(imageData, 0, 0);

/* a bufory zamieniamy
*/
  const copy = buffer1.slice(0);
  buffer1 = buffer2;
  buffer2 = copy;
}, 25);

Dwie linie pojawiły się w kodzie pomimo, że są zakomentowane - możesz sprawdzić jak wydajne jest stawianie pikseli poprzez metodę fillRect (zakomentuj wcześniej 4 powyższe linie). Jeśli wciśnięty jest przycisk myszy kreślę nie punkt 1x1, lecz 7x7. Daje to dużo lepszy efekt. Kręgi są grubsze i nie nikną tak szybko. Chcesz się przekonać jak wygląda wrzucenie czegoś innego niż takiej cegły - zmniejsz wartości graniczne w pętlach lub po prostu wstawiaj punkt 1x1.

Jeśli efekt Ci się spodobał, to zapraszam Cię na drugi epizod tego wpisu, gdzie naocznie będzie można się przekonać, że istnieje jeszcze fajniejszy wariant tego efektu. No, już się nie marszcz. Do przeczytania!

 

Przydatne linki:
Water ripple effect.
Opis algorytmu ripple water effect według Hugo Elias'a.
Powtórka z tabliczki mnożenia, czyli o przesunięciach bitowych.
The Fast & The Canvas, czyli szybki dostęp do pikseli na Canvas.