Correct polygon splitting in an almost-coplanar case.

cc/quads/draw_polygon_unittest.cc

 // Copyright 2014 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.
 
 // We would like to use M_PI on windows too.
 #ifdef _WIN32
 #define _USE_MATH_DEFINES
 #endif
 
 #include <stddef.h>
 
 #include <limits>
 #include <vector>
 
 #include "base/memory/ptr_util.h"
+#include "base/stl_util.h"
 #include "cc/output/bsp_compare_result.h"
 #include "cc/quads/draw_polygon.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "ui/gfx/transform.h"
 
 namespace cc {
 
 #if !defined(OS_WIN)
 void DrawPolygon::RecomputeNormalForTesting() {
   ConstructNormal();
@@ skipping 453 matching lines @@
   test_points_b.push_back(gfx::Point3F(1.0f, 0.0f, 0.0f));
   test_points_b.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
   test_points_b.push_back(gfx::Point3F(0.0f, 0.0f, 10.0f));
   test_points_b.push_back(gfx::Point3F(10.0f, 0.0f, 10.0f));
   test_points_b.push_back(gfx::Point3F(10.0f, 0.0f, 9.0f));
 
   ValidatePointsWithinDeltaOf(*front_polygon, test_points_a, 1e-6f);
   ValidatePointsWithinDeltaOf(*back_polygon, test_points_b, 1e-6f);
 }
 
+// This test was derived from crbug.com/693826. An almost coplanar
+// pair of polygons are used for splitting. In this case, the
+// splitting plane distance signs are [ 0 0 + - ]. This configuration
+// represents a case where snapping to the splitting plane causes the
+// polygon to become twisted. Splitting should still give a valid
+// result, indicated by all four of the input split polygon vertices
+// being present in the output polygons.
+TEST(DrawPolygonSplitTest, AlmostCoplanarSplit) {
+  std::vector<gfx::Point3F> vertices_a;
+  vertices_a.push_back(gfx::Point3F(723.814758300781250f, 552.810119628906250f,
+                                    -206.656036376953125f));
+  vertices_a.push_back(gfx::Point3F(797.634155273437500f, 549.095703125000000f,
+                                    -209.802902221679688f));
+  vertices_a.push_back(gfx::Point3F(799.264648437500000f, 490.325805664062500f,
+                                    -172.261627197265625f));
+  vertices_a.push_back(gfx::Point3F(720.732421875000000f, 493.944458007812500f,
+                                    -168.700469970703125f));
+  std::vector<gfx::Point3F> vertices_b;
+  vertices_b.push_back(gfx::Point3F(720.631286621093750f, 487.595977783203125f,
+                                    -164.681198120117188f));
+  vertices_b.push_back(gfx::Point3F(799.672851562500000f, 484.059020996093750f,
+                                    -168.219161987304688f));
+  vertices_b.push_back(gfx::Point3F(801.565490722656250f, 416.416809082031250f,
+                                    -125.007690429687500f));
+  vertices_b.push_back(gfx::Point3F(717.096801757812500f, 419.792327880859375f,
+                                    -120.967689514160156f));
+
+  CREATE_NEW_DRAW_POLYGON_PTR(
+      splitting_polygon, vertices_a,
+      gfx::Vector3dF(-0.062916249036789f, -0.538499474525452f,
+                     -0.840273618698120f),
+      0);
+  CREATE_NEW_DRAW_POLYGON_PTR(
+      split_polygon, vertices_b,
+      gfx::Vector3dF(-0.061713f, -0.538550f, -0.840330f), 1);
+
+  std::unique_ptr<DrawPolygon> front_polygon;
+  std::unique_ptr<DrawPolygon> back_polygon;
+  bool is_coplanar;
+
+  splitting_polygon->SplitPolygon(std::move(split_polygon), &front_polygon,
+                                  &back_polygon, &is_coplanar);
+
+  EXPECT_FALSE(is_coplanar);
+  EXPECT_TRUE(front_polygon != nullptr);
+  EXPECT_TRUE(back_polygon != nullptr);
+
+  for (auto vertex : vertices_b) {
+    EXPECT_TRUE(base::ContainsValue(front_polygon->points(), vertex) ||
+                base::ContainsValue(back_polygon->points(), vertex));
+  }
+}
+
 // In this test we cut the corner of a quad so that it creates a triangle and
 // a pentagon as a result, and then cut the pentagon.
 TEST(DrawPolygonSplitTest, DoubleSplit) {
   std::vector<gfx::Point3F> vertices_a;
   vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
   vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 10.0f));
   vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 10.0f));
   vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
   std::vector<gfx::Point3F> vertices_b;
   vertices_b.push_back(gfx::Point3F(2.0f, 5.0f, 1.0f));
@@ skipping 12 matching lines @@
   bool is_coplanar;
 
   polygon_b->SplitPolygon(std::move(polygon_a), &front_polygon, &back_polygon,
                           &is_coplanar);
   EXPECT_FALSE(is_coplanar);
   EXPECT_TRUE(front_polygon != nullptr);
   EXPECT_TRUE(back_polygon != nullptr);
 
   EXPECT_EQ(3u, front_polygon->points().size());
   EXPECT_EQ(5u, back_polygon->points().size());
+  std::vector<gfx::Point3F> saved_back_polygon_vertices =
+      back_polygon->points();
 
   std::vector<gfx::Point3F> vertices_c;
   vertices_c.push_back(gfx::Point3F(0.0f, 0.0f, 10.0f));
   vertices_c.push_back(gfx::Point3F(1.0f, -0.05f, 0.0f));
   vertices_c.push_back(gfx::Point3F(10.0f, 0.05f, 9.0f));
 
   CREATE_NEW_DRAW_POLYGON_PTR(polygon_c, vertices_c,
                               gfx::Vector3dF(0.005555f, -0.99997f, 0.005555f),
                               0);
   polygon_c->RecomputeNormalForTesting();
 
   std::unique_ptr<DrawPolygon> second_front_polygon;
   std::unique_ptr<DrawPolygon> second_back_polygon;
 
   polygon_c->SplitPolygon(std::move(back_polygon), &second_front_polygon,
                           &second_back_polygon, &is_coplanar);
   EXPECT_FALSE(is_coplanar);
   EXPECT_TRUE(second_front_polygon != nullptr);
   EXPECT_TRUE(second_back_polygon != nullptr);
 
-  EXPECT_EQ(3u, second_front_polygon->points().size());
+  EXPECT_EQ(4u, second_front_polygon->points().size());
   EXPECT_EQ(3u, second_back_polygon->points().size());
+
+  for (auto vertex : saved_back_polygon_vertices) {
+    EXPECT_TRUE(base::ContainsValue(second_front_polygon->points(), vertex) ||
+                base::ContainsValue(second_back_polygon->points(), vertex));
+  }
 }
 
 TEST(DrawPolygonTransformTest, TransformNormal) {
   std::vector<gfx::Point3F> vertices_a;
   vertices_a.push_back(gfx::Point3F(1.0f, 0.0f, 1.0f));
   vertices_a.push_back(gfx::Point3F(-1.0f, 0.0f, -1.0f));
   vertices_a.push_back(gfx::Point3F(0.0f, 1.0f, 0.0f));
   CREATE_NEW_DRAW_POLYGON(polygon_a, vertices_a,
                           gfx::Vector3dF(sqrt(2) / 2, 0.0f, -sqrt(2) / 2), 0);
   EXPECT_NORMAL(polygon_a, sqrt(2) / 2, 0.0f, -sqrt(2) / 2);
 
   gfx::Transform transform;
   transform.RotateAboutYAxis(45.0f);
   // This would transform the vertices as well, but we are transforming a
   // DrawPolygon with 0 vertices just to make sure our normal transformation
   // using the inverse tranpose matrix gives us the right result.
   polygon_a.TransformToScreenSpace(transform);
 
   // Note: We use EXPECT_FLOAT_WITHIN_EPSILON instead of EXPECT_FLOAT_EQUAL here
   // because some architectures (e.g., Arm64) employ a fused multiply-add
   // instruction which causes rounding asymmetry and reduces precision.
   // http://crbug.com/401117.
   EXPECT_NORMAL(polygon_a, 0.0f, 0.0f, -1.0f);
 }
 
 }  // namespace
 }  // namespace cc