Abstract:
A method is disclosed for indexing 3D digital models, retrieving them, comparing them and displaying the results in a 3D space. The method comprises four complementary parts, i.e. displaying, comparing/searching, reconciling the faces, and classifying the results. These parts can overlap with each other or can be implemented separately. A method is described for retrieving 3D models that share certain similarities of form with a reference 3D model, involving a first step of analysis in order to generate representations (descriptors). The process of searching/comparing 3D models based on descriptors partially related to the faces optionally requires a process of pairing and reconciling the faces. The results are displayed in a single 3-dimensional space and, owing to a mark on the faces of the 3D models, makes it possible to distinguish several types of difference between similar 3D models.

Description:
FIELD OF THE INVENTION 
       [0001]    This patent application relates to the field of 3D models, as an example to the digital representations in a space of dimension 3, and more particularly to the field of 3D models comparison, such as using descriptors, for the purposes of a search, a ranking and/or a comparative analysis of the parties. 
       BACKGROUND OF THE INVENTION 
       [0002]    Objects&#39; Tri-dimensional (3D) digital representations of are well-known in the fields of engineering, medicine, video game, film, and even in widely spread applications (for example SketchUp by Google, now Trimble). Usage in such fields was made possible by software for 3D creation and edition including CAD systems (computer aided design), for reverse engineering and for other techniques of 3D reconstruction, but also by 3D scanning equipment. All these means generate digital models in dimension 3. None of the said digital models are 3D models describing boundaries between objects and their environment also known as Boundary Representations (B-rep, found for example in the STEP standard or geometric modelers like Parasolid and Acis). Others provide a tessellation (for example STL or VRML formats). These models may include information other than purely geometrical data. 
         [0003]    The above types of 3D models are commonly used in enterprises and in many areas of everyday life, and their number are still quickly increasing. Therefore, a multi-facet problem is arising, i.e. (i) to identify the 3D models, (ii) to find similar digital objects, (iii) to compare them to identify differences or identical parts, and finally (iv) to display relevant results according to a set of criteria to ensure simple and efficient use of the search results. 
         [0004]    Currently, there are two distinct categories of systems. Systems belonging to the first category compare a first 3D model to a second 3D model to determine the differences between them. Systems from the second category find 3D models that are similar to a 3D model given in reference. 
       3D Models Comparison Systems 
       [0005]    A second category of applications aims at finding 3D models by comparing a reference 3D model with a set of 3D models to order the said 3D models based on their similarity to the reference 3D model. The found similarity is usually expressed with a quantitative value used to order these 3D models. Various methods are available to compute the similarity. At first, an analysis of each 3D model generates a representation used to carry out effectively later comparisons. In this case, this representation is often referred to in various terms, including descriptor, representation, and index. Whatever the name, the representation may take several forms, such as a graph (US 2004/0249809 A1), a vector of predefined dimension N (U.S. Pat. No. 6,625,607 B1) or variable depending on the 3D model, etc. The descriptors are usually saved during the execution of the comparisons. A 3D model is chosen as a reference. In some cases, the reference 3D model is replaced by images, photographs or two dimensions drawings [A 3D Model Search Engine, Patrick Min, Ph.d. Dissertation, Princeton University, 2004]. If necessary, the descriptor is calculated. Descriptors are compared. Here again several methods are described in [Content-based three-dimensional Engineering Shape Search, K. Lou, S. Prabhakar, K. Ramani, Proceedings of the 20th International Conference on Data Engineering 2004]. Based on the results of the comparison, similar 3D models are generally ordered on the basis of a quantity we refer to as an index of similarity. These results are then displayed in various forms, usually images of small sizes (icons, miniature). 
         [0006]    As mentioned earlier, many approaches have been proposed to search for 3D models based on the shape of a reference 3D model. Some approaches focus on organic type shapes, others seek a permissive similarity (e.g. find cars, chairs, glasses). In particular, these methods are not designed to determine whether two 3D models are exactly the same, using a precision that is of the same order of magnitude as the manufacturing tolerances. Systems such as Siemens Geolus or Cadenas GeoSearch are representative of this category. The said systems analyze 3D models approximated by a tessellated representation to generate descriptors or they use a sampling of points of the boundary (US20100073365) therefore deteriorating the precision of the comparison. Several proposed methods to extract the descriptors from the 3D models and to compare them, require a high computing time and are therefore difficult to apply when the number of 3D models to process are increased (more than a million of models, for example) or for interactive search. 
         [0007]    Moreover, these approaches search for 3D models completely similar to the reference 3D model, i.e. the complete 3D model. Known 3D models search tools or systems have neither the information nor the technology to perform a search based on parts of 3D models or that favor parts of these 3D models during the search process. 
       SUMMARY OF THE INVENTION 
       [0008]    There is a need for systems to search for digital 3D models from heterogeneous sources and which are similar in whole or in part. Such systems should determine and describe the differences from a 3D reference model considered in its entirety or in part, should display the results with any relevant information on the found differences and similarities. Such systems should provide extremely high precision according to different criteria and should be adapted to deal with very large number of 3D models. 
         [0009]    To meet these needs, a method is proposed, the said method is configured to initially builds descriptors to identify (or index) 3D models. The built descriptor has the ability to capture properties at the level of a complete 3D model, each solid body (in the usual sense of three-dimensional geometric and topological representation) composing a 3D model and also properties at the level of each face (always within the usual meaning of three-dimensional geometric and topological representation) forming the 3D model. Boundary representations do not guarantee the uniqueness of representation of a 3D model, that is, multiple boundary representations may correspond to the same object. To obtain such property which is essential to the comparison of 3D models, faces that are G2 continuous (geometric second derivative) along one of their common edge are regrouped and faces built on surfaces which are not G2 continuous are divided if required. All subsequent steps of the method, except displaying in 3D, may be applied to the descriptors without having to necessarily use 3D models. 
         [0010]    Method further comprises comparing the characteristics of the descriptors based on criteria selected by the operator. The said step is based on two elements, the reconciliation of the terms or features of the descriptors and a more rigorous qualification of the differences applied at the level of parts of the 3D models, i.e. solid bodies and faces. The said reconciliation corresponds to achieving a pairing of solid bodies and faces of the 3D models which thus may be expressed in different coordinate systems, in different CAD systems, and in different geometric and topological representations. Such pairing allows taking into account only parts of 3D models for processing. Current methods are typically limited are limited to the following characterizations: identical, modified or new. Up to nine characterizations may be used (such as identical, intrinsically identical, identical geometric type, different topology, etc.). A portion of a 3D model, a solid body or a face may simultaneously possess a plurality of characterizations. The marking for the display relies on these properties (for example, a color associated with a combination of qualifications) and the criteria in the query of the operator. A function based on the differences determines the index of similarity (or similarity) to order the 3D models. 
         [0011]    As the handled digital objects are 3D models, a new way of communicating the results in the form of a 3D structure (Scene) in a single 3D space is proposed. One of the axes represent the similarity value wherein the marking (colors, etc.) of the faces are used to show the types of difference and the two other axes are used to represent other quantities or properties such as for example, costs, dates, suppliers, configurations, versions, etc. 
         [0012]    As an example, the method comprises (i) identifying 3D models identical to a reference 3D model with an accuracy comparable to that of the manufacturing&#39;s process precision of said object (identification of duplicates or geometric clones); (ii) identifying a part (a solid body) identical or similar in a mechanical system (a 3D model); (iii) identifying a component (set of solid bodies) identical or similar in a system or several systems (3D models); (iv) identifying similar 3D models in large optionally distributed databases of 3D models; etc. 
         [0013]    Thanks to the descriptors that capture properties with a very fine granularity (set of parameters or characteristics at the level of each face) and capabilities of the comparator, including the principles of reconciliation and qualification of the faces, the system may also identify and recognize form features, i.e. parts of 3D models. As an example, the system may be configured to identify (i) a set of through holes with given diameter and distance in between axes (set of disconnected faces and their parameters) in various 3D models; (ii) a keyway (a set of connected faces and intrinsic parameters); (iii) to identify a face, or a set of identical or similar faces in one or several 3D models; etc. 
         [0014]    Each element, be it (i) the search of similar 3D models based on volume and boundary descriptors, (ii) the reconciliation (pairing) of terms or characteristics of the descriptors enabling multi repositioning and retrieval of parts of 3D models, (iii) the principle of qualification of the differences and (iv) the display of results combining similarities and differences between several 3D models into a single 3 dimensional space are inventions. 
         [0015]    According to a first aspect of the invention, we propose a method of comparison of 3D models for the purposes of searching, sorting and/or comparatively analyzing the boundary representation of 3D models. According to this method, a descriptor is provided to each of a plurality of 3D models. These descriptors are comprised of (i) geometric characteristics of 3D models that are invariant with regards to the modeling coordinate system and (ii) geometric characteristics of 3D models depending on the coordinate system. When needed, features not depending on the coordinate system to match parts of a first 3D model and parts of at least another 3D model (pairing process) may be used. Features that depend on coordinate system for the parts whose pairing is successful in order to determine a group of transformations that links parts of the first 3D model to parts of at least another 3D model may also be used. At least a group of identical transformations is determined, where the similarities and differences between 3D models are identified, at least in part, by the said group of identical transformations (identical means respecting a certain threshold). 
         [0016]    Geometric characteristics of parts of a 3D model which are invariable according to the coordinate system may include the area, the eigenvalues of the inertia moments and/or the perimeter of the planar faces of 3D models. Geometric characteristics of portions of a 3D model that depend on the coordinate system may include the center of gravity and/or the axes of the moments of inertia of the planar faces. 
         [0017]    The step to determine at least a group of identical transformations may include determining at least two groups of identical transformations in order to allow the comparison of similar 3D models but where at least a part of 3D models is in a different position and/or orientation. 
         [0018]    According to a second aspect of the invention, a method of comparison of 3D models for the purposes of searching, of sorting, and/or of comparatively analyzing the boundary representation of 3D models is provided. According to this method, a descriptor is provided to each of a plurality of 3D models, descriptors with geometric characteristics of 3D models that are invariant depending on the modeling coordinate system and geometric characteristics of 3D models that depend on the coordinate system. If needed, features not depending on the coordinate system are used to match faces from a first 3D model to at least one other 3D model. Data obtained in the process of pairing between the characteristics of the descriptors of at least two 3D models are stored. For parts of 3D models for which the pairing is successful, a group of transformation is determined to reposition the parts of 3D models in a same coordinate system. At least two 3D models whose 3D models parts are marked according to the types of differences are displayed. A portion of a 3D model may, among other things, mean a face. 
         [0019]    According to a third aspect of the invention, a method of comparison of 3D models for the purposes of searching, of sorting, and/or of comparatively analyzing the boundary representation of 3D models is provided. According to this method, a descriptor is provided to each of a plurality of 3D models, descriptors with geometric characteristics of 3D models that are invariant depending on the modeling coordinate system and geometric characteristics of the 3D models that depend on the coordinate system. If needed, features not depending on the coordinate system are used to match the faces of a first 3D model and at least one other 3D model. A collection of data that is related to the pairing of at least some 3D models is stored. The method comprises providing a first result of search, of sorting, and/or of comparison of the boundary representations of 3D models, that uses at least partially the stored data issued from the pairing process. The method further comprises using the features, that are invariant depending on the coordinate system, in order to match the faces between the first 3D model and said at least another 3D model to build on these initial data from the pairing. A second result of search, of sorting, and/or of comparison of the boundary representation is provided using at least partly refined data issued from the matching process. 
         [0020]    The geometric characteristics of the 3D model that are invariable depending on the modeling coordinate system may include area, the eigenvalues of the moments of inertia, the perimeter of the planar faces or its type (plane, cylinder, for example), and geometric characteristics of the 3D model that depend on the modeling coordinate system may include the center of gravity and/or the axes of the moments of inertia of the planar faces. 
         [0021]    According to a fourth aspect of the invention, a method of comparison of 3D models for the purposes of searching, of sorting, and/or comparatively analyzing the boundary representation of 3D models is provided. The method comprises providing a descriptor to each of a plurality of 3D models, descriptors including characteristics of 3D models. The method further comprises assigning relative weight to one or more features in a first 3D model. The method comprises generating a numerical pairing value between a first 3D model and at least another 3D model based on the characteristics and, when applicable, the weight attributed to one or more of these characteristics of the first 3D model. 
         [0022]    According to a fifth aspect of the invention, a method of comparison of 3D models for the purposes of searching, of sorting, and/or of comparatively analyzing the boundary representation of 3D models is provided. The method comprises providing a descriptor to each of a plurality of 3D models. The method further comprises generating a numerical pairing value between a first 3D model and a plurality of other 3D models by using their respective descriptors. The method further comprises generating a display of multiple 3D models arranged spatially in clusters, where each cluster is defined according to common characteristics of the descriptor. Clusters may be based on a search query or based on the importance given to one or a plurality of descriptors characteristics, i.e. a weighting of descriptors. 
         [0023]    According to a sixth aspect of the invention, a method of comparison of 3D models for the purposes of searching, of sorting, and/or of comparatively analyzing the boundary representation of 3D models. The method comprises providing a descriptor to each of a plurality of 3D models based on the second order continuity of the faces&#39; underlying surfaces, commonly called ‘G2 continuity’, by regrouping distinct faces respecting the ‘G2 continuity’, and cutting faces whose underlying surfaces are not G2 continuous. 
         [0024]    According to seventh aspect of invention a method of comparison of 3D models for the purposes of searching, of sorting, and/or of comparatively analyzing of the boundary representation of 3D models is provided. The method comprises selecting distinct parts from at least two 3D models. The method further comprises identifying the respectively identical portions and qualifying the identified portions based on the type of differences. The method further comprises displaying at least one 3D model by marking the portions according to the qualification of the state (identical, type of difference). 
         [0025]    According to some embodiments, a search system used to find 3D models in a collection of 3D models uses a query 3D model through a 3D model descriptor is comprised of a selector of features/characteristics used to select at least one feature or a part of a 3D model or a descriptor to which we attribute a different weight for the purposes of the search, and a 3D models comparator, said comparator being configurable to compare a descriptor to a collection of descriptors taking into account said weight of said features or part of model 3D of the search query, and to generate a list of 3D models based on the comparison. 
         [0026]    The features selector may assign weight values to the characteristics of a descriptor of the said search query 3D descriptor. The system may also comprises a sorting system of search results, and a view generator configured in such a way to generate displayable scenes with at least a part of the list of the corresponding 3D models, positioned and organized according to preset criteria. Such sorted 3D models may be arranged on the basis of a similarity index computed from the descriptors. These pre-selected criteria may include a criterion that depends on the descriptor. The features selector may be configured to recognize significant descriptors in the resulting sets of 3D and to select one of the significant descriptors. Descriptors may comprise a volumetric component and a face or some other boundary representation. 
         [0027]    According to some embodiments, the process of manufacturing a product is characterized by the exploitation of a 3D model for the production of at least a portion of the product, the said 3D model being directly selected and possibly modified by using a system of search/comparison of 3D models or process according to either of the embodiments according to the present invention. 
       Definitions 
       [0028]    In this application, the following terms shall have the following meaning: 
       3D Model 
       [0029]    In this text, the expression 3D model is used to describe a digital representation in a space of dimension 3 of an object. A 3D model describes the boundaries between one or a plurality of objects and their environment. The boundaries are commonly based on boundary representations (B-Rep) as in the STEP standard or in geometric modelers of CAD systems or CAM systems for example or tessellations as in STL or VRML formats, for example. The boundary is composed of one or more faces, which is a surface limited by one or more edges. A face is a 3D model. a plurality of faces joined or not jointed is a 3D model. A set of faces representing a Euclidean sub-space of dimension 3 is generally known as solid body is a 3D model. A set of faces representing a plurality of solids is a 3D model. In the present definition, any part of a 3D model is a 3D model and any composition of 3D models is a 3D model. 3D models may comprise information other than purely geometric, such as the properties of the materials used or recommended manufacturing processes. 
       Descriptor 
       [0030]    A descriptor may be a representation of a model 3D adapted for a specific purpose, the representation being normally more efficient and more concise than the 3D model itself. The description may comprise a set of information that characterizes a 3D model or a part of it. In some cases, the descriptor comprises a list of volumetric characteristics of a 3D model for example and without being exhaustive, the dimensions of the bounding box of the 3D model, its volume, its area, its principal moments of inertia, its center of gravity, its principal axes of inertia, a list of solid bodies in the 3D model and for each of them, which is also a 3D model, the volume, the total area, the principal moments of inertia, the center of gravity and the principal axes of inertia. In some cases, the descriptor includes (without being exhaustive) a list of faces of the 3D model and for each of them, a list of features, comprising the type of the underlying surface and its parameters, the dimensions of the bounding box, the area, the perimeter, the moments of inertia, the barycenter, the principal axes of inertia for example. The differences and the similarities between 3D models are obtained from a process called comparison of descriptors. A 3D model can also be a descriptor. A 3D model may have several different descriptors. 
       Form Feature 
       [0031]    A form feature may be understood as a part or a property (or attribute) of a descriptor (and hence a 3D model) with a particular interest for a particular processing. A form feature or a characteristic of a shape may also be defined as a descriptor, or any combination of a plurality of elements of a descriptor. As examples, the value of the diameter of a cylindrical face is a basic form feature, the value of a center to center distance of two holes is a form feature, and a round ended keyway is a form feature. Each of these examples corresponds to a part of a descriptor where the form feature may be determined from the descriptors. In its most basic form, the form feature is more simply called feature or characteristic. A characteristic is said to be intrinsic to a 3D model or its descriptor if it depends only on the said 3D model or its descriptor and can be determined from it alone and not from the context, i.e. a 3D model that would encompass the feature. Otherwise, the feature is called extrinsic. 
       Pairing 
       [0032]    Pairing represents the process for determining of the matches between the characteristics of two descriptors. Part of a descriptor may, for example, characterize a solid body or a face. The pairing process matches the part of the descriptor to another part of a descriptor (the same one or another descriptor) when the two parts of the descriptors share similar characteristics (same or included in intervals of values for example). Such process allows, among others, to pair through the respective descriptors, solid bodies or faces of 3D models without taking into account their position in space. The pairing process does not require that the 3D models to be described with the same geometric representation (STEP and Parasolid, for example) or to be expressed in a common coordinate system. 
       Reconciliation 
       [0033]    Reconciliation represents a process of clustering of elements or portions of descriptors by taking into account the relative position in space of the form features associated with the paired portions of descriptors. The process proceeds by determining the groups of transformation matrices which allows the positioning of the form features in a common coordinate system. Said process allows among other things the recognition of the characteristics of identical or similar forms between 3D models. Thus, as an example at the level of the faces, the pairing identifies faces which share intrinsic characteristics. As an example, if the type of some faces is cylindrical, the diameter might be between 5 and 6 mm and the length is 20 mm. During the reconciliation, extrinsic parameters are taken into account. As an example, the direction of the axis of the cylindrical faces may be equal to the Z axis and the center to center distance may be equal to 20 mm. The pairing-reconciliation process may be applied iteratively. 
       Comparative Analysis of the Descriptors 
       [0034]    The comparative analysis of the descriptors is a process determining and to describing the identical and distinct characteristics between descriptors according to the query that is specified by the operator. The comparison is performed on the whole or only portions of the descriptor. A different weighting, specified by the operator, may be attributed to each part to emphasize on certain form features, or even to consider only a portion of the 3D model. The similarity index is determined from the comparative analysis of the descriptors. 
       Operator 
       [0035]    The operator refers to both a human operator as another computer system, interacting with the system, interactively or offline (batch mode). 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0036]    The embodiments of the invention will be better understood through drawings, which are listed below and which come with the number of examples appearing in the detailed description of the embodiments of the invention, among which: 
           [0037]      FIG. 1  shows a diagram of a sequence of steps of a process according to an embodiment of the invention; 
           [0038]      FIG. 2  shows a block diagram of a computer system according to an embodiment set to at least run the process shown in  FIG. 1 ; 
           [0039]      FIG. 3  is a view of a 3D model; 
           [0040]      FIG. 4  is a view of a simplified version of the 3D model of  FIG. 3 ; 
           [0041]      FIG. 5  is a view of the 3D model in  FIG. 4  that identifies in a generic way the faces of 3D models; 
           [0042]      FIG. 6A  is a view of the 3D model used as reference 3D model in the description of this realization; 
           [0043]      FIG. 6B  is a view of a 3D model similar to that shown in  FIG. 6A  to describe the process of comparison; 
           [0044]      FIG. 7A  is a view of the 3D models of the  FIGS. 6A and 6B  following an initial position; 
           [0045]      FIG. 7B  is a view of the 3D models of the  FIGS. 6A and 6B  following a second position; 
           [0046]      FIG. 8  shows a perspective view of the reference 3D model and an interface to the definition of constraints by the operator showing a set of constraints used to describe a particular; embodiment; 
           [0047]      FIG. 9  is a perspective view of a plurality of similar 3D models positioned and marked according to the result of their comparison with the reference 3D model and the constraints defined by the operator; 
           [0048]      FIG. 10  shows a block diagram of a version of the computer system of  FIG. 2  following a distributed architecture. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Detailed Description of the Embodiments of the Invention 
       [0049]    The embodiments of the invention are described according to  FIGS. 1 and 2  which show the sequence of steps to determine concomitant similarities and differences between a reference 3D model and a number of 3D models from their descriptors. The number of 3D models under consideration may vary tremendously. Insofar as the objective is to compare a reference 3D model to some known 3D models, such number may be low. In contrast, if the goal is to find an appropriate or similar 3D model, the search may be performed on thousands or even millions of descriptors of existing 3D models.  FIG. 2  shows a block diagram of a software system which can perform the steps shown in  FIGS. 1 and 2  in essence. 
         [0050]      FIG. 3  shows an example of a 3D model of a part. To simplify the description of the following embodiments,  FIG. 4  shows a simplified version of the 3D model of  FIG. 3 . The said simplified version will be used in the following description. The illustrated exhibit contains two circular openings of different size in its upper and lower parts and a middle part which connects the upper and lower portions. 
         [0051]    In  FIG. 5 , the faces are marked from Si, 1  to Si, 20 . Labelling is quite arbitrary, and can differ from a 3D model to the other. Thus the label Sm, f of a face identifies the face f of the 3D model m. The descriptor in this embodiment may consist of a list of characteristics, such as the type of the 3D model (Type), parameters depending of the type (TypePar), the volume, in the case of a solid body or area, in the case of a face (Int(N)), the area of a solid body or the perimeter of a face (Int(N−1)), the center of gravity (Gx, y, z), moments of inertia (M1, 2, 3), the axes of inertia (Ai x, y, z with i=1, 2, 3) and the dimensions of the bounding box (Bx, y, z) for each solid body forming the 3D model and for the complete 3D model, as well as for each of the faces composing the 3D model. 
         [0052]    The boundary representation does not respect the uniqueness property, i.e. more than one boundary representation may exist for a given 3D model. But said uniqueness property is essential to the comparison of 3D models. It is possible for example using different modeling systems (say two CAD systems) that the set of faces, composing the boundary of a 3D model, is not always unique. To solve this issue, “strictly G2 continuous” faces are used. Thus, faces may be grouped to form a single face if the second geometric derivative, usually denoted G2, is continuous along a common edge of the two faces. Similarly, a face whose underlying surface would not be G2 continuous would be split into multiple faces so that the underlying surface of each resulting face is G2 continuous. By proceeding in this way, the uniqueness property is restored at the level of the faces of the boundary representation. 
         [0053]    Table 1 presents the values of characteristics for the 3D model of  FIG. 6 a   . The link between the identifier of a 3D model in the descriptor (Mod3D column) and the 3D model itself could, for example, be resolved with a lookup table. 
         [0054]      FIG. 6 b    presents another example of 3D models. Table 2 shows the values of the characteristics of its descriptors. 
         [0055]    In  FIG. 1 , the step for building descriptors is S 100 . All 3D models are subject to this step. The said step may be performed at different times. Adequate descriptors may be stored with the data from the 3D models or separately. 
         [0056]    In  FIG. 2 , 3D models are stored in a data store referenced S 30 . The data store reference S 30  may be embodied as a single data store or as a distributed storage of 3D models. Descriptors generator S 32  reads the 3D models in data store S 30  and saves the descriptors in a second data store called S 34 . Said data store S 34  may be integrated in the S 30  data store, or may be separated and may also be remote. 
         [0057]    The system may comprise a 3D models management system S 40  controlling the 3D models to be compared. A selector or a generator of a reference 3D model S 42  allows an operator to select or create a reference 3D model. The descriptor of the reference 3D model may be generated using the descriptors generator S 32  and inputted to the search engine or comparison engine S 50 . The S 50  engine retrieves or fetches the descriptors from S 34  data store. 
         [0058]    The system described in  FIG. 2  may reside on an independent workstation or may be distributed among different computers and/or servers in order to ease the processing, storage and management of data. 
         [0059]      FIG. 7A  shows the 3D model of the  FIG. 4  on which is superimposed a second 3D model, namely that of  FIG. 6B . The latter presents differences from the reference 3D model in  FIG. 6A , namely the middle part is longer (the center to center distance increased from 120 mm to 150 mm), and the middle part connects to the bottom at a different angle of 30 degrees. The 3D model in  FIG. 6A  is the reference 3D model selected in step S 102  of  FIG. 1  and the 3D model in  FIG. 6B  is the one to which the reference is compared to explain the method. Such comparison is performed for each available 3D model. 
         [0060]      FIG. 7B  shows two 3D models in a different relative position. The systems described in the prior art use only a single relative position to compare 3D models. The relative position is either automatically determined from the coordinates system specific to each 3D model, either using a “best-fit” of the two 3D models or by an operator. The approach adopted in the following embodiments determines from the characteristics of the faces in the descriptors all relative positions that allow reconciliation of the form features (parts of the initial 3D models) from the compared 3D models. 
         [0061]    Although a comparison at the level of solid bodies between two 3D models may produce useful results for research purposes, such method may not be useful to identify a 3D model inside another 3D model (higher complexity), which would contain one or more parts of the searched 3D model. A comparison of the faces allows matching of the said faces to identify 3D models which may potentially contain the desired 3D model. The matching of faces is obtained through an iterative process of comparison of descriptors in two steps. The first step provides pairing based on intrinsic 3D model specifications. As an example the area or the moments of inertia of the intrinsic 3D model. The second step provides reconciliation based on extrinsic characteristics of the 3D model, for example the center of gravity or the axes of inertia of the 3D model, the said characteristics depending on the 3D model but also on the coordinates system in which it is described, and more generally from the context of the 3D model. 
         [0062]    The identification (in the labelling sense) of faces typically differs among compared 3D models. However, in the context of our simplified example, the numbering is identical only in order to facilitate the understanding of the process. Using intrinsic characteristics of faces of the descriptor, faces among 3D models are matched. For example, the values of the characteristics area Int(N), perimeter Int(N−1), and three moments of inertia M1, 2, 3 of faces Si, 5 ; Si, 18 ; Si, 6  and Si, 4  are unique and identical and therefore these faces are matched between the two 3D models with a maximum confidence index of 1. By contrast, the intrinsic values for faces Si, 7 ; Si, 8 ; Si, 16  and Si, 17  are not unique and involve multiple potential pairing of faces, for example S 1 , 7  with {S 2 , 7 ; S 2 , 8 ; S 2 , 16 ; S 2 , 17 } or even S 1 , 9  with {S 2 , 9 ; S 2 , 25 }. Such undetermined pairing of faces will be thrown during the step of reconciliation. For the surfaces S 1 , 1 ; S 1 , 2  and S 1 , 3  with S 2 , 1 ; S 2 , 2  and S 2 , 3  respectively, the values of the intrinsic characteristics are unique but some values differ between the faces of the two compared 3D models. The said faces of the two compared 3D models are paired with a confidence index being less than 1. The index may be calculated using different methods. For sake of simplicity, a simple method to calculate the index is presented. Such method uses the summation of the index for each characteristic taken into account divided by the number of considered characteristics. When used with a quantitative parameter, for example, the index is calculated following one minus the absolute value of the ratio of the difference of the values for this characteristic and their average value let&#39;s say |(Vref−Vcomp/((Vref+Vcomp)/2)|, and when used with a qualitative parameter, a table of values corresponding to the cases of difference. Understandably, the method is used only as an example and is defined otherwise in other embodiments of the process. The said index is involved in the determination of the index of similarity between 3D models in our embodiments. The number of faces of the two compared 3D models may be different, and at the end of the present stepsome faces may remain unpaired. 
         [0063]    The result of the comparison of the descriptors of the present simplified example and with the described embodiment after the pairing stage is presented in table 3. 
         [0064]    The table 3 shows a comparison between intrinsic characteristics of solid bodies showing an imperfect pairing (similar but not identical 3D models) followed by a comparison between intrinsic characteristics of faces. Several cases are shown, like the perfect unique pairings, or multiple pairing with identical characteristics values and pairing based on values of only partially identical characteristics and therefore with an index of confidence that is less than 1. Ambiguities are thrown in a subsequent phase of reconciliation. 
         [0065]    The pairing process has been described at the face level of a 3D model. We understand that a similar process is applicable at the body level to a plurality of solid bodies, if they exist in 3D models. Pairing is done using their intrinsic characteristics, such as volume (Int(N)), area (Int(N−1)), three Moments of inertia (M1, 2, 3) with the present example of descriptor following the same principle. The process therefore may also, as an example, be used to compare assemblies of 3D models, or even to find subsystems in more complex systems. Starting from the step S 120  (see  FIG. 1 ), the index of confidence corresponds to a temporary similarity index that is used to increase the efficiency of computation in the process. When a 3D model having an index of confidence computed in relation to the reference 3D model, falls below a threshold determined by the operator, the comparison between descriptors and the temporary index of similarity (step S 122  in  FIG. 1 ) is not refined. Such step provides a rapid indication of potentially similar 3D models and allows dealing with a great number of 3D models without the need to refine the comparison when not required. 
         [0066]    The pairing compares 3D models or of portions thereof, which are herein known as 3D models (be it a face, a set of faces (form feature), one or several solid bodies) by analyzing intrinsic parameters of the descriptor. At this stage, each 3D model is considered in isolation without taking into account the relative position of the 3D model in comparison with other 3D models. 
         [0067]    The scale of a 3D model may generally be considered as being well defined and a low index of confidence on dimensional characteristics may be considered as a ground to reject a pairing. However, in some cases, a scaling factor may be determined during the process of pairing of the faces, and that pairing may thus be realized for a given scale factor. 
         [0068]    The addition of the data in the rows of the table for each 3D model which is compared to the 3D model of reference is performed in step S 124  of  FIG. 1 . When a threshold number of similar 3D models is obtained or when all available descriptors were compared, the refinement of the comparison process may continue (in step S 126 ). From the step S 126 , the method may further comprise a step to identify the 3D models being the mostly similar based on for example the number of paired faces or the ratio of the sum of the areas of paired faces and the sum of the areas of all faces, or any other function that would determine a temporary similarity index. Referring now to  FIG. 1 , the method further comprises the step of reconciliation of the 3D models. Based on the above definition, the 3D models may be one or a plurality of faces or one or a plurality of solid bodies. The method may further comprise focusing on the most promising 3D models. 
         [0069]    In  FIG. 2 , the comparison engine S 52  performs the comparison of descriptors and the storage in the data store S 54  of the comparative data presented in the tables. The engine S 50  controls the process and performs the computation of a similarity index. 
         [0070]    The step of reconciliation S 140  shown in  FIG. 1  comprises taking into account the extrinsic characteristics of descriptors and more particularly the relative positions of the 3D models therebetween. Using the definitive pairings (having a confidence index=1), transformation matrices of the coordinate systems are determined. The transformation matrices reposition the compared 3D models in a common coordinates system, such as the coordinate system of the reference 3D model. The determination of the transformation matrices is well-known in the art and is a fairly routine operation. At this stage, several transformation matrices are created. When applied to the 3D models, some of the matrices are used to reconcile only the 3D models that helped in the computation of the matrices. The relevance of such matrices is thus low and the matrices are discarded at the step S 142 . 
         [0071]    Understandably, the transformations or the transformations matrices to the coordinate systems may not be calculated between all the geometric characteristics of the descriptors (parts of 3D models, for example faces) to define at least a group of identical transformations (taking into account computational tolerances), just like a transformation for a first characteristic (e.g. a first face) may be computed to then try to apply the said transformation to the other characteristics (e.g. other faces). Accordingly, a group of characteristics having a common transformation may be developed. 
         [0072]    For each repositioning obtained by applying transformation matrices which are retained, the extrinsic characteristics are compared (step  144 ). In the present example, two matrices are retained. A first matrix M1 positions 3D models as shown in  FIG. 7A . The faces Si, 5 , Si, 6  and Si, 18  which were already positively paired are reconciled and perfectly matched together. The faces are determined as being identical for the specific positioning. Using generated matrix, the pairing ambiguities of the faces Si, 7 ; Si, 8 ; Si, 9 ; Si, 15 ; Si, 16  and Si, 17  are discarded. The remaining faces are reconciled and are also determined as being identical for the positioning. Finally, the extrinsic characteristics of descriptors of the faces S 1 , 2  and S 1 , 10 , with S 2 , 10  and S 2 , 14  are compared. Upon comparison, multiple values are determined as identical and others as different. The faces are reconciled with a confidence index of less than 1. The faces are identified as being different and the identified differences are qualified using the comparison of the descriptors as will be demonstrated at the marking stage. The second matrix M2 is applied to position the 3D models as represented in  FIG. 7B . The faces Si, 4  and Si, 6  as positively paired, are reconciled to perfectly match together. Therefore the paired faces are declared identical for this second positioning. Finally, the faces Si, 11 ; Si, 12  and Si, 13  are reconciled using an index of less than 1 and thus comprising differences for the particular positioning. Based on the predetermined threshold value of the confidence index, a face such as Si, 3  is also reconciled. A plurality of transformation matrices may lead to reconcile some faces multiple times. In such an event, the reconciliation having the best confidence index value is used. These matrices do not help resolve all ambiguities in all cases and sometimes some faces remain orphaned. Such faces are new faces, or heavily modified faces. 
         [0073]    Table 4 presents the data added by the stage of reconciliation for the present example. All data of the table 4 or only data having a certain interest to the continuation of the process and to the needs of the operator may be stored. 
         [0074]    It is found that the principle of multi positioning introduced in this invention completely redefines the concept of comparison and differences between 3D models and allows comparison of parts of 3D models (form features). Thus the comparison can be executed using all transformation matrices, or by using only one or more particular matrices, or even by constraining the determination of a matrix on some characteristics of the descriptors selected by the operator. Understandably, in step S 146 , similarity indices that depend on these choices may be computed. 
         [0075]    The method may further comprise the truncating of the table of comparison data to remove multiple and ambiguous pairing of faces which were introduced during the pairing step for which the values of the intrinsic characteristics are considered non-relevant during reconciliation (step S 148 ). Table 5 shows the comparison data after being cleaning out in the context of the present example. 
         [0076]    The refinement of the comparison process continues until a sufficient number of similar 3D models either is reached or that all the available descriptors have been compared in step S 150 . 
         [0077]    Understandably, such a process of comparison between 3D models is useful for many applications such as retrieving similar 3D models, classifying 3D models according to an index of similarity, making a classification (clustering) of the 3D models, highlighting the same or different characteristics, or still allowing identification and reconciliation of references (identifiers) when a 3D model is substituted for a reference 3D model. 
         [0078]    The reconciliation engine S 56  (see  FIG. 2 ) carries out the above-mentioned operations and updates data in the data store S 54 . 
         [0079]    Referring to  FIG. 2 , the method comprises identifying the 3D model having the closest similarity to the reference 3D model using the engine S 50  which relies on data from the tables in the data store S 54  powered by engines S 52  and S 56  The identified 3D models are now ready to be displayed to the operator through the system S 46 . The system S 46  generates a requested view of the 3D models. To generate the view, the system S 46  fetches the 3D models stored in the data store S 30  and the marking engine S 45  uses the data from the comparison data store S 54  to mark identical or different faces or to mark other characteristics of the 3D models. The operator selects the desired settings or marking criteria through the interface S 44 . The interface S 44  also allows the selection of the properties and functions which determine the layout of 3D models in a 3 dimensional space generated by the system S 46 . In certain embodiments, S 46  uses a CAD system or a Web browser (web viewer) to display the results in 3D. The layout and marking of the displayed 3D models vary depending on the needs of the operator. For example, in some cases, the operator may want to highlight the identical parts (form features) of 3D models for a particular positioning, or for multiple positioning or even highlight differences for one or more characteristics. It is believed that such method of simultaneously communicating the comparison of several 3D models based on the marking and the position of the 3D models in a 3D scene, such as illustrated in  FIG. 9 , is entirely new. 
         [0080]    Understandably, several types of differences between face, sets of faces (form features) and solid bodies are determined when 3D models are compared. The marking distinguishes the said 3D models according to the requests of the operator. The following presents some examples illustrating the types of differences according to the needs of the operator. In a first example, the operator searches, in a set of 3D models, for feature forms identical to those present in the reference 3D model without inputting said feature forms. In this case, the process executes pairing, reconciliation, multi repositioning and marking of faces as a result. The faces Si, 4 ; Si, 5 ; Si, 6 ; Si, 7 ; Si, 8 ; Si, 9 ; Si, 15 ; Si, 16 ; Si, 17 ; Si, 18  respectively on the reference 3D models (i=1) and on the compared one (i=2), are fully identical at a given position (a transformation matrix) and are therefore described as identical and marked accordingly (using for example the color blue). The faces Si, 1 ; Si, 2 ; Si, 11 ; Si, 13  and faces S 1 , 10 ; S 1 , 14  with face S 2 , 10  of the 3D models are first paired with a low index of confidence. The index of confidence is reviewed to be increased during reconciliation. The said faces are eventually marked as having identical geometry but different topologies (using for example the color green) because they share the same geometric characteristics (axis and radius for the cylindrical surfaces S 1 , 10 ; S 1 , 14  and S 2 , 10  and the same normal and position for the planar faces Si, 1 ; Si, 2 ; Si, 11 ; Si, 13 ) but differ on other characteristics (values) of their descriptors which characterize their topology (perimeter for example in our descriptors). The pairing and reconciliation of the face Si 13  of the compared 3D models do not return a level of confidence being high enough to conclude with confidence that the face is the same as the modified face. At this stage, a few unreconciled faces remain so the best choice is remaining. In this case, the characteristic Type is identical and depends on the threshold value of the confidence index. The characteristic is identified as “reconciled and different” (using for example the color purple colour) or simply identified as “not reconciled and new” (using for example the color red). The faces are different both from the point of view of their geometry and their topology for all selected transformation matrices. Faces S 2 , 19 , and S 2 , 20  are identified as “non-reconciled”, so new (using for example the color red color). 
         [0081]    In another example, the operator selects, through the interface S 44  ( FIG. 2 ), a portion of the 3D model (which becomes de facto the reference 3D model). The portion of the 3D model represents the functional faces or faces in contact with other components (interfaces), as an example to illustrate the present, faces S 1 , 5 ; S 1 , 1 ; S 1 , 18  which are also used to define a positioning (transformation matrix) for the step of reconciliation, as well as the surfaces S 1 , 6 ; S 1 , 4 . To ease the interpretation of the results, the operator inputs that the identical faces on the found 3D models be marked in blue, that the reconciled surfaces with identical geometry but whose topology is different be marked in cyan and finally that the other faces (not taken into account, not reconciled, new) to be grayed out and transparent. Now referring to the 3D models of  FIGS. 6A and 7B , that the faces S 2 , 5 ; S 2 , 18  are identified as identical (hence in blue), that the faces S 2 , 1 ; S 2 , 4 ; S 2 , 6  are geometrically identical (hence in cyan) and that all the other faces are not considered (hence in grey, transparent). 
         [0082]    Understandably, the operator may set extremely precise constraints using an appropriate graphical interface S 44  such as e.g. impose the center to center distance and the diameters of the faces Si, 5  and Si, 6  or the parallelism and the distance between Si, 11  and Si, 13 . All these constraints may be computed from the characteristics of the descriptors contained in this embodiment. 
         [0083]    By displaying a 3D model with a label or with different textures or colors associated to specific faces is well-known in the art. 
         [0084]    Differences are represented using colors, transparencies, textures, hatches, annotations or any other graphic effect that may be considered as being a marking. The similarity between the 3D models is represented with the position of the 3D models in the 3D space of the 3D scene displayed in the viewer. The similarity is typically known as the 3D models having the lowest number of differences according to the operator requirements. 
         [0085]    It shall be understood that a wide range of markings may be used. Thus, similarity is expressed by the respective positions in the 3D space of 3D models obtained by the function computing the index of similarity. The similarity may also be appreciated from the marking of differences in 3D models. For example, if a hole from the reference 3D model is smaller in diameter than the holes of the other compared 3D model but comprises an identical axis, the 3D model will be marked in some way; on the other hand, if the diameter and the axis are different, the said hole is marked using a different marking to differentiate the two types of differences. 
         [0086]    In certain embodiments, the process of comparison of the descriptors is influenced by the definition of characteristics of interest or by those on the contrary that are not of interest. The definition of characteristics may be explicitly or implicitly specified by the operator. In step S 152  of  FIG. 1 , 3D models are selected according to similarity indices and the criteria expressed by the operator. The results are formatted and displayed in step S 160 . Among other possible forms, 3D models displayed in a 3D space as shown in  FIG. 9 , with identification by marking, as described above, of the similarities and differences and the use of the positioning within the 3D space of 3D models is new and represents the way of communicating the results. We understand that these results may also be transmitted in text format (table, list or other form). 
         [0087]      FIG. 8  shows the simplified 3D model of  FIG. 4  and represents an example of interface for the definition of the comparison constraints. In this case the full 3D model is taken into account to make the comparison by authorizing the multi repositioning for similarity assessment, and the constraints have been imposed such as (i) the distance between the axes of the cylinders Si, 5  and Si, 6  must be between 120 and 150 mm, (ii) the faces Si, 18  and Si, 5  must be parallel, (iii) Si, 6  must have a radius of 20 mm and finally (iv) the distance between the faces Si, 11  and Si, 13  must be greater than 10 mm. The constraints may be determined using the constraints determination interface S 48  shown in  FIG. 2 . The operator has the ability to define if all or only a portion of the 3D model is taken into consideration. In this case, the operator selects portions of the 3D model to be used (which are also 3D models) and for each part, the operator indicates if the portions of the 3D model should be identical or only similar with the 3D models to be compared. The operator further selects the possibility of using multi repositioning or of imposing a coordinates system to make the comparison. As an example, the coordinate system may be the current coordinates system of the 3D models or a specific coordinates system built from constraints to be imposed. Finally, the operator may set constraints that are of greater importance to him. As examples, the user may set constraints such as a center to center distance between 120 and 150 mm for the two cylinders Si, 5  and Si, 6 , a radius of 20 mm for cylinder Si, 6  and a distance greater than or equal to 10 mm for the faces Si, 11  and Si, 13 . The operator therefore builds constraints directly on the explicit characteristics of the descriptors (radius of Si, 6 =20 mm) but also on implicit characteristics (distances between axes Si, 5  and Si, 6  or parallelism between Si, 18  and Si, 5 ). Such implicit characteristics are added in the tables containing the results of comparison (additional columns) to participate in the calculation of the index of similarity. 
         [0088]    This way of defining constraints is similar to method provided by the CAD systems to constrain sketches or assemblies and is known in the State of the art. 
         [0089]    Understandably, the inventory of properties or available constraints, their mode of selection, their layout and ordering, as well as how the properties are weighted may varied in a multitude of variations without departing from the underlying functionality. Rather than offering a simple binary selection (distinguishing a selection “keep/important” of another “withhold/not-important”), the interface could, for example, accept a value of weighting expressed as a percentage of importance or another calibrated value. Similarly, the operator may eliminate parts or portions of 3D models that are considered insignificant to the application of the operator. As an example solid bodies smaller than a given size (size of the bounding box) or volume, or faces whose area would be less than a certain percentage of the total area of the 3D model (3D model simplification) could be eliminated. It is also possible to force the comparison by a volume of maximum occupancy (reservation of space in an Assembly). 
         [0090]    During the process of comparison, constraints such as for example, expressing the distance between the two cylinders can be used as a filter (Go/No Go) or intervene only during the marking stage to show that the constraint is satisfied or otherwise unmet. These constraints may also be taken into account when computing the index of similarity which can then be seen as an indication of compliance with the constraints. 
         [0091]    It shall be understood that when constraints are changed, the entire process may be repeated or only the index of similarity and marking of already selected 3D models may be computed. 
         [0092]    In certain embodiments, 3D models are ordered following the comparison process based on pairing and reconciliation of descriptors according to the computed similarity index.  FIG. 9  shows an example of eight 3D models of a component of a hinge similar the reference 3D model (i.e. to the 3D model used in the comparison for the purposes of the presented search). The 3D models are positioned in an isometric 3D view (for example, an Assembly in CAD system). It shall be obvious that the operator may change the perspective. 
         [0093]    The 3D model used as the reference 3D model is positioned at the origin (or the bottom right corner). The faces in blue (marked with a *) are taken into account in the marking of differences after the comparison. The faces in grey (not identified faces) will not be marked whether such faces are identical or different to facilitate interpretation of the results for example. Similar 3D models are positioned in a 3D space using criteria related to each of the three axes. Marking (colors, textures, transparencies, annotations, etc.) may represent other criteria or information. In particular, in this figure, one of the axes is used to represent a similarity index. The more a 3D model differs from the reference 3D model, the more the distance increases along this axis. The 3D models having an index of similarity of the same order of magnitude are grouped along the second axis. Thus two 3D models are displayed in the first row directly next to the reference 3D model, one of the two models is an identical one and the other is a mirror one (left/right hand, e.g. planar symmetry). The only resulting 3D model which is different but satisfies all the constraints (no yellow face, no face marked in the attached figure) is positione in the second row. 3D models that do not satisfy all constraints and differ more and more compared to the reference 3D model are displayed in the following rows. The first 3D model of the third row has a different groove and the faces are marked accordingly (in yellow, marked by a * in this figure). The four holes and the boring (all faces marked by *) are different in the next 3D model in the same row. 
         [0094]    In the present example, the third axis is not used. The third axis may be used to represent other information such as versions, origin of issue, steps of manufacturing or any other classification of 3D models that it is of interest to the operator. 
         [0095]    Understandably, the reference 3D model may be derived from an existing scanned component (part or mechanism) or a more or less roughly sketched 3D model by the operator on the screen. In the latter case, the operator may have omitted some details that appear nevertheless among searched 3D models. Such an interface may allow the operator to switch from the initial reference 3D model to one of the resulting 3D models listed in the results of the search. When the reference 3D model is substituted, the operator may optionally maintain the previous comparison constraints or define new ones. 
         [0096]    It shall be understood that the above described system of 3D model comparison may be a powerful tool in the search, the analysis, or the organization (classification, clustering) of 3D models. In many industries and other domains, the use of the system as well as the above described methods allow for the saving of time throughout the life cycle of the products, including at design and the manufacturing stages of the products. 
         [0097]    As shown in  FIG. 10 , the system in  FIG. 2  may be deployed as distributed system on multiple computers, the Web (the cloud), or on an intranet, allowing remote access to an operator, to data stores of 3D models, to stores of descriptors, to search and comparison engines, to marking systems or other add-ons. In the example in  FIG. 10 , search and comparison tasks are performed by a remote server from the operator workstation. Marking engine and the engine used to compute the associated 3D scene, are on the search server. In other embodiments, the marking engine may run on client-side. The 3D scene and 3D models are sent to the operator for use in a browser (web browser) for example. Similarly, according to the illustration, storage of descriptors is remotely hosted. The generation of the descriptors may constitute a separate service for 3D models data stores. The system of  FIG. 10  shows also three data stores at different location, separate from 3D models. 
         [0098]    The use of such a system allows an operator to browse, search, and compare 3D models of a plurality of sources from a single client workstation. 
         [0099]    The use of such a system allows an operator to upload his existing 3D models for the purpose of generation of descriptors using a remote service, whether his 3D models are for search and comparison by him and him alone, or for a search and comparison made by others also. 
         [0100]    Table 1: Value of the characteristics of the descriptor for the 3D model of  FIG. 6  A 
         [0101]    Table 2: Value of the characteristics of the descriptor for the 3D model of  FIG. 6  B 
         [0102]    Table 3: Results after pairing of 3D models 
         [0103]    Table 4: Results after pairing and reconciliation of 3D models 
         [0104]    Table 5: Results cleaned after pairing and reconciliation of 3D models (not final)