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

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