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