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