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 <stddef.h>

#include <vector>

#include "base/memory/ptr_util.h"
#include "cc/output/bsp_compare_result.h"
#include "cc/quads/draw_quad.h"

namespace {
// This threshold controls how "thick" a plane is. If a point's distance is
// <= |split_threshold|, then it is considered on the plane for the purpose of
// polygon splitting.
static const float split_threshold = 0.05f;

static const float normalized_threshold = 0.001f;

void PointInterpolate(const gfx::Point3F& from,
                      const gfx::Point3F& to,
                      double delta,
                      gfx::Point3F* out) {
  out->SetPoint(from.x() + (to.x() - from.x()) * delta,
                from.y() + (to.y() - from.y()) * delta,
                from.z() + (to.z() - from.z()) * delta);
}
}  // namespace

namespace cc {

DrawPolygon::DrawPolygon() {
}

DrawPolygon::DrawPolygon(const 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), is_split_(true) {
  for (size_t i = 0; i < in_points.size(); i++) {
    points_.push_back(in_points[i]);
  }
  normal_ = normal;
  DCHECK_LE((ConstructNormal(), (normal_ - normal).Length()),
            normalized_threshold);
}

// This takes the original DrawQuad that this polygon should be based on,
// a visible content rect to make the 4 corner points from, and a transformation
// to move it and its normal into screen space.
DrawPolygon::DrawPolygon(const DrawQuad* original_ref,
                         const gfx::RectF& visible_layer_rect,
                         const gfx::Transform& transform,
                         int draw_order_index)
    : normal_(0.0f, 0.0f, 1.0f),
      order_index_(draw_order_index),
      original_ref_(original_ref),
      is_split_(false) {
  gfx::Point3F points[8];
  int num_vertices_in_clipped_quad;
  gfx::QuadF send_quad(visible_layer_rect);

  // Doing this mapping here is very important, since we can't just transform
  // the points without clipping and not run into strange geometry issues when
  // crossing w = 0. At this point, in the constructor, we know that we're
  // working with a quad, so we can reuse the MathUtil::MapClippedQuad3d
  // function instead of writing a generic polygon version of it.
  MathUtil::MapClippedQuad3d(
      transform, send_quad, points, &num_vertices_in_clipped_quad);
  for (int i = 0; i < num_vertices_in_clipped_quad; i++) {
    points_.push_back(points[i]);
  }
  transform.TransformVector(&normal_);
  ConstructNormal();
}

DrawPolygon::~DrawPolygon() {
}

std::unique_ptr<DrawPolygon> DrawPolygon::CreateCopy() {
  std::unique_ptr<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 new_polygon;
}

//
// If this were to be more generally used and expected to be applicable
// replacing this with Newell's algorithm (or an improvement thereof)
// would be preferable, but usually this is coming in from a rectangle
// that has been transformed to screen space and clipped.
// Averaging a few near diagonal cross products is pretty good in that case.
//
void DrawPolygon::ConstructNormal() {
  gfx::Vector3dF new_normal(0.0f, 0.0f, 0.0f);
  int delta = points_.size() / 2;
  for (size_t i = 1; i + delta < points_.size(); i++) {
    new_normal +=
        CrossProduct(points_[i] - points_[0], points_[i + delta] - points_[0]);
  }
  float normal_magnitude = new_normal.Length();
  // Here we constrain the new normal to point in the same sense as the old one.
  // This allows us to handle winding-reversing transforms better.
  if (gfx::DotProduct(normal_, new_normal) < 0.0) {
    normal_magnitude *= -1.0;
  }
  if (normal_magnitude != 0 && normal_magnitude != 1) {
    new_normal.Scale(1.0f / normal_magnitude);
  }
  normal_ = new_normal;
}

#if defined(OS_WIN)
//
// Allows the unittest to invoke this for the more general constructor.
//
void DrawPolygon::RecomputeNormalForTesting() {
  ConstructNormal();
}
#endif

float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const {
  return gfx::DotProduct(point - points_[0], normal_);
}

// 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);
  transform.TransformVector(&normal_);
  ConstructNormal();
}

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

// Split |polygon| based upon |this|, leaving the results in |front| and |back|.
// If |polygon| is not split by |this|, then move it to either |front| or |back|
// depending on its orientation relative to |this|. Sets |is_coplanar| to true
// if |polygon| is actually coplanar with |this| (in which case whether it is
// front facing or back facing is determined by the dot products of normals, and
// document order).
void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon,
                               std::unique_ptr<DrawPolygon>* front,
                               std::unique_ptr<DrawPolygon>* back,
                               bool* is_coplanar) const {
  DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f));

  const size_t num_points = polygon->points_.size();
  const auto next = [num_points](size_t i) { return (i + 1) % num_points; };
  const auto prev = [num_points](size_t i) {
    return (i + num_points - 1) % num_points;
  };

  std::vector<float> vertex_distance;
  size_t pos_count = 0;
  size_t neg_count = 0;

  // Compute plane distances for each vertex of polygon.
  vertex_distance.resize(num_points);
  for (size_t i = 0; i < num_points; i++) {
    vertex_distance[i] = SignedPointDistance(polygon->points_[i]);
    if (vertex_distance[i] < -split_threshold) {
      ++neg_count;
    } else if (vertex_distance[i] > split_threshold) {
      ++pos_count;
    } else {
      vertex_distance[i] = 0.0;
    }
  }

  // Handle non-splitting cases.
  if (!pos_count && !neg_count) {
    double dot = gfx::DotProduct(normal_, polygon->normal_);
    if ((dot >= 0.0f && polygon->order_index_ >= order_index_) ||
        (dot <= 0.0f && polygon->order_index_ <= order_index_)) {
      *back = std::move(polygon);
    } else {
      *front = std::move(polygon);
    }
    *is_coplanar = true;
    return;
  }

  *is_coplanar = false;
  if (!neg_count) {
    *front = std::move(polygon);
    return;
  } else if (!pos_count) {
    *back = std::move(polygon);
    return;
  }

  // There should be at most two points that are considered to be on the thick
  // plane. If this is not the case, then the polygon is not convex.
  DCHECK_LE(num_points - pos_count - neg_count, 2u);

  // Handle splitting case.
  size_t front_begin;
  size_t back_begin;
  size_t pre_front_begin;
  size_t pre_back_begin;

  // Find the first vertex that is part of the front split polygon.
  front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
                             [](float val) { return val > 0.0; }) -
                vertex_distance.begin();
  while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0)
    front_begin = pre_front_begin;

  // Find the first vertex that is part of the back split polygon.
  back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
                            [](float val) { return val < 0.0; }) -
               vertex_distance.begin();
  while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0)
    back_begin = pre_back_begin;

  DCHECK(vertex_distance[front_begin] > 0.0);
  DCHECK(vertex_distance[pre_front_begin] <= 0.0);
  DCHECK(vertex_distance[back_begin] < 0.0);
  DCHECK(vertex_distance[pre_back_begin] >= 0.0);

  gfx::Point3F pre_pos_intersection;
  gfx::Point3F pre_neg_intersection;

  // Compute the intersection points. N.B.: If the "pre" vertex is on
  // the thick plane, then the intersection will be at the same point, because
  // we set vertex_distance to 0 in this case.
  PointInterpolate(
      polygon->points_[pre_front_begin], polygon->points_[front_begin],
      -vertex_distance[pre_front_begin] /
          gfx::DotProduct(normal_, polygon->points_[front_begin] -
                                       polygon->points_[pre_front_begin]),
      &pre_pos_intersection);
  PointInterpolate(
      polygon->points_[pre_back_begin], polygon->points_[back_begin],
      -vertex_distance[pre_back_begin] /
          gfx::DotProduct(normal_, polygon->points_[back_begin] -
                                       polygon->points_[pre_back_begin]),
      &pre_neg_intersection);

  // Build the front and back polygons.
  std::vector<gfx::Point3F> out_points;

  out_points.push_back(pre_pos_intersection);
  do {
    out_points.push_back(polygon->points_[front_begin]);
    front_begin = next(front_begin);
  } while (vertex_distance[front_begin] > 0.0);
  out_points.push_back(pre_neg_intersection);
  *front =
      base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
                                    polygon->normal_, polygon->order_index_);

  out_points.clear();

  out_points.push_back(pre_neg_intersection);
  do {
    out_points.push_back(polygon->points_[back_begin]);
    back_begin = next(back_begin);
  } while (vertex_distance[back_begin] < 0.0);
  out_points.push_back(pre_pos_intersection);
  *back =
      base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points,
                                    polygon->normal_, polygon->order_index_);

  DCHECK_GE((*front)->points().size(), 3u);
  DCHECK_GE((*back)->points().size(), 3u);
}

// 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