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" |
11 #include "cc/output/bsp_compare_result.h" | 12 #include "cc/output/bsp_compare_result.h" |
12 #include "cc/quads/draw_quad.h" | 13 #include "cc/quads/draw_quad.h" |
13 | 14 |
14 namespace { | 15 namespace { |
15 // This threshold controls how "thick" a plane is. If a point's distance is | 16 // This threshold controls how "thick" a plane is. If a point's distance is |
16 // <= |compare_threshold|, then it is considered on the plane. Only when this | 17 // <= |split_threshold|, then it is considered on the plane for the purpose of |
17 // boundary is crossed do we consider doing splitting. | 18 // polygon 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. | |
29 static const float split_threshold = 0.05f; | 19 static const float split_threshold = 0.05f; |
30 | 20 |
31 static const float normalized_threshold = 0.001f; | 21 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 } |
32 } // namespace | 31 } // namespace |
33 | 32 |
34 namespace cc { | 33 namespace cc { |
35 | 34 |
36 DrawPolygon::DrawPolygon() { | 35 DrawPolygon::DrawPolygon() { |
37 } | 36 } |
38 | 37 |
39 DrawPolygon::DrawPolygon(const DrawQuad* original, | 38 DrawPolygon::DrawPolygon(const DrawQuad* original, |
40 const std::vector<gfx::Point3F>& in_points, | 39 const std::vector<gfx::Point3F>& in_points, |
41 const gfx::Vector3dF& normal, | 40 const gfx::Vector3dF& normal, |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
125 // | 124 // |
126 void DrawPolygon::RecomputeNormalForTesting() { | 125 void DrawPolygon::RecomputeNormalForTesting() { |
127 ConstructNormal(); | 126 ConstructNormal(); |
128 } | 127 } |
129 #endif | 128 #endif |
130 | 129 |
131 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { | 130 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { |
132 return gfx::DotProduct(point - points_[0], normal_); | 131 return gfx::DotProduct(point - points_[0], normal_); |
133 } | 132 } |
134 | 133 |
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 | |
229 // This function is separate from ApplyTransform because it is often unnecessary | 134 // This function is separate from ApplyTransform because it is often unnecessary |
230 // to transform the normal with the rest of the polygon. | 135 // to transform the normal with the rest of the polygon. |
231 // When drawing these polygons, it is necessary to move them back into layer | 136 // When drawing these polygons, it is necessary to move them back into layer |
232 // space before sending them to OpenGL, which requires using ApplyTransform, | 137 // space before sending them to OpenGL, which requires using ApplyTransform, |
233 // but normal information is no longer needed after sorting. | 138 // but normal information is no longer needed after sorting. |
234 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) { | 139 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) { |
235 // Now we use the inverse transpose of |transform| to transform the normal. | 140 // Now we use the inverse transpose of |transform| to transform the normal. |
236 gfx::Transform inverse_transform; | 141 gfx::Transform inverse_transform; |
237 bool inverted = transform.GetInverse(&inverse_transform); | 142 bool inverted = transform.GetInverse(&inverse_transform); |
238 DCHECK(inverted); | 143 DCHECK(inverted); |
(...skipping 29 matching lines...) Expand all Loading... |
268 // In the case of TransformToLayerSpace, we assume that we are giving the | 173 // In the case of TransformToLayerSpace, we assume that we are giving the |
269 // inverse transformation back to the polygon to move it back into layer space | 174 // inverse transformation back to the polygon to move it back into layer space |
270 // but we can ignore the costly process of applying the inverse to the normal | 175 // but we can ignore the costly process of applying the inverse to the normal |
271 // since we know the normal will just reset to its original state. | 176 // since we know the normal will just reset to its original state. |
272 void DrawPolygon::TransformToLayerSpace( | 177 void DrawPolygon::TransformToLayerSpace( |
273 const gfx::Transform& inverse_transform) { | 178 const gfx::Transform& inverse_transform) { |
274 ApplyTransform(inverse_transform); | 179 ApplyTransform(inverse_transform); |
275 normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f); | 180 normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f); |
276 } | 181 } |
277 | 182 |
278 bool DrawPolygon::Split(const DrawPolygon& splitter, | 183 // Split |polygon| based upon |this|, leaving the results in |front| and |back|. |
279 std::unique_ptr<DrawPolygon>* front, | 184 // If |polygon| is not split by |this|, then move it to either |front| or |back| |
280 std::unique_ptr<DrawPolygon>* back) { | 185 // depending on its orientation relative to |this|. Sets |is_coplanar| to true |
281 gfx::Point3F intersections[2]; | 186 // if |polygon| is actually coplanar with |this| (in which case whether it is |
282 std::vector<gfx::Point3F> out_points[2]; | 187 // front facing or back facing is determined by the dot products of normals, and |
283 // vertex_before stores the index of the vertex before its matching | 188 // document order). |
284 // intersection. | 189 void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon, |
285 // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane | 190 std::unique_ptr<DrawPolygon>* front, |
286 // which resulted in the line/plane intersection giving us intersections[0]. | 191 std::unique_ptr<DrawPolygon>* back, |
287 size_t vertex_before[2]; | 192 bool* is_coplanar) const { |
288 size_t points_size = points_.size(); | 193 DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f)); |
289 size_t current_intersection = 0; | |
290 | 194 |
291 size_t current_vertex = 0; | 195 const size_t num_points = polygon->points_.size(); |
292 // We will only have two intersection points because we assume all polygons | 196 const auto next = [num_points](size_t i) { return (i + 1) % num_points; }; |
293 // are convex. | 197 const auto prev = [num_points](size_t i) { |
294 while (current_intersection < 2) { | 198 return (i + num_points - 1) % num_points; |
295 if (LineIntersectPlane(points_[(current_vertex % points_size)], | 199 }; |
296 points_[(current_vertex + 1) % points_size], | 200 |
297 splitter.points_[0], | 201 std::vector<float> vertex_distance; |
298 splitter.normal_, | 202 size_t pos_count = 0; |
299 &intersections[current_intersection], | 203 size_t neg_count = 0; |
300 split_threshold)) { | 204 |
301 vertex_before[current_intersection] = current_vertex % points_size; | 205 // Compute plane distances for each vertex of polygon. |
302 current_intersection++; | 206 vertex_distance.resize(num_points); |
303 // We found both intersection points so we're done already. | 207 for (size_t i = 0; i < num_points; i++) { |
304 if (current_intersection == 2) { | 208 vertex_distance[i] = SignedPointDistance(polygon->points_[i]); |
305 break; | 209 if (vertex_distance[i] < -split_threshold) { |
306 } | 210 ++neg_count; |
307 } | 211 } else if (vertex_distance[i] > split_threshold) { |
308 if (current_vertex++ > (points_size)) { | 212 ++pos_count; |
309 break; | 213 } else { |
| 214 vertex_distance[i] = 0.0; |
310 } | 215 } |
311 } | 216 } |
312 DCHECK_EQ(current_intersection, static_cast<size_t>(2)); | |
313 | 217 |
314 // Since we found both the intersection points, we can begin building the | 218 // Handle non-splitting cases. |
315 // vertex set for both our new polygons. | 219 if (!pos_count && !neg_count) { |
316 size_t start1 = (vertex_before[0] + 1) % points_size; | 220 double dot = gfx::DotProduct(normal_, polygon->normal_); |
317 size_t start2 = (vertex_before[1] + 1) % points_size; | 221 if ((dot >= 0.0f && polygon->order_index_ >= order_index_) || |
318 size_t points_remaining = points_size; | 222 (dot <= 0.0f && polygon->order_index_ <= order_index_)) { |
| 223 *back = std::move(polygon); |
| 224 } else { |
| 225 *front = std::move(polygon); |
| 226 } |
| 227 *is_coplanar = true; |
| 228 return; |
| 229 } |
319 | 230 |
320 // First polygon. | 231 *is_coplanar = false; |
321 out_points[0].push_back(intersections[0]); | 232 if (!neg_count) { |
322 DCHECK_GE(vertex_before[1], start1); | 233 *front = std::move(polygon); |
323 for (size_t i = start1; i <= vertex_before[1]; i++) { | 234 return; |
324 out_points[0].push_back(points_[i]); | 235 } else if (!pos_count) { |
325 --points_remaining; | 236 *back = std::move(polygon); |
| 237 return; |
326 } | 238 } |
327 out_points[0].push_back(intersections[1]); | |
328 | 239 |
329 // Second polygon. | 240 // There should be at most two points that are considered to be on the thick |
330 out_points[1].push_back(intersections[1]); | 241 // plane. If this is not the case, then the polygon is not convex. |
331 size_t index = start2; | 242 DCHECK_LE(num_points - pos_count - neg_count, 2u); |
332 for (size_t i = 0; i < points_remaining; i++) { | |
333 out_points[1].push_back(points_[index % points_size]); | |
334 ++index; | |
335 } | |
336 out_points[1].push_back(intersections[0]); | |
337 | 243 |
338 // Give both polygons the original splitting polygon's ID, so that they'll | 244 // Handle splitting case. |
339 // still be sorted properly in co-planar instances. | 245 size_t front_begin; |
340 std::unique_ptr<DrawPolygon> poly1( | 246 size_t back_begin; |
341 new DrawPolygon(original_ref_, out_points[0], normal_, order_index_)); | 247 size_t pre_front_begin; |
342 std::unique_ptr<DrawPolygon> poly2( | 248 size_t pre_back_begin; |
343 new DrawPolygon(original_ref_, out_points[1], normal_, order_index_)); | |
344 | 249 |
345 DCHECK_GE(poly1->points().size(), 3u); | 250 // Find the first vertex that is part of the front split polygon. |
346 DCHECK_GE(poly2->points().size(), 3u); | 251 front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), |
| 252 [](float val) { return val > 0.0; }) - |
| 253 vertex_distance.begin(); |
| 254 while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0) |
| 255 front_begin = pre_front_begin; |
347 | 256 |
348 if (SideCompare(*poly1, splitter) == BSP_FRONT) { | 257 // Find the first vertex that is part of the back split polygon. |
349 *front = std::move(poly1); | 258 back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), |
350 *back = std::move(poly2); | 259 [](float val) { return val < 0.0; }) - |
351 } else { | 260 vertex_distance.begin(); |
352 *front = std::move(poly2); | 261 while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0) |
353 *back = std::move(poly1); | 262 back_begin = pre_back_begin; |
354 } | 263 |
355 return true; | 264 DCHECK(vertex_distance[front_begin] > 0.0); |
| 265 DCHECK(vertex_distance[pre_front_begin] <= 0.0); |
| 266 DCHECK(vertex_distance[back_begin] < 0.0); |
| 267 DCHECK(vertex_distance[pre_back_begin] >= 0.0); |
| 268 |
| 269 gfx::Point3F pre_pos_intersection; |
| 270 gfx::Point3F pre_neg_intersection; |
| 271 |
| 272 // Compute the intersection points. N.B.: If the "pre" vertex is on |
| 273 // the thick plane, then the intersection will be at the same point, because |
| 274 // we set vertex_distance to 0 in this case. |
| 275 PointInterpolate( |
| 276 polygon->points_[pre_front_begin], polygon->points_[front_begin], |
| 277 -vertex_distance[pre_front_begin] / |
| 278 gfx::DotProduct(normal_, polygon->points_[front_begin] - |
| 279 polygon->points_[pre_front_begin]), |
| 280 &pre_pos_intersection); |
| 281 PointInterpolate( |
| 282 polygon->points_[pre_back_begin], polygon->points_[back_begin], |
| 283 -vertex_distance[pre_back_begin] / |
| 284 gfx::DotProduct(normal_, polygon->points_[back_begin] - |
| 285 polygon->points_[pre_back_begin]), |
| 286 &pre_neg_intersection); |
| 287 |
| 288 // Build the front and back polygons. |
| 289 std::vector<gfx::Point3F> out_points; |
| 290 |
| 291 out_points.push_back(pre_pos_intersection); |
| 292 do { |
| 293 out_points.push_back(polygon->points_[front_begin]); |
| 294 front_begin = next(front_begin); |
| 295 } while (vertex_distance[front_begin] > 0.0); |
| 296 out_points.push_back(pre_neg_intersection); |
| 297 *front = |
| 298 base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, |
| 299 polygon->normal_, polygon->order_index_); |
| 300 |
| 301 out_points.clear(); |
| 302 |
| 303 out_points.push_back(pre_neg_intersection); |
| 304 do { |
| 305 out_points.push_back(polygon->points_[back_begin]); |
| 306 back_begin = next(back_begin); |
| 307 } while (vertex_distance[back_begin] < 0.0); |
| 308 out_points.push_back(pre_pos_intersection); |
| 309 *back = |
| 310 base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, |
| 311 polygon->normal_, polygon->order_index_); |
| 312 |
| 313 DCHECK_GE((*front)->points().size(), 3u); |
| 314 DCHECK_GE((*back)->points().size(), 3u); |
356 } | 315 } |
357 | 316 |
358 // This algorithm takes the first vertex in the polygon and uses that as a | 317 // This algorithm takes the first vertex in the polygon and uses that as a |
359 // pivot point to fan out and create quads from the rest of the vertices. | 318 // pivot point to fan out and create quads from the rest of the vertices. |
360 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate | 319 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate |
361 // offset+1 and offset+2 respectively. | 320 // offset+1 and offset+2 respectively. |
362 // After the first quad is created, the first vertex in the next quad is the | 321 // After the first quad is created, the first vertex in the next quad is the |
363 // same as all the rest, the pivot point. The second vertex in the next quad is | 322 // same as all the rest, the pivot point. The second vertex in the next quad is |
364 // the old |op2|, the last vertex added to the previous quad. This continues | 323 // the old |op2|, the last vertex added to the previous quad. This continues |
365 // until all points are exhausted. | 324 // until all points are exhausted. |
(...skipping 16 matching lines...) Expand all Loading... |
382 quads->push_back( | 341 quads->push_back( |
383 gfx::QuadF(first, | 342 gfx::QuadF(first, |
384 gfx::PointF(points_[offset].x(), points_[offset].y()), | 343 gfx::PointF(points_[offset].x(), points_[offset].y()), |
385 gfx::PointF(points_[op1].x(), points_[op1].y()), | 344 gfx::PointF(points_[op1].x(), points_[op1].y()), |
386 gfx::PointF(points_[op2].x(), points_[op2].y()))); | 345 gfx::PointF(points_[op2].x(), points_[op2].y()))); |
387 offset = op2; | 346 offset = op2; |
388 } | 347 } |
389 } | 348 } |
390 | 349 |
391 } // namespace cc | 350 } // namespace cc |
OLD | NEW |