Wojciech Polak

Software renderer

05/03/2016

Ostatnio wiele osób pytało mnie się jak można rysować za pomocą HTMLowego canvasa pewną scenę w 3D. Jako że miałem nieco styczności zarówno z OpenGL, jak i z DirectX, postanowiłem nieco przybliżyć temat. Dziś napiszemy bardzo prosty software’owy renderer - narysujemy obracający się sześcian wireframe (tzn. taki, w którym trójkąty nie są wypełniane, a widać jedynie krawędzie, bez testu głębokości).

Technologia

Na potrzeby przykładu użyję:

  • Javascript
  • CanvasQuery - biblioteka, która jest prostym wrapperem na czysty canvas. Wszystko co dziś zobaczycie, da się zrobić bez niej - operacje które pokażę są uniwersalne, niezależnie od tego czy chcecie renderować w canvasie, SDL, czy np. czystym WinAPI ( w tym wypadku mowa o aplikacji napisanej np. w C ;-) )

Cały kod źródłowy omawiany w artykule jest dostępny tutaj

Szkielet

Ok! Możemy zacząć zabawę.

 
(function() {
    var layer = cq(800, 600).appendTo(document.body).strokeStyle("#fff"); // 1.

    var render = function() { // 2.
        layer.clear("#333"); // 3.

    };

    setInterval(function() { //4.
        render();
    }, 1000 / 60);
})();

Póki co utworzyłem szkielet naszej aplikacji. W 1. zainicjowałem cały canvas, dodałem go to strony html, oraz ustawiłem, aby nasze rysowane linie miały kolor biały. 2. to nasza główna funkcja, która będzie wywoływana w interwale określonym w 4.. Zaś w 3. wyczyściłem cały canvas - przed każdym rysowaniem kolejnej klatki usuwamy to co rysowaliśmy w poprzedniej.

Słowo o wierzchołkach

Jako że chcemy wyrenderować jakiś obiekt (w naszym przypadku jest to sześcian), musimy w jakiś sposób przechowywać informacje o jego kształcie. W większości przypadków każdy model należy striangularyzować - to znaczy zbudować go z trójkątów, gdyż nasze karty graficzne kochają właśnie trójkąty i na nich najlepiej operują. Co prawda póki co będziemy wszystko robić za pomocą procesora, jednakże warto o tym pamiętać i już teraz uczyć się dobrych praktyk.

Oczywiście nic nie stoi na przeszkodzie aby rysować bezpośrednio linie, czworokąty czy inne figury. My będziemy trzymać się tych trójkątów.

Normalnie proces triangularyzacji przeprowadzany jest automatycznie np. w programie graficznym Blender. Nasz model jest na tyle prosty, że możemy zrobić to ręcznie za pomocą kartki i ołówka.

Każdy trójkąt możemy zapisać jako ciąg 3 wierzchołków. Każdy wierzchołek możemy zapisać jako wektor o 3 wymiarach: X, Y i Z Z tego wynika, że jedną ścianę naszego modelu moglibyśmy po prostu zapisać jako:

 
[
    [1, -1, -1], [-1, -1, -1], [1, 1, -1],
    [1, 1, -1], [-1, -1, -1], [-1, 1, -1]
]

Potrzebowaliśmy na to 2 trójkąty , czyli 2 * 3 wierzchołków. Jednakże jak możecie zauważyć, te trójkąty się powtarzają! W przypadku jednej ściany, czy też sześcianu - to nie jest duży problem. Ale wyobraźcie sobie że nie chcemy wyrenderować jednej kostki, a skomplikowany model budynku. Tam tych wierzchołków jest więcej, a to oznacza, że i duplikatów będzie więcej.

Indeksy

Rozwiązaniem naszego problemu są indeksy. Zamiast trzymać wierzchołki w porządku, w jakim będą budowane, możemy zapisać je wszystkie raz i zapamiętać na której pozycji w naszej tabeli leżą:

 
vertices: [
    [-1, -1, -1], //0
    [1, -1, -1], //1
    [-1, 1, -1], //2
    [1, 1, -1], //3

    [-1, -1, 1], //4
    [1, -1, 1], //5
    [-1, 1, 1], //6
    [1, 1, 1] // 8
]

Teraz potrzeba drugiej tabeli, która powie nam jak nasze trójkąty rysować. Tabela ta składa się z samych numerów co znacznie ułatwia sprawę:

 
indices: [
    1, 0, 3, // back
    3, 0, 2, 

    4, 5, 6, // front
    6, 5, 7,

    5, 1, 7, //left
    7, 1, 3,

    0, 4, 2, //right
    2, 4, 6, 

    0, 1, 4, //top
    4, 1, 5, 

    6, 7, 2, //bottom
    2, 7, 3
]

Te dwie tablice w sumie dają nasz model.

 
var layer = ...

var cube = {
    vertices: [],
    indices: []
};

var render = ...

Pytanie jakie się rodzi - Jak mamy teraz rysować nasz model? Zacznijmy od naszej funkcji render.

Funkcja render

Na chwilę obecną nasza funkcja render jedynie czyści ekran. Oprócz czyszczenia potrzebujemy jeszcze:

  • Przekształcić za pomocą macierzy wszystkie wierzchołki modelu. (Zauważmy, że przekształcamy pojedyńcze wierzchołki, a nie trójkąty - dzięki naszym optymalizacjom każde przekształcenie w każdej klatce wykonujemy jedynie 8 razy - bo 8 mamy wierzchołków).
  • Pobrać (w pętli) po 3 indeksy.
  • Pobrać odpowiednie wierzchołki.
  • Narysować 3 linie dla każdego trójkąta.

Póki co zajmijmy się trzema ostatnimi punktami:

 
var render = function() {
    layer.clear("#333");

    var vertices = [];

    ...

    for(var i = 0, len = cube.indices.length; i < len; i++) {
        var i1 = cube.indices[i++];
        var i2 = cube.indices[i++];
        var i3 = cube.indices[i];

        var v1 = vertices[i1];
        var v2 = vertices[i2];
        var v3 = vertices[i3];

        layer.strokeLine(v1.x, v1.y, v2.x, v2.y)
            .strokeLine(v2.x, v2.y, v3.x, v3.y)
            .strokeLine(v1.x, v1.y, v3.x, v3.y);
    }
};

Zapytacie - czemu bierzemy cube.indices a nie używamy cube.vertices? Dlatego, że w cube.vertices przechowujemy dane o wierzchołkach w formacie XYZ w przestrzeni lokalnej

Czym jest przestrzeń lokalna

Zazwyczaj gdy mowa jest o przestrzeni lokalnej, mamy na myśli taką przestrzeń, gdzie punkt [0, 0, 0] znajduje się dokładnie w środku modelu. I właśnie o ten punkt najczęściej obracany jest model. Czemu jednak wyróżniamy ją jako lokalną?

Załóżmy że chcemy wyrenderować 2 piłki. Każdą piłkę chcemy obracać wokół jej środka (czyli jej punktu [0, 0, 0] w przestrzeni lokalnej) i jednocześnie przesuwać po powierzchni boiska względem np. środka boiska (czyli punktu [0, 0, 0] w przestrzeni globalnej). Aby oszczędzić pamięć, trzymamy informację jedynie o jednym modelu piłki - ponieważ obie są identyczne. Te dwie piłki różnią się od siebie jedynie pozycją oraz rotacją. Czyli informacjami których używamy do przekształceń.

Słowo o macierzach

Macierze są naszą główną bronią, jakiej użyjemy aby wyrenderować sześcian. To dzięki nim będziemy w stanie obrócić model, przesunąć go o pewien wektor oraz zrzutować do przestrzeni ekranu (ang. screen space).

Zazwyczaj będziemy korzystać z macierzy 4x4 - gdyż używamy przekształceń na przestrzeni 3D, a nie każde przekształcenia (np. translacja czyli przesunięcie) nie może być zapisane jako macierz 3x3. Oprócz tego nasze wierzchołki (które możemy interpretować jako wektory 3D), możemy zapisać jako macierze 4x1 [X, Y, Z, 1]

Macierze możemy przechowywać w pamięci komputera jako tablice jednowymiarowe o rozmiarze Width*Height. Stwórzmy więc nową strukturę danych:

 
var Matrix = function(mat, width, height) {
    this.mat = mat;
    this.width = width;
    this.height = height;
};

Najważniejszą operacją jaką musimy wykonywać na macierzach jest mnożenie ich przez siebie Poprzez wymnażanie macierzy przez wektor , przekształcamy ten wektor (ponieważ tak jak napisałem wcześniej, wektor możemy interpretować jako macierz [4x1]).

Przypomnijmy sobie jak wygląda mnożenie macierzy:

e & g f & h
a b a*e + b*g a*f + b*h
c d c*e + d*g c*f + d*h

W przypadku wektora, wyglądałoby to tak:

x & y
a b a*x + b*y
c d c*x + d*y

Napiszmy więc naszą funkję mnożącą macierz przez inną macierz

 
Matrix.prototype = {
    mul: function(other) {
         var out = [];
         for(var i = 0; i < this.width * other.height; i++) out.push(0);

         for(var x = 0; x < this.width; x++) {
             for(var y = 0; y < other.height; y++) {
                 var sum = 0;
                 var outI = y + other.height * x;
                 for(var z = 0; z < other.width; z++) {
                     var mI = z + this.width * x;
                     var oI = y + other.height * z;
                     sum += this.mat[mI] * other.mat[oI];
                 }
                 out[outI] = sum;
             }
         }

         return new Matrix(out, this.width, other.height);
     }
};

Macierz projekcji

Mając naszą klasę macierzy jesteśmy w stanie zaprojektować naszą pierwszą macierz. Będzie to macierz projekcji. Macierz projekcji bierze nasze wierzchołki i przekształca je do przestrzeni ekranu

Dla potrzeb tego artykułu pokażę macierz ortagonalną - w efekcie nie będzie widać różnicy pomiędzy obiektem oddalonym od wirtualnej “kamery”. Inną macierzą jest macierz perspektywy - najczęściej używana w np. grach komputerowych.

 
var Ortho = function(left, right, top, bottom, near, far) {
    return new Matrix([
            2 / (right - left), 0 , 0, -(right + left)/(right - left),
            0, 2 / (top - bottom), 0, -(top + bottom) / (top - bottom),
            0, 0, -2 / (far - near), -(far + near) / (far - near),
            0, 0, 0, 1
    ], 4, 4);
};

Rozmiary left, right, top i bottom określają wymiary ekranu. Gdybyśmy podali tu odpowiednio 0, 800, 0, 600, to na ekranie kostka o wymiarach [-1, -1, -1] do [1, 1, 1] miała by rozmiar 2px*2px.

Near i far określa granice wyświetlania. Jeśli odległość wierzchołka od “kamery” będzie większa od far lub mniejsza od near - dany wierzchołek nie zostanie narysowany.

Przekształcenia wierzchołków

Mając naszą macierz projekcji już prawie jesteśmy w stanie wyrenderować naszą kostkę na ekranie. Póki co przemnóżmy nasze wierzchołki przez nią.

 
var toVec4 = function(vec3) {
    return new Matrix([ vec3[0], vec3[1], vec3[2], 1.0], 4, 1);
};

var render = function() {
    layer.clear("#333");

    var vertices = [];

    var proj = Ortho(-8, 8, 6, -6, 0.01, 100.0);

    for(var i in cube.vertices) {
        vertices[i] = toVec4(cube.vertices[i]);
        vertices[i] = proj.mul(vertices[i]);
    }

    for(var i = 0, len = cube.indices.length; i < len; i++) {
        ...
    }
};

Problemem jest fakt, że w chwili obecnej nasze mnożenie “wypluje” macierz 4x1. Tymczasem potrzebujemy wektora 2D. Nasza macierz 4x1 jest teraz w przestrzeni od [-1, -1, -1] do [1, 1, 1]. Napiszmy więc kolejną funkcję która przekalkuluje naszą macierz do koordynatów 2D.

 
var bound = function(x, min, max) {
    return Math.max(min, Math.min(max, Math.round(x)));
};

var toViewPort = function(vec4, width, height) {
    var x = vec4.mat[0];
    var y = vec4.mat[1];
    var z = vec4.mat[2];

    x /= z;
    y /= z;

    x = width * ( x + 1.0) / 2.0;
    y = height * (1.0 - (( y + 1.0 ) /2.0));

    return  {
        x: bound(x, 0, width),
        y: bound(y, 0, height)
    };
};

Teraz możemy użyć tej funkcji i wyrenderować nasz sześcian!

 
vertices[i] = toVec4(cube.vertices[i]);
vertices[i] = proj.mul(vertices[i]);
vertices[i] = toViewPort(vertices[i], 800, 600);

Ponieważ użyliśmy macierzy ortagonalnej, nasz sześcian powinien wyświetlić się jako kwadrat. Dzieje się tak, gdyż nasza macierz nie bierze pod uwagę odległości od kamery - ściana bliższa ma ten sam rozmiar na ekranie co ściana w oddali.

Aby zobaczyć “efekt 3D” powinniśmy obrócić naszą kostkę. W tym celu wykorzystamy macierz modelu

Macierz modelu

Macierz modelu to macierz, która przekształca model z przestrzeni lokalnej do przestrzeni globalnej. Do tej pory nie ruszaliśmy naszej kostki, przez co jej wierzchołki miały te same koordynaty w obu przestrzeniach. Obecnie chcemy nasz sześcian obrócić więc musimy te wierzchołki przekształcić

W tym celu użyjemy nowej macierzy - macierzy rotacji o oś Y.

 
var RotateY = function(angle) {
    return new Matrix([
            Math.cos(angle), 0, Math.sin(angle), 0,
            0, 1, 0, 0,
            -Math.sin(angle), 0, Math.cos(angle), 0,
            0, 0, 0, 1
    ], 4, 4);
};

Teraz jesteśmy w stanie użyć naszej funkcji aby stworzyć odpowiedni obrót o dany kąt.

 
var ang = 0;
var render = function() {
    ...
    var proj = ...
    var model = RotateY(ang);

    ang += 0.01;
}

Do tej pory mnożyliśmy naszą macierz projekcji przez wektor. Teraz jednak stworzymy nową macierz - macierz modelProj która będzie złożeniem macierzy modelu i macierzy projekcji. Następnie każdy wierzchołek będziemy przekształcać za pomocą nowo powstałej macierzy.

 
ang += 0.01;

var modelProj = proj.mul(model); // Bardzo ważna jest kolejność. proj.mul(model) != model.mul(proj)

...

vertices[i] = modelProj.mul(vertices[i]);

A gdybyśmy chcieli dodatkowo przesunąć kostkę o 2 jednostki w lewo lub w prawo? Do tego służy kolejna macierz:

 
var Translate = function(x, y, z) {
    return new Matrix([
            1, 0, 0, x,
            0, 1, 0, y,
            0, 0, 1, z,
            0, 0, 0, 1
    ], 4, 4);
};

...

var rotate = RotateY(ang);
var translate = Translate(2, 0, 0);

var model = rotate.mul(translate); //Jako ćwiczenie możecie zamienić mnożenie i zobaczyć jakie ma konsekwencje.

Cieszę się, że dotarliście do końca tego artykułu. Cały kod źródłowy jest dostępny tutaj