sys/src/libttf/scan.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <bio.h>
   4 #include <ttf.h>
   5 #include "impl.h"
   6
   7 typedef struct Scan Scan;
   8 typedef struct TTLine TTLine;
   9
  10 enum {
  11         LINEBLOCK = 32,
  12         PTBLOCK = 64,
  13 };
  14
  15 struct TTLine {
  16         int x0, y0;
  17         int x1, y1;
  18         int link;
  19         u8int dir;
  20 };
  21
  22 struct Scan {
  23         enum {
  24                 DROPOUTS = 1,
  25                 STUBDET = 2,
  26                 SMART = 4,
  27         } flags;
  28
  29         TTGlyph *g;
  30
  31         TTLine *lines;
  32         int nlines;
  33
  34         int *hpts, *vpts;
  35         int nhpts, nvpts;
  36         int *hscanl, *vscanl;
  37
  38         u8int *bit;
  39         int width, height;
  40         int stride;
  41 };
  42
  43 static void
  44 dobezier(Scan *s, TTPoint p, TTPoint q, TTPoint r)
  45 {
  46         vlong m, n;
  47         TTLine *l;
  48
  49         m = (vlong)(q.x - p.x) * (r.y - p.y) - (vlong)(q.y - p.y) * (r.x - p.x);
  50         n = (vlong)(r.x - p.x) * (r.x - p.x) + (vlong)(r.y - p.y) * (r.y - p.y);
  51         if(m * m > 4 * n){
  52                 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});
  53                 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);
  54                 return;
  55         }
  56         if((s->nlines & LINEBLOCK - 1) == 0)
  57                 s->lines = realloc(s->lines, sizeof(TTLine) * (s->nlines + LINEBLOCK));
  58         l = &s->lines[s->nlines++];
  59         if(p.y < r.y){
  60                 l->x0 = p.x;
  61                 l->y0 = p.y;
  62                 l->x1 = r.x;
  63                 l->y1 = r.y;
  64                 l->dir = 0;
  65         }else{
  66                 l->x0 = r.x;
  67                 l->y0 = r.y;
  68                 l->x1 = p.x;
  69                 l->y1 = p.y;
  70                 l->dir = 1;
  71         }
  72         l->link = -1;
  73 }
  74
  75 static int
  76 hlinecmp(void *va, void *vb)
  77 {
  78         TTLine *a, *b;
  79
  80         a = va;
  81         b = vb;
  82         if(a->y0 < b->y0) return -1;
  83         if(a->y0 > b->y0) return 1;
  84         return 0;
  85 }
  86
  87 static int
  88 vlinecmp(void *va, void *vb)
  89 {
  90         TTLine *a, *b;
  91
  92         a = va;
  93         b = vb;
  94         if(a->x0 < b->x0) return -1;
  95         if(a->x0 > b->x0) return 1;
  96         return 0;
  97 }
  98
  99 static int
 100 intcmp(void *va, void *vb)
 101 {
 102         int a, b;
 103
 104         a = *(int*)va;
 105         b = *(int*)vb;
 106         return (a>b) - (a<b);
 107 }
 108
 109 static void
 110 hprep(Scan *s)
 111 {
 112         int i, j, x, y;
 113         TTLine *l;
 114         int watch, act, *p;
 115
 116         qsort(s->lines, s->nlines, sizeof(TTLine), hlinecmp);
 117         s->hscanl = calloc(sizeof(int), (s->height + 1));
 118         act = -1;
 119         watch = 0;
 120         p = &act;
 121         for(i = 0; i < s->height; i++){
 122                 y = 64 * i + 32;
 123                 for(; watch < s->nlines && s->lines[watch].y0 <= y; watch++){
 124                         if(s->lines[watch].y1 <= y || s->lines[watch].y0 == s->lines[watch].y1)
 125                                 continue;
 126                         s->lines[watch].link = -1;
 127                         *p = watch;
 128                         p = &s->lines[watch].link;
 129                 }
 130                 s->hscanl[i] = s->nhpts;
 131                 p = &act;
 132                 while(j = *p, j >= 0){
 133                         l = &s->lines[j];
 134                         if(l->y1 <= y){
 135                                 j = l->link;
 136                                 l->link = -1;
 137                                 *p = j;
 138                                 continue;
 139                         }
 140                         x = l->x0 + ttfvrounddiv((vlong)(y - l->y0)*(l->x1 - l->x0), l->y1 - l->y0);
 141                         if((s->nhpts & PTBLOCK - 1) == 0)
 142                                 s->hpts = realloc(s->hpts, (s->nhpts + PTBLOCK) * sizeof(int));
 143                         s->hpts[s->nhpts++] = x << 1 | l->dir;
 144                         p = &l->link;
 145                 }
 146                 qsort(s->hpts + s->hscanl[i], s->nhpts - s->hscanl[i], sizeof(int), intcmp);
 147         }
 148         s->hscanl[i] = s->nhpts;
 149 }
 150
 151 static int
 152 iswhite(Scan *s, int x, int y)
 153 {
 154         return (s->bit[(s->height - 1 - y) * s->stride + (x>>3)] >> 7-(x&7) & 1)==0;
 155 }
 156
 157 static void
 158 pixel(Scan *s, int x, int y)
 159 {
 160         assert(x >= 0 && x < s->width && y >= 0 && y < s->height);
 161         s->bit[(s->height - 1 - y) * s->stride + (x>>3)] |= (1<<7-(x&7));
 162 }
 163
 164 static int
 165 intersectsh(Scan *s, int x, int y)
 166 {
 167         int a, b, c, vc, v;
 168
 169         a = s->hscanl[y];
 170         b = s->hscanl[y+1]-1;
 171         v = x * 64 + 32;
 172         if(a > b || s->hpts[a]>>1 > v + 64 || s->hpts[b]>>1 < v) return 0;
 173         while(a <= b){
 174                 c = (a + b) / 2;
 175                 vc = s->hpts[c]>>1;
 176                 if(vc < v)
 177                         a = c + 1;
 178                 else if(vc > v + 64)
 179                         b = c - 1;
 180                 else
 181                         return 1;
 182         }
 183         return 0;
 184 }
 185
 186 static int
 187 intersectsv(Scan *s, int x, int y)
 188 {
 189         int a, b, c, vc, v;
 190
 191         a = s->vscanl[x];
 192         b = s->vscanl[x+1]-1;
 193         v = y * 64 + 32;
 194         if(a > b || s->vpts[a]>>1 > v + 64 || s->vpts[b]>>1 < v) return 0;
 195         while(a <= b){
 196                 c = (a + b) / 2;
 197                 vc = s->vpts[c]>>1;
 198                 if(vc < v)
 199                         a = c + 1;
 200                 else if(vc > v + 64)
 201                         b = c - 1;
 202                 else
 203                         return 1;
 204         }
 205         return 0;
 206 }
 207
 208 static void
 209 hscan(Scan *s)
 210 {
 211         int i, j, k, e;
 212         int wind, match, seen, x;
 213
 214         for(i = 0; i < s->height; i++){
 215                 e = s->hscanl[i+1];
 216                 k = s->hscanl[i];
 217                 if(k == e) continue;
 218                 wind = 0;
 219                 for(j = 0; j < s->width; j++){
 220                         x = 64 * j + 32;
 221                         match = 0;
 222                         seen = 0;
 223                         while(k < e && (s->hpts[k] >> 1) <= x){
 224                                 wind += (s->hpts[k] & 1) * 2 - 1;
 225                                 seen |= 1<<(s->hpts[k] & 1);
 226                                 if((s->hpts[k] >> 1) == x)
 227                                         match++;
 228                                 k++;
 229                         }
 230                         if(match || wind)
 231                                 pixel(s, j, i);
 232                         else if((s->flags & DROPOUTS) != 0 && seen == 3 && j > 0 && iswhite(s, j-1, i)){
 233                                 if((s->flags & STUBDET) == 0){
 234                                         pixel(s, j-1, i);
 235                                         continue;
 236                                 }
 237                                 if(i <= 0 || i > s->height - 1 || j <= 0 || j > s->width - 1)
 238                                         continue;
 239                                 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))
 240                                         continue;
 241                                 pixel(s, j-1, i);
 242                         }
 243                 }
 244         }
 245 }
 246
 247 static void
 248 vprep(Scan *s)
 249 {
 250         int i, j, x, y;
 251         TTLine *l;
 252         int watch, act, *p;
 253
 254         for(i = 0; i < s->nlines; i++){
 255                 l = &s->lines[i];
 256                 if(l->x0 > l->x1){
 257                         x = l->x0, l->x0 = l->x1, l->x1 = x;
 258                         x = l->y0, l->y0 = l->y1, l->y1 = x;
 259                         l->dir ^= 1;
 260                 }
 261         }
 262         qsort(s->lines, s->nlines, sizeof(TTLine), vlinecmp);
 263         s->vscanl = calloc(sizeof(int), (s->width + 1));
 264         act = -1;
 265         watch = 0;
 266         p = &act;
 267         for(i = 0; i < s->width; i++){
 268                 x = 64 * i + 32;
 269                 for(; watch < s->nlines && s->lines[watch].x0 <= x; watch++){
 270                         if(s->lines[watch].x1 <= x || s->lines[watch].x0 == s->lines[watch].x1)
 271                                 continue;
 272                         s->lines[watch].link = -1;
 273                         *p = watch;
 274                         p = &s->lines[watch].link;
 275                 }
 276                 s->vscanl[i] = s->nvpts;
 277                 p = &act;
 278                 while(j = *p, j >= 0){
 279                         l = &s->lines[j];
 280                         if(l->x1 <= x){
 281                                 j = l->link;
 282                                 l->link = -1;
 283                                 *p = j;
 284                                 continue;
 285                         }
 286                         y = l->y0 + ttfvrounddiv((vlong)(x - l->x0) * (l->y1 - l->y0), l->x1 - l->x0);
 287                         if((s->nvpts & PTBLOCK - 1) == 0)
 288                                 s->vpts = realloc(s->vpts, (s->nvpts + PTBLOCK) * sizeof(int));
 289                         s->vpts[s->nvpts++] = y << 1 | l->dir;
 290                         p = &l->link;
 291                 }
 292                 qsort(s->vpts + s->vscanl[i], s->nvpts - s->vscanl[i], sizeof(int), intcmp);
 293         }
 294         s->vscanl[i] = s->nvpts;
 295
 296 }
 297
 298 static void
 299 vscan(Scan *s)
 300 {
 301         int i, j, k, e;
 302         int seen, y;
 303
 304         for(i = 0; i < s->width; i++){
 305                 e = s->vscanl[i+1];
 306                 k = s->vscanl[i];
 307                 if(k == e) continue;
 308                 for(j = 0; j < s->height; j++){
 309                         y = 64 * j + 32;
 310                         seen = 0;
 311                         while(k < e && (s->vpts[k] >> 1) <= y){
 312                                 seen |= 1<<(s->vpts[k] & 1);
 313                                 k++;
 314                         }
 315                         if(seen == 3 && j > 0 && iswhite(s, i, j-1) && iswhite(s, i, j)){
 316                                 if((s->flags & STUBDET) == 0){
 317                                         pixel(s, i, j-1);
 318                                         continue;
 319                                 }
 320                                 if(i <= 0 || i > s->width - 1 || j <= 0 || j > s->height - 1)
 321                                         continue;
 322                                 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))
 323                                         continue;
 324                                 pixel(s, i, j-1);
 325                         }
 326                 }
 327         }
 328 }
 329
 330 void
 331 ttfscan(TTGlyph *g)
 332 {
 333         int i, j, c;
 334         TTPoint p, q, r;
 335         Scan s;
 336
 337         memset(&s, 0, sizeof(s));
 338         s.g = g;
 339         s.flags = 0;
 340         c = g->font->scanctrl;
 341         if((c & 1<<8) != 0 && g->font->ppem <= (c & 0xff))
 342                 s.flags |= DROPOUTS;
 343         if((c & 1<<11) != 0 && g->font->ppem > (c & 0xff))
 344                 s.flags &= ~DROPOUTS;
 345         if((c & 3<<12) != 0)
 346                 s.flags &= ~DROPOUTS;
 347         if((s.flags & DROPOUTS) != 0)
 348                 switch(g->font->scantype){
 349                 case 0: break;
 350                 case 1: s.flags |= STUBDET; break;
 351                 case 2: case 3: case 6: case 7: s.flags &= ~DROPOUTS; break;
 352                 case 4: s.flags |= SMART; break;
 353                 case 5: s.flags |= SMART | STUBDET; break;
 354                 }
 355
 356 //      s.width = (g->pt[g->npt - 1].x + 63) / 64;
 357 //      s.height = g->font->ascentpx + g->font->descentpx;
 358         s.width = -g->xminpx + g->xmaxpx;
 359         s.height = -g->yminpx + g->ymaxpx;
 360         s.stride = s.width + 7 >> 3;
 361         s.bit = mallocz(s.height * s.stride, 1);
 362         assert(s.bit != nil);
 363         for(i = 0; i < g->npt; i++){
 364                 g->pt[i].x -= g->xminpx * 64;
 365                 g->pt[i].y -= g->yminpx * 64;
 366 //              g->pt[i].y += g->font->descentpx * 64;
 367         }
 368         for(i = 0; i < g->ncon; i++){
 369                 if(g->confst[i] + 1 >= g->confst[i+1]) continue;
 370                 p = g->pt[g->confst[i]];
 371                 assert((p.flags & 1) != 0);
 372                 for(j = g->confst[i]; j++ < g->confst[i+1]; ){
 373                         if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
 374                                 q = g->pt[j++];
 375                         else
 376                                 q = p;
 377                         if(j >= g->confst[i+1])
 378                                 r = g->pt[g->confst[i]];
 379                         else{
 380                                 r = g->pt[j];
 381                                 if((g->pt[j].flags & 1) == 0){
 382                                         r.x = (r.x + q.x) / 2;
 383                                         r.y = (r.y + q.y) / 2;
 384                                 }
 385                         }
 386                         dobezier(&s, p, q, r);
 387                         p = r;
 388                         if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
 389                                 j--;
 390                 }
 391         }
 392         hprep(&s);
 393         if((s.flags & DROPOUTS) != 0)
 394                 vprep(&s);
 395         hscan(&s);
 396         if((s.flags & DROPOUTS) != 0)
 397                 vscan(&s);
 398         free(s.hpts);
 399         free(s.vpts);
 400         free(s.hscanl);
 401         free(s.vscanl);
 402         free(s.lines);
 403         g->bit = s.bit;
 404         g->width = s.width;
 405         g->height = s.height;
 406         g->stride = s.stride;
 407 }
 408
 409 int
 410 ttfgetcontour(TTGlyph *g, int i, float **fp, int *np)
 411 {
 412         float offx, offy, scale;
 413         float *nf;
 414         int n, j;
 415         TTPoint p, q, r;
 416
 417         if((uint)i >= g->ncon)
 418                 return 0;
 419         if(g->confst[i]+1 >= g->confst[i+1]){
 420                 if(np != nil)
 421                         *np = 0;
 422                 if(fp != nil)
 423                         *fp = malloc(0);
 424                 return g->ncon - i;
 425         }
 426         if(g->bit != nil){
 427                 scale = 1.0f / 64;
 428                 offx = g->xminpx;
 429                 offy = g->yminpx;
 430         }else{
 431                 scale = 1.0f * g->font->ppem / g->font->u->emsize;
 432                 offx = 0;
 433                 offy = 0;
 434         }
 435         p = g->pt[g->confst[i]];
 436         n = 1;
 437         if(fp != nil){
 438                 *fp = malloc(2 * sizeof(float));
 439                 if(*fp == nil) return -1;
 440                 (*fp)[0] = p.x * scale;
 441                 (*fp)[1] = p.y * scale + offy;
 442         }
 443         assert((p.flags & 1) != 0);
 444         for(j = g->confst[i]; j++ < g->confst[i+1]; ){
 445                 if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
 446                         q = g->pt[j++];
 447                 else
 448                         q = p;
 449                 if(j >= g->confst[i+1])
 450                         r = g->pt[g->confst[i]];
 451                 else{
 452                         r = g->pt[j];
 453                         if((g->pt[j].flags & 1) == 0){
 454                                 r.x = (r.x + q.x) / 2;
 455                                 r.y = (r.y + q.y) / 2;
 456                         }
 457                 }
 458                 if(fp != nil){
 459                         nf = realloc(*fp, sizeof(float) * 2 * (n + 2));
 460                         if(nf == nil){
 461                                 free(*fp);
 462                                 return -1;
 463                         }
 464                         *fp = nf;
 465                         nf[2*n] = q.x * scale;
 466                         nf[2*n+1] = q.y * scale + offy;
 467                         nf[2*n+2] = r.x * scale;
 468                         nf[2*n+3] = r.y * scale + offy;
 469                 }
 470                 p = r;
 471                 n += 2;
 472                 if(j < g->confst[i+1] && (g->pt[j].flags & 1) == 0)
 473                         j--;
 474         }
 475         if(np != nil)
 476                 *np = n;
 477         return g->ncon - i;
 478 }