System and method for volume rendering of finite element models

• US 5,570,460 A
• Filed: 10/21/1994
• Issued: 10/29/1996
• Est. Priority Date: 10/21/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ramanujam, Gopalan
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): BUCHEL JR, RUDOLPH JOHN
• Application Number:
  US08/327,337
• Time in Patent Office: 739 Days
• Field of Search: 395/124, 364/413.14, 364/413.19
• US Class Current: 345/424
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

The present invention converts an unstructured grid of finite volume data to a rectangular grid of voxel definitions for use by a volume rendering technique operable on such a rectangular grid of voxel definitions. The unstructured finite element grid is sliced using a slicing process generating intersection polygons at scalar data at polygon vertices. This vertex scalar data is then mapped to shades of a color based on a linear mapping function. A linear interpolation is then utilized to generate a rectangular two dimensional array, for each slicing interval, which is dependent upon a pixel resolution of the display device utilized within the data processing system implementing the present invention. Each pixel represents a three-dimensional point in the viewing coordinate space wherein each pixel represents a voxel corner. The color of each pixel is used to determine the scalar value to be associated with each voxel corner. This created rectilinear grid of voxel definitions is then utilized within a volume rendering process operable on data associated with rectangular grids.

Claims

1. A method of converting an unstructured finite element grid to a grid of voxel data, said grid of voxel data to be displayed on a display device, said method comprising the steps of:

inputting data representing said unstructured finite element grid, wherein said unstructured finite element grid represents a three-dimensional object;

performing a plurality of slicing operations upon said unstructured finite element grid in a viewing direction;

generating, during each slicing operation, intersection polygons with scalar data at polygon vertices;

mapping, during each slicing operation, each of said scalar data to shades of a color;

generating, during each slicing operation, a two-dimensional array of pixel colors from said shades of a color; and

reading back said two-dimensional array of pixel colors from a frame buffer such that each pixel represents a three dimensional point voxel corner.

2. The method as recited in claim 1, further comprising the step of:

transforming, during each slicing operation, said two-dimensional array of pixel colors to generate x, y, z viewing coordinate points and vertex data.

3. The method as recited in claim 2, further comprises the steps of:

performing a volume rendering process upon the x, y, Z coordinate points to produce an object;

and displaying the object.

4. The method as recited in claim 1, wherein said mapping step further comprising utilizing a linear mapping function to map each of said scalar data.

5. A method comprising the steps of:

inputting representative data of an unstructured finite grid element, wherein said unstructured finite element grid represent an object in three-dimensional space;

generating intersection polygons with scalar data at polygon vertices from said representative data;

generating two-dimensional array of pixel colors from said intersection polygons;

reading the two-dimensional array of pixel colors from a frame buffer, such that each pixel represents a voxel corner;

transforming said two-dimensional array of pixel colors into a rectilinear grid of voxel data; and

inputting said rectilinear grid of voxel data into a volume rendering process for subsequent display of the object.

6. A volume rendering system comprising:

means for inputting data representing an unstructured finite element grid, wherein said data representing said unstructured finite element grid represent an object in three-dimensional space;

means for performing a plurality of slicing operations upon said unstructured finite element grid, wherein slices of said unstructured finite element grid are parallel to each other and perpendicular to a direction of viewing of said object;

means for generating, during each slicing operation, intersection polygons with scalar data at polygon vertices;

means for linearly mapping, during each slicing operation, each of said scalar data to a shade of a color;

means for generating, during each slicing operation, a rectangular array of data points by linear interpolation of said color shades associated with said polygon vertices, wherein said rectangular array is dependent on a pixel resolution of a display device;

means for reading, for each slicing operation, said rectangular array of data points from a frame buffer such that each pixel represents a voxel corner;

means for inputting said rectangular array of data points into a volume rendering process capable of handling said rectangular array of data points; and

means for displaying said object as a result of said volume rendering process using said rectangular array of data points.

7. A data processing system, comprising:

an input device for inputting data representing an unstructured finite element grid, wherein said data representing said unstructured finite element grid represents an object in three-dimensional space;

a processor, coupled to said input device by a bus, said processor performs a pre-processing algorithm upon said data representing said unstructured finite element grid to produce a rectilinear grid of voxel data, said processor inputting said rectilinear grid of voxel data into a volume rendering process capable of handling said rectilinear grid of voxel data;

a storage device, coupled to said processor and said input device via said bus, for storing said data representing said unstructured finite element grid, said pre-processing algorithm, and said rectilinear grid of voxel data, wherein said storage device includes, for storing said pre-processing algorithm,;

first storage means for storing program instructions that cause said processor to generate intersection polygons with scalar data at polygon vertices from said data representing said unstructured finite grid element;

second storage means for storing program instructions that cause said processor to generate two-dimensional array of pixel colors from said intersection polygons;

third storage means for storing program instructions that cause said processor to read said two-dimensional array of pixel colors from a frame buffer, such that each pixel represents a voxel corner;

fourth storage means for storing program instructions that cause said processor to transform said two-dimensional array of pixel colors into said rectilinear grid of voxel data; and

a display device, coupled to said processor, said storage device, and said input device via said bus, for displaying said object as a result of said volume rendering process using said rectilinear grid of voxel data.

8. A volume rendering system comprising:

means for inputting data representing an unstructured finite dement grid;

means for performing a plurality of slicing operations upon said unstructured finite element grid;

means for generating, during each slicing operation, intersection polygons with scalar data at polygon vertices;

means for mapping, during each slicing operation, each of said scalar data to a range of an attribute thereby producing mapped data;

means for mapping, during each slicing operation, the mapped data from a frame buffer such that each pixel represents a voxel corner; and

means for inputting said mapped data into a volume rendering process, wherein said volume rendering process includes a means for blending, for each pixel, color and opacity accumulated from said each slicing interval.

9. The system as recited in claim 8, wherein color blending, for each pixel, is performed according to the following function:

space="preserve" listing-type="equation">C.sub.r =C.sub.c +MIN(1-A.sub.c, A.sub.i) * C.sub.i

and wherein opacity blending, for each pixel, is performed according to the following function;

space="preserve" listing-type="equation">A.sub.r =A.sub.c +MIN(1-A.sub.c, A.sub.i)

wherein C denotes said color, A denotes said opacity, c denotes a current frame buffer content for said color or said opacity, i denotes an incoming new color or opacity, r denotes a result of said blending, and MIN is a minimum function returning the smallest of its two arguments.