#i105937# Much improved gradient support for canvas/basegfx/drawinglayer.

See http://blog.thebehrens.net/2009/07/28/hackweek-iv-canvas-convwatch/ for more background information

12 files changed, 476 insertions, 46 deletions

diff --git a/basegfx/inc/basegfx/matrix/b2dhommatrixtools.hxx b/basegfx/inc/basegfx/matrix/b2dhommatrixtools.hxx
index 0b200b812bed..54d961d40ac2 100644
--- a/basegfx/inc/basegfx/matrix/b2dhommatrixtools.hxx
+++ b/basegfx/inc/basegfx/matrix/b2dhommatrixtools.hxx
@@ -36,6 +36,8 @@
 #include <basegfx/matrix/b2dhommatrix.hxx>
 #include <basegfx/vector/b2dvector.hxx>
 
+namespace rtl { class OUString; }
+
 ///////////////////////////////////////////////////////////////////////////////
 
 namespace basegfx
@@ -79,6 +81,10 @@ namespace basegfx
         double getRotate() const { const_cast< DecomposedB2DHomMatrixContainer* >(this)->impCheckDecompose(); return mfRotate; }
         double getShearX() const { const_cast< DecomposedB2DHomMatrixContainer* >(this)->impCheckDecompose(); return mfShearX; }
     };
+
+    /// Returns a string with svg's "matrix(m00,m10,m01,m11,m02,m12)" representation
+    ::rtl::OUString exportToSvg( const B2DHomMatrix& rMatrix );
+
 } // end of namespace basegfx
 
 ///////////////////////////////////////////////////////////////////////////////
diff --git a/basegfx/inc/basegfx/numeric/ftools.hxx b/basegfx/inc/basegfx/numeric/ftools.hxx
index 5003ede0c4cf..6cecbecc1f9f 100644
--- a/basegfx/inc/basegfx/numeric/ftools.hxx
+++ b/basegfx/inc/basegfx/numeric/ftools.hxx
@@ -112,7 +112,7 @@ namespace basegfx
 
     /** clamp given value against given minimum and maximum values
     */
-    template <class T> const T& clamp(const T& value, const T& minimum, const T& maximum)
+    template <class T> inline const T& clamp(const T& value, const T& minimum, const T& maximum)
     {
         if(value < minimum)
         {
diff --git a/basegfx/inc/basegfx/tools/gradienttools.hxx b/basegfx/inc/basegfx/tools/gradienttools.hxx
index 0c7f2ab2c060..dbcc5a3221f0 100644
--- a/basegfx/inc/basegfx/tools/gradienttools.hxx
+++ b/basegfx/inc/basegfx/tools/gradienttools.hxx
@@ -37,6 +37,9 @@
 #include <basegfx/matrix/b2dhommatrix.hxx>
 #include <basegfx/numeric/ftools.hxx>
 
+#include <vector>
+#include <algorithm>
+
 namespace basegfx
 {
     /** Gradient definition as used in ODF 1.2
@@ -78,6 +81,8 @@ namespace basegfx
     {
         /** Create matrix for ODF's linear gradient definition
 
+            Note that odf linear gradients are varying in y direction.
+
             @param o_rGradientInfo
             Receives the calculated texture transformation matrix (for
             use with standard [0,1]x[0,1] texture coordinates)
@@ -109,7 +114,7 @@ namespace basegfx
 
             @param rUV
             Current uv coordinate. Values outside [0,1] will be
-            clamped.
+            clamped. Assumes gradient color varies along the y axis.
 
             @param rGradInfo
             Gradient info, for transformation and number of steps
@@ -129,6 +134,14 @@ namespace basegfx
 
         /** Create matrix for ODF's axial gradient definition
 
+            Note that odf axial gradients are varying in y
+            direction. Note further that you can map the axial
+            gradient to a linear gradient (in case you want or need to
+            avoid an extra gradient renderer), by using
+            createLinearODFGradientInfo() instead, shifting the
+            resulting texture transformation by 0.5 to the top and
+            appending the same stop colors again, but mirrored.
+
             @param o_rGradientInfo
             Receives the calculated texture transformation matrix (for
             use with standard [0,1]x[0,1] texture coordinates)
@@ -160,7 +173,7 @@ namespace basegfx
 
             @param rUV
             Current uv coordinate. Values outside [0,1] will be
-            clamped.
+            clamped. Assumes gradient color varies along the y axis.
 
             @param rGradInfo
             Gradient info, for transformation and number of steps
@@ -394,7 +407,6 @@ namespace basegfx
         {
             return getSquareGradientAlpha(rUV, rGradInfo); // only matrix setup differs
         }
-
     }
 }
 
diff --git a/basegfx/inc/basegfx/tools/keystoplerp.hxx b/basegfx/inc/basegfx/tools/keystoplerp.hxx
new file mode 100644
index 000000000000..a54b3485b1a1
--- /dev/null
+++ b/basegfx/inc/basegfx/tools/keystoplerp.hxx
@@ -0,0 +1,100 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: canvastools.hxx,v $
+ * $Revision: 1.10 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#ifndef _BGFX_TOOLS_KEYSTOPLERP_HXX
+#define _BGFX_TOOLS_KEYSTOPLERP_HXX
+
+#include <basegfx/numeric/ftools.hxx>
+#include <vector>
+
+namespace com{ namespace sun{ namespace star{ namespace uno {
+    template<typename T> class Sequence;
+}}}}
+
+namespace basegfx
+{
+    namespace tools
+    {
+        /** Lerp in a vector of key stops
+
+            This class holds a key stop vector and provides the
+            functionality to lerp inside it. Useful e.g. for
+            multi-stop gradients, or the SMIL key time activity.
+
+            For those, given a global [0,1] lerp alpha, one need to
+            find the suitable bucket index from key stop vector, and
+            then calculate the relative alpha between the two buckets
+            found.
+         */
+        class KeyStopLerp
+        {
+        public:
+            typedef std::pair<std::ptrdiff_t,double> ResultType;
+
+            /** Create lerper with given vector of stops
+
+                @param rKeyStops
+
+                Vector of stops, must contain at least two elements
+                (though preferrably more, otherwise you probably don't
+                need key stop lerping in the first place). All
+                elements must be of monotonically increasing value.
+             */
+            explicit KeyStopLerp( const std::vector<double>& rKeyStops );
+
+            /** Create lerper with given sequence of stops
+
+                @param rKeyStops
+
+                Sequence of stops, must contain at least two elements
+                (though preferrably more, otherwise you probably don't
+                need key stop lerping in the first place). All
+                elements must be of monotonically increasing value.
+             */
+            explicit KeyStopLerp( const ::com::sun::star::uno::Sequence<double>& rKeyStops );
+
+            /** Find two nearest bucket index & interpolate
+
+                @param fAlpha
+                Find bucket index i, with keyStops[i] < fAlpha <=
+                keyStops[i+1]. Return new alpha value in [0,1),
+                proportional to fAlpha's position between keyStops[i]
+                and keyStops[i+1]
+             */
+            ResultType lerp(double fAlpha) const;
+
+        private:
+            std::vector<double>    maKeyStops;
+            mutable std::ptrdiff_t mnLastIndex;
+        };
+    }
+}
+
+#endif
diff --git a/basegfx/inc/basegfx/tools/lerp.hxx b/basegfx/inc/basegfx/tools/lerp.hxx
new file mode 100644
index 000000000000..590ef34c2009
--- /dev/null
+++ b/basegfx/inc/basegfx/tools/lerp.hxx
@@ -0,0 +1,60 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: lerp.hxx,v $
+ * $Revision: 1.6 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#ifndef _BGFX_TOOLS_LERP_HXX
+#define _BGFX_TOOLS_LERP_HXX
+
+#include <sal/types.h>
+
+namespace basegfx
+{
+    namespace tools
+    {
+        /** Generic linear interpolator
+
+            @tpl ValueType
+            Must have operator+ and operator* defined, and should
+            have value semantics.
+
+            @param t
+            As usual, t must be in the [0,1] range
+        */
+        template< typename ValueType > ValueType lerp( const ValueType&     rFrom,
+                                                       const ValueType&     rTo,
+                                                       double               t )
+        {
+            // This is only to suppress a double->int warning. All other
+            // types should be okay here.
+            return static_cast<ValueType>( (1.0-t)*rFrom + t*rTo );
+        }
+    }
+}
+
+#endif /* _BGFX_TOOLS_LERP_HXX */
diff --git a/basegfx/prj/d.lst b/basegfx/prj/d.lst
index a58cd33e4f9c..170796920945 100644
--- a/basegfx/prj/d.lst
+++ b/basegfx/prj/d.lst
@@ -89,6 +89,8 @@ mkdir: %_DEST%\inc%_EXT%\basegfx\tuple
 
 mkdir: %_DEST%\inc%_EXT%\basegfx\tools
 ..\inc\basegfx\tools\canvastools.hxx %_DEST%\inc%_EXT%\basegfx\tools\canvastools.hxx
+..\inc\basegfx\tools\keystoplerp.hxx %_DEST%\inc%_EXT%\basegfx\tools\keystoplerp.hxx
+..\inc\basegfx\tools\lerp.hxx %_DEST%\inc%_EXT%\basegfx\tools\lerp.hxx
 ..\inc\basegfx\tools\unopolypolygon.hxx %_DEST%\inc%_EXT%\basegfx\tools\unopolypolygon.hxx
 ..\inc\basegfx\tools\rectcliptools.hxx %_DEST%\inc%_EXT%\basegfx\tools\rectcliptools.hxx
 ..\inc\basegfx\tools\tools.hxx %_DEST%\inc%_EXT%\basegfx\tools\tools.hxx
diff --git a/basegfx/source/matrix/b2dhommatrixtools.cxx b/basegfx/source/matrix/b2dhommatrixtools.cxx
index 59a1ff432fc7..366a08a1d202 100644
--- a/basegfx/source/matrix/b2dhommatrixtools.cxx
+++ b/basegfx/source/matrix/b2dhommatrixtools.cxx
@@ -33,11 +33,39 @@
 #include "precompiled_basegfx.hxx"
 
 #include <basegfx/matrix/b2dhommatrixtools.hxx>
+#include <rtl/ustring.hxx>
+#include <rtl/ustrbuf.hxx>
 
 ///////////////////////////////////////////////////////////////////////////////
 
 namespace basegfx
 {
+    ::rtl::OUString exportToSvg( const B2DHomMatrix& rMatrix )
+    {
+        rtl::OUStringBuffer aStrBuf;
+        aStrBuf.appendAscii("matrix(");
+
+        aStrBuf.append(rMatrix.get(0,0));
+        aStrBuf.appendAscii(", ");
+
+        aStrBuf.append(rMatrix.get(1,0));
+        aStrBuf.appendAscii(", ");
+
+        aStrBuf.append(rMatrix.get(0,1));
+        aStrBuf.appendAscii(", ");
+
+        aStrBuf.append(rMatrix.get(1,1));
+        aStrBuf.appendAscii(", ");
+
+        aStrBuf.append(rMatrix.get(0,2));
+        aStrBuf.appendAscii(", ");
+
+        aStrBuf.append(rMatrix.get(1,2));
+        aStrBuf.appendAscii(")");
+
+        return aStrBuf.makeStringAndClear();
+    }
+
 } // end of namespace basegfx
 
 ///////////////////////////////////////////////////////////////////////////////
diff --git a/basegfx/source/tools/gradienttools.cxx b/basegfx/source/tools/gradienttools.cxx
index 9e78039cd590..337f9bd8e52b 100644
--- a/basegfx/source/tools/gradienttools.cxx
+++ b/basegfx/source/tools/gradienttools.cxx
@@ -52,6 +52,8 @@ namespace basegfx
         o_rGradientInfo.maBackTextureTransform.identity();
         o_rGradientInfo.mnSteps = nSteps;
 
+        fAngle = -fAngle;
+
         double fTargetSizeX(rTargetRange.getWidth());
         double fTargetSizeY(rTargetRange.getHeight());
         double fTargetOffsetX(rTargetRange.getMinX());
@@ -70,7 +72,23 @@ namespace basegfx
             fTargetSizeY = fNewY;
         }
 
-        // add object scale before rotate
+        double fSizeWithoutBorder=0;
+        double fTranslateY=0;
+        if( bAxial )
+        {
+            fSizeWithoutBorder = (1.0 - fBorder) * 0.5;
+            fTranslateY = 0.5;
+        }
+        else
+        {
+            fSizeWithoutBorder = 1.0 - fBorder;
+            fTranslateY = fBorder;
+        }
+
+        if(!fTools::equal(fSizeWithoutBorder, 0.0))
+            o_rGradientInfo.maTextureTransform.scale(1.0, fSizeWithoutBorder);
+
+        o_rGradientInfo.maTextureTransform.translate(0.0, fTranslateY);
         o_rGradientInfo.maTextureTransform.scale(fTargetSizeX, fTargetSizeY);
 
         // add texture rotate after scale to keep perpendicular angles
@@ -90,24 +108,9 @@ namespace basegfx
         // prepare aspect for texture
         o_rGradientInfo.mfAspectRatio = (0.0 != fTargetSizeY) ?  fTargetSizeX / fTargetSizeY : 1.0;
 
-        // build transform from u,v to [0.0 .. 1.0]. As base, use inverse texture transform
+        // build transform from u,v to [0.0 .. 1.0].
         o_rGradientInfo.maBackTextureTransform = o_rGradientInfo.maTextureTransform;
         o_rGradientInfo.maBackTextureTransform.invert();
-
-        double fSizeWithoutBorder=0;
-        if( bAxial )
-        {
-            fSizeWithoutBorder = (1.0 - fBorder) * 0.5;
-            o_rGradientInfo.maBackTextureTransform.translate(0.0, -0.5);
-        }
-        else
-        {
-            fSizeWithoutBorder = 1.0 - fBorder;
-            o_rGradientInfo.maBackTextureTransform.translate(0.0, -fBorder);
-        }
-
-        if(!fTools::equal(fSizeWithoutBorder, 0.0))
-            o_rGradientInfo.maBackTextureTransform.scale(1.0, 1.0 / fSizeWithoutBorder);
     }
 
     /** Most of the setup for radial & ellipsoidal gradient is the same,
@@ -125,6 +128,8 @@ namespace basegfx
         o_rGradientInfo.maBackTextureTransform.identity();
         o_rGradientInfo.mnSteps = nSteps;
 
+        fAngle = -fAngle;
+
         double fTargetSizeX(rTargetRange.getWidth());
         double fTargetSizeY(rTargetRange.getHeight());
         double fTargetOffsetX(rTargetRange.getMinX());
@@ -147,7 +152,11 @@ namespace basegfx
             fTargetSizeY = 1.4142 * fTargetSizeY;
         }
 
-        // add object scale before rotate
+        const double fHalfBorder((1.0 - fBorder) * 0.5);
+        if(!fTools::equal(fHalfBorder, 0.0))
+            o_rGradientInfo.maTextureTransform.scale(fHalfBorder, fHalfBorder);
+
+        o_rGradientInfo.maTextureTransform.translate(0.5, 0.5);
         o_rGradientInfo.maTextureTransform.scale(fTargetSizeX, fTargetSizeY);
 
         if( !bCircular )
@@ -155,9 +164,8 @@ namespace basegfx
             // add texture rotate after scale to keep perpendicular angles
             if(0.0 != fAngle)
             {
-                B2DPoint aCenter(0.5, 0.5);
-                aCenter *= o_rGradientInfo.maTextureTransform;
-
+                const B2DPoint aCenter(0.5*fTargetSizeX,
+                                       0.5*fTargetSizeY);
                 o_rGradientInfo.maTextureTransform.translate(-aCenter.getX(), -aCenter.getY());
                 o_rGradientInfo.maTextureTransform.rotate(fAngle);
                 o_rGradientInfo.maTextureTransform.translate(aCenter.getX(), aCenter.getY());
@@ -178,17 +186,9 @@ namespace basegfx
         // prepare aspect for texture
         o_rGradientInfo.mfAspectRatio = (0.0 != fTargetSizeY) ?  fTargetSizeX / fTargetSizeY : 1.0;
 
-        // build transform from u,v to [0.0 .. 1.0]. As base, use inverse texture transform
+        // build transform from u,v to [0.0 .. 1.0].
         o_rGradientInfo.maBackTextureTransform = o_rGradientInfo.maTextureTransform;
         o_rGradientInfo.maBackTextureTransform.invert();
-        o_rGradientInfo.maBackTextureTransform.translate(-0.5, -0.5);
-        const double fHalfBorder((1.0 - fBorder) * 0.5);
-
-        if(!fTools::equal(fHalfBorder, 0.0))
-        {
-            const double fFactor(1.0 / fHalfBorder);
-            o_rGradientInfo.maBackTextureTransform.scale(fFactor, fFactor);
-        }
     }
 
     /** Setup for rect & square gradient is exactly the same. Factored out
@@ -205,6 +205,8 @@ namespace basegfx
         o_rGradientInfo.maBackTextureTransform.identity();
         o_rGradientInfo.mnSteps = nSteps;
 
+        fAngle = -fAngle;
+
         double fTargetSizeX(rTargetRange.getWidth());
         double fTargetSizeY(rTargetRange.getHeight());
         double fTargetOffsetX(rTargetRange.getMinX());
@@ -223,15 +225,18 @@ namespace basegfx
             fTargetSizeY = fNewY;
         }
 
-        // add object scale before rotate
+        const double fHalfBorder((1.0 - fBorder) * 0.5);
+        if(!fTools::equal(fHalfBorder, 0.0))
+            o_rGradientInfo.maTextureTransform.scale(fHalfBorder, fHalfBorder);
+
+        o_rGradientInfo.maTextureTransform.translate(0.5, 0.5);
         o_rGradientInfo.maTextureTransform.scale(fTargetSizeX, fTargetSizeY);
 
         // add texture rotate after scale to keep perpendicular angles
         if(0.0 != fAngle)
         {
-            B2DPoint aCenter(0.5, 0.5);
-            aCenter *= o_rGradientInfo.maTextureTransform;
-
+            const B2DPoint aCenter(0.5*fTargetSizeX,
+                                   0.5*fTargetSizeY);
             o_rGradientInfo.maTextureTransform.translate(-aCenter.getX(), -aCenter.getY());
             o_rGradientInfo.maTextureTransform.rotate(fAngle);
             o_rGradientInfo.maTextureTransform.translate(aCenter.getX(), aCenter.getY());
@@ -254,14 +259,6 @@ namespace basegfx
         // build transform from u,v to [0.0 .. 1.0]. As base, use inverse texture transform
         o_rGradientInfo.maBackTextureTransform = o_rGradientInfo.maTextureTransform;
         o_rGradientInfo.maBackTextureTransform.invert();
-        o_rGradientInfo.maBackTextureTransform.translate(-0.5, -0.5);
-        const double fHalfBorder((1.0 - fBorder) * 0.5);
-
-        if(!fTools::equal(fHalfBorder, 0.0))
-        {
-            const double fFactor(1.0 / fHalfBorder);
-            o_rGradientInfo.maBackTextureTransform.scale(fFactor, fFactor);
-        }
     }
 
     namespace tools
diff --git a/basegfx/source/tools/keystoplerp.cxx b/basegfx/source/tools/keystoplerp.cxx
new file mode 100644
index 000000000000..99c74a350a69
--- /dev/null
+++ b/basegfx/source/tools/keystoplerp.cxx
@@ -0,0 +1,104 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: canvastools.hxx,v $
+ * $Revision: 1.10 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+#include "basegfx/tools/keystoplerp.hxx"
+#include <com/sun/star/uno/Sequence.hxx>
+
+#include <algorithm>
+
+static void validateInput(const std::vector<double>& rKeyStops)
+{
+    (void)rKeyStops;
+#ifdef DBG_UTIL
+    OSL_ENSURE( rKeyStops.size() > 1,
+                "KeyStopLerp::KeyStopLerp(): key stop vector must have two entries or more" );
+
+    // rKeyStops must be sorted in ascending order
+    for( ::std::size_t i=1, len=rKeyStops.size(); i<len; ++i )
+    {
+        if( rKeyStops[i-1] > rKeyStops[i] )
+            OSL_ENSURE( false,
+                        "KeyStopLerp::KeyStopLerp(): time vector is not sorted in ascending order!" );
+    }
+#endif
+}
+
+namespace basegfx
+{
+    namespace tools
+    {
+        KeyStopLerp::KeyStopLerp( const std::vector<double>& rKeyStops ) :
+            maKeyStops(rKeyStops),
+            mnLastIndex(0)
+        {
+            validateInput(maKeyStops);
+        }
+
+        KeyStopLerp::KeyStopLerp( const ::com::sun::star::uno::Sequence<double>& rKeyStops ) :
+            maKeyStops(rKeyStops.getLength()),
+            mnLastIndex(0)
+        {
+            std::copy( rKeyStops.getConstArray(),
+                       rKeyStops.getConstArray()+rKeyStops.getLength(),
+                       maKeyStops.begin() );
+            validateInput(maKeyStops);
+        }
+
+        KeyStopLerp::ResultType KeyStopLerp::lerp(double fAlpha) const
+        {
+            // cached value still okay?
+            if( maKeyStops.at(mnLastIndex) < fAlpha ||
+                maKeyStops.at(mnLastIndex+1) >= fAlpha )
+            {
+                // nope, find new index
+                mnLastIndex = std::min<std::ptrdiff_t>(
+                    maKeyStops.size()-2,
+                    // range is ensured by max below
+                    std::max<std::ptrdiff_t>(
+                        0,
+                        std::distance( maKeyStops.begin(),
+                                       std::lower_bound( maKeyStops.begin(),
+                                                         maKeyStops.end(),
+                                                         fAlpha )) - 1 ));
+            }
+
+            // lerp between stop and stop+1
+            const double fRawLerp=
+                (fAlpha-maKeyStops.at(mnLastIndex)) /
+                (maKeyStops.at(mnLastIndex+1) - maKeyStops.at(mnLastIndex));
+
+            // clamp to permissible range (input fAlpha might be
+            // everything)
+            return ResultType(
+                mnLastIndex,
+                clamp(fRawLerp,0.0,1.0));
+        }
+    }
+}
diff --git a/basegfx/source/tools/makefile.mk b/basegfx/source/tools/makefile.mk
index 1bede8b22d88..d55bbae12f8f 100755
--- a/basegfx/source/tools/makefile.mk
+++ b/basegfx/source/tools/makefile.mk
@@ -44,6 +44,7 @@ ENABLE_EXCEPTIONS=TRUE
 SLOFILES= $(SLO)$/canvastools.obj	\
           $(SLO)$/gradienttools.obj	\
           $(SLO)$/debugplotter.obj	\
+          $(SLO)$/keystoplerp.obj	\
           $(SLO)$/liangbarsky.obj	\
           $(SLO)$/tools.obj		    \
           $(SLO)$/unopolypolygon.obj
diff --git a/basegfx/test/basegfxtools.cxx b/basegfx/test/basegfxtools.cxx
new file mode 100644
index 000000000000..6ace65c5894d
--- /dev/null
+++ b/basegfx/test/basegfxtools.cxx
@@ -0,0 +1,119 @@
+/*************************************************************************
+ *
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * Copyright 2008 by Sun Microsystems, Inc.
+ *
+ * OpenOffice.org - a multi-platform office productivity suite
+ *
+ * $RCSfile: basegfx2d.cxx,v $
+ * $Revision: 1.14 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org.  If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_basegfx.hxx"
+// autogenerated file with codegen.pl
+
+#include <cppunit/simpleheader.hxx>
+
+#include <basegfx/tools/keystoplerp.hxx>
+#include <basegfx/numeric/ftools.hxx>
+
+#include <boost/tuple/tuple.hpp>
+
+using namespace ::basegfx;
+using namespace ::boost::tuples;
+
+namespace basegfxtools
+{
+
+class KeyStopLerpTest : public CppUnit::TestFixture
+{
+    tools::KeyStopLerp maKeyStops;
+
+    static std::vector<double> getTestVector()
+    {
+        std::vector<double> aStops(3);
+        aStops[0] = 0.1;
+        aStops[1] = 0.5;
+        aStops[2] = 0.9;
+        return aStops;
+    }
+
+public:
+    KeyStopLerpTest() :
+        maKeyStops(getTestVector())
+    {}
+
+    void setUp()
+    {}
+
+    void tearDown()
+    {}
+
+    void test()
+    {
+        double fAlpha;
+        std::ptrdiff_t nIndex;
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(-1.0);
+        CPPUNIT_ASSERT_MESSAGE("-1.0", nIndex==0 && fAlpha==0.0);
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(0.1);
+        CPPUNIT_ASSERT_MESSAGE("0.1", nIndex==0 && fAlpha==0.0);
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(0.3);
+        CPPUNIT_ASSERT_MESSAGE("0.3", nIndex==0 && fTools::equal(fAlpha,0.5));
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(0.5);
+        CPPUNIT_ASSERT_MESSAGE("0.5", nIndex==0 && fTools::equal(fAlpha,1.0));
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(0.51);
+        CPPUNIT_ASSERT_MESSAGE("0.51", nIndex==1 && fTools::equal(fAlpha,0.025));
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(0.9);
+        CPPUNIT_ASSERT_MESSAGE("0.51", nIndex==1 && fTools::equal(fAlpha,1.0));
+
+        tie(nIndex,fAlpha) = maKeyStops.lerp(1.0);
+        CPPUNIT_ASSERT_MESSAGE("0.51", nIndex==1 && fAlpha==1.0);
+    }
+
+    // Change the following lines only, if you add, remove or rename
+    // member functions of the current class,
+    // because these macros are need by auto register mechanism.
+
+    CPPUNIT_TEST_SUITE(KeyStopLerpTest);
+    CPPUNIT_TEST(test);
+    CPPUNIT_TEST_SUITE_END();
+};
+
+// -----------------------------------------------------------------------------
+CPPUNIT_TEST_SUITE_NAMED_REGISTRATION(basegfxtools::KeyStopLerpTest, "basegfxtools");
+} // namespace basegfxtools
+
+
+// -----------------------------------------------------------------------------
+
+// this macro creates an empty function, which will called by the RegisterAllFunctions()
+// to let the user the possibility to also register some functions by hand.
+// NOADDITIONAL;
+
diff --git a/basegfx/test/makefile.mk b/basegfx/test/makefile.mk
index 1bd4d59b98d5..bc44daffd27c 100644
--- a/basegfx/test/makefile.mk
+++ b/basegfx/test/makefile.mk
@@ -46,6 +46,7 @@ SHL1OBJS=  \
     $(SLO)$/basegfx1d.obj \
     $(SLO)$/basegfx2d.obj \
     $(SLO)$/basegfx3d.obj \
+    $(SLO)$/basegfxtools.obj \
     $(SLO)$/testtools.obj	
 
 # linking statically against basegfx parts