pdf2swf/spline.cc

   1 /* spline.cc
   2    Routine to convert cubic splines into quadratic ones.
   3
   4    Part of the swftools package.
   5
   6    Copyright (c) 2001 Matthias Kramm <kramm@quiss.org>
   7
   8    This file is distributed under the GPL, see file COPYING for details */
   9
  10 /* At the moment, we convert non-recursively into at max. 6 quadratic splines,
  11    trying to maintain the general structure of the curve, rather than it's
  12    exact path.
  13    To accomplish this, we split each curve at it's X,Y extremas as well as
  14    its deviation's X,Y extremas.
  15  */
  16
  17 #include <math.h>
  18 #include "spline.h"
  19
  20 int solve(double a,double b,double c, double*dd)
  21 {
  22     double det=b*b-4*a*c;
  23     int pos = 0;
  24     if(det<0) return 0; // we don't do imaginary. not today.
  25     if(det==0) { // unlikely, but we have to deal with it.
  26      dd[0]=-b/2*a;
  27      return (dd[0]>0 && dd[0]<1);
  28     }
  29
  30     dd[pos]=(-b+sqrt(det))/(2*a);
  31     if(dd[pos]>0 && dd[pos]<1)
  32      pos++;
  33     dd[pos]=(-b-sqrt(det))/(2*a);
  34     if(dd[pos]>0 && dd[pos]<1)
  35      pos++;
  36     return pos;
  37 }
  38
  39 struct plotxy splinepos(struct plotxy p0, struct plotxy p1, struct plotxy p2, struct plotxy p3, double d) {
  40     struct plotxy p;
  41     p.x = (p0.x * d*d*d + p1.x * 3*(1-d)*d*d + p2.x * 3*(1-d)*(1-d)*d + p3.x * (1-d)*(1-d)*(1-d));
  42     p.y = (p0.y * d*d*d + p1.y * 3*(1-d)*d*d + p2.y * 3*(1-d)*(1-d)*d + p3.y * (1-d)*(1-d)*(1-d));
  43     return p;
  44 }
  45
  46 double distance(struct plotxy p0, struct plotxy p1)
  47 {
  48  double xd=p1.x-p0.x;
  49  double yd=p1.y-p0.y;
  50  return sqrt(xd*xd+yd*yd);
  51 }
  52
  53 int wp(double p0,double p1,double p2,double p3,double*dd)
  54 {
  55     double div= (6*p0-18*p1+18*p2-6*p3);
  56     if(!div) return 0;
  57     dd[0] = -(6*p1-12*p2+6*p3)/div;
  58     return (dd[0]>0 && dd[0]<1);
  59 }
  60
  61 int approximate(struct plotxy p0, struct plotxy p1,
  62                 struct plotxy p2, struct plotxy p3, struct qspline*q)
  63 {
  64     double roots[12];
  65     int pos = 0;
  66     int s,t;
  67     struct plotxy myxy[12];
  68     struct plotxy last;
  69     // the parameters for the solve function are the 1st deviation of a cubic spline
  70     roots[pos] = 0;pos++;
  71     pos += solve(3*p0.x-9*p1.x+9*p2.x-3*p3.x, 6*p1.x-12*p2.x+6*p3.x,3*p2.x-3*p3.x, &roots[pos]);
  72     pos += solve(3*p0.y-9*p1.y+9*p2.y-3*p3.y, 6*p1.y-12*p2.y+6*p3.y,3*p2.y-3*p3.y, &roots[pos]);
  73     pos += wp(p0.x,p1.x,p2.x,p3.x,&roots[pos]);
  74     pos += wp(p0.x,p1.x,p2.x,p3.x,&roots[pos]);
  75     roots[pos] = 1;pos++;
  76
  77     // bubblesort - fast enough for 4-6 parameters
  78     for(s=0;s<pos;s++)
  79     for(t=s+1;t<pos;t++)
  80     if(roots[s]>roots[t])
  81     {
  82        double tmp=roots[s];
  83        roots[s]=roots[t];
  84        roots[t]=tmp;
  85     }
  86     for(t=0;t<pos;t++)
  87      myxy[t] = splinepos(p0,p1,p2,p3,roots[t]);
  88
  89     s=1;
  90     last = myxy[0];
  91     for(t=1;t<pos;t++)
  92     {
  93        double dist=distance(myxy[t],last);
  94        myxy[s]=myxy[t];
  95        roots[s]=roots[t];
  96        if(dist>0.01 || t==pos-1)
  97        {
  98         s++;
  99         last=myxy[t];
 100        }
 101     }
 102     pos = s;
 103
 104     // try 1:curve through 3 points, using the middle of the cubic spline.
 105     for(t=0;t<pos-1;t++) {
 106 //     circle(myxy[t].x,myxy[t].y,5);
 107      struct plotxy control;
 108      struct plotxy midpoint = splinepos(p0,p1,p2,p3,(roots[t]+roots[t+1])/2);
 109      control.x = midpoint.x + (midpoint.x-(myxy[t].x+myxy[t+1].x)/2);
 110      control.y = midpoint.y + (midpoint.y-(myxy[t].y+myxy[t+1].y)/2);
 111      //qspline(myxy[t],control,myxy[t+1]);
 112      q[t].start=myxy[t];
 113      q[t].control=control;
 114      q[t].end=myxy[t+1];
 115     }
 116
 117     /*
 118     for(t=0;t<pos-1;t++) {
 119      plotxy control;
 120      vga.setcolor(0xffffff);
 121      circle(myxy[t].x,myxy[t].y,5);
 122      if(t==0) {
 123        //double lenmain = distance(p3,p0);
 124        //double lenq = distance(myxy[0],myxy[1]);
 125        //control.x = myxy[0].x + (p2.x-p3.x);// /lenmain*lenq;
 126        //control.y = myxy[0].y + (p2.y-p3.y);// /lenmain*lenq;
 127        plotxy midpoint = splinepos(p0,p1,p2,p3,(roots[t]+roots[t+1])/2);
 128        control.x = midpoint.x + (midpoint.x-(myxy[t].x+myxy[t+1].x)/2);
 129        control.y = midpoint.y + (midpoint.y-(myxy[t].y+myxy[t+1].y)/2);
 130        qspline(myxy[0], control, myxy[1]);
 131      } else {
 132        control.x = 2*myxy[t].x - last.x;
 133        control.y = 2*myxy[t].y - last.y;
 134        qspline(myxy[t], control, myxy[t+1]);
 135      }
 136      last = control;
 137     }*/
 138     return pos-1;
 139 }
 140