"""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.
"""
from __future__ import annotations
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