2 Copyright (C) 2013 Paul Davis
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.
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.
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.
24 #include "canvas/curve.h"
26 using namespace ArdourCanvas;
30 Curve::Curve (Group* parent)
35 , points_per_segment (16)
36 , curve_type (CatmullRomCentripetal)
40 /** When rendering the curve, we will always draw a fixed number of straight
41 * line segments to span the x-axis extent of the curve. More segments:
42 * smoother visual rendering. Less rendering: closer to a visibily poly-line
46 Curve::set_points_per_segment (uint32_t n)
48 /* this only changes our appearance rather than the bounding box, so we
49 just need to schedule a redraw rather than notify the parent of any
52 points_per_segment = n;
58 Curve::compute_bounding_box () const
60 PolyItem::compute_bounding_box ();
62 /* possibly add extents of any point indicators here if we ever do that */
66 Curve::set (Points const& p)
76 interpolate (_points, points_per_segment, CatmullRomCentripetal, false, samples);
77 n_samples = samples.size();
80 /* Cartmull-Rom code from http://stackoverflow.com/questions/9489736/catmull-rom-curve-with-no-cusps-and-no-self-intersections/19283471#19283471
82 * Thanks to Ted for his Java version, which I translated into Ardour-idiomatic
87 * Calculate the same values but introduces the ability to "parameterize" the t
88 * values used in the calculation. This is based on Figure 3 from
89 * http://www.cemyuksel.com/research/catmullrom_param/catmullrom.pdf
91 * @param p An array of double values of length 4, where interpolation
92 * occurs from p1 to p2.
93 * @param time An array of time measures of length 4, corresponding to each
95 * @param t the actual interpolation ratio from 0 to 1 representing the
96 * position between p1 and p2 to interpolate the value.
99 __interpolate (double p[4], double time[4], double t)
101 const double L01 = p[0] * (time[1] - t) / (time[1] - time[0]) + p[1] * (t - time[0]) / (time[1] - time[0]);
102 const double L12 = p[1] * (time[2] - t) / (time[2] - time[1]) + p[2] * (t - time[1]) / (time[2] - time[1]);
103 const double L23 = p[2] * (time[3] - t) / (time[3] - time[2]) + p[3] * (t - time[2]) / (time[3] - time[2]);
104 const double L012 = L01 * (time[2] - t) / (time[2] - time[0]) + L12 * (t - time[0]) / (time[2] - time[0]);
105 const double L123 = L12 * (time[3] - t) / (time[3] - time[1]) + L23 * (t - time[1]) / (time[3] - time[1]);
106 const double C12 = L012 * (time[2] - t) / (time[2] - time[1]) + L123 * (t - time[1]) / (time[2] - time[1]);
111 * Given a list of control points, this will create a list of points_per_segment
112 * points spaced uniformly along the resulting Catmull-Rom curve.
114 * @param points The list of control points, leading and ending with a
115 * coordinate that is only used for controling the spline and is not visualized.
116 * @param index The index of control point p0, where p0, p1, p2, and p3 are
117 * used in order to create a curve between p1 and p2.
118 * @param points_per_segment The total number of uniformly spaced interpolated
119 * points to calculate for each segment. The larger this number, the
120 * smoother the resulting curve.
121 * @param curve_type Clarifies whether the curve should use uniform, chordal
122 * or centripetal curve types. Uniform can produce loops, chordal can
123 * produce large distortions from the original lines, and centripetal is an
124 * optimal balance without spaces.
125 * @return the list of coordinates that define the CatmullRom curve
126 * between the points defined by index+1 and index+2.
129 _interpolate (const Points& points, Points::size_type index, int points_per_segment, Curve::SplineType curve_type, Points& results)
135 for (int i = 0; i < 4; i++) {
136 x[i] = points[index + i].x;
137 y[i] = points[index + i].y;
144 if (curve_type != Curve::CatmullRomUniform) {
146 for (int i = 1; i < 4; i++) {
147 double dx = x[i] - x[i - 1];
148 double dy = y[i] - y[i - 1];
149 if (curve_type == Curve::CatmullRomCentripetal) {
150 total += pow (dx * dx + dy * dy, .25);
152 total += pow (dx * dx + dy * dy, .5);
160 int segments = points_per_segment - 1;
161 results.push_back (points[index + 1]);
163 for (int i = 1; i < segments; i++) {
164 double xi = __interpolate (x, time, tstart + (i * (tend - tstart)) / segments);
165 double yi = __interpolate (y, time, tstart + (i * (tend - tstart)) / segments);
166 results.push_back (Duple (xi, yi));
169 results.push_back (points[index + 2]);
173 * This method will calculate the Catmull-Rom interpolation curve, returning
174 * it as a list of Coord coordinate objects. This method in particular
175 * adds the first and last control points which are not visible, but required
176 * for calculating the spline.
178 * @param coordinates The list of original straight line points to calculate
179 * an interpolation from.
180 * @param points_per_segment The integer number of equally spaced points to
181 * return along each curve. The actual distance between each
182 * point will depend on the spacing between the control points.
183 * @return The list of interpolated coordinates.
184 * @param curve_type Chordal (stiff), Uniform(floppy), or Centripetal(medium)
185 * @throws gov.ca.water.shapelite.analysis.CatmullRomException if
186 * points_per_segment is less than 2.
190 Curve::interpolate (const Points& coordinates, uint32_t points_per_segment, SplineType curve_type, bool closed, Points& results)
192 if (points_per_segment < 2) {
196 // Cannot interpolate curves given only two points. Two points
197 // is best represented as a simple line segment.
198 if (coordinates.size() < 3) {
199 results = coordinates;
203 // Copy the incoming coordinates. We need to modify it during interpolation
204 Points vertices = coordinates;
206 // Test whether the shape is open or closed by checking to see if
207 // the first point intersects with the last point. M and Z are ignored.
209 // Use the second and second from last points as control points.
210 // get the second point.
211 Duple p2 = vertices[1];
212 // get the point before the last point
213 Duple pn1 = vertices[vertices.size() - 2];
215 // insert the second from the last point as the first point in the list
216 // because when the shape is closed it keeps wrapping around to
218 vertices.insert(vertices.begin(), pn1);
219 // add the second point to the end.
220 vertices.push_back(p2);
222 // The shape is open, so use control points that simply extend
223 // the first and last segments
225 // Get the change in x and y between the first and second coordinates.
226 double dx = vertices[1].x - vertices[0].x;
227 double dy = vertices[1].y - vertices[0].y;
229 // Then using the change, extrapolate backwards to find a control point.
230 double x1 = vertices[0].x - dx;
231 double y1 = vertices[0].y - dy;
233 // Actaully create the start point from the extrapolated values.
234 Duple start (x1, y1);
236 // Repeat for the end control point.
237 int n = vertices.size() - 1;
238 dx = vertices[n].x - vertices[n - 1].x;
239 dy = vertices[n].y - vertices[n - 1].y;
240 double xn = vertices[n].x + dx;
241 double yn = vertices[n].y + dy;
244 // insert the start control point at the start of the vertices list.
245 vertices.insert (vertices.begin(), start);
247 // append the end control ponit to the end of the vertices list.
248 vertices.push_back (end);
251 // When looping, remember that each cycle requires 4 points, starting
252 // with i and ending with i+3. So we don't loop through all the points.
254 for (Points::size_type i = 0; i < vertices.size() - 3; i++) {
256 // Actually calculate the Catmull-Rom curve for one segment.
259 _interpolate (vertices, i, points_per_segment, curve_type, r);
261 // Since the middle points are added twice, once for each bordering
262 // segment, we only add the 0 index result point for the first
263 // segment. Otherwise we will have duplicate points.
265 if (results.size() > 0) {
269 // Add the coordinates for the segment to the result list.
271 results.insert (results.end(), r.begin(), r.end());
276 Curve::render (Rect const & area, Cairo::RefPtr<Cairo::Context> context) const
278 if (!_outline || _points.size() < 2 || !_bounding_box) {
282 Rect self = item_to_window (_bounding_box.get());
283 boost::optional<Rect> d = self.intersection (area);
285 Rect draw = d.get ();
287 /* Our approach is to always draw n_segments across our total size.
289 * This is very inefficient if we are asked to only draw a small
290 * section of the curve. For now we rely on cairo clipping to help
295 setup_outline_context (context);
297 if (_points.size() == 2) {
303 window_space = item_to_window (_points.front());
304 context->move_to (window_space.x, window_space.y);
305 window_space = item_to_window (_points.back());
306 context->line_to (window_space.x, window_space.y);
312 /* curve of at least 3 points */
314 /* x-axis limits of the curve, in window space coordinates */
316 Duple w1 = item_to_window (Duple (_points.front().x, 0.0));
317 Duple w2 = item_to_window (Duple (_points.back().x, 0.0));
319 /* clamp actual draw to area bound by points, rather than our bounding box which is slightly different */
322 context->rectangle (draw.x0, draw.y0, draw.width(), draw.height());
325 /* expand drawing area by several pixels on each side to avoid cairo stroking effects at the boundary.
326 they will still occur, but cairo's clipping will hide them.
329 draw = draw.expand (4.0);
331 /* now clip it to the actual points in the curve */
333 if (draw.x0 < w1.x) {
337 if (draw.x1 >= w2.x) {
341 /* find left and right-most sample */
343 Points::size_type left = 0;
344 Points::size_type right = n_samples;
346 for (Points::size_type idx = 0; idx < n_samples - 1; ++idx) {
348 window_space = item_to_window (Duple (samples[idx].x, 0.0));
349 if (window_space.x >= draw.x0) break;
351 for (Points::size_type idx = n_samples; idx > left + 1; --idx) {
352 window_space = item_to_window (Duple (samples[idx].x, 0.0));
353 if (window_space.x <= draw.x1) break;
357 /* draw line between samples */
358 window_space = item_to_window (Duple (samples[left].x, samples[left].y));
359 context->move_to (window_space.x, window_space.y);
360 for (uint32_t idx = left + 1; idx < right; ++idx) {
361 window_space = item_to_window (Duple (samples[idx].x, samples[idx].y));
362 context->line_to (window_space.x, window_space.y);
372 setup_fill_context (context);
373 for (Points::const_iterator p = _points.begin(); p != _points.end(); ++p) {
374 Duple window_space (item_to_window (*p));
375 context->arc (window_space.x, window_space.y, 5.0, 0.0, 2 * M_PI);
382 Curve::covers (Duple const & pc) const
384 Duple point = canvas_to_item (pc);
386 /* O(N) N = number of points, and not accurate */
388 for (Points::const_iterator p = _points.begin(); p != _points.end(); ++p) {
390 const Coord dx = point.x - (*p).x;
391 const Coord dy = point.y - (*p).y;
392 const Coord dx2 = dx * dx;
393 const Coord dy2 = dy * dy;
395 if ((dx2 < 2.0 && dy2 < 2.0) || (dx2 + dy2 < 4.0)) {