DrawPolygon class with Unit Tests

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

[enne (OOO), 2014/07/23 00:22:42]

Thinking about simplifying things or removing complexity, you're only using area
to do the original sort, right?  If so, why not just look at the original draw
quad and multiply width by height and then be done.  Area can just be
"OriginalArea".

[troyhildebrandt, 2014/07/23 19:47:56]

The area gets recalculated when things are split. In the case that it is the
original quad though, we can definitely speed up the calculation by just doing
that. We can also avoid the area calculation on the second piece of a split.

[enne (OOO), 2014/07/23 20:07:17]

Could you test areas of non-quads, then?

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

[enne (OOO), 2014/07/23 00:22:42]

Will this clobber |clipped| every time it is called?

Do you even use this return value?

[troyhildebrandt, 2014/07/23 19:47:56]

It definitely clobbers clipped every single time, but MapPoint requires us to
feed it that boolean so no real choice there. The return value isn't used
anywhere though, and would be useless in this case, so that's been changed to
void.

+  }
+  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_vertex++ > points_size) {
+      break;
+    }
+    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;
+      }
+    }
+  }
+  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