Image analysis – Image compression or coding
Reexamination Certificate
1998-07-21
2001-11-06
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
C345S440000
Reexamination Certificate
active
06314205
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the compression and transmission of three-dimensional geometric models.
2. Description of the Related Art
The introduction of three-dimensional (3D) CAD system have been widely adopted by many manufacturing companies. The use of such systems requires greater data handling capabilities in quantities ranging from several hundred MB to several GB. Moreover, the 3D CAD systems have been used in collaborative, concurrent design processes in a network environment. Therefore, the length of the period of time required for the transfer of CAD data across a network and for the display of the CAD data is important. The importance of this time period will increase as the use of 3D CAD is expanded in the future. The transfer of product data is also being discussed by ISO STEP and CALS.
In order to rapidly transfer and display a solid model and surface model which are created using the 3D CAD system, data for the models may be compressed. However, the compression of solid models and surface models, which include holes and which may include a face whose boundary consists of an edge and a vertex or a face whose boundary consists of two edges and two vertexes, has not been studied much. On the other hand, various compressions of triangle mesh models have been studied.
To express a triangle mesh model, usually n vertex coordinates and three vertex indexes per one triangle are required. First, an explanation will be given only for topological data, i.e., information concerning how n received vertexes are linked together to form a triangle. In the ordinary expression, assuming the number of triangles in an n-vertex mesh model is 2n, the quantity of data required for expressing a triangle is 6log2n bits.
The reference “OpenGL Programming Guide,” J. Neider, T. Davis and M. Woo, Addision-Wesley, 1993 describes APIs, a triangle strip and a triangle fan as methods for rapidly transferring a triangle. These methods are employed to express vertexes for triangles having fewer processes than have those for which the vertexes are held separately. As shown in FIG.
11
(
a
), for the triangle strip, vertexes are provided in a zigzag fashion. On the other hand, as shown in FIG.
11
(
b
), for the triangle fan, vertexes are provided like a fan. In a triangle strip consisting of n triangles, the number of vertex coordinates to be transmitted is reduced from 3n to (n+2), and if vertexes are expressed by indexes, the quantity of data is 2(n+2)log
2
n bits.
In “Geometry Compression,” M. Deeling, SIGGRAPH '95, 1995, a generalized triangle strip by which the quantity of data is further reduced. According to this method, a buffer for 16 vertex coordinates is provided and topological control code is transmitted, so that a long generalized strip can be created having mixed properties, incorporating those of the triangle strip and the triangle fan. The quantity of data is approximately (⅛nlog
2
n+Sn) in a case where there are n vertexes.
In “Geometric Compression Through Topological Surgery,” G. Taubin, IBM Research Report RC-20340, January 1996, there is disclosed a method for expressing a triangle mesh using a vertex spanning tree (a tree for tracing all the vertexes using a mesh model) and a triangle tree (a tree structure formed of the previously mentioned triangle strip). According to this method, in an ideal case, one triangle can be expressed by one bit and the topology of a mesh model can be expressed by a total of 2(2log
2
n+2n) bits. An ideal case means a case where the entire mesh model constitutes a single triangle strip. Since the triangle tree is uniquely determined by the vertex spanning tree, the actual quantity of data depends on whether a spanning tree can be acquired whereby the longest triangle strip can be provided. Although the search for the optimal solution is an NP complete problem, by using a method for searching for the approximate solution, data can be compressed considerably more than it can by using a conventional method.
The above described methods are provided for a triangle mesh model. When only a triangle mesh model is a target, the following problems arise.
(1) Although a triangle mesh model is a presentation that is easily handled by hardware and is optimal for a high speed display, the quantity of data for a curved surface model, however, becomes enormous. If a model in FIG.
12
(
a
) describing a free curved surface is approximated to triangles so that the error from the original curved surface is 10~ or less, very many triangles are required and the quantity of data is increased by one or more digits. It is inconvenient to employ an excessively increasing quantity of triangle mesh data for a high speed transfer, and in this case, a curved surface model should be transmitted unchanged. The above references do not provide any solutions for this problem.
(2) Although the largest market for the geometric model is the manufacturing industry, a triangle mesh model cannot adequately cope with this field. A CAD model that is popular with the manufacturing industry employs a manifold as a defined region (the term “manifold” is usually interpreted to mean a “closed” manifold that is the domain of a solid model, in this case a manifold “having boundaries” is also included). Therefore, the topology shown in FIGS.
12
(
b
), (
c
) and (
d
) exists, and a compression method for a triangle cannot be employed for them.
Since in many cases the quantity of data for a 3D geometric model is large, transferring data takes a great deal of time. According to the conventional technique, the 3D model cannot be displayed at a transfer destination unless the transferring of all the data has completed. However, if a display is provided based on a data transfer by sequentially using only data that is received, an approximate understanding of the shape of the 3D geometric model can be obtained during the transfer of data, and the transfer of data may be halted during the transfer process.
The technique described “Progressive Mesh,” H. Hoppe, SIGGRAPH '96, 1996 is known as a related technique. This technique employs a mesh simplification method used in LOD ((Level Of Detail) or Multiresolution)). According to the mesh simplification method, vertexes at both edges are fused to reduce the number of triangles. This processing is shown in FIG.
13
. The simplification process proceeds from FIGS.
13
(
a
) to
13
(
b
) (the designated solid line arrow), and vertexes vi and v
2
in FIG.
13
(
a
) are fused to serve as v′ in FIG.
13
(
b
). A process proceeding from FIGS.
13
(
b
) to
13
(
a
) (indicated by a broken line arrow) is shown as a progressive display process. This process is performed by simultaneously transferring coordinate data and topological data for changing the level of detail. The method described in Mesh is closely related to a triangle mesh, and has the conventional problem described above for topological data compression.
SUMMARY OF THE INVENTION
To resolve these and other problems, it is one object of the present invention to perform lossless data compression for a 3D geometric model that includes a solid model and a surface model.
It is another object of the present invention to provide a data compression method for topological structures of various geometric models.
It is an additional object of the present invention to enable the high speed transfer of the geometric data and the reduction of the disk memory capacity required for the storage of geometric data.
It is a further object of the present invention to enable the progressive transfer (display) of a 3D geometric model.
According to the present invention, a topological transformation is performed for a three-dimensional (3D) geometric model that is to be compressed, and a triangle mesh is generated. Since the triangle mesh is generated, the triangle mesh compression method, as described above is employed. Associated data required for the performance of a reverse operation for the topological transformation ar
Aono Masaki
Masuda Hiroshi
Ohbuchi Ryutarou
Couso Jose L.
Dang Duy M.
International Business Machines - Corporation
Percello Louis J.
LandOfFree
Method and apparatus for compressing and transmitting a... 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 compressing and transmitting a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compressing and transmitting a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2586679