COMPUTING DEVICE AND METHOD FOR EXTRACTING DATA OF PRODUCT FOR USE IN CONSTRUCTION OF POINT CLOUD

• US 20130156292A1
• Filed: 06/15/2012
• Published: 06/20/2013
• Est. Priority Date: 12/14/2011
• Status: Active Grant

• Current Assignee: Hong Fu Jin Precision Industry (Shenzhen) Co., Ltd. (Hon Hai Precision Industry Co., Ltd.), Hon Hai Precision Industry Co., Ltd.
• Original Assignee: Hong Fu Jin Precision Industry (Shenzhen) Co., Ltd. (Hon Hai Precision Industry Co., Ltd.), Hon Hai Precision Industry Co., Ltd.
• Inventors: CHANG, CHIH-KUANG, WU, XIN-YUAN, YANG, GEN
• Granted Patent: US 8,831,332 B2
• Time in Patent Office: Days
• US Class Current: 382/141
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30164 Workpiece; Machine component
• CPC Class Codes: G06T 7/001 using an image reference approach

Abstract

In a method for extracting data of a product, an electronic design document related to the product and point cloud created using actual measurements of the product are received. The point cloud includes points of the product. The method aligns the curved surface of the product with the corresponding portion of the point cloud using a best-fit method, creates a maximum space box for a feature element of the product, and deletes points that are not within the maximum space box. According to an average distance between two neighboring points of the point cloud, the maximum space box can be divided into many small space boxes. Using the small space boxes, the points are filtered to form a feature element.

Claims

1. A computer-implemented method for extracting data of a product using a computing device, the method comprising:

receiving an electronic design document of the product, receiving a point cloud of the product created using actual measurements of the product, and a tolerance between a curved surface of the product in the electronic design document and the curved surface of the product in the point cloud, the point cloud comprising a plurality of points of the product;

aligning the curved surface of the product with the corresponding portion of the point cloud using a best-fit method;

creating a maximum space box for a feature element of the product by determining a maximum coordinate value and a minimum coordinate value of the feature element in an x-axis, a y-axis, and a z-axis of a coordinate system, and deleting points that are not within the maximum space box;

dividing the maximum space box into a plurality of small space boxes according to an average distance between two neighboring points of the point cloud, and the maximum coordinate values and the minimum coordinate values of the feature element;

obtaining points interest that are composed of the feature element by filtering the points of the point cloud using the plurality of small space boxes; and

outputting the points of interest on a display device of the computing device, and drawing the feature element of the product based on the points of interest.

2. The method as described in claim 1, wherein the obtaining step comprises:

dividing the curved surface of the product into a mesh of triangles;

determining whether one of the triangles intersects with a small space box;

upon the condition that any of the triangles intersects with any of the small space boxes, associating the triangle with the small space box by adding an identifier of the triangle into a data array of the small space box;

calculating a unique identifier nG for each small space box that contains at least one point of the point cloud;

upon the condition that the small space box whose unique identifier is nG has a associated triangle, associating the small space box with the at least one point that is within the small space box;

deleting the small space boxes that do not have associated triangles, deleting the points that are not within any one of the small space boxes, and obtaining a group of remaining points of the point cloud after the deleting;

calculating a distance between each of the remaining points and a corresponding small space box that encloses the remaining point;

upon the condition that the distance between one of the remaining points and the corresponding small space box is greater than the tolerance, deleting the remaining point from the group of remaining points;

or

upon the condition that a normal direction of one of the remaining points is different from a normal direction of the corresponding small box that is associated with the remaining point, deleting the remaining point from the group of remaining points.

3. The method as described in claim 2, wherein the step of determining whether one of the triangles intersects with a small space box comprises:

deleting the small space box that does not associate with any one of the triangles;

upon the condition that an intersection of one small space box and a plane containing a triangle is within the triangle, determining that the triangle intersects with the small space box;

upon the condition that all vertexes of one triangle are within one of the small space boxes, determining that the triangle intersects with the small space box; and

upon the condition that an intersection of one side of the triangles and a small space box is within the small space box, determining that the triangle intersects with the small space box.

4. The method as described in claim 3, wherein the step of deleting the small space box that does not associate with one of the triangles comprises:

constructing a circumscribed sphere for each of the small space boxes, and obtaining a radius and a center of the circumscribed sphere;

obtaining a plane that contains the triangle, which is associated with the small space box;

upon the condition that a distance between the plane and the center of the circumscribed sphere is not greater than the radius of the circumscribed sphere, determining that the triangle intersects with the small space box;

or

upon the condition that distance is greater than the radius of the circumscribed sphere, deleting the small space box.

5. The method as described in claim 1, wherein the feature element is selected from a group consisting of a point, a line, a plane, a circle, a column, a taper, a sphere, a curve, and a triangular facet.

6. A computing device, comprising:

at least one processor;

a storage system; and

one or more modules that are stored in the storage system and executed by the at least one processor, the one or more modules comprising;

a receiving module that receives an electronic design document of the product, receives a point cloud of the product created using actual measurements of the product, and a tolerance between a curved surface of the product in the electronic design document and the curved surface of the product in the point cloud, the point cloud comprising a plurality of points of the product;

a aligning module that aligns the curved surface of the product with the corresponding portion of the point cloud using a best-fit method;

a crude filter module that creates a maximum space box for a feature element of the product by determining a maximum coordinate value and a minimum coordinate value of the feature element in an x-axis, a y-axis, and a z-axis of a coordinate system, and deletes points that are not within the maximum space box;

a fine detail filter module that divides the maximum space box into a plurality of small space boxes according to an average distance between two neighboring points of the point cloud, and the maximum coordinate values and the minimum coordinate values of the feature element, and obtains points interest that are composed of the feature element by filtering the points of the point cloud using the plurality of small space boxes; and

an output module that outputs the points of interest on a display device of the computing device, and draws the feature element of the product based on the points of interest.

7. The computing device as described in claim 6, wherein the further filter module comprises:

a box constructing module that divides the maximum space box into a plurality of small space boxes according to an average distance between two neighboring points of the point cloud, and the maximum coordinate values and the minimum coordinate values of the feature element, and each of the small space boxes corresponding to a data array;

a first association module that divides the curved surface of the product into a mesh of triangles, determines whether one of the triangles intersects with a small space box, and associates the triangle with the small space box that intersects with the triangle by adding an identifier of the triangle into the data array of the small space box;

a second association module that calculates a unique identifier nG for each small space box that contains at least one point of the point cloud, and associates the small space box with the at least one point that is within the small space box, upon the condition that the small space box whose unique identifier is nG has a associated triangle;

a deleting module that deletes the small space boxes that do not intersect with any one of the triangles, deletes the points that are not within any one of small space boxes, and obtains a group of remaining points of the point cloud after the deleting; and

the deleting module that further calculates a distance between each of the remaining points and a corresponding small space box that is associated with the remaining point, upon the condition that the distance between one of the remaining points and the corresponding small space box is greater than the tolerance, deletes the remaining point from the group of remaining points, or upon the condition that a normal direction of one of the remaining points is different from a normal direction of the corresponding small box that is associated with the remaining point, deletes the remaining point from the group of remaining points.

8. The computing device as described in claim 7, wherein the first association module executes following steps to determine whether one of the triangles intersects with a small space box:

deleting the small space box that does not associate with any one of the triangles;

upon the condition that an intersection of one small space box and a plane containing a triangle is within the triangle, determining that the triangle intersects with the small space box;

upon the condition that all vertexes of one triangle are within one of the small space boxes, determining that the triangle intersects with the small space box; and

upon the condition that an intersection of one side of the triangles and a small space box is within the small space box, determining that the triangle intersects with the small space box.

9. The computing device as described in claim 8, wherein the second association module executes following steps to delete the small space box that does not associate with any one of the triangles:

constructing a circumscribed sphere for each of the small space boxes, and obtaining a radius and a center of the circumscribed sphere;

obtaining a plane that contains the triangle, which is associated with the small space box;

upon the condition that a distance between the plane and the center of the circumscribed sphere is not greater than the radius of the circumscribed sphere, determining that the triangle intersects with the small space box;

or

upon the condition that distance is greater than the radius of the circumscribed sphere, deleting the small space box.

10. The computing device as described in claim 6, wherein the feature element is selected from a group consisting of a point, a line, a plane, a circle, a column, a taper, a sphere, a curve, and a triangular facet.

11. A non-transitory computer readable storage medium having stored thereon instructions that, when executed by a processor of a computing device, causes the computing device to perform a method for extracting data of a product, the method comprising:

receiving an electronic design document of the product, receiving a point cloud of the product created using actual measurements of the product, and a tolerance between a curved surface of the product in the electronic design document and the curved surface of the product in the point cloud, the point cloud comprising a plurality of points of the product;

aligning the curved surface of the product with the corresponding portion of the point cloud using a best-fit method;

creating a maximum space box for a feature element of the product by determining a maximum coordinate value and a minimum coordinate value of the feature element in an x-axis, a y-axis, and a z-axis of a coordinate system, and deleting points that are not within the maximum space box;

dividing the maximum space box into a plurality of small space boxes according to an average distance between two neighboring points of the point cloud, and the maximum coordinate values and the minimum coordinate values of the feature element;

obtaining points interest that are composed of the feature element by filtering the points of the point cloud using the plurality of small space boxes; and

outputting the points of interest on a display device of the computing device, and drawing the feature element of the product based on the points of interest.

12. The storage medium as described in claim 11, wherein the obtaining step comprises:

dividing the curved surface of the product into a mesh of triangles;

determining whether one of the triangles intersects with a small space box;

upon the condition that any of the triangles intersects with any of the small space boxes, associating the triangle with the small space box by adding an identifier of the triangle into a data array of the small space box;

calculating a unique identifier nG for each small space box that contains at least one point of the point cloud;

upon the condition that the small space box whose unique identifier is nG has a associated triangle, associating the small space box with the at least one point that is within the small space box;

deleting the small space boxes that do not have associated triangles, deleting the points that are not within any one of the small space boxes, and obtaining a group of remaining points of the point cloud after the deleting;

calculating a distance between each of the remaining points and a corresponding small space box that encloses the remaining point;

upon the condition that the distance between one of the remaining points and the corresponding small space box is greater than the tolerance, deleting the remaining point from the group of remaining points;

or

upon the condition that a normal direction of one of the remaining points is different from a normal direction of the corresponding small box that is associated with the remaining point, deleting the remaining point from the group of remaining points.

13. The storage medium as described in claim 12, wherein the step of determining whether one of the triangles intersects with a small space box comprises:

deleting the small space box that does not associate with any one of the triangles;

upon the condition that an intersection of one small space box and a plane containing a triangle is within the triangle, determining that the triangle intersects with the small space box;

upon the condition that all vertexes of one triangle are within one of the small space boxes, determining that the triangle intersects with the small space box; and

upon the condition that an intersection of one side of the triangles and a small space box is within the small space box, determining that the triangle intersects with the small space box.

14. The storage medium as described in claim 13, wherein the step of deleting the small space box that does not associate with any one of the triangles comprises:

constructing a circumscribed sphere for each of the small space boxes, and obtaining a radius and a center of the circumscribed sphere;

obtaining a plane that contains the triangle, which is associated with the small space box;

upon the condition that a distance between the plane and the center of the circumscribed sphere is not greater than the radius of the circumscribed sphere, determining that the triangle intersects with the small space box;

or

upon the condition that distance is greater than the radius of the circumscribed sphere, deleting the small space box.

15. The storage medium as described in claim 11, wherein the feature element is selected from a group consisting of a point, a line, a plane, a circle, a column, a taper, a sphere, a curve, and a triangular facet.