"""True MSDF atlas generation from vector contours.
Generates multi-channel signed distance fields from FreeType glyph outlines.
Each RGB channel encodes distance to a different set of edges, enabling
sharp corner reconstruction in the fragment shader via median filtering.
"""
import logging
from dataclasses import dataclass
import numpy as np
from .font import Font, GlyphMetrics
log = logging.getLogger(__name__)
[docs]
@dataclass
class GlyphRegion:
"""Atlas region for a packed glyph."""
char: str
x: int
y: int
w: int
h: int
metrics: GlyphMetrics
u0: float = 0.0
v0: float = 0.0
u1: float = 0.0
v1: float = 0.0
[docs]
class MSDFAtlas:
"""MSDF font atlas with incremental shelf-based bin packing.
Glyphs are rendered on demand and appended to the atlas. ASCII is
pre-seeded at init time so Latin text works without re-uploads.
"""
_MAX_ATLAS_SIZE = 4096
def __init__(
self,
font: Font,
atlas_size: int = 1024,
glyph_padding: int = 4,
sdf_range: float = 4.0,
charset: str | None = None,
):
self.font = font
self.atlas_size = atlas_size
self.glyph_padding = glyph_padding
self.sdf_range = sdf_range
# Shelf packing state
self._shelf_y = 0
self._shelf_h = 0
self._cursor_x = 0
# Version tracking for GPU re-upload
self.version = 0
self.dirty = False
if charset is None:
charset = (
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" "0123456789 .!?:;,'-\"()[]{}/<>@#$%^&*+=_~`\\|"
)
self.atlas = np.zeros((atlas_size, atlas_size, 4), dtype=np.uint8)
self.regions: dict[str, GlyphRegion] = {}
# Pre-seed with initial charset (sorted tallest-first for packing)
self._seed(charset)
def _seed(self, charset: str) -> None:
"""Batch-add initial charset sorted by height for optimal packing."""
pad = self.glyph_padding
glyphs = []
for ch in charset:
if ch in self.regions:
continue
gm = self.font.get_glyph(ch)
w = max(gm.width + pad * 2, pad * 2 + 1)
h = max(gm.height + pad * 2, pad * 2 + 1)
glyphs.append((ch, gm, w, h))
glyphs.sort(key=lambda g: -g[3])
for ch, gm, w, h in glyphs:
self._pack_glyph(ch, gm, w, h)
self.version += 1
self.dirty = True
def _pack_glyph(self, ch: str, gm: GlyphMetrics, w: int, h: int) -> bool:
"""Pack a single glyph into the atlas. Returns True on success."""
if self._cursor_x + w > self.atlas_size:
self._shelf_y += self._shelf_h
self._shelf_h = 0
self._cursor_x = 0
if self._shelf_y + h > self.atlas_size:
if not self._grow_atlas():
return False
if h > self._shelf_h:
self._shelf_h = h
x, y = self._cursor_x, self._shelf_y
region = GlyphRegion(
char=ch,
x=x,
y=y,
w=w,
h=h,
metrics=gm,
u0=x / self.atlas_size,
v0=y / self.atlas_size,
u1=(x + w) / self.atlas_size,
v1=(y + h) / self.atlas_size,
)
self.regions[ch] = region
msdf = _render_glyph_msdf(gm, w, h, self.glyph_padding, self.sdf_range)
self.atlas[y : y + h, x : x + w, :3] = msdf
self.atlas[y : y + h, x : x + w, 3] = 255
self._cursor_x += w
return True
def _grow_atlas(self) -> bool:
"""Double atlas size (up to _MAX_ATLAS_SIZE), preserving existing data."""
new_size = self.atlas_size * 2
if new_size > self._MAX_ATLAS_SIZE:
return False
new_atlas = np.zeros((new_size, new_size, 4), dtype=np.uint8)
old = self.atlas_size
new_atlas[:old, :old, :] = self.atlas
self.atlas = new_atlas
self.atlas_size = new_size
# Recompute UVs for all existing regions
for r in self.regions.values():
r.u0 = r.x / new_size
r.v0 = r.y / new_size
r.u1 = (r.x + r.w) / new_size
r.v1 = (r.y + r.h) / new_size
return True
[docs]
def ensure_glyphs(self, text: str) -> bool:
"""Ensure all glyphs in *text* are in the atlas.
Returns True if the atlas was modified (caller should re-upload).
Glyphs missing from the underlying font are silently skipped.
"""
missing = [ch for ch in text if ch not in self.regions and ch not in (" ", "\n", "\t")]
if not missing:
return False
pad = self.glyph_padding
added = False
for ch in missing:
if not self.font.has_glyph(ch):
continue
gm = self.font.get_glyph(ch)
w = max(gm.width + pad * 2, pad * 2 + 1)
h = max(gm.height + pad * 2, pad * 2 + 1)
self._pack_glyph(ch, gm, w, h)
added = True
if added:
self.version += 1
self.dirty = True
return added
[docs]
def ensure_glyphs_from(self, chars: str, font: Font) -> bool:
"""Pack glyphs for *chars* using an external *font* into this atlas.
Used by the fallback chain: the primary atlas borrows glyphs from
a fallback font so all text renders from a single GPU texture.
Returns True if the atlas was modified.
"""
missing = [ch for ch in chars if ch not in self.regions and ch not in (" ", "\n", "\t")]
if not missing:
return False
pad = self.glyph_padding
added = False
for ch in missing:
if not font.has_glyph(ch):
continue
gm = font.get_glyph(ch)
w = max(gm.width + pad * 2, pad * 2 + 1)
h = max(gm.height + pad * 2, pad * 2 + 1)
self._pack_glyph(ch, gm, w, h)
added = True
if added:
self.version += 1
self.dirty = True
return added
[docs]
def missing_glyphs(self, text: str) -> list[str]:
"""Return characters from *text* that this atlas's font cannot render."""
return [
ch for ch in dict.fromkeys(text)
if ch not in self.regions and ch not in (" ", "\n", "\t") and not self.font.has_glyph(ch)
]
[docs]
def get_uv(self, char: str) -> tuple[float, float, float, float]:
if char not in self.regions:
char = "?"
if char not in self.regions:
return (0, 0, 0, 0)
r = self.regions[char]
return (r.u0, r.v0, r.u1, r.v1)
[docs]
class BitmapAtlas:
"""Font atlas using FreeType hinted bitmap rendering (no SDF).
Produces pixel-perfect glyphs at a fixed target size. The atlas format
is RGBA with R=G=B=coverage so the MSDF shader's median(r,g,b) acts as
a simple alpha blend passthrough.
"""
def __init__(
self,
font_path: str,
target_size: int,
atlas_size: int = 512,
charset: str | None = None,
):
from .font import Font
self.font = Font(font_path, size=target_size)
self.atlas_size = atlas_size
self.glyph_padding = 0
self.sdf_range = 0.5 # Small value — shader acts as simple alpha blend
self.version = 0
self.dirty = False
if charset is None:
charset = (
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
"0123456789 .!?:;,'-\"()[]{}/<>@#$%^&*+=_~`\\|"
)
self.atlas = np.zeros((atlas_size, atlas_size, 4), dtype=np.uint8)
self.regions: dict[str, GlyphRegion] = {}
# Shelf packing state
self._shelf_y = 0
self._shelf_h = 0
self._cursor_x = 0
self._seed(charset)
def _seed(self, charset: str) -> None:
glyphs = []
for ch in charset:
if ch in self.regions:
continue
bitmap, gm = self.font.render_bitmap(ch)
if bitmap.size == 0:
continue
glyphs.append((ch, bitmap, gm))
glyphs.sort(key=lambda g: -g[1].shape[0])
for ch, bitmap, gm in glyphs:
self._pack_glyph(ch, bitmap, gm)
self.version += 1
self.dirty = True
def _pack_glyph(self, ch: str, bitmap: np.ndarray, gm) -> bool:
h, w = bitmap.shape if bitmap.size > 0 else (1, 1)
if self._cursor_x + w > self.atlas_size:
self._shelf_y += self._shelf_h
self._shelf_h = 0
self._cursor_x = 0
if self._shelf_y + h > self.atlas_size:
return False
if h > self._shelf_h:
self._shelf_h = h
x, y = self._cursor_x, self._shelf_y
region = GlyphRegion(
char=ch, x=x, y=y, w=w, h=h, metrics=gm,
u0=x / self.atlas_size, v0=y / self.atlas_size,
u1=(x + w) / self.atlas_size, v1=(y + h) / self.atlas_size,
)
self.regions[ch] = region
if bitmap.size > 0:
# R=G=B=coverage, A=255 — median(r,g,b) passthrough for MSDF shader
self.atlas[y : y + h, x : x + w, 0] = bitmap
self.atlas[y : y + h, x : x + w, 1] = bitmap
self.atlas[y : y + h, x : x + w, 2] = bitmap
self.atlas[y : y + h, x : x + w, 3] = 255
self._cursor_x += w
return True
[docs]
def ensure_glyphs(self, text: str) -> bool:
missing = [ch for ch in text if ch not in self.regions and ch not in (" ", "\n", "\t")]
if not missing:
return False
added = False
for ch in missing:
if not self.font.has_glyph(ch):
continue
bitmap, gm = self.font.render_bitmap(ch)
if bitmap.size > 0:
self._pack_glyph(ch, bitmap, gm)
added = True
if added:
self.version += 1
self.dirty = True
return added
[docs]
def missing_glyphs(self, text: str) -> list[str]:
"""Return characters from *text* that this atlas's font cannot render."""
return [
ch for ch in dict.fromkeys(text)
if ch not in self.regions and ch not in (" ", "\n", "\t") and not self.font.has_glyph(ch)
]
[docs]
def get_uv(self, char: str) -> tuple[float, float, float, float]:
if char not in self.regions:
char = "?"
if char not in self.regions:
return (0, 0, 0, 0)
r = self.regions[char]
return (r.u0, r.v0, r.u1, r.v1)
# --- Edge types ---
class _Line:
__slots__ = ("p0", "p1")
def __init__(self, p0: tuple[float, float], p1: tuple[float, float]):
self.p0 = p0
self.p1 = p1
class _Quad:
__slots__ = ("p0", "p1", "p2")
def __init__(self, p0, p1, p2):
self.p0 = p0
self.p1 = p1
self.p2 = p2
def _resolve_contour(contour):
"""Insert implicit on-curve midpoints between consecutive off-curve points.
TrueType contours use quadratic Beziers where two adjacent off-curve
control points imply an on-curve point at their midpoint. After
resolution the point list strictly alternates on/off so edge
extraction becomes trivial.
"""
n = len(contour)
if n < 2:
return []
resolved = []
for i in range(n):
x, y, on = contour[i]
resolved.append((x, y, on))
if not on:
xn, yn, on_n = contour[(i + 1) % n]
if not on_n:
resolved.append(((x + xn) * 0.5, (y + yn) * 0.5, True))
return resolved
def _build_edges_per_contour(contours):
"""Convert contour points to edge segments, grouped by contour.
Returns list[list[_Line | _Quad]] — one inner list per contour.
Properly handles consecutive off-curve points via midpoint resolution.
"""
result = []
for contour in contours:
resolved = _resolve_contour(contour)
n = len(resolved)
if n < 2:
continue
# Rotate to start from an on-curve point
start = next((i for i, (_, _, on) in enumerate(resolved) if on), None)
if start is None:
continue
resolved = resolved[start:] + resolved[:start]
n = len(resolved)
edges: list[_Line | _Quad] = []
i = 0
while i < n:
x0, y0, on0 = resolved[i]
if not on0:
i += 1
continue
j = (i + 1) % n
x1, y1, on1 = resolved[j]
if on1:
edges.append(_Line((x0, y0), (x1, y1)))
i += 1
else:
k = (j + 1) % n
x2, y2, _ = resolved[k]
edges.append(_Quad((x0, y0), (x1, y1), (x2, y2)))
i += 2
if edges:
result.append(edges)
return result
def _tessellate_contour(contour, steps: int = 8) -> list[tuple[float, float]]:
"""Convert a contour with off-curve control points to a polyline.
Subdivides quadratic Bezier curves into line segments.
"""
poly = []
n = len(contour)
if n < 2:
return poly
i = 0
while i < n:
x0, y0, on0 = contour[i]
x1, y1, on1 = contour[(i + 1) % n]
if on0 and on1:
# Line segment
poly.append((x0, y0))
i += 1
elif on0 and not on1:
# Quadratic Bezier: find endpoint
x2, y2, on2 = contour[(i + 2) % n]
if not on2:
# Implicit on-curve point between two off-curve
x2, y2 = (x1 + x2) * 0.5, (y1 + y2) * 0.5
i += 1
else:
i += 2
# Subdivide the quadratic Bezier
for si in range(steps):
t = si / steps
s = 1.0 - t
bx = s * s * x0 + 2 * s * t * x1 + t * t * x2
by = s * s * y0 + 2 * s * t * y1 + t * t * y2
poly.append((bx, by))
elif not on0:
# Off-curve start: need implicit on-curve from previous
# This handles the case where contour starts with off-curve
xp, yp, _ = contour[(i - 1) % n]
mx, my = (xp + x0) * 0.5, (yp + y0) * 0.5
if on1:
for si in range(steps):
t = si / steps
s = 1.0 - t
bx = s * s * mx + 2 * s * t * x0 + t * t * x1
by = s * s * my + 2 * s * t * y0 + t * t * y1
poly.append((bx, by))
i += 1
else:
mx2, my2 = (x0 + x1) * 0.5, (y0 + y1) * 0.5
for si in range(steps):
t = si / steps
s = 1.0 - t
bx = s * s * mx + 2 * s * t * x0 + t * t * mx2
by = s * s * my + 2 * s * t * y0 + t * t * my2
poly.append((bx, by))
i += 1
else:
i += 1
return poly
def _winding_number(px: float, py: float, contours) -> int:
"""Compute winding number of point relative to all contours.
Tessellates Bezier curves before testing. Nonzero winding = inside.
"""
wn = 0
for contour in contours:
poly = _tessellate_contour(contour)
n = len(poly)
if n < 2:
continue
for i in range(n):
x0, y0 = poly[i]
x1, y1 = poly[(i + 1) % n]
if y0 <= py:
if y1 > py:
cross = (x1 - x0) * (py - y0) - (px - x0) * (y1 - y0)
if cross > 0:
wn += 1
else:
if y1 <= py:
cross = (x1 - x0) * (py - y0) - (px - x0) * (y1 - y0)
if cross < 0:
wn -= 1
return wn
def _dist_line_vec(gx, gy, p0, p1):
"""Vectorized distance from pixel grid to a line segment."""
ax, ay = p0
bx, by = p1
dx, dy = bx - ax, by - ay
len_sq = dx * dx + dy * dy
if len_sq < 1e-10:
return np.sqrt((gx - ax) ** 2 + (gy - ay) ** 2)
t = np.clip(((gx - ax) * dx + (gy - ay) * dy) / len_sq, 0.0, 1.0)
cx = ax + t * dx
cy = ay + t * dy
return np.sqrt((gx - cx) ** 2 + (gy - cy) ** 2)
def _dist_quad_vec(gx, gy, p0, p1, p2):
"""Vectorized distance from pixel grid to a quadratic Bezier."""
# Coarse sampling to find best t
ts = np.linspace(0, 1, 9).reshape(-1, 1, 1) # (9, 1, 1)
ss = 1.0 - ts
bx = ss * ss * p0[0] + 2 * ss * ts * p1[0] + ts * ts * p2[0]
by = ss * ss * p0[1] + 2 * ss * ts * p1[1] + ts * ts * p2[1]
d_sq = (gx - bx) ** 2 + (gy - by) ** 2 # (9, h, w)
best_idx = np.argmin(d_sq, axis=0) # (h, w)
best_t = best_idx / 8.0
# Newton refinement (3 iterations)
for _ in range(3):
s = 1.0 - best_t
bx = s * s * p0[0] + 2 * s * best_t * p1[0] + best_t * best_t * p2[0]
by = s * s * p0[1] + 2 * s * best_t * p1[1] + best_t * best_t * p2[1]
tx = 2 * (s * (p1[0] - p0[0]) + best_t * (p2[0] - p1[0]))
ty = 2 * (s * (p1[1] - p0[1]) + best_t * (p2[1] - p1[1]))
dpx = gx - bx
dpy = gy - by
dot = dpx * tx + dpy * ty
tang_sq = tx * tx + ty * ty
mask = tang_sq > 1e-10
best_t = np.where(mask, np.clip(best_t + dot / np.maximum(tang_sq, 1e-10), 0, 1), best_t)
s = 1.0 - best_t
bx = s * s * p0[0] + 2 * s * best_t * p1[0] + best_t * best_t * p2[0]
by = s * s * p0[1] + 2 * s * best_t * p1[1] + best_t * best_t * p2[1]
return np.sqrt((gx - bx) ** 2 + (gy - by) ** 2)
def _winding_number_vec(gx, gy, contours):
"""Vectorized winding number for entire pixel grid.
Returns int array (h, w): nonzero = inside glyph.
"""
wn = np.zeros_like(gx, dtype=np.int32)
for contour in contours:
poly = _tessellate_contour(contour)
n = len(poly)
if n < 2:
continue
for i in range(n):
x0, y0 = poly[i]
x1, y1 = poly[(i + 1) % n]
# Upward crossing
up = (y0 <= gy) & (y1 > gy)
cross_up = (x1 - x0) * (gy - y0) - (gx - x0) * (y1 - y0)
wn += (up & (cross_up > 0)).astype(np.int32)
# Downward crossing
down = (y0 > gy) & (y1 <= gy)
cross_down = (x1 - x0) * (gy - y0) - (gx - x0) * (y1 - y0)
wn -= (down & (cross_down < 0)).astype(np.int32)
return wn
def _render_glyph_msdf(gm, w, h, pad, sdf_range):
"""Render a single glyph as MSDF (RGB uint8).
Vectorized with NumPy — processes all pixels at once per edge.
Channel assignment cycles per-contour with wraparound fix so
adjacent edges (including first↔last) always differ.
"""
if not gm.contours:
return np.zeros((h, w, 3), dtype=np.uint8)
contour_edges = _build_edges_per_contour(gm.contours)
if not contour_edges:
return np.zeros((h, w, 3), dtype=np.uint8)
msdf = np.full((h, w, 3), 128, dtype=np.uint8)
# Build coordinate grids in glyph space
px = np.arange(w, dtype=np.float64)
py = np.arange(h, dtype=np.float64)
px_grid, py_grid = np.meshgrid(px, py)
gx = (px_grid - pad) + gm.bearing_x
gy = pad + gm.bearing_y - py_grid
# Winding number for inside/outside
wn = _winding_number_vec(gx, gy, gm.contours)
sign = np.where(wn != 0, 1.0, -1.0)
# Per-channel minimum distance
ch_dist = np.full((3, h, w), np.inf, dtype=np.float64)
# Channel pairs: edge i → channels ch_pairs[i % 3]
# Adjacent edges share exactly one channel, enabling corner detection.
ch_pairs = [[0, 1], [1, 2], [2, 0]]
for edges in contour_edges:
ne = len(edges)
for ei, edge in enumerate(edges):
ch_idx = ei % 3
# Wraparound fix: when ne % 3 == 1 the last edge would get the
# same pair as the first, merging both channels at their corner.
# Shift it to share only one channel instead.
if ne > 1 and ei == ne - 1 and ch_idx == 0:
ch_idx = 1
d = (
_dist_quad_vec(gx, gy, edge.p0, edge.p1, edge.p2)
if isinstance(edge, _Quad)
else _dist_line_vec(gx, gy, edge.p0, edge.p1)
)
for ch in ch_pairs[ch_idx]:
ch_dist[ch] = np.minimum(ch_dist[ch], d)
# Convert to signed distance and map to [0, 255]
for ch in range(3):
sd = ch_dist[ch] * sign
val = (sd / sdf_range + 1.0) * 0.5
msdf[:, :, ch] = np.clip(val * 255, 0, 255).astype(np.uint8)
return msdf