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