| blob | 2f60da70b2128b5c8e355a4882aa0e34e6eb2c45 |
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, 2009 Henrik Tidefelt -->
18 <section id="algorithm/approximators">
19 <title>Path approximators</title>
20 <top>
21 <p><str-Shapes /> can search a point on a path which is closest to a given point or another path. The algorithms are designed to be similar in <str-2D /> and <str-3D /> to reduce development time and facilitate maintenance of the code. Hence, only when the difference is important, we shall be explicit regarding dimensions.</p>
22 <p>The algorithms described here are accessed through <value name="approximator" />.</p>
23 </top>
25 <section id="algorithm/approximators/point">
26 <title>Path-to-point approximation</title>
27 <body>
28 <p>Since the distance between a line segment and the given point can be computed cheaply, the algorithm begins by scanning all the endpoints of the cubic spline segments and any straight line segments for an upper bound on the distance between the path and the point (recording where this distance was obtained). All curved segments are put in a job queue.</p>
29 <p>Before we continue, we just make a note of the representation used in the job queue. For each curved segment we make a base element, containing various precomputed coefficients of the spline position and its first and second derivatives. A job item is then a structure with a reference to a base element and an interval of spline times on the segment. Hence, a job item is a sub-segment of one of the original curved segments, and we shall generally speak of <em>job item</em> and <em>sub-segment</em> interchangeably..</p>
30 <p>To process the job queue, we need to compute lower bounds on the distance between sub-segment and the point, and a way to split sub-segments to obtain better estimates of the distance. With these tools at hand, a branch-and-bound algorithm is easily constructed, and we shall not go into the details of this. (Just note that each point where a sub-segment is split will be used to obtain improved upper bounds on the distance.)</p>
31 <p>To obtain lower bounds for a sub-segment, we use that the sub-segment is contained in the convex hull of the control points representation of the sub-segment. The distance between the convex hull of a set of generators and the given point can be computed in several ways, and one should use methods that are robust and efficient in the case of only four generators. Iterative improvement algorithms such as Gilbert's algorithm are avoided since it is thought that sub-optimal estimates could lead to poor convergence in ill-conditioned problems. This thought should be verified by experiments. In the meantime, we could have used the recently developed active set polytope distance algorithm (or a version of it tailored to the case of one polytope having just one generator), but we don't since it was not available at the time when the path-to-point algorithm was written. Instead, we use a scheme that enumerates the facets of the polytope, and think that this may actually be quite efficient when there is only four generators.</p>
32 <p>Computing where to split a segment is rather tricky compared to obtaining the lower bounds. The reason is that poor strategies may lead to very poor convergence (or no convergence at all) of the branch and bound algorithm. For instance, it is necessary that the splitting always result in segments that are at most some fixed factor less than one of the size of the sub-segment being split. This property will ensure that all sub-segments will eventually be shorter than <tol-param name="arcdelta" />, in which case no further splitting is made. The splitting should also occur at a local optimum along the sub-segment, as this will hopefully yield two new sub-segments which are both further away (from the given point) than the point where the split occurred. To find a good local optimizer, we first use a sparse grid of points, and from the best of these we use Newton's method.</p>
33 </body>
34 </section>
36 <section id="algorithm/approximators/path">
37 <title>Path-to-path approximation</title>
38 <body>
39 <p>Path-to-path approximation is a generalization of path-to-path intersections in <str-2D />, which is both robust in the sense that no intersection is needed for the result to be well defined, and which generalizes nicely to <str-3D /> (path-to-path intersection in <str-3D /> is not a very useful concept). To generalize the intersection computation in <str-2D /> some care must be taken to insure that the first intersection is returned if there are more than one intersection, but this causes only minor thought to implement and we shall not discuss this further.</p>
40 <p>The algorithm reminds much of the path-to-point algorithm, with the major difference that the search is now performed in a two-dimensional space (one spline time along each path). The distance between pairs of straight line segments may still be computed cheaply during the initialization of the algorithm, but any other combination of straight and curved segments are pushed on the job queue.</p>
41 <p>The same type of two-layered representation of the job items is used here as in the path-to-point algorithm, with one base element for each pair of original spline segments, and the two major tasks are the computation of lower bounds and splitting times. As in the path-to-point algorithm, lower bounds are obtained by computing the distance between the convex hulls of the control point representation of the two sub-segments in a job item. For this, an active set algorithm is used. The active set algorithm deserves its own documentation, but it remains to be written (at this time, we just remark that <tol-param name="disttol" /> is related to Lagrange multipliers by a nice geometric interpretation of a scaled gradient). When computing where to split a job item, it is important that both sub-segments are divided so that they both eventually become smaller than <tol-param name="arcdelta" />. (Just making the “area” spanned by the job item's two dimensions tend to zero is not enough, as there is no efficient way to estimate the distance between a long and a very short sub-segment — two very short segments, on the other hand, are well approximated by their control point convex hull distance.) Again (as in the path-to-point algorithm) we first use a grid and then Newton's method.</p>
42 </body>
43 </section>
45 </section>