About
I am a researcher within the Titane team at INRIA Sophia Antipolis.
In particular I am working with Pierre Alliez on the ERC IRON (Robust Geometry Processing) project.
Before my time at Inria I received my Diplom (2006) and PhD (2012) in Computer Science at the
Computer Graphics Group of Prof. Leif Kobbelt at RWTH Aachen.
My research interests include:
 Geometry processing
 Differential geometry
 Mesh generation
 Numerical optimization
News
 September 2013: Starting Research Position at Inria
I'm happy to anounce that from October 2013 on I will be a researcher in the Titane team.
 August 2013: Paper at SIGGRAPH Asia 2013
Our paper "QEx: Robust Quad Mesh Extraction" (see below) got accepted for presentation at
ACM SIGGRAPH Asia 2013.
 May 2013: Best PhD Thesis Award at EUROGRAPHICS 2013
My PhD thesis was recognized as a strong technical contribution and selected for one of the four
EUROGRAPHICS 2013 Best PhD Thesis Awards.
 April 2013: Paper at SIGGRAPH 2013
Our paper "IntegerGrid Maps for Reliable Quad Meshing" (see below) got accepted for presentation at
ACM SIGGRAPH 2013.
Publications

IntegerGrid Maps for Reliable Quad Meshing
David Bommes, Marcel Campen, HansChristian Ebke, Pierre Alliez, Leif Kobbelt
SIGGRAPH 2013
Abstract:
Quadrilateral remeshing approaches based on global parametrization enable many desirable mesh properties.
Two of the most important ones are (1) high regularity due to explicit control over irregular vertices and
(2) smooth distribution of distortion achieved by convex variational formulations. Apart from these strengths,
stateoftheart techniques suffer from limited reliability on realworld input data, i.e. the determined map
might have degeneracies like (local) noninjectivities and consequently often cannot be used directly to generate
a quadrilateral mesh. In this paper we propose a novel convex MixedInteger Quadratic Programming (MIQP) formulation
which ensures by construction that the resulting map is within the class of so called IntegerGrid Maps that are
guaranteed to imply a quad mesh. In order to overcome the NPhardness of MIQP and to be able to remesh typical
input geometries in acceptable time we propose two additional problem specific optimizations: a complexity reduction
algorithm and singularity separating conditions. While the former decouples the dimension of the MIQP search space
from the input complexity of the triangle mesh and thus is able to dramatically speed up the computation without inducing
inaccuracies, the latter improves the continuous relaxation, which is crucial for the success of modern MIQP optimizers.
Our experiments show that the reliability of the resulting algorithm does not only annihilate the main drawback of
parametrization based quadremeshing but moreover enables the global search for highquality coarse quad layouts  a
difficult task solely tackled by greedy methodologies before.
[pdf]
[bibtex]
[zip  additional material]


QEx: Robust Quad Mesh Extraction
HansChristian Ebke, David Bommes, Marcel Campen, Leif Kobbelt
SIGGRAPH Asia 2013
Abstract:
The most popular and actively researched class of quad remeshing techniques is
the family of parametrization based quad meshing methods. They all strive
to generate an integergrid map, i.e. a parametrization of the input surface
into R^{2} such that the canonical grid of integer isolines forms a
quad mesh when mapped back onto the surface in R^{3}. An essential,
albeit broadly neglected aspect of these methods is the quad extraction
step, i.e. the materialization of an actual quad mesh from the mere “quad
texture”. Quad (mesh) extraction is often believed to be a trivial matter but
quite the opposite is true: Numerous special cases, ambiguities induced by
numerical inaccuracies and limited solver precision, as well as imperfections
in the maps produced by most methods (unless costly countermeasures are taken)
pose significant challenges to the quad extractor. We present a method to
sanitize a provided parametrization such that it becomes numerically
consistent even in a limited precision floating point representation. Based
on this we are able to provide a comprehensive and sound description of how to
perform quad extraction robustly and without the need for any complex
tolerance thresholds or disambiguation rules. On top of that we develop a
novel strategy to cope with common local foldovers in the parametrization.
This allows our method, dubbed QEx, to generate allquadrilateral meshes
where otherwise holes, nonquad polygons or no output at all would have been
produced. We thus enable the practical use of an entire class of maps that was
previously considered defective. Since state of the art quad meshing methods
spend a significant share of their run time solely to prevent local
foldovers, using our method it is now possible to obtain quad meshes
significantly quicker than before. We also provide libQEx , an open source
C++ reference implementation of our method and thus significantly lower the
bar to enter the field of quad meshing.
[pdf]
[bibtex]
[zip  additional material]
[source code]


Advanced Automatic Hexahedral Mesh Generation from Surface Quad Meshes
Michael Kremer, David Bommes, Isaak Lim, Leif Kobbelt
22nd International Meshing Roundtable
Abstract:
A purely topological approach for the generation of hexahedral meshes from quadrilateral
surface meshes of genus zero has been proposed by M. MüllerHannemann: in a first stage,
the input surface mesh is reduced to a single hexahedron by successively eliminating loops
from the dual graph of the quad mesh; in the second stage, the hexahedral mesh is constructed
by extruding a layer of hexahedra for each dual loop from the first stage in reverse elimination
order. In this paper, we introduce several techniques to extend the scope of target shapes of the
approach and significantly improve the quality of the generated hexahedral meshes. While the
original method can only handle "almost convex" objects and requires mesh surgery and remeshing
in case of concave geometry, we propose a method to overcome this issue by introducing the notion
of concave dual loops. Furthermore, we analyze and improve the heuristic to determine the
elimination order for the dual loops such that the inordinate introduction of interior singular
edges, i.e. edges of degree other than four in the hexahedral mesh, can be avoided in many cases.
[pdf]
[bibtex]


Dual Loops Meshing: Quality Quad Layouts on Manifolds
Marcel Campen, David Bommes, Leif Kobbelt
SIGGRAPH 2012
Abstract:
We present a theoretical framework and practical method for the automatic construction of simple,
allquadrilateral patch layouts on manifold surfaces. The resulting layouts are coarse, surfaceembedded
cell complexes well adapted to the geometric structure, hence they are ideally suited as domains
and base complexes for surface parameterization, spline fitting, or subdivision surfaces and can be
used to generate quad meshes with a highlevel patch structure that are advantageous in many application
scenarios. Our approach is based on the careful construction of the layout graph's combinatorial dual.
In contrast to the primal this dual perspective provides direct control over the globally interdependent
structural constraints inherent to quad layouts. The dual layout is built from curvatureguided, crossing
loops on the surface. A novel method to construct these efficiently in a geometry and structureaware
manner constitutes the core of our approach.
[pdf]
[bibtex]


Rationalization of TriangleBased PointFolding Structures
Henrik Zimmer, Marcel Campen, David Bommes, Leif Kobbelt
Eurographics 2012
Abstract:
In mechanical engineering and architecture, structural elements with low material consumption and
high loadbearing capabilities are essential for lightweight and even selfsupporting constructions.
This paper deals with so called pointfolding elements  nonplanar, pyramidal panels, usually formed
from thin metal sheets, which exploit the increased structural capabilities emerging from folds or
creases. Given a triangulated freeform surface, a corresponding pointfolding structure is a
collection of pyramidal elements basing on the triangles. Userspecified or materialinduced geometric
constraints often imply that each individual folding element has a different shape, leading to immense
fabrication costs. We present a rationalization method for such structures which respects the prescribed
aesthetic and production constraints and finds a minimal set of molds for the production process, leading
to drastically reduced costs. For each base triangle we compute and parametrize the range of feasible
folding elements that satisfy the given constraints within the allowed tolerances. Then we pose the
rationalization task as a geometric intersection problem, which we solve so as to maximize the reuse
of mold dies. Major challenges arise from the high precision requirements and the nontrivial parametrization
of the search space. We evaluate our method on a number of practical examples where we achieve rationalization
gains of more than 90%.
[pdf]
[bibtex]


State of the Art in Quad Meshing
David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio T. Silva, Marco Tarini, Denis Zorin
Eurographics STARS 2012
Abstract:
Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and
geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral
meshes, especially semiregular ones, have advantages for many applications, and significant progress was made in
quadrilateral mesh generation and processing during the last several years. In this State of the Art Report, we
discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis
and mesh quality, simplification, adaptive refinement, alignment with features, parametrization, and remeshing.
[pdf]
[bibtex]


OpenVolumeMesh  A Versatile IndexBased Data Structure for 3D Polytopal Complexes
Michael Kremer, David Bommes, Leif Kobbelt
International Meshing Roundtable 2012, San Jose, California, USA.
Abstract:
OpenVolumeMesh is a data structure which is able to represent heterogeneous 3dimensional polytopal
cell complexes and is general enough to also represent non manifolds without incurring undue overhead.
Extending the idea of halfedge based data structures for twomanifold surface meshes, all faces, i.e.
the twodimensional entities of a mesh, are represented by a pair of oriented halffaces. The concept
of using directed halfentities enables inducing an orientation to the meshes in an intuitive and
easy to use manner. We pursue the idea of encoding connectivity by storing firstorder topdown
incidence relations per entity, i.e. for each entity of dimension d, a list of links to the
respective incident entities of dimension d<1 is stored. For instance, each halfface as well
as its orientation is uniquely determined by a tuple of links to its incident halfedges or
each 3D cell by the set of incident halffaces. This representation allows for handling nonmanifolds
as well as mixeddimensional mesh configurations. No entity is duplicated according to its valence, instead,
it is shared by all incident entities in order to reduce memory consumption. Furthermore, an
arraybased storage layout is used in combination with direct indexbased access. This guarantees
constant access time to the entities of a mesh. Although bottomup incidence relations are implied
by the topdown incidences, our data structure provides the option to explicitly generate and cache
them in a transparent manner. This allows for accelerated navigation in the local neighbor hood of
an entity. We provide an opensource and platformindependent implementation of the proposed data structure
written in C++ using dynamic typing paradigms. The li brary is equipped with a set of STL compliant iterators,
a generic property system to dynamically attach properties to all entities at runtime, and a
serializer/deserializer supporting a simple file format. Due to its similarity to the OpenMesh data structure,
it is easy to use, in particular for those familiar with OpenMesh. Since the presented data structure is compact,
intuitive, and efficient, it is suitable for a variety of applications, such as meshing, visualization, and
numerical analysis. OpenVolumeMesh is opensource software licensed under the terms of the LGPL.
[pdf]
[bibtex]
[project]


Practical MixedInteger Optimization for Geometry Processing
David Bommes, Henrik Zimmer, Leif Kobbelt
Special Issue of Lecture Notes in Computer Science 2012, Proceedings of Curves and Surfaces 2010
Abstract:
Solving mixedinteger problems, i.e., optimization problems where some of the unknowns are continuous while
others are discrete, is NPhard. Unfortunately, realworld problems like e.g., quadrangular remeshing usually
have a large number of unknowns such that exact methods become unfeasible. In this article we present a greedy
strategy to rapidly approximate the solution of large quadratic mixedinteger problems within a practically
sufficient accuracy. The algorithm, which is freely available as an open source library implemented in C++,
determines the values of the discrete variables by successively solving relaxed problems. Additionally the
specification of arbitrary linear equality constraints which typically arise as side conditions of the optimization
problem is possible. The performance of the base algorithm is strongly improved by two novel extensions which are (1)
simultaneously estimating sets of discrete variables which do not interfere and (2) a fillin reducing reordering of
the constraints. Exemplarily the solver is applied to the problem of quadrilateral surface remeshing, enabling a great
flexibility by supporting different types of user guidance within a realtime modeling framework for input surfaces
of moderate complexity.
[pdf]
[bibtex]
[project]


Global Structure Optimization of Quadrilateral Meshes
David Bommes, Timm Lempfer, Leif Kobbelt
Eurographics 2011 (best paper award)
Abstract:
We introduce a fully automatic algorithm which optimizes the highlevel structure of a given quadrilateral
mesh to achieve a coarser quadrangular base complex. Such a topological optimization is highly desirable,
since stateoftheart quadrangulation techniques lead to meshes which have an appropriate singularity
distribution and an anisotropic element alignment, but usually they are still far away from the highlevel
structure which is typical for carefully designed meshes manually created by specialists and used e.g. in
animation or simulation. In this paper we show that the quality of the highlevel structure is negatively
affected by helical configurations within the quadrilateral mesh. Consequently we present an algorithm which
detects helices and is able to remove most of them by applying a novel grid preserving simplification operator
(GPoperator) which is guaranteed to maintain an allquadrilateral mesh. Additionally it preserves the given
singularity distribution and in particular does not introduce new singularities. For each helix we construct
a directed graph in which cycles through the start vertex encode operations to remove the corresponding helix.
Therefore a simple graph search algorithm can be performed iteratively to remove as many helices as possible
and thus improve the highlevel structure in a greedy fashion. We demonstrate the usefulness of our automatic
structure optimization technique by showing several examples with varying complexity.
[pdf]
[bibtex]
[zip  additional material]


MixedInteger Quadrangulation
David Bommes, Henrik Zimmer, Leif Kobbelt
SIGGRAPH 2009
Abstract:
We present a novel method for quadrangulating a given triangle mesh. After constructing an as smooth as
possible symmetric cross field satisfying a sparse set of directional constraints (to capture the geometric
structure of the surface), the mesh is cut open in order to enable a low distortion unfolding. Then a seamless
globally smooth parametrization is computed whose isoparameter lines follow the cross field directions.
In contrast to previous methods, sparsely distributed directional constraints are sufficient to automatically
determine the appropriate number, type and position of singularities in the quadrangulation. Both steps of
the algorithm (cross field and parametrization) can be formulated as a mixedinteger problem which we solve
very efficiently by an adaptive greedy solver. We show several complex examples where high quality quad meshes
are generated in a fully automatic manner.
The Constrained MixedInteger Solver used in this project has been released under GPL and can be found on its
projects page.
[pdf]
[bibtex]
[zip  additional material]


Quadrangular Parameterization for Reverse Engineering
David Bommes, Tobias Vossemer, Leif Kobbelt
Special Issue of Lecture Notes in Computer Science 2009 Proceedings of Curves and Surfaces 2008
Abstract:
The aim of Reverse Engineering is to convert an unstructured representation of a geometric object, emerging e.g.
from laser scanners, into a natural, structured representation in the spirit of CAD models, which is suitable
for numerical computations. Therefore we present a usercontrolled, as isometric as possible parameterization
technique which is able to prescribe geometric features of the input and produces highquality quadmeshes with
low distortion. Starting with a coarse, userprescribed layout this is achieved by using affine functions for
the transition between nonorthogonal quadrangular charts of a global parameterization. The shape of each chart
is optimized nonlinearly for isometry of the underlying parameterization to produce meshes with low edgelength
distortion. To provide full control over the meshing alignment the user can additionally tag an arbitrary subset
of the layout edges which are guaranteed to be represented by enforcing them to lie on isolines of the
parameterization but still allowing the global parameterization to relax in the direction of the isolines.
[pdf]
[bibtex]


Accurate Computation of Geodesic Distance Fields for Polygonal Curves on Triangle Meshes
David Bommes, Leif Kobbelt
VMV 2007
Abstract:
We present an algorithm for the efficient and accurate computation of geodesic distance fields on triangle meshes.
We generalize the algorithm originally proposed by Surazhsky et al. . While the original algorithm is able to compute
geodesic distances to isolated points on the mesh only, our generalization can handle arbitrary, possibly open,
polygons on the mesh to define the zero set of the distance field. Our extensions integrate naturally into the
base algorithm and consequently maintain all its nice properties. For most geometry processing algorithms, the
exact geodesic distance information is sampled at the mesh vertices and the resulting piecewise linear interpolant
is used as an approximation to the true distance field. The quality of this approximation strongly depends on the
structure of the mesh and the location of the medial axis of the distance fild. Hence our second contribution is
a simple adaptive refinement scheme, which inserts new vertices at critical locations on the mesh such that the
final piecewise linear interpolant is guaranteed to be a faithful approximation to the true geodesic distance field.
[pdf]
[bibtex]


Efficient Linear System Solvers for Mesh Processing
Mario Botsch, David Bommes, Leif Kobbelt
Invited paper at XIth IMA Conference on the Mathematics of Surfaces
Abstract:
The use of polygonal mesh representations for freeform geometry enables the formulation of many important
geometry processing tasks as the solution of one or several linear systems. As a consequence, the key
ingredient for efficient algorithms is a fast procedure to solve linear systems. A large class of
standard problems can further be shown to lead more specifically to sparse, symmetric, and positive
definite systems, that allow for a numerically robust and efficient solution. In this paper we discuss
and evaluate the use of \emph{sparse direct solvers} for such kind of systems in geometry processing
applications, since in our experiments they turned out to be superior even to highly optimized multigrid
methods, but at the same time were considerably easier to use and implement. Although the methods we
present are well known in the field of high performance computing, we observed that they are in practice
surprisingly rarely applied to geometry processing problems.
[pdf]
[bibtex]


GPUbased Tolerance Volumes for Mesh Processing
Mario Botsch, David Bommes, Christoph Vogel, Leif Kobbelt
Proc. Pacific Graphics, 237243, 2004
Abstract:
In an increasing number of applications triangle meshes represent a flexible and efficient alternative to
traditional NURBSbased surface representations. Especially in engineering applications it is crucial to
guarantee that a prescribed approximation tolerance to a given reference geometry is respected for any
combination of geometric algorithms that are applied when processing a triangle mesh. We propose a simple
and generic method for computing the distance of a given polygonal mesh to the reference surface, based
on a linear approximation of its signed distance field. Exploiting the hardware acceleration of modern
GPUs allows us to perform up to 3M triangle checks per second, enabling realtime distance evaluations
even for complex geometries. An additional feature of our approach is the accurate highquality distance
visualization of dynamically changing meshes at a rate of 15M triangles per second. Due to its generality,
the presented approach can be used to enhance any mesh processing method by global error control,
guaranteeing the resulting mesh to stay within a prescribed error tolerance. The application examples
that we present include mesh decimation, mesh smoothing and freeform mesh deformation.
[pdf]
[bibtex]
[slides]

