doc/parts/tutorial/chap-paths.sxml

   1 <!-- This file is part of Shapes.                                           -->
   2 <!--                                                                        -->
   3 <!-- Shapes is free software: you can redistribute it and/or modify         -->
   4 <!-- it under the terms of the GNU General Public License as published by   -->
   5 <!-- the Free Software Foundation, either version 3 of the License, or      -->
   6 <!-- any later version.                                                     -->
   7 <!--                                                                        -->
   8 <!-- Shapes is distributed in the hope that it will be useful,              -->
   9 <!-- but WITHOUT ANY WARRANTY; without even the implied warranty of         -->
  10 <!-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          -->
  11 <!-- GNU General Public License for more details.                           -->
  12 <!--                                                                        -->
  13 <!-- You should have received a copy of the GNU General Public License      -->
  14 <!-- along with Shapes.  If not, see <http://www.gnu.org/licenses/>.        -->
  15 <!--                                                                        -->
  16 <!-- Copyright 2008 Henrik Tidefelt                                         -->
  17
  18 <section id="chap-paths">
  19 <title>More on paths</title>
  20 <top>
  21 <p>In this chapter we'll explore some of the more powerful operations that can be performed on paths.</p>
  22 </top>
  23
  24 <section id="paths/spline-arc-time">
  25 <title>Spline time and arc time</title>
  26 <body>
  27         <p>Before discussing path sliders in the next section, we must introduce the concepts of <em>spline time</em> and <em>arc time</em>.  Recall that a path is a sequence of connected cubic splines, and that each spline segment can be parameterized by a scalar in the range 0 to 1.</p>
  28
  29         <p>First, a <em>spline time</em> is a real number used to refer to points on paths.  The integer part refers to a spline segment, with zero being the first segment, while the fractional part refers to a point on that segment.  Second, an <em>arc time</em> is a length used to refer to points on paths.  The length is simply the arc length from the beginning of the path to the point being referred to.</p>
  30
  31         <p>Note that spline time makes no sense from a geometric point of view.  To see this, note that any spline segment can be divided into several shorter spline segments, and that while this does not change the geometry of the path, it changes the interpretation of spline times along the path.  On the other hand, spline time is very natural from a computer representation point of view.  Therefore, all arc times are converted to spline times internally in <str-Shapes />, a procedure which relies on numeric integration.</p>
  32
  33         <p>While the numeric integration required to work with arc time may seem costly from a computational point of view, it is believed that working with features of geometry rather then representation is such an important tool that it is worth while the extra computation time.  While this argument may not have been feasible in the times when <str-MetaPost /> was designed, the computational power of personal computers has increased by huge amounts since then, and we think that computing arc lengths is a good use of this power.  Hence, users are recommended to avoid thinking in terms of spline time unless working explicitly with the underlying path representation.</p>
  34
  35         <p>Use the function <value name="abs" /> to find the total length of a path, and <value name="duration" /> to find the final spline time of a path.  Note that the duration of a closed path is 1 more than that of the corresponding open path.</p>
  36
  37 </body>
  38 </section><!-- End of paths/spline-arc-time -->
  39
  40
  41 <section id="paths/sliders">
  42 <title>Sliders</title>
  43 <body>
  44         <p>A <em>path slider</em>, generally referred to as just <em>slider</em>, is a location on a particular path.  It is the natural result of any operation that selects a point on a path, and gives access to local characteristics of the path such as tangent its direction and curvature.  In <str-Shapes />, a sub-range of a path is constructed by <em>connecting</em> one slider at the beginning of the range with another slider at the end of the range.</p>
  45
  46 <p>There are two types of sliders, depending on whether their paths are contained in <str-2D /> or <str-3D />, see <named-type name="PathSlider" /> and <named-type name="PathSlider3D" />, for details.</p>
  47
  48 <p>As the name suggests, a slider can be used to move along the path.  By adding <named-type name="Float" /> or <named-type name="Length" /> values to a slider, one obtains a new slider at the given distance from the original slider; <named-type name="Float" /> values move in terms of spline time, while <named-type name="Length" /> values move in terms of arc length.</p>
  49
  50 <p>The simplest operations that yield sliders on a path are either to access the fields <field name="begin" /> or <field name="end" />, or to <em>apply</em> the path like a function to a <named-type name="Float" /> value to construct a slider with the given spline time.  Similarly, if the path is applied to a <named-type name="Length" /> value, one obtains a slider at the given arc time.</p>
  51
  52 <p>The function <value name="..Shapes..Layout..mspoint" /> (read it as <em>mediation-slide point</em>) is a convenient way to specify the arc time relative to the arc length of the path itself.</p>
  53
  54 <p>The most often used field of a slider is its location in space.  The name of this field is <field name="p" />.  This along with other fields and slider use is shown in the next example.  Note that there are additional fields in <str-3D />, and that it is not obvious how to best extend the definitions from <str-2D /> to <str-3D />.</p>
  55
  56 <example-with-output title="Sliders" internal-id="example:slider-use">
  57 <image pdf="doc/tutorial-slider-use_3.pdf" jpg="doc/tutorial-slider-use_y_big.jpg" />
  58 <source file="doc/tutorial-slider-use.shape">
  59 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-slider-use.shape" -->]]>
  60 </source>
  61 <stdout>
  62 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-slider-use.stdout" -->]]>
  63 </stdout>
  64 <caption>
  65         <p>Sliders.  Given a slider, other sliders can be specified relative to the first one, either in terms of distance or in terms of spline time.  Then, there are many fields to access to get both geometric and representation-related information about the particular point along the path.  The right part of the picture shows that the velocity field <field name="v" /> varies along a circle, so this is an example of a non-geometric field.</p>
  66         <p>Note that arrows indicating direction have been given an arbitrary length.</p>
  67 </caption>
  68 </example-with-output>
  69
  70 </body>
  71 </section><!-- End of paths/sliders -->
  72
  73 <section id="paths/point-references">
  74         <title>Point references</title>
  75         <body>
  76                 <p>In this section, we shall describe the powerful ways of referring to points (one at a time) on paths.  Although most of these methods are defined and implemented in terms of optimization and that this may seem expensive from a computational point of view, one should keep in mind that precise computation of curve lengths (arc times) can be rather expensive too.  Hence, try to use the powerful abstractions presented here whenever you think they are the best match for your thinking, and resort only to less expensive alternatives when too lengthy computations are a fact.</p>
  77
  78                 <p>As usual, we concentrate on the methods in <str-2D />, and make at most minor comments regarding the <str-3D /> counterparts.</p>
  79
  80                 <p>Let us begin with a concept which appears also in <str-MetaPost />, namely to find the first point on a path where the path has a certain direction.  In <str-Shape /> one does not specify the direction, but maximize the function in an orthogonal direction.  This avoids undefined results when the given direction is never attained, and generalizes immediately to <str-3D />.  The function that does the job is <value name="maximizer" />.  Sometimes, one is only interested in a coarse maximization, looking only at the points where the path goes through a path point, in which case <value name="pathpoint_maximizer" /> does the job.  A third option is to maximize over all the control points of the path (the convex hull of which is known to contain the path).  Note, though, that while <value name="maximizer" /> and <value name="pathpoint_maximizer" /> yield a <named-type name="PathSlider" />, <value name="controlling_maximizer" /> cannot do this but returns a <named-type name="Coords" /> since the maximizing point is not on the path in general.</p>
  81
  82 <example-with-output title="Maximizers" internal-id="example:maximizer">
  83 <image pdf="doc/tutorial-maximizer_3.pdf" jpg="doc/tutorial-maximizer_y_big.jpg" />
  84 <source file="doc/tutorial-maximizer.shape">
  85 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-maximizer.shape" -->]]>
  86 </source>
  87 <caption>
  88         <p>Maximizing in the direction indicated by the arrow.  Control points of the path are marked by connecting them with blue lines to the path point they belong to.  The first maximizing point on the path is marked with a red spot, the first maximizing point through a path point is marked with a small circle, and the maximizing point among all the control points is marked with a cross.</p>
  89 </caption>
  90 </example-with-output>
  91
  92   <p>The next concept for point references is to minimize the distance to a given point.  This is done using <value name="approximator" />, and analogous to the maximization suite, there is also a <value name="pathpoint_approximator" />.  The next example gives an illustration in <str-2D />, but the concept makes sense and is implemented also in <str-3D />.</p>
  93
  94 <example-with-output title="Point approximators" internal-id="example:approximator">
  95 <image pdf="doc/tutorial-approximator_3.pdf" jpg="doc/tutorial-approximator_y_big.jpg" />
  96 <source file="doc/tutorial-approximator.shape">
  97 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-approximator.shape" -->]]>
  98 </source>
  99 <caption>
 100         <p>Minimizing the distance to the point marked with a cross.  The first maximizing point on the path is marked with a red spot, and the first maximizing point through a path point is marked with a small circle.</p>
 101 </caption>
 102 </example-with-output>
 103
 104   <p>Another concept for point references is that of intersection points.  This has only been implemented in <str-2D /> as the function <value name="intersection" /> (where the intersection with another path can be found), since <str-Shapes /> does not support the abstraction of a general surface in <str-3D />.  Note that there may be no intersection at all, in which case <value name="intersection" /> will invoke an error handler, see the following example.</p>
 105
 106 <example-with-output title="Path intersection" internal-id="example:intersection">
 107 <image pdf="doc/tutorial-intersection_3.pdf" jpg="doc/tutorial-intersection_y_big.jpg" />
 108 <source file="doc/tutorial-intersection.shape">
 109 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-intersection.shape" -->]]>
 110 </source>
 111 <caption>
 112         <p>Finding the first point on the solid black path (direction indicated by the arrow) where it intersects with the dashed blue path (direction not important).  The intersection is marked with a red spot, and an error handler is used to treat the case when there is no intersection.</p>
 113 </caption>
 114 </example-with-output>
 115
 116   <p>Finally, there is a generalization of intersection of paths which generalizes to <str-3D />, and that is to find the point where the path is closest to the other path.  Again, <value name="approximator" /> is the interface — depending on argument types, it will dispatch to the appropriate path-to-point or path-to-path algorithm.  Note that, in the absence of intersections, it is ill-conditioned to speak of order between equally closed points (since the distance cannot be computed exactly anyway).  The first example shows basic use, the following example shows how <value name="approximator" /> is used as an alternative to <value name="intersection" />.</p>
 117
 118 <example-with-output title="Path approximator" internal-id="example:path-approximator">
 119 <image pdf="doc/tutorial-path-approximator_3.pdf" jpg="doc/tutorial-path-approximator_y_big.jpg" />
 120 <source file="doc/tutorial-path-approximator.shape">
 121 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-path-approximator.shape" -->]]>
 122 </source>
 123 <caption>
 124         <p>Minimizing the distance to the dashed blue path.  The closest point on the path is marked with a red spot.  The corresponding point on the target path is found using path-to-point approximation, which is significantly cheaper, although it could be argued that this point should also be returned somehow from the path-to-path approximation.</p>
 125 </caption>
 126 </example-with-output>
 127
 128 <example-with-output title="Path intersection by approximation" internal-id="example:path-approximator-intersection">
 129 <image pdf="doc/tutorial-approximator-intersection_3.pdf" jpg="doc/tutorial-approximator-intersection_y_big.jpg" />
 130 <source file="doc/tutorial-approximator-intersection.shape">
 131 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-approximator-intersection.shape" -->]]>
 132 </source>
 133 <caption>
 134         <p>Using <value name="approximator" /> as a robust alternative to <value name="intersection" />.  Note that <value name="approximator" /> will (just like <value name="intersection" />) give the first intersection when there are several, and that the result is well defined also when there is no intersection (no need to set up an error handler, compare with the path intersection example above).</p>
 135 </caption>
 136 </example-with-output>
 137
 138   <p>OK, that's pretty much all for now; more point references may be added in the future.  However, it should be mentioned here that there is no built in support for evaluating the point references on anything smaller than the whole path.  The last example in this section shows how this can be done manually.</p>
 139
 140 <example-with-output title="Subpath intersection" internal-id="example:subpath-intersection">
 141 <image pdf="doc/tutorial-subpath-intersection_3.pdf" jpg="doc/tutorial-subpath-intersection_y_big.jpg" />
 142 <source file="doc/tutorial-subpath-intersection.shape">
 143 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)doc/tutorial-subpath-intersection.shape" -->]]>
 144 </source>
 145 <caption>
 146         <p>Finding the first point on the solid black path (direction indicated by the arrow), between the two circles, where it intersects with the dashed blue path (direction not important).  The intersection is marked with a red spot.  Note that one must make use of arc length rather than spline time to relate the slider on the sub path to a slider on the whole path (which makes this a bit more expensive and inaccurate compared to what a built-in solution could offer).</p>
 147 </caption>
 148 </example-with-output>
 149
 150         </body>
 151 </section><!-- End of paths/point-references -->
 152
 153 <section id="paths/upsampling">
 154         <title>Upsampling</title>
 155         <body>
 156                 <p>There are operations on paths that despite a seemingly simple abstraction turn out very complicated to implement to a reasonable degree of accuracy.  The design choice of <str-Shapes /> was not to provide lousy implementations of these abstractions, but to provide simpler operations that can be implemented accurately and that will allow users to make their own approximations of the difficult abstractions.  Basically, this comes down to means for folding over the discrete spline points defining a path, and means for generating a sufficiently dense <em>sampling</em> of the path.  Currently, there are only means for <em>upsampling</em>, that is, to generate a representation that uses more points to define the same geometric path.  The opposite, <em>downsampling</em> may be added in the future, but right now it is not even clear how the operation should be defined abstractly (note that downsampling will require the original path to be approximated somehow).</p>
 157
 158                 <p>In this section, we shall discuss the available methods for upsampling.  One of the methods refers to the Bezier spline representation of the new path, while the other methods have geometric meanings.</p>
 159
 160                 <p>Beginning with the method which is not geometric, we have <value name="upsample_balace" />, which will divide each spline in two, such that the velocity is continuous through the new sample point.  This will imply that the the two interpolation points around the new sample point are at equal distance (and opposite), hence the <em>balance</em> part of the name.  It turns out that the sample point will be at spline time 0.5, so the operation is very cheap.  Use this method if you need speed more than good properties of the upsampled path.</p>
 161
 162                 <p>The method <value name="upsample_inflections" /> adds samples where there were inflections on the spline segments of the original path.  The new path will only have spline segments without inflections, which can be a useful thing when reasoning about the path in terms of its spline segment representation.</p>
 163
 164                 <p>The method <value name="upsample_bends" /> may be the most useful method of them all.  It begins sampling at inflections (see <value name="upsample_inflections" />), and then it makes sure that each spline segment bends at most some given angle.  Since it is often the parts of a path where it bends most that are difficult to work with, this method often gives you samples where you need them most.</p>
 165
 166                 <p>The last method, <value name="upsample_every" />, simply ensures that each spline segment is shorter than some given length.  The idea is simple, but it is not clear to me when this is more useful than <value name="upsample_bends" />.</p>
 167
 168                 <p>The example below show the various methods applied to a variety of paths.</p>
 169
 170 <example-with-output title="Upsampling" internal-id="example:upsampling">
 171 <image pdf="features/upsample_3.pdf" jpg="features/upsample_y_big.jpg" />
 172 <source file="features/upsample.shape">
 173 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/upsample.shape" -->]]>
 174 </source>
 175 <caption>
 176         <p>Various ways of upsampling a path.</p>
 177 </caption>
 178 </example-with-output>
 179
 180 <p>We end this section with an example showing an application of upsampling.  The seemingly simple abstraction is to compute a path, following a given path at a certain distance.  Basically, one would like to be able to compute one of the boundaries of a stroke along the path, but it is easy to also imagine more interesting generalizations.  The idea is easy as long as the path has a radius of curvature being larger than the distance between the original and the new path, but when it is not the situation gets much more involved, and it is for this reason the (very important) operation is not included in the kernel.</p>
 181 <example-with-output title="Sidepaths" internal-id="example:sidepaths">
 182 <image pdf="features/sidepaths_3.pdf" jpg="features/sidepaths_y_big.jpg" />
 183 <source file="features/sidepaths.shape">
 184 <![CDATA[<!--#include depth="0" virtual="$(BUILDDIR)$(EXAMPLES)features/sidepaths.shape" -->]]>
 185 </source>
 186 <caption>
 187         <p>Application of upsampling:  Computing <em>side paths</em>.  Note that much of the interesting source code for this example is located in the extension <a extension="pathmapping" />.</p>
 188 </caption>
 189 </example-with-output>
 190
 191         </body>
 192 </section><!-- End of paths/upsampling -->
 193
 194 <section id="paths/join">
 195         <title>Joining paths</title>
 196         <body>
 197                 <p>It is possible to join two paths to create a longer path (which can then be joined with a third path, and so on).  This is done using the connection operator <operator name="--" />, which will connect the end of the first path with the beginning of the second path.  If these are not the ends one intends to join, one may have to reverse one of the paths, so that its beginning becomes its end, and vice versa.  To reverse a path, use the function <value name="reverse" />.  (At the time of writing, this is implemented by constructing a new path with everything reversed, but this may be changed with the help of a more efficient path representation in the future.)</p>
 198
 199                 <p>When paths are joined using the connection operator <operator name="--" />, one must be able to specify the interpolation points of the spline filling the gap from the first to the second path.  <str-Shapes /> does not provide an operation to attach an interpolation point on the outside of a path end, although this can be achieved using a technique to be described soon.</p>
 200
 201                 <p>For paths being constructed by joining path points, this is straight forward; even if the interpolation points on the outside of the first and last path point on an (open) path have no meaning when the path is stroked, the interpolation points still exist and will be used when the path is joined with more path points or other paths.</p>
 202
 203                 <p>However, when creating a path from a sub-range of another path, the basic operation of connecting two sliders will create a path without interpolation points on the outsides.  To specify interpolation points on the outside of the new path, one may attach interpolation points to the sliders before connecting them.  (By using this technique with the end point sliders of a path, one can thus attach or replace interpolation points on the outside end of a complete path.)</p>
 204
 205                 <p>Yet another way to join paths is to merge the end of the first path with the beginning of the second path, see <value name="meetpaths" /> for more details and an example.</p>
 206         </body>
 207 </section><!-- End of paths/misc -->
 208
 209 </section><!-- End of chap-paths -->