IJPAM: Volume 51, No. 4 (2009)
MULTIGRID DYNAMICAL PROGRAMMING ON
EXPO-RATIONAL TENSOR-PRODUCT SURFACES
Institute for Information, Energy and Space Technology
Narvik University College
2, Lodve Lange's St., P.O. Box 385, N-8505, Narvik, NORWAY
Abstract.In [#!CA!#] the problem about finding geodesics on parametric surfaces with a given known parametrization was considered. The purpose of the present work is to study the possibility to compute geodesics and possibly some other types of optimal curves on surfaces in the more general situation when a parametrization of the surface is not readily available, but information about this surface is only given on a discrete rectangular set of points. This information may include only position of the point on the surface, or it may also include information about derivatives of the parametrized surface. From the discrete set of points, by interpolation, a parametrization of the surface is generated which interpolates the given data. For this purpose we use expo-rational B-spline (ERBS) surfaces. A remarkable advantage of ERBS compared to traditional tools of computer-aided geometric design, such as, polynomial B-splines and NURBS, is that ERBS tensor-product surfaces have -smooth parametrization even when they are only -continuous.
We confirm the remarks made in section 6 of [#!CA!#] that the property "-smooth non-regular parametrization of a -continuous surface" can be used to obtain efficient and elegant extension of the methods for exact or numerical minimization of smooth functionals to the case of non-smooth ones.
The direct optimization method of multigrid dynamic programming type, proposed in [#!CA!#] and [#!CB!#] is completed with an implementation of the A**-method introduced here, which is an upgrade of the so-called A*-search method (see [#!WA!#]). The main difference between the A**-method for global search, and its analogue in [#!CA!#] and [#!CB!#] is that the cross sections of the dynamic programming are smaller in size than in [#!CA!#] which leads to lower computational cost for achieving results which are very close to the results of [#!CA!#]. Thus, the dynamical programming method proposed here can be used for verification of the dynamical programming method proposed in [#!CA!#] and [#!CB!#], and vice versa.
Here several types of cost functionals are considered; however, similar to [#!CA!#], only the case of shortest length (geodesics) is considered in detail. Similar to [#!CB!#], constraints of several types are studied, both of equality or inequality type, smooth or non-smooth.
One of the advantages of the present algorithm, compared to the methods on triangulated surfaces as discussed in [#!CD!#], is its easy upgrading to 3D volume deformations and higher-dimensional manifolds. The use of expo-rational B-splines allows a simple uniform classical variational approach to the handling of both very smooth and non-smooth geometrical data, including cases where subgradient methods for non-smooth optimization do not work (for example, for Lip- cost functionals and/or constraints with ).
The extension of the definition of expo-rational B-splines for triangulated manifolds (see [#!D1!#]) allows the method considered here for tensor-product surfaces to be extended for general triangulated manifolds. It also allows to upgrade the method of geodesic Bezier curves proposed in [#!MA!#] so that the challenges of handling non-smooth and very smooth manifolds (see Subsection 7.1 in [#!MA!#]) are simultaneously overcome in a uniform way. The uniformity and robustness of the expo-rational B-spline parametrization has considerable potential even in cases where parametric models are considered less efficient than implicit and other non-parametric geometric representations (see, e.g., [#!PA!#]).
The animated 3D visualization used for the illustrations given here
is based on C++/OpenGL, using the in-house library GM_lib developed
at Narvik University College, Norway, and Qt window handling.
Received: April 17, 2008
AMS Subject Classification: 49L20, 53C22, 65D07, 26B35, 33F05, 41A05, 41A15, 41A30, 41A55, 41A63, 53A04, 53A05, 65D05, 65D17, 65D18, 65Y25, 68U05, 68U07
Key Words and Phrases: local, global, optimization, algorithm, discrete time, continuous time, dynamical system, variational calculus, optimal control, Bellman's optimality principle, dynamical programming, direct optimization method, cost-functional, smooth, non-smooth, Lipschitz, cuspidal, discontinuous, additive, constraint, equality, inequality, computational complexity, grid refinement, resolution tolerance, multigrid, triangulation, parametric curve, parametric surface, computer-aided geometric design, global geodesics, numerical integration, error, stability, sensitivity, robustness, small perturbation
Source: International Journal of Pure and Applied Mathematics