System and method for approximating an editable surface

• US 20050246130A1
• Filed: 04/29/2005
• Published: 11/03/2005
• Est. Priority Date: 04/29/2004
• Status: Active Grant

• Current Assignee: Landmark Graphics Corporation (Halliburton Company)
• Original Assignee: Landmark Graphics Corporation (Halliburton Company)
• Inventors: Spicer, Sean, Xu, Zitao
• Granted Patent: US 7,352,369 B2
• Time in Patent Office: Days
• US Class Current: 702/152
• CPC Class Codes: G06T 17/30 Polynomial surface description

Abstract

A system and methods are disclosed for automatically approximating an editable surface from a 3D data set or a 3D point set, which may be imaged in the form of a NURBS surface.

Claims

1. A method for approximating an editable surface from a 3D data set comprising the steps of:

selecting a 3D point set from the 3D data set;

determining a best-fit plane for the 3D point set;

projecting at least a portion of the 3D point set onto the best-fit plane;

determining a boundary for the best-fit plane according to the projected 3D point set;

projecting a grid onto the best-fit plane within the boundary, the grid containing a plurality of grid points;

initializing the grid points;

determining a value for at least a portion of the grid points;

selecting at least a portion of the grid points with a value; and

imaging the editable surface using at least a portion of the selected grid points.

2. The method of claim 1, wherein the 3D point set comprises an arbitrary surface.

3. The method of claim 2, further comprising the steps of:

fitting an ellipsoid to the 3D point set; and

determining a dominant axis for the 3D point set based on the ellipsoid.

4. The method of claim 3, wherein the dominant axis is used to determine the best-fit plane.

5. The method of claim 1, wherein the 3D point set comprises one of the 3D data set and a portion of the 3D data set.

6. The method of claim 1, wherein the best-fit plane is determined by a dominant axis for the 3D point set.

7. The method of claim 1, wherein the boundary of the best-fit plane is determined by a plurality of point extremes contained in the projected 3D point set.

8. The method of claim 1, wherein the projected grid is based on predetermined grid parameters.

9. The method of claim 1, wherein each grid point is defined by an intersection on the grid.

10. The method of claim 1, wherein the grid points are initialized to zero.

11. The method of claim 1, wherein the grid point value is determined by one or more points in the projected 3D point set within a predetermined area of the grid point and a distance from each point in the predetermined area to the grid point.

12. The method of claim 1, wherein the editable surface represents a best-fit approximation of the 3D point set to the editable surface.

13. The method of claim 1, wherein the editable surface represents a NURBS surface.

14. The method of claim 1, further comprising the steps of:

refining the value for at least a portion of the at least a portion of the grid points; and

selecting at least a portion of the grid points based on one of the value and the refined value.

15. The method of claim 14, further comprising the step of replacing the value with the refined value for the grid points selected with a value and a refined value.

16. The method of claim 1, further comprising the step of converting the 3D data set to the 3D point set.

17. A method for approximating an editable surface from a 3D point set comprising the steps of:

determining a best-fit plane for the 3D point set;

projecting the 3D point set onto the best-fit plane;

determining a boundary for the best-fit plane according to the 3D point set;

projecting a grid onto the best-fit plane within the boundary, the grid containing a plurality of grid points;

initializing the grid points to zero;

determining a value for the grid points;

refining the value for at least a portion of the grid points;

selecting at least a portion of the grid points based on one of the value and the refined value; and

imaging the editable surface using the selected grid points, the editable surface representing a best-fit approximation of the 3D point set to the editable surface.

18. The method of claim 17, wherein the best-fit plane is determined by a dominant axis for the 3D point set.

19. The method of claim 17, wherein the boundary of the best-fit plane is determined by a plurality of point extremes contained in the projected 3D point set.

20. The method of claim 17, wherein the projected grid is based on predetermined grid parameters.

21. The method of claim 17, where in each grid point is defined by an intersection on the grid.

22. The method of claim 17, wherein the grid point value is determined by one or more points in the projected 3D point set within a predetermined area of the grid point and a distance from each point in the predetermined area to the grid point.

23. The method of claim 17, wherein the editable surface represents a NURBS surface.

24. The method of claim 17, further comprising the step of replacing the value with the refined value for the grid points selected with a value and a refined value.

25. The method of claim 22, wherein refining the value comprises:

forming a new grid by increasing the grid density, the new grid containing a plurality of new grid points;

determining a value for the new grid points;

fitting a new plane to the new grid points;

reevaluating the value for the new grid points; and

smoothing the value for the new grid points.

26. The method of claim 25, further comprising the steps of:

initializing the new grid points to zero; and

determining a new value for the new grid points.

27. The method of claim 26, wherein the new grid point value is determined by one or more points in the 3D point set within another predetermined area of the new grid point and a distance from each point in the another predetermined area to the new grid point, wherein the another predetermined area is smaller than the predetermined area.

28. The method of claim 26, further comprising the step of repeating the steps in claim 25.

29. The method of claim 25, wherein the new plane is weighted.

30. The method of claim 25, wherein the values of the new grid points are reevaluated.

31. The method of claim 25, wherein the values of the new grid points are smoothed.

59. The system of claim 57, further comprising the step of repeating the steps in claim 25.

32. A system for approximating an editable surface from a 3D data set comprising a computer-readable memory medium configured to store a program of instructions, the program instructions being executable to implement:

selecting a 3D point set from the 3D data set;

determining a best-fit plane for the 3D point set;

projecting at least a portion of the 3D point set onto the best-fit plane;

determining a boundary for the best-fit plane according to the projected 3D point set;

projecting a grid onto the best-fit plane within the boundary, the grid containing a plurality of grid points;

initializing the grid points;

determining a value for at least a portion of the grid points;

selecting at least a portion of the grid points with a value; and

imaging the editable surface using at least a portion of the selected grid points.

33. The system of claim 32, wherein the 3D point set comprises an arbitrary surface.

34. The system of claim 33, further comprising the steps of:

fitting an ellipsoid to the 3D point set; and

determining a dominant axis for the 3D point set based on the ellipsoid.

35. The system of claim 34, wherein the dominant axis is used to determine the best-fit plane.

36. The system of claim 32, wherein the 3D point set comprises one of the 3D data set and a portion of the 3D data set.

37. The system of claim 32, wherein the best-fit plane is determined by a dominant axis for the 3D point set.

38. The system of claim 32, wherein the boundary of the best-fit plane is determined by a plurality of point extremes contained in the projected 3D point set.

39. The system of claim 32, wherein the projected grid is based on predetermined grid parameters.

40. The system of claim 32, wherein each grid point is defined by an intersection on the grid.

41. The system of claim 32, wherein the grid points are initialized to zero.

42. The system of claim 32, wherein the grid point value is determined by one or more points in the projected 3D point set within a predetermined area of the grid point and a distance from each point in the predetermined area to the grid point.

43. The system of claim 32, wherein the editable surface represents a best-fit approximation of the 3D point set to the editable surface.

44. The system of claim 32, wherein the editable surface represents a NURBS surface.

45. The system of claim 32, further comprising the steps of:

refining the value for at least a portion of the at least a portion of the grid points; and

selecting at least a portion of the grid points based on one of the value and the refined value.

46. The system of claim 45, further comprising the step of replacing the value with the refined value for the grid points selected with a value and a refined value.

47. The system of claim 32, further comprising the step of converting the 3D data set to the 3D point set.

48. A system for approximating an editable surface from a 3D point set comprising a computer-readable memory medium configured to store a program of instructions, the program instructions being executable to implement:

determining a best-fit plane for the 3D point set;

projecting the 3D point set onto the best-fit plane;

determining a boundary for the best-fit plane according to the 3D point set;

projecting a grid onto the best-fit plane within the boundary, the grid containing a plurality of grid points;

initializing the grid points to zero;

determining a value for the grid points;

refining the value for at least a portion of the grid points;

selecting at least a portion of the grid points based on one of the value and the refined value; and

imaging the editable surface using the selected grid points, the editable surface representing a best-fit approximation of the 3D point set to the editable surface.

49. The system of claim 48, wherein the best-fit plane is determined by a dominant axis for the 3D point set.

50. The system of claim 48, wherein the boundary of the best-fit plane is determined by a plurality of point extremes contained in the projected 3D point set.

51. The system of claim 48, wherein the projected grid is based on predetermined grid parameters.

52. The system of claim 48, where in each grid point is defined by an intersection on the grid.

53. The system of claim 48, wherein the grid point value is determined by one or more points in the projected 3D point set within a predetermined area of the grid point and a distance from each point in the predetermined area to the grid point.

54. The system of claim 48, wherein the editable surface represents a NURBS surface.

55. The system of claim 48, further comprising the step of replacing the value with the refined value for the grid points selected with a value and a refined value.

56. The system of claim 53, wherein refining the value comprises:

forming a new grid by increasing the grid density, the new grid containing a plurality of new grid points;

determining a value for the new grid points;

fitting a new plane to the new grid points;

reevaluating the value for the new grid points; and

smoothing the value for the new grid points.

57. The system of claim 56, further comprising the steps of:

initializing the new grid points to zero; and

determining a new value for the new grid points.

58. The system of claim 57, wherein the new grid point value is determined by one or more points in the 3D point set within another predetermined area of the new grid point and a distance from each point in the another predetermined area to the new grid point, wherein the another predetermined area is smaller than the predetermined area.

60. The system of claim 56, wherein the new plane is weighted.

61. The system of claim 56, wherein the values of the new grid points are reevaluated.

62. The system of claim 56, wherein the values of the new grid points are smoothed.