Non-convex hull surfaces

1. A program storage device, comprising:

a memory storing instructions; and

at least one hardware processor to execute the instructions to:

sample a boundary surface of the object to obtain a data set, the data set comprises oriented points including sample point locations associated with orientation vectors;

estimate non-convex hull signed distance function parameters from the data set, the estimating further comprising the steps of:

a. associating a set of curvature parameters with the oriented points;

b. selecting a first oriented point of the data set, the first oriented point including a first sample point location, and a first orientation vector, the first oriented point having an associated first curvature parameter;

c. initializing the first curvature parameter to zero;

d. selecting a second oriented point of the data set, the second oriented point being different from the first oriented point, the second oriented point including a second sample point location, and a second orientation vector;

e. computing a first displacement vector from the first sample point location to the second sample point location;

f. computing a first temporary parameter as an inner product of the first orientation vector and the first displacement vector;

g. computing a second temporary parameter as a square norm of the first displacement vector;

h. computing a third temporary parameter as a result of subtracting the product of the first curvature parameter times the second temporary parameter, from the first temporary parameter;

i. if the third temporary parameter is larger than zero, making the first curvature parameter equal to the result of dividing the first temporary parameter by the second temporary parameter;

j. repeating steps d. to i. until every second oriented point has been selected; and

k. repeating steps b. to j. until every first oriented point has been selected;

evaluate the non-convex hull signed distance function on vertices of a volumetric mesh; and

approximate a zero level set of the non-convex hull signed distance function by a polygonal mesh using an isosurface algorithm.

2. The program storage device of claim 1 , wherein the surface is a smooth oriented, watertight surface.

3. The program storage device of claim 1 , wherein the data set is a finite set.

4. The program storage device of claim 1 , wherein the data set is an infinite set.

5. The program storage device of claim 1 , wherein the step of evaluating further comprises the steps of:

a. selecting a first vertex of the volumetric mesh;

b. setting a first vertex evaluation value to negative infinity;

c. selecting a third oriented point of the data set, the third oriented point including a third sample point location, and a third orientation vector, the third oriented point having an associated third curvature parameter from a set of curvature parameters;

d. computing a second displacement vector from the first vertex to the third sample point location;

e. computing a fourth temporary parameter as the inner product of the third orientation vector and the second displacement vector;

f. computing a fifth temporary parameter as the square norm of the second displacement vector;

g. computing a sixth temporary parameter as the result of subtracting the product of the third curvature parameter times the fifth temporary parameter, from the fourth temporary parameter;

h. if the sixth parameter is larger than the first vertex evaluation value, making the first vertex evaluation value equal to the sixth parameter;

i. repeating steps c. to h. until every third oriented point has been selected; and

j. repeating steps a. to i. until every first vertex of the volumetric mesh has been selected.

6. The program storage device of claim 1 , wherein a geometry of the reconstructed surface is independent of a reversal of the orientation vector.

7. The program storage device of claim 1 , wherein the associated orientation vectors are consistently oriented either towards the outside or towards the inside of the object.

8. The program storage device of claim 1 , wherein the volumetric mesh is a regular volumetric mesh.

9. The program storage device of claim 1 , wherein the volumetric mesh is an adaptive volumetric mesh.

10. The program storage device of claim 1 , wherein the volumetric mesh is a regular voxel grid.

11. The program storage device of claim 1 , wherein the volumetric mesh is an octree.

12. The program storage device of claim 1 , wherein the isosurface algorithm used is Marching Cubes Algorithm.

13. The program storage device of claim 1 , wherein the isosurface algorithm used is Dual Marching Cubes Algorithm.

14. The program storage device of claim 1 , wherein the data set is obtained using an adaptive subsampling method by interpolating a subset of the oriented points and approximating remaining oriented points under defined maximum error.

15. The program storage device of claim 1 , wherein the data set is acquired using optical measuring devices.

16. The program storage device of claim 1 , wherein the data set is acquired using multi-view stereo reconstruction.

17. The program storage device of claim 1 , wherein the orientation vectors are computed by independent measurements provided by a sensor.

18. The program storage device of claim 1 , wherein the orientation vectors are computed using neighboring sample point locations.

19. The program storage device of claim 1 , wherein the orientation vectors are computed using neighboring sample point locations and locations of sensors.

20. The program storage device of claim 1 , wherein the step of estimating further comprises the steps of:

a. associating a set of positive curvature parameters and a set of negative curvature parameters with the oriented points;

b. selecting a first oriented point of the data set, the first oriented point including a first sample point location, and a first orientation vector, the first oriented point having an associated first positive curvature parameter, and an associated first negative curvature parameter;

c. initializing the first positive curvature parameter and the first negative curvature parameter to zero;

d. selecting a second oriented point of the data set, the second oriented point being different from the first oriented point, the second oriented point including a second sample point location, and a second orientation vector;

e. computing a first displacement vector from the first sample point location to the second sample point location;

f. computing a first temporary parameter as an inner product of the first orientation vector and the first displacement vector;

g. computing a second temporary parameter as a square norm of the first displacement vector;

h. computing a third temporary parameter as a result of subtracting the product of the first positive curvature parameter times the second temporary parameter, from the first temporary parameter;

i. if the third temporary parameter is larger than zero, making the first positive curvature parameter equal to the result of dividing the first temporary parameter by the second temporary parameter;

j. computing a fourth temporary parameter as a negative of the first temporary parameter;

k. computing a fifth temporary parameter as a result of subtracting the product of the first negative curvature parameter times the second temporary parameter, from the third temporary parameter;

l. if the fifth temporary parameter is larger than zero, making the first negative curvature parameter equal to the result of dividing the third temporary parameter by the second temporary parameter;

m. repeating steps d. to l. until every second oriented point has been selected; and

n. repeating steps b. to m. until every first oriented point has been selected.