Computer tools for creating, analyzing and modifying geometry are the core component in computer-aided design systems, indispensable for engineering and product prototyping, surgical simulation, prosthesis design, dentistry, architecture, computer animation and games. There is a considerable demand for high-level modeling tools, expressing the user?s intent directly while being capable of handling complex models robustly. Surface optimization techniques unify traditional ab initio modeling of high-quality surfaces and manipulation of existing geometric data in a single natural framework by specifying suitable optimization functionals governing the surface behavior. This framework is conceptually representation-independent: the surface can be approximated by spline patches, subdivision surfaces, meshes or in implicit form. While this framework is highly appealing for practical applications, surface optimization rarely finds its way into industrial applications, as existing interactive techniques are not sufficiently robust, while the more precise and reliable methods are too slow to be used interactively.

This research project develops fundamental mathematical and algorithmic techniques essential for bringing surface optimization methods to mainstream geometric modeling applications. The research is addressing the following problems: shape representation and its accuracy, such that the modeled surfaces depend solely on the user input and not the particular choice of sampling or approximation basis; robust and efficient modeling algorithms to ensure predictable and responsive behavior in interactive applications; diverse control to allow sufficient freedom for arbitrary shape manipulation. The investigated approach has two key components: multifield geometry descriptions, building on ideas from discrete geometry, high-order geometric modeling, and finite elements and novel multiscale numerical solvers that combine robust global algorithms at coarse scales with fast and accurate algorithms at fine scales to achieve the performance and robustness needed in applications. The new methods are explored in the context of high-level modeling tasks, including modeling from two-dimensional projections or drawings, feature-based and appearance-based editing and template fitting for dental CAD.

Project Report

Geometric algorithms are used in a broad variety of contexts, from computer animation for modeling characters and objects, to engineering design, for creating and virtually testing products, to medical imaging. Accuracy and robustness are of essence in many of these applications. The focus of this project was on developing novel robust and accurate versions of several important geometric algorithms, using the "multifield" approach, that involves using several variables at each point simultaneously to solve geometric optimization problems. The project funding resulted in a number of advances in geometry processing. We expect that techniques we have developed will be relevant in a broader context, including applications to engineering analysis, physical simulation and medical imaging. For surface deformations, an essential technique for a variety of applications (e.g., defining a smooth motion of a character by moving just few points on the surface, or designing free-form shape for a car hood) we have developed a method allowing to ensure that the result of certain types of deformations depends primarily on the shape itself, rather how it was sampled for computational purposes to produce a mesh. At the same time, our approach allows us to systematically formulate a variety of conditions on the deformation behavior on the shape boundary, which often determines the overall behavior. In a related direction, we have developed a feature-based modeling method, using an additional scalar field on the surface to represent features. of a shape. Feature-based modeling in general is an evolving trend in geometric modeling, where low-level modeling operations were long researched, and high-level, semantically-enhanced modeling is now being looked at. Many important advances were made in the theory and practical algorithms for surface parametrization, that is, mapping a surface to the plane. This basic operation is needed for many geometry processing operations: texture mapping, surface compression, shape matching, reverse engineering of CAD surface descriptions. These advances include: (1) a method for parametrizing 3D range-scan data directly, without mesh reconstruction; (2) new methods for placing parametrization singularities that minimize distortion, an important quality measure for parametrization, simultaneously developing new insights into the fundamental problem of determining the optimal number of singularities of a parametrization (3) a scalable approach to parametrization extending existing techniques for larger objects with tens to hundreds millions of vertices. All these techniques were based on increasingly tightly integrating two views of the parametrization maps -- piecewise-linear maps and vector fields. We have developed a novel technique for high-order representation of surfaces combining features of T-splines (ability to handle control T-meshes which as we have shown are a natural match for global parametrization), and subdivision surfaces, one of the most commonly used ways to construct complex shapes.The combination of the algorithms and methods resulted in significant improvements both in quality, scalability and robustness of computed maps.

Agency
National Science Foundation (NSF)
Institute
Division of Information and Intelligent Systems (IIS)
Application #
0905502
Program Officer
Lawrence Rosenblum
Project Start
Project End
Budget Start
2009-07-15
Budget End
2013-12-31
Support Year
Fiscal Year
2009
Total Cost
$739,111
Indirect Cost
Name
New York University
Department
Type
DUNS #
City
New York
State
NY
Country
United States
Zip Code
10012