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 counter-intuitive. 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:

1. A set of theoretical conditions for preventing self-intersection by ensuring the injectivity (one-to-one mapping) of FFD.
2. An exact (necessary and sufficient) injectivity test which is accurate but computationally costly.
3. An efficient but approximate injectivity test which is a sufficient condition only.
4. A new form of DMFFD which acts by composing many small injective deformations. This expands the range of possible deformations without sacrificing the speed of the approximate test.