Font creation/rendering

[BenLunt]

Hi,

I have nearly finished a project, and in the meantime have been thinking about the next project, and fonts comes to mind.

My current GUI uses numerous fonts, as shown here, but each of those fonts are fixed sized bitmaps. For example, the character 'A', in its simplest form, might use an 8-bit width and an 10-byte height, a set bit meaning to plot a pixel, a clear bit meaning to bring the background pixel forward.

This makes it really simple. In fact, I created a simple font creation utility that allows me to create these fonts with ease, the 'A' in question, shown. Each white box represents a background pixel (a transparent pixel) while a black box represents a foreground pixel (non-transparent pixel). The utility allows me to move the bits around, but in the end, the character is still just a bitmap of pixels.

The other font, the LucidaC font is again, the exact same thing, though more pixels in the width and height directions.

The problem is, they remain the same size, period. If the font is 19 pixels tall, as in the LucidaC font, the characters are always 19 pixels tall. I have no way of displaying different sizes, unless I use a routine to simply expand the pixel bitmap.

For example, in this image, notice the background image is at a fixed size of 640x480, but in this image I have used a routine to "stretch" the background image to match the screen size.

I thought about doing this technique to the current font bitmap design, but as the font size increased, so would the pixelation appearance.

I have looked around for font ideas, TrueType, OpenType, etc. I looked on this forum, the previous few screen shots of projects like klange's Toaruos, pat's Saturn and nakst's projects, that seem to show font size differences, though I know that Saturn uses FreeType as its font rendering engine.

I grabbed a few simple font files from WinXP, each roughly 50k in size, and tore them apart looking to see what they did. (I thought it would be really nice to grab one of these font files, try to display it, having a WinXP machine do the same, and then compare).

Also, having recently worked with my ACPI and AML stuff, I thought of having an AML type language that would tell the rendering engine how to draw the character, possibly similar to the TrueType font file, but not so detailed. The TTF file has 14 tables, more than half referencing each other just to get information about how to display the font, let along the actual glyphs.

So, my question is for those of you whom have stuck around and read this far (smile), what have you done, thought about doing, think you might do, etc.? I know pat's Saturn uses FreeType, but I don't want to port someone else's code, I want to do this myself.

If I did an AML type language, I could have instructions like, for simplicity sake:
- move to x,y (x and y being units in size)
- turn on pixel drawing
- move to x,y
- draw radius at x,y w/radius = r, from degree (d0) to degree (d1)
- stop pixel drawing
- move to x,y
- etc....

As long as I remembered that x,y and any size related variable needed to be "current font height/width" aware, this would work for simple fonts.

My question is, do I want to take the time to create a TTF rendering package where I can simply download a free font from the web and display it (many advantages), or create a much simpler font rendering package of my own, but have to create each font file myself?

Just asking for your thoughts and ideas.

Thanks,
Ben
- http://www.fysnet.net/osdesign_book_series.htm

[Schol-R-LEA]

The YouTube channel "Computerphile" has several videos on the history and complexities of typesetting and fontology, and some of them discussion this issue (among others). The video The Font Magicians in particular discusses the problem of trying to scale fonts simply by resizing or stretching. It was solving exactly these problems (for certain meanings of 'solving') that was the cornerstone of Adobe's early success. The video mostly discusses outline fonts, and to a lesser extent stroke fonts, but the problem applies to scaling bitmap fonts as well.

So a book on PostScript might be helpful, at least for comparison's sake.

You might also want to take a look at Knuth's books on Metafont, which is the description language for native TeX fonts (yes, I am sure Ben knows about TeX, but some others here might not). The Metafont Book would be a good starting point for that, with his series Computers and Typesetting being useful for the deeper details - if you can afford them, or have a nearby college library that has them.

A few more I found, but don't know much about; most are about using existing fontography and typesetting software, and some are quite dated, but they may have some insights for you:

• Using Fontographer (this is the book mentioned in one of the videos)
• Fonts and Encodings
• A Typographic Workbook
• The Joy of TeX
• Document Formatting and Typesetting in Unix
• The LaTeX Companion
• Typesetting
• Explorations in Typography
• Guide to LaTeX: Tools and Techniques

[simeonz]

Also, having recently worked with my ACPI and AML stuff, I thought of having an AML type language that would tell the rendering engine how to draw the character, possibly similar to the TrueType font file, but not so detailed.

Not a subject I am familiar with, but just my 2c.

First, ordinary postscript and windows metafiles are such languages. So, the idea is not that weird. However, as the video from Schol-R-LEA's post pointed out, it is rather difficult to preserve symmetries, avoiding loss of connecting lines, holes, serifs, etc. I imagine that any language that features some arithmetic and has information about the rasterization output - that is, can round distances to raster units and align endpoints to discrete coordinate values, should be able to produce all corrections required for symmetries, minimum gaps, minimum thickness and other arbitrary constraints, assuming that individually tuned program for every glyph is provided. But then, you will need to compile to this language from a more typography friendly representation, and more importantly to enter all glyph details manually for all the glyphs, which seems like a lot of effort. If I were you, I would at least consider a tool for converting TrueType or OpenType to whatever format you need, so that you don't force yourself to study letter design for a couple of years.

[klange]

I have looked around for font ideas, TrueType, OpenType, etc. I looked on this forum, the previous few screen shots of projects like klange's Toaruos, pat's Saturn and nakst's projects, that seem to show font size differences, though I know that Saturn uses FreeType as its font rendering engine.

Hi Ben,

The text rendering technique used in the ToaruOS screenshot you linked is signed distance fields. It's a relatively new idea and was designed for use in 3D rendering to provide antialiased stencil textures at any resolution and in a way that is easily rendered by shaders. It's meant for larger rendering, but its performance in small sizes is surprisingly good - almost comparable to unhinted vector fonts in ideal cases. The font data stores a rasterized bitmap of distances from edges of the font glyphs (signed, so the interior distances are also maintained and can be distinguished from the outer distances). It has some weird quirks, especially with sharp corners (though some techniques exist that rectify these issues, such as storing distances along multiple vectors so sharp corners can be identified). Ultimately, it's probably not a good long-term solution for text rendering in an OS, but it's very simple to implement if you want a quick way to get scaled text. I'm considering extending my implementation into an encapsulated font format with more flexibility and extended glyph information like kerning.

[pat]

So, my question is for those of you whom have stuck around and read this far (smile), what have you done, thought about doing, think you might do, etc.? I know pat's Saturn uses FreeType, but I don't want to port someone else's code, I want to do this myself.

Well we know what I did, but here's what I think I might do. Eventually I might consider writing a TTF font renderer to replace FreeType as I really don't like FT that much. I understand the desire to write everything yourself, I mean, that's why we're posting on osdev.org and not ubuntuforums.org. But I try to stay practical and keep focused on one goal. I wanted to spend a lot of time working on my own UI framework, and wanted to get to it as soon as possible. That required supporting text rendering first. Since I would be supporting TTF fonts in some fashion, the format's already laid out and it wouldn't really matter if I wrote it as the output would still be the same. Not a lot of room for creativity there, sure I could optimize it to my system but that doesn't change the behaviour. That's why I opted for FT, so I could quickly bootstrap UI development where there is ample room for creativity.

My question is, do I want to take the time to create a TTF rendering package where I can simply download a free font from the web and display it (many advantages), or create a much simpler font rendering package of my own, but have to create each font file myself?

I would strongly encourage you to support TTF so you can take advantage of the massive amount of beautiful, high quality fonts out there. Unless you are artistically inclined and know a lot about typography, it doesn't make a whole lot of sense spending a lot of time not only designing the fonts with multiple styles, but also taking care of things like kerning pairs. If you're very strongly inclined to write your own font language, at least spend time making it TTF compatible so you can write a converter/interpreter. Think down the road: eventually if you get web support, or like a Word-esque document suite people are going to want to use the popular existing/their pet favourite fonts.

The text rendering technique used in the ToaruOS screenshot you linked is signed distance fields.

Took my advice from chat a while back did ya? . SDFs are fantastic, they were very cheap on budget hardware a decade ago so I can imagine how good it is now. Even getting 'fancy' with separate colours for border and fill was only a few extra pixel shader instructions. Generating the fields was a bit of a slow process though, depending on quality and number of glyphs, but its an offline process so whatever, run it overnight.

[tay10r]

Personally, I would not bother with creating an entirely new font rendering system.
It would take the focus away from the rest of the project since it's not a easy thing to do right.
Perhaps it would be worth it if you felt like you can write a better font rendering engine than FreeType, which is hard to beat.

What I did for Alloy, the front end for BareMetal-OS, was creating a program that used FreeType to render fonts into C files so that they could be compiled.
The benefit of doing it this way is that you don't have to try and compile FreeType to work on your system.
It's also much simpler since you don't need file system access for it.
You can generate code for multiple sizes to accomplish what your trying to do.
The object file will end up being around 15KB in size.
That might freak some people out who are trying to boot from a floppy, but realistically storage is cheap now.
The down side is that you lose some flexibility at run-time.
I believe it's a good solution for starting up the project.
You can then switch to using FreeType in your system when you think it's ready.

Here's a picture of the Source Code Pro font in Alloy:



Here's the source code for the program that generates the code for the font:

https://github.com/ReturnInfinity/Alloy ... enerator.c

You could use that as a reference to make your own tool, or you can use it directly in your project under the BSD 2-Clause license.

Hope that helps!

[BenLunt]

Thanks everyone for the comments. I may go the route of creating a TTF/OTF rendering engine, but am still debating other ideas.

I appreciate the comments,
Ben

[BenLunt]

Just an update. I took the older TTF file format and was able to display the outlines of all of the fonts I tried. I am away from my work desk, so I can't show you the results, but have noticed that some fonts have been worked on considerably and the outline's points are somewhat close together to make a very good looking character (more than 500 points per char). Then there are other fonts that have the points far enough away that you can see the straight lines between points (as few as 10 points per char).

I have started the virtual machine code to execute the font instructions that will make those lesser defined fonts look better.

Anyway, I have chosen the TTF format, and later add updates to support the OTF format (CFF tables). Thanks to all for your comments.

-Ben

[BenLunt]

As a followup, I have been able to display TTF fonts of any size, though with some restrictions.

For example, they must be type 1 TTF files (the older style), with no CFF tables.

Also, my byte code virtual machine is not complete. I have some obvious errors. For example, in one of the debug outputs I see that the byte code reads from temporary storage, but has yet to write to that location. Another is the inclusion of nested IF/[ELSE]/ENDIF blocks. I haven't read yet where it is specified if you can have nested IF blocks. My current code does not support nested blocks which makes it very easy.

Code: Select all

  // start of execution
  int execute_code = 0;  // a zero value means to execute code.  A non-zero value means to skip it.
  ...
  ...
  // IF statement found
  execute_code = (if condition is TRUE) ? 0 : 1;
  ...
  ...
  // ELSE statement found
  --execute_code;
  ...
  ...
  // ENDIF statement found
  execute_code = 0;

That code makes for a very simple flag to know whether to execute the code or not. (By the way, the byte code gives no reference to the size of the block, nor how far away the ELSE or ENDIF is located. You have to follow each byte until this instruction is found). (note: ACPI's AML code does give this information in its code system) For nested blocks, I will have to do a stacked flag, or something else.

Anyway, as a followup from my last post, some fonts have a lot of points listed and very little byte code, while other fonts have few points and a lot of byte code.



For example, the 'B' on the top left shows it only having a few points (~25). You can clearly see the straight line outlines. However, it has a lot of byte code to correct this.
The 'B' on the bottom left has many points (~256) and little byte code. These many points are close enough together that you can hardly see the straight line outline. Very little byte code is used since very little correction is needed. (The two 'B's on the right are the same character only filled in)

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucket dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

Lot's of work to do.

Ben
- http://www.fysnet.net/osdesign_book_series.htm

[Sik]

If I recall correctly the main purpose of the bytecode is to allow characters to look OK at smaller sizes where they start resembling more pixelart than outline fonts.

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucket dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

Do you have at least the bounding box? (which I imagine you can compute from the resulting outline)

If I recall correctly, filling is a stencil operation boiling down to "not zero". Counterclockwise sides are -1, clockwise sides are +1 (or the other way, doesn't matter as long as they're opposite). So you could scan through the whole bounding box and check where the sides are (and their angle) to increment/decrement an internal counter in each line, and fill in those pixels where the counter is not 0. This also means you'll need to step back and work on the outline itself rather than rendered pixels.

You may want to also keep the current routine as its own feature though. Outlined text can be useful :v


EDIT: by the way it's very important that you follow the "not zero" part. A lot of people are taught that filled areas are clockwise and non-filled areas are counterclockwise and hence get the impression that the check is an "above zero", then get confused when a counterclockwise area shows up on its own and turns out solid (and indeed some renderers get this wrong and some fonts end up misrendered). The correct behavior is "not zero".

Also expect fonts with overlapping areas, so you'll need to first render the text on its own buffer and then use that as a mask for whatever color they're meant to be on the target framebuffer (this matters if e.g. text is translucent).

[Brendan]

Hi,

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucked dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

This would be done using a kind of "rasterisation".

The simple method is; for each row of pixels imagine a horizontal line in the centre, find points where the outline intersects with the horizontal line, and use those intersections to toggle a "yes/no" flag. E.g. when the horizontal line hits the first intersection (left-most edge of outline) start turning pixels on, then when it hits the next intersection start turning pixels off, then ... This gives you a little anti-aliasing because the intersection/s probably won't happen exactly on the boundary between pixels.

The complex method is to recognise that a row of pixels is actually a "1 pixel tall" horizontal strip; and find intersections between the outline and the top and the bottom of the strip, plus track points that are in the middle of the strip. Then split the horizontal row into segments separated at "intersection or point x-coords" and calculate thickness at each of these x-coords. Finally, interpolate based on the thicknesses to generate alpha values. For example, if the strip is "0% thickness at x=1.5, 100% thickness at x=2, 100% thickness at x=4.5, 0% thickness at x=5.5" then you get alpha values for each pixel like "0.0, 0.5, 1.0, 1.0, 0.66, 0.33".

Note that there are patents on sub-pixel rendering that expire next year. For code (or documentation) that won't be released publicly until after the patents expire, it's probably a good idea to consider the inclusion of sub-pixel rendering now. This mostly just means doing each (red/green/blue) channel separately and having a different horizontal offset for each channel. Also note that subpixel rendering isn't necessarily just for fonts - there's no real reason (other than performance) why you can't have a fancy 3D graphics pipeline that renders three separate monochrome pictures (one for red, one for green, one for blue) taking sub-pixel positioning into account, that combines the three monochrome images to get the final "RGB pixel values".


Cheers,

Brendan

[BenLunt]

If I recall correctly the main purpose of the bytecode is to allow characters to look OK at smaller sizes where they start resembling more pixelart than outline fonts.

Could be. I am just learning about these things. I have never actually dug into font rendering. This is all a first for me.

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucket dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

Do you have at least the bounding box? (which I imagine you can compute from the resulting outline)

If I recall correctly, filling is a stencil operation boiling down to "not zero". Counterclockwise sides are -1, clockwise sides are +1 (or the other way, doesn't matter as long as they're opposite). So you could scan through the whole bounding box and check where the sides are (and their angle) to increment/decrement an internal counter in each line, and fill in those pixels where the counter is not 0. This also means you'll need to step back and work on the outline itself rather than rendered pixels.

You may want to also keep the current routine as its own feature though. Outlined text can be useful :v

EDIT: by the way it's very important that you follow the "not zero" part. A lot of people are taught that filled areas are clockwise and non-filled areas are counterclockwise and hence get the impression that the check is an "above zero", then get confused when a counterclockwise area shows up on its own and turns out solid (and indeed some renderers get this wrong and some fonts end up misrendered). The correct behavior is "not zero".

Also expect fonts with overlapping areas, so you'll need to first render the text on its own buffer and then use that as a mask for whatever color they're meant to be on the target framebuffer (this matters if e.g. text is translucent).

I do have a bounding box, and I thought of "painting" the bounding box area after the outlines where drawn, then inverting the "painting". However, as with the 'B' shown in a previous post, this would not "clear" the inside of the 'B'.

As mentioned, I am new to this font rendering stuff. Could you elaborate a little on this "not zero" technique. Maybe I have done this before, I am just not recognizing it by this name/description. Maybe I haven't seen it at all. Please elaborate a little so that I can have something to start with in my research.

Thanks,
Ben

[BenLunt]

Hi,

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucked dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

This would be done using a kind of "rasterisation".

The simple method is; for each row of pixels imagine a horizontal line in the centre, find points where the outline intersects with the horizontal line, and use those intersections to toggle a "yes/no" flag. E.g. when the horizontal line hits the first intersection (left-most edge of outline) start turning pixels on, then when it hits the next intersection start turning pixels off, then ... This gives you a little anti-aliasing because the intersection/s probably won't happen exactly on the boundary between pixels.

I thought of that too, but there were too many places where this would be an off-by-one count and start filling in the wrong area. Especially drawing at smaller sizes. However, I have been thinking that one could "draw" the outlines, at full size, to a temp buffer, then do this "simple" method on the full sized character. This would eliminate most, if not 99% of this error. I would then need to find a way to "convert" that back down to the smaller character's outline.

The complex method is to recognise that a row of pixels is actually a "1 pixel tall" horizontal strip; and find intersections between the outline and the top and the bottom of the strip, plus track points that are in the middle of the strip. Then split the horizontal row into segments separated at "intersection or point x-coords" and calculate thickness at each of these x-coords. Finally, interpolate based on the thicknesses to generate alpha values. For example, if the strip is "0% thickness at x=1.5, 100% thickness at x=2, 100% thickness at x=4.5, 0% thickness at x=5.5" then you get alpha values for each pixel like "0.0, 0.5, 1.0, 1.0, 0.66, 0.33".

Note that there are patents on sub-pixel rendering that expire next year. For code (or documentation) that won't be released publicly until after the patents expire, it's probably a good idea to consider the inclusion of sub-pixel rendering now. This mostly just means doing each (red/green/blue) channel separately and having a different horizontal offset for each channel. Also note that subpixel rendering isn't necessarily just for fonts - there's no real reason (other than performance) why you can't have a fancy 3D graphics pipeline that renders three separate monochrome pictures (one for red, one for green, one for blue) taking sub-pixel positioning into account, that combines the three monochrome images to get the final "RGB pixel values".

Cheers,

Brendan

There are a few commands in the byte-code that have to do with interpolate. I am wondering if that will help. As mentioned, I am just getting into this specific kind of thing.

Thanks,
Ben

[Sik]

As mentioned, I am new to this font rendering stuff. Could you elaborate a little on this "not zero" technique. Maybe I have done this before, I am just not recognizing it by this name/description. Maybe I haven't seen it at all. Please elaborate a little so that I can have something to start with in my research.

If you know about GPU rendering: this is literally the same as a stencil test.

If not, in short: you start with a buffer filled with all pixels as zeroes. Shapes where their vertices are ordered clockwise increment the pixel by 1. Shapes where vertices are ordered counterclockwise decrement it by 1. Then you go through the buffer and check the resulting values: pixels that are not zero become opaque, pixels that are zero become transparent. (fonts have curved shapes which makes this messier but principle remains the same)


(rambling) For your case it may be better to modify the outline renderer so every pixel stores the angles of every border that passes through them (yes, store all of them, in case two shapes get too close together or overlap). Actually, store them rotated 90º so they point "inside" the shape (will make the next part easier). Then after that is done, on every line start a counter at 0, then scan it left to right, and for every stored angle you find, increment or decrement the counter accordingly (if you stored them rotated 90º then this is a simple range check). Then draw those pixels where the counter was not 0.

I may or may not be missing something. Counting how many sides cross a line is a common way to determine if something is inside an arbitrary shape, though (Duke Nukem 3D did something like this to determine if something was inside a sector).


EDIT: and yes I know this doesn't account for antialiasing. Actually, if you look around you'll notice that pretty much all font antialiasing methods involve rendering at a high resolution and then using multiple samples to come up with the value of a pixel (basically supersampling). The methods differ in how they decide how to merge multiple samples into one pixel.

[Brendan]

Hi,

The second thing I need to do is actually fill in the glyph. I only have the outlines drawn. I need to find a way to fill in the glyph. By the way, a simple "paint bucked dump" algo won't work since the font does not specify where to make this dump, nor does it account for two outlines close enough together to "block" this dump from another area.

This would be done using a kind of "rasterisation".

The simple method is; for each row of pixels imagine a horizontal line in the centre, find points where the outline intersects with the horizontal line, and use those intersections to toggle a "yes/no" flag. E.g. when the horizontal line hits the first intersection (left-most edge of outline) start turning pixels on, then when it hits the next intersection start turning pixels off, then ... This gives you a little anti-aliasing because the intersection/s probably won't happen exactly on the boundary between pixels.

I thought of that too, but there were too many places where this would be an off-by-one count and start filling in the wrong area. Especially drawing at smaller sizes. However, I have been thinking that one could "draw" the outlines, at full size, to a temp buffer, then do this "simple" method on the full sized character. This would eliminate most, if not 99% of this error. I would then need to find a way to "convert" that back down to the smaller character's outline.

For the simple method; the only tricky case is when your horizontal line passes exactly through a point, and you have to decide if the point should be ignored (or not). For example, the point/s at the bottom of a 'V' don't count as an edge and need to be ignored, but the points on the left of a '<' do need to be treated as an edge. However it's extremely easy to decide by examining the next and previous points - if both of their Y coords are above the point you hit or if both their Y coords are below the point you hit then the point is ignored, and for all other cases the point is treated as an edge.

For scaling (for both methods); you'd scale all the points once before you start rasterisation. There shouldn't be any need for temporary buffers at different scales (except maybe caches to avoid re-doing the same work).

The complex method is to recognise that a row of pixels is actually a "1 pixel tall" horizontal strip; and find intersections between the outline and the top and the bottom of the strip, plus track points that are in the middle of the strip. Then split the horizontal row into segments separated at "intersection or point x-coords" and calculate thickness at each of these x-coords. Finally, interpolate based on the thicknesses to generate alpha values. For example, if the strip is "0% thickness at x=1.5, 100% thickness at x=2, 100% thickness at x=4.5, 0% thickness at x=5.5" then you get alpha values for each pixel like "0.0, 0.5, 1.0, 1.0, 0.66, 0.33".

There are a few commands in the byte-code that have to do with interpolate. I am wondering if that will help. As mentioned, I am just getting into this specific kind of thing.

The complex method is possibly "excessively complex" (there's lots of corner-cases to worry about); but would give much better quality results. The interpolation (of the thicknesses) is because changes in thickness (where points were) usually don't occur at the edges of pixels (but happen at "fractional x coords", like at "x=5.125" and not at "x = 5").

I doubt that any mention of interpolation in the byte-code commands has anything to do with rasterisation. Instead, I'd assume it's related to curves (e.g. maybe Bézier curves).


Cheers,

Brendan