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