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.
5 #include "cc/quads/draw_polygon.h"
9 #include "cc/output/bsp_compare_result.h"
10 #include "cc/quads/draw_quad.h"
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
28 static const float split_threshold
= 0.5f
;
33 gfx::Vector3dF
DrawPolygon::default_normal
= gfx::Vector3dF(0.0f
, 0.0f
, -1.0f
);
35 DrawPolygon::DrawPolygon() {
38 DrawPolygon::DrawPolygon(DrawQuad
* original
,
39 const std::vector
<gfx::Point3F
>& in_points
,
40 const gfx::Vector3dF
& normal
,
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
]);
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
,
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
);
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
]);
72 ApplyTransformToNormal(transform
);
75 DrawPolygon::~DrawPolygon() {
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
);
90 float DrawPolygon::SignedPointDistance(const gfx::Point3F
& point
) const {
91 return gfx::DotProduct(point
- points_
[0], normal_
);
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_
);
103 bool normal_match
= false;
104 // This check assumes that the normals are normalized.
105 if (std::abs(dot
) >= 1.0f
- coplanar_dot_epsilon
) {
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
) {
114 if (sign
> compare_threshold
) {
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.
121 if (a
.order_index_
< b
.order_index_
) {
122 return BSP_COPLANAR_FRONT
;
124 return BSP_COPLANAR_BACK
;
127 if (a
.order_index_
< b
.order_index_
) {
128 return BSP_COPLANAR_BACK
;
130 return BSP_COPLANAR_FRONT
;
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_
);
140 if (sign
< -compare_threshold
) {
142 } else if (sign
> compare_threshold
) {
146 if (pos_count
&& neg_count
) {
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
;
166 double start_distance
= gfx::DotProduct(start_to_origin_vector
, plane_normal
);
167 double end_distance
= gfx::DotProduct(end_to_origin_vector
, plane_normal
);
169 // The case where one vertex lies on the thick-plane and the other
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());
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
;
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
));
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
);
207 inverse_transform
.Transpose();
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
);
219 void DrawPolygon::ApplyTransform(const gfx::Transform
& transform
) {
220 for (size_t i
= 0; i
< points_
.size(); i
++) {
221 transform
.TransformPoint(&points_
[i
]);
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
);
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
);
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
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;
256 size_t current_vertex
= 0;
257 // We will only have two intersection points because we assume all polygons
259 while (current_intersection
< 2) {
260 if (LineIntersectPlane(points_
[(current_vertex
% points_size
)],
261 points_
[(current_vertex
+ 1) % points_size
],
264 &intersections
[current_intersection
],
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) {
273 if (current_vertex
++ > points_size
) {
277 DCHECK_EQ(current_intersection
, static_cast<size_t>(2));
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
;
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
]);
291 out_points
[0].push_back(intersections
[1]);
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
]);
300 out_points
[1].push_back(intersections
[0]);
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_
));
309 if (SideCompare(*poly1
, splitter
) == BSP_FRONT
) {
310 *front
= poly1
.Pass();
311 *back
= poly2
.Pass();
313 *front
= poly2
.Pass();
314 *back
= poly1
.Pass();
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)
334 gfx::PointF
first(points_
[0].x(), points_
[0].y());
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.
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())));