001/*
002 * SVG Salamander
003 * Copyright (c) 2004, Mark McKay
004 * All rights reserved.
005 *
006 * Redistribution and use in source and binary forms, with or 
007 * without modification, are permitted provided that the following
008 * conditions are met:
009 *
010 *   - Redistributions of source code must retain the above 
011 *     copyright notice, this list of conditions and the following
012 *     disclaimer.
013 *   - Redistributions in binary form must reproduce the above
014 *     copyright notice, this list of conditions and the following
015 *     disclaimer in the documentation and/or other materials 
016 *     provided with the distribution.
017 *
018 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
019 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
020 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
021 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
022 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
023 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
025 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
026 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
027 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
028 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
029 * OF THE POSSIBILITY OF SUCH DAMAGE. 
030 * 
031 * Mark McKay can be contacted at mark@kitfox.com.  Salamander and other
032 * projects can be found at http://www.kitfox.com
033 *
034 * Created on January 14, 2005, 4:08 AM
035 */
036
037package com.kitfox.svg.animation;
038
039import java.awt.geom.*;
040
041/**
042 * http://mathworld.wolfram.com/BezierCurve.html
043 * @author kitfox
044 */
045public class Bezier
046{
047    double length;
048    double[] coord;
049
050    public Bezier(double sx, double sy, double[] coords, int numCoords)
051    {
052        setCoords(sx, sy, coords, numCoords);
053    }
054    
055    public void setCoords(double sx, double sy, double[] coords, int numCoords)
056    {
057        coord = new double[numCoords * 2 + 2];
058        coord[0] = sx;
059        coord[1] = sy;
060        for (int i = 0; i < numCoords; i++)
061        {
062            coord[i * 2 + 2] = coords[i * 2];
063            coord[i * 2 + 3] = coords[i * 2 + 1];
064        }
065        
066        calcLength();        
067    }
068    
069    /**
070     * Retuns aproximation of the length of the bezier
071     */
072    public double getLength()
073    {
074        return length;
075    }
076    
077    private void calcLength()
078    {
079        length = 0;
080        for (int i = 2; i < coord.length; i += 2)
081        {
082            length += lineLength(coord[i - 2], coord[i - 1], coord[i], coord[i + 1]);
083        }
084    }
085    
086    private double lineLength(double x1, double y1, double x2, double y2)
087    {
088        double dx = x2 - x1, dy = y2 - y1;
089        return Math.sqrt(dx * dx + dy * dy);
090    }
091    
092    public Point2D.Double getFinalPoint(Point2D.Double point)
093    {
094        point.x = coord[coord.length - 2];
095        point.y = coord[coord.length - 1];
096        return point;
097    }
098    
099    public Point2D.Double eval(double param, Point2D.Double point)
100    {
101        point.x = 0;
102        point.y = 0;
103        int numKnots = coord.length / 2;
104        
105        for (int i = 0; i < numKnots; i++)
106        {
107            double scale = bernstein(numKnots - 1, i, param);
108            point.x += coord[i * 2] * scale;
109            point.y += coord[i * 2 + 1] * scale;
110        }
111        
112        return point;
113    }
114    
115    /**
116     * Calculates the bernstein polynomial for evaluating parametric bezier
117     * @param numKnots - one less than number of knots in this curve hull
118     * @param knotNo - knot we are evaluating Bernstein for
119     * @param param - Parametric value we are evaluating at
120     */
121    private double bernstein(int numKnots, int knotNo, double param)
122    {
123        double iParam = 1 - param;
124        //Faster evaluation for easy cases:
125        switch (numKnots)
126        {
127            case 0:
128                return 1;
129            case 1:
130            {
131                switch (knotNo)
132                {
133                    case 0:
134                        return iParam;
135                    case 1:
136                        return param;
137                }
138                break;
139            }
140            case 2:
141            {
142                switch (knotNo)
143                {
144                    case 0:
145                        return iParam * iParam;
146                    case 1:
147                        return 2 * iParam * param;
148                    case 2:
149                        return param * param;
150                }
151                break;
152            }
153            case 3:
154            {
155                switch (knotNo)
156                {
157                    case 0:
158                        return iParam * iParam * iParam;
159                    case 1:
160                        return 3 * iParam * iParam * param;
161                    case 2:
162                        return 3 * iParam * param * param;
163                    case 3:
164                        return param * param * param;
165                }
166                break;
167            }
168        }
169        
170        //If this bezier has more than four points, calculate bernstein the hard way
171        double retVal = 1;
172        for (int i = 0; i < knotNo; i++)
173        {
174            retVal *= param;
175        }
176        for (int i = 0; i < numKnots - knotNo; i++)
177        {
178            retVal *= iParam;
179        }
180        retVal *= choose(numKnots, knotNo);
181        
182        return retVal;
183    }
184    
185    
186    
187    private int choose(int num, int denom)
188    {
189        int denom2 = num - denom;
190        if (denom < denom2)
191        {
192            int tmp = denom;
193            denom = denom2;
194            denom2 = tmp;
195        }
196        
197        int prod = 1;
198        for (int i = num; i > denom; i--)
199        {
200            prod *= num;
201        }
202        
203        for (int i = 2; i <= denom2; i++)
204        {
205            prod /= i;
206        }
207        
208        return prod;
209    }
210}