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