Premium
Bidirectional Search for Interactive Motion Synthesis
Author(s) -
Lo WanYen,
Zwicker Matthias
Publication year - 2010
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2009.01626.x
Subject(s) - merge (version control) , computer science , speedup , search algorithm , path (computing) , bidirectional search , graph , graph traversal , algorithm , motion (physics) , theoretical computer science , beam search , incremental heuristic search , computer vision , parallel computing , programming language
We present an approach to improve the search efficiency for near‐optimal motion synthesis using motion graphs. An optimal or near‐optimal path through a motion graph often leads to the most intuitive result. However, finding such a path can be computationally expensive. Our main contribution is a bidirectional search algorithm. We dynamically divide the search space evenly and merge two search trees to obtain the final solution. This cuts the maximum search depth almost in half and leads to significant speedup. To illustrate the benefits of our approach, we present an interactive sketching interface that allows users to specify complex motions quickly and intuitively.