src/cc/quads/draw_polygon.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/quads/draw_polygon.h"
   6
   7 #include <vector>
   8
   9 #include "cc/output/bsp_compare_result.h"
  10 #include "cc/quads/draw_quad.h"
  11
  12 namespace {
  13 // This allows for some imperfection in the normal comparison when checking if
  14 // two pieces of geometry are coplanar.
  15 static const float coplanar_dot_epsilon = 0.01f;
  16 // This threshold controls how "thick" a plane is. If a point's distance is
  17 // <= |compare_threshold|, then it is considered on the plane. Only when this
  18 // boundary is crossed do we consider doing splitting.
  19 static const float compare_threshold = 1.0f;
  20 // |split_threshold| is lower in this case because we want the points created
  21 // during splitting to be well within the range of |compare_threshold| for
  22 // comparison purposes. The splitting operation will produce intersection points
  23 // that fit within a tighter distance to the splitting plane as a result of this
  24 // value. By using a value >= |compare_threshold| we run the risk of creating
  25 // points that SHOULD be intersecting the "thick plane", but actually fail to
  26 // test positively for it because |split_threshold| allowed them to be outside
  27 // this range.
  28 static const float split_threshold = 0.5f;
  29 }  // namespace
  30
  31 namespace cc {
  32
  33 gfx::Vector3dF DrawPolygon::default_normal = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
  34
  35 DrawPolygon::DrawPolygon() {
  36 }
  37
  38 DrawPolygon::DrawPolygon(DrawQuad* original,
  39                          const std::vector<gfx::Point3F>& in_points,
  40                          const gfx::Vector3dF& normal,
  41                          int draw_order_index)
  42     : order_index_(draw_order_index), original_ref_(original) {
  43   for (size_t i = 0; i < in_points.size(); i++) {
  44     points_.push_back(in_points[i]);
  45   }
  46   normal_ = normal;
  47 }
  48
  49 // This takes the original DrawQuad that this polygon should be based on,
  50 // a visible content rect to make the 4 corner points from, and a transformation
  51 // to move it and its normal into screen space.
  52 DrawPolygon::DrawPolygon(DrawQuad* original_ref,
  53                          const gfx::RectF& visible_content_rect,
  54                          const gfx::Transform& transform,
  55                          int draw_order_index)
  56     : order_index_(draw_order_index), original_ref_(original_ref) {
  57   normal_ = default_normal;
  58   gfx::Point3F points[8];
  59   int num_vertices_in_clipped_quad;
  60   gfx::QuadF send_quad(visible_content_rect);
  61
  62   // Doing this mapping here is very important, since we can't just transform
  63   // the points without clipping and not run into strange geometry issues when
  64   // crossing w = 0. At this point, in the constructor, we know that we're
  65   // working with a quad, so we can reuse the MathUtil::MapClippedQuad3d
  66   // function instead of writing a generic polygon version of it.
  67   MathUtil::MapClippedQuad3d(
  68       transform, send_quad, points, &num_vertices_in_clipped_quad);
  69   for (int i = 0; i < num_vertices_in_clipped_quad; i++) {
  70     points_.push_back(points[i]);
  71   }
  72   ApplyTransformToNormal(transform);
  73 }
  74
  75 DrawPolygon::~DrawPolygon() {
  76 }
  77
  78 scoped_ptr<DrawPolygon> DrawPolygon::CreateCopy() {
  79   DrawPolygon* new_polygon = new DrawPolygon();
  80   new_polygon->order_index_ = order_index_;
  81   new_polygon->original_ref_ = original_ref_;
  82   new_polygon->points_.reserve(points_.size());
  83   new_polygon->points_ = points_;
  84   new_polygon->normal_.set_x(normal_.x());
  85   new_polygon->normal_.set_y(normal_.y());
  86   new_polygon->normal_.set_z(normal_.z());
  87   return scoped_ptr<DrawPolygon>(new_polygon);
  88 }
  89
  90 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const {
  91   return gfx::DotProduct(point - points_[0], normal_);
  92 }
  93
  94 // Checks whether or not shape a lies on the front or back side of b, or
  95 // whether they should be considered coplanar. If on the back side, we
  96 // say ABeforeB because it should be drawn in that order.
  97 // Assumes that layers are split and there are no intersecting planes.
  98 BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a,
  99                                           const DrawPolygon& b) {
 100   // Right away let's check if they're coplanar
 101   double dot = gfx::DotProduct(a.normal_, b.normal_);
 102   float sign = 0.0f;
 103   bool normal_match = false;
 104   // This check assumes that the normals are normalized.
 105   if (std::abs(dot) >= 1.0f - coplanar_dot_epsilon) {
 106     normal_match = true;
 107     // The normals are matching enough that we only have to test one point.
 108     sign = gfx::DotProduct(a.points_[0] - b.points_[0], b.normal_);
 109     // Is it on either side of the splitter?
 110     if (sign < -compare_threshold) {
 111       return BSP_BACK;
 112     }
 113
 114     if (sign > compare_threshold) {
 115       return BSP_FRONT;
 116     }
 117
 118     // No it wasn't, so the sign of the dot product of the normals
 119     // along with document order determines which side it goes on.
 120     if (dot >= 0.0f) {
 121       if (a.order_index_ < b.order_index_) {
 122         return BSP_COPLANAR_FRONT;
 123       }
 124       return BSP_COPLANAR_BACK;
 125     }
 126
 127     if (a.order_index_ < b.order_index_) {
 128       return BSP_COPLANAR_BACK;
 129     }
 130     return BSP_COPLANAR_FRONT;
 131   }
 132
 133   int pos_count = 0;
 134   int neg_count = 0;
 135   for (size_t i = 0; i < a.points_.size(); i++) {
 136     if (!normal_match || (normal_match && i > 0)) {
 137       sign = gfx::DotProduct(a.points_[i] - b.points_[0], b.normal_);
 138     }
 139
 140     if (sign < -compare_threshold) {
 141       ++neg_count;
 142     } else if (sign > compare_threshold) {
 143       ++pos_count;
 144     }
 145
 146     if (pos_count && neg_count) {
 147       return BSP_SPLIT;
 148     }
 149   }
 150
 151   if (pos_count) {
 152     return BSP_FRONT;
 153   }
 154   return BSP_BACK;
 155 }
 156
 157 static bool LineIntersectPlane(const gfx::Point3F& line_start,
 158                                const gfx::Point3F& line_end,
 159                                const gfx::Point3F& plane_origin,
 160                                const gfx::Vector3dF& plane_normal,
 161                                gfx::Point3F* intersection,
 162                                float distance_threshold) {
 163   gfx::Vector3dF start_to_origin_vector = plane_origin - line_start;
 164   gfx::Vector3dF end_to_origin_vector = plane_origin - line_end;
 165
 166   double start_distance = gfx::DotProduct(start_to_origin_vector, plane_normal);
 167   double end_distance = gfx::DotProduct(end_to_origin_vector, plane_normal);
 168
 169   // The case where one vertex lies on the thick-plane and the other
 170   // is outside of it.
 171   if (std::abs(start_distance) < distance_threshold &&
 172       std::abs(end_distance) > distance_threshold) {
 173     intersection->SetPoint(line_start.x(), line_start.y(), line_start.z());
 174     return true;
 175   }
 176
 177   // This is the case where we clearly cross the thick-plane.
 178   if ((start_distance > distance_threshold &&
 179        end_distance < -distance_threshold) ||
 180       (start_distance < -distance_threshold &&
 181        end_distance > distance_threshold)) {
 182     gfx::Vector3dF v = line_end - line_start;
 183     float total_distance = std::abs(start_distance) + std::abs(end_distance);
 184     float lerp_factor = std::abs(start_distance) / total_distance;
 185
 186     intersection->SetPoint(line_start.x() + (v.x() * lerp_factor),
 187                            line_start.y() + (v.y() * lerp_factor),
 188                            line_start.z() + (v.z() * lerp_factor));
 189
 190     return true;
 191   }
 192   return false;
 193 }
 194
 195 // This function is separate from ApplyTransform because it is often unnecessary
 196 // to transform the normal with the rest of the polygon.
 197 // When drawing these polygons, it is necessary to move them back into layer
 198 // space before sending them to OpenGL, which requires using ApplyTransform,
 199 // but normal information is no longer needed after sorting.
 200 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) {
 201   // Now we use the inverse transpose of |transform| to transform the normal.
 202   gfx::Transform inverse_transform;
 203   bool inverted = transform.GetInverse(&inverse_transform);
 204   DCHECK(inverted);
 205   if (!inverted)
 206     return;
 207   inverse_transform.Transpose();
 208
 209   gfx::Point3F new_normal(normal_.x(), normal_.y(), normal_.z());
 210   inverse_transform.TransformPoint(&new_normal);
 211   // Make sure our normal is still normalized.
 212   normal_ = gfx::Vector3dF(new_normal.x(), new_normal.y(), new_normal.z());
 213   float normal_magnitude = normal_.Length();
 214   if (normal_magnitude != 0 && normal_magnitude != 1) {
 215     normal_.Scale(1.0f / normal_magnitude);
 216   }
 217 }
 218
 219 void DrawPolygon::ApplyTransform(const gfx::Transform& transform) {
 220   for (size_t i = 0; i < points_.size(); i++) {
 221     transform.TransformPoint(&points_[i]);
 222   }
 223 }
 224
 225 // TransformToScreenSpace assumes we're moving a layer from its layer space
 226 // into 3D screen space, which for sorting purposes requires the normal to
 227 // be transformed along with the vertices.
 228 void DrawPolygon::TransformToScreenSpace(const gfx::Transform& transform) {
 229   ApplyTransform(transform);
 230   ApplyTransformToNormal(transform);
 231 }
 232
 233 // In the case of TransformToLayerSpace, we assume that we are giving the
 234 // inverse transformation back to the polygon to move it back into layer space
 235 // but we can ignore the costly process of applying the inverse to the normal
 236 // since we know the normal will just reset to its original state.
 237 void DrawPolygon::TransformToLayerSpace(
 238     const gfx::Transform& inverse_transform) {
 239   ApplyTransform(inverse_transform);
 240   normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
 241 }
 242
 243 bool DrawPolygon::Split(const DrawPolygon& splitter,
 244                         scoped_ptr<DrawPolygon>* front,
 245                         scoped_ptr<DrawPolygon>* back) {
 246   gfx::Point3F intersections[2];
 247   std::vector<gfx::Point3F> out_points[2];
 248   // vertex_before stores the index of the vertex before its matching
 249   // intersection.
 250   // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane
 251   // which resulted in the line/plane intersection giving us intersections[0].
 252   size_t vertex_before[2];
 253   size_t points_size = points_.size();
 254   size_t current_intersection = 0;
 255
 256   size_t current_vertex = 0;
 257   // We will only have two intersection points because we assume all polygons
 258   // are convex.
 259   while (current_intersection < 2) {
 260     if (LineIntersectPlane(points_[(current_vertex % points_size)],
 261                            points_[(current_vertex + 1) % points_size],
 262                            splitter.points_[0],
 263                            splitter.normal_,
 264                            &intersections[current_intersection],
 265                            split_threshold)) {
 266       vertex_before[current_intersection] = current_vertex % points_size;
 267       current_intersection++;
 268       // We found both intersection points so we're done already.
 269       if (current_intersection == 2) {
 270         break;
 271       }
 272     }
 273     if (current_vertex++ > points_size) {
 274       break;
 275     }
 276   }
 277   DCHECK_EQ(current_intersection, static_cast<size_t>(2));
 278
 279   // Since we found both the intersection points, we can begin building the
 280   // vertex set for both our new polygons.
 281   size_t start1 = (vertex_before[0] + 1) % points_size;
 282   size_t start2 = (vertex_before[1] + 1) % points_size;
 283   size_t points_remaining = points_size;
 284
 285   // First polygon.
 286   out_points[0].push_back(intersections[0]);
 287   for (size_t i = start1; i <= vertex_before[1]; i++) {
 288     out_points[0].push_back(points_[i]);
 289     --points_remaining;
 290   }
 291   out_points[0].push_back(intersections[1]);
 292
 293   // Second polygon.
 294   out_points[1].push_back(intersections[1]);
 295   size_t index = start2;
 296   for (size_t i = 0; i < points_remaining; i++) {
 297     out_points[1].push_back(points_[index % points_size]);
 298     ++index;
 299   }
 300   out_points[1].push_back(intersections[0]);
 301
 302   // Give both polygons the original splitting polygon's ID, so that they'll
 303   // still be sorted properly in co-planar instances.
 304   scoped_ptr<DrawPolygon> poly1(
 305       new DrawPolygon(original_ref_, out_points[0], normal_, order_index_));
 306   scoped_ptr<DrawPolygon> poly2(
 307       new DrawPolygon(original_ref_, out_points[1], normal_, order_index_));
 308
 309   if (SideCompare(*poly1, splitter) == BSP_FRONT) {
 310     *front = poly1.Pass();
 311     *back = poly2.Pass();
 312   } else {
 313     *front = poly2.Pass();
 314     *back = poly1.Pass();
 315   }
 316   return true;
 317 }
 318
 319 // This algorithm takes the first vertex in the polygon and uses that as a
 320 // pivot point to fan out and create quads from the rest of the vertices.
 321 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate
 322 // offset+1 and offset+2 respectively.
 323 // After the first quad is created, the first vertex in the next quad is the
 324 // same as all the rest, the pivot point. The second vertex in the next quad is
 325 // the old |op2|, the last vertex added to the previous quad. This continues
 326 // until all points are exhausted.
 327 // The special case here is where there are only 3 points remaining, in which
 328 // case we use the same values for vertex 3 and 4 to make a degenerate quad
 329 // that represents a triangle.
 330 void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const {
 331   if (points_.size() <= 2)
 332     return;
 333
 334   gfx::PointF first(points_[0].x(), points_[0].y());
 335   size_t offset = 1;
 336   while (offset < points_.size() - 1) {
 337     size_t op1 = offset + 1;
 338     size_t op2 = offset + 2;
 339     if (op2 >= points_.size()) {
 340       // It's going to be a degenerate triangle.
 341       op2 = op1;
 342     }
 343     quads->push_back(
 344         gfx::QuadF(first,
 345                    gfx::PointF(points_[offset].x(), points_[offset].y()),
 346                    gfx::PointF(points_[op1].x(), points_[op1].y()),
 347                    gfx::PointF(points_[op2].x(), points_[op2].y())));
 348     offset = op2;
 349   }
 350 }
 351
 352 }  // namespace cc