Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-04
2001-10-23
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000, C345S441000
Reexamination Certificate
active
06307554
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus and a method for generating progressive polygon data, and an apparatus and a method for generating three-dimensional real-time graphics using the progressive polygon data.
2. Description of the Prior Art
In recent years, in the field of computer graphics (hereinafter, referred to as “CG”), a variety of circuit boards dedicated to three-dimensional (hereinafter, referred to as “3D”) representation (hereinafter, simply referred to as “boards”) and machines for rendering 3D graphics are commercially available. Among these, inexpensive boards are available to be built into a personal computer (hereinafter, referred to as “PC”), as Windows 95® and Windows NT® become widespread. Moreover, inexpensive game machines making use of such boards are also available.
Under these circumstances, most boards and game machines represent data for 3D graphics as polygons. Boards that handle polygons range from high-performance boards to low-performance boards. For example, in a high-performance board, a fine 3D object (hereinafter, referred to as “object”) can be rendered with 10,000 polygons, whereas in a low-performance board, it is necessary to render an object with about 500 polygons.
Conventionally, when a creator of animation (hereinafter, referred to as “animator”) produced real-time animation with an animation tool such as SoftImage® (product of Microsoft Co.), at least 30,000 polygons were generally required.
However, in order to render graphics in real time on a currently available PC, 2,000 is the maximum number of polygons for use in rendering. Moreover, when a plurality of objects are rendered simultaneously, it is necessary to restrict the total number of polygons for rendering all objets to about 2,000 polygons.
Japanese Laid-Open Patent Publication (Tokkai-Hei) No.7-85307 discloses a technique for the reduction of the polygon data used for rendering an individual object, when a plurality of objects are rendered. In this technique, a plurality of sets of polygon data that have different resolutions are prepared previously, and the resolutions are changed depending on what is rendered, e.g., what kind of behavior is rendered or the like.
This method makes it possible to reduce the number of polygons according to the behavior of an object or the like when rendering the object, so that this method is effective to display a plurality of objects on the screen.
When an animation is stored in the form of polygon data, a large storage area is generally required for storing one animation. The above-described technique requires a large amount of polygon data corresponding to a plurality of resolutions to be stored previously, so that a large storage area is necessary for storing the polygon data.
Furthermore, in the above-described technique, since the same polygon data cannot be used for machines with different performance, it is necessary to prepare as many sets of animation as performance levels of the machines. Therefore, not only a large storage area is necessary, but also a large amount of work is required from the animator.
SUMMARY OF THE INVENTION
Therefore, with the foregoing in mind, it is an object of the present invention to provide an apparatus and a method for generating progressive polygon data that makes it possible to reduce the storage area for polygon data, and an apparatus and a method for generating 3D real-time graphics that makes it possible to reduce the work of the animator by using this progressive polygon data. Furthermore, it is another object of the present invention to provide a recording medium storing a program for realizing these methods and a recording medium storing the progressive polygon data.
In order to solve the above-described problems, a progressive polygon data generator includes a basic vertex determinator for determining vertices of a basic polyhedron approximate to a shape of a 3D object, a detailed vertex determinator for determining vertices of a polyhedron in a level of approximation to the object that is higher than the basic polyhedron progressively, based on the level of approximation, and a detailed vertex coordinate calculator for progressively calculating coordinates of vertices of a polyhedron determined by the detailed vertex determinator in a coordinate system determined based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the polyhedron.
In one embodiment of the present invention, the basic vertex determinator determines vertices of the basic polyhedron by selection of an operator.
According to another aspect of the present invention, a progressive polygon data generator includes a basic vertex determinator for determining vertices of polygons approximate to cross-sections virtually segmenting a 3D object as vertices of a basic polyhedron approximate to a shape of the 3D object, a detailed vertex determinator for determining vertices of a polyhedron in a level of approximation to the object that is higher than the basic polyhedron progressively based on the level of approximation, and a detailed vertex coordinate calculator for calculating coordinates of vertices of a polyhedron progressively determined by the detailed vertex determinator in a coordinate system determined based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the polyhedron.
Preferably, when points at which line segments represented by original polygon data obtained by geometric modeling of the 3D object intersect a face virtually bisecting the object are selected as control points so as to form a second polygonal shape by connecting the control points, the polygon approximate to each cross-section is a quadrilateral defined by four vertices that divide a total length of sides of the second polygonal shape into four equal lengths.
Preferably, the detailed vertex determinator progressively determines vertices of a polygon the number of which is increased so that the level of approximation to the cross-section is higher than the polygon approximate to the cross-section as detailed vertices, based on the increased number of vertices. This is because information about the position of the detailed vertex can be stored in a simplified form.
Preferably, the detailed vertex determinator includes an approximation level calculator for calculating a difference between a length of each side of the quadrilateral and a total length of sides of the second polygonal shape between both ends of each side of the quadrilateral, a comparator for comparing the difference calculated by the approximation level calculator with a predetermined value, and a progressive vertex determinator for determining a point that divides into two equal lengths the total length of the sides of the second polygonal shape between both ends of the side of the quadrilateral as a vertex of a polygon in a higher level of approximation when the comparator determines that the difference is the predetermined value or more, and not determining a vertex of a polygon in a higher level of approximation when the difference is determined to be smaller than the predetermined value. When a vertex of a polygon in a higher level of approximation is determined by the progressive vertex determinator, the approximation level calculator calculates the difference with respect to a newly produced side of the polygon whose vertex is determined, and the progressive vertex determinator determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex determinator no longer determines a vertex of a polygon in a higher level of approximation. When the detailed vertex is determined by this process, it is possible to produce suitable 3D polygon data in accordance with the number of 3D polygons that are desired to be used for rendering.
Preferably, the detailed vertex determinator includes an approximation level calculator for calculating a difference between an area of each face of the
Arai Masatoshi
Miyata Ryosuke
Murakami Koichi
Fujitsu Limited
Padmanabhan Mano
Staas & Halsey , LLP
Zimmerman Mark
LandOfFree
Apparatus and method for generating progressive polygon... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for generating progressive polygon..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for generating progressive polygon... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617738