ref: d17a049c5b083751f66d7089d8950aaefd047bc6
dir: /sys/src/libttf/scan.c/
#include <u.h> #include <libc.h> #include <bio.h> #include <ttf.h> #include "impl.h" typedef struct Scan Scan; typedef struct TTLine TTLine; enum { LINEBLOCK = 32, PTBLOCK = 64, }; struct TTLine { int x0, y0; int x1, y1; int link; u8int dir; }; struct Scan { enum { DROPOUTS = 1, STUBDET = 2, SMART = 4, } flags; TTGlyph *g; TTLine *lines; int nlines; int *hpts, *vpts; int nhpts, nvpts; int *hscanl, *vscanl; u8int *bit; int width, height; int stride; }; static void dobezier(Scan *s, TTPoint p, TTPoint q, TTPoint r) { vlong m, n; TTLine *l; m = (vlong)(q.x - p.x) * (r.y - p.y) - (vlong)(q.y - p.y) * (r.x - p.x); n = (vlong)(r.x - p.x) * (r.x - p.x) + (vlong)(r.y - p.y) * (r.y - p.y); if(m * m > 4 * n){ dobezier(s, p, (TTPoint){(p.x+q.x+1)/2, (p.y+q.y+1)/2, 0}, (TTPoint){(p.x+2*q.x+r.x+2)/4, (p.y+2*q.y+r.y+2)/4, 0}); dobezier(s, (TTPoint){(p.x+2*q.x+r.x+2)/4, (p.y+2*q.y+r.y+2)/4, 0}, (TTPoint){(r.x+q.x+1)/2, (r.y+q.y+1)/2, 0}, r); return; } if((s->nlines & LINEBLOCK - 1) == 0) s->lines = realloc(s->lines, sizeof(TTLine) * (s->nlines + LINEBLOCK)); l = &s->lines[s->nlines++]; if(p.y < r.y){ l->x0 = p.x; l->y0 = p.y; l->x1 = r.x; l->y1 = r.y; l->dir = 0; }else{ l->x0 = r.x; l->y0 = r.y; l->x1 = p.x; l->y1 = p.y; l->dir = 1; } l->link = -1; } static int hlinecmp(void *va, void *vb) { TTLine *a, *b; a = va; b = vb; if(a->y0 < b->y0) return -1; if(a->y0 > b->y0) return 1; return 0; } static int vlinecmp(void *va, void *vb) { TTLine *a, *b; a = va; b = vb; if(a->x0 < b->x0) return -1; if(a->x0 > b->x0) return 1; return 0; } static int intcmp(void *va, void *vb) { int a, b; a = *(int*)va; b = *(int*)vb; return (a>b) - (a<b); } static void hprep(Scan *s) { int i, j, x, y; TTLine *l; int watch, act, *p; qsort(s->lines, s->nlines, sizeof(TTLine), hlinecmp); s->hscanl = calloc(sizeof(int), (s->height + 1)); act = -1; watch = 0; p = &act; for(i = 0; i < s->height; i++){ y = 64 * i + 32; for(; watch < s->nlines && s->lines[watch].y0 <= y; watch++){ if(s->lines[watch].y1 <= y || s->lines[watch].y0 == s->lines[watch].y1) continue; s->lines[watch].link = -1; *p = watch; p = &s->lines[watch].link; } s->hscanl[i] = s->nhpts; p = &act; while(j = *p, j >= 0){ l = &s->lines[j]; if(l->y1 <= y){ j = l->link; l->link = -1; *p = j; continue; } x = l->x0 + ttfvrounddiv((vlong)(y - l->y0)*(l->x1 - l->x0), l->y1 - l->y0); if((s->nhpts & PTBLOCK - 1) == 0) s->hpts = realloc(s->hpts, (s->nhpts + PTBLOCK) * sizeof(int)); s->hpts[s->nhpts++] = x << 1 | l->dir; p = &l->link; } qsort(s->hpts + s->hscanl[i], s->nhpts - s->hscanl[i], sizeof(int), intcmp); } s->hscanl[i] = s->nhpts; } static int iswhite(Scan *s, int x, int y) { return (s->bit[(s->height - 1 - y) * s->stride + (x>>3)] >> 7-(x&7) & 1)==0; } static void pixel(Scan *s, int x, int y) { assert(x >= 0 && x < s->width && y >= 0 && y < s->height); s->bit[(s->height - 1 - y) * s->stride + (x>>3)] |= (1<<7-(x&7)); } static int intersectsh(Scan *s, int x, int y) { int a, b, c, vc, v; a = s->hscanl[y]; b = s->hscanl[y+1]-1; v = x * 64 + 32; if(a > b || s->hpts[a]>>1 > v + 64 || s->hpts[b]>>1 < v) return 0; while(a <= b){ c = (a + b) / 2; vc = s->hpts[c]>>1; if(vc < v) a = c + 1; else if(vc > v + 64) b = c - 1; else return 1; } return 0; } static int intersectsv(Scan *s, int x, int y) { int a, b, c, vc, v; a = s->vscanl[x]; b = s->vscanl[x+1]-1; v = y * 64 + 32; if(a > b || s->vpts[a]>>1 > v + 64 || s->vpts[b]>>1 < v) return 0; while(a <= b){ c = (a + b) / 2; vc = s->vpts[c]>>1; if(vc < v) a = c + 1; else if(vc > v + 64) b = c - 1; else return 1; } return 0; } static void hscan(Scan *s) { int i, j, k, e; int wind, match, seen, x; for(i = 0; i < s->height; i++){ e = s->hscanl[i+1]; k = s->hscanl[i]; if(k == e) continue; wind = 0; for(j = 0; j < s->width; j++){ x = 64 * j + 32; match = 0; seen = 0; while(k < e && (s->hpts[k] >> 1) <= x){ wind += (s->hpts[k] & 1) * 2 - 1; seen |= 1<<(s->hpts[k] & 1); if((s->hpts[k] >> 1) == x) match++; k++; } if(match || wind) pixel(s, j, i); else if((s->flags & DROPOUTS) != 0 && seen == 3 && j > 0 && iswhite(s, j-1, i)){ if((s->flags & STUBDET) == 0){ pixel(s, j-1, i); continue; } if(i <= 0 || i > s->height - 1 || j <= 0 || j > s->width - 1) continue; if(!intersectsv(s, j-1, i-1) && !intersectsh(s, j-1, i-1) && !intersectsv(s, j, i-1) || !intersectsv(s, j-1, i) && !intersectsh(s, j-1, i+1) && !intersectsv(s, j, i)) continue; pixel(s, j-1, i); } } } } static void vprep(Scan *s) { int i, j, x, y; TTLine *l; int watch, act, *p; for(i = 0; i < s->nlines; i++){ l = &s->lines[i]; if(l->x0 > l->x1){ x = l->x0, l->x0 = l->x1, l->x1 = x; x = l->y0, l->y0 = l->y1, l->y1 = x; l->dir ^= 1; } } qsort(s->lines, s->nlines, sizeof(TTLine), vlinecmp); s->vscanl = calloc(sizeof(int), (s->width + 1)); act = -1; watch = 0; p = &act; for(i = 0; i < s->width; i++){ x = 64 * i + 32; for(; watch < s->nlines && s->lines[watch].x0 <= x; watch++){ if(s->lines[watch].x1 <= x || s->lines[watch].x0 == s->lines[watch].x1) continue; s->lines[watch].link = -1; *p = watch; p = &s->lines[watch].link; } s->vscanl[i] = s->nvpts; p = &act; while(j = *p, j >= 0){ l = &s->lines[j]; if(l->x1 <= x){ j = l->link; l->link = -1; *p = j; continue; } y = l->y0 + ttfvrounddiv((vlong)(x - l->x0) * (l->y1 - l->y0), l->x1 - l->x0); if((s->nvpts & PTBLOCK - 1) == 0) s->vpts = realloc(s->vpts, (s->nvpts + PTBLOCK) * sizeof(int)); s->vpts[s->nvpts++] = y << 1 | l->dir; p = &l->link; } qsort(s->vpts + s->vscanl[i], s->nvpts - s->vscanl[i], sizeof(int), intcmp); } s->vscanl[i] = s->nvpts; } static void vscan(Scan *s) { int i, j, k, e; int seen, y; for(i = 0; i < s->width; i++){ e = s->vscanl[i+1]; k = s->vscanl[i]; if(k == e) continue; for(j = 0; j < s->height; j++){ y = 64 * j + 32; seen = 0; while(k < e && (s->vpts[k] >> 1) <= y){ seen |= 1<<(s->vpts[k] & 1); k++; } if(seen == 3 && j > 0 && iswhite(s, i, j-1) && iswhite(s, i, j)){ if((s->flags & STUBDET) == 0){ pixel(s, i, j-1); continue; } if(i <= 0 || i > s->width - 1 || j <= 0 || j > s->height - 1) continue; if(!intersectsv(s, i-1, j-1) & !intersectsh(s, i-1, j-1) & !intersectsh(s, i-1, j) | !intersectsv(s, i+1, j-1) & !intersectsh(s, i, j-1) & !intersectsh(s, i, j)) continue; pixel(s, i, j-1); } } } } void ttfscan(TTGlyph *g) { int i, j, c; TTPoint p, q, r; Scan s; memset(&s, 0, sizeof(s)); s.g = g; s.flags = 0; c = g->font->scanctrl; if((c & 1<<8) != 0 && g->font->ppem <= (c & 0xff)) s.flags |= DROPOUTS; if((c & 1<<11) != 0 && g->font->ppem > (c & 0xff)) s.flags &= ~DROPOUTS; if((c & 3<<12) != 0) s.flags &= ~DROPOUTS; if((s.flags & DROPOUTS) != 0) switch(g->font->scantype){ case 0: break; case 1: s.flags |= STUBDET; break; case 2: case 3: case 6: case 7: s.flags &= ~DROPOUTS; break; case 4: s.flags |= SMART; break; case 5: s.flags |= SMART | STUBDET; break; } // s.width = (g->pt[g->npt - 1].x + 63) / 64; // s.height = g->font->ascentpx + g->font->descentpx; s.width = -g->xminpx + g->xmaxpx; s.height = -g->yminpx + g->ymaxpx; s.stride = s.width + 7 >> 3; s.bit = mallocz(s.height * s.stride, 1); assert(s.bit != nil); for(i = 0; i < g->npt; i++){ g->pt[i].x -= g->xminpx * 64; g->pt[i].y -= g->yminpx * 64; // g->pt[i].y += g->font->descentpx * 64; } for(i = 0; i < g->ncon; i++){ if(g->confst[i] + 1 >= g->confst[i+1]) continue; p = g->pt[g->confst[i]]; assert((p.flags & 1) != 0); for(j = g->confst[i]; j++ < g->confst[i+1]; ){ if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0) q = g->pt[j++]; else q = p; if(j >= g->confst[i+1]) r = g->pt[g->confst[i]]; else{ r = g->pt[j]; if((g->pt[j].flags & 1) == 0){ r.x = (r.x + q.x) / 2; r.y = (r.y + q.y) / 2; } } dobezier(&s, p, q, r); p = r; if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0) j--; } } hprep(&s); if((s.flags & DROPOUTS) != 0) vprep(&s); hscan(&s); if((s.flags & DROPOUTS) != 0) vscan(&s); free(s.hpts); free(s.vpts); free(s.hscanl); free(s.vscanl); free(s.lines); g->bit = s.bit; g->width = s.width; g->height = s.height; g->stride = s.stride; } int ttfgetcontour(TTGlyph *g, int i, float **fp, int *np) { float offx, offy, scale; float *nf; int n, j; TTPoint p, q, r; if((uint)i >= g->ncon) return 0; if(g->confst[i]+1 >= g->confst[i+1]){ if(np != nil) *np = 0; if(fp != nil) *fp = malloc(0); return g->ncon - i; } if(g->bit != nil){ scale = 1.0f / 64; offx = g->xminpx; offy = g->yminpx; }else{ scale = 1.0f * g->font->ppem / g->font->u->emsize; offx = 0; offy = 0; } p = g->pt[g->confst[i]]; n = 1; if(fp != nil){ *fp = malloc(2 * sizeof(float)); if(*fp == nil) return -1; (*fp)[0] = p.x * scale; (*fp)[1] = p.y * scale + offy; } assert((p.flags & 1) != 0); for(j = g->confst[i]; j++ < g->confst[i+1]; ){ if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0) q = g->pt[j++]; else q = p; if(j >= g->confst[i+1]) r = g->pt[g->confst[i]]; else{ r = g->pt[j]; if((g->pt[j].flags & 1) == 0){ r.x = (r.x + q.x) / 2; r.y = (r.y + q.y) / 2; } } if(fp != nil){ nf = realloc(*fp, sizeof(float) * 2 * (n + 2)); if(nf == nil){ free(*fp); return -1; } *fp = nf; nf[2*n] = q.x * scale; nf[2*n+1] = q.y * scale + offy; nf[2*n+2] = r.x * scale; nf[2*n+3] = r.y * scale + offy; } p = r; n += 2; if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0) j--; } if(np != nil) *np = n; return g->ncon - i; }