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

cc/quads/draw_polygon.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/quads/draw_polygon.h"
 
 #include <stddef.h>
 
 #include <vector>
 
+#include "base/memory/ptr_util.h"
 #include "cc/output/bsp_compare_result.h"
 #include "cc/quads/draw_quad.h"
 
 namespace {
 // This threshold controls how "thick" a plane is. If a point's distance is
 // <= |compare_threshold|, then it is considered on the plane. Only when this
 // boundary is crossed do we consider doing splitting.
 static const float compare_threshold = 0.1f;
 // |split_threshold| is lower in this case because we want the points created
 // during splitting to be well within the range of |compare_threshold| for
 // comparison purposes. The splitting operation will produce intersection points
 // that fit within a tighter distance to the splitting plane as a result of this
 // value. By using a value >= |compare_threshold| we run the risk of creating
 // points that SHOULD be intersecting the "thick plane", but actually fail to
 // test positively for it because |split_threshold| allowed them to be outside
 // this range.
 // This is really supposd to be compare_threshold / 2.0f, but that would
 // create another static initializer.
 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 {
 
 DrawPolygon::DrawPolygon() {
 }
 
 DrawPolygon::DrawPolygon(const DrawQuad* original,
                          const std::vector<gfx::Point3F>& in_points,
                          const gfx::Vector3dF& normal,
@@ skipping 87 matching lines @@
 #endif
 
 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const {
   return gfx::DotProduct(point - points_[0], normal_);
 }
 
 // Checks whether or not shape a lies on the front or back side of b, or
 // whether they should be considered coplanar. If on the back side, we
 // say A_BEFORE_B because it should be drawn in that order.
 // Assumes that layers are split and there are no intersecting planes.
 BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a,

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

Is this function used anymore?

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

Only in tests.

                                           const DrawPolygon& b) {
   // Let's make sure that this is normalized.  Without this SignedPointDistance
   // will not be right, but putting the check in there will validate it
   // redundantly for each point.
   DCHECK_GE(normalized_threshold, std::abs(b.normal_.LengthSquared() - 1.0f));
 
   int pos_count = 0;
   int neg_count = 0;
   for (size_t i = 0; i < a.points_.size(); i++) {
     float sign = b.SignedPointDistance(a.points_[i]);
@@ skipping 20 matching lines @@
   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 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
 // space before sending them to OpenGL, which requires using ApplyTransform,
 // but normal information is no longer needed after sorting.
 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) {
   // Now we use the inverse transpose of |transform| to transform the normal.
   gfx::Transform inverse_transform;
   bool inverted = transform.GetInverse(&inverse_transform);
   DCHECK(inverted);
@@ skipping 29 matching lines @@
 // In the case of TransformToLayerSpace, we assume that we are giving the
 // inverse transformation back to the polygon to move it back into layer space
 // but we can ignore the costly process of applying the inverse to the normal
 // since we know the normal will just reset to its original state.
 void DrawPolygon::TransformToLayerSpace(
     const gfx::Transform& inverse_transform) {
   ApplyTransform(inverse_transform);
   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;
+// 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));
 
-  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;
+  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;
+  // 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;
+  }
 
-  // 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]);
+  // Handle splitting case.
+  size_t front_begin;
+  size_t back_begin;
+  size_t pre_front_begin;
+  size_t pre_back_begin;
 
-  // 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]);
+  // 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;
 
-  // 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_));
+  // 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_GE(poly1->points().size(), 3u);
-  DCHECK_GE(poly2->points().size(), 3u);
+  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);
 
-  if (SideCompare(*poly1, splitter) == BSP_FRONT) {
-    *front = std::move(poly1);
-    *back = std::move(poly2);
-  } else {
-    *front = std::move(poly2);
-    *back = std::move(poly1);
-  }
-  return true;
+  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
 // pivot point to fan out and create quads from the rest of the vertices.
 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate
 // offset+1 and offset+2 respectively.
 // After the first quad is created, the first vertex in the next quad is the
 // same as all the rest, the pivot point. The second vertex in the next quad is
 // the old |op2|, the last vertex added to the previous quad. This continues
 // until all points are exhausted.
@@ skipping 16 matching lines @@
     quads->push_back(
         gfx::QuadF(first,
                    gfx::PointF(points_[offset].x(), points_[offset].y()),
                    gfx::PointF(points_[op1].x(), points_[op1].y()),
                    gfx::PointF(points_[op2].x(), points_[op2].y())));
     offset = op2;
   }
 }
 
 }  // namespace cc