System and method for hole filling in 3D models
View Patent ↗A method for hole-filling in 3D models includes identifying vertices adjacent to hole boundaries in a mesh of points on a digital image and constructing a signed distance function based on vertices adjacent to hole boundaries. A Radial Basis Function is fit based on the constructed signed distance function and evaluated on a grid, which include the hole. The points on the hole surface are extracted and meshed to fill the hole.
1. A method for hole-filling in 3D models, comprising the steps of:
identifying vertices adjacent to hole boundaries in a mesh of points on a digital image;
constructing a signed distance function based on vertices adjacent to hole boundaries;
fitting a Radial Basis Function based on the constructed signed distance function;
evaluating the fitted Radial Basis Function on a grid including the hole; and
extracting and meshing the points on the hole surface to fill the hole.
2. The method as recited in claim 1 , further comprising the step of generating a mesh using points of an image.
3. The method as recited in claim 2 , further comprising the step of scanning an image using a Ball Pivoting Algorithm.
4. The method as recited in claim 1 , further comprising the step of listing and indexing holes in the mesh.
5. The method as recited in claim 1 , further comprising the step of scanning an object to generate the mesh.
6. The method as recited in claim 1 , wherein the step of identifying vertices adjacent to hole boundaries includes employing a search algorithm.
7. The method as recited in claim 1 , wherein the search algorithm includes employing a breadth first search.
8. The method as recited in claim 1 , wherein the step of constructing a signed distance function includes:
defining a distance function d for additional points, which lie on surface normals from vertices;
evaluating a continuous distance function on a grid.
9. The method as recited in claim 7 , wherein a value of a distance d between each additional point and its associated vertex controls a topology of an output surface, and further comprising the step of defining the value of distance d by a user.
10. The method as recited in claim 7 , wherein a resolution of the grid defines the detail of generated surfaces, and further comprising the step of defining the resolution of the grid by a user.
11. The method as recited in claim 1 , wherein fitting a Radial Basis Function based on the constructed signed distance function includes solving a set of simultaneous equations given by Equation 6.
12. The method as recited in claim 1 , wherein the step of extracting is performed by a zero crossing method.
13. A system for hole-filling in 3D models, comprising:
a storage device, which stores a digital form of an image;
a processor, which graphically renders the image on a graphics subsystem;
the system further comprising a program which identifies points in the image and integrates a mesh between these points to define vertices adjacent to hole boundaries in the mesh, the program further comprising:
a signed distance function which is constructed based on vertices adjacent to hole boundaries;
a Radial Basis Function which is fitted based on the constructed signed distance function, the Radial Basis Function being evaluated on a grid including one of the holes such that the hole is filled by extracting and meshing the points of the hole surface.
14. The system as recited in claim 13 , wherein the mesh is generated using points of an image.
15. The system as recited in claim 13 , further comprising an image acquisition device, which scans a digital image of an object to be modeled.
16. The system as recited in claim 13 , wherein the program employs a Ball Pivoting Algorithm in scanning an image.
17. The system as recited in claim 13 , wherein the program identifies vertices adjacent to hole boundaries by employing a search algorithm.
18. The system as recited in claim 17 , wherein the search algorithm includes a breadth first search.
19. The system as recited in claim 13 , wherein the signed distance function includes values of distances between additional points located on a surface normal from associated vertices, the values of distances to control a topology of an output surface.
20. The system as recited in claim 19 , wherein the values of distances are user defined.
21. The system as recited in claim 13 , wherein a resolution of the grid defines the detail of generated surfaces.
22. The system as recited in claim 21 , wherein the resolution of the grid is user defined.
23. The system as recited in claim 13 , wherein the Radial Basis Function includes the form of s(x) in Equation 4.
24. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for hole-filling in 3D models, the method steps comprising:
identifying vertices adjacent to hole boundaries in a mesh of points on a digital image;
constructing a signed distance function based on vertices adjacent to hole boundaries;
fitting a Radial Basis Function based on the constructed signed distance function;
evaluating the fitted Radial Basis Function on a grid including one of the holes; and
extracting and meshing the points on the hole surface to fill the hole.
25. The program storage device as recited in claim 24 , further comprising the step of generating a mesh using points of an image.
26. The program storage device as recited in claim 24 , further comprising the step of listing and indexing holes in the mesh.
27. The program storage device as recited in claim 24 , wherein the step of identifying vertices adjacent to hole boundaries includes employing a search algorithm.
28. The program storage device as recited in claim 24 , wherein the step of constructing a signed distance function includes:
defining a distance function d for additional points, which lie on surface normals from vertices;
evaluating a continuous distance function on a grid.
29. The program storage device as recited in claim 28 , wherein a value of a distance d between each additional point and its associated vertex controls a topology of an output surface, and the value of distance d is defined by a user.
30. The program storage device as recited in claim 28 , wherein a resolution of the grid defines the detail of generated surfaces, and the resolution of the grid is defined by a user.
31. The program storage device as recited in claim 24 , wherein fitting a Radial Basis Function based on the constructed signed distance function includes solving a set of simultaneous equations given by Equation 6.