Modern measuring systems can easily produce data sets consisting of thousands, even millions of points

The data points are almost always random

Also, accurate modelling of shapes using NURBS often involves surfaces with tens of thousands of control points.

The developed surface approximation method was designed to address such situations. Using the cloud of points and a suitable base surface as input, the process involves the following iterative steps:

  • Data parameterisation (assigning UV coordinates to data points)
  • Linear Least Squares fitting
  • Knot insertion

Knot insertion is usually necessary in order to introduces additional control points and to provide additional flexibility for modelling the surface detail.  The iterative process may be applied a number of times until satisfactory modelling accuracy is achieved.

The described process is known to suffer from two main issues, which have been successfully resolved.

NURBS

Ill-conditioning

  • Relative sparsity of data points in relation to the control points can lead to ill-conditioning or even instability. This is often the case following knot insertion.
  • Solved through the use of suitable smoothing criteria, which also allow good user control over the surface regions poorly defined by the data.

Consider the example of fitting a flat base surface to non-uniformly distributed data

Ill-conditioning

 

Successive steps of knot insertion and fitting lead to ill-conditioning in sparsely sampled regions

Ill-conditioning

 

Resolved using the implemented smoothing criteria

Ill-conditioning

Computational efficiency

  • Large number of data points and control points can quickly lead to problems of insoluble size in terms of both memory and computational time
  • Solved by identiftying and fully exploiting the exact sparsity structure of relevant matrices
  • Realised computational complexity:

    - Memory storage linear with the number of control points
    - Computing time linear with the number of data points

Performance

The following data illustrates the realised performanace of the method on a modest Pentium PC (1GHz, 1Gb).

  • Number of data points: 1,000,000
  • Number of control points: 10,000
  • Total memory requirement: 1,054 KB
  • Preparation time (setting up normal equationa): 57 seconds
  • Solution time (per iteration): 233 seconds

Examples

Surface reconstruction from digitsed data

The pictures show reconstructed face of the statue of David (courtesy of the Digital Michelangelo Project). 500,000 points were obtained using laser scanner and the surface was reconstructed using 120,000 control points in iorder to accurately represent the fine detail.

Surface reconstruction from digitsed data

 

Simplification of CAD models

The pictures show a CAD model of a calculator. The original model consisted of several hundred trimmed NURBS patches. The model was sampled at a high density and a single wraparound NURBS surface was fitted to the data. This is important in many applications where dealing with a large number of trimmed surface antities (possibly with gaps and overlaps) causes difficulties in downstream processing, e.g. automatic meshing.

Simplification of CAD models