OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2013 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 | |
11 namespace { | |
12 // This allows for some imperfection in the normal comparison when checking if | |
13 // two pieces of geometry are coplanar. | |
14 const float coplanar_dot_epsilon = 0.99f; | |
15 } // namespace | |
16 | |
17 namespace cc { | |
18 | |
19 DrawPolygon::DrawPolygon() { | |
20 } | |
21 | |
22 static float SignedArea(const DrawPolygon& polygon) { | |
23 gfx::Vector3dF total; | |
24 for (unsigned int i = 0; i < polygon.points.size(); i++) { | |
25 unsigned int j = (i + 1) % polygon.points.size(); | |
26 gfx::Vector3dF cross_prod = | |
27 gfx::CrossProduct(gfx::Vector3dF(polygon.points[i].x(), | |
28 polygon.points[i].y(), | |
29 polygon.points[i].z()), | |
30 gfx::Vector3dF(polygon.points[j].x(), | |
31 polygon.points[j].y(), | |
32 polygon.points[j].z())); | |
33 total = total + cross_prod; | |
34 } | |
35 return 0.5f * std::abs(gfx::DotProduct(total, polygon.normal)); | |
Ian Vollick
2014/07/22 16:12:15
The fns in DrawPolygon are probably the most invol
troyhildebrandt
2014/07/23 21:43:56
Changed and all part of the DrawPolygon patch sepa
| |
36 } | |
37 | |
38 float Area(const DrawPolygon& polygon) { | |
39 return std::abs(SignedArea(polygon)); | |
40 } | |
41 | |
42 DrawPolygon::DrawPolygon(DrawQuad* original, | |
43 gfx::Point3F* in_points, | |
44 int num_vertices_in_polygon, | |
45 int draw_order_index) | |
46 : order_index(draw_order_index), original_ref(original) { | |
47 for (int i = 0; i < num_vertices_in_polygon; i++) { | |
48 points.push_back(in_points[i]); | |
49 } | |
50 | |
51 if (num_vertices_in_polygon > 2) { | |
52 gfx::Vector3dF c12 = in_points[1] - in_points[0]; | |
53 gfx::Vector3dF c13 = in_points[2] - in_points[0]; | |
54 normal = gfx::CrossProduct(c12, c13); | |
55 normal.Scale(1.0f / normal.Length()); | |
56 } | |
57 area = Area(*this); | |
58 } | |
59 | |
60 DrawPolygon::DrawPolygon(const DrawPolygon& other) { | |
61 CopyFrom(other); | |
62 } | |
63 | |
64 DrawPolygon::~DrawPolygon() { | |
65 } | |
66 | |
67 DrawPolygon& DrawPolygon::operator=(const DrawPolygon& rhs) { | |
68 CopyFrom(rhs); | |
69 return *this; | |
70 } | |
71 | |
72 void DrawPolygon::CopyFrom(const DrawPolygon& other) { | |
73 order_index = other.order_index; | |
74 original_ref = other.original_ref; | |
75 points.reserve(other.points.size()); | |
76 points = other.points; | |
77 normal.set_x(other.normal.x()); | |
78 normal.set_y(other.normal.y()); | |
79 normal.set_z(other.normal.z()); | |
80 area = other.area; | |
81 } | |
82 | |
83 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { | |
84 return gfx::DotProduct(point - points[0], normal); | |
85 } | |
86 | |
87 // Checks whether or not shape a lies on the front or back side of b, or | |
88 // whether they should be considered coplanar. If on the back side, we | |
89 // say ABeforeB because it should be drawn in that order. | |
90 // Assumes that layers are split and there are no intersecting planes. | |
91 BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a, | |
92 const DrawPolygon& b, | |
93 float z_threshold) { | |
94 // Right away let's check if they're coplanar | |
95 double dot = gfx::DotProduct(a.normal, b.normal); | |
96 float sign; | |
97 bool normal_match = false; | |
98 // This check assumes that the normals are normalized. | |
99 if (std::abs(dot) >= coplanar_dot_epsilon) { | |
100 normal_match = true; | |
101 // The normals are matching enough that we only have to test one point. | |
102 sign = gfx::DotProduct(a.points[0] - b.points[0], b.normal); | |
103 // Is it on either side of the splitter? | |
104 if (sign < -z_threshold) { | |
105 return BSP_BACK; | |
106 } | |
107 | |
108 if (sign > z_threshold) { | |
109 return BSP_FRONT; | |
110 } | |
111 | |
112 // No it wasn't, so the sign of the dot product of the normals | |
113 // along with document order determines which side it goes on. | |
114 if (dot >= 0.0f) { | |
115 if (a.order_index < b.order_index) { | |
116 return BSP_COPLANAR_FRONT; | |
117 } | |
118 return BSP_COPLANAR_BACK; | |
119 } | |
120 | |
121 if (a.order_index < b.order_index) { | |
122 return BSP_COPLANAR_BACK; | |
123 } | |
124 return BSP_COPLANAR_FRONT; | |
125 } | |
126 | |
127 unsigned int pos_count = 0; | |
128 unsigned int neg_count = 0; | |
129 for (unsigned int i = 0; i < a.points.size(); i++) { | |
130 if (!normal_match || (normal_match && i > 0)) { | |
131 sign = gfx::DotProduct(a.points[i] - b.points[0], b.normal); | |
132 } | |
133 | |
134 if (sign < -z_threshold) { | |
135 ++neg_count; | |
136 } else if (sign > z_threshold) { | |
137 ++pos_count; | |
138 } | |
139 | |
140 if (pos_count && neg_count) { | |
141 return BSP_SPLIT; | |
142 } | |
143 } | |
144 | |
145 if (pos_count) { | |
146 return BSP_FRONT; | |
147 } | |
148 return BSP_BACK; | |
149 } | |
150 | |
151 static bool LineIntersectPlane(const gfx::Point3F& line_start, | |
152 const gfx::Point3F& line_end, | |
153 const gfx::Point3F& plane_origin, | |
154 const gfx::Vector3dF& plane_normal, | |
155 gfx::Point3F* intersection, | |
156 float distance_threshold) { | |
157 gfx::Vector3dF vec1 = plane_origin - line_start; | |
158 gfx::Vector3dF vec2 = plane_origin - line_end; | |
159 | |
160 double start_distance = gfx::DotProduct(vec1, plane_normal); | |
161 double end_distance = gfx::DotProduct(vec2, plane_normal); | |
162 | |
163 // The case where one vertex lies on the thick-plane and the other | |
164 // is outside of it. | |
165 if (std::abs(start_distance) < distance_threshold && | |
166 std::abs(end_distance) > distance_threshold) { | |
167 intersection->SetPoint(line_start.x(), line_start.y(), line_start.z()); | |
168 return true; | |
169 } | |
170 | |
171 // This is the case where we clearly cross the thick-plane. | |
172 if ((start_distance > distance_threshold && | |
173 end_distance < -distance_threshold) || | |
174 (start_distance < -distance_threshold && | |
175 end_distance > distance_threshold)) { | |
176 gfx::Vector3dF v = line_end - line_start; | |
177 | |
178 v.Scale(1.f / v.Length()); | |
179 double projected_length = gfx::DotProduct(v, plane_normal); | |
180 if (!projected_length) | |
181 return false; | |
182 | |
183 double scale = start_distance / projected_length; | |
184 intersection->SetPoint(line_start.x() + (v.x() * scale), | |
185 line_start.y() + (v.y() * scale), | |
186 line_start.z() + (v.z() * scale)); | |
187 | |
188 return true; | |
189 } | |
190 return false; | |
191 } | |
192 | |
193 bool DrawPolygon::ApplyTransform(const gfx::Transform& transform) { | |
194 bool clipped = false; | |
195 for (unsigned int i = 0; i < points.size(); i++) { | |
196 points[i] = MathUtil::MapPoint(transform, points[i], &clipped); | |
197 } | |
198 return !clipped; | |
199 } | |
200 | |
201 bool DrawPolygon::Split(const DrawPolygon& splitter, | |
202 double plane_threshold, | |
203 scoped_ptr<DrawPolygon>* front, | |
204 scoped_ptr<DrawPolygon>* back) { | |
205 gfx::Point3F intersections[2]; | |
206 std::vector<gfx::Point3F> out_points[2]; | |
207 int vertex_before[2]; | |
208 int points_size = points.size(); | |
209 int current_intersection = 0; | |
210 | |
211 int current_vertex = 0; | |
212 while (current_intersection < 2) { | |
213 if (current_intersection > 0 && | |
214 vertex_before[0] == (current_vertex % points_size)) { | |
215 continue; | |
216 } | |
217 | |
218 if (LineIntersectPlane(points[(current_vertex % points_size)], | |
219 points[(current_vertex + 1) % points_size], | |
220 splitter.points[0], | |
221 splitter.normal, | |
222 &intersections[current_intersection], | |
223 plane_threshold)) { | |
224 vertex_before[current_intersection] = current_vertex % points_size; | |
225 current_intersection++; | |
226 // We found both intersection points so we're done already. | |
227 if (current_intersection == 2) { | |
228 break; | |
229 } | |
230 } | |
231 ++current_vertex; | |
232 // We've gone around one whole time, leave early. | |
233 if (current_vertex > points_size) { | |
234 break; | |
235 } | |
236 } | |
237 if (current_intersection < 2) { | |
238 return false; | |
239 } | |
240 | |
241 // Since we found both the intersection points, we can begin building the | |
242 // vertex set for both our new polygons. | |
243 int start1 = (vertex_before[0] + 1) % points_size; | |
244 int start2 = (vertex_before[1] + 1) % points_size; | |
245 int points_remaining = points_size; | |
246 | |
247 // First polygon. | |
248 out_points[0].push_back(intersections[0]); | |
249 for (int i = start1; i <= vertex_before[1]; i++) { | |
250 out_points[0].push_back(points[i]); | |
251 --points_remaining; | |
252 } | |
253 out_points[0].push_back(intersections[1]); | |
254 | |
255 // Second polygon. | |
256 out_points[1].push_back(intersections[1]); | |
257 int index = start2; | |
258 for (int i = 0; i < points_remaining; i++) { | |
259 out_points[1].push_back(points[index % points_size]); | |
260 ++index; | |
261 } | |
262 out_points[1].push_back(intersections[0]); | |
263 | |
264 // Give both polygons the original splitting polygon's ID, so that they'll | |
265 // still be sorted properly in co-planar instances. | |
266 // Send false as last parameter for is_original because they're split. | |
267 scoped_ptr<DrawPolygon> poly1(new DrawPolygon(original_ref, | |
268 &(out_points[0][0]), | |
269 out_points[0].size(), | |
270 this->order_index)); | |
271 scoped_ptr<DrawPolygon> poly2(new DrawPolygon(original_ref, | |
272 &(out_points[1][0]), | |
273 out_points[1].size(), | |
274 this->order_index)); | |
275 | |
276 if (SideCompare(*poly1, splitter, plane_threshold) == BSP_FRONT) { | |
277 *front = poly1.Pass(); | |
278 *back = poly2.Pass(); | |
279 } else { | |
280 *front = poly2.Pass(); | |
281 *back = poly1.Pass(); | |
282 } | |
283 return true; | |
284 } | |
285 | |
286 void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const { | |
287 if (points.size() == 0) | |
288 return; | |
289 | |
290 // op1 = offset plus 1, op2 = offset plus 2. | |
291 gfx::PointF first(points[0].x(), points[0].y()); | |
292 unsigned int offset = 1; | |
293 while (offset < points.size() - 1) { | |
294 unsigned int op1 = offset + 1; | |
295 unsigned int op2 = offset + 2; | |
296 if (op2 >= points.size()) { | |
297 // It's going to be a degenerate triangle. | |
298 op2 = op1; | |
299 } | |
300 quads->push_back( | |
301 gfx::QuadF(first, | |
302 gfx::PointF(points[offset].x(), points[offset].y()), | |
303 gfx::PointF(points[op1].x(), points[op1].y()), | |
304 gfx::PointF(points[op2].x(), points[op2].y()))); | |
305 offset = op2; | |
306 } | |
307 } | |
308 | |
309 bool DrawPolygon::GetInverseTransform(gfx::Transform* transform) const { | |
310 return original_ref->quadTransform().GetInverse(transform); | |
311 } | |
312 | |
313 } // namespace cc | |
OLD | NEW |