JP2005084780A - DEVICE AND METHOD FOR DATA COMPRESSION, DEVICE AND METHOD FOR DATA EXPANSION, DATA STRUCTURE, n-th DIMENSIONAL SHAPE MODEL PROCESSING DEVICE, PROGRAM, AND RECORDING MEDIUM - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a data compression device which can execute compression, storage, transmission and expansion of an n-th dimensional triangular mesh, without reducing the space efficiency of a storage device such as a hard disk or the like, a displaying speed and a transmission speed, even if the size of data on an n-dimensional shape model is increased. <P>SOLUTION: The data compression device consecutively stores a plurality of apex coordinates in an apex coordinate table to apexes on the same plane, when it compresses the shape data which represents the shape model of n-th dimensional space in triangular meshes, stores a normal vector at a single apex in a normal vector table only to the single apex among the apexes in the same plane, and generates the compressed shape data from the data on the n-th dimensional shape model so that it stores "truth" to the single apex and store "false" to other apexes on the plane in a planar flag table. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

  The present invention relates to a data compression device, a method thereof, a data decompression device, a method thereof, a data structure, a three-dimensional shape processing device, a program, and a recording medium, and more specifically, a three-dimensional shape model generation device and a three-dimensional shape model display The present invention relates to a data structure that can be applied to a device, a shape measuring device, a virtual reality device, and that can store shape data compactly when the surface of a shape model is represented by a triangular mesh, and a technology for compressing / decompressing shape data using the data structure. The present invention relates to a technique for enabling high-speed transfer using a network by using this data structure.

Curved surfaces and curves are widely used in CAD (Computer Aided Design) as means for expressing a three-dimensional shape model (see Non-Patent Document 1). In order to display a three-dimensional shape model, it is common to convert a curved surface into data in a triangular mesh format.
On the other hand, in recent years, a CAD data dedicated viewer (3D viewer) that has been used for purposes other than the design department has also appeared.
This viewer converts the surface into shape data expressed in a triangular mesh format and stores it in a viewer-dedicated file. Once the CAD file is converted to this dedicated file, the conversion process each time can be omitted. Realizes faster display than CAD. In some of these 3D viewers, data unnecessary for display is omitted, and further compression is performed to increase the display speed and reduce the data weight.
Toriya Hiroshi and Chiyokura Hiroaki: Basics and Applications of 3D CAD, Kyoritsu Publishing, 1991

However, the use of three-dimensional shape models is increasing, and the amount of data tends to increase as a large-scale and complicated three-dimensional shape model is handled, and it is necessary to further compress the data. Specifically, the following are problems.
(1) Reduced space efficiency of storage devices such as hard disks due to increased data size,
(2) Decrease in display speed due to increase in data size,
(3) Decrease in transfer speed due to increase in data size.
The present invention has been made in consideration of the above-described circumstances, and without reducing the space efficiency, display speed, and transfer speed of a storage device such as a hard disk even when the data size of the n-dimensional shape model increases. , Data compression apparatus capable of performing compression, storage, transfer and decompression processing of triangular mesh in n-dimensional space, method thereof, data decompression apparatus, method thereof, data structure, three-dimensional shape processing apparatus, program and recording medium The purpose is to provide.

In order to solve the above problems, claim 1 of the present invention is a data structure for storing shape data representing a shape model of an n-dimensional space by a triangular mesh, and a vertex storing n-dimensional vertex coordinates This is a data structure using an enumerated triangular mesh characterized by comprising a coordinate table, a normal vector table storing n-dimensional normal vectors, and a plane flag table indicating true / false for each vertex. .
According to a second aspect of the present invention, in the data structure according to the first aspect, the vertex coordinate table and the plane flag table are in a triangle set format or a triangle strip format. It is.
According to a third aspect of the present invention, in the data compression apparatus for compressing shape data in which a shape model of an n-dimensional space is represented by a triangular mesh, a plurality of vertex coordinates are consecutive for a plurality of vertices on the same plane. And the vertex coordinate compression means for storing in the vertex coordinate table, and the normal vector at that vertex is stored in the normal vector table only for a single vertex among the vertices on the same plane. Is provided with normal vector compression means for storing true in the plane flag table and false at other vertices on the plane.
According to a fourth aspect of the present invention, in the data compression method for compressing shape data in which a shape model of an n-dimensional space is represented by a triangular mesh, a plurality of vertex coordinates are continuously applied to a plurality of vertices on the same plane. Stored in the vertex coordinate table, and for only a single vertex on the same plane, the normal vector at that vertex is stored in the normal vector table, true for that vertex, False is stored in the plane flag table for the other vertices on the plane.
According to a fifth aspect of the present invention, there is provided a data decompressing device for decompressing the shape data compressed by the data compressing device according to the third aspect, wherein all vertex coordinates stored in the vertex coordinate table successively. A vertex coordinate extension means for extending the vertex coordinates by reading out a plurality of vertex coordinates stored continuously in the vertex coordinate table when reading true from the plane flag table. Normal vector expansion means for expanding a normal vector by assigning a single normal vector stored in the normal vector table as a normal vector of a plurality of vertices on the same plane. It is characterized by providing.

According to a sixth aspect of the present invention, there is provided a data decompression method for decompressing the shape data compressed by the data compression method according to the fourth aspect, wherein all the vertex coordinates stored in the vertex coordinate table successively. When the vertex coordinates are expanded by reading out and true is read out from the plane flag table, the plurality of vertex coordinates continuously stored in the vertex coordinate table are regarded as the vertex coordinates of a plurality of vertices on the same plane. The normal vector is extended by assigning a single normal vector stored in the normal vector table as a normal vector of a plurality of vertices on the same plane.
According to a seventh aspect of the present invention, there is provided a data structure for storing shape data representing a shape model of an n-dimensional space with a triangular mesh, a vertex coordinate table storing n-dimensional vertex coordinates, For each vertex, a normal vector table storing normal vectors, a vertex coordinate index table storing indexes to the vertex coordinate table, a normal vector index table storing indexes to the normal vector table, and each vertex It is a data structure using an index type triangular mesh characterized by comprising a plane flag table indicating true / false.
According to claim 8 of the present invention, in the data structure according to claim 7, the vertex coordinate index table and the plane flag table are in a triangle set format or a triangle strip format. It is a structure.
According to a ninth aspect of the present invention, in a data compression apparatus for compressing shape data representing a shape model of an n-dimensional space by a triangular mesh, a plurality of vertices on the same plane are stored in a vertex coordinate table without overlapping. The vertex coordinate compression means for storing and storing the vertex coordinate indices in the vertex coordinate index table in succession, and the normal vector at that vertex only for a single vertex on the same plane Store in the normal vector table without duplication, store the normal vector index in the normal vector index table, and specify true for the vertex and false for the other vertices on the plane. Normal vector compression means for storing in a table is provided.

According to a tenth aspect of the present invention, in a data compression method for compressing shape data representing a shape model of an n-dimensional space by a triangular mesh, the shape data is stored in a vertex coordinate table without duplication, and the plurality of vertex coordinate indexes are stored. Consecutively stored in the vertex coordinate index table, and for only a single vertex on the same plane, the normal vector at that vertex is stored in the normal vector table without duplication, and the normal A vector index is stored in a normal vector index table, and true is stored for the vertex and false is stored for another vertex on the plane in the plane flag table.
Further, an eleventh aspect of the present invention is a data decompression device for decompressing the shape data compressed by the data compression device according to the ninth aspect, wherein all the vertices stored successively in the vertex coordinate index table are stored. When the coordinates are read from the vertex coordinate table by the vertex coordinate index with respect to the vertex, the vertex coordinate expansion means for reading and expanding the vertex coordinates, and when the true is read from the plane flag table, the vertex coordinate index table A plurality of vertex coordinates stored in succession are regarded as vertex coordinates of a plurality of vertices on the same plane, and a single normal vector index stored in the normal vector index table is assigned to a plurality of vertices on the same plane. Assigned as a normal vector index, the normal vector Characterized in that it comprises a normal vector decompressing means for decompressing the normal vector by extracting normal vectors from Le table.

According to a twelfth aspect of the present invention, there is provided a data decompression method for decompressing the shape data compressed by the data compression method according to the tenth aspect, wherein all the vertices stored successively in the vertex coordinate index table are stored. The coordinates are continuously stored in the vertex coordinate index table when the vertex coordinates are expanded by reading out the vertex coordinates from the vertex coordinate table by the vertex coordinate index with respect to the vertex, and the true is read from the plane flag table. The plurality of vertex coordinates are regarded as the vertex coordinates of a plurality of vertices on the same plane, and the single normal vector index stored in the normal vector index table is used as the normal vector index of the plurality of vertices on the same plane. Assign and modulo from the normal vector table by this normal vector index Characterized by stretching the normal vector by extracting vector.
A thirteenth aspect of the present invention is a data structure for storing shape data representing a shape model of an n-dimensional space by a triangular mesh, a vertex coordinate table storing n-dimensional vertex coordinates, and an n-dimensional vertex table. For each vertex, a normal vector table storing normal vectors, a vertex coordinate index table storing indexes to the vertex coordinate table, a normal vector index table storing indexes to the normal vector table, and each vertex A reference type triangle comprising a vertex coordinate reference flag table indicating true / false, a normal vector reference flag table indicating true / false for each vertex, and a plane flag table indicating true / false for each vertex This is a data structure using a mesh.
According to a fourteenth aspect of the present invention, in the data structure according to the thirteenth aspect, the vertex coordinate reference table, the normal vector reference flag table, and the plane flag table are either a triangle set format or a triangle strip format. It is a data structure characterized by being.

According to a fifteenth aspect of the present invention, in a data compression apparatus for compressing shape data in which a shape model of an n-dimensional space is represented by a triangular mesh, vertex coordinates referred to for the first time with respect to a plurality of vertices on the same plane. Stores the vertex coordinates in the vertex coordinate table, stores true in the vertex coordinate reference flag table corresponding to the plurality of vertices, and for the vertex coordinates referenced for the second and subsequent times, the vertex coordinate index is stored in the vertex coordinate index table. The vertex coordinate compression means that stores and stores false in the vertex coordinate reference flag table corresponding to the plurality of vertices, and the normal vector that is referred to for the first time, with respect to a single vertex among the vertices on the same plane Only the normal vector at the vertex is stored in the normal vector table, and the normal vector reference flag table corresponding to the vertex is set to true. For normal vectors that are referenced after the second time, the normal vectors at the vertices are stored in the normal vector table only for a single vertex among the vertices on the same plane. Store the normal vector index in the normal vector index table, store false in the normal vector reference flag table corresponding to the vertex, and set true to the plane flag for the vertex corresponding to the single normal vector Normal vector compression means for storing in a table is provided.
According to a sixteenth aspect of the present invention, in a data compression method for compressing shape data representing a shape model of an n-dimensional space by a triangular mesh, vertex coordinates referred to for the first time with respect to a plurality of vertices on the same plane Stores the vertex coordinates in the vertex coordinate table, stores true in the vertex coordinate reference flag table corresponding to the plurality of vertices, and for the vertex coordinates referenced for the second and subsequent times, the vertex coordinate index is stored in the vertex coordinate index table. Stores false in the vertex coordinate reference flag table corresponding to the plurality of vertices, and for the normal vector that is referred to for the first time, the vertex only for a single vertex among the vertices on the same plane The normal vector at is stored in the normal vector table, and true is stored in the normal vector reference flag table corresponding to the vertex. For the normal vector to be illuminated, the normal vector at that vertex is stored in the normal vector table only for a single vertex among the vertices on the same plane, and the normal vector index is stored as the normal vector. Storing in a vector index table, storing false in the normal vector reference flag table corresponding to the vertex, and storing true in the plane flag table for the vertex corresponding to the single normal vector And

According to a seventeenth aspect of the present invention, there is provided a data decompressing device for decompressing the shape data compressed by the data compressing device according to the fifteenth aspect, the flag of the vertex coordinate reference flag table corresponding to the vertex being processed. Is true, the vertex coordinates of the vertex are read from the vertex coordinate table, and when the flag of the vertex coordinate reference flag table corresponding to the vertex is false, the vertex coordinates of the vertex coordinate index table corresponding to the vertex Vertex coordinate extension means for extending the vertex coordinates by reading the coordinate value pointed to by the index from the vertex coordinate table, and a method corresponding to the vertex when the normal vector reference flag table flag of the vertex on the plane is true When a line vector is read from the normal vector table and the normal vector reference flag table flag of the vertex is false, the vertex vector is read. The normal vector corresponding to is read from the normal vector table indicated by the normal vector index of the normal vector index table, and the normal vector is extended by assigning the normal vector to multiple vertices on the same plane. Normal vector expansion means.
According to claim 18 of the present invention, there is provided a data decompression method for decompressing shape data compressed by the data compression apparatus according to claim 16, wherein the flag of the vertex coordinate reference flag table corresponding to the vertex being processed is stored. Is true, the vertex coordinates of the vertex are read from the vertex coordinate table, and when the flag of the vertex coordinate reference flag table corresponding to the vertex is false, the vertex coordinates of the vertex coordinate index table corresponding to the vertex When the coordinate value indicated by the index is read from the vertex coordinate table, the vertex coordinate is expanded, and if the normal vector reference flag table flag of the vertex on the plane is true, the normal vector corresponding to the vertex is the normal line. When reading from the vector table and the normal vector reference flag table flag of the vertex is false, the normal vector corresponding to the vertex is The normal vector is expanded by assigning the normal vector to multiple vertices on the same plane by reading the data from the normal vector table indicated by the normal vector index of the normal vector index table To do.
According to a nineteenth aspect of the present invention, in the data structure according to the first, seventh or thirteenth aspect, the vertex coordinate table and the normal vector table are subjected to floating point representation or vector quantization compression. A characteristic data structure.

According to a twentieth aspect of the present invention, there is provided an n-dimensional shape model processing apparatus for processing a shape model of an n-dimensional space, the data compression device according to the third, ninth or fifteenth aspect, and the fifth, eleventh or seventeenth aspect. Including at least one of the data decompression devices described above, wherein the data compression device generates and transmits shape data obtained by compressing an n-dimensional shape model, and the data decompression device decompresses the received shape data, An n-dimensional shape model is generated.
According to a twenty-first aspect of the present invention, the function of the data compression device according to the third, ninth or fifteenth aspect, the function of the data decompression device according to the fifth, eleventh or seventeenth aspect, or the twentieth aspect is provided. Is a program for executing the function of the n-dimensional shape model processing device described in the above.
The twenty-second aspect of the present invention is a computer-readable recording medium on which the program according to the twenty-first aspect is recorded.

According to the present invention, compression and expansion of a triangular mesh in an n-dimensional space can be performed.
Using this data structure reduces the data size and improves the space efficiency of a storage device such as a hard disk.
Further, since the data size is reduced, the display speed and the transfer speed are improved.
Furthermore, by using this data structure in the three-dimensional shape processing apparatus, compact three-dimensional shape model data can be realized.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings.
The configuration and operation of the present invention will be described based on the following assumptions (1) to (3).
(1) The triangular mesh handled in the present invention is generated based on a curved surface generated by a general three-dimensional shape processing system, and corresponds to which surface (curved surface or plane) each vertex of the triangular mesh corresponds to. Is stored as shape model data.
(2) There are planes and curved surfaces other than the plane, and information on normal vectors (x component, y component, z component) common to all points on the plane can be acquired. To do.
For example, the plane shown in FIG. 1 includes five triangular meshes, and these five triangular meshes have a common normal vector. That is, the normal vectors at the seven vertices of this plane have the common normal vector shown in FIG.
(3) Triangle expression formats include a triangle set format and a triangle strip format.
Among these, the triangle set format is a format in which the three vertex coordinates of each triangle are sequentially arranged and stored. For example, FIG. 2 sequentially stores the three vertex coordinates for three triangles (A, B, C). Since the coordinates of the three vertices of the triangle A are (t _j , t _{j + 1} , t _{j + 2} ), the vertex coordinates are stored in this order in the data structure.
Therefore, in the case of the triangle set format, one triangle can be expressed by taking out three at a time, which is convenient for handling, but is inferior to the triangle strip format in terms of data compression.
On the other hand, the triangle strip format is a format in which the coordinates of the vertices of adjacent triangles are arranged in sequence with one side of the triangle, and the last two vertices are the vertices of the first side of the next adjacent triangle. Arrange so that At the end of the triangle strip format, a delimiter identifier is given by a value that does not appear in the vertex coordinate value or a flag indicating the end.
For example, in FIG. 3, for the three triangles (A, B, C), the three vertex coordinates are stored in a strip format. In this case, the coordinates of the three vertices of the triangle A are extracted from the top three (t _j , t _{j + 1} , t _{j + 2} ), and the coordinates of the three vertices of the triangle B are extracted after the second three. (T _{j + 1} , t _{j + 2} , t _{j + 3} ). A delimiter identifier is placed at the end of the vertex.
Therefore, the triangle strip format is more difficult to handle than the triangle set format, but it is convenient when continuously extracting triangles, and the data compression is superior to the triangle set format. ing.

Next, three types (enumeration type, index type, and reference type) that are data storage formats of the triangular mesh handled in the present invention will be described.
(1) Enumerated triangular mesh:
The enumerated triangular mesh is composed of a vertex coordinate table and a normal vector table.
In the vertex coordinate table, (x, y, z) values of each vertex coordinate of the triangle mesh are stored in either a triangle set format or a triangle strip format. Similarly, the normal vector table stores the (x component, y component, z component) value of the normal vector at each vertex.
(2) Index type triangular mesh:
The index type triangular mesh includes a vertex coordinate table, a normal vector table, a vertex coordinate index table that stores an index of the vertex coordinate table, and a normal vector index table that stores an index of the normal vector table.
The vertex coordinate table unifies the vertex coordinate values (x, y, z) having no overlapping values by unifying the vertex coordinates having overlapping values among the vertex coordinates of the triangular mesh into one.
The vertex coordinate index table stores an index to the vertex coordinate table in which each vertex coordinate value of the triangle mesh is stored in either a triangle set format or a triangle strip format.
Similarly, in the normal vector table, normal vectors having overlapping values among the normal vectors at the respective vertices are unified into one, and normal vectors having no overlap (x component, y component, z component) are obtained. Stores the value.
The normal vector index table stores an index to a normal vector table in which normal vector values at each vertex of the triangular mesh are stored.

(3) Reference triangle mesh:
The reference type triangular mesh has a vertex coordinate table, a normal vector table, a vertex coordinate index table storing an index to the vertex coordinate table, a normal vector index table storing an index to the normal vector table, and a vertex coordinate reference flag table. And a normal vector reference flag table.
The vertex coordinate table registers vertex coordinate values not yet registered in this table, and the true flag value is stored in the vertex coordinate reference flag table corresponding to the vertex.
In addition, in the case of a vertex already registered in the vertex coordinate table, an index to the already registered vertex coordinate value is registered in the vertex coordinate index table, and the vertex coordinate reference flag table corresponding to the vertex is registered in the vertex coordinate reference flag table. A false flag value is stored.
The vertex coordinate reference flag table stored in this way stores these flag values in either a triangle set format or a triangle strip format.
When finding the vertex coordinate value from the vertex coordinate table, the true flag value in the vertex coordinate reference flag table is counted from the top of the table to the location corresponding to the vertex position to be obtained, and this count value is an index into the vertex coordinate table. It is calculated by.
In addition, when finding the vertex coordinate index from the vertex coordinate index table, the false flag value in the vertex coordinate reference flag table is counted from the top of the table to the place corresponding to the vertex position to be obtained, and this count value is counted as the vertex coordinate index. It is obtained by making an index into the table.

The normal vector table registers normal vector values that are not yet registered in this table. In the case of a normal vector already registered in the normal vector table, the index to the already registered normal vector value is registered in the normal vector index table.
In the normal vector reference flag table, a flag value indicating whether the normal vector is stored in the normal vector table or the normal vector index table in a triangle set format or a triangle strip format corresponding to each vertex. Store either.
If the flag value of this normal vector reference flag table is true, it indicates that the normal vector has been stored in the normal vector table. If the flag value is false, the normal vector is stored in the normal vector index table. It shows that it was stored via.
Here, since the normal vectors of the vertices of the triangular mesh belonging to a certain plane are common, only one normal vector is registered in either the normal vector table or the normal vector index table. In this case, the flag values of other vertices on the plane on which the normal vector is registered are registered as values other than true / false.
When finding the normal vector value from the normal vector table, the true flag value in the normal vector reference flag table is counted from the top of the table to the location corresponding to the vertex position to be obtained, and this count value is calculated as the normal vector. It is obtained by making an index into the table.
When the normal vector index is found from the normal vector index table, the false flag value in the normal vector reference flag table is counted from the top of the table to the location corresponding to the position of the vertex to be obtained, and this count value is calculated. It is obtained by setting an index to the normal vector index table.
By storing using this reference type, the data storage area can be further reduced than the index type.

<Embodiment 1>
(1) Data structure of shape data using enumerated triangular mesh:
FIG. 4 shows a data structure for storing an n-dimensional (2-4 dimensional) shape model using the enumerated triangular mesh data structure of the present invention.
The data structure for storing the n-dimensional shape model includes a vertex coordinate table V in which n-dimensional vertex coordinates are stored, a normal vector table U in which n-dimensional normal vectors are stored, and true / false for each vertex. The plane flag table P shown in FIG.
In the vertex coordinate table V, the number of vertex coordinates (= nv) and nv vertex coordinates are stored in the order of the vertex coordinates V1 to the vertex coordinates Vnv in either a triangle set format or a triangle strip format. These vertex coordinates are each composed of three coordinate values (x, y, z), and each coordinate value is subjected to floating point or vector quantization compression.
In the plane flag table P, true and false are stored depending on whether the vertex is a point on the plane or a point on the curved surface, in the same order as the vertexes registered in the vertex coordinate table V. Therefore, the size of the curved surface flag table is the same as the number of vertex coordinates.
In the normal vector table U, the number of normal vectors (= nu) and nu normal vectors are stored in the order of the normal vector U1 to the normal vector Unu. Each of these normal vectors is composed of three components (x component, y component, z component), and each coordinate value is subjected to floating point or vector quantization compression.
Further, when one or more triangular meshes are on the same plane, a common normal vector is used, so that only one normal vector is registered in the normal vector table U.

(2) Shape data compression:
Next, a method for storing predetermined n-dimensional shape data will be described using the data structure shown in the first embodiment (FIG. 4).
First, it is assumed that data representing an n-dimensional shape has already been databased (shape DB) by an n-dimensional shape processing apparatus.
FIG. 5 is a block diagram illustrating the configuration of the data compression apparatus according to the first embodiment. In the figure, the data compression apparatus includes a vertex coordinate compression means 20, a normal vector compression means 30, a generated table (vertex coordinate table, normal vector table, plane flag table) and a data holding means 40 for storing a shape DB. And control means 10 for controlling these means.
FIG. 6 is a flowchart showing a processing procedure when the designated shape data in the shape DB is stored in the format of the data structure of FIG.
A vertex coordinate table that continuously stores the vertex coordinates of all the vertices included in the specified shape data in the shape DB is written to the data holding means 40 (step S10). In step S10, the vertex coordinate compression means 20 is configured.
It is determined whether or not the surface included in the specified shape data is a plane. If the surface is a plane (YES in step S11), a common normal vector of triangular meshes belonging to this plane is set as one normal line. The vector is stored in the normal vector table as a vector (step S12).
In the plane flag table, true flags corresponding to the number of vertices of the triangular mesh belonging to this plane are stored (step S13), and the process proceeds to step S16. At this time, the order in which the flag values are stored in the plane flag table is the same as when the vertex coordinates are registered in the vertex coordinate table.
On the other hand, if it is not a plane (NO in step S11), the normal vectors are successively stored in the normal vector table in association with all vertices on the same curved surface (step S14).
Further, a false flag is stored in the plane flag table in association with all vertices on the same curved surface (step S15), and the process proceeds to step S16.
The above steps S11 to S15 are performed on all the surfaces (step S16), and the created plane flag table and normal vector table are written in the data holding means 40. The normal vector compression means 30 is configured by these steps S11 to S16.

(3) Data expansion:
FIG. 7 is a block diagram illustrating a configuration of a data decompression apparatus that decompresses shape data compressed and stored with the data structure of the first embodiment. In the figure, the data decompression device includes vertex coordinate decompression means 110, normal vector decompression means 120, shape data (vertex coordinate table, plane flag table, normal vector table) held and decompressed shape model data in the shape DB. Data holding means 130 for storing data and control means 100 for controlling these means.
FIG. 8 is a flowchart showing a processing procedure when the shape data expanded by the data expansion device of the first embodiment is stored in the shape DB.
All vertex coordinates stored continuously in the vertex coordinate table are read from the data holding means 130 and written to the shape DB (step S20). By this step S20, the vertex coordinate expansion means 110 is configured.
A single normal vector is read from the normal vector table (step S21), the read normal vector is assigned as the normal vector of the vertex corresponding to the plane flag, and the shape DB is updated (step S22).
Next, the presence / absence of an unprocessed plane flag is checked. If there is no unprocessed plane flag (NO in step S23), the process ends.
On the other hand, when there is an unprocessed plane flag (YES in step S23) and the plane flag is true (YES in step S24), the process after step S22 is performed again, and the true flag is continuous. The shape DB is updated by assigning as a normal vector of the vertex corresponding to the plane flag.
If the plane flag is false (NO in step S24), the process from step S21 is performed again, the vertex normal vector for the new surface is assigned, and the shape DB is updated.
The normal vector expansion means 120 is configured by steps S21 to S24.

FIG. 9 is an example of data storage when an enumerated triangular mesh is used. FIG. 9 shows a vertex coordinate table storing 7 vertex coordinates from vertex [0] to vertex [6] and a normal vector table storing 5 normal vectors.
When the vertex [3], the vertex [4], and the vertex [5] are vertices on the plane, true is stored in the flag [3], the flag [4], and the flag [5] of the plane flag table. Since the normal vectors of the vertex [3], the vertex [4], and the vertex [5] on this plane are common, the X component [3] and the Y component [3] that are normal vectors at the vertex [3] And the Z component [3] are stored in the normal vector table, and the normal vectors of the other vertices [4] and [5] are not stored in the normal vector table.
When decompressing the shape data compressed as described above, since the flag [3], the flag [4], and the flag [5] are true when the plane flag table is referenced, the modulus of the vertex [3] is calculated. Only the X component [3], Y component [3], and Z component [3] that are line vectors are read, and for the vertex [4] and vertex [5], the X component [3], Y component [3], and Z Ingredient [3] is used.
By configuring the data compression device and the data decompression device as described above, it is possible to compress and decompress the triangular mesh in the n-dimensional space.
Further, when this data structure is used, the size of the plane flag table that only represents true / false is considerably smaller than the size of the normal vector table that represents the X component, the Y component, and the Z component. Since the rate of data reduction due to compression of the normal vector table is larger than the data increase due to the addition of data, the overall data size is reduced, and the space efficiency of a storage device such as a hard disk is improved.

<Embodiment 2>
(1) Data structure of shape data using index type triangular mesh:
FIG. 10 shows a data structure for storing an n-dimensional (2- to 4-dimensional) shape model using the indexed triangular mesh data structure of the present invention.
The data structure for storing the n-dimensional shape model includes a vertex coordinate table V in which n-dimensional vertex coordinates are stored, a normal vector table U in which n-dimensional normal vectors are stored, and an index to the vertex coordinate table V. Are stored in a vertex coordinate index table S, a normal vector index table T in which an index to the normal vector table U is stored, and a plane flag table P indicating true / false for each vertex.
In the vertex coordinate table V, the number of vertex coordinates (= nv) and nv vertex coordinates registered in the table are stored as non-overlapping coordinate values in the order of vertex coordinates V1 to vertex coordinates Vnv. , Each consisting of three coordinate values (x, y, z), and each coordinate value is subjected to floating point or vector quantization compression.
In the vertex coordinate index table S, the number of vertex coordinate indexes (= nvi) and nvi vertex coordinate indexes (indexes to the vertex coordinate table V storing the coordinate values of the vertices) are in the triangle set format in the order of S1 to Snvi. Stored in one of the triangle strip formats. The size of the vertex coordinate index table is the same as the number of all vertices.
In the plane flag table P, true and false are stored in the same manner as the order of the vertices registered in the vertex coordinate index table S depending on whether the vertex is a point on the plane or a point on the curved surface. Therefore, the size of the curved surface flag table is the same as the number of vertex coordinate indexes.
In the normal vector table U, the number of normal vectors (= nu) and nu normal vectors are stored as non-overlapping values in the order of the normal vector U1 to the normal vector Unu. Are composed of three components (x component, y component, z component), and each coordinate value is subjected to floating point or vector quantization compression.
In the normal vector index table T, the number of normal vector indexes (= nui) and nui normal vector indexes (indexes to the normal vector table U storing normal vector values) are T1 to Tnui. Stored in order.
Further, when one or more triangular meshes are on the same plane, a common normal vector is used, so that only an index to one normal vector is registered in the normal vector table T.

(2) Shape data compression:
Next, a method for storing predetermined n-dimensional shape data will be described using the data structure shown in the second embodiment (FIG. 10).
First, it is assumed that data representing an n-dimensional shape has already been databased (shape DB) by an n-dimensional shape processing apparatus.
Since the configuration of the data compression apparatus of the second embodiment is the same as that of the first embodiment, the description thereof is omitted (see FIG. 5).
FIG. 11 is a flowchart showing a processing procedure when the designated shape data in the shape DB is stored in the format of the data structure of FIG.
The vertex coordinates of all the vertices included in the specified shape data in the shape DB are written to the vertex coordinate table without duplication. Next, with reference to this vertex coordinate table, the vertex coordinate index to all vertex coordinates is obtained, and a vertex coordinate index table in which this vertex coordinate index is continuously stored is created. The coordinate index table is written into the data holding means 40 (step S30). In step S30, the vertex coordinate compression means 20 is configured.
It is determined whether or not the surface included in the specified shape data is a plane. If it is a plane (YES in step S31), a common normal vector of triangular meshes belonging to this plane is set as one normal line. The vector index is stored in the normal vector index table (step S32). For this normal vector index, normal vectors that do not overlap are registered in the normal vector table, and the table index at the time of registration is used.

In the plane flag table, true flags corresponding to the number of vertices of the triangular mesh belonging to this plane are stored (step S33), and the process proceeds to step S36. At this time, the order in which the flag values are stored in the plane flag table is the same as when the vertex coordinate index is registered in the vertex coordinate index table.
On the other hand, if it is not a plane (NO in step S31), the normal vector index is continuously stored in the normal vector index table in association with all vertices on the same curved surface (step S34). For this normal vector index, normal vectors that do not overlap are registered in the normal vector table, and the table index at the time of registration is used.
Further, a false flag is stored in the plane flag table in association with all vertices on the same curved surface (step S35), and the process proceeds to step S36.
The above steps S31 to S35 are performed on all the surfaces (step S36), and the created plane flag table, normal vector table and normal vector index table are written in the data holding means 40. The normal vector compression means 30 is configured by these steps S31 to S36.

(3) Data expansion:
Since the configuration of the data decompression device that decompresses the shape data compressed and stored with the data structure of the second embodiment is the same as that of the first embodiment, description thereof is omitted (see FIG. 7).
FIG. 12 is a flowchart showing a processing procedure when the shape data expanded by the data expansion device of the second embodiment is stored in the shape DB.
All the vertex coordinate indexes continuously stored in the vertex coordinate index table are read from the data holding means 130, and the vertex coordinate values stored at the position corresponding to the vertex coordinate index are retrieved with reference to the vertex coordinate table. Writing to the shape DB (step S40). By this step S40, the vertex coordinate expansion means 110 is configured.
A single normal vector index is read from the normal vector index table, and the normal vector value stored in the position corresponding to the normal vector index is retrieved with reference to the normal vector table (step S41). The extracted normal vector is assigned as the normal vector of the vertex corresponding to the plane flag, and the shape DB is updated (step S42).
Next, the presence / absence of an unprocessed plane flag is checked. If there is no unprocessed plane flag (NO in step S43), the process ends.
On the other hand, when there is an unprocessed plane flag (YES in step S43) and the unprocessed plane flag is true (YES in step S44), the processes after step S42 are performed again, and the true flag continues. The shape DB is updated by assigning it as the normal vector of the vertex corresponding to the plane flag in the case of
When the unprocessed plane flag is false (NO in step S44), the process from step S41 is performed again, the vertex normal vector for the new plane is assigned, and the shape DB is updated.
The normal vector expansion means 120 is configured by steps S41 to S44.
By configuring the data compression device and the data decompression device as described above, it is possible to compress and decompress the triangular mesh in the n-dimensional space.
Further, when this data structure is used, the data size is reduced and the space efficiency of a storage device such as a hard disk is improved.

<Embodiment 3>
(1) Data structure of shape data using reference type triangular mesh:
FIG. 13 shows a data structure for storing an n-dimensional (2- to 4-dimensional) shape model using the reference triangular mesh data structure of the present invention.
The data structure for storing the n-dimensional shape model includes a vertex coordinate table V in which n-dimensional vertex coordinates are stored, a normal vector table U in which n-dimensional normal vectors are stored, and an index to the vertex coordinate table V. Is stored in the vertex coordinate index table S, the normal vector index table T in which the index to the normal vector table U is stored, the vertex coordinate reference flag table FV indicating true / false for each vertex, and for each vertex. It consists of a normal vector reference flag table FU indicating true / false and a plane flag table P indicating true / false for each vertex.
In the vertex coordinate table V, the number of vertex coordinates (= nv) and nv vertex coordinates registered in the table are stored as non-overlapping coordinate values in the order of vertex coordinates V1 to vertex coordinates Vnv. , Each consisting of three coordinate values (x, y, z), and each coordinate value is subjected to floating point or vector quantization compression.
In the vertex coordinate index table S, the number of vertex coordinate indexes (= nvi) and nvi vertex coordinate indexes (indexes to the vertex coordinate table V storing vertex coordinate values) are stored in the order of S1 to Snvi. This vertex coordinate index table S is created only for vertices already registered in the vertex coordinate table.
In the vertex coordinate reference flag table FV, the number of reference flags (nvr) and nvr vertex coordinate reference flags are stored in the order of FV1 to FVnvr for each vertex in either a triangle set format or a triangle strip format. The number of vertex coordinate reference flags (nvr) is the same as the number of all vertices.

The coordinates of each vertex of the triangular mesh are obtained as follows.
First, the position of the vertex to be searched is searched for in the vertex coordinate reference flag table.
Next, the number of true flags from the top of this reference flag table to the found vertex position is counted, and the coordinate value of the vertex coordinate table corresponding to the position of this count value is obtained.
On the other hand, the number of false flags from the top of this reference flag table to the found vertex position is counted, the vertex coordinate index of the vertex coordinate index table corresponding to the position of this count value is obtained, and the vertex coordinate corresponding to this index Get the coordinate value of the table.
In the plane flag table P, true and false are stored in the same manner as the order of the vertices registered in the vertex coordinate index table S depending on whether the vertex is a point on the plane or a point on the curved surface. Therefore, the size of the curved surface flag table is the same as the number of vertex coordinate reference flags.
In the normal vector table U, the number of normal vectors (= nu) and nu normal vectors are stored as non-overlapping values in the order of the normal vector U1 to the normal vector Unu. Are composed of three components (x component, y component, z component), and each coordinate value is subjected to floating point or vector quantization compression.

In the normal vector index table T, the number of normal vector indexes (= nui) and nui normal vector indexes (indexes to the normal vector table U storing normal vector values) are T1 to Tnui. Stored in order. The normal vector index table T is created only for normal vectors already registered in the normal vector table.
The normal vector reference flag table FU stores the number of reference flags (nur) and ur normal vector reference flags in the order of FU1 to FUnur in the form of either a triangle set format or a triangle strip format for each vertex. The The number (nur) of normal vector reference flags is the same as the number of all vertices.
When the flag value of this normal vector reference flag is true, it indicates that the normal vector is stored in the normal vector table. When the flag value is false, the normal vector is stored in the normal vector index table. It shows that it was stored using.
Here, since the normal vectors of the vertices of the triangular mesh on the plane are common, only one normal vector is registered in either the normal vector table or the normal vector index table. In this case, the flag values of other vertices on the plane on which the normal vector is registered are registered as values other than true / false.
When finding the normal vector value from the normal vector table, the true flag value in the normal vector reference flag table is counted from the top of the table to the location corresponding to the vertex position to be obtained, and this count value is calculated as the normal vector. It is obtained by making an index into the table.
When the normal vector index is found from the normal vector index table, the false flag value in the normal vector reference flag table is counted from the top of the table to the location corresponding to the position of the vertex to be obtained, and this count value is calculated. It is obtained by setting an index to the normal vector index table.

(2) Shape data compression:
Next, a method for storing predetermined n-dimensional shape data will be described using the data structure shown in the third embodiment (FIG. 13).
First, it is assumed that data representing an n-dimensional shape has already been databased (shape DB) by an n-dimensional shape processing apparatus.
Since the configuration of the data compression apparatus of the third embodiment is the same as that of the first embodiment, the description of the configuration is omitted (see FIG. 5).
FIG. 14, FIG. 15 and FIG. 16 are flowcharts showing the processing procedure when storing the specified shape data in the shape DB in the format of the data structure of FIG.
It is determined whether or not the vertex coordinates on the surface included in the designated shape data in the shape DB are the vertex coordinates that are referred to for the first time. If the vertex coordinates are referred to for the first time (YES in step S50), the vertex of the vertex is determined. The coordinates are stored in the vertex coordinate table (step S51), the true flag is stored in the vertex coordinate reference flag table corresponding to the vertex (step S52), and the process proceeds to step S55.
On the other hand, in the case of vertex coordinates that are referred to for the second time and thereafter (NO in step S50), a vertex coordinate index to the already stored vertex coordinates is obtained, and this vertex coordinate index is stored in the vertex coordinate index table (step S53). ), A false flag is stored in the vertex coordinate reference flag table corresponding to the vertex (step S54), and the process proceeds to step S55.
Steps S50 to S55 are performed on all the vertices of the surface, and the created vertex coordinate table, vertex coordinate index table, and vertex coordinate reference flag table are written in the data holding means 40. The vertex coordinate compressing means 20 is configured in steps S50 to S55.
It is determined whether or not the surface included in the specified shape data is a plane. If it is a plane (YES in step S56), the normal vector of the vertex included in this plane is registered in the normal vector table. If it is not registered (YES in step S57), this normal vector is registered in the normal vector table (step S58), and a normal vector reference flag table corresponding to the vertex for this normal vector is registered. Is stored in the normal vector reference flag table corresponding to other vertices on the same plane (step S59), and the process proceeds to step S62.
On the other hand, when registered (NO in step S57), a normal vector index storing the same normal vector value as this normal vector is registered in the normal vector index table (step S60), and this normal vector is stored. False is stored in the normal vector reference flag table corresponding to the vertex for, and values other than true / false are stored in the normal vector reference flag table corresponding to other vertices on the same plane (step S61). Proceed to step S62.

In the plane flag table, true flags corresponding to the number of vertices of the triangular mesh belonging to this plane are stored (step S62), and if there are still unprocessed planes (YES in step S63), the process returns to step S50 and other Process the normal vector for the surface.
On the other hand, if the surface being processed is not a plane (NO in step S56), the normal vector of the vertex on the same curved surface is not yet registered in the normal vector table (YES in step S64). Is registered in the normal vector table (step S65), true is stored in the normal vector reference flag table corresponding to the vertex for this normal vector (step S66), and the process proceeds to step S69.
If registered (NO in step S64), a normal vector index storing the same normal vector value as this normal vector is registered in the normal vector index table (step S67). False is stored in the normal vector reference flag table corresponding to the vertex for (step S68), and the process proceeds to step S69.
Further, a false flag is stored in the plane flag table (step S69), and steps S64 to S70 are performed on all the vertices of the plane, and the process returns to step S63, and the created plane flag table and normal line are obtained. The vector table, normal vector index table, and normal vector reference flag table are written into the data holding means 40. The normal vector compression means 30 is configured by these steps S56 to S70.

(3) Data expansion:
Since the configuration of the data decompression device that decompresses the shape data compressed and stored with the data structure of the third embodiment is the same as that of the first embodiment, description thereof is omitted (see FIG. 7).
FIGS. 17 and 18 are flowcharts showing a processing procedure when shape data expanded by the data expansion apparatus of the third embodiment is stored in the shape DB.
If the vertex flag being processed in the vertex coordinate reference flag table in the data holding means 130 is true (YES in step S80), the position of the vertex being processed is obtained in the vertex coordinate table, and the coordinate value at that position is obtained. Reading and writing to the shape DB (step S81), the process proceeds to step S83. Here, the position of the vertex being processed in the vertex coordinate table is the number of true flags from the top of the vertex coordinate reference flag table to the vertex being processed.
On the other hand, if the flag of the vertex being processed is false (NO in step S80), the position of the vertex being processed is obtained in the vertex coordinate index table, and the coordinate value in the vertex coordinate table indicated by the vertex coordinate index at that position is read. The shape DB is written (step S82), and the process proceeds to step S83. Here, the position of the vertex being processed in the vertex coordinate table is the number of false flags from the top of the vertex coordinate reference flag table to the vertex being processed.
As described above, steps 80 to S82 are processed for the unprocessed vertex coordinate reference flag (step S83).
By these steps S80 to S83, the vertex coordinate expansion means 110 is configured.

Next, when the flag of the vertex being processed in the normal vector reference flag table in the data holding means 130 is true (YES in step S85), the normal vector table holding the normal vector for the vertex being processed , The normal vector value at that position is read (step S85), and the process proceeds to step S87. Here, the position in the normal vector table that holds the normal vector for the vertex being processed is the number of true flags from the head of the normal vector reference flag table to the vertex being processed.
On the other hand, if the flag of the vertex being processed is false (NO in step S84), the position in the normal vector index table holding the normal vector for the vertex being processed is obtained, and the normal vector index at that position indicates The normal vector value in the normal vector table is read (step S86), and the process proceeds to step S87. Here, the position in the normal vector index table that holds the normal vector for the vertex being processed is the number of false flags from the head of the normal vector reference flag table to the vertex being processed.
The read normal vector is assigned as the normal vector for the vertex being processed, and is written to the shape DB (step S87).
If there is no unprocessed plane flag (NO in step S88), the process ends.
On the other hand, if there is an unprocessed plane flag (YES in step S88), the plane flag of the vertex being processed is true and the plane flag of the next vertex is also true (YES in step 89), the other on the same plane In order to assign the read normal vector to the vertex, the next vertex is processed and the process returns to step S87.
However, if the plane flag of the vertex being processed is false or the plane flag of the next vertex is false (NO in step 89), the next vertex is advanced to assign a normal vector to the next vertex. The process returns to step S84.
The normal vector expansion means 120 is constituted by steps S84 to S89.
By configuring the data compression device and the data decompression device as described above, it is possible to compress and decompress the triangular mesh in the n-dimensional space.
Further, when this data structure is used, the data size is reduced and the space efficiency of a storage device such as a hard disk is improved.

<Embodiment 4>
Further, the above-described data compression device and data decompression device may be connected by a communication link, and the shape data obtained by compressing the n-dimensional shape model may be transferred from the data compression device to the data decompression device.
Here, examples of the communication link include a serial link (RS-232), a parallel link, a wireless link, an infrared link, and a network (local area network, wide area network, intranet, Internet).
For example, an n-dimensional shape processing apparatus including the above-described data compression apparatus or the function thereof and an n-dimensional shape processing apparatus including the data expansion apparatus or the function thereof are connected by a communication link, and the n-dimensional shape including the data compression apparatus or the function thereof is connected. The processing device creates shape data having the data structure shown in FIG. 4, FIG. 10, or FIG. 13 from the n-dimensional shape model, stores it in the data holding means, and sends the shape data through the communication link.
An n-dimensional shape processing apparatus including a data expansion apparatus or a function thereof can display an n-dimensional shape model obtained by expanding received shape data on a display device such as a display, or can perform shape processing on the model ( (See FIG. 19).

<Embodiment 5>
Furthermore, the present invention is not limited only to the above-described embodiments, but the functions of the devices of the above-described embodiments are each programmed, written in advance on a recording medium such as a CD-ROM, and mounted on a computer. It goes without saying that the object of the present invention can also be achieved by installing the CD-ROM or the like in a medium driving device such as a CD-ROM drive, and installing and executing these programs.
In this case, the program read from the recording medium itself realizes the above-described embodiment, and the program and the recording medium on which the program is recorded also constitute the present invention.
As a recording medium, a semiconductor medium (for example, ROM, nonvolatile memory card, etc.), an optical medium (for example, DVD, MO, MD, CD-R, etc.), a magnetic medium (for example, magnetic tape, flexible disk, etc.) Either may be sufficient.
Alternatively, the program stored in the storage device may be directly supplied from the server computer via a communication network such as the Internet. In this case, the storage device of this server computer is also included in the recording medium of the present invention.
Further, not only the above-described embodiment is realized by executing the loaded program, but the operating system or the like performs part or all of the actual processing based on the instruction of the program, and the above-described embodiment is performed by the processing. The case where the form is realized is also included.
Further, the above-described program is stored in a storage device such as a magnetic disk of a server computer, an execution instruction is received from a user's computer connected via a communication network such as the Internet, and the program is executed. When providing use by an ASP (Application Service Provider) that returns a message to the user's computer, the storage device of the server computer and its program are also included in the present invention.
Note that the present invention is not limited to the above-described embodiment, and various modifications and corrections can be made without departing from the scope of the present invention.

It is a figure for demonstrating the triangular mesh and normal vector which comprise a plane. It is a figure for demonstrating the triangle set format which is a representation format of a triangle mesh. It is a figure for demonstrating the triangle strip format which is a representation format of a triangle mesh. It is a figure for demonstrating the data structure of the shape data using the enumeration type | mold triangle mesh. It is a block diagram which shows the function structure of a data compression apparatus. It is a flowchart which shows the process sequence which compresses shape model data using the data structure of FIG. It is a block diagram which shows the function structure of a data expansion | extension apparatus. It is a flowchart which shows the process sequence which expand | extracts the shape data compressed using the data structure of FIG. It is a figure which shows the example of shape data expressed using the data structure of FIG. It is a figure for demonstrating the data structure of the shape data using an index type triangular mesh. It is a flowchart which shows the process sequence which compresses shape model data using the data structure of FIG. It is a flowchart which shows the process sequence which expand | extracts the shape data compressed using the data structure of FIG. It is a figure for demonstrating the data structure of the shape data using a reference type | mold triangle mesh. It is a flowchart (the 1) which shows the process sequence which compresses shape model data using the data structure of FIG. It is a flowchart (the 2) which shows the process sequence which compresses shape model data using the data structure of FIG. It is a flowchart (the 3) which shows the process sequence which compresses shape model data using the data structure of FIG. It is a flowchart (the 1) which shows the process sequence which expand | extracts the shape data compressed using the data structure of FIG. It is a flowchart (the 2) which shows the process sequence which expand | extracts the shape data compressed using the data structure of FIG. It is a figure for demonstrating the usage example of the n-dimensional shape processing apparatus using the function of the data compression apparatus of this invention, and a data expansion | extension apparatus.

Explanation of symbols

DESCRIPTION OF SYMBOLS 10 ... Control means, 20 ... Vertex coordinate compression means, 30 ... Normal vector compression means, 40 ... Data holding means, 100 ... Control means, 110 ... Vertex coordinate expansion means, 120 ... Normal vector expansion means, 130 ... Data holding means.

Claims (22)

  A data structure for storing shape data representing a shape model of an n-dimensional space with a triangular mesh, a vertex coordinate table storing n-dimensional vertex coordinates, and a normal vector storing n-dimensional normal vectors A data structure using an enumerated triangular mesh characterized by comprising a table and a plane flag table indicating true / false for each vertex.   2. The data structure according to claim 1, wherein the vertex coordinate table and the plane flag table are in a triangle set format or a triangle strip format.   Vertex coordinate compression that stores multiple vertex coordinates in a vertex coordinate table for multiple vertices on the same plane in a data compression device that compresses shape data representing a shape model of an n-dimensional space with a triangular mesh The normal vector at that vertex is stored in the normal vector table only for a single vertex among the vertices on the same plane, true for that vertex, and other on the plane A data compression apparatus comprising normal vector compression means for storing false in the plane flag table at the vertex of   In a data compression method for compressing shape data representing a shape model of an n-dimensional space with a triangular mesh, for a plurality of vertices on the same plane, a plurality of vertex coordinates are continuously stored in a vertex coordinate table. Only for a single vertex on the plane, the normal vector at that vertex is stored in the normal vector table, true for the vertex, false for the other vertices on the plane Is stored in the plane flag table.   4. A data decompression device for decompressing shape data compressed by the data compression device according to claim 3, wherein the vertex coordinates are decompressed by reading out all vertex coordinates stored in the vertex coordinate table continuously. When the true value is read from the coordinate extension means and the plane flag table, the plurality of vertex coordinates successively stored in the vertex coordinate table are regarded as the vertex coordinates of a plurality of vertices on the same plane, and the normal vector A data expansion apparatus comprising: normal vector expansion means for expanding a normal vector by assigning a single normal vector stored in a table as a normal vector of a plurality of vertices on the same plane.   A data decompression method for decompressing shape data compressed by the data compression method according to claim 4, wherein the vertex coordinates are decompressed by reading all vertex coordinates stored in the vertex coordinate table continuously, When reading true from the plane flag table, the vertex coordinates stored continuously in the vertex coordinate table are regarded as the vertex coordinates of a plurality of vertices on the same plane, and stored in the normal vector table A data decompression method comprising decompressing a normal vector by assigning a single normal vector as a normal vector of a plurality of vertices on the same plane.   A data structure for storing shape data representing a shape model of an n-dimensional space with a triangular mesh, a vertex coordinate table storing n-dimensional vertex coordinates, and a normal vector storing n-dimensional normal vectors A table, a vertex coordinate index table storing an index to the vertex coordinate table, a normal vector index table storing an index to the normal vector table, and a plane flag table indicating true / false for each vertex A data structure using an index type triangular mesh characterized by   8. The data structure according to claim 7, wherein the vertex coordinate index table and the plane flag table are in a triangle set format or a triangle strip format.   In a data compression apparatus that compresses shape data representing a shape model of an n-dimensional space with a triangular mesh, a plurality of vertices on the same plane are stored in a vertex coordinate table without duplication, and the plurality of vertex coordinate indexes are stored. Vertex coordinate compression means that continuously stores in the vertex coordinate index table, and normal vectors at that vertex are stored in the normal vector table only for single vertices on the same plane without duplication Normal vector compression means for storing the normal vector index in the normal vector index table, storing true for the vertex, and false for the other vertices on the plane in the plane flag table. A data compression apparatus comprising:   In a data compression method that compresses shape data that represents a shape model of an n-dimensional space with a triangular mesh, it is stored in the vertex coordinate table without duplication, and the vertex coordinate index is stored in the vertex coordinate index table in succession. The normal vector at that vertex is stored in the normal vector table without duplication only for a single vertex among the vertices on the same plane, and the normal vector index is stored in the normal vector index table. A data compression method, wherein true is stored for the vertex and false is stored for another vertex on the plane in a plane flag table.   10. A data decompression device for decompressing shape data compressed by the data compression device according to claim 9, wherein all vertex coordinates stored successively in the vertex coordinate index table are represented by the vertex coordinate index for the vertex. Vertex coordinate expansion means for obtaining and reading out vertex coordinates from the vertex coordinate table and extending the vertex coordinates, and when reading true from the plane flag table, a plurality of vertex coordinates stored successively in the vertex coordinate index table Are regarded as the vertex coordinates of a plurality of vertices on the same plane, and a single normal vector index stored in the normal vector index table is assigned as a normal vector index of a plurality of vertices on the same plane. Normal vector from the normal vector table by line vector index Data expansion apparatus, comprising a normal vector decompressing means for decompressing the normal vector by extracting.   A data decompression method for decompressing shape data compressed by the data compression method according to claim 10, wherein all vertex coordinates stored successively in the vertex coordinate index table are represented by the vertex coordinate index for the vertex. When a vertex coordinate is obtained from the vertex coordinate table and read out, the vertex coordinate is expanded, and true is read out from the plane flag table, a plurality of vertex coordinates successively stored in the vertex coordinate index table are stored on the same plane. And assigning a single normal vector index stored in the normal vector index table as a normal vector index of a plurality of vertices on the same plane, and the normal vector index By extracting the normal vector from the normal vector table Data decompression method characterized by stretching the normal vector.   A data structure for storing shape data representing a shape model of an n-dimensional space with a triangular mesh, a vertex coordinate table storing n-dimensional vertex coordinates, and a normal vector storing n-dimensional normal vectors Table, vertex coordinate index table storing indexes to vertex coordinate table, normal vector index table storing indexes to normal vector table, and vertex coordinate reference flag table indicating true / false for each vertex And a normal vector reference flag table indicating true / false for each vertex, and a plane flag table indicating true / false for each vertex, a data structure using a reference type triangular mesh.   14. The data structure according to claim 13, wherein the vertex coordinate reference table, the normal vector reference flag table, and the plane flag table are in a triangle set format or a triangle strip format.   In a data compression device that compresses shape data that represents a shape model of an n-dimensional space with a triangular mesh, vertex coordinates that are referenced for the first time with respect to multiple vertices on the same plane are stored in the vertex coordinate table. Then, true is stored in the vertex coordinate reference flag table corresponding to the plurality of vertices, and the vertex coordinate index is stored in the vertex coordinate index table for the vertex coordinates that are referred to for the second time and thereafter, and the vertex coordinates are corresponding to the plurality of vertices. For the vertex coordinate compression means that stores false in the vertex coordinate reference flag table and the normal vector that is referenced for the first time, the normal vector at that vertex is only applied to a single vertex among the vertices on the same plane. Store in the normal vector table, store true in the normal vector reference flag table corresponding to the vertex, and will be referenced the second time and thereafter For normal vectors, only normal vertices out of vertices on the same plane are stored in the normal vector table, and the normal vector index is stored in the normal vector index table. Normal vector compression means for storing false in the normal vector reference flag table corresponding to the vertex and storing true in the plane flag table for the vertex corresponding to the single normal vector. A data compression apparatus comprising:   In a data compression method that compresses shape data representing a shape model of an n-dimensional space with a triangular mesh, vertex coordinates that are referenced for the first time for multiple vertices on the same plane are stored in the vertex coordinate table. Then, true is stored in the vertex coordinate reference flag table corresponding to the plurality of vertices, and the vertex coordinate index is stored in the vertex coordinate index table for the vertex coordinates that are referred to for the second time and thereafter, and the vertex coordinates are corresponding to the plurality of vertices. Stores false in the vertex coordinate reference flag table, and for the normal vector that is referenced for the first time, the normal vector at that vertex is stored in the normal vector table only for a single vertex on the same plane. Stores true, stores true in the normal vector reference flag table corresponding to the vertex, and stores normal vectors that are referenced for the second and subsequent times. Stores the normal vector at that vertex only in a single vertex among the vertices on the same plane, stores the normal vector index in the normal vector index table, A data compression method, wherein false is stored in a normal vector reference flag table corresponding to the vertex, and true is stored in a plane flag table for a vertex corresponding to the single normal vector.   16. A data decompression device for decompressing shape data compressed by the data compression device according to claim 15, wherein when the flag of the vertex coordinate reference flag table corresponding to the vertex being processed is true, the vertex of the vertex When the coordinates are read from the vertex coordinate table and the flag of the vertex coordinate reference flag table corresponding to the vertex is false, the coordinate value indicated by the vertex coordinate index of the vertex coordinate index table corresponding to the vertex is the vertex coordinate table If the flag in the normal vector reference flag table of the vertex on the plane is true, the normal vector corresponding to the vertex is read from the normal vector table, When the flag of the normal vector reference flag table of the vertex is false, the normal vector corresponding to the vertex is calculated Normal vector expansion means for expanding a normal vector by assigning the normal vector to a plurality of vertices on the same plane by reading from the normal vector table indicated by the normal vector index of the vector index table A data decompression device characterized by that.   17. A data decompression method for decompressing shape data compressed by the data compression method according to claim 16, wherein if the flag of the vertex coordinate reference flag table corresponding to the vertex being processed is true, the vertex of the vertex When the coordinates are read from the vertex coordinate table and the flag of the vertex coordinate reference flag table corresponding to the vertex is false, the coordinate value indicated by the vertex coordinate index of the vertex coordinate index table corresponding to the vertex is the vertex coordinate table The vertex coordinates are expanded by reading from the normal vector, and when the normal vector reference flag table flag of the vertex on the plane is true, the normal vector corresponding to the vertex is read from the normal vector table and the normal of the vertex is read. If the flag in the vector reference flag table is false, the normal vector corresponding to the vertex is set as the normal vector index. By reading from the normal vector table normal vector index table points, data decompression method characterized by stretching the normal vector by assigning a normal vector to a plurality vertices on the same plane.   14. The data structure according to claim 1, wherein the vertex coordinate table and the normal vector table are subjected to floating point expression or vector quantization compression.   An n-dimensional shape model processing apparatus for processing a shape model of an n-dimensional space, wherein at least one of the data compression apparatus according to claim 3, 9 or 15 and the data expansion apparatus according to claim 5, 11 or 17 is provided. The data compression device generates and transmits shape data obtained by compressing an n-dimensional shape model, and the data decompression device decompresses the received shape data to generate an n-dimensional shape model. An n-dimensional shape model processing apparatus.   The function of the data compression device according to claim 3, 9 or 15, the function of the data expansion device according to claim 5, 11 or 17, or the n-dimensional shape model processing device according to claim 20 A program for executing functions.   A computer-readable recording medium on which the program according to claim 21 is recorded.

Images