Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-10-05
2003-01-28
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S473000, C345S440000, C345S441000, C382S128000
Reexamination Certificate
active
06512516
ABSTRACT:
FIELD OF INVENTION
This invention relates to voxel-based systems and more particularly to a system for rapidly deforming volumetric inhomogenous objects.
BACKGROUND OF THE INVENTION
Surgical simulation requires interactive modeling and visualization of complex, 3D anatomical structures. For example, surgery of the abdomen involves probing and cutting through organs and tissues that have complex shapes and material properties. Because modeling the deformation and cutting of tissue requires a representation of interior structure. Volumetric object representation is well suited to surgical simulation. A volumetric representation can incorporate detailed information about internal anatomical or physiological structure. This detailed information can be used to model tissue deformation more accurately than a model which represents the object surface and assumes a homogeneous interior.
In the past, a so-called 3D ChainMail algorithm has been developed for rapid deformation of homogenous objects as described by S. Gibson “3D ChainMail: A fast algorithm for Deforming Volumetric Objects” Proceeding 1997 Synopsis on Interactive 3D Graphics pp. 149-154, Providence R.I. USA, 1997. In this algorithm, links between sampled data elements are established and characteristics of these links are defined. The links are such that an element is moved only if it needs to be which eliminates calculating movement of elements not affected by the movement of the selected element. The 3D ChainMail algorithm in one embodiment 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 neighboring elements only if a maximum or minimum preset distance is exceeded between the moved element and its neighbor.
While link characteristics are relatively easy to establish for homogenous materials, the problem is more complex for inhomogenous materials. Modeling of inhomogenous materials is important in applications ranging from image processing to virtual reality. In surgical simulation, for example, 3D ChainMail can be used for tissue modeling. Since tissue, in general, is not homogenous, techniques must be developed to take into account the speeds of propagation in inhomogenous materials.
SUMMARY OF THE INVENTION
In the subject invention, the 3D ChainMail algorithm is enhanced based on a physical model of how information is propagated through a body by passing it from one element to another. To achieve correct propagation of information in inhomogenous material, two basic concepts are introduced.
First, in ChainMail the material constraints determine the “stiffness” of a connection between two neighbors. To model inhomogenous material, different material constraints are assigned to different elements.
Secondly, the order in which neighbors of moved elements are considered for a move determines where in the body information is propagated first. The processing order can therefore be used to model different, direction-dependent propagation speeds in the material.
After moving an element, its neighbors are examined to determine whether any constraint has been violated. The constraints between two neighbors are the sum of the contributions from the two affected elements. Note, affected elements are those which are neighbors of a moved element. If a constraint was violated, the neighbor with the largest constraint violation is processed first. This is equivalent to processing neighbors in the order in which their constraints were violated. By always following this order, it is guaranteed that the information follows the “stiffest” links.
In summary, an improvement to a voxel-based system to permit rapidly deforming volumetric objects made up of inhomogeneous material includes providing different material constraints assigned to different elements, with the constraints of a link between two neighboring elements being calculated from contributions of the two affected elements. The order in which neighbors of moved element are considered for a move determines where in the body information is propagated first. The processing order can therefore be used to model different direction-dependent propagation speeds in the material.
REFERENCES:
Jegathese et al. “A New Approach for Goal-Oriented Deformation of Voxel Models”, (IEEE, this Conference was held Jun. 26-29, 1998, pp. 214-215).*
Chen et al. “Physically-based Animation of Volumetric Objects”, (IEEE, this Conference was held Jun. 8-10, 1998, pp. 154-160).*
Klein “Forward Deformation of PET Volumes Using Material Constraints”, (IEEE, this Conference was held Jun. 26-27, 1998, pp. 64-71).*
Schill et al. “Biomechanical Simulation of the Vitreous Humor in the Eye an Enhanced ChainMail Algorithm”, Oct. 1998, Internat. Conference on Medical Image Computing and Computer-Assisted Intervention, 9 pages.
Gibson Sarah F.
Schill Markus Andrew
Bringman Dirk
Mitsubishi Electric Research Laboratories Inc.
Nguyen Kimbinh T.
Zimmerman Mark
LandOfFree
Voxel-based system to permit rapidly deforming volumetric... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Voxel-based system to permit rapidly deforming volumetric..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Voxel-based system to permit rapidly deforming volumetric... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3029285