Research Seminar

OCTOBER 17-21, 2011


Location: Auditório 3, IMPA


Schedule


MONDAY
13h30 - 14h30 :: Cindy Grimm
14h30 - 15h30 :: Denis Zorin
15h30 - 16h00 :: Break
16h00 - 17h00 :: Hong Qin

TUESDAY
13h30 - 14h30 :: Jos Stam
14h30 - 15h30 :: Michael Kazhdan
15h30 - 16h00 :: Break
16h00 - 17h00 :: Mathieu Desbrun

WEDNESDAY
13h30 - 14h30 :: Charles Loop
14h30 - 15h30 :: Jorg Peters
15h30 - 16h00 :: Break
16h00 - 17h00 :: Panel 1

THURSDAY
13h30 - 14h30 :: Pierre Alliez
14h30 - 15h30 :: Christoph von Tycowicz
15h30 - 16h00 :: Break
16h00 - 17h00 :: Gabriel Taubin

FRIDAY
13h30 - 14h30 :: Peter Schröder
14h30 - 15h30 :: Konrad Polthier
15h30 - 16h00 :: Break
16h00 - 17h00 :: Panel 2



Talks


Cindy Grimm (WUSTL)
Title: Analytic surface approximation and parameterization using manifolds
Abstract: We describe how to build a parameterization of a mesh with arbitrary topology mesh using the corresponding manifold of the same topology.
This parameterization can then be used to build an analytic surface approximation of the mesh of any desired continuity by building basis and embedding functions on that parameterization. We discuss issues with parameterization (what is the right manifold to use? How to optimize the parameterization?) and issues with surface fitting (how do you minimize both average and maximum error?)

Denis Zorin (NYU)
Title: Global parametrization and projection manifold structure
Abstract: Projections to a collection of planes can be used to define a manifold structure on a surface. This structure naturally appears in range image data, and can be easily computed for a variety of surface discretizations, including different types of implicit surfaces and point clouds. Rather than reconstructing a manifold mesh from the original data, one can perform various types of processing operations on the charts of this structure directly.I will discuss how equations on the surface can be solved using the projection manifold structure, with variables represented on a collection of regularly sampled charts. In particular, I will describe a method for global parametrization based on a formulation of a Poisson equation on the projection structure. (joint work with Nico Pietroni, Marco Tarini and Olga Sorkine).

Hong Qin (Stonybrook)
Title: Manifold Splines: Theory and Applications for Visual Computing
Abstract: Despite many technical advances in geometry, solid, and physics-based modeling during the last two decades, one key, fundamental challenge is how to effectively represent real-world objects of complicated topology in a compact manner in order to facilitate rapid and accurate computation of their CAD-based digital models in graphics and virtual environments. In this talk, I will present Manifold Splines as a powerful modeling and computational framework for Computer Graphics and various Visual Computing applications. At the theoretical level, it has been an open problem on how to rigorously define spline surfaces on manifolds of arbitrary topology. I will present our theoretical results and demonstate that conventional spline surfaces defined over planar domains can be systematically extended to arbitrary manifold domains of complicated topology. In particular, I will concentrate on the aspects of simplex splines, tensor-product B-splines, T-splines, subdivision surfaces, and extra-ordinary point handling to highlight our theoretical results. At the application level, I will demonstrate various experimental examples in 3D shape modeling, computer graphics, reverse engineering, interactive editing, physics-based animation, medical imaging, and scientific visualization. Time permitting, I also plan to briefly present several of our on-going research projects with video clips.

Mathieu Desbrun (Caltech)
Title: Differential Computations on Discrete Manifolds
Abstract: In this talk, we give an overview of a discrete exterior calculus and its multiple applications to computational modeling, ranging from geometry processing to physical simulation. We will focus on differential forms, the building blocks of this calculus, and show how they provide differential, yet readily discretizable computational foundations. The resulting discrete forms are shown to form the Lie algebra of a discrete diffeomorphism group. The importance of preserving differential geometric notions in the discrete, computational setting will be a recurring theme throughout the talk. If time allows, a discussion about the current limitations of this setup will be mentioned, along with possible remedies.

Pierre Alliez (INRIA)
Title: An Optimal Transport Approach to Robust Shape Reconstruction
Abstract: We propose a robust shape reconstruction and simplification algorithm which takes as input a defect-laden point set with noise and outliers. We introduce an optimal-transport driven approach where the input point set, considered as
a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on simplices. A fine-to-coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples, with or without noise, features, and boundaries.

Peter Schröder (Caltech)
Title: Spin Transformations of Discrete Surfaces
Abstract: We introduce a new method for computing conformal transformations of triangle meshes in R3. Conformal maps are desirable in digital geometry processing because they do not exhibit shear, and therefore preserve texture fidelity as well as the quality of the mesh itself. Traditional discretizations consider maps into the complex plane, which are useful only for problems such as surface parameterization and planar shape deformation where the target surface is flat. We instead consider maps into the quaternions H, which allows us to work directly with surfaces sitting in R3. In particular, we introduce a quaternionic Dirac operator and use it to develop a novel integrability condition on conformal deformations. Our discretization of this condition results in a sparse linear system that is simple to build and can be used to efficiently edit surfaces by manipulating curvature and boundary data, as demonstrated via several mesh processing applications.

Konrad Polthier (Freie Universität-Berlin)
Title: CubeCover - Cubical grids for bounded volumes
Abstract: We discuss novel techniques to fill a bounded volumetric shape with a (preferably coarse) cubical voxel structure. Among the optimization goals are alignment of the voxels with the bounding surface as well as simplicity of the voxel grid. Mathematical analysis of the possible singularities is given. The algorithm is uses a tetrahedral volume mesh plus a user given guiding frame field as input. Then it constructs an atlas of chart functions, i.e. the parameterization function of the volume, such that the images of the coordinate lines align with the given frame field. Formally the function is given by a first-order PDE, namely the gradients of the coordinate functions are the vectors of the frame. In a first step, the algorithm uses a discrete Hodge decomposition to assure local integrability of the frame field. A subsequent step assures global integrability along generators of the first homology group and alignment a face of the boundary cube with the original surface boundary. All steps can be merged into solving linear equations. Conceptually the presented CubeCover-algorithm extends the known QuadCover-algorithm from surface meshes to volumes meshes.

Charles Loop (Microsoft)
Title: $G^2$ Tensor Product Splines over Extraordinary Vertices
Abstract: We present a second order smooth filling of an $n$-valent Catmull-Clark spline ring with $n$ biseptic patches. While an underdetermined biseptic solution to this problem has appeared previously, we make several advances in this paper. Most notably, we cast the problem as a constrained minimization and introduce a novel quadratic energy functional whose absolute minimum of zero is achieved for bicubic polynomials. This means that for the regular 4-valent case, we reproduce the bicubic B-splines. In other cases, the resulting surfaces are aesthetically well behaved. We extend our constrained minimization framework to handle the case of input mesh with boundary.

Gabriel Taubin (Brown)
Title:Smooth Signed Distance Surface Reconstruction
Abstract: We introduce a new variational formulation for the problem of reconstructing a watertight surface defined by an implicit equation from a finite set of oriented points; a problem which has attracted a lot of attention for more than two decades. As in the Poisson Surface Reconstruction approach, discretizations of the continuous formulation reduce to the solution of sparse linear systems of equations. But rather than forcing the implicit function to approximate the indicator function of the volume bounded by the implicit surface, in our formulation the implicit function is forced to be a smooth approximation of the signed distance function to the surface. Since an indicator function is discontinuous, its gradient does not exist exactly where it needs to be compared with the normal vector data. The smooth signed distance has approximate unit slope in the neighborhood of the data points. As a result, the normal vector data can be incorporated directly into the energy function without implicit function smoothing. In addition, rather than first extending the oriented points to a vector field within the bounding volume, and then approximating the vector field by a gradient field in the least squares sense, here the vector field is constrained to be the gradient of the implicit function, and a single variational problem is solved directly in one step. The formulation allows for a number of different efficient discretizations, reduces to a finite least squares problem for all linearly parameterized families of functions, and does not require boundary conditions. The resulting algorithms are significantly simpler and easier to implement, and produce results of quality comparable with state-of-the-art algorithms. An efficient implementation based on a primal-graph octree-based hybrid finite element-finite difference discretization, and the Dual Marching Cubes isosurface extraction algorithm, is shown to produce high quality crack-free adaptive manifold polygon meshes.

Jos Stam (Autodesk)
Title: Flows on surfaces of arbitrary topology
Abstract: We introduce a method to simulate fluid flows on smooth surfaces of arbitrary topology: an effect never seen before. We achieve this by combining a two-dimensional stable fluid solver with an atlas of parametrizations of a Catmull-Clark surface. The contributions of this paper are: (i) an extension of the Stable Fluids solver to arbitrary curvilinear coordinates, (ii) an elegant method to handle cross-patch boundary conditions and (iii) a set of new external forces custom tailored for surface flows. Our techniques can also be generalized to handle other types of processes on surfaces modeled by partial differential equations, such as reaction-diffusion. Some of our simulations allow a user to interactively place densities and apply forces to the surface, then watch their effects in real-time. We have also computed higher resolution animations of surface flows off-line.

Michael Kazhdan (JHU)
Title: Fast Poisson Solvers for Signal Processing on Meshes
Abstract: In this talk, we will describe a new, octree-based, FEM solver for performing geometry-aware signal processing on meshes. We show that by considering the restriction of functions defined in 3D to the surface, we can define a regular function space on the mesh that supports both multigrid solvers, and parallel and streaming computation. We will discuss applications of the solver to a number of traditional challenges, including texture stitching, parameterization, interactive geometry processing, and surface flow.

Jorg Peters (UFL)
Title: Rational Splines Revisited
Abstract: Rational spline pieces, typically in Bezier form, can exactly reproduce elementary geometric shapes such as quadrics or cyclides. But this piecemeal approach lacks the elegance of the B-spline approach that yields one smoothly-connected structure. The talk will re-examine rational splines within a design framework that starts with elementary shapes, re-represents them in spline form and then uses the spline shape handles for localized free-form modification.

Christoph von Tycowicz (FU-Berlin)
Title: Interactive Surface Modeling using Modal Analysis
Abstract: We propose a framework for deformation-based surface modeling that is interactive, robust and intuitive to use. The deformations are described by a non-linear optimization problem that models static states of elastic shapes under external forces which implement the user input. Interactive response is achieved by a combination of model reduction, a robust energy approximation, and an efficient quasi-Newton solver. Motivated by the observation that a typical modeling session requires only a fraction of the full shape space of the underlying model, we use second and third derivatives of a deformation energy to construct a low-dimensional shape space that forms the feasible set for the optimization. Based on mesh coarsening, we propose an energy approximation scheme with adjustable approximation quality. The quasi-Newton solver guarantees superlinear convergence without the need of costly Hessian evaluations during modeling. We demonstrate the effectiveness of the approach on different examples including the test suite introduced in [Botsch and Sorkine 2008].



Panels


Topic: Robustness Issues in Geometry Processing
Pierre Alliez (INRIA)


Topic: Open Problems in Computational Manifolds
Peter Schröder (Caltech)