Fix \kf fill positioning

Our effect_timing is currently used as a coordinate relative to a weird origin:
take each glyph's center within the run, apply 3D transforms, pick the leftmost
one, and round it down a little. This makes no sense and is the result of an
unrelated code change. But if I recall correctly, \kf positioning was already
incorrect before that last change (but in a different manner).

To fix this and hopefully to prevent this kind of error from occurring again,
convert effect_timing to absolute screen coordinate.

Start the fill at the glyph run's leftmost post-transform control point.
This matches VSFilter and allows karaoke to work in vertical text (unlike,
for example, starting the fill at the first glyph's pre-transform origin).

Fixes https://github.com/libass/libass/issues/216.
Fixes https://github.com/libass/libass/issues/357.

4 files changed, 41 insertions, 6 deletions

diff --git a/libass/ass_outline.c b/libass/ass_outline.c
index 7a71678..ae5c06a 100644
--- a/libass/ass_outline.c
+++ b/libass/ass_outline.c
@@ -323,6 +323,20 @@ bool outline_transform_3d(ASS_Outline *outline, const ASS_Outline *source,
     return true;
 }
 
+void outline_update_min_transformed_x(const ASS_Outline *outline,
+                                      const double m[3][3],
+                                      int32_t *min_x) {
+    const ASS_Vector *pt = outline->points;
+    for (size_t i = 0; i < outline->n_points; i++) {
+        double z = m[2][0] * pt[i].x + m[2][1] * pt[i].y + m[2][2];
+        double x = (m[0][0] * pt[i].x + m[0][1] * pt[i].y + m[0][2]) / FFMAX(z, 0.1);
+        if (isnan(x))
+            continue;
+        int32_t ix = lrint(FFMINMAX(x, -OUTLINE_MAX, OUTLINE_MAX));
+        *min_x = FFMIN(*min_x, ix);
+    }
+}
+
 
 void outline_free(ASS_Outline *outline)
 {
diff --git a/libass/ass_outline.h b/libass/ass_outline.h
index 841f9de..f5606dd 100644
--- a/libass/ass_outline.h
+++ b/libass/ass_outline.h
@@ -95,6 +95,9 @@ bool outline_transform_2d(ASS_Outline *outline, const ASS_Outline *source,
                           const double m[2][3]);
 bool outline_transform_3d(ASS_Outline *outline, const ASS_Outline *source,
                           const double m[3][3]);
+void outline_update_min_transformed_x(const ASS_Outline *outline,
+                                      const double m[3][3],
+                                      int32_t *min_x);
 void outline_free(ASS_Outline *outline);
 
 bool outline_add_point(ASS_Outline *outline, ASS_Vector pt, char segment);
diff --git a/libass/ass_render.c b/libass/ass_render.c
index 64dde4d..48e3ead 100644
--- a/libass/ass_render.c
+++ b/libass/ass_render.c
@@ -381,7 +381,7 @@ render_glyph(ASS_Renderer *render_priv, Bitmap *bm, int dst_x, int dst_y,
         return render_glyph_i(render_priv, bm, dst_x, dst_y, color, color2,
                               brk, tail, type, source);
 
-    // brk is relative to dst_x
+    // brk is absolute
     // color = color left of brk
     // color2 = color right of brk
     int b_x0, b_y0, b_x1, b_y1; // visible part of the bitmap
@@ -391,7 +391,7 @@ render_glyph(ASS_Renderer *render_priv, Bitmap *bm, int dst_x, int dst_y,
 
     dst_x += bm->left;
     dst_y += bm->top;
-    brk -= bm->left;
+    brk -= dst_x;
 
     // clipping
     clip_x0 = FFMINMAX(render_priv->state.clip_x0, 0, render_priv->width);
@@ -1302,6 +1302,7 @@ static void calc_transform_matrix(ASS_Renderer *render_priv,
  */
 static void
 get_bitmap_glyph(ASS_Renderer *render_priv, GlyphInfo *info,
+                 int32_t *leftmost_x,
                  ASS_Vector *pos, ASS_Vector *pos_o,
                  ASS_DVector *offset, bool first, int flags)
 {
@@ -1320,6 +1321,9 @@ get_bitmap_glyph(ASS_Renderer *render_priv, GlyphInfo *info,
     }
     memcpy(m, m2, sizeof(m));
 
+    if (info->effect_type == EF_KARAOKE_KF)
+        outline_update_min_transformed_x(&info->outline->outline[0], m, leftmost_x);
+
     BitmapHashKey key;
     key.outline = info->outline;
     if (!quantize_transform(m, pos, offset, first, &key)) {
@@ -2338,6 +2342,7 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
                 memcpy(&current_info->c, &info->c, sizeof(info->c));
                 current_info->effect_type = info->effect_type;
                 current_info->effect_timing = info->effect_timing;
+                current_info->leftmost_x = OUTLINE_MAX;
 
                 FilterDesc *filter = &current_info->filter;
                 filter->flags = flags;
@@ -2374,7 +2379,7 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
             ASS_Vector pos, pos_o;
             info->pos.x = double_to_d6(device_x + d6_to_double(info->pos.x) * render_priv->font_scale_x);
             info->pos.y = double_to_d6(device_y) + info->pos.y;
-            get_bitmap_glyph(render_priv, info, &pos, &pos_o,
+            get_bitmap_glyph(render_priv, info, &current_info->leftmost_x, &pos, &pos_o,
                              &offset, !current_info->bitmap_count, flags);
 
             if (!info->bm && !info->bm_o) {
@@ -2405,6 +2410,14 @@ static void render_and_combine_glyphs(ASS_Renderer *render_priv,
 
     for (int i = 0; i < nb_bitmaps; i++) {
         CombinedBitmapInfo *info = &combined_info[i];
+        if (!info->bitmap_count) {
+            free(info->bitmaps);
+            continue;
+        }
+
+        if (info->effect_type == EF_KARAOKE_KF)
+            info->effect_timing += d6_to_int(info->leftmost_x);
+
         for (int j = 0; j < info->bitmap_count; j++) {
             info->bitmaps[j].pos.x -= info->x;
             info->bitmaps[j].pos.y -= info->y;
diff --git a/libass/ass_render.h b/libass/ass_render.h
index eb4124e..9796841 100644
--- a/libass/ass_render.h
+++ b/libass/ass_render.h
@@ -99,9 +99,14 @@ typedef struct {
     FilterDesc filter;
     uint32_t c[4];              // colors
     Effect effect_type;
-    int effect_timing;          // time duration of current karaoke word
-    // after process_karaoke_effects: distance in pixels from the glyph origin.
+
+    // during render_and_combine_glyphs: distance in pixels from the karaoke origin.
+    // after render_and_combine_glyphs: screen coordinate in pixels.
     // part of the glyph to the left of it is displayed in a different color.
+    int effect_timing;
+
+    // karaoke origin: screen coordinate of leftmost post-transform control point x in subpixels
+    int32_t leftmost_x;
 
     size_t bitmap_count, max_bitmap_count;
     BitmapRef *bitmaps;
@@ -142,7 +147,7 @@ typedef struct glyph_info {
     ASS_Vector cluster_advance;
     Effect effect_type;
     int effect_timing;          // time duration of current karaoke word
-    // after process_karaoke_effects: distance in pixels from the glyph origin.
+    // after process_karaoke_effects: distance in pixels from the karaoke origin.
     // part of the glyph to the left of it is displayed in a different color.
     int effect_skip_timing;     // delay after the end of last karaoke word
     int asc, desc;              // font max ascender and descender