libs/canvas/curve.cc

   1 /*
   2     Copyright (C) 2013 Paul Davis
   3
   4     This program is free software; you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation; either version 2 of the License, or
   7     (at your option) any later version.
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program; if not, write to the Free Software
  16     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18 */
  19
  20 #include <exception>
  21 #include <algorithm>
  22
  23 #include "canvas/curve.h"
  24
  25 using namespace ArdourCanvas;
  26 using std::min;
  27 using std::max;
  28
  29 Curve::Curve (Group* parent)
  30         : Item (parent)
  31         , PolyItem (parent)
  32 {
  33
  34 }
  35
  36 void
  37 Curve::compute_bounding_box () const
  38 {
  39         PolyItem::compute_bounding_box ();
  40
  41         if (_bounding_box) {
  42
  43                 bool have1 = false;
  44                 bool have2 = false;
  45
  46                 Rect bbox1;
  47                 Rect bbox2;
  48
  49                 for (Points::const_iterator i = first_control_points.begin(); i != first_control_points.end(); ++i) {
  50                         if (have1) {
  51                                 bbox1.x0 = min (bbox1.x0, i->x);
  52                                 bbox1.y0 = min (bbox1.y0, i->y);
  53                                 bbox1.x1 = max (bbox1.x1, i->x);
  54                                 bbox1.y1 = max (bbox1.y1, i->y);
  55                         } else {
  56                                 bbox1.x0 = bbox1.x1 = i->x;
  57                                 bbox1.y0 = bbox1.y1 = i->y;
  58                                 have1 = true;
  59                         }
  60                 }
  61
  62                 for (Points::const_iterator i = second_control_points.begin(); i != second_control_points.end(); ++i) {
  63                         if (have2) {
  64                                 bbox2.x0 = min (bbox2.x0, i->x);
  65                                 bbox2.y0 = min (bbox2.y0, i->y);
  66                                 bbox2.x1 = max (bbox2.x1, i->x);
  67                                 bbox2.y1 = max (bbox2.y1, i->y);
  68                         } else {
  69                                 bbox2.x0 = bbox2.x1 = i->x;
  70                                 bbox2.y0 = bbox2.y1 = i->y;
  71                                 have2 = true;
  72                         }
  73                 }
  74
  75                 Rect u = bbox1.extend (bbox2);
  76                 _bounding_box = u.extend (_bounding_box.get());
  77         }
  78
  79         _bounding_box_dirty = false;
  80 }
  81
  82 void
  83 Curve::set (Points const& p)
  84 {
  85         PolyItem::set (p);
  86
  87         first_control_points.clear ();
  88         second_control_points.clear ();
  89
  90         compute_control_points (_points, first_control_points, second_control_points);
  91 }
  92
  93 void
  94 Curve::render (Rect const & area, Cairo::RefPtr<Cairo::Context> context) const
  95 {
  96         if (_outline) {
  97                 setup_outline_context (context);
  98                 render_path (area, context);
  99                 context->stroke ();
 100         }
 101 }
 102
 103 void
 104 Curve::render_path (Rect const & area, Cairo::RefPtr<Cairo::Context> context) const
 105 {
 106         PolyItem::render_curve (area, context, first_control_points, second_control_points);
 107 }
 108
 109 void
 110 Curve::compute_control_points (Points const& knots,
 111                                Points& firstControlPoints,
 112                                Points& secondControlPoints)
 113 {
 114         Points::size_type n = knots.size() - 1;
 115
 116         if (n < 1) {
 117                 return;
 118         }
 119
 120         if (n == 1) {
 121                 /* Special case: Bezier curve should be a straight line. */
 122
 123                 Duple d;
 124
 125                 d.x = (2.0 * knots[0].x + knots[1].x) / 3;
 126                 d.y = (2.0 * knots[0].y + knots[1].y) / 3;
 127                 firstControlPoints.push_back (d);
 128
 129                 d.x = 2.0 * firstControlPoints[0].x - knots[0].x;
 130                 d.y = 2.0 * firstControlPoints[0].y - knots[0].y;
 131                 secondControlPoints.push_back (d);
 132
 133                 return;
 134         }
 135
 136         // Calculate first Bezier control points
 137         // Right hand side vector
 138
 139         std::vector<double> rhs;
 140
 141         rhs.assign (n, 0);
 142
 143         // Set right hand side X values
 144
 145         for (Points::size_type i = 1; i < n - 1; ++i) {
 146                 rhs[i] = 4 * knots[i].x + 2 * knots[i + 1].x;
 147         }
 148         rhs[0] = knots[0].x + 2 * knots[1].x;
 149         rhs[n - 1] = (8 * knots[n - 1].x + knots[n].x) / 2.0;
 150
 151         // Get first control points X-values
 152         double* x = solve (rhs);
 153
 154         // Set right hand side Y values
 155         for (Points::size_type i = 1; i < n - 1; ++i) {
 156                 rhs[i] = 4 * knots[i].y + 2 * knots[i + 1].y;
 157         }
 158         rhs[0] = knots[0].y + 2 * knots[1].y;
 159         rhs[n - 1] = (8 * knots[n - 1].y + knots[n].y) / 2.0;
 160
 161         // Get first control points Y-values
 162         double* y = solve (rhs);
 163
 164         for (Points::size_type i = 0; i < n; ++i) {
 165
 166                 firstControlPoints.push_back (Duple (x[i], y[i]));
 167
 168                 if (i < n - 1) {
 169                         secondControlPoints.push_back (Duple (2 * knots [i + 1].x - x[i + 1],
 170                                                               2 * knots[i + 1].y - y[i + 1]));
 171                 } else {
 172                         secondControlPoints.push_back (Duple ((knots [n].x + x[n - 1]) / 2,
 173                                                               (knots[n].y + y[n - 1]) / 2));
 174                 }
 175         }
 176
 177         delete [] x;
 178         delete [] y;
 179 }
 180
 181 /** Solves a tridiagonal system for one of coordinates (x or y)
 182  *  of first Bezier control points.
 183  */
 184
 185 double*
 186 Curve::solve (std::vector<double> const & rhs)
 187 {
 188         std::vector<double>::size_type n = rhs.size();
 189         double* x = new double[n]; // Solution vector.
 190         double* tmp = new double[n]; // Temp workspace.
 191
 192         double b = 2.0;
 193
 194         x[0] = rhs[0] / b;
 195
 196         for (std::vector<double>::size_type i = 1; i < n; i++) {
 197                 // Decomposition and forward substitution.
 198                 tmp[i] = 1 / b;
 199                 b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
 200                 x[i] = (rhs[i] - x[i - 1]) / b;
 201         }
 202
 203         for (std::vector<double>::size_type i = 1; i < n; i++) {
 204                 // Backsubstitution
 205                 x[n - i - 1] -= tmp[n - i] * x[n - i];
 206         }
 207
 208         delete [] tmp;
 209
 210         return x;
 211 }
 212
 213 bool
 214 Curve::covers (Duple const & pc) const
 215 {
 216         Duple point = canvas_to_item (pc);
 217
 218         /* XXX Hellaciously expensive ... */
 219
 220         for (Points::const_iterator p = _points.begin(); p != _points.end(); ++p) {
 221
 222                 const Coord dx = point.x - (*p).x;
 223                 const Coord dy = point.y - (*p).y;
 224                 const Coord dx2 = dx * dx;
 225                 const Coord dy2 = dy * dy;
 226
 227                 if ((dx2 < 2.0 && dy2 < 2.0) || (dx2 + dy2 < 4.0)) {
 228                         return true;
 229                 }
 230         }
 231
 232         return false;
 233 }