BlueMonkMN's picture

Improvement to text drawing.

In the Usage forum I posted a question about fonts being drawn anti-aliased when they shouldn't be (only large font sizes should be anti-aliased) so I investigated and found out that it was because of the behavior of MeasureString that characters were being drawn at non-integral positions. So I did a little more coding, and I think I found a solution that makes text look much better, and could be further enhanced to relatively easily support wrapping and alignment. I just hope .NET supports these operations on all platforms. Here are the changes I've made. Please tell me if some changes like this could be included in the main code base and/or what to do next.

TextureFont.cs

        public class CharLayout
        {
           public PointF pos;
           public char character;
           public CharLayout(char character)
           {
              this.character = character;
              pos = PointF.Empty;
           }
        }
 
        public CharLayout[] GetCharLayout(string str)
        {
            List<CharacterRange> ranges = new List<CharacterRange>(32); // Win32 GDI limitation
            List<CharLayout> result = new List<CharLayout>(str.Length);
            int unprocessed_idx = 0;
            for (int idx = 0; idx < str.Length; idx++)
            {
               if (!Char.IsWhiteSpace(str[idx]))
               {
                  if (ranges.Count >= 32)
                  {
                     GetCharLayout(str, ranges.ToArray(), result, unprocessed_idx);
                     unprocessed_idx = result.Count;
                     ranges.Clear();
                  }
                  ranges.Add(new CharacterRange(idx, 1));
                  result.Add(new CharLayout(str[idx]));
               }
            }
            if (ranges.Count > 0)
               GetCharLayout(str, ranges.ToArray(), result, unprocessed_idx);
            return result.ToArray();
        }
 
        private void GetCharLayout(string str, CharacterRange[] ranges, IList<CharLayout> result, int start)
        {
           StringFormat fmt = new StringFormat(StringFormat.GenericTypographic);
           fmt.SetMeasurableCharacterRanges(ranges);
           Region[] positions = gfx.MeasureCharacterRanges(str, font, new RectangleF(0, 0, 1024, 768), fmt);
           for (int idx = start; idx < result.Count; idx++)
              result[idx].pos = positions[idx-start].GetBounds(gfx).Location;
        }

TextPrinter.cs (inside PerformLayout function)

            if (alignment == StringAlignment.Near && !rightToLeft || alignment == StringAlignment.Far && rightToLeft)
            {
                OpenTK.Fonts.TextureFont.CharLayout[] coords = font.GetCharLayout(text);
                for(int char_idx = 0; char_idx < coords.Length; char_idx++)
                {
                    x_pos = coords[char_idx].pos.X;
                    y_pos = coords[char_idx].pos.Y;
                    font.GlyphData(coords[char_idx].character, out char_width, out char_height, out rect, out texture);
                    vertices[vertex_count].X = x_pos;                // Vertex
                    vertices[vertex_count++].Y = y_pos;
                    vertices[vertex_count].X = rect.Left;            // Texcoord
                    vertices[vertex_count++].Y = rect.Top;
                    vertices[vertex_count].X = x_pos;                // Vertex
                    vertices[vertex_count++].Y = y_pos + char_height;
                    vertices[vertex_count].X = rect.Left;            // Texcoord
                    vertices[vertex_count++].Y = rect.Bottom;
 
                    vertices[vertex_count].X = x_pos + char_width;   // Vertex
                    vertices[vertex_count++].Y = y_pos + char_height;
                    vertices[vertex_count].X = rect.Right;           // Texcoord
                    vertices[vertex_count++].Y = rect.Bottom;
                    vertices[vertex_count].X = x_pos + char_width;   // Vertex
                    vertices[vertex_count++].Y = y_pos;
                    vertices[vertex_count].X = rect.Right;           // Texcoord
                    vertices[vertex_count++].Y = rect.Top;
 
                    indices[index_count++] = (ushort)(vertex_count - 8);
                    indices[index_count++] = (ushort)(vertex_count - 6);
                    indices[index_count++] = (ushort)(vertex_count - 4);
 
                    indices[index_count++] = (ushort)(vertex_count - 4);
                    indices[index_count++] = (ushort)(vertex_count - 2);
                    indices[index_count++] = (ushort)(vertex_count - 8);
                }
            }

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
the Fiddler's picture

Thanks for the code, I've been looking for changes like these. I'm aware of the problems with small font sizes: OpenTK performs kerning on individual glyphs up to 16pt, but doesn't layout text on whole pixels. This can (and will be) included to OpenTK, provided we can find the answers to some important questions:

First, are Gdi functions supported on Mono/X11? I guess they are, but we'll have to find out since which version (if it's Mono 1.2.3 or earlier there's no problem).

Second, MeasureCharacterRanges (Gdi) returns different lengths than MeasureString (Gdi+) - we'll need to take that into account internally in TextureFont.MeasureString(). Actually, these functions don't need to be public - they are just an implementation detail.

Third, up to which font size should this method be used? My personal preference is for sizes up to 16-18pt, but this depends on many factors.

Fourth, does MeasureCharacterRanges allocate memory? If yes, this method should not be used in uncached TextPrinter.Draw calls (ugh).

Fifth (and final), how do we handle text scrolling in this case? We might have layed out the text perfectly on pixel boundaries, but the user can destroy that with a simple call to GL.Translate(0.1, 0, 0). Should we leave this up to the user, or should we somehow try to compensate?

I'll check for Mono support asap, but we'll have to think a little on the rest to find the best approach.

BlueMonkMN's picture

I hope you have other sources for information about Mono/X11 because I have little to no experience in that area. But I can respond to some of the other concerns. On the question of MeasureCharacterRanges versus MeasureString, I think it would be a good idea to just use MeasureCharacterRanges in all cases because it is a more accurate function and can be used the same way as MeasureString. I have seen other people talking about using MeasureCharacterRanges instead of MeasureString because MeasureString (as I understood their comments) is intended for providing an upper bound on the string size, and MeasureCharacterRanges provides the exact size.

On the question about to which font sizes this should apply, same answer. Use MeasureCharacterRanges for all sizes and probably eliminate MeasureString. When I talked about Anti-aliasing being intended only for large sizes, I didn't mean to imply that MeasureCharacterRanges would pixel-align for all sizes to avoid anti-aliasing. MeasureCharacterRanges just performs the same layout that an actual DrawText operation would, which, in turn, behaves differently at small sizes versus large sizes (I believe). So I see no problem using MeasureCharacterRanges for all sizes.

On the question of memory allocation, MeasureCharacterRanges uses a StringFormat, which implements IDisposable, and returns an array of Region objects, which are also Disposable. I don't know how best to determine beyond this if any other memory is allocated. But the memory allocated for these two types of objects can be discarded after the call is done executing because what the function returns is just some .NET data structures (non-disposable) that track the character positions. But MeasureCharacterRanges wouldn't need to be used in the TextPrinter.Draw calls would it? Just in the Prepare call. The Draw call just relies on already-calculated values doesn't it? Is any further investigation in this area required?

On the issue of scrolling, I think it will be up to the user to align their transform on pixel boundaries if they want it on pixel boundaries. I don't know how OpenTK could compensate in any way to make it look any better. For the immediate future, I don't think it's worth trying to do anything if we don't see any problems here, but I can imagine a day where we might want to copy some of the transform information from OpenGL into the Graphics object before performing MeasureCharacterRanges, if we find that it has some effect we want/need.

the Fiddler's picture

Ok, here's a quick quality comparison of the current implementation, grid-fitting through MeasureCharacterRanges and manual grid-fitting on top of the current implementation:

Apart from the smallest size, MeasureCharacterRanges provides better results (ignore the y-direction, as this is not grid-fitted in any of the above). I'll also provide a screenshot of TextRenderer.DrawText for comparison, which should provide the best results.

I'm still not sure if MeasureCharacterRanges is a good tradeoff, however. It is faster than MeasureString, provides a little better results, but it generates garbage which might have a bigger impact on performance in the long term. It also looks like there is a bug in the native implementation, where trailing spaces are not measured. Last, but not least, the current implementation fails on the Text sample - it renders some text correctly but stops after a number of characters (can you confirm that on your machine?)

[Caching]
TextPrinter.Draw can render both cached and uncached text, so we need to minimize the garbage it generates - which is my main objection on MeasureCharacterRanges.

BlueMonkMN's picture

Something is screwy with the MeasureCharacterRanges results. It seems to behave differently in my Windows Forms test than in the OpenTK test. I'm getting different numbers back for the same text. By the time the position of the "d" in "Hello, World!" is being measured, it's almost a whole character off (which explains why the text in OpenTK looks more compressed than it should).

Aha, the smallest size looks much better if you construct a default StringFormat instead of one based on GenericTypographic. Unfortunately I'm out of time to investigate the other issues at the moment, but at least we can fix the problem with the smallest size and hopefully yield the best appearance with MeasureCharacterRanges at all sizes.

BlueMonkMN's picture

Now to comment on the rest of the issues.
Yes, the native implementation of MeasureCharacterRanges (and .NET implementation built on it) has a limitation of 32 characters per call. That's why my code was processing 32 characters at a time. Did you hit the limitation via some other means? Is this the limitation you're talking about?

What garbage does MeasureCharacterRanges generate? I thought it would all be cleaned up by properly disposing of the StringFormat and Range objects (which I neglected to do in my implementation, but could easily be done). Dealing with Disposable objects in quite common in GDI. Heck, just to draw a shape of a particular color you have to create a SolidBrush object to contain that color, and that's something that has to be disposed. Is that a problem?

I suppose by "garbage", you're referring to allocated-then-freed memory. Honestly, I've heard about this in academic contexts, but never in real performance optimization discussions that I can recall -- maybe I just haven't been involved in enough optimization discussions. But I'd think twice before discarding this on a theoretical performance hit. .NET does have much better memory management than the average compiler, as I understand it. Now granted, it's interacting with GDI+, and who knows what kind of memory management that has under the covers, but considering the trade-offs as I currently understand them, it might just be worthwhile to get the best text rendering, since I don't see any other way of getting it. I'll tell you one thing. At one time I was creating a new 128x128-pixel bitmap on every MouseMove event in my graphics editing component, and had neglected to dispose of the Bitmap. I thought .NET was good at memory management and knew best how and when to dispose of things when they were no longer referenced. Not so. It was chugging every few seconds as I drew things with the mouse. I assume it was doing automated garbage collection forced by the fact that it had built up a zillion un-diposed bitmap objects that could be disposesd, so then it would periodically clean them up. But then when I realized by folly and introduced a Dispose call, everything zipped right along. So I suspect garbage collection is not so much an issue if you properly dispose of all your disposable objects. What do you think?

My other concern is that, although the smallest font size is a small percentage of the available sizes, I suspect it will be the most popular size and the one people would most want to render cleanly and easily.

On the trailing space issue, did you write your own code or use mine? Mine was intentionally ignoring whitespace and I can see how it might have easily misled you to believing that MeasureCharacterRanges didn't process whitespace properly.

the Fiddler's picture

[Rendering problem]
Actually, it looks like MeasureCharacterRanges isn't at fault here. The problem is that TextPrinter.Prepare stops processing glyphs after a set number (maybe 300 characters?) and lumps the rest at (0,0). I haven't spent any time investigating though, because I started looking into an alternative implementation (see below).

[Garbage]
This is a significant topic - XNA has been criticized for generating garbage, which force the GC to run every few seconds, causing hiccups. There are two approaches to minimize this: a) keep the allocation graph as simple as possible (e.g. reusing temporary objects through memory pools, minimizing allocations), or b) go wild with allocations, but only during loading phases (no allocations at all during gameplay).

(a) allows the creation of temporary objects, since the simplified graph will allow gen-0 GC-runs to complete extremely fast, while (b) prohibits temporary objects. The middle ground is where performance issues lie, unfortunately - quite limiting, but this is the price to pay for high performance :/ Even worse, Mono does not sport a generational GC yet, which makes (a) impossible to achieve.

Now, it could be that temp objects from MeasureCharacterRanges aren't an issue (it's one gen-0 object every 32 characters, if you call Dispose()), but this will also depend on the allocation behavior of the application - obviously, no garbage is better than little garbage. Anyway, let's forget about this for now, until we have some more concrete performance data.

One last thing though, regarding your application with temporary Bitmaps: without the Dispose() call, these are treated as gen-1 objects due to their finalizers, which explains the bad performance you were observing (a full GC-run every few seconds is bound to be bad!). Calling Dispose() suppresses the finalizers, turning these into gen-0 objects - much faster.

[Trailing spaces]
I didn't observe that problem myself (didn't test a string with trailing spaces), but read about this on a message board. Just something to keep in mind, if it shows up in the future.

[Small sizes]
Actually, my impression is that, apart from strategy games and a few RPGs, the rest tend to use font sizes between 18-26 points. I may be mistaken, but this was the case with everything I've played recently. I suspect that anything under 14 would be too hard to read during actual gameplay.

[Font rendering]
I've been toying with another approach which yields much better results than any of the above: cache the results of Graphics.DrawString or TextRenderer.DrawText on a texture, instead of building a display list or a VBO of individual glyphs. I'll post screenshots once I manage to get correct alpha out of ClearType characters, but this looks promising.

Edit: Here are screenies of the new methods. First is TextRenderer.DrawText, which matches the system-wide rendering settings (this is rendered with ClearType on Vista, after extracting luminance). Second is Graphics.DrawString, in grayscale antialiasing mode (note that only the first 5 lines are hinted):

I'm not sure which looks better. The first has the the advantage of being able to handle complex scripts (nice!), but it is slower, is affected by system settings and is untested on Linux. The second allows us to turn off hinting, which gives better shapes on larger font sizes. What do you think?

Edit 2: spelling.

Edit 3: For the first screenshot, I've let the drivers handle luminance extraction from an rgba source. The problem is that TextRenderer.DrawText premultiplies alpha on the rgb channels, assuming a uniform background (black in this case). We can improve the font edges by devising a different algorithm (the current one goes from rgb -> luminance -> alpha) - unfortunately, no time for this right now.

BlueMonkMN's picture

[Garbage]
Actually GetCharacterRanges is currently dealing with up to 32 pieces of garbage per call because it returns an array of (up to) 32 Region objects with each call. But sure, we can leave this alone until more performance data is available.

[Font Rendering]
The potential problem with caching the results of DrawString on a texture is the limitation of texture memory. For an application that is nearing its limit on texture memory or wants to draw (or more importantly, cache) a huge piece of text, it will hit a limitation and be unable to draw/cache as much text this way as it would using another draw method with individual glyphs.

[Samples]
What's TextRenderer? I don't see that in the .NET framework.
I like the output and trade-offs (those that you mentioned) of Graphics.DrawText (of course it's designed to handle all permutations one might want when drawing text), but I'm nervous about other costs: the cost of transferring the image from system memory to video memory might outweigh the cost of MeasureCharacterRanges plus its memory management plus the operations involved in telling GL to draw from a texture (even if the latter sounds like a lot more pieces). And I'm nervous about the memory cost of having to effectively store the whole text output block as a bitmap/texture at least temporarily. Don't you run into the same memory allocation/garbage problems... or are you planning on having a permanent fixed-size bitmap and texture dedicated to rendering text operations?

BTW, I noticed that when I disposed of a TextureFont, the font object passed into the constructor is also disposed. That kind of threw me for a loop. Was that intentional? (I wonder what happens if I pass a system font into the constructor.)

the Fiddler's picture

[Garbage]
Duh, you are correct. Region objects are not primitive types, so it's an allocation of 32 distinct objects.

[TextRenderer]
It's in the Windows.Forms namespace. Introduced in .Net 2.0.

[Memory]
I was worried about that at first, but a quick calculation shows it's not as big a problem as it sounds at first. The current implementation requires 88 bytes per character, plus the actual texture storage of the glyph itself (a one-time cost of width*height bytes). The new implementation requires width*height bytes for each appearance of the glyph.

In any case:
a) how much text will you need to precache? A single 1024x1024 texture can about 4K glyphs at 16 pixels size.
b) the driver will swap this texture out of video memory when not in use. System memory, rather than video memory, is the limiting factor here.

In any case, these sheets are highly compressible. I haven't tested yet, but it's likely that we'll be able to achieve at least a 4 to 1 compression ratio (about 256KB for a 1024x1024 sheet).

Regarding bandwidth, uncached text will travel over the bus, true, but this is unlikely to be the bottleneck in real world scenarios; the actual rasterization process would be the slow part here.

[TextureFont]
Thanks for reporting, this is a bug.

BlueMonkMN's picture

[Memory]
According to your calculations of 1024x1024 at 4:1 compression being 256KB, I assume you're thinking of a 1-byte-per-pixel pixel format. I haven't played around with various pixel formats much, but I'm just curious if that would also allow the application to draw the cached text in any color if the pixel format, for example, is only the alpha channel or something.

[Performance]
So the rasterization would be the bottleneck in this scenario. This would become in issue in scenarios where dynamic text needs to be drawn each frame (like an FPS counter), right? Are you going to perform some tests to compare the performance of this solution versus the original solution (and/or the MeasureCharacterRanges solution) of drawing individual glyphs directly from a texture, which presumably doesn't have this issue (or the System-Video transfer issue)?

I pointed out the potential flaw of system-video RAM transfer overhead, and it seems like the response is "that's not the half of it", which suggests to me that it might not be the end-all perfect solution ;).

I think things were on the right track (as far as performance is concerned) when you had all the glyphs (well, all the ones most people care about anyway) stored in texture memory. It was a truly hardware accelerated solution (right?). And I'm not sure where the best balance between features and performance is (if there isn't a single balance, maybe there needs to be two solutions allowing the client application to choose).

But in the interest of looking for the perfect solution ideal for all clients, let me share some other ideas that have been occurring to me:
1) Instead of caching all the glyphs when the font is created, which I presume is what's happening right now, it might be practical to "lazy-initialize" each glyph as it is used, which I believe is what system text rendering functions do internally. Then you wouldn't be limited to which characters could be drawn (do I understand correctly that the set it limited in the current implementation?). This probably isn't the best idea for a high performance game architecture, but it was an idea that occurred to me, so I figured I'd mention it just in case.
2) I was wondering if there was some way to cache the character sizes/offsets for each glyph as part of the TextureFont object instead of calling measurement functions each time, which might eliminate some concerns about garbage generation. But I don't know if the character size is static or changes based on its context. I feared for a moment that MeasureCharacterRanges would only return an area occupied by actual visible pixels of the glyph, but a test I just performed seems to confirm (with a non-serif font even) that the size of the "l" in "Hello, World!" fully occupies the space between the r and the d. But I also discovered that MeasureCharacterRanges does not in fact return regions that entirely enclose the glyphs as demonstrated by the magnified screenshot below. The overhang in the j is not included in the character range even if it's the only character I'm measuring.

So I'm starting to wonder how far to take this. I don't want things to get all blown out of proportion. Your solution of rendering in system memory and transferring to video memory is probably the best balance for now until/unless at some point we want to start delving into font internals to figure out how font rendering actually works internally just to get the correct character positions manually or something.

the Fiddler's picture

You raise some good questions, let me try to answer them one by one:

[Colors]
Of course, you can call GL.Color4 prior to TextPrinter.Draw, to set the color of the text.

[Performance]
The current approach is a good compromise between performance and quality: it offers excellent performance on cached text, acceptable performance on uncached text and moderate memory usage. It does suffer on quality a bit, as you found out, since it cannot (efficiently) perform grid-fitting. Moreover, it doesn't support more advanced layout options and complex scripts (without a lot more coding).

MeasureCharacterRanges will improve quality significantly, but at the expense of speed on the case of uncached text.

The method I am testing right now, provides excellent performance on cached text (on par or better than the current method) and excellent quality, at the expense of higher memory usage. Uncached text is an unknown variable at this point (haven't tested yet), but I suspect it will be slow on Windows and acceptable on Linux. The *big* benefit however, is that it reduces code complexity a lot: you gain justfication and formatting, as well as handling of complex scripts for free. This method also matches the rendering quality of the OS, which is great for user interfaces (but this probably doesn't matter in actual games).

[Caching]
Eager initialization was out of the question since the beginning (we want to support more than plain ASCII!). Glyphs are initialized lazily during the TextPrinter.Prepare (or the uncached TextPrinter.Draw) method.

We cannot cache widths and offsets, unfortunately. As you noted on the image above, characters distances differ according to character pairs (look up "kerning"), while hinting and grid-fitting further complicate matters. And in any case, .Net does not provide access to this information.

[How far do we go]
As long as we move withing the boundaries of the .Net API, we are playing a game of compromises. The goal is to achieve good performance without compromising quality (too much), and with the least programming effort.

What is the alternative? By using FreeType we would be able to improve both performance and quality. The catch (there's always a catch) is that this would hamper deployment. Right now you can run OpenTK programs on any supported platforms, using just c&p - add an unmanaged dependency, and you suddenly have to tell your users, "look there's this library called FreeType, which you need to compile and install before playing this game" (ok, this is hyperbole, but you lose on of the main benefits of .Net).

In any case, I'm going to leave this matter aside for a little while, to focus on getting the next release out. Please keep your suggestions coming (isn't anyone else interested in font rendering?), or - even better - run a few quality/speed comparisons.

BlueMonkMN, if you are interested I can upload the code to the alternative TextPrinter implementation used in the screenshots above. I can provide a few pointers if you wish to play with it (it's much simpler than the existing one) - if we can improve speed in the uncached case, I'd say this is the way to go.