Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-01-14
2001-10-23
Nguyen, Tan (Department: 3661)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06307551
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of computer graphics and, in particular, to methods for building surface levels of details suitable for fast transmission over computer networks.
BACKGROUND OF THE INVENTION
Polygonal surfaces are widely used for representing three dimensional (3-D) geometric models. Such surfaces consist of a plurality of polygons, which are cycles of vertices, whose coordinates are generally expressed in a modeling space coordinate system. The polygonal surfaces may be used for generating pictures and animations, and may also be used in Computer Aided Design (CAD) systems, in scientific visualization, and in medical imaging.
However, typical polygonal surfaces may be so large that real time interaction is impossible using current hardware, or that the transmission of the data describing the surfaces over computer networks is unacceptably slow. Providing different resolutions, or levels of details (LODs), of such polygonal surfaces overcomes this problem as it is possible to use an appropriate lower LOD for a given task. Such LODs may be generated using a software modeling tool or by using algorithms that automatically produce LODs. One example of such algorithms is described in commonly assigned U.S. Pat. No. 5,448,686 “Multi-Resolution Graphic Representation Employing at Least One Simplified Model for Interactive Visualization Applications”, by P. Borrel and J. Rossignac, the disclosure of which is incorporated by reference herein in its entirety. Another example of a LOD generation algorithm is described in commonly assigned U.S. patent application Ser. No. 08/742,631 filed Nov. 1, 1996, “Surface Simplification Preserving a Solid Volume and Respecting Distance Tolerances”, by A. Gueziec, herein incorporated by reference in its entirety. Reference in this regard may also be had to a publication entitled “Surface Simplification with Variable Tolerance”, A. Gueziec, Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery, pages 132-139, Baltimore, Md., November 1995.
Such polygonal surfaces and LODs of polygonal surfaces are increasingly exchanged over computer networks. When transmitting several LODs of the same polygonal surface, it is desirable to avoid transmitting duplicate information.
In addition, when transmitting the data through a computer network, one may wish to progressively display a surface such that while the computer is busy preparing high resolution images, lower resolution images are quickly available for display and interaction using simplified models.
Conventional methods for producing levels of details from polygonal surfaces include four techniques, described by Hoppe “Progressive Meshes”, Proceedings of ACM SIGGRAPH'93, pp. 99-108, by Eck et al. “Multi-resolution analysis of arbitrary meshes”, Proceedings of ACM SIGGRAPH'95, pp. 173-182, by Popovic et al. “Progressive Simplicial Complexes”, Proceedings of ACM SIGGRAPH'97, pp. 217-224, and by De Floriani et al. “Building and Traversing a Surface at Variable Resolution”, IEEE Visualization'97, pp. 103-110. The technique of Hoppe builds a progressive mesh representation that consists of a description of the transition from a simplified mesh to the original mesh. Hoppe sends a succession of “vertex splits”, in order to undo the edge collapses that he performed earlier. For each of these edge splits, he must specify the indices in the original mesh of the simplified vertex resulting from the collapse, as well as the indices of the neighboring vertices where the new triangles will be inserted. In addition, the displacement of the new vertex with respect to the previous position of the vertex must be specified.
One problem with Hoppe's Progressive Meshes technique is that each vertex split information contains a vertex identification (ID), the position of two vertices after splitting, and the relative position of two vertices in the neighborhood of the first vertex. This results in sending a significant amount of information. Since the number of vertex splits that are specified are generally on the order of magnitude of n, the information that must be provided with Hoppe's method can be assumed to be on the order of n*log(n) or higher.
Another drawback to the use of Hoppe's method is that each individual vertex split must be specified.
The technique of Eck et al. builds an approximation of the original mesh that has the same connectivity as a subdivided surface. The position of the vertices are treated as a signal decomposed over a multi-resolution wavelet basis. Levels of detail are obtained by varying the number of wavelet coefficients that are transmitted. One problem with this approach is that the highest level of detail is still an approximation to the original polyhedron, and one may need to provide an unacceptably large number of wavelet coefficients to approach the original polygonal surface with sufficient accuracy. In general, this technique is only suitable if a lossy result for geometry and topology is acceptable. It should also be noted that Eck's techniques for building the base surface are complex and computationally expensive. Further, it should be noted that when the topology of the surface is fairly complex, i.e, when the surface has a large number of boundary curves or an Euler characteristic largely higher or largely lower than zero (for instance, a torus has an Euler characteristic of 0, a double torus of −2, a triple torus of −4 and so on, a disk has one boundary curve corresponding to the outer circle of the disk; boundary curves and the Euler characteristic are defined in various textbooks such as Massey's “Algebraic Topology”, Springer Verlag, 1977), it is not clear whether Eck's method and related methods can obtain a useful approximation of the surface.
The Progressive Simplicial Complexes technique of Popovic and Hoppe is a generalization of the Progressive Meshes technique to simplicial complexes formed with points, lines, surfaces and volumes. A vertex split is replaced with a “generalized vertex split”, and additional information is necessary to encode whether the added vertex will add a point, a line segment, a triangle, or a tetrahedron to the complex. This method suffers from the same limitations as Hoppe's, when applied to a polygonal surface.
The Multi-Triangulation technique of De Floriani et al. is essentially a method for representing several levels of detail of a surface simultaneously, using a directed acyclic graph whose nodes represent increases and decreases of the number of triangles and whose arcs represent the dependencies between such increases or decreases. It is not stated how the levels of detail could be transmitted efficiently.
None of the above methods known to the inventors enable one to represent and encode changes of surface levels of detail in an efficient manner. There is thus a long felt need to overcome these and other problems of the prior art and to provide an automatic generation and representation of surface level of detail changes.
OBJECTS AND ADVANTAGES OF THE INVENTION
It is a first object and advantage of this invention to provide a method for transmitting information to update an existing level of detail to bring it to a next resolution level, rather than sending the information specifying the next resolution level.
It is a further object and advantage of this invention to provide an enhanced method for testing for the collapsibility of edges of a polygonal surface representation.
It is another object and advantage of this invention to provide an improved data structure for representing a polygonal surface, wherein the data structure has a surface description formed of a list of vertices and a list of triangles, the data structure further having data for specifying edge marks, vertex displacements, and a triangle forest.
SUMMARY OF THE INVENTION
The foregoing and other problems are overcome and the objects and advantages are realized by methods and apparatus in accordance with embodiments of this inve
Gueziec Andre
Lazarus Francis
Taubin Gabriel
August, Esq. Casey
International Business Machines - Corporation
Nguyen Tan
Nguyen Thu
Perman & Green LLP
LandOfFree
Method for generating and applying changes in the level 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 Method for generating and applying changes in the level of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating and applying changes in the level of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573140