diff options
| -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 |