Consolidate and quantize all transformations

This commit defers all outline transformations until rasterization stage.
Combined transformation is then quantized and used as bitmap key.
That should improve performance of slow animations.

Also caching of initial and stroked outlines and bitmaps is now separate
in preparation to proper error estimation for stroker stage.

Note that Z-clipping for perspective transformations is now done
differently compared to VSFilter. That clipping is mostly safety feature
to protect from overflows and divisions by zero and is almost never
triggered in real-world subtitles.

9 files changed, 578 insertions, 578 deletions

diff --git a/libass/ass_bitmap.c b/libass/ass_bitmap.c
index cc40ed6..3e3a5a0 100644
--- a/libass/ass_bitmap.c
+++ b/libass/ass_bitmap.c
@@ -200,6 +200,9 @@ Bitmap *outline_to_bitmap(ASS_Renderer *render_priv,
         return NULL;
     }
 
+    if (rst->bbox.x_min > rst->bbox.x_max || rst->bbox.y_min > rst->bbox.y_max)
+        return NULL;
+
     if (bord < 0 || bord > INT_MAX / 2)
         return NULL;
     if (rst->bbox.x_max > INT_MAX - 63 || rst->bbox.y_max > INT_MAX - 63)
@@ -434,36 +437,6 @@ int be_padding(int be)
     return FFMAX(128 - be, 0);
 }
 
-bool outline_to_bitmap2(ASS_Renderer *render_priv, ASS_Outline *outline,
-                        ASS_Outline *border1, ASS_Outline *border2,
-                        Bitmap **bm_g, Bitmap **bm_o)
-{
-    assert(bm_g && bm_o);
-    *bm_g = *bm_o = NULL;
-
-    if (outline && !outline->n_points)
-        outline = NULL;
-    if (border1 && !border1->n_points)
-        border1 = NULL;
-    if (border2 && !border2->n_points)
-        border2 = NULL;
-
-    if (outline) {
-        *bm_g = outline_to_bitmap(render_priv, outline, NULL, 1);
-        if (!*bm_g)
-            return false;
-    }
-
-    if (border1 || border2) {
-        *bm_o = outline_to_bitmap(render_priv, border1, border2, 1);
-        if (!*bm_o) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
 /**
  * \brief Add two bitmaps together at a given position
  * Uses additive blending, clipped to [0,255]. Pure C implementation.
diff --git a/libass/ass_bitmap.h b/libass/ass_bitmap.h
index e919cd5..ca7ea32 100644
--- a/libass/ass_bitmap.h
+++ b/libass/ass_bitmap.h
@@ -108,18 +108,6 @@ Bitmap *outline_to_bitmap(ASS_Renderer *render_priv,
 void ass_synth_blur(const BitmapEngine *engine, int opaque_box, int be,
                     double blur_radius, Bitmap *bm_g, Bitmap *bm_o);
 
-/**
- * \brief perform glyph rendering
- * \param outline original glyph
- * \param border1 inside "border" outline, produced by stroker
- * \param border2 outside "border" outline, produced by stroker
- * \param bm_g out: pointer to the bitmap of original glyph is returned here
- * \param bm_o out: pointer to the bitmap of border glyph is returned here
- */
-bool outline_to_bitmap2(ASS_Renderer *render_priv, ASS_Outline *outline,
-                        ASS_Outline *border1, ASS_Outline *border2,
-                        Bitmap **bm_g, Bitmap **bm_o);
-
 int be_padding(int be);
 void be_blur_pre(uint8_t *buf, intptr_t w,
                  intptr_t h, intptr_t stride);
diff --git a/libass/ass_cache.c b/libass/ass_cache.c
index 3f2cb19..b92e6d9 100644
--- a/libass/ass_cache.c
+++ b/libass/ass_cache.c
@@ -92,66 +92,22 @@ const CacheDesc font_cache_desc = {
 
 
 // bitmap cache
-static uint32_t bitmap_hash(void *key, uint32_t hval)
-{
-    BitmapHashKey *k = key;
-    switch (k->type) {
-    case BITMAP_OUTLINE:
-        return outline_bitmap_hash(&k->u, hval);
-    case BITMAP_CLIP:
-        return clip_bitmap_hash(&k->u, hval);
-    default:
-        return hval;
-    }
-}
-
-static bool bitmap_compare(void *a, void *b)
-{
-    BitmapHashKey *ak = a;
-    BitmapHashKey *bk = b;
-    if (ak->type != bk->type)
-        return false;
-    switch (ak->type) {
-    case BITMAP_OUTLINE:
-        return outline_bitmap_compare(&ak->u, &bk->u);
-    case BITMAP_CLIP:
-        return clip_bitmap_compare(&ak->u, &bk->u);
-    default:
-        return false;
-    }
-}
-
 static bool bitmap_key_move(void *dst, void *src)
 {
-    BitmapHashKey *d = dst, *s = src;
-    if (!dst) {
-        if (s->type == BITMAP_OUTLINE)
-            ass_cache_dec_ref(s->u.outline.outline);
-        return true;
-    }
-    memcpy(dst, src, sizeof(BitmapHashKey));
-    if (s->type != BITMAP_CLIP)
-        return true;
-    d->u.clip.text = strdup(s->u.clip.text);
-    return d->u.clip.text;
+    BitmapHashKey *k = src;
+    if (dst)
+        memcpy(dst, src, sizeof(BitmapHashKey));
+    else
+        ass_cache_dec_ref(k->outline);
+    return true;
 }
 
 static void bitmap_destruct(void *key, void *value)
 {
     BitmapHashValue *v = value;
     BitmapHashKey *k = key;
-    if (v->bm)
-        ass_free_bitmap(v->bm);
-    if (v->bm_o)
-        ass_free_bitmap(v->bm_o);
-    switch (k->type) {
-    case BITMAP_OUTLINE:
-        ass_cache_dec_ref(k->u.outline.outline);
-        break;
-    case BITMAP_CLIP:
-        free(k->u.clip.text);
-        break;
-    }
+    ass_free_bitmap(v->bm);
+    ass_cache_dec_ref(k->outline);
 }
 
 size_t ass_bitmap_construct(void *key, void *value, void *priv);
@@ -173,7 +129,8 @@ static uint32_t composite_hash(void *key, uint32_t hval)
     CompositeHashKey *k = key;
     hval = filter_hash(&k->filter, hval);
     for (size_t i = 0; i < k->bitmap_count; i++) {
-        hval = fnv_32a_buf(&k->bitmaps[i].image, sizeof(k->bitmaps[i].image), hval);
+        hval = fnv_32a_buf(&k->bitmaps[i].image,   sizeof(k->bitmaps[i].image),   hval);
+        hval = fnv_32a_buf(&k->bitmaps[i].image_o, sizeof(k->bitmaps[i].image_o), hval);
         hval = fnv_32a_buf(&k->bitmaps[i].x, sizeof(k->bitmaps[i].x), hval);
         hval = fnv_32a_buf(&k->bitmaps[i].y, sizeof(k->bitmaps[i].y), hval);
     }
@@ -187,7 +144,8 @@ static bool composite_compare(void *a, void *b)
     if (ak->bitmap_count != bk->bitmap_count)
         return false;
     for (size_t i = 0; i < ak->bitmap_count; i++) {
-        if (ak->bitmaps[i].image != bk->bitmaps[i].image ||
+        if (ak->bitmaps[i].image   != bk->bitmaps[i].image   ||
+            ak->bitmaps[i].image_o != bk->bitmaps[i].image_o ||
             ak->bitmaps[i].x != bk->bitmaps[i].x ||
             ak->bitmaps[i].y != bk->bitmaps[i].y)
             return false;
@@ -202,8 +160,10 @@ static bool composite_key_move(void *dst, void *src)
         return true;
     }
     CompositeHashKey *k = src;
-    for (size_t i = 0; i < k->bitmap_count; i++)
+    for (size_t i = 0; i < k->bitmap_count; i++) {
         ass_cache_dec_ref(k->bitmaps[i].image);
+        ass_cache_dec_ref(k->bitmaps[i].image_o);
+    }
     free(k->bitmaps);
     return true;
 }
@@ -212,14 +172,13 @@ static void composite_destruct(void *key, void *value)
 {
     CompositeHashValue *v = value;
     CompositeHashKey *k = key;
-    if (v->bm)
-        ass_free_bitmap(v->bm);
-    if (v->bm_o)
-        ass_free_bitmap(v->bm_o);
-    if (v->bm_s)
-        ass_free_bitmap(v->bm_s);
-    for (size_t i = 0; i < k->bitmap_count; i++)
+    ass_free_bitmap(v->bm);
+    ass_free_bitmap(v->bm_o);
+    ass_free_bitmap(v->bm_s);
+    for (size_t i = 0; i < k->bitmap_count; i++) {
         ass_cache_dec_ref(k->bitmaps[i].image);
+        ass_cache_dec_ref(k->bitmaps[i].image_o);
+    }
     free(k->bitmaps);
 }
 
@@ -245,9 +204,10 @@ static uint32_t outline_hash(void *key, uint32_t hval)
         return glyph_hash(&k->u, hval);
     case OUTLINE_DRAWING:
         return drawing_hash(&k->u, hval);
-    default:
-        // unused, added to disable warning
-        return outline_common_hash(&k->u, hval);
+    case OUTLINE_BORDER:
+        return border_hash(&k->u, hval);
+    default:  // OUTLINE_BOX
+        return hval;
     }
 }
 
@@ -262,9 +222,10 @@ static bool outline_compare(void *a, void *b)
         return glyph_compare(&ak->u, &bk->u);
     case OUTLINE_DRAWING:
         return drawing_compare(&ak->u, &bk->u);
-    default:
-        // unused, added to disable warning
-        return outline_common_compare(&ak->u, &bk->u);
+    case OUTLINE_BORDER:
+        return border_compare(&ak->u, &bk->u);
+    default:  // OUTLINE_BOX
+        return true;
     }
 }
 
@@ -277,19 +238,21 @@ static bool outline_key_move(void *dst, void *src)
         return true;
     }
     memcpy(dst, src, sizeof(OutlineHashKey));
-    if (s->type != OUTLINE_DRAWING)
-        return true;
-    d->u.drawing.text = strdup(s->u.drawing.text);
-    return d->u.drawing.text;
+    if (s->type == OUTLINE_DRAWING) {
+        d->u.drawing.text = strdup(s->u.drawing.text);
+        return d->u.drawing.text;
+    }
+    if (s->type == OUTLINE_BORDER)
+        ass_cache_inc_ref(s->u.border.outline);
+    return true;
 }
 
 static void outline_destruct(void *key, void *value)
 {
     OutlineHashValue *v = value;
     OutlineHashKey *k = key;
-    outline_free(&v->outline);
-    outline_free(&v->border[0]);
-    outline_free(&v->border[1]);
+    outline_free(&v->outline[0]);
+    outline_free(&v->outline[1]);
     switch (k->type) {
     case OUTLINE_GLYPH:
         ass_cache_dec_ref(k->u.glyph.font);
@@ -297,6 +260,11 @@ static void outline_destruct(void *key, void *value)
     case OUTLINE_DRAWING:
         free(k->u.drawing.text);
         break;
+    case OUTLINE_BORDER:
+        ass_cache_dec_ref(k->u.border.outline);
+        break;
+    default:  // OUTLINE_BOX
+        break;
     }
 }
 
diff --git a/libass/ass_cache.h b/libass/ass_cache.h
index 453cefa..93e5e11 100644
--- a/libass/ass_cache.h
+++ b/libass/ass_cache.h
@@ -30,9 +30,7 @@ typedef struct cache Cache;
 // cache values
 
 typedef struct {
-    bool valid;
-    Bitmap *bm;               // the actual bitmaps
-    Bitmap *bm_o;
+    Bitmap *bm;  // the actual bitmap
 } BitmapHashValue;
 
 typedef struct {
@@ -43,11 +41,10 @@ typedef struct {
 
 typedef struct {
     bool valid;
-    ASS_Outline outline;
-    ASS_Outline border[2];
-    ASS_Rect bbox_scaled;       // bbox after scaling, but before rotation
-    int advance;                // 26.6, advance distance to the next outline in line
-    int asc, desc;              // ascender/descender
+    ASS_Outline outline[2];
+    ASS_Rect cbox;  // bounding box of all control points
+    int advance;    // 26.6, advance distance to the next outline in line
+    int asc, desc;  // ascender/descender
 } OutlineHashValue;
 
 typedef struct {
@@ -71,27 +68,18 @@ typedef struct outline_hash_key {
     enum {
         OUTLINE_GLYPH,
         OUTLINE_DRAWING,
+        OUTLINE_BORDER,
+        OUTLINE_BOX,
     } type;
     union {
         GlyphHashKey glyph;
         DrawingHashKey drawing;
-        OutlineCommonKey common;
+        BorderHashKey border;
     } u;
 } OutlineHashKey;
 
-typedef struct bitmap_hash_key {
-    enum {
-        BITMAP_OUTLINE,
-        BITMAP_CLIP,
-    } type;
-    union {
-        OutlineBitmapHashKey outline;
-        ClipMaskHashKey clip;
-    } u;
-} BitmapHashKey;
-
 typedef struct {
-    BitmapHashValue *image;
+    BitmapHashValue *image, *image_o;
     int x, y;
 } BitmapRef;
 
diff --git a/libass/ass_cache_template.h b/libass/ass_cache_template.h
index 2bb0228..0c4ffdc 100644
--- a/libass/ass_cache_template.h
+++ b/libass/ass_cache_template.h
@@ -51,26 +51,14 @@
 
 
 // describes an outline bitmap
-START(outline_bitmap, outline_bitmap_hash_key)
+START(bitmap, bitmap_hash_key)
     GENERIC(OutlineHashValue *, outline)
-    GENERIC(int, frx) // signed 10.22
-    GENERIC(int, fry) // signed 10.22
-    GENERIC(int, frz) // signed 10.22
-    GENERIC(int, fax) // signed 16.16
-    GENERIC(int, fay) // signed 16.16
-    // shift vector that was added to glyph before applying rotation
-    // = 0, if frx = fry = frx = 0
-    // = (glyph base point) - (rotation origin), otherwise
-    GENERIC(int, shift_x)
-    GENERIC(int, shift_y)
-    VECTOR(advance) // subpixel shift vector
-END(OutlineBitmapHashKey)
-
-// describe a clip mask bitmap
-START(clip_bitmap, clip_bitmap_hash_key)
-    GENERIC(int, scale)
-    STRING(text)
-END(ClipMaskHashKey)
+    // quantized transform matrix
+    VECTOR(offset)
+    VECTOR(matrix_x)
+    VECTOR(matrix_y)
+    VECTOR(matrix_z)
+END(BitmapHashKey)
 
 START(glyph_metrics, glyph_metrics_hash_key)
     GENERIC(ASS_Font *, font)
@@ -79,25 +67,8 @@ START(glyph_metrics, glyph_metrics_hash_key)
     GENERIC(int, glyph_index)
 END(GlyphMetricsHashKey)
 
-// common outline data
-START(outline_common, outline_common_hash_key)
-    GENERIC(unsigned, scale_x) // 16.16
-    GENERIC(unsigned, scale_y) // 16.16
-    VECTOR(outline) // border width, 26.6
-    GENERIC(unsigned, border_style)
-    GENERIC(int, scale_fix)    // 16.16
-    GENERIC(int, advance)      // 26.6
-END(OutlineCommonKey)
-
 // describes an outline glyph
 START(glyph, glyph_hash_key)
-    GENERIC(unsigned, scale_x) // 16.16
-    GENERIC(unsigned, scale_y) // 16.16
-    VECTOR(outline) // border width, 26.6
-    GENERIC(unsigned, border_style)
-    GENERIC(int, scale_fix)    // 16.16
-    GENERIC(int, advance)      // 26.6
-
     GENERIC(ASS_Font *, font)
     GENERIC(double, size) // font size
     GENERIC(int, face_index)
@@ -109,18 +80,19 @@ END(GlyphHashKey)
 
 // describes an outline drawing
 START(drawing, drawing_hash_key)
-    GENERIC(unsigned, scale_x) // 16.16
-    GENERIC(unsigned, scale_y) // 16.16
-    VECTOR(outline) // border width, 26.6
-    GENERIC(unsigned, border_style)
-    GENERIC(int, scale_fix)    // 16.16
-    GENERIC(int, advance)      // 26.6
-
-    GENERIC(int, pbo)
-    GENERIC(int, scale)
     STRING(text)
 END(DrawingHashKey)
 
+// describes an offset outline
+START(border, border_hash_key)
+    GENERIC(OutlineHashValue *, outline)
+    // outline is scaled by 2^scale_ord_x|y before stroking
+    // to keep stoker error in allowable range
+    GENERIC(int, scale_ord_x)
+    GENERIC(int, scale_ord_y)
+    VECTOR(border)  // border size in STROKER_ACCURACY units
+END(BorderHashKey)
+
 // describes post-combining effects
 START(filter, filter_desc)
     GENERIC(int, flags)
diff --git a/libass/ass_outline.c b/libass/ass_outline.c
index 1ed94b8..109e09a 100644
--- a/libass/ass_outline.c
+++ b/libass/ass_outline.c
@@ -287,43 +287,15 @@ bool outline_close_contour(ASS_Outline *outline)
 }
 
 
-void outline_translate(const ASS_Outline *outline, int32_t dx, int32_t dy)
-{
-    for (size_t i = 0; i < outline->n_points; i++) {
-        outline->points[i].x += dx;
-        outline->points[i].y += dy;
-    }
-}
-
-void outline_adjust(const ASS_Outline *outline, double scale_x, int32_t dx, int32_t dy)
-{
-    int32_t mul = lrint(scale_x * 0x10000);
-    if (mul == 0x10000) {
-        outline_translate(outline, dx, dy);
-        return;
-    }
-    for (size_t i = 0; i < outline->n_points; i++) {
-        int32_t x = (int64_t) outline->points[i].x * mul >> 16;
-        outline->points[i].x = x + dx;
-        outline->points[i].y += dy;
-    }
-}
-
-void outline_get_cbox(const ASS_Outline *outline, ASS_Rect *cbox)
+/*
+ * \brief Update bounding box of control points.
+ */
+void outline_update_cbox(const ASS_Outline *outline, ASS_Rect *cbox)
 {
-    if (!outline->n_points) {
-        cbox->x_min = cbox->x_max = 0;
-        cbox->y_min = cbox->y_max = 0;
-        return;
-    }
-    cbox->x_min = cbox->x_max = outline->points[0].x;
-    cbox->y_min = cbox->y_max = outline->points[0].y;
-    for (size_t i = 1; i < outline->n_points; i++) {
-        cbox->x_min = FFMIN(cbox->x_min, outline->points[i].x);
-        cbox->x_max = FFMAX(cbox->x_max, outline->points[i].x);
-        cbox->y_min = FFMIN(cbox->y_min, outline->points[i].y);
-        cbox->y_max = FFMAX(cbox->y_max, outline->points[i].y);
-    }
+    for (size_t i = 0; i < outline->n_points; i++)
+        rectangle_update(cbox,
+                         outline->points[i].x, outline->points[i].y,
+                         outline->points[i].x, outline->points[i].y);
 }
 
 
diff --git a/libass/ass_outline.h b/libass/ass_outline.h
index 85faea9..0a45589 100644
--- a/libass/ass_outline.h
+++ b/libass/ass_outline.h
@@ -96,9 +96,7 @@ 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);
-void outline_adjust(const ASS_Outline *outline, double scale_x, int32_t dx, int32_t dy);
-void outline_get_cbox(const ASS_Outline *outline, ASS_Rect *cbox);
+void outline_update_cbox(const ASS_Outline *outline, ASS_Rect *cbox);
 
 bool outline_stroke(ASS_Outline *result, ASS_Outline *result1,
                     const ASS_Outline *path, int xbord, int ybord, int eps);
diff --git a/libass/ass_render.c b/libass/ass_render.c
index 8e5014e..4badaad 100644
--- a/libass/ass_render.c
+++ b/libass/ass_render.c
@@ -34,7 +34,10 @@
 #define MAX_BITMAPS_INITIAL 16
 #define MAX_SUB_BITMAPS_INITIAL 64
 #define SUBPIXEL_MASK 63
-#define SUBPIXEL_ACCURACY 7
+#define STROKER_PRECISION 16     // stroker error in integer units, unrelated to final accuracy
+#define RASTERIZER_PRECISION 16  // rasterizer spline approximation error in 1/64 pixel units
+#define POSITION_PRECISION 8.0   // rough estimate of transform error in 1/64 pixel units
+#define MAX_PERSP_SCALE 16.0
 
 
 ASS_Renderer *ass_renderer_init(ASS_Library *library)
@@ -75,7 +78,8 @@ ASS_Renderer *ass_renderer_init(ASS_Library *library)
     priv->engine = &ass_bitmap_engine_c;
 #endif
 
-    if (!rasterizer_init(&priv->rasterizer, priv->engine->tile_order, 16)) {
+    if (!rasterizer_init(&priv->rasterizer, priv->engine->tile_order,
+                         RASTERIZER_PRECISION)) {
         FT_Done_FreeType(ft);
         goto ass_init_exit;
     }
@@ -442,6 +446,197 @@ render_glyph(ASS_Renderer *render_priv, Bitmap *bm, int dst_x, int dst_y,
     return tail;
 }
 
+static bool quantize_transform(double m[3][3], BitmapHashKey *key)
+{
+    // Full transform:
+    // x_out = (m_xx * x + m_xy * y + m_xz) / z,
+    // y_out = (m_yx * x + m_yy * y + m_yz) / z,
+    // z     =  m_zx * x + m_zy * y + m_zz.
+
+    const double max_val = 1000000;
+
+    const ASS_Rect *bbox = &key->outline->cbox;
+    double x0 = (bbox->x_min + bbox->x_max) / 2.0;
+    double y0 = (bbox->y_min + bbox->y_max) / 2.0;
+    double dx = (bbox->x_max - bbox->x_min) / 2.0 + 64;
+    double dy = (bbox->y_max - bbox->y_min) / 2.0 + 64;
+
+    // Change input coordinates' origin to (x0, y0),
+    // after that transformation x:[-dx, dx], y:[-dy, dy],
+    // max|x| = dx and max|y| = dy.
+    for (int i = 0; i < 3; i++)
+        m[i][2] += m[i][0] * x0 + m[i][1] * y0;
+
+    if (m[2][2] <= 0)
+        return false;
+
+    double w = 1 / m[2][2];
+    // Transformed center of bounding box
+    double center[2] = { m[0][2] * w, m[1][2] * w };
+    // Change output coordinates' origin to center,
+    // m_xz and m_yz is skipped as it becomes 0 and no longer needed.
+    for (int i = 0; i < 2; i++)
+        for (int j = 0; j < 2; j++)
+            m[i][j] -= m[2][j] * center[i];
+
+    int32_t qr[2];
+    for (int i = 0; i < 2; i++) {
+        center[i] /= POSITION_PRECISION;
+        if (!(fabs(center[i]) < max_val))
+            return false;
+        qr[i] = lrint(center[i]);
+    }
+
+    // Minimal bounding box z coordinate
+    double z0 = m[2][2] - fabs(m[2][0]) * dx - fabs(m[2][1]) * dy;
+    // z0 clamped to z_center / MAX_PERSP_SCALE to mitigate problems with small z
+    w = 1.0 / POSITION_PRECISION / FFMAX(z0, m[2][2] / MAX_PERSP_SCALE);
+    double mul[2] = { dx * w, dy * w };  // 1 / q_x, 1 / q_y
+
+    // z0 = m_zz - |m_zx| * dx - |m_zy| * dy,
+    // m_zz = z0 + |m_zx| * dx + |m_zy| * dy,
+    // z = m_zx * x + m_zy * y + m_zz
+    //  = m_zx * (x + sign(m_zx) * dx) + m_zy * (y + sign(m_zy) * dy) + z0.
+
+    // D(f)--absolute value of error in quantity f
+    // as function of error in matrix coefficients, i. e. D(m_??).
+    // Error in constant is zero, i. e. D(dx) = D(dy) = D(z0) = 0.
+    // In the following calculation errors are considered small
+    // and second- and higher-order terms are dropped.
+    // That approximation is valid as long as glyph dimensions are larger than couple of pixels.
+    // Therefore standard relations for derivatives can be used for D(?):
+    // D(A * B) <= D(A) * max|B| + max|A| * D(B),
+    // D(1 / C) <= D(C) * max|1 / C^2|.
+
+    // D(x_out) = D((m_xx * x + m_xy * y) / z)
+    //  <= D(m_xx * x + m_xy * y) * max|1 / z| + max|m_xx * x + m_xy * y| * D(1 / z)
+    //  <= (D(m_xx) * dx + D(m_xy) * dy) / z0 + (|m_xx| * dx + |m_xy| * dy) * D(z) / z0^2,
+    // D(y_out) = D((m_yx * x + m_yy * y) / z)
+    //  <= D(m_yx * x + m_yy * y) * max|1 / z| + max|m_yx * x + m_yy * y| * D(1 / z)
+    //  <= (D(m_yx) * dx + D(m_yy) * dy) / z0 + (|m_yx| * dx + |m_yy| * dy) * D(z) / z0^2,
+    // |m_xx| * dx + |m_xy| * dy = x_lim,
+    // |m_yx| * dx + |m_yy| * dy = y_lim,
+    // D(z) <= 2 * (D(m_zx) * dx + D(m_zy) * dy),
+    // D(x_out) <= (D(m_xx) * dx + D(m_xy) * dy) / z0
+    //       + 2 * (D(m_zx) * dx + D(m_zy) * dy) * x_lim / z0^2,
+    // D(y_out) <= (D(m_yx) * dx + D(m_yy) * dy) / z0
+    //       + 2 * (D(m_zx) * dx + D(m_zy) * dy) * y_lim / z0^2.
+
+    // To estimate acceptable error in matrix coefficient
+    // set error in all other coefficients to zero and solve system
+    // D(x_out) <= ACCURACY & D(y_out) <= ACCURACY for desired D(m_??).
+    // ACCURACY here is some part of total error, i. e. ACCURACY ~ POSITION_PRECISION.
+    // Note that POSITION_PRECISION isn't total error, it's convenient constant.
+    // True error can be up to several POSITION_PRECISION.
+
+    // Quantization steps (ACCURACY ~ POSITION_PRECISION):
+    // D(m_xx), D(m_yx) ~ q_x = POSITION_PRECISION * z0 / dx,
+    // D(m_xy), D(m_yy) ~ q_y = POSITION_PRECISION * z0 / dy,
+    // qm_xx = round(m_xx / q_x), qm_xy = round(m_xy / q_y),
+    // qm_yx = round(m_yx / q_x), qm_yy = round(m_yy / q_y).
+
+    int32_t qm[3][2];
+    for (int i = 0; i < 2; i++)
+        for (int j = 0; j < 2; j++) {
+            double val = m[i][j] * mul[j];
+            if (!(fabs(val) < max_val))
+                return false;
+            qm[i][j] = lrint(val);
+        }
+
+    // x_lim = |m_xx| * dx + |m_xy| * dy
+    //  ~= |qm_xx| * q_x * dx + |qm_xy| * q_y * dy
+    //  = (|qm_xx| + |qm_xy|) * POSITION_PRECISION * z0,
+    // y_lim = |m_yx| * dx + |m_yy| * dy
+    //  ~= |qm_yx| * q_x * dx + |qm_yy| * q_y * dy
+    //  = (|qm_yx| + |qm_yy|) * POSITION_PRECISION * z0,
+    // max(x_lim, y_lim) / z0 ~= w
+    //  = max(|qm_xx| + |qm_xy|, |qm_yx| + |qm_yy|) * POSITION_PRECISION.
+
+    // Quantization steps (ACCURACY ~ 2 * POSITION_PRECISION):
+    // D(m_zx) ~ POSITION_PRECISION * z0^2 / max(x_lim, y_lim) / dx ~= q_zx = q_x / w,
+    // D(m_zy) ~ POSITION_PRECISION * z0^2 / max(x_lim, y_lim) / dy ~= q_zy = q_y / w,
+    // qm_zx = round(m_zx / q_zx), qm_zy = round(m_zy / q_zy).
+
+    int32_t qmx = abs(qm[0][0]) + abs(qm[0][1]);
+    int32_t qmy = abs(qm[1][0]) + abs(qm[1][1]);
+    w = POSITION_PRECISION * FFMAX(qmx, qmy);
+    mul[0] *= w;
+    mul[1] *= w;
+
+    for (int j = 0; j < 2; j++) {
+        double val = m[2][j] * mul[j];
+        if (!(fabs(val) < max_val))
+            return false;
+        qm[2][j] = lrint(val);
+    }
+
+    key->offset.x = qr[0];  key->offset.y = qr[1];
+    key->matrix_x.x = qm[0][0];  key->matrix_x.y = qm[0][1];
+    key->matrix_y.x = qm[1][0];  key->matrix_y.y = qm[1][1];
+    key->matrix_z.x = qm[2][0];  key->matrix_z.y = qm[2][1];
+    return true;
+}
+
+static void restore_transform(double m[3][3], const BitmapHashKey *key)
+{
+    const ASS_Rect *bbox = &key->outline->cbox;
+    double x0 = (bbox->x_min + bbox->x_max) / 2.0;
+    double y0 = (bbox->y_min + bbox->y_max) / 2.0;
+    double dx = (bbox->x_max - bbox->x_min) / 2.0 + 64;
+    double dy = (bbox->y_max - bbox->y_min) / 2.0 + 64;
+
+    // Arbitrary scale has chosen so that z0 = 1
+    double q_x = POSITION_PRECISION / dx;
+    double q_y = POSITION_PRECISION / dy;
+    m[0][0] = key->matrix_x.x * q_x;
+    m[0][1] = key->matrix_x.y * q_y;
+    m[1][0] = key->matrix_y.x * q_x;
+    m[1][1] = key->matrix_y.y * q_y;
+
+    int32_t qmx = abs(key->matrix_x.x) + abs(key->matrix_x.y);
+    int32_t qmy = abs(key->matrix_y.x) + abs(key->matrix_y.y);
+    double scale_z = 1.0 / POSITION_PRECISION / FFMAX(qmx, qmy);
+    m[2][0] = key->matrix_z.x * q_x * scale_z;  // qm_zx * q_zx
+    m[2][1] = key->matrix_z.y * q_y * scale_z;  // qm_zy * q_zy
+
+    m[0][2] = m[1][2] = 0;
+    m[2][2] = 1 + fabs(m[2][0]) * dx + fabs(m[2][1]) * dy;
+    m[2][2] = FFMIN(m[2][2], MAX_PERSP_SCALE);
+
+    double center[2] = {
+        key->offset.x * POSITION_PRECISION,
+        key->offset.y * POSITION_PRECISION,
+    };
+    for (int i = 0; i < 2; i++)
+        for (int j = 0; j < 3; j++)
+            m[i][j] += m[2][j] * center[i];
+
+    for (int i = 0; i < 3; i++)
+        m[i][2] -= m[i][0] * x0 + m[i][1] * y0;
+}
+
+static BitmapHashValue *get_bitmap(ASS_Renderer *render_priv, OutlineHashValue *outline,
+                                   const ASS_Transform *trans, const double mat[3][3])
+{
+    if (!outline)
+        return NULL;
+
+    double m[3][3];
+    for (int i = 0; i < 3; i++) {
+        m[i][0] = mat[i][0] * trans->scale.x;
+        m[i][1] = mat[i][1] * trans->scale.y;
+        m[i][2] = mat[i][0] * trans->offset.x + mat[i][1] * trans->offset.y + mat[i][2];
+    }
+
+    BitmapHashKey k;
+    k.outline = outline;
+    if (quantize_transform(m, &k))
+        return ass_cache_get(render_priv->cache.bitmap_cache, &k, render_priv);
+    ass_cache_dec_ref(outline);
+    return NULL;
+}
+
 // Calculate bitmap memory footprint
 static inline size_t bitmap_size(Bitmap *bm)
 {
@@ -459,13 +654,30 @@ static void blend_vector_clip(ASS_Renderer *render_priv,
     if (!render_priv->state.clip_drawing_text)
         return;
 
-    // Get mask from cache
-    BitmapHashKey key;
-    key.type = BITMAP_CLIP;
-    key.u.clip.scale = render_priv->state.clip_drawing_scale;
-    key.u.clip.text = render_priv->state.clip_drawing_text;
+    OutlineHashKey key;
+    key.type = OUTLINE_DRAWING;
+    key.u.drawing.text = render_priv->state.clip_drawing_text;
+    OutlineHashValue *outline =
+        ass_cache_get(render_priv->cache.outline_cache, &key, render_priv);
+    if (!outline || !outline->valid) {
+        ass_cache_dec_ref(outline);
+        return;
+    }
+
+    ASS_Transform trans;
+    double w = render_priv->font_scale / (1 << (render_priv->state.clip_drawing_scale - 1));
+    trans.scale.x = render_priv->font_scale_x * w;
+    trans.scale.y = w;
+
+    trans.offset.x = int_to_d6(render_priv->settings.left_margin);
+    trans.offset.y = int_to_d6(render_priv->settings.top_margin);
 
-    BitmapHashValue *val = ass_cache_get(render_priv->cache.bitmap_cache, &key, render_priv);
+    double m[3][3] = {
+        { 1, 0, 0 },
+        { 0, 1, 0 },
+        { 0, 0, 1 },
+    };
+    BitmapHashValue *val = get_bitmap(render_priv, outline, &trans, m);
     if (!val)
         return;
 
@@ -880,104 +1092,6 @@ static void free_render_context(ASS_Renderer *render_priv)
     text_info->length = 0;
 }
 
-/*
- * Replace the outline of a glyph by a contour which makes up a simple
- * opaque rectangle.
- */
-static void draw_opaque_box(ASS_Renderer *render_priv,
-                            double scale_x, double scale_y,
-                            int asc, int desc, ASS_Outline *ol,
-                            int adv, int sx, int sy)
-{
-    // to avoid gaps
-    sx = FFMAX(64, sx);
-    sy = FFMAX(64, sy);
-
-    // Emulate the WTFish behavior of VSFilter, i.e. double-scale
-    // the sizes of the opaque box.
-    adv *= scale_x;
-    sx *= scale_x;
-    sy *= scale_y;
-    desc *= scale_y;
-    desc += asc * (scale_y - 1.0);
-
-    ASS_Vector points[4] = {
-        { .x = -sx,         .y = -asc - sy },
-        { .x = adv + sx,    .y = -asc - sy },
-        { .x = adv + sx,    .y = desc + sy },
-        { .x = -sx,         .y = desc + sy },
-    };
-
-    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->segments[ol->n_segments++] = segments[i];
-    }
-}
-
-/**
- * \brief Prepare glyph hash
- */
-static void
-fill_glyph_hash(ASS_Renderer *priv, OutlineHashKey *outline_key,
-                GlyphInfo *info)
-{
-    OutlineCommonKey *common = &outline_key->u.common;
-    common->scale_x = double_to_d16(info->scale_x);
-    common->scale_y = double_to_d16(info->scale_y);
-    common->outline.x = double_to_d6(info->border_x * priv->border_scale);
-    common->outline.y = double_to_d6(info->border_y * priv->border_scale);
-    common->border_style = info->border_style;
-    // following fields only matter for opaque box borders (see draw_opaque_box),
-    // so for normal borders, maximize cache utility by ignoring them
-    if (info->border_style == 3) {
-        common->scale_fix = double_to_d16(info->scale_fix);
-        common->advance = info->hspacing_scaled;
-        if (priv->settings.shaper != ASS_SHAPING_SIMPLE && !info->drawing_text)
-            common->advance += info->advance.x;
-    } else {
-        common->scale_fix = 0;
-        common->advance = 0;
-    }
-
-    if (info->drawing_text) {
-        outline_key->type = OUTLINE_DRAWING;
-        DrawingHashKey *key = &outline_key->u.drawing;
-        key->text = info->drawing_text;
-        key->pbo = info->drawing_pbo;
-        key->scale = info->drawing_scale;
-    } else {
-        outline_key->type = OUTLINE_GLYPH;
-        GlyphHashKey *key = &outline_key->u.glyph;
-        key->font = info->font;
-        key->size = info->font_size;
-        key->face_index = info->face_index;
-        key->glyph_index = info->glyph_index;
-        key->bold = info->bold;
-        key->italic = info->italic;
-        key->flags = info->flags;
-    }
-}
-
-/**
- * \brief Prepare combined-bitmap hash
- */
-static void fill_composite_hash(CompositeHashKey *hk, CombinedBitmapInfo *info)
-{
-    hk->filter = info->filter;
-    hk->bitmap_count = info->bitmap_count;
-    hk->bitmaps = info->bitmaps;
-}
-
 /**
  * \brief Get normal and outline (border) glyphs
  * \param info out: struct filled with extracted data
@@ -988,27 +1102,121 @@ static void fill_composite_hash(CompositeHashKey *hk, CombinedBitmapInfo *info)
 static void
 get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info)
 {
-    memset(&info->hash_key, 0, sizeof(info->hash_key));
+    OutlineHashValue *val;
+    ASS_DVector scale, offset = {0};
 
+    int32_t asc, desc;
     OutlineHashKey key;
-    fill_glyph_hash(priv, &key, info);
-    OutlineHashValue *val = ass_cache_get(priv->cache.outline_cache, &key, priv);
-    if (!val || !val->valid) {
-        ass_cache_dec_ref(val);
-        return;
+    if (info->drawing_text) {
+        key.type = OUTLINE_DRAWING;
+        key.u.drawing.text = info->drawing_text;
+        val = ass_cache_get(priv->cache.outline_cache, &key, priv);
+        if (!val || !val->valid) {
+            ass_cache_dec_ref(val);
+            return;
+        }
+
+        double w = priv->font_scale / (1 << (info->drawing_scale - 1));
+        scale.x = info->scale_x * w;
+        scale.y = info->scale_y * w;
+        desc = 64 * info->drawing_pbo;
+        asc = val->asc - desc;
+
+        offset.y = -asc * scale.y;
+    } else {
+        key.type = OUTLINE_GLYPH;
+        GlyphHashKey *k = &key.u.glyph;
+        k->font = info->font;
+        k->size = info->font_size;
+        k->face_index = info->face_index;
+        k->glyph_index = info->glyph_index;
+        k->bold = info->bold;
+        k->italic = info->italic;
+        k->flags = info->flags;
+
+        val = ass_cache_get(priv->cache.outline_cache, &key, priv);
+        if (!val || !val->valid) {
+            ass_cache_dec_ref(val);
+            return;
+        }
+
+        scale.x = info->scale_x;
+        scale.y = info->scale_y;
+        asc  = val->asc;
+        desc = val->desc;
     }
 
-    info->hash_key.u.outline.outline = val;
-    info->outline = &val->outline;
-    info->border[0] = &val->border[0];
-    info->border[1] = &val->border[1];
-    info->bbox = val->bbox_scaled;
+    info->outline = val;