1// Copyright 2016 PDFium 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// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7#include "core/fxge/cfx_pathdata.h" 8 9#include "core/fxcrt/fx_system.h" 10#include "third_party/base/numerics/safe_math.h" 11 12namespace { 13 14void UpdateLineEndPoints(CFX_FloatRect* rect, 15 const CFX_PointF& start_pos, 16 const CFX_PointF& end_pos, 17 FX_FLOAT hw) { 18 if (start_pos.x == end_pos.x) { 19 if (start_pos.y == end_pos.y) { 20 rect->UpdateRect(end_pos.x + hw, end_pos.y + hw); 21 rect->UpdateRect(end_pos.x - hw, end_pos.y - hw); 22 return; 23 } 24 25 FX_FLOAT point_y; 26 if (end_pos.y < start_pos.y) 27 point_y = end_pos.y - hw; 28 else 29 point_y = end_pos.y + hw; 30 31 rect->UpdateRect(end_pos.x + hw, point_y); 32 rect->UpdateRect(end_pos.x - hw, point_y); 33 return; 34 } 35 36 if (start_pos.y == end_pos.y) { 37 FX_FLOAT point_x; 38 if (end_pos.x < start_pos.x) 39 point_x = end_pos.x - hw; 40 else 41 point_x = end_pos.x + hw; 42 43 rect->UpdateRect(point_x, end_pos.y + hw); 44 rect->UpdateRect(point_x, end_pos.y - hw); 45 return; 46 } 47 48 CFX_PointF diff = end_pos - start_pos; 49 FX_FLOAT ll = FXSYS_sqrt2(diff.x, diff.y); 50 FX_FLOAT mx = end_pos.x + hw * diff.x / ll; 51 FX_FLOAT my = end_pos.y + hw * diff.y / ll; 52 FX_FLOAT dx1 = hw * diff.y / ll; 53 FX_FLOAT dy1 = hw * diff.x / ll; 54 rect->UpdateRect(mx - dx1, my + dy1); 55 rect->UpdateRect(mx + dx1, my - dy1); 56} 57 58void UpdateLineJoinPoints(CFX_FloatRect* rect, 59 const CFX_PointF& start_pos, 60 const CFX_PointF& mid_pos, 61 const CFX_PointF& end_pos, 62 FX_FLOAT half_width, 63 FX_FLOAT miter_limit) { 64 FX_FLOAT start_k = 0; 65 FX_FLOAT start_c = 0; 66 FX_FLOAT end_k = 0; 67 FX_FLOAT end_c = 0; 68 FX_FLOAT start_len = 0; 69 FX_FLOAT start_dc = 0; 70 FX_FLOAT end_len = 0; 71 FX_FLOAT end_dc = 0; 72 FX_FLOAT one_twentieth = 1.0f / 20; 73 74 bool bStartVert = FXSYS_fabs(start_pos.x - mid_pos.x) < one_twentieth; 75 bool bEndVert = FXSYS_fabs(mid_pos.x - end_pos.x) < one_twentieth; 76 if (bStartVert && bEndVert) { 77 int start_dir = mid_pos.y > start_pos.y ? 1 : -1; 78 FX_FLOAT point_y = mid_pos.y + half_width * start_dir; 79 rect->UpdateRect(mid_pos.x + half_width, point_y); 80 rect->UpdateRect(mid_pos.x - half_width, point_y); 81 return; 82 } 83 84 if (!bStartVert) { 85 CFX_PointF start_to_mid = start_pos - mid_pos; 86 start_k = (mid_pos.y - start_pos.y) / (mid_pos.x - start_pos.x); 87 start_c = mid_pos.y - (start_k * mid_pos.x); 88 start_len = FXSYS_sqrt2(start_to_mid.x, start_to_mid.y); 89 start_dc = static_cast<FX_FLOAT>( 90 FXSYS_fabs(half_width * start_len / start_to_mid.x)); 91 } 92 if (!bEndVert) { 93 CFX_PointF end_to_mid = end_pos - mid_pos; 94 end_k = end_to_mid.y / end_to_mid.x; 95 end_c = mid_pos.y - (end_k * mid_pos.x); 96 end_len = FXSYS_sqrt2(end_to_mid.x, end_to_mid.y); 97 end_dc = 98 static_cast<FX_FLOAT>(FXSYS_fabs(half_width * end_len / end_to_mid.x)); 99 } 100 if (bStartVert) { 101 CFX_PointF outside(start_pos.x, 0); 102 if (end_pos.x < start_pos.x) 103 outside.x += half_width; 104 else 105 outside.x -= half_width; 106 107 if (start_pos.y < (end_k * start_pos.x) + end_c) 108 outside.y = (end_k * outside.x) + end_c + end_dc; 109 else 110 outside.y = (end_k * outside.x) + end_c - end_dc; 111 112 rect->UpdateRect(outside.x, outside.y); 113 return; 114 } 115 116 if (bEndVert) { 117 CFX_PointF outside(end_pos.x, 0); 118 if (start_pos.x < end_pos.x) 119 outside.x += half_width; 120 else 121 outside.x -= half_width; 122 123 if (end_pos.y < (start_k * end_pos.x) + start_c) 124 outside.y = (start_k * outside.x) + start_c + start_dc; 125 else 126 outside.y = (start_k * outside.x) + start_c - start_dc; 127 128 rect->UpdateRect(outside.x, outside.y); 129 return; 130 } 131 132 if (FXSYS_fabs(start_k - end_k) < one_twentieth) { 133 int start_dir = mid_pos.x > start_pos.x ? 1 : -1; 134 int end_dir = end_pos.x > mid_pos.x ? 1 : -1; 135 if (start_dir == end_dir) 136 UpdateLineEndPoints(rect, mid_pos, end_pos, half_width); 137 else 138 UpdateLineEndPoints(rect, start_pos, mid_pos, half_width); 139 return; 140 } 141 142 FX_FLOAT start_outside_c = start_c; 143 if (end_pos.y < (start_k * end_pos.x) + start_c) 144 start_outside_c += start_dc; 145 else 146 start_outside_c -= start_dc; 147 148 FX_FLOAT end_outside_c = end_c; 149 if (start_pos.y < (end_k * start_pos.x) + end_c) 150 end_outside_c += end_dc; 151 else 152 end_outside_c -= end_dc; 153 154 FX_FLOAT join_x = (end_outside_c - start_outside_c) / (start_k - end_k); 155 FX_FLOAT join_y = start_k * join_x + start_outside_c; 156 rect->UpdateRect(join_x, join_y); 157} 158 159} // namespace 160 161FX_PATHPOINT::FX_PATHPOINT() = default; 162 163FX_PATHPOINT::FX_PATHPOINT(const CFX_PointF& point, FXPT_TYPE type, bool close) 164 : m_Point(point), m_Type(type), m_CloseFigure(close) {} 165 166FX_PATHPOINT::FX_PATHPOINT(const FX_PATHPOINT& other) = default; 167 168FX_PATHPOINT::~FX_PATHPOINT() = default; 169 170CFX_PathData::CFX_PathData() {} 171 172CFX_PathData::~CFX_PathData() {} 173 174CFX_PathData::CFX_PathData(const CFX_PathData& src) : m_Points(src.m_Points) {} 175 176void CFX_PathData::Clear() { 177 m_Points.clear(); 178} 179 180void CFX_PathData::ClosePath() { 181 if (m_Points.empty()) 182 return; 183 m_Points.back().m_CloseFigure = true; 184} 185 186void CFX_PathData::Append(const CFX_PathData* pSrc, const CFX_Matrix* pMatrix) { 187 if (pSrc->m_Points.empty()) 188 return; 189 190 size_t cur_size = m_Points.size(); 191 m_Points.insert(m_Points.end(), pSrc->m_Points.begin(), pSrc->m_Points.end()); 192 193 if (!pMatrix) 194 return; 195 196 for (size_t i = cur_size; i < m_Points.size(); i++) 197 m_Points[i].m_Point = pMatrix->Transform(m_Points[i].m_Point); 198} 199 200void CFX_PathData::AppendPoint(const CFX_PointF& point, 201 FXPT_TYPE type, 202 bool closeFigure) { 203 m_Points.push_back(FX_PATHPOINT(point, type, closeFigure)); 204} 205 206void CFX_PathData::AppendRect(FX_FLOAT left, 207 FX_FLOAT bottom, 208 FX_FLOAT right, 209 FX_FLOAT top) { 210 m_Points.push_back( 211 FX_PATHPOINT(CFX_PointF(left, bottom), FXPT_TYPE::MoveTo, false)); 212 m_Points.push_back( 213 FX_PATHPOINT(CFX_PointF(left, top), FXPT_TYPE::LineTo, false)); 214 m_Points.push_back( 215 FX_PATHPOINT(CFX_PointF(right, top), FXPT_TYPE::LineTo, false)); 216 m_Points.push_back( 217 FX_PATHPOINT(CFX_PointF(right, bottom), FXPT_TYPE::LineTo, false)); 218 m_Points.push_back( 219 FX_PATHPOINT(CFX_PointF(left, bottom), FXPT_TYPE::LineTo, true)); 220} 221 222CFX_FloatRect CFX_PathData::GetBoundingBox() const { 223 if (m_Points.empty()) 224 return CFX_FloatRect(); 225 226 CFX_FloatRect rect; 227 rect.InitRect(m_Points[0].m_Point.x, m_Points[0].m_Point.y); 228 for (size_t i = 1; i < m_Points.size(); i++) 229 rect.UpdateRect(m_Points[i].m_Point.x, m_Points[i].m_Point.y); 230 return rect; 231} 232 233CFX_FloatRect CFX_PathData::GetBoundingBox(FX_FLOAT line_width, 234 FX_FLOAT miter_limit) const { 235 CFX_FloatRect rect(100000.0f, 100000.0f, -100000.0f, -100000.0f); 236 size_t iPoint = 0; 237 FX_FLOAT half_width = line_width; 238 int iStartPoint = 0; 239 int iEndPoint = 0; 240 int iMiddlePoint = 0; 241 bool bJoin; 242 while (iPoint < m_Points.size()) { 243 if (m_Points[iPoint].IsTypeAndOpen(FXPT_TYPE::MoveTo)) { 244 iStartPoint = iPoint + 1; 245 iEndPoint = iPoint; 246 bJoin = false; 247 } else { 248 if (m_Points[iPoint].IsTypeAndOpen(FXPT_TYPE::BezierTo)) { 249 rect.UpdateRect(m_Points[iPoint].m_Point.x, m_Points[iPoint].m_Point.y); 250 rect.UpdateRect(m_Points[iPoint + 1].m_Point.x, 251 m_Points[iPoint + 1].m_Point.y); 252 iPoint += 2; 253 } 254 if (iPoint == m_Points.size() - 1 || 255 m_Points[iPoint + 1].IsTypeAndOpen(FXPT_TYPE::MoveTo)) { 256 iStartPoint = iPoint - 1; 257 iEndPoint = iPoint; 258 bJoin = false; 259 } else { 260 iStartPoint = iPoint - 1; 261 iMiddlePoint = iPoint; 262 iEndPoint = iPoint + 1; 263 bJoin = true; 264 } 265 } 266 267 CFX_PointF start_pos = m_Points[iStartPoint].m_Point; 268 CFX_PointF end_pos = m_Points[iEndPoint].m_Point; 269 if (bJoin) { 270 CFX_PointF mid_pos = m_Points[iMiddlePoint].m_Point; 271 UpdateLineJoinPoints(&rect, start_pos, mid_pos, end_pos, half_width, 272 miter_limit); 273 } else { 274 UpdateLineEndPoints(&rect, start_pos, end_pos, half_width); 275 } 276 iPoint++; 277 } 278 return rect; 279} 280 281void CFX_PathData::Transform(const CFX_Matrix* pMatrix) { 282 if (!pMatrix) 283 return; 284 for (auto& point : m_Points) 285 point.m_Point = pMatrix->Transform(point.m_Point); 286} 287 288bool CFX_PathData::GetZeroAreaPath(const CFX_Matrix* pMatrix, 289 bool bAdjust, 290 CFX_PathData* NewPath, 291 bool* bThin, 292 bool* setIdentity) const { 293 *setIdentity = false; 294 if (m_Points.size() < 3) 295 return false; 296 297 if (m_Points.size() == 3 && m_Points[0].m_Type == FXPT_TYPE::MoveTo && 298 m_Points[1].m_Type == FXPT_TYPE::LineTo && 299 m_Points[2].m_Type == FXPT_TYPE::LineTo && 300 m_Points[0].m_Point == m_Points[2].m_Point) { 301 for (size_t i = 0; i < 2; i++) { 302 CFX_PointF point = m_Points[i].m_Point; 303 if (bAdjust) { 304 if (pMatrix) 305 point = pMatrix->Transform(point); 306 307 point = CFX_PointF(static_cast<int>(point.x) + 0.5f, 308 static_cast<int>(point.y) + 0.5f); 309 } 310 NewPath->AppendPoint( 311 point, i == 0 ? FXPT_TYPE::MoveTo : FXPT_TYPE::LineTo, false); 312 } 313 if (bAdjust && pMatrix) 314 *setIdentity = true; 315 316 // Note, they both have to be not equal. 317 if (m_Points[0].m_Point.x != m_Points[1].m_Point.x && 318 m_Points[0].m_Point.y != m_Points[1].m_Point.y) { 319 *bThin = true; 320 } 321 return true; 322 } 323 324 if (((m_Points.size() > 3) && (m_Points.size() % 2))) { 325 int mid = m_Points.size() / 2; 326 bool bZeroArea = false; 327 CFX_PathData t_path; 328 for (int i = 0; i < mid; i++) { 329 if (!(m_Points[mid - i - 1].m_Point == m_Points[mid + i + 1].m_Point && 330 m_Points[mid - i - 1].m_Type != FXPT_TYPE::BezierTo && 331 m_Points[mid + i + 1].m_Type != FXPT_TYPE::BezierTo)) { 332 bZeroArea = true; 333 break; 334 } 335 336 t_path.AppendPoint(m_Points[mid - i].m_Point, FXPT_TYPE::MoveTo, false); 337 t_path.AppendPoint(m_Points[mid - i - 1].m_Point, FXPT_TYPE::LineTo, 338 false); 339 } 340 if (!bZeroArea) { 341 NewPath->Append(&t_path, nullptr); 342 *bThin = true; 343 return true; 344 } 345 } 346 347 int stratPoint = 0; 348 int next = 0; 349 for (size_t i = 0; i < m_Points.size(); i++) { 350 FXPT_TYPE point_type = m_Points[i].m_Type; 351 if (point_type == FXPT_TYPE::MoveTo) { 352 stratPoint = i; 353 } else if (point_type == FXPT_TYPE::LineTo) { 354 next = (i + 1 - stratPoint) % (m_Points.size() - stratPoint) + stratPoint; 355 if (m_Points[next].m_Type != FXPT_TYPE::BezierTo && 356 m_Points[next].m_Type != FXPT_TYPE::MoveTo) { 357 if ((m_Points[i - 1].m_Point.x == m_Points[i].m_Point.x && 358 m_Points[i].m_Point.x == m_Points[next].m_Point.x) && 359 ((m_Points[i].m_Point.y - m_Points[i - 1].m_Point.y) * 360 (m_Points[i].m_Point.y - m_Points[next].m_Point.y) > 361 0)) { 362 int pre = i; 363 if (FXSYS_fabs(m_Points[i].m_Point.y - m_Points[i - 1].m_Point.y) < 364 FXSYS_fabs(m_Points[i].m_Point.y - m_Points[next].m_Point.y)) { 365 pre--; 366 next--; 367 } 368 369 NewPath->AppendPoint(m_Points[pre].m_Point, FXPT_TYPE::MoveTo, false); 370 NewPath->AppendPoint(m_Points[next].m_Point, FXPT_TYPE::LineTo, 371 false); 372 } else if ((m_Points[i - 1].m_Point.y == m_Points[i].m_Point.y && 373 m_Points[i].m_Point.y == m_Points[next].m_Point.y) && 374 ((m_Points[i].m_Point.x - m_Points[i - 1].m_Point.x) * 375 (m_Points[i].m_Point.x - m_Points[next].m_Point.x) > 376 0)) { 377 int pre = i; 378 if (FXSYS_fabs(m_Points[i].m_Point.x - m_Points[i - 1].m_Point.x) < 379 FXSYS_fabs(m_Points[i].m_Point.x - m_Points[next].m_Point.x)) { 380 pre--; 381 next--; 382 } 383 384 NewPath->AppendPoint(m_Points[pre].m_Point, FXPT_TYPE::MoveTo, false); 385 NewPath->AppendPoint(m_Points[next].m_Point, FXPT_TYPE::LineTo, 386 false); 387 } else if (m_Points[i - 1].m_Type == FXPT_TYPE::MoveTo && 388 m_Points[next].m_Type == FXPT_TYPE::LineTo && 389 m_Points[i - 1].m_Point == m_Points[next].m_Point && 390 m_Points[next].m_CloseFigure) { 391 NewPath->AppendPoint(m_Points[i - 1].m_Point, FXPT_TYPE::MoveTo, 392 false); 393 NewPath->AppendPoint(m_Points[i].m_Point, FXPT_TYPE::LineTo, false); 394 *bThin = true; 395 } 396 } 397 } else if (point_type == FXPT_TYPE::BezierTo) { 398 i += 2; 399 continue; 400 } 401 } 402 403 size_t new_path_size = NewPath->GetPoints().size(); 404 if (m_Points.size() > 3 && new_path_size > 0) 405 *bThin = true; 406 return new_path_size != 0; 407} 408 409bool CFX_PathData::IsRect() const { 410 if (m_Points.size() != 5 && m_Points.size() != 4) 411 return false; 412 413 if ((m_Points.size() == 5 && m_Points[0].m_Point != m_Points[4].m_Point) || 414 m_Points[0].m_Point == m_Points[2].m_Point || 415 m_Points[1].m_Point == m_Points[3].m_Point) { 416 return false; 417 } 418 // Note, both x,y have to not equal. 419 if (m_Points[0].m_Point.x != m_Points[3].m_Point.x && 420 m_Points[0].m_Point.y != m_Points[3].m_Point.y) { 421 return false; 422 } 423 424 for (int i = 1; i < 4; i++) { 425 if (m_Points[i].m_Type != FXPT_TYPE::LineTo) 426 return false; 427 // Note, both x,y have to not equal. 428 if (m_Points[i].m_Point.x != m_Points[i - 1].m_Point.x && 429 m_Points[i].m_Point.y != m_Points[i - 1].m_Point.y) { 430 return false; 431 } 432 } 433 return m_Points.size() == 5 || m_Points[3].m_CloseFigure; 434} 435 436bool CFX_PathData::IsRect(const CFX_Matrix* pMatrix, 437 CFX_FloatRect* pRect) const { 438 if (!pMatrix) { 439 if (!IsRect()) 440 return false; 441 442 if (pRect) { 443 pRect->left = m_Points[0].m_Point.x; 444 pRect->right = m_Points[2].m_Point.x; 445 pRect->bottom = m_Points[0].m_Point.y; 446 pRect->top = m_Points[2].m_Point.y; 447 pRect->Normalize(); 448 } 449 return true; 450 } 451 452 if (m_Points.size() != 5 && m_Points.size() != 4) 453 return false; 454 455 if ((m_Points.size() == 5 && m_Points[0].m_Point != m_Points[4].m_Point) || 456 m_Points[1].m_Point == m_Points[3].m_Point) { 457 return false; 458 } 459 // Note, both x,y not equal. 460 if (m_Points.size() == 4 && m_Points[0].m_Point.x != m_Points[3].m_Point.x && 461 m_Points[0].m_Point.y != m_Points[3].m_Point.y) { 462 return false; 463 } 464 465 CFX_PointF points[5]; 466 for (size_t i = 0; i < m_Points.size(); i++) { 467 points[i] = pMatrix->Transform(m_Points[i].m_Point); 468 469 if (i == 0) 470 continue; 471 if (m_Points[i].m_Type != FXPT_TYPE::LineTo) 472 return false; 473 if (points[i].x != points[i - 1].x && points[i].y != points[i - 1].y) 474 return false; 475 } 476 477 if (pRect) { 478 pRect->left = points[0].x; 479 pRect->right = points[2].x; 480 pRect->bottom = points[0].y; 481 pRect->top = points[2].y; 482 pRect->Normalize(); 483 } 484 return true; 485} 486