BSP Tree perf tests to match LayerSorter perf tests

cc/base/math_util.cc

 // Copyright 2012 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 "cc/base/math_util.h"
 
 #include <algorithm>
 #include <cmath>
 #include <limits>
 
@@ skipping 64 matching lines @@
   //    p = (1-t) h1 + (t) h2.
 
   // Technically this is a special case of the following assertion, but its a
   // good idea to keep it an explicit sanity check here.
   DCHECK_NE(h2.w(), h1.w());
   // Exactly one of h1 or h2 (but not both) must be on the negative side of the
   // w plane when this is called.
   DCHECK(h1.ShouldBeClipped() ^ h2.ShouldBeClipped());
 
   // ...or any positive non-zero small epsilon
-  SkMScalar w = 0.00001f;
+  SkMScalar w = 0.01f;

[enne (OOO), 2014/07/28 23:37:40]

Just for the record (and to jog my memory), this was a subjectively determined
value based on some 3d scenes you had looked at? In particular, I know there was
the FPS-esque one where 0.000001f caused severe clipping issues but 0.01f was
fine, right?

Why is this needed with the perf tests?

[troyhildebrandt, 2014/07/29 19:57:17]

It's necessary for the perf tests because without it, we get inaccuracies in the
floating point values in the vertices during clipping. The visual issues are
just a result of this, and those issues could possibly have an effect on
sorting/splitting.

   SkMScalar t = (w - h1.w()) / (h2.w() - h1.w());
 
   SkMScalar x = (SK_MScalar1 - t) * h1.x() + t * h2.x();
   SkMScalar y = (SK_MScalar1 - t) * h1.y() + t * h2.y();
   SkMScalar z = (SK_MScalar1 - t) * h1.z() + t * h2.z();
 
   return HomogeneousCoordinate(x, y, z, w);
 }
 
 static inline void ExpandBoundsToIncludePoint(float* xmin,
                                               float* xmax,
                                               float* ymin,
                                               float* ymax,
                                               const gfx::PointF& p) {
   *xmin = std::min(p.x(), *xmin);
   *xmax = std::max(p.x(), *xmax);
   *ymin = std::min(p.y(), *ymin);
   *ymax = std::max(p.y(), *ymax);
 }
 
 static inline void AddVertexToClippedQuad(const gfx::PointF& new_vertex,
                                           gfx::PointF clipped_quad[8],
                                           int* num_vertices_in_clipped_quad) {
   clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
   (*num_vertices_in_clipped_quad)++;
 }
 
+static inline void AddVertexToClippedQuad3d(const gfx::Point3F& new_vertex,
+                                            gfx::Point3F clipped_quad[8],
+                                            int* num_vertices_in_clipped_quad) {
+  clipped_quad[*num_vertices_in_clipped_quad] = new_vertex;
+  (*num_vertices_in_clipped_quad)++;
+}
+
 gfx::Rect MathUtil::MapEnclosingClippedRect(const gfx::Transform& transform,
                                             const gfx::Rect& src_rect) {
   if (transform.IsIdentityOrIntegerTranslation()) {
     return src_rect +
            gfx::Vector2d(
                static_cast<int>(SkMScalarToFloat(transform.matrix().get(0, 3))),
                static_cast<int>(
                    SkMScalarToFloat(transform.matrix().get(1, 3))));
   }
   return gfx::ToEnclosingRect(MapClippedRect(transform, gfx::RectF(src_rect)));
@@ skipping 122 matching lines @@
   if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
     AddVertexToClippedQuad(
         ComputeClippedPointForEdge(h4, h1).CartesianPoint2d(),
         clipped_quad,
         num_vertices_in_clipped_quad);
   }
 
   DCHECK_LE(*num_vertices_in_clipped_quad, 8);
 }
 
+bool MathUtil::MapClippedQuad3d(const gfx::Transform& transform,
+                                const gfx::QuadF& src_quad,
+                                gfx::Point3F clipped_quad[8],
+                                int* num_vertices_in_clipped_quad) {
+  HomogeneousCoordinate h1 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p1()));
+  HomogeneousCoordinate h2 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p2()));
+  HomogeneousCoordinate h3 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p3()));
+  HomogeneousCoordinate h4 =
+      MapHomogeneousPoint(transform, gfx::Point3F(src_quad.p4()));
+
+  // The order of adding the vertices to the array is chosen so that
+  // clockwise / counter-clockwise orientation is retained.
+
+  *num_vertices_in_clipped_quad = 0;
+
+  if (!h1.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h1.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h1.ShouldBeClipped() ^ h2.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h1, h2).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h2.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h2.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h2.ShouldBeClipped() ^ h3.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h2, h3).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h3.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h3.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h3.ShouldBeClipped() ^ h4.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h3, h4).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  if (!h4.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        h4.CartesianPoint3d(), clipped_quad, num_vertices_in_clipped_quad);
+  }
+
+  if (h4.ShouldBeClipped() ^ h1.ShouldBeClipped()) {
+    AddVertexToClippedQuad3d(
+        ComputeClippedPointForEdge(h4, h1).CartesianPoint3d(),
+        clipped_quad,
+        num_vertices_in_clipped_quad);
+  }
+
+  DCHECK_LE(*num_vertices_in_clipped_quad, 8);
+  return (*num_vertices_in_clipped_quad >= 4);
+}
+
 gfx::RectF MathUtil::ComputeEnclosingRectOfVertices(
     const gfx::PointF vertices[],
     int num_vertices) {
   if (num_vertices < 2)
     return gfx::RectF();
 
   float xmin = std::numeric_limits<float>::max();
   float xmax = -std::numeric_limits<float>::max();
   float ymin = std::numeric_limits<float>::max();
   float ymax = -std::numeric_limits<float>::max();
@@ skipping 113 matching lines @@
             h3.ShouldBeClipped() || h4.ShouldBeClipped();
 
   // Result will be invalid if clipped == true. But, compute it anyway just in
   // case, to emulate existing behavior.
   return gfx::QuadF(h1.CartesianPoint2d(),
                     h2.CartesianPoint2d(),
                     h3.CartesianPoint2d(),
                     h4.CartesianPoint2d());
 }
 
+gfx::QuadF MathUtil::MapQuad3d(const gfx::Transform& transform,
+                               const gfx::QuadF& q,
+                               gfx::Point3F* p,
+                               bool* clipped) {
+  if (transform.IsIdentityOrTranslation()) {
+    gfx::QuadF mapped_quad(q);
+    mapped_quad +=
+        gfx::Vector2dF(SkMScalarToFloat(transform.matrix().get(0, 3)),
+                       SkMScalarToFloat(transform.matrix().get(1, 3)));
+    *clipped = false;
+    p[0] = gfx::Point3F(mapped_quad.p1().x(), mapped_quad.p1().y(), 0.0f);
+    p[1] = gfx::Point3F(mapped_quad.p2().x(), mapped_quad.p2().y(), 0.0f);
+    p[2] = gfx::Point3F(mapped_quad.p3().x(), mapped_quad.p3().y(), 0.0f);
+    p[3] = gfx::Point3F(mapped_quad.p4().x(), mapped_quad.p4().y(), 0.0f);
+    return mapped_quad;
+  }
+
+  HomogeneousCoordinate h1 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p1()));
+  HomogeneousCoordinate h2 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p2()));
+  HomogeneousCoordinate h3 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p3()));
+  HomogeneousCoordinate h4 =
+      MapHomogeneousPoint(transform, gfx::Point3F(q.p4()));
+
+  *clipped = h1.ShouldBeClipped() || h2.ShouldBeClipped() ||
+             h3.ShouldBeClipped() || h4.ShouldBeClipped();
+
+  // Result will be invalid if clipped == true. But, compute it anyway just in
+  // case, to emulate existing behavior.
+  p[0] = h1.CartesianPoint3d();
+  p[1] = h2.CartesianPoint3d();
+  p[2] = h3.CartesianPoint3d();
+  p[3] = h4.CartesianPoint3d();
+
+  return gfx::QuadF(h1.CartesianPoint2d(),
+                    h2.CartesianPoint2d(),
+                    h3.CartesianPoint2d(),
+                    h4.CartesianPoint2d());
+}
+
 gfx::PointF MathUtil::MapPoint(const gfx::Transform& transform,
                                const gfx::PointF& p,
                                bool* clipped) {
   HomogeneousCoordinate h = MapHomogeneousPoint(transform, gfx::Point3F(p));
 
   if (h.w() > 0) {
     *clipped = false;
     return h.CartesianPoint2d();
   }
 
@@ skipping 255 matching lines @@
   return scoped_ptr<base::Value>(new base::FundamentalValue(
       std::min(value, std::numeric_limits<double>::max())));
 }
 
 scoped_ptr<base::Value> MathUtil::AsValueSafely(float value) {
   return scoped_ptr<base::Value>(new base::FundamentalValue(
       std::min(value, std::numeric_limits<float>::max())));
 }
 
 }  // namespace cc