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,FX_FLOAT hw)14 void 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
UpdateLineJoinPoints(CFX_FloatRect * rect,const CFX_PointF & start_pos,const CFX_PointF & mid_pos,const CFX_PointF & end_pos,FX_FLOAT half_width,FX_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 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
161 FX_PATHPOINT::FX_PATHPOINT() = default;
162
FX_PATHPOINT(const CFX_PointF & point,FXPT_TYPE type,bool close)163 FX_PATHPOINT::FX_PATHPOINT(const CFX_PointF& point, FXPT_TYPE type, bool close)
164 : m_Point(point), m_Type(type), m_CloseFigure(close) {}
165
166 FX_PATHPOINT::FX_PATHPOINT(const FX_PATHPOINT& other) = default;
167
168 FX_PATHPOINT::~FX_PATHPOINT() = default;
169
CFX_PathData()170 CFX_PathData::CFX_PathData() {}
171
~CFX_PathData()172 CFX_PathData::~CFX_PathData() {}
173
CFX_PathData(const CFX_PathData & src)174 CFX_PathData::CFX_PathData(const CFX_PathData& src) : m_Points(src.m_Points) {}
175
Clear()176 void CFX_PathData::Clear() {
177 m_Points.clear();
178 }
179
ClosePath()180 void CFX_PathData::ClosePath() {
181 if (m_Points.empty())
182 return;
183 m_Points.back().m_CloseFigure = true;
184 }
185
Append(const CFX_PathData * pSrc,const CFX_Matrix * pMatrix)186 void 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
AppendPoint(const CFX_PointF & point,FXPT_TYPE type,bool closeFigure)200 void 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
AppendRect(FX_FLOAT left,FX_FLOAT bottom,FX_FLOAT right,FX_FLOAT top)206 void 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
GetBoundingBox() const222 CFX_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
GetBoundingBox(FX_FLOAT line_width,FX_FLOAT miter_limit) const233 CFX_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
Transform(const CFX_Matrix * pMatrix)281 void 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
GetZeroAreaPath(const CFX_Matrix * pMatrix,bool bAdjust,CFX_PathData * NewPath,bool * bThin,bool * setIdentity) const288 bool 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
IsRect() const409 bool 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
IsRect(const CFX_Matrix * pMatrix,CFX_FloatRect * pRect) const436 bool 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