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

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));
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
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