A text editor on a game engine's UI (part 1): drawing text and storing it as lines
How ColumbaEngine draws a string with FreeType, a glyph atlas and a pen, and why its text editor stores the document as a vector of lines instead of one std::string.
Drawing text with the engine: glyphs, a pen and measureText
I made my own game engine, and the more I worked on its script integration, the more polished it felt. At some point a thought came: could I replace my code editor with one made with my own engine? I should have all the pieces to build one. So I began to explore how to make a text editor, and what should go into it.
How does one go about building a multi-line editor, with lots of features (like wrapping, UTF-8 cursors and grouped undo), on top of a game engine’s ECS UI that only had a single-line text input?
The first step is to write something on the screen.
My engine is quite low level, and SDL is its only graphical API. SDL can draw rectangles and textures, but it has no idea what a letter is. To draw a character, we first need to know how it is drawn, what its shape is. A good solution already exists for that: fonts.
Fonts: characters’ shapes stored as outlines
A font is a file, usually a .ttf, for TrueType. Its idea is simple: it does not store pictures of letters, it stores outlines. Each character is a closed shape described by curves (quadratic Bézier curves), as numbers.
Why is it done this way? A picture of an a at 12 pixels is blurry at 60. An outline has no size: you scale it to the size you want, and only then turn it into pixels. One small file serves every size. And because the format is standard, any font you find can be used.
Besides outlines, the file holds tables with what a text needs. A table maps a Unicode code point to the number of its glyph (cmap). Another holds each glyph’s outline (glyf). Others give how far to move after a glyph (the advance, in hmtx) and the kerning of pairs like AV, which sit closer than their advances say (kern).
Reading these tables by hand is a project on its own, so the engine uses FreeType, a library that does it. The steps, in /src/Engine/UI/fontatlas.cpp, are:
FT_New_Faceopens the font file.FT_Set_Pixel_Sizeschooses the size in pixels.FT_Get_Char_Indexturns a code point into a glyph number.FT_Load_GlyphwithFT_LOAD_RENDERfills the outline and gives back a bitmap: a small grey image where each pixel says how much ink covers it, from 0 to 255. It also gives the numbers that place that bitmap: the bearing and the advance.
That bitmap is something SDL can use: a texture. We now have one picture of a letter at one size.
One string, one glyph at a time
A line of text is many letters, so the engine has to keep their pictures somewhere and put them side by side.
To put them side by side, the engine uses a pen: an x position on the line, where the next letter goes. It starts at 0, on the left of the text. The letters stand on one shared line, the baseline: an ‘e’ sits on it, and a ‘g’ hangs below it. The font also gives its ascender, the height of its tallest letters above the baseline, so the baseline of a line of text sits that far below the line’s top.
The engine rasterises the characters it needs once, with FreeType as just described, into one big single-channel image: the atlas (1024 by 1024 pixels at a pixel ratio of 1). For each character the atlas keeps a record, GlyphInfo in /src/Engine/UI/fontatlas.h, with the numbers that place it: its size, its bearing (how far the picture sits from the pen, right and up), its advance (how far the pen moves after it) and its position in the atlas as UV coordinates.
To draw a string, the engine walks over its code points, decoded from UTF-8, and moves the pen along. For each character:
- If the font has kerning for the pair (previous character, this one), the pen first moves by that amount.
- The engine places one textured rectangle for the glyph at
pen + bearing.xhorizontally, andascender - bearing.ybelow the top of the line, so that all letters share a baseline. - The pen moves right by the glyph’s
advance, plus the letter spacing if there is any, all times the scale.
A space has no picture. It only moves the pen. A \n moves the pen back to 0 and one line down, and the line height comes from the font.
The trick is that every character is drawn from the same atlas. The GPU does not have to load a different texture for each letter: it keeps one texture bound and only the UV coordinates change from one glyph to the next. The two l of Hello are the same atlas entry, looked up twice.
The layout is not redone every frame either. The engine keeps the glyph rectangles it computed for a text, relative to the text’s position, and rebuilds them only when the text changes. Moving the text only reapplies its position.
The pen walk has to be run by something, for every text on the screen, and run again when a text changes. My engine has something for this purpose: TTFText. It is a component that holds the text to show and the font to render it with: a text, a fontPath, a scale and colors, plus fields for wrapping, alignment and spacing, all listed in /src/Engine/Components/TTFText.pgcomp. Combined with a PositionComponent, which holds the position of the entity, TTFTextSystem has all it needs to draw a line of text anywhere on the screen.
TTFText only holds data. The work is done by TTFTextSystem, which owns every TTFText and reads its position. When a field changes, for example text, the setter sends a TTFTextChangedEvent, and the system rebuilds the glyphs of that entity with the pen walk above.
An editor also wants more than one colour in a line, for a heading or a piece of code, and one entity per coloured word would be a lot of entities. So the string given to TTFText is not only characters: it is read as markup. \n is a line break, and \c{r,g,b,a} starts a colour that holds until the next colour tag. The system splits the string into segments at the tags, and each glyph takes the colour of its segment. A coloured heading is one string with colour tags in it.
Measuring a string without drawing it
Drawing is not all an editor needs from the pen. To put the cursor after the fifth letter, or to know where a line must wrap, it needs to know where the pen ends, without drawing anything. TTFTextSystem has a function for this: measureText. It runs the same pen walk as the drawing, through the same function (layoutText, in /src/Engine/UI/ttftext.h), but it only counts. It returns a TextMetrics: the width of the widest line, the number of lines, the line height, and penEnd, the pen’s x after the last character. Because measuring and drawing share one layout pass, a measure can never disagree with what is drawn.
A string on screen is not a document
With these two tools I can draw any string and know its width. That is a lot, but look at what they take as input: one string. TTFText does not know what a document is. It does not know which line the cursor is on, where a paragraph ends, or what to do when you press Backspace. Everything the user does in an editor is an operation on a whole text: put the cursor here, select from there to here, undo.
So the editor needs its own way to hold the document, and to hand TTFText the right piece of it. How should the text be stored?
Storing the text: a vector of lines, not one string
Let’s first start by implementing the simplest way to store it, one std::string for the whole document, and a cursor that is an index into it. Typing inserts a character at the index. Backspace erases the one before it.
The usual objection is that an insert in the middle moves every byte after it. That is O(n), and it is true. But “true” does not say “too slow”. It depends on the size of the problem. So the first thing to do is to look at how big n is here.
The first text this editor has to hold is an article like this one. I write this site in the Writer, an app built on my engine’s UI, and the editor in this article is its editor. The articles on this site are 12 to 33 KB of Markdown. At that size, how much does moving bytes cost?
Measure the two costs
I timed two operations on one std::string: an insert near the start, and finding the last line by scanning for \n byte by byte. The text is made of lines of 400 bytes, a mid-sized paragraph. I used g++ -O2 on one machine (4 cores, Intel Core i7-1185G7, 3.0 GHz), and averaged over repeated runs. These are my timings:
One std::string | 80 KB | 1 MB | 50 MB |
|---|---|---|---|
| insert near the start | 0.8 µs | 12 µs | 3.5 ms |
| find the last line, byte by byte | 37 µs | 490 µs | 24 ms |
The reference is the frame. To keep editing feeling smooth, an operation on the text should never take longer than one frame at 60 fps, which is about 16,700 µs.
Read the first row. At 80 KB, an insert costs 0.8 µs. That is about a twenty-thousandth of a frame. Even at 1 MB it is 12 µs. Only at 50 MB does it grow to 3.5 ms, a fifth of a frame, for one letter. So moving bytes is a real cost on a big file, and not on a file as “small” as an article.
Now read the second row. Finding the last line costs 37 µs at 80 KB. That is already about forty-five times the insert, on the same string. And it is not paid once. A string does not remember where its lines start, so every time any part of the editor asks “where is line N?”, the scan starts again from the beginning. At 50 MB the scan takes 24 ms, almost a frame and a half. A faster scan, with memchr instead of a loop, is much quicker (2 µs instead of 37 at 80 KB, 3 ms instead of 24 at 50 MB), but it is still paid again on every lookup.
So the price that matters is not the insert. It is finding a line.
Who asks for a line?
Almost every part of the editor asks for lines:
- The cursor needs its line, to know its row and its column.
- Wrapping works on one line at a time.
- Markdown colouring reads a line and returns coloured spans.
- Drawing shows the lines in view.
- Undo remembers which lines changed.
A string does not know what a line is. For each of these, “line 40” means scanning from the start and counting newlines.
Why not add an index of line starts?
The natural fix keeps the string and adds a second array: the offset where each line starts. Then line 40 is one lookup.
That fix has two costs.
First, the index goes wrong on every edit. Insert one letter in line 3, and the start of every line after it moves by one. So the whole index has to be shifted on every edit. We removed the scan, and we added a loop over the lines to every keystroke.
Second, the index only tells you where a line starts. The string has no line objects to hand over, so each part that wants a line gets a pointer and a length into the string (in C++, a std::string_view). That view is only valid until the next edit, because an insert shifts or reallocates the bytes under it. So wrap, colouring and drawing must each look at a line and never keep it, and the index stays the only way to find the line.
For a part to keep a line, it would need its own copy. Copy every line out of the string, update the copies on every edit, and you hold the text twice: once as the string, and once as a vector of lines. The string is then only a second copy to keep in sync.
So a better design is to store the document as a vector of lines from the start.
The vector of lines
That is what the model does. In the TextBuffer class:
/src/Engine/UI/texteditor/textbuffer.h:115 - The document is a vector of lines, one std::string each, so line i is lines_[i] with no scanning.
std::vector<std::string> lines_;
There is one entry per logical line, and the newline is not stored. Line 40 is lines_[40]. There is no scan.
The parts of the editor get the lines directly:
/src/Engine/UI/texteditor/textbuffer.h:37-39 - Every part of the editor gets lines directly; the whole text is only joined by text(), e.g. on save.
void setText(const std::string& text);
std::string text() const;
const std::vector<std::string>& lines() const { return lines_; }
lines() returns a const reference, so wrap, colouring and drawing look at the lines and copy nothing. The whole text exists as one string only when you ask for it. text() joins the lines with \n, and that is what happens on save.
What does an edit cost now? An edit touches one entry, or a few. And how long is an entry? In Markdown a paragraph is one line, from a few hundred bytes to a few KB. So an insert moves bytes inside one short string, never inside the whole document. The O(n) from the objection is still there, but n is now the length of one line.
I timed the same text held as a vector of lines, with the same benchmark and the same 400-byte lines:
| 80 KB | 1 MB | 50 MB | |
|---|---|---|---|
| insert near the start: one string | 0.8 µs | 12 µs | 3.5 ms |
| insert near the start: vector of lines | 7 ns | 7 ns | 7 ns |
| find the last line: one string, byte by byte | 37 µs | 490 µs | 24 ms |
find the last line: vector of lines, lines_[n - 1] | 2 ns | 2 ns | 2 ns |
| Enter near the start: one string | 0.8 µs | 12 µs | 3.5 ms |
| Enter near the start: vector of lines (split a line) | 0.2 µs | 2.9 µs | 140 µs |
The insert costs the same at every size, because it only moves the bytes of one line. Reaching a line is an index, so it costs nothing. The main cost now is the creation of a new line. Splitting a line puts a new entry in the vector, and every entry after it shifts by one, so the cost grows with the number of lines. Even at 50 MB it takes 140 µs, well under a frame, and still less than an Enter on one string, which is an insert like any other.
What the big-file editors do instead
Editors for huge files cannot make this choice, because their lines and their documents are too big. They use other structures. I only name them here, as a pointer to what I may implement later. Each one makes an insert cheap in a huge text:
- A gap buffer is one array with a hole kept at the cursor. Typing fills the hole. Moving the cursor moves the hole.
- A piece table never changes the original text. New text is appended to a second buffer. The document is a list of pieces, and each piece says “this range of that buffer”.
- A rope is a balanced tree of string chunks. An insert or a delete touches one branch.
Look at what the three have in common. They answer “how to insert fast in a huge text”. That is the problem my timings say I do not have at 12 to 33 KB. They do not give you a line either: each one would need a line index on top. The vector of lines gives the line directly, and the line is what the cursor, the wrap and undo want.
Built for articles, not for logs
This editor is built for articles, not for 50 MB logs. The vector of lines pays one allocation per line. At that size the allocations, and a vector with millions of entries, would hurt, and one of the structures above would be the place to look first.
At this point my engine can draw a string, and the buffer can hold a whole document as lines. That is enough to show an article on screen. It is not an editor yet. A viewer displays text and stops there. An editor is everything that lets a person change that text: put a cursor in it, move it, select a range, type, delete, take back a mistake, and still see the right lines at 60 fps as the document grows we will see that in part 2 !
TL;DR
- A font stores each character as an outline, not a picture. FreeType turns an outline into a bitmap at the size you ask for, and the engine keeps those bitmaps in an atlas.
- To draw a string, the engine places one glyph after another along a pen, moving it by each glyph’s advance.
TTFTextdoes this, andmeasureTextruns the same layout without drawing and tells you where the pen ends. - To store the document, I use a vector of lines instead of one
std::string. Moving bytes is cheap at article size. Finding a line is the cost that matters, because the cursor, wrapping, colouring, drawing and undo all work on lines.
Try the engine
My engine is open source, and it is on GitHub. The text editor from this article is in /src/Engine/UI/texteditor/. Have a look if you want to read the code or build something with it. If you want to follow it until part 2, a star on GitHub helps.