Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
  • G06F16/50—Information retrieval; Database structures therefor; File system structures therefor of still image data
  • G06F16/58—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
  • G06F16/583—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content
  • G06F16/5854—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content using shape and object relationship
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F30/00—Computer-aided design [CAD]
  • G06F30/20—Design optimisation, verification or simulation

Definitions

• the field of art disclosed herein pertains to a three-dimensional data processing apparatus, a three-dimensional data processing method and a three-dimensional data processing program. More particularly, the present invention relates to an apparatus, a method or a program that has capabilities to search for an object similar to a predetermined shape from inputted three-dimensional shape models (e.g., computer-aided design (CAD) models or mesh models) and is able to change the search scope in terms of size and/or proportion.
• CAD computer-aided design
• the present disclosure is directed, in general, to computer aided design, drafting, manufacturing, and visualization systems (individually and collectively, "CAD systems").
• CAD systems often use databases of geometric models, both two-dimensional (2D) and three-dimensional (3D).
• the method includes, for each 3D triangle of the received triangular mesh data of the 3D object evaluated as a reference triangle: (i) identifying one or more adjacent triangles that share a side with the reference triangle; (ii) calculating a value for the length of the perimeters of the adjacent triangles (total perimeter or the equivalent identifying value based on conditions for congruence of triangles); and (iii) assigning the reference triangle the calculated value.
• the method includes comparing the calculated values assigned to the 3D object to calculated values assigned to the reference object; and determining whether a match exists between the 3D object and the reference object based upon an amount of matching of the obtained and stored calculated values.
• FIG. 15 illustrates a flow diagram presenting an example method for comparing two or more three-dimensional (3D) object models, according to one or more embodiments.
• the 3D model may include a polygon mesh.
• the polygon mesh is a triangle mesh and the reference polygon is a reference triangle.
• the systems and methods of the present invention provide for obtaining triangular mesh data of a 3D object (e.g., from a slicer program).
• the scalar value computed from the data of each layer of each of the orientations are obtained and compared to stored scalar values for a reference object to determine a degree of matching.
• measurement data is facilitated by processing software.
• smaller objects within the 3D object are also analyzed.
• each triangle in the triangular mesh data is analyzed by numerically combining the scalar values computed from of surrounding triangles to assign a value.
• matching with the reference object is made based on the assigned combined scalar values.
• the 3D object can be scaled in one, two or three orthogonal dimensions to match the reference object.
• the method includes receiving triangular mesh data describing two or more 3D object models.
• the method includes assigning one of the two or more 3D object models as a reference object.
• the method includes evaluating at least one 3D triangle from each received triangular mesh data of the two or more 3D object models as a reference triangle, and for each reference triangle: (i) identifying one or more adjacent triangles using conditions for congruence of triangles; and (ii) performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle.
• the method includes comparing the object hash value to one or more reference hash values assigned respectively to one or more 3D object models.
• the method includes determining whether a match exists between one or more 3D object models and the reference object based upon an amount of matching of obtained hash values.
• a method for identifying deviations in an object.
• the method includes receiving first triangular mesh data describing an object at a first time.
• the method includes evaluating at least one 3D triangle from the received triangular mesh data by (i) identifying one or more adjacent triangles using conditions for congruence of triangles; and (ii) performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle.
• the method includes creating a first 3D reference model comprises the respective object hash values for the at least one triangle of the first triangular mesh data.
• the method includes receiving second triangular mesh data describing one of a similar object or the object at a second time that is subsequent to the first time.
• the method includes evaluating at least one 3D triangle from each received second triangular mesh data for each reference triangle: (i) identifying one or more adjacent triangles using conditions for congruence of triangles.
• the method includes performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle.
• the method includes creating a second 3D reference model comprises the respective object hash values for the at least one triangle.
• the method includes comparing the first and the second 3D object models.
• the present innovation relates generally to a novel system and methods of comparing two or more three-dimensional (3D) object models.
• the present innovation relates to a three-dimensional data processing apparatus, a three-dimensional data processing method and a three-dimensional data processing program. More particularly, the present invention relates to an apparatus, a method or a program that has capabilities to search for a part similar to a predetermined shape from inputted shape models (such as CAD models or mesh models) and is able to change the search scope in terms of size and/or topology.
• matching with the reference object is made based on the assigned total perimeter values.
• the calculated values for the 3D object and the reference object do not have to correlate 1 : 1 but can be proportional.
• the two items can be differently scaled and the matching may be achieved by normalization, standardization, etc.
• the 3D object can be scaled in one, two or three orthogonal dimensions to match the reference object.
• the various methods are utilized according to the average processing time needed for calculations.
• the method and process steps are not co-dependent and can be used in a variety of combinations to evaluate similarities and differences between two or more three-dimensional (3D) object models.
• the analysis methods may be used independently, together with another one or more other analyses, in any given order, and may include other processes for further data collection on a case-by-case basis.
• the present innovation relates to a similar shape comparison and retrieval apparatus 100 that comprises: (i) a reference shape model inputting unit 102 for providing a reference shape model; (ii) a test shape model inputting unit 104 for providing a test shape model; (iii) a comparison and retrieving unit 106 for searching for a shape model similar to the test shape model; and (iv) a display unit 108 for displaying any one of the test shape model that is determined as being similar to the reference shape model.
• the comparison and retrieving unit desirably comprises: (i) a file converting module (optional) 110; (ii) a mesh generating module (optional) 112 for meshing the shape model to obtain a shape mesh model; (iii) a parameter calculating module 116 for calculating the parameters of the partial shape model; (iv) an object extracting module 118 for dividing the shape model into one or more partial shape models; (v) a comparison calculating module 120 for comparing the amount of similarity of parameter characteristics of the shape model with the parameter characteristics of the reference shape model.
• the comparison and retrieving unit desirably comprises: (i) a file converting module (optional) 110; (ii) a mesh generating module (optional) 112 for meshing the shape model to obtain a shape mesh model; (iii) an object slicing module (optional) 114 for slicing the shape model to obtain slice parameters of the shape model; (iv) a parameter calculating module 116 for calculating the parameters of the partial shape model; (v) an object extracting module 118 for dividing the shape model into one or more partial shape models; (vi) a comparison calculating module 120 for comparing the amount of similarity of parameter characteristics of the shape model with the parameter characteristics of the reference shape model.
• STL STereoLithography
• STL is a file format native to the stereolithography CAD software created by 3D Systems.
• STL has several after-the-fact backronyms such as "Standard Triangle Language” and "Standard Tessellation Language”. This file format is supported by many other software packages; it is widely used for rapid prototyping, 3D printing and computer-aided manufacturing.
• One advantageous method to model 3D data is to triangulate the point cloud to generate a mesh of triangles having the digitized points as vertices.
• 3-D triangular meshes are a known surface modeling primitive used to represent real world and synthetic surfaces in computer graphics. Each triangle 'knows' about its neighbors, which is the structure that allows fast processing of the geometry represented by the triangulation. It is important to stress that the same set of vertices or data points could have several triangulations. The emphasis, therefore, is on the vertices themselves, rather than the ' surface' as represented by the triangles.
• a triangle mesh representation consists of information about geometry and connectivity, also known as topology. Geometry defines the location of vertices in a (Euclidean) coordinate system. They are represented as triplets (x, y, z). Connectivity defines the sets of points that are connected to form triangles or faces of the mesh. Triangles are given by three index values, which identify the three vertices bounding the triangle.
• density calculations can be performed as another source of information for matching objects.
• artificial intelligence can be incorporated to extend use cases to predictive and even prescriptive analyses.
• One or more embodiments may employ various artificial intelligence (Al) based schemes for carrying out various aspects thereof.
• classification may employ a probabilistic or statistical-based analysis (e.g., factoring into the analysis utilities and costs) to forecast or infer an action that a user desires to be automatically performed.
• a support vector machine is an example of a classifier that may be employed.
• the SVM operates by finding a hypersurface in the space of possible inputs, which the hypersurface attempts to split the triggering criteria from the non-triggering events. Intuitively, this makes the classification correct for testing data that may be similar, but not necessarily identical to training data.
• Other directed and undirected model classification approaches e.g., naive Bayes, Bayesian networks, decision trees, neural networks, fuzzy logic models, and probabilistic classification models
• Classification as used herein, may be inclusive of statistical regression utilized to develop models of priority.
• One or more embodiments may employ classifiers that are explicitly trained (e.g., via a generic training data) as well as classifiers, which are implicitly trained (e.g., via observing user behavior, receiving extrinsic information).
• SVMs may be configured via a learning or training phase within a classifier constructor and feature selection module.
• a classifier may be used to automatically learn and perform a number of functions, including but not limited to determining according to predetermined criteria.
• One application would be a “Doctor ATM” or “ADM (Automatic Doctor Machine)” that uses a CT scanner to look at an entire body, identify individual components such as organs and compare these components to previous scans of known healthy and diseased organs and look for early indicators of diseases and cancers. The comparison can also be made to a previous model made of the same individual to detect a trend. Regular scanning would allow our algorithm to make alerts if a known pattern emerged that is indicative of the early onset of a disease such a degenerative skeletal condition, a type of cancer, or an enlarged heart.
• ADM Automatic Doctor Machine
• FIG. 6 illustrates a flow diagram of an example method 600 of expedited matching using slice perimeter measurements, according to one or more embodiments.
• Method 600 begins receiving triangular mesh data describing a three-dimensional (3D) object (block 602).
• Method 600 includes, in each of three orthogonal orientations, obtaining dimensional layers of the 3D object from a slicer program (block 604).
• Method 600 includes obtaining a perimeter length value for each layer of each of the three orthogonal orientations (block 606).
• Method 600 includes comparing the obtained perimeter length values to stored perimeter length value for a reference object (block 608). Method 600 includes determining whether a match exists between the 3D object and the reference object based upon an amount of matching of the obtained and stored perimeter length values (block 610). Then method 600 ends.
• FIG. 7 illustrates a flow diagram of an example method 700 of rigorous matching associating each reference triangle of a 3D triangular mesh with perimeter totals for adjacent triangles, according to one or more embodiments.
• Method 700 begins receiving triangular mesh data describing a three-dimensional (3D) object (block 702).
• block 704 for each 3D triangle of the received triangular mesh data of the 3D object evaluated as a reference triangle:
• Method 700 includes identifying three adjacent triangles that share a side with the reference triangle (block 706).
• Method 700 includes calculating a total perimeter value for the length of the perimeters of the three adjacent triangles (block 708).
• Method 700 includes assigning the reference triangle the total perimeter value (block 710).
• Method 700 includes comparing the total perimeter values assigned to the 3D object to total perimeter values assigned to the reference object (block 712). Method 700 includes determining whether a match exists between the 3D object and the reference object based upon an amount of matching of the obtained and stored total perimeter values (block 714). Then method 700 ends.
• stages include: a. Design Stage i. CAD ii. 3D Models b. Actualization i. Production ii. Scans of 3D part using laser scan c. Utilization i. Wear & Tear ii. Performance iii. Scans of 3D part using laser scan
• examples of uses include: (i) CAD (SolidWorks, SolidEdge, AutoCAD); (ii) ANSI and other standards compliance; (iii) Searching for similar models and similar differences; (iv) Differences between models or versions; (v) Searches for physical attributes and within certain cases - defined tolerances; (vi) Add: quality control to see that a part (scan or 3D drawing) not just same part/item but any changes: (a) +tol erance adherence for example +/-; and (b) For example, add in that the gold standard is x, but has a tolerance is Y.
• aspects of the present innovation look to improve quality control by improving speed and efficiency, especially as compared to generally-known visual human inspection that is slow and costly and can only do so many inspections.
• a coordinate measuring machine is a device used in the measurement of the physical geometrical characteristics of an object. These machines can be manually controlled by an operator or they may be computer controlled. Measurements are defined by a probe attached to the third moving axis of this machine. CMM is also a device used in manufacturing and assembly processes to test a part or assembly against the design intent. By precisely recording the X, Y, and Z coordinates of the object, points are generated which can then be analyzed via regression algorithms for the construction of features. These points are collected by using a probe that is positioned manually by an operator or automatically via Direct Computer Control (DCC). DCC CMMs can be programmed to repeatedly measure identical parts; therefore, this can be seen as a specialized form of industrial robot.
• DCC Direct Computer Control
• 3D scanners measure the geometries of a physical part and brings it into the digital world.
• the data output is typically a point-cloud represented in STL (stereolithography) file format. This data is used to compare to the original CAD drawings or to a previous scan of gold standard part within tolerances.
• STL stereolithography
• Non-contact techniques are generally used, i.e., no physical probe touches the part.
• Non-contact techniques all generally detect some form of energy emanating from the sample being probed. Suitable energy forms include light, heat, and sound.
• the light may include one or more of visible light, infrared (IR) light, near-infrared (NIR) light, and ultraviolet (UV) light.
• Energy detectors suitable for light detection include photodetectors, for example a photodiode, a position sensitive device, an array detector, and a CCD (charge coupled device).
• Energy detectors suitable for heat detection include infrared imagers.
• Energy detectors suitable for sound detection include ultrasonic transducers.
• the energy emitter imparts energy onto the part.
• the energy is a radiative form, such as light, heat, and/or sound. Whatever the form of energy, the energy emitter does not typically impart enough energy to damage or otherwise interfere with the part.
• Energy emitters suitable for light emission include lamps, wide-field illuminators, structured illuminators, lasers, laser scanners, flash lamps, and modulated illuminators.
• dimensional measuring device may be configured to use ambient light as a supplement or alternative to a light energy emitter. Accordingly, an energy detector may be configured to detect ambient light reflected and/or transmitted by the part.
• Energy emitters suitable for heat emission include heaters.
• Energy emitters suitable for sound emission include ultrasonic transducers.
• 3D Scan e.g., laser scan
• helper software e.g., Polyworks
• 3D Scan e.g., laser scan
• helper software e.g., Polyworks
• 3D scanning equipment can be usable on large structures such as for inspection of cell towers and military antenna.
• the 3D scan data can be used for the required twice annual inspections to confirm that alignment of the tower and attached antennae are providing a best field of view/reception.
• scanning can be performed by an automated drone that scans with a Lidar, laser, computed tomography (CT), and photogrammetry, etc., to get 3D model.
• CT computed tomography
• the present innovation can compare relevant aspects of a scanned object to a previously determined gold standard such as a designated CAD drawing or preciously scanned object in terms of relevant parameters such as height, center line, angle, etc. User can put in tolerances as defaults or user set by number or percentage, etc.
• a method for modeling a cell site with an Unmanned Aerial Vehicle comprising causing the UAV to fly a given flight path about a cell tower at the cell site; obtaining a plurality of scans of the cell site about the flight plane; and obtaining and processing the plurality of scans to define a three dimensional (3D) model of the cell site based on the one or more location identifiers and/or one or more objects of interest.
• UAV Unmanned Aerial Vehicle
• An example Key4++ function is a 64-bit integer (key exponent, mantissa uKeyC, mantissa al, mantissa a2, mantissa a3) where uKeyc, uKeyC_al, uKeyC_a2, uKeyC_a3 are as defined in Key4 but with no digit founding applied.
• Key exponent is the 11 -bit exponent of max( uKeyC, uKeyC al, uKeyC_a2, uKeyC_a3).
• mantissa_* is the 13-bit mantissa (significant digit part) of uKeyc, uKeyC_al, uKeyC_a2, uKeyC_a3 respectively.
• FIG. 13 depicts KeyV facet neighbor edge hashing.
• FIG. 14 depicts KeyE or Key 10 facet neighbor edge hashing.
• KeE or Key 10 is a face neighbor edge hashing that extends the concept of KeyC to a next order of triangle adjacently: Tuple (KeyC, KeyC_al, KeyC_al 1 , keyC_al 2, KeyC_a2, KeyC_a21 , KeyC_a22, KeyC_a3, KeyC_a31, KeyC_a32)).
• Curvature Hashing The present disclosure extends the concept of extracting numerical properties from groups of neighboring triangles.
• the Gaussian curvature of a surface is a mathematical measurement of the rate of directional change along a surface. This method approximates the Gaussian curvature of a surface at a triangle and multiplies it with the area to obtain an area normalized Gaussian curvature. This value is used combined with perimeters of the neighboring triangles to create a triangle signature (also known as a hash value).
• the Key4 method uses the perimeter lengths of triangles to determine a unique signature This method creates an additional signature which also captures information about the angular change of neighboring triangles, which is then used for similar applications.
• a method computes a code (single number or set of numbers) that stems from the analysis of a reference triangle and its neighboring triangles in a 3D mesh, such that this code represents a numeric value for the localized shape/geometry of the mesh.
• a method includes scanning an object to obtain first triangular mesh data.
• the method includes scanning the object to obtain second triangular mesh data. The method includes determining whether the match exists between the 3D object based on the second triangular mesh data and the reference object based on the first triangular mesh data based upon the amount of matching of the obtained total perimeter values.
• aspects of the present disclosure include additionally computing the rigid affine transformation in three space which optimally aligns the matching subparts.
• FIG. 15 is a flow diagram present an example method 1500 for comparing two or more three-dimensional (3D) object models.
• the method 1500 includes receiving triangular mesh data describing two or more 3D object models (block 1502).
• the method 1500 includes assigning one of the two or more 3D object models as a reference object (block 1504).
• the method 1500 includes evaluating at least one 3D triangle from each received triangular mesh data of the two or more 3D object models as a reference triangle (block 1506).
• the method 1500 includes, for each reference triangle: (i) identifying two or more adjacent triangles using conditions for congruence of triangles; and (ii) performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle (block 1508).
• the method 1500 includes comparing the object hash value to one or more reference hash values assigned respectively to one or more 3D object models (block 1510).
• the method 1500 includes determining whether a match exists between one or more 3D object models and the reference object based upon an amount of matching of obtained hash values (block 1512). Then method 1500 ends.
• the conditions for congruence of triangles comprises one or more of: (i) Side-Side-Side (SSS); (ii) Side- Angle-Side (SAS); (iii) Angle-Side-Angle (ASA); (iv) Angle-Angle-Side (AAS); and (v) Right Angle-Hypotenuse-Side (RHS).
• the neighbor facet edge hashing comprises a KeyC technique comprising summing a perimeter length of edges of a triangle and of three neighbor triangles.
• the neighbor facet edge hashing further includes performing a Key4 technique combining KeyC scores for the triangle and the three neighbors into a sorted set.
• the method 1500 includes performing a Key4++ technique for extending numerical dynamic range and making configurable precision configurable by evaluating an exponent of a largest sum and a mantissa of each of four sums produced by the Key4 technique to produce a set of five integers.
• the method 1500 includes performing a KeyE/KeylO technique by extending the KeyC to a next order of adjacent triangles.
• the neighbor facet edge hashing comprises KeyV2 technique comprises summing a perimeter length of the triangle, edge adjacent perimeters, and vertex-adjacent perimeters.
• the neighbor facet edge hashing comprises KeyV technique comprises summing a perimeter length of the triangle and edges of vertex-adjacent triangles.
• the method 1500 further includes performing Gaussian curvature adjustment to the 3D triangular mesh data.
• the method 1500 includes searching a database of more than one 3D triangular mesh data to find matches based on a pattern of hash values. Then method 1500 ends.
• FIG. 16 is a flow diagram presenting a method 1600 for identifying deviations in an object.
• the method includes receiving first triangular mesh data describing an object at a first time (block 1602).
• the method 1600 includes evaluating at least one 3D triangle from the received triangular mesh data by (i) identifying two or more adjacent triangles using conditions for congruence of triangles; and (ii) performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle (block 1604).
• the method 1600 includes creating a first 3D reference model comprises the respective object hash values for the at least one triangle of the first triangular mesh data (block 1606).
• the method 1600 includes receiving second triangular mesh data describing one of a similar object or the object at a second time that is subsequent to the first time (block 1608).
• the method 1600 includes evaluating at least one 3D triangle from each received second triangular mesh data for each reference triangle by identifying two or more adjacent triangles using conditions for congruence of triangles (block 1610).
• Method 1600 includes performing neighbor facet edge hashing to produce an object hash value for each of the at least one 3D triangle (block 1612).
• Method 1600 includes creating a second 3D reference model comprises the respective object hash values for the at least one triangle (block 1614).
• Method 1600 includes comparing the first and the second 3D object models (block 1616). Then method 1600 ends.
• the method 1600 includes determining at least one of subobjects that is added or removed based on comparing the first and the second 3D object models. In one or more embodiments, the method 1600 includes determining at least one of sub-objects that is one or more of translated and rotated based on comparing the first and the second 3D object models. In one or more embodiments, the method 1600 includes extracting a center point for each at least one 3D triangle; and performing best fit rigid affine transformations to align the first and the second 3D object models. In one or more embodiments, the method 1600 includes determining Hausdorff distance to determine deviations between features of the first and the second 3D object models.
• Computer memory includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computing system.
• the system memory includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) and random-access memory (RAM).
• ROM read only memory
• RAM random-access memory
• a basic input/output system (BIOS) containing the basic routines that help to transfer information between elements within computing system, such as during start-up, is typically stored in ROM.
• BIOS basic input/output system
• RAM typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit. By way of example, and not limitation, an operating system, application programs, other program modules and program data are shown.
• removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like.
• the hard disk drive is typically connected to the system bus through a non-removable memory interface such as interface, and magnetic disk drive and optical disk drive are typically connected to the system bus by a removable memory interface, such as interface.

Landscapes

• Engineering & Computer Science (AREA)
• Theoretical Computer Science (AREA)
• Physics & Mathematics (AREA)
• General Physics & Mathematics (AREA)
• Library & Information Science (AREA)
• General Engineering & Computer Science (AREA)
• Evolutionary Computation (AREA)
• Geometry (AREA)
• Computer Hardware Design (AREA)
• Data Mining & Analysis (AREA)
• Databases & Information Systems (AREA)
• Processing Or Creating Images (AREA)
• Image Generation (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=90013993

Family Applications (1)

Country Status (4)

Family Cites Families (3)

• 2023
  • 2023-08-22 JP JP2025511645A patent/JP2025529885A/ja active Pending
  • 2023-08-22 CN CN202380061796.9A patent/CN119768839A/zh active Pending
  • 2023-08-22 WO PCT/US2023/072640 patent/WO2024044581A2/en not_active Ceased
  • 2023-08-22 EP EP23858234.0A patent/EP4577985A2/de active Pending

Also Published As

Similar Documents

Legal Events