System, method and data structure for simulated interaction with graphical objects

• US 7,676,356 B2
• Filed: 10/31/2005
• Issued: 03/09/2010
• Est. Priority Date: 10/01/1999
• Status: Active Grant

• Current Assignee: Immersion Corporation
• Original Assignee: Immersion Corporation
• Inventors: Ullrich, Christopher J., Tremblay, Marc, Tian, Jerry, DesRosiers, Hugo J. C., Carmel, Ron, Kramer, James F., Gomez, Daniel
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): GUILL, RUSSELL L
• Application Number:
  US11/264,743
• Publication Number:
  US 20060122819A1
• Time in Patent Office: 1,590 Days
• Field of Search: 345/420, 345/440, 703/2, 703/6, 703/21
• US Class Current: 703/21
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2210/28 Force feedback
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

Object simulation and interaction of and between computer-generated or graphical objects in a virtual space includes neutral scene graphs, data structures and procedures for using such graphs and data structures.

Claims

1. A method for simulating interaction with graphical objects, the method comprising:

within a computing device comprising one or more processors, a memory, and one or more clocks, wherein the computing device is configured to transmit signals from the one or more processors to the memory, sending one or more signals from the processor to the memory to configure the memory to store a representation of a first scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a second scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a neutral scene graph, comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the second scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the second scene graph, and any sending one or more signals from the one or more processors to the memory to configure the memory to update the representation of the first scene graph at a first update rate timed by one of the one or more clocks; and

sending one or more signals from the one or more processors to the memory to configure the memory to update the representation of the second scene graph at a second update rate timed by one of the one or more clocks, the second update rate being substantially higher than the first update rate.

2. The method of claim 1, wherein the neutral scene graph provides a topology transformation between the first scene graph and the second scene graph.

3. The method of claim 1, wherein the first scene graph and the second scene graph are asynchronous, further comprising the step of synchronizing the representation of the first scene graph and the representation of the second scene graph.

4. The method of claim 1, wherein the first scene graph is a graphical scene graph, and the second scene graph is a haptic scene graph.

5. The method of claim 1, wherein the first update rate is between about 10-60 Hz;

and wherein the second update rate is between about 1000-2000 Hz.

6. A method for simulating interaction with graphical objects, the method comprising:

within a computing device comprising one or more processors, a memory, and one or more clocks, wherein the computing device is configured to transmit signals from the one or more processors to the memory, sending one or more signals from the processor to the memory to configure the memory to store a representation of a first scene graph comprising a representation of a plurality of nodes and one or more interconnections between the plurality of nodes;

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a second scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a first neutral scene graph, comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the second scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the second scene graph;

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a third scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes; and

sending one or more signals from the one or more processors to the memory to configure the memory to store a representation of a second neutral scene graph, comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the third scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the third scene graph.

7. A method for simulating interaction with graphical objects, the method comprising:

within a computing device comprising one or more processors, a haptic device, and a memory, wherein the computing device is configured to transmit signals from the haptic device to the one or more processors, and to transmit signals from the one or more processors to the memory, sending one or more signals from the haptic device to the one or more processors, wherein the one or more signals represent geometric information about a plurality of real-world objects;

sending one or more signals from the one or more processors to the memory to configure the memory to store one or more data structures comprising a plurality of virtual representations, each virtual representation uniquely associated with a real-world object from the plurality of real-world objects, and each virtual representation comprising geometric information associated with the real world object;

determining if at least one contact state exists between a first virtual representation from the plurality of virtual representations and a second virtual representation from the plurality of virtual representations;

if at least one contact state exists, determining if the at least one contact state meets a predetermined threshold number of required contact states between the first virtual representation and the second virtual representation, each of the at least one contact states being associated with a corresponding portion of the first virtual representation and a portion of the second virtual representation;

if the at least one contact state meets a predetermined threshold number of contact states, determining if a minimum drop angle parameter is exceeded for each portion of the first virtual representation associated with the at least one contact state;

if the minimum drop angle parameter is exceeded, sending a signal to indicate a grasp state associated with the second virtual representation; and

if the minimum drop angle parameter is not exceeded, sending a signal to indicate a release state associated with the second virtual representation.

8. The method of claim 7, wherein the first virtual representation is a virtual representation of a hand and each portion of the virtual representation of the hand that is associated with a contact state being a virtual representation of a finger of the hand.

9. The method of claim 7, further comprising:

analyzing a relationship between the first virtual representation and the second virtual representation;

determining, at least partially based on the analyzed relationship, a local surface approximation associated with each portion of the first virtual representation associated with the at least one contact state and each portion of the first virtual representation within a predetermined distance from the second virtual representation; and

storing each local surface approximation in memory.

10. The method of claim 7, further comprising:

analyzing a relationship between the first virtual representation and the second virtual representation;

determining, at least partially based on the analyzed relationship, a local surface approximation associated with each portion of the first virtual representation associated with the at least one contact state and each portion of the first virtual representation within a predetermined distance from the second virtual representation;

storing each local surface approximation in memory; and

sending a signal configured to cause a haptic effect in the haptic device at least partially based on at least one local surface approximation stored in memory, the haptic effect being configured to output a sensation at least partially based on the at least one contact state.

11. An apparatus for simulating interaction with graphical objects, the apparatus comprising:

a computing device comprising one or more processors, one or more data storage devices, and one or more clocks, wherein the computing device is configured to transmit signals from the one or more processors to the memory;

means for sending one or more signals from the processor to the one or more data storage devices to configure the one or more data storage devices to store a representation of a first scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a second scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a neutral scene graph comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the second scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the second scene graph;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to update the representation of the first scene graph at a first update rate timed by one of the one or more clocks; and

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to update the representation of the second scene graph at a second update rate timed by one of the one or more clocks, the second update rate being substantially higher than the first update rate.

12. The apparatus of claim 11, wherein the neutral scene graph is configured to provide a topology transformation between the first scene graph and the second scene graph.

13. The apparatus of claim 11, further comprising means for synchronizing the representation of the first scene graph and the representation of the second scene graph if the first scene graph and the second scene graph are asynchronous.

14. The apparatus of claim 11, wherein the first scene graph is configured to be a graphical scene graph representing geometric information comprising a representation of one or more images on a graphical display system, and the second scene graph is configured to be a haptic scene graph comprising a representation of geometric information regarding the environment of a haptic device.

15. The apparatus of claim 11:

means for wherein the first update rate is between about 10-60 Hz; and

means for wherein the second update rate is between about 1000-2000 Hz.

16. An apparatus for simulating interaction with graphical objects, the apparatus comprising:

a computing device comprising one or more processors, one or more data storage devices, and one or more clocks, wherein the computing device is configured to transmit signals from the one or more processors to the memory;

means for sending one or more signals from the processor to the one or more data storage devices to configure the one or more data storage devices to store a representation of a first scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a second scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a first neutral scene graph comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the second scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the second scene graph;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a third scene graph comprising a representation of a plurality of nodes and of one or more interconnections between one or more of the plurality of nodes;

means for sending one or more signals from the one or more processors to the one or more data storage devices to configure the one or more data storage devices to store a representation of a second neutral scene graph, comprising a representation of a plurality of associations between each node from the plurality of nodes of the first scene graph and a node from the plurality of nodes of the third scene graph, wherein each association is independent of any interconnections of the first scene graph and any interconnections of the third scene graph.

17. An apparatus for simulating interaction with graphical objects, the apparatus comprising:

one or more data storage devices;

means for uniquely associating a plurality of real-world objects with a plurality of virtual representations stored in the one or more data storage devices, each virtual representation from the plurality of virtual representations being a representation of its associated real-world object from the plurality of real-world objects;

means for determining if at least one contact state exists between a first virtual representation from the plurality of virtual representations and a second virtual representation from the plurality of virtual representations;

means for, if at least one contact state exists, determining if the at least one contact state meets a predetermined threshold number of required contact states between the first virtual representation and the second virtual representation, each of the at least one contact states being associated with a corresponding portion of the first virtual representation and a portion of the second virtual representation;

means for, if the at least one contact state meets a predetermined threshold number of contact states, determining if a minimum drop angle parameter is exceeded for each portion of the first virtual representation associated with the at least one contact state;

means for, if the minimum drop angle parameter is exceeded, sending a signal to indicate a grasp state associated with the second virtual representation; and

means for, if the minimum drop angle parameter is not exceeded, sending a signal to indicate a release state associated with the second virtual representation.

18. The apparatus of claim 17, wherein the first virtual representation is configured to be a virtual representation of a hand and each portion of the virtual representation of the hand that is associated with a contact state, itself configured to be a virtual representation of a finger of the hand.

19. The apparatus of claim 17, further comprising:

means for analyzing a relationship between the first virtual representation and the second virtual representation;

means for determining, at least partially based on the analyzed relationship, a local surface approximation associated with each portion of the first virtual representation associated with the at least one contact state and each portion of the first virtual representation within a predetermined distance from the second virtual representation; and

means for storing each local surface approximation in the one or more data storage devices.

20. The apparatus of claim 17, further comprising:

means for analyzing a relationship between the first virtual representation and the second virtual representation;

means for determining, at least partially based on the analyzed relationship, a local surface approximation associated with each portion of the first virtual representation associated with the at least one contact state and each portion of the first virtual representation within a predetermined distance from the second virtual representation;

means for storing each local surface approximation in the one or more data storage devices; and

means for sending a signal configured to cause a haptic effect at least partially based on at least one local surface approximation stored in the one or more data storage devices, the haptic effect being configured to output a sensation at least partially based on the at least one contact state.