 |
|
|
|
|
|
 Title: |
US5905507:
Compression of geometric models using spanning trees
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Rossignac, Jarek Jaroslaw Roman; Cronton-on-Hudson, NY
Taubin, Gabriel; Hartsdale, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1999-05-18
/ 1996-07-30
|
| Application Number: |
US1996000685422
|
| IPC Code: |
Advanced:
G06T 9/40;
Core:
more...
IPC-7:
G06F 15//00;
|
| ECLA Code: |
G06T9/40;
|
| U.S. Class: |
Current:
345/440;
Original:
345/440;
|
| Field of Search: |
345/443,440,441,118,121
|
| Priority Number: |
| 1996-07-30 |
US1996000685422 |
| 1996-01-16 |
US1996000010045P |
|
| Abstract: |
A computer system stores and transmits compressed triangular meshes. The computer uses a data structure that represents a triangular mesh in n-dimensional space. The data structure has a table of vertex runs, a table of triangle runs, zero or more marching records, which provide the connectivity information of the triangular mesh. The data structure also has zero or more associated data records that include the geometric information of the triangular mesh. The table of triangle runs and the marching record have information that describes how to construct a triangular mesh (therefore, the polygon vertices and the boundary edges). The table of vertex runs describes a vertex spanning tree that provides additional connectivity information to construct the triangular mesh from the polygon. The associated data record determines the exact position of the triangular mesh in space. The system also includes ways for creating this data structure from a triangular mesh, transmitting this information between computers, and compressing and decompressing this transmitted information.
|
| Attorney, Agent or Firm: |
Percello, Louis J. ;
|
| Primary / Asst. Examiners: |
Nguyen, Phu K.;
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Parent Case: |
CROSS-REFERENCE TO RELATED APPLICATIONS
The present application claims priority to co-pending U.S. provisional application 60/010,045, filed on Jan. 16, 1996 and entitled "Compression of Geometric Models Using Spanning Trees".
|
| Family: |
Show 8 known family members
|
First Claim:
Show all 32 claims |
We claim:
1. A data structure stored in a memory of a computer system for representing the connectivity of a connected n-dimensional triangular mesh, the data structure comprising:
- a table of vertex runs with one or more vertex run records that describe a vertex spanning tree connecting two or more vertices on the triangulated mesh, each vertex run record having a vertex last field, a length of vertex run field, and a vertex leaf field;
- a table of triangle runs having one or more triangle run records, each triangle run record having a triangle leaf field indicating if a triangle is a leaf of a triangle run of a triangle tree, a length of triangle run field indicating a length of the the triangle run, and one or more jump information fields each having information about a jump edge in the triangle run, the triangle run being a triangulated polygon cut from the triangular mesh by cutting the triangular mesh along the vertex spanning tree; and
- a marching record having one or more triangle root fields with a triangle root and a sequence of marching commands describing how to construct the triangles in the triangulated polygon with the triangle root as a root.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 19 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
|
| Other References: |
J. Neider et al., "Open GL Programming Guide," Addison-Wesley Publishing Company, Jun. 1993, pp. 34-37.
C.W. Brown et al., "Graphics File Formats," Manning Publishing Company, 1995, pp. vii-218.
J. D. Foley et al., "Computer Graphics" 2nd Edition, Addison-Wesley Publishing Company, Nov. 1992, pp. 471-477.
R. E. Tarjan, "Data Structures and Network Algorithms," Society for Industrial and Applied Mathematics, Philadelphia, PA 1983, pp. 14-21.
M. Deering, "Geometry Compression," ACM-0-89791-701 Apr. 1995, Computer Graphics Proceedings, Annual Conference Series, 1995.
|
|
 Nominate this for the Gallery...
|
|
