DrawPolygon class with Unit Tests

Review URL: https://codereview.chromium.org/411793002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@286316 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 609 insertions, 0 deletions

diff --git a/cc/cc.gyp b/cc/cc.gyp
index eeb4cb6..67a50326 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -244,6 +244,7 @@
         'layers/video_layer_impl.h',
         'output/begin_frame_args.cc',
         'output/begin_frame_args.h',
+        'output/bsp_compare_result.h',
         'output/compositor_frame.cc',
         'output/compositor_frame.h',
         'output/compositor_frame_ack.cc',
@@ -308,6 +309,8 @@
         'quads/content_draw_quad_base.h',
         'quads/debug_border_draw_quad.cc',
         'quads/debug_border_draw_quad.h',
+        'quads/draw_polygon.cc',
+        'quads/draw_polygon.h',
         'quads/draw_quad.cc',
         'quads/draw_quad.h',
         'quads/io_surface_draw_quad.cc',
diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 0d5cbd1..d29413d 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -67,6 +67,7 @@
       'output/renderer_unittest.cc',
       'output/shader_unittest.cc',
       'output/software_renderer_unittest.cc',
+      'quads/draw_polygon_unittest.cc',
       'quads/draw_quad_unittest.cc',
       'quads/render_pass_unittest.cc',
       'resources/layer_quad_unittest.cc',
diff --git a/cc/output/bsp_compare_result.h b/cc/output/bsp_compare_result.h
new file mode 100644
index 0000000..cdd251f
--- /dev/null
+++ b/cc/output/bsp_compare_result.h
@@ -0,0 +1,21 @@
+// 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.
+
+#ifndef CC_OUTPUT_BSP_COMPARE_RESULT_H_
+#define CC_OUTPUT_BSP_COMPARE_RESULT_H_
+
+namespace cc {
+
+enum BspCompareResult {
+  BSP_FRONT,
+  BSP_BACK,
+  BSP_SPLIT,
+  BSP_COPLANAR_FRONT,
+  BSP_COPLANAR_BACK,
+  BSP_COPLANAR,
+};
+
+}  // namespace cc
+
+#endif  // CC_OUTPUT_BSP_COMPARE_RESULT_H_
diff --git a/cc/quads/draw_polygon.cc b/cc/quads/draw_polygon.cc
new file mode 100644
index 0000000..db2249c
--- /dev/null
+++ b/cc/quads/draw_polygon.cc
@@ -0,0 +1,325 @@
+// 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.01f;
+// 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;
+// |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.
+static const float split_threshold = 0.5f;
+}  // namespace
+
+namespace cc {
+
+gfx::Vector3dF DrawPolygon::default_normal = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
+
+DrawPolygon::DrawPolygon() {
+}
+
+DrawPolygon::DrawPolygon(DrawQuad* original,
+                         const std::vector<gfx::Point3F>& in_points,
+                         const gfx::Vector3dF& normal,
+                         int draw_order_index)
+    : order_index_(draw_order_index), original_ref_(original) {
+  for (size_t i = 0; i < in_points.size(); i++) {
+    points_.push_back(in_points[i]);
+  }
+  normal_ = normal;
+}
+
+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());
+  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 = 0.0f;
+  bool normal_match = false;
+  // This check assumes that the normals are normalized.
+  if (std::abs(dot) >= 1.0f - 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;
+  }
+
+  int pos_count = 0;
+  int neg_count = 0;
+  for (size_t 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)) {
+    gfx::Vector3dF v = line_end - line_start;
+    float total_distance = std::abs(start_distance) + std::abs(end_distance);
+    float lerp_factor = std::abs(start_distance) / total_distance;
+
+    intersection->SetPoint(line_start.x() + (v.x() * lerp_factor),
+                           line_start.y() + (v.y() * lerp_factor),
+                           line_start.z() + (v.z() * lerp_factor));
+
+    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 (size_t i = 0; i < points_.size(); i++) {
+    transform.TransformPoint(&points_[i]);
+  }
+}
+
+// TransformToScreenSpace assumes we're moving a layer from its layer space
+// into 3D screen space, which for sorting purposes requires the normal to
+// be transformed along with the vertices.
+void DrawPolygon::TransformToScreenSpace(const gfx::Transform& transform) {
+  ApplyTransform(transform);
+  ApplyTransformToNormal(transform);
+}
+
+// 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,
+                        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].
+  size_t vertex_before[2];
+  size_t points_size = points_.size();
+  size_t current_intersection = 0;
+
+  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;
+    }
+  }
+  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;
+
+  // First polygon.
+  out_points[0].push_back(intersections[0]);
+  for (size_t 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]);
+  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]);
+
+  // Give both polygons the original splitting polygon's ID, so that they'll
+  // still be sorted properly in co-planar instances.
+  scoped_ptr<DrawPolygon> poly1(
+      new DrawPolygon(original_ref_, out_points[0], normal_, order_index_));
+  scoped_ptr<DrawPolygon> poly2(
+      new DrawPolygon(original_ref_, out_points[1], normal_, 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());
+  size_t offset = 1;
+  while (offset < points_.size() - 1) {
+    size_t op1 = offset + 1;
+    size_t 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;
+  }
+}
+
+}  // namespace cc
diff --git a/cc/quads/draw_polygon.h b/cc/quads/draw_polygon.h
new file mode 100644
index 0000000..c4dfa13
--- /dev/null
+++ b/cc/quads/draw_polygon.h
@@ -0,0 +1,77 @@
+// 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.
+
+#ifndef CC_QUADS_DRAW_POLYGON_H_
+#define CC_QUADS_DRAW_POLYGON_H_
+
+#include <vector>
+
+#include "cc/base/math_util.h"
+#include "cc/output/bsp_compare_result.h"
+#include "cc/quads/draw_quad.h"
+#include "ui/gfx/point3_f.h"
+#include "ui/gfx/quad_f.h"
+#include "ui/gfx/vector3d_f.h"
+
+namespace cc {
+
+class CC_EXPORT DrawPolygon {
+ public:
+  DrawPolygon();
+  ~DrawPolygon();
+
+  DrawPolygon(DrawQuad* original_ref,
+              const std::vector<gfx::Point3F>& in_points,
+              const gfx::Vector3dF& normal,
+              int draw_order_index = 0);
+
+  // Split takes this DrawPolygon and splits it into two pieces that are on
+  // either side of |splitter|. Any edges of this polygon that cross the plane
+  // of |splitter| will have an intersection point that is shared by both
+  // polygons on either side.
+  // Split will only return true if it determines that we got back 2
+  // intersection points. Only when it returns true will front and back both be
+  // valid new polygons that are on opposite sides of the splitting plane.
+  bool Split(const DrawPolygon& splitter,
+             scoped_ptr<DrawPolygon>* front,
+             scoped_ptr<DrawPolygon>* back);
+  float SignedPointDistance(const gfx::Point3F& point) const;
+  // Checks polygon a against polygon b and returns which side it lies on, or
+  // whether it crosses (necessitating a split in the BSP tree).
+  static BspCompareResult SideCompare(const DrawPolygon& a,
+                                      const DrawPolygon& b);
+  void ToQuads2D(std::vector<gfx::QuadF>* quads) const;
+  void TransformToScreenSpace(const gfx::Transform& transform);
+  void TransformToLayerSpace(const gfx::Transform& inverse_transform);
+
+  const std::vector<gfx::Point3F>& points() const { return points_; }
+  const gfx::Vector3dF& normal() const { return normal_; }
+  const DrawQuad* original_ref() const { return original_ref_; }
+  int order_index() const { return order_index_; }
+
+  scoped_ptr<DrawPolygon> CreateCopy();
+
+  static gfx::Vector3dF default_normal;
+
+ private:
+  void ApplyTransform(const gfx::Transform& transform);
+  void ApplyTransformToNormal(const gfx::Transform& transform);
+
+  std::vector<gfx::Point3F> points_;
+  // Normalized, necessitated by distance calculations and tests of coplanarity.
+  gfx::Vector3dF normal_;
+  // This is an index that can be used to test whether a quad comes before or
+  // after another in document order, useful for tie-breaking when it comes
+  // to coplanar surfaces.
+  int order_index_;
+  // The pointer to the original quad, which gives us all the drawing info
+  // we need.
+  // This DrawQuad is owned by the caller and its lifetime must be preserved
+  // as long as this DrawPolygon is alive.
+  DrawQuad* original_ref_;
+};
+
+}  // namespace cc
+
+#endif  // CC_QUADS_DRAW_POLYGON_H_
diff --git a/cc/quads/draw_polygon_unittest.cc b/cc/quads/draw_polygon_unittest.cc
new file mode 100644
index 0000000..3b8caf3
--- /dev/null
+++ b/cc/quads/draw_polygon_unittest.cc
@@ -0,0 +1,182 @@
+// 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 <vector>
+
+#include "cc/output/bsp_compare_result.h"
+#include "cc/quads/draw_polygon.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "ui/gfx/transform.h"
+
+namespace cc {
+namespace {
+
+#define CREATE_NEW_DRAW_POLYGON(name, points_vector, normal, polygon_id) \
+  DrawPolygon name(NULL, points_vector, normal, polygon_id)
+
+#define EXPECT_POINT_EQ(point_a, point_b)    \
+  EXPECT_FLOAT_EQ(point_a.x(), point_b.x()); \
+  EXPECT_FLOAT_EQ(point_a.y(), point_b.y()); \
+  EXPECT_FLOAT_EQ(point_a.z(), point_b.z());
+
+static void ValidatePoints(const DrawPolygon& polygon,
+                           const std::vector<gfx::Point3F>& points) {
+  EXPECT_EQ(polygon.points().size(), points.size());
+  for (size_t i = 0; i < points.size(); i++) {
+    EXPECT_POINT_EQ(polygon.points()[i], points[i]);
+  }
+}
+
+// Two quads are definitely not touching and so no split should occur.
+TEST(DrawPolygonSplitTest, NotTouchingNoSplit) {
+  std::vector<gfx::Point3F> vertices_a;
+  vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f));
+  std::vector<gfx::Point3F> vertices_b;
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, 5.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, 15.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, 15.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, 5.0f));
+
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_a, vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0);
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_b, vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1);
+
+  EXPECT_EQ(DrawPolygon::SideCompare(polygon_b, polygon_a), BSP_FRONT);
+}
+
+// One quad is resting against another, but doesn't cross its plane so no split
+// should occur.
+TEST(DrawPolygonSplitTest, BarelyTouchingNoSplit) {
+  std::vector<gfx::Point3F> vertices_a;
+  vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f));
+  std::vector<gfx::Point3F> vertices_b;
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, 0.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, -10.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, -10.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, 0.0f));
+
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_a, vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0);
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_b, vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1);
+
+  EXPECT_EQ(DrawPolygon::SideCompare(polygon_b, polygon_a), BSP_BACK);
+}
+
+// One quad intersects another and becomes two pieces.
+TEST(DrawPolygonSplitTest, BasicSplit) {
+  std::vector<gfx::Point3F> vertices_a;
+  vertices_a.push_back(gfx::Point3F(0.0f, 10.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 10.0f, 0.0f));
+  std::vector<gfx::Point3F> vertices_b;
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, -5.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, -5.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 0.0f, 5.0f));
+  vertices_b.push_back(gfx::Point3F(5.0f, 10.0f, 5.0f));
+
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_a, vertices_a, gfx::Vector3dF(0.0f, 0.0f, 1.0f), 0);
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_b, vertices_b, gfx::Vector3dF(-1.0f, 0.0f, 0.0f), 1);
+
+  EXPECT_EQ(DrawPolygon::SideCompare(polygon_b, polygon_a), BSP_SPLIT);
+
+  scoped_ptr<DrawPolygon> front_polygon;
+  scoped_ptr<DrawPolygon> back_polygon;
+  polygon_b.Split(polygon_a, &front_polygon, &back_polygon);
+  EXPECT_EQ(DrawPolygon::SideCompare(*front_polygon, polygon_a), BSP_FRONT);
+  EXPECT_EQ(DrawPolygon::SideCompare(*back_polygon, polygon_a), BSP_BACK);
+
+  std::vector<gfx::Point3F> test_points_a;
+  test_points_a.push_back(gfx::Point3F(5.0f, 0.0f, 0.0f));
+  test_points_a.push_back(gfx::Point3F(5.0f, 0.0f, 5.0f));
+  test_points_a.push_back(gfx::Point3F(5.0f, 10.0f, 5.0f));
+  test_points_a.push_back(gfx::Point3F(5.0f, 10.0f, 0.0f));
+  std::vector<gfx::Point3F> test_points_b;
+  test_points_b.push_back(gfx::Point3F(5.0f, 10.0f, 0.0f));
+  test_points_b.push_back(gfx::Point3F(5.0f, 10.0f, -5.0f));
+  test_points_b.push_back(gfx::Point3F(5.0f, 0.0f, -5.0f));
+  test_points_b.push_back(gfx::Point3F(5.0f, 0.0f, 0.0f));
+  ValidatePoints(*(front_polygon.get()), test_points_a);
+  ValidatePoints(*(back_polygon.get()), test_points_b);
+
+  EXPECT_EQ(front_polygon->points().size(), 4u);
+  EXPECT_EQ(back_polygon->points().size(), 4u);
+}
+
+// In this test we cut the corner of a quad so that it creates a triangle and
+// a pentagon as a result.
+TEST(DrawPolygonSplitTest, AngledSplit) {
+  std::vector<gfx::Point3F> vertices_a;
+  vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
+  vertices_a.push_back(gfx::Point3F(0.0f, 0.0f, 10.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 10.0f));
+  vertices_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
+  std::vector<gfx::Point3F> vertices_b;
+  vertices_b.push_back(gfx::Point3F(2.0f, 5.0f, 1.0f));
+  vertices_b.push_back(gfx::Point3F(2.0f, -5.0f, 1.0f));
+  vertices_b.push_back(gfx::Point3F(-1.0f, -5.0f, -2.0f));
+  vertices_b.push_back(gfx::Point3F(-1.0f, 5.0f, -2.0f));
+
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_a, vertices_a, gfx::Vector3dF(0.0f, 1.0f, 0.0f), 0);
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_b, vertices_b, gfx::Vector3dF(0.707107f, 0.0f, -0.707107f), 1);
+
+  EXPECT_EQ(DrawPolygon::SideCompare(polygon_a, polygon_b), BSP_SPLIT);
+
+  scoped_ptr<DrawPolygon> front_polygon;
+  scoped_ptr<DrawPolygon> back_polygon;
+  polygon_a.Split(polygon_b, &front_polygon, &back_polygon);
+  EXPECT_EQ(DrawPolygon::SideCompare(*front_polygon, polygon_b), BSP_FRONT);
+  EXPECT_EQ(DrawPolygon::SideCompare(*back_polygon, polygon_b), BSP_BACK);
+
+  EXPECT_EQ(front_polygon->points().size(), 3u);
+  EXPECT_EQ(back_polygon->points().size(), 5u);
+
+  std::vector<gfx::Point3F> test_points_a;
+  test_points_a.push_back(gfx::Point3F(10.0f, 0.0f, 9.0f));
+  test_points_a.push_back(gfx::Point3F(10.0f, 0.0f, 0.0f));
+  test_points_a.push_back(gfx::Point3F(1.0f, 0.0f, 0.0f));
+  std::vector<gfx::Point3F> test_points_b;
+  test_points_b.push_back(gfx::Point3F(1.0f, 0.0f, 0.0f));
+  test_points_b.push_back(gfx::Point3F(0.0f, 0.0f, 0.0f));
+  test_points_b.push_back(gfx::Point3F(0.0f, 0.0f, 10.0f));
+  test_points_b.push_back(gfx::Point3F(10.0f, 0.0f, 10.0f));
+  test_points_b.push_back(gfx::Point3F(10.0f, 0.0f, 9.0f));
+
+  ValidatePoints(*(front_polygon.get()), test_points_a);
+  ValidatePoints(*(back_polygon.get()), test_points_b);
+}
+
+TEST(DrawPolygonTransformTest, TransformNormal) {
+  // We give this polygon no actual vertices because we're not interested
+  // in actually transforming any points, just the normal.
+  std::vector<gfx::Point3F> vertices_a;
+  CREATE_NEW_DRAW_POLYGON(
+      polygon_a, vertices_a, gfx::Vector3dF(0.707107f, 0.0f, -0.707107f), 0);
+
+  gfx::Transform transform;
+  transform.RotateAboutYAxis(45.0);
+  // This would transform the vertices as well, but we are transforming a
+  // DrawPolygon with 0 vertices just to make sure our normal transformation
+  // using the inverse tranpose matrix gives us the right result.
+  polygon_a.TransformToScreenSpace(transform);
+
+  EXPECT_FLOAT_EQ(polygon_a.normal().x(), 0);
+  EXPECT_FLOAT_EQ(polygon_a.normal().y(), 0);
+  EXPECT_FLOAT_EQ(polygon_a.normal().z(), -1);
+}
+
+}  // namespace
+}  // namespace cc