Manipulation of graphic structures

• US 6,025,852 A
• Filed: 05/24/1996
• Issued: 02/15/2000
• Est. Priority Date: 05/24/1996
• Status: Expired due to Fees

• Current Assignee: Autodesk, Inc.
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Zhao, Jianmin
• Primary Examiner(s): Feild, Joseph H.
• Assistant Examiner(s): Young, John L.
• Application Number:
  US08/653,671
• Time in Patent Office: 1,362 Days
• Field of Search: 345/473, 345/474, 395/99, 395/95, 395/90, 364/167.01, 364/512, 364/474.24
• US Class Current: 345/474
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation

Abstract

Manipulation of a graphic structure having a root, a joint and an end effector to a configuration positioning the structure'"'"'s end effector at a goal position is aided by determining characteristic configurations for the structure having different distances between the root and the end effector. The characteristic configurations form the basis of a transition function mapping goal distances between the root and goal positions to intermediate configurations, with the intermediate configurations having end effector distances (between the root and end effector) equal to the corresponding goal distances. The intermediate configuration may be reoriented to a final configuration positioning the end effector at the goal position.

Claims

1. A computer-implemented method for aiding manipulation of a graphic structure having a root, at least one joint, and an end effector, the method comprising:

determining two or more characteristic configurations for the graphic structure, each having a different end effector distance between the root and the end effector; and

determining a transition function based on the characteristic configurations, for mapping goal distances between the root and the end effector to intermediate configurations.

2. The method of claim 1, wherein one of the determined characteristic configurations has an end effector distance that is a minimum distance between the root and the end effector.

3. The method of claim 1, wherein one of the determined characteristic configurations has an end effector distance that is a maximum distance between the root and the end effector.

4. The method of claim 1, further comprising determining three or more characteristic configurations having different end effector distances, including a first characteristic configuration having an end effector distance of a minimum distance between the root and the end effector and a second characteristic configuration having an end effector distance of a maximum distance between the root and the end effector, and wherein the remaining characteristic configurations have end effector distances that are intermediate distances between the root and the end effector.

5. The method of claim 4, wherein the transition function maps goal distances to intermediate configurations by interpolating between characteristic configurations.

6. The method of claim 1, wherein the transition function maps goal distances to intermediate configurations by interpolating between characteristic configurations.

7. The method of claim 1, wherein the graphic structure has two or more joints, each joint having an assigned weight, and the transition function maps goal distances to intermediate configurations in accordance with the assigned weights.

8. The method of claim 1, further comprising the steps of:

using the transition function to map a distance between the root and a specified goal position to an intermediate configuration; and

reorienting the intermediate configuration to a final configuration positioning the end effector at the specified goal position.

9. The method of claim 1 further comprising, inputting a goal distance to the transition function to determine an intermediate configuration of the graphic structure.

10. The method of claim 1 wherein the transition function comprises a function that determines a set of angles that configure the graphic structure.

11. A computer-implemented method for aiding manipulation of a graphic structure having a root, at least one joint, and an end effector to a final configuration positioning the end effector at a goal position, the method comprising:

mapping a goal distance between the root and the goal position to an intermediate configuration for the graphic structure using a predetermined transition function, wherein the intermediate configuration has an end effector distance between the root and the end effector equal to the goal distance;

determining the final configuration for the graphic structure by reorienting the intermediate configuration such that the final configuration positions the end effector at the goal position.

12. A memory device storing computer-readable instructions for aiding a computer to manipulate a graphic structure having a root, at least one joint, and an end effector, the instructions comprising:

instructions for determining two characteristic configurations for the graphic structure, having two different end effector distances between the root and the end effector; and

instructions for determining a transition function based on the characteristic configurations, for mapping goal distances between the root and the end effector to intermediate configurations for the graphic structure.

13. The memory device of claim 12, wherein one of the determined characteristic configurations has an end effector distance that is a minimum distance between the root and the end effector.

14. The memory device of claim 12, wherein one of the determined characteristic configurations has an end effector distance that is a maximum distance between the root and the end effector.

15. The memory device of claim 12, further comprising instructions for determining three or more characteristic configurations having different end effector distances, including a first characteristic configuration having an end effector distance of a minimum distance between the root and the end effector and a second characteristic configuration having an end effector distance of a maximum distance between the root and the end effector, and wherein the remaining characteristic configurations have end effector distances that are intermediate distances between the root and the end effector.

16. The memory device of claim 15, wherein the transition function maps goal distances to intermediate configurations by interpolating between characteristic configurations.

17. The memory device of claim 12, wherein the transition function maps goal distances to intermediate configurations by interpolating between characteristic configurations.

18. The memory device of claim 12, wherein the graphic structure has two or more joints, each joint having an assigned weight, and the transition function maps goal distances to intermediate configurations in accordance with the assigned weights.

19. The memory device of claim 12, further comprising:

instructions for using the transition function to map a distance between the root and a specified goal position to an intermediate configuration; and

instructions for reorienting the intermediate configuration to a final configuration positioning the end effector at the goal position.

20. A memory device storing computer-readable instructions for aiding a computer to manipulate a graphic structure having a root, at least one joint, and an end effector to a final configuration positioning the end effector at a goal position, the instructions comprising:

instructions for determining an intermediate configuration of the graphic structure based on a predetermined transition function that maps goal distances between the root and the end effector to intermediate configurations of the graphic structure, the intermediate configuration having a distance between the root and the end effector substantially equal to the distance between the root and the goal position; and

instructions for determining the final configuration for the graphic structure by reorienting the intermediate configuration to a final configuration positioning the end effector at the goal position.

21. A computer-implemented method for aiding manipulation of a graphic structure having a root, a joint, and an end effector, the method comprising:

determining a minimum characteristic configuration having an end effector distance that is a minimum possible distance between the root and the end effector;

determining a maximum characteristic configuration having an end effector distance that is a maximum possible distance between the root and the end effector;

determining a transition function based on the minimum and maximum characteristic configurations, the function mapping goal distances between the root and the end effector to configurations of joints of the graphic structure;

determining different joint configurations of the graphic structure by inputting different goal distances between the root and the end effector to the transition function.

22. The method of claim 21, further comprising after determining a configuration of the graphic structure, rotating the determined configuration.