Method for generating surface data to be added to three dimensional shape data

Abstract

An object of the present invention is to automatically determine the orientation of a newly generated surface, etc. when performing such processing as filling a dropout portion of three dimensional shape data, and to generate more natural three dimensional shape data. The present invention provides a method for generating a grid-patterned surface in three dimensional shape data, and comprises a first step (# 11 ) for detecting the orientation of a polygon in the three dimensional shape data that is located at a periphery of a surface to be fitted, a second step (# 12 ) for determining the orientation of the surface so that a grid orientation of the surface matches the orientation of the detected polygon, and a third step (# 13 ) for fitting the surface onto the three dimensional shape data while maintaining the thus determined orientation.

What is claimed is:  
     
         1 . A method for fitting a, grid-patterned surface data onto a portion of a three-dimensional shape data including a plurality of polygons, the method comprising: 
 a first step of detecting the conditions of a plurality of polygons in the three dimensional shape data that is located at a periphery of a surface to be fitted the surface data;    a second step of determining conditions of grid-pattern of the surface data on the basis of detected conditions of the plurality of polygons; and    a third step of fitting the surface data whose grid-pattern has been determined onto the three dimensional shape data.    
     
     
         2 . The method according to    claim 1   , 
 wherein said condition of polygon includes an orientation thereof, and said condition of grid-pattern includes an orientation thereof for the three-dimensional shape data.    
     
     
         3 . The method according to    claim 2   , 
 wherein the orientation of the polygon is detected in the first step by picking up a vector whose starting point is at a vertex of the polygon located at the periphery of the surface to be fitted, and whose end point is at a vertex connected to the vertex taken as the starting point, and the orientation of the grid-pattern is determined in the second step so as to take along direction of the picked up vector.    
     
     
         4 . The method according to    claim 1   , 
 wherein said condition of polygon includes a position thereof in a three-dimensional space, and said condition of grid-pattern includes a orientation thereof for the three-dimensional shape data.    
     
     
         5 . The method according to    claim 4   , 
 wherein said second step comprising sub-steps of: 
 generating a rectangular bounding box that includes the portion to be fitted the surface data;  
 setting a grid inside and outside the bounding box;  
 obtaining a Z value of a vertex of the grid as a boundary value;  
 rotating the bounding box so that an evaluation value based of the boundary value is minimized or maximized; and  
 determining the orientation of the surface so that the orientation of the grid-pattern aligns with a coordinate space whose X or Y axis is taken along a direction in which the grid of the bounding box is oriented by the rotation.  
   
     
     
         6 . The method according to    claim 1   , 
 wherein said condition of polygon includes a density thereof, and said condition of grid-pattern includes a density thereof.    
     
     
         7 . The method according to    claim 6   , 
 wherein the density of polygon is detected in the first step by picking up vectors each consisting of two adjacent vertices in the vertices forming the polygon, and in the second step, the density in X direction is detected on the basis of an average value of the x components of the vectors near the X-axis direction among the picked up vectors, the density in Y direction is detected on the basis of an average value of the Y components of the vectors near the Y-axis direction among the picked up vectors, and the density of the grid is determined on the basis of the detected densities.    
     
     
         8 . The method according to    claim 1   , 
 wherein said portion is where three-dimensional data lacks.    
     
     
         9 . The method according to    claim 1   , 
 wherein said portion is designated from within the three-dimensional data by a operator.    
     
     
         10 . A method for fitting a grid-patterned surface data onto a portion of a three-dimensional shape data consisting of a plurality of polygons, the method comprising: 
 a first step of picking up a vector whose starting point is at a vertex of the polygon located at the periphery of the surface to be fitted the surface data;    a second step of determining a orientation of the surface data on the basis of the picked up vector; and    a third step of fitting the surface data to the three-dimensional shape data in the determined orientation.    
     
     
         11 . The method according to    claim 10   , 
 wherein in the second step, X-Y coordinates is determined so as to minimize a sum of the squares of the products of the x and y components of the respective vectors, and the orientation of the surface data is determined according to the determined X-y coordinates.    
     
     
         12 . The method according to    claim 10   , 
 wherein in the second step, X-Y coordinates is determined using a technique of principal component analysis, and the orientation of the surface data is determined according to the determined X-y coordinates.    
     
     
         13 . A method for fitting a grid-patterned surface data onto a portion of a three-dimensional shape data consisting of a plurality of polygons, the method comprising steps of: 
 generating a rectangular bounding box that includes the portion to be fitted the surface data;    setting a grid inside and outside the bounding box;    obtaining a evaluation value based on Z value of a vertex of the grid;    determining the orientation of the surface according to orientation of the bounding box which making the evaluation value to minimize or maximize.    
     
     
         14 . A method for fitting a grid-patterned surface data onto a portion of a three-dimensional shape data consisting of a plurality of polygons, the method comprising steps of: 
 picking up vectors each consisting of two adjacent vertices in the vertices forming the portion;    determining the density in X direction on the basis of an average value of the x components of the vectors near the X-axis direction among the picked up vectors;    determining the density in Y direction on the basis of an average value of the Y components of the vectors near the Y-axis direction among the picked up vectors; and    fitting the surface that the density of which grid is determined to the three-dimensional shape data.    
     
     
         15 . An apparatus for fitting a grid-patterned surface data onto a portion of a three-dimensional shape data consisting of a plurality of polygons, the apparatus comprising: 
 a detector for detecting the conditions of a plurality of polygons in the three dimensional shape data that is located at a periphery of a surface to be fitted the surface data;    a determination portion for determining conditions of grid-pattern of the surface data on the basis of detected conditions of the plurality of polygons; and    a processor for fitting the surface data whose grid-pattern has been determined onto the three dimensional shape data.    
     
     
         16 . A computer program for making a computer to execute processes of: 
 detecting the conditions of a plurality of polygons in the three dimensional shape data that is located at a periphery of a surface to be fitted the surface data;    determining conditions of grid-pattern of the surface data on the basis of detected conditions of the plurality of polygons; and    fitting the surface data whose grid-pattern has been determined onto the three dimensional shape data.