granicus.if.org Git - libass/blob - libass/ass_drawing.c

   1 /*
   2  * Copyright (C) 2009 Grigori Goronzy <greg@geekmind.org>
   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 <ft2build.h>
  20 #include FT_GLYPH_H
  21 #include FT_OUTLINE_H
  22 #include FT_BBOX_H
  23 #include <math.h>
  24
  25 #include "ass_utils.h"
  26 #include "ass_font.h"
  27 #include "ass_drawing.h"
  28
  29 #define CURVE_ACCURACY 64.0
  30 #define GLYPH_INITIAL_POINTS 100
  31 #define GLYPH_INITIAL_CONTOURS 5
  32
  33 /*
  34  * \brief Get and prepare a FreeType glyph
  35  */
  36 static void drawing_make_glyph(ASS_Drawing *drawing, void *fontconfig_priv,
  37                                ASS_Font *font)
  38 {
  39     FT_OutlineGlyph glyph;
  40
  41     // This is hacky...
  42     glyph = (FT_OutlineGlyph) ass_font_get_glyph(fontconfig_priv, font,
  43                                                  (uint32_t) ' ', 0, 0);
  44     if (glyph) {
  45         FT_Outline_Done(drawing->ftlibrary, &glyph->outline);
  46         FT_Outline_New(drawing->ftlibrary, GLYPH_INITIAL_POINTS,
  47                        GLYPH_INITIAL_CONTOURS, &glyph->outline);
  48
  49         glyph->outline.n_contours = 0;
  50         glyph->outline.n_points = 0;
  51         glyph->root.advance.x = glyph->root.advance.y = 0;
  52     }
  53     drawing->glyph = glyph;
  54 }
  55
  56 /*
  57  * \brief Add a single point to a contour.
  58  */
  59 static inline void drawing_add_point(ASS_Drawing *drawing,
  60                                      FT_Vector *point)
  61 {
  62     FT_Outline *ol = &drawing->glyph->outline;
  63
  64     if (ol->n_points >= drawing->max_points) {
  65         drawing->max_points *= 2;
  66         ol->points = realloc(ol->points, sizeof(FT_Vector) *
  67                              drawing->max_points);
  68         ol->tags = realloc(ol->tags, drawing->max_points);
  69     }
  70
  71     ol->points[ol->n_points].x = point->x;
  72     ol->points[ol->n_points].y = point->y;
  73     ol->tags[ol->n_points] = 1;
  74     ol->n_points++;
  75 }
  76
  77 /*
  78  * \brief Close a contour and check glyph size overflow.
  79  */
  80 static inline void drawing_close_shape(ASS_Drawing *drawing)
  81 {
  82     FT_Outline *ol = &drawing->glyph->outline;
  83
  84     if (ol->n_contours >= drawing->max_contours) {
  85         drawing->max_contours *= 2;
  86         ol->contours = realloc(ol->contours, sizeof(short) *
  87                                drawing->max_contours);
  88     }
  89
  90     if (ol->n_points) {
  91         ol->contours[ol->n_contours] = ol->n_points - 1;
  92         ol->n_contours++;
  93     }
  94 }
  95
  96 /*
  97  * \brief Prepare drawing for parsing.  This just sets a few parameters.
  98  */
  99 static void drawing_prepare(ASS_Drawing *drawing)
 100 {
 101     // Scaling parameters
 102     drawing->point_scale_x = drawing->scale_x *
 103                              64.0 / (1 << (drawing->scale - 1));
 104     drawing->point_scale_y = drawing->scale_y *
 105                              64.0 / (1 << (drawing->scale - 1));
 106 }
 107
 108 /*
 109  * \brief Finish a drawing.  This only sets the horizontal advance according
 110  * to the glyph's bbox at the moment.
 111  */
 112 static void drawing_finish(ASS_Drawing *drawing, int raw_mode)
 113 {
 114     int i, offset;
 115     FT_BBox bbox = drawing->cbox;
 116     FT_Outline *ol = &drawing->glyph->outline;
 117
 118     // Close the last contour
 119     drawing_close_shape(drawing);
 120
 121     if (drawing->library)
 122         ass_msg(drawing->library, MSGL_V,
 123                 "Parsed drawing with %d points and %d contours", ol->n_points,
 124                 ol->n_contours);
 125
 126     if (raw_mode)
 127         return;
 128
 129     drawing->glyph->root.advance.x = d6_to_d16(bbox.xMax - bbox.xMin);
 130
 131     drawing->desc = double_to_d6(-drawing->pbo * drawing->scale_y);
 132     drawing->asc = bbox.yMax - bbox.yMin + drawing->desc;
 133
 134     // Place it onto the baseline
 135     offset = (bbox.yMax - bbox.yMin) + double_to_d6(-drawing->pbo *
 136                                                     drawing->scale_y);
 137     for (i = 0; i < ol->n_points; i++)
 138         ol->points[i].y += offset;
 139 }
 140
 141 /*
 142  * \brief Check whether a number of items on the list is available
 143  */
 144 static int token_check_values(ASS_DrawingToken *token, int i, int type)
 145 {
 146     int j;
 147     for (j = 0; j < i; j++) {
 148         if (!token || token->type != type) return 0;
 149         token = token->next;
 150     }
 151
 152     return 1;
 153 }
 154
 155 /*
 156  * \brief Tokenize a drawing string into a list of ASS_DrawingToken
 157  * This also expands points for closing b-splines
 158  */
 159 static ASS_DrawingToken *drawing_tokenize(char *str)
 160 {
 161     char *p = str;
 162     int i, val, type = -1, is_set = 0;
 163     FT_Vector point = {0, 0};
 164
 165     ASS_DrawingToken *root = NULL, *tail = NULL, *spline_start = NULL;
 166
 167     while (*p) {
 168         if (*p == 'c' && spline_start) {
 169             // Close b-splines: add the first three points of the b-spline
 170             // back to the end
 171             if (token_check_values(spline_start->next, 2, TOKEN_B_SPLINE)) {
 172                 for (i = 0; i < 3; i++) {
 173                     tail->next = calloc(1, sizeof(ASS_DrawingToken));
 174                     tail->next->prev = tail;
 175                     tail = tail->next;
 176                     tail->type = TOKEN_B_SPLINE;
 177                     tail->point = spline_start->point;
 178                     spline_start = spline_start->next;
 179                 }
 180                 spline_start = NULL;
 181             }
 182         } else if (!is_set && mystrtoi(&p, &val)) {
 183             point.x = val;
 184             is_set = 1;
 185             p--;
 186         } else if (is_set == 1 && mystrtoi(&p, &val)) {
 187             point.y = val;
 188             is_set = 2;
 189             p--;
 190         } else if (*p == 'm')
 191             type = TOKEN_MOVE;
 192         else if (*p == 'n')
 193             type = TOKEN_MOVE_NC;
 194         else if (*p == 'l')
 195             type = TOKEN_LINE;
 196         else if (*p == 'b')
 197             type = TOKEN_CUBIC_BEZIER;
 198         else if (*p == 'q')
 199             type = TOKEN_CONIC_BEZIER;
 200         else if (*p == 's')
 201             type = TOKEN_B_SPLINE;
 202         // We're simply ignoring TOKEN_EXTEND_B_SPLINE here.
 203         // This is not harmful at all, since it can be ommitted with
 204         // similar result (the spline is extended anyway).
 205
 206         if (type != -1 && is_set == 2) {
 207             if (root) {
 208                 tail->next = calloc(1, sizeof(ASS_DrawingToken));
 209                 tail->next->prev = tail;
 210                 tail = tail->next;
 211             } else
 212                 root = tail = calloc(1, sizeof(ASS_DrawingToken));
 213             tail->type = type;
 214             tail->point = point;
 215             is_set = 0;
 216             if (type == TOKEN_B_SPLINE && !spline_start)
 217                 spline_start = tail->prev;
 218         }
 219         p++;
 220     }
 221
 222     return root;
 223 }
 224
 225 /*
 226  * \brief Free a list of tokens
 227  */
 228 static void drawing_free_tokens(ASS_DrawingToken *token)
 229 {
 230     while (token) {
 231         ASS_DrawingToken *at = token;
 232         token = token->next;
 233         free(at);
 234     }
 235 }
 236
 237 /*
 238  * \brief Update drawing cbox
 239  */
 240 static inline void update_cbox(ASS_Drawing *drawing, FT_Vector *point)
 241 {
 242     FT_BBox *box = &drawing->cbox;
 243
 244     box->xMin = FFMIN(box->xMin, point->x);
 245     box->xMax = FFMAX(box->xMax, point->x);
 246     box->yMin = FFMIN(box->yMin, point->y);
 247     box->yMax = FFMAX(box->yMax, point->y);
 248 }
 249
 250 /*
 251  * \brief Translate and scale a point coordinate according to baseline
 252  * offset and scale.
 253  */
 254 static inline void translate_point(ASS_Drawing *drawing, FT_Vector *point)
 255 {
 256     point->x = drawing->point_scale_x * point->x;
 257     point->y = drawing->point_scale_y * -point->y;
 258
 259     update_cbox(drawing, point);
 260 }
 261
 262 /*
 263  * \brief Evaluate a curve into lines
 264  * This curve evaluator is also used in VSFilter (RTS.cpp); it's a simple
 265  * implementation of the De Casteljau algorithm.
 266  */
 267 static void drawing_evaluate_curve(ASS_Drawing *drawing,
 268                                    ASS_DrawingToken *token, char spline,
 269                                    int started)
 270 {
 271     double cx3, cx2, cx1, cx0, cy3, cy2, cy1, cy0;
 272     double t, h, max_accel, max_accel1, max_accel2;
 273     FT_Vector cur = {0, 0};
 274
 275     cur = token->point;
 276     translate_point(drawing, &cur);
 277     int x0 = cur.x;
 278     int y0 = cur.y;
 279     token = token->next;
 280     cur = token->point;
 281     translate_point(drawing, &cur);
 282     int x1 = cur.x;
 283     int y1 = cur.y;
 284     token = token->next;
 285     cur = token->point;
 286     translate_point(drawing, &cur);
 287     int x2 = cur.x;
 288     int y2 = cur.y;
 289     token = token->next;
 290     cur = token->point;
 291     translate_point(drawing, &cur);
 292     int x3 = cur.x;
 293     int y3 = cur.y;
 294
 295     if (spline) {
 296         // 1   [-1 +3 -3 +1]
 297         // - * [+3 -6 +3  0]
 298         // 6   [-3  0 +3  0]
 299         //         [+1 +4 +1  0]
 300
 301         double div6 = 1.0/6.0;
 302
 303         cx3 = div6*(-  x0+3*x1-3*x2+x3);
 304         cx2 = div6*( 3*x0-6*x1+3*x2);
 305         cx1 = div6*(-3*x0          +3*x2);
 306         cx0 = div6*(   x0+4*x1+1*x2);
 307
 308         cy3 = div6*(-  y0+3*y1-3*y2+y3);
 309         cy2 = div6*( 3*y0-6*y1+3*y2);
 310         cy1 = div6*(-3*y0     +3*y2);
 311         cy0 = div6*(   y0+4*y1+1*y2);
 312     } else {
 313         // [-1 +3 -3 +1]
 314         // [+3 -6 +3  0]
 315         // [-3 +3  0  0]
 316         // [+1  0  0  0]
 317
 318         cx3 = -  x0+3*x1-3*x2+x3;
 319         cx2 =  3*x0-6*x1+3*x2;
 320         cx1 = -3*x0+3*x1;
 321         cx0 =    x0;
 322
 323         cy3 = -  y0+3*y1-3*y2+y3;
 324         cy2 =  3*y0-6*y1+3*y2;
 325         cy1 = -3*y0+3*y1;
 326         cy0 =    y0;
 327     }
 328
 329     max_accel1 = fabs(2 * cy2) + fabs(6 * cy3);
 330     max_accel2 = fabs(2 * cx2) + fabs(6 * cx3);
 331
 332     max_accel = FFMAX(max_accel1, max_accel2);
 333     h = 1.0;
 334
 335     if (max_accel > CURVE_ACCURACY)
 336         h = sqrt(CURVE_ACCURACY / max_accel);
 337
 338     if (!started) {
 339         cur.x = cx0;
 340         cur.y = cy0;
 341         drawing_add_point(drawing, &cur);
 342     }
 343
 344     for (t = 0; t < 1.0; t += h) {
 345         cur.x = cx0 + t * (cx1 + t * (cx2 + t * cx3));
 346         cur.y = cy0 + t * (cy1 + t * (cy2 + t * cy3));
 347         drawing_add_point(drawing, &cur);
 348     }
 349
 350     cur.x = cx0 + cx1 + cx2 + cx3;
 351     cur.y = cy0 + cy1 + cy2 + cy3;
 352     drawing_add_point(drawing, &cur);
 353 }
 354
 355 /*
 356  * \brief Create and initialize a new drawing and return it
 357  */
 358 ASS_Drawing *ass_drawing_new(void *fontconfig_priv, ASS_Font *font,
 359                              FT_Library lib)
 360 {
 361     ASS_Drawing *drawing;
 362
 363     drawing = calloc(1, sizeof(*drawing));
 364     drawing->text = calloc(1, DRAWING_INITIAL_SIZE);
 365     drawing->size = DRAWING_INITIAL_SIZE;
 366     drawing->cbox.xMin = drawing->cbox.yMin = INT_MAX;
 367     drawing->cbox.xMax = drawing->cbox.yMax = INT_MIN;
 368     drawing->fontconfig_priv = fontconfig_priv;
 369     drawing->font = font;
 370     drawing->ftlibrary = lib;
 371     if (font)
 372         drawing->library = font->library;
 373
 374     drawing->scale_x = 1.;
 375     drawing->scale_y = 1.;
 376     drawing->max_contours = GLYPH_INITIAL_CONTOURS;
 377     drawing->max_points = GLYPH_INITIAL_POINTS;
 378
 379     return drawing;
 380 }
 381
 382 /*
 383  * \brief Free a drawing
 384  */
 385 void ass_drawing_free(ASS_Drawing* drawing)
 386 {
 387     if (drawing) {
 388         free(drawing->text);
 389     }
 390     free(drawing);
 391 }
 392
 393 /*
 394  * \brief Add one ASCII character to the drawing text buffer
 395  */
 396 void ass_drawing_add_char(ASS_Drawing* drawing, char symbol)
 397 {
 398     drawing->text[drawing->i++] = symbol;
 399     drawing->text[drawing->i] = 0;
 400
 401     if (drawing->i + 1 >= drawing->size) {
 402         drawing->size *= 2;
 403         drawing->text = realloc(drawing->text, drawing->size);
 404     }
 405 }
 406
 407 /*
 408  * \brief Create a hashcode for the drawing
 409  * XXX: To avoid collisions a better hash algorithm might be useful.
 410  */
 411 void ass_drawing_hash(ASS_Drawing* drawing)
 412 {
 413     drawing->hash = fnv_32a_str(drawing->text, FNV1_32A_INIT);
 414 }
 415
 416 /*
 417  * \brief Convert token list to outline.  Calls the line and curve evaluators.
 418  */
 419 FT_OutlineGlyph *ass_drawing_parse(ASS_Drawing *drawing, int raw_mode)
 420 {
 421     int started = 0;
 422     ASS_DrawingToken *token;
 423     FT_Vector pen = {0, 0};
 424
 425     if (drawing->font)
 426         drawing_make_glyph(drawing, drawing->fontconfig_priv, drawing->font);
 427     if (!drawing->glyph)
 428         return NULL;
 429
 430     drawing->tokens = drawing_tokenize(drawing->text);
 431     drawing_prepare(drawing);
 432
 433     token = drawing->tokens;
 434     while (token) {
 435         // Draw something according to current command
 436         switch (token->type) {
 437         case TOKEN_MOVE_NC:
 438             pen = token->point;
 439             translate_point(drawing, &pen);
 440             token = token->next;
 441             break;
 442         case TOKEN_MOVE:
 443             pen = token->point;
 444             translate_point(drawing, &pen);
 445             if (started) {
 446                 drawing_close_shape(drawing);
 447                 started = 0;
 448             }
 449             token = token->next;
 450             break;
 451         case TOKEN_LINE: {
 452             FT_Vector to;
 453             to = token->point;
 454             translate_point(drawing, &to);
 455             if (!started) drawing_add_point(drawing, &pen);
 456             drawing_add_point(drawing, &to);
 457             started = 1;
 458             token = token->next;
 459             break;
 460         }
 461         case TOKEN_CUBIC_BEZIER:
 462             if (token_check_values(token, 3, TOKEN_CUBIC_BEZIER) &&
 463                 token->prev) {
 464                 drawing_evaluate_curve(drawing, token->prev, 0, started);
 465                 token = token->next;
 466                 token = token->next;
 467                 token = token->next;
 468                 started = 1;
 469             } else
 470                 token = token->next;
 471             break;
 472         case TOKEN_B_SPLINE:
 473             if (token_check_values(token, 3, TOKEN_B_SPLINE) &&
 474                 token->prev) {
 475                 drawing_evaluate_curve(drawing, token->prev, 1, started);
 476                 token = token->next;
 477                 started = 1;
 478             } else
 479                 token = token->next;
 480             break;
 481         default:
 482             token = token->next;
 483             break;
 484         }
 485     }
 486
 487     drawing_finish(drawing, raw_mode);
 488     drawing_free_tokens(drawing->tokens);
 489     return &drawing->glyph;
 490 }