Methods, apparatus and computer program products that reconstruct surfaces from data point sets

A method of modeling a surface of an object, comprising the steps of:

• projecting each point and corresponding set of one or more neighboring points in a point set to a respective plane;
• determining a star for each plane;
• and
• merging the stars into a surface triangulation.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining an estimated normal for each of a plurality of points in a 3D point set that at least partially describes the 3D surface;
• evaluating a differential structure of the estimated normals associated with the plurality of points to estimate principal curvature directions on the 3D surface and classify a respective local neighborhood of each of the plurality of points in terms of its shape characteristic;
• determining a respective approximating surface for each of the local neighborhoods;
• and
• denoising the 3D point set by moving each of the plurality of points to a respective approximating surface that is associated with a local neighborhood of the respective point.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining a respective set of near points Si for each of a plurality of points pi in a 3D point set S that at least partially describes the 3D surface, where Si⊂S;
• determining a normal bundle for the 3D point set S by determining a respective plane hi of best fit for each of the sets of near points Si and a respective normal ni for each of the planes hi of best fit;
• and
• determining a respective approximating surface for each of the sets of near points Si using the normal bundle to estimate respective principal curvature directions for each of the sets of near points Si.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining a respective set of near points Si for each of a first plurality of points p1i in a first 3D point set S1 that at least partially describes the 3D surface, where Si⊂S1;
• fitting each set of near points Si with a respective approximating surface;
• denoising the first 3D point set S1 into a second 3D point set S2 by moving at least some of the first plurality of points p1i in the first 3D point set S1 to the approximating surfaces associated with their respective sets of near points Si;
• determining a plurality of stars from a second plurality of points p2i in the second 3D point set S2, by projecting the second plurality of points p2i onto planes Ti that are estimated to be tangent about a respective one of the second plurality of points p2i;
• and
• merging the plurality of stars into a digital model of the 3D surface.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining a respective set of near points for each of a plurality of points in a 3D point set that at least partially describes the 3D surface;
• fitting each set of near points with a respective approximating surface that is a selected from a group consisting of cylinders and quadratic and/or cubic surfaces;
• and
• denoising the 3D point set by moving each of the plurality of points in the 3D point set to the approximating surface associated with its respective set of near points.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining a respective set of near points for each of a first plurality of points in a 3D point set that at least partially describes the 3D surface;
• and
• determining an estimated normal for each of the first plurality of points by:
• determining a respective plane of best fit for each of the sets of near points;
• and
• determining a normal for each of the planes of best fit.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• determining a respective set of near points for each of a first plurality of points in a 3D point set that at least partially describes the 3D surface;
• determining a normal bundle by determining a respective plane of best fit for each of the sets of near points and a normal for each of the planes of best fit;
• and
• determining from the normal bundle at least one respective principal curvature direction for each of the sets of near points.

A method of modeling a three-dimensional (3D) surface, comprising the step of:

• denoising a 3D point set that at least partially describes the 3D surface by:
• classifying a first neighborhood of points in the 3D point set S1 using a mass distribution matrix of the first neighborhood of points to estimate first normals associated with the first neighborhood of points and a normal distribution matrix of the first normals to estimate principal curvature directions;
• fitting an approximate surface, which is selected from a group consisting of cylindrical, quadratic and cubic surfaces, to the first neighborhood of points;
• and
• moving at least one point in the first neighborhood of points to the approximate surface.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• identifying a respective subset of near points for each of a plurality of points in a 3D point set that at least partially describes the 3D surface by:
• determining dimensions of a near point search space using a random sample of the 3D point set;
• and
• selecting, for each of the plurality of points, a respective set of points in the 3D point set that are within a respective near point search space that is oriented about a respective one of the plurality of points;
• determining a plurality of stars from the plurality of points in the 3D point set by projecting the points in each subset of near points to a respective plane;
• and
• merging the plurality of stars into a digital model of the 3D surface.

A method of reconstructing a surface of an object from a three-dimensional (3D) point cloud data set S derived from scanning the object, comprising the steps of:

• determining a respective subset of near points Si⊂S for each of a plurality of points pi∈S;
• estimating a tangent plane Ti for each subset of near points Si;
• projecting each subset of near points Si onto its respective tangent plane Ti;
• constructing a respective star of each of the plurality of points pi from the projected points on each of the tangent planes Ti;
• merging the stars associated with the tangent planes Ti into a 3D model of the surface by eliminating edges and triangles from the stars that are in conflict and merging nonconflicting edges and triangles from the stars into a 3D surface triangulation;
• and
• filling one or more holes in the 3D surface triangulation.

A method of reconstructing a surface of an object from a three-dimensional dimensional (3D) point cloud, comprising the steps of:

• determining for each of a first plurality of points in the point cloud a respective approximating surface that fits the point's neighborhood;
• moving each of the first plurality of points to its respective approximating surface;
• determining an estimated tangent plane for each of a second plurality of points that have been moved to a respective approximating surface;
• projecting each of the second plurality of points and points in their respective neighborhoods to a respective one of the estimated tangent planes;
• constructing stars from points projected to the estimated tangent planes;
• and
• merging the stars into a surface triangulation.

A method of reconstructing a surface of an object from a three-dimensional (3D) point cloud, comprising the steps of:

• denoising the point cloud;
• determining an estimated tangent plane for each of a plurality of points in the denoised point cloud;
• projecting each of the plurality of points and other points in its respective neighborhood to a respective one of the estimated tangent planes;
• constructing stars from points projected to the estimated tangent planes;
• and
• merging the stars into a surface triangulation.

A method of modeling a three-dimensional (3D) surface, comprising the steps of:

• moving each of a plurality of first points in a point set that at least partially describes the 3D surface to a respective approximating surface that is derived by evaluating a respective first point and a plurality of its neighboring points in the point set;
• projecting at least one of the first points, which has been moved to an approximating surface, to a first plane that is estimated to be tangent about the at least one of the first points;
• projecting a plurality of points in a neighborhood of the at least one of the first points to the first plane;
• and
• generating a star from a plurality of projected points on the first plane.

A method of modeling a three-dimensional (3D) surface, comprising the step of:

• determining a star of a first point in a 3D point set that at least partially describes the 3D surface, by:
• projecting the first point and second, third and fourth points in a neighborhood of the first point to a plane;
• assigning respective weights to each of the second, third and fourth points that are based on projection distance;
• and
• evaluating whether the projection of the fourth point is within an orthocircle defined by a triangle having projections of the first, second and third points as vertices.

A method of modeling a three-dimensional (3D) surface, comprising the step of:

• determining a first star of a first point in a 3D point set that at least partially describes the 3D surface, by:
• projecting the first point and first near points in a neighborhood of the first point to a first plane that is estimated to be tangent to the first point:
• assigning respective weights to each of the projected first near points that are based on distances between the first near points and the projected first near points;
• and
• connecting the projected first point and at least some of the projected first near points with triangles that share the projected first point as a vertex, by evaluating whether a next projected near point in a first sequence of projected first near points is closer than orthogonal to an orthocenter of a triangle having the projected first point and two of the projected first near points as vertices.