Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
2000-04-25
2001-12-04
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
C345S420000
Reexamination Certificate
active
06326968
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an approximation method for shape data, particularly with normal vectors and a drawing device which are adapted for reducing the complexity of the shape, and with respect to shape data with normal vectors expressing a geometric model used in computer graphics (CG).
2. Description of the Related Art
In drawing by so-called computer graphics (CG), in general, a same model is constantly used regardless of the position, size and depth of the model, the point of a viewer's attention, and the shifting speed of the model.
However, the same model is not always required for drawing. By switching the model in accordance with the position, size and depth of the model within a screen, the point of the viewer's attention, and the shifting speed of the model, and using a more simplified model as well as an original detailed model, sufficient picture quality may be obtained.
For example, if a model is located at a distant position, the size of the model on the screen is so small that minute uneven changes of the original model are not seen. Also, with respect to a model located outside of the viewpoint of the viewer, detailed portions need not be seen. In addition, if the mode shifts within the screen at a high speed or if no attention should be paid to the model, detailed portions of the model need not be seen, either.
That is, in such cases, it is not necessary to perform drawing by using the detailed original model. It suffices to use an approximated model from which detailed portions of the original model have been removed.
With a model as a drawing target, a normal is allocated to each surface and vertex, and drawing is performed based on the assumption that a light is radiated to the model. In this way, the quality of drawing results is generally improved. This technique produces results similar to those in the case where a light is actually radiated to the model, by calculating reflectance and refraction in the case where the light is radiated.
Therefore, in performing shape approximation as described above, it is necessary to pay attention to the normals allocated to the surfaces and vertices of the model. There should not be any inconvenience, such as, increase in the entire operation quantity as a result of preventing deterioration in appearance of the model due to an erroneous direction or value of the normal at the time of approximation, or as a result of duplicate operations for re-allocating the normal to the approximated model.
Meanwhile, with respect to shape approximation, a trial of hierarchical approximation of a polygon model is described, for example, in the literature “Re-tiling polygonal surface” (computer graphics, Vol.26, No.2, July 1992) by Greg Turk. In this literature, however, the normal allocated to each vertex and surface of the model is not considered. In “Mesh Optimization” (Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH 1993) by Hugues Hoppe, et al., energy is introduced in evaluation of an approximated model, and the model is approximated by repeating removal of an edge, division of a patch and swapping of the edge so that the energy is minimized. However, the normal vector at the time of approximation is not considered in this technique, either. Therefore, duplicate processing for providing normal vectors to an approximated model after the approximation of the model is required.
As described above, the past studies have some problems in model approximation.
Specifically, in the conventional approximation technique for geometric models used for CG, deterioration in quality after approximation has not been prevented by processing, such as, removal of the normal allocated to the model or change of value of the normal. Also, no particular measures have been taken to eliminate the necessity of re-allocating the normal after approximation. Approximation in consideration of the normal vectors themselves has not been done.
In view of the foregoing status of the art, it is an object of the present invention to provide a shape data approximation method and a drawing device which enable approximation of a geometric model used for CG in a state that normal vectors are appended, and which enable prevention of distortion of the normal vectors in approximation results.
SUMMARY OF THE INVENTION
According to the present invention, in approximating shape data with normal vectors appended thereto to desired resolution, which edge of the shape data to be removed is decided and the amount of shift of vertices after removal of the edge or new vertex positions are decided. In response to an output obtained from the edge removal decision and the vertex shift decision, normal vector values are changed in conformity with removal of an unnecessary normal and the new vertex positions of the shape data, with respect to the normal vectors allocated to the respective surfaces of the shape data.
According to the present invention, in order to obtain a model with normal vectors having a desired degree of detail, removal of an edge in model approximation is decided and the amount of shift of the vertices remaining after removal of the edge is decided. In response to the output obtained from the edge removal decision and the vertex shift decision, the removal and shift of the normal vectors allocated to the model surfaces are decided. In accordance with this decision, removal of the normal vector or change of value is carried out. Through these procedures, distortion of the normal vectors in model approximation is restrained so that approximation of a model including a picture is enabled.
REFERENCES:
patent: 4152766 (1979-05-01), Osofsky et al.
patent: 4600919 (1986-07-01), Stern
patent: 4694407 (1987-09-01), Ogden
patent: 4783829 (1988-11-01), Miyakawa et al.
patent: 4969204 (1990-11-01), Melnychuck et al.
patent: 5029228 (1991-07-01), Nonoyama et al.
patent: 5040130 (1991-08-01), Chang et al.
patent: 5193145 (1993-03-01), Akeley
patent: 5276786 (1994-01-01), Long et al.
patent: 5341466 (1994-08-01), Perlin et al.
patent: 5373375 (1994-12-01), Weldy
patent: 5384904 (1995-01-01), Sprague et al.
patent: 5448686 (1995-09-01), Borrel et al.
patent: 5490239 (1996-02-01), Myers
patent: 5506947 (1996-04-01), Taubin
patent: 5590248 (1996-12-01), Zarge et al.
patent: 5613051 (1997-03-01), Iodice et al.
patent: 5615317 (1997-03-01), Freitag
patent: 5621827 (1997-04-01), Uchiyama et al.
patent: 5689577 (1997-11-01), Arata
patent: 5761332 (1998-06-01), Wischmann et al.
patent: 5774130 (1998-06-01), Horikawa et al.
patent: 5796400 (1998-08-01), Atkinson et al.
patent: 5929860 (1999-07-01), Hoppe
patent: 5963668 (1999-10-01), Horikawa et al.
patent: 6100902 (2000-08-01), Horikawa et al.
F. Schmitt et al., “An Adaptive Subdivision Method for Surface-fitting From Sampled Data,”Computer Graphics, vol. 20, No. 4, Aug. 18-22, 1996.
M. Garland et al., “Surface Simplification Using Quadric Error Metrics,”Computer Graphics Proceedings, Annual Conference Series, Aug. 3-8, 1997, pp. 209-216.
G. Turk, “Re-tiling Polygonal Surfaces,”Sisgraph '92, Computer Graphics Conference Proceedings, Jul. 26-31, 1992, pp. 55-64.
H. Hoppe et al., “Mesh Optimization,”Sisgraph '93, Computer Graphics Conference Proceedings, Aug. 1-6, 1993, pp. 19-26.
U.S. application No. 08/987,004, filed Dec. 8, 1997, pending.
U.S. application No. 09/326,841, filed Jun. 7, 1999, pending.
Horikawa Junji
Totsuka Takashi
Bell Boyd & Lloyd LLC
Santiago Enrique L.
Sony Corporation
Zimmerman Mark
LandOfFree
Image data approximation considering normal vectors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image data approximation considering normal vectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image data approximation considering normal vectors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556444