OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "cc/quads/draw_polygon.h" | 5 #include "cc/quads/draw_polygon.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 | 8 |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
11 #include "base/memory/ptr_util.h" | |
12 #include "cc/output/bsp_compare_result.h" | 11 #include "cc/output/bsp_compare_result.h" |
13 #include "cc/quads/draw_quad.h" | 12 #include "cc/quads/draw_quad.h" |
14 | 13 |
15 namespace { | 14 namespace { |
16 // This threshold controls how "thick" a plane is. If a point's distance is | 15 // This threshold controls how "thick" a plane is. If a point's distance is |
17 // <= |split_threshold|, then it is considered on the plane for the purpose of | 16 // <= |compare_threshold|, then it is considered on the plane. Only when this |
18 // polygon splitting. | 17 // boundary is crossed do we consider doing splitting. |
| 18 static const float compare_threshold = 0.1f; |
| 19 // |split_threshold| is lower in this case because we want the points created |
| 20 // during splitting to be well within the range of |compare_threshold| for |
| 21 // comparison purposes. The splitting operation will produce intersection points |
| 22 // that fit within a tighter distance to the splitting plane as a result of this |
| 23 // value. By using a value >= |compare_threshold| we run the risk of creating |
| 24 // points that SHOULD be intersecting the "thick plane", but actually fail to |
| 25 // test positively for it because |split_threshold| allowed them to be outside |
| 26 // this range. |
| 27 // This is really supposd to be compare_threshold / 2.0f, but that would |
| 28 // create another static initializer. |
19 static const float split_threshold = 0.05f; | 29 static const float split_threshold = 0.05f; |
20 | 30 |
21 static const float normalized_threshold = 0.001f; | 31 static const float normalized_threshold = 0.001f; |
22 | |
23 void PointInterpolate(const gfx::Point3F& from, | |
24 const gfx::Point3F& to, | |
25 double delta, | |
26 gfx::Point3F* out) { | |
27 out->SetPoint(from.x() + (to.x() - from.x()) * delta, | |
28 from.y() + (to.y() - from.y()) * delta, | |
29 from.z() + (to.z() - from.z()) * delta); | |
30 } | |
31 } // namespace | 32 } // namespace |
32 | 33 |
33 namespace cc { | 34 namespace cc { |
34 | 35 |
35 DrawPolygon::DrawPolygon() { | 36 DrawPolygon::DrawPolygon() { |
36 } | 37 } |
37 | 38 |
38 DrawPolygon::DrawPolygon(const DrawQuad* original, | 39 DrawPolygon::DrawPolygon(const DrawQuad* original, |
39 const std::vector<gfx::Point3F>& in_points, | 40 const std::vector<gfx::Point3F>& in_points, |
40 const gfx::Vector3dF& normal, | 41 const gfx::Vector3dF& normal, |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
124 // | 125 // |
125 void DrawPolygon::RecomputeNormalForTesting() { | 126 void DrawPolygon::RecomputeNormalForTesting() { |
126 ConstructNormal(); | 127 ConstructNormal(); |
127 } | 128 } |
128 #endif | 129 #endif |
129 | 130 |
130 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { | 131 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { |
131 return gfx::DotProduct(point - points_[0], normal_); | 132 return gfx::DotProduct(point - points_[0], normal_); |
132 } | 133 } |
133 | 134 |
| 135 // Checks whether or not shape a lies on the front or back side of b, or |
| 136 // whether they should be considered coplanar. If on the back side, we |
| 137 // say A_BEFORE_B because it should be drawn in that order. |
| 138 // Assumes that layers are split and there are no intersecting planes. |
| 139 BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a, |
| 140 const DrawPolygon& b) { |
| 141 // Let's make sure that this is normalized. Without this SignedPointDistance |
| 142 // will not be right, but putting the check in there will validate it |
| 143 // redundantly for each point. |
| 144 DCHECK_GE(normalized_threshold, std::abs(b.normal_.LengthSquared() - 1.0f)); |
| 145 |
| 146 int pos_count = 0; |
| 147 int neg_count = 0; |
| 148 for (size_t i = 0; i < a.points_.size(); i++) { |
| 149 float sign = b.SignedPointDistance(a.points_[i]); |
| 150 |
| 151 if (sign < -compare_threshold) { |
| 152 ++neg_count; |
| 153 } else if (sign > compare_threshold) { |
| 154 ++pos_count; |
| 155 } |
| 156 |
| 157 if (pos_count && neg_count) { |
| 158 return BSP_SPLIT; |
| 159 } |
| 160 } |
| 161 |
| 162 if (pos_count) { |
| 163 return BSP_FRONT; |
| 164 } |
| 165 if (neg_count) { |
| 166 return BSP_BACK; |
| 167 } |
| 168 |
| 169 double dot = gfx::DotProduct(a.normal_, b.normal_); |
| 170 if ((dot >= 0.0f && a.order_index_ >= b.order_index_) || |
| 171 (dot <= 0.0f && a.order_index_ <= b.order_index_)) { |
| 172 // The sign of the dot product of the normals along with document order |
| 173 // determine which side it goes on, the vertices are ambiguous. |
| 174 return BSP_COPLANAR_BACK; |
| 175 } |
| 176 |
| 177 return BSP_COPLANAR_FRONT; |
| 178 } |
| 179 |
| 180 static bool LineIntersectPlane(const gfx::Point3F& line_start, |
| 181 const gfx::Point3F& line_end, |
| 182 const gfx::Point3F& plane_origin, |
| 183 const gfx::Vector3dF& plane_normal, |
| 184 gfx::Point3F* intersection, |
| 185 float distance_threshold) { |
| 186 const gfx::Vector3dF line_start_vec(line_start.x(), line_start.y(), |
| 187 line_start.z()); |
| 188 const gfx::Vector3dF line_end_vec(line_end.x(), line_end.y(), line_end.z()); |
| 189 const gfx::Vector3dF plane_origin_vec(plane_origin.x(), plane_origin.y(), |
| 190 plane_origin.z()); |
| 191 |
| 192 double plane_d = -gfx::DotProduct(plane_origin_vec, plane_normal); |
| 193 |
| 194 double end_distance = gfx::DotProduct(line_end_vec, plane_normal) + plane_d; |
| 195 if (std::abs(end_distance) <= distance_threshold) { |
| 196 // No intersection if |line_end| is within |distance_threshold| of plane. |
| 197 return false; |
| 198 } |
| 199 |
| 200 double start_distance = |
| 201 gfx::DotProduct(line_start_vec, plane_normal) + plane_d; |
| 202 if (std::abs(start_distance) <= distance_threshold) { |
| 203 // Intersection at |line_start| if |line_start| is within |
| 204 // |distance_threshold| of plane. |
| 205 intersection->SetPoint(line_start.x(), line_start.y(), line_start.z()); |
| 206 return true; |
| 207 } |
| 208 |
| 209 // If signs differ, we cross the plane. |
| 210 if (start_distance * end_distance < 0.0) { |
| 211 // Plane: P . N + d = 0 [ d = -(plane_normal . plane_origin) ] |
| 212 // Ray: P = P0 + Pd * t [ P0 = line_start, Pd = line_end - line_start ] |
| 213 // Substituting: |
| 214 // (P0 + Pd * t) . N + d = 0 |
| 215 // P0 . N + t * Pd . N + d = 0 |
| 216 // t = -(P0 . N + d) / Pd . N |
| 217 |
| 218 gfx::Vector3dF line_delta = line_end - line_start; |
| 219 double t = -start_distance / gfx::DotProduct(plane_normal, line_delta); |
| 220 intersection->SetPoint(line_start.x() + line_delta.x() * t, |
| 221 line_start.y() + line_delta.y() * t, |
| 222 line_start.z() + line_delta.z() * t); |
| 223 |
| 224 return true; |
| 225 } |
| 226 return false; |
| 227 } |
| 228 |
134 // This function is separate from ApplyTransform because it is often unnecessary | 229 // This function is separate from ApplyTransform because it is often unnecessary |
135 // to transform the normal with the rest of the polygon. | 230 // to transform the normal with the rest of the polygon. |
136 // When drawing these polygons, it is necessary to move them back into layer | 231 // When drawing these polygons, it is necessary to move them back into layer |
137 // space before sending them to OpenGL, which requires using ApplyTransform, | 232 // space before sending them to OpenGL, which requires using ApplyTransform, |
138 // but normal information is no longer needed after sorting. | 233 // but normal information is no longer needed after sorting. |
139 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) { | 234 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) { |
140 // Now we use the inverse transpose of |transform| to transform the normal. | 235 // Now we use the inverse transpose of |transform| to transform the normal. |
141 gfx::Transform inverse_transform; | 236 gfx::Transform inverse_transform; |
142 bool inverted = transform.GetInverse(&inverse_transform); | 237 bool inverted = transform.GetInverse(&inverse_transform); |
143 DCHECK(inverted); | 238 DCHECK(inverted); |
(...skipping 29 matching lines...) Expand all Loading... |
173 // In the case of TransformToLayerSpace, we assume that we are giving the | 268 // In the case of TransformToLayerSpace, we assume that we are giving the |
174 // inverse transformation back to the polygon to move it back into layer space | 269 // inverse transformation back to the polygon to move it back into layer space |
175 // but we can ignore the costly process of applying the inverse to the normal | 270 // but we can ignore the costly process of applying the inverse to the normal |
176 // since we know the normal will just reset to its original state. | 271 // since we know the normal will just reset to its original state. |
177 void DrawPolygon::TransformToLayerSpace( | 272 void DrawPolygon::TransformToLayerSpace( |
178 const gfx::Transform& inverse_transform) { | 273 const gfx::Transform& inverse_transform) { |
179 ApplyTransform(inverse_transform); | 274 ApplyTransform(inverse_transform); |
180 normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f); | 275 normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f); |
181 } | 276 } |
182 | 277 |
183 // Split |polygon| based upon |this|, leaving the results in |front| and |back|. | 278 bool DrawPolygon::Split(const DrawPolygon& splitter, |
184 // If |polygon| is not split by |this|, then move it to either |front| or |back| | 279 std::unique_ptr<DrawPolygon>* front, |
185 // depending on its orientation relative to |this|. Sets |is_coplanar| to true | 280 std::unique_ptr<DrawPolygon>* back) { |
186 // if |polygon| is actually coplanar with |this| (in which case whether it is | 281 gfx::Point3F intersections[2]; |
187 // front facing or back facing is determined by the dot products of normals, and | 282 std::vector<gfx::Point3F> out_points[2]; |
188 // document order). | 283 // vertex_before stores the index of the vertex before its matching |
189 void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon, | 284 // intersection. |
190 std::unique_ptr<DrawPolygon>* front, | 285 // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane |
191 std::unique_ptr<DrawPolygon>* back, | 286 // which resulted in the line/plane intersection giving us intersections[0]. |
192 bool* is_coplanar) const { | 287 size_t vertex_before[2]; |
193 DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f)); | 288 size_t points_size = points_.size(); |
| 289 size_t current_intersection = 0; |
194 | 290 |
195 const size_t num_points = polygon->points_.size(); | 291 size_t current_vertex = 0; |
196 const auto next = [num_points](size_t i) { | 292 // We will only have two intersection points because we assume all polygons |
197 return (i + 1) % num_points; | 293 // are convex. |
198 }; | 294 while (current_intersection < 2) { |
199 const auto prev = [num_points](size_t i) { | 295 if (LineIntersectPlane(points_[(current_vertex % points_size)], |
200 return (i + num_points - 1) % num_points; | 296 points_[(current_vertex + 1) % points_size], |
201 }; | 297 splitter.points_[0], |
202 | 298 splitter.normal_, |
203 std::vector<float> vertex_distance; | 299 &intersections[current_intersection], |
204 size_t pos_count = 0; | 300 split_threshold)) { |
205 size_t neg_count = 0; | 301 vertex_before[current_intersection] = current_vertex % points_size; |
206 | 302 current_intersection++; |
207 // Compute plane distances for each vertex of polygon. | 303 // We found both intersection points so we're done already. |
208 vertex_distance.resize(num_points); | 304 if (current_intersection == 2) { |
209 for (size_t i = 0; i < num_points; i++) { | 305 break; |
210 vertex_distance[i] = SignedPointDistance(polygon->points_[i]); | 306 } |
211 if (vertex_distance[i] < -split_threshold) { | 307 } |
212 ++neg_count; | 308 if (current_vertex++ > (points_size)) { |
213 } else if (vertex_distance[i] > split_threshold) { | 309 break; |
214 ++pos_count; | |
215 } else { | |
216 vertex_distance[i] = 0.0; | |
217 } | 310 } |
218 } | 311 } |
| 312 DCHECK_EQ(current_intersection, static_cast<size_t>(2)); |
219 | 313 |
220 // Handle non-splitting cases. | 314 // Since we found both the intersection points, we can begin building the |
221 if (!pos_count && !neg_count) { | 315 // vertex set for both our new polygons. |
222 double dot = gfx::DotProduct(normal_, polygon->normal_); | 316 size_t start1 = (vertex_before[0] + 1) % points_size; |
223 if ((dot >= 0.0f && polygon->order_index_ >= order_index_) || | 317 size_t start2 = (vertex_before[1] + 1) % points_size; |
224 (dot <= 0.0f && polygon->order_index_ <= order_index_)) { | 318 size_t points_remaining = points_size; |
225 *back = std::move(polygon); | 319 |
226 } else { | 320 // First polygon. |
227 *front = std::move(polygon); | 321 out_points[0].push_back(intersections[0]); |
228 } | 322 DCHECK_GE(vertex_before[1], start1); |
229 *is_coplanar = true; | 323 for (size_t i = start1; i <= vertex_before[1]; i++) { |
230 return; | 324 out_points[0].push_back(points_[i]); |
| 325 --points_remaining; |
231 } | 326 } |
| 327 out_points[0].push_back(intersections[1]); |
232 | 328 |
233 *is_coplanar = false; | 329 // Second polygon. |
234 if (!neg_count) { | 330 out_points[1].push_back(intersections[1]); |
235 *front = std::move(polygon); | 331 size_t index = start2; |
236 return; | 332 for (size_t i = 0; i < points_remaining; i++) { |
237 } else if (!pos_count) { | 333 out_points[1].push_back(points_[index % points_size]); |
238 *back = std::move(polygon); | 334 ++index; |
239 return; | |
240 } | 335 } |
| 336 out_points[1].push_back(intersections[0]); |
241 | 337 |
242 // There should be at most two points that are considered to be on the thick | 338 // Give both polygons the original splitting polygon's ID, so that they'll |
243 // plane. If this is not the case, then the polygon is not convex. | 339 // still be sorted properly in co-planar instances. |
244 DCHECK(num_points - pos_count - neg_count <= 2); | 340 std::unique_ptr<DrawPolygon> poly1( |
| 341 new DrawPolygon(original_ref_, out_points[0], normal_, order_index_)); |
| 342 std::unique_ptr<DrawPolygon> poly2( |
| 343 new DrawPolygon(original_ref_, out_points[1], normal_, order_index_)); |
245 | 344 |
246 // Handle splitting case. | 345 DCHECK_GE(poly1->points().size(), 3u); |
247 size_t front_begin; | 346 DCHECK_GE(poly2->points().size(), 3u); |
248 size_t back_begin; | |
249 size_t pre_front_begin; | |
250 size_t pre_back_begin; | |
251 | 347 |
252 // Find the first vertex that is part of the front split polygon. | 348 if (SideCompare(*poly1, splitter) == BSP_FRONT) { |
253 front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), | 349 *front = std::move(poly1); |
254 [](float val) { return val > 0.0; }) - | 350 *back = std::move(poly2); |
255 vertex_distance.begin(); | 351 } else { |
256 while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0) | 352 *front = std::move(poly2); |
257 front_begin = pre_front_begin; | 353 *back = std::move(poly1); |
258 | 354 } |
259 // Find the first vertex that is part of the back split polygon. | 355 return true; |
260 back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), | |
261 [](float val) { return val < 0.0; }) - | |
262 vertex_distance.begin(); | |
263 while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0) | |
264 back_begin = pre_back_begin; | |
265 | |
266 DCHECK(vertex_distance[front_begin] > 0.0); | |
267 DCHECK(vertex_distance[pre_front_begin] <= 0.0); | |
268 DCHECK(vertex_distance[back_begin] < 0.0); | |
269 DCHECK(vertex_distance[pre_back_begin] >= 0.0); | |
270 | |
271 gfx::Point3F pre_pos_intersection; | |
272 gfx::Point3F pre_neg_intersection; | |
273 | |
274 // Compute the intersection points. N.B.: If the "pre" vertex is on | |
275 // the thick plane, then the intersection will be at the same point, because | |
276 // we set vertex_distance to 0 in this case. | |
277 PointInterpolate( | |
278 polygon->points_[pre_front_begin], polygon->points_[front_begin], | |
279 -vertex_distance[pre_front_begin] / | |
280 gfx::DotProduct(normal_, polygon->points_[front_begin] - | |
281 polygon->points_[pre_front_begin]), | |
282 &pre_pos_intersection); | |
283 PointInterpolate( | |
284 polygon->points_[pre_back_begin], polygon->points_[back_begin], | |
285 -vertex_distance[pre_back_begin] / | |
286 gfx::DotProduct(normal_, polygon->points_[back_begin] - | |
287 polygon->points_[pre_back_begin]), | |
288 &pre_neg_intersection); | |
289 | |
290 // Build the front and back polygons. | |
291 std::vector<gfx::Point3F> out_points; | |
292 | |
293 out_points.push_back(pre_pos_intersection); | |
294 do { | |
295 out_points.push_back(polygon->points_[front_begin]); | |
296 front_begin = next(front_begin); | |
297 } while (vertex_distance[front_begin] > 0.0); | |
298 out_points.push_back(pre_neg_intersection); | |
299 *front = | |
300 base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, | |
301 polygon->normal_, polygon->order_index_); | |
302 | |
303 out_points.clear(); | |
304 | |
305 out_points.push_back(pre_neg_intersection); | |
306 do { | |
307 out_points.push_back(polygon->points_[back_begin]); | |
308 back_begin = next(back_begin); | |
309 } while (vertex_distance[back_begin] < 0.0); | |
310 out_points.push_back(pre_pos_intersection); | |
311 *back = | |
312 base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, | |
313 polygon->normal_, polygon->order_index_); | |
314 | |
315 DCHECK_GE((*front)->points().size(), 3u); | |
316 DCHECK_GE((*back)->points().size(), 3u); | |
317 } | 356 } |
318 | 357 |
319 // This algorithm takes the first vertex in the polygon and uses that as a | 358 // 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. | 359 // 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 | 360 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate |
322 // offset+1 and offset+2 respectively. | 361 // offset+1 and offset+2 respectively. |
323 // After the first quad is created, the first vertex in the next quad is the | 362 // 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 | 363 // 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 | 364 // the old |op2|, the last vertex added to the previous quad. This continues |
326 // until all points are exhausted. | 365 // until all points are exhausted. |
(...skipping 16 matching lines...) Expand all Loading... |
343 quads->push_back( | 382 quads->push_back( |
344 gfx::QuadF(first, | 383 gfx::QuadF(first, |
345 gfx::PointF(points_[offset].x(), points_[offset].y()), | 384 gfx::PointF(points_[offset].x(), points_[offset].y()), |
346 gfx::PointF(points_[op1].x(), points_[op1].y()), | 385 gfx::PointF(points_[op1].x(), points_[op1].y()), |
347 gfx::PointF(points_[op2].x(), points_[op2].y()))); | 386 gfx::PointF(points_[op2].x(), points_[op2].y()))); |
348 offset = op2; | 387 offset = op2; |
349 } | 388 } |
350 } | 389 } |
351 | 390 |
352 } // namespace cc | 391 } // namespace cc |
OLD | NEW |