JPH036786A - Method and device for drawing volume body to computer graphic display unit - Google Patents

Abstract

PURPOSE: To make it possible to mutually act the volume data with the geometric data without losing the resolution of volume by using geometric elemental components mapping the volume and depicting the volume. CONSTITUTION: This device is provided with a computer 1, an input device 5, a large capacity storage 6 and a display monitor 7, and the volume to be depicted are lined up to the geometric elemental components, and a mapping function relating the geometric elemental components to the volume is generated. The mapping function relates respective voxels in the volume space to elements of the elemental components, that is, points. Thereby, the volume is displayed as the function of the geometric elemental components mapping the volume. Thus, geometric operation such as the clipping or the rotation are performed easily for the elemental components, and further, since the raw volume data are depicted directly 10 the geometric space, they are mutually acted easily with the geometric data.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to the field of computer graphics, and more particularly to displaying volume objects on a computer display.

[Conventional technology]

Volume data is represented by a three-dimensional array of volume elements called voxels (ox*1). Each voxel has three integer coordinates representing its location in volume space and a certain It is combined with at least one integer value, called the density, representing a property, such as temperature or composition, which is not directly related to the descriptive attribute. Geometric data, on the other hand, are
It is represented by a y, z coordinate position and a descriptive attribute such as color.

Unlike volumetric data, geometric data is easily rendered for display purposes. The reason is that geometric data provides the necessary descriptive information to display geometric techniques. Volume data includes information related to the volume object itself.

Therefore, in order to display volume data, the volume data must be translated from the volume space into a format that is compatible with the space of the display device. There are basically two techniques for representing volumes on computer graphics display devices: geometric techniques and volumetric techniques. In geometric techniques, volume data is fitted to geometric elementary components. The geometric elementary components yield a model that includes those elementary components. In volumetric techniques, volumes are directly depicted using reprojection or optical projection techniques.

``Optimal Surface Reconstruction Four Tube Flaner Contours'' by Fuchs
struet for Planar Cont.
ours) J CACM 20 (1977) describes a method for describing surfaces contained in volume data by reconstructing a three-dimensional surface from a set of contours drawn on serial slices through the volume. A geometric algorithm is described. Their contours are generally obtained using semi-automatic edging following routines. The contours are then filled in using geometric elementary elements such as batches of triangles, polygons or bi-cubies. Those geometric elementary components form a three-dimensional polygonal model. These models can be drawn using conventional techniques. A similar technique for surface reconstruction is described in US Pat. No. 4,729,098. However, extraction of surface contours often requires operator intervention.

Requires a large number of polygons to preserve detail. Ninth, since the volume data is now represented only by the volume's surface data, the raw volume data is lost and partial surfaces or objects cannot be displayed.

The Cuberll method was developed as a result of efforts to preserve surface detail at the voxel level (Gordon, Image Space Shading of 3-Dimensional Objects, Computer Urn Vision Graphics). Su & Ken Image Society Prosets'/7g (rmag
e 5pace Shading of 3-D1m@
n51onal Dbjset+ Compatar
Vlalon Graphlc@and Image
Processing ) 29 + 377-393
(1985)'). This technique constructs a binary volume that is compressed to efficiently delineate surface boundaries. Voxel faces are depicted as shaded polygons. This technique cannot depict translucent or partial surfaces. Marching Cubes
Another geometric algorithm known as Voxel Cubes calculates the intersection of a surface and a voxel cube, yielding triangles that provide a very detailed surface approximation. sick rough 198
7 Glossy Deings (Slggraph) 198
7 (Proceedings) (July 1987)
, pp. 163-169, "Marching Cubes: A High-Resolution 3-D?-Face Number Construction Clear Algorithm, Computer
Graphics (M&rehjng Cubes:
A HlIrh Re5solution 3-DSur
face construction A1gorlt
See the article by Lawreneon et al. entitled hm+ Computsr Graphics) J. ) - layer details are provided by the split cube algorithm. The algorithm represents the boundary as a set of points. Mezoica A/11 Physics (Medi
cal Physles) June 1988 issue.
Two Algorithms Battle for the Record/Structural/Of e-Surface from Society Tomogram (Tw
o Algorithm For Th@Raeon
gtruetlon of SurfaeeFrom
Tomograms) Klein (CIi) entitled J.
ns) et al. and U.S. Pat. No. 4,719,585.

Those methods perform surface extraction of the volume, but the raw volume data is not maintained. Therefore, no further interaction with the raw volume data is possible since only volume surface information is maintained. Thus, functions such as partial volumes, transparency, and interactions with the volume such as picking (i.e. reading data values from or writing data values from the volume), and geometry onto the volume. Imposition of scientific objects cannot be carried out.

In compositing techniques, volume data is preprocessed by classifying each voxel according to four different descriptive attributes, such as color, opacity, and texture, thereby creating multiple volume representations. The various volume representations are then combined to form a single volume representation for rendering on the display device. Drebin et al., [Volume Rendering, Computer Graphics Syllagraph Procedures (Vol.
m@Randerlng, Computer Gra
phlcs Siggraph Pr.

(August 1988), 65-74
Page and IEEE-Kai Computer Graphics and Applications (IEEEBCom)
putsr Graphics and Applic
ations (May 1988), ``Display of 5 surfaces from e-data'' (May 1988).
mVolum@Data) and US Pat. No. 4,737,921. but,
This technology does not have a continuous mapping function. Therefore, if the output image to be rendered is much larger than the original volume data, large aliasing (all
aslng ) i (happen.

Light projection is a simple method for direct voxel delineation. Written by Roth [Raycasting for
Modeling Solutions, Computer Graphics and Image Processing (Rayaamt)
ing For Modeling 5olltj.

Campar Grapblcm and
18'', 109
~144 pages, Computer Graphics Silagraph 1988 Proceedings (Comput@r
Graphies Slggraph 198B Pr
oceedings ) (August 1988) 51-5
“A Rendering Fist Algorithm 7” on page 5
Visualizing, 3-D, Scaler Fields (A Randerlng Algorithm)
For Vfgualfzlng3-D 5eale
r Fleldg) J.
V-Buff Visible Volume Rendering (V-Buff.r Visible Volume Rendering), published in the Computer Graphics Silagram 1988 Proceedings, pp. 59-64.
me Rand@rlng)
pson) Please refer to other papers. In light projection techniques, light rays are transmitted through a volume and emitted to each pixel along a visual vector. The values determined along the rays are combined into one value and displayed on a display device. Numerous algorithms have been developed to determine the output rendered by a beam of light. For example, an additive recast algorithm produces an x-ray-like image by averaging the brightness of volume points along the ray. Another reprojection technique assigns color and transparency to density ranges so that the volume appears as a composite of transparent gel (Proceeding
s of th@NCGA) March 1986 issue, ``3-Dimensional Display of Medical Image Volume Points''
onal Display of Medicml I
(See the paper by Schluasslberg et al. entitled "Mage Volumes" J).

Previously published computer graphics syllabus 19
84 Proceedings, pp. 165-173, “Ray Tracing - Volume Densities (Ra
ytraefng Volume Densities
The paper by Kjlya et al., entitled ) J, describes true ray tracing in which a large number of additional rays are generated at surface boundaries in order to calculate surface-to-surface reflection properties. However, in practice, ray tracing is not used because it requires extensive calculations and a large amount of cost. In long plane projection techniques, one or more planes are moved through the volume and mapped to a coloring function to display specific density values. However, this technique, like ray projection, is cumbersome, requires a lot of calculations, and requires additional rendering for each perspective.

[Problem to be solved by the invention]

It is therefore an object of the invention to obtain a method and a device for representing a volume using its primitive components.

Another object of the present invention is to provide a method and apparatus for depicting a volume that includes geometric elementary components mapped to the volume.

Yet another object of the invention is to obtain a method and apparatus for depicting a volume that allows the volume to interact with geometric objects.

[Means to solve the problem]

In the method and apparatus of the present invention, direct depiction of the volume from the volume data provides a means by which volume resolution is not lost and the volume data fully interacts with the geometric data.

The volume to be described, or a portion thereof, is aligned to the geometrical elements and a mapping function is generated that associates the geometrical elements to the volumes or volume portions. The mapping function relates each voxel in the volume space to an elementary component element or point. In this way, the volume is displayed as a function of the geometric component to which the volume portion is mapped.

In a preferred embodiment, the volume or volume portion to be depicted is limited by one or more geometrical elements, and the geometrical elements, such as three-dimensional polygons, are associated with the volume. Matuping occurs. Then, any geometric operations performed on the volume operate on the geometric elementary components and are performed using a mapping function to translate the volume into geometric space. The volume data will be displayed. Preferably, the polygon surrounding the volume is a cube, such as a normalized nine cube, with vertices ranging from -1 to +1.

By defining a volume as a function of a geometric elementary component such as a polygon, geometric operations such as clipping or rotation can be easily performed on the elementary components, and mapping functions can be used. The data is used to determine the corresponding volume data to be displayed. Furthermore, because the raw volumetric data is directly depicted in geometric space, geometric data can be easily interacted with the raw volumetric data.

Notation and Terminology The detailed description that follows is primarily of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the art to most effectively convey the substance of their work to others skilled in the art.

Here, an algorithm is defined as a self-consistent sequence of steps leading to a desired result. The steps require physical manipulations of physical quantities. Usually, but not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise processed. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. However, all such terms and similar terms should be related to appropriate physics;
And it should be remembered that these terms are only convenient labels applied to these quantities.

Furthermore, the operations performed are often referred to with terms such as addition or comparison. Their processing is generally associated with mental work performed by the operator. In most cases, such capabilities of the operator are not required in any of the operations described herein, which form part of the present invention! te is undesirable. The operation is the operation of the machine. Useful devices for carrying out the operations of the present invention include general purpose digital computers or other similar devices. In all cases, one should remember the difference between the operation of the method of operating the computer and the calculation method itself. The present invention relates to a method for operating a computer in the processing of electrical and other (eg, mechanical, chemical) physical signals to generate other desired physical signals.

The invention also relates to apparatus for performing those operations. The apparatus may be specially constructed for the purpose sought or may include a general purpose computer that can be selectively activated or reconfigured by a computer program stored on the computer.

The algorithms presented herein are not inherently related to any particular computer or other apparatus. It will soon become apparent that a variety of general-purpose machines can be used with programs written in accordance with the teachings of this specification, or it may be more convenient to construct more specialized equipment to carry out the required method. It's clear.

〔Example〕

General Structure of the Apparatus FIG. 1 shows a typical computer-based apparatus for displaying volume data on a Conview 11 display apparatus in accordance with the present invention. In this figure, a computer 1 is shown having three main parts. First, the inputs/outputs (Ilo) used to communicate information in an appropriately configured form with other parts of the computer 1.
There is circuit 2.

Also shown in FIG. 4 as components of the computer 1 are a central processing unit (CPU) 3 and a memory 4.

The latter two components are typically found in most general-purpose computers and almost all special-purpose computers. Indeed, several of the components included in computer 1 are intended to represent this broad category of data processors.

Particular examples of suitable data processing equipment to serve as computer 1 include the Sun Mlerosyst, Mountain View, California, USA.
emm+ Inc.). Other computers with similar capabilities could of course be used in a linear fashion to perform the functions described below.

An input device 5 is also shown in FIG. In this figure, the input device 5 is shown as a keyboard.

However, the input device 5 may actually be a card reader, a magnetic tape reader, a paper tape reader, or other similar well-known input devices (of course, a separate computer, or a computerized data acquisition device such as a computerized tomography device). equipment included).

A mass storage device 6 is coupled to the I10 circuit 2 to provide additional storage capacity for the computer 1. This mass storage device may contain other programs, etc., and may take the form of magnetic tape, paper tape, or other well-known forms. It will be appreciated that the data held in the mass storage device 6 may be included in the computer 1 in a standard manner as part of the memory 4, if appropriate.

A display monitor 7 is also shown for displaying messages and other communications to the user. The display monitor can take the form of any of several well-known CRT displays. The display monitor T is a high-resolution computer screen display capable of displaying volumetric images rendered according to the method of the invention. A cursor control 8 is used to select command modes and edit input data, such as font dimensions. This cursor control provides a more convenient means of entering information into the computer.

Overview of the Method In the method and apparatus of the present invention, a volume object or a portion of a volume object is aligned with one or more geometric elementary elements, and the geometric element in a geometric space is aligned with one or more geometric elementary elements. A mapping function between the volume object and the volume object in the volume space is generated. The use of mapping functions, transformations, inspections, and other geometric operations is as simple as performing geometric operations on the geometric constituents to which the volume is mapped and interpreting the corresponding volume data. , can be executed against a volume.

Volumetric data, ie, voxels representing a volumetric object containing attributes of the volume at a particular location within the volumetric space, is stored in memory according to the position of each voxel within a three-dimensional play of voxels representing the volumetrical object. In order to represent a volumetric object, the volumetric object is described in terms of at least one geometric element, such as a cube. The geometrical elements used should be sized and aligned such that the volume to be described can be mapped to a portion of the volume to the elemental element. The geometrical elements used are preferably normalized to simplify subsequent operations that can be performed, such as scaling, moving or rotating the image.

For example, with reference to FIG.
A portion of the volume representing the can be mapped into a geometric vector and displayed in screen space.

Once the vector is mapped, the volume vector can be mapped and moved in the geometric space simply by performing rotation/translation operations on the geometric vector and using the mapping function to find the corresponding volume element. Can be easily rotated and moved.

This is particularly useful in curved surface extraction techniques that use volume vector elementary components. In the ninth parable, referring to Figures 3 to 3C, the volume object can represent at least one of human tissue and organs. In this case, the volume includes capillaries 100 located throughout the volume. It may be desirable to extract the exact path or exact shape of a capillary through a tissue and/or organ representing a volume. This is done 9 by mapping the volume vector 110 to a geometric vector at a point 120 along a curved surface, e.g. a capillary. Once mapping is done, the geometric vectors can be rotated and the corresponding volumetric data mapped so that from various perspective positions, for example, the perspective view shown in Figure 3c, a display showing capillaries can be created. Depict.

The volume is mapped into one or more elementary geometric components that form a three-dimensional object, such as a cube. The cubes are arranged so that the cube encloses the volume. As shown in FIG. 4z, the volume object 150 is surrounded by a cube 160. A mapping function is generated between the volume and the voxel containing the (X 17 r 1 ) coordinate of the cube. Once the mapping function is generated, various geometric operations can be applied to the volume object through operations performed on the cube.

For example, by clipping cube 160, a portion 175 of volume 170 can be removed and an image of the resulting volume easily displayed as shown in Figure 4b.

The mapping function is based on each voxel of some volume object, also called volume space - (U, V + W) space,
(X, 7.g) Gives the mathematical correspondence between the vertices, or lattice points, of geometric elementary constituents in the space (geometric space). A volume object can be said to be "fitted" to a geometric elementary component such that the boundaries of the volume are mapped to the boundaries of the geometric elementary component.

In this way, the mapping function maps the voxel locations stored in memory to a particular

Connect to the y, z coordinate position. The mapping function used can be of any order.

Zero-order and mapping functions can be used such that each voxel is mapped to the nearest vertex in geometric space. For example, if the dimensions of the volume are (10x20x
30) and is mapped to a normalized cube with vertices between -1 and 1, a voxel at position in play (1,1,1) will be mapped to coordinate position (0,0,0). mapped to the vertices of a cube, array (10, 20, 30
) The voxel at the position is the coordinate position (1, 1, 1)
mapped to a vertex in . Position in volume space (
Vertices between 1°1.1) and (10,20,30) are mapped to the nearest vertex, resulting in a value calculated using dimensional proportionality calculations between volume space and geometric space. In this example, the number of vertices in U is equal to 10,
Since the number of vertices in X is equal to 2 (-1 to 1),
The ratio of U to X is equal to FilO to 2.

Therefore, for the mapping function zvxuy15
-1.

This function can also be a linear function, also called a trilinear function. In a trilinear function, a weighted average calculation is performed on the eight closest vertices in geometric space to determine the position of the vertex of the volume in geometric space. The use of the -order function has a smoothing effect, thereby minimizing the amount of aliasing that occurs when volumetric data is mapped. Refer now to FIG. Vertex 200 is mapped to the enclosing cube by determining the closest eight vertices in the geometric space, denoted vertices a, b, e+d+e+f+g+Il. Then, the coordinate position of the voxel is determined according to the following equation.

X= (CCa *FRACT(u)+ (1-FRA
CT($b)☆FRACT(v)-1-(c☆FR
AC hole u)+-(1-FRACT(u)-&d) (
1-+'RACT(c))☆FRACT←Crazy(・☆FR
ACT(u)) +(1-FRACT(u))☆p)☆
FRACT(v)−+−(g☆FRACT(u))+(
1-mc'r(u))☆n)☆(1-F'RAC'r(
c))☆(1-+″RACT←)) Here, X is the voxel 20 at location (u, ma, v) K in the volume space.
Geometric position of 0, & + b + e + d, @
+ f r g + b is the 8 corners of the cube surrounding the volume coordinates to be determined (X + 7 + Z
) coordinate position, FRACT This is a function that indicates the decimal part of the U coordinate.

Once the mapping function is determined, the modification or processing of the geometric operations performed on the geometric object can be
This can be done for volumetric objects via the geometric elementary components to which the volume is mapped. To achieve various viewing dimensions and aspect ratios or perspective of volumetric data, transformations are multiplied to the IJ lux geometric element. Therefore, the transformation map) IJ lux modifies the volume data mapped to the geometric elementary components.

Also, the elementary constituent elements of the volume are defined.

The elementary components of a volume, such as point vectors, polygons or rays, have definitions in the volume space and in the geometric space according to the mapping performed. So, for example, a point is in {x, y, z) space and (
u, v, w) has one location in space and the vector is (
X + 7 + Z) space and (u.

m, v) have two points in space that define the starting and ending points of the vector. Similarly, a polygon has points in (X + 7 + ”) space and in (u, ma, w) space that bound the polygon. A ray has points in (U,
We have one point in the (X + 7 + 'L) space that maps multiple points in the (X + 7 + 'L) space. These elementary components can be used to add to volumes and data, and to draw from or otherwise interact with volume data.

For example, to expose the internal surface of a volume,
Elementary components can be used to slice a portion of a volume. This is shown in Figures 4& and 4b. In those figures, polygons are used to slice away portions of the volume to expose the inner surface of the volume. Elementary components can also be used to generate geometric images that interact with volumes within volumetric space. In this case, the effect can be displayed.

This is particularly useful in medical radiation therapy, where a physician can observe the interaction of a vertical or laser beam formed using elementary components generated within a volumetric space with human tissue. A more realistic image is obtained because the geometric image interacts with the raw volume data and not with the volume's surface extraction data.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a ninth computer device for rendering volumetric data on a computer display; FIG. 2 illustrates the mapping of volumetric elements in volumetric space to elements in geometric space; and FIG. 3a. , 3b and 3c illustrate the application of a preferred embodiment of the present invention, 4a and 4b illustrate the mapping and display of a volume enclosed by a geometric cube, and 5. A trilinear mapping function is shown. 16...computer, 2-...engineering circuit, 3φ・
...CPU, 4 @...-Memo IJ, 5...Fist input device, 6...Mass storage device, γ...-Display monitor.

Claims (4)

[Claims] (1) represents at least a part of a volumetric object, (u, v
, w) storing in memory volume data represented in volume space; and at least one geometric coordinate representing a pixel on a computer graphics display device;
configuring at least one geometric graphics elementary component represented in a coordinate space to correspond to the volume object; aligning the volume data to the geometric graphics elementary components; generating a mapping function that maps the volume data to the geometric coordinates of the geometric graphics element to which the volume data is mapped; A method of depicting a volumetric object on a computer graphics display device, the method comprising displaying volumetric data at coordinate locations. (2) represents at least a part of the volume object, (u, v
, w) storing in memory volumetric data represented in volumetric space; and the process of configuring at least one geometric graphics elementary component that is represented in a geometric space and that limits a volumetric object in three dimensions; generating a mapping function that maps to the geometric coordinates of the element, thereby displaying the volume data at the geometric coordinate position of the geometric graphics element to which the volume data is mapped. A method for representing volumetric objects on a computer graphics display device featuring features. (3) represents at least a part of the volume object, (u, v
, w) means for storing volumetric data represented in a volumetric space in a memory; and at least one geometric coordinate representing a pixel on a computer graphics display;
means for configuring at least one geometric graphics element represented in a coordinate space to correspond to a volumetric object; and means for aligning the volumetric data to the geometric graphics element; means for generating a mapping function that maps the volume data to the geometric coordinates of the geometric graphics element, whereby the volume data is mapped to the geometric coordinates of the geometric graphics element; A device for depicting a volume object on a computer graphics display device, characterized in that volume data is displayed at coordinate positions. (4) represents at least a part of the volume object, (u, v
, w) means for storing in memory volume data represented in volume space; and means for configuring at least one geometrical graphics elementary component represented in a geometrical space and surrounding a volumetric object in three dimensions; and a geometrical graphics elementary component confining each volumetric data to the volumetric object. means for generating a mapping function that maps the volume data to the geometric coordinates of the geometric coordinates of the geometric element, whereby the volume data is displayed at the geometric coordinate position of the geometric graphics element to which the volume data is mapped. A device for depicting a volumetric object on a computer graphics display device.