Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1999-06-07
2004-02-10
Mariam, Daniel G. (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S199000, C345S441000
Reexamination Certificate
active
06690827
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a shape data approximation method for reducing the amount of data address of a shape model used in the field of computer graphics, in which the shape model is approximated with its general shape maintained. The present invention also relates to an information processing apparatus that executes the approximation method and a medium that provides a program for the approximation method.
2. Description of the Related Art
When a plurality of identical models are present on screen in the image rendering in the computer graphics, the same model is typically rendered regardless of the location, size, and depth of the model, a point of interest to a viewer, and speed of the movement of the model. Such shape model is called a polygon model, and is constructed of a plurality of surfaces.
The same model is not always required in the rendering. Models are switched depending on the location, size, depth of the model, a point of interest to a viewer, and the speed of the model. Not only an original detailed model, but also a more simplified model is rendered at a sufficiently high image quality.
Specifically, a graphics display apparatus has prepared models at different levels of detail, and switch them from one to another during the rendering, presenting an apparent image quality as good as that provided by the original model. Since the rendering time in the computer graphics depends on the amount of data, a model having a smaller amount of data is rendered faster than the original model. Such an arrangement satisfies two requirements at the same time, a high-speed rendering and a high-image quality rendering, normally required of computer graphics.
Techniques for creating models having different levels of detail are effective for the display of computer graphics models. If the amount of data is simply reduced to lower the level of detail of the model, the viewer may find an approximate model unnatural. To minimize the unnatural look, a general feature portion of the model is preferably left while the remaining portion is cut to reduce the amount of data. Such an approximation of the model is hitherto manually performed by designers, requiring a great deal of labor and time.
Reducing the amount of data (the number of polygons and the number of surfaces) is called a polygon reduction, a polygonal approximation, a polygon compression, or a surface simplification.
Several studies for performing the polygonal approximation, namely, surface simplification on a computer have been made. These studies treat an approximation method for a single component only, and fail to consider an approximation that maintain a positional relationship and engagement relationship between a plurality of associated components.
If the engagement relationship is destroyed in rendering components, such as gears in mesh or a top covering and a bottom covering, having an engagement relationship, the destroyed engagement relationship not only presents an unnaturally looking image to the viewer but also makes it impossible to render a plurality of components together on screen.
In a paper authored by Greg Turk, entitled “Re-Tiling Polygonal Surface” (Computer Graphics, Vol. 26, No. 2, Jul. 1992), points, arranged on the surface of a polygon model, are connected to reorganize the model, and the model is thus hierarchically approximated. The algorithm presented by this paper treats a rounded object, but is inappropriate for a sharp edged shape, and is unable to cover objects of general shapes.
In a paper authored by Francis J. M. Schmitt, Brian A. Barsky, and Wen-Hui Du, entitled “An Adaptive Subdivision Method for Surface-Fitting from Sampled Data” (Computer Graphics Vol. 20, No. 4, Aug. 1986), Bezier patches are attached to a three-dimensional object for approximation. According to this paper, however, general polygons typically used in the computer graphics are not treated.
In a paper authored by Hugues Hoppe et al., entitled “Mesh Optimization” (Computer Graphics Proceedings, Annual Conference. Series, SIGGRAPH 1993), energy is introduced in the evaluation of a approximation model. In order to the minimize the energy, an edge removal, a patch segmentation, and an edge swapping are iterated to approximate the model. In the technique disclosed in this paper, long iterative calculations are required before a minimum energy point is found. For the point not to be trapped in a localized minimum point, some solution, such as simulated annealing, is required like other minimum energy problems. The minimum energy point is not necessarily the best in terms of the sense of vision.
In a paper authored by Hugues Hoppe, entitled “Viewed Dependent Refinement of Progressive Meshes” (Siggraph 97 Conference Proceedings 1997), the energy of an edge is calculated, and an edge having a small energy value is removed. Furthermore, a polygon reduction is performed in accordance with a viewer's point of view. However, an adjacency relationship between components is not considered. Michael Garland and Paul S. Heckbert disclose a polygon reduction technique in a paper entitled “Surface Simplification Using Quadric Error Metrics” (Siggraph 97 Conference Proceedings 1997). A distance from an apex to a surface is squared, squared distances are summed, and an edge having a smaller sum has a higher priority in removal. In this case also, the adjacency and engagement relationships between components are not considered.
These past studies of the approximation of the model fail to treat the adjacency relationship and engagement relationship.
In the conventional shape approximation, the objects to be handled are limited, a long calculation time is required, and the adjacency relationship striding over a plurality of components is not considered.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a shape data approximation method which approximates shape data while maintaining an adjacency relationship and engagement relationship in an adjacent region where a plurality of components are adjacent to each other, in the approximation of a shape model used in the computer graphics. It is also an object to provide an information processing apparatus that executes the approximation method and a medium that provides a program for the approximation method.
In one aspect of the present invention, the approximation method for approximating shape data at a desired level of detail to be approximate data, includes the designating step of designating an adjacent region where a plurality of components are adjacent to each other in the shape data, the evaluating step of calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and the approximating step of approximating the shape data in accordance with the evaluation score to create the approximate data.
In another aspect of the present invention, the approximation method for approximating shape data at a desired level of detail to be approximate data, includes the forming step of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, the selecting step of selecting an evaluation edge of interest for evaluation from edges constituting the shape data and the virtual edge, the evaluating step of calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and the approximating step of approximating the shape data in accordance with the evaluation score.
In yet another aspect of the present invention, the An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, includes designating means for designating an adjacent region where a plurality of components are adjacent to each other in the shape data, evaluating means for calculating an evaluation score in accordance with the degree of deformation
Horikawa Junji
Totsuka Takashi
Bell Boyd & Lloyd LLC
Mariam Daniel G.
Sony Corporation
LandOfFree
Approximation method of shape data, information processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Approximation method of shape data, information processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation method of shape data, information processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294661