From a0bf40896a4295964bba56dc7edfa020af761f5e Mon Sep 17 00:00:00 2001 From: "Dr.Smile" Date: Sun, 17 Sep 2017 03:36:29 +0300 Subject: Switch to more efficient representation of outlines --- libass/ass_drawing.c | 30 +-- libass/ass_outline.c | 510 +++++++++++++++++++++++++----------------------- libass/ass_outline.h | 33 +++- libass/ass_rasterizer.c | 176 ++++------------- libass/ass_render.c | 22 ++- 5 files changed, 355 insertions(+), 416 deletions(-) (limited to 'libass') diff --git a/libass/ass_drawing.c b/libass/ass_drawing.c index 4deb19a..64f7b29 100644 --- a/libass/ass_drawing.c +++ b/libass/ass_drawing.c @@ -30,7 +30,7 @@ #include "ass_font.h" #define GLYPH_INITIAL_POINTS 100 -#define GLYPH_INITIAL_CONTOURS 5 +#define GLYPH_INITIAL_SEGMENTS 100 /* * \brief Prepare drawing for parsing. This just sets a few parameters. @@ -53,8 +53,8 @@ static void drawing_finish(ASS_Drawing *drawing, bool raw_mode) if (drawing->library) ass_msg(drawing->library, MSGL_V, - "Parsed drawing with %d points and %d contours", ol->n_points, - ol->n_contours); + "Parsed drawing with %d points and %d segments", + ol->n_points, ol->n_segments); if (raw_mode) return; @@ -230,10 +230,10 @@ static bool drawing_add_curve(ASS_Drawing *drawing, ASS_DrawingToken *token, } 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); + outline_add_point(&drawing->outline, p[0], 0)) && + outline_add_point(&drawing->outline, p[1], 0) && + outline_add_point(&drawing->outline, p[2], 0) && + outline_add_point(&drawing->outline, p[3], OUTLINE_CUBIC_SPLINE); } /* @@ -250,7 +250,7 @@ ASS_Drawing *ass_drawing_new(ASS_Library *lib) drawing->scale_x = 1.; drawing->scale_y = 1.; - if (!outline_alloc(&drawing->outline, GLYPH_INITIAL_POINTS, GLYPH_INITIAL_CONTOURS)) { + if (!outline_alloc(&drawing->outline, GLYPH_INITIAL_POINTS, GLYPH_INITIAL_SEGMENTS)) { free(drawing); return NULL; } @@ -314,6 +314,8 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, bool raw_mode) pen = token->point; translate_point(drawing, &pen); if (started) { + if (!outline_add_segment(&drawing->outline, OUTLINE_LINE_SEGMENT)) + goto error; if (!outline_close_contour(&drawing->outline)) goto error; started = false; @@ -323,9 +325,9 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, bool raw_mode) case TOKEN_LINE: { ASS_Vector to = token->point; translate_point(drawing, &to); - if (!started && !outline_add_point(&drawing->outline, pen, FT_CURVE_TAG_ON)) + if (!started && !outline_add_point(&drawing->outline, pen, 0)) goto error; - if (!outline_add_point(&drawing->outline, to, FT_CURVE_TAG_ON)) + if (!outline_add_point(&drawing->outline, to, OUTLINE_LINE_SEGMENT)) goto error; started = true; token = token->next; @@ -360,8 +362,12 @@ ASS_Outline *ass_drawing_parse(ASS_Drawing *drawing, bool raw_mode) } // Close the last contour - if (started && !outline_close_contour(&drawing->outline)) - goto error; + if (started) { + if (!outline_add_segment(&drawing->outline, OUTLINE_LINE_SEGMENT)) + goto error; + if (!outline_close_contour(&drawing->outline)) + goto error; + } drawing_finish(drawing, raw_mode); drawing_free_tokens(drawing->tokens); diff --git a/libass/ass_outline.c b/libass/ass_outline.c index c4aa510..85ceff8 100644 --- a/libass/ass_outline.c +++ b/libass/ass_outline.c @@ -24,29 +24,27 @@ -bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_contours) +bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_segments) { - outline->contours = malloc(sizeof(size_t) * n_contours); outline->points = malloc(sizeof(ASS_Vector) * n_points); - outline->tags = malloc(n_points); - if (!outline->contours || !outline->points || !outline->tags) { + outline->segments = malloc(n_segments); + if (!outline->points || !outline->segments) { outline_free(outline); return false; } - outline->max_contours = n_contours; outline->max_points = n_points; + outline->max_segments = n_segments; return true; } static void outline_clear(ASS_Outline *outline) { - outline->contours = NULL; outline->points = NULL; - outline->tags = NULL; + outline->segments = NULL; - outline->n_contours = outline->max_contours = 0; outline->n_points = outline->max_points = 0; + outline->n_segments = outline->max_segments = 0; } bool outline_convert(ASS_Outline *outline, const FT_Outline *source) @@ -56,27 +54,151 @@ bool outline_convert(ASS_Outline *outline, const FT_Outline *source) return true; } - if (!outline_alloc(outline, source->n_points, source->n_contours)) + if (!outline_alloc(outline, 2 * source->n_points, source->n_points)) return false; - short start = 0; - outline->n_contours = outline->n_points = 0; - for (int i = 0; i < source->n_contours; i++) { - size_t n = source->contours[i] - start + 1; + enum Status { + S_ON, S_Q, S_C1, S_C2 + }; + + outline->n_points = outline->n_segments = 0; + for (size_t i = 0, j = 0; i < source->n_contours; i++) { + ASS_Vector pt; + bool skip_last = false; + enum Status st; + + int last = source->contours[i]; + if (j > last || last >= source->n_points) + goto fail; + // skip degenerate 2-point contours from broken fonts - if (n >= 3) { - for (size_t k = 0; k < n; k++) { - outline->points[outline->n_points + k].x = source->points[start + k].x; - outline->points[outline->n_points + k].y = -source->points[start + k].y; + if (last - j < 2) { + j = last + 1; + continue; + } + + switch (FT_CURVE_TAG(source->tags[j])) { + case FT_CURVE_TAG_ON: + st = S_ON; + break; + + case FT_CURVE_TAG_CONIC: + pt.x = source->points[last].x; + pt.y = -source->points[last].y; + switch (FT_CURVE_TAG(source->tags[last])) { + case FT_CURVE_TAG_ON: + skip_last = true; + break; + + case FT_CURVE_TAG_CONIC: + pt.x = (pt.x + source->points[j].x) >> 1; + pt.y = (pt.y - source->points[j].y) >> 1; + break; + + default: + goto fail; + } + outline->points[outline->n_points++] = pt; + st = S_Q; + break; + + default: + goto fail; + } + pt.x = source->points[j].x; + pt.y = -source->points[j].y; + outline->points[outline->n_points++] = pt; + + for (j++; j <= last; j++) { + switch (FT_CURVE_TAG(source->tags[j])) { + case FT_CURVE_TAG_ON: + switch (st) { + case S_ON: + outline->segments[outline->n_segments++] = OUTLINE_LINE_SEGMENT; + break; + + case S_Q: + outline->segments[outline->n_segments++] = OUTLINE_QUADRATIC_SPLINE; + break; + + case S_C2: + outline->segments[outline->n_segments++] = OUTLINE_CUBIC_SPLINE; + break; + + default: + goto fail; + } + st = S_ON; + break; + + case FT_CURVE_TAG_CONIC: + switch (st) { + case S_ON: + st = S_Q; + break; + + case S_Q: + outline->segments[outline->n_segments++] = OUTLINE_QUADRATIC_SPLINE; + pt.x = (pt.x + source->points[j].x) >> 1; + pt.y = (pt.y - source->points[j].y) >> 1; + outline->points[outline->n_points++] = pt; + break; + + default: + goto fail; + } + break; + + case FT_CURVE_TAG_CUBIC: + switch (st) { + case S_ON: + st = S_C1; + break; + + case S_C1: + st = S_C2; + break; + + default: + goto fail; + } + break; + + default: + goto fail; } - memcpy(outline->tags + outline->n_points, source->tags + start, n); + pt.x = source->points[j].x; + pt.y = -source->points[j].y; + outline->points[outline->n_points++] = pt; + } - outline->n_points += n; - outline->contours[outline->n_contours++] = outline->n_points - 1; + switch (st) { + case S_ON: + if (skip_last) { + outline->n_points--; + break; + } + outline->segments[outline->n_segments++] = OUTLINE_LINE_SEGMENT; + break; + + case S_Q: + outline->segments[outline->n_segments++] = OUTLINE_QUADRATIC_SPLINE; + break; + + case S_C2: + outline->segments[outline->n_segments++] = OUTLINE_CUBIC_SPLINE; + break; + + default: + goto fail; } - start = source->contours[i] + 1; + outline->segments[outline->n_segments - 1] |= OUTLINE_CONTOUR_END; } return true; + +fail: + outline_free(outline); + return false; } bool outline_copy(ASS_Outline *outline, const ASS_Outline *source) @@ -86,14 +208,13 @@ bool outline_copy(ASS_Outline *outline, const ASS_Outline *source) return true; } - if (!outline_alloc(outline, source->n_points, source->n_contours)) + if (!outline_alloc(outline, source->n_points, source->n_segments)) return false; - memcpy(outline->contours, source->contours, sizeof(size_t) * source->n_contours); memcpy(outline->points, source->points, sizeof(ASS_Vector) * source->n_points); - memcpy(outline->tags, source->tags, source->n_points); - outline->n_contours = source->n_contours; + memcpy(outline->segments, source->segments, source->n_segments); outline->n_points = source->n_points; + outline->n_segments = source->n_segments; return true; } @@ -102,9 +223,8 @@ void outline_free(ASS_Outline *outline) if (!outline) return; - free(outline->contours); free(outline->points); - free(outline->tags); + free(outline->segments); outline_clear(outline); } @@ -112,20 +232,35 @@ void outline_free(ASS_Outline *outline) /* * \brief Add a single point to a contour. + * Also adds outline segment if segment parameter is nonzero. */ -bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char tag) +bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char segment) { 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 !segment || outline_add_segment(outline, segment); +} + +/* + * \brief Add a segment to a contour. + */ +bool outline_add_segment(ASS_Outline *outline, char segment) +{ + if (outline->n_segments >= outline->max_segments) { + size_t new_size = 2 * outline->max_segments; + if (!ASS_REALLOC_ARRAY(outline->segments, new_size)) + return false; + outline->max_segments = new_size; + } + outline->segments[outline->n_segments] = segment; + outline->n_segments++; return true; } @@ -134,14 +269,9 @@ bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char tag) */ 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++; + assert(outline->n_segments); + assert(!(outline->segments[outline->n_segments - 1] & ~OUTLINE_COUNT_MASK)); + outline->segments[outline->n_segments - 1] |= OUTLINE_CONTOUR_END; return true; } @@ -241,6 +371,7 @@ typedef struct { typedef struct { ASS_Outline *result[2]; // result outlines + size_t contour_first[2]; // start position of last contours double xbord, ybord; // border sizes double xscale, yscale; // inverse border sizes int eps; // allowable error in coordinate space @@ -251,8 +382,8 @@ typedef struct { int first_skip, last_skip; // normal at first and last point ASS_DVector first_normal, last_normal; - // first and last point of current contour - ASS_Vector first_point, last_point; + // first point of current contour + ASS_Vector first_point; // cosinus of maximal angle that do not require cap double merge_cos; @@ -298,24 +429,24 @@ static inline double vec_len(ASS_DVector vec) * \param str stroker state * \param pt source point * \param offs offset in normal space - * \param tag outline tag flag + * \param segment outline segment type * \param dir destination outline flags * \return false on allocation failure */ static bool emit_point(StrokerState *str, ASS_Vector pt, - ASS_DVector offs, char tag, int dir) + ASS_DVector offs, char segment, int dir) { int32_t dx = (int32_t) (str->xbord * offs.x); int32_t dy = (int32_t) (str->ybord * offs.y); if (dir & 1) { ASS_Vector res = { pt.x + dx, pt.y + dy }; - if (!outline_add_point(str->result[0], res, tag)) + if (!outline_add_point(str->result[0], res, segment)) return false; } if (dir & 2) { ASS_Vector res = { pt.x - dx, pt.y - dy }; - if (!outline_add_point(str->result[1], res, tag)) + if (!outline_add_point(str->result[1], res, segment)) return false; } return true; @@ -337,16 +468,12 @@ static void fix_first_point(StrokerState *str, ASS_Vector pt, if (dir & 1) { ASS_Vector res = { pt.x + dx, pt.y + dy }; ASS_Outline *ol = str->result[0]; - size_t first = ol->n_contours ? - ol->contours[ol->n_contours - 1] + 1 : 0; - ol->points[first] = res; + ol->points[str->contour_first[0]] = res; } if (dir & 2) { ASS_Vector res = { pt.x - dx, pt.y - dy }; ASS_Outline *ol = str->result[1]; - size_t first = ol->n_contours ? - ol->contours[ol->n_contours - 1] + 1 : 0; - ol->points[first] = res; + ol->points[str->contour_first[1]] = res; } } @@ -371,8 +498,8 @@ static bool process_arc(StrokerState *str, ASS_Vector pt, 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); + return emit_point(str, pt, normal0, OUTLINE_QUADRATIC_SPLINE, dir) && + emit_point(str, pt, center, 0, dir); } /** @@ -477,10 +604,10 @@ static bool start_segment(StrokerState *str, ASS_Vector pt, 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)) + if (!emit_point(str, pt, prev, OUTLINE_LINE_SEGMENT, ~str->last_skip & skip_dir)) return false; ASS_DVector zero_normal = {0, 0}; - if (!emit_point(str, pt, zero_normal, FT_CURVE_TAG_ON, skip_dir)) + if (!emit_point(str, pt, zero_normal, OUTLINE_LINE_SEGMENT, skip_dir)) return false; } str->last_skip = skip_dir; @@ -492,10 +619,10 @@ static bool start_segment(StrokerState *str, ASS_Vector pt, /** * \brief Same as emit_point() but also updates skip flags */ -static bool emit_first_point(StrokerState *str, ASS_Vector pt, int dir) +static bool emit_first_point(StrokerState *str, ASS_Vector pt, char segment, int dir) { str->last_skip &= ~dir; - return emit_point(str, pt, str->last_normal, FT_CURVE_TAG_ON, dir); + return emit_point(str, pt, str->last_normal, segment, dir); } /** @@ -510,7 +637,7 @@ static bool prepare_skip(StrokerState *str, ASS_Vector 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)) + else if (!emit_point(str, pt, str->last_normal, OUTLINE_LINE_SEGMENT, ~str->last_skip & dir)) return false; str->last_skip |= dir; return true; @@ -519,26 +646,26 @@ static bool prepare_skip(StrokerState *str, ASS_Vector pt, int dir, bool first) /** * \brief Process source line segment * \param str stroker state - * \param pt end point of the line segment + * \param pt0 start point of the line segment + * \param pt1 end point of the line segment * \param dir destination outline flags * \return false on allocation failure */ -static bool add_line(StrokerState *str, ASS_Vector pt, int dir) +static bool add_line(StrokerState *str, ASS_Vector pt0, ASS_Vector pt1, int dir) { - int32_t dx = pt.x - str->last_point.x; - int32_t dy = pt.y - str->last_point.y; + int32_t dx = pt1.x - pt0.x; + int32_t dy = pt1.y - pt0.y; if (dx > -str->eps && dx < str->eps && dy > -str->eps && dy < str->eps) return true; ASS_DVector deriv = { dy * str->yscale, -dx * str->xscale }; double scale = 1 / vec_len(deriv); ASS_DVector normal = { deriv.x * scale, deriv.y * scale }; - if (!start_segment(str, str->last_point, normal, dir)) + if (!start_segment(str, pt0, normal, dir)) return false; - if (!emit_first_point(str, str->last_point, dir)) + if (!emit_first_point(str, pt0, OUTLINE_LINE_SEGMENT, dir)) return false; str->last_normal = normal; - str->last_point = pt; return true; } @@ -603,13 +730,13 @@ static bool process_quadratic(StrokerState *str, const ASS_Vector *pt, return false; if (f0 < 0 || f1 < 0) { ASS_DVector 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)) + if (!emit_point(str, pt[0], zero_normal, OUTLINE_LINE_SEGMENT, skip_dir) || + !emit_point(str, pt[2], zero_normal, OUTLINE_LINE_SEGMENT, skip_dir)) return false; } else { double mul = f0 / abs_s; ASS_DVector offs = { normal[0].v.x * mul, normal[0].v.y * mul }; - if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir)) + if (!emit_point(str, pt[0], offs, OUTLINE_LINE_SEGMENT, skip_dir)) return false; } dir &= ~skip_dir; @@ -625,9 +752,9 @@ static bool process_quadratic(StrokerState *str, const ASS_Vector *pt, ASS_DVector result; if (check_dir && estimate_quadratic_error(str, c, s, normal, &result)) { - if (!emit_first_point(str, pt[0], check_dir)) + if (!emit_first_point(str, pt[0], OUTLINE_QUADRATIC_SPLINE, check_dir)) return false; - if (!emit_point(str, pt[1], result, FT_CURVE_TAG_CONIC, check_dir)) + if (!emit_point(str, pt[1], result, 0, check_dir)) return false; dir &= ~check_dir; if (!dir) { @@ -660,12 +787,12 @@ static bool process_quadratic(StrokerState *str, const ASS_Vector *pt, double len = vec_len(next_deriv[1]); if (len < str->min_len) { // check degenerate case - if (!emit_first_point(str, next[0], dir)) + if (!emit_first_point(str, next[0], OUTLINE_LINE_SEGMENT, 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); + return emit_point(str, next[2], normal[1].v, OUTLINE_LINE_SEGMENT, dir); } double scale = 1 / len; @@ -690,12 +817,12 @@ static bool add_quadratic(StrokerState *str, const ASS_Vector *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); + return add_line(str, pt[0], 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); + return add_line(str, pt[0], pt[2], dir); ASS_DVector deriv[2] = { { dy0 * str->yscale, -dx0 * str->xscale }, @@ -709,12 +836,8 @@ static bool add_quadratic(StrokerState *str, const ASS_Vector *pt, int dir) }; 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; + return start_segment(str, pt[0], normal[0].v, dir) && + process_quadratic(str, pt, deriv, normal, dir, first); } @@ -889,13 +1012,13 @@ static bool process_cubic(StrokerState *str, const ASS_Vector *pt, return false; if (f0 < 0 || f1 < 0) { ASS_DVector 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)) + if (!emit_point(str, pt[0], zero_normal, OUTLINE_LINE_SEGMENT, skip_dir) || + !emit_point(str, pt[3], zero_normal, OUTLINE_LINE_SEGMENT, skip_dir)) return false; } else { double mul = f0 / abs_s; ASS_DVector offs = { normal[0].v.x * mul, normal[0].v.y * mul }; - if (!emit_point(str, pt[0], offs, FT_CURVE_TAG_ON, skip_dir)) + if (!emit_point(str, pt[0], offs, OUTLINE_LINE_SEGMENT, skip_dir)) return false; } dir &= ~skip_dir; @@ -957,10 +1080,10 @@ static bool process_cubic(StrokerState *str, const ASS_Vector *pt, 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)) + if (!emit_first_point(str, pt[0], OUTLINE_CUBIC_SPLINE, 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)) + if (!emit_point(str, pt[1], result[0], 0, check_dir) || + !emit_point(str, pt[2], result[1], 0, check_dir)) return false; dir &= ~check_dir; if (!dir) { @@ -1042,7 +1165,7 @@ static bool process_cubic(StrokerState *str, const ASS_Vector *pt, } if (len1 < str->min_len) { - if (!emit_first_point(str, next[0], dir)) + if (!emit_first_point(str, next[0], OUTLINE_LINE_SEGMENT, dir)) return false; } else { if (!process_cubic(str, next + 0, next_deriv + 0, next_normal + 0, dir, first)) @@ -1051,7 +1174,7 @@ static bool process_cubic(StrokerState *str, const ASS_Vector *pt, if (!start_segment(str, next[2], next_normal[2].v, dir)) return false; if (len2 < str->min_len) { - if (!emit_first_point(str, next[3], dir)) + if (!emit_first_point(str, next[3], OUTLINE_LINE_SEGMENT, dir)) return false; } else { if (!process_cubic(str, next + 3, next_deriv + 2, next_normal + 2, dir, false)) @@ -1087,7 +1210,7 @@ static bool add_cubic(StrokerState *str, const ASS_Vector *pt, int dir) dx0 = pt[2].x - pt[0].x; dy0 = pt[2].y - pt[0].y; if (dx0 > -str->eps && dx0 < str->eps && dy0 > -str->eps && dy0 < str->eps) - return add_line(str, pt[3], dir); + return add_line(str, pt[0], pt[3], dir); flags ^= 1; } @@ -1097,12 +1220,12 @@ static bool add_cubic(StrokerState *str, const ASS_Vector *pt, int dir) dx2 = pt[3].x - pt[1].x; dy2 = pt[3].y - pt[1].y; if (dx2 > -str->eps && dx2 < str->eps && dy2 > -str->eps && dy2 < str->eps) - return add_line(str, pt[3], dir); + return add_line(str, pt[0], pt[3], dir); flags ^= 4; } if (flags == 12) - return add_line(str, pt[3], dir); + return add_line(str, pt[0], pt[3], dir); int32_t dx1 = pt[flags >> 2].x - pt[flags & 3].x; int32_t dy1 = pt[flags >> 2].y - pt[flags & 3].y; @@ -1120,34 +1243,31 @@ static bool add_cubic(StrokerState *str, const ASS_Vector *pt, int dir) }; bool first = str->contour_start; - if (!start_segment(str, pt[0], normal[0].v, dir)) - return false; - if (!process_cubic(str, pt, deriv, normal, dir, first)) - return false; - str->last_point = pt[3]; - return true; + return start_segment(str, pt[0], normal[0].v, dir) && + process_cubic(str, pt, deriv, normal, dir, first); } /** * \brief Process contour closing * \param str stroker state + * \param last_point last contour point * \param dir destination outline flags * \return false on allocation failure */ -static bool close_contour(StrokerState *str, int dir) +static bool close_contour(StrokerState *str, ASS_Vector last_point, int dir) { if (str->contour_start) { if ((dir & 3) == 3) dir = 1; - if (!draw_circle(str, str->last_point, dir)) + if (!draw_circle(str, last_point, dir)) return false; } else { - if (!add_line(str, str->first_point, dir)) + if (!add_line(str, last_point, str->first_point, dir)) return false; if (!start_segment(str, str->first_point, str->first_normal, dir)) return false; - if (!emit_point(str, str->first_point, str->first_normal, FT_CURVE_TAG_ON, + if (!emit_point(str, str->first_point, str->first_normal, OUTLINE_LINE_SEGMENT, ~str->last_skip & dir & str->first_skip)) return false; if (str->last_normal.x != str->first_normal.x || @@ -1160,6 +1280,8 @@ static bool close_contour(StrokerState *str, int dir) return false; if ((dir & 2) && !outline_close_contour(str->result[1])) return false; + str->contour_first[0] = str->result[0]->n_points; + str->contour_first[1] = str->result[1]->n_points; return true; } @@ -1177,15 +1299,18 @@ static bool close_contour(StrokerState *str, int dir) bool outline_stroke(ASS_Outline *result, ASS_Outline *result1, const ASS_Outline *path, int xbord, int ybord, int eps) { + const int dir = 3; int rad = FFMAX(xbord, ybord); assert(rad >= eps); - result->n_contours = result->n_points = 0; - result1->n_contours = result1->n_points = 0; + result->n_points = result->n_segments = 0; + result1->n_points = result1->n_segments = 0; StrokerState str; str.result[0] = result; str.result[1] = result1; + str.contour_first[0] = 0; + str.contour_first[1] = 0; str.xbord = xbord; str.ybord = ybord; str.xscale = 1.0 / FFMAX(eps, xbord); @@ -1202,165 +1327,54 @@ bool outline_stroke(ASS_Outline *result, ASS_Outline *result1, str.err_c = 390 * rel_err * rel_err; str.err_a = e; - enum Status { - S_ON, S_Q, S_C1, S_C2 - }; - - const int dir = 3; - for (size_t i = 0, j = 0; i < path->n_contours; i++) { - ASS_Vector start, p[4]; - int process_end = 1; - enum Status st; - - int last = path->contours[i]; - if (j > last) - return false; - - if (path->points[j].x < -(1 << 28) || path->points[j].x >= (1 << 28)) + for (size_t i = 0; i < path->n_points; i++) { + if (path->points[i].x < OUTLINE_MIN || path->points[i].x > OUTLINE_MAX) return false; - if (path->points[j].y < -(1 << 28) || path->points[j].y >= (1 << 28)) + if (path->points[i].y < OUTLINE_MIN || path->points[i].y > OUTLINE_MAX) return false; + } - switch (FT_CURVE_TAG(path->tags[j])) { - case FT_CURVE_TAG_ON: - p[0] = path->points[j]; - start = p[0]; - st = S_ON; - break; - - case FT_CURVE_TAG_CONIC: - switch (FT_CURVE_TAG(path->tags[last])) { - case FT_CURVE_TAG_ON: - p[0] = path->points[last]; - p[1] = path->points[j]; - process_end = 0; - start = p[0]; - st = S_Q; - break; + ASS_Vector *start = path->points, *cur = start; + for (size_t i = 0; i < path->n_segments; i++) { + int n = path->segments[i] & OUTLINE_COUNT_MASK; + cur += n; - case FT_CURVE_TAG_CONIC: - p[1] = path->points[j]; - p[0].x = (p[1].x + path->points[last].x) >> 1; - p[0].y = (p[1].y + path->points[last].y) >> 1; - start = p[0]; - st = S_Q; - break; + ASS_Vector *end = cur, p[4]; + if (path->segments[i] & OUTLINE_CONTOUR_END) { + end = start; + start = cur; + } - default: + switch (n) { + case OUTLINE_LINE_SEGMENT: + if (!add_line(&str, cur[-1], *end, dir)) return false; - } break; - default: - return false; - } - str.last_point = start; - - for (j++; j <= last; j++) { - if (path->points[j].x < -(1 << 28) || path->points[j].x >= (1 << 28)) - return false; - if (path->points[j].y < -(1 << 28) || path->points[j].y >= (1 << 28)) + case OUTLINE_QUADRATIC_SPLINE: + p[0] = cur[-2]; + p[1] = cur[-1]; + p[2] = *end; + if (!add_quadratic(&str, p, dir)) return false; + break; - switch (FT_CURVE_TAG(path->tags[j])) { - case FT_CURVE_TAG_ON: - switch (st) { - case S_ON: - p[1] = path->points[j]; - if (!add_line(&str, p[1], dir)) - return false; - p[0] = p[1]; - break; - - case S_Q: - p[2] = path->points[j]; - if (!add_quadratic(&str, p, dir)) - return false; - p[0] = p[2]; - st = S_ON; - break; - - case S_C2: - p[3] = path->points[j]; - if (!add_cubic(&str, p, dir)) - return false; - p[0] = p[3]; - st = S_ON; - break; - - default: - return false; - } - break; - - case FT_CURVE_TAG_CONIC: - switch (st) { - case S_ON: - p[1] = path->points[j]; - st = S_Q; - break; - - case S_Q: - p[3] = path->points[j]; - p[2].x = (p[1].x + p[3].x) >> 1; - p[2].y = (p[1].y + p[3].y) >> 1; - if (!add_quadratic(&str, p, dir)) - return false; - p[0] = p[2]; - p[1] = p[3]; - break; - - default: - return false; - } - break; - - case FT_CURVE_TAG_CUBIC: - switch (st) { - case S_ON: - p[1] = path->points[j]; - st = S_C1; - break; - - case S_C1: - p[2] = path->points[j]; - st = S_C2; - break; - - default: - return false; - } - break; - - default: + case OUTLINE_CUBIC_SPLINE: + p[0] = cur[-3]; + p[1] = cur[-2]; + p[2] = cur[-1]; + p[3] = *end; + if (!add_cubic(&str, p, dir)) return false; - } - } - - if (process_end) - switch (st) { - case S_ON: - if (!add_line(&str, start, dir)) - return false; - break; - - case S_Q: - p[2] = start; - if (!add_quadratic(&str, p, dir)) - return false; - break; + break; - case S_C2: - p[3] = start; - if (!add_cubic(&str, p, dir)) - return false; - break; + default: + return false; + } - default: - return false; - } - if (!close_contour(&str, dir)) + if (start == cur && !close_contour(&str, *end, dir)) return false; } + assert(start == cur && cur == path->points + path->n_points); return true; } diff --git a/libass/ass_outline.h b/libass/ass_outline.h index 7e71b8a..4ee21d1 100644 --- a/libass/ass_outline.h +++ b/libass/ass_outline.h @@ -37,20 +37,41 @@ typedef struct { int32_t x_min, y_min, x_max, y_max; } ASS_Rect; -typedef struct ass_outline { - size_t n_contours, max_contours; - size_t *contours; +/* + * Outline represented with array of points and array of segments. + * Segment here is spline of order 1 (line), 2 (quadratic) or 3 (cubic). + * Each segment owns number of points equal to its order in point array + * and uses first point owned by the next segment as last point. + * Last segment in each contour instead of the next segment point uses + * point owned by the first segment in that contour. Correspondingly + * total number of points is equal to the sum of spline orders of all segments. + */ + +enum { + OUTLINE_LINE_SEGMENT = 1, // line segment + OUTLINE_QUADRATIC_SPLINE = 2, // quadratic spline + OUTLINE_CUBIC_SPLINE = 3, // cubic spline + OUTLINE_COUNT_MASK = 3, // spline order mask + OUTLINE_CONTOUR_END = 4 // last segment in contour flag +}; + +typedef struct { size_t n_points, max_points; + size_t n_segments, max_segments; ASS_Vector *points; - char *tags; + char *segments; } ASS_Outline; -bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_contours); +#define OUTLINE_MIN (-((int32_t) 1 << 28)) +#define OUTLINE_MAX (((int32_t) 1 << 28) - 1) + +bool outline_alloc(ASS_Outline *outline, size_t n_points, size_t n_segments); bool outline_convert(ASS_Outline *outline, const FT_Outline *source); bool outline_copy(ASS_Outline *outline, const ASS_Outline *source); void outline_free(ASS_Outline *outline); -bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char tag); +bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char segment); +bool outline_add_segment(ASS_Outline *outline, char segment); bool outline_close_contour(ASS_Outline *outline); void outline_translate(const ASS_Outline *outline, int32_t dx, int32_t dy); diff --git a/libass/ass_rasterizer.c b/libass/ass_rasterizer.c index 97bebb2..1af4509 100644 --- a/libass/ass_rasterizer.c +++ b/libass/ass_rasterizer.c @@ -263,167 +263,59 @@ static bool add_cubic(RasterizerData *rst, const ASS_Vector *pt) bool rasterizer_set_outline(RasterizerData *rst, const ASS_Outline *path, bool extra) { - enum Status { - S_ON, S_Q, S_C1, S_C2 - }; - if (!extra) { rst->x_min = rst->y_min = INT32_MAX; rst->x_max = rst->y_max = INT32_MIN; rst->n_first = 0; } rst->size[0] = rst->n_first; - for (size_t i = 0, j = 0; i < path->n_contours; i++) { - ASS_Vector start, p[4]; - int process_end = 1; - enum Status st; - - int last = path->contours[i]; - if (j > last) - return false; - if (path->points[j].x < -(1 << 28) || path->points[j].x >= (1 << 28)) + for (size_t i = 0; i < path->n_points; i++) { + if (path->points[i].x < OUTLINE_MIN || path->points[i].x > OUTLINE_MAX) return false; - if (path->points[j].y < -(1 << 28) || path->points[j].y >= (1 << 28)) + if (path->points[i].y < OUTLINE_MIN || path->points[i].y > OUTLINE_MAX) return false; + } - switch (FT_CURVE_TAG(path->tags[j])) { - case FT_CURVE_TAG_ON: - p[0] = path->points[j]; - start = p[0]; - st = S_ON; - break; - - case FT_CURVE_TAG_CONIC: - switch (FT_CURVE_TAG(path->tags[last])) { - case FT_CURVE_TAG_ON: - p[0] = path->points[last]; - p[1] = path->points[j]; - process_end = 0; - st = S_Q; - break; - - case FT_CURVE_TAG_CONIC: - p[1] = path->points[j]; - p[0].x = (p[1].x + path->points[last].x) >> 1; - p[0].y = (p[1].y + path->points[last].y) >> 1; - start = p[0]; - st = S_Q; - break; - - default: - return false; - } - break; + ASS_Vector *start = path->points, *cur = start; + for (size_t i = 0; i < path->n_segments; i++) { + int n = path->segments[i] & OUTLINE_COUNT_MASK; + cur += n; - default: - return false; + ASS_Vector *end = cur, p[4]; + if (path->segments[i] & OUTLINE_CONTOUR_END) { + end = start; + start = cur; } - for (j++; j <= last; j++) { - if (path->points[j].x < -(1 << 28) || path->points[j].x >= (1 << 28)) - return false; - if (path->points[j].y < -(1 << 28) || path->points[j].y >= (1 << 28)) + switch (n) { + case OUTLINE_LINE_SEGMENT: + if (!add_line(rst, cur[-1], *end)) return false; + break; - switch (FT_CURVE_TAG(path->tags[j])) { - case FT_CURVE_TAG_ON: - switch (st) { - case S_ON: - p[1] = path->points[j]; - if (!add_line(rst, p[0], p[1])) - return false; - p[0] = p[1]; - break; - - case S_Q: - p[2] = path->points[j]; - if (!add_quadratic(rst, p)) - return false; - p[0] = p[2]; - st = S_ON; - break; - - case S_C2: - p[3] = path->points[j]; - if (!add_cubic(rst, p)) - return false; - p[0] = p[3]; - st = S_ON; - break; - - default: - return false; - } - break; - - case FT_CURVE_TAG_CONIC: - switch (st) { - case S_ON: - p[1] = path->points[j]; - st = S_Q; - break; - - case S_Q: - p[3] = path->points[j]; - p[2].x = (p[1].x + p[3].x) >> 1; - p[2].y = (p[1].y + p[3].y) >> 1; - if (!add_quadratic(rst, p)) - return false; - p[0] = p[2]; - p[1] = p[3]; - break; - - default: - return false; - } - break; - - case FT_CURVE_TAG_CUBIC: - switch (st) { - case S_ON: - p[1] = path->points[j]; - st = S_C1; - break; - - case S_C1: - p[2] = path->points[j]; - st = S_C2; - break; - - default: - return false; - } - break; - - default: + case OUTLINE_QUADRATIC_SPLINE: + p[0] = cur[-2]; + p[1] = cur[-1]; + p[2] = *end; + if (!add_quadratic(rst, p)) return false; - } - } + break; - if (process_end) - switch (st) { - case S_ON: - if (!add_line(rst, p[0], start)) - return false; - break; - - case S_Q: - p[2] = start; - if (!add_quadratic(rst, p)) - return false; - break; - - case S_C2: - p[3] = start; - if (!add_cubic(rst, p)) - return false; - break; - - default: + case OUTLINE_CUBIC_SPLINE: + p[0] = cur[-3]; + p[1] = cur[-2]; + p[2] = cur[-1]; + p[3] = *end; + if (!add_cubic(rst, p)) return false; - } + break; + + default: + return false; + } } + assert(start == cur && cur == path->points + path->n_points); for (size_t k = rst->n_first; k < rst->size[0]; k++) { rst->x_min = FFMIN(rst->x_min, rst->linebuf[0][k].x_min); diff --git a/libass/ass_render.c b/libass/ass_render.c index c340e1a..9708aa0 100644 --- a/libass/ass_render.c +++ b/libass/ass_render.c @@ -943,14 +943,20 @@ static void draw_opaque_box(ASS_Renderer *render_priv, GlyphInfo *info, { .x = -sx, .y = desc + sy }, }; - ol->n_points = ol->n_contours = 0; - if (!outline_alloc(ol, 4, 1)) + const char segments[4] = { + OUTLINE_LINE_SEGMENT, + OUTLINE_LINE_SEGMENT, + OUTLINE_LINE_SEGMENT, + OUTLINE_LINE_SEGMENT | OUTLINE_CONTOUR_END + }; + + ol->n_points = ol->n_segments = 0; + if (!outline_alloc(ol, 4, 4)) return; - for (int i = 0; i < 4; ++i) { - ol->points[ol->n_points] = points[i]; - ol->tags[ol->n_points++] = FT_CURVE_TAG_ON; + for (int i = 0; i < 4; i++) { + ol->points[ol->n_points++] = points[i]; + ol->segments[ol->n_segments++] = segments[i]; } - ol->contours[ol->n_contours++] = ol->n_points - 1; } /** @@ -1088,8 +1094,8 @@ get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info) int xbord = double_to_d6(info->border_x * priv->border_scale); int ybord = double_to_d6(info->border_y * priv->border_scale); if(xbord >= eps || ybord >= eps) { - outline_alloc(&val->border[0], 2 * val->outline.n_points, val->outline.n_contours); - outline_alloc(&val->border[1], 2 * val->outline.n_points, val->outline.n_contours); + outline_alloc(&val->border[0], 2 * val->outline.n_points, 2 * val->outline.n_segments); + outline_alloc(&val->border[1], 2 * val->outline.n_points, 2 * val->outline.n_segments); if (!val->border[0].max_points || !val->border[1].max_points || !outline_stroke(&val->border[0], &val->border[1], &val->outline, xbord, ybord, eps)) { -- cgit v1.2.3