Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-12-18
2001-05-01
Au, Amelia (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S203000, C345S440000
Reexamination Certificate
active
06226405
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the generation of a curve using a string of nodes, or of a surface using a mesh that includes a set of nodes.
2. Related Art
In the VRML, CAD and CG fields, there is a demand to represent a smooth curve or smooth surface, using a mesh, such as a triangular or a quadrilateral mesh, that is defined as a set of linear elements.
For example, in a case that the three-dimensional contents of the Web is generated as VRML data, the free shape is expressed mainly by using a mesh of triangles. If a smooth shape, such as the hand or the face of a human being is to be generated, it is difficult to determine each position of the mesh nodes. If the position of a specific node is fixed, it is preferable that the positions of the other nodes be so determined that they interpolate the fixed node.
The surface used for a CAD field is frequently expressed by using a parametric surface, such as NURBS (Non-Uniform Rational B-Spline). On the other hand, since the parametric surface that is mainly employed has a quadrilateral structure, there are such shapes for which it is difficult to generate a parametric surface because of topological restrictions. A fillet for rounding the corners of a mechanical part is one of such examples. It is easier for this shape to generate a smooth surface using a mesh.
In addition, in the CAD field, a wire frame, that is a line drawing, may first be input to a computer because it is difficult to input a desired surface directly. In this case, a method is required for generating a surface the inside of which can be smoothly interpolated from the input wire frame.
A problem that occurs during the generation of a smooth curve or surface is concerned with the provision of an adequate definition of force and a determination of under what condition the force is balanced. According to the normal method, the initial coordinate of the node is updated by repeatedly performing calculations to obtain a final shape. The property and the superiority of an algorithm are determined depending on how the force is defined.
In other words, which model of the force should be defined and which algorithm should be used to obtain a state where the force is balanced is all about in a method for generating a smooth curve or surface.
Several methods have been proposed for generating a smooth curve or curved surface by minimizing strain energy on the curved surface (see “Deformable Curve And Surface Finite-Elements For Free-Form Shape Design,” G. Celiniker and D. Gossard, Computer Graphics, Vol. 25, No. 4, pp. 257-266, 1991; “Variational Surface Modeling,” W. Welch and A. Witkin, Computer Graphics, Vol. 26, No. 2, pp. 157-166, 1992; or “Free-Form Shape Design Using Triangulated Surfaces,” W. Welch and A. Witkin, Computer Graphics Proceedings, pp. 247-256, 1994). According to these methods, the presence of a surface inside a triangular element is assumed. Then, for the entire element, integral calculations are performed for the force applied at individual points on the surface, and the internal energy is obtained. Following this, the shape of the surface which causes the internal energy to be minimum is calculated. However, the methods for evaluating the values for the energy across the inside of the triangular elements generally require an extended period of time, compared with a discrete method for evaluating values for only nodes.
As one method for evaluating values for only nodes, there is a procedure called Laplacian smoothing that is frequently employed in order to improve the quality of an FEM mesh (see “Finite Element Mesh Generation Methods: A Review And Classification,” K. Ho-Le, Computer Aided Design, Vol. 20, No. 1, 1988). This is a method for repeating a process for moving the position of each node to the center of gravity of a polygon that is constituted by adjacent nodes. This method is characterized in that a surface is generated that is so shaped as to satisfy a designated constraint condition and to minimize the dimensions. However, if, for example, nodes on the boundary of a meshed region are fixed and a node at the center of the region is fixed to a specific position, a surface that has a sharp tip at the center of the region is generated, so that this method can not be used to generate a smooth curve or surface. The constraint condition that can be provided is limited to the restriction of a position, and the normal can not be provided as a constraint condition.
As another method for evaluating values only at discrete points, proposed is “Surface Modeling With Oriented Particle Systems,” R. Szeliski and D. Tonnesen, Computer Graphics, Vol. 26, No. 2, pp. 185-194, 1992. To briefly explain this method, the stretching force, which is exerted by a spring to minimize the dimensions of a surface, and the bending force, which is exerted by a spring to flatten the surface in the vicinity of each node, act on the individual nodes by multiplying them by weighing coefficients. The weighing coefficients are considered as one type of the degree of freedom to obtain the shape. However, which shape is obtained by using which weighing coefficient is not intuitive. If the weighing coefficient is zero relative to the stretching spring and only the bending spring acts on the nodes, only the force for flattening the shape in the vicinity of nodes is applied, and the shape will be dispersed infinitely. If the weighing coefficient is zero relative to the bending spring and only the stretching spring acts on the nodes, a sharp tip occurs at the node whose constraint condition is the same as in the Laplacian smoothing. In order to generate a smooth surface, an adequate weighing coefficient must be determined. However, this paper contains no description of how this may be accomplished.
Disclosed in Japanese Published Unexamined Patent Application No. Hei 1-125671 and No. Hei 1-124062 are techniques in which attributes that correspond to a mass and an electric charge are defined at the individual nodes of a surface; as force types, a field force such as the gravity, a mutual reaction between the sources of the force such as electric charges, and elastic force such as a spring are also defined; and the positions of the points are defined by balancing these forces so that the shape of the surface is determined. According to this technique, the spring is set between one or more specific points and the individual points that form the surface. No other conditions are described in these publications.
Disclosed in Japanese Published Unexamined Patent Application No. Hei 10-69549 is a technique comprising the steps of: pasting a mesh to an image; determining spring coefficients for springs that connect the nodes of the mesh; determining spring coefficients for the springs that share the mesh nodes and the rotation springs which define an angle between springs; calculating a matrix for a balanced equation for each spring and a matrix for an overall spring balanced equation; inputting transformation control information and transforming the spring balanced equations in accordance with that information; obtaining the positions of mesh nodes after the transformation and calculating an interpolation expression for the coordinate transformation for each mesh element; and obtaining a deformed image. However, no idea in which a spring is set in the normal direction of the mesh point is disclosed.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to change the positions of a plurality of nodes in order to generate a smooth curve or surface.
It is another object of the present invention to generate a smooth curve or a surface that satisfies a given condition, such as a passing point.
In a first aspect of the present invention, to change the positions of a plurality of nodes that constitute a line or a surfaces, following steps are executed: storing in a storage device data of a normal at a node; changing the position of the node and storing the position information into the storage device by (1) defining a v
Furuhata Tomotake
Hou Ko Hsiu
Shimada Kenji
Yamada Atsushi
Au Amelia
Dastouri Mehrdad
International Business Machines - Corporation
Kaufman, Esq. Stephen C.
McGuireWoods LLP
LandOfFree
Method and apparatus for updating node position 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 and apparatus for updating node position, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for updating node position will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446598