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 353