Three-dimensional modeling from arbitrary three-dimensional curves

• US 7,487,063 B2
• Filed: 06/11/2004
• Issued: 02/03/2009
• Est. Priority Date: 06/13/2003
• Status: Active Grant

• Current Assignee: Creaform, Inc. (Ametek Incorporated)
• Original Assignee: Universite Laval
• Inventors: Laurendeau, Denis, Tubic, Dragan, Hébert, Patrick
• Primary Examiner(s): Lau; Tung S
• Assistant Examiner(s): VO, HIEN XUAN
• Application Number:
  US10/560,130
• Publication Number:
  US 20070052974A1
• Time in Patent Office: 1,698 Days
• Field of Search: 702150-153, 382/285, 382/293, 382/295, 345/418, 345/419, 345/420
• US Class Current: 702/152
• CPC Class Codes: G01B 21/045 Correction of measurements G01B9/02055 takes precedence
• CPC Class Codes: G05B 19/4207 in which a model is traced or scanned and corresponding data recorded
• CPC Class Codes: G05B 2219/36443 Auto follow coarse contour, operator can correct contour before recording
• CPC Class Codes: G05B 2219/36458 Teach only some points, for playback interpolation between points
• CPC Class Codes: G05B 2219/36462 Minimize teach time, compress data, many points in curve, few in line
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

The present invention relates to a method and a system for creating three-dimensional models of objects from sets of arbitrary three-dimensional entities obtained from target surfaces. It also provides an efficient method for individually refining the alignment of curves to improve the accuracy of the surface model with a linear complexity with respect to the number of curves. The principle behind the invention is that a set of three-dimensional entities, at their approximate positions, creates a field from which the surface can be extracted. The field is constructed in a manner such that the three-dimensional entities are attracted toward the extracted surface. This attraction is used to accurately register each three-dimensional entity with respect to extracted surface. Through iterations, both the field and the entity positions are refined.

Claims

1. A method for reconstructing a surface from at least one arbitrary three-dimensional entity obtained from a target surface, comprising:

obtaining a set of at least one three-dimensional entity and a position for said at least one entity in a common three-dimensional coordinate system, each entity being a set of three-dimensional points, each said point containing at least the three-dimensional coordinates of said point on said target surface, wherein said entity is one of an unorganized cloud, a three-dimensional curve and a range image;

constructing a volumetric implicit representation of said target surface in the form of a vector field using said set, each vector in said vector field containing at least the distance to said target surface and the direction toward said target surface;

reconstructing said target surface from the information contained in said vector field.

2. The method as claimed in claim 1, wherein said set of at least one entity includes at least one entity being one of said unorganized cloud and said curve.

3. The method as claimed in claim 1, wherein a subset of said points contains surface properties measured on said target surface.

5. The method as claimed in claim 3, wherein at least one of said surface properties measured on said target surface is a color information associated to said point.

6. The method as claimed in claim 3, wherein at least one of said surface properties measured on said target surface is an information describing the surface texture associated to said point.

7. The method as claimed in claim 1, further comprising:

using a ranging sensor to produce said set of entities.

8. The method as claimed in claim 7, wherein said ranging sensor is held in hand by an operator.

9. The method as claimed in claim 7, wherein said ranging sensor is moved by a mechanical device.

10. The method as claimed in claim 1, wherein said three-dimensional points are all measured in a single plane and the three-dimensional coordinate system can be reduced to a two-dimensional coordinate system.

4. The method as claimed in 3, wherein at least one of said surface properties measured on said target surface is a grayscale value associated to said point.

11. A method for refining an alignment of arbitrary three-dimensional entities obtained from a target surface, comprising:

(a) obtaining a set of at least two three-dimensional entities and a position for said at least two entities in a common three dimensional coordinate system, each entity being a set of three-dimensional points, each said point containing at least the three-dimensional coordinates of said point on said target surface, wherein each said entity is one of an unorganized cloud, a three-dimensional curve and a range image;

(b) constructing a volumetric implicit representation of said target surface in the form of a vector field using a subset of at least one entity of said set, each vector in said vector field containing at least the distance to said target surface and the direction toward said target surface;

(c) selecting at least one obtained entity;

(d) obtaining a subset of said points on each of said selected entities, points in these subsets being called control points;

(e) for each control point in each selected entity, computing a contribution to a cost function, said contribution being a function of at least said vector field and said coordinate of said control point;

(f) for each selected entity, computing a new position that optimizes its corresponding cost function; and

(g) placing each selected entity in said vector field at its newly computed position and updating said vector field accordingly.

12. The method as claimed in claim 11, wherein said set of at least two entities includes at least one entity being one of said unorganized cloud and said curve.

13. The method as claimed in claim 11 wherein steps (c), (d), (e), (f) and (g) are repeated until a set of convergence criteria is met.

14. The method as claimed in claim 11, wherein

said step (b) comprises placing at least one entity in said vector field and updating said vector field accordingly;

and wherein

said step (c) comprises selecting at least one of said entities not yet placed in said vector field and placing said selected entities in said vector field without updating said field.

15. The method as claimed in claim 11 wherein a subset of said points contains surface properties measured on said target surface.

16. The method as claimed in claim 15, wherein said cost function is a function of said surface properties measured on said target surface.

17. A system for reconstructing a surface from at least one arbitrary three-dimensional entity obtained from a target surface comprising:

a three-dimensional entity provider for obtaining a set of at least one three-dimensional entity and a position for said at least one entity in a common three-dimensional coordinate system, each entity being a set of three-dimensional points, each point containing at least the three-dimensional coordinates of said point on said target surface, wherein said entity is one of an unorganized cloud, a three-dimensional curve and a range image;

an implicit representation constructor for constructing a volumetric implicit representation of said target surface in the form of a vector field using said set, each vector in said vector field containing at least the distance to said target surface and the direction toward said target surface; and

a target surface reconstructor for reconstructing said target surface from the information contained in said vector field.

18. The system as claimed in claim 17, wherein said set of at least one entity includes at least one entity being one of said unorganized cloud and said curve.

19. A system for refining an alignment of arbitrary three-dimensional entities obtained from a target surface, comprising:

a three-dimensional entity provider for obtaining a set of at least two three-dimensional entities and a position for said at least two entities in a common three-dimensional coordinate system, each entity being a set of three-dimensional points, each point containing at least the three-dimensional coordinates of said point on said target surface, wherein each said entity is one of an unorganized cloud, a three-dimensional curve and a range image;

an implicit representation constructor for constructing a volumetric implicit representation of said target surface in the form of a vector field using said set, each vector in said vector field containing at least the distance to said target surface and the direction toward said target surface; and

a control point selector for selecting at least one entity used in said vector field;

a subset provider for obtaining a subset of points on each of said selected entities, points in these subsets being called control points;

a cost function calculator for computing, for each control point in each selected entity, a contribution to a cost function, the contribution being a function of at least the vector field and the coordinate of the control point;

a new position calculator for computing, for each selected entity, a new position that optimizes its corresponding cost function;

wherein the implicit representation constructor places each selected entity in the vector field at its newly computed position and updates the vector field accordingly.

20. The system as claimed in claim 19, wherein said set of at least two entities includes at least one entity being one of said unorganized cloud and said curve.