size=-1 color=black>Yahoo! is not affiliated with the authors of this page or responsible for its content.
INTERACTIVE REACH PLANNING FOR ANIMATED CHARACTERS USING HARDWARE ACCELERATION

INTERACTIVE REACH PLANNING FOR ANIMATED CHARACTERS
USING HARDWARE ACCELERATION


YING LIU

A DISSERTATION
in
Computer and Information Science
University of Pennsylvania


Presented to the Faculties of the University of Pennsylvania in Partial Fulfillment of the
Requirements for the Degree of Doctor of Philosophy.
2003




Norman I. Badler
Supervisor of Dissertation




Benjamin C. Pierce
Graduate Group Chair
ii





Copyright 2003
by
Ying Liu
iii

Acknowledgements

First of all, I would like to thank my advisor, Dr. Norman I. Badler, for his guidance, support,
patience and constant encouragement throughout my dissertation research. He is always
accessible to me and his comments are always inspiring and insightful.

I thank my dissertation committee members, Dr. Jean Gallier, Dr. Vijay Kumar, Dr. Stephen Lane
and Dr. Ming Lin, for their valuable comments and suggestions.

My fellow labmates from the Center for Human Modeling and Simulation make my 5 years
working and studying in Penn enjoyable and memorable. Special thanks to Koji Ashida for the
numerous discussions with me, to Jan Allbeck, Matt Beitler and JoDe Hendrick for the technical
support, to Gang Huang for performing live reaches in assist of the evaluation of this work.

The last but not the least, my thanks go to my family. I would like to thank my parents for being
patient and always having faith in me. I would also like to thank my husband Yang Lu for his
special encouragement and programming support.

iv

ABSTRACT
INTERACTIVE REACH PLANNING FOR ANIMATED CHARACTERS
USING HARDWARE ACCELERATION

Ying Liu

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.
v

Contents

1 Introduction................................................................................................................................ 1

1.1

Motivation ...................................................................................................................... 1

1.2

Problem Description....................................................................................................... 2

1.3

Objectives ....................................................................................................................... 3

1.4

Applications.................................................................................................................... 3

1.5

Organization ................................................................................................................... 4

2 Background Knowledge ............................................................................................................ 5

2.1

Motion Planning ............................................................................................................. 5

2.2

Classification of Motion Planning Problems.................................................................. 5

2.3

Workspace ...................................................................................................................... 6

2.4

Configuration.................................................................................................................. 6

2.5

Configuration Space ....................................................................................................... 6

2.6

Free Space ...................................................................................................................... 7

2.7

Basic Approaches to Solving Motion Planning.............................................................. 7

2.8

Taxonomy of Motion Planning Algorithms ................................................................... 8

2.9

Computational Complexity of Motion Planning Algorithms ......................................... 9

2.10

Depth Buffer................................................................................................................... 9

3 Related Work ........................................................................................................................... 11

3.1

Computer Animation .................................................................................................... 11

3.2

Robotics........................................................................................................................ 12

4 Human Arm Model.................................................................................................................. 15

4.1

Human Arm Model....................................................................................................... 15

4.2

Coordinate Systems ...................................................................................................... 16

4.3

Joint Specification ........................................................................................................ 17

vi
4.4

Joint Limits................................................................................................................... 17

4.5

Absolute and Relative Positioning ............................................................................... 18

4.6

Terminology and Notation ........................................................................................... 18

5 3-Step Reach Planning Algorithm.......................................................................................... 19

5.1

Algorithm Overview..................................................................................................... 19

5.2

Planning Procedure....................................................................................................... 23

5.3

Implementation and Experimental Results................................................................... 26

5.4

Discussion .................................................................................................................... 30

5.5

Limitations.................................................................................................................... 31

5.6

Summary ...................................................................................................................... 32

6 Sequential Planning Algorithm .............................................................................................. 34

6.1

Algorithm Overview..................................................................................................... 34

6.2

Spatial Search ............................................................................................................... 36

6.3

Joint Limits Checking................................................................................................... 49

6.4

Collision Detection....................................................................................................... 49

6.5

Planning Procedure....................................................................................................... 50

6.6

Path Execution.............................................................................................................. 53

6.7

Implementation and Experimental Results.......................................................