Preventing self-intersection under free-form deformation

Free-Form Deformation (FFD) is a versatile and efficient modeling technique which transforms an object by warping the surrounding space. The conventional user-interface is a lattice of movable control points but this tends to be cumbersome and counterintuitive. Directly Manipulated Free-Form Deformation (DMFFD) allows the user to drag object points directly and has proven useful in an interactive sculpting context. A serious shortcoming of both FFD and DMFFD is that some deformations cause self-intersection of the object. This is unrealistic and compromises the object's validity and suitability for later use. An in-built self-intersection test is thus required for FFD and its extensions to be truly robust In this paper, we present the following novel results set of theoretical conditions for preventing self-intersection by ensuring the injectivity (one-to-one mapping) of FFD, an exact. (necessary and sufficient) injectivity test which is accurate but computationally costly, an efficient but approximate injectivity test which is a sufficient condition only, and a new form of DMFFD which acts by composing many small injective deformations. The latter expands the range of possible deformations without sacrificing the speed of the approximate test.

1 Introduction

Free-Form Deformation (FFD) [7], [29] and its extensions form a class of highly intuitive, versatile, and efficient free-form modeling and animation tools. They address the task of computer-assisted shape design and modification by warping the ambient space containing an embedded object. However, a major drawback which is often overlooked in the literature is the self-intersection of objects under FFD. In this paper, we present a novel solution to this problem by developing two self-intersection tests: the first exact, although inefficient, and the second approximate, but efficient. Finally, we seamlessly incorporate this latter test into Directly Manipulated Free-Form Deformation (DMFFD) [19], [8], providing a robust and interactive modeling tool which prevents self-intersection.