• Skip to content
  • Skip to link menu
KDE 4.2 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

KHTML

PathTraversalState.cpp

Go to the documentation of this file.
00001 /*
00002  * This file is part of the WebKit open source project.
00003  *
00004  * Copyright (C) 2006, 2007 Eric Seidel (eric@webkit.org)
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Library General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2 of the License, or (at your option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Library General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU Library General Public License
00017  * along with this library; see the file COPYING.LIB.  If not, write to
00018  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019  * Boston, MA 02110-1301, USA.
00020  */
00021 
00022 #include "config.h"
00023 #include "PathTraversalState.h"
00024 
00025 #include "Path.h"
00026 
00027 #include <math.h>
00028 
00029 namespace WebCore {
00030 
00031 static const float kPathSegmentLengthTolerance = 0.00001f;
00032 
00033 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
00034 {
00035     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
00036 }
00037 
00038 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
00039 {
00040     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
00041 }
00042 
00043 struct QuadraticBezier {
00044     QuadraticBezier() { }
00045     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
00046         : start(s)
00047         , control(c)
00048         , end(e)
00049     {
00050     }
00051     
00052     float approximateDistance() const
00053     {
00054         return distanceLine(start, control) + distanceLine(control, end);
00055     }
00056     
00057     void split(QuadraticBezier& left, QuadraticBezier& right) const
00058     {
00059         left.control = midPoint(start, control);
00060         right.control = midPoint(control, end);
00061         
00062         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
00063         left.end = leftControlToRightControl;
00064         right.start = leftControlToRightControl;
00065 
00066         left.start = start;
00067         right.end = end;
00068     }
00069     
00070     FloatPoint start;
00071     FloatPoint control;
00072     FloatPoint end;
00073 };
00074 
00075 struct CubicBezier {
00076     CubicBezier() { }
00077     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
00078         : start(s)
00079         , control1(c1)
00080         , control2(c2)
00081         , end(e)
00082     {
00083     }
00084     
00085     float approximateDistance() const
00086     {
00087         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
00088     }
00089         
00090     void split(CubicBezier& left, CubicBezier& right) const
00091     {    
00092         FloatPoint startToControl1 = midPoint(control1, control2);
00093         
00094         left.start = start;
00095         left.control1 = midPoint(start, control1);
00096         left.control2 = midPoint(left.control1, startToControl1);
00097         
00098         right.control2 = midPoint(control2, end);
00099         right.control1 = midPoint(right.control2, startToControl1);
00100         right.end = end;
00101         
00102         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
00103         left.end = leftControl2ToRightControl1;
00104         right.start = leftControl2ToRightControl1;
00105     }
00106     
00107     FloatPoint start;
00108     FloatPoint control1;
00109     FloatPoint control2;
00110     FloatPoint end;
00111 };
00112 
00113 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
00114 // A simple speed-up would be to use an additional boolean template parameter to control whether
00115 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
00116 // version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.
00117 // Another check which is possible up-front (to send us down the fast path) would be to check if
00118 // approximateDistance() + current total distance > desired distance
00119 template<class CurveType>
00120 static float curveLength(PathTraversalState& traversalState, CurveType curve)
00121 {
00122     Vector<CurveType> curveStack;
00123     curveStack.append(curve);
00124 
00125     float totalLength = 0.0f;
00126     do {
00127         float length = curve.approximateDistance();
00128         if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
00129             CurveType left, right;
00130             curve.split(left, right);
00131             curve = left;
00132             curveStack.append(right);
00133         } else {
00134             totalLength += length;
00135             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
00136              || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
00137                 traversalState.m_previous = curve.start;
00138                 traversalState.m_current = curve.end;
00139                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
00140                     return totalLength;
00141             }
00142             curve = curveStack.last();
00143             curveStack.removeLast();
00144         }
00145     } while (!curveStack.isEmpty());
00146     
00147     return totalLength;
00148 }
00149 
00150 PathTraversalState::PathTraversalState(PathTraversalAction action)
00151     : m_action(action)
00152     , m_success(false)
00153     , m_totalLength(0.0f)
00154     , m_segmentIndex(0)
00155     , m_desiredLength(0.0f)
00156     , m_normalAngle(0.0f)
00157 {
00158 }
00159 
00160 float PathTraversalState::closeSubpath()
00161 {
00162     float distance = distanceLine(m_current, m_start);
00163     m_start = m_control1 = m_control2 = m_current;
00164     return distance;
00165 }
00166 
00167 float PathTraversalState::moveTo(const FloatPoint& point)
00168 {
00169     m_current = m_start = m_control1 = m_control2 = point;
00170     return 0.0f;
00171 }
00172 
00173 float PathTraversalState::lineTo(const FloatPoint& point)
00174 {
00175     float distance = distanceLine(m_current, point);
00176     m_current = m_control1 = m_control2 = point;
00177     return distance;
00178 }
00179 
00180 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
00181 {
00182     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
00183 
00184     m_control1 = newControl;
00185     m_control2 = newEnd;
00186 
00187     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 
00188         m_current = newEnd;
00189 
00190     return distance;
00191 }
00192 
00193 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
00194 {
00195     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
00196 
00197     m_control1 = newEnd;
00198     m_control2 = newControl2;
00199  
00200     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 
00201         m_current = newEnd;
00202 
00203     return distance;
00204 }
00205 
00206 }
00207 

KHTML

Skip menu "KHTML"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.7
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal