Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-10-07
2003-04-29
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C348S420100
Reexamination Certificate
active
06556194
ABSTRACT:
BACKGROUND OF THE INVENTION
This application is based on the application No. 10-286391 filed in Japan, the contents of which are hereby incorporated by reference.
1. Field of the Invention
The present invention relates to a method of merging three-dimensional (3-D) shape data and a method of representing the same, especially in a vector potential space.
2. Description of the Background Art
Now, the concept of merging of 3-D shape data is described with reference to
FIGS. 1 and 2
. To obtain 3-D shape data (hereinafter referred to as “shape data”) describing the shape of a three-dimensional object, it is necessary to capture a range image of the object using an apparatus such as a 3-D scanner. Here image capturing only from a single viewpoint is not enough to capture the entire 3-D object due to the presence of blind spots; thus, the images must be taken from a plurality of viewpoints. Accordingly, registration and merging of the shape data obtained from different viewpoints become necessary.
FIG. 1
shows an example of 3-D image capturing, wherein a cup CP is captured from two different directions A, B indicated by the arrows. Two shape data obtained have different surfaces even through registration since they have different origin points, etc. This state is shown in FIG.
2
.
FIG. 2
schematically shows misalignment between the two shape data when viewed from the opening of the cup CP. As shown, shape data CP
1
(indicated by hatching) obtained from the direction A is not in proper alignment with shape data CP
2
obtained from the direction B. Merging is the process that integrates such two shape data without misalignment.
Referring now to
FIGS. 3 through 7
, a conventional merging method is described.
FIGS. 3 and 4
show partial shape data
1
and
2
, respectively, a portion of overlap therebetween being enclosed by the closing lines.
FIG. 5
shows a registration result of the partial shape data
1
and
2
, i.e., shape data
3
represented by range potential (range function). This representation is hereinafter referred to as a potential representation. The range potential is a concept that relatively indicates where is the position of the surface of a three-dimensional object when seen from a viewpoint. In
FIG. 5
, the surface of the 3-D object is viewed in the direction of the arrow, so it is assumed that a potential value of the shape data
3
is 0, a potential value of data closer to the viewpoint by a predetermined distance than the shape data
3
is −0.5, and a potential value of data farther from the viewpoint by a predetermined distance than the shape data
3
is +0.5. In this case, a potential direction equals the direction of the arrow. The potential value is calculated for each neighbor point (e.g., all neighbor voxels) considered as necessary in shaped surface processing. A line obtained by connecting every point in space with the potential value of −0.5 is a contour line of the potential value −0.5 and a line obtained by connecting every point in space with the potential value of +0.5 is a contour line of the potential value +0.5.
By using the potential representation for the shape data, a boundary portion, i.e., the shape of the surface of a three-dimensional object, which has been represented by a series of polygons, can be represented by cubes called voxels. This brings about the effect of shortening processing time required for the shape data.
FIG. 6
shows merged shape data
3
A obtained through arithmetic operations, such as addition of the potential (range) values, on the shape data
3
in potential representation.
Then, shape data with the potential value of 0 is extracted by an isosurface extraction technique such as a marching cubes method, and a voxel representation is returned to a polygon.representation so that the boundary portion is represented by polygons.
FIG. 7
shows the extracted shape data with the potential value of 0.
The above conventional merging method merges shape data in potential representation through arithmetic operations such as addition of the potential (range) values. This method works well when the potential directions, i.e., viewing positions, of the respective partial shape data
1
,
2
to be merged are not so different as shown in
FIG. 5
, but it fails to provide an accurate merging result of the shape data when the potential directions vary widely.
SUMMARY OF THE INVENTION
One aspect of the present invention is directed to a method of merging a plurality of three-dimensional shape data describing shapes of a three-dimensional object taken from a plurality of viewpoints, comprising the steps of: (a) performing registration of the plurality of shape data to obtain a plurality of registered shape data; (b) representing each of the plurality of registered shape data by shape vectors which depend on positions of points on a surface of the three-dimensional object, each of the shape vectors having a range component and a directional component; and (c) merging the plurality of registered shape data each represented by the shape vectors, through vector arithmetic. Preferably, origin points of the shape vectors should be on the surface of the three-dimensional object.
Since the registered shape data each represented by the shape vectors are merged through vector arithmetic, even if three-dimensional shape data are obtained from widely varying viewpoints (potential directions), merging of the registered shape data becomes more accurate than merging based only on the scalar quantity.
According to another aspect of the present invention, the step (b) of the method of merging a plurality of three-dimensional shape data includes the step of forming voxels corresponding to the shape vectors in a space including shape.
According to still another aspect of the present invention, the step (c) of the method of merging a plurality of three-dimensional shape data includes the step of merging corresponding shape vectors representing the plurality of registered shape data.
This method considerably facilitates the merging of registered shape data.
Still another aspect of the present invention is directed to a method of representing three-dimensional shape data describing a shape of a three-dimensional object. The method comprises the step of providing shape vectors which depend on positions of points on a surface of the three-dimensional object, each of the shape vectors having a range component and a directional component, and the step of representing the three-dimensional shape data by using the shape vectors. Preferably, origin points of the shape vectors should be on the surface of the three-dimensional object.
Since the three-dimensional shape data is represented by the shape vectors each having a range component and a directional component, the amount of information on the three-dimensional shape data increases, whereby more accurate data processing becomes possible.
These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5706419 (1998-01-01), Matsugu et al.
patent: 5894310 (1999-04-01), Arsenault et al.
patent: 6198487 (2001-03-01), Fortenbery et al.
Curless, Brian and Levoy, Marc, “A Volumetric Method for Building Complex Models from Range Images”,In Proceedings of ACM Siggraph '92, 1996, pp. 303-312, Stanford, California.
Wheeler, Mark D., Sato, Yoichi, and Ikeuchi, Katsushi, “Consensus Surfaces for Modeling 3D Objects from Multiple Range Images”,In Proceedings of ICCV, Jan. 1998, pp. 917-924.
Sidley Austin Brown & Wood LLP
Vo Cliff N.
LandOfFree
Method of merging three-dimensional shape data and method of... 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 of merging three-dimensional shape data and method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of merging three-dimensional shape data and method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115208