Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-01-14
2001-02-06
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06184897
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of computer graphics and, in particular, to methods for representing, encoding and decoding sequences of changes in three dimensional (3D) geometric models.
BACKGROUND OF THE INVENTION
Although modeling systems used in Mechanical Computer Aided Design and in animation are expanding their geometric domain to include free form surfaces, polygonal models remain the primary 3D representation used in the manufacturing, architectural, Geographic Information Systems, geoscience, and entertainment industries. Polygonal models are particularly effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mock-up applications involving complex Computer Aided Design (CAD) models.
Since methods are known in the prior art for easily and efficiently triangulating arbitrary polygonal faces, it is sufficient to consider geometric models which are defined by triangular meshes. For example, a method to triangulate the faces of a polygonal model is described by Ronfard, R. and Rossignac, J. in “Triangulating multiply-connected polygons: A simple, yet efficient algorithm”, Computer Graphics Forum, V. 13, No. 3, 1994, pp. 281-292.
A “triangular mesh” is defined by the position of its vertices (“geometry”), which are N-dimensional vectors, by the association between each triangle and its sustaining vertices (“connectivity”), and by colors, normals, and texture coordinates (“properties”), which do not affect the geometry, but influence the way it is shaded.
A triangular mesh with V vertices and T triangles is typically represented in the prior art (for example, as described by Foley et.al. in “Computer Graphics: Principles and Practice”, Addison-Wesley, 1990) by a “vertex positions array”, a “triangle array”, and (optionally) one or more “property arrays”. The position of each vertex of the triangular mesh is represented in the vertex positions array by N floating point coordinates. Each triangle of the triangular mesh is represented in the triangle array by three indices to the vertex positions array.
A triangular mesh may also have continuous or discrete properties, such as colors, normals, and texture coordinates, associated with its vertices or triangles. To model various discontinuous phenomena on the triangular mesh, properties can also be associated with each vertex of each triangle. These (triangle,vertex) pairs are called “corners”, and the corresponding properties “corner” properties. These corner properties are represented in the optional property arrays.
Triangular meshes are typically classified (for example, as described by Hoffmann, C., “Geometric and Solid Modeling”, Morgan Kaufmann, 1989) as manifolds and non-manifolds. An “edge” of a triangular mesh is a pair of vertices in a triangle, without taking into account the order of the two vertices within the edge. The two vertices of an edge are called endpoints of the edge. The triangle is said to be incident to the edge, and the edge incident to the vertices. Two triangles sharing an edge are said to be adjacent. Two edges sharing a vertex are said to be adjacent. The set of triangles that share a vertex are referred to as the star of the vertex. The number of triangles in the star of a vertex is referred to herein as the valence of the vertex. The link of a vertex is obtained by connecting all adjacent edges bounding the star of the vertex and discarding from the list of edges so formed the edges incident to the vertex. If the link has one component, and is not intersecting itself, the vertex is said to be a regular vertex, otherwise it is referred to as a singular vertex. For a regular vertex, if the link is closed, meaning that the first end point of the first edge of the link is the same as the last end point of the last edge, the vertex is an interior regular vertex, otherwise it is a boundary vertex.
The edges of a triangular mesh define a partition of the vertices of the triangular mesh into one or more disjoint subsets of vertices such that the two endpoints of each edge of the triangular mesh belong to the same subset. This partition of the vertices of the triangular mesh defines an associated partition of the triangles of the triangular mesh into one or more disjoint subsets of triangles, which are in one to one correspondence with the subsets of vertices. The subset of triangles associated with a subset of vertices is composed of all the triangles of the triangular mesh with vertices in the subset of vertices. If the triangular mesh has properties, the partition of the vertices also defines corresponding partitions of the properties in a similar manner. Each subset of vertices, the corresponding subset of triangles, and (optionally) the corresponding subsets of properties define a new triangular mesh which is called a “connected component” of the triangular mesh.
A triangular mesh is referred to as a “manifold triangular mesh” if the following two conditions are satisfied: 1) if any two triangles of the triangular mesh intersect, the intersection is either a common vertex or a common edge; and 2) all the vertices of the triangular mesh are regular vertices, which implies that each edge of the triangular mesh is shared by at most two triangles.
An edge of a manifold triangular mesh may have either one or two incident triangles. An “interior edge” is an edge with two incident triangles. A “boundary edge” is an edge with one incident triangle. It is known in the prior art that the endpoints of the boundary edges of a manifold triangular mesh are boundary vertices, and that the boundary vertices of a manifold triangular mesh are endpoints of the boundary edges. The boundary edges of a manifold triangular mesh can be partitioned into one or more disjoint subsets of boundary edges referred to as “boundaries”, such that two boundary edges which share a boundary vertex as a common endpoint belong to the same boundary. It is also known in the prior art that each boundary vertex of a manifold triangular mesh is the endpoint of exactly two boundary edges.
Since methods are known in the prior art for converting non-manifold polygonal models into manifold polygonal models, it is sufficient to consider triangular meshes which are manifolds. A method to convert non-manifold polygonal models into manifold polygonal models is described in “Method to Convert Non-Manifold Polyhedral Surfaces into Manifold Surfaces”, U.S. patent application Ser. No. 08/840,001, filed on Apr. 24, 1997, by A. Gueziec and G. Taubin, herein incorporated by reference in its entirety.
A manifold triangular mesh can be changed or edited to produce a new manifold triangular mesh, by modifying either its geometry, its connectivity, or both its geometry and its connectivity. Optionally, the change may also involve a modification of the properties of the manifold triangular mesh.
It is known in the prior art (described by Massey, W. S., in “Algebraic Topology: An Introduction”, Hartcourt, Brace & World, Inc., New York, 1967) that the following types of changes on a manifold triangular mesh , referred to herein as “mesh surgery operations”, produce a new manifold triangular mesh:
1) cut the manifold through a subset of its edges; 2) identify, or stitch, adjacent pairs of boundaries edges; 3) delete one or more connected components; 4) add one or more connected components; and 5) move vertices and (optionally) properties.
Of most interest to the teaching of this invention is to represent sequences of mesh surgery operations applied to an initial manifold triangular mesh in compressed form for efficient storage and transmission, and efficient decompression methods. For the purposes of this disclosure a manifold triangular mesh followed by a sequence of mesh surgery operations is referred to as “changing mesh”.
One significant advantage of applying mesh surgery operations to manifolds is that the boundaries are closed 1-D manifolds. This property results in a simplified description and encoding of some operations, such as adding a surface and other stitch
Gueziec Andre
Taubin Gabriel
International Business Machines - Corporation
Nguyen Phu K.
Perman & Green LLP
Sbrollini Jay P.
LandOfFree
Compressed representation of changing meshes and method to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compressed representation of changing meshes and method to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed representation of changing meshes and method to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609311