System and method for generation of a three-dimensional solid model

• US 6,249,600 B1
• Filed: 11/26/1997
• Issued: 06/19/2001
• Est. Priority Date: 11/07/1997
• Status: Expired due to Term

• Current Assignee: Columbia University
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Allen, Peter K., Reed, Michael K.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US08/979,221
• Time in Patent Office: 1,301 Days
• Field of Search: 382/154, 382/254, 382/266, 382/285, 382/284, 382/255, 382/256, 382/206, 382/318, 356/2, 356/3, 356/3.1, 345/419, 345/420, 345/421, 345/424, 345/425, 345/446, 348/47, 348/48, 348/50
• US Class Current: 382/154
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A system and method for generating a three-dimensional representation of an object or scene which minimizes the number of range scans required from different positions to produce an image of acceptable resolution. The technique first produces an initial mesh representation from a predetermined number of scans which is transformed into a solid. Vertices and surfaces in the solid mesh are tagged with either an occluded (unscanned) or imaged (scanned) tag. The occlusion tags allows the technique to select the best view for next scanning iteration by identifying the scanable surface area with the most occlusions. The technique then adjusts the object-scanner positioning so that the targeted view is scanned next. The process is repeated until an acceptable resolution of the object is achieved. The use of occlusion tags with a planning stage decreases the minimum number of scans necessary to complete the process.

Claims

1. A method for generating a three-dimensional representation of at least one object comprising:

a. scanning said at least one object from at least one view and initially generating said representation including data elements responsive to the presence of said object in said at least one view;

b. storing visibility attributes associated with said data elements;

c. selecting a targeted area on said at least one object responsive to said visibility attributes;

d. further scanning said targeted area and generating additional data elements and additional corresponding visibility attributes for said further scan;

e. modifying said representation and said stored visibility attributes responsive to said new data elements and said new visibility attributes; and

f. repeating steps c through e until a termination condition occurs.

2. The method of claim 1, wherein said data elements are organized as a mesh representation.

3. The method of claim 2, further including the step of extruding said mesh representation into a solid model.

4. The method of claim 3, further including the step of joining said extruded representations into one representation.

5. The method of claim 1, wherein said storing step includes determining if an edge between two of said data elements is occluded.

6. The method of claim 5, wherein said storing step includes determining if a surface defined by at least said edge is occluded.

7. The method of claim 5, wherein said determination is responsive to said edge'"'"'s length.

8. The method of claim 6, wherein said determination is responsive to said surface'"'"'s normal relative to sensing direction of said object being scanned.

9. The method of claim 1, wherein said scanning step a is performed for a predetermined number of times to produce said representation.

10. The method of claim 9, wherein said predetermined number is four.

11. The method of claim 1, wherein said target area selected encompasses the greatest surface area of remaining data elements with an associated visibility attribute which indicates an occlusion.

12. The method of claim 11, wherein said greatest surface area of remaining data elements is determined by a construction of a visibility volume for said occluded attributes associated with said at least one object.

13. The method of claim 1, wherein said visibility attributes which indicate that said data elements are occluded are changed to indicate said data elements are unoccluded when said further scanning operation scans said occluded data elements if said data elements are positioned within a scanning field of said further scan operation.

14. The method of claim 1, wherein said visibility attributes which indicate that a surface defined by said data elements is occluded is changed to indicate said surface is unoccluded when said further scanning operation scans said occluded surface if said surface is positioned within a scanning field of said further scan operation.

15. The method of claim 2, wherein said data elements in said mesh which are near said at least one object'"'"'s outside edges are moved in a direction which increases said mesh'"'"'s size.

16. The method of claim 15, wherein said moved data elements are moved one sampling distance.

17. The method of claim 1, wherein said termination condition is predetermined prior to said scanning operation.

18. The method of claim 17, wherein said termination condition is responsive to said representation'"'"'s resolution.

19. The method of claim 1, wherein said termination condition is selected by a user during said generation method.

20. A method for generating a three-dimensional representation of at least one object comprising the steps of:

a. generating a composite solid representation of said at least one object being scanned, wherein said solid representation includes occlusion tags corresponding to a plurality of surfaces in said solid representation;

b. selecting the next best view of said at least one object which encompasses the greatest surface area of said occlusion tags indicating an occluded state;

c. scanning said selected next view and generating a new solid representation with a plurality of occlusion tags responsive to said next view;

d. merging said composite representation with said new representation generated in step c to generate an updated said composite representation;

e. repeating steps b through d until a termination condition occurs.

21. The method of claim 20, wherein said merging step includes comparing corresponding occlusion tags from said composite model with said new representation.

22. The method of claim 21, wherein each said occlusion tags of said updated composite model indicate a scanned condition if at least one of said corresponding tags indicates a scanned condition.

23. The method of claim 20, wherein said solid is generated from a mesh, and said occlusion tags'"'"' indication is responsive to an edge in said mesh.

24. The method of claim 23, wherein said occlusion tag'"'"'s indication is responsive to said edge'"'"'s length.

25. The method of claim 23, wherein said occlusion tags are responsive to a surface determined by at least one said edge.

26. The method of claim 25, wherein said occlusion tag'"'"'s indication is responsive to said surface'"'"'s normal relative to an axis scanning direction of a scanner.

27. The method of claim 20, wherein said generating step a is performed for a predetermined number of scans to produce said composite representation.

28. The method of claim 20, wherein determining said greatest surface area in said selecting step is performed by constructing a visibility volume.

29. The method of claim 20, wherein said mesh comprises data elements, and said data elements near said at least one object'"'"'s outside edges are moved in a direction which increases said mesh'"'"'s size.

30. The method of claim 29, wherein said moved data elements are moved one sampling distance.

31. The method of claim 20, wherein said termination condition is predetermined prior to said scanning operation.

32. The method of claim 31, wherein said termination condition is responsive to said resolution of said at least one object.

33. A system for generating a three-dimensional representation of at least one object comprising:

a. means for scanning said at least one object from at least one view and generating scan data responsive to the presence of said object in said view;

b. means for initially generating a representation comprising data elements responsive to said scan data;

c. means for storing visibility attributes associated with said data elements;

d. means for selecting a targeted area on said at least one object responsive to said stored visibility attributes;

e. means for further scanning said targeted area and generating additional data elements and additional corresponding visibility attributes for said further scan; and

f. means for modifying said representation and said stored attributes responsive to said new data elements and said new visibility elements.

34. The system of claim 33, further including a monitor to display said representation.

35. The system of claim 33, further including an input means wherein said scanning means'"'"' use is responsive to said input means.

36. The system of claim 33, further including a means for communicating said representation to an external terminal.

37. The system of claim 33, wherein said representation is generated from a mesh.

38. The system of claim 37, further including a means for moving at least one data element in said mesh to expand said mesh.