Some time ago I read the @lisyarus' post about his UI library. In his blog post he compares existing UI frameworks, analyses reasons why they don't work to them, and shows how he created his own library to build in-game UI.
His blog post immediately inspired me: how would I build my UI library?
I have to make a confession, I don't like OOP.
Don't get me wrong, I use objects a lot, but I just don't like the idea of orienting my code around them. Dynamic dispatch, inheritance hierarchy, interfaces, it's just not for me. What I like to do is just get the data, and transform the data.
But don't worry, the data oriented stuff doesn't contradict or prohibit the OOP stuff, so you can keep all the features of the language you want! I will even suggest the places where you can use them.
I also ask you to put aside any dogma about what the good code is, and think of this as an experiment, where I use the things that I find useful, okay?
Most of the UI libraries out there base their structure on the OOP patterns. The UI elements are naturally hierarchical, so it's natural to use inheritance to represent structure, right?
For example, containers are groups of elements, so they can have children, and those children can be any element out there. They can be other groups, they can be shapes, or text, or whatever else.
So you might want to write something like this:
class ui_element
{
// Virtual calls and common data
};
class ui_group : public ui_element
{
ui_element *parent;
array<ui_element *> children;
};
class ui_shape : public ui_element
{
ui_element *parent;
vector4 color;
};
I will argue that this is not what I want. Look at the picture below:
Note that this is not an inheritance hierarchy, it's a completely different hierarchy, so it doesn't have to be exactly like this.
Ok, but how would you build this DOD way?
The first observation I want to make is that we actually have two completely different "classes" of UI elements: visible elements and groups. We don't render groups, we just combine elements together and apply a common transformation to them, whereas visible elements have no children, but should be drawn.
The second observation, or rather a question I want to ask, is "what is the most common operation in the UI"? The answer to this question will determine what we will build our architecture around. These operations are drawing and updating animations. These are the operations that will happen every frame, so they should be quick and easy to do.
I refer to this talk here https://youtu.be/yy8jQgmhbAU, where the author talks about these kinds of operations and how to do them in the data oriented design.
First, I will create a ui::system structure that will store all the data:
struct system
{
allocator ui_allocator;
};
void update(system *s);
void draw(system *s);I provide the system with an allocator. I also define the two operations that I talked about.
Now let's create some ui elements:
struct element
{
vector2 position;
vector2 scale;
float32 rotation;
vector4 color;
element *parent;
array<element *> children;
};
struct system
{
allocator ui_allocator;
element root;
array<element> groups;
array<element> shapes;
};Note that I separate groups not by tags or types, but by the fact that they lie in the groups array or the shapes array!
This is common practice in DOD, you could see it a lot. Why combine elements in the single array and dispatch them later,
when we can put them in separate arrays and remove the dispatching altogether!
I've also added a root element, it's for my own convenience, I'll consider that UI always has a root, which is a group with an identity transform, and all elements in the arrays have parents. This eliminates branching in the update loops, and makes the code easier to understand.
You might ask me why groups array and shapes arrays store that same type? Looks like shapes will store children and groups will store color, - but I just do not see it as a problem RIGHT NOW. It's not about type purity, it's just about memory footprint and data compression. We will work on the compression later. Let's get this thing working first!
Drawing is easy, remember I said that all groups are invisible? Let's just assume that all shapes are 100x100 squares for now:
void draw(system *s)
{
for (usize i = 0; i < s->shapes.size(); i++)
{
element *e = s->shapes.data() + i;
auto rectangle = rectangle2::from_center_size(e->position, 100, 100);
// Where are the MVC matrices???
draw_rectangle(model, view, projection, rectangle, e->color); // @todo: implement this with OpenGL
}
}Oh no! I forgot about nested transforms of the hierarchy! Let's fix that. To do this, I will cache two matrices.
transform will be the matrix that transforms from the coordinate system of the element to that of its parent.
transform_to_root will be the matrix that transforms from the coordinate system of the element to that of the root.
Code to update these caches:
struct element
{
// ...
matrix4 transform;
matrix4 transform_to_root;
};void update_transform(element *e)
{
e->transform =
rotated_z(to_radians(e->rotation),
scaled(e->scale,
translated(e->position,
matrix4::identity())));
}
void update_transforms(system *s)
{
for (usize i = 0; i < s->groups.size(); i++)
{
element *e = s->groups.data() + i;
update_transform(e);
e->transform_to_root = e->parent->transform_to_root * e->transform;
}
for (usize i = 0; i < s->shapes.size(); i++)
{
element *e = s->shapes.data() + i;
update_transform(e);
e->transform_to_root = e->parent->transform_to_root * e->transform;
}
}
void update(system *s)
{
update_transforms(s);
}Ok, I will pass transform_to_root as the model matrix, but what to do with view and projection?
View is basically the matrix of a camera, and since we do not have any cameras in UI, I will pass identity matrix.
The projection matrix is a bit more interesing, the purpose of the projection matrix is to take coordinates from whatever the view matrix returns and fit them into NDC (Normalized Device Coordinates).
In OpenGL NDC go from -1 to 1 on the X-axis, and from -1 to 1 on the Y-axis, but most of the time in UI the Y-axis is reversed and origin is placed in the upper left corner, so it looks like this:
So let's make a projection matrix:
void draw(system *s)
{
auto projection =
math::translated(V3(-1, 1, 0),
math::scaled(V3(2.0/context->letterbox_width, -2.0/context->letterbox_height, 1),
math::matrix4::identity()));
for (usize i = 0; i < s->shapes.size(); i++)
{
element *e = s->shapes.data() + i;
auto model = e->transform_to_root;
auto view = math::matrix::identity();
auto rect = rectangle2::from_center_size(V2(0, 0), 100, 100);
draw_rectangle(model, view, projection, rect, e->color); // @todo: implement this with OpenGL
}
}Now we can easily add width and height to our shapes, and draw rectangles of any size:
auto rect = rectangle2::from_center_size(V2(0, 0), e->width, e->height);I'm going to build a UI in the init function (which is called before the game loop). For this I have created a few of functions like this:
element *make_group(system *s, element *parent)
{
element *result = s->groups.push();
result->scale = V2(1, 1);
result->parent = parent;
parent->children.push(result);
return result;
}
element *make_shape(system *s, element *parent)
{
element *result = s->shapes.push();
result->scale = V2(1, 1);
result->parent = parent;
parent->children.push(result);
return result;
}Then call them like this:
ui::system ui = {};
void initialize_game()
{
// Do not forget to initialize ui.ui_allocator and ui.root first!
auto group_1 = ui::make_group(&ui, &ui.root);
auto shape_1 = ui::make_shape(&gs->ui, group_1);
shape_1->position = V2(500, 600);
shape_1->rotation = 20.f;
shape_1->color = V4(0.9, 0.4, 0.2, 1.0);
auto shape_2 = ui::make_shape(&gs->ui, group_1);
shape_2->position.xy = V2(300, 600);
shape_2->width = 300.f;
shape_2->height = 20.f;
shape_2->rotation = 45.f;
shape_2->color = V4(0.3, 0.6, 0.4, 1.0);
auto shape_3 = ui::make_shape(&gs->ui, &gs->ui.root);
shape_3->position.xy = V2(400, 200);
shape_3->scale.xy = V2(2, 2);
shape_3->rotation = 70.f;
shape_3->color = V4(0.3, 0.3, 0.8, 1.0);
}And finally, we can draw them in the game loop!
while(true)
{
// Draw the game here.
ui::update(&ui);
ui::draw(&ui);
}We should see something like this:
You may have noticed that my code has a few oddities, so I will address them here.
- The
ui::elementtype is the only one out there with all the data needed for everything? Isn't that expensive?
Yes, it is. And I don't expect it to stay the same, I will certainly separate the group and shape types, but at this stage of development it's ok to leave them as they are.
- The
update_transformsfunction depends on order of elements in the arrays!
Yes, it does. Ideally you would do the BFS (Breadth First Search) algorithm there, but since we have no way to move elements in the arrays, I will leave it like that FOR NOW! When I will do reordering, element removal, UI editor, I will certainly address this issue.
- It will be really hard to do event propagation, clicking, etc.
I think it will be really easy, actually, I'll show you in the next blog post, stay tuned! :)
- "Data Oriented Design in C++", YouTube video: https://youtu.be/rX0ItVEVjHc
- "OOP Is Dead, Long Live Data-oriented Design", YouTube video: https://youtu.be/yy8jQgmhbAU
- "How not to design a UI library", blog post: https://lisyarus.github.io/blog/programming/2023/03/11/how-not-to-ui.html
Part 2: https://gist.github.com/JustSlavic/fd72162bb22cee7be6b002418ed69062