diff options
Diffstat (limited to 'libass')
-rw-r--r-- | libass/ass_drawing.c | 58 | ||||
-rw-r--r-- | libass/ass_outline.c | 1170 | ||||
-rw-r--r-- | libass/ass_outline.h | 7 | ||||
-rw-r--r-- | libass/ass_parse.c | 35 | ||||
-rw-r--r-- | libass/ass_parse.h | 3 | ||||
-rw-r--r-- | libass/ass_render.c | 134 | ||||
-rw-r--r-- | libass/ass_render.h | 3 |
7 files changed, 1062 insertions, 348 deletions
diff --git a/libass/ass_drawing.c b/libass/ass_drawing.c index 3428d21..23fe8cd 100644 --- a/libass/ass_drawing.c +++ b/libass/ass_drawing.c @@ -35,47 +35,6 @@ #define GLYPH_INITIAL_CONTOURS 5 /* - * \brief Add a single point to a contour. - */ -static inline bool drawing_add_point(ASS_Drawing *drawing, - const FT_Vector *point, char tags) -{ - ASS_Outline *ol = &drawing->outline; - if (ol->n_points >= ol->max_points) { - size_t new_size = 2 * ol->max_points; - if (!ASS_REALLOC_ARRAY(ol->points, new_size)) - return false; - if (!ASS_REALLOC_ARRAY(ol->tags, new_size)) - return false; - ol->max_points = new_size; - } - - ol->points[ol->n_points].x = point->x; - ol->points[ol->n_points].y = point->y; - ol->tags[ol->n_points] = tags; - ol->n_points++; - return true; -} - -/* - * \brief Close a contour and check outline size overflow. - */ -static inline bool drawing_close_shape(ASS_Drawing *drawing) -{ - ASS_Outline *ol = &drawing->outline; - if (ol->n_contours >= ol->max_contours) { - size_t new_size = 2 * ol->max_contours; - if (!ASS_REALLOC_ARRAY(ol->contours, new_size)) - return false; - ol->max_contours = new_size; - } - - ol->contours[ol->n_contours] = ol->n_points - 1; - ol->n_contours++; - return true; -} - -/* * \brief Prepare drawing for parsing. This just sets a few parameters. */ static void drawing_prepare(ASS_Drawing *drawing) @@ -278,10 +237,11 @@ static bool drawing_evaluate_curve(ASS_Drawing *drawing, p[2].y -= y12; } - return (started || drawing_add_point(drawing, &p[0], FT_CURVE_TAG_ON)) && - drawing_add_point(drawing, &p[1], FT_CURVE_TAG_CUBIC) && - drawing_add_point(drawing, &p[2], FT_CURVE_TAG_CUBIC) && - drawing_add_point(drawing, &p[3], FT_CURVE_TAG_ON); + return (started || + outline_add_point(&drawing->outline, p[0], FT_CURVE_TAG_ON)) && + outline_add_point(&drawing->outline, p[1], FT_CURVE_TAG_CUBIC) && + outline_add_point(&drawing->outline, p[2], FT_CURVE_TAG_CUBIC) && + outline_add_point(&drawing->outline, p[3], FT_CURVE_TAG_ON); } /* @@ -362,7 +322,7 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, int raw_mode) pen = token->point; translate_point(drawing, &pen); if (started) { - if (!drawing_close_shape(drawing)) + if (!outline_close_contour(&drawing->outline)) goto error; started = 0; } @@ -372,9 +332,9 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, int raw_mode) FT_Vector to; to = token->point; translate_point(drawing, &to); - if (!started && !drawing_add_point(drawing, &pen, FT_CURVE_TAG_ON)) + if (!started && !outline_add_point(&drawing->outline, pen, FT_CURVE_TAG_ON)) goto error; - if (!drawing_add_point(drawing, &to, FT_CURVE_TAG_ON)) + if (!outline_add_point(&drawing->outline, to, FT_CURVE_TAG_ON)) goto error; started = 1; token = token->next; @@ -409,7 +369,7 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, int raw_mode) } // Close the last contour - if (started && !drawing_close_shape(drawing)) + if (started && !outline_close_contour(&drawing->outline)) goto error; drawing_finish(drawing, raw_mode); diff --git a/libass/ass_outline.c b/libass/ass_outline.c index 7c1d784..1facc6d 100644 --- a/libass/ass_outline.c +++ b/libass/ass_outline.c @@ -37,21 +37,30 @@ bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_contours) return true; } -ASS_Outline *outline_convert(const FT_Outline *source) +ASS_Outline *outline_create(size_t n_points, size_t n_contours) { - if (!source) - return NULL; - ASS_Outline *ol = calloc(1, sizeof(*ol)); if (!ol) return NULL; - if (!outline_alloc(ol, source->n_points, source->n_contours)) { + if (!outline_alloc(ol, n_points, n_contours)) { outline_free(ol); free(ol); return NULL; } + return ol; +} + +ASS_Outline *outline_convert(const FT_Outline *source) +{ + if (!source) + return NULL; + + ASS_Outline *ol = outline_create(source->n_points, source->n_contours); + if (!ol) + return NULL; + for (int i = 0; i < source->n_contours; i++) ol->contours[i] = source->contours[i]; memcpy(ol->points, source->points, sizeof(FT_Vector) * source->n_points); @@ -66,16 +75,10 @@ ASS_Outline *outline_copy(const ASS_Outline *source) if (!source) return NULL; - ASS_Outline *ol = calloc(1, sizeof(*ol)); + ASS_Outline *ol = outline_create(source->n_points, source->n_contours); if (!ol) return NULL; - if (!outline_alloc(ol, source->n_points, source->n_contours)) { - outline_free(ol); - free(ol); - return NULL; - } - memcpy(ol->contours, source->contours, sizeof(size_t) * source->n_contours); memcpy(ol->points, source->points, sizeof(FT_Vector) * source->n_points); memcpy(ol->tags, source->tags, source->n_points); @@ -95,6 +98,42 @@ void outline_free(ASS_Outline *outline) } +/* + * \brief Add a single point to a contour. + */ +bool outline_add_point(ASS_Outline *outline, FT_Vector pt, char tag) +{ + if (outline->n_points >= outline->max_points) { + size_t new_size = 2 * outline->max_points; + if (!ASS_REALLOC_ARRAY(outline->points, new_size)) + return false; + if (!ASS_REALLOC_ARRAY(outline->tags, new_size)) + return false; + outline->max_points = new_size; + } + outline->points[outline->n_points] = pt; + outline->tags[outline->n_points] = tag; + outline->n_points++; + return true; +} + +/* + * \brief Close a contour. + */ +bool outline_close_contour(ASS_Outline *outline) +{ + if (outline->n_contours >= outline->max_contours) { + size_t new_size = 2 * outline->max_contours; + if (!ASS_REALLOC_ARRAY(outline->contours, new_size)) + return false; + outline->max_contours = new_size; + } + outline->contours[outline->n_contours] = outline->n_points - 1; + outline->n_contours++; + return true; +} + + void outline_translate(const ASS_Outline *outline, FT_Pos dx, FT_Pos dy) { for (size_t i = 0; i < outline->n_points; i++) { @@ -133,143 +172,1008 @@ void outline_get_cbox(const ASS_Outline *outline, FT_BBox *cbox) } -/** - * \brief Calculate the cbox of a series of points - */ -static void -get_contour_cbox(FT_BBox *box, FT_Vector *points, int start, int end) + +typedef struct { + int32_t x, y; +} OutlinePoint; + +typedef struct { + double x, y; +} Vector; + +typedef struct { + Vector v; + double len; +} Normal; + +typedef struct { + ASS_Outline *result[2]; + double xbord, ybord; + double xscale, yscale; + int eps; + + bool contour_start; + int first_skip, last_skip; + Vector first_normal, last_normal; + OutlinePoint first_point, last_point; + + double merge_cos, split_cos, min_len; + double err_q, err_c, err_a; +} StrokerState; + +static inline double vec_dot(Vector vec1, Vector vec2) { - box->xMin = box->yMin = INT_MAX; - box->xMax = box->yMax = INT_MIN; - for (int i = start; i <= end; i++) { - box->xMin = (points[i].x < box->xMin) ? points[i].x : box->xMin; - box->xMax = (points[i].x > box->xMax) ? points[i].x : box->xMax; - box->yMin = (points[i].y < box->yMin) ? points[i].y : box->yMin; - box->yMax = (points[i].y > box->yMax) ? points[i].y : box->yMax; + return vec1.x * vec2.x + vec1.y * vec2.y; +} + +static inline double vec_crs(Vector vec1, Vector vec2) +{ + return vec1.x * vec2.y - vec1.y * vec2.x; +} + +static inline double vec_len(Vector vec) +{ + return sqrt(vec.x * vec.x + vec.y * vec.y); +} + + +static bool emit_point(StrokerState *str, OutlinePoint pt, + Vector offs, char tag, int dir) +{ + int32_t dx = (int32_t)(str->xbord * offs.x); + int32_t dy = (int32_t)(str->ybord * offs.y); + + if (dir & 1) { + FT_Vector res = { pt.x + dx, pt.y + dy }; + res.y = -res.y; + if (!outline_add_point(str->result[0], res, tag)) + return false; + } + if (dir & 2) { + FT_Vector res = { pt.x - dx, pt.y - dy }; + res.y = -res.y; + if (!outline_add_point(str->result[1], res, tag)) + return false; } + return true; } -/** - * \brief Determine signed area of a contour - * \return area doubled - */ -static long long get_contour_area(FT_Vector *points, int start, int end) +static void fix_first_point(StrokerState *str, OutlinePoint pt, + Vector offs, int dir) +{ + int32_t dx = (int32_t)(str->xbord * offs.x); + int32_t dy = (int32_t)(str->ybord * offs.y); + + if (dir & 1) { + FT_Vector res = { pt.x + dx, pt.y + dy }; + res.y = -res.y; + ASS_Outline *ol = str->result[0]; + size_t first = ol->n_contours ? + ol->contours[ol->n_contours - 1] + 1 : 0; + ol->points[first] = res; + } + if (dir & 2) { + FT_Vector res = { pt.x - dx, pt.y - dy }; + res.y = -res.y; + ASS_Outline *ol = str->result[1]; + size_t first = ol->n_contours ? + ol->contours[ol->n_contours - 1] + 1 : 0; + ol->points[first] = res; + } +} + +static bool process_arc(StrokerState *str, OutlinePoint pt, + Vector normal0, Vector normal1, + const double *mul, int level, int dir) { - long long area = 0; - int x = points[end].x; - int y = points[end].y; - for (int i = start; i <= end; i++) { - area += (long long)(points[i].x + x) * (points[i].y - y); - x = points[i].x; - y = points[i].y; - } - return area; + Vector center; + center.x = (normal0.x + normal1.x) * mul[level]; + center.y = (normal0.y + normal1.y) * mul[level]; + if (level) + return process_arc(str, pt, normal0, center, mul, level - 1, dir) && + process_arc(str, pt, center, normal1, mul, level - 1, dir); + return emit_point(str, pt, normal0, FT_CURVE_TAG_ON, dir) && + emit_point(str, pt, center, FT_CURVE_TAG_CONIC, dir); } -/** - * \brief Apply fixups to please the FreeType stroker and improve the - * rendering result, especially in case the outline has some anomalies. - * At the moment, the following fixes are done: - * - * 1. Reverse contours that have "inside" winding direction but are not - * contained in any other contours' cbox. - * 2. Remove "inside" contours depending on border size, so that large - * borders do not reverse the winding direction, which leads to "holes" - * inside the border. The inside will be filled by the border of the - * outside contour anyway in this case. - * - * \param outline FreeType outline, modified in-place - * \param border_x border size, x direction, d6 format - * \param border_x border size, y direction, d6 format - */ -void fix_freetype_stroker(ASS_Outline *outline, int border_x, int border_y) +static bool draw_arc(StrokerState *str, OutlinePoint pt, + Vector normal0, Vector normal1, double c, int dir) { - int nc = outline->n_contours; - int begin, stop; - char modified = 0; - char *valid_cont = malloc(nc); - int start = 0; - int end = -1; - FT_BBox *boxes = malloc(nc * sizeof(FT_BBox)); - int i, j; - - long long area = 0; - // create a list of cboxes of the contours - for (i = 0; i < nc; i++) { - start = end + 1; - end = outline->contours[i]; - get_contour_cbox(&boxes[i], outline->points, start, end); - area += get_contour_area(outline->points, start, end); - } - int inside_direction = area < 0; - - // for each contour, check direction and whether it's "outside" - // or contained in another contour - end = -1; - for (i = 0; i < nc; i++) { - start = end + 1; - end = outline->contours[i]; - int dir = get_contour_area(outline->points, start, end) > 0; - valid_cont[i] = 1; - if (dir == inside_direction) { - for (j = 0; j < nc; j++) { - if (i == j) - continue; - if (boxes[i].xMin >= boxes[j].xMin && - boxes[i].xMax <= boxes[j].xMax && - boxes[i].yMin >= boxes[j].yMin && - boxes[i].yMax <= boxes[j].yMax) - goto check_inside; - } - /* "inside" contour but we can't find anything it could be - * inside of - assume the font is buggy and it should be - * an "outside" contour, and reverse it */ - for (j = 0; j < (end - start) / 2; j++) { - FT_Vector temp = outline->points[start + 1 + j]; - char temp2 = outline->tags[start + 1 + j]; - outline->points[start + 1 + j] = outline->points[end - j]; - outline->points[end - j] = temp; - outline->tags[start + 1 + j] = outline->tags[end - j]; - outline->tags[end - j] = temp2; + const int max_subdiv = 15; + double mul[max_subdiv + 1]; + + Vector center; + bool small_angle = true; + if (c < 0) { + double mul = dir & 2 ? -sqrt(0.5) : sqrt(0.5); + mul /= sqrt(1 - c); + center.x = (normal1.y - normal0.y) * mul; + center.y = (normal0.x - normal1.x) * mul; + c = sqrt(FFMAX(0, 0.5 + 0.5 * c)); + small_angle = false; + } + + int pos = max_subdiv; + while (c < str->split_cos && pos) { + mul[pos] = sqrt(0.5) / sqrt(1 + c); + c = (1 + c) * mul[pos]; + pos--; + } + mul[pos] = 1 / (1 + c); + return small_angle ? + process_arc(str, pt, normal0, normal1, mul + pos, max_subdiv - pos, dir) : + process_arc(str, pt, normal0, center, mul + pos, max_subdiv - pos, dir) && + process_arc(str, pt, center, normal1, mul + pos, max_subdiv - pos, dir); +} + +static bool draw_circle(StrokerState *str, OutlinePoint pt, int dir) +{ + const int max_subdiv = 15; + double mul[max_subdiv + 1], c = 0; + + int pos = max_subdiv; + while (c < str->split_cos && pos) { + mul[pos] = sqrt(0.5) / sqrt(1 + c); + c = (1 + c) * mul[pos]; + pos--; + } + mul[pos] = 1 / (1 + c); + + Vector normal[4] = { + { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } + }; + return process_arc(str, pt, normal[0], normal[1], mul + pos, max_subdiv - pos, dir) && + process_arc(str, pt, normal[1], normal[2], mul + pos, max_subdiv - pos, dir) && + process_arc(str, pt, normal[2], normal[3], mul + pos, max_subdiv - pos, dir) && + process_arc(str, pt, normal[3], normal[0], mul + pos, max_subdiv - pos, dir); +} + +static bool start_segment(StrokerState *str, OutlinePoint pt, + Vector normal, int dir) +{ + if (str->contour_start) { + str->contour_start = false; + str->first_skip = str->last_skip = 0; + str->first_normal = str->last_normal = normal; + str->first_point = pt; + return true; + } + + Vector prev = str->last_normal; + double c = vec_dot(prev, normal); + if (c > str->merge_cos) { // merge without cap + double mul = 1 / (1 + c); + str->last_normal.x = (str->last_normal.x + normal.x) * mul; + str->last_normal.y = (str->last_normal.y + normal.y) * mul; + return true; + } + str->last_normal = normal; + + // check for negative curvative + double s = vec_crs(prev, normal); + int skip_dir = s < 0 ? 1 : 2; + if (dir & skip_dir) { + if (!emit_point(str, pt, prev, FT_CURVE_TAG_ON, ~str->last_skip & skip_dir)) + return false; + Vector zero_normal = {0, 0}; + if (!emit_point(str, pt, zero_normal, FT_CURVE_TAG_ON, skip_dir)) + return false; + } + str->last_skip = skip_dir; + + dir &= ~skip_dir; + return !dir || draw_arc(str, pt, prev, normal, c, dir); +} + +static bool emit_first_point(StrokerState *str, OutlinePoint pt, int dir) +{ + str->last_skip &= ~dir; + return emit_point(str, pt, str->last_normal, FT_CURVE_TAG_ON, dir); +} + +static bool prepare_skip(StrokerState *str, OutlinePoint pt, int dir, bool first) +{ + if (first) + str->first_skip |= dir; + else if (!emit_point(str, pt, str->last_normal, FT_CURVE_TAG_ON, ~str->last_skip & dir)) + return false; + str->last_skip |= dir; + return true; +} + +static bool add_line(StrokerState *str, OutlinePoint pt, int dir) +{ + int32_t dx = pt.x - str->last_point.x; + int32_t dy = pt.y - str->last_point.y; + if (dx > -str->eps && dx < str->eps && dy > -str->eps && dy < str->eps) + return true; + + Vector deriv = { dy * str->yscale, -dx * str->xscale }; + double scale = 1 / vec_len(deriv); + Vector normal = { deriv.x * scale, deriv.y * scale }; + if (!start_segment(str, str->last_point, normal, dir)) + return false; + if (!emit_first_point(str, str->last_point, dir)) + return false; + str->last_normal = normal; + str->last_point = pt; + return true; +} + + +static bool estimate_quadratic_error(StrokerState *str, double c, double s, + const Normal *normal, Vector *result) +{ + // check radial error + if (!((3 + c) * (3 + c) < str->err_q * (1 + c))) + return false; + + double mul = 1 / (1 + c); + double l0 = 2 * normal[0].len, l1 = 2 * normal[1].len; + double dot0 = l0 + normal[1].len * c, crs0 = (l0 * mul - normal[1].len) * s; + double dot1 = l1 + normal[0].len * c, crs1 = (l1 * mul - normal[0].len) * s; + // check angular error + if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1)) + return false; + + result->x = (normal[0].v.x + normal[1].v.x) * mul; + result->y = (normal[0].v.y + normal[1].v.y) * mul; + return true; +} + +static bool process_quadratic(StrokerState *str, const OutlinePoint *pt, + const Vector *deriv, const Normal *normal, + int dir, bool first) +{ + double c = vec_dot(normal[0].v, normal[1].v); + double s = vec_crs(normal[0].v, normal[1].v); + int check_dir = dir, skip_dir = s < 0 ? 1 : 2; + if (dir & skip_dir) { + double abs_s = fabs(s); + double f0 = normal[0].len * c + normal[1].len; + double f1 = normal[1].len * c + normal[0].len; + double g0 = normal[0].len * abs_s; + double g1 = normal[1].len * abs_s; + // check for self-intersection + if (f0 < abs_s && f1 < abs_s) { + double d2 = (f0 * normal[1].len + f1 * normal[0].len) / 2; + if (d2 < g0 && d2 < g1) { + if (!prepare_skip(str, pt[0], skip_dir, first)) + return false; + if (f0 < 0 || f1 < 0) { + Vector zero_normal = {0, 0}; + if (!emit_point(str, pt[0], zero_normal, FT_CURVE_TAG_ON, skip_dir) || + !emit_point(str, pt[2], zero_normal, FT_CURVE_TAG_ON, skip_dir)) + return false; + } else { + double mul = f0 / abs_s; + Vector offs = { normal[0].v.x * mul, normal[0].v.y * mul }; + if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir)) + return false; + } + dir &= ~skip_dir; + if (!dir) { + str->last_normal = normal[1].v; + return true; + } } - dir ^= 1; + check_dir ^= skip_dir; + } else if (c + g0 < 1 && c + g1 < 1) + check_dir ^= skip_dir; + } + + Vector result; + if (check_dir && estimate_quadratic_error(str, c, s, normal, &result)) { + if (!emit_first_point(str, pt[0], check_dir)) + return false; + if (!emit_point(str, pt[1], result, FT_CURVE_TAG_CONIC, check_dir)) + return false; + dir &= ~check_dir; + if (!dir) { + str->last_normal = normal[1].v; + return true; } - check_inside: - if (dir == inside_direction) { - FT_BBox box; - get_contour_cbox(&box, outline->points, start, end); - int width = box.xMax - box.xMin; - int height = box.yMax - box.yMin; - if (width < border_x * 2 || height < border_y * 2) { - valid_cont[i] = 0; - modified = 1; - } + } + + OutlinePoint next[5]; + next[1].x = pt[0].x + pt[1].x; + next[1].y = pt[0].y + pt[1].y; + next[3].x = pt[1].x + pt[2].x; + next[3].y = pt[1].y + pt[2].y; + next[2].x = (next[1].x + next[3].x + 2) >> 2; + next[2].y = (next[1].y + next[3].y + 2) >> 2; + next[1].x >>= 1; + next[1].y >>= 1; + next[3].x >>= 1; + next[3].y >>= 1; + next[0] = pt[0]; + next[4] = pt[2]; + + Vector next_deriv[3]; + next_deriv[0].x = deriv[0].x / 2; + next_deriv[0].y = deriv[0].y / 2; + next_deriv[2].x = deriv[1].x / 2; + next_deriv[2].y = deriv[1].y / 2; + next_deriv[1].x = (next_deriv[0].x + next_deriv[2].x) / 2; + next_deriv[1].y = (next_deriv[0].y + next_deriv[2].y) / 2; + + double len = vec_len(next_deriv[1]); + if (len < str->min_len) { // check degenerate case + if (!emit_first_point(str, next[0], dir)) + return false; + if (!start_segment(str, next[2], normal[1].v, dir)) + return false; + str->last_skip &= ~dir; + return emit_point(str, next[2], normal[1].v, FT_CURVE_TAG_ON, dir); + } + + double scale = 1 / len; + Normal next_normal[3] = { + { normal[0].v, normal[0].len / 2 }, + { { next_deriv[1].x * scale, next_deriv[1].y * scale }, len }, + { normal[1].v, normal[1].len / 2 } + }; + return process_quadratic(str, next + 0, next_deriv + 0, next_normal + 0, dir, first) && + process_quadratic(str, next + 2, next_deriv + 1, next_normal + 1, dir, false); +} + +static bool add_quadratic(StrokerState *str, const OutlinePoint *pt, int dir) +{ + int32_t dx0 = pt[1].x - pt[0].x; + int32_t dy0 = pt[1].y - pt[0].y; + if (dx0 > -str->eps && dx0 < str->eps && dy0 > -str->eps && dy0 < str->eps) + return add_line(str, pt[2], dir); + + int32_t dx1 = pt[2].x - pt[1].x; + int32_t dy1 = pt[2].y - pt[1].y; + if (dx1 > -str->eps && dx1 < str->eps && dy1 > -str->eps && dy1 < str->eps) + return add_line(str, pt[2], dir); + + Vector deriv[2] = { + { dy0 * str->yscale, -dx0 * str->xscale }, + { dy1 * str->yscale, -dx1 * str->xscale } + }; + double len0 = vec_len(deriv[0]), scale0 = 1 / len0; + double len1 = vec_len(deriv[1]), scale1 = 1 / len1; + Normal normal[2] = { + { { deriv[0].x * scale0, deriv[0].y * scale0 }, len0 }, + { { deriv[1].x * scale1, deriv[1].y * scale1 }, len1 } + }; + + bool first = str->contour_start; + if (!start_segment(str, pt[0], normal[0].v, dir)) + return false; + if (!process_quadratic(str, pt, deriv, normal, dir, first)) + return false; + str->last_point = pt[2]; + return true; +} + + +enum { + FLAG_INTERSECTION = 1, + FLAG_ZERO_0 = 2, + FLAG_ZERO_1 = 4, + FLAG_CLIP_0 = 8, + FLAG_CLIP_1 = 16, + FLAG_DIR_2 = 32, + + FLAG_COUNT = 6, + + MASK_INTERSECTION = FLAG_INTERSECTION << FLAG_COUNT, + MASK_ZERO_0 = FLAG_ZERO_0 << FLAG_COUNT, + MASK_ZERO_1 = FLAG_ZERO_1 << FLAG_COUNT, + MASK_CLIP_0 = FLAG_CLIP_0 << FLAG_COUNT, + MASK_CLIP_1 = FLAG_CLIP_1 << FLAG_COUNT, +}; + +static int estimate_cubic_error(StrokerState *str, double c, double s, + const double *dc, const double *ds, + const Normal *normal, Vector *result, + int check_flags, int dir) +{ + double t = (ds[0] + ds[1]) / (dc[0] + dc[1]), c1 = 1 + c, ss = s * s; + double ts = t * s, tt = t * t, ttc = tt * c1, ttcc = ttc * c1; + + const double w = 0.4; + double f0[] = { + 10 * w * (c - 1) + 9 * w * tt * c, + 2 * (c - 1) + 3 * tt + 2 * ts, + 2 * (c - 1) + 3 * tt - 2 * ts, + }; + double f1[] = { + 18 * w * (ss - ttc * c), + 2 * ss - 6 * ttc - 2 * ts * (c + 4), + 2 * ss - 6 * ttc + 2 * ts * (c + 4), + }; + double f2[] = { + 9 * w * (ttcc - ss) * c, + 3 * ss + 3 * ttcc + 6 * ts * c1, + 3 * ss + 3 * ttcc - 6 * ts * c1, + }; + + double aa = 0, ab = 0; + double ch = sqrt(c1 / 2); + double inv_ro0 = 1.5 * ch * (ch + 1); + for (int i = 0; i < 3; i++) { + double a = 2 * f2[i] + f1[i] * inv_ro0; + double b = f2[i] - f0[i] * inv_ro0 * inv_ro0; + aa += a * a; ab += a * b; + } + double ro = ab / (aa * inv_ro0 + 1e-9); // best fit + + double err2 = 0; + for (int i = 0; i < 3; i++) { + double err = f0[i] + ro * (f1[i] + ro * f2[i]); + err2 += err * err; + } + if (!(err2 < str->err_c)) // check radial error + return 0; + + double r = ro * c1 - 1; + double ro0 = t * r - ro * s; + double ro1 = t * r + ro * s; + + int check_dir = check_flags & FLAG_DIR_2 ? 2 : 1; + if (dir & check_dir) { + double test_s = s, test0 = ro0, test1 = ro1; + if (check_flags & FLAG_DIR_2) { + test_s = -test_s; + test0 = -test0; + test1 = -test1; + } + int flags = 0; + if (2 * test_s * r < dc[0] + dc[1]) flags |= FLAG_INTERSECTION; + if (normal[0].len - test0 < 0) flags |= FLAG_ZERO_0; + if (normal[1].len + test1 < 0) flags |= FLAG_ZERO_1; + if (normal[0].len + dc[0] + test_s - test1 * c < 0) flags |= FLAG_CLIP_0; + if (normal[1].len + dc[1] + test_s + test0 * c < 0) flags |= FLAG_CLIP_1; + if ((flags ^ check_flags) & (check_flags >> FLAG_COUNT)) { + dir &= ~check_dir; + if (!dir) + return 0; } } - // if we need to modify the outline, rewrite it and skip - // the contours that we determined should be removed. - if (modified) { - int p = 0, c = 0; - for (i = 0; i < nc; i++) { - if (!valid_cont[i]) - continue; - begin = (i == 0) ? 0 : outline->contours[i - 1] + 1; - stop = outline->contours[i]; - for (j = begin; j <= stop; j++) { - outline->points[p].x = outline->points[j].x; - outline->points[p].y = outline->points[j].y; - outline->tags[p] = outline->tags[j]; - p++; + double d0c = 2 * dc[0], d0s = 2 * ds[0]; + double d1c = 2 * dc[1], d1s = 2 * ds[1]; + double dot0 = d0c + 3 * normal[0].len, crs0 = d0s + 3 * ro0 * normal[0].len; + double dot1 = d1c + 3 * normal[1].len, crs1 = d1s + 3 * ro1 * normal[1].len; + // check angular error (stage 1) + if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1)) + return 0; + + double cl0 = c * normal[0].len, sl0 = +s * normal[0].len; + double cl1 = c * normal[1].len, sl1 = -s * normal[1].len; + dot0 = d0c - ro0 * d0s + cl0 + ro1 * sl0 + cl1 / 3; + dot1 = d1c - ro1 * d1s + cl1 + ro0 * sl1 + cl0 / 3; + crs0 = d0s + ro0 * d0c - sl0 + ro1 * cl0 - sl1 / 3; + crs1 = d1s + ro1 * d1c - sl1 + ro0 * cl1 - sl0 / 3; + // check angular error (stage 2) + if (!(fabs(crs0) < str->err_a * dot0 && fabs(crs1) < str->err_a * dot1)) + return 0; + + result[0].x = normal[0].v.x + normal[0].v.y * ro0; + result[0].y = normal[0].v.y - normal[0].v.x * ro0; + result[1].x = normal[1].v.x + normal[1].v.y * ro1; + result[1].y = normal[1].v.y - normal[1].v.x * ro1; + return dir; +} + +static bool process_cubic(StrokerState *str, const OutlinePoint *pt, + const Vector *deriv, const Normal *normal, + int dir, bool first) +{ + double c = vec_dot(normal[0].v, normal[1].v); + double s = vec_crs(normal[0].v, normal[1].v); + double dc[] = { vec_dot(normal[0].v, deriv[1]), vec_dot(normal[1].v, deriv[1]) }; + double ds[] = { vec_crs(normal[0].v, deriv[1]), vec_crs(normal[1].v, deriv[1]) }; + double f0 = normal[0].len * c + normal[1].len + dc[1]; + double f1 = normal[1].len * c + normal[0].len + dc[0]; + double g0 = normal[0].len * s - ds[1]; + double g1 = normal[1].len * s + ds[0]; + + double abs_s = s; + int check_dir = dir, skip_dir = 2; + int flags = FLAG_INTERSECTION | FLAG_DIR_2; + if (s < 0) { + abs_s = -s; + skip_dir = 1; + flags = 0; + g0 = -g0; + g1 = -g1; + } + + if (!(dc[0] + dc[1] > 0)) + check_dir = 0; + else if (dir & skip_dir) { + if (f0 < abs_s && f1 < abs_s) { // check for self-intersection + double d2 = (f0 + dc[1]) * normal[1].len + (f1 + dc[0]) * normal[0].len; + d2 = (d2 + vec_dot(deriv[1], deriv[1])) / 2; + if (d2 < g0 && d2 < g1) { + double q = sqrt(d2 / (2 - d2)); + double h0 = (f0 * q + g0) * normal[1].len; + double h1 = (f1 * q + g1) * normal[0].len; + q *= (4.0 / 3) * d2; + if (h0 > q && h1 > q) { + if (!prepare_skip(str, pt[0], skip_dir, first)) + return false; + if (f0 < 0 || f1 < 0) { + Vector zero_normal = {0, 0}; + if (!emit_point(str, pt[0], zero_normal, FT_CURVE_TAG_ON, skip_dir) || + !emit_point(str, pt[3], zero_normal, FT_CURVE_TAG_ON, skip_dir)) + return false; + } else { + double mul = f0 / abs_s; + Vector offs = { normal[0].v.x * mul, normal[0].v.y * mul }; + if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir)) + return false; + } + dir &= ~skip_dir; + if (!dir) { + str->last_normal = normal[1].v; + return true; + } + } + } + check_dir ^= skip_dir; + } else { + if (ds[0] < 0) + flags ^= MASK_INTERSECTION; + if (ds[1] < 0) + flags ^= MASK_INTERSECTION | FLAG_INTERSECTION; + bool parallel = flags & MASK_INTERSECTION; + int badness = parallel ? 0 : 1; + if (c + g0 < 1) { + if (parallel) { + flags ^= MASK_ZERO_0 | FLAG_ZERO_0; + if (c < 0) + flags ^= MASK_CLIP_0; + if (f0 > abs_s) + flags ^= FLAG_ZERO_0 | FLAG_CLIP_0; + } + badness++; + } else { + flags ^= MASK_INTERSECTION | FLAG_INTERSECTION; + if (!parallel) { + flags ^= MASK_ZERO_0; + if (c > 0) + flags ^= MASK_CLIP_0; + } } - outline->contours[c] = p - 1; - c++; + if (c + g1 < 1) { + if (parallel) { + flags ^= MASK_ZERO_1 | FLAG_ZERO_1; + if (c < 0) + flags ^= MASK_CLIP_1; + if (f1 > abs_s) + flags ^= FLAG_ZERO_1 | FLAG_CLIP_1; + } + badness++; + } else { + flags ^= MASK_INTERSECTION; + if (!parallel) { + flags ^= MASK_ZERO_1; + if (c > 0) + flags ^= MASK_CLIP_1; + } + } + if (badness > 2) + check_dir ^= skip_dir; + } + } + + Vector result[2]; + if (check_dir) + check_dir = estimate_cubic_error(str, c, s, dc, ds, + normal, result, flags, check_dir); + if (check_dir) { + if (!emit_first_point(str, pt[0], check_dir)) + return false; + if (!emit_point(str, pt[1], result[0], FT_CURVE_TAG_CUBIC, check_dir) || + !emit_point(str, pt[2], result[1], FT_CURVE_TAG_CUBIC, check_dir)) + return false; + dir &= ~check_dir; + if (!dir) { + str->last_normal = normal[1].v; + return true; } - outline->n_points = p; - outline->n_contours = c; } - free(boxes); - free(valid_cont); + OutlinePoint next[7], center; + next[1].x = pt[0].x + pt[1].x; + next[1].y = pt[0].y + pt[1].y; + center.x = pt[1].x + pt[2].x + 2; + center.y = pt[1].y + pt[2].y + 2; + next[5].x = pt[2].x + pt[3].x; + next[5].y = pt[2].y + pt[3].y; + next[2].x = next[1].x + center.x; + next[2].y = next[1].y + center.y; + next[4].x = center.x + next[5].x; + next[4].y = center.y + next[5].y; + next[3].x = (next[2].x + next[4].x - 1) >> 3; + next[3].y = (next[2].y + next[4].y - 1) >> 3; + next[2].x >>= 2; + next[2].y >>= 2; + next[4].x >>= 2; + next[4].y >>= 2; + next[1].x >>= 1; + next[1].y >>= 1; + next[5].x >>= 1; + next[5].y >>= 1; + next[0] = pt[0]; + next[6] = pt[3]; + + Vector next_deriv[5], center_deriv; + next_deriv[0].x = deriv[0].x / 2; + next_deriv[0].y = de |