Abstract: Locomotion such as walking, jogging, and running is one of the most basic forms of daily human motions. However, the previous methods can hardly generate the convincing locomotion of a character following a curved path with a desired speed and style. Based on scattered data interpolation, we propose a novel approach for on-the-fly generation of convincing locomotion, given parameters such as speed, turning angle, and style, on top of others given in the previous approaches. We first present an incremental scheme for timewarping to align the example motion clips of various speeds. Then, we provide a novel scheme for joint angle blending which guarantees similar poses to have similar representations. Finally, we show how to adapt the blended motion to the target character and the environment in an on-line, real-time manner. The resulting motions are not only convincing but also effectively controlled to reflect animator's intention. Our approach is efficient enough for on-line applications such as real-time animation systems and video games.