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

   1 /*
   2  * Copyright (C) 2016 Vabishchevich Nikolay <vabnick@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 #include "ass_compat.h"
  21
  22 #include "ass_utils.h"
  23 #include "ass_outline.h"
  24
  25
  26
  27 bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_contours)
  28 {
  29     outline->contours = malloc(sizeof(size_t) * n_contours);
  30     outline->points = malloc(sizeof(ASS_Vector) * n_points);
  31     outline->tags = malloc(n_points);
  32     if (!outline->contours || !outline->points || !outline->tags) {
  33         outline_free(outline);
  34         return false;
  35     }
  36
  37     outline->max_contours = n_contours;
  38     outline->max_points = n_points;
  39     return true;
  40 }
  41
  42 static void outline_clear(ASS_Outline *outline)
  43 {
  44     outline->contours = NULL;
  45     outline->points = NULL;
  46     outline->tags = NULL;
  47
  48     outline->n_contours = outline->max_contours = 0;
  49     outline->n_points = outline->max_points = 0;
  50 }
  51
  52 bool outline_convert(ASS_Outline *outline, const FT_Outline *source)
  53 {
  54     if (!source || !source->n_points) {
  55         outline_clear(outline);
  56         return true;
  57     }
  58
  59     if (!outline_alloc(outline, source->n_points, source->n_contours))
  60         return false;
  61
  62     short start = 0;
  63     outline->n_contours = outline->n_points = 0;
  64     for (int i = 0; i < source->n_contours; i++) {
  65         size_t n = source->contours[i] - start + 1;
  66         // skip degenerate 2-point contours from broken fonts
  67         if (n >= 3) {
  68             for (size_t k = 0; k < n; k++) {
  69                 outline->points[outline->n_points + k].x = source->points[start + k].x;
  70                 outline->points[outline->n_points + k].y = source->points[start + k].y;
  71             }
  72             memcpy(outline->tags + outline->n_points, source->tags + start, n);
  73
  74             outline->n_points += n;
  75             outline->contours[outline->n_contours++] = outline->n_points - 1;
  76         }
  77         start = source->contours[i] + 1;
  78     }
  79     return true;
  80 }
  81
  82 bool outline_copy(ASS_Outline *outline, const ASS_Outline *source)
  83 {
  84     if (!source || !source->n_points) {
  85         outline_clear(outline);
  86         return true;
  87     }
  88
  89     if (!outline_alloc(outline, source->n_points, source->n_contours))
  90         return false;
  91
  92     memcpy(outline->contours, source->contours, sizeof(size_t) * source->n_contours);
  93     memcpy(outline->points, source->points, sizeof(ASS_Vector) * source->n_points);
  94     memcpy(outline->tags, source->tags, source->n_points);
  95     outline->n_contours = source->n_contours;
  96     outline->n_points = source->n_points;
  97     return true;
  98 }
  99
 100 void outline_free(ASS_Outline *outline)
 101 {
 102     if (!outline)
 103         return;
 104
 105     free(outline->contours);
 106     free(outline->points);
 107     free(outline->tags);
 108
 109     outline_clear(outline);
 110 }
 111
 112
 113 /*
 114  * \brief Add a single point to a contour.
 115  */
 116 bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char tag)
 117 {
 118     if (outline->n_points >= outline->max_points) {
 119         size_t new_size = 2 * outline->max_points;
 120         if (!ASS_REALLOC_ARRAY(outline->points, new_size))
 121             return false;
 122         if (!ASS_REALLOC_ARRAY(outline->tags, new_size))
 123             return false;
 124         outline->max_points = new_size;
 125     }
 126     outline->points[outline->n_points] = pt;
 127     outline->tags[outline->n_points] = tag;
 128     outline->n_points++;
 129     return true;
 130 }
 131
 132 /*
 133  * \brief Close a contour.
 134  */
 135 bool outline_close_contour(ASS_Outline *outline)
 136 {
 137     if (outline->n_contours >= outline->max_contours) {
 138         size_t new_size = 2 * outline->max_contours;
 139         if (!ASS_REALLOC_ARRAY(outline->contours, new_size))
 140             return false;
 141         outline->max_contours = new_size;
 142     }
 143     outline->contours[outline->n_contours] = outline->n_points - 1;
 144     outline->n_contours++;
 145     return true;
 146 }
 147
 148
 149 void outline_translate(const ASS_Outline *outline, int32_t dx, int32_t dy)
 150 {
 151     for (size_t i = 0; i < outline->n_points; i++) {
 152         outline->points[i].x += dx;
 153         outline->points[i].y += dy;
 154     }
 155 }
 156
 157 void outline_transform(const ASS_Outline *outline, const FT_Matrix *matrix)
 158 {
 159     for (size_t i = 0; i < outline->n_points; i++) {
 160         int32_t x = FT_MulFix(outline->points[i].x, matrix->xx) +
 161                     FT_MulFix(outline->points[i].y, matrix->xy);
 162         int32_t y = FT_MulFix(outline->points[i].x, matrix->yx) +
 163                     FT_MulFix(outline->points[i].y, matrix->yy);
 164         outline->points[i].x = x;
 165         outline->points[i].y = y;
 166     }
 167 }
 168
 169 void outline_get_cbox(const ASS_Outline *outline, ASS_Rect *cbox)
 170 {
 171     if (!outline->n_points) {
 172         cbox->x_min = cbox->x_max = 0;
 173         cbox->y_min = cbox->y_max = 0;
 174         return;
 175     }
 176     cbox->x_min = cbox->x_max = outline->points[0].x;
 177     cbox->y_min = cbox->y_max = outline->points[0].y;
 178     for (size_t i = 1; i < outline->n_points; i++) {
 179         cbox->x_min = FFMIN(cbox->x_min, outline->points[i].x);
 180         cbox->x_max = FFMAX(cbox->x_max, outline->points[i].x);
 181         cbox->y_min = FFMIN(cbox->y_min, outline->points[i].y);
 182         cbox->y_max = FFMAX(cbox->y_max, outline->points[i].y);
 183     }
 184 }
 185
 186
 187 /*
 188  * Outline Stroke Algorithm
 189  *
 190  * Goal:
 191  * Given source outline, construct two border outlines, such as that
 192  * for any point inside any border outline (nonzero winding rule)
 193  * minimal distance to points of source outline (same rule)
 194  * is less than 1 with given precision, and for any point outside
 195  * both border outlines minimal distance is more than approximately 1.
 196  * Distance here is defined in normal space that is scaled by [1 / xbord, 1 / ybord].
 197  * Correspondingly distance is equal to hypot(dx / xbord, dy / ybord) and
 198  * approximate allowable error is eps / max(xbord, ybord).
 199  *
 200  * Two border outlines correspond to ±1 offset curves and
 201  * are required in case of self-intersecting source outline.
 202  *
 203  * Each of source segment that can be line segment, quadratic or cubic spline,
 204  * and also connection between them is stroked mostly independently.
 205  * Line segments can be offset quite straightforwardly.
 206  * For splines algorithm first tries to offset individual points,
 207  * then estimates error of such approximation and subdivide recursively if necessary.
 208  *
 209  * List of border cases handled by this algorithm:
 210  * 1) Too close points lead to random derivatives or even division by zero.
 211  *    Algorithm solves that by merging such points into one.
 212  * 2) Degenerate cases--near zero derivative at some spline points.
 213  *    Algorithm adds circular cap in such cases.
 214  * 3) Negative curvature--offset amount is larger than radius of curvature.
 215  *    Algorithm checks if produced splines can potentially have self-intersection
 216  *    and handles them accordingly. It's mostly done by skipping
 217  *    problematic spline and replacing it with polyline that covers only
 218  *    positive winging part of mathematical offset curve.
 219  *
 220  * Error estimation for splines is done by analyzing offset spline.
 221  * Offset spline is the difference between result and source spline in normal space.
 222  * Such spline should consist of vectors with length 1 and orthogonal to source spline.
 223  * Correspondingly error estimator have radial and angular part.
 224  *
 225  * Useful facts about B-splines.
 226  * 1) Derivative of B-spline of order N is B-spline of order N-1.
 227  * 2) Multiplication of B-splines of order N and M is B-spline of order N+M.
 228  * 3) B-spline is fully contained inside convex hull of its control points.
 229  *
 230  * So, for radial error it's possible to check only control points of
 231  * offset spline multiplication by itself. And for angular error it's
 232  * possible to check control points of cross and dot product between
 233  * offset spline and derivative spline.
 234  */
 235
 236
 237 typedef struct {
 238     ASS_DVector v;
 239     double len;
 240 } Normal;
 241
 242 typedef struct {
 243     ASS_Outline *result[2];   // result outlines
 244     double xbord, ybord;      // border sizes
 245     double xscale, yscale;    // inverse border sizes
 246     int eps;                  // allowable error in coordinate space
 247
 248     // true if where are points in current contour
 249     bool contour_start;
 250     // skip flags for first and last point
 251     int first_skip, last_skip;
 252     // normal at first and last point
 253     ASS_DVector first_normal, last_normal;
 254     // first and last point of current contour
 255     ASS_Vector first_point, last_point;
 256
 257     // cosinus of maximal angle that do not require cap
 258     double merge_cos;
 259     // cosinus of maximal angle of circular arc that can be approximated with quadratic spline
 260     double split_cos;
 261     // maximal distance between control points in normal space that triggers handling of degenerates
 262     double min_len;
 263     // constant that used in exact radial error checking in quadratic case
 264     double err_q;
 265     // constant that used in approximate radial error checking in cubic case
 266     double err_c;
 267     // tangent of maximal angular error
 268     double err_a;
 269 } StrokerState;
 270
 271 /**
 272  * \brief 2D vector dot product
 273  */
 274 static inline double vec_dot(ASS_DVector vec1, ASS_DVector vec2)
 275 {
 276     return vec1.x * vec2.x + vec1.y * vec2.y;
 277 }
 278
 279 /**
 280  * \brief 2D vector cross product
 281  */
 282 static inline double vec_crs(ASS_DVector vec1, ASS_DVector vec2)
 283 {
 284     return vec1.x * vec2.y - vec1.y * vec2.x;
 285 }
 286
 287 /**
 288  * \brief 2D vector length
 289  */
 290 static inline double vec_len(ASS_DVector vec)
 291 {
 292     return sqrt(vec.x * vec.x + vec.y * vec.y);
 293 }
 294
 295
 296 /**
 297  * \brief Add point to one or two border outlines
 298  * \param str stroker state
 299  * \param pt source point
 300  * \param offs offset in normal space
 301  * \param tag outline tag flag
 302  * \param dir destination outline flags
 303  * \return false on allocation failure
 304  */
 305 static bool emit_point(StrokerState *str, ASS_Vector pt,
 306                        ASS_DVector offs, char tag, int dir)
 307 {
 308     int32_t dx = (int32_t) (str->xbord * offs.x);
 309     int32_t dy = (int32_t) (str->ybord * offs.y);
 310
 311     if (dir & 1) {
 312         ASS_Vector res = { pt.x + dx, pt.y + dy };
 313         res.y = -res.y;
 314         if (!outline_add_point(str->result[0], res, tag))
 315             return false;
 316     }
 317     if (dir & 2) {
 318         ASS_Vector res = { pt.x - dx, pt.y - dy };
 319         res.y = -res.y;
 320         if (!outline_add_point(str->result[1], res, tag))
 321             return false;
 322     }
 323     return true;
 324 }
 325
 326 /**
 327  * \brief Replace first point of current contour
 328  * \param str stroker state
 329  * \param pt source point
 330  * \param offs offset in normal space
 331  * \param dir destination outline flags
 332  */
 333 static void fix_first_point(StrokerState *str, ASS_Vector pt,
 334                             ASS_DVector offs, int dir)
 335 {
 336     int32_t dx = (int32_t) (str->xbord * offs.x);
 337     int32_t dy = (int32_t) (str->ybord * offs.y);
 338
 339     if (dir & 1) {
 340         ASS_Vector res = { pt.x + dx, pt.y + dy };
 341         res.y = -res.y;
 342         ASS_Outline *ol = str->result[0];
 343         size_t first = ol->n_contours ?
 344             ol->contours[ol->n_contours - 1] + 1 : 0;
 345         ol->points[first] = res;
 346     }
 347     if (dir & 2) {
 348         ASS_Vector res = { pt.x - dx, pt.y - dy };
 349         res.y = -res.y;
 350         ASS_Outline *ol = str->result[1];
 351         size_t first = ol->n_contours ?
 352             ol->contours[ol->n_contours - 1] + 1 : 0;
 353         ol->points[first] = res;
 354     }
 355 }
 356
 357 /**
 358  * \brief Helper function for circular arc construction
 359  * \param str stroker state
 360  * \param pt center point
 361  * \param normal0 first normal
 362  * \param normal1 last normal
 363  * \param mul precalculated coefficients
 364  * \param level subdivision level
 365  * \param dir destination outline flags
 366  * \return false on allocation failure
 367  */
 368 static bool process_arc(StrokerState *str, ASS_Vector pt,
 369                         ASS_DVector normal0, ASS_DVector normal1,
 370                         const double *mul, int level, int dir)
 371 {
 372     ASS_DVector center;
 373     center.x = (normal0.x + normal1.x) * mul[level];
 374     center.y = (normal0.y + normal1.y) * mul[level];
 375     if (level)
 376         return process_arc(str, pt, normal0, center, mul, level - 1, dir) &&
 377                process_arc(str, pt, center, normal1, mul, level - 1, dir);
 378     return emit_point(str, pt, normal0, FT_CURVE_TAG_ON, dir) &&
 379            emit_point(str, pt, center, FT_CURVE_TAG_CONIC, dir);
 380 }
 381
 382 /**
 383  * \brief Construct circular arc
 384  * \param str stroker state
 385  * \param pt center point
 386  * \param normal0 first normal
 387  * \param normal1 last normal
 388  * \param c dot product between normal0 and normal1
 389  * \param dir destination outline flags
 390  * \return false on allocation failure
 391  */
 392 static bool draw_arc(StrokerState *str, ASS_Vector pt,
 393                      ASS_DVector normal0, ASS_DVector normal1, double c, int dir)
 394 {
 395     const int max_subdiv = 15;
 396     double mul[max_subdiv + 1];
 397
 398     ASS_DVector center;
 399     bool small_angle = true;
 400     if (c < 0) {
 401         double mul = dir & 2 ? -sqrt(0.5) : sqrt(0.5);
 402         mul /= sqrt(1 - c);
 403         center.x = (normal1.y - normal0.y) * mul;
 404         center.y = (normal0.x - normal1.x) * mul;
 405         c = sqrt(FFMAX(0, 0.5 + 0.5 * c));
 406         small_angle = false;
 407     }
 408
 409     int pos = max_subdiv;
 410     while (c < str->split_cos && pos) {
 411         mul[pos] = sqrt(0.5) / sqrt(1 + c);
 412         c = (1 + c) * mul[pos];
 413         pos--;
 414     }
 415     mul[pos] = 1 / (1 + c);
 416     return small_angle ?
 417         process_arc(str, pt, normal0, normal1, mul + pos, max_subdiv - pos, dir) :
 418         process_arc(str, pt, normal0, center,  mul + pos, max_subdiv - pos, dir) &&
 419         process_arc(str, pt, center,  normal1, mul + pos, max_subdiv - pos, dir);
 420 }
 421
 422 /**
 423  * \brief Construct full circle
 424  * \param str stroker state
 425  * \param pt center point
 426  * \param dir destination outline flags
 427  * \return false on allocation failure
 428  */
 429 static bool draw_circle(StrokerState *str, ASS_Vector pt, int dir)
 430 {
 431     const int max_subdiv = 15;
 432     double mul[max_subdiv + 1], c = 0;
 433
 434     int pos = max_subdiv;
 435     while (c < str->split_cos && pos) {
 436         mul[pos] = sqrt(0.5) / sqrt(1 + c);
 437         c = (1 + c) * mul[pos];
 438         pos--;
 439     }
 440     mul[pos] = 1 / (1 + c);
 441
 442     ASS_DVector normal[4] = {
 443         { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }
 444     };
 445     return process_arc(str, pt, normal[0], normal[1], mul + pos, max_subdiv - pos, dir) &&
 446            process_arc(str, pt, normal[1], normal[2], mul + pos, max_subdiv - pos, dir) &&
 447            process_arc(str, pt, normal[2], normal[3], mul + pos, max_subdiv - pos, dir) &&
 448            process_arc(str, pt, normal[3], normal[0], mul + pos, max_subdiv - pos, dir);
 449 }
 450
 451 /**
 452  * \brief Start new segment and add circular cap if necessary
 453  * \param str stroker state
 454  * \param pt start point of the new segment
 455  * \param normal normal at start of the new segment
 456  * \param dir destination outline flags
 457  * \return false on allocation failure
 458  */
 459 static bool start_segment(StrokerState *str, ASS_Vector pt,
 460                           ASS_DVector normal, int dir)
 461 {
 462     if (str->contour_start) {
 463         str->contour_start = false;
 464         str->first_skip = str->last_skip = 0;
 465         str->first_normal = str->last_normal = normal;
 466         str->first_point = pt;
 467         return true;
 468     }
 469
 470     ASS_DVector prev = str->last_normal;
 471     double c = vec_dot(prev, normal);
 472     if (c > str->merge_cos) {  // merge without cap
 473         double mul = 1 / (1 + c);
 474         str->last_normal.x = (str->last_normal.x + normal.x) * mul;
 475         str->last_normal.y = (str->last_normal.y + normal.y) * mul;
 476         return true;
 477     }
 478     str->last_normal = normal;
 479
 480     // check for negative curvature
 481     double s = vec_crs(prev, normal);
 482     int skip_dir = s < 0 ? 1 : 2;
 483     if (dir & skip_dir) {
 484         if (!emit_point(str, pt, prev, FT_CURVE_TAG_ON, ~str->last_skip & skip_dir))
 485             return false;
 486         ASS_DVector zero_normal = {0, 0};
 487         if (!emit_point(str, pt, zero_normal, FT_CURVE_TAG_ON, skip_dir))
 488             return false;
 489     }
 490     str->last_skip = skip_dir;
 491
 492     dir &= ~skip_dir;
 493     return !dir || draw_arc(str, pt, prev, normal, c, dir);
 494 }
 495
 496 /**
 497  * \brief Same as emit_point() but also updates skip flags
 498  */
 499 static bool emit_first_point(StrokerState *str, ASS_Vector pt, int dir)
 500 {
 501     str->last_skip &= ~dir;
 502     return emit_point(str, pt, str->last_normal, FT_CURVE_TAG_ON, dir);
 503 }
 504
 505 /**
 506  * \brief Prepare to skip part of curve
 507  * \param str stroker state
 508  * \param pt start point of the skipped part
 509  * \param dir destination outline flags
 510  * \param first true if the skipped part is at start of the segment
 511  * \return false on allocation failure
 512  */
 513 static bool prepare_skip(StrokerState *str, ASS_Vector pt, int dir, bool first)
 514 {
 515     if (first)
 516         str->first_skip |= dir;
 517     else if (!emit_point(str, pt, str->last_normal, FT_CURVE_TAG_ON, ~str->last_skip & dir))
 518         return false;
 519     str->last_skip |= dir;
 520     return true;
 521 }
 522
 523 /**
 524  * \brief Process source line segment
 525  * \param str stroker state
 526  * \param pt end point of the line segment
 527  * \param dir destination outline flags
 528  * \return false on allocation failure
 529  */
 530 static bool add_line(StrokerState *str, ASS_Vector pt, int dir)
 531 {
 532     int32_t dx = pt.x - str->last_point.x;
 533     int32_t dy = pt.y - str->last_point.y;
 534     if (dx > -str->eps && dx < str->eps && dy > -str->eps && dy < str->eps)
 535         return true;
 536
 537     ASS_DVector deriv = { dy * str->yscale, -dx * str->xscale };
 538     double scale = 1 / vec_len(deriv);
 539     ASS_DVector normal = { deriv.x * scale, deriv.y * scale };
 540     if (!start_segment(str, str->last_point, normal, dir))
 541         return false;
 542     if (!emit_first_point(str, str->last_point, dir))
 543         return false;
 544     str->last_normal = normal;
 545     str->last_point = pt;
 546     return true;
 547 }
 548
 549
 550 /**
 551  * \brief Estimate error for quadratic spline
 552  * \param str stroker state
 553  * \param c dot product between normal[0] and normal[1]
 554  * \param s cross product between normal[0] and normal[1]
 555  * \param normal first and last spline normal
 556  * \param result best offset for central spline point
 557  * \return false if error is too large
 558  */
 559 static bool estimate_quadratic_error(StrokerState *str, double c, double s,
 560                                      const Normal *normal, ASS_DVector *result)
 561 {
 562     // check radial error
 563     if (!((3 + c) * (3 + c) < str->err_q * (1 + c)))
 564         return false;
 565
 566     double mul = 1 / (1 + c);
 567     double l0 = 2 * normal[0].len, l1 = 2 * normal[1].len;
 568     double dot0 = l0 + normal[1].len * c, crs0 = (l0 * mul - normal[1].len) * s;
 569     double dot1 = l1 + normal[0].len * c, crs1 = (l1 * mul - normal[0].len) * s;
 570     // check angular error
 571     if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1))
 572         return false;
 573
 574     result->x = (normal[0].v.x + normal[1].v.x) * mul;
 575     result->y = (normal[0].v.y + normal[1].v.y) * mul;
 576     return true;
 577 }
 578
 579 /**
 580  * \brief Helper function for quadratic spline construction
 581  * \param str stroker state
 582  * \param pt array of 3 source spline points
 583  * \param deriv array of 2 differences between adjacent points in normal space
 584  * \param normal first and last spline normal
 585  * \param dir destination outline flags
 586  * \param first true if the current part is at start of the segment
 587  * \return false on allocation failure
 588  */
 589 static bool process_quadratic(StrokerState *str, const ASS_Vector *pt,
 590                               const ASS_DVector *deriv, const Normal *normal,
 591                               int dir, bool first)
 592 {
 593     double c = vec_dot(normal[0].v, normal[1].v);
 594     double s = vec_crs(normal[0].v, normal[1].v);
 595     int check_dir = dir, skip_dir = s < 0 ? 1 : 2;
 596     if (dir & skip_dir) {
 597         double abs_s = fabs(s);
 598         double f0 = normal[0].len * c + normal[1].len;
 599         double f1 = normal[1].len * c + normal[0].len;
 600         double g0 = normal[0].len * abs_s;
 601         double g1 = normal[1].len * abs_s;
 602         // check for self-intersection
 603         if (f0 < abs_s && f1 < abs_s) {
 604             double d2 = (f0 * normal[1].len + f1 * normal[0].len) / 2;
 605             if (d2 < g0 && d2 < g1) {
 606                 if (!prepare_skip(str, pt[0], skip_dir, first))
 607                     return false;
 608                 if (f0 < 0 || f1 < 0) {
 609                     ASS_DVector zero_normal = {0, 0};
 610                     if (!emit_point(str, pt[0], zero_normal, FT_CURVE_TAG_ON, skip_dir) ||
 611                         !emit_point(str, pt[2], zero_normal, FT_CURVE_TAG_ON, skip_dir))
 612                         return false;
 613                 } else {
 614                     double mul = f0 / abs_s;
 615                     ASS_DVector offs = { normal[0].v.x * mul, normal[0].v.y * mul };
 616                     if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir))
 617                         return false;
 618                 }
 619                 dir &= ~skip_dir;
 620                 if (!dir) {
 621                     str->last_normal = normal[1].v;
 622                     return true;
 623                 }
 624             }
 625             check_dir ^= skip_dir;
 626         } else if (c + g0 < 1 && c + g1 < 1)
 627             check_dir ^= skip_dir;
 628     }
 629
 630     ASS_DVector result;
 631     if (check_dir && estimate_quadratic_error(str, c, s, normal, &result)) {
 632         if (!emit_first_point(str, pt[0], check_dir))
 633             return false;
 634         if (!emit_point(str, pt[1], result, FT_CURVE_TAG_CONIC, check_dir))
 635             return false;
 636         dir &= ~check_dir;
 637         if (!dir) {
 638             str->last_normal = normal[1].v;
 639             return true;
 640         }
 641     }
 642
 643     ASS_Vector next[5];
 644     next[1].x = pt[0].x + pt[1].x;
 645     next[1].y = pt[0].y + pt[1].y;
 646     next[3].x = pt[1].x + pt[2].x;
 647     next[3].y = pt[1].y + pt[2].y;
 648     next[2].x = (next[1].x + next[3].x + 2) >> 2;
 649     next[2].y = (next[1].y + next[3].y + 2) >> 2;
 650     next[1].x >>= 1;
 651     next[1].y >>= 1;
 652     next[3].x >>= 1;
 653     next[3].y >>= 1;
 654     next[0] = pt[0];
 655     next[4] = pt[2];
 656
 657     ASS_DVector next_deriv[3];
 658     next_deriv[0].x = deriv[0].x / 2;
 659     next_deriv[0].y = deriv[0].y / 2;
 660     next_deriv[2].x = deriv[1].x / 2;
 661     next_deriv[2].y = deriv[1].y / 2;
 662     next_deriv[1].x = (next_deriv[0].x + next_deriv[2].x) / 2;
 663     next_deriv[1].y = (next_deriv[0].y + next_deriv[2].y) / 2;
 664
 665     double len = vec_len(next_deriv[1]);
 666     if (len < str->min_len) {  // check degenerate case
 667         if (!emit_first_point(str, next[0], dir))
 668             return false;
 669         if (!start_segment(str, next[2], normal[1].v, dir))
 670             return false;
 671         str->last_skip &= ~dir;
 672         return emit_point(str, next[2], normal[1].v, FT_CURVE_TAG_ON, dir);
 673     }
 674
 675     double scale = 1 / len;
 676     Normal next_normal[3] = {
 677         { normal[0].v, normal[0].len / 2 },
 678         { { next_deriv[1].x * scale, next_deriv[1].y * scale }, len },
 679         { normal[1].v, normal[1].len / 2 }
 680     };
 681     return process_quadratic(str, next + 0, next_deriv + 0, next_normal + 0, dir, first) &&
 682            process_quadratic(str, next + 2, next_deriv + 1, next_normal + 1, dir, false);
 683 }
 684
 685 /**
 686  * \brief Process source quadratic spline
 687  * \param str stroker state
 688  * \param pt array of 3 source spline points
 689  * \param dir destination outline flags
 690  * \return false on allocation failure
 691  */
 692 static bool add_quadratic(StrokerState *str, const ASS_Vector *pt, int dir)
 693 {
 694     int32_t dx0 = pt[1].x - pt[0].x;
 695     int32_t dy0 = pt[1].y - pt[0].y;
 696     if (dx0 > -str->eps && dx0 < str->eps && dy0 > -str->eps && dy0 < str->eps)
 697         return add_line(str, pt[2], dir);
 698
 699     int32_t dx1 = pt[2].x - pt[1].x;
 700     int32_t dy1 = pt[2].y - pt[1].y;
 701     if (dx1 > -str->eps && dx1 < str->eps && dy1 > -str->eps && dy1 < str->eps)
 702         return add_line(str, pt[2], dir);
 703
 704     ASS_DVector deriv[2] = {
 705         { dy0 * str->yscale, -dx0 * str->xscale },
 706         { dy1 * str->yscale, -dx1 * str->xscale }
 707     };
 708     double len0 = vec_len(deriv[0]), scale0 = 1 / len0;
 709     double len1 = vec_len(deriv[1]), scale1 = 1 / len1;
 710     Normal normal[2] = {
 711         { { deriv[0].x * scale0, deriv[0].y * scale0 }, len0 },
 712         { { deriv[1].x * scale1, deriv[1].y * scale1 }, len1 }
 713     };
 714
 715     bool first = str->contour_start;
 716     if (!start_segment(str, pt[0], normal[0].v, dir))
 717         return false;
 718     if (!process_quadratic(str, pt, deriv, normal, dir, first))
 719         return false;
 720     str->last_point = pt[2];
 721     return true;
 722 }
 723
 724
 725 enum {
 726     FLAG_INTERSECTION =  1,
 727     FLAG_ZERO_0       =  2,
 728     FLAG_ZERO_1       =  4,
 729     FLAG_CLIP_0       =  8,
 730     FLAG_CLIP_1       = 16,
 731     FLAG_DIR_2        = 32,
 732
 733     FLAG_COUNT        =  6,
 734
 735     MASK_INTERSECTION = FLAG_INTERSECTION << FLAG_COUNT,
 736     MASK_ZERO_0       = FLAG_ZERO_0       << FLAG_COUNT,
 737     MASK_ZERO_1       = FLAG_ZERO_1       << FLAG_COUNT,
 738     MASK_CLIP_0       = FLAG_CLIP_0       << FLAG_COUNT,
 739     MASK_CLIP_1       = FLAG_CLIP_1       << FLAG_COUNT,
 740 };
 741
 742 /**
 743  * \brief Estimate error for cubic spline
 744  * \param str stroker state
 745  * \param c dot product between normal[0] and normal[1]
 746  * \param s cross product between normal[0] and normal[1]
 747  * \param dc dot products between normals and central points difference in normal space
 748  * \param dc cross products between normals and central points difference in normal space
 749  * \param normal first and last spline normal
 750  * \param result best offsets for central spline points (second & third)
 751  * \return flags for destination outlines that do not require subdivision
 752  */
 753 static int estimate_cubic_error(StrokerState *str, double c, double s,
 754                                 const double *dc, const double *ds,
 755                                 const Normal *normal, ASS_DVector *result,
 756                                 int check_flags, int dir)
 757 {
 758     double t = (ds[0] + ds[1]) / (dc[0] + dc[1]), c1 = 1 + c, ss = s * s;
 759     double ts = t * s, tt = t * t, ttc = tt * c1, ttcc = ttc * c1;
 760
 761     const double w = 0.4;
 762     double f0[] = {
 763         10 * w * (c - 1) + 9 * w * tt * c,
 764         2 * (c - 1) + 3 * tt + 2 * ts,
 765         2 * (c - 1) + 3 * tt - 2 * ts,
 766     };
 767     double f1[] = {
 768         18 * w * (ss - ttc * c),
 769         2 * ss - 6 * ttc - 2 * ts * (c + 4),
 770         2 * ss - 6 * ttc + 2 * ts * (c + 4),
 771     };
 772     double f2[] = {
 773         9 * w * (ttcc - ss) * c,
 774         3 * ss + 3 * ttcc + 6 * ts * c1,
 775         3 * ss + 3 * ttcc - 6 * ts * c1,
 776     };
 777
 778     double aa = 0, ab = 0;
 779     double ch = sqrt(c1 / 2);
 780     double inv_ro0 = 1.5 * ch * (ch + 1);
 781     for (int i = 0; i < 3; i++) {
 782         double a = 2 * f2[i] + f1[i] * inv_ro0;
 783         double b = f2[i] - f0[i] * inv_ro0 * inv_ro0;
 784         aa += a * a;  ab += a * b;
 785     }
 786     double ro = ab / (aa * inv_ro0 + 1e-9);  // best fit
 787
 788     double err2 = 0;
 789     for (int i = 0; i < 3; i++) {
 790         double err = f0[i] + ro * (f1[i] + ro * f2[i]);
 791         err2 += err * err;
 792     }
 793     if (!(err2 < str->err_c))  // check radial error
 794         return 0;
 795
 796     double r = ro * c1 - 1;
 797     double ro0 = t * r - ro * s;
 798     double ro1 = t * r + ro * s;
 799
 800     int check_dir = check_flags & FLAG_DIR_2 ? 2 : 1;
 801     if (dir & check_dir) {
 802         double test_s = s, test0 = ro0, test1 = ro1;
 803         if (check_flags & FLAG_DIR_2) {
 804             test_s = -test_s;
 805             test0 = -test0;
 806             test1 = -test1;
 807         }
 808         int flags = 0;
 809         if (2 * test_s * r < dc[0] + dc[1]) flags |= FLAG_INTERSECTION;
 810         if (normal[0].len - test0 < 0) flags |= FLAG_ZERO_0;
 811         if (normal[1].len + test1 < 0) flags |= FLAG_ZERO_1;
 812         if (normal[0].len + dc[0] + test_s - test1 * c < 0) flags |= FLAG_CLIP_0;
 813         if (normal[1].len + dc[1] + test_s + test0 * c < 0) flags |= FLAG_CLIP_1;
 814         if ((flags ^ check_flags) & (check_flags >> FLAG_COUNT)) {
 815             dir &= ~check_dir;
 816             if (!dir)
 817                 return 0;
 818         }
 819     }
 820
 821     double d0c = 2 * dc[0], d0s = 2 * ds[0];
 822     double d1c = 2 * dc[1], d1s = 2 * ds[1];
 823     double dot0 = d0c + 3 * normal[0].len, crs0 = d0s + 3 * ro0 * normal[0].len;
 824     double dot1 = d1c + 3 * normal[1].len, crs1 = d1s + 3 * ro1 * normal[1].len;
 825     // check angular error (stage 1)
 826     if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1))
 827         return 0;
 828
 829     double cl0 = c * normal[0].len, sl0 = +s * normal[0].len;
 830     double cl1 = c * normal[1].len, sl1 = -s * normal[1].len;
 831     dot0 = d0c - ro0 * d0s + cl0 + ro1 * sl0 + cl1 / 3;
 832     dot1 = d1c - ro1 * d1s + cl1 + ro0 * sl1 + cl0 / 3;
 833     crs0 = d0s + ro0 * d0c - sl0 + ro1 * cl0 - sl1 / 3;
 834     crs1 = d1s + ro1 * d1c - sl1 + ro0 * cl1 - sl0 / 3;
 835     // check angular error (stage 2)
 836     if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1))
 837         return 0;
 838
 839     result[0].x = normal[0].v.x + normal[0].v.y * ro0;
 840     result[0].y = normal[0].v.y - normal[0].v.x * ro0;
 841     result[1].x = normal[1].v.x + normal[1].v.y * ro1;
 842     result[1].y = normal[1].v.y - normal[1].v.x * ro1;
 843     return dir;
 844 }
 845
 846 /**
 847  * \brief Helper function for cubic spline construction
 848  * \param str stroker state
 849  * \param pt array of 4 source spline points
 850  * \param deriv array of 3 differences between adjacent points in normal space
 851  * \param normal first and last spline normal
 852  * \param dir destination outline flags
 853  * \param first true if the current part is at start of the segment
 854  * \return false on allocation failure
 855  */
 856 static bool process_cubic(StrokerState *str, const ASS_Vector *pt,
 857                           const ASS_DVector *deriv, const Normal *normal,
 858                           int dir, bool first)
 859 {
 860     double c = vec_dot(normal[0].v, normal[1].v);
 861     double s = vec_crs(normal[0].v, normal[1].v);
 862     double dc[] = { vec_dot(normal[0].v, deriv[1]), vec_dot(normal[1].v, deriv[1]) };
 863     double ds[] = { vec_crs(normal[0].v, deriv[1]), vec_crs(normal[1].v, deriv[1]) };
 864     double f0 = normal[0].len * c + normal[1].len + dc[1];
 865     double f1 = normal[1].len * c + normal[0].len + dc[0];
 866     double g0 = normal[0].len * s - ds[1];
 867     double g1 = normal[1].len * s + ds[0];
 868
 869     double abs_s = s;
 870     int check_dir = dir, skip_dir = 2;
 871     int flags = FLAG_INTERSECTION | FLAG_DIR_2;
 872     if (s < 0) {
 873         abs_s = -s;
 874         skip_dir = 1;
 875         flags = 0;
 876         g0 = -g0;
 877         g1 = -g1;
 878     }
 879
 880     if (!(dc[0] + dc[1] > 0))
 881         check_dir = 0;
 882     else if (dir & skip_dir) {
 883         if (f0 < abs_s && f1 < abs_s) {  // check for self-intersection
 884             double d2 = (f0 + dc[1]) * normal[1].len + (f1 + dc[0]) * normal[0].len;
 885             d2 = (d2 + vec_dot(deriv[1], deriv[1])) / 2;
 886             if (d2 < g0 && d2 < g1) {
 887                 double q = sqrt(d2 / (2 - d2));
 888                 double h0 = (f0 * q + g0) * normal[1].len;
 889                 double h1 = (f1 * q + g1) * normal[0].len;
 890                 q *= (4.0 / 3) * d2;
 891                 if (h0 > q && h1 > q) {
 892                     if (!prepare_skip(str, pt[0], skip_dir, first))
 893                         return false;
 894                     if (f0 < 0 || f1 < 0) {
 895                         ASS_DVector zero_normal = {0, 0};
 896                         if (!emit_point(str, pt[0], zero_normal, FT_CURVE_TAG_ON, skip_dir) ||
 897                             !emit_point(str, pt[3], zero_normal, FT_CURVE_TAG_ON, skip_dir))
 898                             return false;
 899                     } else {
 900                         double mul = f0 / abs_s;
 901                         ASS_DVector offs = { normal[0].v.x * mul, normal[0].v.y * mul };
 902                         if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir))
 903                             return false;
 904                     }
 905                     dir &= ~skip_dir;
 906                     if (!dir) {
 907                         str->last_normal = normal[1].v;
 908                         return true;
 909                     }
 910                 }
 911             }
 912             check_dir ^= skip_dir;
 913         } else {
 914             if (ds[0] < 0)
 915                 flags ^= MASK_INTERSECTION;
 916             if (ds[1] < 0)
 917                 flags ^= MASK_INTERSECTION | FLAG_INTERSECTION;
 918             bool parallel = flags & MASK_INTERSECTION;
 919             int badness = parallel ? 0 : 1;
 920             if (c + g0 < 1) {
 921                 if (parallel) {
 922                     flags ^= MASK_ZERO_0 | FLAG_ZERO_0;
 923                     if (c < 0)
 924                         flags ^= MASK_CLIP_0;
 925                     if (f0 > abs_s)
 926                         flags ^= FLAG_ZERO_0 | FLAG_CLIP_0;
 927                 }
 928                 badness++;
 929             } else {
 930                 flags ^= MASK_INTERSECTION | FLAG_INTERSECTION;
 931                 if (!parallel) {
 932                     flags ^= MASK_ZERO_0;
 933                     if (c > 0)
 934                         flags ^= MASK_CLIP_0;
 935                 }
 936             }
 937             if (c + g1 < 1) {
 938                 if (parallel) {
 939                     flags ^= MASK_ZERO_1 | FLAG_ZERO_1;
 940                     if (c < 0)
 941                         flags ^= MASK_CLIP_1;
 942                     if (f1 > abs_s)
 943                         flags ^= FLAG_ZERO_1 | FLAG_CLIP_1;
 944                 }
 945                 badness++;
 946             } else {
 947                 flags ^= MASK_INTERSECTION;
 948                 if (!parallel) {
 949                     flags ^= MASK_ZERO_1;
 950                     if (c > 0)
 951                         flags ^= MASK_CLIP_1;
 952                 }
 953             }
 954             if (badness > 2)
 955                 check_dir ^= skip_dir;
 956         }
 957     }
 958
 959     ASS_DVector result[2];
 960     if (check_dir)
 961         check_dir = estimate_cubic_error(str, c, s, dc, ds,
 962                                          normal, result, flags, check_dir);
 963     if (check_dir) {
 964         if (!emit_first_point(str, pt[0], check_dir))
 965             return false;
 966         if (!emit_point(str, pt[1], result[0], FT_CURVE_TAG_CUBIC, check_dir) ||
 967             !emit_point(str, pt[2], result[1], FT_CURVE_TAG_CUBIC, check_dir))
 968             return false;
 969         dir &= ~check_dir;
 970         if (!dir) {
 971             str->last_normal = normal[1].v;
 972             return true;
 973         }
 974     }
 975
 976     ASS_Vector next[7], center;
 977     next[1].x = pt[0].x + pt[1].x;
 978     next[1].y = pt[0].y + pt[1].y;
 979     center.x = pt[1].x + pt[2].x + 2;
 980     center.y = pt[1].y + pt[2].y + 2;
 981     next[5].x = pt[2].x + pt[3].x;
 982     next[5].y = pt[2].y + pt[3].y;
 983     next[2].x = next[1].x + center.x;
 984     next[2].y = next[1].y + center.y;
 985     next[4].x = center.x + next[5].x;
 986     next[4].y = center.y + next[5].y;
 987     next[3].x = (next[2].x + next[4].x - 1) >> 3;
 988     next[3].y = (next[2].y + next[4].y - 1) >> 3;
 989     next[2].x >>= 2;
 990     next[2].y >>= 2;
 991     next[4].x >>= 2;
 992     next[4].y >>= 2;
 993     next[1].x >>= 1;
 994     next[1].y >>= 1;
 995     next[5].x >>= 1;
 996     next[5].y >>= 1;
 997     next[0] = pt[0];
 998     next[6] = pt[3];
 999
1000     ASS_DVector next_deriv[5], center_deriv;
1001     next_deriv[0].x = deriv[0].x / 2;
1002     next_deriv[0].y = deriv[0].y / 2;
1003     center_deriv.x = deriv[1].x / 2;
1004     center_deriv.y = deriv[1].y / 2;
1005     next_deriv[4].x = deriv[2].x / 2;
1006     next_deriv[4].y = deriv[2].y / 2;
1007     next_deriv[1].x = (next_deriv[0].x + center_deriv.x) / 2;
1008     next_deriv[1].y = (next_deriv[0].y + center_deriv.y) / 2;
1009     next_deriv[3].x = (center_deriv.x + next_deriv[4].x) / 2;
1010     next_deriv[3].y = (center_deriv.y + next_deriv[4].y) / 2;
1011     next_deriv[2].x = (next_deriv[1].x + next_deriv[3].x) / 2;
1012     next_deriv[2].y = (next_deriv[1].y + next_deriv[3].y) / 2;
1013
1014     double len = vec_len(next_deriv[2]);
1015     if (len < str->min_len) {  // check degenerate case
1016         Normal next_normal[4];
1017         next_normal[0].v = normal[0].v;
1018         next_normal[0].len = normal[0].len / 2;
1019         next_normal[3].v = normal[1].v;
1020         next_normal[3].len = normal[1].len / 2;
1021
1022         next_deriv[1].x += next_deriv[2].x;
1023         next_deriv[1].y += next_deriv[2].y;
1024         next_deriv[3].x += next_deriv[2].x;
1025         next_deriv[3].y += next_deriv[2].y;
1026         next_deriv[2].x = next_deriv[2].y = 0;
1027
1028         double len1 = vec_len(next_deriv[1]);
1029         if (len1 < str->min_len) {
1030             next_normal[1] = normal[0];
1031         } else {
1032             double scale = 1 / len1;
1033             next_normal[1].v.x = next_deriv[1].x * scale;
1034             next_normal[1].v.y = next_deriv[1].y * scale;
1035             next_normal[1].len = len1;
1036         }
1037
1038         double len2 = vec_len(next_deriv[3]);
1039         if (len2 < str->min_len) {
1040             next_normal[2] = normal[1];
1041         } else {
1042             double scale = 1 / len2;
1043             next_normal[2].v.x = next_deriv[3].x * scale;
1044             next_normal[2].v.y = next_deriv[3].y * scale;
1045             next_normal[2].len = len2;
1046         }
1047
1048         if (len1 < str->min_len) {
1049             if (!emit_first_point(str, next[0], dir))
1050                 return false;
1051         } else {
1052             if (!process_cubic(str, next + 0, next_deriv + 0, next_normal + 0, dir, first))
1053                 return false;
1054         }
1055         if (!start_segment(str, next[2], next_normal[2].v, dir))
1056             return false;
1057         if (len2 < str->min_len) {
1058             if (!emit_first_point(str, next[3], dir))
1059                 return false;
1060         } else {
1061             if (!process_cubic(str, next + 3, next_deriv + 2, next_normal + 2, dir, false))
1062                 return false;
1063         }
1064         return true;
1065     }
1066
1067     double scale = 1 / len;
1068     Normal next_normal[3] = {
1069         { normal[0].v, normal[0].len / 2 },
1070         { { next_deriv[2].x * scale, next_deriv[2].y * scale }, len },
1071         { normal[1].v, normal[1].len / 2 }
1072     };
1073     return process_cubic(str, next + 0, next_deriv + 0, next_normal + 0, dir, first) &&
1074            process_cubic(str, next + 3, next_deriv + 2, next_normal + 1, dir, false);
1075 }
1076
1077 /**
1078  * \brief Process source cubic spline
1079  * \param str stroker state
1080  * \param pt array of 4 source spline points
1081  * \param dir destination outline flags
1082  * \return false on allocation failure
1083  */
1084 static bool add_cubic(StrokerState *str, const ASS_Vector *pt, int dir)
1085 {
1086     int flags = 9;
1087
1088     int32_t dx0 = pt[1].x - pt[0].x;
1089     int32_t dy0 = pt[1].y - pt[0].y;
1090     if (dx0 > -str->eps && dx0 < str->eps && dy0 > -str->eps && dy0 < str->eps) {
1091         dx0 = pt[2].x - pt[0].x;
1092         dy0 = pt[2].y - pt[0].y;
1093         if (dx0 > -str->eps && dx0 < str->eps && dy0 > -str->eps && dy0 < str->eps)
1094             return add_line(str, pt[3], dir);
1095         flags ^= 1;
1096     }
1097
1098     int32_t dx2 = pt[3].x - pt[2].x;
1099     int32_t dy2 = pt[3].y - pt[2].y;
1100     if (dx2 > -str->eps && dx2 < str->eps && dy2 > -str->eps && dy2 < str->eps) {
1101         dx2 = pt[3].x - pt[1].x;
1102         dy2 = pt[3].y - pt[1].y;
1103         if (dx2 > -str->eps && dx2 < str->eps && dy2 > -str->eps && dy2 < str->eps)
1104             return add_line(str, pt[3], dir);
1105         flags ^= 4;
1106     }
1107
1108     if (flags == 12)
1109         return add_line(str, pt[3], dir);
1110
1111     int32_t dx1 = pt[flags >> 2].x - pt[flags & 3].x;
1112     int32_t dy1 = pt[flags >> 2].y - pt[flags & 3].y;
1113
1114     ASS_DVector deriv[3] = {
1115         { dy0 * str->yscale, -dx0 * str->xscale },
1116         { dy1 * str->yscale, -dx1 * str->xscale },
1117         { dy2 * str->yscale, -dx2 * str->xscale }
1118     };
1119     double len0 = vec_len(deriv[0]), scale0 = 1 / len0;
1120     double len2 = vec_len(deriv[2]), scale2 = 1 / len2;
1121     Normal normal[2] = {
1122         { { deriv[0].x * scale0, deriv[0].y * scale0 }, len0 },
1123         { { deriv[2].x * scale2, deriv[2].y * scale2 }, len2 }
1124     };
1125
1126     bool first = str->contour_start;
1127     if (!start_segment(str, pt[0], normal[0].v, dir))
1128         return false;
1129     if (!process_cubic(str, pt, deriv, normal, dir, first))
1130         return false;
1131     str->last_point = pt[3];
1132     return true;
1133 }
1134
1135
1136 /**
1137  * \brief Process contour closing
1138  * \param str stroker state
1139  * \param dir destination outline flags
1140  * \return false on allocation failure
1141  */
1142 static bool close_contour(StrokerState *str, int dir)
1143 {
1144     if (str->contour_start) {
1145         if ((dir & 3) == 3)
1146             dir = 1;
1147         if (!draw_circle(str, str->last_point, dir))
1148             return false;
1149     } else {
1150         if (!add_line(str, str->first_point, dir))
1151             return false;
1152         if (!start_segment(str, str->first_point, str->first_normal, dir))
1153             return false;
1154         if (!emit_point(str, str->first_point, str->first_normal, FT_CURVE_TAG_ON,
1155                        ~str->last_skip & dir & str->first_skip))
1156             return false;
1157         if (str->last_normal.x != str->first_normal.x ||
1158             str->last_normal.y != str->first_normal.y)
1159             fix_first_point(str, str->first_point, str->last_normal,
1160                            ~str->last_skip & dir & ~str->first_skip);
1161         str->contour_start = true;
1162     }
1163     if ((dir & 1) && !outline_close_contour(str->result[0]))
1164         return false;
1165     if ((dir & 2) && !outline_close_contour(str->result[1]))
1166         return false;
1167     return true;
1168 }
1169
1170
1171 /*
1172  * Stroke an outline glyph in x/y direction.
1173  * \param result first result outline
1174  * \param result1 second result outline
1175  * \param path source outline
1176  * \param xbord border size in X direction
1177  * \param ybord border size in Y direction
1178  * \param eps approximate allowable error
1179  * \return false on allocation failure
1180  */
1181 bool outline_stroke(ASS_Outline *result, ASS_Outline *result1,
1182                     const ASS_Outline *path, int xbord, int ybord, int eps)
1183 {
1184     int rad = FFMAX(xbord, ybord);
1185     assert(rad >= eps);
1186
1187     result->n_contours = result->n_points = 0;
1188     result1->n_contours = result1->n_points = 0;
1189
1190     StrokerState str;
1191     str.result[0] = result;
1192     str.result[1] = result1;
1193     str.xbord = xbord;
1194     str.ybord = ybord;
1195     str.xscale = 1.0 / FFMAX(eps, xbord);
1196     str.yscale = 1.0 / FFMAX(eps, ybord);
1197     str.eps = eps;
1198
1199     str.contour_start = true;
1200     double rel_err = (double) eps / rad;
1201     str.merge_cos = 1 - rel_err;
1202     double e = sqrt(2 * rel_err);
1203     str.split_cos = 1 + 8 * rel_err - 4 * (1 + rel_err) * e;
1204     str.min_len = rel_err / 4;
1205     str.err_q = 8 * (1 + rel_err) * (1 + rel_err);
1206     str.err_c = 390 * rel_err * rel_err;
1207     str.err_a = e;
1208
1209     enum Status {
1210         S_ON, S_Q, S_C1, S_C2
1211     };
1212
1213     const int dir = 3;
1214     for (size_t i = 0, j = 0; i < path->n_contours; i++) {
1215         ASS_Vector start, p[4];
1216         int process_end = 1;
1217         enum Status st;
1218
1219         int last = path->contours[i];
1220         if (j > last)
1221             return false;
1222
1223         if (path->points[j].x <  -(1 << 28) || path->points[j].x >= (1 << 28))
1224             return false;
1225         if (path->points[j].y <= -(1 << 28) || path->points[j].y >  (1 << 28))
1226             return false;
1227
1228         switch (FT_CURVE_TAG(path->tags[j])) {
1229         case FT_CURVE_TAG_ON:
1230             p[0].x =  path->points[j].x;
1231             p[0].y = -path->points[j].y;
1232             start = p[0];
1233             st = S_ON;
1234             break;
1235
1236         case FT_CURVE_TAG_CONIC:
1237             switch (FT_CURVE_TAG(path->tags[last])) {
1238             case FT_CURVE_TAG_ON:
1239                 p[0].x =  path->points[last].x;
1240                 p[0].y = -path->points[last].y;
1241                 p[1].x =  path->points[j].x;
1242                 p[1].y = -path->points[j].y;
1243                 process_end = 0;
1244                 start = p[0];
1245                 st = S_Q;
1246                 break;
1247
1248             case FT_CURVE_TAG_CONIC:
1249                 p[1].x =  path->points[j].x;
1250                 p[1].y = -path->points[j].y;
1251                 p[0].x = (p[1].x + path->points[last].x) >> 1;
1252                 p[0].y = (p[1].y - path->points[last].y) >> 1;
1253                 start = p[0];
1254                 st = S_Q;
1255                 break;
1256
1257             default:
1258                 return false;
1259             }
1260             break;
1261
1262         default:
1263             return false;
1264         }
1265         str.last_point = start;
1266
1267         for (j++; j <= last; j++) {
1268             if (path->points[j].x <  -(1 << 28) || path->points[j].x >= (1 << 28))
1269                 return false;
1270             if (path->points[j].y <= -(1 << 28) || path->points[j].y >  (1 << 28))
1271                 return false;
1272
1273             switch (FT_CURVE_TAG(path->tags[j])) {
1274             case FT_CURVE_TAG_ON:
1275                 switch (st) {
1276                 case S_ON:
1277                     p[1].x =  path->points[j].x;
1278                     p[1].y = -path->points[j].y;
1279                     if (!add_line(&str, p[1], dir))
1280                         return false;
1281                     p[0] = p[1];
1282                     break;
1283
1284                 case S_Q:
1285                     p[2].x =  path->points[j].x;
1286                     p[2].y = -path->points[j].y;
1287                     if (!add_quadratic(&str, p, dir))
1288                         return false;
1289                     p[0] = p[2];
1290                     st = S_ON;
1291                     break;
1292
1293                 case S_C2:
1294                     p[3].x =  path->points[j].x;
1295                     p[3].y = -path->points[j].y;
1296                     if (!add_cubic(&str, p, dir))
1297                         return false;
1298                     p[0] = p[3];
1299                     st = S_ON;
1300                     break;
1301
1302                 default:
1303                     return false;
1304                 }
1305                 break;
1306
1307             case FT_CURVE_TAG_CONIC:
1308                 switch (st) {
1309                 case S_ON:
1310                     p[1].x =  path->points[j].x;
1311                     p[1].y = -path->points[j].y;
1312                     st = S_Q;
1313                     break;
1314
1315                 case S_Q:
1316                     p[3].x =  path->points[j].x;
1317                     p[3].y = -path->points[j].y;
1318                     p[2].x = (p[1].x + p[3].x) >> 1;
1319                     p[2].y = (p[1].y + p[3].y) >> 1;
1320                     if (!add_quadratic(&str, p, dir))
1321                         return false;
1322                     p[0] = p[2];
1323                     p[1] = p[3];
1324                     break;
1325
1326                 default:
1327                     return false;
1328                 }
1329                 break;
1330
1331             case FT_CURVE_TAG_CUBIC:
1332                 switch (st) {
1333                 case S_ON:
1334                     p[1].x =  path->points[j].x;
1335                     p[1].y = -path->points[j].y;
1336                     st = S_C1;
1337                     break;
1338
1339                 case S_C1:
1340                     p[2].x =  path->points[j].x;
1341                     p[2].y = -path->points[j].y;
1342                     st = S_C2;
1343                     break;
1344
1345                 default:
1346                     return false;
1347                 }
1348                 break;
1349
1350             default:
1351                 return false;
1352             }
1353         }
1354
1355         if (process_end)
1356             switch (st) {
1357             case S_ON:
1358                 if (!add_line(&str, start, dir))
1359                     return false;
1360                 break;
1361
1362             case S_Q:
1363                 p[2] = start;
1364                 if (!add_quadratic(&str, p, dir))
1365                     return false;
1366                 break;
1367
1368             case S_C2:
1369                 p[3] = start;
1370                 if (!add_cubic(&str, p, dir))
1371                     return false;
1372                 break;
1373
1374             default:
1375                 return false;
1376             }
1377         if (!close_contour(&str, dir))
1378             return false;
1379     }
1380     return true;
1381 }