1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Catmull-Rom Splines</title>
<link rel="stylesheet" href="../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../interpolation.html" title="Chapter 13. Interpolation">
<link rel="prev" href="vector_barycentric.html" title="Vector-valued Barycentric Rational Interpolation">
<link rel="next" href="bezier_polynomial.html" title="Bezier Polynomials">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="vector_barycentric.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interpolation.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="bezier_polynomial.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.catmull_rom"></a><a class="link" href="catmull_rom.html" title="Catmull-Rom Splines">Catmull-Rom Splines</a>
</h2></div></div></div>
<h4>
<a name="math_toolkit.catmull_rom.h0"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.synopsis"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">interpolators</span><span class="special">/</span><span class="identifier">catmull_rom</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>
<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Point</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">RandomAccessContainer</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">Point</span><span class="special">></span> <span class="special">></span>
<span class="keyword">class</span> <span class="identifier">catmull_rom</span>
<span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="identifier">catmull_rom</span><span class="special">(</span><span class="identifier">RandomAccessContainer</span><span class="special">&&</span> <span class="identifier">points</span><span class="special">,</span> <span class="keyword">bool</span> <span class="identifier">closed</span> <span class="special">=</span> <span class="keyword">false</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">alpha</span> <span class="special">=</span> <span class="special">(</span><span class="identifier">Real</span><span class="special">)</span> <span class="number">1</span><span class="special">/</span> <span class="special">(</span><span class="identifier">Real</span><span class="special">)</span> <span class="number">2</span><span class="special">)</span>
<span class="identifier">catmull_rom</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">initializer_list</span><span class="special"><</span><span class="identifier">Point</span><span class="special">></span> <span class="identifier">l</span><span class="special">,</span> <span class="keyword">bool</span> <span class="identifier">closed</span> <span class="special">=</span> <span class="keyword">false</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Point</span><span class="special">::</span><span class="identifier">value_type</span> <span class="identifier">alpha</span> <span class="special">=</span> <span class="special">(</span><span class="keyword">typename</span> <span class="identifier">Point</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">)</span> <span class="number">1</span><span class="special">/</span> <span class="special">(</span><span class="keyword">typename</span> <span class="identifier">Point</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">)</span> <span class="number">2</span><span class="special">);</span>
<span class="identifier">Real</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">Real</span> <span class="identifier">s</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span>
<span class="identifier">Real</span> <span class="identifier">max_parameter</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span>
<span class="identifier">Real</span> <span class="identifier">parameter_at_point</span><span class="special">(</span><span class="identifier">size_t</span> <span class="identifier">i</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span>
<span class="identifier">Point</span> <span class="identifier">prime</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">s</span><span class="special">)</span> <span class="keyword">const</span><span class="special">;</span>
<span class="special">};</span>
<span class="special">}}</span>
</pre>
<h4>
<a name="math_toolkit.catmull_rom.h1"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.description"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.description">Description</a>
</h4>
<p>
Catmull-Rom splines are a family of interpolating curves which are commonly
used in computer graphics and animation. Catmull-Rom splines enjoy the following
properties:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Affine invariance: The interpolant commutes with affine transformations.
</li>
<li class="listitem">
Local support of the basis functions: This gives stability and fast evaluation.
</li>
<li class="listitem">
<span class="emphasis"><em>C</em></span><sup>2</sup>-smoothness
</li>
<li class="listitem">
Interpolation of control points-this means the curve passes through the
control points. Many curves (such as Bézier) are <span class="emphasis"><em>approximating</em></span>
- they do not pass through their control points. This makes them more difficult
to use than interpolating splines.
</li>
</ul></div>
<p>
The <code class="computeroutput"><span class="identifier">catmull_rom</span></code> class provided
by Boost.Math creates a cubic Catmull-Rom spline from an array of points in
any dimension. Since there are numerous ways to represent a point in <span class="emphasis"><em>n</em></span>-dimensional
space, the class attempts to be flexible by templating on the point type. The
requirements on the point type are discussing in more detail below, but roughly,
it must have a dereference operator defined (e.g., <code class="computeroutput"><span class="identifier">p</span><span class="special">[</span><span class="number">0</span><span class="special">]</span></code>
is not a syntax error), it must be able to be dereferenced up to <code class="computeroutput"><span class="identifier">dimension</span> <span class="special">-</span><span class="number">1</span></code>, and <code class="computeroutput"><span class="identifier">p</span><span class="special">[</span><span class="identifier">i</span><span class="special">]</span></code>
is of type <code class="computeroutput"><span class="identifier">Real</span></code>, define <code class="computeroutput"><span class="identifier">value_type</span></code>, and the free function <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>. These
requirements are met by <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>
and <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span></code>. The basic usage is shown here:
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span> <span class="number">3</span><span class="special">>></span> <span class="identifier">points</span><span class="special">(</span><span class="number">4</span><span class="special">);</span>
<span class="identifier">points</span><span class="special">[</span><span class="number">0</span><span class="special">]</span> <span class="special">=</span> <span class="special">{</span><span class="number">0</span><span class="special">,</span><span class="number">0</span><span class="special">,</span><span class="number">0</span><span class="special">};</span>
<span class="identifier">points</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">=</span> <span class="special">{</span><span class="number">1</span><span class="special">,</span><span class="number">0</span><span class="special">,</span><span class="number">0</span><span class="special">};</span>
<span class="identifier">points</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">=</span> <span class="special">{</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">0</span><span class="special">};</span>
<span class="identifier">points</span><span class="special">[</span><span class="number">3</span><span class="special">]</span> <span class="special">=</span> <span class="special">{</span><span class="number">0</span><span class="special">,</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">};</span>
<span class="identifier">catmull_rom</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span> <span class="number">3</span><span class="special">>></span> <span class="identifier">cr</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">points</span><span class="special">));</span>
<span class="comment">// Interpolate at s = 0.1:</span>
<span class="keyword">auto</span> <span class="identifier">point</span> <span class="special">=</span> <span class="identifier">cr</span><span class="special">(</span><span class="number">0.1</span><span class="special">);</span>
</pre>
<p>
Here, <span class="emphasis"><em>s</em></span> varies between 0 and <span class="emphasis"><em>cr.max_parameter()</em></span>.
The latter's value depends on the choice of <span class="emphasis"><em>alpha</em></span>. In
order to interpolate the curve between /points[i]/ and /points[i+1]<span class="emphasis"><em>,
/s</em></span> should go from <span class="emphasis"><em>cr.parameter_at_point(i)</em></span>
and <span class="emphasis"><em>cr.parameter_at_point(i+1)</em></span>.
</p>
<p>
The spline can be either open or <span class="emphasis"><em>closed</em></span>, closed meaning
that there is some <span class="emphasis"><em>s > 0</em></span> such that <span class="emphasis"><em>P(s) =
P(0)</em></span>. The default is open, but this can be easily changed:
</p>
<pre class="programlisting"><span class="comment">// closed = true</span>
<span class="identifier">catmull_rom</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span> <span class="number">3</span><span class="special">>></span> <span class="identifier">cr</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">points</span><span class="special">),</span> <span class="keyword">true</span><span class="special">);</span>
</pre>
<p>
In either case, evaluating the interpolator at <span class="emphasis"><em>s=0</em></span> returns
the first point in the list.
</p>
<p>
If the curve is open, then the first and last segments may have strange behavior.
The traditional solution is to prepend a carefully selected control point to
the data so that the first data segment (second interpolator segment) has reasonable
tangent vectors, and simply ignore the first interpolator segment. A control
point is appended to the data using similar criteria. However, we recommend
not going through this effort until it proves to be necessary: For most use-cases,
the curve is good enough without prepending and appending control points, and
responsible selection of non-data control points is difficult.
</p>
<p>
Inside <code class="computeroutput"><span class="identifier">catmull_rom</span></code>, the curve
is represented as closed. This is because an open Catmull-Rom curve is <span class="emphasis"><em>implicitly
closed</em></span>, but the closing point is the zero vector. There is no reason
to suppose that the zero vector is a better closing point than the endpoint
(or any other point, for that matter), so traditionally Catmull-Rom splines
leave the segment between the first and second point undefined, as well as
the segment between the second-to-last and last point. We find this property
of the traditional implementation of Catmull-Rom splines annoying and confusing
to the user. Hence internally, we close the curve so that the first and last
segments are defined. Of course, this causes the <span class="emphasis"><em>tangent</em></span>
vectors to the first and last points to be bizarre. This is a "pick your
poison" design decision-either the curve cannot interpolate in its first
and last segments, or the tangents along the first and last segments are meaningless.
In the vast majority of cases, this will be no problem to the user. However,
if it becomes a problem, then the user should add one extra point in a position
they believe is reasonable and close the curve.
</p>
<p>
Since the routine internally represents the curve as closed, a question arises:
Why does the user have to specify if the curve is open or closed? The answer
is that the parameterization is chosen by the routine, so it is of interest
to the user to understand the values where a meaningful result is returned.
</p>
<pre class="programlisting"><span class="identifier">Real</span> <span class="identifier">max_s</span> <span class="special">=</span> <span class="identifier">cr</span><span class="special">.</span><span class="identifier">max_parameter</span><span class="special">();</span>
</pre>
<p>
If you attempt to interpolate for <code class="computeroutput"><span class="identifier">s</span>
<span class="special">></span> <span class="identifier">max_s</span></code>,
an exception is thrown. If the curve is closed, then <code class="computeroutput"><span class="identifier">cr</span><span class="special">(</span><span class="identifier">max_s</span><span class="special">)</span>
<span class="special">=</span> <span class="identifier">p0</span></code>,
where <code class="computeroutput"><span class="identifier">p0</span></code> is the first point
on the curve. If the curve is open, then <code class="computeroutput"><span class="identifier">cr</span><span class="special">(</span><span class="identifier">max_s</span><span class="special">)</span>
<span class="special">=</span> <span class="identifier">pf</span></code>,
where <code class="computeroutput"><span class="identifier">pf</span></code> is the final point
on the curve.
</p>
<p>
The Catmull-Rom curve admits an infinite number of parameterizations. The default
parameterization of the <code class="computeroutput"><span class="identifier">catmull_rom</span></code>
class is the so-called <span class="emphasis"><em>centripedal</em></span> parameterization. This
parameterization has been shown to be the only parameterization that does not
form cusps or self-intersections within segments. However, for advanced users,
other parameterizations can be chosen using the <span class="emphasis"><em>alpha</em></span>
parameter:
</p>
<pre class="programlisting"><span class="comment">// alpha = 1 is the "chordal" parameterization.</span>
<span class="identifier">catmull_rom</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="keyword">double</span><span class="special">,</span> <span class="number">3</span><span class="special">>></span> <span class="identifier">cr</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">points</span><span class="special">),</span> <span class="keyword">false</span><span class="special">,</span> <span class="number">1.0</span><span class="special">);</span>
</pre>
<p>
The alpha parameter must always be in the range <code class="computeroutput"><span class="special">[</span><span class="number">0</span><span class="special">,</span><span class="number">1</span><span class="special">]</span></code>.
</p>
<p>
Finally, the tangent vector to any point of the curve can be computed via
</p>
<pre class="programlisting"><span class="keyword">double</span> <span class="identifier">s</span> <span class="special">=</span> <span class="number">0.1</span><span class="special">;</span>
<span class="identifier">Point</span> <span class="identifier">tangent</span> <span class="special">=</span> <span class="identifier">cr</span><span class="special">.</span><span class="identifier">prime</span><span class="special">(</span><span class="identifier">s</span><span class="special">);</span>
</pre>
<p>
Since the magnitude of the tangent vector is dependent on the parameterization,
it is not meaningful (unless the user chooses the chordal parameterization
<span class="emphasis"><em>alpha = 1</em></span> which parameterizes by Euclidean distance between
points.) However, its direction is meaningful no matter the parameterization,
so the user may wish to normalize this result.
</p>
<h4>
<a name="math_toolkit.catmull_rom.h2"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.examples"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.examples">Examples</a>
</h4>
<h4>
<a name="math_toolkit.catmull_rom.h3"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.performance"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.performance">Performance</a>
</h4>
<p>
The following performance numbers were generated for a call to the Catmull-Rom
interpolation method. The number that follows the slash is the number of points
passed to the interpolant. We see that evaluation of the interpolant is 𝑶(<span class="emphasis"><em>log</em></span>(<span class="emphasis"><em>N</em></span>)).
</p>
<pre class="programlisting"><span class="identifier">Run</span> <span class="identifier">on</span> <span class="number">2700</span> <span class="identifier">MHz</span> <span class="identifier">CPU</span>
<span class="identifier">CPU</span> <span class="identifier">Caches</span><span class="special">:</span>
<span class="identifier">L1</span> <span class="identifier">Data</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x2</span><span class="special">)</span>
<span class="identifier">L1</span> <span class="identifier">Instruction</span> <span class="number">32</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x2</span><span class="special">)</span>
<span class="identifier">L2</span> <span class="identifier">Unified</span> <span class="number">262</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x2</span><span class="special">)</span>
<span class="identifier">L3</span> <span class="identifier">Unified</span> <span class="number">3145</span><span class="identifier">K</span> <span class="special">(</span><span class="identifier">x1</span><span class="special">)</span>
<span class="special">---------------------------------------------------------</span>
<span class="identifier">Benchmark</span> <span class="identifier">Time</span> <span class="identifier">CPU</span>
<span class="special">---------------------------------------------------------</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4</span> <span class="number">20</span> <span class="identifier">ns</span> <span class="number">20</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8</span> <span class="number">21</span> <span class="identifier">ns</span> <span class="number">21</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16</span> <span class="number">23</span> <span class="identifier">ns</span> <span class="number">23</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32</span> <span class="number">24</span> <span class="identifier">ns</span> <span class="number">24</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">64</span> <span class="number">27</span> <span class="identifier">ns</span> <span class="number">27</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">128</span> <span class="number">27</span> <span class="identifier">ns</span> <span class="number">27</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">256</span> <span class="number">30</span> <span class="identifier">ns</span> <span class="number">30</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">512</span> <span class="number">32</span> <span class="identifier">ns</span> <span class="number">31</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">1024</span> <span class="number">33</span> <span class="identifier">ns</span> <span class="number">33</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">2048</span> <span class="number">34</span> <span class="identifier">ns</span> <span class="number">34</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">4096</span> <span class="number">36</span> <span class="identifier">ns</span> <span class="number">36</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">8192</span> <span class="number">38</span> <span class="identifier">ns</span> <span class="number">38</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">16384</span> <span class="number">39</span> <span class="identifier">ns</span> <span class="number">39</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">32768</span> <span class="number">40</span> <span class="identifier">ns</span> <span class="number">40</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">65536</span> <span class="number">45</span> <span class="identifier">ns</span> <span class="number">44</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">131072</span> <span class="number">46</span> <span class="identifier">ns</span> <span class="number">46</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">262144</span> <span class="number">50</span> <span class="identifier">ns</span> <span class="number">50</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">524288</span> <span class="number">53</span> <span class="identifier">ns</span> <span class="number">52</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">>/</span><span class="number">1048576</span> <span class="number">58</span> <span class="identifier">ns</span> <span class="number">57</span> <span class="identifier">ns</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_BigO</span> <span class="number">2.97</span> <span class="identifier">lgN</span> <span class="number">2.97</span> <span class="identifier">lgN</span>
<span class="identifier">BM_CatmullRom</span><span class="special"><</span><span class="keyword">double</span><span class="special">></span><span class="identifier">_RMS</span> <span class="number">19</span> <span class="special">%</span> <span class="number">19</span> <span class="special">%</span>
</pre>
<h4>
<a name="math_toolkit.catmull_rom.h4"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.point_types"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.point_types">Point
types</a>
</h4>
<p>
We have already discussed that certain conditions on the <code class="computeroutput"><span class="identifier">Point</span></code>
type template argument must be obeyed. The following shows a custom point type
in 3D which can be used as a template argument to Catmull-Rom:
</p>
<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Real</span><span class="special">></span>
<span class="keyword">class</span> <span class="identifier">mypoint3d</span>
<span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="comment">// Must define a value_type:</span>
<span class="keyword">typedef</span> <span class="identifier">Real</span> <span class="identifier">value_type</span><span class="special">;</span>
<span class="comment">// Regular constructor--need not be of this form.</span>
<span class="identifier">mypoint3d</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">y</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">z</span><span class="special">)</span> <span class="special">{</span><span class="identifier">m_vec</span><span class="special">[</span><span class="number">0</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">x</span><span class="special">;</span> <span class="identifier">m_vec</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">y</span><span class="special">;</span> <span class="identifier">m_vec</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">z</span><span class="special">;</span> <span class="special">}</span>
<span class="comment">// Must define a default constructor:</span>
<span class="identifier">mypoint3d</span><span class="special">()</span> <span class="special">{}</span>
<span class="comment">// Must define array access:</span>
<span class="identifier">Real</span> <span class="keyword">operator</span><span class="special">[](</span><span class="identifier">size_t</span> <span class="identifier">i</span><span class="special">)</span> <span class="keyword">const</span>
<span class="special">{</span>
<span class="keyword">return</span> <span class="identifier">m_vec</span><span class="special">[</span><span class="identifier">i</span><span class="special">];</span>
<span class="special">}</span>
<span class="comment">// Must define array element assignment:</span>
<span class="identifier">Real</span><span class="special">&</span> <span class="keyword">operator</span><span class="special">[](</span><span class="identifier">size_t</span> <span class="identifier">i</span><span class="special">)</span>
<span class="special">{</span>
<span class="keyword">return</span> <span class="identifier">m_vec</span><span class="special">[</span><span class="identifier">i</span><span class="special">];</span>
<span class="special">}</span>
<span class="keyword">private</span><span class="special">:</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span> <span class="number">3</span><span class="special">></span> <span class="identifier">m_vec</span><span class="special">;</span>
<span class="special">};</span>
<span class="comment">// Must define the free function "size()":</span>
<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Real</span><span class="special">></span>
<span class="keyword">constexpr</span> <span class="identifier">size_t</span> <span class="identifier">size</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">>&</span> <span class="identifier">c</span><span class="special">)</span>
<span class="special">{</span>
<span class="keyword">return</span> <span class="number">3</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
These conditions are satisfied by both <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span></code> and
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, but it may nonetheless be useful
to define your own point class so that (say) you can define geometric distance
between them.
</p>
<h4>
<a name="math_toolkit.catmull_rom.h5"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.caveats"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.caveats">Caveats</a>
</h4>
<p>
The Catmull-Rom interpolator requires memory for three more points than is
provided by the user. This causes the class to call a <code class="computeroutput"><span class="identifier">resize</span><span class="special">()</span></code> on the input vector. If <code class="computeroutput"><span class="identifier">v</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">()</span> <span class="special">>=</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span>
<span class="special">+</span> <span class="number">3</span></code>,
then no problems arise; there are no reallocs, and in practice this condition
is almost always satisfied. However, if <code class="computeroutput"><span class="identifier">v</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">()</span> <span class="special"><</span> <span class="identifier">v</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span>
<span class="special">+</span> <span class="number">3</span></code>,
the <code class="computeroutput"><span class="identifier">realloc</span></code> causes a performance
penalty of roughly 20%.
</p>
<h4>
<a name="math_toolkit.catmull_rom.h6"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.generic_containers"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.generic_containers">Generic
Containers</a>
</h4>
<p>
The <code class="computeroutput"><span class="identifier">Point</span></code> type may be stored
in a different container than <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>.
For example, here is how to store the points in a Boost.uBLAS vector:
</p>
<pre class="programlisting"><span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p0</span><span class="special">(</span><span class="number">0.1</span><span class="special">,</span> <span class="number">0.2</span><span class="special">,</span> <span class="number">0.3</span><span class="special">);</span>
<span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p1</span><span class="special">(</span><span class="number">0.2</span><span class="special">,</span> <span class="number">0.3</span><span class="special">,</span> <span class="number">0.4</span><span class="special">);</span>
<span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p2</span><span class="special">(</span><span class="number">0.3</span><span class="special">,</span> <span class="number">0.4</span><span class="special">,</span> <span class="number">0.5</span><span class="special">);</span>
<span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p3</span><span class="special">(</span><span class="number">0.4</span><span class="special">,</span> <span class="number">0.5</span><span class="special">,</span> <span class="number">0.6</span><span class="special">);</span>
<span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p4</span><span class="special">(</span><span class="number">0.5</span><span class="special">,</span> <span class="number">0.6</span><span class="special">,</span> <span class="number">0.7</span><span class="special">);</span>
<span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">></span> <span class="identifier">p5</span><span class="special">(</span><span class="number">0.6</span><span class="special">,</span> <span class="number">0.7</span><span class="special">,</span> <span class="number">0.8</span><span class="special">);</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">numeric</span><span class="special">::</span><span class="identifier">ublas</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">>></span> <span class="identifier">u</span><span class="special">(</span><span class="number">6</span><span class="special">);</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">0</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p0</span><span class="special">;</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p1</span><span class="special">;</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p2</span><span class="special">;</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">3</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p3</span><span class="special">;</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">4</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p4</span><span class="special">;</span>
<span class="identifier">u</span><span class="special">[</span><span class="number">5</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">p5</span><span class="special">;</span>
<span class="comment">// Tests initializer_list:</span>
<span class="identifier">catmull_rom</span><span class="special"><</span><span class="identifier">mypoint3d</span><span class="special"><</span><span class="identifier">Real</span><span class="special">>,</span> <span class="keyword">decltype</span><span class="special">(</span><span class="identifier">u</span><span class="special">)></span> <span class="identifier">cat</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">u</span><span class="special">));</span>
</pre>
<h4>
<a name="math_toolkit.catmull_rom.h7"></a>
<span class="phrase"><a name="math_toolkit.catmull_rom.references"></a></span><a class="link" href="catmull_rom.html#math_toolkit.catmull_rom.references">References</a>
</h4>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Cem Yuksel, Scott Schaefer, and John Keyser, <span class="emphasis"><em>Parameterization
and applications of Catmull–Rom curves</em></span>, Computer-Aided Design
43 (2011) 747–755.
</li>
<li class="listitem">
Phillip J. Barry and Ronald N. Goldman, <span class="emphasis"><em>A Recursive Evaluation
Algorithm for a Class of Catmull-Rom Splines</em></span>, Computer Graphics,
Volume 22, Number 4, August 1988
</li>
</ul></div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="vector_barycentric.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interpolation.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="bezier_polynomial.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
