System for rapidly deforming a graphical object

• US 6,069,634 A
• Filed: 01/08/1997
• Issued: 05/30/2000
• Est. Priority Date: 01/08/1997
• Status: Expired due to Term

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Information Technology Centre Europe BV (Mitsubishi Electric Corporation)
• Inventors: Gibson, Sarah
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/780,388
• Time in Patent Office: 1,238 Days
• Field of Search: 345/427, 345/424, 345/420, 345/419, 345/441, 345/121
• US Class Current: 345/424
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2219/2016 Rotation, translation, scaling
• CPC Class Codes: G06T 2219/2021 Shape modification

Abstract

A voxel-based system for rapidly deforming volumetric objects performs simple deformation calculations for each element of the graphical object to be deformed such that when the object is manipulated, the object stretches or contracts through the movement of a selected element, followed by movement of neighboring elements only if a maximum or minimum preset distance is exceeded between the moved element and its neighbor. Thus elements are moved only if they need to be, which eliminates calculating movements of elements not affected by movement of the selected element. This in turn allows fast propagation of the deformation through the volume represented by the object to the deformed, with the motion constraints being similar to the motion provided by a set of linked elements in a chain.

Claims

1. A system for deforming a graphical object displayed amongst other graphical objects, comprising:

means including a computer for characterizing a graphical object as a volumetric object with volumetric elements;

a user interface coupled to said computer for selecting and moving a selected one of said volumetric elements;

means responsive to said user interface for deforming said graphical object by moving said selected volumetric element an amount specified by said user interface, the movement of said selected volumetric element resulting in the deformation of said graphical object;

means for detecting and preventing collisions between graphical objects during the deformation of said graphical object;

means coupled to the output of said graphical object deforming means for relaxing the relative positions of volumetric elements in the deformed graphical object based on the elasticity thereof; and

,

means coupled to the output of said relaxing means and including a display for rendering the result of moving, deforming and relaxing said volumetric graphical object.

2. The system of claim 1 wherein said graphical object deforming means includes

means for moving a neighboring volumetric element for a distance and in a direction corresponding to the movement of said selected volumetric element.

3. The system of claim 2 wherein said neighboring volumetric element is moved only when a predetermined min/max distance threshold between said predetermined volumetric element and said neighboring volumetric element is exceeded and then only by that amount to which said threshold is exceeded.

4. The system of claim 3 wherein said threshold is set according to the rigidity that said graphical object is to represent.

5. The system of claim 3 wherein the movement of said neighboring element causes movement of a further neighboring volumetric element whenever said predetermined distance threshold is exceeded between said neighboring volumetric element and said further neighboring volumetric element.

6. The system of claim 1 wherein said deformed graphical object relaxing means includes means for adjusting the volumetric element positions within the deformed object.

7. A system for deforming a graphical object, comprising:

means including a computer for characterizing a graphical object as a volumetric object with volumetric elements;

a user interface coupled to said computer for selecting and moving a selected one of said volumetric elements, with said selected element being surrounded by neighboring volumetric elements;

means responsive to said user interface for deforming said graphical object by moving said selected volumetric element an amount specified by said user interface, the movement of said selected volumetric element resulting in movement of one or more of said neighboring volumetric elements, thus to cause the deformation of said graphical object; and

,

means coupled to the output of said deforming means and including a display for rendering the result of deforming said graphical object.

8. The system of claim 7 wherein said graphical object deforming means includes

means for moving a neighboring volumetric element for a distance and in a direction corresponding to the movement of said selected volumetric element.

9. The system of claim 8 wherein said neighboring volumetric element is moved only when a predetermined min/max distance threshold between said predetermined volumetric element and said neighboring volumetric element is exceeded and then only by that amount to which said threshold is exceeded.

10. The system of claim 9 wherein said threshold is set according to the rigidity that said graphical object is to represent.

11. The system of claim 7 wherein the movement of said neighboring element causes movement of a further neighboring volumetric element whenever said predetermined distance threshold is exceeded between said neighboring volumetric element and said further neighboring volumetric element.

12. A system for deforming a graphical object, comprising:

means including a computer for characterizing a graphical object as a volumetric object with volumetric elements;

a user interface coupled to said computer for selecting and moving a selected one of said volumetric elements, with said selected element being surrounded by neighboring volumetric elements;

means responsive to said user interface for deforming said graphical object by moving said selected volumetric element an amount specified by said user interface, the movement of said selected volumetric element resulting in movement of one or more of said neighboring volumetric elements, thus to cause the deformation of said graphical object;

means coupled to the output of said graphical object deforming means for relaxing the deformed graphical object based on the elasticity thereof; and

,

means coupled to the output of said relaxing means and including a display for rendering the result of relaxing said deformed graphical object.

13. A method for rapidly deforming a graphical object characterized as a volumetric object with volumetric elements

selecting a volumetric element to be moved;

moving said selected element;

calculating the distances between said selected element and an ordered sequence of neighboring elements after said selected element'"'"'s moved;

comparing said distances with predetermined min/max thresholds; and

,

moving an element which is a neighbor of said selected element in the direction of movement of said selected element only if said min/max threshold is exceeded and only by that amount that said min/max threshold is exceeded, whereby the rapidity of propogation of the resultant deformation throughout the volume derives from the fact that each element in the volume is considered at most once for each deformation, is compared to only one neighbor to determine if and how it must be moved, and due to the fact that the deformation is propogated outwards from said selected element and terminates as soon as possible due to the min/max threshold constraints.

14. The method of claim 13 wherein said calculating step includes maintaining a list of pointers to elements that have been moved and their previous positions, maintaining lists of neighboring elements for movement, classified as to whether they are a top, left, bottom, or right neighbor of said selected element;

processing each element in turn starting from said selected element and proceeding in order through right, left, top, and bottom lists of elements, with deformation min/max thresholds checked against said selected element; and

wherein said moving step includes moving a checked element only if said min/max threshold is exceeded, with the movement stopped when said min/max threshold is satisfied.

15. A method for deforming a graphical object represented by graphical elements stored as a data structure in a memory of a computer system, each graphical element having associated values characterizing the graphical object at a specific location of the graphical object, comprising the steps of:

assigning a minimum and maximum distance threshold to each graphical element;

selecting a graphical element at a location;

first moving the selected graphical element a distance in a selected direction from the location;

in response to the first moving, second moving a neighboring graphical element located in the direction from the selected graphic element if the distance moved is less than the minimum or greater than the maximum distance threshold of the adjacent graphic element; and

repeating the second moving for a next neighboring graphical element in the direction until the distance is greater than the minimum or less than the maximum distance threshold of the corresponding next neighboring graphic element.

16. The method of claim 15 wherein the graphical object has three dimensions, each graphical element is a voxel, and wherein neighboring graphical elements are to the left and right, the top and bottom, and the front and back of the selected graphical element.