Patent Description:
A volume mesh is a representation of the interior volume of an object. A volume mesh may be used to simulate surface and volume deformation due to external forces through finite element analysis, for example. In a physically-based simulation, a volume mesh model of a physical object ordinarily includes a grid of tetrahedral or hexahedral elements that aids in the computation of deformations to the volume mesh due to virtual forces imparted to the volume mesh. A volume mesh, however, generally does not capture shading material and the outer texture of the simulated object as viewed under a light source. To this end, a surface mesh may be added to support the computation of light interactions with a boundary surface of the volume mesh i.e. through material shading. However, displacement of surface portions of the volume mesh during simulation must be propagated to the surface mesh for material shading to account for these surface deformations during the simulation. A process to propagate volumetric changes to a surface has used manual definition of multiple anchor points on a surface mesh to synchronize motion between the volumetric mesh and the surface mesh during simulation. The anchor points propagate changes in position of a surface portion of a volume mesh during simulation to a surface mesh for use shading.

<CIT> discloses solid mechanics simulation of a deformable object having a model representing a condition of the deformable object. A rendering module presents an image of the object in response to states of the elements of the object according to an oriented view. A user interface permits a user to mechanically interact with the model to deform the modeled object. An enhancement is provided that effectively supplies a refined rendering of the set of elements of the object in view, without adding elements to the model, so that the image is of an object defined locally to a higher degree than that of the model.

<CIT> discloses a macroscopic imaging data, such as from a CT, MR, PET, or SPECT scanner. Microscopic imaging data of at least a portion of the same tissue is obtained. To align the microscopic imaging data with the macroscopic imaging data, intermediate data is also obtained. For example, photographic data is acquired at an intermediary stage of a process of preparing tissue for microscopic scan. The macroscopic and microscopic data are registered to the intermediary photographic data. Once registered to the intermediary data, the spatial relationship between the macroscopic and microscopic data is known and may be used for imaging or quantification. <NPL>, explains in part that, viscoelasticity is the property of materials that exhibit both viscous and elastic characteristics under deformation. Elastic materials strain when stretched and quickly return to their original state once the stress is removed. Viscoelastic materials exhibit time-dependent strain. Whereas elasticity is usually the result of bond stretching along crystallographic planes in an ordered solid, viscosity is ordinarily is the result of the diffusion of atoms or molecules inside an amorphous material.

A volume mesh represents a three-dimensional (3D) structure. The volume mesh includes a surface mesh portion. The volume mesh is made up of a multiplicity of polygons that each includes multiple vertices. Some of the vertices are surface vertices within the surface mesh portion and others are internal vertices. The vertices of the volume mesh are arranged in a unified list structure that includes a first sub-list that includes the surface vertices and that includes a second sub-list that includes the internal vertices and follows the first sub-list in the unified list. During shading, only the surface vertices in the first sub-list are accessed. During simulation involving application of virtual force to the volume mesh, both the surface vertices in the first sub-list and the internal vertices in the second sub-list are accessed. These accesses to the unified list use a same base address and at least a count of surface vertices.

Different aspects of the invention provide a data storage and retrieval system, a method, and a computer memory including instructions for performing the method, as defined by the independent claims.

Embodiments of the invention are defined by the dependent claims.

<FIG> is an illustrative drawing representing a simulation and shading system <NUM> in accordance with some embodiments. The system <NUM> includes a scanning system <NUM>, a model creation (synthesis) engine <NUM>, a model simulation engine <NUM>, a conversion system <NUM>, a shader engine <NUM> and a display system <NUM>. The scanning system <NUM> is operative to scan the physical anatomical tissue object <NUM> to produce a three-dimensional (3D) image scan data model <NUM> that includes a three-dimensional image representation of the anatomical tissue object <NUM>. The scanning system <NUM> may be implemented using any of a number of different modalities such as. Computerized Tomography (CT), Magnetic Resonance Imaging (MRI) or Ultrasound techniques, for example. The scanning system <NUM> produces image scan data <NUM> that indicates the physical tissue constituency at discreet three-dimensional volumetric locations within die tissue structure of the anatomical object <NUM>. The model creation engine <NUM> produces a volume mesh structure <NUM>, based upon the 3D image scan data model <NUM>, to represent the physical anatomical tissue object <NUM> during a simulation. The conversion system <NUM> converts the volume mesh representation <NUM> to a unified mesh format (UMF) <NUM><NUM> in which surface vertices and internal vertices of polygons of the volume mesh representation <NUM> are separately grouped. The simulation engine <NUM> simulates application of real physical forces to impart real physical deformation to the real physical anatomical object <NUM>, based upon the UMF representation <NUM> of the object <NUM>, by applying virtual forces to deform a volume mesh representation <NUM>. The shader engine <NUM> produces a (close to) photorealistic visual representation of a deformation of the object <NUM> based upon surface deformation of the volume mesh representation <NUM>, to for display by the display system <NUM>.

<FIG> is an illustrative generalized functional flow diagram representing a data method <NUM> to transform a three-dimensional (3D) image scan data model <NUM> of an object <NUM> to a UMF <NUM> and to use the UMF <NUM> to display an image <NUM> representing deformation of the 3D model <NUM> of the object <NUM>. The method <NUM> may be performed by the system <NUM> of <FIG>. The physical anatomical tissue object <NUM> is provided that may be a human organ such as a kidney, for example. A 3D image scan data model <NUM> is produced that provides a three-dimensional representation of the object <NUM>. The 3D image scan data model <NUM> includes pixel data (pixels) arranged in a voxel grid in which pixels are disposed at voxel vertices. The illustrative diagram of <FIG> shows four example voxels Vx1-Vx4, each with eight vertices, each vertex associated with a pixel value (not shown). A viscoelasticity map <NUM> is produced based upon the 3D image scan data model <NUM> in which viscoelasticity values are associated with three-dimensional locations that correspond to locations within the image data set. The illustrative diagram of <FIG> shows four example viscoelasticity values VE1-VE4, each associated with one of the four example voxels Vx1-Vx4. Each voxel value represents viscoelasticity value for its entire voxel, which is computed based upon values of the eight voxels at the voxel's eight vertices. A volume mesh <NUM> also is produced based upon the 3D image scan data model <NUM> in which vertices of primitive volumetric cells that form the volume mesh are associated with three-dimensional locations that correspond to locations within the image data set. The illustrative diagram of <FIG> shows an example primitive tetrahedral volumetric cell Vci with four vertices (i, j, k, l).

It will be appreciated that because the 3D image scan data model <NUM> is produced based upon the physical object <NUM>, three-dimensional locations within the image scan data model <NUM> correspond to three-dimensional locations within the physical object <NUM>. Moreover, because both the viscoelasticity map <NUM> and the volume mesh <NUM> are produced based upon the image scan data model <NUM>, 3D locations within the viscoelasticity map <NUM>, correspond to 3D locations within the volume mesh <NUM>. Furthermore, 3D locations within the viscoelasticity map <NUM> and corresponding 3D locations within the volume mesh <NUM> correspond to 3D locations within the physical object <NUM>.

A vertex k of the example primitive volumetric cell Vciis disposed at 3D location (xk, yk, zk) within the volume mesh <NUM>, which corresponds to a 3D location (xk', yk', zk') within the viscoelasticity map <NUM>. The location (xk', yk', zk') within the viscoelasticity map <NUM> is nearby to voxels Vx1-Vx4 within the viscoelasticity map <NUM>. A tissue stiffness function determines a viscoelasticity value VEk associated with the 3D location (xk', yk', zk') based upon the viscoelasticity values VE1-VE4 associated with nearby voxels Vx1-Vx4. A sorting function sorts vertices of primitive volumetric cells within the volume mesh <NUM>, including the vertex k of volumetric cell Vci at location (xk, yk, zk), into a UMF structure <NUM> in which surface vertices are grouped separately from internal vertices. The determined viscoelasticity value VEk is stored in association with vertex k of volumetric cell VC1 within the unified (surface and internal) mesh structure <NUM>. Thus, the UMF <NUM> associates volumetric cell vertices with viscoelasticity values, e.g., associates vertex k with volumetric value VEk.

During simulation, a simulation engine <NUM> changes 3D locations of vertices of primitive volumetric cells within the volume mesh <NUM> in response to virtual forces to simulate deformation of the real physical object <NUM> in response to real forces. Simulation, therefore, results in updating of 3D locations of vertices within the UMF <NUM>. A simulation image <NUM> is displayed on a computer display screen <NUM>. A shader engine <NUM> uses color and texture information to produce a more realistic image <NUM> based upon the angle of incidence of light rays within a simulation scene upon vertices disposed at the surface of the volume mesh. The shader engine uses three-dimensional positions of vertices disposed at the surface of the volume mesh <NUM> to determine the vertex positions and orientation relative to light rays. A separate grouping of surface vertices <NUM> and internal vertices <NUM> within the UMF <NUM> makes the surface vertices easily available to the shader engine <NUM> while also making both the surface vertices120S and the internal vertices 120I easily available to the simulation engine <NUM>.

<FIG> are illustrative perspective views of an example primitive tetrahedral volumetric cell that may be included within a volume mesh in a unified mesh format that contains both surface vertices and internal vertices. The tetrahedral cell includes four vertices P0-P3, six edges e0-e5, and includes four faces F0-F3. One of the four faces F0-F3 may be included as a portion of a surface portion of the volume mesh while the remaining three faces are internal to the volume mesh, for example. It will be appreciated that if one of the faces of the example tetrahedral cell forms a portion of the surface mesh, then each of the three vertices of that surface face shares a separate edge with the one remaining other non-surface vertex, which is disposed internal to the volume mesh. <FIG> is an illustrative perspective view of an illustrative example primitive hexahedral cell that may be included within a volume mesh in a unified mesh format that contains both surface vertices and internal vertices. One of the six faces F0-F5 may be included as a portion of the surface mesh while the remaining five faces are internal to the volume mesh, for example. The hexahedral cell includes eight vertices P0-P7, twelve edges, and includes six faces F0-F5.

<FIG> is an illustrative perspective view of an example volume mesh representation of a physical tissue object that includes a plurality of volumetric hexahedral cells. Only a few example hexahedral cells are shown so as to not overcomplicate the drawings and explanation. Each of the example cell shown in <FIG> has one face that acts as a surface mesh portion of the volume mesh. Each volumetric hexahedral cell has eight vertex nodes that are associated with edges to define six faces. For example, a first volumetric hexahedral cell includes vertex vertices (P0, P1, P2, P3, Q0, Q1, Q2, Q3) that define an integral portion of the volume mesh. Vertices (P0, P1, P2, P3), which are a subset of the vertex nodes within first hexahedral cell define a face that forms an integral surface mesh portion of the volume mesh. Internal vertex pairs (P0, Q0), (P1, Q1), (P2, Q2) and (P3, Q3) each defines an internal edge. Thus, the first volumetric hexahedral cell includes both surface vertices and internal vertices. Similarly, for example, a second volumetric hexahedral cell includes vertex vertices (P2, P3, P4, P5, Q2, Q3, Q4, Q5). The second volumetric hexahedral cell includes surface vertices (P2, P3, P4, P5) that define a face that forms an integral surface mesh portion of the volume mesh. Internal vertex pairs (P2, Q2), (P3, Q3), (P4, Q4) and (P5, Q5) each defines an internal edge. Thus, a volume mesh includes primitive volumetric cells that have both surface vertices that define a surface portion of the volume mesh and internal vertices that define an internal portion of the volume mesh.

<FIG> is an illustrative drawing representing certain details of a unified mesh format (UMF) representation of the volume mesh of <FIG>. The unified mesh information structure includes a combined nodes list which contains a first ordered list of surface vertices and a separate second ordered list of internal vertices. In some embodiments, a single list is provided for all nodes, which is sliced into sub-lists: a surface node sub-list and an internal nodes sub-list. To access these lists separately the system provides a base address to the combined list and the count of surface nodes as well as all nodes in the list. An advantage of list with sub-list data structure is that after computing the deformation-related displacements of vertices due to virtual external forces, position/displacement information for all nodes (surface or internal) may be updated. Having all nodes under one overall list improves performance in updating positions/displacements. However only surface nodes need be accessed during shading to apply color or texture to a surface. Co-locating the surface nodes together in a sub-list provides improves access to the surface nodes during shading since they are not comingled with the internal nodes, for example. Co-locating the surface nodes together in a sub-list that precedes a sub-list of internal nodes improves fast access to these nodes since they are at the top of the list, for example.

More specifically, the list of surface vertices and the list of internal vertices are ordered with the surface vertices disposed first, preceding the internal vertices. The surface vertices are accessed more frequently due to the shading procedure. The same base address is used in simulation and rendering and there is no need to compute effective addresses when in rendering procedure. This organization of list and sub-lists is advantageous since, after computing the displacements due to external forces, all nodes (surface or internal) may require updating. Having all nodes under a single list improves the performance since a simulation is typically runs on it device memory and it is more efficient to perform one memory transaction instead of two per cycle.

When applying color or texture to the surface, for example, the system directly accesses the surface nodes only, which is already available at the base address. Moreover, since the frequency of access to the surface nodes generally is higher than that of the internal nodes due to shading computations, it is more efficient to supply the base address to the list and the number of surface nodes so that the same base address is valid for both simulation and rendering procedures. Alternatively, departing from the invention, if internal nodes are placed first in the list then the pointer to the beginning of the surface nodes list is different and should be computed and supplied separately for the rendering procedure.

As explained above, each vertex in the unified mesh format representation of the volume mesh has a three-dimensional location. For example, assume that vertex P0 has location (XP0, YP0, ZP0) and vertex Q0 has location (XQ0, YQ0, ZQ0). Surface vertices P0-P15 are associated with shading parameters, e.g., color (Cn), normal (nn), that are used by the shading engine. All vertices, surface and internal, are associated with viscoelasticity parameters, e.g., mass (Mn), Young's modulus (γn) and Poisson Ratio (on), which are used by the simulation engine.

<FIG> is an illustrative drawing representing a volume mesh data structure stored in a storage memory device to represent a volume mesh in accordance with some embodiments. By way of overview, during simulation, the mass and stiffness properties associated per each vertex are loaded into a simulation engine from a SimulationDataStore. The TopologyDataStore is accessed to extract connectivity information between nodes using edges and the cellular elements (e.g. tetrahedra, hexahedra). Displacements and updates of the current node positions are accessed in the VertexDataStore. By way of further overview, during shading, a shading engine is loaded with per vertex color and normal attributes from a Surface Shading DataStore and with current vertex positions from the VertexDataStore. Surface portions of the mesh are shaded using this information on a graphics processing unit (GPU) component of the shading engine to produce shader output values in a frame buffer is sent for rendering.

More particularly, still referring to <FIG>, in accordance with some embodiments, a fiber in the system is defined as a memory-aligned dynamic array that provides storage for specific mesh attributes e.g. position, normal, color etc. The SurfaceShadingDataStore portion of the volume mesh data structure includes surface shading data such texture coordinates, normal and colors are stored for rendering purposes. The TopologyDataStore portion of the volume mesh data structure includes connectivity information such as edges, faces, and volumetric cells in associated lists of edges, faces, and cells in that order. A VertexDataStore portion of the volume mesh data structure includes current and at-rest three-dimensional locations of all surface vertices and for all internal vertices. A collection of fibers create a structure of arrays that define a specific property of the mesh, e.g. all shading information are defined in the SurfaceShadingDataStore and all mesh connectivity information are stored in the TopologyDataStore. This grouping approach provides a clear definition of the roles per each data store. A mesh-stats portion of the data structure provides additional information about the current mesh, i.e. name and total number of fibers that defines the current mesh, the type of volumetric cells and surface faces used and other associated information such as external transformations, textures and materials for the current mesh. During a simulation time-step the current and rest positions of all nodes are loaded from the VertexDataStore to the simulation engine, other physically-based attributes associated per each vertex are fetched from the SimulationDataStore, such as masses and stiffness properties that define the internal volumetric properties of the mesh. The TopologyDataStore provides the configuration of each volumetric cell e.g. tetrahedral elements and the associated connectivity links between nodes from the edges. Using this information the system computes the internal stress and strains of the volume due to virtual internal and external forces and solves for displacements. The current positions of all nodes may be updated based upon die computed displacements. When the simulation time-step is completed, updated vertex positions and per vertex color and normal properties are supplied from the SurfaceShadingDataStore to the rendering system for shading. Using existing techniques such as Phong shading model, a final color associated per each pixel is determined based upon the configuration of light sources in the scene and the supplied surface properties. See, <NPL>for a discussion of the Phong shading model.

<FIG> are illustrative flow diagrams representing processes to use a volume mesh in a unified mesh format (UMF) during simulation and shading in accordance with some embodiments. Functional blocks of the processes configure one or more computing systems to perform algorithmic processes corresponding to the functions. <FIG> is an illustrative flow diagram representing a set up process <NUM> to set up a computing system to act as a simulation engine <NUM> and to act as a shader engine <NUM> to use a UMF volume mesh in simulation and shading. Functional block <NUM> reads a UMF file <NUM> into a storage memory. Functional block <NUM> initializes mass-stiffness matrices, which involves setting the matrices and filling them with the data stored in a file. Functional block <NUM> initializes a system force model. Functional block <NUM> sets up a system solver.

<FIG> is an illustrative flow diagram representing a simulation process <NUM> based upon a UMF volume mesh in accordance with some embodiments. A computing system configured to act as the simulation engine <NUM> performs the simulation process <NUM>. Functional decision block <NUM> determines whether to continue with simulation. Assuming yes, functional block <NUM> aggregates all external forces upon the UMF volume mesh. Functional block <NUM> applies the external forces to the UMF volume mesh. Functional block <NUM> solves for three-dimensional displacements of vertices within the UMF volume mesh. Functional block <NUM> updates the surface vertices and updates the internal vertices within the UMF volume mesh based upon displacements determined by the solver based upon finite element analysis procedures. See, <NPL>). Control flows to back functional decision block <NUM>, which again determines whether to continue with simulation. It will be appreciated that the simulation cycle that includes functional blocks <NUM>-<NUM> represents application of one time increment of aggregated force upon the UMF volume mesh.

<FIG> is an illustrative flow diagram representing a image rendering process <NUM> based upon a UMF volume mesh in accordance with some embodiments. A computing system configured to act as the shader engine <NUM> performs the image rendering process <NUM>. Functional decision block <NUM> determines whether to continue with shading. Functional block <NUM> fetches updated surface vertex information from the UMF volume mesh. Functional block <NUM> applies shading and texturing based upon fetched vertex locations, colors and normals. Functional block <NUM> produces a frame buffer based upon the shading and texturing information to produce a new frame <NUM> for use to generate an image of the simulated deformation of the volume mesh on a computer display screen. Control flows back to functional decision block block <NUM> determine whether to produces the next frame in the rendering process.

<FIG> is an illustrative flow diagram representing a process <NUM> performed by simulation and shader system <NUM> of <FIG>, in accordance with some embodiments. The simulation and shader system <NUM> is configured to act as a data storage and retrieval system to configure a computer memory storage device, according to a unified mesh format (UMF) representation <NUM> of a volume mesh <NUM>, to represent a physical anatomical tissue object <NUM>. Functional blocks of the process represent configuration of the system <NUM> to perform algorithmic processes to create, a UMF volume mesh <NUM> for use with a computing system configured to act as the simulation engine <NUM> performs the simulation process <NUM>. by the simulation engine <NUM> and the shading engine <NUM>.

A scanning device (e.g., CT, MRI or Ultrasound) <NUM> scans an anatomical tissue object to produce an image scan data set. A scanned image data set within data storage memory block <NUM> represents an image scan data set received from the scanning system that may be stored in a computer readable storage device. The received image scan data includes three-dimensional, i.e. (x, y, z) location based, tissue data that may include image data used by a display system to display a visual image representation of the tissue structure, such as a CT, MRI or Ultrasound image, on a display device, for example. In some embodiments, the three-dimensional tissue data set may be organized according the Digital Imaging and Communications in Medicine (DICOM) image format, which is a standard format for medical images. The tissue data set may include individual pixel values corresponding to individual three-dimensional locations within a tissue structure. Cross-sectional slices through the three-dimensional data set may be used to display cross-sectional image slices of the three-dimensional tissue structure. The image scan data set may include image data such as gray scale information or color information, for example, that is indicative of tissue constituency such as tissue density. Tissue density is indicative of tissue type. Specifically, different gray or color scale values at different three-dimensional locations may indicate different tissue densities or types at those different locations.

A segmenter functional block <NUM> configures a computer system to perform a segmenting process to segment the received image scan data set according to different tissue types represented in the image scan data set. A labeled data set data within memory storage block <NUM> indicates that the segmenting functional block <NUM> produces a labeled image data set that includes label information applied to the original received image data set that may segment the image data set based upon tissue type. The segmenter functional block <NUM> may be operative manually, through machine learning techniques, or through a combination of the two. The received image data set may include grey scale values arranged in patterns that correspond to the tissue structures that they represent. For example, blood vessels and bone tissue structures may have different corresponding gray scale image values and different corresponding three-dimensional shape patterns. A computer system (not shown) used by a segmenter (human operator and/or machine) uses die image data set to display image slices of anatomical object, and the segmenter uses knowledge of anatomy to segment tissue images according to tissue type. More particularly, the segmenter may provide input to a computer user interface to add label information to different portions of the image data set within the labeled data set of memory storage block <NUM> to distinguish different tissue types that may be represented in the image data set so as to segment the image data set according to tissue type. More specifically, the segmenter functional block <NUM> associates label information with three-dimensional locations within the labeled data set of memory storage block <NUM> so as to segment portions of the image data set that are associated with different tissue types. A segmenter may use a combination of gray scale values and shape patterns as a basis to segment tissue data according to tissue type such as tissue data corresponding to blood vessels and tissue data corresponding to bone, for example.

A first process flow segment indicated by dashed lines <NUM>, which encompasses functional blocks <NUM>-<NUM>, produces a viscoelasticity map based upon three-dimensional (3D) image scan data model <NUM>, in accordance with some embodiments. A voxel viscoelasticity determination functional block <NUM> configures the computer system to compute viscoelasticity values for the image scan data set. In some embodiments, the three-dimensional tissue data set may be organized as a voxel grid. More particularly in accordance with the DICOM image format, the image data may include an axis-aligned voxel grid of data samples. Each vertex in the voxel grid is associated with a pixel value. Moreover, in some embodiments, the viscoelasticity values are represented as Hounsfeld unit (HU) values. Each individual pixel value within the three-dimensional tissue data set may have a gray scale value within a numerical range of one to two-hundred fifty-six, for example, that is indicative of the attenuation of X-rays by tissue at die corresponding tissue location, which can be expressed in terms of HUs. Thus, in some embodiments, a voxel is represented as eight pixel values, one pixel value at each of eight vertices. The voxel viscoelasticity determination functional block <NUM> configures the computer system to determine an HU value corresponding to an entire voxel based upon HU values of the pixels at the voxel's vertices. More specifically, an HU value corresponding to an entire voxel may be determined through linear interpolation such as based upon an average of the HU values of the pixels at the voxel's eight vertices. Thus, in some embodiments a three-dimensional location at a center of a voxel within the image scan data set is assigned an HU value computed as an average of the HU values associated with the vertices of the voxel. Voxel viscoelasticity data of memory storage block <NUM> includes a viscoelasticity data set structure that may be stored in a computer readable storage device. Thus, the viscoelasticity data set structure may include individual viscoelasticity values, determined using the functional block <NUM>, that correspond to and that are associated, within the viscoelasticity data set structure, with three-dimensional locations that correspond to individual voxel centers.

A cluster functional block <NUM> configures the computer system to cluster voxel HU value data according to tissue type. Cluster functional block <NUM> superimposes the labeled data set of memory storage block <NUM> with the voxel viscoelasticity data of memory storage block <NUM> to produce a tissue cluster data within memory storage block <NUM> in which tissue viscoelasticity values are clustered based upon tissue type. For example, if the anatomical object is a kidney and the segmenter functional block <NUM> segments the kidney into four tissue segments (e.g., parenchyma, collecting system, arteries and veins), then the tissue cluster data within memory storage block <NUM> includes viscoelasticity values (e.g., per voxel HU values) that are clustered based upon the tissue type that they belong to. Thus, the cluster functional block <NUM> associates three-dimensional locations corresponding to viscoelasticity values in the voxel viscoelasticity data block with three-dimensional locations in the labeled data set of memory storage block <NUM> so as to superimpose the two data sets to indicate boundaries between viscoelasticity values belonging to different tissue types. The tissue cluster data within memory storage block <NUM> also may indicate points of attachment between tissues. For example, in some embodiments, the tissue cluster data within memory storage block <NUM> may indicate the number of voxels disposed between adjacent tissue types and the shortest path between adjacent tissue types. The cluster data indicates anchor points, linkages and paths between different tissue types, which may be used during simulation to indicate transference of forces between adjacent tissues, for example. In some embodiments, the cluster functional block <NUM> produces tissue cluster data organized in a tree data structure that indicates parent and child relationships between different tissue structures, for example.

A mapping functional block <NUM> configures the computer system to produce a three-dimensional viscoelasticity map within memory storage block <NUM> for a tissue type, based upon tissue cluster data within memory storage block <NUM>. The mapping functional block <NUM> configures the computer system to map the tissue viscoelasticity values determined by voxel viscoelasticity determination functional block <NUM> to three-dimensional locations corresponding to a tissue structure type identified by the cluster functional block <NUM>. A separate viscoelasticity map may be created for each identified tissue type. The viscoelasticity map within memory storage block <NUM> includes a data structure that associates viscoelasticity values (e.g., HU values) with three-dimensional locations within the image data set.

The viscoelasticity map of memory storage block <NUM> may act as a tissue viscoelasticity look-up-table (LUT) data structure that indicates tissue viscoelasticity based upon three-dimensional location. The viscoelasticity map acting as a LUT allows for ease or real-time determination of viscoelasticity at different tissue locations. For example, the map may indicate that a tissue portion at a three-dimensional location at a tissue surface has a certain viscoelasticity value, and the map may indicate that a tissue portion at a three-dimensional location tissue location nearer to a tissue core has a different viscoelasticity.

A surface extraction functional block <NUM> configures the computer system to produce a surface mesh structure to store in memory storage block <NUM>, based upon the labeled image data set of memory storage block <NUM>. In some embodiments, a different surface mesh structure is determined for each different tissue type labeled by the segmenter functional block <NUM>. A space partitioning technique such as "marching cubes" may be used to determine voxels within the labeled image data set having faces associated with tissue surfaces. <NPL> describes techniques to determine isosurfaces within an image data set.

Several post-processing steps further refine the surface structures within the memory storage block <NUM> to prepare it for use in producing a volume mesh <NUM>. A watcrtighting functional block <NUM> performs a watertighting process to search for holes in a surface mesh structure within the memory storage block and to patches them to create a solid surface mesh structure. A watertight mesh is one in which all of the surfaces are complete, the lines of the mesh create valid elements suitable for use in simulation, and the mesh properly connects to adjacent surfaces around the surface mesh perimeter so that the volume is fully enclosed. A need for a watertighting during post-processing may arise, for example, because the original image scan data set within memory storage block <NUM> may be missing data for certain portions of tissue structure object or be cut off due to scanning device boundaries or mispositioning of the tissue structure object relative to the scanning system. The watertighting process may generate triangular or quadrilateral patch structures to fill holes based upon extrapolation from the existing surface structure within the memory storage block <NUM>.

A smoothing functional block <NUM> performs a smoothing process to remove artifacts from a surface mesh and to replace them with a smoother more continuous surface pattern. A need for a smoothing during post-processing may arise, for example, because portions of the original image data set within memory storage <NUM> may be blocky or pixilated due to inaccurate or incomplete scan data. As a consequence, the segmenter functional block <NUM> may produce labels that do not accurately represent transitions between different tissue structures. For example, a DICOM image may not have been clear in some area and so the segmenter may simplify and label to indicate an abrupt change from one tissue structure to the next. Because of such inaccurate labeling, the surface extraction functional block <NUM>, in turn, may produce a surface mesh structure that includes artifacts such as a staircase effect in some portions of surface mesh structure, for example. The smoothing functional block <NUM> removes these artifacts from the surface mesh structures.

Pruning functional block <NUM> performs a filter and prune process to reduce the number of vertices in the surface mesh. The filter and prune process may remove overhanging edges such as overhanging edges of a primitive tringle or quadrilateral, for example. The filter and prune process also may reduce the number of primitive structures used to represent a portion of a mesh surface. For example, it may be possible that a large smooth portion of the surface mesh can be represented using a smaller number of larger triangles. Fewer triangles (primitives) means fewer vertices which reduces latency during simulation. Thus, the filter and prune process may reduce the number of triangles used to represent smooth portions of a surface mesh. Functional block <NUM> performs a tetrahedralization process to produce one or more volume mesh structures <NUM> using primitive volumetric cells based upon the post-processed surface mesh structure <NUM>.

A polygonization functional block <NUM> generates internal primitive volumetric cells that collectively create the volume mesh structure within memory storage block <NUM>, which is encompassed by the surface mesh within memory storage block <NUM>. In some embodiments, the primitive volumetric cells include tetrahedral cells. In some embodiments, the primitive volumetric cells include hexahedral cells. The polygonization functional block <NUM> may employ known polygonization methods such as Delaunay triangulations to generate the volume mesh structures <NUM>. A description of polygonization is provided in <NPL>), at pages _-_. The primitive volumetric polygonal cells are used during simulation involving a finite element analysis process to simulate deformation of tissue structure in response to forces applied to the tissue. Each primitive volumetric polygonal structure is associated with multiple vertex nodes and each vertex node is associated with a three-dimensional volume location. A separate volume mesh structure may be produced for each separately labeled tissue type. For example, as mentioned above, kidney includes at least four different tissue types, artery, vein, parenchyma and collecting system. Thus, the segmenter functional block <NUM>, labels original scan data within memory storage block <NUM> that represents a kidney with at least four different labels, each corresponding to a different tissue type. In that case, the polygonization functional block <NUM> produces four separate volume mesh structures that correspond to the four differently labeled portions of the original data set <NUM>.

A second process flow segment indicated by dashed lines <NUM>, which encompasses functional blocks <NUM>-<NUM>, produces the unified mesh format representation <NUM> of the volume mesh <NUM>, in accordance with some embodiments. Sorting functional block <NUM> sorts vertices of primitive volumetric cells within a volume mesh structure into a corresponding first list of surface vertices within memory storage block <NUM> and a corresponding second list of internal vertices within memory storage block <NUM>, which may be stored in a computer readable storage device. The sorting functional block <NUM> implements a sorting process that performs a top-down traversal of the primitive volumetric cells. By way of overview, in a top-down traversal we start from a volumetric cell and then proceed to the faces associated with that cell (<NUM> faces for hexahedra and <NUM> for tetrahedral) and then per each face, the edges associated with that faces are visited. In the end each edge is associated with two end points i.e. nodes. Alternatively, by way of overview, in a bottom-up traversal we start from a node and then visit all adjacent edges to that node. And then per each edge, all adjacent faces to that edges and lastly per each face all adjacent cells to a given face are visited.

More specifically, a sorting process in accordance with some embodiments identifies faces of each primitive volumetric cell. For each identified cell face, sorting process identifies the edges of the cell. Each volumetric cell edge has two endpoint vertices. The sorting process determines for each identified cell face, whether the identified face is associated with more than one volumetric cell. In response to a determination that an identified face is associated with only one volumetric cell, the sorting process determines that the vertex nodes at the endpoints of the edges of the identified face are surface vertex nodes, and the sorting process enters identifiers for these surface vertex nodes in the first list structure, which includes surface vertices stored in the memory storage block <NUM>. In response to the sorting process determining that an identified face is associated with more than one volumetric cell, the sorting process determines that the vertex nodes at the endpoints of the edges of the identified face are internal vertex nodes, and the sorting process enters identifiers for these internal vertex nodes in the second list structure, which includes internal vertices stored in the memory storage block <NUM>.

Merge functional block <NUM> merges the first, surface, list within memory storage block <NUM> and the second, internal, list within memory storage block <NUM> that represent a volume mesh structure corresponding to a tissue type to produce a merged (unified) list structure within memory storage block <NUM>. According to the invention, the unified list structure within memory storage block <NUM> orders the surface vertices in the unified list precede the internal vertices in the unified list. It will be appreciated that surface nodes are accessed more frequently than the internal nodes since surface nodes are passed through both shading and simulation. If the internal nodes are placed first, contrary to the invention, then the pointer to the beginning of the surface nodes list should be computed and supplied separately for the rendering procedure. In case of cutting the volume, new faces and cells may be produced and appended to the list. Then the base address to the surface nodes may be recomputed each time.

Moreover, it will be understood that although the surface and internal vertices are stored separately in first and second lists within the storage memory block <NUM>, they are constituents of the volume mesh produced by the polygonization functional block <NUM>, and that during simulation, virtual forces may be applied to these vertices to cause deformation of the volume mesh to simulate deformation of the physical anatomy object represented by the volume mesh in response to real physical forces.

Shading functional block <NUM> associates color and texture parameter values to surface vertex nodes for use in a shading process performed in the course of a simulation. Shading produces may be employed to produce a more realistic image of a tissue structure based upon its angle to incident light and its distance from incident light. Shading involves altering the appearance of a three-object, based upon its color and texture and its angle with respect to incident light and its distance from the incident light. Shading involving color and texture is described in Fundamentals of Computer Graphics, Supra. , at pages <NUM>-<NUM> and at pages <NUM>-<NUM>.

A vertex viscoelasticity determination functional block <NUM> determines viscoelasticity values for surface and internal vertices within the unified list within memory storage block <NUM>. More specifically, each node of the unified list in block <NUM> is associated with a three-dimensional (x, y, z) location. For each three-dimensional location of a vertex node in the unified list <NUM>, the functional block <NUM> determines a corresponding viscoelasticity value based upon the map in memory storage block <NUM>.

The vertex viscoelasticity determination functional block <NUM> configures the computer system to use the viscoelasticity map of memory storage block <NUM> as a LUT to determine tissue viscoelasticity values to associate with three-dimensional locations of vertices within a volume mesh representation of a tissue object based upon viscoelasticity values at corresponding three-dimensional locations within a scanned image data set obtained for the tissue object. The functional block <NUM> implements a data driven viscoelasticity determination function in which a three-dimensional (x, y, z) tissue location is received as an input value and a scalar value representing tissue viscoelasticity at the received location is provided as an output value. The scalar value may include a Young's modulus in terms of stiffness, for example. The vertex viscoelasticity determination functional block <NUM> accesses the viscoelasticity map of memory storage block <NUM>, which acts as a LUT, to produce a three-dimensional tissue location based viscoelasticity value in response to a received three-dimensional input location.

In some embodiments, the vertex viscoelasticity determination functional block <NUM> determines a viscoelasticity value to associate with a three-dimensional location input location by interpolating between average voxel values associated with three-dimensional locations nearby to the received three-dimensional input location. More particularly, in some embodiments, functional block <NUM> interpolates a viscoelasticity value to return in response to a received three-dimensional input location based upon viscoelasticity values associated with a prescribed number of viscoelasticity values associated with three-dimensional locations closest to the received three-dimensional input location.

Thus, for each surface vertex and for each internal vertex within the unified list, the functional block <NUM> uses a three-dimensional location associated with the vertex in the volume mesh as an input location. The functional block determines a corresponding value within the viscoelasticity map of memory storage block <NUM>. Determining the corresponding value may involve interpolation between multiple viscoelasticity values associated with three-dimensional locations in die viscoelasticity map that are nearby to the input location. For each surface vertex and for each internal vertex, the functional block <NUM> stores a corresponding determined viscoelasticity value in the unified mesh within memory storage <NUM> in association with the vertex to which it pertains.

<FIG> shows an illustrative diagrammatic representation of a machine in the example form of a computer system <NUM> within which a set of instructions is included, for causing the machine to perform any one or more of the methodologies discussed herein. In alternative embodiments, the machine operates as a standalone device or may be connected (e.g., networked) to other machines. In a networked deployment, the machine may operate in the capacity of a server or a client machine in server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine may be a server computer, a client computer, a personal computer (PC), for example. Further, while only a single machine is illustrated, the term "machine" shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

The example computer system <NUM> includes a processor <NUM> (e.g., a central processing unit (CPU), a graphics processing unit (GPU), or both), a main memory <NUM> and a static memory <NUM>, which communicate with each other via a bus <NUM>. The computer system <NUM> may further include a display screen <NUM> of a display device <NUM> (e.g., liquid crystal display (LCD), organic light emitting diode (OLED), touch screen, or a cathode ray tube (CRT)). The computer system <NUM> also includes one or more user input devices to receive user input commands. The user interface input devices of the illustrative system include an alphanumeric input device <NUM> (e.g., a physical or virtual keyboard), a cursor control device <NUM> (e.g., a mouse, a touch screen, a touchpad, a trackball, a trackpad), a nontransitory storage device <NUM>, a signal generation device <NUM> (e.g., a speaker) one or more data interfaces <NUM> including an interface to a network interface device <NUM>. The data interfaces <NUM> may be wired or wireless to send and receive information such as motion picture camera image information or network information, for example.

The storage device <NUM> includes a machine-readable medium <NUM> on which is stored one or more sets of instructions <NUM> (e.g., software) data structures <NUM> (e.g., an index structure) embodying any one or more of the methodologies or functions described herein. The processor <NUM> may be configured according to instructions <NUM> in the machine-readable medium to act as a synthesis system <NUM>, to act as a UMF conversion system <NUM>, to act as a simulation engine <NUM> and to act as a shader engine <NUM>. The machine-readable medium <NUM> also may store 3D) image scan data model <NUM>, a volume mesh representation <NUM>, and a UMF representation <NUM>. The storage device may include one or more of a disk drive, solid-state memories, optical and magnetic media, for example. The instructions <NUM> may also reside, completely or at least partially, within the main memory <NUM> and/or within the processor <NUM> during execution thereof by the computer system <NUM>, the main memory <NUM> and the processor <NUM> also constituting machine-readable media. The instructions <NUM>, data structures <NUM> and motion picture pixel frames <NUM>, <NUM> may further be transmitted or received over the network <NUM> via the network interface device <NUM>.

Claim 1:
A data storage and retrieval system for a computer memory comprising:
a viscoelasticity map (<NUM>) that associates viscoelasticity values (VEK, VE1-VE4) with three-dimensional, 3D, locations;
a volume mesh structure (<NUM>, <NUM>, <NUM>) that represent a 3D model that includes volumetric cells (VC1) that include surface vertices (P0-P15) that correspond to 3D locations that are associated with viscoelasticity (VEK, VE1-VE4) values by the viscoelasticity map and include internal vertices (Q0-Q15) that correspond to 3D locations that are associated with viscoelasticity values (VEK, VE1-VE4) by the viscoelasticity map;
sorting means (<NUM>) for sorting the surface vertices (P0-P15) and internal vertices (Q0-Q15) of the volume mesh structure (<NUM>, <NUM>, <NUM>) to configure said memory according to a unified mesh structure that associates volumetric cell vertices with viscoelasticity values (VEK, VE1-VE4), said unified mesh structure including:
a first list (<NUM>) within a unified list, the first list including the 3D locations of the surface vertices (P0-P15) of the volume mesh structure; and
a second list (<NUM>) following the first list within the unified list, the second list including the 3D locations of the internal vertices (Q0-Q15) of the volume mesh structure, and
wherein to access the first list and second list within the unified list, a same base address to the unified list and at least a count of surface vertices is used when simulating deformation and rendering colour or texture.