git.sesse.net Git - vlc/blob - modules/gui/skins2/utils/bezier.cpp

   1 /*****************************************************************************
   2  * bezier.cpp
   3  *****************************************************************************
   4  * Copyright (C) 2003 the VideoLAN team
   5  * $Id$
   6  *
   7  * Authors: Cyril Deguet     <asmax@via.ecp.fr>
   8  *          Olivier Teulière <ipkiss@via.ecp.fr>
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
  23  *****************************************************************************/
  24
  25 #include <vlc/vlc.h>
  26 #include "bezier.hpp"
  27 #include <math.h>
  28
  29 #ifndef HAVE_LRINTF
  30 #   define lrintf(a) (int)rint(a)
  31 #endif
  32
  33 Bezier::Bezier( intf_thread_t *p_intf, const vector<float> &rAbscissas,
  34                 const vector<float> &rOrdinates, Flag_t flag )
  35     : SkinObject( p_intf )
  36 {
  37     // Copy the control points coordinates
  38     m_ptx.assign( rAbscissas.begin(), rAbscissas.end() );
  39     m_pty.assign( rOrdinates.begin(), rOrdinates.end() );
  40
  41     // We expect m_ptx and m_pty to have the same size, of course
  42     m_nbCtrlPt = m_ptx.size();
  43
  44     // Precalculate the factoriels
  45     m_ft.push_back( 1 );
  46     for( int i = 1; i < m_nbCtrlPt; i++ )
  47     {
  48         m_ft.push_back( i * m_ft[i - 1] );
  49     }
  50
  51     // Calculate the first point
  52     int oldx, oldy;
  53     computePoint( 0, oldx, oldy );
  54     m_leftVect.push_back( oldx );
  55     m_topVect.push_back( oldy );
  56     m_percVect.push_back( 0 );
  57
  58     // Calculate the other points
  59     float percentage;
  60     int cx, cy;
  61     for( float j = 1; j <= MAX_BEZIER_POINT; j++ )
  62     {
  63         percentage = j / MAX_BEZIER_POINT;
  64         computePoint( percentage, cx, cy );
  65         if( ( flag == kCoordsBoth && ( cx != oldx || cy != oldy ) ) ||
  66             ( flag == kCoordsX && cx != oldx ) ||
  67             ( flag == kCoordsY && cy != oldy ) )
  68         {
  69             m_percVect.push_back( percentage );
  70             m_leftVect.push_back( cx );
  71             m_topVect.push_back( cy );
  72             oldx = cx;
  73             oldy = cy;
  74         }
  75     }
  76     m_nbPoints = m_leftVect.size();
  77
  78     // If we have only one control point, we duplicate it
  79     // This allows to simplify the algorithms used in the class
  80     if( m_nbPoints == 1 )
  81     {
  82         m_leftVect.push_back( m_leftVect[0] );
  83         m_topVect.push_back( m_topVect[0] );
  84         m_percVect.push_back( 1 );
  85         m_nbPoints = 2;
  86    }
  87
  88     // Ensure that the percentage of the last point is always 1
  89     m_percVect[m_nbPoints - 1] = 1;
  90 }
  91
  92
  93 float Bezier::getNearestPercent( int x, int y ) const
  94 {
  95     int nearest = findNearestPoint( x, y );
  96     return m_percVect[nearest];
  97 }
  98
  99
 100 float Bezier::getMinDist( int x, int y ) const
 101 {
 102     int nearest = findNearestPoint( x, y );
 103     return sqrt( (m_leftVect[nearest] - x) * (m_leftVect[nearest] - x) +
 104                  (m_topVect[nearest] - y) * (m_topVect[nearest] - y) );
 105 }
 106
 107
 108 void Bezier::getPoint( float t, int &x, int &y ) const
 109 {
 110     // Find the precalculated point whose percentage is nearest from t
 111     int refPoint = 0;
 112     float minDiff = fabs( m_percVect[0] - t );
 113
 114     // The percentages are stored in increasing order, so we can stop the loop
 115     // as soon as 'diff' starts increasing
 116     float diff;
 117     while( refPoint < m_nbPoints &&
 118            (diff = fabs( m_percVect[refPoint] - t )) <= minDiff )
 119     {
 120         refPoint++;
 121         minDiff = diff;
 122     }
 123
 124     // The searched point is then (refPoint - 1)
 125     // We know that refPoint > 0 because we looped at least once
 126     x = m_leftVect[refPoint - 1];
 127     y = m_topVect[refPoint - 1];
 128 }
 129
 130
 131 int Bezier::getWidth() const
 132 {
 133     int width = 0;
 134     for( int i = 0; i < m_nbPoints; i++ )
 135     {
 136         if( m_leftVect[i] >= width )
 137         {
 138             width = m_leftVect[i] + 1;
 139         }
 140     }
 141     return width;
 142 }
 143
 144
 145 int Bezier::getHeight() const
 146 {
 147     int height = 0;
 148     for( int i = 0; i < m_nbPoints; i++ )
 149     {
 150         if( m_topVect[i] >= height )
 151         {
 152             height = m_topVect[i] + 1;
 153         }
 154     }
 155     return height;
 156 }
 157
 158
 159 int Bezier::findNearestPoint( int x, int y ) const
 160 {
 161     // The distance to the first point is taken as the reference
 162     int refPoint = 0;
 163     int minDist = (m_leftVect[0] - x) * (m_leftVect[0] - x) +
 164                   (m_topVect[0] - y) * (m_topVect[0] - y);
 165
 166     int dist;
 167     for( int i = 1; i < m_nbPoints; i++ )
 168     {
 169         dist = (m_leftVect[i] - x) * (m_leftVect[i] - x) +
 170                (m_topVect[i] - y) * (m_topVect[i] - y);
 171         if( dist < minDist )
 172         {
 173             minDist = dist;
 174             refPoint = i;
 175         }
 176     }
 177
 178     return refPoint;
 179 }
 180
 181
 182 void Bezier::computePoint( float t, int &x, int &y ) const
 183 {
 184     // See http://astronomy.swin.edu.au/~pbourke/curves/bezier/ for a simple
 185     // explanation of the algorithm
 186     float xPos = 0;
 187     float yPos = 0;
 188     float coeff;
 189     for( int i = 0; i < m_nbCtrlPt; i++ )
 190     {
 191         coeff = computeCoeff( i, m_nbCtrlPt - 1, t );
 192         xPos += m_ptx[i] * coeff;
 193         yPos += m_pty[i] * coeff;
 194     }
 195
 196     x = lrintf(xPos);
 197     y = lrintf(yPos);
 198 }
 199
 200
 201 inline float Bezier::computeCoeff( int i, int n, float t ) const
 202 {
 203     return (power( t, i ) * power( 1 - t, (n - i) ) *
 204         (m_ft[n] / m_ft[i] / m_ft[n - i]));
 205 }
 206
 207
 208 inline float Bezier::power( float x, int n ) const
 209 {
 210     if( n > 0 )
 211         return x * power( x, n - 1);
 212     else
 213         return 1;
 214 }