Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-04-22
2002-09-17
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06452596
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of computer graphics and, in particular, to methods for compressing, storing and processing data representative of surfaces.
BACKGROUND OF THE INVENTION
Polygonal surfaces form one of the major representations of three dimensional geometric models. Such surfaces consist of a plurality of polygons, which are cycles of vertices, whose coordinates are usually expressed in a local coordinate system. Such polygonal surfaces may be used for generating various images, pictures, and animations, and may also be used in CAD systems, in scientific visualization systems, and in medical imaging systems, as well as in manufacturing, architectural, geographic information, warfare simulation, robotics and entertainment industries systems. In particular, polygons (especially, triangles) are required for generating three-dimensional renderings using available graphics architecture.
In general, polyhedral surfaces, such as surfaces represented as triangles, are commonly represented in a computer memory with a “vertex array” (with three floating point numbers per vertex) and a “triangle array” (with three indices into the vertex array per triangle). Very often this representation allows for the surface to be non-manifold, i.e., to have either one or both of singular vertices or edges. A vertex is singular if its star (the set of triangles incident to the vertex) is not topologically equivalent (continuously deformed) to a closed disk. An edge is singular if it is shared by more than two triangles. However, many geometric algorithms and operations, such as compression, simplification, smoothing, and deformation operations, require the surface to be manifold.
There are a number of known algorithms that operate on polygonal surfaces including, but not limited to, the following. A first type of algorithms are those that produce two dimensional graphics for display on computer screens, for printing, or for other purposes. These algorithms are typically implemented using both software and hardware components. A second type of algorithms are those that compute surface characteristics (e.g. curvature, area). A third type of algorithms are those used for filtering, such as smoothing algorithms and other filtering algorithms. A fourth type of algorithms are those that perform finite element analysis for various engineering applications. A fifth type of algorithms are those that simplify surfaces, either because the surfaces are too large for available hardware to process in a reasonable period of time, or for efficiency purposes. In this context “simplifying” means approximating the surface with another surface that contains fewer polygons. An example of such a simplification algorithm is described in commonly assigned U.S. Patent Application entitled “Surface Simplification Preserving a Solid Volume and Respecting Distance Tolerances”, Ser. No. 08/742,641, filed Nov. 1, 1996, by André P. Guéziec. A sixth type of algorithms are those used for surface subdivision, wherein surface subdivision is considered to be a technique for introducing new polygons into the surface so as to produce a result that resembles a smooth surface. A seventh type of algorithms are those used for surface compression, wherein surface compression is considered to be a technique to provide an efficient encoding of polygons defining the surface. An example of a surface compression algorithm is described by Rossignac et al. in U.S. Pat. No. 5,825,369 entitled “Compression Of Simple Geometric Models Using Spanning Trees.” In the Rossignac et al. method, the vertices of the mesh are organized as a spanning forest, the spanning forest being composed of one or more rooted trees, each rooted tree spanning the vertices of one connected component of the manifold mesh. The spanning forest can be described by a v_father array, with j=v_father[i] indicating that the j-th vertex is the father of the i-th vertex, with i and j being indices corresponding with the order of traversal of the vertex forest. If the i-th vertex is the root of a tree in the vertex forest, then v_father[i]=i. Most available algorithms of the foregoing categories, with the exception of the first category (A), require that the surface be a manifold surface. To understand the concept of a manifold surface one can consider a solid object, and the surface bounding that solid object. The bounding surface is a manifold surface, together with surfaces obtained after cutting a series of holes in the original surface. A precise definition of a surface, and of a manifold surface, are given below.
The following three situations can arise when an algorithm that requires that the surface be a manifold surface is instead presented with a surface that is not a manifold surface. First, the algorithm can include a method for rejecting the presented surface. However, there is an additional cost incurred in designing and implementing the input surface rejection method. Second, the algorithm may not recognize that the presented surface is a non-manifold surface, but safeguards allow the computer program implementing the algorithm to terminate properly, without performing the original function of the algorithm. In this case there is an additional cost incurred in designing and implementing the safeguards. Third, the computer program implementing the algorithm may simply terminate abnormally. This latter case is undesirable for a number of reasons.
Conventional methods for converting non-manifold surfaces to manifold surfaces include three techniques, described by Szeliski et al. “Curvature and Continuity Control in Particle-Based Surface Models”, Proceedings of SPIE “Geometric Methods in Computer Vision II”, Vol 2031-15, July 1993, pp.172-181, by Welch and Witkin “Free-Form Shape Design Using Triangulated Surfaces”, Proceedings of ACM SIGGRAPH'95, July 1994, pp.247-256, and by Butlin et al. “CAD Data Repair”, in 5th International Meshing Roundtable, Pittsburgh, Pa., October 1996.
The technique of Szeliski et al. builds a new polygonal surface from an existing surface by defining a collection of point samples, using point repulsion methods to distribute the points evenly. Subsequently, a surface triangulation of the remaining points is found by extending the techniques of Delaunay triangulations to surfaces. Delaunay triangulations are discussed by O'Rourke in “Computational geometry in C”, Cambridge University Press, 1994. The method of Szeliski et al. produces surfaces that are manifolds, but at the expense of discarding the original surface geometry (vertex positions) and connectivity (triangles or polygons), by defining entirely new vertices and triangles. Furthermore, the triangulation method employed is a heuristic method that most likely does not apply in all cases.
The technique of Welch et al. builds a polygonal surface starting from a simple surface, by applying a series of surface operations that consist of adding, deleting, or morphing a portion of the surface. This technique uses methods similar to Szeliski et al. for building triangulations of the surface points. Surface or mesh cutting techniques are also used, but the mesh cutting techniques cut only along simple curves, and are not capable of multiplying vertices at complex curve intersections.
The technique of Butlin et al. is directed towards the conversion of CAD data. This technique is interactive and requires user assistance, and automatic methods for detecting and converting vertices where non-manifold situations occur are not described.
An improved technique for converting a non-manifold surface to a manifold surface is described in commonly assigned U.S. patent application Ser. No. 08/840,001, filed Apr. 24, 1997, entitled “Method to Convert Non-Manifold Polyhedral Surfaces into Manifold Surfaces”, by André Guéziec and Gabriel Taubin, the disclosure of which is incorporated by reference herein in its entirety.
Turning now to the compression of polygonal surfaces, which is of most interest to the teachings of this inven
Bossen Frank J
Gueziec Andre P
Silva Claudio
Taubin Gabriel
Brier Jeffery
Percello, Esq. Louis J.
Perman & Green LLP
Yang Ryan
LandOfFree
Methods and apparatus for the efficient compression of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for the efficient compression of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for the efficient compression of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2884554