Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-08-21
2003-02-25
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000, C345S424000
Reexamination Certificate
active
06525729
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the display of three-dimensional image data sets, and in particular to raycasting.
BACKGROUND OF THE INVENTION
Volumetric data sets are usually viewed by being projected unto a two dimensional surface. Two main types of projection systems are used: an orthographic projection, and a perspective projection. In a perspective projection, a single viewpoint is assumed, from which rays emanate and strike the surface. In an orthographic projection, these rays are all perpendicular to a common plane.
Some methods of rendering a volumetric data set onto a two dimensional surface utilize a z-buffer. The values in the z-buffer are equal to the length of rays from the projection point (plane) to the surface. One method of generating the z-buffer, namely raycasting, is applied by following a plurality of rays from their source (point or plane) until they terminate at a solid voxel. Once a z-buffer is generated, the voxels are projected unto the z-buffer and lighting calculations are made, using well known methods, such as described in “Computer Graphics Principles and Practice, Second Edition in C”, by James D. Foley, et al., Addison-Wesly, 1996, the disclosure of which is incorporated herein by reference.
The data set is typically a binary data set, at least for the purposes of raycasting. The value of each voxel is generally assumed to be a discrete sample of a continues spatial function at the center of that voxel. Thus, it is necessary to perform some type of interpolation to determine whether the ray is passing through a transparent voxel or has reached a boundary voxel. Unfortunately, high quality interpolations are generally slow. In addition, some high quality interpolations are not smooth. For example, a long series of values . . . 010101010 . . . will usually not be interpolated as a fixed value 0.5. Generally, some of the waviness of the data will remain after the interpolation, resulting in a wavy interpolation. This is in conflict with the general desire that the z-buffer should not contain frequencies of the order of one over a voxel dimension, because these frequencies are mainly artifacts caused by the limited spatial sampling of the volume.
Cubic interpolations are generally determined using four data points and four constraints. Two sets of constraints, known in the art are:
(1) y(x
n
)=y
n
; for n=1 . . . 4, where x
n
and y
n
are known and where x is between x
2
and x
3
; and
(2) y(x
2
)=y
2
, y(x
3
)=y
3
, y′(x
2
)=(y
3
−y
1
)/(x
3
−x
1
) and y′(x
3
)=(y
4
−y
2
)/(x
4
−x
2
)
SUMMARY OF THE INVENTION
It is an object of some embodiments of the present invention to provide a method of ray-casting a voxel data set in which only a required accuracy of values for elements in a z-buffer is achieved. Preferably, the required accuracy is locally determined based on variations in the voxel data set. In one preferred embodiment of the invention, a reduced accuracy of determination of intersections between rays and solid voxels, i.e. the length of the rays, is allowed. Alternatively or additionally, reduced spatial resolution of the z-buffer is allowed, resulting in a less accurate value for the true distance between individual solid voxels and the view origin. Alternatively or additionally, a less accurate interpolation of data is allowed.
It is an object of some embodiments of the present invention, to provide a fast method of cubic interpolation, which is especially suitable for raycasting, but is also useful for other applications, especially those requiring smoothing of data.
It is an object of some preferred embodiments of the present invention, to provide a method of raycasting, in which the spacing of the rays is dependent on a surface variation of the voxel data. In a preferred embodiment of the invention, the method is applied to an image having a plurality of areas having low-contrast features, separated by sharp boundaries. Such images are typical of some types of medical images, where the act of segmentation creates sharp boundaries. Preferably, the spacing of the rays is decreased at the sharp boundaries and increased at the low-detail areas, thereby being adapted to the required accuracy of raycasting.
It is an object of some preferred embodiments of the present invention, to provide a method of raycasting in which the accuracy of determining the length of each ray is dependent on the surface variation.
It is another object of some preferred embodiments of the present invention to provide a method of raycasting, in which the length of a ray is iteratively determined.
It is another object of some preferred embodiments of the present invention to provide a method of raycasting, wherein the type of data interpolation used is adapted to the instant accuracy at which the ray is cast.
It is an object of some preferred embodiments of the invention, to provide a method of cubic interpolation which smoothes out the data, e.g., it smoothes a sequence such as . . . 0101010101010 . . . , without leaving a residual ripple.
In accordance with a preferred embodiment of the present invention, a method of raycasting comprises casting rays in multiple spacing resolutions, starting at a coarse (large) spacing. Rays are added between rays of a previous step, depending on the gradient of data in the z-buffer. If the gradient is small, the z-buffer value is determined by interpolation, rather than by casting a new ray. In a preferred embodiment of the invention, the large spacing casting is applied to a reduced-resolution version of the data set, preferably into a low resolution z-buffer. Preferably, previously cast rays are re-cast, when the resolution of the z-buffer is increased. Preferably, the previously determined z-values are used as a starting point for the search for the solid voxel boundary-ray intersection location, in the finer spacing. Alternatively the raycasting is applied to the fill resolution data set, even in the coarser spacing levels, so that the determined intersection location has a maximal accuracy. Preferably the coarsest spacing level is selected responsive to a statistical property of the data set.
In some preferred embodiments of the invention, externally provided information is used to determine the spacing of the cast rays, at the start of the casting and/or at the end of the casting and/or locally. In one preferred embodiment of the invention, information regarding the clinical interest of a portion of the data is available. Areas which are of more clinical interest are preferably ray cast with a smaller initial inter-ray spacing and/or a lower gradient threshold. In one preferred embodiment of the invention, areas of clinical interest are automatically identified by registering the data set with a previously interpreted data set in which areas of interest are indicated.
In a preferred embodiment of the invention, the inter-ray spacing and/or the gradient threshold and/or other factors which affect the accuracy of the raycasting are dependent on the ray length and/or on the angle between the ray and the voxel surface and/or on the relative location of the ray in the field of view. Preferably, a highest image quality is desired for voxels which are nearer the center of the field of view and within a certain range of distances from the viewing origin. Preferably, this higher image quality is attained by increasing the accuracy of determination of the z-buffer for these voxels. In a preferred embodiment of the invention, a user may enter parameters which define the required accuracy and/or relative image quality for voxels at different distances, angles and/or surface angles.
In accordance with a preferred embodiment of the present invention, additionally or alternatively to coarse ray-spacing, a reduced accuracy of ray length determination is allowed. In a preferred embodiment of the invention, the intersection between the ray and a voxel is searched for, other than by sequentially tracing along the ray. In one preferred emb
Akerman Shmuel
Miller Gad
Algotec Systems Ltd.
Fenster & Company Patent Attorneys Ltd.
LandOfFree
Raycasting system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Raycasting system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Raycasting system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3156213