Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Utility Patent
1997-06-13
2001-01-02
Brier, Jeffery (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S421000
Utility Patent
active
06169551
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data visualization processing, and in particular to a method for assigning or converting a volume data value which is defined at a cell center to volume data values at node points of the cell in such a manner that a residual value becomes as small as possible.
2. Description of the Related Art
Currently, it is presupposed by the majority of existing data visualization algorithms, that the volume data value is defined on each node point of a volume cell. For example, the Marching Cubes Algorithm by Lorensen and Cline examines each volume cell and determines, from the arrangement of nodal points with data values above or below a given threshold value, what the topology of an isosurface passing through the volume cell would be. See Lorensen, W., and Cline, H. E., “Marching Cubes: A High Resolution 3-D Surface Construction Algorithm,” Computer Graphics, Vol. 21, No. 4, 1987. Mathematics of Computation, Vol. 38, No. 157, pp. 181-199. When calculating a streamline, vector data values are interpolated by using nodal data values within an element. See Haimes, R., Giles, M., and Darmofal, D., “Visual 3-D Software Environment for Flow Visualization,” VKI Lecture Series on Computer Graphics and Flow Visualization on CFD, 1991.
However, some numerical simulation algorithms define their variables at the centers of the volume cells. In order to apply the visualization algorithms indicated above, currently the data at the centers of the volume cells have to be converted into data at the volume cell's node points by one of the following methods. That is, the Inverse-Weighted Method proposed by Shepard (see Franke, R., “Scattered Data Interpolation: Tests of Some Methods,” Mathematics of Computation, Vol. 38, No. 157, pp. 181-199.) or an extrapolation technique (see Vankeirsbilck, P. and Decomink, H., “Higher Order Upwind Finite Volume Schemes with ENO-properties for General Unstructured Meshes,” AGRAD Report 787, 1992).
In the former, the data value S
i
point
at the i-th node point is given by the following expression:
S
i
point
=
∑
c
i
cell
S
cell
×
W
cell
∑
c
i
cell
W
cell
[
Expression
9
]
where, S
cell
means a data value at the center of the cell, W
cell
means an inverse value of a distance between the node point and the center of the cell, and
∑
c
i
cell
means a summation with respect to volume cells that share the node point i.
The latter technique is based on a gradient vector ∇S
cell
estimated at the center of an element, and S
i
point
is given as follows:
S
i
point
=S
cell
+({right arrow over (D)},∇
S
cell
) [Expression 10]
where the parenthesis of the second item in the above expression means an inner product, and the vector D represents a vector from the center of a cell to a node point. In addition, ∇S
cell
means a gradient of the scalar function S
cell
. When extrapolating from the center of the cell to the node points, different values for each node will be generated from each of the volume cells that share that node point. The usual approach in this situation is to average the contribution from each volume cell to generate a single value.
In general, the data space spanned by the resulting data at the node points is different from one spanned by the original data at the center of the cell. The above techniques do not consider any residual due to the difference.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore one object of the present invention to provide a method for assigning volume data values, defined at the center of the cells, to node points, considering the residuals.
It is another object of the present invention to provide a method for assigning volume data values defined at the center of the cells, to node points so that the following integral is made smaller.
∫
V
k
(
∑
i
=
0
n
-
1
S
i
point
×
N
i
(
u
,
v
,
w
)
-
S
k
cell
)
ⅆ
v
[Expression 11]
where N
i
(u,v,w) is an interpolating function for a node point i, S
k
cell
is a volume data value at the center of the cell k, and the integral is performed over the whole cell k.
According to the present invention, a method is utilized for computing volume data values at a plurality of node points from volume data at each center of a plurality of cells which are composed of the plurality of node points, wherein the position and the ID of each node point are stored in a memory with relation to each of the corresponding node points. The volume data value at each node point is computed so that a value determined by (a) weighting a residual value which is the difference between a cell-inside value at a point inside a cell and a volume data value at the center of the cell by a predetermined weighting function, where the cell-inside value is calculated by interpolating a volume data value at each node point which composes the cell, and then (b) accumulating the weighted residual value over all regions of each of all the cells and (c) setting the sum of the accumulations to zero. By selecting an appropriate weighting function, an assignment in which the residual is small becomes possible.
According to another embodiment of the present invention, there is a method for computing volume data values at a plurality of node points from a volume data value at each center of a plurality of cells which are composed of the plurality of node points, wherein the position and the ID of each node point are stored in a memory with relation to each of the corresponding node points. S
i
point
, which is a volume data value at a node point i which composes a cell k of a plurality of cells which share a node point j, is computed so that, with respect to all node points j, the expression,
∑
C
j
cell
(
∫
V
k
M
j
(
u
,
v
,
w
)
R
k
(
u
,
v
,
w
)
ⅆ
v
)
=
0
[Expression 12]
is satisfied, where C
j
cell
means all cells which share the node point j, and M
j
(u,v,w) is a predetermined weighting function corresponding to the node point j, and N
i
(u,v,w) is a predetermined interpolating function at a point (u,v,w) inside the cell which corresponds to the node point i, and S
k
cell
is a volume data value at the center of the cell k, and a residual value R
k
(u,v,w) is the difference between S
k
cell
and the result of summing the product of S
i
point
and N
i
(u,v,w) with respect to all node points which compose the cell k.
According to still another embodiment of the present invention, there is a method for computing volume data values at a plurality of node points from a volume data value at each center of a plurality of cells which are composed of the plurality of node points and for visualizing the computed volume data values, wherein the position and the ID of each node point are stored in a memory with relation to each of the corresponding node points, the method including the steps of: computing S
i
point
which is a volume data value at a node point i which composes a cell k of a plurality of cells which share a node point j such that, with respect to all node points j, the expression,
∑
C
j
cell
(
∫
V
k
M
j
(
u
,
v
,
w
)
R
k
(
u
,
v
,
w
)
ⅆ
v
)
=
0
[Expression 13]
is satisfied, where C
j
cell
means all cells which share the node point j, and M
j
(u,v,w) is a predetermined weighting function corresponding to the node point j, and N
i
(u,v,w) is a predetermined interpolating function at a point (u,v,w) inside the cell which corresponds to the node point i, and S
k
cell
is a volume data value at the center of the cell k, and a residual value R
k
(u,v,w) is the difference between S
k
cell
and the result of summing the product of S
i
point
and N
i
(u,v,w) with respect to all node points which compose the cell k; and performing a visualization process for the computed S
i
point
and displaying the result of the processing.
According to still another embodiment of the present invention, there is a method for
Brier Jeffery
Clay A. Bruce
Felsman Bradley Vaden Gunter & Dillon, LLP
Harrison Chante E.
International Business Machines - Corporation
LandOfFree
Method and apparatus for computing and visualizing volume... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for computing and visualizing volume..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for computing and visualizing volume... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544179