Index: cc/quads/draw_polygon.cc |
diff --git a/cc/quads/draw_polygon.cc b/cc/quads/draw_polygon.cc |
index 770d241570bb06755f9321c7794efbfa0460d0ee..86cb87319426d18f5ee1a1ddc3c6839d994ab289 100644 |
--- a/cc/quads/draw_polygon.cc |
+++ b/cc/quads/draw_polygon.cc |
@@ -8,27 +8,26 @@ |
#include <vector> |
+#include "base/memory/ptr_util.h" |
#include "cc/output/bsp_compare_result.h" |
#include "cc/quads/draw_quad.h" |
namespace { |
// This threshold controls how "thick" a plane is. If a point's distance is |
-// <= |compare_threshold|, then it is considered on the plane. Only when this |
-// boundary is crossed do we consider doing splitting. |
-static const float compare_threshold = 0.1f; |
-// |split_threshold| is lower in this case because we want the points created |
-// during splitting to be well within the range of |compare_threshold| for |
-// comparison purposes. The splitting operation will produce intersection points |
-// that fit within a tighter distance to the splitting plane as a result of this |
-// value. By using a value >= |compare_threshold| we run the risk of creating |
-// points that SHOULD be intersecting the "thick plane", but actually fail to |
-// test positively for it because |split_threshold| allowed them to be outside |
-// this range. |
-// This is really supposd to be compare_threshold / 2.0f, but that would |
-// create another static initializer. |
+// <= |split_threshold|, then it is considered on the plane for the purpose of |
+// polygon splitting. |
static const float split_threshold = 0.05f; |
static const float normalized_threshold = 0.001f; |
+ |
+void PointInterpolate(const gfx::Point3F& from, |
+ const gfx::Point3F& to, |
+ double delta, |
+ gfx::Point3F* out) { |
+ out->SetPoint(from.x() + (to.x() - from.x()) * delta, |
+ from.y() + (to.y() - from.y()) * delta, |
+ from.z() + (to.z() - from.z()) * delta); |
+} |
} // namespace |
namespace cc { |
@@ -132,100 +131,6 @@ float DrawPolygon::SignedPointDistance(const gfx::Point3F& point) const { |
return gfx::DotProduct(point - points_[0], normal_); |
} |
-// Checks whether or not shape a lies on the front or back side of b, or |
-// whether they should be considered coplanar. If on the back side, we |
-// say A_BEFORE_B because it should be drawn in that order. |
-// Assumes that layers are split and there are no intersecting planes. |
-BspCompareResult DrawPolygon::SideCompare(const DrawPolygon& a, |
- const DrawPolygon& b) { |
- // Let's make sure that this is normalized. Without this SignedPointDistance |
- // will not be right, but putting the check in there will validate it |
- // redundantly for each point. |
- DCHECK_GE(normalized_threshold, std::abs(b.normal_.LengthSquared() - 1.0f)); |
- |
- int pos_count = 0; |
- int neg_count = 0; |
- for (size_t i = 0; i < a.points_.size(); i++) { |
- float sign = b.SignedPointDistance(a.points_[i]); |
- |
- if (sign < -compare_threshold) { |
- ++neg_count; |
- } else if (sign > compare_threshold) { |
- ++pos_count; |
- } |
- |
- if (pos_count && neg_count) { |
- return BSP_SPLIT; |
- } |
- } |
- |
- if (pos_count) { |
- return BSP_FRONT; |
- } |
- if (neg_count) { |
- return BSP_BACK; |
- } |
- |
- double dot = gfx::DotProduct(a.normal_, b.normal_); |
- if ((dot >= 0.0f && a.order_index_ >= b.order_index_) || |
- (dot <= 0.0f && a.order_index_ <= b.order_index_)) { |
- // The sign of the dot product of the normals along with document order |
- // determine which side it goes on, the vertices are ambiguous. |
- return BSP_COPLANAR_BACK; |
- } |
- |
- return BSP_COPLANAR_FRONT; |
-} |
- |
-static bool LineIntersectPlane(const gfx::Point3F& line_start, |
- const gfx::Point3F& line_end, |
- const gfx::Point3F& plane_origin, |
- const gfx::Vector3dF& plane_normal, |
- gfx::Point3F* intersection, |
- float distance_threshold) { |
- const gfx::Vector3dF line_start_vec(line_start.x(), line_start.y(), |
- line_start.z()); |
- const gfx::Vector3dF line_end_vec(line_end.x(), line_end.y(), line_end.z()); |
- const gfx::Vector3dF plane_origin_vec(plane_origin.x(), plane_origin.y(), |
- plane_origin.z()); |
- |
- double plane_d = -gfx::DotProduct(plane_origin_vec, plane_normal); |
- |
- double end_distance = gfx::DotProduct(line_end_vec, plane_normal) + plane_d; |
- if (std::abs(end_distance) <= distance_threshold) { |
- // No intersection if |line_end| is within |distance_threshold| of plane. |
- return false; |
- } |
- |
- double start_distance = |
- gfx::DotProduct(line_start_vec, plane_normal) + plane_d; |
- if (std::abs(start_distance) <= distance_threshold) { |
- // Intersection at |line_start| if |line_start| is within |
- // |distance_threshold| of plane. |
- intersection->SetPoint(line_start.x(), line_start.y(), line_start.z()); |
- return true; |
- } |
- |
- // If signs differ, we cross the plane. |
- if (start_distance * end_distance < 0.0) { |
- // Plane: P . N + d = 0 [ d = -(plane_normal . plane_origin) ] |
- // Ray: P = P0 + Pd * t [ P0 = line_start, Pd = line_end - line_start ] |
- // Substituting: |
- // (P0 + Pd * t) . N + d = 0 |
- // P0 . N + t * Pd . N + d = 0 |
- // t = -(P0 . N + d) / Pd . N |
- |
- gfx::Vector3dF line_delta = line_end - line_start; |
- double t = -start_distance / gfx::DotProduct(plane_normal, line_delta); |
- intersection->SetPoint(line_start.x() + line_delta.x() * t, |
- line_start.y() + line_delta.y() * t, |
- line_start.z() + line_delta.z() * t); |
- |
- return true; |
- } |
- return false; |
-} |
- |
// This function is separate from ApplyTransform because it is often unnecessary |
// to transform the normal with the rest of the polygon. |
// When drawing these polygons, it is necessary to move them back into layer |
@@ -275,84 +180,138 @@ void DrawPolygon::TransformToLayerSpace( |
normal_ = gfx::Vector3dF(0.0f, 0.0f, -1.0f); |
} |
-bool DrawPolygon::Split(const DrawPolygon& splitter, |
- std::unique_ptr<DrawPolygon>* front, |
- std::unique_ptr<DrawPolygon>* back) { |
- gfx::Point3F intersections[2]; |
- std::vector<gfx::Point3F> out_points[2]; |
- // vertex_before stores the index of the vertex before its matching |
- // intersection. |
- // i.e. vertex_before[0] stores the vertex we saw before we crossed the plane |
- // which resulted in the line/plane intersection giving us intersections[0]. |
- size_t vertex_before[2]; |
- size_t points_size = points_.size(); |
- size_t current_intersection = 0; |
- |
- size_t current_vertex = 0; |
- // We will only have two intersection points because we assume all polygons |
- // are convex. |
- while (current_intersection < 2) { |
- if (LineIntersectPlane(points_[(current_vertex % points_size)], |
- points_[(current_vertex + 1) % points_size], |
- splitter.points_[0], |
- splitter.normal_, |
- &intersections[current_intersection], |
- split_threshold)) { |
- vertex_before[current_intersection] = current_vertex % points_size; |
- current_intersection++; |
- // We found both intersection points so we're done already. |
- if (current_intersection == 2) { |
- break; |
- } |
- } |
- if (current_vertex++ > (points_size)) { |
- break; |
+// Split |polygon| based upon |this|, leaving the results in |front| and |back|. |
+// If |polygon| is not split by |this|, then move it to either |front| or |back| |
+// depending on its orientation relative to |this|. Sets |is_coplanar| to true |
+// if |polygon| is actually coplanar with |this| (in which case whether it is |
+// front facing or back facing is determined by the dot products of normals, and |
+// document order). |
+void DrawPolygon::SplitPolygon(std::unique_ptr<DrawPolygon> polygon, |
+ std::unique_ptr<DrawPolygon>* front, |
+ std::unique_ptr<DrawPolygon>* back, |
+ bool* is_coplanar) const { |
+ DCHECK_GE(normalized_threshold, std::abs(normal_.LengthSquared() - 1.0f)); |
+ |
+ const size_t num_points = polygon->points_.size(); |
+ const auto next = [num_points](size_t i) { return (i + 1) % num_points; }; |
+ const auto prev = [num_points](size_t i) { |
+ return (i + num_points - 1) % num_points; |
+ }; |
+ |
+ std::vector<float> vertex_distance; |
+ size_t pos_count = 0; |
+ size_t neg_count = 0; |
+ |
+ // Compute plane distances for each vertex of polygon. |
+ vertex_distance.resize(num_points); |
+ for (size_t i = 0; i < num_points; i++) { |
+ vertex_distance[i] = SignedPointDistance(polygon->points_[i]); |
+ if (vertex_distance[i] < -split_threshold) { |
+ ++neg_count; |
+ } else if (vertex_distance[i] > split_threshold) { |
+ ++pos_count; |
+ } else { |
+ vertex_distance[i] = 0.0; |
} |
} |
- DCHECK_EQ(current_intersection, static_cast<size_t>(2)); |
- |
- // Since we found both the intersection points, we can begin building the |
- // vertex set for both our new polygons. |
- size_t start1 = (vertex_before[0] + 1) % points_size; |
- size_t start2 = (vertex_before[1] + 1) % points_size; |
- size_t points_remaining = points_size; |
- |
- // First polygon. |
- out_points[0].push_back(intersections[0]); |
- DCHECK_GE(vertex_before[1], start1); |
- for (size_t i = start1; i <= vertex_before[1]; i++) { |
- out_points[0].push_back(points_[i]); |
- --points_remaining; |
- } |
- out_points[0].push_back(intersections[1]); |
- |
- // Second polygon. |
- out_points[1].push_back(intersections[1]); |
- size_t index = start2; |
- for (size_t i = 0; i < points_remaining; i++) { |
- out_points[1].push_back(points_[index % points_size]); |
- ++index; |
+ |
+ // Handle non-splitting cases. |
+ if (!pos_count && !neg_count) { |
+ double dot = gfx::DotProduct(normal_, polygon->normal_); |
+ if ((dot >= 0.0f && polygon->order_index_ >= order_index_) || |
+ (dot <= 0.0f && polygon->order_index_ <= order_index_)) { |
+ *back = std::move(polygon); |
+ } else { |
+ *front = std::move(polygon); |
+ } |
+ *is_coplanar = true; |
+ return; |
} |
- out_points[1].push_back(intersections[0]); |
- |
- // Give both polygons the original splitting polygon's ID, so that they'll |
- // still be sorted properly in co-planar instances. |
- std::unique_ptr<DrawPolygon> poly1( |
- new DrawPolygon(original_ref_, out_points[0], normal_, order_index_)); |
- std::unique_ptr<DrawPolygon> poly2( |
- new DrawPolygon(original_ref_, out_points[1], normal_, order_index_)); |
- |
- DCHECK_GE(poly1->points().size(), 3u); |
- DCHECK_GE(poly2->points().size(), 3u); |
- |
- if (SideCompare(*poly1, splitter) == BSP_FRONT) { |
- *front = std::move(poly1); |
- *back = std::move(poly2); |
- } else { |
- *front = std::move(poly2); |
- *back = std::move(poly1); |
+ |
+ *is_coplanar = false; |
+ if (!neg_count) { |
+ *front = std::move(polygon); |
+ return; |
+ } else if (!pos_count) { |
+ *back = std::move(polygon); |
+ return; |
} |
- return true; |
+ |
+ // There should be at most two points that are considered to be on the thick |
+ // plane. If this is not the case, then the polygon is not convex. |
+ DCHECK_LE(num_points - pos_count - neg_count, 2u); |
+ |
+ // Handle splitting case. |
+ size_t front_begin; |
+ size_t back_begin; |
+ size_t pre_front_begin; |
+ size_t pre_back_begin; |
+ |
+ // Find the first vertex that is part of the front split polygon. |
+ front_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), |
+ [](float val) { return val > 0.0; }) - |
+ vertex_distance.begin(); |
+ while (vertex_distance[pre_front_begin = prev(front_begin)] > 0.0) |
+ front_begin = pre_front_begin; |
+ |
+ // Find the first vertex that is part of the back split polygon. |
+ back_begin = std::find_if(vertex_distance.begin(), vertex_distance.end(), |
+ [](float val) { return val < 0.0; }) - |
+ vertex_distance.begin(); |
+ while (vertex_distance[pre_back_begin = prev(back_begin)] < 0.0) |
+ back_begin = pre_back_begin; |
+ |
+ DCHECK(vertex_distance[front_begin] > 0.0); |
+ DCHECK(vertex_distance[pre_front_begin] <= 0.0); |
+ DCHECK(vertex_distance[back_begin] < 0.0); |
+ DCHECK(vertex_distance[pre_back_begin] >= 0.0); |
+ |
+ gfx::Point3F pre_pos_intersection; |
+ gfx::Point3F pre_neg_intersection; |
+ |
+ // Compute the intersection points. N.B.: If the "pre" vertex is on |
+ // the thick plane, then the intersection will be at the same point, because |
+ // we set vertex_distance to 0 in this case. |
+ PointInterpolate( |
+ polygon->points_[pre_front_begin], polygon->points_[front_begin], |
+ -vertex_distance[pre_front_begin] / |
+ gfx::DotProduct(normal_, polygon->points_[front_begin] - |
+ polygon->points_[pre_front_begin]), |
+ &pre_pos_intersection); |
+ PointInterpolate( |
+ polygon->points_[pre_back_begin], polygon->points_[back_begin], |
+ -vertex_distance[pre_back_begin] / |
+ gfx::DotProduct(normal_, polygon->points_[back_begin] - |
+ polygon->points_[pre_back_begin]), |
+ &pre_neg_intersection); |
+ |
+ // Build the front and back polygons. |
+ std::vector<gfx::Point3F> out_points; |
+ |
+ out_points.push_back(pre_pos_intersection); |
+ do { |
+ out_points.push_back(polygon->points_[front_begin]); |
+ front_begin = next(front_begin); |
+ } while (vertex_distance[front_begin] > 0.0); |
+ out_points.push_back(pre_neg_intersection); |
+ *front = |
+ base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, |
+ polygon->normal_, polygon->order_index_); |
+ |
+ out_points.clear(); |
+ |
+ out_points.push_back(pre_neg_intersection); |
+ do { |
+ out_points.push_back(polygon->points_[back_begin]); |
+ back_begin = next(back_begin); |
+ } while (vertex_distance[back_begin] < 0.0); |
+ out_points.push_back(pre_pos_intersection); |
+ *back = |
+ base::MakeUnique<DrawPolygon>(polygon->original_ref_, out_points, |
+ polygon->normal_, polygon->order_index_); |
+ |
+ DCHECK_GE((*front)->points().size(), 3u); |
+ DCHECK_GE((*back)->points().size(), 3u); |
} |
// This algorithm takes the first vertex in the polygon and uses that as a |