Faller RV (ed): Assessment of Oral Health.
`Monogr Oral Sci. Basel, Karger, 2000, vol 17, pp 73–129
`
`............................
`Analysis of the Morphology of Oral
`Structures from 3-D Co-Ordinate Data
`
`V. Jovanovski a, E. Lynchb
`
`a Department of Adult Oral Health, St. Bartholomew’s and the Royal London School
`of Medicine and Dentistry, London, and
`b Restorative Dentistry and Gerodontology, School of Clinical Dentistry, The Queen’s
`University of Belfast, UK
`
`Abstract
`A non-intrusive method is described which can be used to determine the forms of oral
`structures. It is based on the digitising of standard replicas with a co-ordinate-measuring
`machine. Supporting software permits a mathematical model of the surface to be recon-
`structed and visualised from captured three-dimensional co-ordinates. A series of surface
`data sets can be superposed into a common reference frame without the use of extrinsic
`markers, allowing changes in the shapes of oral structures to be quantified accurately over
`an extended period of time. The system has found numerous applications.
`Copyright Ó 2000 S. Karger AG, Basel
`
`Introduction
`
`There is a clinical need for objective quantification of the shapes of three-
`dimensional oral structures such as the morphology of teeth, the position
`and contour of the gingivae, the surface characteristics of fillings and their
`adaptation to the teeth in which they are placed. This need is particularly
`evident in the field of conservative dentistry which is concerned with all aspects
`of the conservation and restoration of teeth as well as the whole care of the
`patient. Additionally, such care requires assessment not only of shape, but
`also of changes in shape due to, for example, the wear of teeth and restorations,
`plaque accumulation, gingival recession or gingival inflammation.
`Much of this assessment has previously been subjective and reliant on
`the clinician’s experience. Examples are the USPHS criteria for evaluating
`
`3SHAPE EXHIBIT 1125
`3Shape v. Align
`IPR2019-00157
`
`

`

`occlusal restorations [1] by which several aspects of a restoration are classified
`as ideal, acceptable or unacceptable based on the observations of two or
`more evaluators, or the Leinfelder method [2] in which an experimental
`cast is compared visually to standard casts calibrated for wear in steps of
`100 ♯m.
`Subjective methods are insensitive to small changes and produce few,
`if any, quantitative results. Consequently, numerous techiques for obtaining
`objective measurements have been developed. Sometimes the features of inter-
`est can be presented in a planar (two-dimensional) form, for instance by
`producing sectioned silicone replicas which permit lengths and angles to be
`measured from photographs magnified by a known factor [3]. However, the
`most useful and widely applicable techniques are those which provide numeri-
`cal data in the form of three-dimensional co-ordinates. Such techniques include
`stereophotogrammetry [4, 5], reflex microscopy [6–8], laser interferometry
`[9, 10], scanning electron microscopy [11–14], microtomography [15–17], con-
`forcal microscopy [18], infra-red cameras [19] and mechanical digitisers [20].
`A review can be found in Chadwick [21] and a table of methods and accuracies
`in Bayne et al. [22].
`From the point of view of conservative dentistry, the techniques of greatest
`interest are those which can provide three-dimensional co-ordinate data ac-
`quired from an entire tooth surface with sufficient density and accuracy to
`permit the construction of a computer model. Additionally, the speed of data
`acquisition must be sufficient to permit practical application in clinical research
`studies involving large numbers of subjects.
`Each of the techniques listed above is well suited for its particular area
`of application, but fails to meet these requirements in one or more aspects.
`A satisfactory solution has been provided by a category of measurement
`apparatus known as ‘co-ordinate measuring machines’ (CMMs), many of
`which were developed in the 1980s for industrial quality control of manufac-
`tured parts. Most CMMs consist of a horizontal platform upon which the
`object to be measured (a tooth replica, for instance) is placed and 3-D co-
`ordinates are acquired from it by an active data acquisition component in the
`form of a mechanical stylus or optical probe.
`A number of systems based on CMMs or devices of equivalent func-
`tionality have been employed in dental research [23–30]. Their application
`generally involves three distinct stages of work. Firstly, a replica or model of
`the study surface is produced. Depending on the specific system used, there
`may be a requirement that the material be non-elastic, electrically conductive
`or of a particular colour and reflectivity. Secondly, co-ordinate data are ac-
`quired from the model surface. Finally, the data are analysed to produce
`quantitative results.
`
`Jovanovski/Lynch
`
`74
`
`

`

`The published reports vary in the emphasis and amount of detail given
`relating to the methodology, but it is evident that the analysis of acquired co-
`ordinate data has frequently been problematic due to the unavailability of
`software which would be specifically tailored to the needs of dental research.
`The use of software intended for other application areas can render the process
`impracticably laborious. Where specialised software has been written, little is
`reported about the mathematical methods employed. Mitchell and Chadwick
`[31] write that ‘although clinical results derived from such techniques are
`reported within the dental literature, none of the dental papers to date has
`described fully the underlying theory’.
`With this in mind we present a detailed account of the methodology,
`supporting software and clinical application of the system for dental co-
`ordinate metrology developed at St. Bartholomew’s and the Royal London
`School of Medicine and Dentistry [32]. Emphasis is given to description of the
`supporting mathematical models and the software which permits researchers to
`perform their own analyses by providing: (1) visualisation of surfaces with
`realistic rendering to enable the identification of anatomical features of interest;
`(2) construction of cross-sections and measurement of lengths and angles on
`such cross-sections; (3) quantification of changes in morphology by compar-
`ison of sequential replicas, particularly depth and volume changes on hard
`tissue and gingivae, and (4) output of results in graphical and numerical
`formats.
`Particular attention is paid to the ‘superposition’ (or ‘registration’) of
`data sets obtained from a sequence of replicas of the same oral structure taken
`at different times. Such data sets do not generally lie in the same frame
`of reference and their comparison requires the application of co-ordinate
`transformations (rotations and translations) by which corresponding anatom-
`ical features are brought into coincidence.
`The material is presented here in the following sequence, which reflects
`the progression from clinical replication to numerical results:
`
`Replication of the study surface
`
`
`Co-ordinate data acquisition
`
`
`Construction of a computer model of the study surface
`
`
`Superposition of sequential data into a common reference frame
`
`
`Measurement
`
`Dental Metrology
`
`75
`
`

`

`Replication of the Study Surface
`
`Materials and Methods
`The physical characteristics and mode of operation of CMMs preclude
`their use directly in the mouth. However, the provision of dental care invariably
`involves the replication of oral structures at some stage and dentistry has
`developed materials for the accurate and safe replication of oral structures,
`together with clinical expertise to use them effectively [33, 34]. Silicone impres-
`sion materials are ideal for the purpose in hand, having been widely researched
`to determine their safety for use in the mouth, their elasticity, their ability to
`replicate very fine detail and their dimensional stability [35, 36].
`The replicas in our studies were produced by a procedure similar to the
`standard routine followed in patient care but appropriately modified to address
`the special considerations that arise from the intended purpose of measuring
`changes in surface morphology. In studies involving sequential replicas of the
`same oral structure over a period of time it was desirable that the co-ordinate
`data capture be performed with all replicas having approximately the same
`orientation. In order to recreate not only the surface of interest but also its
`orientation, a special impression tube was designed which could be reposi-
`tioned within the mouth in the same orientation each time.
`An aspect of a tooth was selected as appropriate for the study to be
`undertaken, usually the buccal or occlusal surface of a tooth, and a plaster
`model was constructed from an alginate impression (fig. 1). A 9-mm length
`of accurately machined square section, rigid brass tubing of 12- or 16-mm
`nominal internal width was selected according to the size of the area to be
`studied. The surface of the model was lubricated and the impression tubing
`positioned on the plaster model over the surface to be replicated, so that its
`long axis was approximately normal to that surface (fig. 2). Its periphery was
`modified as necessary using a stone or a file so as to approximate the surface
`reasonably well. A polymethyl methacrylate resin was applied to the outside
`of the tubing to ensure that there were no gaps between the surface of the
`tooth and the tubing and to facilitate the correct locating of the tube in the
`mouth itself on one or many occasions.
`On a subsequent patient visit, the quadrant containing the study surface
`was isolated and the tooth was gently dried with air. The tube was then located
`in its position in the mouth, held firmly in place and a polyvinyl siloxane
`dental impression material (Kerr Extrude, SDS Kerr, Orange, Calif., USA)
`was then injected onto the tooth surface within the tube to fill the latter to
`excess (fig. 3).
`When the impression material had polymerised, the tube containing the
`silicone impression was removed from the mouth. Approximately 3 min after
`
`Jovanovski/Lynch
`
`76
`
`

`

`1
`
`2
`
`3
`
`4
`
`Fig. 1. The surface of interest identified in vivo and on the plaster model.
`Fig. 2. Fabrication of the impression tube.
`Fig. 3. Replication of the study surface.
`Fig. 4. The completed replica.
`
`Dental Metrology
`
`77
`
`

`

`Table 1. Repeatability of hard tissue
`replication
`
`Study
`date
`
`1996
`1996
`1997
`1997
`
`Number
`of pairs
`
`RMS/point
`♯m (mean×SD)
`
`112
`30
`63
`18
`
`8.4×2.1
`7.7×1.8
`6.5×2.5
`5.9×1.4
`
`this removal the base of the brass tube was trimmed flush with the edge of
`the tubing using a sharp blade and the block of silicone extruded from it. The
`tube was then available for further use on a subsequent occasion and the
`replica was ready for study (fig. 4).
`
`Results
`The physical properties of silicone-based impression materials have been
`researched extensively [36–40], showing their dimensional accuracy and long-
`term stability to be in the region of 0.1%. However, the replicas used in
`this work were not produced under the controlled conditions available in a
`laboratory, but in a clinical environment where they might be subjected to
`many additional influences. It was therefore considered necessary to perform
`our own evaluations of the practically achievable repeatability of sequential
`replicas of the same oral structure.
`Sequences of repeat replicas were digitised and the data sets superposed
`into a common reference frame. Pairs of data sets were compared by evaluating
`the z co-ordinates of each of the data sets at 2,500 x–y locations distributed
`on a rectangular grid and recording the differences (which should ideally be
`zero). The measure of repeatability was defined as the root mean square (RMS)
`of the z differences, customarily termed the ‘RMS/point’ [30, 41]. Bearing in
`mind the procedures carried out to arrive at superposed mathematical models
`of the replica surfaces, the repeatability values obtained were all-inclusive,
`being influenced not only by the replication accuracy but also by the accuracy
`of the co-ordinate measurements, the superposition, as well as the instability
`of any soft tissue, e.g. the gingivae.
`
`Hard Tissue
`Table 1 shows the repeatability of replication of hard tissue over the course
`of several studies involving a total of 223 replica pairs taken at intervals ranging
`from 10 min to 6 months. Values which were found to differ significantly from
`these could invariably be attributed to the clinical procedure, for instance
`distortion due to failure of the replica material to polymerise fully.
`
`Jovanovski/Lynch
`
`78
`
`

`

`Soft Tissue
`Repeatability in the replication of gingivae was assessed on a series of
`10 replicas taken in immediate succession. The pairwise RMS/point values
`were found to be between 29.0 and 64.5 (mean 41.8) ♯m. It is not currently
`clear what proportion of these differences in the sequential replicas of gingi-
`vae can be attributed to the physical distortion caused by the pressure
`applied during replication, and how much to changes in the gingival contour
`resulting from other factors including alterations in blood flow, desiccation
`or reactions to the chemicals within the impression material prior to its
`polymerisation. However, the repeatability of replication of the gingivae is
`sufficiently good to permit the investigation of changes in their contour
`caused by factors of interest in our studies, since such changes are generally
`considerably greater.
`
`Plaque
`The repeatability of replicas made in order to determine the location and
`thickness of plaque were comparable to those made on clean teeth. There was
`some concern that the plaque may be removed or disturbed by the replication
`process, but measurements of the repeat replicas indicated that any such effects,
`if they had occurred, would be too small to detect with our system. Further-
`more, the clinical applications have confirmed that the accuracy is sufficient,
`for instance, to demonstrate the progressive accumulation of plaque over a
`period of 21 days and to detect statistically significant differences between the
`efficacy of two plaque-removal procedures.
`
`Data Acquisition
`
`CMM and Optical Probe
`The central data acquisition equipment is a Merlin Mk II 750 Co-
`ordinate Measuring Machine (International Metrology Systems Ltd., Liv-
`ingstone, UK) fitted with a Renishaw (Renshaw plc, Wotton-under Edge,
`UK) OP2 optical probe (fig. 5). The dimensions of the machine permit
`accommodation of a wide variety of differently sized objects, combining a
`large measuring volume (500¶750¶500 mm) with high accuracy throughout
`that volume. The worktable consists of a block of solid granite whose mass
`reduces the effects of environmental vibration. The position of the probe in
`each axis is determined to a resolution of 0.5 ♯m by a photocell which detects
`patterns on a stainless steel/glass grating. The accuracy of the position in
`each axis is 4.0 ♯m+L/275000 where L is the distance (in metres) travelled
`from an initial starting point. Control is provided by an IBM-PC compatible
`
`Dental Metrology
`
`79
`
`

`

`Fig. 5. The CMM and OP2 probe.
`
`computer interfaced to the electronic desk unit which integrates the functions
`of the CMM and probe.
`The Renishaw OP2 optical probe operates on the principle of ‘optical
`triangulation’ (fig. 6). A laser diode generates infrared laser radiation with a
`wavelength of 830 nm which is focused onto the surface, producing a spot
`25 ♯m in diameter. The light scattered from the surface is detected by a
`position-sensitive device from which the surface height is computed. Each
`probe is individually calibrated and the calibration data stored in the controller
`firmware. The vertical measurement range of the probe is ×2 mm but this is
`effectively extended by the vertical motion of the probe column. Further
`flexibility in orienting the probe is provided by a multidirectional mounting
`which permits rotation of the probe around two axes. The maximum measure-
`
`Jovanovski/Lynch
`
`80
`
`

`

`Fig. 6. Principle of operation of the OP2 probe. Copy-
`right Ó 1988 Renishaw plc. Reproduced with permission.
`
`Fig. 7. The angle between the optical centre line and the surface normal. Copyright
`Ó 1988 Renishaw plc. Reproduced with permission.
`
`ment frequency is 50 readings/s but in the integrated Merlin/OP2 configuration
`the optimal speed was determined to be 10 readings/s.
`Two primary characteristics of a measurement device are its ‘repeatability’
`(variations between repeated measurements) and ‘accuracy’ (how close the
`measurement is to the true value). The OP2 probe has a quoted repeatability
`of 2 ♯m. Its accuracy, however, depends on several factors, foremost of which
`is the angle between the probe’s optical centre line and the surface normal
`(fig. 7), termed the ‘gradient’. As the gradient increases, the intensity of the
`
`Dental Metrology
`
`81
`
`

`

`scattered light which reaches the detector decreases and the focused spot
`becomes elongated to an ellipse, which reduces the detection reliability. An
`optimal arrangement is achieved when the surface normal coincides either
`with the optical axis of the laser diode or with that of the detector and in
`such cases its accuracy is 5 ♯m.
`A replica is digitised by programming the probe to move across the surface
`tracing a pattern of parallel ‘scan lines’. The data point spacing (or ‘scanning
`pitch’) is most commonly selected to be 100 ♯m, with dimensions of a typical
`region of interest being 10¶10 mm. Such a region requires around 25 min
`of processing time. The worktable can accommodate up to 36 replicas, placed
`on a 6¶6 grid of squares, which can be processed sequentially without operator
`intervention. On completion of a batch of replicas the data sets are transferred
`to shared storage on a Novell NetWare (Novell Inc., Utah, USA) server where
`they can be accessed by all authorised users.
`
`Repeatability and Accuracy
`Familiarity with the capabilities and, equally importantly, the limitations
`of a measurement system allows it to be used efficiently while avoiding any
`temptation to extract meaningful information from unreliable data. The repeat-
`ability and accuracy are a complex combination of many factors and although
`it is convenient to summarise them in terms of single values, such summaries
`are not always realistic indicators of performance.
`A series of experiments to establish the repeatability and accuracy of
`measurements in practice were carried out under standard operating conditions
`and on surfaces which were representative of those encountered in the clinical
`applications.
`Repeatability was assessed by performing multiple measurements of a
`single replica. Since the OP2 probe is sensitive to the surface gradient, a
`labial surface which contained both mild and severe gradients was chosen
`(fig. 8).The replica was digitised four times. Within each region of interest
`(A–D), the z co-ordinates were evaluated at 2,500 locations and the standard
`deviation was computed for each location. Repeatability for each region was
`defined as the average of the 2,500 standard deviations. The results are
`given in table 2. As expected, measurements on steeper gradients were less
`repeatable, except in the case of region D which was not located on the
`smooth hard tissue.
`The accuracy was determined by measuring objects of known shape and
`dimensions and also the replicas of those objects made from standard impres-
`sion material. On a sphere of known diameter, the acquisition errors manifested
`themselves as progressive systematic deviations from the true values in accord-
`ance with the graph in figure 9, plus an additional random component which
`
`Jovanovski/Lynch
`
`82
`
`

`

`Fig. 8. Regions with different gradients.
`
`Table 2. Repeatability on different gradients
`
`Region
`
`A
`
`20º
`2.4
`
`B
`
`52º
`4.0
`
`C
`
`70º
`5.3
`
`D
`
`20º
`4.5
`
`Gradient
`Repeatability, ♯m
`
`is of a similar magnitude to the errors on flat, optimally oriented surfaces
`[42, 43]. The result of measuring a smooth surface was, therefore, again a
`smooth surface, although slightly distorted in regions with steep gradients.
`This had the desirable consequence of preserving reproducibility. Thus, when
`comparing sequential replicas of a single tooth, the difference between the
`two replicas could be determined to a greater accuracy (generally 5 ♯m) than
`could their true shapes.
`It was also found that the probe’s accuracy was not omnidirectional with
`respect to rotation around the optical centre line and that optimal results
`could be achieved if the probe travelled in a direction which was normal to
`the plane defined by the laser beam and the optical centre line [44]. The
`
`Dental Metrology
`
`83
`
`

`

`Fig. 9. OP2 probe accuracy vs. gradient.
`
`standard procedure for digitising replicas was modified to take this aspect
`into account.
`If a surface with a variable gradient is to be digitised without continually
`reorienting the probe, the best compromise is to orient the probe in such a
`way that the optical centre line is normal to the ‘mean best fit plane’ through
`the surface. Some surfaces can be processed using two or more probe orienta-
`tions, but doing so requires additional operator effort and is not used routinely.
`In most applications involving single surfaces of teeth, the region of interest
`does not extend over too large a range of gradients and the replica can be
`positioned on the worktable in such a way that it is presented to the probe
`in a favourable orientation.
`Although the error in z co-ordinates acquired on steep gradients may be
`relatively large (assuming that the probe is oriented so that its optical centre
`line coincides with the z axis), the errors of computed ‘distances’ are smaller
`when the dimension of interest is in a direction normal to the surface, for
`instance when measuring the loss of hard tooth tissue. If ♅z is the acquisition
`error for a point on a flat surface inclined at angle ♡ to the horizontal, then
`the error of measured distances ♅d is only affected by that component of
`the acquisition error which lies in the direction of the dimension of interest
`(♅d>♅z cos ♡). If a replica is digitised in two different orientations, the average
`probe-to-surface angle will also differ and the measurements at any particular
`location on the replica will have been made under different accuracy conditions.
`Similar considerations apply when digitising two sequential replicas of the
`
`Jovanovski/Lynch
`
`84
`
`

`

`same oral structure. For purposes of quantifying morphological change, the
`two data sets can be brought into a common reference frame but doing so
`does not compensate for inconsistencies caused by acquisition errors which
`arise from the different probe-to-surface gradients. In practice this aspect
`proved not to be a problem for misorientations of up to 10º, an accuracy of
`positioning which is easily achieved by the operator.
`The repeatability of measurements was found to be lower on regions
`whose contour changes rapidly over an interval comparable to the scanning
`pitch. This is not due to acquisition errors, since it occurs even with a theoreti-
`cally perfect digitiser, but a consequence of the sparse spacing of the data
`points relative to the complexity of the surface contour. In relation to oral
`structures, this effect can occur to a small extent on gingivae, shown by the
`reduced repeatability for region D of figure 8. However, changes in gingival
`contour are evaluated over a sufficiently large region (?1 mm2) for the height
`uncertainty to be greatly reduced by averaging. Thus, even with high-accuracy
`digitising systems, on certain types of surface features the sampling density is
`the primary determinant of accuracy and repeatability. The scanning pitch
`therefore needs to be appropriate to the surface morphology and the desired
`detail of information. In the literature, assessments of accuracy and repeatabil-
`ity of individual measurement systems are generally produced by measuring
`a flat surface, perhaps at several different inclinations. Such assessments should
`not be taken to mean that the values so provided are valid for ‘real’ tooth
`replicas, or that they are constant over the entire surface.
`
`Reconstruction of Surfaces from Co-Ordinate Data
`
`The data set obtained by digitising a replica consists of individual 3-D
`points (fig. 10). For the purposes of visualisation and measurement such a
`representation is not the most convenient or practical. For instance, one
`method of computing the volume enclosed between two surfaces is based on
`evaluating the difference in their z co-ordinate for a given x and y. This
`approach is not possible if the two surfaces were digitised over different x–y
`grids. The co-ordinate data therefore need to be represented in a form appro-
`priate to the intended analyses. Since the orientation and movement of the
`laser probe during scanning are such that only one z co-ordinate is sampled
`at each (x, y) location, the natural form of a continuous surface that models
`the acquired data is a single-valued function z>f(x, y).
`The aim of surface reconstruction is to find such a function f(x, y) which
`passes through the measured points exactly (interpolation) or as closely as
`sensibly possible (approximation) and which models the underlying surface
`
`Dental Metrology
`
`85
`
`

`

`Fig. 10. A data set consisting of 11,432 points acquired from a labial tooth surface.
`
`with sufficient accuracy in the regions between data points. The degree of
`success with which this can be done is dependent, amongst other things, on
`the accuracy of the measurements, their density (which should be sufficiently
`high to represent the smallest features of interest) and their (x, y) locations
`(more complex and time-consuming for non-uniform data). From a practical
`viewpoint, it is also desirable that the computation and subsequent evaluation
`of the function f be efficient and numerically stable.
`
`Polynomial Splines
`Consider the interpolation of a set of 2-D data points A>{(x1, y1),
`(x2, y2), ..., (xn, yn)} obtained from measurements of a curve defined on an
`interval [xmin, xmax] satisfying xmin>x1=x2==xn>xmax. We wish to find a
`function y>f(x) defined on the same interval which passes through all the
`points of A.
`The simplest solution is provided by the piecewise-linear function whose
`graph can be constructed by joining the successive points of A with line
`segments. This function is continuous but it is not smooth and therefore it
`cannot be expected to model curved lines accurately.
`
`Jovanovski/Lynch
`
`86
`
`

`

`On the other hand, the n-th degree polynomial
`a0+a1x+a2x2++anxn
`
`(1)
`
`whose coefficients ai can be determined formally by solving the system of
`n linear equations obtained by substituting each (xi, yi)
`in turn into
`expression (1), passes through all the points of A, but its value between the
`data points may often exhibit spuriously large oscillations. Its behaviour is
`non-local in the sense that each coefficient is dependent on all the data points
`and even a small change in the location of any of the points will in general
`alter the appearance of the entire curve.
`An intermediate scheme which is both sufficiently flexible and stable is
`one whereby a function f is constructed by defining different polynomials on
`each subinterval [xi, xi+1]. These polynomials can be of a low degree (often
`cubic) and conditions can be specified at the joins in such a way that the
`resulting curve has continuity not only of value, but also of its first and possibly
`higher-order derivatives. Functions constructed in this way are known as
`‘polynomial splines’, a term which derives from the analogy with the draughts-
`man’s tool of the same name [45].
`The concept of polynomial splines can be extended to higher dimensions.
`Polynomial spline surfaces have found wide application in a diversity of areas
`including computer-aided design [46], reverse engineering [47, 48], terrain
`mapping [49, 50] and medicine [51]. On this basis they were considered appro-
`priate for modelling oral structures whose shapes are almost arbitrarily compli-
`cated and which belong to the category of ‘free-form’ surfaces about which
`very few assumptions can be made. A concise introduction to the mathematical
`theory and practical implementation of polynomial splines can be found in
`Cox [52, 53], and with more detail in de Boor [54].
`
`Polynomial Spline Curves
`Polynomial spline curves can be expressed as linear combinations of basis
`functions known as ‘B-splines’. In defining a spline on an interval [xmin, xmax],
`we will consider that the interval is partitioned by N points ♮1, ..., ♮N termed
`‘interior knots’:
`
`xmin=♮1O ♮2OO ♮N=xmax
`
`and that additional points, termed ‘exterior knots’, are defined such that
`
`O ♮Ö1O ♮0Oxmin, xmaxO ♮N+1O ♮N+2O
`
`Most commonly, the exterior knots are selected such that ♮j>xmin if j=1 and
`♮j>xmax if j?N and this will be assumed to apply here.
`
`Dental Metrology
`
`87
`
`

`

`[xmin, xmax]
`The interval
`I0, I1, ..., IN defined by
`
`is divided into N+1 disjoint subintervals
`
`Ij> [♮j, ♮j+1)
`
`[♮j, ♮j+1]
`
`j>0, 1, ..., NÖ1,
`j>N.
`
`is defined on the knots
`A B-spline of order n, denoted by Nn, j(x),
`♮jÖn, ♮jÖn+1, ..., ♮j by the recurrence relation due to Cox [55] and de Boor [56]:
`Nn, j(x)> xÖ♮jÖn
`♮jÖ1Ö♮jÖn NnÖ1, jÖ1(x)+ ♮jÖx
`♮jÖ♮jÖn+1 NnÖ1, j(x)
`
`if n?1
`
`and
`
`N1, j(x)> 1
`
`if xeIjÖ1,
`0 otherwise.
`
`The B-spline Nn, j(x) consists of polynomial ‘pieces’ of degree nÖ1 so, for
`instance, B-splines of order 4 are referred to as cubic B-splines. It is non-zero
`only on the interval (♮jÖn, ♮j) and therefore if a function is represented as a
`linear combination of B-splines, altering any one of the coefficients will only
`alter the function locally, over the same interval.
`A polynomial spline curve s(x) of order n defined on a set of knots
`♮1, ..., ♮N is a linear combination of B-splines
`
`q
`
`s(x)>
`
`j>1
`
`cjNn, j(x)
`
`where q>N+n and c1, ..., cq are ‘B-spline coefficients’. Interpolation of a set
`of data points with a spline curve thus consists of selecting an appropriate grid
`and then determining the unknown B-spline coefficients from the conditions
`s(xi)>yi. Figure 11 shows a cubic spline curve
`
`s(x)>11
`
`j>1
`
`cjN4, j(x)
`
`with N>7 interior knots. The B-spline N4, 6(x) is shown in bold.
`
`Polynomial Spline Surfaces
`A polynomial spline surface is defined over a rectangular region [xmin, xmax]¶
`[ymin, ymax]. Taking each axis separately, denote by Mnx, i(x) the B-splines of
`order nx for a set of Nx interior knots ♮1, ..., ♮Nx on [xmin, xmax] and by
`Nny, j(y) the B-splines of order ny for a set of Ny interior knots ♯1, ..., ♯Ny on
`[ymin, ymax]. A polynomial spline surface s(x, y) is defined as the sum of products
`of B-splines
`
`Jovanovski/Lynch
`
`88
`
`

`

`Fig. 11. A spline curve and the B-splines of which it is composed.
`
`q
`
`y
`
`cijMnx, i(x)Nny, j(y)
`j>1
`
`qx
`
`s(x)>
`
`i>1
`
`with coefficients {cij |i>1, ..., qx, j>1, ..., qy} where qx>Nx+nx and qy>Ny+ny.
`The process of constructing the interpolant of a set of data points (xi, yi, zi)
`consists of finding the unknown coefficient matrix C by solving the system of
`linear equations resulting from the conditions s(xi, yi)>zi. If the x–y locations
`of the data points lie on a rectangular mx¶my grid, then the coefficients C
`can be determined extremely rapidly and efficiently [53] by taking advantage
`of the separability of the system into the form AxCAT
`y>F where Ax is the
`mx¶mx matrix consisting of B-spline basis functions in x evaluated at the x
`gridlines, and Ay similarly for y.
`
`Interpolation of CMM Data
`As a consequence of the way in which a spline surface is defined as a
`sum of products of univariate B-splines, interpolation is straightforward only
`if the data points lie on a rectangular x–y grid. This is not the case with CMM
`data whose spacing is controlled by two parameters: the speed of motion of
`the probe column, and the frequency of readings of the OP2 probe. The two
`parameters are computed by the system software from a user-specified desired
`point spacing, but the actual achieved spacing is not guaranteed to be equal
`
`Dental Metrology
`
`89
`
`

`

`to this value, or to be regular. Additionally the laser beam need not be oriented
`vertically in which case the scan line is not straight but dependent on the
`surface contour. Whilst some CMMs are capable of producing data with
`constant spacing, this is not a great advantage since the rectangular distribution
`is generally lost if a data set is rotated in order to superpose it onto another.
`It was therefore necessary to consider methods appropriate for data points
`which do not lie on a rectangular grid.
`Although any of the many existing methods for gridding generally scat-
`tered data could be applied, advantage can be taken of the fact that the data
`points are distributed on approximately straight lines [57–60]. The data set is
`regularised first in the direction of x, then in y by two series of successive
`univariate interpolations, resulting in a