generic: ręcznie napisany silnik 3D w JavaScripcie, przeniesiony na ESP8266

Zastrzeżenie: opisane tu projekty są efektem mojej własnej, samodzielnej pracy, wykonanej bez użycia AI. Sam artykuł powstał z pomocą AI.

Większość moich eksperymentów graficznych zaczyna się od tego samego kawałka kodu. generic (dziś katalog js3d-engine w moim repozytorium retro-lab) to mały silnik 3D, który napisałem na początku 2013 roku dla przeglądarek na Androidzie i Windows Phone, bez WebGL i bez żadnej biblioteki 3D. Wszystko, od macierzy obrotu po mapowanie tekstur, to czysty JavaScript rysujący na canvasie 2D.

W 2018 roku uporządkowałem go, opublikowałem i użyłem jako implementacji referencyjnej dla portów na Commodore 64, sektor rozruchowy x86 oraz mikrokontroler ESP8266.

Co robi silnik #

Wektory i macierze pochodzą z biblioteki Sylvester, wyszukiwanie ścieżek z PathFinding.js, a reszta to mój własny kod.

Obrót z cache #

Macierz obrotu jest iloczynem trzech macierzy wokół osi X, Y i Z. Jej obliczenie jest kosztowne, a kąt kamery zmienia się rzadko, więc wynik jest cache'owany według kąta, a funkcje trygonometryczne przechodzą przez własny cache (getT):

getM = function(th) {
  var lookup = ""+th.x+th.y+th.z;
  var existingEntry = cacheM[lookup];
  if (existingEntry !== undefined) {
    return existingEntry;
  }
  var d1 = [
    1, 0,                0                  ,
    0, getT("cos",th.x), -1*getT("sin",th.x),
    0, getT("sin",th.x), getT("cos",th.x)   ];
  var d2 = [
    getT("cos",th.y),    0, getT("sin",th.y),
    0,                   1, 0               ,
    -1*getT("sin",th.y), 0, getT("cos",th.y)];
  var d3 = [
    getT("cos",th.z), -1*getT("sin",th.z), 0,
    getT("sin",th.z), getT("cos",th.z),    0,
    0,                0,                   1];
  var newEntry = matM(matM(d1,d2),d3);
  cacheM[lookup] = newEntry;
  return newEntry;
}

Algorytm malarza i „światło” #

Nie ma z-bufora. OcclusionCulling przechowuje listę modeli, w każdej klatce aktualizuje odległość każdego z nich od kamery i sortuje listę od najdalszego do najbliższego, więc bliższe ściany są po prostu malowane na dalszych.

Oświetlenie to sztuczka, a nie model fizyczny: kolor ściany jest rozjaśniany lub przyciemniany o procent zależny od odległości między kamerą a środkiem ściany. Wyniki są cache'owane dla każdego koloru i procentu, bo konwersja string ↔ hex w JavaScripcie była zaskakująco kosztowna na telefonie z 2013 roku:

getFaceColor: function(faceCenter, requestedColor) {
  var distance = getDistance3(camera.position, faceCenter);
  return this.getColor(requestedColor, 20-(distance/15));
}

Uruchomienie #

Wystarczy dowolny serwer plików statycznych. Z Rubym:

ruby -run -ehttpd . -p8000

Następnie otwórz http://localhost:8000/html/core.html i poruszaj kamerą klawiszami a/d oraz w/s. Pierwszy kafelek mapy 10×10 jest teksturowany.

Przeniesienie matematyki na ESP8266 #

ESP8266 to układ Wi-Fi z 32-bitowym rdzeniem Tensilica L106, 80 KB pamięci RAM na dane i zegarem 80 lub 160 MHz. Z firmware NodeMCU uruchamia Lua, więc wziąłem część generic odpowiedzialną za projekcję (macierze obrotu, kamera, dzielenie perspektywiczne) i przepisałem ją w Lua (3d.lua). Nie ma wyświetlacza: układ oblicza rzutowane wierzchołki, a wynik trafia na konsolę szeregową, co wystarcza do zmierzenia przepustowości.

Co warto wiedzieć, zanim zaczniesz:

• Zbuduj firmware tylko z potrzebnymi modułami za pomocą usługi NodeMCU custom builds. Możesz wybrać wersję integer lub float; port używa liczb całkowitych ze stałym współczynnikiem skalowania, więc działa na obu.
• Wgraj go za pomocą nodemcu-flasher: firmware pod 0x00000, a esp_init_data_default.bin pod 0xfc000, 115200 bodów. Pierwsze uruchomienie formatuje system plików.
• Pliki Lua wgrywaj przez ESPlorer. Jeśli skrypt zablokuje układ, wyczyść pamięć flash i zacznij od nowa:

python esptool.py -p COM3 -b 115200 erase_flash

init.lua mierzy wolną pamięć sterty przed uruchomieniem i po nim:

print("START HEAP "..node.heap());
dofile("3d.lua")
print("FINISH HEAP "..node.heap());

Program startuje z 41 424 bajtami wolnej sterty i kończy z 24 792.

Liczby #

Na ESP8266 szybkość skaluje się dokładnie z zegarem, co oznacza, że praca jest ograniczona wyłącznie przez CPU: przy tej skali nie ma wąskiego gardła w pamięci ani we/wy. Na tablecie jeden teksturowany kafelek w polu widzenia obniża przepustowość o jedną trzecią lub więcej: teksturowanie na canvasie 2D, bez GPU, jest zdecydowanie najkosztowniejszą rzeczą, jaką robi silnik.

Czego mnie to nauczyło #

• Mały silnik, który rozumiesz w całości, jest lepszym punktem odniesienia niż duży, którego nie rozumiesz. Przeniesienie generic na cztery bardzo różne maszyny było możliwe tylko dlatego, że cały mieści mi się w głowie.
• Cache'owanie (macierzy, funkcji trygonometrycznych, kolorów) dało więcej niż jakakolwiek mikrooptymalizacja kodu rysującego.
• Mierzenie wierzchołków na sekundę na każdej platformie dało mi jedną liczbę do porównania przeglądarki, mikrokontrolera i komputera 8-bitowego. Tego samego podejścia użyłem później z OpenCL w Simple High Performance Computing.

Kod źródłowy: retro-lab/js3d-engine i retro-lab/esp8266. Zobacz też przegląd moich praktycznych projektów.