Home | History | Annotate | Download | only in graphics 
      1 /*
      2  * This file is part of the WebKit open source project.
      3  *
      4  * Copyright (C) 2006, 2007 Eric Seidel (eric (at) webkit.org)
      5  *
      6  * This library is free software; you can redistribute it and/or
      7  * modify it under the terms of the GNU Library General Public
      8  * License as published by the Free Software Foundation; either
      9  * version 2 of the License, or (at your option) any later version.
     10  *
     11  * This library is distributed in the hope that it will be useful,
     12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     14  * Library General Public License for more details.
     15  *
     16  * You should have received a copy of the GNU Library General Public License
     17  * along with this library; see the file COPYING.LIB.  If not, write to
     18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     19  * Boston, MA 02110-1301, USA.
     20  */
     21 
     22 #include "config.h"
     23 #include "PathTraversalState.h"
     24 
     25 #include "Path.h"
     26 
     27 #include <math.h>
     28 
     29 namespace WebCore {
     30 
     31 static const float kPathSegmentLengthTolerance = 0.00001f;
     32 
     33 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
     34 {
     35     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
     36 }
     37 
     38 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
     39 {
     40     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
     41 }
     42 
     43 struct QuadraticBezier {
     44     QuadraticBezier() { }
     45     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
     46         : start(s)
     47         , control(c)
     48         , end(e)
     49     {
     50     }
     51 
     52     float approximateDistance() const
     53     {
     54         return distanceLine(start, control) + distanceLine(control, end);
     55     }
     56 
     57     void split(QuadraticBezier& left, QuadraticBezier& right) const
     58     {
     59         left.control = midPoint(start, control);
     60         right.control = midPoint(control, end);
     61 
     62         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
     63         left.end = leftControlToRightControl;
     64         right.start = leftControlToRightControl;
     65 
     66         left.start = start;
     67         right.end = end;
     68     }
     69 
     70     FloatPoint start;
     71     FloatPoint control;
     72     FloatPoint end;
     73 };
     74 
     75 struct CubicBezier {
     76     CubicBezier() { }
     77     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
     78         : start(s)
     79         , control1(c1)
     80         , control2(c2)
     81         , end(e)
     82     {
     83     }
     84 
     85     float approximateDistance() const
     86     {
     87         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
     88     }
     89 
     90     void split(CubicBezier& left, CubicBezier& right) const
     91     {
     92         FloatPoint startToControl1 = midPoint(control1, control2);
     93 
     94         left.start = start;
     95         left.control1 = midPoint(start, control1);
     96         left.control2 = midPoint(left.control1, startToControl1);
     97 
     98         right.control2 = midPoint(control2, end);
     99         right.control1 = midPoint(right.control2, startToControl1);
    100         right.end = end;
    101 
    102         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
    103         left.end = leftControl2ToRightControl1;
    104         right.start = leftControl2ToRightControl1;
    105     }
    106 
    107     FloatPoint start;
    108     FloatPoint control1;
    109     FloatPoint control2;
    110     FloatPoint end;
    111 };
    112 
    113 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
    114 // A simple speed-up would be to use an additional boolean template parameter to control whether
    115 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
    116 // version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.
    117 // Another check which is possible up-front (to send us down the fast path) would be to check if
    118 // approximateDistance() + current total distance > desired distance
    119 template<class CurveType>
    120 static float curveLength(PathTraversalState& traversalState, CurveType curve)
    121 {
    122     Vector<CurveType> curveStack;
    123     curveStack.append(curve);
    124 
    125     float totalLength = 0.0f;
    126     do {
    127         float length = curve.approximateDistance();
    128         if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
    129             CurveType left, right;
    130             curve.split(left, right);
    131             curve = left;
    132             curveStack.append(right);
    133         } else {
    134             totalLength += length;
    135             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
    136              || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
    137                 traversalState.m_previous = curve.start;
    138                 traversalState.m_current = curve.end;
    139                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
    140                     return totalLength;
    141             }
    142             curve = curveStack.last();
    143             curveStack.removeLast();
    144         }
    145     } while (!curveStack.isEmpty());
    146 
    147     return totalLength;
    148 }
    149 
    150 PathTraversalState::PathTraversalState(PathTraversalAction action)
    151     : m_action(action)
    152     , m_success(false)
    153     , m_totalLength(0.0f)
    154     , m_segmentIndex(0)
    155     , m_desiredLength(0.0f)
    156     , m_normalAngle(0.0f)
    157 {
    158 }
    159 
    160 float PathTraversalState::closeSubpath()
    161 {
    162     float distance = distanceLine(m_current, m_start);
    163     m_start = m_control1 = m_control2 = m_current;
    164     return distance;
    165 }
    166 
    167 float PathTraversalState::moveTo(const FloatPoint& point)
    168 {
    169     m_current = m_start = m_control1 = m_control2 = point;
    170     return 0.0f;
    171 }
    172 
    173 float PathTraversalState::lineTo(const FloatPoint& point)
    174 {
    175     float distance = distanceLine(m_current, point);
    176     m_current = m_control1 = m_control2 = point;
    177     return distance;
    178 }
    179 
    180 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
    181 {
    182     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
    183 
    184     m_control1 = newControl;
    185     m_control2 = newEnd;
    186 
    187     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    188         m_current = newEnd;
    189 
    190     return distance;
    191 }
    192 
    193 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
    194 {
    195     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
    196 
    197     m_control1 = newEnd;
    198     m_control2 = newControl2;
    199 
    200     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
    201         m_current = newEnd;
    202 
    203     return distance;
    204 }
    205 
    206 }
    207 
    208