Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(119)

Side by Side Diff: cc/quads/draw_polygon.cc

Issue 384083002: WIP BSP Tree for 3D Layer Sorting (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« cc/quads/draw_polygon.h ('K') | « cc/quads/draw_polygon.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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
OLDNEW
« cc/quads/draw_polygon.h ('K') | « cc/quads/draw_polygon.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698