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

cc/quads/draw_polygon.cc

Index: cc/quads/draw_polygon.cc
diff --git a/cc/quads/draw_polygon.cc b/cc/quads/draw_polygon.cc
index 770d241570bb06755f9321c7794efbfa0460d0ee..dd7a24c4428e45d3c57b35bb80d8cec725381b51 100644
--- a/cc/quads/draw_polygon.cc
+++ b/cc/quads/draw_polygon.cc
@@ -8,6 +8,7 @@
 
 #include <vector>
 
+#include "base/memory/ptr_util.h"
 #include "cc/output/bsp_compare_result.h"
 #include "cc/quads/draw_quad.h"
 
@@ -29,6 +30,15 @@ static const float compare_threshold = 0.1f;
 static const float split_threshold = 0.05f;
 
 static const float normalized_threshold = 0.001f;
+
+void PointInterpolate(const gfx::Point3F& from,
+                      const gfx::Point3F& to,
+                      double delta,
+                      gfx::Point3F* out) {
+  out->SetPoint(from.x() + (to.x() - from.x()) * delta,
+                from.y() + (to.y() - from.y()) * delta,
+                from.z() + (to.z() - from.z()) * delta);
+}
 }  // namespace
 
 namespace cc {
@@ -177,55 +187,6 @@ BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a,
   return BSP_COPLANAR_FRONT;
 }
 
-static bool LineIntersectPlane(const gfx::Point3F& line_start,
-                               const gfx::Point3F& line_end,
-                               const gfx::Point3F& plane_origin,
-                               const gfx::Vector3dF& plane_normal,
-                               gfx::Point3F* intersection,
-                               float distance_threshold) {
-  const gfx::Vector3dF line_start_vec(line_start.x(), line_start.y(),
-                                      line_start.z());
-  const gfx::Vector3dF line_end_vec(line_end.x(), line_end.y(), line_end.z());
-  const gfx::Vector3dF plane_origin_vec(plane_origin.x(), plane_origin.y(),
-                                        plane_origin.z());
-
-  double plane_d = -gfx::DotProduct(plane_origin_vec, plane_normal);
-
-  double end_distance = gfx::DotProduct(line_end_vec, plane_normal) + plane_d;
-  if (std::abs(end_distance) <= distance_threshold) {
-    // No intersection if |line_end| is within |distance_threshold| of plane.
-    return false;
-  }
-
-  double start_distance =
-      gfx::DotProduct(line_start_vec, plane_normal) + plane_d;
-  if (std::abs(start_distance) <= distance_threshold) {
-    // Intersection at |line_start| if |line_start| is within
-    // |distance_threshold| of plane.
-    intersection->SetPoint(line_start.x(), line_start.y(), line_start.z());
-    return true;
-  }
-
-  // If signs differ, we cross the plane.
-  if (start_distance * end_distance < 0.0) {
-    // Plane: P . N + d = 0   [ d = -(plane_normal . plane_origin) ]
-    // Ray:   P = P0 + Pd * t [ P0 = line_start, Pd = line_end - line_start ]
-    // Substituting:
-    //   (P0 + Pd * t) . N + d = 0
-    //   P0 . N + t * Pd . N + d = 0
-    //   t = -(P0 . N + d)  / Pd . N
-
-    gfx::Vector3dF line_delta = line_end - line_start;
-    double t = -start_distance / gfx::DotProduct(plane_normal, line_delta);
-    intersection->SetPoint(line_start.x() + line_delta.x() * t,
-                           line_start.y() + line_delta.y() * t,
-                           line_start.z() + line_delta.z() * t);
-
-    return true;
-  }
-  return false;
-}
-
 // This function is separate from ApplyTransform because it is often unnecessary
 // to transform the normal with the rest of the polygon.
 // When drawing these polygons, it is necessary to move them back into layer
@@ -275,84 +236,141 @@ void DrawPolygon::TransformToLayerSpace(
   normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
 }
 
-bool DrawPolygon::Split(const DrawPolygon& splitter,
-                        std::unique_ptr<DrawPolygon>* front,
-                        std::unique_ptr<DrawPolygon>* back) {
-  gfx::Point3F intersections[2];
-  std::vector<gfx::Point3F> out_points[2];
-  // vertex_before stores the index of the vertex before its matching
-  // intersection.
-  // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane
-  // which resulted in the line/plane intersection giving us intersections[0].
-  size_t vertex_before[2];
-  size_t points_size = points_.size();
-  size_t current_intersection = 0;
-
-  size_t current_vertex = 0;
-  // We will only have two intersection points because we assume all polygons
-  // are convex.
-  while (current_intersection < 2) {
-    if (LineIntersectPlane(points_[(current_vertex % points_size)],
-                           points_[(current_vertex + 1) % points_size],
-                           splitter.points_[0],
-                           splitter.normal_,
-                           &intersections[current_intersection],
-                           split_threshold)) {
-      vertex_before[current_intersection] = current_vertex % points_size;
-      current_intersection++;
-      // We found both intersection points so we're done already.
-      if (current_intersection == 2) {
-        break;
-      }
-    }
-    if (current_vertex++ > (points_size)) {
-      break;
+// Split |polygon| based upon |this|, leaving the results in |front| and |back|.
+// If |polygon| is not split by |this|, then move it to either |front| or |back|
+// depending on its orientation relative to |this|. Return true if |polygon| is
+// actually coplanar with |this| (in which case whether it is front facing or
+// back facing is determined by the dot products of normals, and document
+// order).
+bool DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon,
+                               std::unique_ptr<DrawPolygon>* front,
+                               std::unique_ptr<DrawPolygon>* back) {
+  DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f));
+
+  const size_t N_points = polygon->points_.size();

[enne (OOO), 2016/06/08 22:02:51]

N_points isn't valid chromium style.

I think you're looking for n_points or maybe num_points?

[Tobias Sargeant, 2016/06/09 16:48:44]

Done.

+  const auto next = [N_points](size_t i) {
+    return (i + 1) % N_points;
+  };
+  const auto prev = [N_points](size_t i) {
+    return (i + N_points - 1) % N_points;
+  };
+
+  std::vector<float> vertex_distance;
+  size_t pos_count = 0;
+  size_t neg_count = 0;
+
+  // Compute plane distances for each vertex of polygon.
+  vertex_distance.resize(N_points);
+  for (size_t i = 0; i < N_points; i++) {
+    vertex_distance[i] = SignedPointDistance(polygon->points_[i]);
+    if (vertex_distance[i] < -split_threshold) {
+      ++neg_count;
+    } else if (vertex_distance[i] > split_threshold) {
+      ++pos_count;
+    } else {
+      vertex_distance[i] = 0.0;
     }
   }
-  DCHECK_EQ(current_intersection, static_cast<size_t>(2));
-
-  // Since we found both the intersection points, we can begin building the
-  // vertex set for both our new polygons.
-  size_t start1 = (vertex_before[0] + 1) % points_size;
-  size_t start2 = (vertex_before[1] + 1) % points_size;
-  size_t points_remaining = points_size;
-
-  // First polygon.
-  out_points[0].push_back(intersections[0]);
-  DCHECK_GE(vertex_before[1], start1);
-  for (size_t i = start1; i <= vertex_before[1]; i++) {
-    out_points[0].push_back(points_[i]);
-    --points_remaining;
-  }
-  out_points[0].push_back(intersections[1]);
-
-  // Second polygon.
-  out_points[1].push_back(intersections[1]);
-  size_t index = start2;
-  for (size_t i = 0; i < points_remaining; i++) {
-    out_points[1].push_back(points_[index % points_size]);
-    ++index;
-  }
-  out_points[1].push_back(intersections[0]);
-
-  // Give both polygons the original splitting polygon's ID, so that they'll
-  // still be sorted properly in co-planar instances.
-  std::unique_ptr<DrawPolygon> poly1(
-      new DrawPolygon(original_ref_, out_points[0], normal_, order_index_));
-  std::unique_ptr<DrawPolygon> poly2(
-      new DrawPolygon(original_ref_, out_points[1], normal_, order_index_));
-
-  DCHECK_GE(poly1->points().size(), 3u);
-  DCHECK_GE(poly2->points().size(), 3u);
-
-  if (SideCompare(*poly1, splitter) == BSP_FRONT) {
-    *front = std::move(poly1);
-    *back = std::move(poly2);
-  } else {
-    *front = std::move(poly2);
-    *back = std::move(poly1);
+
+  // Handle non-splitting cases.
+  if (!pos_count && !neg_count) {
+    // |polygon| is coplanar with |this|.
+    double dot = gfx::DotProduct(normal_, polygon->normal_);
+    if ((dot >= 0.0f && polygon->order_index_ >= order_index_) ||
+        (dot <= 0.0f && polygon->order_index_ <= order_index_)) {
+      *back = std::move(polygon);
+    } else {
+      *front = std::move(polygon);
+    }
+    return true;
+  } else if (!neg_count) {
+    *front = std::move(polygon);
+    return false;
+  } else if (!pos_count) {
+    *back = std::move(polygon);
+    return false;
   }
-  return true;
+
+  // Handle splitting case.
+  size_t front_begin;
+  size_t back_begin;
+  size_t pre_front_begin;
+  size_t pre_back_begin;
+
+  // Find the first vertex that is part of the front split polygon.
+  front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
+                             [](float val) { return val > 0.0; }) -
+                vertex_distance.begin();
+  while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0)
+    front_begin = pre_front_begin;
+
+  // Find the first vertex that is part of the back split polygon.
+  back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
+                            [](float val) { return val < 0.0; }) -
+               vertex_distance.begin();
+  while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0)
+    back_begin = pre_back_begin;
+
+  DCHECK(vertex_distance[front_begin] > 0.0);
+  DCHECK(vertex_distance[pre_front_begin] <= 0.0);
+  DCHECK(vertex_distance[back_begin] < 0.0);
+  DCHECK(vertex_distance[pre_back_begin] >= 0.0);
+
+  gfx::Point3F pre_pos_intersection;
+  gfx::Point3F pre_neg_intersection;
+
+  // Compute the intersection points. N.B.: If the "pre" vertex is on
+  // the thick plane, then the intersection will be at the same point, because
+  // we set vertex_distance to 0 in this case.
+  PointInterpolate(
+      polygon->points_[pre_front_begin], polygon->points_[front_begin],
+      -vertex_distance[pre_front_begin] /
+          gfx::DotProduct(normal_, polygon->points_[front_begin] -
+                                       polygon->points_[pre_front_begin]),
+      &pre_pos_intersection);
+  PointInterpolate(
+      polygon->points_[pre_back_begin], polygon->points_[back_begin],
+      -vertex_distance[pre_back_begin] /
+          gfx::DotProduct(normal_, polygon->points_[back_begin] -
+                                       polygon->points_[pre_back_begin]),
+      &pre_neg_intersection);
+
+  // Build the front and back polygons.
+  std::vector<gfx::Point3F> out_points;
+
+  out_points.push_back(pre_pos_intersection);
+  do {
+    out_points.push_back(polygon->points_[front_begin]);
+    front_begin = next(front_begin);
+  } while (vertex_distance[front_begin] > 0.0);
+  out_points.push_back(pre_neg_intersection);
+  *front =
+      base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
+                                    polygon->normal_, polygon->order_index_);
+
+  out_points.clear();
+
+  out_points.push_back(pre_neg_intersection);
+  do {
+    out_points.push_back(polygon->points_[back_begin]);
+    back_begin = next(back_begin);
+  } while (vertex_distance[back_begin] < 0.0);
+  out_points.push_back(pre_pos_intersection);
+  *back =
+      base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
+                                    polygon->normal_, polygon->order_index_);
+
+  return false;

[enne (OOO), 2016/06/08 22:02:51]

Can you add some dchecks that out_points in both cases have at least three
points and that the sum total of points - 4 = original number of points?  This
is less clear than in the original version.

[enne (OOO), 2016/06/08 22:02:51]

Can you add some dchecks that out_points in both cases have at least three
points and that the sum total of points - 4 = original number of points?  This
is less clear than in the original version.

[Tobias Sargeant, 2016/06/09 16:48:44]

Yes, but that latter condition is actually wrong in the case where there are
some points that are on the thick plane. Looking at the code as it stood, I
think this wasn't handled correctly previously. e.g.

     |
    /|\
   / | \
  /  |  \
  \  |  /
   \ | /
    \|/
     |

Then splitting that quad should result in 2 triangles. Previously it looks like
this would result in 2 degenerate quads with two vertices at the same
coordinate.

I've DCHECKed that there are at most two vertices that lie on the thick plane,
which is equivalent to catching (some) non-convex cases, and also ensures that
the vertex loop is divisible into two halves such that no vertices are lost.

[enne (OOO), 2016/06/09 17:11:26]

Yeah, that was my concern--I didn't want to lose vertices.  Thanks for the
clarification about the total number of points in those cases.

+}
+
+// Convenience overload for testing purposes.
+bool DrawPolygon::SplitPolygon(const DrawPolygon& polygon,
+                               std::unique_ptr<DrawPolygon>* front,
+                               std::unique_ptr<DrawPolygon>* back) {
+  return SplitPolygon(
+      base::MakeUnique<DrawPolygon>(polygon.original_ref_, polygon.points_,
+                                    polygon.normal_, polygon.order_index_),
+      front, back);
 }
 
 // This algorithm takes the first vertex in the polygon and uses that as a