MaxPlanckInstitut für Informatik
Department 4: Computer Graphics
Saarland Informatics Campus
Building E1.4, Room 206
66123 Saarbrücken
Germany
Email: renjie.chen[at]mpiinf.mpg.de
Phone: +49 681 9325 4006
Fax: +49 681 9325 4099
I am heading the Images and Geometry group within the Max Planck Center for Visual Computing and Communication at MaxPlanckInstitut Informatik in Saarbrücken.
Our research topics includes
Open positions: We are currently looking for PhD students and Postdocs. Outstanding students with various backgrounds (Computer Science, Electrical Engineering, Applied Mathematics and Computer Engineering), who are interested in performing cutting edge research in computer graphics are welcome to contact me.
Abstract: Path generation is an important problem in many fields, especially robotics. One way to create a path between a source point z and a target point y inside a complex planar domain Ω is to define a nonnegative distance function d(y,z), such that following the negative gradient of d (by z) traces out such a path. This presents two challenges: (1) The mathematical challenge of defining d, such that d(y,z) has a single minimum at z=y for any fixed y, because the gradientdescent path may otherwise terminate at a local minimum before reaching y; (2) The computational challenge of defining d, such that it can be computed efficiently. Using the concepts of harmonic measure and fdivergence, we show how to assign a set of reduced coordinates to each point in Ω and to define a family of distance functions based on these coordinates, such that both the mathematical and the computational challenge are met. Since in practice, especially in robotics applications, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites sampled from Ω, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm, which is the discrete equivalent of continuous gradient descent, based on our reduced coordinates is guaranteed to generate a path in the network between any two sites. In many cases, this network is close to a planar graph, especially if the set of sites is dense. Guaranteeing the existence of a greedy route between any two points in the graph is a significant advantage in practical applications, avoiding the complexity of other pathplanning methods, such as the shortestpath and A* algorithms. While the paths generated by our algorithm are not the shortest possible, in practice we found that they are close to that.  
Abstract: We present a highly efficient planar meshless shape deformation algorithm. Our method is based on an unconstrained minimization of isometric energies, and is guaranteed to produce C ∞ locally injective maps by operating within a reduced dimensional subspace of harmonic maps. We extend the harmonic subspace of [Chen and Weber 2015] to support multiplyconnected domains, and further provide a generalization of the bounded distortion theorem that appeared in that paper. Our harmonic map, as well as the gradient and the Hessian of our isometric energies possess closedform expressions. A key result is a simpleandfast analytic modification of the Hessian of the energy such that it is positive definite, which is crucial for the successful operation of a Newton solver. The method is straightforward to implement and is specifically designed to harness the processing power of modern graphics hardware. Our modified Newton iterations are shown to be extremely effective, leading to fast convergence after a handful of iterations, while each iteration is fast due to a combination of a number of factors, such as the smoothness and the low dimensionality of the subspace, the closedform expressions for the differentials, and the avoidance of expensive strategies to ensure positive definiteness. The entire pipeline is carried out on the GPU, leading to deformations that are significantly faster to compute than the stateoftheart.  
Abstract: Distance functions between points in a domain can be used to automatically plan a gradientdescent path towards a given target point in the domain, avoiding obstacles that may be present. A key requirement from such distance functions is the absence of spurious local minima, and this has led to the common use of harmonic potential functions. This choice guarantees the absence of spurious minima, but is well known to be slow to numerically compute and prone to numerical precision issues. To alleviate the first of these problems, we propose a family of novel divergence distances. These are based on fdivergence of the Poisson kernel of the domain. Using the concept of conformal invariance, we show that divergence distances are equivalent to the harmonic potential function on simplyconnected domains, namely generate paths which are identical to those generated by the potential function. We then discuss how to compute two special cases of divergence distances, one based on the KullbackLeibler, the other on the total variation divergence, in practice by discretizing the domain with a triangle mesh and using Finite Elements (FEM) computation. We show that using divergence distances instead of the potential function and other distances has a significant computational advantage, as, following a preprocessing stage, they may be computed online in a multiquery scenario up to an order of magnitude faster than the others when taking advantage of certain sparsity properties of the Poisson kernel. Furthermore, the computation is “embarrassingly parallel”, so may be implemented on a GPU with up to three orders of magnitude speedup.  
Abstract: Continuous conformal maps are typically approximated numerically using a triangle mesh which discretizes the plane. Computing a conformal map subject to userprovided constraints then reduces to a sparse linear system, minimizing a quadratic “conformal energy”. We address the more general case of nontriangular elements, and provide a complete analysis of the case where the plane is discretized using a mesh of regular polygons, e.g. equilateral triangles, squares and hexagons, whose interiors are mapped using barycentric coordinate functions. We demonstrate experimentally that faster convergence to continuous conformal maps may be obtained this way. We provide a formulation of the problem and its solution using complex number algebra, significantly simplifying the notation. We examine a number of common barycentric coordinate functions and demonstrate that superior approximation to harmonic coordinates of a polygon are achieved by the Moving Least Squares coordinates. We also provide a simple iterative algorithm to invert barycentric maps of regular polygon meshes, allowing to apply them in practical applications, e.g. for texture mapping. 

Abstract:
Transfinite barycentric kernels are the continuous version of traditional barycentric coordinates used to define interpolants of
values given on a smooth planar contour. When the data is twodimensional, i.e. the boundary of a planar map, these kernels
may be conveniently expressed using complex number algebra. In this paper we develop some of the basic complexvalued
algebra needed to describe these planar maps, and use it to define similarity kernels, a natural alternative to the usual barycentric kernels.


Abstract:
Harmonic coordinates are widely considered to be perfect barycentric coordinates of a
polygonal domain due to their attractive mathematical properties. Alas, they have no closed
form in general, so must be numerically approximated by solving a large linear equation
on a discretization of the domain. The alternatives are a number of other simpler schemes
which have closed forms, many designed as a (computationally) cheap approximation
to harmonic coordinates. One test of the quality of the approximation is whether the
coordinates coincide with the harmonic coordinates for the special case where the polygon
is close to a circle (where the harmonic coordinates have a closed form – the celebrated
Poisson kernel). Coordinates which pass this test are called “pseudoharmonic”. Another
test is how small the differences between the coordinates and the harmonic coordinates
are for “realworld” polygons using some natural distance measures.


Abstract: Planar shape interpolation is a classic problem in computer graphics. We present a novel shape interpolation method that blends a set of C∞ planar harmonic mappings represented in closedform. The intermediate mappings in the blending are guaranteed to be locally injective C∞ harmonic mappings, with conformal and isometric distortion bounded by that of the input mappings. The key to the success of our method is the fact that the blended differentials of our interpolated mapping have a simple closedform expression, so they can be evaluated with unprecedented efficiency and accuracy. Moreover, in contrast to previous approaches, these differentials are integrable, and result in an actual mapping without further modification. Our algorithm is embarrassingly parallel and is orders of magnitude faster than stateoftheart methods due to its simplicity, yet it still produce mappings that are superior to those of existing techniques due to its guaranteed bounds on geometric distortion. 

Abstract:
Discrete conformal mappings of planar triangle meshes, also known as the AsSimilarAsPossible (ASAP) mapping, involve the minimization of a quadratic energy function, thus are very easy to generate and are popular in image warping scenarios. We generalize this classical mapping to the case of quad meshes, taking into account the mapping of the interior of the quad, and analyze in detail the most common case  the unit grid mesh. We show that the generalization, when combined with barycentric coordinate mappings between the source and target polygons, spawns an entire family of new mappings governed by quadratic energy functions, which allow to control quite precisely various effects of the mapping. This approach is quite general and applies also to arbitrary planar polygon meshes.


Abstract:
We present a framework for the computation of harmonic and conformal mappings in the plane with mathematical guarantees that the computed mappings are C∞, locally injective and satisfy strict bounds on the conformal and isometric distortion. Such mappings are very desirable in many computer graphics and geometry processing applications.


Abstract:
Polyhedral meshes (PM)  meshes having planar faces  have enjoyed a rise in popularity in recent years due to their
importance in architectural and industrial design. However, they are also notoriously difficult to generate and manipulate. Previous
methods start with a smooth surface and then apply elaborate meshing schemes to create polyhedral meshes approximating the
surface. In this paper, we describe a reverse approach: given the topology of a mesh, we explore the space of possible planar
meshes having that topology.


Abstract: We discuss an intuitive extension to compressive multilayer light field displays that greatly extends their field of view and depth of field. Rather than optimizing these displays to create a moderately narrow field of view at the center of the display, we constrain optimization to create narrow view cones that are directed to a few viewers’ eyes, allowing the available display bandwidth to be utilized more efficiently. These narrow view cones follow the viewers, creating a wide apparent field of view. Imagery is also recalculated for the viewers’ exact eye positions, creating a greater depth of field. The view cones can be scaled to match the positional error and latency of the tracking system. Using more efficient optimization and commodity tracking hardware and software, we demonstrate a realtime, glassesfree 3D display that offers a 100° × 40° field of view. 

Abstract: Planar shape interpolation is widely used in computer graphics applications. Despite a wealth of interpolation methods, there is currently no approach that
produces shapes with a bounded amount of distortion with respect to the input. As a result, existing
interpolation methods may produce shapes that are significantly different than
the input and can suffer from foldovers and other visual artifacts,
making them less useful in many practical scenarios. We introduce a novel shape
interpolation scheme designed specifically to produce results with a bounded amount of conformal (angular) distortion. Our method is based on an elegant continuous mathematical formulation and provides several appealing properties such as existence and uniqueness of the solution as well as smoothness in space and time domains. 

Abstract: We describe a fast sampling algorithm for generating uniformlydistributed point patterns with good blue noise characteristics. The method, based on constrained farthest point optimization, is provably optimal and may be easily parallelized, resulting in an algorithm whose performance/quality tradeoff is superior to other stateoftheart approaches. 

Abstract: We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines. 

Abstract: Given a 3vertexconnected triangular planar graph and an embedding of its boundary vertices, can the interior vertices be embedded to form a valid triangulation? We describe an algorithm which decides this problem and produces such an embedding if it exists. 

Abstract: We present a new method for contentaware image resizing based on a framework of global optimization. We show that the basic resizing problem can be formulated as a convex quadratic program. Furthermore, we demonstrate how the basic framework may be extended to prevent foldovers of the underlying mesh; encourage the magniﬁcation of salient regions; and preserve straight line structures. We show results demonstrating the effectiveness of the proposed method by comparing with four leading competitor methods.


Abstract: We describe a fast sampling algorithm for generating uniformlydistributed point patterns with good blue noise characteristics. The method, based on constrained farthest point optimization, is provably optimal and may be easily parallelized, resulting in an algorithm whose performance/quality tradeoff is superior to other stateoftheart approaches.


Abstract: The Delaunay triangulation of a planar point set is a fundamental construct in computational geometry. A simple algorithm to generate it is based on flips of diagonal edges in convex quads. We characterize the effect of a single edge flip in a triangulation on the geometric Laplacian of the triangulation, which leads to a simpler and shorter proof of a theorem of Rippa that the Dirichlet energy of any piecewiselinear scalar function on a triangulation obtains its minimum on the Delaunay triangulation. Using Rippa’s theorem, we provide a spectral characterization of the Delaunay triangulation, namely that the spectrum of the geometric Laplacian is minimized on this triangulation. This spectral theorem then leads to a simpler proof of a theorem of Musin that the harmonic index also obtains its minimum on the Delaunay triangulation.


Abstract: We develop a direct and accurate approach for local resampling in vector fields, and then use the approach to synthesize textures on 2D manifold surfaces directly from a texture exemplar. Regulargrid patches produced by the local resampling are used as building blocks for texture synthesis. Then, texture optimization and patchbased sampling are generalized to synthesize texture directly in vector fields. Users can control the vector field on the mesh to generate textures with local variations including the orientation and scale. Many experimental results are presented to demonstrate the ease of use and reliable results provided by our system.


Abstract: Mesh smoothing aims to relocate the positions of the vertices to remove the noise. A good smooth algorithm should preserve the data precision and avoid dealing with the details of the model as noises and removing them. To meet these need, we present a novel approach for smoothing triangular meshes which guarantees that each vertex in the result does not exceed a given distance tolerance from its original position. We formulize the problem as a quadratic optimization with a set of nonlinear constraints and propose a reliable iterative linear solution to solve the optimization. Our algorithm can also preserve the sharp features in the result by integrating feature constraints in the optimization. Many experimental results on both scanned models and synthetic models have shown that our algorithm can remove all the noise while preserving the features of the original model. 

Abstract: This paper presents a novel algorithm for detecting the principal lines in digital images. The feature edge pixels are first detected in the image by the segmentation technique. The short line segments are used for approximating the feature pixels and then are clustered using some similarity metric. We use a line to fit each cluster of segments in an iterative manner. Finally the principal lines are determined according to the validity measurement. We demonstrate two practical applications including automatic image inpainting and automatic photo composition to show the applicability of the principal lines in image processing. 
R. Chen, ContentAware Image Retargeting(in Chinese), PhD Thesis, Zhejiang University, June, 2010