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