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 WebCore {
     27 
     28 static const float kPathSegmentLengthTolerance = 0.00001f;
     29 
     30 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
     31 {
     32     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
     33 }
     34 
     35 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
     36 {
     37     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
     38 }
     39 
     40 struct QuadraticBezier {
     41     QuadraticBezier() { }
     42     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
     43         : start(s)
     44         , control(c)
     45         , end(e)
     46     {
     47     }
     48 
     49     float approximateDistance() const
     50     {
     51         return distanceLine(start, control) + distanceLine(control, end);
     52     }
     53 
     54     void split(QuadraticBezier& left, QuadraticBezier& right) const
     55     {
     56         left.control = midPoint(start, control);
     57         right.control = midPoint(control, end);
     58 
     59         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
     60         left.end = leftControlToRightControl;
     61         right.start = leftControlToRightControl;
     62 
     63         left.start = start;
     64         right.end = end;
     65     }
     66 
     67     FloatPoint start;
     68     FloatPoint control;
     69     FloatPoint end;
     70 };
     71 
     72 struct CubicBezier {
     73     CubicBezier() { }
     74     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
     75         : start(s)
     76         , control1(c1)
     77         , control2(c2)
     78         , end(e)
     79     {
     80     }
     81 
     82     float approximateDistance() const
     83     {
     84         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
     85     }
     86 
     87     void split(CubicBezier& left, CubicBezier& right) const
     88     {
     89         FloatPoint startToControl1 = midPoint(control1, control2);
     90 
     91         left.start = start;
     92         left.control1 = midPoint(start, control1);
     93         left.control2 = midPoint(left.control1, startToControl1);
     94 
     95         right.control2 = midPoint(control2, end);
     96         right.control1 = midPoint(right.control2, startToControl1);
     97         right.end = end;
     98 
     99         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
    100         left.end = leftControl2ToRightControl1;
    101         right.start = leftControl2ToRightControl1;
    102     }
    103 
    104     FloatPoint start;
    105     FloatPoint control1;
    106     FloatPoint control2;
    107     FloatPoint end;
    108 };
    109 
    110 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
    111 // A simple speed-up would be to use an additional boolean template parameter to control whether
    112 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
    113 // version which does update the PathTraversalState. We'll have to shark it to see if that's necessary.
    114 // Another check which is possible up-front (to send us down the fast path) would be to check if
    115 // approximateDistance() + current total distance > desired distance
    116 template<class CurveType>
    117 static float curveLength(PathTraversalState& traversalState, CurveType curve)
    118 {
    119     static const unsigned curveStackDepthLimit = 20;
    120 
    121     Vector<CurveType> curveStack;
    122     curveStack.append(curve);
    123 
    124     float totalLength = 0;
    125     do {
    126         float length = curve.approximateDistance();
    127         if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() <= curveStackDepthLimit) {
    128             CurveType leftCurve;
    129             CurveType rightCurve;
    130             curve.split(leftCurve, rightCurve);
    131             curve = leftCurve;
    132             curveStack.append(rightCurve);
    133         } else {
    134             totalLength += length;
    135             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
    136                 traversalState.m_previous = curve.start;
    137                 traversalState.m_current = curve.end;
    138                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
    139                     return totalLength;
    140             }
    141             curve = curveStack.last();
    142             curveStack.removeLast();
    143         }
    144     } while (!curveStack.isEmpty());
    145 
    146     return totalLength;
    147 }
    148 
    149 PathTraversalState::PathTraversalState(PathTraversalAction action)
    150     : m_action(action)
    151     , m_success(false)
    152     , m_totalLength(0)
    153     , m_segmentIndex(0)
    154     , m_desiredLength(0)
    155     , m_normalAngle(0)
    156 {
    157 }
    158 
    159 float PathTraversalState::closeSubpath()
    160 {
    161     float distance = distanceLine(m_current, m_start);
    162     m_current = m_control1 = m_control2 = m_start;
    163     return distance;
    164 }
    165 
    166 float PathTraversalState::moveTo(const FloatPoint& point)
    167 {
    168     m_current = m_start = m_control1 = m_control2 = point;
    169     return 0;
    170 }
    171 
    172 float PathTraversalState::lineTo(const FloatPoint& point)
    173 {
    174     float distance = distanceLine(m_current, point);
    175     m_current = m_control1 = m_control2 = point;
    176     return distance;
    177 }
    178 
    179 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
    180 {
    181     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
    182 
    183     m_control1 = newControl;
    184     m_control2 = newEnd;
    185 
    186     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    187         m_current = newEnd;
    188 
    189     return distance;
    190 }
    191 
    192 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
    193 {
    194     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
    195 
    196     m_control1 = newEnd;
    197     m_control2 = newControl2;
    198 
    199     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    200         m_current = newEnd;
    201 
    202     return distance;
    203 }
    204 
    205 void PathTraversalState::processSegment()
    206 {
    207     if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength)
    208         m_success = true;
    209 
    210     if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) {
    211         float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
    212         if (m_action == TraversalPointAtLength) {
    213             float offset = m_desiredLength - m_totalLength;
    214             m_current.move(offset * cosf(slope), offset * sinf(slope));
    215         } else {
    216             m_normalAngle = rad2deg(slope);
    217         }
    218         m_success = true;
    219     }
    220     m_previous = m_current;
    221 }
    222 
    223 }
    224 
    225