Home | History | Annotate | Download | only in graphics 
      1 /*
      2  * Copyright (C) 2006, 2007 Eric Seidel <eric (at) webkit.org>
      3  *
      4  * This library is free software; you can redistribute it and/or
      5  * modify it under the terms of the GNU Library General Public
      6  * License as published by the Free Software Foundation; either
      7  * version 2 of the License, or (at your option) any later version.
      8  *
      9  * This library is distributed in the hope that it will be useful,
     10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     12  * Library General Public License for more details.
     13  *
     14  * You should have received a copy of the GNU Library General Public License
     15  * along with this library; see the file COPYING.LIB.  If not, write to
     16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     17  * Boston, MA 02110-1301, USA.
     18  */
     19 
     20 #include "config.h"
     21 #include "platform/graphics/PathTraversalState.h"
     22 
     23 #include "wtf/MathExtras.h"
     24 #include "wtf/Vector.h"
     25 
     26 namespace blink {
     27 
     28 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
     29 {
     30     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
     31 }
     32 
     33 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
     34 {
     35     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
     36 }
     37 
     38 struct QuadraticBezier {
     39     QuadraticBezier() { }
     40     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
     41         : start(s)
     42         , control(c)
     43         , end(e)
     44         , splitDepth(0)
     45     {
     46     }
     47 
     48     double magnitudeSquared() const
     49     {
     50         return ((double)(start.dot(start)) + (double)(control.dot(control)) + (double)(end.dot(end))) / 9.0;
     51     }
     52 
     53     float approximateDistance() const
     54     {
     55         return distanceLine(start, control) + distanceLine(control, end);
     56     }
     57 
     58     void split(QuadraticBezier& left, QuadraticBezier& right) const
     59     {
     60         left.control = midPoint(start, control);
     61         right.control = midPoint(control, end);
     62 
     63         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
     64         left.end = leftControlToRightControl;
     65         right.start = leftControlToRightControl;
     66 
     67         left.start = start;
     68         right.end = end;
     69 
     70         left.splitDepth = right.splitDepth = splitDepth + 1;
     71     }
     72 
     73     FloatPoint start;
     74     FloatPoint control;
     75     FloatPoint end;
     76     unsigned short splitDepth;
     77 };
     78 
     79 struct CubicBezier {
     80     CubicBezier() { }
     81     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
     82         : start(s)
     83         , control1(c1)
     84         , control2(c2)
     85         , end(e)
     86         , splitDepth(0)
     87     {
     88     }
     89 
     90     double magnitudeSquared() const
     91     {
     92         return ((double)(start.dot(start)) + (double)(control1.dot(control1)) + (double)(control2.dot(control2)) + (double)(end.dot(end))) / 16.0;
     93     }
     94 
     95     float approximateDistance() const
     96     {
     97         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
     98     }
     99 
    100     void split(CubicBezier& left, CubicBezier& right) const
    101     {
    102         FloatPoint startToControl1 = midPoint(control1, control2);
    103 
    104         left.start = start;
    105         left.control1 = midPoint(start, control1);
    106         left.control2 = midPoint(left.control1, startToControl1);
    107 
    108         right.control2 = midPoint(control2, end);
    109         right.control1 = midPoint(right.control2, startToControl1);
    110         right.end = end;
    111 
    112         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
    113         left.end = leftControl2ToRightControl1;
    114         right.start = leftControl2ToRightControl1;
    115 
    116         left.splitDepth = right.splitDepth = splitDepth + 1;
    117     }
    118 
    119     FloatPoint start;
    120     FloatPoint control1;
    121     FloatPoint control2;
    122     FloatPoint end;
    123     unsigned short splitDepth;
    124 };
    125 
    126 template<class CurveType>
    127 static float curveLength(PathTraversalState& traversalState, CurveType curve)
    128 {
    129     static const unsigned short curveSplitDepthLimit = 20;
    130     static const double pathSegmentLengthToleranceSquared = 1.e-16;
    131 
    132     double curveScaleForToleranceSquared = curve.magnitudeSquared();
    133     if (curveScaleForToleranceSquared < pathSegmentLengthToleranceSquared)
    134         return 0;
    135 
    136     Vector<CurveType> curveStack;
    137     curveStack.append(curve);
    138 
    139     float totalLength = 0;
    140     do {
    141         float length = curve.approximateDistance();
    142         double lengthDiscrepancy = length - distanceLine(curve.start, curve.end);
    143         if ((lengthDiscrepancy * lengthDiscrepancy) / curveScaleForToleranceSquared > pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
    144             CurveType leftCurve;
    145             CurveType rightCurve;
    146             curve.split(leftCurve, rightCurve);
    147             curve = leftCurve;
    148             curveStack.append(rightCurve);
    149         } else {
    150             totalLength += length;
    151             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
    152                 traversalState.m_previous = curve.start;
    153                 traversalState.m_current = curve.end;
    154                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
    155                     return totalLength;
    156             }
    157             curve = curveStack.last();
    158             curveStack.removeLast();
    159         }
    160     } while (!curveStack.isEmpty());
    161 
    162     return totalLength;
    163 }
    164 
    165 PathTraversalState::PathTraversalState(PathTraversalAction action)
    166     : m_action(action)
    167     , m_success(false)
    168     , m_totalLength(0)
    169     , m_segmentIndex(0)
    170     , m_desiredLength(0)
    171     , m_normalAngle(0)
    172 {
    173 }
    174 
    175 float PathTraversalState::closeSubpath()
    176 {
    177     float distance = distanceLine(m_current, m_start);
    178     m_current = m_start;
    179     return distance;
    180 }
    181 
    182 float PathTraversalState::moveTo(const FloatPoint& point)
    183 {
    184     m_current = m_start = point;
    185     return 0;
    186 }
    187 
    188 float PathTraversalState::lineTo(const FloatPoint& point)
    189 {
    190     float distance = distanceLine(m_current, point);
    191     m_current = point;
    192     return distance;
    193 }
    194 
    195 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
    196 {
    197     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
    198 
    199     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    200         m_current = newEnd;
    201 
    202     return distance;
    203 }
    204 
    205 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
    206 {
    207     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
    208 
    209     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    210         m_current = newEnd;
    211 
    212     return distance;
    213 }
    214 
    215 void PathTraversalState::processSegment()
    216 {
    217     if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength)
    218         m_success = true;
    219 
    220     if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) {
    221         float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
    222         if (m_action == TraversalPointAtLength) {
    223             float offset = m_desiredLength - m_totalLength;
    224             m_current.move(offset * cosf(slope), offset * sinf(slope));
    225         } else {
    226             m_normalAngle = rad2deg(slope);
    227         }
    228         m_success = true;
    229     }
    230     m_previous = m_current;
    231 }
    232 
    233 } // namespace blink
    234 
    235