Skip to content

Commit 42d0a3d

Browse files
authored
[Impeller] Fix interpolation error in Rect::TransformAndClipBounds (#181420)
We had been interpolating the points backwards in the `Rect::TransformAndClipBounds` code. When we transform a rectangle under a perspective transform, some of the points may generate a homogenous bias (W) that is less than 0. This is a special condition that means that the point was transformed "behind the camera" (this is one way of looking at it and helps explain why we avoid such values). In order for it to contribute properly to the bounds in front of the "camera", it needs to be moved back into the positive (W>0) space. We do this by interpolating from that out of bounds coordinate to either of its adjacent neighbors which are in bounds (i.e. their W>0) to move the point to a bias value that is just slightly in the "in bounds" half-space - we choose W=(1/2^14) as our "in bounds" bias value. Unfortunately, the code to interpolate the 2 coordinates was written with conflicting definitions of which direction we computed the `t` value and which direction we applied it to the 2 coordinates - thus generating nonsensical values. This turned up while debugging a fix for #173104 where we fixed the transform logic in the clip code, but the rectangle was still partially clipped due to a bad result from the `GetCoverage` method of the rect geometry code. Note that this fix alone does not correct the problem in that Issue, it merely fixes a needed utility method that the fix will rely on.
1 parent e9386dd commit 42d0a3d

2 files changed

Lines changed: 235 additions & 130 deletions

File tree

‎engine/src/flutter/impeller/geometry/rect.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -777,8 +777,8 @@ struct TRect {
777777
if (neighbor.z >= kMinimumHomogenous) {
778778
auto t = (kMinimumHomogenous - p.z) / (neighbor.z - p.z);
779779
clipped[index++] = {
780-
(t * p.x + (1.0f - t) * neighbor.x) / kMinimumHomogenous,
781-
(t * p.y + (1.0f - t) * neighbor.y) / kMinimumHomogenous,
780+
((1.0f - t) * p.x + t * neighbor.x) / kMinimumHomogenous,
781+
((1.0f - t) * p.y + t * neighbor.y) / kMinimumHomogenous,
782782
};
783783
}
784784
return index;

‎engine/src/flutter/impeller/geometry/rect_unittests.cc‎

Lines changed: 233 additions & 128 deletions
Original file line numberDiff line numberDiff line change
@@ -3113,134 +3113,239 @@ TEST(RectTest, IRectRound) {
31133113
}
31143114
}
31153115

3116-
TEST(RectTest, TransformAndClipBounds) {
3117-
{
3118-
// This matrix should clip no corners.
3119-
auto matrix = impeller::Matrix::MakeColumn(
3120-
// clang-format off
3121-
2.0f, 0.0f, 0.0f, 0.0f,
3122-
0.0f, 4.0f, 0.0f, 0.0f,
3123-
0.0f, 0.0f, 1.0f, 0.0f,
3124-
0.0f, 0.0f, 0.0f, 8.0f
3125-
// clang-format on
3126-
);
3127-
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3128-
// None of these should have a W<0
3129-
EXPECT_EQ(matrix.TransformHomogenous(src.GetLeftTop()),
3130-
Vector3(200.0f, 400.0f, 8.0f));
3131-
EXPECT_EQ(matrix.TransformHomogenous(src.GetRightTop()),
3132-
Vector3(400.0f, 400.0f, 8.0f));
3133-
EXPECT_EQ(matrix.TransformHomogenous(src.GetLeftBottom()),
3134-
Vector3(200.0f, 800.0f, 8.0f));
3135-
EXPECT_EQ(matrix.TransformHomogenous(src.GetRightBottom()),
3136-
Vector3(400.0f, 800.0f, 8.0f));
3137-
3138-
Rect expect = Rect::MakeLTRB(25.0f, 50.0f, 50.0f, 100.0f);
3139-
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3140-
EXPECT_EQ(src.TransformAndClipBounds(matrix), expect);
3141-
}
3142-
3143-
{
3144-
// This matrix should clip one corner.
3145-
auto matrix = impeller::Matrix::MakeColumn(
3146-
// clang-format off
3147-
2.0f, 0.0f, 0.0f, -0.01f,
3148-
0.0f, 2.0f, 0.0f, -0.006f,
3149-
0.0f, 0.0f, 1.0f, 0.0f,
3150-
0.0f, 0.0f, 0.0f, 3.0f
3151-
// clang-format on
3152-
);
3153-
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3154-
// Exactly one of these should have a W<0
3155-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3156-
Vector3(200.0f, 200.0f, 1.4f));
3157-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3158-
Vector3(400.0f, 200.0f, 0.4f));
3159-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3160-
Vector3(200.0f, 400.0f, 0.8f));
3161-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3162-
Vector3(400.0f, 400.0f, -0.2f));
3163-
3164-
Rect expect = Rect::MakeLTRB(142.85715f, 142.85715f, 6553600.f, 6553600.f);
3165-
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3166-
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3167-
}
3168-
3169-
{
3170-
// This matrix should clip two corners.
3171-
auto matrix = impeller::Matrix::MakeColumn(
3172-
// clang-format off
3173-
2.0f, 0.0f, 0.0f, -.015f,
3174-
0.0f, 2.0f, 0.0f, -.006f,
3175-
0.0f, 0.0f, 1.0f, 0.0f,
3176-
0.0f, 0.0f, 0.0f, 3.0f
3177-
// clang-format on
3178-
);
3179-
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3180-
// Exactly two of these should have a W<0
3181-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3182-
Vector3(200.0f, 200.0f, 0.9f));
3183-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3184-
Vector3(400.0f, 200.0f, -0.6f));
3185-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3186-
Vector3(200.0f, 400.0f, 0.3f));
3187-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3188-
Vector3(400.0f, 400.0f, -1.2f));
3189-
3190-
Rect expect = Rect::MakeLTRB(222.2222f, 222.2222f, 5898373.f, 6553600.f);
3191-
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3192-
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3193-
}
3194-
3195-
{
3196-
// This matrix should clip three corners.
3197-
auto matrix = impeller::Matrix::MakeColumn(
3198-
// clang-format off
3199-
2.0f, 0.0f, 0.0f, -.02f,
3200-
0.0f, 2.0f, 0.0f, -.006f,
3201-
0.0f, 0.0f, 1.0f, 0.0f,
3202-
0.0f, 0.0f, 0.0f, 3.0f
3203-
// clang-format on
3204-
);
3205-
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3206-
// Exactly three of these should have a W<0
3207-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3208-
Vector3(200.0f, 200.0f, 0.4f));
3209-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3210-
Vector3(400.0f, 200.0f, -1.6f));
3211-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3212-
Vector3(200.0f, 400.0f, -0.2f));
3213-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3214-
Vector3(400.0f, 400.0f, -2.2f));
3215-
3216-
Rect expect = Rect::MakeLTRB(499.99988f, 499.99988f, 5898340.f, 4369400.f);
3217-
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3218-
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3219-
}
3220-
3221-
{
3222-
// This matrix should clip all four corners.
3223-
auto matrix = impeller::Matrix::MakeColumn(
3224-
// clang-format off
3225-
2.0f, 0.0f, 0.0f, -.025f,
3226-
0.0f, 2.0f, 0.0f, -.006f,
3227-
0.0f, 0.0f, 1.0f, 0.0f,
3228-
0.0f, 0.0f, 0.0f, 3.0f
3229-
// clang-format on
3230-
);
3231-
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3232-
// All of these should have a W<0
3233-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3234-
Vector3(200.0f, 200.0f, -0.1f));
3235-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3236-
Vector3(400.0f, 200.0f, -2.6f));
3237-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3238-
Vector3(200.0f, 400.0f, -0.7f));
3239-
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3240-
Vector3(400.0f, 400.0f, -3.2f));
3241-
3242-
EXPECT_TRUE(src.TransformAndClipBounds(matrix).IsEmpty());
3243-
}
3116+
TEST(RectTest, TransformAndClipBoundsNoCornersClipped) {
3117+
// This matrix should clip no corners.
3118+
auto matrix = impeller::Matrix::MakeColumn(
3119+
// clang-format off
3120+
2.0f, 0.0f, 0.0f, 0.0f,
3121+
0.0f, 4.0f, 0.0f, 0.0f,
3122+
0.0f, 0.0f, 1.0f, 0.0f,
3123+
0.0f, 0.0f, 0.0f, 8.0f
3124+
// clang-format on
3125+
);
3126+
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3127+
3128+
// None of these should have a W<0
3129+
3130+
EXPECT_EQ(matrix.TransformHomogenous(src.GetLeftTop()),
3131+
Vector3(200.0f, 400.0f, 8.0f));
3132+
EXPECT_EQ(matrix.TransformHomogenous(src.GetRightTop()),
3133+
Vector3(400.0f, 400.0f, 8.0f));
3134+
EXPECT_EQ(matrix.TransformHomogenous(src.GetLeftBottom()),
3135+
Vector3(200.0f, 800.0f, 8.0f));
3136+
EXPECT_EQ(matrix.TransformHomogenous(src.GetRightBottom()),
3137+
Vector3(400.0f, 800.0f, 8.0f));
3138+
3139+
Rect expect = Rect::MakeLTRB(25.0f, 50.0f, 50.0f, 100.0f);
3140+
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3141+
EXPECT_EQ(src.TransformAndClipBounds(matrix), expect);
3142+
}
3143+
3144+
TEST(RectTest, TransformAndClipBoundsOneCornerClipped) {
3145+
// This matrix should clip one corner.
3146+
auto matrix = impeller::Matrix::MakeColumn(
3147+
// clang-format off
3148+
2.0f, 0.0f, 0.0f, -0.01f,
3149+
0.0f, 2.0f, 0.0f, -0.006f,
3150+
0.0f, 0.0f, 1.0f, 0.0f,
3151+
0.0f, 0.0f, 0.0f, 3.0f
3152+
// clang-format on
3153+
);
3154+
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3155+
3156+
// Exactly one of these should have a W<0
3157+
//
3158+
// When W<0 we interpolate the point back towards the adjacent points
3159+
// that have W>0 to a location just greater than the W=0 half-plane.
3160+
// We interpolate them to W=epsilon where epsilon == 2^-14.
3161+
3162+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3163+
Vector3(200.0f, 200.0f, 1.4f));
3164+
// Contributes (200, 200) / 1.4 == (142.85714, 142.85714)
3165+
3166+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3167+
Vector3(400.0f, 200.0f, 0.4f));
3168+
// Contributes (400, 200) / 0.4 == (1000, 500)
3169+
3170+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3171+
Vector3(200.0f, 400.0f, 0.8f));
3172+
// Contributes (200, 400) / 0.8 == (250, 500)
3173+
3174+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3175+
Vector3(400.0f, 400.0f, -0.2f));
3176+
// Interpolates at epsilon against RightTop to produce:
3177+
// t = (epsilon - -.2) / (.4 - -.2)
3178+
// = (epsilon + .2) / .6
3179+
// = 0.333435
3180+
// Lerp(RightBottom, RightTop, 0.333435) = (400, 333.313, epsilon)
3181+
// = (6553600, 5461000)
3182+
//
3183+
// It also interpolates at epsilon against LeftBottom to produce:
3184+
// t = (epsilon - -.2) / (.8 - -.2)
3185+
// = (epsilon + .2) / 1
3186+
// = 0.200061
3187+
// Lerp(RightBottom, LeftBottom, 0.200061) = (359.988, 400, epsilon)
3188+
// = (5898040, 6553600)
3189+
3190+
// Min/Max X and Y of all the points generated above are:
3191+
// Min X == 142.85714
3192+
// Min Y == 142.85714
3193+
// Max X == 6553600
3194+
// Max Y == 6553600
3195+
3196+
Rect expect = Rect::MakeLTRB(142.85714f, 142.85714f, 6553600.f, 6553600.f);
3197+
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3198+
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3199+
}
3200+
3201+
TEST(RectTest, TransformAndClipBoundsTwoCornersClipped) {
3202+
// This matrix should clip two corners.
3203+
auto matrix = impeller::Matrix::MakeColumn(
3204+
// clang-format off
3205+
2.0f, 0.0f, 0.0f, -.015f,
3206+
0.0f, 2.0f, 0.0f, -.006f,
3207+
0.0f, 0.0f, 1.0f, 0.0f,
3208+
0.0f, 0.0f, 0.0f, 3.0f
3209+
// clang-format on
3210+
);
3211+
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3212+
3213+
// Exactly two of these homogenous results should have a W<0
3214+
//
3215+
// When W<0 we interpolate the point back towards the adjacent points
3216+
// that have W>0 to a location just greater than the W=0 half-plane.
3217+
// We interpolate them to W=epsilon where epsilon == 2^-14.
3218+
3219+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3220+
Vector3(200.0f, 200.0f, 0.9f));
3221+
// Contributes (200, 200) / 0.9 == (222.2222, 222.2222) to bounds
3222+
3223+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3224+
Vector3(400.0f, 200.0f, -0.6f));
3225+
// Interpolates at epsilon against LeftTop to produce:
3226+
// t = (epsilon - -.6) / (.9 - -.6)
3227+
// = (epsilon + .6) / 1.5
3228+
// = 0.4000407
3229+
// Lerp(RightTop, LeftTop, 0.4000407) = (319.9919, 200, epsilon)
3230+
// = (5242747, 3276800)
3231+
// Cannot interpolate against RightBottom because it also has W<0
3232+
3233+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3234+
Vector3(200.0f, 400.0f, 0.3f));
3235+
// Contributes (200, 400) / 0.3 == (666.6667, 1333.3333) to bounds
3236+
3237+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3238+
Vector3(400.0f, 400.0f, -1.2f));
3239+
// Interpolates at epsilon against LeftBottom to produce:
3240+
// t = (epsilon - -1.2) / (.3 - -1.2)
3241+
// = (epsilon + 1.2) / 1.5
3242+
// = 0.8000407
3243+
// Lerp(RightBottom, LeftBottom, 0.8000407) = (239.9919, 400, epsilon)
3244+
// = (3932026.667, 6553600)
3245+
// Cannot interpolate against RightTop because it also has W<0
3246+
3247+
// Min/Max X and Y of all the points generated above are:
3248+
// Min X == 222.2222
3249+
// Min Y == 222.2222
3250+
// Max X == 5242747
3251+
// Max Y == 6553600
3252+
3253+
Rect expect = Rect::MakeLTRB(222.2222f, 222.2222f, 5242747.f, 6553600.f);
3254+
3255+
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3256+
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3257+
}
3258+
3259+
TEST(RectTest, TransformAndClipBoundsThreeCornersClipped) {
3260+
// This matrix should clip three corners.
3261+
auto matrix = impeller::Matrix::MakeColumn(
3262+
// clang-format off
3263+
2.0f, 0.0f, 0.0f, -.02f,
3264+
0.0f, 2.0f, 0.0f, -.006f,
3265+
0.0f, 0.0f, 1.0f, 0.0f,
3266+
0.0f, 0.0f, 0.0f, 3.0f
3267+
// clang-format on
3268+
);
3269+
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3270+
3271+
// Exactly three of these homogenous results should have a W<0
3272+
//
3273+
// When W<0 we interpolate the point back towards the adjacent points
3274+
// that have W>0 to a location just greater than the W=0 half-plane.
3275+
// We interpolate them to W=epsilon where epsilon == 2^-14.
3276+
3277+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3278+
Vector3(200.0f, 200.0f, 0.4f));
3279+
// Contributes (200, 200) / 0.4 == (500, 500) to bounds
3280+
3281+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3282+
Vector3(400.0f, 200.0f, -1.6f));
3283+
// Interpolates at epsilon against LeftTop to produce:
3284+
// t = (epsilon - -1.6) / (.4 - -1.6)
3285+
// = (epsilon + 1.6) / 2
3286+
// = 0.8000305
3287+
// Lerp(RightTop, LeftTop, 0.8000305) = (239.9939, 200, epsilon)
3288+
// = (3932060, 3276800)
3289+
// Cannot interpolate against RightBottom because it also has W<0
3290+
3291+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3292+
Vector3(200.0f, 400.0f, -0.2f));
3293+
// Interpolates against LeftTop to produce:
3294+
// t = (epsilon - -.2) / (.4 - -.2)
3295+
// = (epsilon + .2) / .6
3296+
// = 0.333435
3297+
// Lerp(LeftBottom, LeftTop, .333435) = (200, 333.31299, epsilon)
3298+
// = (3276800, 5461000)
3299+
// Cannot interpolate against RightBottom because it also has W<0
3300+
3301+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3302+
Vector3(400.0f, 400.0f, -2.2f));
3303+
// Cannot interpolate against either RightTop or LeftBottom because
3304+
// both of those adjacent points transformed to a W<0 homogenous point.
3305+
3306+
// Min/Max X and Y of all the points generated above are:
3307+
// Min X == 500
3308+
// Min Y == 500
3309+
// Max X == 3932060
3310+
// Max Y == 5461000
3311+
3312+
Rect expect = Rect::MakeLTRB(500.0f, 500.0f, 3932060.f, 5461000.f);
3313+
3314+
EXPECT_FALSE(src.TransformAndClipBounds(matrix).IsEmpty());
3315+
EXPECT_RECT_NEAR(src.TransformAndClipBounds(matrix), expect);
3316+
}
3317+
3318+
TEST(RectTest, TransformAndClipBoundsAllFourCornersClipped) {
3319+
// This matrix should clip all four corners.
3320+
auto matrix = impeller::Matrix::MakeColumn(
3321+
// clang-format off
3322+
2.0f, 0.0f, 0.0f, -.025f,
3323+
0.0f, 2.0f, 0.0f, -.006f,
3324+
0.0f, 0.0f, 1.0f, 0.0f,
3325+
0.0f, 0.0f, 0.0f, 3.0f
3326+
// clang-format on
3327+
);
3328+
Rect src = Rect::MakeLTRB(100.0f, 100.0f, 200.0f, 200.0f);
3329+
3330+
// All of these should have a W<0
3331+
//
3332+
// When W<0 we interpolate the point back towards the adjacent points
3333+
// that have W>0 to a location just greater than the W=0 half-plane.
3334+
// We interpolate them to W=epsilon where epsilon == 2^-14.
3335+
3336+
// In this case, none of the homogenous results are in bounds (W > 0)
3337+
// so we can perform no interpolation - the operation is not visible.
3338+
3339+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftTop()),
3340+
Vector3(200.0f, 200.0f, -0.1f));
3341+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightTop()),
3342+
Vector3(400.0f, 200.0f, -2.6f));
3343+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetLeftBottom()),
3344+
Vector3(200.0f, 400.0f, -0.7f));
3345+
EXPECT_VECTOR3_NEAR(matrix.TransformHomogenous(src.GetRightBottom()),
3346+
Vector3(400.0f, 400.0f, -3.2f));
3347+
3348+
EXPECT_TRUE(src.TransformAndClipBounds(matrix).IsEmpty());
32443349
}
32453350

32463351
} // namespace testing

0 commit comments

Comments
 (0)