Fuzzy inference system for simplifying mesh

Details Fuzzy inference system for simplifying mesh Fuzzy inference system for simplifying mesh

2000-12-19

2004-06-15

Davis, George B. (Department: 2121)

Data processing: artificial intelligence

Fuzzy logic hardware

Fuzzy inference processing

C706S047000

Reexamination Certificate

active

06751599

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method for simplifying mesh. More particularly, the present invention relates to a fuzzy inference system capable of simplifying meshes in computer graphics by integrating variances of mesh attributes and estimating the cost of removing a portion of data.
2. Description of Related Art
Conventional mesh simplification techniques can be roughly divided into two types, namely, edge collapsing and vertex decimation.
FIG. 1
is an illustration showing the working principles behind the conventional edge collapsing method for simplifying mesh. As shown in
FIG. 1
, vertices(v
t
, v
s
) on the left side of the figure is chosen to be the edge collapsing vertices. After collapsing the edge between the vertice(v
t
, v
s
), only a single vertex v
s′
is left. Hence, one vertex is eliminated and the triangles represented by the vertices(v
t
, v
l
, v
s
) and (v
t
, v
s
, v
r
) are removed. Meanwhile, five edges including v
t
v
s
, v
t
v
l
, v
t
v
r
, v
r
v
s
, v
s
v
l
originally on the left is reduced to just two edges, namely, v
l
v
s′
and v
s′
v
r
.
FIG. 2
is an illustration showing the working principles behind the conventional vertex decimation method for simplifying meshes. In the vertex decimation method, vertices are classified according to the geometry of its neighboring triangles. As shown in
FIG. 2
, vertices of secondary importance are removed (for example, v
m
) and the ‘hole’ so created is again triangulated (to form triangles A
1
, A
2
and A
3
). With such processing, the vertex v
m
on the left side of the figure is eliminated so that the original five triangles B
1
, B
2
, B
3
, B
4
, B
5
are reduced to just three triangles A
1
, A
2
and A
3
. Meanwhile, the five edges v
m
v
s
, v
m
v
t
, v
m
v
u
, v
m
v
v
, v
m
v
w
on the left side of the figure are reduced to just two edges v
s
v
u
and v
s
v
v
on the right side of the figure.
In the two aforementioned methods, a lower resolution mesh is generated from a high resolution mesh. However, in the process of removing data (collapsing edges or decimating vertices), judging the importance of various attributes of the mesh and putting up a weight for each attribute is often very difficult. This process frequently leads to visual distortion of the mesh. In some cases, if the data chosen for removal is actually important, fundamental characteristics or external appearance may be changed or else the degree of simplification is quite limited. Hence, the method of picking up not-so-relevant data for deletion is a critical issue.
In general, the edge collapsing method shown in
FIG. 1
is suitable mostly for geometric treatment with due consideration to the cost resulting from positional change. Other factors such as curvature change in neighboring triangles and color change are mostly ignored. As for the vertex decimation method shown in
FIG. 2
, the method is limited to applications on a curve surface. For a three-dimensional mesh, deletion of vertices will be very difficult. In addition, any sharp cornered section or important section must be heavily weighted. Hence, if there is no unified scheme for weighing the attributes of a particular mesh, the simplification process may lead to serious warping.
Since most mesh simplification techniques estimate the cost of removing part of the data by considering some of the attributes only, major visual effects, characteristics and external appearance of a mesh are only partially considered. Moreover, no definite rules can be found to measure the cost of the removed attributes. For example, length or distance between the desired-to-remove data positions can be used to estimate positional variation. Similarly, change in the desired-to-remove normal data can be used to measure curvature variation and difference between the desired-to-remove color data can be used to compute color variation. The three attributes need to be integrated and balanced so that a final cost for removing part of the data can be obtained. Due to the absence of definite rules or standards, attributes are often poorly integrated leading to the destruction of fundamental characteristics and the restriction of mesh simplification.
SUMMARY OF THE INVENTION
Accordingly, one object of the present invention is to provide a method of using a fuzzy inference system to simplify meshes in computer graphics. A fuzzy inference system is used to integrate all possible attributes, and then the cost of eliminating the desired-to-remove data is estimated. Thereafter, the attributes are integrated to obtain a balance so that a final cost for the desired-to-remove data is determined. The final cost serves as a criteria for simplifying the mesh. Hence, after the mesh is simplified, all the good characteristics and visual appearance are retained. The method is suitable for progressive meshing. The method can be applied to multiresolution modeling rendering such as virtual reality, multimedia, computer graphics, three-dimensional games and progressive transmission within a network.
To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention provides a method of using a fuzzy inference system to simplify meshes. First, m attributes are selected for a particular mesh. Variation of each attribute m
i
is characterized by n
1
fuzzy sets, where 1≦i≦m. According to a fuzzy inference rule, variation of m attributes and the corresponding n
i
fuzzy sets, n
1
.n
2
. . . n
m
different combinations are formed. Using a first function, n
1
.n
2
. . . n
m
weights is computed from the n
1
.n
2
. . . n
m
different combinations. According to the fuzzy inference rule, variation of the m attributes is next computed using a second function to obtain n
1
.n
2
. . . n
m
output values. Finally, according to the n
1
.n
2
. . . n
m
weights and the n
1
.n
2
. . . n
m
output values estimated cost is obtained by computation using a third function. The estimated cost serves as a parameter for removing data when simplifying the mesh.
The TSK fuzzy inference system can be used as the fuzzy inference rule. The first function, with respect to the n
1
.n
2
. . . n
m
different combinations, can be defined in such a way that the one having the smallest membership value among the fuzzy sets that correspond to the variation of the m attributes is selected to obtain the n
1
.n. . . n
m
weights. The second function, with respect to the n
1
.n. . . n
m
different combinations, can be defined in such a way that cost of data removal, in other words, visual effects on the simplified mesh is selected to be the power of the variation of the m attributes followed by multiplying with each other, hence obtaining the n
1
.n
2
. . . n
m
output values. The third function can be defined as the computation of a weighed average.
The fuzzy-based inference mesh simplification method of this invention is not limited to using TSK fuzzy inference system. For example, common Mamdani fuzzy inference system, Tsukamotos fuzzy inference system and so on can also be used, as long as all attributes within a mesh is considered without any loss of generality.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.


REFERENCES:
patent: 5537514 (1996-07-01), Nishidai
patent: 5566072 (1996-10-01), Momose et al.
patent: 5845008 (1998-12-01), Katoh et al.
Eshera et al, “Parallel Rule-Based Fuzzy Inference of Mesh-Connected Systolic Arrays”, IEEE Intelligent System, Winter 1989.

Affiliated with

Also associated with

Rating

Fuzzy inference system for simplifying mesh does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fuzzy inference system for simplifying mesh, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fuzzy inference system for simplifying mesh will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3343188