Monday, June 28, 2010

Electric Sink

It's summer, and I'm not really feeling in the programming mood after work, though there are a lot of projects that I'd be happy to start.

I've always be interested in Constructive Solid Geometry but never written an implementation. This pdf seems to be a good introduction.

Saturday, June 05, 2010

Bonus Content: Kerning

Bitmap fonts and text were both handled in the C# Game Programming book but kerning wasn't. Kerning refers to the amount of spacing between characters in text. Without kerning the letters in words may appear to be spaced out oddly.

The code in the book produced text that looked like this:


Rather naively, I assumed this looked a bit funky due to kerning issues (hence this very topic to make everything nicer) but having revisited the code I see there is actually an error in the text class that means all the spacing is off.

Well this post will address both those problems. The first step is creating a font file that uses kerning. The ones included with the book are all monotype which means they don't use kerning at all!

Bitmap fonts are easy to make using Angel Code BMFont program. Here I've created a one texture page Arial bitmap font:


When you save the font file a .fnt file is created, as well as one or more texture maps of the font. If you open the .fnt file in a text editor and look near the bottom; you'll see that there is a section like this

kernings count=89
kerning first=32  second=65  amount=-2  
kerning first=32  second=89  amount=-1  
kerning first=49  second=49  amount=-4  
kerning first=65  second=32  amount=-2

Each line describes the kerning adjustment between two characters. For example if character 65 follows character 32 then character 65 should be moved back along the x axis by 2 pixels.

The kerning data can be represented quite simply by a dictionary that has a key of two characters and returns a integer kerning amount. The key can described by the following data structure:

1 /// <summary> 2 /// Used to as key to the kerning amount for two characters. 3 /// </summary> 4 internal struct KernKey 5 { 6 public int FirstCharacter { get; set; } 7 public int SecondCharacter { get; set; } 8 9 public KernKey(int firstCharacter, int secondCharacter) : this() 10 { 11 FirstCharacter = firstCharacter; 12 SecondCharacter = secondCharacter; 13 } 14 }

KernKey should be created in the Engine project; as it will be used with Text and Font.

This can now be used as a key to a dictionary of kerning amounts. The next task is parsing the kerning information from the file and adding it to such a dictionary. At the moment the FontParser.Parse method has the following function declaration:

public static Dictionary<char, CharacterData> Parse(string filePath)

This method returns a list of character information but this declaration must change if we're to also extract kerning information for the characters. A good way to handle this is to rename and re-purpose the entire function so that it's declaration appears like this:

/// <summary>
/// Create a font object from a .fnt file (and associated textures)
/// </summary>
/// <param name="path">Path to the .fnt file.</param>
/// <param name="textureManager">Texture manager to load font textures</param>
/// <returns>Font as described by the .fnt file.</returns>
public static Font CreateFont(string path, TextureManager textureManager)

This CreateFont function replaces the old parse method. It takes in the path to the .fnt file and then loads any textures, finally returning a new font object. It needs to deal with the possibility of textures already existing in the TextureManager. Textures should only be loaded once and if a situation arises where a texture is being loaded more than once a warning needs to be produced and the situation handled. The TextureManager needs an extra method adding.

/// <summary>
/// Has a texture of this name already been loaded?
/// </summary>
/// <param name="textureId">The id of the texture to check</param>
/// <returns>true if a texture exits, false if it doesn't</returns>
public bool Exists(string textureId)
{
    return _textureDatabase.Keys.Contains(textureId);
}

With this method defined the upgraded FontParser class can be given in full. Once the FontParser is written the Font class itself will need updating so that it is aware of the kerning table. Then finally the Text class will need to be updated to actually use the kern data (and this is the place we'll fix the bugs with the font rendering).

  1 public class FontParser
  2 {
  3     static int HeaderSize = 2;
  4 
  5     // Gets the value after an equal sign and converts it
  6     // from a string to an integer
  7     private static int GetValue(string s)
  8     {
  9         string value = s.Substring(s.IndexOf('=') + 1);
 10         return int.Parse(value);
 11     }
 12 
 13 
 14     private static string GetTextValue(string s)
 15     {
 16         string value = s.Substring(s.IndexOf('=') + 1);
 17         return value;
 18     }
 19 
 20     /// <summary>
 21     /// Create a font object from a .fnt file (and associated textures)
 22     /// </summary>
 23     /// <param name="path">Path to the .fnt file.</param>
 24     /// <param name="textureManager">Texture manager to load font textures</param>
 25     /// <returns>Font as described by the .fnt file.</returns>
 26     public static Font CreateFont(string path, TextureManager textureManager)
 27     {
 28         List<Texture> _texturePages = new List<Texture>();
 29         Dictionary<KernKey, int> kernDictionary = new Dictionary<KernKey, int>();
 30         Dictionary<char, CharacterData> charDictionary = new Dictionary<char, CharacterData>();
 31 
 32         string[] lines = File.ReadAllLines(path);
 33 
 34         int texturePageInfo = HeaderSize;
 35         while (lines[texturePageInfo].StartsWith("page"))
 36         {
 37             string line = lines[texturePageInfo];
 38             string[] typesAndValues = line.Split(" ".ToCharArray(),
 39                 StringSplitOptions.RemoveEmptyEntries);
 40             string textureString = GetTextValue(typesAndValues[2]).Trim('"');
 41             string textureId = Path.GetFileNameWithoutExtension(textureString);
 42 
 43             if (textureManager.Exists(textureId))
 44             {
 45                 // Really textures should never be loaded twice so it's worth warning the user
 46                 Console.Error.WriteLine("WARNING: Tried to load a texture that had been already been loaded. "
 47                     + "[" + textureString + "] when loading font [" + path + "]");
 48             }
 49             else
 50             {
 51                 // Assume texture files are in the same path as the .fnt file.
 52                 string directory = Path.GetDirectoryName(path);
 53                 if (string.IsNullOrEmpty(directory) == false)
 54                 {
 55                     directory += "\\";
 56                 }
 57                 textureManager.LoadTexture(textureId, directory  + textureString);   
 58             }
 59 
 60             _texturePages.Add(textureManager.Get(textureId));
 61 
 62             texturePageInfo++;
 63         }
 64 
 65         texturePageInfo++; // jump over number of characters data.
 66 
 67         for (int i = texturePageInfo; i < lines.Length; i += 1)
 68         {
 69             string line = lines[i];
 70             string[] typesAndValues = line.Split(" ".ToCharArray(),
 71                 StringSplitOptions.RemoveEmptyEntries);
 72 
 73             // Some fonts have kerning data at the end
 74             if (line.StartsWith("kernings"))
 75             {
 76                 ParseKernData(i + 1, lines, kernDictionary);
 77                 break;
 78             }
 79 
 80             // All the data comes in a certain order,
 81             // used to make the parser shorter
 82             CharacterData charData = new CharacterData
 83             {
 84                 Id = GetValue(typesAndValues[1]),
 85                 X = GetValue(typesAndValues[2]),
 86                 Y = GetValue(typesAndValues[3]),
 87                 Width = GetValue(typesAndValues[4]),
 88                 Height = GetValue(typesAndValues[5]),
 89                 XOffset = GetValue(typesAndValues[6]),
 90                 YOffset = GetValue(typesAndValues[7]),
 91                 XAdvance = GetValue(typesAndValues[8])
 92             };
 93             charDictionary.Add((char)charData.Id, charData);
 94         }
 95 
 96         return new Font(_texturePages.FirstOrDefault(), charDictionary, kernDictionary);
 97     }
 98 
 99     private static void ParseKernData(int start, string[] lines, Dictionary<KernKey, int> kernDictionary)
100     {
101         for (int i = start; i < lines.Length; i += 1)
102         {
103             string line = lines[i];
104             string[] typesAndValues = line.Split(" ".ToCharArray(), 
105                 StringSplitOptions.RemoveEmptyEntries);
106             // As before the order of the enteries is used to make the parsing simpler.
107             KernKey key = new KernKey(GetValue(typesAndValues[1]), GetValue(typesAndValues[2]));
108             kernDictionary.Add(key, GetValue(typesAndValues[3]));
109         }
110     }
111 }

The new parser class has additional code to read in the kerning information. It'll also uses the .fnt file to find all the textures the font uses and put them in a list. At the end only the first item of this list is passed onto the Font object. This is because, for the moment, we're not support fonts that use more that one texture. It's a feature that's easy to add and it may be addressed in a later update.

Here's the updated Font class that can store this new kern data.
1 public class Font 2 { 3 Texture _texture; 4 Dictionary<char, CharacterData> _characterData; 5 Dictionary<KernKey, int> _kernData; 6 7 internal Font(Texture texture, Dictionary<char, CharacterData> characterData, Dictionary<KernKey, int> kernData) 8 { 9 _texture = texture; 10 _characterData = characterData; 11 _kernData = kernData; 12 } 13 14 public int GetKerning(char first, char second) 15 { 16 KernKey key = new KernKey((int)first, (int)second); 17 int outValue; 18 if(_kernData.TryGetValue(key, out outValue)) 19 { 20 return outValue; 21 } 22 return 0; 23 } 24 25 public Vector MeasureFont(string text) 26 { 27 return MeasureFont(text, -1); 28 } 29 30 public Vector MeasureFont(string text, double maxWidth) 31 { 32 Vector dimensions = new Vector(); 33 34 char lastChar = ' '; 35 foreach (char c in text) 36 { 37 CharacterData data = _characterData[c]; 38 dimensions.X += data.XAdvance + GetKerning(lastChar, c); 39 dimensions.Y = Math.Max(dimensions.Y, data.Height + data.YOffset); 40 lastChar = c; 41 } 42 return dimensions; 43 } 44 45 public CharacterSprite CreateSprite(char c) 46 { 47 CharacterData charData = _characterData[c]; 48 Sprite sprite = new Sprite(); 49 sprite.Texture = _texture; 50 51 // Setup UVs 52 Point topLeft = new Point((float)charData.X / (float)_texture.Width, 53 (float)charData.Y / (float)_texture.Height); 54 Point bottomRight = new Point(topLeft.X + ((float)charData.Width / (float)_texture.Width), 55 topLeft.Y + ((float)charData.Height / (float)_texture.Height)); 56 sprite.SetUVs(topLeft, bottomRight); 57 sprite.SetWidth(charData.Width); 58 sprite.SetHeight(charData.Height); 59 sprite.SetColor(new Color(1, 1, 1, 1)); 60 61 return new CharacterSprite(sprite, charData); 62 } 63 }

This new Font class can store the kerning data and it also uses it when measuring the font. The final class to be updated is the Text class.

1 private void CreateText(double x, double y, double maxWidth) 2 { 3 _bitmapText.Clear(); 4 double currentX = 0; 5 double currentY = 0; 6 7 string[] words = _text.Split(' '); 8 9 foreach (string word in words) 10 { 11 Vector nextWordLength = _font.MeasureFont(word); 12 13 if (maxWidth != -1 && 14 (currentX + nextWordLength.X) > maxWidth) 15 { 16 currentX = 0; 17 currentY += nextWordLength.Y; 18 } 19 20 string wordWithSpace = word + " "; // add the space character that was removed. 21 22 char lastChar = ' '; 23 foreach (char c in wordWithSpace) 24 { 25 int kernAmount = _font.GetKerning(lastChar, c); 26 CharacterSprite sprite = _font.CreateSprite(c); 27 var w = sprite.Sprite.GetWidth(); 28 29 float yOffset = (((float)sprite.Data.Height) * 0.5f) + ((float)sprite.Data.YOffset); 30 float xOffset = ((float)sprite.Data.XOffset) + kernAmount; 31 sprite.Sprite.SetPosition(x + currentX + (sprite.Sprite.GetWidth() / 2) + xOffset, y - currentY - yOffset); 32 currentX += sprite.Data.XAdvance; 33 System.Diagnostics.Debug.Assert((int)sprite.Sprite.GetWidth() == sprite.Data.Width); 34 35 _bitmapText.Add(sprite); 36 lastChar = c; 37 } 38 } 39 _dimensions = _font.MeasureFont(_text, _maxWidth); 40 _dimensions.Y = currentY; 41 SetColor(_color); 42 }

The inner loop now uses the kern data. The problem with the previous code (and cause of the bug) was that each character of the sprite wasn being position around it's center, the position needed to be adjusted so that it was the top left. Here's the Hello World again with the changes.


I think it's easy to see this version is far better!

Wednesday, June 02, 2010

Momentum

I've repointed the godpatterns url so it's pointing to this blog now and I'll slowly move across any good articles and content from the previous wordpress blog.

In the meantime:
Sublime - this is an excellent text editor that has recently appeared on to my radar. I'm using it at work to edit Lua and at home for a little Scheme and basic text.

Free GDC Talks - yay, can't beat that.

Recently I've finished writing a book about basic C# Game Programming. I'm going to be adding a few articles that follow on from code in the book.