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 "components/viz/service/display/draw_polygon.h"
6
7 #include <stddef.h>
8 #include <vector>
9
10 #include "build/build_config.h"
11 #include "cc/base/math_util.h"
12 #include "components/viz/common/quads/draw_quad.h"
13
14 namespace {
15 // This threshold controls how "thick" a plane is. If a point's distance is
16 // <= |split_threshold|, then it is considered on the plane for the purpose of
17 // polygon splitting.
18 static const float split_threshold = 0.05f;
19
20 static const float normalized_threshold = 0.001f;
21
PointInterpolate(const gfx::Point3F & from,const gfx::Point3F & to,double delta,gfx::Point3F * out)22 void PointInterpolate(const gfx::Point3F& from,
23 const gfx::Point3F& to,
24 double delta,
25 gfx::Point3F* out) {
26 out->SetPoint(from.x() + (to.x() - from.x()) * delta,
27 from.y() + (to.y() - from.y()) * delta,
28 from.z() + (to.z() - from.z()) * delta);
29 }
30 } // namespace
31
32 namespace viz {
33
34 DrawPolygon::DrawPolygon() = default;
35
DrawPolygon(const DrawQuad * original,const std::vector<gfx::Point3F> & in_points,const gfx::Vector3dF & normal,int draw_order_index)36 DrawPolygon::DrawPolygon(const DrawQuad* original,
37 const std::vector<gfx::Point3F>& in_points,
38 const gfx::Vector3dF& normal,
39 int draw_order_index)
40 : normal_(normal),
41 order_index_(draw_order_index),
42 original_ref_(original),
43 is_split_(true) {
44 for (size_t i = 0; i < in_points.size(); i++) {
45 points_.push_back(in_points[i]);
46 }
47 // If life was fair, we could recalculate the normal from the given points
48 // and assert it was roughly the same. This causes unhelpful breaks on
49 // trivial slices of split polygons. Similarly, when splitting, it is
50 // better to keep the normal that was constructed from the original.
51 }
52
53 // This takes the original DrawQuad that this polygon should be based on,
54 // a visible content rect to make the 4 corner points from, and a transformation
55 // to move it and its normal into screen space.
DrawPolygon(const DrawQuad * original_ref,const gfx::RectF & visible_layer_rect,const gfx::Transform & transform,int draw_order_index)56 DrawPolygon::DrawPolygon(const DrawQuad* original_ref,
57 const gfx::RectF& visible_layer_rect,
58 const gfx::Transform& transform,
59 int draw_order_index)
60 : normal_(0.0f, 0.0f, 1.0f),
61 order_index_(draw_order_index),
62 original_ref_(original_ref),
63 is_split_(false) {
64 gfx::Point3F points[6];
65 int num_vertices_in_clipped_quad;
66 gfx::QuadF send_quad(visible_layer_rect);
67
68 // Doing this mapping here is very important, since we can't just transform
69 // the points without clipping and not run into strange geometry issues when
70 // crossing w = 0. At this point, in the constructor, we know that we're
71 // working with a quad, so we can reuse the MathUtil::MapClippedQuad3d
72 // function instead of writing a generic polygon version of it.
73 cc::MathUtil::MapClippedQuad3d(transform, send_quad, points,
74 &num_vertices_in_clipped_quad);
75 for (int i = 0; i < num_vertices_in_clipped_quad; i++) {
76 points_.push_back(points[i]);
77 }
78 transform.TransformVector(&normal_);
79 ConstructNormal();
80 }
81
82 DrawPolygon::~DrawPolygon() = default;
83
CreateCopy()84 std::unique_ptr<DrawPolygon> DrawPolygon::CreateCopy() {
85 std::unique_ptr<DrawPolygon> new_polygon(new DrawPolygon());
86 new_polygon->order_index_ = order_index_;
87 new_polygon->original_ref_ = original_ref_;
88 new_polygon->points_.reserve(points_.size());
89 new_polygon->points_ = points_;
90 new_polygon->normal_.set_x(normal_.x());
91 new_polygon->normal_.set_y(normal_.y());
92 new_polygon->normal_.set_z(normal_.z());
93 return new_polygon;
94 }
95
96 //
97 // If this were to be more generally used and expected to be applicable
98 // replacing this with Newell's algorithm (or an improvement thereof)
99 // would be preferable, but usually this is coming in from a rectangle
100 // that has been transformed to screen space and clipped.
101 // Averaging a few near diagonal cross products is pretty good in that case.
102 //
ConstructNormal()103 void DrawPolygon::ConstructNormal() {
104 gfx::Vector3dF new_normal(0.0f, 0.0f, 0.0f);
105 int delta = points_.size() / 2;
106 for (size_t i = 1; i + delta < points_.size(); i++) {
107 new_normal +=
108 CrossProduct(points_[i] - points_[0], points_[i + delta] - points_[0]);
109 }
110 float normal_magnitude = new_normal.Length();
111 // Here we constrain the new normal to point in the same sense as the old one.
112 // This allows us to handle winding-reversing transforms better.
113 if (gfx::DotProduct(normal_, new_normal) < 0.0) {
114 normal_magnitude *= -1.0;
115 }
116 if (normal_magnitude != 0 && normal_magnitude != 1) {
117 new_normal.Scale(1.0f / normal_magnitude);
118 }
119 normal_ = new_normal;
120 }
121
122 #if defined(OS_WIN)
123 //
124 // Allows the unittest to invoke this for the more general constructor.
125 //
RecomputeNormalForTesting()126 void DrawPolygon::RecomputeNormalForTesting() {
127 ConstructNormal();
128 }
129 #endif
130
SignedPointDistance(const gfx::Point3F & point) const131 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const {
132 return gfx::DotProduct(point - points_[0], normal_);
133 }
134
135 // This function is separate from ApplyTransform because it is often unnecessary
136 // to transform the normal with the rest of the polygon.
137 // When drawing these polygons, it is necessary to move them back into layer
138 // space before sending them to OpenGL, which requires using ApplyTransform,
139 // but normal information is no longer needed after sorting.
ApplyTransformToNormal(const gfx::Transform & transform)140 void DrawPolygon::ApplyTransformToNormal(const gfx::Transform& transform) {
141 // Now we use the inverse transpose of |transform| to transform the normal.
142 gfx::Transform inverse_transform;
143 bool inverted = transform.GetInverse(&inverse_transform);
144 DCHECK(inverted);
145 if (!inverted)
146 return;
147 inverse_transform.Transpose();
148
149 gfx::Point3F new_normal(normal_.x(), normal_.y(), normal_.z());
150 inverse_transform.TransformPoint(&new_normal);
151 // Make sure our normal is still normalized.
152 normal_ = gfx::Vector3dF(new_normal.x(), new_normal.y(), new_normal.z());
153 float normal_magnitude = normal_.Length();
154 if (normal_magnitude != 0 && normal_magnitude != 1) {
155 normal_.Scale(1.0f / normal_magnitude);
156 }
157 }
158
ApplyTransform(const gfx::Transform & transform)159 void DrawPolygon::ApplyTransform(const gfx::Transform& transform) {
160 for (size_t i = 0; i < points_.size(); i++) {
161 transform.TransformPoint(&points_[i]);
162 }
163 }
164
165 // TransformToScreenSpace assumes we're moving a layer from its layer space
166 // into 3D screen space, which for sorting purposes requires the normal to
167 // be transformed along with the vertices.
TransformToScreenSpace(const gfx::Transform & transform)168 void DrawPolygon::TransformToScreenSpace(const gfx::Transform& transform) {
169 ApplyTransform(transform);
170 transform.TransformVector(&normal_);
171 ConstructNormal();
172 }
173
174 // In the case of TransformToLayerSpace, we assume that we are giving the
175 // inverse transformation back to the polygon to move it back into layer space
176 // but we can ignore the costly process of applying the inverse to the normal
177 // since we know the normal will just reset to its original state.
TransformToLayerSpace(const gfx::Transform & inverse_transform)178 void DrawPolygon::TransformToLayerSpace(
179 const gfx::Transform& inverse_transform) {
180 ApplyTransform(inverse_transform);
181 normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f);
182 }
183
184 // Split |polygon| based upon |this|, leaving the results in |front| and |back|.
185 // If |polygon| is not split by |this|, then move it to either |front| or |back|
186 // depending on its orientation relative to |this|. Sets |is_coplanar| to true
187 // if |polygon| is actually coplanar with |this| (in which case whether it is
188 // front facing or back facing is determined by the dot products of normals, and
189 // document order).
SplitPolygon(std::unique_ptr<DrawPolygon> polygon,std::unique_ptr<DrawPolygon> * front,std::unique_ptr<DrawPolygon> * back,bool * is_coplanar) const190 void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon,
191 std::unique_ptr<DrawPolygon>* front,
192 std::unique_ptr<DrawPolygon>* back,
193 bool* is_coplanar) const {
194 DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f));
195
196 const size_t num_points = polygon->points_.size();
197 const auto next = [num_points](size_t i) { return (i + 1) % num_points; };
198 const auto prev = [num_points](size_t i) {
199 return (i + num_points - 1) % num_points;
200 };
201
202 std::vector<float> vertex_distance;
203 size_t pos_count = 0;
204 size_t neg_count = 0;
205
206 // Compute plane distances for each vertex of polygon.
207 vertex_distance.resize(num_points);
208 for (size_t i = 0; i < num_points; i++) {
209 vertex_distance[i] = SignedPointDistance(polygon->points_[i]);
210 if (vertex_distance[i] < -split_threshold) {
211 ++neg_count;
212 } else if (vertex_distance[i] > split_threshold) {
213 ++pos_count;
214 } else {
215 vertex_distance[i] = 0.0;
216 }
217 }
218
219 // Handle non-splitting cases.
220 if (!pos_count && !neg_count) {
221 double dot = gfx::DotProduct(normal_, polygon->normal_);
222 if ((dot >= 0.0f && polygon->order_index_ >= order_index_) ||
223 (dot <= 0.0f && polygon->order_index_ <= order_index_)) {
224 *back = std::move(polygon);
225 } else {
226 *front = std::move(polygon);
227 }
228 *is_coplanar = true;
229 return;
230 }
231
232 *is_coplanar = false;
233 if (!neg_count) {
234 *front = std::move(polygon);
235 return;
236 } else if (!pos_count) {
237 *back = std::move(polygon);
238 return;
239 }
240
241 // Handle splitting case.
242 size_t front_begin;
243 size_t back_begin;
244 size_t pre_front_begin;
245 size_t pre_back_begin;
246
247 // Find the first vertex that is part of the front split polygon.
248 front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
249 [](float val) { return val > 0.0; }) -
250 vertex_distance.begin();
251 while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0)
252 front_begin = pre_front_begin;
253
254 // Find the first vertex that is part of the back split polygon.
255 back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(),
256 [](float val) { return val < 0.0; }) -
257 vertex_distance.begin();
258 while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0)
259 back_begin = pre_back_begin;
260
261 DCHECK(vertex_distance[front_begin] > 0.0);
262 DCHECK(vertex_distance[pre_front_begin] <= 0.0);
263 DCHECK(vertex_distance[back_begin] < 0.0);
264 DCHECK(vertex_distance[pre_back_begin] >= 0.0);
265
266 gfx::Point3F pre_pos_intersection;
267 gfx::Point3F pre_neg_intersection;
268
269 // Compute the intersection points. N.B.: If the "pre" vertex is on
270 // the thick plane, then the intersection will be at the same point, because
271 // we set vertex_distance to 0 in this case.
272 PointInterpolate(
273 polygon->points_[pre_front_begin], polygon->points_[front_begin],
274 -vertex_distance[pre_front_begin] /
275 gfx::DotProduct(normal_, polygon->points_[front_begin] -
276 polygon->points_[pre_front_begin]),
277 &pre_pos_intersection);
278 PointInterpolate(
279 polygon->points_[pre_back_begin], polygon->points_[back_begin],
280 -vertex_distance[pre_back_begin] /
281 gfx::DotProduct(normal_, polygon->points_[back_begin] -
282 polygon->points_[pre_back_begin]),
283 &pre_neg_intersection);
284
285 // Build the front and back polygons.
286 std::vector<gfx::Point3F> out_points;
287
288 out_points.push_back(pre_pos_intersection);
289 for (size_t index = front_begin; index != back_begin; index = next(index)) {
290 out_points.push_back(polygon->points_[index]);
291 }
292 if (out_points.back() != pre_neg_intersection) {
293 out_points.push_back(pre_neg_intersection);
294 }
295 *front =
296 std::make_unique<DrawPolygon>(polygon->original_ref_, out_points,
297 polygon->normal_, polygon->order_index_);
298
299 out_points.clear();
300
301 out_points.push_back(pre_neg_intersection);
302 for (size_t index = back_begin; index != front_begin; index = next(index)) {
303 out_points.push_back(polygon->points_[index]);
304 }
305 if (out_points.back() != pre_pos_intersection) {
306 out_points.push_back(pre_pos_intersection);
307 }
308 *back =
309 std::make_unique<DrawPolygon>(polygon->original_ref_, out_points,
310 polygon->normal_, polygon->order_index_);
311
312 DCHECK_GE((*front)->points().size(), 3u);
313 DCHECK_GE((*back)->points().size(), 3u);
314 }
315
316 // This algorithm takes the first vertex in the polygon and uses that as a
317 // pivot point to fan out and create quads from the rest of the vertices.
318 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate
319 // offset+1 and offset+2 respectively.
320 // After the first quad is created, the first vertex in the next quad is the
321 // same as all the rest, the pivot point. The second vertex in the next quad is
322 // the old |op2|, the last vertex added to the previous quad. This continues
323 // until all points are exhausted.
324 // The special case here is where there are only 3 points remaining, in which
325 // case we use the same values for vertex 3 and 4 to make a degenerate quad
326 // that represents a triangle.
ToQuads2D(std::vector<gfx::QuadF> * quads) const327 void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const {
328 if (points_.size() <= 2)
329 return;
330
331 gfx::PointF first(points_[0].x(), points_[0].y());
332 size_t offset = 1;
333 while (offset < points_.size() - 1) {
334 size_t op1 = offset + 1;
335 size_t op2 = offset + 2;
336 if (op2 >= points_.size()) {
337 // It's going to be a degenerate triangle.
338 op2 = op1;
339 }
340 quads->push_back(
341 gfx::QuadF(first, gfx::PointF(points_[offset].x(), points_[offset].y()),
342 gfx::PointF(points_[op1].x(), points_[op1].y()),
343 gfx::PointF(points_[op2].x(), points_[op2].y())));
344 offset = op2;
345 }
346 }
347
348 } // namespace viz
349