Hewlett-packard Company

Barthold Lichtenbelt

Hasan Shahzad Naqvi

Tom Malzbender

Shaz Naqvi

Russell Huonder

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.

Volumetric data organization method that allows for cache efficient

A volumetric pre-clipping method that guarantees only a minimal number of sample points along rays that pass through a volume data set will need to be processed by a volume rendering system. Pre-clipping is a two step process. First, a projection of the volume is made onto an image plane based on the orthographic or perspective view desired. Each bounding vertex of the volume data set is multiplied by the appropriate transformation matrix to transform the vertices from source space to view space. The transformed vertices establish on the view space image plane the projection outline of the volume data set. By definition, only rays cast from pixels on the image plane within this projection outline will pass through the volume data set. Pixels outside the projection outline do not need to be considered. Rays and pixels in view space are transformed back to source space by multiplication with the appropriate inverse transformation matrix for an orthographic or perspective view. Second, for each ray that passes through the volume data set, the entrance point into the volume data set and the exit point out of the volume data set are calculated. Only the sample points along a ray that fall between the entrance and exit points need to be processed by the volume rendering system in order to render the image.

Volumetric pre-clipping method that guarantees minimal number of sample

A ray transform method for performing 3D spacial volume transformation for perspective view rendering of a volume data set on a 2D graphics display. A backward mapping approach is used whereby each destination point along a ray is transformed and resampled from the source. The rays converge at the center of projection, or the eye pont, from the projection plane for the perspective view desired. Each ray has a unique ray transform matrix which is combined with an orthographic model view matrix to yield a combined inverse matrix. The floating point values of the combined inverse matrix are coded into a 32 bit fixed point format having 16 bits of scalar and 16 bits of fraction. Once this coding has been done, then transforming consecutive points along a destination ray becomes simple integer adds. The method supports two resampling techniques, nearest neighbor and trilinear interpolation.

Growing community of inventors

Ft. Collins, CO, United States of America

Barthold Lichtenbelt