WIP BSP Tree for 3D Layer Sorting

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
new file mode 100644
index 0000000000000000000000000000000000000000..c5f60f522e22ded5e9846b2b521f616b0d131bba
--- /dev/null
+++ b/cc/quads/draw_polygon.cc
@@ -0,0 +1,313 @@
+// Copyright 2013 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 <vector>
+
+#include "cc/output/bsp_compare_result.h"
+
+namespace {
+// This allows for some imperfection in the normal comparison when checking if
+// two pieces of geometry are coplanar.
+const float coplanar_dot_epsilon = 0.99f;
+}  // namespace
+
+namespace cc {
+
+DrawPolygon::DrawPolygon() {
+}
+
+static float SignedArea(const DrawPolygon& polygon) {
+  gfx::Vector3dF total;
+  for (unsigned int i = 0; i < polygon.points.size(); i++) {
+    unsigned int j = (i + 1) % polygon.points.size();
+    gfx::Vector3dF cross_prod =
+        gfx::CrossProduct(gfx::Vector3dF(polygon.points[i].x(),
+                                         polygon.points[i].y(),
+                                         polygon.points[i].z()),
+                          gfx::Vector3dF(polygon.points[j].x(),
+                                         polygon.points[j].y(),
+                                         polygon.points[j].z()));
+    total = total + cross_prod;
+  }
+  return 0.5f * std::abs(gfx::DotProduct(total, polygon.normal));

[Ian Vollick, 2014/07/22 16:12:15]

The fns in DrawPolygon are probably the most involved, mathmatically and
numerically. These really should have unit tests. It would be great to show that
these functions are well-conditioned when tough problems are thrown at them.

[troyhildebrandt, 2014/07/23 21:43:56]

Changed and all part of the DrawPolygon patch separately now.

+}
+
+float Area(const DrawPolygon& polygon) {
+  return std::abs(SignedArea(polygon));
+}
+
+DrawPolygon::DrawPolygon(DrawQuad* original,
+                         gfx::Point3F* in_points,
+                         int num_vertices_in_polygon,
+                         int draw_order_index)
+    : order_index(draw_order_index), original_ref(original) {
+  for (int i = 0; i < num_vertices_in_polygon; i++) {
+    points.push_back(in_points[i]);
+  }
+
+  if (num_vertices_in_polygon > 2) {
+    gfx::Vector3dF c12 = in_points[1] - in_points[0];
+    gfx::Vector3dF c13 = in_points[2] - in_points[0];
+    normal = gfx::CrossProduct(c12, c13);
+    normal.Scale(1.0f / normal.Length());
+  }
+  area = Area(*this);
+}
+
+DrawPolygon::DrawPolygon(const DrawPolygon& other) {
+  CopyFrom(other);
+}
+
+DrawPolygon::~DrawPolygon() {
+}
+
+DrawPolygon& DrawPolygon::operator=(const DrawPolygon& rhs) {
+  CopyFrom(rhs);
+  return *this;
+}
+
+void DrawPolygon::CopyFrom(const DrawPolygon& other) {
+  order_index = other.order_index;
+  original_ref = other.original_ref;
+  points.reserve(other.points.size());
+  points = other.points;
+  normal.set_x(other.normal.x());
+  normal.set_y(other.normal.y());
+  normal.set_z(other.normal.z());
+  area = other.area;
+}
+
+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 ABeforeB 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,
+                                          float z_threshold) {
+  // Right away let's check if they're coplanar
+  double dot = gfx::DotProduct(a.normal, b.normal);
+  float sign;
+  bool normal_match = false;
+  // This check assumes that the normals are normalized.
+  if (std::abs(dot) >= coplanar_dot_epsilon) {
+    normal_match = true;
+    // The normals are matching enough that we only have to test one point.
+    sign = gfx::DotProduct(a.points[0] - b.points[0], b.normal);
+    // Is it on either side of the splitter?
+    if (sign < -z_threshold) {
+      return BSP_BACK;
+    }
+
+    if (sign > z_threshold) {
+      return BSP_FRONT;
+    }
+
+    // No it wasn't, so the sign of the dot product of the normals
+    // along with document order determines which side it goes on.
+    if (dot >= 0.0f) {
+      if (a.order_index < b.order_index) {
+        return BSP_COPLANAR_FRONT;
+      }
+      return BSP_COPLANAR_BACK;
+    }
+
+    if (a.order_index < b.order_index) {
+      return BSP_COPLANAR_BACK;
+    }
+    return BSP_COPLANAR_FRONT;
+  }
+
+  unsigned int pos_count = 0;
+  unsigned int neg_count = 0;
+  for (unsigned int i = 0; i < a.points.size(); i++) {
+    if (!normal_match || (normal_match && i > 0)) {
+      sign = gfx::DotProduct(a.points[i] - b.points[0], b.normal);
+    }
+
+    if (sign < -z_threshold) {
+      ++neg_count;
+    } else if (sign > z_threshold) {
+      ++pos_count;
+    }
+
+    if (pos_count && neg_count) {
+      return BSP_SPLIT;
+    }
+  }
+
+  if (pos_count) {
+    return BSP_FRONT;
+  }
+  return BSP_BACK;
+}
+
+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) {
+  gfx::Vector3dF vec1 = plane_origin - line_start;
+  gfx::Vector3dF vec2 = plane_origin - line_end;
+
+  double start_distance = gfx::DotProduct(vec1, plane_normal);
+  double end_distance = gfx::DotProduct(vec2, plane_normal);
+
+  // The case where one vertex lies on the thick-plane and the other
+  // is outside of it.
+  if (std::abs(start_distance) < distance_threshold &&
+      std::abs(end_distance) > distance_threshold) {
+    intersection->SetPoint(line_start.x(), line_start.y(), line_start.z());
+    return true;
+  }
+
+  // This is the case where we clearly cross the thick-plane.
+  if ((start_distance > distance_threshold &&
+       end_distance < -distance_threshold) ||
+      (start_distance < -distance_threshold &&
+       end_distance > distance_threshold)) {
+    gfx::Vector3dF v = line_end - line_start;
+
+    v.Scale(1.f / v.Length());
+    double projected_length = gfx::DotProduct(v, plane_normal);
+    if (!projected_length)
+      return false;
+
+    double scale = start_distance / projected_length;
+    intersection->SetPoint(line_start.x() + (v.x() * scale),
+                           line_start.y() + (v.y() * scale),
+                           line_start.z() + (v.z() * scale));
+
+    return true;
+  }
+  return false;
+}
+
+bool DrawPolygon::ApplyTransform(const gfx::Transform& transform) {
+  bool clipped = false;
+  for (unsigned int i = 0; i < points.size(); i++) {
+    points[i] = MathUtil::MapPoint(transform, points[i], &clipped);
+  }
+  return !clipped;
+}
+
+bool DrawPolygon::Split(const DrawPolygon& splitter,
+                        double plane_threshold,
+                        scoped_ptr<DrawPolygon>* front,
+                        scoped_ptr<DrawPolygon>* back) {
+  gfx::Point3F intersections[2];
+  std::vector<gfx::Point3F> out_points[2];
+  int vertex_before[2];
+  int points_size = points.size();
+  int current_intersection = 0;
+
+  int current_vertex = 0;
+  while (current_intersection < 2) {
+    if (current_intersection > 0 &&
+        vertex_before[0] == (current_vertex % points_size)) {
+      continue;
+    }
+
+    if (LineIntersectPlane(points[(current_vertex % points_size)],
+                           points[(current_vertex + 1) % points_size],
+                           splitter.points[0],
+                           splitter.normal,
+                           &intersections[current_intersection],
+                           plane_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;
+      }
+    }
+    ++current_vertex;
+    // We've gone around one whole time, leave early.
+    if (current_vertex > points_size) {
+      break;
+    }
+  }
+  if (current_intersection < 2) {
+    return false;
+  }
+
+  // Since we found both the intersection points, we can begin building the
+  // vertex set for both our new polygons.
+  int start1 = (vertex_before[0] + 1) % points_size;
+  int start2 = (vertex_before[1] + 1) % points_size;
+  int points_remaining = points_size;
+
+  // First polygon.
+  out_points[0].push_back(intersections[0]);
+  for (int 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]);
+  int index = start2;
+  for (int 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.
+  // Send false as last parameter for is_original because they're split.
+  scoped_ptr<DrawPolygon> poly1(new DrawPolygon(original_ref,
+                                                &(out_points[0][0]),
+                                                out_points[0].size(),
+                                                this->order_index));
+  scoped_ptr<DrawPolygon> poly2(new DrawPolygon(original_ref,
+                                                &(out_points[1][0]),
+                                                out_points[1].size(),
+                                                this->order_index));
+
+  if (SideCompare(*poly1, splitter, plane_threshold) == BSP_FRONT) {
+    *front = poly1.Pass();
+    *back = poly2.Pass();
+  } else {
+    *front = poly2.Pass();
+    *back = poly1.Pass();
+  }
+  return true;
+}
+
+void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const {
+  if (points.size() == 0)
+    return;
+
+  // op1 = offset plus 1, op2 = offset plus 2.
+  gfx::PointF first(points[0].x(), points[0].y());
+  unsigned int offset = 1;
+  while (offset < points.size() - 1) {
+    unsigned int op1 = offset + 1;
+    unsigned int op2 = offset + 2;
+    if (op2 >= points.size()) {
+      // It's going to be a degenerate triangle.
+      op2 = op1;
+    }
+    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;
+  }
+}
+
+bool DrawPolygon::GetInverseTransform(gfx::Transform* transform) const {
+  return original_ref->quadTransform().GetInverse(transform);
+}
+
+}  // namespace cc