To help the SVG WG discussion on powerstroke, a quick code-up of centripetal Catmull-Rom interpolation. The code probably needs a clean up pass, and more generally, the interpolation functions should move into 2geom or at least into a .cpp file.

- Add Catmull-Rom interpolation to powerstroke interpolation options
- Add LPE Interpolate points

(bzr r13341.1.156)

5 files changed, 90 insertions, 3 deletions

diff --git a/src/live_effects/Makefile_insert b/src/live_effects/Makefile_insert
index e9609a4aa..1b8f587e1 100644
--- a/src/live_effects/Makefile_insert
+++ b/src/live_effects/Makefile_insert
@@ -38,6 +38,8 @@ ink_common_sources += \
 	live_effects/lpe-gears.h	\
 	live_effects/lpe-interpolate.cpp	\
 	live_effects/lpe-interpolate.h	\
+	live_effects/lpe-interpolate_points.cpp	\
+	live_effects/lpe-interpolate_points.h	\
 	live_effects/lpe-test-doEffect-stack.cpp	\
 	live_effects/lpe-test-doEffect-stack.h	\
 	live_effects/lpe-bspline.cpp	\
diff --git a/src/live_effects/effect-enum.h b/src/live_effects/effect-enum.h
index bc77d65c3..30dbf4092 100644
--- a/src/live_effects/effect-enum.h
+++ b/src/live_effects/effect-enum.h
@@ -45,6 +45,7 @@ enum EffectType {
     RULER,
     BOOLOPS,
     INTERPOLATE,
+    INTERPOLATE_POINTS,
     TEXT_LABEL,
     PATH_LENGTH,
     LINE_SEGMENT,
diff --git a/src/live_effects/effect.cpp b/src/live_effects/effect.cpp
index dc61701df..540eb99d4 100644
--- a/src/live_effects/effect.cpp
+++ b/src/live_effects/effect.cpp
@@ -43,6 +43,7 @@
 #include "live_effects/lpe-ruler.h"
 #include "live_effects/lpe-boolops.h"
 #include "live_effects/lpe-interpolate.h"
+#include "live_effects/lpe-interpolate_points.h"
 #include "live_effects/lpe-text_label.h"
 #include "live_effects/lpe-path_length.h"
 #include "live_effects/lpe-line_segment.h"
@@ -127,6 +128,7 @@ const Util::EnumData<EffectType> LPETypeData[] = {
 /* 0.91 */
     {POWERSTROKE,           N_("Power stroke"),            "powerstroke"},
     {CLONE_ORIGINAL,        N_("Clone original path"),     "clone_original"},
+/* EXPERIMENTAL */    
     {SHOW_HANDLES,          N_("Show handles"),            "show_handles"},
     {ROUGHEN,               N_("Roughen"),                 "roughen"},
     {BSPLINE,               N_("BSpline"),                 "bspline"},
@@ -135,6 +137,7 @@ const Util::EnumData<EffectType> LPETypeData[] = {
     // TRANSLATORS: "Envelope Perspective" should be equivalent to "perspective transformation"
     {ENVELOPE_PERSPECTIVE,  N_("Envelope Perspective"),    "envelope-perspective"},
     {FILLET_CHAMFER,        N_("Fillet/Chamfer"),          "fillet-chamfer"},
+    {INTERPOLATE_POINTS,    N_("Interpolate points"),      "interpolate_points"},
 };
 const Util::EnumDataConverter<EffectType> LPETypeConverter(LPETypeData, sizeof(LPETypeData)/sizeof(*LPETypeData));
 
@@ -231,6 +234,9 @@ Effect::New(EffectType lpenr, LivePathEffectObject *lpeobj)
         case INTERPOLATE:
             neweffect = static_cast<Effect*> ( new LPEInterpolate(lpeobj) );
             break;
+        case INTERPOLATE_POINTS:
+            neweffect = static_cast<Effect*> ( new LPEInterpolatePoints(lpeobj) );
+            break;
         case TEXT_LABEL:
             neweffect = static_cast<Effect*> ( new LPETextLabel(lpeobj) );
             break;
diff --git a/src/live_effects/lpe-powerstroke-interpolators.h b/src/live_effects/lpe-powerstroke-interpolators.h
index 6f5b75af8..f08259eb3 100644
--- a/src/live_effects/lpe-powerstroke-interpolators.h
+++ b/src/live_effects/lpe-powerstroke-interpolators.h
@@ -27,7 +27,8 @@ enum InterpolatorType {
   INTERP_LINEAR,
   INTERP_CUBICBEZIER,
   INTERP_CUBICBEZIER_JOHAN,
-  INTERP_SPIRO
+  INTERP_SPIRO,
+  INTERP_CENTRIPETAL_CATMULLROM
 };
 
 class Interpolator {
@@ -168,7 +169,81 @@ private:
 };
 
 
-Interpolator*
+// Quick mockup for testing the behavior for powerstroke controlpoint interpolation
+class CentripetalCatmullRomInterpolator : public Interpolator {
+public:
+    CentripetalCatmullRomInterpolator() {};
+    virtual ~CentripetalCatmullRomInterpolator() {};
+
+    virtual Path interpolateToPath(std::vector<Point> const &points) const {
+        unsigned int n_points = points.size();
+
+        Geom::Path fit(points.front());
+
+        if (n_points < 3) return fit; // TODO special cases for 0,1 and 2 input points
+
+        // return n_points-1 cubic segments
+
+        // duplicate first point
+        fit.append(calc_bezier(points[0],points[0],points[1],points[2]));
+
+        for (std::size_t i = 0; i < n_points-2; ++i) {
+            Point p0 = points[i];
+            Point p1 = points[i+1];
+            Point p2 = points[i+2];
+            Point p3 = (i < n_points-3) ? points[i+3] : points[i+2];
+
+            fit.append(calc_bezier(p0, p1, p2, p3));
+        }
+
+        return fit;
+    };
+
+private:
+    CubicBezier calc_bezier(Point p0, Point p1, Point p2, Point p3) const {
+        // create interpolating bezier between p1 and p2
+
+        // calculate time coords (deltas) of points
+        double dt0 = powf(distanceSq(p0, p1), 0.25);
+        double dt1 = powf(distanceSq(p1, p2), 0.25);
+        double dt2 = powf(distanceSq(p2, p3), 0.25);
+
+        // safety check for repeated points
+        double eps = Geom::EPSILON;
+        if (dt1 < eps)
+            dt1 = 1.0;
+        if (dt0 < eps)
+            dt0 = dt1;
+        if (dt2 < eps)
+            dt2 = dt1;
+
+        // compute tangents when parameterized in [t1,t2]
+        Point tan1 = (p1 - p0) / dt0 - (p2 - p0) / (dt0 + dt1) + (p2 - p1) / dt1;
+        Point tan2 = (p2 - p1) / dt1 - (p3 - p1) / (dt1 + dt2) + (p3 - p2) / dt2;
+        // rescale tangents for parametrization in [0,1]
+        tan1 *= dt1;
+        tan2 *= dt1;
+
+        // create bezier from tangents (this is already in 2geom somewhere, or should be moved to it)
+        // the tangent of a bezier curve is: B'(t) = 3(1-t)^2 (b1 - b0) + 6(1-t)t(b2-b1) + 3t^2(b3-b2)
+        // So we have to make sure that B'(0) = tan1  and  B'(1) = tan2, and we already know that b0=p1 and b3=p2
+        // tan1 = B'(0) = 3 (b1 - p1)  --> p1 + (tan1)/3 = b1
+        // tan2 = B'(1) = 3 (p2 - b2)  --> p2 - (tan2)/3 = b2
+
+        Point b0 = p1;
+        Point b1 = p1 + tan1 / 3;
+        Point b2 = p2 - tan2 / 3;
+        Point b3 = p2;
+
+        return CubicBezier(b0, b1, b2, b3);
+    }
+
+    CentripetalCatmullRomInterpolator(const CentripetalCatmullRomInterpolator&);
+    CentripetalCatmullRomInterpolator& operator=(const CentripetalCatmullRomInterpolator&);
+};
+
+
+inline Interpolator*
 Interpolator::create(InterpolatorType type) {
     switch (type) {
       case INTERP_LINEAR:
@@ -179,6 +254,8 @@ Interpolator::create(InterpolatorType type) {
         return new Geom::Interpolate::CubicBezierJohan();
       case INTERP_SPIRO:
         return new Geom::Interpolate::SpiroInterpolator();
+      case INTERP_CENTRIPETAL_CATMULLROM:
+        return new Geom::Interpolate::CentripetalCatmullRomInterpolator();
       default:
         return new Geom::Interpolate::Linear();
     }
diff --git a/src/live_effects/lpe-powerstroke.cpp b/src/live_effects/lpe-powerstroke.cpp
index 90b01aaa4..5bfe88ed1 100644
--- a/src/live_effects/lpe-powerstroke.cpp
+++ b/src/live_effects/lpe-powerstroke.cpp
@@ -188,7 +188,8 @@ static const Util::EnumData<unsigned> InterpolatorTypeData[] = {
     {Geom::Interpolate::INTERP_LINEAR          , N_("Linear"), "Linear"},
     {Geom::Interpolate::INTERP_CUBICBEZIER          , N_("CubicBezierFit"), "CubicBezierFit"},
     {Geom::Interpolate::INTERP_CUBICBEZIER_JOHAN     , N_("CubicBezierJohan"), "CubicBezierJohan"},
-    {Geom::Interpolate::INTERP_SPIRO  , N_("SpiroInterpolator"), "SpiroInterpolator"}
+    {Geom::Interpolate::INTERP_SPIRO  , N_("SpiroInterpolator"), "SpiroInterpolator"},
+    {Geom::Interpolate::INTERP_CENTRIPETAL_CATMULLROM, N_("Centripetal Catmull-Rom"), "CentripetalCatmullRom"}
 };
 static const Util::EnumDataConverter<unsigned> InterpolatorTypeConverter(InterpolatorTypeData, sizeof(InterpolatorTypeData)/sizeof(*InterpolatorTypeData));