| // Copyright 2016 The PDFium Authors |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com |
| |
| #include "core/fxge/cfx_path.h" |
| |
| #include <math.h> |
| |
| #include <algorithm> |
| #include <array> |
| #include <iterator> |
| |
| #include "core/fxcrt/check_op.h" |
| #include "core/fxcrt/fx_system.h" |
| |
| namespace { |
| |
| bool IsRectPreTransform(const std::vector<CFX_Path::Point>& points) { |
| if (points.size() != 5 && points.size() != 4) { |
| return false; |
| } |
| |
| if (points.size() == 5 && points[0].point_ != points[4].point_) { |
| return false; |
| } |
| |
| if (points[0].point_ == points[2].point_ || |
| points[1].point_ == points[3].point_) { |
| return false; |
| } |
| |
| for (size_t i = 1; i < points.size(); ++i) { |
| if (points[i].type_ != CFX_Path::Point::Type::kLine) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| bool XYBothNotEqual(const CFX_PointF& p1, const CFX_PointF& p2) { |
| return p1.x != p2.x && p1.y != p2.y; |
| } |
| |
| bool IsRectImpl(const std::vector<CFX_Path::Point>& points) { |
| if (!IsRectPreTransform(points)) { |
| return false; |
| } |
| |
| for (int i = 1; i < 4; i++) { |
| if (XYBothNotEqual(points[i].point_, points[i - 1].point_)) { |
| return false; |
| } |
| } |
| |
| if (XYBothNotEqual(points[0].point_, points[3].point_)) { |
| return false; |
| } |
| |
| return true; |
| } |
| |
| CFX_FloatRect CreateRectFromPoints(const CFX_PointF& p1, const CFX_PointF& p2) { |
| CFX_FloatRect rect(p1.x, p1.y, p2.x, p2.y); |
| rect.Normalize(); |
| return rect; |
| } |
| |
| bool PathPointsNeedNormalization(const std::vector<CFX_Path::Point>& points) { |
| return points.size() > 5; |
| } |
| |
| std::vector<CFX_Path::Point> GetNormalizedPoints( |
| const std::vector<CFX_Path::Point>& points) { |
| DCHECK(PathPointsNeedNormalization(points)); |
| |
| if (points[0].point_ != points.back().point_) { |
| return {}; |
| } |
| |
| std::vector<CFX_Path::Point> normalized; |
| normalized.reserve(6); |
| normalized.push_back(points[0]); |
| for (auto it = points.begin() + 1; it != points.end(); ++it) { |
| // Exactly 5 points left. Stop normalizing and take what is left. |
| if (normalized.size() + std::distance(it, points.end()) == 5) { |
| std::copy(it, points.end(), std::back_inserter(normalized)); |
| break; |
| } |
| |
| // If the line does not move, skip this point. |
| const auto& point = *it; |
| if (point.type_ == CFX_Path::Point::Type::kLine && !point.close_figure_ && |
| !normalized.back().close_figure_ && |
| point.point_ == normalized.back().point_) { |
| continue; |
| } |
| |
| normalized.push_back(point); |
| |
| // Too many points. Not considered as a rectangle. |
| if (normalized.size() > 5) { |
| return {}; |
| } |
| } |
| |
| DCHECK_EQ(5u, normalized.size()); |
| return normalized; |
| } |
| |
| void UpdateLineEndPoints(CFX_FloatRect* rect, |
| const CFX_PointF& start_pos, |
| const CFX_PointF& end_pos, |
| float hw) { |
| if (start_pos.x == end_pos.x) { |
| if (start_pos.y == end_pos.y) { |
| rect->UpdateRect(end_pos + CFX_PointF(hw, hw)); |
| rect->UpdateRect(end_pos - CFX_PointF(hw, hw)); |
| return; |
| } |
| |
| float point_y; |
| if (end_pos.y < start_pos.y) { |
| point_y = end_pos.y - hw; |
| } else { |
| point_y = end_pos.y + hw; |
| } |
| |
| rect->UpdateRect(CFX_PointF(end_pos.x + hw, point_y)); |
| rect->UpdateRect(CFX_PointF(end_pos.x - hw, point_y)); |
| return; |
| } |
| |
| if (start_pos.y == end_pos.y) { |
| float point_x; |
| if (end_pos.x < start_pos.x) { |
| point_x = end_pos.x - hw; |
| } else { |
| point_x = end_pos.x + hw; |
| } |
| |
| rect->UpdateRect(CFX_PointF(point_x, end_pos.y + hw)); |
| rect->UpdateRect(CFX_PointF(point_x, end_pos.y - hw)); |
| return; |
| } |
| |
| CFX_PointF diff = end_pos - start_pos; |
| float ll = hypotf(diff.x, diff.y); |
| float mx = end_pos.x + hw * diff.x / ll; |
| float my = end_pos.y + hw * diff.y / ll; |
| float dx1 = hw * diff.y / ll; |
| float dy1 = hw * diff.x / ll; |
| rect->UpdateRect(CFX_PointF(mx - dx1, my + dy1)); |
| rect->UpdateRect(CFX_PointF(mx + dx1, my - dy1)); |
| } |
| |
| void UpdateLineJoinPoints(CFX_FloatRect* rect, |
| const CFX_PointF& start_pos, |
| const CFX_PointF& mid_pos, |
| const CFX_PointF& end_pos, |
| float half_width, |
| float miter_limit) { |
| float start_k = 0; |
| float start_c = 0; |
| float end_k = 0; |
| float end_c = 0; |
| float start_len = 0; |
| float start_dc = 0; |
| float end_len = 0; |
| float end_dc = 0; |
| float one_twentieth = 1.0f / 20; |
| |
| bool bStartVert = fabs(start_pos.x - mid_pos.x) < one_twentieth; |
| bool bEndVert = fabs(mid_pos.x - end_pos.x) < one_twentieth; |
| if (bStartVert && bEndVert) { |
| int start_dir = mid_pos.y > start_pos.y ? 1 : -1; |
| float point_y = mid_pos.y + half_width * start_dir; |
| rect->UpdateRect(CFX_PointF(mid_pos.x + half_width, point_y)); |
| rect->UpdateRect(CFX_PointF(mid_pos.x - half_width, point_y)); |
| return; |
| } |
| |
| if (!bStartVert) { |
| CFX_PointF start_to_mid = start_pos - mid_pos; |
| start_k = (mid_pos.y - start_pos.y) / (mid_pos.x - start_pos.x); |
| start_c = mid_pos.y - (start_k * mid_pos.x); |
| start_len = hypotf(start_to_mid.x, start_to_mid.y); |
| start_dc = fabsf(half_width * start_len / start_to_mid.x); |
| } |
| if (!bEndVert) { |
| CFX_PointF end_to_mid = end_pos - mid_pos; |
| end_k = end_to_mid.y / end_to_mid.x; |
| end_c = mid_pos.y - (end_k * mid_pos.x); |
| end_len = hypotf(end_to_mid.x, end_to_mid.y); |
| end_dc = fabs(half_width * end_len / end_to_mid.x); |
| } |
| if (bStartVert) { |
| CFX_PointF outside(start_pos.x, 0); |
| if (end_pos.x < start_pos.x) { |
| outside.x += half_width; |
| } else { |
| outside.x -= half_width; |
| } |
| |
| if (start_pos.y < (end_k * start_pos.x) + end_c) { |
| outside.y = (end_k * outside.x) + end_c + end_dc; |
| } else { |
| outside.y = (end_k * outside.x) + end_c - end_dc; |
| } |
| |
| rect->UpdateRect(outside); |
| return; |
| } |
| |
| if (bEndVert) { |
| CFX_PointF outside(end_pos.x, 0); |
| if (start_pos.x < end_pos.x) { |
| outside.x += half_width; |
| } else { |
| outside.x -= half_width; |
| } |
| |
| if (end_pos.y < (start_k * end_pos.x) + start_c) { |
| outside.y = (start_k * outside.x) + start_c + start_dc; |
| } else { |
| outside.y = (start_k * outside.x) + start_c - start_dc; |
| } |
| |
| rect->UpdateRect(outside); |
| return; |
| } |
| |
| if (fabs(start_k - end_k) < one_twentieth) { |
| int start_dir = mid_pos.x > start_pos.x ? 1 : -1; |
| int end_dir = end_pos.x > mid_pos.x ? 1 : -1; |
| if (start_dir == end_dir) { |
| UpdateLineEndPoints(rect, mid_pos, end_pos, half_width); |
| } else { |
| UpdateLineEndPoints(rect, start_pos, mid_pos, half_width); |
| } |
| return; |
| } |
| |
| float start_outside_c = start_c; |
| if (end_pos.y < (start_k * end_pos.x) + start_c) { |
| start_outside_c += start_dc; |
| } else { |
| start_outside_c -= start_dc; |
| } |
| |
| float end_outside_c = end_c; |
| if (start_pos.y < (end_k * start_pos.x) + end_c) { |
| end_outside_c += end_dc; |
| } else { |
| end_outside_c -= end_dc; |
| } |
| |
| float join_x = (end_outside_c - start_outside_c) / (start_k - end_k); |
| float join_y = start_k * join_x + start_outside_c; |
| rect->UpdateRect(CFX_PointF(join_x, join_y)); |
| } |
| |
| } // namespace |
| |
| CFX_Path::Point::Point() = default; |
| |
| CFX_Path::Point::Point(const CFX_PointF& point, Type type, bool close) |
| : point_(point), type_(type), close_figure_(close) {} |
| |
| CFX_Path::Point::Point(const Point& other) = default; |
| |
| CFX_Path::Point::~Point() = default; |
| |
| CFX_Path::CFX_Path() = default; |
| |
| CFX_Path::CFX_Path(const CFX_Path& src) = default; |
| |
| CFX_Path::CFX_Path(CFX_Path&& src) noexcept = default; |
| |
| CFX_Path::~CFX_Path() = default; |
| |
| void CFX_Path::Clear() { |
| points_.clear(); |
| } |
| |
| void CFX_Path::ClosePath() { |
| if (points_.empty()) { |
| return; |
| } |
| points_.back().close_figure_ = true; |
| } |
| |
| void CFX_Path::Append(const CFX_Path& src, const CFX_Matrix* matrix) { |
| if (src.points_.empty()) { |
| return; |
| } |
| |
| size_t cur_size = points_.size(); |
| points_.insert(points_.end(), src.points_.begin(), src.points_.end()); |
| |
| if (!matrix) { |
| return; |
| } |
| |
| for (size_t i = cur_size; i < points_.size(); i++) { |
| points_[i].point_ = matrix->Transform(points_[i].point_); |
| } |
| } |
| |
| void CFX_Path::AppendPoint(const CFX_PointF& point, Point::Type type) { |
| points_.emplace_back(point, type, /*close=*/false); |
| } |
| |
| void CFX_Path::AppendPointAndClose(const CFX_PointF& point, Point::Type type) { |
| points_.emplace_back(point, type, /*close=*/true); |
| } |
| |
| void CFX_Path::AppendLine(const CFX_PointF& pt1, const CFX_PointF& pt2) { |
| if (points_.empty() || fabs(points_.back().point_.x - pt1.x) > 0.001 || |
| fabs(points_.back().point_.y - pt1.y) > 0.001) { |
| AppendPoint(pt1, CFX_Path::Point::Type::kMove); |
| } |
| AppendPoint(pt2, CFX_Path::Point::Type::kLine); |
| } |
| |
| void CFX_Path::AppendFloatRect(const CFX_FloatRect& rect) { |
| return AppendRect(rect.left, rect.bottom, rect.right, rect.top); |
| } |
| |
| void CFX_Path::AppendRect(float left, float bottom, float right, float top) { |
| CFX_PointF left_bottom(left, bottom); |
| CFX_PointF left_top(left, top); |
| CFX_PointF right_top(right, top); |
| CFX_PointF right_bottom(right, bottom); |
| |
| AppendLine(left_bottom, left_top); |
| AppendLine(left_top, right_top); |
| AppendLine(right_top, right_bottom); |
| AppendLine(right_bottom, left_bottom); |
| ClosePath(); |
| } |
| |
| CFX_FloatRect CFX_Path::GetBoundingBox() const { |
| if (points_.empty()) { |
| return CFX_FloatRect(); |
| } |
| |
| CFX_FloatRect rect(points_[0].point_); |
| for (size_t i = 1; i < points_.size(); ++i) { |
| rect.UpdateRect(points_[i].point_); |
| } |
| return rect; |
| } |
| |
| CFX_FloatRect CFX_Path::GetBoundingBoxForStrokePath(float line_width, |
| float miter_limit) const { |
| CFX_FloatRect rect(100000.0f, 100000.0f, -100000.0f, -100000.0f); |
| size_t iPoint = 0; |
| float half_width = line_width; |
| size_t iStartPoint = 0; |
| size_t iEndPoint = 0; |
| size_t iMiddlePoint = 0; |
| bool bJoin; |
| while (iPoint < points_.size()) { |
| if (points_[iPoint].type_ == CFX_Path::Point::Type::kMove) { |
| if (iPoint + 1 == points_.size()) { |
| if (points_[iPoint].close_figure_) { |
| // Update `rect` right away since this is the final point to be drawn. |
| rect.UpdateRect(points_[iPoint].point_); |
| } |
| break; |
| } |
| |
| iStartPoint = iPoint + 1; |
| iEndPoint = iPoint; |
| bJoin = false; |
| } else { |
| if (points_[iPoint].IsTypeAndOpen(CFX_Path::Point::Type::kBezier)) { |
| // Callers are responsible for adding Beziers in sets of 3. |
| CHECK_LT(iPoint + 2, points_.size()); |
| DCHECK_EQ(points_[iPoint + 1].type_, CFX_Path::Point::Type::kBezier); |
| DCHECK_EQ(points_[iPoint + 2].type_, CFX_Path::Point::Type::kBezier); |
| rect.UpdateRect(points_[iPoint].point_); |
| rect.UpdateRect(points_[iPoint + 1].point_); |
| iPoint += 2; |
| } |
| if (iPoint + 1 == points_.size() || |
| points_[iPoint + 1].type_ == CFX_Path::Point::Type::kMove) { |
| iStartPoint = iPoint - 1; |
| iEndPoint = iPoint; |
| bJoin = false; |
| } else { |
| iStartPoint = iPoint - 1; |
| iMiddlePoint = iPoint; |
| iEndPoint = iPoint + 1; |
| bJoin = true; |
| } |
| } |
| CHECK_LT(iStartPoint, points_.size()); |
| CHECK_LT(iEndPoint, points_.size()); |
| if (bJoin) { |
| CHECK_LT(iMiddlePoint, points_.size()); |
| UpdateLineJoinPoints(&rect, points_[iStartPoint].point_, |
| points_[iMiddlePoint].point_, |
| points_[iEndPoint].point_, half_width, miter_limit); |
| } else { |
| UpdateLineEndPoints(&rect, points_[iStartPoint].point_, |
| points_[iEndPoint].point_, half_width); |
| } |
| ++iPoint; |
| } |
| return rect; |
| } |
| |
| void CFX_Path::Transform(const CFX_Matrix& matrix) { |
| for (auto& point : points_) { |
| point.point_ = matrix.Transform(point.point_); |
| } |
| } |
| |
| bool CFX_Path::IsRect() const { |
| if (PathPointsNeedNormalization(points_)) { |
| return IsRectImpl(GetNormalizedPoints(points_)); |
| } |
| return IsRectImpl(points_); |
| } |
| |
| std::optional<CFX_FloatRect> CFX_Path::GetRect(const CFX_Matrix* matrix) const { |
| bool do_normalize = PathPointsNeedNormalization(points_); |
| std::vector<Point> normalized; |
| if (do_normalize) { |
| normalized = GetNormalizedPoints(points_); |
| } |
| const std::vector<Point>& path_points = do_normalize ? normalized : points_; |
| |
| if (!matrix) { |
| if (!IsRectImpl(path_points)) { |
| return std::nullopt; |
| } |
| |
| return CreateRectFromPoints(path_points[0].point_, path_points[2].point_); |
| } |
| |
| if (!IsRectPreTransform(path_points)) { |
| return std::nullopt; |
| } |
| |
| std::array<CFX_PointF, 5> points; |
| for (size_t i = 0; i < path_points.size(); ++i) { |
| points[i] = matrix->Transform(path_points[i].point_); |
| |
| if (i == 0) { |
| continue; |
| } |
| if (XYBothNotEqual(points[i], points[i - 1])) { |
| return std::nullopt; |
| } |
| } |
| |
| if (XYBothNotEqual(points[0], points[3])) { |
| return std::nullopt; |
| } |
| |
| return CreateRectFromPoints(points[0], points[2]); |
| } |
| |
| CFX_RetainablePath::CFX_RetainablePath() = default; |
| |
| // Note: can't default the copy constructor since Retainable<> has a deleted |
| // copy constructor (as it should). Instead, we want the default Retainable<> |
| // constructor to be invoked so as to create a copy with a ref-count of 1 as |
| // of the time it is created, then populate the remainder of the members from |
| // the |src| object. |
| CFX_RetainablePath::CFX_RetainablePath(const CFX_RetainablePath& src) |
| : CFX_Path(src) {} |
| |
| CFX_RetainablePath::~CFX_RetainablePath() = default; |
| |
| RetainPtr<CFX_RetainablePath> CFX_RetainablePath::Clone() const { |
| return pdfium::MakeRetain<CFX_RetainablePath>(*this); |
| } |