Note: Descriptions are shown in the official language in which they were submitted.
CA 02358527 2001-06-27
1
METHOD FOR SIMPLIFYING A SOURCE MESH TAKING ACCOUNT OF
THE LOCAL CURVATURE AND THE LOCAL GEOMETRICAL DYNAMICS
AND CORRESPONDING APPLICATIONS
1. Field of the invention and ap~olications
7.1 Field of the invention
The field of the invention is that of encoding of geometrical data
structures or meshes especially large-sized ones. More specifically, the
invention relates to the representing and encoding of objects or scenes in
three dimensions. More specifically again, the invention relates to a
technique of approximation of a 3D source mesh capable of being used
alone or in combination with other known techniques. In the latter case, the
method of the invention may consist of an advantageous step of initialization.
A mesh is conventionally defined by a set of oriented vertices and
oriented faces defining a topology. Meshes of this kind are for example used
in computer graphics to model 3D objects with limited geometrical
complexity.
The approximation of a mesh M lies in finding a mesh M' whose
geometrical complexity is lower than that of the mesh M, and best
approaches the geometry of M.
7.2 Exemplaror ap,alications
The invention can be applied in all fields where it is desirable to
reduce the number of pieces of information needed to represent and/or
efficiently manipulate an object in three dimensions or a set of objects, for
example in order to analyze it, store it and/or transmit it and/or obtain its
rendering.
By way of an indication, the invention can be applied especially to the
field of:
- virtual reality (virtual tours or virtual shopping, leisure activities,
remote handling, etc.). In this type of application, the mesh
approximation reduces the cost of the rendering of complex
CA 02358527 2001-06-27
2
scenes, especially by defining the notion of scalability on the
meshes (as a function of the viewpoint, graphic capacities,
desired refresh rate, etc.). In the case of distributed or shared
virtual reality, mesh approximation can also be used to match
the complexity of the scene to the capacity for rendering and
storage of the different terminals as well as the bit rates of the
networks;
- scientific simulation (finite elements, CAO, etc.). The reduction
of the geometrical complexity of the models enables an
acceleration of computation time, faster decision-making,
especially in CAO designing and the elimination of redundant
information in a 3D database;
- modelling (3D scanner (reconstruction of surfaces from non-
organized points), volume scanners, reconstruction of surfaces
from stereoscopic photos or video sequences, digital field
models (radar or satellite imaging), etc.). A digital field model
thus gives a mesh representing the topology of a region. Such
a mesh is obtained by the regular sampling of an image storing
altitude information at each point. This results in a large
quantity of data including information unnecessary for scientific
simulation or too costly for the rendering (in the case of
simulators). Mesh approximation reduces the quantity of data
while ensuring high geometrical fidelity to the initial data and
the conservation of the topology.
2. Prior art
2. 7 Families of algorithms
Several techniques of mesh approximation are already known. The
most widespread ones may be classified under three large families of
algorithms depending on whether they work by:
- decimation;
CA 02358527 2001-06-27
3
- subcritical resampling;
- adaptive subdivision.
2.1.1 Decimation
Decimation consists of the iterative withdrawal of the vertices and/or
faces of a mesh. This operation is called an elementary operation of
simplification. The methods implementing this principle of decimation can
also optimize the positions of the vertices before or during the
simplification.
Optimization during the simplification is chosen so as to preserve the
topology of the mesh as efficiently as possible.
2.1.2 Subcritical resam,uling
Resampling consists of the sampling of an original model either in
taking points randomly on its surface and then retriangulating or by defining
a
3D grid and agglomerating the vertices in each elementary box of the grid.
The model thus generated is simplified and must approximate the initial data
as closely as possible. This technique is fast but does not keep the topology
or the visually important characteristics of the meshes.
2.1.3 Adaptive subdivision
Adaptive subdivision begins with a model comprising a very simple
geometry that is then recursively subdivided by adding a detail at each
iteration in the regions where the approximation error is the maximum.
2.1.4 Combinations of alcrorithms
In order to enable an approximation of a mesh with satisfactory
reconstruction quality, it is necessary to combine a decimation and an
optimization of the positions of the vertices preserved. In other words, since
the basic goal of a source mesh encoding method is to maximize the quality
of the approximation for a given geometrical complexity, it must especially
have the following properties:
- decimation;
- preservation of the topology;
- optimizing of positions according to a predefined error criterion.
i
CA 02358527 2001-06-27
4
Thus there is a first method called "remeshing" that meets these
criteria. It is presented especially in Greg Turk, "Re-tiling Polygonal
Surfaces" by Greg Turk (SIGGRAPH 95 Conference proceedings, pp. 55-64,
92). It works by sampling, decimation and optimizing of the positions.
Another technique, known as "progressive mesh encoding" has been
developed by Hughes Hoppes in "Progressive Meshes" (SIGGRAPH 96
Conference proceedings, pp. 99-108, 1996). It relies on decimation and the
optimization of the points.
Yet another technique is described in the patent application FR-
98 13090 filed on 15/10/98 and not yet published.
There is also a technique, known from the document U.S. 5,590,248,
for reducing the complexity of a mesh. This technique eliminates vertices or
polygons as a function of the distance between a candidate vertex and all the
planes formed by triplets of vertices adjacent to this candidate vertex. This
method is complex because it entails the setting four thresholds and it is
costly in computation time because it entails the reviewing of all the
vertices
and/or polygons at each sequence.
3. Goals of the invention
The invention relates more particularly to the decimation technique
implemented for example by these different techniques.
In particular, a goal of the invention is to overcome the different
drawbacks of known techniques.
Then, a goal of the invention is to provide a method for mesh
simplification by decimation (edge merging) that is more efficient in terms of
perceptual quality than the known techniques.
In other words, it is a goal of the invention to provide a method of this
kind which, up to a high level of decimation, preserves the singularities of
the
meshes and preserves the topology.
CA 02358527 2001-06-27
A goal of the invention is also to provide a method of this kind that is
simple to implement in terms of computations to be performed and has high
execution speed.
According to a first aspect of the invention, another goal is to provide a
5 method of this kind that can be used alone in order to give a fast mesh
simplification method.
According to a second aspect of the invention, one goal is to provide a
method of decimation of this kind that can be used in a method of
geometrical mesh optimization so as to improve it.
4. Main characteristics of the invention
These goals as well as others that shall appear hereinafter are
achieved by means of a method of simplification of a source mesh M formed
by a plurality of surfaces defined by vertices, faces and orientations
thereon,
wherein this method implements a step of decimation by edge merger in
which a edge to be decimated, defined by two vertices, is reduced to a single
vertex located on the segment defined by said edge to be decimated so as to
obtain a simplified mesh M'.
The invention relies on a novel approach to decimation in which the
edges are merged while known techniques seek to eliminate vertices. As
shall be seen here below, this approach can simplify the processing
operations (for example by eliminating of the retriangulation phase that is
necessary when an elimination of vertices is implemented) and optimize the
quality of the results (especially: taking account of the curvature, position
of
the vertex resulting from the merger of edges, etc.).
Advantageously, the method comprises a step of selecting a edge
merger to be performed among all the edge mergers possible, taking account
of:
- at least one piece of information representing the curvature
locally defined around the edge considered;
CA 02358527 2001-06-27
6
- at least one piece of information representing the locally
defined geometrical dynamics.
By taking these two criteria into account, it becomes possible, as shall
~ be seen hereinafter, to optimize the choice of the mergers to be made by
eliminating the perceptually less significant elements as a matter of
priority.
Preferably, said selection step implements a priority queue of the
edges to be merged, driving the decimation process as a function of a priority
criterion, said information representing the curvature, and then of a
secondary criterion, said information representing the geometrical dynamics.
This hierarchy of criteria gives high efficiency.
Advantageously, said selection step manages a threshold of
curvature, and only the edges having a curvature below said threshold are
considered for the application of said secondary criterion, said threshold
being increased when no edge has a curvature smaller than this threshold.
According to different particular embodiments, said information
representing the geometrical dynamics may belong to the group comprising:
- the length of the edge considered;
- a mean of the surfaces of the faces neighboring said edge
considered;
- a mean of the length of the edges adjacent to the vertices
forming said edge considered;
- a combination of lengths of edges and/or surfaces of faces;
- any other characteristic variable linked to the local density.
As shall be seen here below, taking account of the length of the edge
is a simple technique and gives very good results.
The decimation may be interrupted, in particular, as a function of one
of the criteria belonging to the group comprising:
- a compression rate attained;
- a geometric complexity attained expressed by a number of
vertices or faces;
CA 02358527 2001-06-27
7
- a threshold of curvature attained.
Advantageously, the method of the invention also comprises a step of
pseudo-optimization after said step of decimation by edge merger providing
for the positioning of the resultant vertex of said merger so as to reduce the
geometrical deviation between said source mesh M and said simplified mesh
M'.
Said step of pseudo-optimization may advantageously consist in
enumerating the sharp edges around the two vertices forming the edge to be
merged and in distinguishing the following two cases:
- if the number of sharp edges is the same around both vertices,
the vertex resulting from the merger is placed in the middle of
the segment connecting said vertices;
- if the number of sharp edges is different, the vertex resulting
from the merger is placed on the vertex having the greatest
number of sharp edges.
According to a first mode of implementing the invention, the method of
simplifying a source mesh constitutes a step of initializing a method of
geometrical optimization of a mesh.
The invention also relates to a method of this kind for the geometrical
optimization of a source mesh comprising an initialization step implementing
the simplification method described here above.
According to a second mode of implementation of the invention, the
method of simplifying a source mesh can be used alone.
5. List of figiures
Other features and advantages of the invention shall appear more
clearly from the following description of a preferred embodiment, given by
way of a simple illustrative and non-restrictive example, and from the
appended figures, of which:
- Figure 1 illustrates the principle of a edge merger;
Y h
CA 02358527 2001-06-27
g
- Figure 2 illustrates the principle of the priority queue combining
the curvature and the locally defined geometrical dynamics
according to the invention;
- Figure 3 illustrates the enumeration of the sharp edges around
a vertex of the mesh;
- Figure 4 presents the principle of pseudo-optimization between
edge merger according to the invention.
6. Description of an embodiment of the invention
6. 7 Geometrical simplification
As indicated here above, the invention relates especially to a new
technique of simplification of a 3D mesh relying on the implementation of a
priority queue combining the local curvature and the local geometrical
dynamics. This technique especially has the advantage of preserving the
singularities of the meshes, up to a high level of decimation. It furthermore
has valuable execution speed.
According to the invention, a priority queue managing the edge merger
topological operator is built. This priority queue combines the criteria of
local
curvature and of local geometrical dynamics in order to exploit, as
efficiently
as possible, the degree of liberty given by the order of conversions to be
made on the mesh.
The simplification of a mesh M lies in building a mesh M' with reduced
geometrical complexity. This keeps a small geometrical deviation with
respect to M.
The geometrical simplification algorithm must provide for specifying a
geometrical resolution to the closest vertex. For this purpose, an elementary
topological operator for simplification having the right properties is chosen.
These are: maintaining the topology in a certain measure of decimation,
absence of creation of holes in the surfaces, and keeping the orientations.
This elementary topological operator is the edge merger as defined for
example by Hoppe (document referred to) illustrated in Figure 1.
CA 02358527 2001-06-27
9
The edge mergers 10 consist in merging the two adjacent vertices 11
and 12 into a vertex 13, eliminating the two faces 14 and 15 and positioning
the vertex 13 resulting from the merger. It will be noted that this conversion
is reversible (with the possibility of an insertion 16 of a vertex).
Each elementary conversion decimates the mesh approximating M'.
The quality of the approximation therefore gets degraded during the
decimation or, at best, remains unvarying. In order to limit the degradation
brought about in the mesh, it is desired of course to first of all make
conversions affecting the model as little as possible.
For this purpose, a priority queue is defined containing all the
conversions that can be made on the mesh (that is, approximately the
number of edges). During the decimation, the least-costing conversion in the
priority queue is performed and then eliminated from the queue. The cost in
the neighborhood modified by the previous operation is then recomputed and
the new potential conversions on the mesh are inserted into the priority
queue after their cost has been computed.
The geometrical singularities, which are highly informative parts, must
be preserved as long as possible during the decimation. In particular, the
regions of high curvature appear to be highly informative. Consequently, the
first criterion of sorting on the elementary conversions is linked to the
local
curvature around the edge to be merged.
The term "curve C(Xi) around a vertex Xi" designates the maximum
angle between the normals to two adjacent faces around the vertex Xi.
Then, the term "curve around an edge (referenced by two vertices Xi and Xj)"
designates the mean of the criteria assessed at each vertex.
A second criterion based on the length of the edge to be merged,
which reduces the geometrical density of the mesh and gives an efficient
aspect ratio on the resulting triangles, is implemented.
CA 02358527 2001-06-27
It is also possible to use an habitual formula representing
compactness. However, the length of the edge to be merged has
advantages:
- giving a mesh a uniform density in the regions of neighboring
5 curvature;
- preserving high compactness of the triangles since this criterion
tends to create equilateral triangles;
- presenting a low computation cost.
In other words, the priority queue according to the invention is based
10 on taking the following two aspects into account simultaneously:
- a small triangle is valuable only in a highly information region
(namely a region of high curvature);
- it is desirable to reduce the density of a mesh in order to reduce its
complexity.
The two criteria taken into account according to the invention are
combined to obtain the behavior illustrated by Figure 2. This figure is a
scale
of the curvature graduated from 0 to - in radians.
In the regions of low curvature 21, below the first threshold 22, the
density is reduced and the compactness obtained is reasonable since the
edges of minimum length are merged.
The threshold defining a low curvature is then increased (23), when
there is no longer any conversion possible on the segment of low curvature
21.
Thus, on the lowest decimation levels, the constraint of curvature is
automatically relaxed in order to achieve the fixed geometrical complexity.
The priority queue therefore has two levels of constraint organized
according to a hierarchy: its curvature is a priority criterion and its
density is
a secondary criterion.
6.2 Pseudo-optimization
CA 02358527 2001-06-27
11
After an edge merger operation, it is allowed to place the vertex
resulting from the merger on the probable optimum position.
To this end, the notion of a sharp edge is introduced. A edge is sharp
when the angle formed by the normal to the two adjacent faces is greater
than a fixed parametrizable threshold. Then, the number of sharp edges
around the vertices of the edge to be merged is enumerated as shown in
Figure 3. The vertex 31 is associated with no sharp edge, the vertex 32 with
two sharp edges and the vertex 33 with three sharp edges.
From this enumeration, two cases are deduced for the initialization as
shown in Figure 4:
- if the number of sharp edges around Xa and around Xb is
identical, the initialization is done in the middle of the segment
forming the edge to be merged. On the plane faces of low
curvature, this preserves high compactness on the neighboring
triangles. On a regular sharp edge (with the number of sharp
edges equal to 2), it enables the positioning of the vertice close
to the sharp edge which will be preserved during the
optimization;
- if the numbers of sharp edges around Xa and around Xb are
different, the initialization is done on the vertex having the
greatest number of sharp edges. In the most current cases, the
optimum is achieved from this initial position.
In the example of Figure 4, where the source mesh corresponds to a
parallelepiped 41, it is observed that this heuristic approach places the
vertex:
- on the corner of the parallelepiped when the edge to be merged
forms a corner 43;
- and on the regular sharp edge of the parallelepiped when the
edge starts on the plane region and ends on the sharp edge 45.
rt
CA 02358527 2001-06-27
12
The situations where the number of sharp edges is the same around
both vertices are illustrated in 42 and 44.
6.3 Anpiications
As indicated here above, the technique of simplification of the
invention (with or without pseudo-optimization) can be implemented alone, to
provide a mesh approximation technique or as a step of initialization on a
more complex procedure of geometrical optimization such as for example the
one described in the patent application FR-98 13090 referred to here above.
