# 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)