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

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: Removed some forgotten debug output 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/output/bsp_walk_action.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 2014 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 static const float coplanar_dot_epsilon = 0.99f;
15 // This threshold controls how "thick" a plane is. If a point's distance is
16 // <= compare_threshold, then it is considered on the plane. Only when this
17 // boundary is crossed do we consider doing splitting.
18 static const float compare_threshold = 1.0f;
19 static const float split_threshold = 0.5f;
20 } // namespace
21
22 namespace cc {
23
24 DrawPolygon::DrawPolygon() {
25 }
26
27 DrawPolygon::DrawPolygon(DrawQuad* original,
28 const std::vector<gfx::Point3F>& in_points,
29 int draw_order_index)
30 : order_index_(draw_order_index), original_ref_(original) {
31 for (unsigned int i = 0; i < in_points.size(); i++) {
32 points_.push_back(in_points[i]);
33 }
34 normal_ = gfx::Vector3dF(0.0f, 0.0f, 1.0f);
35 }
36
37 DrawPolygon::~DrawPolygon() {
38 }
39
40 void DrawPolygon::SetNormal(const gfx::Vector3dF& normal) {
41 normal_ = normal;
42 }
43
44 scoped_ptr<DrawPolygon> DrawPolygon::CreateCopy() {
45 DrawPolygon* new_polygon = new DrawPolygon();
46 new_polygon->order_index_ = order_index_;
47 new_polygon->original_ref_ = original_ref_;
48 new_polygon->points_.reserve(points_.size());
49 new_polygon->points_ = points_;
50 new_polygon->normal_.set_x(normal_.x());
51 new_polygon->normal_.set_y(normal_.y());
52 new_polygon->normal_.set_z(normal_.z());
53 return scoped_ptr<DrawPolygon>(new_polygon);
54 }
55
56 float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const {
57 return gfx::DotProduct(point - points_[0], normal_);
58 }
59
60 // Checks whether or not shape a lies on the front or back side of b, or
61 // whether they should be considered coplanar. If on the back side, we
62 // say ABeforeB because it should be drawn in that order.
63 // Assumes that layers are split and there are no intersecting planes.
64 BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a,
65 const DrawPolygon& b) {
66 // Right away let's check if they're coplanar
67 double dot = gfx::DotProduct(a.normal_, b.normal_);
68 float sign;
69 bool normal_match = false;
70 // This check assumes that the normals are normalized.
71 if (std::abs(dot) >= coplanar_dot_epsilon) {
72 normal_match = true;
73 // The normals are matching enough that we only have to test one point.
74 sign = gfx::DotProduct(a.points_[0] - b.points_[0], b.normal_);
75 // Is it on either side of the splitter?
76 if (sign < -compare_threshold) {
77 return BSP_BACK;
78 }
79
80 if (sign > compare_threshold) {
81 return BSP_FRONT;
82 }
83
84 // No it wasn't, so the sign of the dot product of the normals
85 // along with document order determines which side it goes on.
86 if (dot >= 0.0f) {
87 if (a.order_index_ < b.order_index_) {
88 return BSP_COPLANAR_FRONT;
89 }
90 return BSP_COPLANAR_BACK;
91 }
92
93 if (a.order_index_ < b.order_index_) {
94 return BSP_COPLANAR_BACK;
95 }
96 return BSP_COPLANAR_FRONT;
97 }
98
99 unsigned int pos_count = 0;
100 unsigned int neg_count = 0;
101 for (unsigned int i = 0; i < a.points_.size(); i++) {
102 if (!normal_match || (normal_match && i > 0)) {
103 sign = gfx::DotProduct(a.points_[i] - b.points_[0], b.normal_);
104 }
105
106 if (sign < -compare_threshold) {
107 ++neg_count;
108 } else if (sign > compare_threshold) {
109 ++pos_count;
110 }
111
112 if (pos_count && neg_count) {
113 return BSP_SPLIT;
114 }
115 }
116
117 if (pos_count) {
118 return BSP_FRONT;
119 }
120 return BSP_BACK;
121 }
122
123 static bool LineIntersectPlane(const gfx::Point3F& line_start,
124 const gfx::Point3F& line_end,
125 const gfx::Point3F& plane_origin,
126 const gfx::Vector3dF& plane_normal,
127 gfx::Point3F* intersection,
128 float distance_threshold) {
129 gfx::Vector3dF start_to_origin_vector = plane_origin - line_start;
130 gfx::Vector3dF end_to_origin_vector = plane_origin - line_end;
131
132 double start_distance = gfx::DotProduct(start_to_origin_vector, plane_normal);
133 double end_distance = gfx::DotProduct(end_to_origin_vector, plane_normal);
134
135 // The case where one vertex lies on the thick-plane and the other
136 // is outside of it.
137 if (std::abs(start_distance) < distance_threshold &&
138 std::abs(end_distance) > distance_threshold) {
139 intersection->SetPoint(line_start.x(), line_start.y(), line_start.z());
140 return true;
141 }
142
143 // This is the case where we clearly cross the thick-plane.
144 if ((start_distance > distance_threshold &&
145 end_distance < -distance_threshold) ||
146 (start_distance < -distance_threshold &&
147 end_distance > distance_threshold)) {
148 // By getting the dot product of the line segment normalized vs. the plane's
149 // normal, we get a value that approaches zero as the angle of the
150 // intersecting line becomes parallel with the plane.
151 // When the line segment vector is equal to the plane's normal, we have the
152 // most direct path to the plane, and the dot product is 1. In this case,
153 // the calculation below is just |start_distance| / 1, which is the trivial
154 // case because the line takes the most direct path to intersect with the
155 // plane. |start_distance| is already the shortest straight line path
156 // distance to the plane.
157 // However, as the vector that represents the direction of the line segment
158 // indicates that it is becoming more parallel with the surface of the plane
159 // and the dot product approaches 0, the path to intersection becomes much
160 // longer, and the division of |start_distance| by < 1 gives us the true
161 // distance of the start point to the plane following the vector of the line
162 // segment.
163 gfx::Vector3dF v = line_end - line_start;
164 v.Scale(1.f / v.Length());
165 double projected_length = gfx::DotProduct(v, plane_normal);
166
167 // The only way this will ever be true is the case where the line runs
168 // parallel to the surface of the plane and would never contact it, and
169 // this would result in a divide by zero below.
170 if (!projected_length) {
171 return false;
172 }
173
174 double scale = start_distance / projected_length;
175 intersection->SetPoint(line_start.x() + (v.x() * scale),
176 line_start.y() + (v.y() * scale),
177 line_start.z() + (v.z() * scale));
178
179 return true;
180 }
181 return false;
182 }
183
184 bool DrawPolygon::Split(const DrawPolygon& splitter,
185 scoped_ptr<DrawPolygon>* front,
186 scoped_ptr<DrawPolygon>* back) {
187 gfx::Point3F intersections[2];
188 std::vector<gfx::Point3F> out_points[2];
189 // vertex_before stores the index of the vertex before its matching
190 // intersection.
191 // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane
192 // which resulted in the line/plane intersection giving us intersections[0].
193 unsigned int vertex_before[2];
194 unsigned int points_size = points_.size();
195 unsigned int current_intersection = 0;
196
197 unsigned int current_vertex = 0;
198 while (current_intersection < 2) {
199 if (LineIntersectPlane(points_[(current_vertex % points_size)],
200 points_[(current_vertex + 1) % points_size],
201 splitter.points_[0],
202 splitter.normal_,
203 &intersections[current_intersection],
204 split_threshold)) {
205 vertex_before[current_intersection] = current_vertex % points_size;
206 current_intersection++;
207 // We found both intersection points so we're done already.
208 if (current_intersection == 2) {
209 break;
210 }
211 }
212 if (current_vertex++ > points_size) {
213 break;
214 }
215 }
216 if (current_intersection < 2) {
217 return false;
218 }
219
220 // Since we found both the intersection points, we can begin building the
221 // vertex set for both our new polygons.
222 unsigned int start1 = (vertex_before[0] + 1) % points_size;
223 unsigned int start2 = (vertex_before[1] + 1) % points_size;
224 unsigned int points_remaining = points_size;
225
226 // First polygon.
227 out_points[0].push_back(intersections[0]);
228 for (unsigned int i = start1; i <= vertex_before[1]; i++) {
229 out_points[0].push_back(points_[i]);
230 --points_remaining;
231 }
232 out_points[0].push_back(intersections[1]);
233
234 // Second polygon.
235 out_points[1].push_back(intersections[1]);
236 unsigned int index = start2;
237 for (unsigned int i = 0; i < points_remaining; i++) {
238 out_points[1].push_back(points_[index % points_size]);
239 ++index;
240 }
241 out_points[1].push_back(intersections[0]);
242
243 // Give both polygons the original splitting polygon's ID, so that they'll
244 // still be sorted properly in co-planar instances.
245 // Send false as last parameter for is_original because they're split.
246 scoped_ptr<DrawPolygon> poly1(
247 new DrawPolygon(original_ref_, out_points[0], order_index_));
248 scoped_ptr<DrawPolygon> poly2(
249 new DrawPolygon(original_ref_, out_points[1], order_index_));
250
251 poly1->SetNormal(normal_);
252 poly2->SetNormal(normal_);
253
254 if (SideCompare(*poly1, splitter) == BSP_FRONT) {
255 *front = poly1.Pass();
256 *back = poly2.Pass();
257 } else {
258 *front = poly2.Pass();
259 *back = poly1.Pass();
260 }
261 return true;
262 }
263
264 // This algorithm takes the first vertex in the polygon and uses that as a
265 // pivot point to fan out and create quads from the rest of the vertices.
266 // |offset| starts off as the second vertex, and then |op1| and |op2| indicate
267 // offset+1 and offset+2 respectively.
268 // After the first quad is created, the first vertex in the next quad is the
269 // same as all the rest, the pivot point. The second vertex in the next quad is
270 // the old |op2|, the last vertex added to the previous quad. This continues
271 // until all points are exhausted.
272 // The special case here is where there are only 3 points remaining, in which
273 // case we use the same values for vertex 3 and 4 to make a degenerate quad
274 // that represents a triangle.
275 void DrawPolygon::ToQuads2D(std::vector<gfx::QuadF>* quads) const {
276 if (points_.size() <= 2)
277 return;
278
279 gfx::PointF first(points_[0].x(), points_[0].y());
280 unsigned int offset = 1;
281 while (offset < points_.size() - 1) {
282 unsigned int op1 = offset + 1;
283 unsigned int op2 = offset + 2;
284 if (op2 >= points_.size()) {
285 // It's going to be a degenerate triangle.
286 op2 = op1;
287 }
288 quads->push_back(
289 gfx::QuadF(first,
290 gfx::PointF(points_[offset].x(), points_[offset].y()),
291 gfx::PointF(points_[op1].x(), points_[op1].y()),
292 gfx::PointF(points_[op2].x(), points_[op2].y())));
293 offset = op2;
294 }
295 }
296
297 bool DrawPolygon::GetInverseTransform(gfx::Transform* transform) const {
298 return original_ref_->quadTransform().GetInverse(transform);
299 }
300
301 } // namespace cc
OLDNEW
« cc/output/bsp_walk_action.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