Bug 1035611 - Part 1: Updated Matrix4x4::ProjectRectBounds to properly handle infinite values when untransformed rects cross the w=0 plane. r=mattwoodrow
authorKearwood (Kip) Gilbert <kgilbert@mozilla.com>
Fri, 13 Mar 2015 16:42:00 -0400
changeset 264201 99153c410bad53b7cfde09da3fd4162fc0998513
parent 264200 84b451463f065af1643e310322e6665f6fbf5983
child 264202 cee8f9d83b7ed50814febaab616eac574564ad56
push id4718
push userraliiev@mozilla.com
push dateMon, 11 May 2015 18:39:53 +0000
treeherdermozilla-beta@c20c4ef55f08 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmattwoodrow
bugs1035611
milestone39.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1035611 - Part 1: Updated Matrix4x4::ProjectRectBounds to properly handle infinite values when untransformed rects cross the w=0 plane. r=mattwoodrow - Added specialized rect clipping functionality to Matrix4x4::ProjectRectBounds so we don't have to return infinite values when rects cross the w=0 plane in homogenous coordinate space. - Updated callsites of ProjectRectBounds to pass a clipping rect that is appropriate for the units that are returned.
gfx/2d/Matrix.cpp
gfx/2d/Matrix.h
layout/base/FrameLayerBuilder.cpp
layout/base/nsDisplayList.cpp
layout/base/nsLayoutUtils.cpp
--- a/gfx/2d/Matrix.cpp
+++ b/gfx/2d/Matrix.cpp
@@ -119,74 +119,101 @@ Matrix4x4::TransformBounds(const Rect& a
   }
 
   return Rect(min_x, min_y, max_x - min_x, max_y - min_y);
 }
 
 Point4D ComputePerspectivePlaneIntercept(const Point4D& aFirst,
                                          const Point4D& aSecond)
 {
-  // FIXME: See bug 1035611
-  // Since we can't easily deal with points as w=0 (since we divide by w), we
-  // approximate this by finding a point with w just greater than 0. Unfortunately
-  // this is a tradeoff between accuracy and floating point precision.
+  // This function will always return a point with a w value of 0.
+  // The X, Y, and Z components will point towards an infinite vanishing
+  // point.
 
-  // We want to interpolate aFirst and aSecond to find a point as close to
-  // the positive side of the w=0 plane as possible.
+  // We want to interpolate aFirst and aSecond to find the point intersecting
+  // with the w=0 plane.
 
   // Since we know what we want the w component to be, we can rearrange the
   // interpolation equation and solve for t.
-  float w = 0.00001f;
-  float t = (w - aFirst.w) / (aSecond.w - aFirst.w);
+  float t = -aFirst.w / (aSecond.w - aFirst.w);
 
   // Use t to find the remainder of the components
   return aFirst + (aSecond - aFirst) * t;
 }
 
-Rect Matrix4x4::ProjectRectBounds(const Rect& aRect) const
+Rect Matrix4x4::ProjectRectBounds(const Rect& aRect, const Rect &aClip) const
 {
+  // This function must never return std::numeric_limits<Float>::max() or any
+  // other arbitrary large value in place of inifinity.  This often occurs when
+  // aRect is an inversed projection matrix or when aRect is transformed to be
+  // partly behind and in front of the camera (w=0 plane in homogenous
+  // coordinates) - See Bug 1035611
+
+  // Some call-sites will call RoundGfxRectToAppRect which clips both the
+  // extents and dimensions of the rect to be bounded by nscoord_MAX.
+  // If we return a Rect that, when converted to nscoords, has a width or height
+  // greater than nscoord_MAX, RoundGfxRectToAppRect will clip the overflow
+  // off both the min and max end of the rect after clipping the extents of the
+  // rect, resulting in a translation of the rect towards the infinite end.
+
+  // The bounds returned by ProjectRectBounds are expected to be clipped only on
+  // the edges beyond the bounds of the coordinate system; otherwise, the
+  // clipped bounding box would be smaller than the correct one and result
+  // bugs such as incorrect culling (eg. Bug 1073056)
+
+  // To address this without requiring all code to work in homogenous
+  // coordinates or interpret infinite values correctly, a specialized
+  // clipping function is integrated into ProjectRectBounds.
+
+  // Callers should pass an aClip value that represents the extents to clip
+  // the result to, in the same coordinate system as aRect.
   Point4D points[4];
 
   points[0] = ProjectPoint(aRect.TopLeft());
   points[1] = ProjectPoint(aRect.TopRight());
   points[2] = ProjectPoint(aRect.BottomRight());
   points[3] = ProjectPoint(aRect.BottomLeft());
 
   Float min_x = std::numeric_limits<Float>::max();
   Float min_y = std::numeric_limits<Float>::max();
   Float max_x = -std::numeric_limits<Float>::max();
   Float max_y = -std::numeric_limits<Float>::max();
 
-  bool foundPoint = false;
   for (int i=0; i<4; i++) {
     // Only use points that exist above the w=0 plane
     if (points[i].HasPositiveWCoord()) {
-      foundPoint = true;
-      Point point2d = points[i].As2DPoint();
-      min_x = min<Float>(point2d.x, min_x);
-      max_x = max<Float>(point2d.x, max_x);
-      min_y = min<Float>(point2d.y, min_y);
-      max_y = max<Float>(point2d.y, max_y);
+      Point point2d = aClip.ClampPoint(points[i].As2DPoint());
+      min_x = std::min<Float>(point2d.x, min_x);
+      max_x = std::max<Float>(point2d.x, max_x);
+      min_y = std::min<Float>(point2d.y, min_y);
+      max_y = std::max<Float>(point2d.y, max_y);
     }
 
     int next = (i == 3) ? 0 : i + 1;
     if (points[i].HasPositiveWCoord() != points[next].HasPositiveWCoord()) {
-      // If the line between two points crosses the w=0 plane, then interpolate a point
-      // as close to the w=0 plane as possible and use that instead.
+      // If the line between two points crosses the w=0 plane, then interpolate
+      // to find the point of intersection with the w=0 plane and use that
+      // instead.
       Point4D intercept = ComputePerspectivePlaneIntercept(points[i], points[next]);
-
-      Point point2d = intercept.As2DPoint();
-      min_x = min<Float>(point2d.x, min_x);
-      max_x = max<Float>(point2d.x, max_x);
-      min_y = min<Float>(point2d.y, min_y);
-      max_y = max<Float>(point2d.y, max_y);
+      // Since intercept.w will always be 0 here, we interpret x,y,z as a
+      // direction towards an infinite vanishing point.
+      if (intercept.x < 0.0f) {
+        min_x = aClip.x;
+      } else if (intercept.x > 0.0f) {
+        max_x = aClip.XMost();
+      }
+      if (intercept.y < 0.0f) {
+        min_y = aClip.y;
+      } else if (intercept.y > 0.0f) {
+        max_y = aClip.YMost();
+      }
     }
   }
 
-  if (!foundPoint) {
+  if (max_x <= min_x || max_y <= min_y) {
     return Rect(0, 0, 0, 0);
   }
 
   return Rect(min_x, min_y, max_x - min_x, max_y - min_y);
 }
 
 bool
 Matrix4x4::Invert()
--- a/gfx/2d/Matrix.h
+++ b/gfx/2d/Matrix.h
@@ -473,17 +473,17 @@ public:
 
     // Solving for z when z' = 0 gives us:
     float z = -(aPoint.x * _13 + aPoint.y * _23 + _43) / _33;
 
     // Compute the transformed point
     return *this * Point4D(aPoint.x, aPoint.y, z, 1);
   }
 
-  Rect ProjectRectBounds(const Rect& aRect) const;
+  Rect ProjectRectBounds(const Rect& aRect, const Rect &aClip) const;
 
   static Matrix4x4 From2D(const Matrix &aMatrix) {
     Matrix4x4 matrix;
     matrix._11 = aMatrix._11;
     matrix._12 = aMatrix._12;
     matrix._21 = aMatrix._21;
     matrix._22 = aMatrix._22;
     matrix._41 = aMatrix._31;
--- a/layout/base/FrameLayerBuilder.cpp
+++ b/layout/base/FrameLayerBuilder.cpp
@@ -1982,29 +1982,31 @@ SetOuterVisibleRegion(Layer* aLayer, nsI
       aOuterVisibleRegion->And(*aOuterVisibleRegion, *aLayerContentsVisibleRect);
     }
   } else {
     nsIntRect outerRect = aOuterVisibleRegion->GetBounds();
     // if 'transform' is not invertible, then nothing will be displayed
     // for the layer, so it doesn't really matter what we do here
     Rect outerVisible(outerRect.x, outerRect.y, outerRect.width, outerRect.height);
     transform.Invert();
-    gfxRect layerVisible = ThebesRect(transform.ProjectRectBounds(outerVisible));
+
+    Rect layerContentsVisible(-float(INT32_MAX) / 2, -float(INT32_MAX) / 2,
+                              float(INT32_MAX), float(INT32_MAX));
     if (aLayerContentsVisibleRect) {
       NS_ASSERTION(aLayerContentsVisibleRect->width >= 0 &&
                    aLayerContentsVisibleRect->height >= 0,
                    "Bad layer contents rectangle");
       // restrict to aLayerContentsVisibleRect before call GfxRectToIntRect,
       // in case layerVisible is extremely large (as it can be when
       // projecting through the inverse of a 3D transform)
-      gfxRect layerContentsVisible(
+      layerContentsVisible = Rect(
           aLayerContentsVisibleRect->x, aLayerContentsVisibleRect->y,
           aLayerContentsVisibleRect->width, aLayerContentsVisibleRect->height);
-      layerVisible.IntersectRect(layerVisible, layerContentsVisible);
     }
+    gfxRect layerVisible = ThebesRect(transform.ProjectRectBounds(outerVisible, layerContentsVisible));
     layerVisible.RoundOut();
     nsIntRect visRect;
     if (gfxUtils::GfxRectToIntRect(layerVisible, &visRect)) {
       *aOuterVisibleRegion = visRect;
     } else  {
       aOuterVisibleRegion->SetEmpty();
     }
   }
--- a/layout/base/nsDisplayList.cpp
+++ b/layout/base/nsDisplayList.cpp
@@ -5696,25 +5696,25 @@ void nsDisplayTransform::HitTest(nsDispl
                            1, 1);
 
   } else {
     Rect originalRect(NSAppUnitsToFloatPixels(aRect.x, factor),
                       NSAppUnitsToFloatPixels(aRect.y, factor),
                       NSAppUnitsToFloatPixels(aRect.width, factor),
                       NSAppUnitsToFloatPixels(aRect.height, factor));
 
-    Rect rect = matrix.ProjectRectBounds(originalRect);
 
     bool snap;
     nsRect childBounds = mStoredList.GetBounds(aBuilder, &snap);
     Rect childGfxBounds(NSAppUnitsToFloatPixels(childBounds.x, factor),
                         NSAppUnitsToFloatPixels(childBounds.y, factor),
                         NSAppUnitsToFloatPixels(childBounds.width, factor),
                         NSAppUnitsToFloatPixels(childBounds.height, factor));
-    rect = rect.Intersect(childGfxBounds);
+
+    Rect rect = matrix.ProjectRectBounds(originalRect, childGfxBounds);
 
     resultingRect = nsRect(NSFloatPixelsToAppUnits(float(rect.X()), factor),
                            NSFloatPixelsToAppUnits(float(rect.Y()), factor),
                            NSFloatPixelsToAppUnits(float(rect.Width()), factor),
                            NSFloatPixelsToAppUnits(float(rect.Height()), factor));
   }
 
   if (resultingRect.IsEmpty()) {
@@ -5944,18 +5944,17 @@ bool nsDisplayTransform::UntransformRect
               NSAppUnitsToFloatPixels(aTransformedBounds.width, factor),
               NSAppUnitsToFloatPixels(aTransformedBounds.height, factor));
 
   Rect childGfxBounds(NSAppUnitsToFloatPixels(aChildBounds.x, factor),
                       NSAppUnitsToFloatPixels(aChildBounds.y, factor),
                       NSAppUnitsToFloatPixels(aChildBounds.width, factor),
                       NSAppUnitsToFloatPixels(aChildBounds.height, factor));
 
-  result = ToMatrix4x4(transform.Inverse()).ProjectRectBounds(result);
-  result = result.Intersect(childGfxBounds);
+  result = ToMatrix4x4(transform.Inverse()).ProjectRectBounds(result, childGfxBounds);
   *aOutRect = nsLayoutUtils::RoundGfxRectToAppRect(ThebesRect(result), factor);
   return true;
 }
 
 bool nsDisplayTransform::UntransformVisibleRect(nsDisplayListBuilder* aBuilder,
                                                 nsRect *aOutRect)
 {
   const gfx3DMatrix& matrix = To3DMatrix(GetTransform());
@@ -5972,18 +5971,17 @@ bool nsDisplayTransform::UntransformVisi
   bool snap;
   nsRect childBounds = mStoredList.GetBounds(aBuilder, &snap);
   Rect childGfxBounds(NSAppUnitsToFloatPixels(childBounds.x, factor),
                       NSAppUnitsToFloatPixels(childBounds.y, factor),
                       NSAppUnitsToFloatPixels(childBounds.width, factor),
                       NSAppUnitsToFloatPixels(childBounds.height, factor));
 
   /* We want to untransform the matrix, so invert the transformation first! */
-  result = ToMatrix4x4(matrix.Inverse()).ProjectRectBounds(result);
-  result = result.Intersect(childGfxBounds);
+  result = ToMatrix4x4(matrix.Inverse()).ProjectRectBounds(result, childGfxBounds);
 
   *aOutRect = nsLayoutUtils::RoundGfxRectToAppRect(ThebesRect(result), factor);
 
   return true;
 }
 
 void
 nsDisplayTransform::WriteDebugInfo(std::stringstream& aStream)
--- a/layout/base/nsLayoutUtils.cpp
+++ b/layout/base/nsLayoutUtils.cpp
@@ -2499,17 +2499,25 @@ nsLayoutUtils::TransformRect(nsIFrame* a
     1.0f / aFromFrame->PresContext()->AppUnitsPerDevPixel();
   float devPixelsPerAppUnitToFrame =
     1.0f / aToFrame->PresContext()->AppUnitsPerDevPixel();
   gfx::Rect toDevPixels = downToDest.ProjectRectBounds(
     upToAncestor.ProjectRectBounds(
       gfx::Rect(aRect.x * devPixelsPerAppUnitFromFrame,
                 aRect.y * devPixelsPerAppUnitFromFrame,
                 aRect.width * devPixelsPerAppUnitFromFrame,
-                aRect.height * devPixelsPerAppUnitFromFrame)));
+                aRect.height * devPixelsPerAppUnitFromFrame),
+      Rect(-std::numeric_limits<Float>::max() * 0.5f,
+           -std::numeric_limits<Float>::max() * 0.5f,
+           std::numeric_limits<Float>::max(),
+           std::numeric_limits<Float>::max())),
+    Rect(-std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame * 0.5f,
+         -std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame * 0.5f,
+         std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame,
+         std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame));
   aRect.x = toDevPixels.x / devPixelsPerAppUnitToFrame;
   aRect.y = toDevPixels.y / devPixelsPerAppUnitToFrame;
   aRect.width = toDevPixels.width / devPixelsPerAppUnitToFrame;
   aRect.height = toDevPixels.height / devPixelsPerAppUnitToFrame;
   return TRANSFORM_SUCCEEDED;
 }
 
 nsRect