NURBS surface fitting

• 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

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

Resolved using the implemented smoothing criteria

• 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

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

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.

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.