Perform BSP polygon splitting and orientation selection in a single step.

cc/output/bsp_tree_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.
 
 #include "cc/output/bsp_tree.h"
 
 #include <stddef.h>
 
 #include <deque>
 #include <memory>
@@ skipping 27 matching lines @@
     BspTree bsp_tree(test_polygons);
 
     std::vector<DrawPolygon*> sorted_list;
     BspWalkActionToVector action_handler(&sorted_list);
     bsp_tree.TraverseWithActionHandler(&action_handler);
 
     EXPECT_SORTED_LISTS_EQ(sorted_list, compare_list);
     EXPECT_TRUE(VerifySidedness(bsp_tree.root()));
   }
 
+  static BspCompareResult SideCompare(const DrawPolygon& a,
+                                      const DrawPolygon& b) {
+    const float split_threshold = 0.05f;
+    bool pos = false;
+    bool neg = false;
+    for (const auto& pt : a.points()) {
+      float dist = b.SignedPointDistance(pt);
+      neg |= dist < -split_threshold;
+      pos |= dist > split_threshold;
+    }
+    if (pos && neg)
+      return BSP_SPLIT;
+    if (neg)
+      return BSP_BACK;
+    if (pos)
+      return BSP_FRONT;
+    double dot = gfx::DotProduct(a.normal(), b.normal());
+    if ((dot >= 0.0f && a.order_index() >= b.order_index()) ||
+        (dot <= 0.0f && a.order_index() <= b.order_index())) {
+      // The sign of the dot product of the normals along with document order
+      // determine which side it goes on, the vertices are ambiguous.
+      return BSP_COPLANAR_BACK;
+    }
+    return BSP_COPLANAR_FRONT;
+  }
+
   static bool VerifySidedness(const std::unique_ptr<BspNode>& node) {
     // We check if both the front and back child nodes have geometry that is
     // completely on the expected side of the current node.
     bool front_ok = true;
     bool back_ok = true;
     if (node->back_child) {
       // Make sure the back child lies entirely behind this node.
-      BspCompareResult result = DrawPolygon::SideCompare(
-          *(node->back_child->node_data), *(node->node_data));
+      BspCompareResult result =
+          SideCompare(*(node->back_child->node_data), *(node->node_data));
       if (result != BSP_BACK) {
         return false;
       }
       back_ok = VerifySidedness(node->back_child);
     }
     // Make sure the front child lies entirely in front of this node.
     if (node->front_child) {
-      BspCompareResult result = DrawPolygon::SideCompare(
-          *(node->front_child->node_data), *(node->node_data));
+      BspCompareResult result =
+          SideCompare(*(node->front_child->node_data), *(node->node_data));
       if (result != BSP_FRONT) {
         return false;
       }
       front_ok = VerifySidedness(node->front_child);
     }
     if (!back_ok || !front_ok) {
       return false;
     }
 
     // Now we need to make sure our coplanar geometry is all actually coplanar.
     for (size_t i = 0; i < node->coplanars_front.size(); i++) {
-      BspCompareResult result = DrawPolygon::SideCompare(
-          *(node->coplanars_front[i]), *(node->node_data));
+      BspCompareResult result =
+          SideCompare(*(node->coplanars_front[i]), *(node->node_data));
       if (result != BSP_COPLANAR_FRONT) {
         return false;
       }
     }
     for (size_t i = 0; i < node->coplanars_back.size(); i++) {
-      BspCompareResult result = DrawPolygon::SideCompare(
-          *(node->coplanars_back[i]), *(node->node_data));
+      BspCompareResult result =
+          SideCompare(*(node->coplanars_back[i]), *(node->node_data));
       if (result != BSP_COPLANAR_BACK) {
         return false;
       }
     }
     return true;
   }
 };
 
 // Simple standing quads all parallel with each other, causing no splits.
 TEST(BspTreeTest, NoSplit) {
@@ skipping 246 matching lines @@
   polygon_list.push_back(std::move(polygon_c));
   polygon_list.push_back(std::move(polygon_d));
 
   int compare_ids[] = {3, 0, 1, 2, 3};
   std::vector<int> compare_list = INT_VECTOR_FROM_ARRAY(compare_ids);
   BspTreeTest::RunTest(&polygon_list, compare_list);
 }
 
 }  // namespace
 }  // namespace cc