USER-GUIDED SURFACE RECONSTRUCTION

• US 20100085353A1
• Filed: 10/04/2008
• Published: 04/08/2010
• Est. Priority Date: 10/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huang, Xin, Zhou, Kun, Guo, Baining
• Granted Patent: US 9,245,382 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• 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, and generating a new surface from the modified point cloud data by parallel operations on 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 processing a set of points, 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 based on processing the set of modified points.

10. The system of claim 9 wherein the user 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 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. One or more computer-readable media having computer-executable instructions, which when executed 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 pointers to related nodes, 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.

18. The one or more computer-readable media 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 one or more computer-readable media of claim 17 having further computer-executable instructions comprising, modifying the points to add visible information to the surface.

20. The one or more computer-readable media 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.