Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1998-03-11
2001-11-27
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S619000, C345S473000, C345S440000, C345S419000, C345S420000
Reexamination Certificate
active
06323863
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to method and apparatus for generating a graph showing an object structure, and also to data converting method, apparatus, system, and data recording medium, all of which can use the graph generating method and apparatus. The present invention is applicable to CAD (Computer Aided Design) or to solid data used in CG (Computer Graphics), for example.
2. Description of the Related Art
For describing an object such as a solid in the field of CAD or CG, approximation using polygons has been known. This method divides the surface of an object into pieces and pastes polygon patches thereon. A large number of objects have been created in the form of polygon data and saved in databases or the like. Reasons why polygon expressions have become so popular are that this method is simple and easy to understand, and that any object can be covered with triangle patches by using this method, although editing procedure may require patience.
As has been pointed out for a long time, a problem in polygon expressions is that pursuit of precision is directly linked to an increase in data amount. Since polygon itself is flat, there is no effective method but to paste smaller polygons more when smoothness of a surface is pursued or a complex shape is expressed. For example, when a figure is modeled to a reasonable precision, tens or hundreds of thousands of polygons are generally needed. A user thinks that CG can create any image, since he/she has got used to amazing images in a movie made by using the state-of-the-art CG, such as in Jurassic Park or Apollo 13. When such a request by a user needs to be fulfilled, the number of polygons naturally increases, as long as the polygon expressions are used.
Remarkable progress in recent computer hardware lies in the background of the polygon number increase. In the past several years, improvements have been made in the areas of main memory capacity, secondary storage capacity, and CPU performance. Therefore, a large amount of polygon data can be dealt with. However, as communications using the Internet is getting popular, a problem has arisen that it takes a considerable amount of time to transfer a high-resolution image via a telephone line, and it has been widely recognized that the amount of image data is generally large. If larger polygon data is to be dealt with in the future, it will be necessary to improve hardware including infrastructure such as communication lines. There seems to be no end in the “rat race” between hardware and the number of polygons.
Based on considerations of the problems described above, a variety of trials have been carried out to reduce the amount of polygon data. In Japanese Patent Laid-Open Publication No. Hei 8-153211 (Apparatus for Reducing Polygons in Computer Graphics Data), an apparatus for reducing redundant polygons in response to viewpoints has been disclosed. According to this apparatus, image drawing speed can be increased while image quality is maintained. However, this apparatus does not reduce the amount of original polygon data needed to describe an object.
In Japanese Patent Laid-Open Publication No. Hei 7-262402 (Method for Surface Description), a method has been disclosed for expressing an object contour more smoothly by converting edges of polygons into arcs, with attention paid to directions of normal vectors at end points of the edges. When the number of polygons is small, the surface of an object is generally rough. The above method mitigates this drawback to some degree. However, this method is effective only for the cases where the number of original polygons is small, and does not reduce the polygon data amount itself.
Meanwhile, there exists another method for describing an object by surface elements called parametric patches. According to the parametric patch method, a surface can generally be expressed more smoothly with comparatively small data. On page 62 of “Basics and Applications of Three-dimensional CAD” (by Hiroshi Toritani and Hiroaki Chiyokura) published by Kyoritsu Shuppan Publishers Co., a method is disclosed for pasting surface patches by generating curve meshes using characteristic lines. In this textbook, explanation regarding how to describe surface patches by equations, how to make connections between the patches smooth, and how to describe irregular shape patches other than quadrilaterals are also given.
However, the greatest problem in using surface patches lies in the difficulties in automatic processing. If the shape to be dealt with is simple such as a cylinder, it would be easy to paste patches thereon. If the shape of an object is complex, it is extremely difficult to design a system which can give theoretical or logical support to, for example, how to approximately divide the object in order to paste patches successfully, or how to carry out minimal division. Therefore, an operator generally needs to manually specify how to paste or correct and pasting patches greatly depends on the operator's experience. On the other hand, if we hold on to the polygon expression giving up free-form surface patches, there will be no prospect of future improvement, with the amount of data to describe shapes being on the rise.
SUMMARY OF THE INVENTION
Based on observations of the reality described above, the present invention has been created to provide a representation method which replaces the existing polygon expressions.
Another object of the present invention is to provide a technique for converting polygon data into precise shape data suitable for free-form surface representation.
Still another object of the present invention is to provide a technique for uniquely and certainly converting polygon data into data in different representation, with logical support therefor.
Yet another object of the present invention is to provide a technique for generating data in representations different from the polygon expression.
Yet still another object of the present invention is to provide a technique for inverting shape data, which is represented in a smaller amount than that of polygon data, into polygon data upon necessity.
Still another object of the present invention is to provide a technique which utilizes assets of existing polygon data in an enormous amount when a shape expression different from polygon expressions is carried out.
Still another object of the present invention is to provide a technique for describing an object structure that is usable for realizing the data converting techniques.
In Japanese Patent Application No. Hei 9-303246, a technique is proposed which can model a complex object precisely and in a unique manner with a simple system such as a drawing tool. The present invention combines that technique and the conventional polygon expressions, and a primary object of the present invention is to revolutionize, in terms of quality, the shape expressions that use polygons.
A structure graph generating method of the present invention generates a skeleton graph of an object by extracting topological information or topology of the object from polygon data representing the shape of the object.
“The object” herein referred to anything that can be expressed in the form of n-dimensional data. The object may be a solid in CAD, temperature distribution, or the like. “Polygon data” include polygonal, mesh, polyhedron data and the like. “Topological information of an object” refers to information regarding the structure of an object. By the structure graph generating method of the present invention, information regarding the skeleton of an object can be obtained, which can be used for defining the shape of the object. A Reeb graph is an example of a skeleton graph, and it may be a classical one, or the one expressed by icons (described later) proposed by the applicants. In the latter case, the Reeb graph can deal with the internal structure of an object.
Another aspect of the present invention comprises the steps of obtaining polygon data representing an object shape, detecting singular points of a
Hirose Kazuki
Shinagawa Yoshihisa
Fleshner & Kim LLP
Good-Johnson Motilewa
Luu Matthew
Monolith Co. Ltd.
LandOfFree
Object structure graph generation and data conversion using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Object structure graph generation and data conversion using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object structure graph generation and data conversion using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572295