summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--libass/ass_drawing.c58
-rw-r--r--libass/ass_outline.c1170
-rw-r--r--libass/ass_outline.h7
-rw-r--r--libass/ass_parse.c35
-rw-r--r--libass/ass_parse.h3
-rw-r--r--libass/ass_render.c134
-rw-r--r--libass/ass_render.h3
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 = deriv[0].y / 2;
+ center_deriv.x = deriv[1].x / 2;
+ center_deriv.y = deriv[1].y / 2;
+ next_deriv[4].x = deriv[2].x / 2;
+ next_deriv[4].y = deriv[2].y / 2;
+ next_deriv[1].x = (next_deriv[0].x + center_deriv.x) / 2;
+ next_deriv[1].y = (next_deriv[0].y + center_deriv.y) / 2;
+ next_deriv[3].x = (center_deriv.x + next_deriv[4].x) / 2;
+ next_deriv[3].y = (center_deriv.y + next_deriv[4].y) / 2;
+ next_deriv[2].x = (next_deriv[1].x + next_deriv[3].x) / 2;
+ next_deriv[2].y = (next_deriv[1].y + next_deriv[3].y) / 2;
+
+ double len = vec_len(next_deriv[2]);
+ if (len < str->min_len) { // check degenerate case
+ Normal next_normal[4];
+ next_normal[0].v = normal[0].v;
+ ne