bezier.cpp

Go to the documentation of this file.
00001 /*
00002  * bezier.cpp
00003  *
00004  * Copyright (C) 2003 Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  *
00031  * simple bezier APIs
00032  */
00033 
00034 // includes --------------------------------------------------------------------
00035 #include "bezier.h"             // include our own header first
00036 
00037 #include <sstream>
00038 
00039 #include <math.h>
00040 #include <stdio.h>
00041 
00042 #include "common/wave_ex.h"
00043 #include "perf/perf.h"
00044 #include "util/token_stream.h"
00045 
00046 
00047 namespace bezier {
00048 
00049 
00050 static const float s_eps                        = 1.0e-8;
00051 
00052 /*
00053  * static helper methods
00054  */
00055 
00056 /*
00057  * finds roots of 3at^2 + 2bt + c = 0
00058  *
00059  * roots t(i) must be in the range 0 < t < 1
00060  *
00061  * TODO: should generalize this into a general quadratic root finder
00062  */
00063 static int
00064 findRoots
00065 (
00066 IN float a,
00067 IN float b,
00068 IN float c,
00069 OUT float * roots
00070 )
00071 throw()
00072 {
00073         perf::Timer timer("bezier::findRoots");
00074 
00075         int nroots = 0;
00076 
00077         ASSERT(roots, "null roots array");
00078 
00079         float t;
00080 
00081         if (a < s_eps && a > -s_eps) {
00082                 if (b < s_eps && b > -s_eps) {
00083                         // DPRINTF("no roots: a=b=0");
00084                         return 0;
00085                 }
00086                 t = (-1.0 * c) / (2.0 * b);
00087                 if (t > 0.0 && t < 1.0) {
00088                         // DPRINTF("one root: a=0, t = %f", t);
00089                         roots[0] = t;
00090                         ++nroots;
00091                 }
00092                 return nroots;
00093         }
00094 
00095         float factor = b * b - 3.0 * a * c;
00096         if (factor < 0.0) {
00097                 // DPRINTF("no roots--imaginary");
00098                 return 0;       // imaginary roots
00099         }
00100 
00101         factor = sqrt(factor);
00102         t = (1.0 / (3.0 * a)) * (factor - b);
00103         if (t > 0.0 && t < 1.0) {
00104                 // DPRINTF("Found a root: %f", t);
00105                 roots[nroots] = t;
00106                 ++nroots;
00107         }
00108 
00109         // skip degenerate roots
00110         if (0.0 == factor)
00111                 return nroots;
00112 
00113         t = (1.0 / (3.0 * a)) * (-factor - b);
00114         if (t > 0.0 && t < 1.0) {
00115                 // DPRINTF("Found a root: %f", t);
00116                 roots[nroots] = t;
00117                 ++nroots;
00118         }
00119         return nroots;
00120 }
00121 
00122 
00123 
00124 static void
00125 checkBoundaries
00126 (
00127 IO float& min,
00128 IO float& max,
00129 IN float value
00130 )
00131 throw()
00132 {
00133         if (value < min)
00134                 min = value;
00135         if (value > max)
00136                 max = value;
00137 }
00138 
00139 
00140 
00141 /*
00142  * getRect() -- gets the bounding rectangle for the bezier.
00143  *
00144  * solutions for maxima are
00145  *
00146  *  t = (1/3a) * (-b +/- sqrt(b^2 - 3ac))
00147  *
00148  *   1) see if roots exist
00149  *   2) see if any roots are between 0 and 1
00150  *   3) maxima are then endpoints + valid roots
00151  */
00152 void
00153 getRect
00154 (
00155 IN const curve_t& curve,
00156 OUT rect_t& rect
00157 )
00158 throw()
00159 {
00160         perf::Timer timer("bezier::getRect");
00161 
00162         // see if we have any roots for x,y
00163         float tx[3], ty[3];
00164         int xroots = findRoots(curve.ax, curve.bx, curve.cx, tx);
00165         int yroots = findRoots(curve.ay, curve.by, curve.cy, ty);
00166 
00167         // DPRINTF("Found %d x-roots...", xroots);
00168         //DPRINTF("Found %d y-roots...", yroots);
00169 
00170         // add endpoint as another root
00171         tx[xroots++] = 1.0;
00172         ty[yroots++] = 1.0;
00173         ASSERT(xroots <= 3, "Bad xroot count: %d", xroots);
00174         ASSERT(yroots <= 3, "Bad yroot count: %d", yroots);
00175 
00176         // check roots for boundary
00177         float xmin = curve.x0;
00178         float xmax = curve.x0;
00179         float ymin = curve.y0;
00180         float ymax = curve.y0;
00181 
00182         // check roots
00183         for (int i = 0; i < xroots; ++ i) {
00184                 float x = curve.x0 + curve.cx * tx[i] +
00185                     curve.bx * tx[i] * tx[i] +
00186                     curve.ax * tx[i] * tx[i] * tx[i];
00187                 //DPRINTF("x-root %d: %f", i, x);
00188                 checkBoundaries(xmin, xmax, x);
00189         }
00190         for (int i = 0; i < yroots; ++i) {
00191                 float y = curve.y0 + curve.cy * ty[i] +
00192                     curve.by * ty[i] * ty[i] +
00193                     curve.ay * ty[i] * ty[i] * ty[i];
00194                 //DPRINTF("y-root: %d: %f", i, y);
00195                 checkBoundaries(ymin, ymax, y);
00196         }
00197 
00198         // return bounding box
00199         rect.left = xmin;
00200         rect.right = xmax;
00201         rect.top = ymin;
00202         rect.bottom = ymax;
00203 }
00204 
00205 
00206 
00207 void
00208 scale
00209 (
00210 IO curve_t& curve,
00211 IN float factor
00212 )
00213 throw()
00214 {
00215         curve.ax *= factor;
00216         curve.bx *= factor;
00217         curve.cx *= factor;
00218 
00219         curve.ay *= factor;
00220         curve.by *= factor;
00221         curve.cy *= factor;
00222 }
00223 
00224 
00225 
00226 static float
00227 writeVal
00228 (
00229 IN float x,
00230 IN float eps
00231 )
00232 throw()
00233 {
00234         if (x < eps && x > -eps) {
00235                 // within +/- epsilon -- effectively zero
00236                 return 0.0;
00237         }
00238         return x;
00239 }
00240 
00241 
00242 
00243 void
00244 write
00245 (
00246 IN const curve_t& curve,
00247 OUT std::string& value,
00248 IN float eps
00249 )
00250 throw()
00251 {
00252         ASSERT(eps >= 0.0, "Bad epsilon value: %f", eps);
00253         value = "";
00254 
00255         std::ostringstream out;
00256         out << writeVal(curve.x0, eps) << " ";
00257         out << writeVal(curve.ax, eps) << " ";
00258         out << writeVal(curve.bx, eps) << " ";
00259         out << writeVal(curve.cx, eps) << " ";
00260 
00261         out << writeVal(curve.y0, eps) << " ";
00262         out << writeVal(curve.ay, eps) << " ";
00263         out << writeVal(curve.by, eps) << " ";
00264         out << writeVal(curve.cy, eps);
00265 
00266         value = out.str();
00267 }
00268 
00269 
00270 #define READ_COMPONENT(x)                                       \
00271         if (!*p) {                                              \
00272                 WAVE_EX(wex);                                   \
00273                 wex << "Could not read bezier component" << #x ; \
00274         }                                                       \
00275         curve.x = atof(p);                                      \
00276         while (*p && !isspace(*p)) { ++p; }                     \
00277         while (*p && isspace(*p)) { ++p; }
00278 
00279 
00280 void
00281 read
00282 (
00283 IN const char * value,
00284 OUT curve_t& curve
00285 )
00286 {
00287         // read all components in order x0, ax, bx, cx, y0, ay, by, cy
00288         // (see write() routine above)
00289 
00290         const char * p = value;
00291         READ_COMPONENT(x0)
00292         READ_COMPONENT(ax)
00293         READ_COMPONENT(bx)
00294         READ_COMPONENT(cx)
00295         READ_COMPONENT(y0)
00296         READ_COMPONENT(ay)
00297         READ_COMPONENT(by)
00298         READ_COMPONENT(cy)
00299 }
00300 
00301 
00302 
00303 void getCurveFromControlPoints
00304 (
00305 IN const control_points_t& cp,
00306 OUT curve_t& b
00307 )
00308 throw()
00309 {
00310         // initial point
00311         b.x0 = cp.p0.x;
00312         b.y0 = cp.p0.y;
00313 
00314         // linear with t
00315         b.cx = 3.0 * (cp.p1.x - cp.p0.x);
00316         b.cy = 3.0 * (cp.p1.y - cp.p0.y);
00317 
00318         // quadradic with t
00319         b.bx = 3.0 * (cp.p0.x - 2.0 * cp.p1.x + cp.p2.x);
00320         b.by = 3.0 * (cp.p0.y - 2.0 * cp.p1.y + cp.p2.y);
00321 
00322         // cubic with t
00323         b.ax = -cp.p0.x + 3.0 * cp.p1.x - 3.0 * cp.p2.x + cp.p3.x;
00324         b.ay = -cp.p0.y + 3.0 * cp.p1.y - 3.0 * cp.p2.y + cp.p3.y;
00325 }
00326 
00327 
00328 
00329 void
00330 getControlPointsFromCurve
00331 (
00332 IN const curve_t& b,
00333 OUT control_points_t& cp
00334 )
00335 throw()
00336 {
00337         // see 8 march 07 journal entry
00338         cp.p0.set(b.x0, b.y0);
00339 
00340         float inv3 = 1.0 / 3.0;
00341 
00342         cp.p1.set(b.x0 + inv3 * b.cx,
00343                   b.y0 + inv3 * b.cy);
00344 
00345         cp.p2.set(inv3 * (b.bx + 2.0 * b.cx + 3.0 * b.x0),
00346                   inv3 * (b.by + 2.0 * b.cy + 3.0 * b.y0));
00347 
00348         cp.p3.set(b.ax + b.bx + b.cx + b.x0,
00349                   b.ay + b.by + b.cy + b.y0);
00350 }
00351 
00352 
00353 
00354 };      // bezier namespace
00355