unexpectedly large kerning table

[phoddie]

When kerning is enabled with the --include-kerning-pairs option, the kerning tables can be surprisingly large. For example, when kerning is disabled the .fnt file generated from OpenSans using the Basic Latin, Latin-1 Supplement, and Cyrillic Unicode blocks is 9 KB. With kerning enabled, it is 489 KB.

fontbm is doing something very clever. It calculates synthetic kerning data for each possible glyph pair, even if the font does not contain a non-zero kerning offset for that pair. The relevant code is here:

fontbm/src/freeType/FtFont.h

Lines 205 to 216 in df0c2a8

	const auto error = FT_Get_Kerning(face, indexLeft, indexRight, FT_KERNING_UNFITTED, &kerning);
	if (error)
	throw std::runtime_error("Couldn't find glyphs kerning");
	// X advance is already in pixels for bitmap fonts
	if (!FT_IS_SCALABLE(face))
	return static_cast<int>(kerning.x);
	float firstRsbDelta = static_cast<float>(renderGlyph(nullptr, 0, 0, 0, 0, left, 0).rsbDelta);
	float secondLsbDelta = static_cast<float>(renderGlyph(nullptr, 0, 0, 0, 0, right, 0).lsbDelta);
	return static_cast <int> (std::floor((secondLsbDelta - firstRsbDelta + static_cast<float>(kerning.x) + 32) / static_cast<float>(1 << 6)));

This is clever because it allows effect of fractional adjustments for horizontal advance to be carried into the .fnt file which has only integer offsets. See the pseudocode for handling lsb_delta and rsb_delta in the FreeType documentation for details.

As an experiment, I disabled the generation of kerning pairs for pairs that have kerning offset of 0 by adding this check after line 207 in getKerning:

		if (!kerning.x)
			return 0;

With this in place, the .fnt output is 23 KB. That feels more reasonable.

FWIW – there is an inconsistency in the generation of the synthetic kerning pairs. If the font contain no kerning table !FT_HAS_KERNING(face) they are not generated.

The behavior currently implemented is clever, but it has a cost by increasing the kerning table output significantly (about 34x in this example). Further, it generates kerning data for pairs that are extremely unlikely to be used. The patch above could be a more reasonable default, or at least an option. For applications that want very precise layout and have the storage space for the larger tables, the current behavior seems great and could even be applied to fonts that do not containing a kerning table.

[vladimirgamalyan]

Draft fixes in the master branch now, the flag --include-kerning-pairs has been replaced with --kerning-pairs with additional kerning generation modes: disabled (no kerning at all), regular (using only FT_Get_Kerning() data) and extended (with additional adjustments from hinter).

I haven’t decided yet whether we need to have another mode, when these additional adjustments are applied only in case when FT_Get_Kerning returns a non-zero value (as in your patch: if (!kerning.x) return 0;). What do you think?

Also there is a new available output format: CBOR, saving up to 50% of bin format size, but requires a little more complex parsing.

[phoddie]

The kerning changes work well. Thank you! I think it makes sense to have options, so the behavior can evolve if needed. The additional mode you propose should be more precise for the kerned pairs. Rather than another mode, regular mode could always apply that refinement. I'm not sure either though. Maybe better to wait for a real-world situation it would benefit.

CBOR compresses nicely. I'm curious what motivated that addition. FWIW - Moddable has used CBOR over BLE to squeeze more data into the limited payloads. Our rendering engine accesses the BMFont tables directly at rendering time because RAM is so limited. (And our tools sort the kerning table to speed the look-up -- though it looks like the kerning table fontbm outputs is always sorted). Having to decode the tables on each glyph would be too much overhead.