Shape Interpolations with Unions of Spheres

VISHWA RANJAN and ALAIN FOURNIER
Department of Computer Science, University of British Columbia

Abstract

Shape interpolation is the process of transforming continuously one object into another. This is useful in applications such as object recognition, object registration and computer animation. Unfortunately, good" shape interpolation is as ill-defined as shape" itself. To be able to control the process in a useful way, we need a representation for the objects using primitives which capture at least some aspects of their shape, with methods to convert other representations to this one. We present here a method to interpolate between two objects represented as a union of spheres. We briefly describe the representation and its properties, and show how to use it to interpolate. Once a distance metric between the spheres is defined (we show different metric producing controlled effects), the algorithm optimally matches the spheres in the two models using a bipartite graph. The transformation then consists in interpolating between the matched spheres. If the union of spheres has been simplified, the other spheres are matched as a function of their positions within their representative cluster. Examples are shown and discussed with two- and three-dimensional objects. The results show that the union of spheres helps capture some notion of shape, and helps to automatically match and interpolate shapes.

Keywords: shape interpolation, stability, volume interpolation, union of spheres, matching, metamorphosis, registration

1 Introduction

Shape interpolation or object interpolation consists in continuously deforming one object into another. In addition to its aesthetic appeal (e.g., in morphing" or metamorphosis [1, 5]), it can be used in visualizing the evolution of objects (e.g., growth of a tumor), in the registration of two views of the same object, or in automatic in-betweening in key-frame animation. The union of spheres (UoS) representation in which the set union of overlapping spheres is used to represent 3D objects is a computer representation of an object which has useful features for many applications [7]. In this paper we present an algorithm to interpolate between two UoS representations of the same or different object(s). The approach is to first match the spheres from one UoS representation to the other and then interpolate between the matched spheres.

2 Shape transformation problem

We want to define a continuous transformation between two objects A (the source object) and B (the destination or target object). Both objects are represented by a set of primitives, fa1, a2, : : :, ang for A and fb1, b2, : : :, bkg for B. Generally the primitives a and b are assumed to be of the same type, but both the number of primitives n and k, and the topologies of A and B can be different. Without loss of generality, we assume n <= k in this paper.

It is difficult to measure the quality of or compare shape transformation algorithms in terms of the intermediate shapes that are generated, since it is already difficult to compare shapes themselves. Generally,