Fall 2004 Graphics Seminar

"Parameterization and Mesh Editing"

September 28

Budi Purnomo
Tarini, Hormann, Cignoni, and Montani
Proceedings of SIGGRAPH 2004. pp. 853-860.

Standard texture mapping of real-world meshes suffers from the presence of seams that need to be introduced in order to avoid excessive distortions and to make the topology of the mesh compatible to the one of the texture domain. In contrast, cube maps provide a mechanism that could be used for seamless texture mapping with low distortion, but only if the object roughly resembles a cube. We extend this concept to arbitrary meshes by using as texture domain the surface of a polycube whose shape is similar to that of the given mesh. Our approach leads to a seamless texture mapping method that is simple enough to be implemented in currently available graphics hardware.

October 5

Joe Hennessey
Laplacian Surface Editing
Olga Sorkine, Daniel Cohen-Or, Yaron Lipman, and Marc Alexa
Symposium on Geometry Processing 2004.

Surface editing operations commonly require geometric details of the surface to be preserved as much as possible. We argue that geometric detail is an intrinsic property of a surface and that, consequently, surface editing is best performed by operating over an intrinsic surface representation. We provide such a representation of a surface, based on the Laplacian of the mesh, by encoding each vertex relative to its neighborhood. The Laplacian of the mesh is enhanced to be invariant to locally linearized rigid transformations and scaling. Based on this Laplacian representation, we develop useful editing operations: interactive free-form deformation in a region of interest based on the transformation of a handle, transfer and mixing of geometric details between two surfaces, and transplanting of a partial surface mesh onto another surface. The main computation involved in all operations is the solution of a sparse linear system, which can be done at interactive rates. We demonstrate the effectiveness of our approach in several examples, showing that the editing operations change the shape while respecting the structural geometric detail
October 12

Peter Yee
Mesh Editing with Poisson-Based Gradient Field Manipulation
Yizhou Yu, Kun Zhou, Dong Xu Xiaohan Shi, Hujun Bao, Baining Guo, Heung-Yeung Shum

In this paper, we introduce a novel approach to mesh editing with the Poisson equation as the theoretical foundation. The most distinctive feature of this approach is that it modifies the original mesh geometry implicitly through gradient field manipulation. Our approach can produce desirable and pleasing results for both global and local editing operations, such as deformation, object merging, and smoothing. With the help from a few novel interactive tools, these operations can be performed conveniently with a small amount of user interaction. Our technique has three key components, a basic mesh solver based on the Poisson equation, a gradient field manipulation scheme using local transforms, and a generalized boundary condition representation based on local frames. Experimental results indicate that our framework can outperform previous related mesh editing techniques.

October 19

Jim Houser
Multii-chart Geometry Images
Sander, Wood, Gortler, Snyder, and Hoppe
Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. pp. 146-155. 2003.

We introduce multi-chart geometry images, a new representation for arbitrary surfaces. It is created by resampling a surface onto a regular 2D grid. Whereas the original scheme of Gu et al. maps the entire surface onto a single square, we use an atlas construction to map the surface piecewise onto charts of arbitrary shape. We demonstrate that this added flexibility reduces parametrization distortion and thus provides greater geometric fidelity, particularly for shapes with long extremities, high genus, or disconnected components. Traditional atlas constructions suffer from discontinuous reconstruction across chart boundaries, which in our context create unacceptable surface cracks. Our solution is a novel zippering algorithm that creates a watertight surface. In addition, we present a new atlas chartification scheme based on clustering optimization.
October 26

Matthew Bolitho
Smooth Geometry Images
Losasso, Hoppe, Schaefer, and Warren
Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. pp. 138-145. 2003.

Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches (e.g. plines, NURBS, recursively subdivided polygons). We introduce a simple construction for these surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image. We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports scalar displacement mapping.
November 2

Pavan Piratla
Global conformal surface parameterization
Xianfeng Gu  and Shing-Tung Yau
Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. pp. 127-137. 2003.

We solve the problem of computing global conformal parameterizations for surfaces with nontrivial topologies. The parameterization is global in the sense that it preserves the conformality everywhere except for a few points, and has no boundary of discontinuity. We analyze the structure of the space of all global conformal parameterizations of a given surface and find all possible solutions by constructing a basis of the underlying linear solution space. This space has a natural structure solely determined by the surface geometry, so our computing result is independent of connectivity, insensitive to resolution, and independent of the algorithms to discover it. Our algorithm is based on the properties of gradient fields of conformal maps, which are closedness, harmonity, conjugacy, duality and symmetry. These properties can be formulated by sparse linear systems, so the method is easy to implement and the entire process is automatic. We also introduce a novel topological modification method to improve the uniformity of the parameterization. Based on the global conformal parameterization of a surface, we can construct a conformal atlas and use it to build conformal geometry images which have very accurate reconstructed normals.

November 9

Chris Niski
Spherical Parametrization and Remeshing
Emil Praun and Hugues Hoppe
ACM SIGGRAPH 2003, 340-349.

The traditional approach for parametrizing a surface involves cutting it into charts and mapping these piecewise onto a planar domain. We introduce a robust technique for directly parametriz-ing a genus-zero surface onto a spherical domain. A key ingredient for making such a parametrization practical is the minimization of a stretch-based measure, to reduce scale-distortion and thereby prevent undersampling. Our second contri-bution is a scheme for sampling the spherical domain using uniformly subdivided polyhedral domains, namely the tetrahe-dron, octahedron, and cube. We show that these particular semi-regular samplings can be conveniently represented as completely regular 2D grids, i.e. geometry images. Moreover, these images have simple boundary extension rules that aid many processing operations. Applications include geometry remeshing, level-of-detail, morphing, compression, and smooth surface subdivision.
November 16

Ashley Fernandes

Iso-charts: Stretch-driven Mesh Parameterization using Spectral Analysis
Kun Zhou, John Snyder, Baining Guo, Heung-Yeung Shum
Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. pp 47-56. 2004.

We describe a fully automatic method, called iso-charts, to create texture atlases on arbitrary meshes. It is the first
to consider stretch not only when parameterizing charts, but also when forming charts. The output atlas bounds
stretch by a user-specified constant, allowing the user to balance the number of charts against their stretch. Our
approach combines two seemingly incompatible techniques: stretch-minimizing parameterization, based on the
surface integral of the trace of the local metric tensor; and the "isomap " or MDS (multi-dimensional scaling)
parameterization, based on an eigen-analysis of the matrix of squared geodesic distances between pairs of mesh
vertices. We show that only a few iterations of nonlinear stretch optimization need be applied to the MDS param-
eterization to obtain low-stretch atlases. The close relationship we discover between these two parameterizations
also allows us to apply spectral clustering based on MDS to partition the mesh into charts having low stretch.
We also novelly apply the graph cut algorithm in optimizing chart boundaries to further minimize stretch, follow
sharp features, and avoid meandering. Overall, our algorithm creates texture atlases quickly, with fewer charts
and lower stretch than previous methods, providing improvement in applications like geometric remeshing. We
also describe an extension, signal-specialized atlas creation, to efficiently sample surface signals, and show for
the first time that considering signal stretch in chart formation produces better texture maps.

November 23

Yuan Chen
Signal-Specialized Parameterization for Piecewise Linear Reconstruction
Geetika Tewari, John Snyder, Pedro V. Sander, Steven J. Gortler, Hugues Hoppe
Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing.  pp 57-66. 2004.

We propose a metric for surface parameterization specialized to its signal that can be used to create more efficient, high-quality texture maps. Derived from Taylor expansion of signal error, our metric predicts the signal approximation error - the difference between the original surface signal and its reconstruction from the sampled texture. Unlike previous methods, our metric assumes piecewise-linear reconstruction, and thus makes a good approximation to bilinear reconstruction employed in graphics hardware. We achieve significant savings in texture area for a desired signal accuracy compared to the signal-specialized parameterization metric proposed by Sander et al. in the 2002 Eurographics Workshop on Rendering.
November 30

Jonathan Bilodeau
Cross-parameterization and compatible remeshing of 3D models
Kraevoy and Scheffer
Proceedings of SIGGRAPH 2004. pp. 861-869

Many geometry processing applications, such as morphing, shape blending, transfer of texture or material properties, and fitting template meshes to scan data, require a bijective mapping between two or more models. This mapping, or cross-parameterization, typically needs to preserve the shape and features of the parameterized models, mapping legs to legs, ears to ears, and so on. Most of the applications also require the models to be represented by compatible meshes, i.e. meshes with identical connectivity, based on the cross-parameterization. In this paper we introduce novel methods for shape preserving cross-parameterization and compatible remeshing. Our cross-parameterization method computes a low-distortion bijective mapping between models that satisfies user prescribed constraints. Using this mapping, the remeshing algorithm preserves the user-defined feature vertex correspondence and the shape correlation between the models. The remeshing algorithm generates output meshes with significantly fewer elements compared to previous techniques, while accurately approximating the input geometry. As demonstrated by the examples, the compatible meshes we construct are ideally suitable for morphing and other geometry processing applications.

December 7

Nat Duca
Interpolating and Approximating Implicit Surfaces From Polygon Soup
Chen Shen, James F. OBrien, and Jonathan R. Shewchuk

This paper describes a method for building interpolating or approximating implicit surfaces from polygonal data. The user can choose to generate a surface that exactly interpolates the polygons, or a surface that approximates the input by smoothing away features smaller than some user-specified size. The implicit functions are represented using a moving least-squares formulation with constraints integrated over the polygons. The paper also presents an improved method for enforcing normal constraints and an iterative procedure for ensuring that the implicit surface tightly encloses the input vertices.