Nathan Litke's Home Page

Nathan Litke
	Ph.D. in Computer Science received June 2005, Caltech. Alumnus of the Multi-Res Modeling Group. Now at digitalfish. Ph.D. thesis: Variational methods in surface parameterization Contact:

Publications

The correspondence generated between two surfaces by our algorithm is used to transfer a texture and create a blend.

An Image Processing Approach to Surface Matching (Nathan Litke, Marc Droske, Martin Rumpf and Peter Schröder), Proceedings of the Symposium on Geometry Processing 2005.
Abstract: Establishing a correspondence between two surfaces is a basic ingredient in many geometry processing applications. Existing approaches, which attempt to match two meshes directly in 3D, can be cumbersome to implement and it is often hard to produce accurate results in a reasonable amount of time. In this paper, we present a new variational method for matching surfaces that addresses these issues. Instead of matching two surfaces directly in 3D, we apply well-established matching methods from image processing in the parameter domains of the surfaces. A matching energy is introduced that can depend on curvature, feature demarcations or surface textures, and a regularization energy controls length and area changes in the induced non-rigid deformation between the two surfaces. The metric on both surfaces is properly incorporated into the formulation of the energy. This approach reduces all computations to the 2D setting while accounting for the original geometries. Consequently a fast multiresolution numerical algorithm for regular image grids can be used to solve the global optimization problem. The final algorithm is robust, generically much simpler than direct matching methods, and very fast for highly resolved triangle meshes.
Video: AVI (9.4MB, requires DivX), Quicktime (87.2MB)

The parameter domain and a texture map of a variationally-optimal parameterization, which balances length, area and angle distortion.

Axioms and Variational Problems in Surface Parameterization (Ulrich Clarenz, Nathan Litke and Martin Rumpf), Computer Aided Geometric Design 21 (8), 2004.
Abstract: For a surface patch on a smooth, two-dimensional surface in R³, low-distortion parameterizations are described in terms of minimizers of suitable energy functionals. Appropriate distortion measures are derived from principles of rational mechanics, closely related to the theory of non-linear elasticity. The parameterization can be optimized with respect to the varying importance of conformality, length preservation and area preservation. A finite element discretization is introduced and a constrained Newton method is used to minimize a corresponding discrete energy. Results of the new approach are compared with other recent parameterization methods.

The patch layout and globally smooth parameterization for a genus-1 surface.

Globally Smooth Parameterizations with Low Distortion (Andrei Khodakovsky, Nathan Litke and Peter Schröder), SIGGRAPH 2003 (BibTeX).
Abstract: Good parameterizations are of central importance in many digital geometry processing tasks. Typically the behavior of such processing algorithms is related to the smoothness of the parameterization and how much distortion it contains. Since a parameterization maps a bounded region of the plane to the surface, a parameterization for a surface which is not homeomorphic to a disc must be made up of multiple pieces. We present a novel parameterization algorithm for arbitrary topology surface meshes which computes a globally smooth parameterization with low distortion. We optimize the patch layout subject to criteria such as shape quality and metric distortion, which are used to steer a mesh simplification approach for base complex construction. Global smoothness is achieved through simultaneous relaxation over all patches, with suitable transition functions between patches incorporated into the relaxation procedure. We demonstrate the quality of our parameterizations through numerical evaluation of distortion measures and the excellent rate distortion performance of semi-regular remeshes produced with these parameterizations. The numerical algorithms required to compute the parameterizations are robust and run on the order of minutes even for large meshes.

A subdivision surface is fitted to scan data and deformed to create a new expression.

Fitting Subdivision Surfaces (Nathan Litke, Adi Levin, and Peter Schröder), Proceedings of Scientific Visualization 2001 (BibTeX).
Abstract: We introduce a new algorithm for fitting a Catmull-Clark subdivision surface to a given shape within a prescribed tolerance, based on the method of quasi-interpolation. The fitting algorithm is fast, local and scales well since it does not require the solution of linear systems. Its convergence rate is optimal for regular meshes and our experiments show that it behaves very well for irregular meshes. We demonstrate the power and versatility of our method with examples from interactive modeling, surface fitting, and scientific visualization.

An example of a trimmed subdivision surface.

Trimming for Subdivision Surfaces (Nathan Litke, Adi Levin, and Peter Schröder), Computer Aided Geometric Design 18 (5), 2001 (BibTeX).
Abstract: Trimming is an important primitive operation in geometric modeling. It is also the root of many numerical and topological problems in modern NURBS based CAGD systems. In this paper we introduce a new method for trimming subdivision surfaces. It is based on the use of combined subdivision schemes to guarantee exact interpolation of trim curves. The latter ensures, for example, that if two surfaces share a trim curve, they will meet exactly at the trim curve. In contrast to traditional approaches to trimming (e.g., for NURBS) we construct a new control mesh with each trim operation. This causes a perturbation of the surface near the trim region, which we control through the use of multiresolution details. These are computed rapidly and at low cost with the help of a novel set of quasi-interpolation operators. We demonstrate our algorithm with a number of examples.