libass/ass_font.c

   1 /*
   2  * Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@gmail.com>
   3  *
   4  * This file is part of libass.
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include "config.h"
  20
  21 #include <inttypes.h>
  22 #include <ft2build.h>
  23 #include FT_FREETYPE_H
  24 #include FT_SYNTHESIS_H
  25 #include FT_GLYPH_H
  26 #include FT_TRUETYPE_TABLES_H
  27 #include FT_OUTLINE_H
  28 #include <strings.h>
  29
  30 #include "ass.h"
  31 #include "ass_library.h"
  32 #include "ass_font.h"
  33 #include "ass_fontconfig.h"
  34 #include "ass_utils.h"
  35 #include "ass_shaper.h"
  36
  37 /**
  38  * Select a good charmap, prefer Microsoft Unicode charmaps.
  39  * Otherwise, let FreeType decide.
  40  */
  41 static void charmap_magic(ASS_Library *library, FT_Face face)
  42 {
  43     int i;
  44     int ms_cmap = -1;
  45
  46     // Search for a Microsoft Unicode cmap
  47     for (i = 0; i < face->num_charmaps; ++i) {
  48         FT_CharMap cmap = face->charmaps[i];
  49         unsigned pid = cmap->platform_id;
  50         unsigned eid = cmap->encoding_id;
  51         if (pid == 3 /*microsoft */
  52             && (eid == 1 /*unicode bmp */
  53                 || eid == 10 /*full unicode */ )) {
  54             FT_Set_Charmap(face, cmap);
  55             return;
  56         } else if (pid == 3 && ms_cmap < 0)
  57             ms_cmap = i;
  58     }
  59
  60     // Try the first Microsoft cmap if no Microsoft Unicode cmap was found
  61     if (ms_cmap >= 0) {
  62         FT_CharMap cmap = face->charmaps[ms_cmap];
  63         FT_Set_Charmap(face, cmap);
  64         return;
  65     }
  66
  67     if (!face->charmap) {
  68         if (face->num_charmaps == 0) {
  69             ass_msg(library, MSGL_WARN, "Font face with no charmaps");
  70             return;
  71         }
  72         ass_msg(library, MSGL_WARN,
  73                 "No charmap autodetected, trying the first one");
  74         FT_Set_Charmap(face, face->charmaps[0]);
  75         return;
  76     }
  77 }
  78
  79 /**
  80  * \brief find a memory font by name
  81  */
  82 static int find_font(ASS_Library *library, char *name)
  83 {
  84     int i;
  85     for (i = 0; i < library->num_fontdata; ++i)
  86         if (strcasecmp(name, library->fontdata[i].name) == 0)
  87             return i;
  88     return -1;
  89 }
  90
  91 static void buggy_font_workaround(FT_Face face)
  92 {
  93     // Some fonts have zero Ascender/Descender fields in 'hhea' table.
  94     // In this case, get the information from 'os2' table or, as
  95     // a last resort, from face.bbox.
  96     if (face->ascender + face->descender == 0 || face->height == 0) {
  97         TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
  98         if (os2) {
  99             face->ascender = os2->sTypoAscender;
 100             face->descender = os2->sTypoDescender;
 101             face->height = face->ascender - face->descender;
 102         } else {
 103             face->ascender = face->bbox.yMax;
 104             face->descender = face->bbox.yMin;
 105             face->height = face->ascender - face->descender;
 106         }
 107     }
 108 }
 109
 110 /**
 111  * \brief Select a face with the given charcode and add it to ASS_Font
 112  * \return index of the new face in font->faces, -1 if failed
 113  */
 114 static int add_face(void *fc_priv, ASS_Font *font, uint32_t ch)
 115 {
 116     char *path;
 117     int index;
 118     FT_Face face;
 119     int error;
 120     int mem_idx;
 121
 122     if (font->n_faces == ASS_FONT_MAX_FACES)
 123         return -1;
 124
 125     path =
 126         fontconfig_select(font->library, fc_priv, font->desc.family,
 127                           font->desc.treat_family_as_pattern,
 128                           font->desc.bold, font->desc.italic, &index, ch);
 129     if (!path)
 130         return -1;
 131
 132     mem_idx = find_font(font->library, path);
 133     if (mem_idx >= 0) {
 134         error =
 135             FT_New_Memory_Face(font->ftlibrary,
 136                                (unsigned char *) font->library->
 137                                fontdata[mem_idx].data,
 138                                font->library->fontdata[mem_idx].size, index,
 139                                &face);
 140         if (error) {
 141             ass_msg(font->library, MSGL_WARN,
 142                     "Error opening memory font: '%s'", path);
 143             free(path);
 144             return -1;
 145         }
 146     } else {
 147         error = FT_New_Face(font->ftlibrary, path, index, &face);
 148         if (error) {
 149             ass_msg(font->library, MSGL_WARN,
 150                     "Error opening font: '%s', %d", path, index);
 151             free(path);
 152             return -1;
 153         }
 154     }
 155     charmap_magic(font->library, face);
 156     buggy_font_workaround(face);
 157
 158     font->faces[font->n_faces++] = face;
 159     ass_face_set_size(face, font->size);
 160     free(path);
 161     return font->n_faces - 1;
 162 }
 163
 164 /**
 165  * \brief Create a new ASS_Font according to "desc" argument
 166  */
 167 ASS_Font *ass_font_new(Cache *font_cache, ASS_Library *library,
 168                        FT_Library ftlibrary, void *fc_priv,
 169                        ASS_FontDesc *desc)
 170 {
 171     int error;
 172     ASS_Font *fontp;
 173     ASS_Font font;
 174
 175     fontp = ass_cache_get(font_cache, desc);
 176     if (fontp)
 177         return fontp;
 178
 179     font.library = library;
 180     font.ftlibrary = ftlibrary;
 181     font.shaper_priv = NULL;
 182     font.n_faces = 0;
 183     font.desc.family = strdup(desc->family);
 184     font.desc.treat_family_as_pattern = desc->treat_family_as_pattern;
 185     font.desc.bold = desc->bold;
 186     font.desc.italic = desc->italic;
 187     font.desc.vertical = desc->vertical;
 188
 189     font.scale_x = font.scale_y = 1.;
 190     font.v.x = font.v.y = 0;
 191     font.size = 0.;
 192
 193     error = add_face(fc_priv, &font, 0);
 194     if (error == -1) {
 195         free(font.desc.family);
 196         return 0;
 197     } else
 198         return ass_cache_put(font_cache, &font.desc, &font);
 199 }
 200
 201 /**
 202  * \brief Set font transformation matrix and shift vector
 203  **/
 204 void ass_font_set_transform(ASS_Font *font, double scale_x,
 205                             double scale_y, FT_Vector *v)
 206 {
 207     font->scale_x = scale_x;
 208     font->scale_y = scale_y;
 209     if (v) {
 210         font->v.x = v->x;
 211         font->v.y = v->y;
 212     }
 213 }
 214
 215 void ass_face_set_size(FT_Face face, double size)
 216 {
 217     TT_HoriHeader *hori = FT_Get_Sfnt_Table(face, ft_sfnt_hhea);
 218     TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 219     double mscale = 1.;
 220     FT_Size_RequestRec rq;
 221     FT_Size_Metrics *m = &face->size->metrics;
 222     // VSFilter uses metrics from TrueType OS/2 table
 223     // The idea was borrowed from asa (http://asa.diac24.net)
 224     if (hori && os2) {
 225         int hori_height = hori->Ascender - hori->Descender;
 226         int os2_height = os2->usWinAscent + os2->usWinDescent;
 227         if (hori_height && os2_height)
 228             mscale = (double) hori_height / os2_height;
 229     }
 230     memset(&rq, 0, sizeof(rq));
 231     rq.type = FT_SIZE_REQUEST_TYPE_REAL_DIM;
 232     rq.width = 0;
 233     rq.height = double_to_d6(size * mscale);
 234     rq.horiResolution = rq.vertResolution = 0;
 235     FT_Request_Size(face, &rq);
 236     m->ascender /= mscale;
 237     m->descender /= mscale;
 238     m->height /= mscale;
 239 }
 240
 241 /**
 242  * \brief Set font size
 243  **/
 244 void ass_font_set_size(ASS_Font *font, double size)
 245 {
 246     int i;
 247     if (font->size != size) {
 248         font->size = size;
 249         for (i = 0; i < font->n_faces; ++i)
 250             ass_face_set_size(font->faces[i], size);
 251     }
 252 }
 253
 254 /**
 255  * \brief Get maximal font ascender and descender.
 256  * \param ch character code
 257  * The values are extracted from the font face that provides glyphs for the given character
 258  **/
 259 void ass_font_get_asc_desc(ASS_Font *font, uint32_t ch, int *asc,
 260                            int *desc)
 261 {
 262     int i;
 263     for (i = 0; i < font->n_faces; ++i) {
 264         FT_Face face = font->faces[i];
 265         TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 266         if (FT_Get_Char_Index(face, ch)) {
 267             int y_scale = face->size->metrics.y_scale;
 268             if (os2) {
 269                 *asc = FT_MulFix(os2->usWinAscent, y_scale);
 270                 *desc = FT_MulFix(os2->usWinDescent, y_scale);
 271             } else {
 272                 *asc = FT_MulFix(face->ascender, y_scale);
 273                 *desc = FT_MulFix(-face->descender, y_scale);
 274             }
 275             return;
 276         }
 277     }
 278
 279     *asc = *desc = 0;
 280 }
 281
 282 /*
 283  * Strike a glyph with a horizontal line; it's possible to underline it
 284  * and/or strike through it.  For the line's position and size, truetype
 285  * tables are consulted.  Obviously this relies on the data in the tables
 286  * being accurate.
 287  *
 288  */
 289 static int ass_strike_outline_glyph(FT_Face face, ASS_Font *font,
 290                                     FT_Glyph glyph, int under, int through)
 291 {
 292     TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 293     TT_Postscript *ps = FT_Get_Sfnt_Table(face, ft_sfnt_post);
 294     FT_Outline *ol = &((FT_OutlineGlyph) glyph)->outline;
 295     int bear, advance, y_scale, i, dir;
 296
 297     if (!under && !through)
 298         return 0;
 299
 300     // Grow outline
 301     i = (under ? 4 : 0) + (through ? 4 : 0);
 302     ol->points = realloc(ol->points, sizeof(FT_Vector) *
 303                          (ol->n_points + i));
 304     ol->tags = realloc(ol->tags, ol->n_points + i);
 305     i = !!under + !!through;
 306     ol->contours = realloc(ol->contours, sizeof(short) *
 307                            (ol->n_contours + i));
 308
 309     // If the bearing is negative, the glyph starts left of the current
 310     // pen position
 311     bear = FFMIN(face->glyph->metrics.horiBearingX, 0);
 312     // We're adding half a pixel to avoid small gaps
 313     advance = d16_to_d6(glyph->advance.x) + 32;
 314     y_scale = face->size->metrics.y_scale;
 315
 316     // Reverse drawing direction for non-truetype fonts
 317     dir = FT_Outline_Get_Orientation(ol);
 318
 319     // Add points to the outline
 320     if (under && ps) {
 321         int pos, size;
 322         pos = FT_MulFix(ps->underlinePosition, y_scale * font->scale_y);
 323         size = FT_MulFix(ps->underlineThickness,
 324                          y_scale * font->scale_y / 2);
 325
 326         if (pos > 0 || size <= 0)
 327             return 1;
 328
 329         FT_Vector points[4] = {
 330             {.x = bear,      .y = pos + size},
 331             {.x = advance,   .y = pos + size},
 332             {.x = advance,   .y = pos - size},
 333             {.x = bear,      .y = pos - size},
 334         };
 335
 336         if (dir == FT_ORIENTATION_TRUETYPE) {
 337             for (i = 0; i < 4; i++) {
 338                 ol->points[ol->n_points] = points[i];
 339                 ol->tags[ol->n_points++] = 1;
 340             }
 341         } else {
 342             for (i = 3; i >= 0; i--) {
 343                 ol->points[ol->n_points] = points[i];
 344                 ol->tags[ol->n_points++] = 1;
 345             }
 346         }
 347
 348         ol->contours[ol->n_contours++] = ol->n_points - 1;
 349     }
 350
 351     if (through && os2) {
 352         int pos, size;
 353         pos = FT_MulFix(os2->yStrikeoutPosition, y_scale * font->scale_y);
 354         size = FT_MulFix(os2->yStrikeoutSize, y_scale * font->scale_y / 2);
 355
 356         if (pos < 0 || size <= 0)
 357             return 1;
 358
 359         FT_Vector points[4] = {
 360             {.x = bear,      .y = pos + size},
 361             {.x = advance,   .y = pos + size},
 362             {.x = advance,   .y = pos - size},
 363             {.x = bear,      .y = pos - size},
 364         };
 365
 366         if (dir == FT_ORIENTATION_TRUETYPE) {
 367             for (i = 0; i < 4; i++) {
 368                 ol->points[ol->n_points] = points[i];
 369                 ol->tags[ol->n_points++] = 1;
 370             }
 371         } else {
 372             for (i = 3; i >= 0; i--) {
 373                 ol->points[ol->n_points] = points[i];
 374                 ol->tags[ol->n_points++] = 1;
 375             }
 376         }
 377
 378         ol->contours[ol->n_contours++] = ol->n_points - 1;
 379     }
 380
 381     return 0;
 382 }
 383
 384 void outline_copy(FT_Library lib, FT_Outline *source, FT_Outline **dest)
 385 {
 386     if (source == NULL) {
 387         *dest = NULL;
 388         return;
 389     }
 390     *dest = calloc(1, sizeof(**dest));
 391
 392     FT_Outline_New(lib, source->n_points, source->n_contours, *dest);
 393     FT_Outline_Copy(source, *dest);
 394 }
 395
 396 void outline_free(FT_Library lib, FT_Outline *outline)
 397 {
 398     if (outline)
 399         FT_Outline_Done(lib, outline);
 400     free(outline);
 401 }
 402
 403 /**
 404  * Slightly embold a glyph without touching its metrics
 405  */
 406 static void ass_glyph_embolden(FT_GlyphSlot slot)
 407 {
 408     int str;
 409
 410     if (slot->format != FT_GLYPH_FORMAT_OUTLINE)
 411         return;
 412
 413     str = FT_MulFix(slot->face->units_per_EM,
 414                     slot->face->size->metrics.y_scale) / 64;
 415
 416     FT_Outline_Embolden(&slot->outline, str);
 417 }
 418
 419 /**
 420  * \brief Get glyph and face index
 421  * Finds a face that has the requested codepoint and returns both face
 422  * and glyph index.
 423  */
 424 int ass_font_get_index(void *fcpriv, ASS_Font *font, uint32_t symbol,
 425                        int *face_index, int *glyph_index)
 426 {
 427     int index = 0;
 428     int i;
 429     FT_Face face = 0;
 430
 431     *glyph_index = 0;
 432
 433     if (symbol < 0x20) {
 434         *face_index = 0;
 435         return 0;
 436     }
 437     // Handle NBSP like a regular space when rendering the glyph
 438     if (symbol == 0xa0)
 439         symbol = ' ';
 440     if (font->n_faces == 0) {
 441         *face_index = 0;
 442         return 0;
 443     }
 444
 445     // try with the requested face
 446     if (*face_index < font->n_faces) {
 447         face = font->faces[*face_index];
 448         index = FT_Get_Char_Index(face, symbol);
 449     }
 450
 451     // not found in requested face, try all others
 452     for (i = 0; i < font->n_faces && index == 0; ++i) {
 453         face = font->faces[i];
 454         index = FT_Get_Char_Index(face, symbol);
 455         if (index)
 456             *face_index = i;
 457     }
 458
 459 #ifdef CONFIG_FONTCONFIG
 460     if (index == 0) {
 461         int face_idx;
 462         ass_msg(font->library, MSGL_INFO,
 463                 "Glyph 0x%X not found, selecting one more "
 464                 "font for (%s, %d, %d)", symbol, font->desc.family,
 465                 font->desc.bold, font->desc.italic);
 466         face_idx = *face_index = add_face(fcpriv, font, symbol);
 467         if (face_idx >= 0) {
 468             face = font->faces[face_idx];
 469             index = FT_Get_Char_Index(face, symbol);
 470             if (index == 0 && face->num_charmaps > 0) {
 471                 int i;
 472                 ass_msg(font->library, MSGL_WARN,
 473                     "Glyph 0x%X not found, broken font? Trying all charmaps", symbol);
 474                 for (i = 0; i < face->num_charmaps; i++) {
 475                     FT_Set_Charmap(face, face->charmaps[i]);
 476                     if ((index = FT_Get_Char_Index(face, symbol)) != 0) break;
 477                 }
 478             }
 479             if (index == 0) {
 480                 ass_msg(font->library, MSGL_ERR,
 481                         "Glyph 0x%X not found in font for (%s, %d, %d)",
 482                         symbol, font->desc.family, font->desc.bold,
 483                         font->desc.italic);
 484             }
 485         }
 486     }
 487 #endif
 488     // FIXME: make sure we have a valid face_index. this is a HACK.
 489     *face_index  = FFMAX(*face_index, 0);
 490     *glyph_index = index;
 491
 492     return 1;
 493 }
 494
 495 /**
 496  * \brief Get a glyph
 497  * \param ch character code
 498  **/
 499 FT_Glyph ass_font_get_glyph(void *fontconfig_priv, ASS_Font *font,
 500                             uint32_t ch, int face_index, int index,
 501                             ASS_Hinting hinting, int deco)
 502 {
 503     int error;
 504     FT_Glyph glyph;
 505     FT_Face face = font->faces[face_index];
 506     int flags = 0;
 507     int vertical = font->desc.vertical;
 508
 509     flags = FT_LOAD_NO_BITMAP | FT_LOAD_IGNORE_GLOBAL_ADVANCE_WIDTH
 510             | FT_LOAD_IGNORE_TRANSFORM;
 511     switch (hinting) {
 512     case ASS_HINTING_NONE:
 513         flags |= FT_LOAD_NO_HINTING;
 514         break;
 515     case ASS_HINTING_LIGHT:
 516         flags |= FT_LOAD_FORCE_AUTOHINT | FT_LOAD_TARGET_LIGHT;
 517         break;
 518     case ASS_HINTING_NORMAL:
 519         flags |= FT_LOAD_FORCE_AUTOHINT;
 520         break;
 521     case ASS_HINTING_NATIVE:
 522         break;
 523     }
 524
 525     error = FT_Load_Glyph(face, index, flags);
 526     if (error) {
 527         ass_msg(font->library, MSGL_WARN, "Error loading glyph, index %d",
 528                 index);
 529         return 0;
 530     }
 531     if (!(face->style_flags & FT_STYLE_FLAG_ITALIC) &&
 532         (font->desc.italic > 55)) {
 533         FT_GlyphSlot_Oblique(face->glyph);
 534     }
 535
 536     if (!(face->style_flags & FT_STYLE_FLAG_BOLD) &&
 537         (font->desc.bold > 80)) {
 538         ass_glyph_embolden(face->glyph);
 539     }
 540     error = FT_Get_Glyph(face->glyph, &glyph);
 541     if (error) {
 542         ass_msg(font->library, MSGL_WARN, "Error loading glyph, index %d",
 543                 index);
 544         return 0;
 545     }
 546
 547     // Rotate glyph, if needed
 548     if (vertical && ch >= VERTICAL_LOWER_BOUND) {
 549         FT_Matrix m = { 0, double_to_d16(-1.0), double_to_d16(1.0), 0 };
 550         TT_OS2 *os2 = FT_Get_Sfnt_Table(face, ft_sfnt_os2);
 551         int desc = 0;
 552
 553         if (os2)
 554             desc = FT_MulFix(os2->sTypoDescender, face->size->metrics.y_scale);
 555
 556         FT_Outline_Translate(&((FT_OutlineGlyph) glyph)->outline, 0, -desc);
 557         FT_Outline_Transform(&((FT_OutlineGlyph) glyph)->outline, &m);
 558         FT_Outline_Translate(&((FT_OutlineGlyph) glyph)->outline,
 559                              face->glyph->metrics.vertAdvance, desc);
 560         glyph->advance.x = face->glyph->linearVertAdvance;
 561     }
 562
 563     // Apply scaling and shift
 564     FT_Matrix scale = { double_to_d16(font->scale_x), 0, 0,
 565                         double_to_d16(font->scale_y) };
 566     FT_Outline *outl = &((FT_OutlineGlyph) glyph)->outline;
 567     FT_Outline_Transform(outl, &scale);
 568     FT_Outline_Translate(outl, font->v.x, font->v.y);
 569     glyph->advance.x *= font->scale_x;
 570
 571     ass_strike_outline_glyph(face, font, glyph, deco & DECO_UNDERLINE,
 572                              deco & DECO_STRIKETHROUGH);
 573
 574     return glyph;
 575 }
 576
 577 /**
 578  * \brief Get kerning for the pair of glyphs.
 579  **/
 580 FT_Vector ass_font_get_kerning(ASS_Font *font, uint32_t c1, uint32_t c2)
 581 {
 582     FT_Vector v = { 0, 0 };
 583     int i;
 584
 585     if (font->desc.vertical)
 586         return v;
 587
 588     for (i = 0; i < font->n_faces; ++i) {
 589         FT_Face face = font->faces[i];
 590         int i1 = FT_Get_Char_Index(face, c1);
 591         int i2 = FT_Get_Char_Index(face, c2);
 592         if (i1 && i2) {
 593             if (FT_HAS_KERNING(face))
 594                 FT_Get_Kerning(face, i1, i2, FT_KERNING_DEFAULT, &v);
 595             return v;
 596         }
 597         if (i1 || i2)           // these glyphs are from different font faces, no kerning information
 598             return v;
 599     }
 600     return v;
 601 }
 602
 603 /**
 604  * \brief Deallocate ASS_Font
 605  **/
 606 void ass_font_free(ASS_Font *font)
 607 {
 608     int i;
 609     for (i = 0; i < font->n_faces; ++i)
 610         if (font->faces[i])
 611             FT_Done_Face(font->faces[i]);
 612     if (font->shaper_priv)
 613         ass_shaper_font_data_free(font->shaper_priv);
 614     free(font->desc.family);
 615     free(font);
 616 }
 617
 618 /**
 619  * \brief Calculate the cbox of a series of points
 620  */
 621 static void
 622 get_contour_cbox(FT_BBox *box, FT_Vector *points, int start, int end)
 623 {
 624     box->xMin = box->yMin = INT_MAX;
 625     box->xMax = box->yMax = INT_MIN;
 626     int i;
 627
 628     for (i = start; i <= end; i++) {
 629         box->xMin = (points[i].x < box->xMin) ? points[i].x : box->xMin;
 630         box->xMax = (points[i].x > box->xMax) ? points[i].x : box->xMax;
 631         box->yMin = (points[i].y < box->yMin) ? points[i].y : box->yMin;
 632         box->yMax = (points[i].y > box->yMax) ? points[i].y : box->yMax;
 633     }
 634 }
 635
 636 /**
 637  * \brief Determine winding direction of a contour
 638  * \return direction; 0 = clockwise
 639  */
 640 static int get_contour_direction(FT_Vector *points, int start, int end)
 641 {
 642     int i;
 643     long long sum = 0;
 644     int x = points[start].x;
 645     int y = points[start].y;
 646     for (i = start + 1; i <= end; i++) {
 647         sum += x * (points[i].y - y) - y * (points[i].x - x);
 648         x = points[i].x;
 649         y = points[i].y;
 650     }
 651     sum += x * (points[start].y - y) - y * (points[start].x - x);
 652     return sum > 0;
 653 }
 654
 655 /**
 656  * \brief Apply fixups to please the FreeType stroker and improve the
 657  * rendering result, especially in case the outline has some anomalies.
 658  * At the moment, the following fixes are done:
 659  *
 660  * 1. Reverse contours that have "inside" winding direction but are not
 661  *    contained in any other contours' cbox.
 662  * 2. Remove "inside" contours depending on border size, so that large
 663  *    borders do not reverse the winding direction, which leads to "holes"
 664  *    inside the border. The inside will be filled by the border of the
 665  *    outside contour anyway in this case.
 666  *
 667  * \param outline FreeType outline, modified in-place
 668  * \param border_x border size, x direction, d6 format
 669  * \param border_x border size, y direction, d6 format
 670  */
 671 void fix_freetype_stroker(FT_Outline *outline, int border_x, int border_y)
 672 {
 673     int nc = outline->n_contours;
 674     int begin, stop;
 675     char modified = 0;
 676     char *valid_cont = malloc(nc);
 677     int start = 0;
 678     int end = -1;
 679     FT_BBox *boxes = malloc(nc * sizeof(FT_BBox));
 680     int i, j;
 681     int inside_direction;
 682
 683     inside_direction = FT_Outline_Get_Orientation(outline) ==
 684         FT_ORIENTATION_TRUETYPE;
 685
 686     // create a list of cboxes of the contours
 687     for (i = 0; i < nc; i++) {
 688         start = end + 1;
 689         end = outline->contours[i];
 690         get_contour_cbox(&boxes[i], outline->points, start, end);
 691     }
 692
 693     // for each contour, check direction and whether it's "outside"
 694     // or contained in another contour
 695     end = -1;
 696     for (i = 0; i < nc; i++) {
 697         start = end + 1;
 698         end = outline->contours[i];
 699         int dir = get_contour_direction(outline->points, start, end);
 700         valid_cont[i] = 1;
 701         if (dir == inside_direction) {
 702             for (j = 0; j < nc; j++) {
 703                 if (i == j)
 704                     continue;
 705                 if (boxes[i].xMin >= boxes[j].xMin &&
 706                     boxes[i].xMax <= boxes[j].xMax &&
 707                     boxes[i].yMin >= boxes[j].yMin &&
 708                     boxes[i].yMax <= boxes[j].yMax)
 709                     goto check_inside;
 710             }
 711             /* "inside" contour but we can't find anything it could be
 712              * inside of - assume the font is buggy and it should be
 713              * an "outside" contour, and reverse it */
 714             for (j = 0; j < (end + 1 - start) / 2; j++) {
 715                 FT_Vector temp = outline->points[start + j];
 716                 char temp2 = outline->tags[start + j];
 717                 outline->points[start + j] = outline->points[end - j];
 718                 outline->points[end - j] = temp;
 719                 outline->tags[start + j] = outline->tags[end - j];
 720                 outline->tags[end - j] = temp2;
 721             }
 722             dir ^= 1;
 723         }
 724         check_inside:
 725         if (dir == inside_direction) {
 726             FT_BBox box;
 727             get_contour_cbox(&box, outline->points, start, end);
 728             int width = box.xMax - box.xMin;
 729             int height = box.yMax - box.yMin;
 730             if (width < border_x * 2 || height < border_y * 2) {
 731                 valid_cont[i] = 0;
 732                 modified = 1;
 733             }
 734         }
 735     }
 736
 737     // if we need to modify the outline, rewrite it and skip
 738     // the contours that we determined should be removed.
 739     if (modified) {
 740         int p = 0, c = 0;
 741         for (i = 0; i < nc; i++) {
 742             if (!valid_cont[i])
 743                 continue;
 744             begin = (i == 0) ? 0 : outline->contours[i - 1] + 1;
 745             stop = outline->contours[i];
 746             for (j = begin; j <= stop; j++) {
 747                 outline->points[p].x = outline->points[j].x;
 748                 outline->points[p].y = outline->points[j].y;
 749                 outline->tags[p] = outline->tags[j];
 750                 p++;
 751             }
 752             outline->contours[c] = p - 1;
 753             c++;
 754         }
 755         outline->n_points = p;
 756         outline->n_contours = c;
 757     }
 758
 759     free(boxes);
 760     free(valid_cont);
 761 }
 762