libs/math/doc/html/math_toolkit/catmull_rom.html

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