Brick-based fusion renderer

• US 7,961,186 B2
• Filed: 05/24/2007
• Issued: 06/14/2011
• Est. Priority Date: 09/26/2005
• Status: Active Grant

• Current Assignee: Siemens Healthineers AG (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Li, Wei
• Primary Examiner(s): Hajnik; Daniel F
• Application Number:
  US11/753,092
• Publication Number:
  US 20070247459A1
• Time in Patent Office: 1,482 Days
• Field of Search: None
• US Class Current: 345/424
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

A method for combining at image data sets to generate a composite image. The method divides each of the data sets into a plurality of bricks along three mutually orthogonal axes. The method includes (a) building a hierarchical structure for each one of the at least two data sets, each structure comprising higher level blocks of voxels and lower level blocks of voxels, the higher level blocks having a larger number of voxels than the lower level blocks; (b) expanding boundaries of each one of the structures into corresponding expanded hierarchical structures, such boundary expanding comprising adding additional virtual processing bricks to the initial processing bricks, such virtual processing bricks comprising semi-unbounded blocks to provide the expanded boundaries of the expanded hierarchical structures; and (c) rendering each one of the bricks in each one of the expanded hierarchical structures into a two dimension image.

Claims

1. A method for combining at least two unregistered three-dimensional (3D) image data sets to generate a composite image from the data sets, comprising:

dividing each of the data sets into a plurality of bricks along three mutually orthogonal axes, wherein each brick is further subdivided into a plurality of blocks along the three mutually orthogonal axes;

merging the blocks into a hierarchical tree structure for each of the at least two data sets, with each block being a leaf node and a root of each tree structure being a union of all blocks that correspond to the data set;

expanding, using a computing device, one tree to cover a full space of the at least two 3D image data sets by adding an expanded root that covers all image data sets, and by adding internal expanded nodes for the other tree structures, wherein each expanded node has one or more boundary faces defined at infinity; and

traversing the expanded tree top down from the root to render the expanded data set, wherein each brick of an image data set volume is tested with all bricks of other image data sets whether they overlap, wherein if a common region exists, rendering is performed.

2. The method of claim 1, further comprising:

dividing each of the data sets into stacks of parallel slices and sorting the slices by visibility order, wherein each block of each brick is rendered slice-by-slice skipping invisible blocks, wherein if a current brick of a data set is invisible, the brick is not sliced.

3. The method of claim 1, wherein rendering is restricted to a common region of current active bricks, defined by inserting cut-planes onto faces of the bricks, expanded nodes and visible, unexpanded intermediate nodes are used to apply cut-planes that divide the image data sets into regions, wherein a region defined by a set of cut planes of an image data set contains at most one brick of the same image data set, and wherein cut-planes between visible and invisible bricks are ignored for bricks that fall completely outside of a view port, and a cut-plane between an empty brick in a middle of the stack and a neighboring non-empty brick is removed.

4. The method of claim 3, further comprising, when an invisible block can be skipped, searching for a largest node that satisfies a criteria for rendering, and skipping all child nodes of that node.

5. The method of claim 4, wherein a criterion for rendering a node is that the node is not fully clipped by cut-planes, and that its percentage of visible voxels is greater than a predetermined number.

6. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for combining at least two unregistered three-dimensional (3D) image data sets to generate a composite image from the data sets, comprising:

dividing each of the data sets into a plurality of bricks along three mutually orthogonal axes, wherein each brick is further subdivided into a plurality of blocks along the three mutually orthogonal axes;

merging the blocks into a hierarchical tree structure for each of the at least two data sets, with each block being a leaf node and a root of each tree structure being a union of all blocks that correspond to the data set;

expanding one tree to cover a full space of the at least two 3D image data sets by adding an expanded root that covers all image data sets, and by adding internal expanded nodes for the other tree structures, wherein each expanded node has one or more boundary faces defined at infinity; and

traversing the expanded tree top down from the root to render the expanded data set, wherein each brick of an image data set volume is tested with all bricks of other image data sets whether they overlap, wherein if a common region exists, rendering is performed.

7. The computer readable program storage device of claim 6, the method further comprising:

dividing each of the data sets into stacks of parallel slices and sorting the slices by visibility order, wherein each block of each brick is rendered slice-by-slice skipping invisible blocks, wherein if a current brick of a data set is invisible, the brick is not sliced.

8. The computer readable program storage device of claim 6, wherein rendering is restricted to a common region of current active bricks, defined by inserting cut-planes onto faces of the bricks, expanded nodes and visible, unexpanded intermediate nodes are used to apply cut-planes that divide the image data sets into regions, wherein a region defined by a set of cut planes of an image data set contains at most one brick of the same image data set, and wherein cut-planes between visible and invisible bricks are ignored for bricks that fall completely outside of a view port, and a cut-plane between an empty brick in a middle of the stack and a neighboring non-empty brick is removed.

9. The computer readable program storage device of claim 8, the method further comprising, when an invisible block can be skipped, searching for a largest node that satisfies a criteria for rendering, and skipping all child nodes of that node.

10. The computer readable program storage device of claim 8, wherein a criterion for rendering a node is that the node is not fully clipped by cut-planes, and that its percentage of visible voxels is greater than a predetermined number.