dali/public-api/geometry/spline.cpp

   1 /*
   2  * Copyright (c) 2014 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 // CLASS HEADER
  19 #include <dali/public-api/geometry/spline.h>
  20
  21 // INTERNAL INCLUDES
  22 #include <dali/public-api/common/constants.h>
  23 #include <dali/public-api/common/dali-common.h>
  24 #include <dali/public-api/math/math-utils.h>
  25
  26 namespace
  27 {
  28 const int MAXIMUM_ITERATIONS=1000;
  29 }
  30
  31 namespace Dali
  32 {
  33
  34 /**
  35  * These basis matrices arise from the cubic polynomial equations for each
  36  * spline type. See Collada 1.4.1 specification for more information
  37  */
  38 const float Spline::BezierBasisA[] = {-1.0f,  3.0f, -3.0f, 1.0f,
  39                                        3.0f, -6.0f,  3.0f, 0.0f,
  40                                       -3.0f,  3.0f,  0.0f, 0.0f,
  41                                        1.0f,  0.0f,  0.0f, 0.0f  };
  42
  43
  44 Spline::Spline()
  45   : mBasis(BezierBasisA)
  46 {
  47 }
  48
  49 Spline::~Spline()
  50 {
  51 }
  52
  53 void Spline::AddKnot(Vector3 knot)
  54 {
  55   mKnots.push_back(knot);
  56   mInTangents.push_back(Vector3());
  57   mOutTangents.push_back(Vector3());
  58 }
  59
  60
  61 void Spline::SetInTangent(size_t knotIndex, Vector3 inTangent)
  62 {
  63   DALI_ASSERT_ALWAYS( knotIndex < mInTangents.size() && "knotIndex out of bounds" );
  64   mInTangents[knotIndex] = inTangent;
  65 }
  66
  67 void Spline::SetOutTangent(size_t knotIndex, Vector3 outTangent)
  68 {
  69   DALI_ASSERT_ALWAYS( knotIndex < mOutTangents.size() && "knotIndex out of bounds" );
  70   mOutTangents[knotIndex] = outTangent;
  71 }
  72
  73 Vector3 Spline::GetKnot(size_t knotIndex)
  74 {
  75   DALI_ASSERT_ALWAYS( knotIndex < mKnots.size() && "knotIndex out of bounds" );
  76   return mKnots[knotIndex];
  77 }
  78
  79 Vector3 Spline::GetInTangent(size_t knotIndex)
  80 {
  81   DALI_ASSERT_ALWAYS( knotIndex < mInTangents.size() && "knotIndex out of bounds" );
  82   return mInTangents[knotIndex];
  83 }
  84
  85 Vector3 Spline::GetOutTangent(size_t knotIndex)
  86 {
  87   DALI_ASSERT_ALWAYS( knotIndex < mOutTangents.size() && "knotIndex out of bounds" );
  88   return mOutTangents[knotIndex];
  89 }
  90
  91 void Spline::GenerateControlPoints(float curvature)
  92 {
  93   size_t numKnots = mKnots.size();
  94   DALI_ASSERT_ALWAYS( numKnots > 1 && "Need at least 1 segment to generate control points" ); // need at least 1 segment
  95
  96   for(size_t knotIndex = 0; knotIndex < numKnots; knotIndex++)
  97   {
  98     Vector3 curPoint = mKnots[knotIndex];
  99     Vector3 prevPoint, nextPoint;
 100     if(knotIndex == 0)
 101     {
 102       // create a dummy point
 103       Vector3 nextPoint = mKnots[1];
 104       prevPoint = curPoint - (nextPoint - curPoint)/8.0f;
 105     }
 106     else
 107     {
 108       prevPoint = mKnots[knotIndex-1];
 109     }
 110
 111     if(knotIndex == numKnots-1)
 112     {
 113       // create a dummy point
 114       nextPoint = curPoint - (prevPoint - curPoint)/8.0f;
 115     }
 116     else
 117     {
 118       nextPoint = mKnots[knotIndex+1];
 119     }
 120
 121     Vector3 a = curPoint - prevPoint;
 122     Vector3 b = nextPoint - curPoint;
 123     float aLength = a.Length();
 124     float bLength = b.Length();
 125
 126     Vector3 tangent = (a*bLength + b*aLength)/2.0f;
 127     tangent.Normalize();
 128
 129     aLength *= curvature;
 130     bLength *= curvature;
 131     mInTangents[knotIndex]  = curPoint - tangent*aLength;
 132     mOutTangents[knotIndex] = curPoint + tangent*bLength;
 133   }
 134 }
 135
 136 unsigned int Spline::GetNumberOfSegments() const
 137 {
 138   return (mKnots.size()>1)?mKnots.size()-1:0;
 139 }
 140
 141
 142 const Vector3 Spline::GetPoint(float alpha) const
 143 {
 144   Vector3 current;
 145   unsigned int numSegs = GetNumberOfSegments();
 146   if(numSegs > 0)
 147   {
 148     unsigned int segment = alpha * numSegs;
 149     float segLength = 1.0f / numSegs;
 150     float segStart  = (float)segment * segLength;
 151     float progress = (alpha - segStart) * numSegs;
 152     if(segment >= numSegs)
 153     {
 154       segment = numSegs-1.0f;
 155       progress = 1.0f;
 156     }
 157     current = GetPoint(segment, progress);
 158   }
 159   return current;
 160 }
 161
 162
 163 // Given a parameter s, return the point on the given spline segment.
 164 // Checks that the segment index is valid (e.g. for 10 points, there
 165 // are only 9 segments)
 166 const Vector3 Spline::GetPoint(unsigned int segmentIndex, float s) const
 167 {
 168   DALI_ASSERT_ALWAYS( segmentIndex+1 < mKnots.size() && segmentIndex < mKnots.size() && "segmentIndex out of bounds" );
 169   DALI_ASSERT_ALWAYS( mOutTangents.size() == mKnots.size() && "Spline not fully initialized" );
 170   DALI_ASSERT_ALWAYS( mInTangents.size()  == mKnots.size() && "Spline not fully initialized" );
 171
 172   Vector3  bPoint;
 173
 174   if(s < 0.0f || s > 1.0f)
 175   {
 176     bPoint.x = 0.0f;
 177     bPoint.y = 0.0f;
 178     bPoint.z = 0.0f;
 179   }
 180   else if(s < Math::MACHINE_EPSILON_1)
 181   {
 182     bPoint = mKnots[segmentIndex];
 183   }
 184   else if( (1.0 - s) < Math::MACHINE_EPSILON_1)
 185   {
 186     bPoint = mKnots[segmentIndex+1];
 187   }
 188   else
 189   {
 190     Vector4  sVect(s*s*s, s*s, s, 1);
 191     Vector4  cVect;
 192
 193     cVect.x  = mKnots[segmentIndex].x;
 194     cVect.y  = mOutTangents[segmentIndex].x;
 195     cVect.z  = mInTangents[segmentIndex+1].x;
 196     cVect.w  = mKnots[segmentIndex+1].x;
 197     bPoint.x = sVect.Dot4(mBasis * cVect);
 198
 199     cVect.x  = mKnots[segmentIndex].y;
 200     cVect.y  = mOutTangents[segmentIndex].y;
 201     cVect.z  = mInTangents[segmentIndex+1].y;
 202     cVect.w  = mKnots[segmentIndex+1].y;
 203     bPoint.y = sVect.Dot4(mBasis * cVect);
 204
 205     cVect.x  = mKnots[segmentIndex].z;
 206     cVect.y  = mOutTangents[segmentIndex].z;
 207     cVect.z  = mInTangents[segmentIndex+1].z;
 208     cVect.w  = mKnots[segmentIndex+1].z;
 209     bPoint.z = sVect.Dot4(mBasis * cVect);
 210   }
 211   return bPoint;
 212 }
 213
 214
 215 // Given a parameter s (NOT x), return the Y value. Checks that the
 216 // segment index is valid. For bezier splines, the last segment is
 217 // only used to specify the end point, so is not valid.
 218 const float  Spline::GetY(unsigned int segmentIndex, float s) const
 219 {
 220   DALI_ASSERT_ALWAYS( segmentIndex+1 < mKnots.size() && segmentIndex < mKnots.size() && "segmentIndex out of bounds");
 221   DALI_ASSERT_ALWAYS( mOutTangents.size() == mKnots.size() && "Spline not fully initialized" );
 222   DALI_ASSERT_ALWAYS( mInTangents.size()  == mKnots.size() && "Spline not fully initialized" );
 223
 224   float    yValue=0.0f;
 225
 226   if(s < 0.0f || s > 1.0f)
 227   {
 228     yValue = 0.0f;
 229   }
 230   else if(s < Math::MACHINE_EPSILON_1)
 231   {
 232     yValue = mKnots[segmentIndex].y;
 233   }
 234   else if( (1.0 - s) < Math::MACHINE_EPSILON_1)
 235   {
 236     yValue = mKnots[segmentIndex+1].y;
 237   }
 238   else
 239   {
 240     Vector4  sVect(s*s*s, s*s, s, 1);
 241     Vector4  cVect;
 242
 243     cVect.x  = mKnots[segmentIndex].y;
 244     cVect.y  = mOutTangents[segmentIndex].y;
 245     cVect.z  = mInTangents[segmentIndex+1].y;
 246     cVect.w  = mKnots[segmentIndex+1].y;
 247     yValue   = sVect.Dot4(mBasis * cVect);
 248   }
 249   return yValue;
 250 }
 251
 252 float ClampToZeroOne(float v)
 253 {
 254   return (v<0.0f)?(0.0f):((v>1.0f)?1.0f:v);
 255 }
 256
 257 // Use de Casteljau subdivision to approximate the parameter required to find x
 258 // on a Bezier spline
 259 // note, atX is already determined to be >= P0_X, <P1_X
 260 const float Spline::ApproximateCubicBezierParameter (
 261   float atX, float P0_X, float C0_X, float C1_X, float P1_X ) const
 262 {
 263   if (fabs(atX - P0_X) < GetRangedEpsilon(atX, P0_X) )
 264   {
 265     return 0.0;
 266   }
 267
 268   if (fabs(P1_X - atX) < GetRangedEpsilon(atX, P1_X) )
 269   {
 270     return 1.0;
 271   }
 272
 273   int iterationStep = 0;
 274
 275   float u = 0.0f; float v = 1.0f;
 276
 277   // iteratively apply subdivision to approach value atX
 278   while (iterationStep < MAXIMUM_ITERATIONS)
 279   {
 280     float a = (P0_X + C0_X)*0.5f;
 281     float b = (C0_X + C1_X)*0.5f;
 282     float c = (C1_X + P1_X)*0.5f;
 283     float d = (a + b)*0.5f;
 284     float e = (b + c)*0.5f;
 285     float f = (d + e)*0.5f; // must be on curve - a Bezier spline is 2nd order diff continuous
 286
 287     // The curve point is close enough to required value.
 288     if (fabsf(f - atX) < GetRangedEpsilon(f, atX) )
 289     {
 290       break;
 291     }
 292
 293     if (f < atX)
 294     {
 295       P0_X = f;
 296       C0_X = e;
 297       C1_X = c;
 298       u = (u + v)*0.5f;
 299     }
 300     else
 301     {
 302       C0_X = a;
 303       C1_X = d;
 304       P1_X = f;
 305       v = (u + v)*0.5f;
 306     }
 307
 308     iterationStep++;
 309   }
 310
 311   return ClampToZeroOne((u + v)*0.5f);
 312 }
 313
 314
 315 const bool Spline::FindSegment(float x, /*out*/ int& segmentIndex) const
 316 {
 317   bool found = false;
 318   unsigned int index=0;
 319   unsigned int prevIndex=0;
 320
 321   while(index < mKnots.size() && mKnots[index].x <= x)
 322   {
 323     prevIndex = index;
 324     ++index;
 325   }
 326
 327   if(index == mKnots.size())
 328   {
 329     --prevIndex;
 330     --index;
 331   }
 332
 333   if( (mKnots[prevIndex].x <= x) && ( x < mKnots[index].x ) )
 334   {
 335     found = true;
 336     segmentIndex = prevIndex;
 337   }
 338   return found;
 339 }
 340
 341 const float Spline::GetYFromMonotonicX(float x) const
 342 {
 343   int segmentIndex=0;
 344   float yValue = 0.0f;
 345
 346   if(FindSegment(x, segmentIndex))
 347   {
 348     float s = ApproximateCubicBezierParameter (x, mKnots[segmentIndex].x,
 349                                                mOutTangents[segmentIndex].x,
 350                                                mInTangents[segmentIndex+1].x,
 351                                                mKnots[segmentIndex+1].x);
 352     yValue  = GetY(segmentIndex, s);
 353   }
 354   else
 355   {
 356     if(mKnots.size() > 0)
 357     {
 358       Vector3 lastPoint = mKnots[mKnots.size()-1];
 359       if(fabsf(lastPoint.x - x) < GetRangedEpsilon(lastPoint.x, x))
 360       {
 361         yValue = lastPoint.y;
 362       }
 363     }
 364   }
 365   return yValue;
 366 }
 367
 368 } // Dali