Font glyph performance improvements

[JeffM2501]

There is currently a performance problem with font drawing.

The function GetGlyphIndex has to look process every record in the font’s glyph list every time for every character. This is because there may be gaps in the glyph indexes, and there is no code to do anything other than a brute force lookup. This lookup slows font drawing down by an additional 100 to 200%. There is code to do a simple lookup, but it only works for ASCII ordered glyphs and is tied to the SUPPORT_UNORDERED_CHARSET define, that is never set.

There is a better way we can do this, While we do need to support random glyphs, the majority of glyphs are used in ranges.

Instead of storing a simple array of glyphs in the font, we can store the glyphs as an array of ranges

typedef struct GlyphInfo {
    int glyphCount;         // Number of glyph characters
    GlyphInfo* glyphs;      // Glyphs info data
} GlyphRange;

// Font, font texture and GlyphInfo array data
typedef struct Font {
    int baseSize;           // Base size (default chars height)
    int glyphRangeCount;         // Number of glyph ranges 
    int glyphPadding;       // Padding around the glyph characters
    Texture2D texture;      // Texture atlas containing the glyphs
    Rectangle* recs;        // Rectangles in texture for the glyphs
    GlyphRange* glyphRanges;      // Glyphs info data
} Font;

This allows GetGlyphIndex to much more quickly find the range of glyphs that we need and can then do a simple index to get the actual item. Finding the item first involves
Walk the range array, finding the range that starts less than or equal to and ends greater than or equal to the desired glyph id.
Subtract the starting glyph ID from the desired ID and use that as an index into the range’s glyphs.

Default font loading already loads a contiguous range of characters so most text drawing will just be faster. Advanced codepoints will simply need to be built into ranges and stored sorted.

This will make font loading slightly more complex as we will need to sort the glyphs, but this is a one time thing, and the benefit in text drawing is huge.

Size wise, the font structure stays the same size so copying it will be identical. We will need to deallocate the array of glyph ranges when unloading a font, but this is also relatively easy compared to the benefit we get.

This post is intended to start the discussion about how we can speed up font drawing. The goal of this post is to have an agreed upon design before any code or PRs are submitted.

[williewillus]

An easy step that doesn't involve introducing new abstractions or changing the ABI: Sort the glyphs, and use binary search to look up the appropriate glyph. I know Raylib doesn't like adding new libc usages, but qsort(3) and bsearch(3) from libc should suffice here, or custom sorts/searches can be implemented, which will require more code.

The current code also looks up the fallback glyph every single time GetGlyphInfo is called; that should probably be precomputed once and cached in the Font itself (affects the ABI).