Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-03-28
2004-09-14
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06791543
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a structured polygonal mesh data forming method and apparatus for approximating a 3D surface shape with a polygonal mesh constituted by a plurality of polygons and forming 2D structured geometry and property data applicable of efficient compression/decompression from the connectivity information of the polygonal mesh, and a storage medium.
BACKGROUND OF THE INVENTION
In general, an object in a 3D space is represented by a set of 3D coordinates of points on the surface of the object and attribute data such as textures on the respective points. In conventional methods of reducing data amount, curvatures at sample points or changes in shape when sample points are deleted are obtained, and the total number of data is decreased by subsampling sample points in flat areas where the curvatures are small or areas where changes in shape are small, thereby reducing the amount of data.
Data used for 3D computer graphics is represented by using a combination of the coordinates of a point in a 3D space and attribute data of the point as a basic element. The image or video sensed by a digital camera or video camera is represented as a set of texture data that do not explicitly contain the position information of each sampling point by determining a scanning order for the data sampled at lattice points set on a square or rectangle imaging plane at equal intervals in the vertical and horizontal directions. Such data is called structured data and is greatly compressed by a standard image/video encoding means such as JPEG or MPEG.
In communication of 3D visual information, however, demands have arisen for improvements in convenience, e.g., developing a system applicable of moving a viewpoint according to user's intention or allowing the user to feel a sense of depth and transmitting the data necessary for the system with sufficient quality within a short time so the user will not feel any stress.
SUMMARY OF THE INVENTION
The present invention has been made to solve the above problems and is characterized by having the following arrangement.
There is provided a structured polygonal mesh data forming method of approximating a 3D surface shape with a polygonal mesh constituted by a plurality of polygons and forming 2D structured geometry and property data applicable of efficient compression/decompression from connectivity information of the polygonal mesh, comprising:
the step of forming a vertex assignment table by assigning vertices constituting the polygonal mesh to nodes as lattice points on a 2D coordinate system to maintain neighboring relations among adjacent polygons on a 2D lattice plane; and
the step of forming the 2D structured geometry and property data from the vertex assignment table that indicates correspondences between the respective vertices and the respective nodes on the 2D lattice plane,
wherein the step of forming the vertex assignment table performs an assigning processing which allows to assign a vertex of the polygon mesh to a plurality of nodes on the 2D coordinate system. This method will be referred to as the first aspect of the present invention hereinafter.
In the above structured polygonal mesh data forming method, the 2D structured geometry and property data preferably comprises
geometry data consisting of position coordinate data of the respective assigned polygon vertices,
property data including color and normal vector information of each vertex, and
a connectivity map which is information about connection between the respective vertices.
Preferably, the above structured polygonal mesh data forming method further comprises the coding step of coding the 2D structured data.
In the above structured polygonal mesh data forming method, the coding step is preferably the step of encoding the connectivity map, which is obtained from the vertex assignment table, in lossless compression.
In the above structured polygonal mesh data forming method, the polygon preferably consists of connected triangles.
In the above structured polygonal mesh data forming method, the color information is preferably color information for reproducing a color of each vertex.
Preferably, the above structured polygonal mesh data forming method further comprises a structuring step of converting the vertex assignment table into a connectivity map.
In the above structured polygonal mesh data forming method, the structuring step is preferably the step of assigning a polygon vertex to a plurality of nodes, if the plurality of nodes with the same assigned vertex are linked on the 2D coordinate system, selecting one representative node from the nodes with the same vertex, and representing positions of the nodes with the same vertex which are not selected as the representative node by relative positions to the representative node, thereby structuring the connectivity information.
Preferably, the above structured polygonal mesh data forming method further comprises the step of compressing the 2D structured data.
In addition, there is provided a structured polygonal mesh data forming apparatus for approximating a 3D surface shape with a polygonal mesh constituted by a plurality of polygons and forming 2D structured geometry and property data applicable of efficient compression/decompression from connectivity information of the polygonal mesh, comprising:
means for forming a vertex assignment table by assigning vertices of the polygonal mesh to nodes as lattice points on a 2D coordinate system to maintain neighboring relations among adjacent polygons on a 2D lattice plane; and
means for forming the 2D structured geometry and property data from the vertex assignment table which indicates correspondences between the polygon vertices and the nodes on the 2D lattice plane,
wherein the means for forms the vertex assignment table performs an assigning processing which allows to assign a vertex of the polygon mesh to a plurality of nodes on the 2D coordinate system.
Furthermore, there is provided a computer-readable memory storing program codes for approximating a 3D surface shape with a polygonal mesh constituted by a plurality of polygons and forming 2D structured geometry and property data applicable of efficient compression/decompression from connectivity information concerning the polygonal mesh, the program codes comprising:
a code for executing the step of forming a vertex assignment table by assigning polygon vertices constituting the polygonal mesh to nodes as lattice points on a 2D coordinate system to maintain neighboring relations among adjacent polygons on a 2D lattice plane; and
a code for executing the step of forming the 2D structured geometry and property data from the vertex assignment table that indicates correspondences between the respective vertices and the respective nodes on the 2D lattice plane,
wherein the code for executing the step of forming the vertex assignment table is a code for executing an assigning processing which allows to assign a vertex of the polygon mesh to a plurality of nodes on the 2D coordinate system.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.
REFERENCES:
patent: 6078331 (2000-06-01), Pulli et al.
patent: 6342884 (2002-01-01), Kamen et al.
patent: 09-171568 (1997-06-01), None
Deering, “Geometry Compression,” Proceedings of the 22nd annual conference on Computer Graphics and Interactive Techniques, pp. 13-20, 1995.
Taubin, et al., “Geometry Coding and VRML”, Proceedings of IEEE, vol. 86, No. 6, pp. 1228-1243, 1998.
Takayuki Kawashima et al., “Geometrical Data Compression with Structuring the Polygonal Mesh”, Faculty of Science and Technology, Sophia University.
Eiichi Inoue et al., “Compression of 3D Shape Data using SA-WT”, 1999 IEEE International Conference on Image Processing, 27AP3.1, 1999.
Henry Sowizral, et al., “The JAVA 3D API Specification”, pp. 379-412.
Arnold Adam
Burns Doane Swecker & Mathis L.L.P.
Kawanaka Akira
Zimmerman Mark
LandOfFree
Forming method for structuring polygonal mesh data and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Forming method for structuring polygonal mesh data and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forming method for structuring polygonal mesh data and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3224667