KR20060087662A - Single-rate geometry coding for 3d quad meshes - Google Patents

Abstract

Three-dimensional figures are emerging as new media in various fields such as animation, virtual reality, games, simulation, and medical imaging. Unlike the existing sound (one-dimensional), image (two-dimensional), and video (two-dimensional + time) data, the three-dimensional figure contains a huge amount of data. Existing compression methods applied to sound (mpeg), image (jpg, gif), video (avi, mpeg), etc. do not take into account the spatial information. It was not efficient to express. Therefore, a new compression method was needed to match the characteristics of three-dimensional data. For the past several years, three-dimensional data compression programs using various techniques have been introduced to improve the compression rate gradually. The present invention aims to drastically reduce such huge three-dimensional mesh data size to facilitate storage and transmission. The three-dimensional figure basically consists of position information (geometry information) of points constituting the figure and connection information indicating a connection state of each point. When compressing three-dimensional figures, connection information takes up 10% of the compressed data, and the remaining 90% is geometric information. Therefore, the influence of the compression rate of geometric information on the overall compression rate is high. The present invention is a simple single-rate geometry coding technique of a new three-dimensional rectangular mesh. This is a method of setting a new local coordinate system accordingly, converting it to a real type local coordinate value, and quantizing it into an integer value.

3D Mesh Compression Single-Rate Compression, Quad Mesh.

Description

Single-Rate Geometry Coding for 3D Quad Meshes

In the case of rectangular mesh, the front face is regarded as a triangle consisting of gates V0-> V1 and FR (front right) vertex and two triangles consisting of gates V0-> V1 and front left vertex. do.

Representative diagram Figure-When compressing the FR (Front Right) point. In this case, the back face is already processed and the triangle formed by the gates V0-> V1 and FR connected to it is the surface to be processed. Since V0 and V1 belong to the front and rear at the same time, it is already compressed at the rear processing, so if you compress only the Front Right (FR) vertex, the processing of the surface consisting of V0, V1 and FR is completed. Therefore, the geometric information to be compressed is always the spatial coordinate value (x, y, z) of the Front Right (FR) Vertex that belongs to the right front of the gate, which is a line segment going from two points V0 to V1. This coordinate value can be expressed using the new Local Coordinate system based on the gate and the back face.

1 is an example of a three-dimensional rectangular mesh

2 is a diagram illustrating a situation when a new point to be compressed is found when compressing geometric information of a 3D rectangular mesh.

3 is a compression tool for implementing the present invention

FIG. 4-Screen for Inserting Region Segmentation Values for Geometric Data Compression

Figure 5-3D mesh after decompression

1. Purpose of the invention

Three-dimensional figures are emerging as new media in various fields such as animation, virtual reality, games, simulation, and medical imaging. Unlike the existing sound (one-dimensional), image (two-dimensional), and video (two-dimensional + time) data, the three-dimensional figure contains a huge amount of data. Existing compression methods applied to sound (mpeg), image (jpg, gif), video (avi, mpeg), etc. do not take into account spatial information. It is not enough to follow. According to the present invention, the conventional simple compression method of 3D mesh geometric information uses the global coordinate quantization technique to unnecessarily divide a lot so that the compression rate is low and the distortion rate between the restored data and the circular data is also severe. The localized quantization method is used to significantly improve the compression rate and reduce the distortion rate. Thus, the present invention further reduces the memory requirements for storing three-dimensional rectangular mesh data and enables fast transmission over the Internet and intranets.

2. Technical field and prior art

With the development of three-dimensional sensors and scanning technologies, the creation of sophisticated and complex three-dimensional data is easily achieved. However, these three-dimensional data has a huge file size has a lot of difficulties in storage and transmission. For this reason, researches on the compression technology of 3D figures have been actively conducted recently. Compression technology for fast transmission of 3D figures on the Internet is an essential technology for the present and future Internet environment. In the past few years, we have witnessed the rapid reduction in the compression rate of common data due to innovative compression techniques. However, in the case of three-dimensional data, the research results were relatively small compared to the media such as sound, pictures or video. Three-dimensional data basically consists of the position of each point (geometric information) and the connection state (connection information) of each point. Three-dimensional compression is divided into single-rate compressing circular data at once and progressive compression, which compresses and transfers additional items after compressing the basic shape. It is also classified into lossy compression and lossless compression. Simple compression is more efficient than progressive compression. In recent years, lossless connection information compression has been a major concern of previous studies, and the upper limit of Bit-Rate has been studied. Until now, global coordinate compression has been used to compress geometric information of three-dimensional data. [1] The Deering paper limits the precision for each coordinate position of a point to 16 bits, because empirically the difference between one point and the neighboring point is less than 16 bits. Only the position of the first point is designated as 32 bits. [2] The IBM Taubin paper used vertex spanning tree to predict the position of each point by using the 1,2,3,4 anchors in the tree. Each coordinate is standardized to a fixed number, such as 8, 10 or 12 bits, to compress the difference between the predicted position and the original position. [3] Touma and Gotsman (TG) 's paper presented global quantization in conjunction with the prediction of geometric information and is the most popular compression method in simple compression techniques. Touma-Gotsman was used in the "Triangle Mesh Compression" paper presented at the Graphics Interface 98 Conference Proceedings. This is a method of converting an integer grid value closest to a coordinate value. However, this method has the disadvantage of being severely distorted because it is simple to implement but cannot completely recover faces that are not parallel to the grids. [4] Vector Quantization This technique proposed a method of moving each point into a model vector formed by three processed points. The resulting model space vectors and correction vector sets are quantified using a modified vector quantization technique. The compression results show a slightly improved compression rate only for 8-bit quantification when compared with the values of TG.

references

[Deer 95] M. Deering. Geometry Compression. Siggraph 95 Conference

   Proceedings,

2. [TR98a] G. Taubin and J. Rossignac. Geometry Compression Through Topological Surgery. ACM Transactions on Graphics, Vol. 17, No. 2, pages 84-115,1998.

[TR98b] G. Taubin and J. Rossignac. Geometry Compression Through Topological Surgery. ACM Trans. on Graphics, 17 (2): 84-115, 1998.

[TR00] G. Taubin and J. Rossignac. 3D Geometry Compression, 1999-2000. ACM Siggraph conference course notes.

3. [TG98] C. Touma and C. Gotsman. Triangle Mesh Compression. Graphics Interface 98 Conference Proceedings

4. [LK00] Eung-Seok Lee and Hyeong-Seok Ko. Vertex data compression for triangle meshes. Proceedings of the 8th Pacific Graphics Conference on Computer Graphics and Application

In the present invention, in order to simply compress and decompress geometric information of 3D mesh data, real-world wide coordinate values are converted to local coordinate values, and then quantized and compressed. To implement this compression method, a new local coordinate system must be defined for the point to be compressed, and new coordinate axes (x-axis, y-axis, and z-axis) are required for this purpose. In the rectangular mesh, variable coordinate axes should be defined for triangles composed of V0, V1, FR and triangles composed of V0, V1, FL. In addition, since the data type of the point used in sophisticated 3D data is double, the difference in 15 digits after the decimal point must be accurately distinguished. In addition, the local coordinate values identical to the local coordinate values used at the time of compression must be correctly restored upon decompression to reduce the distortion rate between the restored figure and the circular shape. There is a need for a precise program technique that must restore the real-type local coordinate values without error from the quantified integer value after decryption.

Detailed Description of Simple Compression of 3D Rectangular Mesh Geometry

1. The local coordinate system is defined as follows.

Define the current gate (V0-> V1) as the x-axis, and let V0 be the origin of the local coordinate system. Convert the x-axis of the local coordinate system to a unit vector and rotate it 90 degrees around the back face normal vector as the y-axis of the local coordinate system. Then, a vector obtained by cross product of the x-axis of the local coordinate system and the y-axis of the local coordinate system is set as the z-axis. Since the range of each local coordinate system axis is unknown, it is necessary to find the range for quantization by examining the range of local coordinate values once before the compression process.

2. Geometry Compression

 When compressing the FR (front right) vertex: The quantified area is divided into desired integer values by projecting the vector connecting V0 and FR vertex to each axis of the local coordinate system. The larger the split value, the closer to lossless compression. After splitting, this value is used to simulate the value to be restored when decompressing. As a result, compression is continued by using the found simulation vertex value (that is, the value to be used for decompression can be known in advance) as the value of the new FR (front right) vertex. Release simulation must be performed to prevent the calculation errors from accumulating.

In the case of FL (Front Left), it is processed in the same way as FR.

3 Geometry Release

Release of 3D rectangular mesh geometry is done in the reverse order of compression.

In the case of transmission, the problem has been solved in the direction of widening the network bandwidth when the size of data is large, and in the case of storage, the solution has been solved in the direction of introducing a large capacity storage device. It dramatically reduces the cost of storage and transmission over the Internet, even with low cost equipment and existing bandwidth. In addition, it is expected to use a lot in the field using 3D shapes such as animation, virtual reality, games, simulation, medical image.

Claims (1)

       Steps to use 3D triangular mesh compression method for two triangles considering the front (rectangle) consists of 2 triangles when compressing geometric information of 3D rectangular mesh Steps to use region segmentation method for compressing and decompressing geometric information of 3D rectangular mesh

Images