Abstract: In many constrained environments, precise control of foot placement during character locomotion is crucial to avoid collisions and to ensure a natural locomotion. In this paper, we present a new exact motion synthesis technique that generates planar parameterized stepping motions based on a combination of rotational and Cartesian interpolation. Existing stepping motions are blended in a linearized representation to guarantee exact control of foot placement. By concatenating these parameterized steps, we can generate highly-constrained stepping animations in real-time. Furthermore, because of a novel blend candidates selection strategy, soft constraints such as stance duration and foot orientation are also taken into account. We will show that our technique can generate a variety of different stepping animations efficiently, even though we impose many constraints on the animation.