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.
+// <= |split_threshold|, then it is considered on the plane for the purpose of
+// polygon splitting.
 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 83 matching lines @@
 //
 void DrawPolygon::RecomputeNormalForTesting() {
   ConstructNormal();
 }
 #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,
-                                          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]);
-
-    if (sign < -compare_threshold) {
-      ++neg_count;
-    } else if (sign > compare_threshold) {
-      ++pos_count;
-    }
-
-    if (pos_count && neg_count) {
-      return BSP_SPLIT;
-    }
-  }
-
-  if (pos_count) {
-    return BSP_FRONT;
-  }
-  if (neg_count) {
-    return BSP_BACK;
-  }
-
-  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 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|. Sets |is_coplanar| to 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).
+void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon,
+                               std::unique_ptr<DrawPolygon>* front,
+                               std::unique_ptr<DrawPolygon>* back,
+                               bool* is_coplanar) const {
+  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 num_points = polygon->points_.size();
+  const auto next = [num_points](size_t i) { return (i + 1) % num_points; };
+  const auto prev = [num_points](size_t i) {
+    return (i + num_points - 1) % num_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(num_points);
+  for (size_t i = 0; i < num_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) {
+    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);
+    }
+    *is_coplanar = true;
+    return;
+  }
 
-  // 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;
+  *is_coplanar = false;
+  if (!neg_count) {
+    *front = std::move(polygon);
+    return;
+  } else if (!pos_count) {
+    *back = std::move(polygon);
+    return;
   }
-  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]);
+  // There should be at most two points that are considered to be on the thick
+  // plane. If this is not the case, then the polygon is not convex.
+  DCHECK_LE(num_points - pos_count - neg_count, 2u);
 
-  // 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_));
+  // Handle splitting case.
+  size_t front_begin;
+  size_t back_begin;
+  size_t pre_front_begin;
+  size_t pre_back_begin;
 
-  DCHECK_GE(poly1->points().size(), 3u);
-  DCHECK_GE(poly2->points().size(), 3u);
+  // 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;
 
-  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;
+  // 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_);
+
+  DCHECK_GE((*front)->points().size(), 3u);
+  DCHECK_GE((*back)->points().size(), 3u);
 }
 
 // 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