CHEBYSHEV REFERENCE SOFTWARE FOR THE EVALUATION OF COORDINATE MEASURING MACHINE DATA

Directorate-General For Translation European Commission

Description

Scientific and technical research
Target audience: Scientific

Informations

• Publié par: EUROPEAN-COMMISSION
• Nombre de lectures: 74
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

coti M}^
d on behalf of
• *
• ,•
*•* COMMISSION OF THE EUROPEAN COMMUNITIES
CHEBYSHEV REFERENCE SOFTWARE
FOR THE EVALUATION OF COORDINATE
MEASURING MACHINE DATA
G.T. ANTHONY, B.P. BUTLER, M.G. COX,
A.B. FORBES, SA. HANNABY, FM. HARRIS
NATIONAL PHYSICAL LABORATORY
B. BITTNER, R. DRIESCHNER, R. ELLIGSEN,
H. GROSS
PHYSIKALISCH-TECHNISCHE BUNDESANSTALT
J. KOK
CENTRUM VOOR WISKUNDE EN INFORMATICA
Programme for REPORT Directorate General XII
Applied Metrology EUR 15304 EN Science, Research and
and Chemical Development
Analysis (BCR)
EC Brussels
National Physical Laboratory - Teddington - UK - Middlesex TW11 OLW ?
Published on behalf of
COMMISSION OF THE EUROPEAN COMMUNITIES
CHEBYSHEV REFERENCE SOFTWARE
FOR THE EVALUATION OF COORDINATE
MEASURING MACHINE DATA
G.T. ANTHONY, B.P. BUTLER, M.G. COX,
A.B. FORBES, S.A. HANNABY, P.M. HARRIS
NATIONAL PHYSICAL LABORATORY
B. BITTNER, R. DRIESCHNER, R. ELLIGSEN,
H. GROSS
PHYSIKALISCH-TECHNISCHE BUNDESANSTALT
PARI EUROP. Biblioth.
N.c.^/^y
J. KOK
CI.
CENTRUM VOOR WISKUNDE EN INFORMATICA
/L.dLo*- JUMoÇ
Directorate General XII REPORT Programme for
Science, Research and EUR 15304 EN Applied Metrology
Development and Chemical
Analysis (BCR)
EC Brussels October 1993
National Physical Laboratory - Teddington - UK - Middlesex TW11 OLW Publication no. EUR 15304 EN of the
Commission of the European Communities,
Dissemination of Scientific and Technical Knowledge Unit,
Directorate General Telecommunications, Information Market and
Exploitation of Research,
Luxembourg
©ECSC - EEC - EAEC, Brussels-Luxembourg, 1993.
LEGAL NOTICE
Neither the Commission of the European Communities nor any person acting
behalf of then is responsible for the use which might be made of t
following information. Abstract
This report describes the work undertaken in a BCR project1 for the development of Cheby-
shev reference software for the evaluation of coordinate measuring machine data. This work
involved designing algorithms for determining best-fit fundamental geometric elements to
coordinate data. "Best-fit" here refers to the size, shape, location and orientation of the
particular geometric element that are optimal in terms of the Chebyshev criterion applied
to deviations of the data from the element, measured normally to the element. Where ap­
propriate, minimum circumscribed and maximum inscribed elements are also employed. The
software implementations of these algorithms and detailed testing to demonstrate their quality
are described.
'Contract 33J7/1/0/158/89/9-BCR-UK(30) Contents
1 Introduction 1
1.1 Coordinate measuring machines
1.2 Assessment software
1.3 Project objectives
1.4 Benefits 2
1.5 Geometric element assessment
1.5.1 Least squares 3
1.5.2 Chebyshev and other measures
1.6 Adopted approach
1.6.1 Local and global solutions 4
1.6.2 Initial estimation 5
1.7 Previous related work
1.7.1 Testing of CMM geometric form assessment algorithms 5
1.7.2 Parametrisation ofc form 6
1.8 Relationship to standards
1.9 Software
1.10 Documentation 7
1.11 Further information
1.12 Organisation of report
2 Chebyshev best-fit geometric elements by mathematical programming 8
2.1 Introduction 8
2.2 Constrained optimisation theory 10
2.2.1 Notation and discussion
2.2.2 Optimality conditions3
2.2.3 Algorithms4
2.3 An algorithm for the linearly constrained problems5
2.3.1 Algorithm statement
2.3.2 Properties6
2.4 An algorithm for the nonlinearly constrained problems 1
2.4.1 Algorithm statement7
2.4.2 Constructing the working set 18
2.4.3 Degeneracy and the computation of Lagrange multiplier estimates . . 19
2.4.4 Determination of the descent, direction 21
2.4.5n of the descent step4
2.4.6 Properties 25
3 Chebyshev best-fit elements by combinatorial methods
3.1 Introduction
3.2 Classification of best-fit elements and algorithms
3.3 Defining geometric element types7
3.4 A combinatorial method to solve minimum inclusion problems 2
3.4.1 Preliminaries
3.4.2 The general algorithm9
3.4.3 The element specific part of the algorithm 30 3.4.4 Determination of essential subsets 31
3.5 Proving the general algorithm correct
3.6 Efficiency of the algorithm2
Software testing methodology3
4.1 Independent testing and evaluation
4.2 General aspects of testing 34
4.3 Test data5
4.4 Testing specific geometric elements6
4.5 Conclusion
Minimum zone lines8
5.1 Formulation
5.2 Standards and literature review9
5.3 Characterising local and global solutions 40
5.4 Algorithm 41
5.4.1 Overview
5.4.2 The linear-Chebyshev line
5.4.3 The exchange algorithm
5.4.4 The hull-searchm2
5.4.5 Resolving degeneracies
5.4.6 Initialisation
5.5 Software
5.5.1 Function mzSline 4
5.5.2 Complexity3
5.6 Testing
5.6.1 Test data
5.6.2 Independent testing and evaluation5
Minimum circumscribed circles6
6.1 Formulation
6.2 Standards and literature Review
6.3 Characterising local and global solutions 47
6.4 Algorithm 49
6.4.1 Overview
6.4.2 Resolving degeneracies
6.4.3 Initialisation
6.5 Software
6.5.1 Function mincxcrc.
6.5.2 Complexity 51
6.6 Testing
6.6.1 Test data
6.6.2 Independent testing and evaluation7 Maximum inscribed circles 53
7.1 Formulation
7.2 Standards and literature review
7.3 Characterising local solutions4
7.4 Algorithm5
7.4.1 Overview
7.4.2 Resolving degeneracies
7.4.3 Initialisation
7.5 Software : : ~ 5
7.5.1 Function maxincrc
7.5.2 Complexity 56
7.6 Testing7
7.6.1 Testdata
7.6.2 Independent testing and evaluation
8 Minimum zone circles9
8.1 Formulation
8.2 Standards and literature review
8.3 Characterising local solutions 60
8.4 Algorithm2
8.4.1 Overview
8.4.2 Resolving degeneracies
8.4.3 Initialisation
8.5 Software
8.5.1 Function minzncrc
8.5.2 Complexity4
8.6 Testing 6
8.6.1 Test data
8.6.2 Independent testing and evaluation 65
9 Minimum zone planes6
9.1 Formulation
9.2 Standards and literature review7
9.3 Algorithm8
9.3.1 Parametrisation
9.3.2 Procedure greyhound 6
9.4 Software9
9.5 Testing
9.5.1 Test data
9.5.2 Independent testing and evaluation 70
10 Minimum circumscribed spheres1
10.1 Formulation 7
10.2 Standards and literature review
10.3 Characterising local and global solutions
10.4 Algorithm4
10.4.1 Overview10.4.2 Resolving degeneracies 74
10.4.3 Initialisation
10.5 Software
10.5.1 Function minexspk
10.5.2 Complexity6
10.6 Testing 7
10.6.1 Test data
10.6.2 Independent testing and evaluation
11 Maximum inscribed spheres7
11.1 Formulation
11.2 Standards and literature review
11.3 Characterising local solutions8
11.4 Algorithm9
11.4.1 Overview
11.4.2 Resolving degeneracies 7
11.4.3 Initialisation
11.5 Software
11.5.1 Function maxinsph
11.5.2 Initialisation 81
11.5.3 Complexity2
11.6 Testing
11.6.1 Test data
11.6.2 Independent testing and evaluation
12 Minimum zone spheres5
12.1 Formulation
12.2 Standards and literature review
12.3 Algorithm6
12.3.1 Parametrisation 8
12.3.2 Procedure greyhound
12.1 Software7
12.5 Testing
12.5.1 Test data
12.5.2 Independent testing and evaluation 88
13 Chebyshev line (3D) 89
14 Minimum circumscribed cylinders 90
11.1 Formulation
14.2 Standards and literature review1
14.3 Algorithm 9
14.3.1 Overview
14.3.2 Initialisation
14.3.3 Inner iteration: MC circle in the projection plane 92
14.3.4 Outer: optimising the axis direction3
14.4 Software