A | B | C | D | E | F 
 G | H | I | J | K | L | M 
 N | O | P | Q | R | S | T 
 U | V | W | X | Y | Z 
max planck institut
mpii logo Minerva of the Max Planck Society


Chen, Renjie

Renjie Chen

Max-Planck-Institut für Informatik
Department 4: Computer Graphics
Saarland Informatics Campus
Building E1.4, Room 206
66123 Saarbrücken

Email: renjie.chen[at]mpi-inf.mpg.de
Phone: +49 681 9325 4006
Fax: +49 681 9325 4099

Research Group

I am heading the Images and Geometry group within the Max Planck Center for Visual Computing and Communication at Max-Planck-Institut 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.


Björn Golla and Hans-Peter Seidel and Renjie Chen
Piecewise Linear Mapping Optimization Based on the Complex View
Comput. Graph. Forum. (Proc. Pacific Graphics), 37(7), 2018

Abstract: We present an efficient modified Newton iteration for the optimization of nonlinear energies on triangle meshes. Noting that the linear mapping between any pair of triangles is a special case of harmonic mapping, we build upon the results of Chen and Weber [CW17]. Based on the complex view of the linear mapping, we show that the Hessian of the isometric energies has a simple and compact analytic expression. This allows us to analytically project the per-element Hessians to positive semidefinite matrices for efficient Newton iteration. We show that our method outperforms state-of-the-art methods on 2D deformation and parameterization. Further, we inspect the spectra of the per triangle energy Hessians and show that given an initial mapping, simple global scaling can shift the energy towards a more convex state. This allows Newton iteration to converge faster than starting from the given initial state. Additionally, our formulations support adding an energy smoothness term to the optimization with little additional effort, which improves the mapping results such that concentrated distortions are reduced.

Renjie Chen and Craig Gotsman and Kai Hormann
Path Planning with Divergence-Based Distance Functions
Computer Aided Geometric Design, 66, 52-74, 2018

Abstract: Distance functions between points in a domain can be used to automatically plan a gradient-descent 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 f-divergence 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 simply-connected 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 Kullback-Leibler, 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 pre-processing stage, they may be computed online in a multi-query 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.

Renjie Chen and Craig Gotsman and Kai Hormann
Efficient Path Generation with Reduced Coordinates
Comput. Graph. Forum. (Proc. Sym. Geom. Proc.), 37(5), 2018

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 non-negative 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 gradient-descent 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 f-divergence, 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 path-planning methods, such as the shortest-path 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.

Renjie Chen and Ofir Weber
GPU-Accelerated Locally Injective Shape Deformation
ACM Transactions on Graphics, 36(6) (SIGGRAPH Asia 2017)

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 multiply-connected 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 closed-form expressions. A key result is a simple-and-fast 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 closed-form 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 state-of-the-art.


Renjie Chen and Craig Gotsman
Approximating Planar Conformal Maps Using Regular Polygonal Meshes
Comput. Graph. Forum., 36(8), 2017

Abstract: Continuous conformal maps are typically approximated numerically using a triangle mesh which discretizes the plane. Computing a conformal map subject to user-provided constraints then reduces to a sparse linear system, minimizing a quadratic “conformal energy”. We address the more general case of non-triangular 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.

Renjie Chen and Craig Gotsman
Complex Transfinite Barycentric Mappings with Similarity Kernels
Comput. Graph. Forum. (Proc. Sym. Geom. Proc.), 35(5), 2016

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 two-dimensional, 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 complex-valued algebra needed to describe these planar maps, and use it to define similarity kernels, a natural alternative to the usual barycentric kernels.

We develop the theory behind similarity kernels, explore their properties, and show that the transfinite versions of the popular three-point barycentric coordinates (Laplace, mean value and Wachspress) have surprisingly simple similarity kernels.

We furthermore show how similarity kernels may be used to invert injective transfinite barycentric mappings using an iterative algorithm which converges quite rapidly.

Renjie Chen and Craig Gotsman
On Pseudo-harmonic Barycentric Coordinates
Computer Aided Geometric Design, 44, 15-35, 2016

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 “pseudo-harmonic”. Another test is how small the differences between the coordinates and the harmonic coordinates are for “real-world” polygons using some natural distance measures.

We provide a qualitative and quantitative comparison of a number of popular barycentric coordinate methods. In particular, we study how good an approximation they are to harmonic coordinates. We pay special attention to the Moving-Least-Squares coordinates, provide a closed form for them and their transfinite counterpart (i.e. when the polygon converges to a smooth continuous curve), prove that they are pseudo-harmonic and demonstrate experimentally that they provide a superior approximation to harmonic coordinates.

Edward Chien and Renjie Chen* and Ofir Weber
Bounded Distortion Harmonic Shape Interpolation
ACM Transactions on Graphics, 35(4) (SIGGRAPH 2016)

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 closed-form. 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 closed-form 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 state-of-the-art 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.


Renjie Chen and Craig Gotsman
Generalized As-Similar-As-Possible Warping with Applications in Digital Photography
Comput. Graph. Forum. (Proc. Eurographics), 35(2), 2016

Abstract: Discrete conformal mappings of planar triangle meshes, also known as the As-Similar-As-Possible (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.

As an application of generalized ASAP mappings of the unit grid mesh, we demonstrate how they can be used to warp digital pho-tographs to achieve a variety of effects. One such effect is modifying the perspective of the camera that took a given photograph (without moving the camera). A related, but more challenging, effect is re-photography – warping a contemporary photograph in order to reproduce the camera view present in a vintage photograph of the same scene - taken many years before with a different camera from a different viewpoint. We apply the generalized ASAP mapping to these images, discretized to a unit grid. Using a quad mesh (as opposed to a triangle mesh) permits biasing towards affine maps of the unit squares. This allows the introduction of an As-Affine-As-Possible (AAAP) mapping for a good approximation of the homographies present in these warps, achieving quite accurate results. We demonstrate the advantages of the AAAP mapping on a variety of synthetic and real-world examples.

mini-gallery         code

Renjie Chen and Ofir Weber
Bounded Distortion Harmonic Mappings in the Plane
ACM Transactions on Graphics, 34(4) (SIGGRAPH 2015)

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.

We establish the sufficient and necessary conditions for a harmonic planar mapping to have bounded distortion. Our key observation is that these conditions relate solely to the boundary behavior of the mapping. This leads to an efficient and accurate algorithm that supports handle-based interactive shape-and-image deformation and is demonstrated to outperform other state-of-the-art methods.


Roi Poranne and Renjie Chen* and Craig Gotsman
On Linear Spaces of Polyhedral Meshes
IEEE Transactions on Visualization and Computer Graphics, 21(5), 652-662, May 2015

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.

Our approach is based on a complete characterization of the maximal linear spaces of polyhedral meshes contained in the curved manifold of polyhedral meshes with a given topology. We show that these linear spaces can be described as nullspaces of differential operators, much like harmonic functions are nullspaces of the Laplacian operator. An analysis of this operator provides tools for global and local design of a polyhedral mesh, which fully expose the geometric possibilities and limitations of the given topology.

Renjie Chen and Andrew Maimone and Henry Fuchs and Ramesh Raskar and Gordon Wetzstein
Wide Field of View Compressive Light Field Display using a Multilayer Architecture and Tracked Viewers
Journal of the Society for Information Display, 22(10), 525–534, April 2015

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 real-time, glasses-free 3D display that offers a 100° × 40° field of view.

Renjie Chen and Ofir Weber and Daniel Keren and Mirela Ben-Chen
Planar Shape Interpolation with Bounded Distortion
ACM Transactions on Graphics, 32(4) (SIGGRAPH 2013)

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 fold-overs 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.
We further present a discretization and an efficient practical algorithm to compute the interpolant and demonstrate its usability and good convergence behavior on a wide variety of input shapes. The method is simple to implement and understand. We compare our method to state-of-the-art interpolation methods and demonstrate its superiority in various cases.


Renjie Chen and Craig Gotsman
Parallel blue-noise sampling by constrained farthest point optimization
Comput. Graph. Forum. (Proc. Sym. Geom. Proc.), 31(5), 1775-1785, 2012

Abstract:  We describe a fast sampling algorithm for generating uniformly-distributed 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 state-of-the-art approaches.  


Renjie Chen and Craig Gotsman
Localizing the Delaunay triangulation and its parallel implementation
Proceedings of the International Symposium on Voronoi Diagrams (ISVD), Rutgers, June 2012

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.

slides         code

Yin Xu and Renjie Chen and Craig Gotsman and Ligang Liu
Embedding a triangular graph within a given boundary
Computer Aided Geometric Design, 28, 349-356, 2011

Abstract:   Given a 3-vertex-connected 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.

Renjie Chen and Daniel Freedman and Zachi Karni and Craig Gotsman and Ligang Liu
Content-aware image resizing by quadratic programming
Proceedings of the NORDIA Workshop, San Francisco, June 2010. (Best Paper Award)

Abstract:  We present a new method for content-aware 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 magnification 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.

Ligang Liu and Renjie Chen and Lior Wolf and Daniel Cohen-Or
Optimizing photo composition
Comput. Graph. Forum. (Proc. Eurographics), 29(2), 469-478, 2010

Abstract:  We describe a fast sampling algorithm for generating uniformly-distributed 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 state-of-the-art approaches.  



Renjie Chen and Yin Xu and Craig Gotsman and Ligang Liu
A spectral characterization of the Delaunay triangulation
Computer Aided Geometric Design, 27(4), 295-300, 2010

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 piecewise-linear 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.

Renjie Chen and Ligang Liu and Guangchang Dong
Local resampling for patch-based texture synthesis in vector fields
International Journal of Computer Applications in Technology, 38(1/2/3), 124-133, 2010

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. Regular-grid patches produced by the local resampling are used as building blocks for texture synthesis. Then, texture optimization and patch-based 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.


Renjie Chen and Ligang Liu and Guangchang Dong
Mesh smoothing with vertex tolerance constraints(in Chinese)
Journal of Zhejiang University (Engineering Science), 44(9), 61-65, 2010

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.

Renjie Chen and Ligang Liu and Guangchang Dong
Detection of principal lines in images(in Chinese)
Journal of Image and Graphics of China, 15(3), 403-408, 2010.

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, Content-Aware Image Retargeting(in Chinese), PhD Thesis, Zhejiang University, June, 2010