added fix that deals with precision in layer sorter

cc/layer_sorter.cc

 // Copyright 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 
 #include "cc/layer_sorter.h"
 
 #include <deque>
 #include <limits>
 #include <vector>
 
 #include "base/logging.h"
 #include "cc/math_util.h"
 #include "cc/render_surface_impl.h"
 #include <public/WebTransformationMatrix.h>
 
 using namespace std;
 using WebKit::WebTransformationMatrix;
 
 namespace cc {
 
+// This epsilon is used to determine if two layers are too close to each other
+// to be able to tell which is in front of the other.  It's a relative epsilon
+// so it is robust to changes in scene scale.  This value was chosen by picking
+// a value near machine epsilon and then increasing it until the flickering on
+// the test scene went away.
+const float LAYER_EPSILON = 1e-4f;

[enne (OOO), 2012/11/01 22:55:23]

style nit: kLayerEpsilon

+
 inline static float perpProduct(const gfx::Vector2dF& u, const gfx::Vector2dF& v)
 {
     return u.x() * v.y() - u.y() * v.x();
 }
 
 // Tests if two edges defined by their endpoints (a,b) and (c,d) intersect. Returns true and the
 // point of intersection if they do and false otherwise.
 static bool edgeEdgeTest(const gfx::PointF& a, const gfx::PointF& b, const gfx::PointF& c, const gfx::PointF& d, gfx::PointF& r)
 {
     gfx::Vector2dF u = b - a;
@@ skipping 74 matching lines @@
                              r))
                 overlapPoints.push_back(r);
 
     if (overlapPoints.empty())
         return None;
 
     // Check the corresponding layer depth value for all overlap points to determine
     // which layer is in front.
     float maxPositive = 0;
     float maxNegative = 0;
+
+    // This flag tracks the existance of a numerically accurate seperation
+    // between two layers.  If there is no accurate seperation, the layers
+    // cannot be effectively sorted.
+    bool accurate = false;

[shawnsingh, 2012/11/01 23:03:57]

Could we move the computation of "accurate" and associated comments into a
simple trivial helper function?

+
     for (unsigned o = 0; o < overlapPoints.size(); o++) {
         float za = a->layerZFromProjectedPoint(overlapPoints[o]);
         float zb = b->layerZFromProjectedPoint(overlapPoints[o]);
 
+        // Here we attempt to avoid numeric issues with layers that are too
+        // close together.  If we have 2-sided quads that are very close
+        // together then we will draw them in document order to avoid
+        // flickering.  The correct solution is for the content maker to turn
+        // on back-face culling or move the quads apart (if they're not two
+        // sides of one object).
+        float absDif = fabsf(zb - za);
+        float absMax = fmax(fabs(zb), fabs(za));

[shawnsingh, 2012/11/01 23:03:57]

We probably should be consistent in our usage of fabsf() versus fabs()

[danakj, 2012/11/01 23:06:34]

Why aren't we using std::abs() from <cmath> ?

+        // Check to see if we've got a result with a reasonable amount of error.
+        if (absDif > LAYER_EPSILON * absMax)

[shawnsingh, 2012/11/01 23:03:57]

I'm still not understanding exactly how this checks ulp-level precision?  this
seems like a relative threshold based on "within percent accuracy" where
LAYER_EPSILON is that percentage.  I'm pretty sure that's not exactly the same
as ulp-thresholding.  Can we discuss it offline briefly?

That said, it might be acceptable to use relative thresholding here than
ulp-level thresholding.

+          accurate = true;
+
         float diff = za - zb;
         if (diff > maxPositive)
             maxPositive = diff;
         if (diff < maxNegative)
             maxNegative = diff;
     }
 
+    // If we can't tell which should come first, we use document order.
+    if (!accurate)
+      return ABeforeB;
+
     float maxDiff = (fabsf(maxPositive) > fabsf(maxNegative) ? maxPositive : maxNegative);
 
     // If the results are inconsistent (and the z difference substantial to rule out
     // numerical errors) then the layers are intersecting. We will still return an
     // order based on the maximum depth difference but with an edge weight of zero
     // these layers will get priority if a graph cycle is present and needs to be broken.
     if (maxPositive > zThreshold && maxNegative < -zThreshold)
         weight = 0;
     else
         weight = fabsf(maxDiff);
@@ skipping 269 matching lines @@
         *it = sortedList[count++]->layer;
 
     DVLOG(2) << "Sorting end ----";
 
     m_nodes.clear();
     m_edges.clear();
     m_activeEdges.clear();
 }
 
 }