Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
2001-03-19
2004-01-13
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
Reexamination Certificate
active
06677949
ABSTRACT:
The field of the invention is that of the encoding of images or image elements. More specifically, the invention relates to the adaptive representation and encoding of scenes (or objects of a scene) in three dimensions (3D) represented by meshes.
The invention can be applied in all fields where it is desirable to reduce the number of information elements needed for the efficient depiction, storage and/or transmission of a digital image. For example, the invention may be used to transmit images through the Internet. In this context, it enables the animation of 3D scenes with real-time display although the bit rate is neither constant nor ensured. In this case, the invention may be a primitive of a data transmission language such as VRML.
Other applications that may be envisaged include the storage of animated data on CD-ROM (or an equivalent data carrier), multiple-user applications, digital television, etc.
The invention proposes an improvement to the methods known as “wavelet” methods used to represent a mesh as a sequence of details added to a basic mesh. The general theory of this technique is described especially in the article by M. Lounsberry, T. DeRose and J. Warren, “Multiresolution analysis for surfaces or arbitrary topological type” (ACM Transaction on Graphics, Vol. 16, No. 1, pp. 34-73).
A method of implementation is presented in the article by M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsberry and W. Stuetzle, “Multiresolution analysis of arbitrary meshes” (Computer Graphics Proceedings 1995). It proposes to use the technique of partition known as the “Delaunay triangulation” method, for multiple resolution meshes.
The method of Eck et al. comprises the following steps:
given a mesh M, ideally a Delaunay triangulation is done of this mesh, namely a special partition of its surface into “topologically triangular” zones;
from this triangulation, a simplified mesh M
0
is deduced in obtaining a correspondence between a triangular facet at each component of the partition;
the parametrization &rgr; between M
0
and M is determined facet by facet in minimizing a particular elastic energy. Thus, an approximation of a harmonic function, which has the advantage of being bijective, is obtained;
with &rgr; available, the filters are applied to obtain the wavelet coefficients.
This technique has a certain number of drawbacks, especially with regard to the length of the computation times and the efficiency of the data compression obtained.
Furthermore, it is necessary for all the data to be transmitted to the terminal so that the object can be reconstructed in a recognizable way. Now, in many applications, it is desirable that this object should be capable of being reconstructed in successive phases (roughly to begin with and then by successive refining operations). More generally, the visual fidelity of the depictions of the object according to the known method is not always ensured.
In particular, it is an aim of the invention to overcome these drawbacks of the prior art.
More specifically, it is a aim of the invention to provide a method for the encoding of a source mesh, that provides a gain in compression, namely a reduction in the number of wavelet coefficients, as compared with prior art techniques.
Another aim of the invention is to provide a method of this kind with higher geometrical fidelity or visual fidelity towards the source object.
It is also an aim of the invention to provide a method of this kind enabling a very swift successive reconstruction of the object, the object being recognizable, in a rough depiction.
Similarly, another aim of the invention is to provide a method of this kind to adapt the degree of precision of the reconstruction of an object to various criteria such as the power of the terminal, the available bit rate, the position of the object in the scene, a choice of the user, etc.
These goals as well as others that shall appear hereinafter are achieved according to the invention by a method for the encoding of a source mesh (M) representing an object in three dimensions, in which a simple mesh (M
0
) is determined, this simple mesh having a limited number of facets each defined by vertices and ridges, and then coefficients in a wavelet base, corresponding to local modifications of said simple mesh (M
0
), a method according to which the determining of said simple mesh (M
0
) comprises the following steps:
the detection in said source mesh (M) of at least one line of discontinuity;
the assignment of said line of discontinuity to at least one of said facets of the simple mesh (M
0
) as a ridge.
In other words, the invention is based especially on the observation that the prior art does not take account of the lines of discontinuity, namely sets of contiguous ridges forming big angles in the vicinity of zones that may be considered to be smooth.
Furthermore, it will be noted that the steps of detection and assignment are performed during a single processing operation. It is not necessary to know or make a preliminary search for all the discontinuities to carry out this processing operation since the detection forms parts of this operation.
The term “discontinuity” is understood, in the present patent application, to mean any set of attributes of contiguous facets that is contained in at least two facets and has a difference greater than at least one threshold (possibly variable) according to a predetermined criterion.
As is described hereinafter, it may be a geometrical attribute or an attribute of orientation. In this case, a discontinuity may be a set of contiguous ridges such that each of the ridges is contained by at least two facets forming a non-negligible angle depending on the criterion chosen.
More generally, the invention can be applied to any specific attribute of the facet such as the color or texture. For example, it may be planned that a discontinuity will be detected if the current difference is great.
Naturally, several criteria of discontinuity may be considered for one and the same mesh (color and orientation for example).
According to the invention, by contrast, the discontinuity lines are directly approached by segments and not by internal parts of faces. In this latter, which is encountered with a Delaunay triangulation, it is indeed necessary to go much further with the subdivision of the facets in the remesh, leading to the creation of wavelet coefficients at superfluous levels of detail (or even to represent a mesh such as the infinite sum of the details whereas a finite number would have been enough to represent it exactly).
The fact that a Delaunay triangulation cannot be used to specify the lines of discontinuity as images of ridges of the mesh M
0
, unlike the invention, explains the inefficiency of this method both for encoding and gradually transmitting meshes with lines of discontinuity. Conversely, it will easily be understood that the invention enables a rough reconstruction, the simple mesh M
0
already enabling a rough reproduction.
It must be noted that the observation of the useftilness of taking account of discontinuities is not obvious to those skilled in the art. It relies on a new approach in which it is first of all the object to be processed that is considered while those skilled in the art generally seek to improve the general, mathematical aspects of the problem. Furthermore, it provides an efficient and simple response to crucial problems for which substantial research has been made without achieving this result.
Advantageously, said determining of the simple mesh (M
0
) comprises a step of searching for zones or components of said source mesh (M) constituted by facets of said source mesh (M) meeting a predetermined coplanarity criterion, comprising said steps of detection and assignment.
According to a preferred embodiment of the invention, said step of detection of a line of discontinuity comprises a step of comparison of the angle formed by two facets of said source mesh at a predetermined threshold angle E
1
, the ridge between said facets being considered to be a line of discontinuity if said
France Telecom
Vo Cliff N.
LandOfFree
Simplifying and encoding a source 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 Simplifying and encoding a source mesh, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplifying and encoding a source mesh will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241459