Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-02-17
2003-02-18
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06522324
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method of deriving an iso-surface in a multi-dimensional data field, in which
the data field assigns data values to positions in a multi-dimensional space, and
data values in positions on the iso-surface are substantially equal to a predetermined iso-value,
the method including the following steps:
deriving a binary shell of one or more lattice cells from a sampled data field, which sampled data field assigns sampled data values to lattice positions on a discrete multi-dimensional lattice in conformity with a sampling of the data field, and
in which individual lattice cells in the binary shell comprise at least one lattice position with a sampled data value larger than or equal to the iso-value and at least one lattice position with a sampled data value smaller than or equal to the iso-value.
2. Description of Related Art
The determination of iso-surfaces is of importance for a variety of applications, notably for the visual reproduction of a data field. Such a data field contains, for example density values or flow data, and is, for example, hydrodynamic or meteorological data flow data, or seismic or medical diagnostic density values. Iso-furfaces are formed by positions in the multi-dimensional space in which the data values of the data field have substantially the same value which is equal to the iso-value. It will be evident that individual iso-values correspond to individual iso-surfaces. It has been found that representations of relevant iso-surfaces constitute a useful tool for acquiring a visual perception of the structure of a data field. It is particularly when the data field has a complex structure, involving complex spatial variations of data values, that different iso-surfaces offer a suitable perception of the relevant data field.
A method of this kind is known from United States patent U.S. Pat. No. 5,517,602.
The known method derives a piece-wise polygonal approximation of the iso-surface from the data field. The polygonal approximation constitutes a polyhedron whose side faces extend through lattice positions of the discrete multi-dimensional lattice on which the data field is sampled. Consequently, the approximating polygon constitutes merely an accurate approximation of the exact iso-surface along edges of the lattice. It is to be noted that the known method produces only a rather coarse approximation of the iso-surface
SUMMARY OF THE INVENTION
It is an object of the invention to provide a method of deriving an isosurface in a multi-dimensional data field which enables the iso-surface to be derived significantly more accurately in comparison with the known method. It is also an object of the invention to provide a method of this kind which requires only a comparatively short computation time for deriving the iso-surface, even if severe accuracy requirements are imposed as regards the deriving of the iso-surface.
This object is achieved by means of a method of deriving an iso-surface in a multi-dimensional data field according to the invention which is characterized in that the method also includes the following steps:
selecting a line of sight in the multi-dimensional space,
determining a current lattice cell in the binary shell wherethrough the line of sight extends, and
deriving an edge point on the line of sight and in the current lattice cell, the data value in the edge point being substantially equal to the iso-value.
The edge point on the line of sight constitutes an accurate approximation of the point of intersection of the iso-surface and the line of sight. The position of the edge point can be derived from the sampled data values in the current lattice cell and possibly neighboring lattice cells by means of comparatively simple calculations. Because these calculations are simple, they can be performed quickly and with a high accuracy. The edge points indicates where along the line of sight the iso-surface is reached. By using the invention with a plurality of lines of sight, if desired, respective edge points are derived which are all accurately situated on the iso-surface. The iso-surface can be determined with an accuracy which is higher as the number of edge points determined on respective lines of sight is greater. When lines of sight with individual directions are used, a perception can be obtained as to how the iso-surface is reached from different directions. The iso-surface can thus be observed as if it were from different points of view.
The calculations for deriving the edge point (or edge points) are performed only for lattice cells in the binary shell. Thus, it is avoided that futile calculations are performed so as to find an edge point in lattice cells which are not traversed by the iso-surface. Thus, no time is wasted on futile calculations and the calculation time required for deriving the iso-surface remains comparatively short, even when the iso-surface has a complex topological structure.
In order to determine the edge points in respective lattice cells in the binary shell, preferably such an order of traversing the binary shell is used that the search for edge points which are obscured from view is avoided. Such a situation occurs, for example when the iso-surface constitutes the boundary of a non-transparent object.
Furthermore, prior to the calculation of the position of the edge point, on the basis of the binary shell it can be determined which lines of sight intersect the iso-surface. To this end, a projection of the binary shell or a contour of the projection of the binary shell is derived from a preselected projection direction. Subsequently, extreme directions which have a point of tangency with the projections are derived. Lines of sight having directions outside the range of these extreme directions do not have a point of intersection with the iso-surface. Thus, when looking along a line of sight having a direction outside the range of said extreme directions, one actually looks past the iso-surface. When respective projections of the binary shell are derived for a plurality of preselected projection directions and when it is determined for which directions lines of sight are tangent to the relevant projection, the unnecessary and futile calculation of edges points for lines of sight which do not intersect the iso-surface will be avoided to a significant degree. It has been found that the calculation time required is reduced to only ⅙ or {fraction (1/7)} part of the calculation time which would be required when the fact that the relevant line of sight does or does not intersect the iso-surface is not taken into account.
Using the method according to the invention, for example iso-surfaces relating to the cerebral cortex and to blood vessels within the brain, respectively, have been derived from a sampled data field of 256×256×151 density values of the brain of a patient to be examined which have been measured by means of magnetic resonance. In order to derive these iso-surfaces with 600×600 points by means of a SunSparc 5 workstation, approximately 1-2 seconds of calculation time are required. Using a faster workstation, such as an UltraSparc workstation, a calculation time of no more than a few tenths of a second to approximately one half second will be required to derive these iso-surfaces.
The method according to the invention can be applied to an arbitrary data field which is, for example continuous in respect of position and value (i.e. an analog data field) by sampling the data field so as to derive the sampled data field from the data field. The method according to the invention can also be applied to an already sampled data field or, when the data field has been obtained with an unsuitable sampling, the data field can be sampled again and the invention can be applied to the resampled data field. Moreover, the method according to the invention can be applied to a modified version of the data field. For example, such a modified version of the data field contains a part of the original data field which is of s
Bosma Marco K.
Smit Jacob
Koninklijke Philips Electronics , N.V.
Sealey Lance W.
Vodopia John
LandOfFree
Deriving an iso-surface in a multi-dimensional data field does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deriving an iso-surface in a multi-dimensional data field, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deriving an iso-surface in a multi-dimensional data field will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3181985