Geometry based search method for 3D CAx/PDM repositories

• US 20060012597A1
• Filed: 07/18/2005
• Published: 01/19/2006
• Est. Priority Date: 07/16/2004
• Status: Active Grant

• Current Assignee: HCL Technologies Limited
• Original Assignee: Geometric Limited (HCL Technologies Limited)
• Inventors: Chakraborty, Tathagata
• Granted Patent: US 7,397,473 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

Traditional techniques of 3D data retrieval using names and subjective attributes are not robust and are difficult to automate over large 3D repositories. Certain techniques developed for search and classification of 2D engineering designs, are in general, difficult to extend to 3D models. These issues are addressed by a system for automated search and classification for 3D CAx models based on their geometric “shape,” which is often an indication of design, analysis and manufacturing process similarity. A new method and system are provided for representing 3D shape as a composition of multiple 2D image projections, which are transformed using the Discrete Fourier and Harr Wavelet transforms. Key coefficients of the transforms are then stored in the 3D model repository and are used to efficiently search and classify such repositories.

Claims

1. A computer-based method for comparing the geometry of a pair of three-dimensional models, wherein each of the three-dimensional models is comprised of a plurality of three-dimensional surfaces and surface approximations, said method comprising using a computer in carrying out the steps of:

computing a plurality of two-dimensional hierarchical representations for each of said three-dimensional models; and

comparing selected values of said corresponding two-dimensional hierarchical representations for said pair of said models to determine a value indicating the amount of geometrical difference between said pair of models.

2. A method as claimed in claim 1, wherein said three-dimensional surfaces and surface approximations comprising the three-dimensional models comprise at least one of parametric surfaces, polygonal facets, mesh approximations, and point-cloud approximations and combinations thereof from which at least one geometric or spatial property may be extracted from localized regions of said surfaces.

3. A method as claimed in claim 1, wherein the step of computing said plurality of two-dimensional hierarchical representations comprises computing two-dimensional transformations of a plurality of two-dimensional projections of each of said three-dimensional models on a plurality of finite sized two-dimensional planes.

4. A method as claimed in claim 1, wherein said the step of computing said plurality of two-dimensional hierarchical representations, further comprises for each of said three-dimensional models:

fitting a three-dimensional grid on the three-dimensional model;

identifying a subset of grid cells comprising said three-dimensional grid intersecting with said plurality of surfaces and surface approximations;

associating with each identified grid cell a value derived from the geometrical or spatial properties of portions of the plurality of surfaces and surface approximations contained within, or neighboring, the identified grid cell;

projecting said values of said identified grid cells on a plurality of two-dimensional planes to create a plurality of two-dimensional grids; and

applying a two-dimensional transform on each said two-dimensional grid and selecting a subset of the values of said transform as a hierarchical two-dimensional representation.

5. A method as claimed in claim 4, wherein said fitting of a three-dimensional grid on the three-dimensional model comprises fitting a bounding box enclosing said three-dimensional model and uniformly subdividing along three axes of said bounding box to obtain an initial set of coarse grid cells.

6. A method as claimed in claim 5, wherein, prior to said fitting a bounding box enclosing said three-dimensional model a plurality of rigid and non-rigid transformations are applied to said plurality of surfaces and surface approximations comprising the three-dimensional model to orient and scale said three-dimensional model invariantly in three-dimensional space.

7. A method as claimed in claim 5, wherein the step of subdividing the interior of the said oriented bounding box further comprises recursively subdividing a subset of said initial set of grid cells into smaller grid cells for each grid cell which intersects with said plurality of surfaces and surface approximations, until a predefined minimum grid cell size is achieved.

8. A method as claimed in claim 4, wherein the step of identifying a subset of the grid cells, comprising said three-dimensional grid and intersecting with said plurality of surfaces and surface approximations, comprises selecting from said three-dimensional grid all grid cells with a minimum grid cell size and intersecting with the model surface.

9. A method as claimed in claim 1, wherein the comparing step comprises comparing a subset of values comprising the hierarchical representations using a standard norm.

10. A method for searching for three dimensional (3D) models with geometries similar to a given query 3D model, by comparing the geometry of at least one 3D model with that of the query 3D model, said method comprising the steps of:

decomposing the 3D models that are compared into a set of two dimensional (2D) projections;

computing 2D hierarchical transforms of said 2D projections; and

comparing selected values of the 2D transforms for the models that are compared.

15. A method as claimed in claim 10, wherein said selected values of said 2D transforms are stored in a data storage device in order to prevent re-computation of said selected values during each search.

16. A method as claimed in claim 10 wherein, prior to said decomposing of the 3D models that are compared into a set of 2D projections, the Principal Component Analysis method is used in orienting the respective models invariantly in 3D space.

11. A method as claimed in claim 11 wherein the set of 2D projections are obtained by projecting a voxellized representation of the respective model, along a plurality of directions on a plurality of finite sized 2D planes.

12. A method as claimed in claim 11 wherein the voxellized representation is obtained from a point cloud approximation of the surface of the respective model and each voxel enclosing at least one point of said point cloud, is assigned a geometric or spatial property representative of the portion of the surface enclosed by the voxel.

13. A method as claimed in claim 12 wherein transforms are applied on the 2D projections and a subset of the values of said transforms are used to capture characteristic shape features.

14. A method as claimed in claim 13 wherein said transforms include the Discrete Fourier Transform and the Harr Wavelet Transform.

17. A computer-readable medium having computer executable instructions stored thereon for execution by a computer for comparing the geometry of a pair of three-dimensional models, wherein each of the three-dimensional models is comprised of a plurality of three-dimensional surfaces and surface approximations, said instructions comprising the steps of:

computing a plurality of two-dimensional hierarchical representations for each of said three-dimensional models; and

comparing selected coefficients of said corresponding two-dimensional hierarchical representations for said pair of said models to determine a value indicating the amount of geometrical difference between said pair of models.

18. A computer-based system for comparing the geometry of a pair of three-dimensional models, wherein each of the three-dimensional models is comprised of a plurality of three-dimensional surfaces and surface approximations, said system comprising:

a module for computing a plurality of two-dimensional hierarchical representations for each of said three-dimensional models; and

a module for comparing selected coefficients of said corresponding two-dimensional hierarchical representations for said pair of said models to determine a value indicating the amount of geometrical difference between said pair of models.