Electronic device for processing image-data, for simulating the behaviour of a deformable object

• US 6,714,901 B1
• Filed: 07/16/1999
• Issued: 03/30/2004
• Est. Priority Date: 11/19/1997
• Status: Expired due to Term

• Current Assignee: Inria Institut National de Recherche EN Informatique et EN Automatique
• Original Assignee: Inria Institut National de Recherche EN Informatique et EN Automatique
• Inventors: Cotin, Stephace, Delingette, Herve, Ayache, Nicholas
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARCIA OTERO, EDUARDO
• Application Number:
  US09/341,651
• Time in Patent Office: 1,719 Days
• Field of Search: 703/7, 703/6, 434/262, 345/701, 345/702, 345/771
• US Class Current: 703/7
• CPC Class Codes: B25J 9/1689 Teleoperation
• CPC Class Codes: G05B 19/4097 characterised by using design data to control NC machines, e.g. CAD/CAM G05B19/4093 takes precedence
• CPC Class Codes: G06F 3/011 Arrangements for interaction with the human body, e.g. for user immersion in virtual reality blind teaching G09B21/00

Abstract

An electronic device for processing image data, particularly image data pertaining to medical procedures, includes a user interface with force feedback (4) corresponding to tool reactions, a “collision” module (18) for estimating a point of intersection between a straight line embodying a displacement derived from the action of the tool and a surface mesh of a given object, and an internal forces module (16) which estimates internal forces exerted on nodes of a first part of at least a volume mesh of the object, on the basis of a displacement applied on nodes pertaining to the surface mesh containing a point of intersection, of boundary conditions, and of node tensors and link tensors, from matrices of rigidity, and a reaction module (20) for determining the reaction force of the object corresponding to its deformation estimated on the basis of the internal forces, such that the force generated by the user interface (4) is balanced by reaction force.

Claims

1. An improved electronic device for processing image data, of the type that includes

a user interface (4) capable of generating a force feedback, in accordance with the reactions of a tool (6, 7),

an internal forces module (16) able, on designation of a 3D object appearing in a set of image data, to establish a field of internal forces between nodes (N) of a volume meshing dependent on a surface meshing of this object, on the basis of a deformation law and of an action defined by the user interface (4) and representative of a maneuver of the said tool, wherein the volume meshing includes links between the nodes thereof, and additionally includes volume mesh cells that are defined by the notes and the links, and

a reaction module (20) for determining a reaction force of the object which corresponds to its deformation estimated on the basis of the internal forces, so that the force generated by the user interface (4) is substantially balanced by this reaction force, and

a refresh module (17) for calculating new image data of the object, in the presence of its estimated deformations supplemented with a representation of the said tool,

wherein the improvement comprises:

a collision module (18) able to estimate a point of intersection between a straight line embodying a displacement derived from the said defined action and the said surface meshing,

wherein the internal forces module (16) is devised so as to estimate the internal force exerted on each node of a first part at least of the volume meshing of the object on the basis of the said displacement applied to the nodes belonging to a surface mesh cell containing the said point of intersection, of boundary conditions, and of node tensors and link tensors emanating respectively for each node and each link of this first part at least, from stiffness matrices specific to each volume mesh cell of at least the said first part and dependent on the deformation law.

2. Device according to claim 1, further comprising a meshing module able to designate the said 3D object by determination of an external envelope, then to decompose the said envelope into the said surface mesh cells with a view to the decomposing of the internal volume of the envelope into the said volume mesh cells.

3. Device according to claim 2, wherein the said external envelope is obtained by a method of segmentation.

4. Device according to claim 2, wherein the said surface mesh cells are triangles.

5. Device according to claim 4, wherein the said volume mesh cells are tetrahedra formed from the triangular surface mesh cells.

6. Device according to claim 5, wherein the said volume mesh cells are obtained by a Delaunay-Voronoi method.

7. Device according to claim 2, wherein the internal forces module (16) is devised so as to calculate the stiffness matrices of each volume mesh cell, as well as the said node tensors and link tensors.

8. Device according to claim 1, wherein the said deformation law is a volume linear elastic law.

9. Device according to claim 1, wherein the internal forces module (16) is devised so as to calculate the internal force exerted on each node of the said first part of the volume meshing on the basis of the product of its node tensor and the estimated displacement of this node, and of a summation, over the set of neighboring nodes possessing a link with the said node, of the product of the link tensor, associated with the link between the neighboring node and the said node, and of the estimated displacement of this neighboring node.

10. Device according to claim 1, wherein the said internal forces module (16) is able to determine the internal forces exerted on some at least of the nodes of the first part of the volume meshing on the basis of the deformation law and of auxiliary surface forces dependent on stored, chosen parameters of the said object.

11. Device according to claim 1, wherein the said internal forces module (16) is able to estimate the displacements of the nodes of the volume meshing on the basis of the displacement derived from the defined action and from at least one external force.

12. Device according to claim 1, wherein the said estimated displacements of the nodes, other than those of the said surface mesh cell comprising the said point of intersection, are obtained by a method chosen from among at least the Euler method and the Runge-Kutta method.

13. Device according to claim 12, wherein the said deformation is obtained by the so-called order 4 Runge-Kutta method.

14. Device according to claim 1, wherein the said internal forces module (16) is able, after determining the estimated displacements of the nodes, to delete at least one link between neighboring nodes or a volume mesh cell as a function of a first criterion, then to update the node tensors and the link tensors as a function of the deleted link(s), and lastly to recalculate the internal forces of the nodes of at least the first part of the volume meshing.

15. Device according to claim 14, wherein the first criterion pertains to at least one parameter chosen from among at least one cue transmitted by the said user interface (4) and relating to the type of tool (6, 7) maneuvered, a volume variation of the volume mesh cell comprising the said link or the said volume mesh cell to be deleted, and a length variation of a link of the volume mesh cell comprising the said link to be deleted.

16. Device according to claim 15, wherein the said internal forces module (16) is able, after determining the estimated displacements of the nodes, to delete a node in the event of detecting the deletion of all the links which join the said node to the neighboring nodes or as a function of the said first criterion, then to update the node tensors and the link tensors as a function of the node and of the deleted links, and lastly to recalculate the internal forces of the nodes of at least the first part of the volume meshing.

17. Device according to claim 16, wherein the said internal forces module (16) is able, in the event of the deletion of a link and/or of a node and before updating the link tensors and node tensors, to add new nodes and new links in such a way as to remesh the said volume meshing.

18. Device according to claim 1, wherein the internal forces module (16) is devised so as to estimate the internal force exerted on each node of the said volume meshing of the said object.

19. Device according to claim 1, wherein the internal forces module (16) is able to determine the internal forces exerted on the nodes of at least a second part of the said volume meshing on the basis of boundary conditions defined by so-called connection nodes placed at an interface between the first and second parts, and of a table of deformation tensors, each tensor of which is representative of the influence of an elementary displacement of each node of at least the said second part on each other node of at least this second part.

20. Device according to claim 19, wherein boundary conditions serving in the calculation of the internal forces of the second part are defined by the internal forces calculated for the said connection nodes in the guise of nodes of the first part.

21. Device according to claim 20, wherein the internal forces module (16) is devised so as to deduce from the values of the internal forces exerted on the nodes of the second part of the volume meshing, values of displacement of the connection nodes in such a way as to provide boundary conditions which in turn make it possible to calculate the internal forces of the nodes of the first part.

22. Device according to claim 21, wherein the internal forces module (16) is able to recalculate the values of the internal forces exerted on the nodes of the first and second parts of the volume meshing on the basis of the boundary conditions determined in succession on the connection nodes, until a position of so-called equilibrium of the internal forces of the said connection nodes is obtained.

23. Device according to claim 19, wherein the parts of the volume meshing are determined on the basis of a predetermined criterion pertaining at least to a parameter of the image data of the said object chosen from among physical parameters and anatomical parameters.

24. Device according to claim 19, wherein the second part is complementary to the said first part.

25. Device according to claim 19, further comprising a partitioning module able to subdivide the said volume meshing into the said parts, including the said first and 20 second parts.

26. Device according to claim 1, wherein the said collision module (18) is able to determine a collision between at least two tools managed by the said user interface (4).

27. Device according to claim 26, wherein each tool comprises at least one end (7) which interacts with the object and is represented by at least one point.

28. Device according to claim 27, wherein each tool has a shank that is represented by a multiplicity of points joined to one another as well as to the end(s) (7), by segments.

29. Device according to claim 27, wherein the said collision module (18) is able to create a three-dimensional space encompassing the external envelope of the said object, then to decompose the said space into volume blocks, the number of which is chosen so that each block comprises a number of node of the said volume meshing of the object substantially equal to the number of nodes of the other blocks, each block intersecting the said external surface comprising at least one node, and lastly to store in multiplets the coordinates of each node with reference to the volume block which encompasses it.

30. Device according to claim 29, wherein the said collision module (18) is able, for each tool, to determine the presence of a point of the tool in the said space through a comparison between the said multiplets and the coordinates of the said point, then the volume block of the said space in which the said point lies.

31. Device according to claim 30, wherein the said collision module (18) is able, for each tool, to determine the distance which separates the said point from the said node(s) encompassed in the said volume block so as to determine the smallest of these distances, termed the minimum distance, then to determine the distance which separates the said point from the said node(s) encompassed in a predetermined number of volume blocks neighboring the volume block in which it lies so as to compare its distances with the said minimum distance, then to determine the collection of surface mesh cells adjacent to the node associated with the said minimum distance so as to determine whether a segment defined by the said position of the point of the tool and by its previous position intersects one at least of these adjacent surface mesh cells, thus making it possible to estimate the barycentric coordinates of the point of collision between the said object and the said tool, with a view to their transmission to the said internal forces module (16).

32. Device according to claim 31, wherein the collision detection module (18) is able, for each tool, to modify the contents of the said multiplets between two determinations of presence of points inside the said volume blocks, in the event of detection of a deformation by the said internal forces module (16).

33. Device according to claim 1, wherein the user interface (4) comprises a harness (5) maneuverable by at least one operator hand so as to simulate the maneuvering of the said tool.

34. Device according to claim 1, further comprising display means (3) coupled to the refresh module (17) for displaying in real time in image form at least the image data of the object and of a representation of the tool.

35. Device according to claim 1, wherein the set of image data represents a three-dimensional digital image of a region including the 3D object.

36. Device according to claim 35, wherein the digital image is a medical image.

38. Device according to claim 3, wherein the method of segmentation comprises extracting iso-surfaces.

39. Device according to claim 11, wherein the at least one external force comprises gravitational force.

40. Device according to claim 23, wherein the parameter of the image data is intensity.

41. Device according to claim 35, wherein the region additionally includes at least one further 3D object.

37. An improved electronic process for processing image data, of the type that includes the steps of

providing a user interface (4) capable of generating a force feedback, in accordance with the reactions of a tool (6, 7),

establishing, on the basis of a deformation law and of an action defined by the user interface (4) and representative of a maneuver of the said tool, a field of internal forces between nodes of a volume meshing dependent on a surface meshing of a 3D object appearing in a set of image data, wherein the volume meshing includes links between the nodes thereof, and additionally includes mesh cells that are defined by the nodes and the links,

determining the reaction force of the object which corresponds to its deformation estimated on the basis of the internal forces, so that the force generated by the user interface (4) is substantially balanced by this reaction force, and

calculating new image data of the object, in the presence of the estimated deformations supplemented with the representation of the said tool,

wherein the improvement comprises:

estimating a point of intersection between a straight line embodying a displacement derived from the said defined action and the said surface meshing is estimated, and

estimating the internal force exerted on the nodes of a first part at least of the volume meshing of the object, on the basis of the displacement applied to the nodes belonging to the surface mesh cell containing the said point of intersection, of boundary conditions, and of node tensors and link tensors emanating respectively for each node and each link of this part at least, from stiffness matrices specific to each volume mesh cell of at least the said first part and dependent on the deformation law.

42. An improved method for permitting a user to manipulate a 3D virtual object with the aid of a user interface that senses movement of a tool by the user and that provides force feedback to the user, the virtual object appearing in a set of image data and having a surface meshing and a volume meshing, said method being of the type that includes

establishing, on the basis of a deformation law, a field of internal forces between nodes of the volume meshing when the virtual object is deformed by the tool;

determining a reaction force that is to be exerted by the user interface when the virtual object is deformed by the tool, the deformation of the virtual object being estimated at least in part on the basis of the internal forces; and

calculating new image data of the object, in the presence of the estimated deformation supplemented with a representation of the tool;

wherein the improvement comprises;

estimating a point of intersection between a straight line embodying a displacement of the tool and the surface meshing,

wherein the internal force exerted on the nodes of a part of at least the volume meshing of the virtual object is estimated on the basis of at least one factor, the at least one factor including a displacement applied to the nodes belonging to a surface mesh cell containing the point of intersection.