Geometric Optimization with Moving and Deformable Objects

In Geometric Computing there is a wide variety of application areas for geometric optimization algorithms that deal with the positioning or deformation of geometric objects (curves, surfaces, triangulated meshes, ...). These algorithms can benefit from an adequate representation of the distance function to a geometric object, e.g. for fast computation of the `closeness` of objects, collision detection, or penetration depth. An optimal description of the distance function is especially important since the most time consuming part of the considered geometric optimization algorithms is the computation of the shortest distance between geometric objects. Consequently, a key issue of this project will be to approximate the distance functions of geometric objects with a hierarchical representation scheme that elegantly exploits the geometry of the distance function. The main focus lies on the speed and robustness of our algorithms, furthermore the applicability on a wide range of geometric optimization problems is highly important. The applications we have in mind include the so-called registration problem of Computer Vision. There, one or more objects are displaced in 3-dimensional Euclidean space such that they optimally fit each other or match other given objects. Our goal is to give alternatives to current iterative algorithms in order to reduce computational cost and the number of iteration steps till convergence. Thus they can be used in 3D vision systems for industrial quality control. Another positioning problem from robotics is the smooth motion design in the presence of obstacles. Here, we pursue new subdivision algorithms for designing motions which interpolate or approximate given positions and avoid given obstacles. This is related to the computation of interpolating or approximating spline curves on manifolds, which will be pursued as well. The basic concepts of our algorithms are also applicable for the efficient treatment of deforming a geometric object into a prescribed shape. In this way, the approximation of a given surface (or data point set) by a B-spline surface or a subdivision surface can be iteratively computed without estimating parameter values to the given data points. Restrictions to convexity preserving approximation and approximation with special surface classes (translational surfaces, ruled surfaces) are possible. This method has important applications, e.g. in Reverse Engineering and Computer Graphics.

Digital cameras for shooting two-dimensional (2D) images are inexpensive and thus nowadays even built into cell phones or other handheld devices. Digital devices that can be used to take three-dimensional (3D) images are much more expensive and are currently only available at universities or in companies. The same is true for the software accompanying these cameras. While 2D image processing software for 2D digital images is widely available and usually shipped with the camera, 3D geometry processing software for 3D digital images is expensive and still lacking a lot of functionality. Researchers working in the FWF funded project "Geometric Optimization with Moving and Deformable Objects" succeeded to solve some of the open fundamental questions that arise with processing 3D geometric data. One class of 3D image recorders scans the surface of objects and returns a cloud of 3D measurement points. Usually we need several such scans to cover the whole surface of a 3D object. Complex objects may need hundreds or even thousands of scans so that they are faithfully represented. One fundamental task is to stitch together all scans of an object to get a complete 3D digital image of it. This process usually needs manual intervention which can be very time consuming. With the ever increasing amount of available 3D data there is an urgent need for a fully automatic solution. A further step in the processing pipeline is the generation of surface models from the point cloud data. The intensive fundamental research performed in the present project led to very promising results that will help in the future to develop better 3D geometry processing software that is easier to use and works more automatically than today.