Home | History | Annotate | Download | only in fxge 
      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 
     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 
     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 
    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 
    169 CFX_PathData::CFX_PathData() {}
    170 
    171 CFX_PathData::~CFX_PathData() {}
    172 
    173 CFX_PathData::CFX_PathData(const CFX_PathData& src) : m_Points(src.m_Points) {}
    174 
    175 void CFX_PathData::Clear() {
    176   m_Points.clear();
    177 }
    178 
    179 void CFX_PathData::ClosePath() {
    180   if (m_Points.empty())
    181     return;
    182   m_Points.back().m_CloseFigure = true;
    183 }
    184 
    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 
    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 
    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 
    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 
    229 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 
    240 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 
    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 
    297 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 
    418 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 
    445 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