Meshless parameterization for surface reconstruction , Michael Floater and M. Riemers, computer aided geometryc design 18 (2001) pg 77-92. The no-mesh part.

Meshless parameterization and B-spline surface reconstruction Michael Floater. The Mathematics of Surfaces IX, 2000, pg 1-18. Used for B-splines. These two papers extend the work of his '97 paper to data points without a mesh. Once the points are projected onto the plane a Delauny triangulation yields a triangular mesh, if desired.

• The Delauny triangulation need not be good, since it only needs to reflect the relative placement of the points.
• No proof of no folding.
• Approach:
  • Pick the boundary point. Order them, and place them on the convex boundary in 2D.
  • For each interior point, find its n "nearest neighbors" and set up the usual least-squares weights. Reciprocal weights work best; i.e., wi = 1/(length of edge) / Length of all edges.
  • Take neighborhood to be 10-20 nearest points.
• Includes a thin-plate spline error term for fitting the B-spline patch (2nd paper).
• Proofs in first paper:
  • The matrix is invertible under weak conditions (neighborhood size big enough).
  • Method 1 uses all points within a radius r. May fail if not uniformly sampled or the surface folds back on itself. Uses uniform weights.
  • Method 2 is similar except the weights are the (normalized) reciprocal distances.
  • Method 3 use the n nearest neighbors. Project them onto the plane, triangulate, then use the shape-preserving weights.
  • The boundary was ordered by hand for one example, in the other they marked the boundary by hand, but sorted them (1/2 at a time) using the same least-squares approach.