diff options
| author | eunhhu <[email protected]> | 2026-09-27 08:56:47 +0100 |
|---|---|---|
| committer | eunhhu <[email protected]> | 2026-09-27 08:56:47 +0100 |
| commit | 2acf27f665f8a926d244efa58f6ef2c92d65e8c4 (patch) | |
| tree | bbe910b904b64876eab1b206226aad1fe7caf1ff | |
| parent | 523b810d6a9c60342c7f5d74f36fe66f3f2057e9 (diff) | |
| download | vega-2acf27f665f8a926d244efa58f6ef2c92d65e8c4.tar.gz vega-2acf27f665f8a926d244efa58f6ef2c92d65e8c4.zip | |
Store symbol outlines as point chains, and keep glyph advances whole
Format 2 (VEGASYM2) writes each contour as a chain of 4-byte points, on or
off the curve as in TrueType: endpoints are shared, lines have no control
point, and two off points imply the on point between them. A curve is still
had from one point and its two neighbours, so a GPU can point at curves by
point index and upload the table as it is. Cubics (CFF, SVG curves and arcs)
become quadratic splines the cu2qu way, joins left implied, within a unit.
Files are about half of format 1: 1.3-1.4x a TrueType font's glyf (the
whole subset font's size), 2.0-2.9x CFF, 2.6x smaller than the SVG icons.
Opening checks each symbol's first and last point instead of every curve:
0.34 ms rather than 19 ms for 11,172 Hangul syllables. Points decode
without branching on their flags (9.7 ns a point), still 1.2-10x cheaper
than FreeType's outline.
Glyph advances were half their width since outlines are doubled for
FreeType's implied points; they now match hmtx, and the check says so.
| -rw-r--r-- | docs/design/002-symbol-format.md | 90 | ||||
| -rw-r--r-- | src/symbols-tool.c | 305 | ||||
| -rw-r--r-- | src/symbols.c | 83 | ||||
| -rw-r--r-- | src/symbols.h | 38 | ||||
| -rw-r--r-- | tests/check.py | 19 |
5 files changed, 378 insertions, 157 deletions
diff --git a/docs/design/002-symbol-format.md b/docs/design/002-symbol-format.md index 3f2c2a8..362798b 100644 --- a/docs/design/002-symbol-format.md +++ b/docs/design/002-symbol-format.md @@ -12,25 +12,34 @@ 재고, 크기와 여는 시간을 잰다. SVG 아이콘 몇 개를 같은 형식으로 바꿔 그려 본다. - 중단 기준: FreeType과의 평균 차이가 256단계 중 8을 넘으면 형식이나 알고리즘을 다시 본다. -## 형식 (`VEGASYM1`, 리틀 엔디언) +## 형식 (`VEGASYM2`, 리틀 엔디언) | 오프셋 | 내용 | |---|---| -| 0 | `VEGASYM1` | +| 0 | `VEGASYM2` | | 8 | u16 단위(em당), u16 0 | -| 12 | u32 심볼 수, u32 곡선 수, u32 파일 크기, u32 0 | -| 28 | 심볼 × 24 B, 코드 순: u32 코드(글리프는 코드 포인트, 아이콘은 빌드 도구가 준 번호), u32 첫 곡선, u32 곡선 수, i16 경계 왼쪽·아래·오른쪽·위, i16 advance, u16 플래그(0) | -| 28 + 24n | 곡선 × 12 B: i16 x0 y0 x1 y1 x2 y2, 2차 베지에. 직선은 가운데 제어점을 끝점과 같게 둔다 | - -- 좌표는 단위 공간, y가 위로 는다(폰트와 같다). 곡선은 심볼마다 닫힌 윤곽들을 이루고, 채우기는 0이 아닌 감김수다. -- 여는 쪽은 심볼마다 한 번 검증한다. 크기가 맞고, 코드가 오름차순이며, 곡선 범위가 곡선 표 안이고, 경계가 뒤집히지 않았다. - 그다음 읽기는 파일 밖으로 나가지 않는다. 곡선 하나하나는 보지 않는다(경계를 벗어난 곡선은 잘못 그려질 뿐이다). 그래서 여는 - 비용은 곡선 수가 아니라 심볼 수에 비례한다. 곡선 표는 그대로 GPU의 저장 버퍼가 될 수 있는 고정 레코드다(해석 없이 올린다). -- 3차 곡선(OpenType CFF, SVG의 `C`)은 빌드할 때 2차 곡선들로 나눈다(단위 공간에서 오차 0.5 이하). +| 12 | u32 심볼 수, u32 점 수, u32 파일 크기, u32 0 | +| 28 | 심볼 × 24 B, 코드 순: u32 코드(글리프는 코드 포인트, 아이콘은 빌드 도구가 준 번호), u32 첫 점, u32 점 수, i16 경계 왼쪽·아래·오른쪽·위, i16 advance, u16 플래그(0) | +| 28 + 24n | 점 × 4 B: i16 2x + 곡선 밖, i16 2y + 윤곽 시작 | + +- 좌표는 단위 공간, y가 위로 는다(폰트와 같다). 채우기는 0이 아닌 감김수다. +- 윤곽은 점의 사슬이다(TrueType의 점 모델을 압축 없이). 윤곽은 곡선 위의 시작 점으로 열고, 그 점으로 돌아온 점으로 닫는다. 곡선 밖 + 점은 2차 곡선의 제어점이고, 곡선 밖 점 둘이 이어지면 그 가운데에 곡선 위 점이 있는 것으로 친다(적지 않는다). 곡선 위 점 둘이 + 이어지면 직선이다(제어점이 없다). +- 그래서 곡선 하나는 점 하나와 그 이웃 둘로 정해진다. 곡선 밖 점은 한 곡선의 제어점이고, 같은 윤곽의 곡선 위 점이 뒤따르는 곡선 + 위 점은 한 직선의 시작이다. GPU는 곡선 번호 대신 점 번호로 곡선을 가리키고 4바이트 셋을 읽는다. 점 하나가 32비트 한 워드라서 + 점 표가 그대로 `RG16I` 텍스처나 저장 버퍼가 된다(해석 없이 올린다). +- 여는 쪽은 심볼마다 한 번 검증한다. 크기가 맞고, 코드가 오름차순이며, 점 범위가 점 표 안이고, 경계가 뒤집히지 않았고, 첫 점이 + 곡선 위의 윤곽 시작이며 마지막 점이 곡선 위다. 그러면 곡선 밖 점의 이웃은 늘 같은 심볼 안에 있어서 그다음 읽기는 심볼 밖으로 + 나가지 않는다. 점 하나하나는 보지 않는다(경계를 벗어난 점은 잘못 그려질 뿐이다). 여는 비용은 점 수가 아니라 심볼 수에 비례한다. +- 좌표는 ±16,383 단위 안이다(플래그가 한 비트씩 쓴다). 빌드 도구는 모든 점이 짝수인 동안 단위를 반으로 줄이므로 TrueType + 글꼴은 제 단위로 손실 없이 담긴다. +- 3차 곡선(OpenType CFF, SVG의 `C`와 호)은 빌드할 때 2차 곡선 사슬로 바꾼다. cu2qu(fontTools)의 방법으로, 이음점이 이웃 제어점의 + 가운데에 오게 해서(적지 않는다) 오차 1단위 안에 드는 가장 적은 조각을 고른다. ## 그리기 -참조 래스터라이저(`vega_symbol_coverage`)는 GPU에서 픽셀마다 돌릴 계산을 그대로 C로 쓴 것이다. 픽셀이 덮인 넓이를 정확히 구한다. +참조 래스터라이저(`vega_coverage`)는 GPU에서 픽셀마다 돌릴 계산을 그대로 C로 쓴 것이다. 픽셀이 덮인 넓이를 정확히 구한다. 곡선마다 픽셀 [0, 1]² 안에 든 부분에서 clamp(1 − x, 0, 1) dy를 적분해 더하면, 닫힌 윤곽 전체의 합이 덮인 넓이가 된다(그린 정리, 반시계면 음수). 곡선은 픽셀의 네 변을 지나는 t(2차 방정식의 근, 최대 8개)에서 나뉘고, 조각마다 픽셀의 왼쪽이면 dy를 통째로, 오른쪽이면 0을, 걸쳐 있으면 t의 3차 다항식을 닫힌 꼴로 적분한다. 겹친 윤곽은 감김수를 넓이로 더한 뒤 절댓값을 1로 자른다 @@ -46,39 +55,48 @@ | 글꼴 | 8px | 12px | 16px | 32px | 64px | |---|---|---|---|---|---| -| DejaVu Sans ASCII (TrueType) 평균 차이 / 최악 | 1.86 / 15 | 1.82 / 16 | 1.50 / 19 | 0.69 / 21 | 0.40 / 26 | -| Nimbus Sans ASCII (CFF) | 3.48 / 31 | 3.19 / 33 | 2.67 / 37 | 1.53 / 47 | 0.80 / 46 | +| DejaVu Sans ASCII (TrueType) 평균 차이 / 최악 | 1.86 / 15 | 1.83 / 17 | 1.51 / 20 | 0.70 / 23 | 0.40 / 26 | +| Nimbus Sans ASCII (CFF) | 3.50 / 31 | 3.22 / 33 | 2.71 / 38 | 1.57 / 47 | 0.83 / 49 | | Baekmuk Batang 한글 11,172자 (TrueType) | | | 1.21 / 24 | | | -| Noto Sans CJK 한글 11,172자 (CFF) | | | 1.69 / 46 | | | +| Noto Sans CJK 한글 11,172자 (CFF) | | | 1.71 / 45 | | | 차이가 큰 픽셀을 64×64 슈퍼샘플링(곡선 256분할)과 대 보면 우리 값은 0.5단계 안에서 맞고 FreeType 값이 벗어나 있다. 남은 차이는 FreeType 쪽 곡선 근사(특히 CFF)다. -변환은 손실이 없다. 글꼴 단위의 두 배를 단위로 쓰면(TrueType의 암시 점, 두 제어점의 중점이 정수에 떨어진다) 글리프 넓이가 -fontTools가 원본 glyf에서 잰 넓이와 0.03 단위² 안에서 같다. FreeType은 암시 점을 정수 나눗셈으로 구하므로 윤곽을 두 배로 늘린 -뒤에 걷는다. CFF는 3차 곡선을 나누므로 em² 대비 평균 1.7e-5 차이다. SVG는 Adwaita 기호 아이콘 575개 중 458개를 변환했고 -(불투명도 82, 변환 23, evenodd 11, 획 1은 거부), fontTools의 SVG 경로 해석과 넓이 차이가 아이콘 픽셀² 평균 0.035, 최악 0.22다 -(16×16 아이콘에서 가장자리가 1/140 픽셀 움직인 정도). - -크기와 읽는 비용(윤곽 표는 fontTools로 해당 글자만 남기고 힌팅을 뺀 부분 폰트의 glyf+loca 또는 CFF): - -| 경우 | 곡선 | 심볼 파일 | 윤곽 표 | gzip 심볼 / 부분 폰트 | 윤곽 하나 (우리 / FreeType) | -|---|---|---|---|---|---| -| DejaVu ASCII | 1,463 | 19,864 B | 7,860 B | 10,059 / 6,466 B | 119 / 544 ns | -| Nimbus ASCII (CFF) | 1,720 | 22,948 B | 5,960 B | 12,160 / 5,851 B | 133 / 3,523 ns | -| Baekmuk 한글 | 1,927,588 | 23.4 MB | 9.55 MB | 6.85 / 1.98 MB | 836 / 4,208 ns | -| Noto CJK 한글 (CFF) | 569,159 | 7.10 MB | 1.08 MB | 2.43 / 0.80 MB | 324 / 9,352 ns | -| Adwaita 아이콘 458개 | 24,341 | 303 KB | SVG 452 KB | 115 / 205 KB | | - -윤곽에 닿는 비용은 FreeType보다 4.6–29배 싸다(해석할 것이 없다). SVG보다는 작다. 그러나 폰트보다 2.1–6.6배 크다. 곡선마다 -12바이트를 따로 두어 이웃 곡선이 끝점을 두 번 적고, 직선(Noto 한글은 66%)도 제어점을 가진다. 이것이 다음 질문이다. 윤곽을 점 -사슬로 적어 끝점을 나누고 직선의 제어점을 빼면(TrueType의 점 모델을 압축 없이) 추정 크기는 DejaVu 11.7 KB, Noto 한글 3.5 MB다. +변환은 TrueType에서 손실이 없다. 글리프 넓이가 fontTools가 원본 glyf에서 잰 넓이와 1단위² 안에서 같고 advance가 hmtx와 같다 +(검사가 지킨다). FreeType은 암시 점을 정수 나눗셈으로 구하므로 윤곽을 두 배로 늘린 뒤에 걷고, 다 쓴 뒤 단위를 되돌린다. CFF는 +em² 대비 평균 2.6e-5, 최악 1.5e-4 차이다. SVG는 Adwaita 기호 아이콘 575개 중 458개를 변환했고(불투명도 82, 변환 23, evenodd +11, 획 1은 거부), fontTools의 SVG 경로 해석과 넓이 차이가 아이콘 픽셀² 평균 0.013, 최악 0.19다. + +크기와 읽는 비용. 윤곽 표는 fontTools로 해당 글자만 남기고 힌팅을 뺀 부분 폰트의 glyf+loca 또는 CFF다. 1판은 곡선마다 12바이트 +레코드였다. + +| 경우 | 점 / 곡선 | 1판 | 2판 | 윤곽 표 | gzip 2판 / 부분 폰트 | 윤곽 하나 (우리 / FreeType) | +|---|---|---|---|---|---|---| +| DejaVu ASCII | 1,933 / 1,463 | 19,864 B | 10,040 B | 7,860 B | 6,944 / 6,465 B | 271 / 539 ns | +| Nimbus ASCII (CFF) | 2,444 / 1,873 | 22,948 B | 12,084 B | 5,960 B | 8,726 / 5,851 B | 334 / 3,529 ns | +| Baekmuk 한글 | 3.28M / 1.93M | 23.4 MB | 13.4 MB | 9.55 MB | 5.50 / 1.98 MB | 3.6 / 4.2 µs | +| Noto CJK 한글 (CFF) | 723K / 598K | 7.10 MB | 3.16 MB | 1.08 MB | 1.37 / 0.80 MB | 1.0 / 9.3 µs | +| Adwaita 아이콘 458개 | | 303 KB | 173 KB | SVG 452 KB | 97 / 205 KB | | + +- 여는 비용: 2판은 DejaVu ASCII 2.5 µs(FreeType 12.7 µs), 한글 11,172자 0.34 ms(FreeType 0.03–0.39 ms). 1판은 곡선마다 경계를 + 검사해 한글에서 19 ms였다. +- 크기: 점을 나누고 직선의 제어점과 암시 점을 빼서 1판의 절반 안팎이 되었다. TrueType 원본의 1.3–1.4배(부분 폰트 파일 전체와는 + 비슷하다), CFF의 2.0–2.9배다. CFF는 3차 곡선과 서브루틴, 가변 길이 정수로 적으므로 고정 크기 점으로는 따라가기 어렵다. 전송은 + gzip이 차이를 줄인다. SVG보다는 2.6배 작다. +- 윤곽 하나에 닿는 비용: 점마다 이웃을 보고 암시 점을 만들어야 해서 1판(곡선을 그대로 읽는다)보다 느려졌다. 곡선 위·밖 플래그가 + 데이터에 따라 바뀌어 분기 예측이 틀리므로 해독은 분기 없이 산술로 한다(점당 9.7 ns). 그래도 TrueType보다 1.2–2배, CFF보다 + 9–10배 싸다. GPU는 해독하지 않고 점을 그대로 읽는다. +- 참조 래스터라이저: 16px 글리프당 24 µs(CPU, 픽셀마다 모든 곡선). GPU에서 띠(band)로 곡선을 추리는 것이 다음이다. + +처음 계획은 12바이트 곡선 레코드(1판)였다. 윤곽에 닿는 비용은 더 쌌지만(119 ns) 폰트의 2.1–6.6배 크기였고, 여는 비용이 곡선 수에 +비례했다. "초경량"이라는 목표에 맞지 않아서 점 사슬로 바꿨다. ## 도구 `vega-symbols build [--font 폰트 --codes 0x20-0x7e,…] [--svg 번호=아이콘.svg …] [--units N] -o 심볼.vsym`: FreeType으로 글리프 -윤곽을 단위 그대로(`FT_LOAD_NO_SCALE`) 읽고, SVG는 `path`의 `d`를 읽어 viewBox(없으면 width·height)의 높이를 em으로 맞춘다. +윤곽을 단위 그대로(`FT_LOAD_NO_SCALE`) 읽고(단위는 글꼴 단위의 두 배에서 시작해 줄인다. 아이콘만이면 4,096), SVG는 `path`의 `d`를 읽어 viewBox(없으면 width·height)의 높이를 em으로 맞춘다. 호(`A`)는 4분의 1 바퀴 이하의 3차 곡선으로, 3차 곡선은 2차 곡선으로 나눈다. 칠해진 경로만 받는다. 변환, 불투명도, evenodd, 획, 경로 밖의 도형을 쓰는 아이콘은 이름을 대고 거부한다(빠뜨리고 그리면 틀린 그림이 된다). 해석은 여기서 한 번이다. -`compare`(FreeType과 픽셀 차이, 여는 시간, 윤곽 하나에 닿는 시간), `info`(심볼마다 곡선 수, 경계, 넓이), `render`(PGM)는 +`compare`(FreeType과 픽셀 차이, 여는 시간, 윤곽 하나에 닿는 시간), `info`(심볼마다 점·곡선 수, 경계, 넓이), `render`(PGM)는 검증과 측정용이다. `tests/check.py`의 10번이 이것들로 형식을 지킨다. diff --git a/src/symbols-tool.c b/src/symbols-tool.c index bec8656..e957c9e 100644 --- a/src/symbols-tool.c +++ b/src/symbols-tool.c @@ -18,81 +18,129 @@ #define PI 3.14159265358979323846 typedef struct { double x, y; } Point; -typedef struct { Point p[3]; } Quad; -typedef struct { Quad *items; size_t count, capacity; Point at, start; bool open; double font_scale; } Path; -typedef struct { uint32_t code; size_t first, count; int16_t advance; } Built; +/* An outline as the pen drew it. smooth: the end lies halfway between this + * control and the next, by construction, so it may go unwritten. */ +typedef enum { MOVE, LINE, QUAD } Kind; +typedef struct { Kind kind; bool smooth; Point control, end; } Segment; +typedef struct { Segment *items; size_t count, capacity; Point at, start; bool open; double font_scale; } Path; +typedef struct { uint32_t code; size_t first, count; int16_t advance; } Built; /* segments [first, first + count) */ static void fail(const char *why) { fprintf(stderr, "vega-symbols: %s\n", why); exit(1); } -static void add_quad(Path *path, Point a, Point b, Point c) { +static void add(Path *path, Segment segment) { if (path->count == path->capacity) { path->capacity = path->capacity ? 2 * path->capacity : 64; if (!(path->items = realloc(path->items, path->capacity * sizeof(*path->items)))) fail("out of memory"); } - path->items[path->count++] = (Quad){{a, b, c}}; + path->items[path->count++] = segment; + path->at = segment.end; } -/* A line is a quadratic whose control point is its middle. */ +static bool same(Point a, Point b) { return a.x == b.x && a.y == b.y; } + static void line_to(Path *path, Point to) { - if (to.x != path->at.x || to.y != path->at.y) - add_quad(path, path->at, (Point){(path->at.x + to.x) / 2, (path->at.y + to.y) / 2}, to); - path->at = to; + if (!same(to, path->at)) add(path, (Segment){LINE, false, to, to}); } -static void quad_to(Path *path, Point control, Point to) { - add_quad(path, path->at, control, to); - path->at = to; +static void quad_to(Path *path, Point control, Point to) { add(path, (Segment){QUAD, false, control, to}); } + +static Point lerp(Point a, Point b, double t) { return (Point){a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t}; } +static double length(double x, double y) { return sqrt(x * x + y * y); } + +/* Whether the cubic of these differences stays within tolerance of zero + * (split in halves until its control points do). */ +static bool fits(Point p0, Point p1, Point p2, Point p3, double tolerance) { + if (length(p1.x, p1.y) <= tolerance && length(p2.x, p2.y) <= tolerance) return true; + Point mid = {(p0.x + 3 * (p1.x + p2.x) + p3.x) / 8, (p0.y + 3 * (p1.y + p2.y) + p3.y) / 8}; + if (length(mid.x, mid.y) > tolerance) return false; + Point d = {(p3.x + p2.x - p1.x - p0.x) / 8, (p3.y + p2.y - p1.y - p0.y) / 8}; + return fits(p0, lerp(p0, p1, 0.5), (Point){mid.x - d.x, mid.y - d.y}, mid, tolerance) && + fits(mid, (Point){mid.x + d.x, mid.y + d.y}, lerp(p2, p3, 0.5), p3, tolerance); } -/* A cubic as quadratics, within half a unit: split in n equal pieces, each - * approximated by the quadratic through its ends with the control point - * (3(c1 + c2) - (p0 + p3)) / 4. The error shrinks with the cube of n. */ -static void cubic_to(Path *path, Point c1, Point c2, Point to) { - Point p0 = path->at; - double dx = to.x - 3 * c2.x + 3 * c1.x - p0.x, dy = to.y - 3 * c2.y + 3 * c1.y - p0.y; - double error = sqrt(3) / 36 * sqrt(dx * dx + dy * dy); - int n = (int)ceil(cbrt(error / 0.5)); - if (n < 1) n = 1; - if (n > 64) n = 64; +/* The piece of cubic c over [a, b], as a cubic. */ +static void piece(const Point c[4], double a, double b, Point out[4]) { + Point q[4]; + for (int k = 0; k < 2; ++k) { + double t = k ? b : a, u = 1 - t; + Point e = {u * u * u * c[0].x + 3 * u * u * t * c[1].x + 3 * u * t * t * c[2].x + t * t * t * c[3].x, + u * u * u * c[0].y + 3 * u * u * t * c[1].y + 3 * u * t * t * c[2].y + t * t * t * c[3].y}; + Point d = {3 * (u * u * (c[1].x - c[0].x) + 2 * u * t * (c[2].x - c[1].x) + t * t * (c[3].x - c[2].x)), + 3 * (u * u * (c[1].y - c[0].y) + 2 * u * t * (c[2].y - c[1].y) + t * t * (c[3].y - c[2].y))}; + double h = (b - a) / 3 * (k ? -1 : 1); + q[3 * k] = e; + q[1 + k] = (Point){e.x + d.x * h, e.y + d.y * h}; + } + memcpy(out, q, sizeof(q)); +} + +/* A cubic as a quadratic spline whose joins lie halfway between neighbouring + * controls (so they go unwritten), within tolerance: the approach of cu2qu + * (fontTools). With n pieces, piece i takes its control on the line between + * the points where the cubic's end tangents reach 1.5 times their control + * arms, at i / (n - 1); the fewest pieces that fit win. */ +static bool spline(const Point c[4], int n, double tolerance, Point *controls) { + if (n == 1) { + /* One quadratic: its control where the end tangents meet. */ + Point a = {c[1].x - c[0].x, c[1].y - c[0].y}, b = {c[2].x - c[3].x, c[2].y - c[3].y}; + double cross = a.x * b.y - a.y * b.x; + if (fabs(cross) < 1e-12) return false; + double t = ((c[3].x - c[0].x) * b.y - (c[3].y - c[0].y) * b.x) / cross; + controls[0] = (Point){c[0].x + a.x * t, c[0].y + a.y * t}; + Point q1 = lerp(c[0], controls[0], 2.0 / 3), q2 = lerp(c[3], controls[0], 2.0 / 3); + return fits((Point){0, 0}, (Point){q1.x - c[1].x, q1.y - c[1].y}, (Point){q2.x - c[2].x, q2.y - c[2].y}, + (Point){0, 0}, tolerance); + } + Point from = c[0], before = {0, 0}; for (int i = 0; i < n; ++i) { - double t0 = (double)i / n, t1 = (double)(i + 1) / n; - Point q[4]; - double ts[2] = {t0, t1}; - /* The piece's points by de Casteljau at t0 and t1, and its control points. */ - Point e[2]; - for (int k = 0; k < 2; ++k) { - double t = ts[k], u = 1 - t; - e[k] = (Point){u * u * u * p0.x + 3 * u * u * t * c1.x + 3 * u * t * t * c2.x + t * t * t * to.x, - u * u * u * p0.y + 3 * u * u * t * c1.y + 3 * u * t * t * c2.y + t * t * t * to.y}; - } - /* Derivatives give the piece's cubic control points. */ - double h = t1 - t0; - for (int k = 0; k < 2; ++k) { - double t = ts[k], u = 1 - t; - Point d = {3 * (u * u * (c1.x - p0.x) + 2 * u * t * (c2.x - c1.x) + t * t * (to.x - c2.x)), - 3 * (u * u * (c1.y - p0.y) + 2 * u * t * (c2.y - c1.y) + t * t * (to.y - c2.y))}; - q[k ? 2 : 1] = k ? (Point){e[1].x - d.x * h / 3, e[1].y - d.y * h / 3} : (Point){e[0].x + d.x * h / 3, e[0].y + d.y * h / 3}; - } - q[0] = e[0]; - q[3] = e[1]; - Point control = {(3 * (q[1].x + q[2].x) - (q[0].x + q[3].x)) / 4, (3 * (q[1].y + q[2].y) - (q[0].y + q[3].y)) / 4}; - path->at = q[0]; - quad_to(path, control, q[3]); + Point p[4]; + piece(c, (double)i / n, (double)(i + 1) / n, p); + Point near = lerp(p[0], p[1], 1.5), far = lerp(p[3], p[2], 1.5); + controls[i] = lerp(near, far, (double)i / (n - 1)); } - path->at = to; + for (int i = 0; i < n; ++i) { + Point p[4]; + piece(c, (double)i / n, (double)(i + 1) / n, p); + Point to = i + 1 < n ? lerp(controls[i], controls[i + 1], 0.5) : c[3]; + Point after = {to.x - p[3].x, to.y - p[3].y}; + Point q1 = lerp(from, controls[i], 2.0 / 3), q2 = lerp(to, controls[i], 2.0 / 3); + if (length(after.x, after.y) > tolerance || + !fits(before, (Point){q1.x - p[1].x, q1.y - p[1].y}, (Point){q2.x - p[2].x, q2.y - p[2].y}, after, tolerance)) + return false; + from = to; + before = after; + } + return true; +} + +static void cubic_to(Path *path, Point c1, Point c2, Point to) { + Point c[4] = {path->at, c1, c2, to}, controls[64]; + if (same(c[0], c1) && same(c1, c2) && same(c2, to)) return; + for (int n = 1; n <= 64; ++n) + if (spline(c, n, 1, controls)) { + for (int i = 0; i < n; ++i) + add(path, (Segment){QUAD, i + 1 < n, controls[i], i + 1 < n ? lerp(controls[i], controls[i + 1], 0.5) : to}); + return; + } + fail("a cubic that 64 quadratics do not fit"); } static void close_path(Path *path) { - if (path->open) line_to(path, path->start); + if (path->open) { + line_to(path, path->start); + /* A contour of a move alone draws nothing: drop it. */ + if (path->count && path->items[path->count - 1].kind == MOVE) --path->count; + } path->open = false; } static void move_to(Path *path, Point to) { close_path(path); - path->at = path->start = to; + add(path, (Segment){MOVE, false, to, to}); + path->start = to; path->open = true; } @@ -300,13 +348,54 @@ static void svg_icon(Path *path, const char *file, uint16_t units, int16_t *adva /* ---- Writing. */ +typedef struct { long x, y; bool off, move; } Emitted; +typedef struct { Emitted *items; size_t count, capacity; } Points; + static void put16(unsigned char *p, int v) { p[0] = (unsigned char)v; p[1] = (unsigned char)((unsigned)v >> 8); } static void put32(unsigned char *p, uint32_t v) { for (int i = 0; i < 4; ++i) p[i] = (unsigned char)(v >> (8 * i)); } -static int16_t unit(double v) { - long r = lround(v); - if (r < INT16_MIN || r > INT16_MAX) fail("a coordinate does not fit 16 bits"); - return (int16_t)r; +static void emit(Points *points, Point at, bool off, bool move) { + if (points->count == points->capacity) { + points->capacity = points->capacity ? 2 * points->capacity : 256; + if (!(points->items = realloc(points->items, points->capacity * sizeof(*points->items)))) fail("out of memory"); + } + points->items[points->count++] = (Emitted){lround(at.x), lround(at.y), off, move}; +} + +/* Whether s ends where its control and the next curve's would imply. */ +static bool implied(const Segment *s, const Segment *next) { + if (s->kind != QUAD || !next || next->kind != QUAD) return false; + return s->smooth || (2 * lround(s->end.x) == lround(s->control.x) + lround(next->control.x) && + 2 * lround(s->end.y) == lround(s->control.y) + lround(next->control.y)); +} + +/* One symbol's segments as points: each contour an on point that starts it, + * then per segment its control (if a curve) and its end, unless the next + * curve's control implies it; the last end, back at the start, is written. + * A contour that starts at an implied point (as FreeType starts TrueType's + * when its first point is off) starts instead at its first written one. */ +static void emit_symbol(Points *points, const Segment *segments, size_t count) { + for (size_t i = 0; i < count;) { + size_t end = i + 1; + while (end < count && segments[end].kind != MOVE) ++end; + const Segment *body = segments + i + 1; + size_t n = end - i - 1, from = 0; + if (n > 1 && implied(&body[n - 1], &body[0])) + for (size_t k = 0; k + 1 < n; ++k) + if (!implied(&body[k], &body[k + 1])) { from = k + 1; break; } + emit(points, from ? body[from - 1].end : segments[i].end, false, true); + for (size_t m = 0; m < n; ++m) { + const Segment *s = &body[(from + m) % n], *next = m + 1 < n ? &body[(from + m + 1) % n] : NULL; + const Emitted *last = &points->items[points->count - 1]; + if (s->kind == LINE) { + if (last->off || last->x != lround(s->end.x) || last->y != lround(s->end.y)) emit(points, s->end, false, false); + continue; + } + emit(points, s->control, true, false); + if (!implied(s, next)) emit(points, s->end, false, false); + } + i = end; + } } static int by_code(const void *a, const void *b) { @@ -317,53 +406,74 @@ static int by_code(const void *a, const void *b) { static void write_symbols(const char *out, uint16_t units, Built *built, size_t count, const Path *path) { qsort(built, count, sizeof(*built), by_code); for (size_t i = 1; i < count; ++i) if (built[i].code == built[i - 1].code) fail("a code is given twice"); - size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + path->count * VEGA_CURVE_BYTES; + Points points = {0}; + size_t *first = calloc(count + 1, sizeof(*first)); + for (size_t i = 0; i < count; ++i) { + first[i] = points.count; + emit_symbol(&points, path->items + built[i].first, built[i].count); + } + first[count] = points.count; + /* Halve units while every coordinate is even: a TrueType font's own. */ + for (;;) { + bool even = units % 2 == 0 && units > 16; + for (size_t i = 0; even && i < points.count; ++i) even = points.items[i].x % 2 == 0 && points.items[i].y % 2 == 0; + for (size_t i = 0; even && i < count; ++i) even = built[i].advance % 2 == 0; + if (!even) break; + for (size_t i = 0; i < points.count; ++i) { points.items[i].x /= 2; points.items[i].y /= 2; } + for (size_t i = 0; i < count; ++i) built[i].advance = (int16_t)(built[i].advance / 2); + units /= 2; + } + size_t size = VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES + points.count * VEGA_POINT_BYTES; unsigned char *bytes = calloc(1, size); if (!bytes) fail("out of memory"); - memcpy(bytes, "VEGASYM1", 8); + memcpy(bytes, "VEGASYM2", 8); put16(bytes + 8, units); put32(bytes + 12, (uint32_t)count); - put32(bytes + 16, (uint32_t)path->count); + put32(bytes + 16, (uint32_t)points.count); put32(bytes + 20, (uint32_t)size); - unsigned char *curves = bytes + VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES; - uint32_t next = 0; + unsigned char *at = bytes + VEGA_SYMBOLS_HEADER + count * VEGA_SYMBOL_BYTES; + for (size_t i = 0; i < points.count; ++i) { + const Emitted *e = &points.items[i]; + if (e->x < -16384 || e->x > 16383 || e->y < -16384 || e->y > 16383) fail("a coordinate does not fit 15 bits"); + put16(at + 4 * i, (int)(2 * e->x + e->off)); + put16(at + 4 * i + 2, (int)(2 * e->y + e->move)); + } for (size_t i = 0; i < count; ++i) { - int16_t left = 0, bottom = 0, right = 0, top = 0; - for (size_t k = 0; k < built[i].count; ++k) { - const Quad *q = &path->items[built[i].first + k]; - unsigned char *c = curves + (size_t)(next + k) * VEGA_CURVE_BYTES; - for (int j = 0; j < 3; ++j) { - int16_t x = unit(q->p[j].x), y = unit(q->p[j].y); - put16(c + 4 * j, x); - put16(c + 4 * j + 2, y); - if (!k && !j) { left = right = x; bottom = top = y; } - if (x < left) left = x; - if (x > right) right = x; - if (y < bottom) bottom = y; - if (y > top) top = y; - } + long left = 0, bottom = 0, right = 0, top = 0; + for (size_t k = first[i]; k < first[i + 1]; ++k) { + const Emitted *e = &points.items[k]; + if (k == first[i]) { left = right = e->x; bottom = top = e->y; } + left = e->x < left ? e->x : left; + right = e->x > right ? e->x : right; + bottom = e->y < bottom ? e->y : bottom; + top = e->y > top ? e->y : top; } - unsigned char *s = bytes + VEGA_SYMBOLS_HEADER + i * VEGA_SYMBOL_BYTES; - put32(s, built[i].code); - put32(s + 4, next); - put32(s + 8, (uint32_t)built[i].count); - put16(s + 12, left); - put16(s + 14, bottom); - put16(s + 16, right); - put16(s + 18, top); - put16(s + 20, built[i].advance); - next += (uint32_t)built[i].count; + unsigned char *p = bytes + VEGA_SYMBOLS_HEADER + i * VEGA_SYMBOL_BYTES; + put32(p, built[i].code); + put32(p + 4, (uint32_t)first[i]); + put32(p + 8, (uint32_t)(first[i + 1] - first[i])); + put16(p + 12, (int)left); + put16(p + 14, (int)bottom); + put16(p + 16, (int)right); + put16(p + 18, (int)top); + put16(p + 20, built[i].advance); } FILE *f = fopen(out, "wb"); if (!f || fwrite(bytes, 1, size, f) != size || fclose(f)) fail("cannot write the symbol file"); - free(bytes); char error[128]; VegaSymbols check; - size_t read_size; - char *again = read_file(out, &read_size); - if (!again || !vega_symbols_open(&check, (unsigned char *)again, read_size, error, sizeof(error))) fail(error); - free(again); - printf("{\"symbols\":%zu,\"curves\":%zu,\"bytes\":%zu}\n", count, path->count, size); + if (!vega_symbols_open(&check, bytes, size, error, sizeof(error))) fail(error); + size_t curves = 0; + VegaCurve curve; + for (uint32_t i = 0; i < check.symbols; ++i) { + VegaSymbol symbol = vega_symbol_at(&check, i); + for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) curves += vega_symbol_curve(&check, &symbol, k, &curve); + } + printf("{\"symbols\":%zu,\"points\":%zu,\"curves\":%zu,\"units\":%u,\"bytes\":%zu}\n", count, points.count, curves, + units, size); + free(bytes); + free(first); + free(points.items); } /* 0x20-0x7e,0xac00 as a list of codes. */ @@ -432,7 +542,7 @@ static int build(int argc, char **argv) { if (FT_Outline_Decompose(&face->glyph->outline, &walk, &path)) fail("cannot walk an outline"); } close_path(&path); - long advance = lround(face->glyph->metrics.horiAdvance * path.font_scale); + long advance = lround((double)face->glyph->metrics.horiAdvance * units / face->units_per_EM); built[made++] = (Built){list[i], first, path.count - first, (int16_t)(advance > INT16_MAX ? INT16_MAX : advance)}; } for (size_t i = 0; i < icon_count; ++i) { @@ -496,12 +606,16 @@ static void measure_open(FT_Library library, const char *font, const VegaSymbols if (FT_New_Memory_Face(library, (const FT_Byte *)font_bytes, (FT_Long)font_size, 0, &face)) fail("cannot open the font"); FT_Outline_Funcs walk = {ignore_point, ignore_point, ignore_conic, ignore_cubic, 0, 0}; long touched = 0, walked = 0; + uint32_t most = 0; + for (uint32_t i = 0; i < s->symbols; ++i) most = vega_symbol_at(s, i).count > most ? vega_symbol_at(s, i).count : most; + VegaCurve *curves = malloc((most + 1) * sizeof(*curves)); started = seconds(); for (int r = 0; r < rounds; ++r) for (uint32_t i = 0; i < s->symbols; ++i) { VegaSymbol symbol; if (!vega_symbol(s, vega_symbol_at(s, i).code, &symbol)) fail("lookup"); - for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) touched += vega_curve(s, k).x2; + uint32_t count = vega_symbol_curves(s, &symbol, curves); + touched += count ? (long)curves[count - 1].x2 : 0; } double outline_ns = (seconds() - started) / rounds / s->symbols * 1e9; started = seconds(); @@ -516,6 +630,7 @@ static void measure_open(FT_Library library, const char *font, const VegaSymbols sink = touched + walked; FT_Done_Face(face); free(font_bytes); + free(curves); } /* Every symbol with a glyph in the font, at each size: our coverage against @@ -572,7 +687,7 @@ static int compare(int argc, char **argv) { return 0; } -/* Each symbol's code, curves, bounds, advance and filled area (in square +/* Each symbol's code, points, curves, bounds, advance and filled area (in square * units: the integral of x dy around its outline, as a check against other * readers of the same fonts and icons). */ static int info(int argc, char **argv) { @@ -583,14 +698,18 @@ static int info(int argc, char **argv) { for (uint32_t i = 0; i < s.symbols; ++i) { VegaSymbol symbol = vega_symbol_at(&s, i); double area = 0; + uint32_t curves = 0; + VegaCurve c; for (uint32_t k = symbol.first; k < symbol.first + symbol.count; ++k) { - VegaCurve c = vega_curve(&s, k); + if (!vega_symbol_curve(&s, &symbol, k, &c)) continue; + ++curves; /* x(t) = x0 - 2 bx t + ax t^2, y'(t) = -2 by + 2 ay t, over [0, 1]. */ double ax = c.x0 - 2 * c.x1 + c.x2, bx = c.x0 - c.x1, ay = c.y0 - 2 * c.y1 + c.y2, by = c.y0 - c.y1; area += c.x0 * -2 * by + (c.x0 * 2 * ay + 4 * bx * by) / 2 + (-4 * bx * ay - 2 * ax * by) / 3 + ax * ay / 2; } - printf("%s{\"code\":%u,\"curves\":%u,\"bounds\":[%d,%d,%d,%d],\"advance\":%d,\"area\":%.1f}", i ? "," : "", - symbol.code, symbol.count, symbol.left, symbol.bottom, symbol.right, symbol.top, symbol.advance, area); + printf("%s{\"code\":%u,\"points\":%u,\"curves\":%u,\"bounds\":[%d,%d,%d,%d],\"advance\":%d,\"area\":%.1f}", + i ? "," : "", symbol.code, symbol.count, curves, symbol.left, symbol.bottom, symbol.right, symbol.top, + symbol.advance, area); } printf("]}\n"); free(bytes); diff --git a/src/symbols.c b/src/symbols.c index daa35e5..cedd68f 100644 --- a/src/symbols.c +++ b/src/symbols.c @@ -1,9 +1,10 @@ #include "symbols.h" #include <math.h> #include <stdio.h> +#include <stdlib.h> #include <string.h> -static const unsigned char magic[8] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M', '1'}; +static const unsigned char magic[8] = {'V', 'E', 'G', 'A', 'S', 'Y', 'M', '2'}; static uint16_t u16(const unsigned char *p) { return (uint16_t)(p[0] | p[1] << 8); } static int16_t i16(const unsigned char *p) { return (int16_t)u16(p); } @@ -14,10 +15,14 @@ VegaSymbol vega_symbol_at(const VegaSymbols *s, uint32_t index) { return (VegaSymbol){u32(p), u32(p + 4), u32(p + 8), i16(p + 12), i16(p + 14), i16(p + 16), i16(p + 18), i16(p + 20)}; } -VegaCurve vega_curve(const VegaSymbols *s, uint32_t index) { +/* A point is two i16s, each its coordinate times two plus a flag: off the + * curve in x, starting a contour in y. */ +VegaPoint vega_point(const VegaSymbols *s, uint32_t index) { const unsigned char *p = s->bytes + VEGA_SYMBOLS_HEADER + (size_t)s->symbols * VEGA_SYMBOL_BYTES + - (size_t)index * VEGA_CURVE_BYTES; - return (VegaCurve){i16(p), i16(p + 2), i16(p + 4), i16(p + 6), i16(p + 8), i16(p + 10)}; + (size_t)index * VEGA_POINT_BYTES; + int x = i16(p), y = i16(p + 2); + /* x >> 1 without relying on how a negative number shifts */ + return (VegaPoint){(int16_t)((x - (x & 1)) / 2), (int16_t)((y - (y & 1)) / 2), x & 1, y & 1}; } #define REFUSE(...) do { snprintf(error, error_size, __VA_ARGS__); return false; } while (0) @@ -25,16 +30,22 @@ VegaCurve vega_curve(const VegaSymbols *s, uint32_t index) { bool vega_symbols_open(VegaSymbols *s, const unsigned char *bytes, size_t size, char *error, size_t error_size) { if (size < VEGA_SYMBOLS_HEADER || memcmp(bytes, magic, sizeof(magic))) REFUSE("not a symbol file"); *s = (VegaSymbols){bytes, size, u16(bytes + 8), u32(bytes + 12), u32(bytes + 16)}; - uint64_t expected = VEGA_SYMBOLS_HEADER + (uint64_t)s->symbols * VEGA_SYMBOL_BYTES + (uint64_t)s->curves * VEGA_CURVE_BYTES; + uint64_t expected = VEGA_SYMBOLS_HEADER + (uint64_t)s->symbols * VEGA_SYMBOL_BYTES + (uint64_t)s->points * VEGA_POINT_BYTES; if (u16(bytes + 10) || u32(bytes + 24) || !s->units) REFUSE("header"); - if (u32(bytes + 20) != size || expected != size) REFUSE("size: %zu bytes for %u symbols and %u curves", size, s->symbols, s->curves); + if (u32(bytes + 20) != size || expected != size) REFUSE("size: %zu bytes for %u symbols and %u points", size, s->symbols, s->points); for (uint32_t i = 0; i < s->symbols; ++i) { VegaSymbol symbol = vega_symbol_at(s, i); const unsigned char *p = bytes + VEGA_SYMBOLS_HEADER + (size_t)i * VEGA_SYMBOL_BYTES; if (u16(p + 22)) REFUSE("symbol %u: flags", i); if (i && symbol.code <= vega_symbol_at(s, i - 1).code) REFUSE("symbol %u: codes out of order", i); - if (symbol.first > s->curves || symbol.count > s->curves - symbol.first) REFUSE("symbol %u: curves", i); + if (symbol.first > s->points || symbol.count > s->points - symbol.first) REFUSE("symbol %u: points", i); if (symbol.left > symbol.right || symbol.bottom > symbol.top) REFUSE("symbol %u: bounds", i); + /* An off point then always has both neighbours within the symbol. */ + if (symbol.count) { + VegaPoint first = vega_point(s, symbol.first), last = vega_point(s, symbol.first + symbol.count - 1); + if (first.off || !first.move) REFUSE("symbol %u: its first point does not start a contour on the curve", i); + if (last.off) REFUSE("symbol %u: its last point is off the curve", i); + } } return true; } @@ -50,6 +61,21 @@ bool vega_symbol(const VegaSymbols *s, uint32_t code, VegaSymbol *out) { return false; } +bool vega_symbol_curve(const VegaSymbols *s, const VegaSymbol *symbol, uint32_t index, VegaCurve *out) { + VegaPoint p = vega_point(s, index); + if (p.off) { + VegaPoint a = vega_point(s, index - 1), b = vega_point(s, index + 1); + *out = (VegaCurve){a.off ? (a.x + p.x) * 0.5f : a.x, a.off ? (a.y + p.y) * 0.5f : a.y, p.x, p.y, + b.off ? (p.x + b.x) * 0.5f : b.x, b.off ? (p.y + b.y) * 0.5f : b.y}; + return true; + } + if (index + 1 >= symbol->first + symbol->count) return false; + VegaPoint b = vega_point(s, index + 1); + if (b.off || b.move) return false; + *out = (VegaCurve){p.x, p.y, (p.x + b.x) * 0.5f, (p.y + b.y) * 0.5f, b.x, b.y}; + return true; +} + /* Where a t^2 + b t + c = 0 inside (0, 1), appended to ts. */ static int roots(double a, double b, double c, double *ts) { int n = 0; @@ -106,13 +132,41 @@ static double curve_area(double x0, double y0, double x1, double y1, double x2, return area; } -double vega_symbol_coverage(const VegaSymbols *s, const VegaSymbol *symbol, double scale, double x, double y) { +/* Without branches on the flags, which no predictor guesses: implied points + * and whether a point begins a curve come out of arithmetic on them. */ +uint32_t vega_symbol_curves(const VegaSymbols *s, const VegaSymbol *symbol, VegaCurve *out) { + if (!symbol->count) return 0; + const unsigned char *p = s->bytes + VEGA_SYMBOLS_HEADER + (size_t)s->symbols * VEGA_SYMBOL_BYTES + + (size_t)symbol->first * VEGA_POINT_BYTES; + uint32_t count = 0; + int x = i16(p), y = i16(p + 2), off = x & 1; + float bx = 0, by = 0, bo = 0, hx = (float)(x - off) * 0.5f, hy = (float)(y - (y & 1)) * 0.5f, ho = (float)off; + for (uint32_t k = 1; k < symbol->count; ++k) { + p += VEGA_POINT_BYTES; + x = i16(p); + y = i16(p + 2); + float nx = (float)(x - (x & 1)) * 0.5f, ny = (float)(y - (y & 1)) * 0.5f, no = (float)(x & 1); + /* before, or halfway to here if before is off; here if here is on */ + float sx = bx + (hx - bx) * 0.5f * bo, sy = by + (hy - by) * 0.5f * bo; + out[count] = (VegaCurve){hx + (sx - hx) * ho, hy + (sy - hy) * ho, hx + (nx - hx) * 0.5f * (1 - ho), + hy + (ny - hy) * 0.5f * (1 - ho), nx + (hx - nx) * 0.5f * no, ny + (hy - ny) * 0.5f * no}; + /* an off point begins a curve, and so does an on point before an on + * point of the same contour (a line) */ + count += (uint32_t)(off | (((x & 1) ^ 1) & ((y & 1) ^ 1))); + off = x & 1; + bx = hx, by = hy, bo = ho; + hx = nx, hy = ny, ho = no; + } + return count; +} + +double vega_coverage(const VegaCurve *curves, uint32_t count, double scale, double x, double y) { /* The pixel's lower left corner, in units. */ double left = x - 0.5 / scale, bottom = y - 0.5 / scale, area = 0; - for (uint32_t k = symbol->first; k < symbol->first + symbol->count; ++k) { - VegaCurve c = vega_curve(s, k); - area += curve_area((c.x0 - left) * scale, (c.y0 - bottom) * scale, (c.x1 - left) * scale, (c.y1 - bottom) * scale, - (c.x2 - left) * scale, (c.y2 - bottom) * scale); + for (uint32_t k = 0; k < count; ++k) { + const VegaCurve *c = &curves[k]; + area += curve_area((c->x0 - left) * scale, (c->y0 - bottom) * scale, (c->x1 - left) * scale, (c->y1 - bottom) * scale, + (c->x2 - left) * scale, (c->y2 - bottom) * scale); } area = fabs(area); return area > 1 ? 1 : area; @@ -120,9 +174,12 @@ double vega_symbol_coverage(const VegaSymbols *s, const VegaSymbol *symbol, doub void vega_symbol_raster(const VegaSymbols *s, const VegaSymbol *symbol, double scale, double left, double top, int width, int height, unsigned char *out) { + VegaCurve *curves = malloc((symbol->count ? symbol->count : 1) * sizeof(*curves)); + uint32_t count = curves ? vega_symbol_curves(s, symbol, curves) : 0; for (int j = 0; j < height; ++j) for (int i = 0; i < width; ++i) { - double coverage = vega_symbol_coverage(s, symbol, scale, left + (i + 0.5) / scale, top - (j + 0.5) / scale); + double coverage = vega_coverage(curves, count, scale, left + (i + 0.5) / scale, top - (j + 0.5) / scale); out[(size_t)j * (size_t)width + (size_t)i] = (unsigned char)lround(coverage * 255); } + free(curves); } diff --git a/src/symbols.h b/src/symbols.h index da33e34..998ff3f 100644 --- a/src/symbols.h +++ b/src/symbols.h @@ -4,12 +4,19 @@ #include <stddef.h> #include <stdint.h> -/* Symbols: glyphs and icons as quadratic curves in one file, verified once - * and then read where it lies (docs/design/002-symbol-format.md). */ -enum { VEGA_SYMBOLS_HEADER = 28, VEGA_SYMBOL_BYTES = 24, VEGA_CURVE_BYTES = 12 }; -typedef struct { int16_t x0, y0, x1, y1, x2, y2; } VegaCurve; +/* Symbols: glyphs and icons as outlines of quadratic curves in one file, + * verified once and then read where it lies (docs/design/002-symbol-format.md). + * An outline is a chain of points, on or off the curve, as in TrueType: two + * off points in a row imply the on point halfway between them. */ +enum { VEGA_SYMBOLS_HEADER = 28, VEGA_SYMBOL_BYTES = 24, VEGA_POINT_BYTES = 4 }; typedef struct { - uint32_t code, first, count; /* its curves: [first, first + count) */ + int16_t x, y; + bool off; /* a control point */ + bool move; /* starts a contour */ +} VegaPoint; +typedef struct { float x0, y0, x1, y1, x2, y2; } VegaCurve; /* a line has its middle as control */ +typedef struct { + uint32_t code, first, count; /* its points: [first, first + count) */ int16_t left, bottom, right, top; /* bounds, in units, y up */ int16_t advance; } VegaSymbol; @@ -17,20 +24,29 @@ typedef struct { const unsigned char *bytes; size_t size; uint16_t units; /* per em */ - uint32_t symbols, curves; + uint32_t symbols, points; } VegaSymbols; /* Verify bytes as a symbol file (kept, not copied); false with why. What - * reading needs is checked, per symbol: after this no read leaves the file. - * The curves themselves are not: one outside its symbol's bounds draws wrong. */ + * reading needs is checked, per symbol: after this no read leaves the file + * or its symbol. The points themselves are not: one outside its symbol's + * bounds draws wrong. */ bool vega_symbols_open(VegaSymbols *, const unsigned char *bytes, size_t size, char *error, size_t error_size); /* The symbol of code (a binary search), or false. */ bool vega_symbol(const VegaSymbols *, uint32_t code, VegaSymbol *out); VegaSymbol vega_symbol_at(const VegaSymbols *, uint32_t index); -VegaCurve vega_curve(const VegaSymbols *, uint32_t index); +VegaPoint vega_point(const VegaSymbols *, uint32_t index); +/* The curve that point index of symbol begins, if any: an off point is the + * control of one, and an on point followed by another on point in the same + * contour starts a line. Every curve of a symbol is had once this way, from + * the point and its two neighbours alone (as a GPU would fetch it). */ +bool vega_symbol_curve(const VegaSymbols *, const VegaSymbol *, uint32_t index, VegaCurve *out); +/* All of a symbol's curves, in one pass over its points; out has room for + * symbol->count (a symbol has no more curves than points). */ +uint32_t vega_symbol_curves(const VegaSymbols *, const VegaSymbol *, VegaCurve *out); /* The coverage (0 to 1) of the pixel whose center is (x, y) in units, at - * scale pixels per unit: as a GPU would compute it per pixel. */ -double vega_symbol_coverage(const VegaSymbols *, const VegaSymbol *, double scale, double x, double y); + * scale pixels per unit: the exact area the curves' outline covers. */ +double vega_coverage(const VegaCurve *, uint32_t count, double scale, double x, double y); /* width x height 8-bit coverage, rows top first; pixel (i, j) has its center * at (left + (i + 0.5) / scale, top - (j + 0.5) / scale) in units. */ void vega_symbol_raster(const VegaSymbols *, const VegaSymbol *, double scale, double left, double top, int width, diff --git a/tests/check.py b/tests/check.py index c3bcfe2..288bd37 100644 --- a/tests/check.py +++ b/tests/check.py @@ -949,7 +949,7 @@ def symbols(tool, work): assert refused.returncode != 0 and refused.stdout == '', (name, refused.stdout) return refused.stderr.strip() - why = [damaged('short', good[:-1]), damaged('magic', b'VEGASYM2' + good[8:])] + why = [damaged('short', good[:-1]), damaged('magic', b'VEGASYM9' + good[8:])] swapped = bytearray(good) swapped[records:records + 24], swapped[records + 24:records + 48] = good[records + 24:records + 48], good[records:records + 24] why.append(damaged('order', swapped)) @@ -962,6 +962,16 @@ def symbols(tool, work): counted = bytearray(good) counted[12:16] = (count + 1).to_bytes(4, 'little') why.append(damaged('count', counted)) + # A symbol's first point starts a contour on the curve, and its last is + # on it, so an off point's neighbours never leave the symbol. + points = records + 24 * count + first, length = (int.from_bytes(good[records + k:records + k + 4], 'little') for k in (4, 8)) + unmoved = bytearray(good) + unmoved[points + 4 * first + 2] &= 0xFE + why.append(damaged('unmoved', unmoved)) + open_end = bytearray(good) + open_end[points + 4 * (first + length - 1)] |= 1 + why.append(damaged('open', open_end)) assert len(set(why)) == len(why), why report = {'icons': len(info['symbols'])} @@ -980,13 +990,14 @@ def symbols(tool, work): except ImportError: return report face = TTFont(font) - outlines, cmap = face.getGlyphSet(), face.getBestCmap() + outlines, cmap, metrics = face.getGlyphSet(), face.getBestCmap(), face['hmtx'] shown = json.loads(run(tool, 'info', glyphs).stdout) - k = shown['units'] / face['head'].unitsPerEm + assert shown['units'] == face['head'].unitsPerEm, shown['units'] # a TrueType font's points stay whole for symbol in shown['symbols']: pen = AreaPen() outlines[cmap[symbol['code']]].draw(pen) - assert abs(abs(pen.value) * k * k - abs(symbol['area'])) < 1, (chr(symbol['code']), pen.value, symbol) + assert abs(abs(pen.value) - abs(symbol['area'])) < 1, (chr(symbol['code']), pen.value, symbol) + assert symbol['advance'] == metrics[cmap[symbol['code']]][0], (chr(symbol['code']), symbol) report['exact_glyphs'] = len(shown['symbols']) return report |
