Interactive reach planning for animated characters using hardware acceleration

We present real-time articulated arm reach planning algorithms for virtual human figures. Given a start configuration and a goal location, we compute a collision-free path for a seven degrees of freedom arm from the start to the goal. We require automatic reaches with natural human movements at interactive rates. Different from the existing configuration space methods, we plan arm movements directly using constrained search in a discretized 3D workspace and efficient collision detection techniques using available graphics hardware. At each step of the process, the end effector is moved to an unoccupied and adjacent cell in the discretized workspace. The search is guided by, but not limited to, the distance gradient to the goal; this makes the process more powerful than potential field methods and not prone to get stuck in local minima. Three novel but successively more effective efforts to solve the reach problem are presented. The first, 3-step planning, searches end effector paths in the workspace and computes arm configurations using inverse kinematics. While the planning can be accomplished interactively, the incompleteness induced by an analytic (single solution) inverse kinematics procedure (IKAN) makes the algorithm fail too frequently. The second algorithm, sequential planning, seeks to find paths in the 3D workspace for wrist, elbow and hand, respectively. Intersecting spherical ranges for arm segments and exploring more candidate configurations improve completeness. In computer animation, it is vitally important that the computed motion for animated characters look natural and realistic. One aspect of naturalness is that internal strength dictates human postures. Therefore, the third algorithm extends sequential planning by incorporating a human strength model in a hybrid of kinematic and biomechanical techniques. The algorithms allow real-time planning in both static and dynamic environments. Algorithm performance is roughly proportional to the complexity of the workspace. No preprocessing for configuration spaces is required. Examples are shown illustrating the competence of the planners at generating motion plans for a typical human arm model