Images and Geometry

Leader of the Group: Dr. Renjie Chen



Vision and Research Strategy

As its core mission, computer graphics endeavors to deliver natural-looking and convincing graphic contents, such as images, videos and 3D models for various applications, including design, entertainment, education, simulation, etc. In many cases, “natural-looking” can be interpreted as low distortion with respect to some reference. Depending on the application, the distortion can be measured as the amount of feature stretching, non-feature noise, change of scale, self-overlapping, and so on. As distortions can largely affect human perception of the contents, we want to generate images and shapes with no distortion or controlled amount of distortions, while satisfying the user-defined constraints for various applications.



Research Areas and Achievements

Shape Interpolation

Computer animation is a computer-aided process where an animator sets the tone for the behavior of the animation in the form of keyframes, while the computer automatically generates intermediate frames that interpolate these keyframes. A good interpolation algorithm allows the artist to increase the time between the keyframes by producing natural and well-behaved intermediate frames that match the artist’s expectations, hence reducing the amount of manual labor. We developed a novel shape interpolation method that blends 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 produces mappings that are superior to those of existing techniques due to its guaranteed bounds on geometric distortion.


Pseudo-Harmonic Barycentric Coordinates

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 alter-natives are a number of other simpler schemes which have closed forms, many designed as a (computationally) cheap approximation to harmonic coordinates. 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, prove that they are pseudo-harmonic and demonstrate experimentally that they provide a superior approximation to harmonic coordinates.


Transfinite Barycentric Mappings

Transfinite barycentric kernels are the continuous version of traditional barycentric coordinates and are used to define interpolants of values given on a smooth planar contour. When the data is two-dimensional, these kernels may be conveniently expressed using complex number algebra, simplifying much of the notation and results. 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 show that the transfinite versions of the popular three-point barycentric coordinates 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. This is useful for rendering images deformed by planar barycentric mappings.


Generalized ASAP for Re-photography

We generalize the classical discrete conformal mappings of planar triangle meshes to the case of quad meshes, taking into account the mapping of the interior of the quad. 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. As an application, we demonstrate how they can be used to warp digital photographs to achieve 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 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.