US 6,144,383 A · Volumetric data organization method that allows for cache efficient rendering speedups and efficient graphics hardware design

Abstract

A volumetric data organization method for volume rendering that is both cache efficient and efficient for hardware graphics design and utilization. A volume data set is divided up into a number of smaller sub-volumes or blocks through a process called blocking. The size of each sub-volume is a function of the computer system being used and/or the application program being run. Typical sub-volume sizes are approximately 5% of cache size. Each voxel tuple in a volume data set is converted to a linear address for linear storage in memory. Two techniques are used for blocking: overlapping and non-overlapping. The non-overlapping blocking technique divides the volume data set up into sub-volumes such that each sub-volume contains a unique set of voxels with no overlap of voxels between sub-volumes. The overlapping blocking technique expands each sub-volume to include voxels located on six planes that are located one voxel away from the sub-volume's existing bounding planes. After employing either technique, each sub-volume can be selected as containing desired or non-desired data. The volume rendering system ignores any sub-volumes that do not contain desired data, greatly speeding up rendering time.

Claims12

Dependent claims

A cache efficient volumetric data organization method for rendering a volume data set on a 2D graphics display of a computer system, said method comprising the steps of:

(a) retrieving said volume data set from a storage medium;
(b) selecting an entire sub-volume from said volume data set, wherein said selecting further comprises the steps of
(b1) selecting said sub-volume of said volume data set wherein said sub-volume has six faces;
and
(b2) including within said sub-volume a group of additional voxels immediately surrounding said sub-volume to create an expanded sub-volume, said group of additional voxels being contained on a group of six planes, one of each of said group of six planes being parallel to a corresponding one of each of said six faces of said sub-volume, and further wherein one of each of said group of six planes is located adjacent to said corresponding one of each of said six faces of said sub-volume and in a direction away from a center of said sub-volume;
(c) converting each address of a voxel tuple of said entire sub-volume to a linear address;
(d) processing said entire sub-volume through a volume rendering system, and
(e) repeating steps (b) through (d) for each sub-volume of said volume data set.

5 more elements

A cache efficient volumetric data organization method for rendering a volume data set on a 2D graphics display of a computer system, said method comprising the steps of:

(a) retrieving said volume data set from a storage medium;
(b) dividing said volume data set into a plurality of sub-volumes wherein each of said plurality of sub-volumes contains a unique set of voxels, and wherein said dividing further comprises
(b1) dividing said volume data set into said plurality of sub-volumes wherein each of said plurality of sub-volumes has six faces, and further wherein each of said plurality of sub-volumes that is adjacent to another of said plurality of sub-volumes share one of said six faces at each occurrence of adjacency, and
(b2) including within each of said plurality of sub-volumes a group of additional voxels immediately surrounding each of said plurality of sub-volumes to create a plurality of expanded sub-volumes, each of said group of additional voxels for each of said plurality of sub-volumes being contained on a group of six planes, one plane of each of said group of six planes being parallel to one of each of said six faces of one of each of said plurality of sub-volumes, and further wherein one plane of each of said group of six planes is located adjacent to one of each of said six faces of each of said plurality of sub-volumes and in a direction away from a center of one of each of said plurality of sub-volumes;
(c) converting each address of a voxel tuple of each of said plurality of sub-volumes to a linear address;
(d) processing each of said sub-volumes through a volume rendering system, wherein each sub-volume is processed in its entirety before processing is started on a subsequent sub-volume.

3 more elements

Dependencies are inferred from the claim text.

Volumetric data organization method that allows for cache efficient rendering speedups and efficient graphics hardware design

Life of this patent

Volumetric data organization method that allows for cache efficient rendering speedups and efficient graphics hardware design

Life of this patent

Abstract

Claims12