User-guided surface reconstruction

• US 9,245,382 B2
• Filed: 10/04/2008
• Issued: 01/26/2016
• Est. Priority Date: 10/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zhou, Kun, Huang, Xin, Guo, Baining
• Primary Examiner(s): Ma, Tize
• Application Number:
  US12/245,709
• Publication Number:
  US 20100085353A1
• Time in Patent Office: 2,670 Days
• Field of Search: 345/419
• US Class Current: 1/1
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 2210/52 Parallel processing

Abstract

Described is a technology by which a user interacts with a surface representative of a point cloud data to correct for imperfect scan data. The surface is reconstructed based on the interaction. Real time viewing of the image is facilitated by parallel surface reconstruction. For example, the user may draw strokes to reduce topological ambiguities in poorly-sampled areas. An algorithm automatically adds new oriented sample points to the original point cloud based on the user interaction. Then a new isosurface is generated for the augmented point cloud. The user also may specify the geometry of missing areas of the surface. The user copies a set of points from another point cloud, and places the points around the target area. A new isosurface is then generated.

Claims

1. In a computing environment, a method comprising:

receiving user interaction with a surface representative of point cloud data;

modifying the point cloud data based on the user interaction, in which at least some of the user interaction corresponds to geometries of missing areas or under-sampled areas, the modifying step comprising at least one of;

adding new oriented sample points to the point cloud data or copying other point cloud data to the point cloud data; and

generating a new surface by parallel operations on nodes including spawning a new thread for each node at a same level of a level order traversal, the nodes comprising at least a portion of the modified point cloud data via a graphics processing unit.

2. The method of claim 1 wherein receiving the user interaction comprises detecting a stroke.

3. The method of claim 1 wherein receiving the user interaction with the surface comprises detecting interaction at a location corresponding to one part of the surface, and wherein modifying the point cloud data comprises adding points corresponding to the location so as to be visible in the new surface.

4. The method of claim 1 wherein receiving the user interaction with the surface comprises detecting interaction at a location corresponding to one part of the surface, and wherein modifying the point cloud data comprises removing points corresponding to the location so as to not be visible in the new surface.

5. The method of claim 1 wherein modifying the point cloud data based on the user interaction comprises computing a depth range of a bounding box of a current view of a point set of point cloud data, and processing the interaction along the current view direction in the depth range to determine where to modify the point cloud data.

6. The method of claim 5 wherein the user interaction is a stroke, and wherein processing the interaction along the current view direction comprises determining a set of points distributed along the stroke, and for each point, computing a function value.

7. The method of claim 6 further comprising, removing a point based on its function value relative to a threshold value.

8. The method of claim 1 wherein generating the new surface comprises using Poisson equation for surface reconstruction.

9. In a computing environment having a graphics processing unit, a system comprising, a surface construction mechanism coupled to the graphics processing unit that communicates with the graphics processing unit to construct a surface based on using a level-order traversal to build nodes for a set of points in parallel by spawning a new thread for each node at the same level, an interactive program that modifies the set of points at a location corresponding to interaction with the surface into a set of modified points, the surface construction mechanism communicating with the graphics processing unit to reconstruct a surface into a new isosurface based on processing the set of modified points by parallel operations.

10. The system of claim 9 wherein the interaction comprises a stroke, or a shape, or any combination of a stroke or a shape.

11. The system of claim 9 wherein the set of points is contained with nodes of an octree, in which the octree is built by computing the nodes in parallel via the graphics processing unit.

12. The system of claim 11 further comprising, means for determining which node or set of nodes correspond to the modified points based on the location and a current depth of the surface.

13. The system of claim 9 wherein the interactive program modifies the set of points by adding points with so as to become visible in the constructed surface.

14. The system of claim 9 wherein the interactive program modifies the set of points by adding points copied from another surface.

15. The system of claim 9 wherein the interactive program modifies the set of points by removing points so as to not be visible in the constructed surface.

16. The system of claim 9 wherein the user interaction is a stroke, and further comprising, means for determining a set of points distributed along the stroke.

17. A computer storage device having computer-executable instructions stored thereon, which in response to execution cause a computer to perform steps comprising, building an octree of nodes for a given set of oriented points, each node containing a set of points enclosed by the node and indirect pointers to related nodes that are independent of the octree, constructing a surface based on the nodes, receiving user interaction that changes the points of at least one of the nodes, and reconstructing the surface based on the changes to the points, via at least some parallel processing in a graphics processing unit.

18. The computer storage device of claim 17 having further computer-executable instructions comprising, determining which node or nodes in which to change point data based on a current view of the surface.

19. The computer storage device of claim 17 having further computer-executable instructions stored thereon, which in response to execution cause the computer to perform further steps comprising, modifying the points to add visible information to the surface.

20. The computer storage device of claim 17 wherein receiving the user interaction that changes the points comprises, adding points copied from another surface, or removing points, or both adding points copied from another surface and removing points.