DrawPolygon class with Unit Tests

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..79ec6cb566a7f15ca5b80cc2395b54ba01b0ab2e
--- /dev/null
+++ b/cc/quads/draw_polygon.cc
@@ -0,0 +1,320 @@
+// 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 <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 {
+
+float DrawPolygon::compare_threshold = 1.0f;
+float DrawPolygon::split_threshold = 0.5f;
+
+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;

[Ian Vollick, 2014/07/24 18:11:27]

How does this do with large quads? Seems like there's risk of overflow? I think
that cases like star shaped polygons with the inner points very close to one
another or triangles with zero height will give catastrophic cancellation here?
Can you please test cases like this and show that the function does something
reasonable? It would put my mind at ease :)

[troyhildebrandt, 2014/07/24 21:05:06]

All of this removed.

+  }
+  return 0.5f * std::abs(gfx::DotProduct(total, polygon.normal));
+}
+
+float Area(const DrawPolygon& polygon) {
+  return std::abs(SignedArea(polygon));
+}
+
+DrawPolygon::DrawPolygon(DrawQuad* original,
+                         const std::vector<gfx::Point3F>& in_points,
+                         int draw_order_index)
+    : order_index(draw_order_index), original_ref(original) {
+  for (unsigned int i = 0; i < in_points.size(); i++) {
+    points.push_back(in_points[i]);
+  }
+
+  if (points.size() > 2) {
+    gfx::Vector3dF c12 = in_points[1] - in_points[0];
+    gfx::Vector3dF c13 = in_points[2] - in_points[0];

[Ian Vollick, 2014/07/24 18:11:27]

Couldn't these two vectors be collinear? I think they could also be the zero
vector if we have a doubled point.

I don't think we need to resort to PCA/eigenvectors for this, but I think we
could do something a bit more clever. Perhaps we could walk around the perimeter
of the polygon keeping a running sum of the cross product of adjacent edge
vectors? They should all be pointing in the same direction, so summing them
shouldn't hurt. I think we're always convex, too, so we shouldn't need to worry
about cancellation. We could also abort the walk if the length of the summed
normal exceeds some threshold. dneto pointed out that this scheme is worst if
we've got a zillion points in a circle and every cross product is tiny. Perhaps
we could traverse the points in a pseudo random order? wdyt?

This can still fall apart when the points are all collinear or coincident. We
should have code for dealing with this and tests that stress this case.

+    normal = gfx::CrossProduct(c12, c13);
+    normal.Scale(1.0f / normal.Length());

[Ian Vollick, 2014/07/24 18:11:28]

Please check for div-by-zero. If |in_points| is filled with coincident points,
this'll def be zero. Should have a test for this.

+  }
+  area = Area(*this);
+}
+
+DrawPolygon::~DrawPolygon() {
+}
+
+scoped_ptr<DrawPolygon> DrawPolygon::CreateCopy() {
+  DrawPolygon* new_polygon = new DrawPolygon();
+  new_polygon->order_index = order_index;
+  new_polygon->original_ref = original_ref;
+  new_polygon->points.reserve(points.size());
+  new_polygon->points = points;
+  new_polygon->normal.set_x(normal.x());
+  new_polygon->normal.set_y(normal.y());
+  new_polygon->normal.set_z(normal.z());
+  new_polygon->area = area;
+  return scoped_ptr<DrawPolygon>(new_polygon);
+}
+
+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) {
+  // 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 < -compare_threshold) {
+      return BSP_BACK;
+    }
+
+    if (sign > compare_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 < -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;
+  }
+  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 start_to_origin_vector = plane_origin - line_start;
+  gfx::Vector3dF end_to_origin_vector = plane_origin - line_end;
+
+  double start_distance = gfx::DotProduct(start_to_origin_vector, plane_normal);
+  double end_distance = gfx::DotProduct(end_to_origin_vector, 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)) {
+    // By getting the dot product of the line segment normalized vs. the plane's
+    // normal, we get a value that approaches zero as the angle of the
+    // intersecting line becomes parallel with the plane.
+    // When the line segment vector is equal to the plane's normal, we have the
+    // most direct path to the plane, and the dot product is 1. In this case,
+    // the calculation below is just |start_distance| / 1, which is the trivial
+    // case because the line takes the most direct path to intersect with the
+    // plane. |start_distance| is already the shortest straight line path
+    // distance to the plane.
+    // However, as the vector that represents the direction of the line segment
+    // indicates that it is becoming more parallel with the surface of the plane
+    // and the dot product approaches 0, the path to intersection becomes much
+    // longer, and the division of |start_distance| by < 1 gives us the true
+    // distance of the start point to the plane following the vector of the line
+    // segment.
+    gfx::Vector3dF v = line_end - line_start;
+    v.Scale(1.f / v.Length());
+    double projected_length = gfx::DotProduct(v, plane_normal);
+
+    // The only way this will ever be true is the case where the line runs
+    // parallel to the surface of the plane and would never contact it, and
+    // this would result in a divide by zero below.
+    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::Split(const DrawPolygon& splitter,
+                        scoped_ptr<DrawPolygon>* front,
+                        scoped_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].
+  unsigned int vertex_before[2];
+  unsigned int points_size = points.size();
+  unsigned int current_intersection = 0;
+
+  unsigned int current_vertex = 0;
+  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;
+    }
+  }
+  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.
+  unsigned int start1 = (vertex_before[0] + 1) % points_size;
+  unsigned int start2 = (vertex_before[1] + 1) % points_size;
+  unsigned int points_remaining = points_size;
+
+  // First polygon.
+  out_points[0].push_back(intersections[0]);
+  for (unsigned 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]);
+  unsigned int index = start2;
+  for (unsigned 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], this->order_index));
+  scoped_ptr<DrawPolygon> poly2(
+      new DrawPolygon(original_ref, out_points[1], this->order_index));
+
+  if (SideCompare(*poly1, splitter) == BSP_FRONT) {
+    *front = poly1.Pass();
+    *back = poly2.Pass();
+  } else {
+    *front = poly2.Pass();
+    *back = poly1.Pass();
+  }
+  return true;
+}
+
+// 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.
+// The special case here is where there are only 3 points remaining, in which
+// case we use the same values for vertex 3 and 4 to make a degenerate quad
+// that represents a triangle.
+void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const {
+  if (points.size() <= 2)
+    return;
+
+  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