• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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