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..1c337bf39ea9df254c0763a347a2fb4a55efe910
--- /dev/null
+++ b/cc/quads/draw_polygon.cc
@@ -0,0 +1,331 @@
+// 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.
+static const float coplanar_dot_epsilon = 0.99f;
+// 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 = 1.0f;
+static const float split_threshold = 0.5f;
+}  // namespace
+
+namespace cc {
+
+DrawPolygon::DrawPolygon() {
+}
+
+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]);
+  }
+  normal_ = gfx::Vector3dF(0.0f, 0.0f, 1.0f);
+}
+
+DrawPolygon::~DrawPolygon() {
+}
+
+void DrawPolygon::SetNormal(const gfx::Vector3dF& normal) {
+  normal_ = normal;
+}
+
+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());
+  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_);

[Ian Vollick, 2014/07/25 15:52:13]

Do we need to ensure that apply normal has been called so that these normals are
valid? It occurs that we only need to transform the normal once for the original
quad and all the split polygons can refer to that normal. Maybe we should grab
the normal off the original polygon here?

[troyhildebrandt, 2014/07/25 20:37:47]

Applying the transformation to the normal happens right before going into the
BSP tree, and this is the only place the normal matters. When anything gets
split, the normal is simply copied to the two split pieces, so the normals
should always be valid in this case.

[Ian Vollick, 2014/07/26 01:24:37]

K. Thanks for the explanation.

+  float sign;
+  bool normal_match = false;
+  // This check assumes that the normals are normalized.
+  if (std::abs(dot) >= coplanar_dot_epsilon) {

[Ian Vollick, 2014/07/25 15:52:13]

It's a little odd to have epsilon be .99 rather than some number close to zero.
Can you make eps = 0.01f and then make your check here be against 1.0f - eps?

[troyhildebrandt, 2014/07/25 20:37:47]

Done.

+    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_);

[Ian Vollick, 2014/07/25 15:52:13]

What if a.points_[0] == b.points_[0] ?

[troyhildebrandt, 2014/07/25 20:37:47]

We end up with the dot product resulting in 0, which is totally okay with us.
This just means that the two surfaces are coplanar and they happen to share a
point which is totally acceptable. These cases are handled below.

[Ian Vollick, 2014/07/26 01:24:37]

I'm not convinced that this is always ok. Two polygons that are not coplanar can
share points, right? One example that comes to mind are two quads that share a
line segment, opening like a book.

[troyhildebrandt, 2014/07/28 17:39:37]

The std::abs(dot) >= coplanar_dot_epsilon dot product check above ensures that
the two surfaces have normals that are either pointing "exactly" the same or
opposite directions, so if it shares one point that just means that the rest of
the points on it are all in the same plane as well.

[Ian Vollick, 2014/07/28 19:39:51]

Oh right (facepalm). Thanks for catching me up :)

+    // 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)) {

[Ian Vollick, 2014/07/25 15:52:13]

Dumb question, if you know start and end distance, can't you lerp the endpoints
of the line segment?

[troyhildebrandt, 2014/07/25 20:37:47]

You're right, much simpler, done.

+    // 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;
+}
+
+// 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);
+  if (!inverted)
+    return;
+  inverse_transform.Transpose();
+
+  gfx::Point3F new_normal(normal_.x(), normal_.y(), normal_.z());
+  inverse_transform.TransformPoint(&new_normal);
+  // Make sure our normal is still normalized.
+  normal_ = gfx::Vector3dF(new_normal.x(), new_normal.y(), new_normal.z());
+  float normal_magnitude = normal_.Length();
+  if (normal_magnitude != 0 && normal_magnitude != 1) {
+    normal_.Scale(1.0f / normal_magnitude);
+  }
+}
+
+void DrawPolygon::ApplyTransform(const gfx::Transform& transform) {
+  for (unsigned int i = 0; i < points_.size(); i++) {
+    transform.TransformPoint(&points_[i]);
+  }
+}
+
+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) {

[Ian Vollick, 2014/07/25 15:52:13]

A comment explaining that we can only have 2 points of intersection b/c the poly
is convex would be helpful. Is the case where poly A slices through an edge and
a vertex of poly B handled by the thick plane stuff in LineIntersectPlane?

[troyhildebrandt, 2014/07/25 20:37:47]

If I'm envisioning the case correctly, then it should be handled just fine by
LineIntersectPlane. When figuring out the 2 intersection points, one of the
edges will have the intersected vertex as its start point, and since that is
within |distance_threshold|, then this point will be an intersection point.

[Ian Vollick, 2014/07/26 01:24:37]

kk.

+    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++) {

[Ian Vollick, 2014/07/25 15:52:12]

Confused about this. Isn't it possible that we'd have to wrap around to get back
to vertex_before[1]? Why don't we have to keep doing i = (i + 1) % size and stop
when i == vertex_before[1]?

[troyhildebrandt, 2014/07/25 20:37:47]

If we had to wrap around to reach vertex_before[1], we would have hit it on the
first run through, and it would instead be vertex_before[0], unless I'm
misunderstanding something? The worst case scenario is that the very last edge
we traverse (the one from vertex n-1 to vertex 0) is our second intersecting
edge, and so vertex_before[1] will be n-1.

It's possible I'm still missing something or misunderstanding you though.

+    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], order_index_));
+  scoped_ptr<DrawPolygon> poly2(
+      new DrawPolygon(original_ref_, out_points[1], order_index_));
+

[troyhildebrandt, 2014/07/25 20:37:47]

This is where the normals are set for the splits so we don't need to reapply the
transform, if this is what you were talking about above.

+  poly1->SetNormal(normal_);
+  poly2->SetNormal(normal_);
+
+  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 {

[Ian Vollick, 2014/07/25 15:52:13]

Does anyone use this?

[troyhildebrandt, 2014/07/25 20:37:47]

This is used when rendering, since we have to go back into layer space before
sending to OpenGL. 

[Ian Vollick, 2014/07/26 01:24:37]

Perhaps you could use it in ApplyTransformToNormal?

[troyhildebrandt, 2014/07/28 17:39:37]

I just removed it instead for now.

+  return original_ref_->quadTransform().GetInverse(transform);
+}
+
+}  // namespace cc