Runtime texture atlas generation

Texture atlas – what is it

Texture atlas is a image containing collections of sub-images. Each of these sub-images representing a texture.

Application can use multiple texture atlases.

Why

Rendering a texture require setting it as active. This operation is time consuming. Since atlas is a single texture containing many of different sub-textures, active texture switches are much rarer. Renderer use region of texture atlas to render concrete texture.

Reducing OpenGL state changes, can give significant performance gains.

Runtime texture atlas generation

Texture atlas can be pre-generated. There are many tools to do it. Usually tool generates also some meta-data file containing coordinates of each sub-texture inside atlas.

Texture atlas can also be generated runtime. Images representing a texture are copied into single large, in-memory image.

Pros of runtime generation

Simplified development process

Images can be added to project (or resource file) immediately. In case of pre-generated texture atlas, image has to be merged in to atlas each time artist submit one.

Image size

Texture size has to be equal to power of two. If not, render process may suffer performance hit. Some OpenGL implementation do not load image at all. Image placed in texture atlas can be any size (Smaller then atlas size).

Optimizations

There are hundreds of different devices. Some of them differ in screen resolution, maximum texture size, etc. Building texture atlas during runtime gives opportunity to optimize textures. On low-end devices, that do not use high-resolution textures, images can be down-sized. So textures would better suited for the particular machine.

Size of texture atlas can be adapted for the machine. OpenGL function glGetIntegerv(GL_MAX_TEXTURE_SIZE …) returns maximum size of the texture. Value can be used to set atlas dimension.

Cons

Creation takes time

Obviously all images merged into texture has to be loaded into memory, and printed into single large one. Additional image resizing also takes extra time.

Implementation description

Runtime texture atlas generation process consists of two phases: * Calculating placement of each sub-texture. * „Painting” sub-textures on atlas texture.

In this post, I will describe only first phase.

Canvas

Texture atlas texture must have dimensions. These values can be based on machine’s GL_MAX_TEXTURE_SIZE. The safest are 1024×1024. All devices should support these.

The canvas on which sub-textures are going to be placed is represented by rectangle:

{ x= 0, y = 0, width = 1024, hight = 1024}

Lets define a list, collection or whatever, which will contain rectangles of free space on canvas. Initially collection will contain single rectangle. The one describing whole canvas.

Divide and conquer

The canvas is just a big rectangle. Image which is going to be added to atlas is smaller rectangle. Smaller subtracted from bigger give surface that can be described as two rectangles:
img1
Sub-texture (green background) was added. Space left (blue rectangle, and red rectangle).

Now. The collections of canvas free space has to be changed. Rectangle which represents whole canvas has to be removed. And two new rectangles has to be add.

Sub-texture coordinates has to be stored somewhere.

Lets add another sub-texture (black background).

img3

Another two rectangles representing free space ware created (orange and white background)

Horizontal or vertical

Surface after subtraction can be divided in two ways. Horizontal or vertical.

img2

Choose one better suited for your textures.

Algorithm

As you may figure it out. Algorithm is quite simple:

  • Get your sub-texture’s dimensions.
  • Find free rectangle that fits sub-texture dimensions.
  • Subtract sub-textures’s dimensions from found rectangle. The result of the subtraction will be two rectangles
  • Store sub-texture coordinates (rectangle) in separate collection.
  • Remove found rectangle from list.
  • Add two new rectangles (result of subtraction) to list.
  • If image does not fit into texture atlas, generate new texture atlas
  • Repeat for each sub-texture

Matching

Whole process of finding fitting rectangle can be optimized by sorting the list.

Padding

Leave at least 1 pixel space between sub-textures. OpenGL does not work based on pixels, but on normalized values. That means some inaccuracies may be added, and „leaks” between textures can be visible.

Coordinates

The result of atlas generation process, should be list of rectangles – coordinates of each sub-texture. The list has to be transformed in to OpenGL texture coordinates list.

Result

example

Tips

  • Coordinate systems can be different. OpenGL’s {0,0} point lays in left, bottom corner. Qt for example, using top left.
  • Sub-texture itself can be atlas (Inception?). For example texture containing font glyphs. sub-sub-texture coordinates has to recalculated.
Reklamy

Creating service container using variadic templates

Let’s have two simple services:

struct T1{
void process(){
cout << "processing T1" << endl;
}
};

struct T2 {
void process() {
cout << "processing T2" << endl;
}
};

Note, they share similar interface. But for compiler these structs are completely unrelated.

Lets say, we want to create a container, which will store our services, and allows to call each service methods.

We want something like this:

auto con = make_container(T1{},T1{}, T2{});
con.process();

>processing T1
>processing T1
>processing T2

 

Of course this could be done by adding a base abstract class which define a common interface for our services. Next, a container – vector for example – for storing (smart) pointers to services. And finally, a class that encapsulate all.

struct storage {
 void process(){
  for (auto &base : container)
    base->process();
 }

private:

std::vector<std::unique_ptr<ServiceBase>> container;
};

This solution is perfectly fine, but:

Sometimes services are defined at compile time, and will not be changed during runtime. Vector’s runtime capabilities are unnecessary.

Services are allocated separately on heap, which may not be cache-friendly.

Solution:


template<typename ...Args>
struct Container{};

template <>
struct Container<>{

    void process(){
    }
};

template<typename T, typename ...Args>
struct Container<T, Args...> {

    Container(T _value, Args ... a) :
        value(_value), childs(a...)
    {}

    void process(){
        value.process();
        childs.process();
    }

    T value;
    Container<Args...> childs;
};

template<typename ...Args>
Container<Args...> make_container(Args ... args){
    return Container<Args...>(args...);
}

This code was inspired by some std::tuple implementations as saw recently.

Instead of recursive inheritance generation, which is used in tuple, this code recursively generates type of „childs” member.

After all variadic magic, compiler generated something like this:

(Pseudocode)

struct Container1{
void process(){}; // empty
}

struct Container2{
  void process() {
     // do my stuff
     childs.process();
  };
  Container1 childs;
}

struct Container3{
  void process() {
     // do my stuff
     childs.process();
  };
  Container2 childs;
}

And more details (pseudocode):

template<typename T>
struct Container1{
void process(){
  value.process();
};
T value;
}

template<typename T, typename C>
struct Container2{
  void process() {
     value.process();
     childs.process();
  };
  Container1<C> childs;
  T value;
}

template<typename T, typename C>
struct Container3{
  void process() {
     value.process();
     childs.process();
  };
  Container2<C> childs;
  T value;
}

void test(){
  auto container3 = create_container3(....);
  container3.process();
}

The really cool thing in this solution is its cache friendliness. All of the data of these structures are located close to each other.

If services implements copy constructors – container3 can be copied.

As long as services share same interface – container can hold any (well, reasonable) number of them, regardless of type.

Happy coding

How to draw point/circle/ellipse using OpenGL ES 2.0 GLSL

I have spend a quite some time experimenting with different solutions. Tried GL_POINT thing – didn’t work as i expected.

First, setup your render process to draw a quad. I do not want to go into details. Maybe I’ll cover 2d OpenGL ES rendering another time.

After setup, call glDrawElements.
As you see, I’m using GL_TRIANGLE_STRIP to draw quad.

glDrawElements(GL_TRIANGLE_STRIP, 4,
GL_UNSIGNED_SHORT, (void *)0);

My vertex shader:

#ifdef GL_ES
// Set default precision to medium
precision mediump int;
precision mediump float;
#endif

uniform mat4 mvp_matrix;
uniform vec4 u_color;

attribute vec4 a_position;
attribute vec2 a_texcoord;

varying vec4 v_color;
varying vec2 v_texcoord;

void main()
{
gl_Position = mvp_matrix * a_position;
v_color = u_color;
v_texcoord = a_texcoord;
}

u_color – I’m using this uniform to define point color.
v_color – varying shared between vertex and fragment shader. Used to transport color value to fragment shader.
a_texcoord – an attribute. Its value is determined on the basis of VBO contents.
v_textcoord – a variable used to transport texture coordinates to fragment shader.

Texture should be disabled before glDrawElements call;
Use glBindTexture(GL_TEXTURE_2D, 0);

Despite no active texture, shader will receive valid texture coordinates;

Fragment shader:


#ifdef GL_ES
// Set default precision to medium
precision mediump int;
precision mediump float;
#endif

varying vec4 v_color;
varying vec2 v_texcoord;

void main()
{
float l = length(v_texcoord - vec2(0.5, 0.5));

if (l > 0.5)
discard;

gl_FragColor = v_color;
}

Here is the magic.

v_texcoord isn’t just copied from VBO. Value is interpolated for each fragment shader call.

float l = length(v_texcoord - vec2(0.5, 0.5));

variable l contains distance of current rendered quad pixel from center of quad.
Because texture coordinates are normalized ( values are in the range 0.0 and 1.0) 0.5,0.5 represents center of quad.

The function /length/ is OpenGL ES2 buildin. Calculates distance between two vectors.

If distance between currently rendered pixel and center of quad is more then 0.5 pixel is discarded. When distance is less or equal 0.5, fragment is rendered using color stored in v_Color;

point_rendering

I hope this picture help to understand how it works.

Blue are texture coordinates.
Pink area is rendered using u_color/v_color.
White space where fragment shader was discarded.
Green lines – distance between fragment coordinates and quad center. Calculated by length function.

Pros and cons of this solution:

Pros:

  • Looks same regardless of size.
  • Shader can be easily modified to produce blured „nova” effect.
  • Works both on mobile and desktop

Cons:

  • No antialiasing – sharp edges.

Linux – serial port loopback

Sometimes, usually when programming embedded systems there is a need to test pair of programs communicating each other via serial port.

Serial ports loopback can be created using socat command:

arek@arek-toshiba:~$ socat -d -d pty,raw,echo=0 pty,raw,echo=0
2016/02/05 21:13:30 socat[7266] N PTY is /dev/pts/0
2016/02/05 21:13:30 socat[7266] N PTY is /dev/pts/17
2016/02/05 21:13:30 socat[7266] N starting data transfer loop with FDs [5,5] and [7,7]

Do data sent to /dev/pts/0 will appear on /dev/pts/17 and vice versa.

Really cool.

 

Ubuntu 15.10 vs good old Huawei E173

They don’t like each other.

Surprisingly, modem previously worked properly on Ubuntu 14.04.

Ubuntu has usb_modswitch installed by default. Unfortunately something changed, and tty’s are not created.

I found workaround:
sudo usb_modeswitch -v 12d1 -p 1446 -J
Should help.

MongoDb i C#

W dzisiejszym wpisie postaram się przybliżyć bazę MongoDB i sposób korzystania z niej za pomocą C#. Nie widzę jakiegoś wielkiego zainteresowania tą bazą w polskiej blogosferze, a szkoda.

MongoDb jest obecnie chyba najbardziej popularną bazą danych NoSQL.
Co to jest NoSQL? Jak sama nazwa wskazuje jest to silnik który nie używa SQLa do zapytań.
Po co komu baza, która posiada jakiś autorski dialekt zapytań, i nie korzysta z dobrze znanej składni SQLa? Otóż są zastosowania w których bazy NoSQL sprawują doskonale. Wszędzie, gdzie mamy dużo (lub bardzo dużo) danych, mało (najlepiej w ogóle) relacji, warto zastanowić się nad Mongo.

Trzeba zaznaczyć, że MongoDB nie jest „silver bullet”, próba zastąpienia relacyjnej bazy danych w systemie mającym relacje między tablicami zakończy się wielkim rozczarowaniem uzyskaną wydajnością.

Tworzeniem i wsparciem silnika MongoDb zajmuje się firma 10gen. I robi to bardzo dobrze. Dostępne są drivery dla wszystkich liczących się języków programowania, driver dla .NET jest przyzwoicie napisany. Kilka miesięcy temu zostało dodane wsparcie dla Linq. Kod pozwalający na połączenie z bazą, dodanie kilku dokumentów do kolekcji, to zaledwie kilka linii.

Wspomniałem już, że Mongo nie jest bazą relacyjną. Co prawda, na upartego można próbować na piechotę łączyć dane z różnych kolekcji, ale wydajność takich operacji będzie niska.

Dane przechowywane są w formacie JSON, a dokładnie w klonie tego formatu pozwalającym na zapis danych binarnych, czyli BSON.
Dokumenty BSON są przechowywane we wspomnianych już kolekcjach. Na upartego można porównać dokument Mongo z rekordem relacyjnej bazy danych, a kolekcję z tablicą. I tu trzeba wspomnieć o rzeczy bardzo ważnej – kolekcje nie posiadają zadanego sztywnego schematu, można w nich przechowywać dowolne dokumenty BSON.

Niestety Mongo posiada także i ograniczenia. Uruchomione na 32-bitowym systemie, pozwala na przechowanie nieco ponad 2GB danych.
Jest to związane ze sposobem, w jaki dane są zapisywane w plikach bazy. Mongo mapuje plik w pamięci, a 32-bitowy system operacyjny nie jest w stanie zaadresować większych obszarów. Tak więc, jeśli baza przekroczy 2GB (cała baza, czyli dane + indeksy), mongo zakończy pracę mało przyjemnym błędem.

Jeśli komuś chodzi po głowie deployment bazy wraz z desktopowym klientem, niech się lepiej dobrze zastanowi.

Uruchomienie mongo jest bardzo proste:

mongod --dbpath "sciezka do folderu z danymi" --logpath "sciezka do folderu na logi"

aby zainstalować mongo jako usługę systemową należy dodać parametr –install do tych powyżej
Zainstalowaną usługę warto uruchomić:

net start MongoDB

Polecenia trzeba wykonywać za pomocą linii komend z uprawieniami administracyjnymi.

Jak już wspomniałem, dokument mongo nie ma ustalonego schematu. Do kolekcji można dodać dowolne dane, byle były opakowane w JSON.

Wszystko pięknie, ale czasami wygodnie jest zdefiniować sobie klasę danych, która będzie automatycznie serializowana i deserializowana, tak jak robią to nHibernate, czy Entity Framework.

Sterownik dla .NET zapewnia taką funkcjonalność.

pubic class KlasaA
{
  public ObjectId _id {get; set;}
  public List<KlasaB> ObiektyKlasyB {get; set;}
}

Jak widać, dane mogą być zagnieżdżone. KlasaA może zawierać listę obiektów klasy B

KlasaA, jako „root” powinna mieć zdefiniowane pole które będzie identyfikatorem. Najprościej jest dodać właściwość _id typu ObjectId. Ale za pomocą atrybutów można wyznaczyć praktycznie dowolne pole aby było identyfikatorem.

Atrybutów którymi można udekorować klasy i ich właściwości jest znacznie więcej, znajdują one się w przestrzeni nazw MongoDB.Bson.Serialization.Attributes. Bardzo przydatnym atrybutem jest BsonIgnoreExtraElements, dzięki któremu nie jest wyrzucany wyjątek, kiedy klasa nie zawiera pola które znajduje się dokumencie JSON.

Połączenie z bazą:

var connectionString = "mongodb://localhost";
var client = new MongoClient(connectionString);
var server = client.GetServer();
var database = server.GetDatabase("NAZWA_BAZY_DANYCH");

Baz danych możne być oczywiście kilka na serwerze.

Zdefiniuję teraz prostą encję:

public class User
{
  public ObjectId _id {get; set;}
  public string Name {get; set;}
}

Pobieramy kolekcję:

var users = database.GetCollection<User>("Users");

Dodajemy dokument do kolekcji

var user = new User() {Name="Arek"};
users.Insert(user);

Zapytanie:

var arki = users.AsQueryable().Where(u=> u == "Arek");

Niestety, na dzień dzisiejszy nie wszystkie funkcje LINQ są wspierane. Aby na
przykład pogrupować dokumenty trzeba się trochę nagimnastykować. Trzeba skorzystać z JavaScriptu. Takie zapytania to dosyć obszerny temat, postaram się je opisać w osobnym wpisie.

Jeśli pola używamy jako kryterium wyszukiwania, warto założyć na nim indeks. Poprawi to znacznie wydajność zapytań.

Robi się to bardzo łatwo:

users.EnsureIndex("Name");

To wszystko jeśli chodzi o podstawowe informacje. Mam nadzieję, że wystarczą do uruchomienia i rozpoczęcia eksperymentów z Mongo. A kolejnej notce omówię
grupowanie danych, i prace z klasę BsonDocument.

Hyper-V vs VirtualBox

Zainstalowałem Windows 8.

Po przeczytaniu kilku entuzjastycznych postów o Hyper-V uruchomiłem tą opcję w systemie.
Niestety nie miałem czasu, aby się nią pobawić. Do pracy używam na co dzień VirtualBox, którego sobie bardzo chwalę.

Zdziwiłem się „lekko”, kiedy po uruchomieniu Hyper-V VirtualBox zaczął rzucać komunikatami błędów. Jeszcze bardziej się zdziwiłem, kiedy okazało się, że wcale nie jest tak prosto wyłączyć Hyper-V.

Ale znalazłem polecenie które załatwiło sprawę (cmd.exe uruchom jako administrator):

dism.exe /Online /Disable-Feature:Microsoft-Hyper-V /All

PS. Hyper-V „kradnie” sprzętowe wsparcie procesora dla wirtualizacji. VirtualBox próbuje uruchamiać wirtualne maszyny z takim wsparciem, nie znajduje go i sypie błędami.