The complex shapes with tight tolerances which are increasingly adopted in industrial applications make it become a great challenge for geometrical product specification to control the geometrical variations along the product lifecycle. Significant efforts are being devoted to develop systems that can support geometrical product specifications. Among them, GeoSpelling [Ballu 95] [Mathieu 03] is a classical one, which has already standardized as ISO 17450-2005. This thesis investigates on the achievement of GeoSpelling system for geometrical product specification from two aspects: discrete geometry processing supported for GeoSpelling and skin model simulation.

GeoSpelling is proposed as a coherent and complete model to manage the geometrical variations along the product lifecycle. GeoSpelling is based on six geometrical operations to handle both ideal and non-ideal features. The discrete representations of features are first introduced and a new framework is developed to implement the operationalization of GeoSpelling based on discrete geometry processing techniques.

The Skin model, a non ideal feature, is a kernel concept of GeoSpelling. Robust discrete shape modeling methods for skin model simulation are the main concern of this work. The proposed simulation of the skin model is composed of nominal model, random deviations and systematic deviations. Different methods are developed to add random and systematic deviations to the nominal model.

Random errors are statistic fluctuations in either direction and typically obeyed to Gaussian distribution. Three methods are developed to simulate the skin model considering the random deviations: 1-D Gaussian based method, multi-Gaussian based method and Gibbs based method. The specified associated tolerances are used as constrains to locate the simulated skin model within the specified tolerance zone. A comparative analysis of the developed three methods is discussed Comparing to random errors, systematic errors are reproducible inaccuracies that are consistently in the same directions. They usually keep similar values or follow some specific functions which can be calculated or simulated. A group of second order shapes are used as constraints for systematic deviations' generation. The complete skin model can be generated by adding random and systematic deviations. A method based on statistic shape models is proposed for skin model analysis and trend prediction.

The above methods have been implemented in a new computerized system. An application with a detailed case study is discussed. The simulated skin model by the proposed methods is compared to the measured data and the simulated results by another FEA-based method. The comparative results testify that our methods can provide a satisfying performance.

Figures

With the economy globalization, complex shapes are increasingly adopted to improve company's competition. Product is desired to be machined as accurate as possible to match its functional requirements. However, the more accurate it is manufactured, the more cost it will take both time and money. Therefore, geometric tolerances are designed to make a compromise between the functional requirements and production cost during the design phase. Geometrical variations are inevitably generated during the manufacturing stage because of the accuracy of applied machining methods, machining tools, etc. variations also generate during the measurement stage considering the measurement uncertainty always exists. How to design the geometric tolerance to control the geometrical variations is a critical issue in geometrical product specification (GPS). Some Computer Aided Tolerancing platforms have already developed to assist geometrical tolerancing process [Salmon 96] [ Ballu 03]. However, the techniques for computational-supported geometrical product specification haven't solved.

It is necessary to manage geometric variations and to share a coherent and complete tolerancing process along the product live cycle [Mathieu 05]. According to Mathieu and Ballu [Mathieu 05], Geometrical tolerancing process can be synthesized into four main tasks: tolerance specification, tolerance analysis, and tolerance synthesis and tolerance verification. They proposed a proper solution called

Geospelling to cover these four stages for coherent and complete tolerancing process, which has already standardized as ISO17450. GeoSpelling is based on geometrical operations and is able to describe both ideal and non-ideal geometric features [Mathieu 05]. However, till now, GeoSpelling is only a "paper-based" concept and realized with computer. There is no GeoSpelling-based CAT (Computer-Aided Tolerancing) system developed to optimize tolerancing process. It is thus very useful to research and find proper solutions to develop GeoSpelling-based system with computer and the advantages of GeoSpelling can then be completely fulfilled.

In this dissertation, we investigate the solutions to develop the GeoSpelling system for Geometrical Product Specification (GPS). Solutions are proposed based on discrete shape modeling and statistic analysis for skin model simulation and applications.

GeoSpelling, as an ISO standardized representation of geometrical tolerances, proposes a coherent and complete representation scheme to manage the geometrical Skin model is a kernel concept in GeoSpelling, which acts as an approximation of the actual shapes of real products. To simulate and shape the skin models is a fundamental task for GeoSpelling based tolerancing systems. An appropriate skin model is also the basis for the implementations of the 6 operations for geometry processing in GeoSpelling.

Geometrical variations may come from random errors (e.g. random errors in manufacturing and inspection) and from systematic errors (e.g. the imperfect performances of the applied instruments for manufacturing). In order to simulate and represent the actual shapes of real products, both of them should be considered for skin model simulation and shaping. It is necessary to develop methods to analyze the skin models, to predict the trend of real shapes, to guide the geometrical production specification in applications.

Contributions

The objective of the thesis is to enhance the digital processing capability of GeoSpelling model using discrete geometry technique. The main contributions of the thesis are:

A new framework for geometrical operationalization of GeoSpelling based on association between discrete geometry and GeoSpelling.

A comparative analysis of common-used discrete normal estimation methods.

Three different methods to simulate the skin model by adding the random deviations in different ways.

Set of methods to simulate the skin model considering systematic errors.

A method to generate statistical shape model for skin model analysis and trend prediction.

A developed software framework for discrete geometry processing especially for the skin model simulation.

Outline

The thesis is organized as follows:

Chapter 1 introduces the tolerance process especially focus on the tolerance representation techniques, and the shape modeling approaches are also presented.

Chapter 2 presents the association between GeoSpelling and discrete geometry.

Both of the characteristics of GeoSpelling and discrete geometry are introduced. The method to associate them together is discussed for GeoSpelling operationalization based on discrete geometry techniques.

Chapter 3 presents the developed three methods of skin model simulation considering the random errors: 1-D Gaussian-based, multi-Gaussian-based, and Gibbs-based. The methods to generate the skin models considering specified tolerances are presented. A comparative analysis of the three methods is discussed.

Chapter 4 presents methods to simulate the skin models with systematic errors. A group of predefined parametric second order shapes are implemented to constraint the systematic deviations. A method to compute the statistical shape model of a set of training skin models is developed for skin model analysis and trend prediction.

Chapter 5 presents a detailed case study of an industrial workpiece which is a cross-shaped model. The developed software, which serves as the test platform for the algorithms developed in this thesis. The detailed processing results of the studied workpiece are presented. The comparative analysis between the simulation models and the measurement models is discussed.

In conclusion, we summarize the thesis and propose some promising directions for the future research.

Chapter 1 Geometrical Variations within the Whole

Product Lifecycle

Introduction

In modern production engineering, complex shapes with tight tolerances are increasingly adopted to improve the products' competition. Geometrical variations are inevitably generated during the manufacturing stage due to the limited accuracy of applied machining methods, machining tools, etc. Variations also generate during the measurement stage considering the measurement uncertainty always exists. The complex shapes with high quality requirements make it as a great challenge for tolerancing process and geometrical variations' control.

Within the context of Product Lifecycle Management (PLM), the information

Tolerance modeling

Tolerancing process

In automotive, aerospace and other industrial applications, the management of geometrical variation has become an important issue in product design, concurrent

Tolerance model

The tolerance model scheme in current CAD/CAM systems includes two research domains: tolerance modeling and tolerance representation. The first one is used to establish the mathematical expression of tolerance specification, and the latter one focus on how the express the tolerance specification in computerization context.

This section provides a survey on tolerance model technique based on this classification.

(1). Tolerance modeling technique

The difficulty in translating the information language (customer level) into a formal language (industrial level) through a mathematic model of geometric deviations is well known. When the designer cannot interpret the shape variations model in mathematic expression, the annotation writing manner is adopted even it is difficult for the metrologist to measure. Some efforts on this topic are discussed as follow.

Hillyard and Braid [Hillyard 78] developed the concept of variational geometry that is a dimension-driven, constraint-based technique. This approach adopts constraint equation to reflect the tolerance information. In this approach, the solid objects are deemed as the physical frames. At the initial state, the physical frame is linked incompactly by each part. The notes and the connecting bars of the physical frames are the corresponding points and edges of the solid objects. Accordingly, the dimension information of the objects is the fixed constraint of the physical frame, while the tolerance information is the minor changes of constraints. Therefore, the dimension tolerance can be reflected by the displacement of parameter vectors, which are derived from the physical frame model. For the orientation and position variation of the object, each point of the surface should be parameterized thereby infinite dimension vectors are need to express the variation and this is impossible for calculation. Thus, his approach can reflect the dimension tolerance well but it can not deal with the geometric tolerance information.

Another early example of previous work of tolerance modeling technique is the solids offset approach proposed by Requicha [Requicha 83], and its improvement in [Requicha 84] [Requicha 86]. In this method, the tolerance zones of the objects are obtained by "offsetting" the nominal boundaries. Conventional tolerances are considered as a special case of geometric tolerances, and no attempt is made to characterize the nominal geometry using dimensions. This approach considers both ideal and non-ideal features to respect the specification when its boundary is within tolerance zones. The solids offset method differs from the tolerancing standards, since the individual pairs of offset surface are combined to obtain a composite tolerance zone of the entire solid and the individual tolerances cease to be independent constraints [Salomons 96].

Based on the solids offset approach, Jayaraman [Jayaraman 89] and Srinivasan Considering both the solids offset approach [Requicha 83] and the virtual boundary requirements [ Srinivasan 89] approach provide a strict tolerance constraint.

Based on solids offset approach, Etesmi [Etesmi 93] formalize the solids offset model, and proposed using Tolerance Specification Language (TSL) to describe tolerance constraints. At the same time he discussed some practical implementation cases.

Hoffman [Hoffman 82] proposed using point vector to express the tolerance requirements in three-dimensional Euclidean space. The principle of this approach is that the geometrical images are deemed as a set of point vectors and thus the tolerance requirements are converted to the tolerance function, in which the parameters are the point vectors. The tolerance requirements can be explained by an inequation ( ) L f x U , where x is the parameter, f is the tolerance function, and L , U is the limitation of the tolerance zone.

Based on Hoffman approach, Turner [Turner 87] proposed a higher degree polynomial function to model form tolerance for the nominal planar part feature. In this approach, the independent geometric variables defined as the basic vectors of the vector space. This feasibility space approach is not suitable for three-dimension tolerance representation because of a too high complexity and doubtful used fullness in three-dimension space. Based on the higher degree polynomial approach, Turner and Wozny [Turner 87] proposed to model straightness tolerance by breaking up the boundary line with additional vertices. The number of these interior vertices determines the form variation frequencies of the boundary line. Later, Gupta and Turner [Turner 87] proposed to break a planar surface into triangular patches and fit Bezier triangles to each patch. In this approach, the boundary segment is represented by a curved surface (in two-dimension), which is more natural than the straight line (in one-dimension) used in previous approach.

Wirtz [Wirtz 93] proposed another approach based on vectorial theory. In this approach, the tolerance is represented as a limit constraint on the elements of a vector, which has a correspondence between the toleranced feature and the reference feature.

This approach also has the limitations that it is not close to the standards and is oriented too much towards older dimensioning and tolerancing practices, for example, it can not deal with the form tolerances specification problems.

Roy [Roy 98a] [Roy 99] presented a mathematical scheme for interpreting dimensional and geometric tolerances for polyhedral parts in a solid modeler. Using the interrelated surface-based variational modeling technique, the geometric tolerance specifications have been interpreted as sets of algebraic constraints that define tolerance zones for model variables. The main object of this approach is to define the resultant tolerance zones of a part (from its tolerance specifications) in terms of appropriate sets of algebraic relations. Each face of the part is described by these model variables and those variables are ultimately constrained by the algebraic relations. This approach considers both the issues of initial tolerance zone formation and final representation of the variant boundary surfaces. Based on this approach, Tech [Tech 01] studied the modeling method of tolerance zone of planar shapes, and applied it to the tolerance analysis process.

Wang and Pramanik [Wang 06] proposed a method that can convert tolerance specifications as per maximum material condition (MMC)/least material condition (LMC)/regardless of feature size (RFS) material conditions for standard mating features (such as: planar, cylindrical, spherical) into a set of inequalities in a deviation space. The constant boundary generated by the collective effects of a size feature's specified MMC or LMC material condition and the geometric tolerance for the material condition. The principle of this approach is that the variations of size or shape could be thought of as deviations of a set of generalized coordinates defined at some convenient point on a feature, and any tolerance specification for a feature imposed kinds of restrictions on its deviation parameters. This approach is also used for tolerance synthesis and analysis process.

Shah [Shah 98] proposed a dimension and geometric model, which is based on the relative degrees of freedom of geometric entities: feature axes, edges, faces and features-of-size. In this approach, the dimension graphs are created based on the degrees of freedom for each control direction, and the datum reference frames and the standard tolerance classes are incorporated into the graph. This approach allows dimension specification, dimension scheme modification, and dimension scheme validation. The principle of this approach is that the deviations of the toleranced features follow the direction of the freedoms of the features, thus the deviations can reflect the semantics of the tolerance. Later, Davidson, Mujezinovic and Shah proposed T-MAP [Davidson 02] based on the Shah approach. In T-MAP approach, the variations of the toleranced features are reflected by the volumes of the point sets.

Combining Minkowski calculation to the T-MAP approach, the accumulative calculation of the tolerance zones can be obtained.

The concept of the Small Displacement Torsor (SDT) has been developed by Bourdet and Clement [Bourdet 87] in order to solve the general problem of the fit of a geometrical surface model to a set of points using rigid body movements [ElMaraghy 05]. The great advantage of the torsors for the displacement modelisation is due to the fact that the set of torsors is a vectorial space. The composition of small displacements is obtained by a sum of torsors. This operation is commutative and simple to compute, while the composition of two displacements in the general case (great displacements) is a non commutative operation [Bourdet 96]. For their operations of tolerance transfer, the deviations have to be composed. The sum of torsors allows modelising these operations [ Giordano 07].

For an effective integration of CAD and CAM, the tolerance specifications should be taken into account in the context of computerization procedure. How to express the tolerance information in the computer point of view is an important topic. Some contributions on this topic are discussed below.

(2). Tolerance representation technique

According to the relationship with the solid modeling technique, the tolerance representation techniques are divided into solid modeling dependent tolerance representation method and solid modeling independent tolerance representation method [ Xu 08]. The first one is an attribute model, since it provides an object-oriented programming environment in which specifications of each part, such as tolerances, functional requirements, cost function, machining process, have been treated as classes with their attributes [Roy 98b]. The attribute models can be classified into: CSG based method, the B-Rep based method and the hybrid CSG/B-Rep method. While the other models can be divided into: TTRS, tolerance primitive, UML based method and GeoSpelling, etc. The system does not use the B-rep for direct access to these NFaces. An indexing scheme for the faces of each instance of the primitive solids is consistently adopted in the system for the proper identification of any requirement.

As the handling of dimensions and tolerances in the general case requires the ability to access the bounded entities of objects, the CSG-based tolerance theory of Requicha raises some manipulation problems during implementation [Roy 90]. The principal disadvantage of CSG based approach is that all non primitive faces derived from the same primitive face receive the same variations.

(c) Hybrid CSG/B-Rep model.

The tolerance representation is feature-based, and these geometric features can be classified lower-level features (such as points, lines, arcs and surfaces) and higher-level features (such as holes, slots, pockets or other complex features).

Lower-level features are basic topological entities, and the higher-level features are combinations of the lower-level features. Based on the investigation that the features information must be extracted from the solid model, Roy and Liu [Roy 88] proposed a hybrid CSG/B-Rep data structure for the tolerance representation (see figure 1234). This approach can integrate the advantages both CSG and B-Rep models. Figure 1234shows how the specified tolerance information integrated into the hybrid CSG/B-Rep modeler by the reference face list, which is the ligament between CSG and B-Rep data structure.

Gossard [Gossard 88] proposed a similar feature-based design system, which uses B-Rep solid model and combines GSG representational scheme. This approach can be employed on a polyhedral solid model, but it is limited to the conventional tolerance representation only. proved that seven basic surface types can construct the complex objects. These basic surface types are: spherical surface, planar surface, cylinder surface, helical surface, rotational surface, prismatic surface and the any surface. To combine these 7 surface types, 28 cases of combinations can be obtained, and these combinations are named TTRS (Technologically and Topologically Related Surfaces). This method employs the reclassifications of TTRS to denote the different tolerance cases, and the relationship between MGDE (Minimum Geometric Datum Element) and the basic surfaces is shown in table1-1. Indeed, it allows express the specification from the function to the verification with a common language. This model is based on geometrical operations which are applied not only to ideal features, defined by the geometrical modelers in a CAD system, but also to the non-ideal features which represent a real part. These operations are themselves defined by constraints on the form and relative characteristics of the features. GeoSpelling is proved to be a unique specification model used in the global product lifecycle in mathematical and theoretical view [Ballu 95]. The details of Geospelling model is presented in section 2.2.

Shape modeling

Shape is any multi-dimensional media that is primarily characterized by form or spatial extent in a space of two, three or higher dimension [ Biasotti 08]. Considering that shape records all the geometrical information that remains when location, scale and rotational effects are filtered out from an object [Kendall 84], it is an important information media and focal resource in many scientific and applied scenarios: mechanical engineering, computer graphics and vision, biological and medical applications, etc.

According to Requicha [Requicha 89], a shape model is a computational structure that captures the spatial aspects of the objects of interest for an application.

Requicha's work which shaped the whole geometric modeling field introduces four levels of abstraction, called universes. The first level is used to clarify the problem from the point of view of the universe to be modeled, (the physical universe); the second level is used to analyze the problem from the mathematical point of view (the mathematical model); the third allows to understand the various issues of discretizing the elements from the mathematical universe (the representation or computational model); and the fourth is used to map the discretized elements from the representation universe into the structures of a computer language (implementation model)

[ Robbiano 10].

In mechanical engineering, shape modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional geometric shapes and/or solids. It covers the domains as geometric shape design, shape representation, shape analysis and etc. The computer representation of shapes which provides the foundations for other issues are the basis for shape modeling.

In this section, three issues are discussed for shape modeling: shape structural expression, shape representation scheme and shape description.

Shape structural expression

Shape represents 3D object using a collection of various geometric entities in 3D space, such as points, triangles, curves, surfaces, etc. According to their appearance, shape structural expression can be divided into three categories: point-based, surface/shell-based and volume-based. Point-based data are usually created by 3D scanners. In metrology/inspection purpose, the acquired point data can be used directly to compare with the CAD model, but, more commonly, they themselves are not direct usable in many applications and therefore are converted to polygon or triangle mesh models, NURBS surface models, or CAD models through a process commonly referred to as surface reconstruction.

(

2). Surface/shell-based

These models represent the surface, e.g. the boundary of the object, not its volume (like an infinitesimally thin eggshell). Because the appearance of an object depends largely on the exterior of the object, surface representations are common in computer graphics. Two dimensional surfaces are a good analogy for the objects used in graphics, though quite often these objects are non-manifold. For discrete surface, a discrete digital approximation is required since surface is not finite. Polygonal meshes (and to a less extent subdivision surfaces) are by far the most common representation

(3). Volume-based

These models define the volume of the object they represent (like a rock). These are more realistic, but more difficult to build. The material characters, like mass, elastic modulus, etc. can be specified for a volume-based shape. Volume-based models are mostly used for non-visual simulations such as medical and engineering simulations, for CAD and specialized visual applications. Recently, Computer-Tomography (CT) technology is increasingly applied in dimensional metrology, which acquires volumetric point clouds, the volume-based shape modeling is becoming more and more popular.

Shape representation

Representations of shape or geometry have a very strong connection to mathematics. These include Set Theory, Graph Theory, Algebraic Topology, etc., in addition to the various varieties of shape/geometry: projective, analytic, algebraic, differential, and combinatorial [Naylor 96]. Based on the mathematical foundations, a shape representation scheme can be defined as a mapping from a computer structure to a well-defined mathematical model which defines the notion of the physical object in terms of computable mathematical properties and is independent of any particular representation scheme [ Shapird 01]. For mechanical engineering applications, we focus on the different methods or schemes to represent shapes in computer, the details about the mathematical model can be referred to [ Biasotti 08] [ Shapird 01].

Considering various kinds and properties of shapes, many representation methods are developed, and the same shape may also be represented by different schemes. The modeling space of any representation methods is finite, and any single representation scheme may not completely suffice to represent all types of solids. Therefore, the most suitable representation methods should be considered for a specific shape.

In this thesis, the shape representation schemes are classified by their principles and used data structures but organized according to their suitable applications. Any single pure representation in its pure form will be limited in the range of operations for which it is ideally suited [Naylor 96]. It is interesting and useful to identify their suitable applications considering the shape properties. The considering shape properties include shape type (discrete or continuous) and their structural expression (point-based, surface/shell-based or volume-based). Figure1-7 presents a general taxonomy of categories of shape representation schemes for this purpose.

For each category, only several representative schemes are presented. Not all representation schemes used today are presented in this classification. In the following, some of the widely used schemes are discussed in further details.

(1). CSG (Constructive Solid Geometry)

Constructive solid geometry (CSG) is a technique used in solid modeling.

Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine primitive objects. CSG is often used in CAD and 3D computer graphics for procedural modeling. It can also be performed on Polygon mesh based models.

In CSG, The simplest solid objects used for the representation are called primitives. Typically they are the objects of simple shape: cuboids, cylinders, prisms, pyramids, spheres, cones. It is said that an object is constructed from primitives by means of allowable operations, which are typically Boolean operations on sets: union, (

2). B-rep (Boundary representation)

Boundary representation is a method for representing shapes using the limits. A shape/solid is represented as a collection of connected surface elements, the boundary between solid and non-solid. A B-rep shape model is composed two parts: topology and geometry. The main topological items include faces, edges, vertices and the geometrical items are surface, curves and points. A face is a bounded portion of a surface; the bounding curves of a face are represented as edges. An edge is a bounded piece of a curve; the portion curve that forms the edge is represented by two vertices.

A vertex lies at a point. A simple example of B-rep shape using 6 faces is given in figure1-9. The 3D mesh, also called volumetric mesh, which not only represents the surface, but also represent the volume information, is also used in some application, but this is out of this thesis's content.

(4). Voxel-based representation

A voxel is a volume element, representing a value on a regular grid in three-dimensional space. This is analogous to a pixel, which represents 2D image data.

As with pixels in a bitmap, voxels themselves do not typically have their position (

5). F-rep (Function representation)

F-rep [Pascal 04] was introduced in "Function representation in geometric modeling: concepts, implementation and applications" as a uniform representation of multidimensional geometric objects (shapes). F-rep defines a geometric object by a single real continuous function of point coordinates as formula 1-1

( ) 0 F X (1-1) 1 2 ( , ,..., ) n X x x
x is a point in n E , and F is the defining function defined on space n E . The above inequality defines a closed n-dimensional object in En space with the following characteristics:

( ) 0 F X
for points inside the object;

( ) 0 F X for points on the object's boundary;

( ) 0 F X for points outside the object.

F-rep combines many different models like algebraic surfaces, skeleton based implicit surfaces, set-theoretic solids or CSG, sweeps, volumetric objects, parametric models, procedural models, etc. the main features of F-rep are:

(a) Defining function evaluation procedures traversing the constructive tree structure.

(b) Leaves of the constructive tree are primitives with known types of defining functions.

(c) Nodes of the tree contain operations and relations.

(d) Extensibility of primitives, operations, and relation.

(6). Parametric representation

Parametric representation is the most general way to specify a surface. A parametric surface is defined by a parametric form with two parameters in the Euclidean space 3 R . The two parameters are often labeled as u and v . The parameterization of a surface can then be formed as a vector valued function as

formula 1-2 r( , ) s u v (1-2)
The regular surfaces, such as sphere, cylinder, parabolic, hyperboloid, etc. their parametric form are quite known. Take the spherical surface for example, which has the parametric formula 1-3 sin( ) cos( ) sin( ) sin( ) cos( )

x r u v y r u v z r u (1-3) Where, [0, ] u and [0, 2 ] v .
In general, for 3D freeform surface representation, The Bezier surface, B-Spline and NURBS (Non-Uniform Rational B-Spline) surfaces are the most commonly implemented techniques in CAD and computer graphics applications. Take NURBS surface which is the most popular techniques in CAD for parametric surface modeling for example, the parametric form can be represented as formula 1-

p q i m j n i j i j i j p q i m j n i j i j B u B v P w u v B u B v w (1-4) 4 , , , , 0 0 , , , 0 0 ( ) ( ) S( , ) ( ) ( )
Where, , i j P is a control point, and , i j w is the weight being associated to it.

, ( ) i m B u and , ( )

j n
B v are the basis functions along u , v directions respectively, and they have similar recursive definitions. The definition of , ( )

i m B u is decribed by formula 1-5 1 ,0 , 1 , , 1 1, 1 1 1 1 ( ) ( 0) 0 ( ) ( ) ( ) ( ) i i i i m i i k i k i k i k i k i i k i u u u B u m else B u u u u u B u B u B u else u u u u (1-5) , ( ) i m
B u and , ( )

j n
B v can also be expressed through a polynomial for convenient derivatives calculation. , for well-behaved functions f , this defined surface is indeed a manifold surface. A simple example is given as the implicit representation of a sphere as formula 1-7

2 2 2 2 ( , , ) 0 f x y z x y z R (1-7)
One of the most important properties of implicit representation is that connectivity dose not need to be determined for the discretization. A uniform Cartesian grid can be used along with straightforward generalizations of the technology from two spatial dimensions. Possibly the most powerful aspect of implicit surface is that it is straightforward to go from two spatial dimensions to three spatial dimensions.

Implicit interface representations include some very powerful geometric tools.

For example, since we have designated the ( ) 0 f p iso-contour as the interface.

We can determine which side of the interface a point is on simply by looking at the local sign of ( ) f p . ( ) 0 f p indicates the point is inside the interface while Shape descriptors which simplify the shape representations but carry most of the important information and easier to handle are used to describe shapes. Various descriptors are designed for shape description, including shape signature, signature histogram, shape invariants (e.g. curvature), moments, shape context, shape matrix spectral features, etc. [Zhang 04a]. In this section, the shape descriptors we consider are of two types: TTRS (see section 1.2) and curvature based shape descriptors.

Moments are used to transform a shape into a set of features or 1D function and carry invariant properties with respect to some group of spatial transformation. They are robust in shape identification and shape comparison tasks [ Taron 07].

Curvature is a shape invariant parameter and has been classically used as a shape descriptor. Curvature is one of the most critical differential characters of a shape (both continuous and discrete). There are many curvature-based descriptors, such as the principal curvatures, Gaussian curvature, Mean curvature, shape index, curvedness, etc. Typically, three or four numbers of curvature are sufficient to characterize the shape for an infinitesimally small region [Zhang 04a].

Curvatures are defined to measure the local bending of the surface. Take a given point p for example, for each unit direction u on its tangent plane ( ) T p , the normal curvature ( ) n u is defined as the curvature of the curve that belongs to both the surface itself and a perpendicular plane containing both ( ) n p and u . Formally, the normal curvature is defined by formula 1-8 [Oneill 97]:

( ) ( ) n p u S u u (1-8)
Where, ( ) p S u denotes the shape operator at point p along the direction u .

The shape operator which is also known as Weingarten endomorphism is defined as the derivate of ( ) n p with the tangent direction u . Mathematically, it's defined as formula 1-9:

( ) ( ) p u S u n p (1-9)
Where, ( ) u n p indicates the gradients of ( ) n p along u at point p .

The shape operator can be shown to be symmetric. The eigenvalues and eigenvectors of the shape operator are respectively called the principal curvatures and the principal directions. In other words, both the principal curvatures and the principal directions can be recovered from the shape operator matrix. The principal curvatures can also be derived directly from the Gaussian and Mean curvatures which can computed directly based on the first and second fundamental forms of surface.

For discrete shape, the discrete shape operator can be constructed based on the neighbor information of a given point and the principal curvatures can then be approximated (see figure 1 Some important curvatures can be represented as formula 1-10 to formula 1-13:

2 1 K (1-10) ) ( 2 1 2 1 M (1-11) 1 2 1 2 1 2 2 arctan( ) ( ) s (1-12) 2 2 1 2 2 c (1-13)
Where, K indicates Gaussian curvature which is an intrinsic measure of

Conclusion

A coherent and complete tolerancing process is necessary to control the geometrical variations along the whole product lifecycle. This chapter surveys the techniques for geometrical variation management within product lifecycle.

Firstly, the tolerance modeling methods which are common-used in CAT and Geometrical product specification are reviewed considering the tolerance specifications and representations.

Secondly, the shape modeling techniques are introduced considering three issues:

shape structural expressions, shape representations and shape descriptions. The different representation methods are discussed according their principles. The mapping relationship between shape structural expressions and representations are constructed. Discrete shape modeling is highlight for the further processing of geometrical variations.

In the Chapter 2, we will derive the main characteristics of discrete geometry and Geospelling in order to provide a new framework for the operationalization of

Geospelling. The Skin model or non-ideal geometry will benefit from our studies as described in Chapter 3 and Chapter 4.

Chapter 2

A Discrete Geometry Framework for GeoSpelling

Introduction

GeoSpelling is proposed as a coherent and complete model to manage the geometrical variations along product lifecycle. GeoSpelling is defined based on geometrical operations to handle both ideal (e.g. CAD model) and non-ideal (real part) This chapter is organized as follow:

Section 2.2 presents the characteristic concepts and geometrical operations of GeoSpelling. Section 2.3 introduces the basic principles of discrete geometry. Section 2.4 discusses the new framework for operationalization of GeoSpelling using discrete geometry methods. Section 2.5 is a case study and 2.6 is the conclusion.

GeoSpelling

GeoSpelling is a geometrical specifications model proposed by Mathieu and Ballu in 1990s. This model is designed as a mean of communication, in which designers, manufacturers and metrologists exchange product geometrical information concerning the function requirements of products unambiguously. GeoSpelling that has been adopted by ISO TC 213 experts can describe both ideal and non-ideal geometrical features, and it allows expressing th94e geometrical specification from the function to the verification with a common language [ Mathieu 07]. While, as the actual GeoSpelling has not been defined completely, it can not be fully integrated in CAD/CAM/PLM chain directly. The objective of improving the actual GeoSpelling is to enhance its computational capability. In this chapter, t discrete geometry concepts and methods are discussed in the context of GeoSpelling. Discrete geometry mainly focuses on discrete geometrical objects (such as point and mesh), and it also has a large overlap with computational geometry and discrete differential geometry. These characteristics of discrete geometry could provide a consistent and rigorous framework for enhancing digital processing capability of GeoSpelling. GeoSpelling model is defined by the following concepts.

Specification

Geometrical Features

In GeoSpelling, the features are classified into three categories: ideal features, non-ideal features and limited features. Today the definitions of these features are roughly described as follow.

Let us consider ideal features such as a plane of the nominal model of the part or a cylinder fitted to a real feature nominally cylindrical. In the first case, the plane of the nominal model is a nominal feature; while in the second case, the cylinders fitted to real surfaces are fitted features. Therefore, the ideal features can be divided into two classes: nominal features and associated features. The nominal features are those features that completely independent of the real surface of the part and also can constitute the nominal model defined by the CAD systems. The associated features can be obtained by association operation from a skin model. Actually, an ideal feature can be defined by an equation, and they are characterized by their invariance class [Clement 94] and their type.

Non ideal features such as a surface portion of the model of the real surface of a part or a real axis. The non ideal features can not be defined by equations. They depend completely on the real surface of the part.

Operations

The operations are used to obtain geometrical features. They are classified into six categories (figure 2-2).

Characteristics

A characteristic is a parameter of one feature or between two features to express a length or an angle. The characteristics are used to define specifications, and they belong to five families.

(a) Intrinsic characteristic. They are the characteristic of an ideal feature.

(b) Situation characteristic between ideal features. The characteristic defines the relative position between two ideal features.

(c) Situation characteristic between ideal and limited features. The characteristic defines the relative position between an ideal feature and a limited feature.

(d) Situation characteristic between ideal and non ideal features. The characteristic defines the relative position between a non ideal feature and an ideal feature.

(e) Situation characteristic between non ideal features. The characteristic defines the relative position between two non ideal features.

Skin model

Based

Discrete geometry

Along with the development of computer science and information technologies, discrete geometry emerged as a new growing area of research that uses concepts from classical and non-classical geometry, topology, combinatorics, probability theory, computer science and engineering in order to design structures and algorithms for the acquisition, representation, processing and transmission of complex 3D models.

Discrete geometry as a discipline is on the cutting edge of modern applications such as geographic information systems, computer graphics, solid modeling, and computational biology.

Discrete geometry deals with the structure and complexity of discrete geometric objects as well as with the design of efficient computer algorithms for their manipulation. Discrete refers to the fact that the objects of interest are discrete data (point sets, triangle meshes, tetrahedron meshes, etc.) and is used to contrast with "continuous" geometry, for example, smooth surfaces.

Discrete geometry has large overlap with Computational geometry that arose as a new field within the past thirty years. The term "discrete" fit well with the term "computational" as the geometry must be discretized in preparation for computations [Devadoss 11].

In our work we consider that discrete geometry covers both the old topics of discrete geometry and the new issues of computational geometry.

Research themes in discrete geometry cover the geometry processing pipeline that include studying transition mechanisms between physical (real), mathematical (abstract), and discrete (digital) representations of complex shapes [ Botsch 10].

Alliez [Alliez 09] enumerates and structures the related algorithms throughout the following geometry processing pipeline: (c) Reconstruction. The process of shape reconstruction is determining a surface that approximates an unknown shape from samples. This problem is ill-defined since many surfaces approximating the samples can be retrieved. Moreover, the point set can be characterized with variable density as well as noise and outliers due to the acquisition process. The main challenge here is to guarantee that the topology of the original surface is preserved, while sharp features and surface boundaries are The terms "surface fitting" is in reference to two distinct classes of problems [Hoppe 92]: surface reconstruction and function reconstruction. The goal of function reconstruction is to determine a function that "best" approximates a known domain surface. Function reconstruction methods can be used for surface reconstruction in special cases, where the surface to be reconstructed is known such as quadric surfaces [ Zhang 11].

Fitting surfaces to measured data algorithms estimate surface parameters by minimizing the shortest distances between the surface and the measurement points.

There

Discrete geometry and GeoSpelling

GeoSpelling proposed by Ballu and Mathieu [Ballu 95] is used to describe both ideal and non-ideal geometric features. Indeed, it allows the expression of product specifications from function to verification with a common language. This model is based on geometrical operations which are applied not only to ideal features defined by CAD systems, but also to the non-ideal features which can represent a real part.

Geometrical Features

There are two kinds of geometrical features defined in GeoSpelling: ideal features and non ideal features. These two kinds of features are related to the surface models (skin model). The features that are obtained from the nominal surface models defined by the CAD software can be approximately deemed as ideal features, while the non ideal features are derived form the skin model which integrated the imaginations of the real workpiece by the designers. In discrete geometry field, ideal features can be acquired by reconstruction and fitting operations, while ideal features can be describe by discrete geometrical features such as point, segment, polyline, mesh etc.

Operations

Operation defined in [ISO 2005] including partition, extraction, filtration, association, collection and construction. These operations play an important part in Geospelling [ Mathieu 07], so in this section we want to find out the interrelated techniques in discrete geometry.

(

1) . Partition

The operation called partition is used to identify bounded features [ISO 2005]. In Discrete geometry, there are abundant contributions on this area. The majority of partition methods can be classified into three categories: edge-detection methods, region-growing method and hybrid methods [Woo 02].

Edge-detection method can be described that, after identified the boundary points, Based on the hybrid methods, Zhao [Zhao 10] proposed a segmentation method based on shape index and curvedness. This method is based on two assumptions: the initial discrete shapes can be broken down into various components, and these segmented components can be represented by mathematic functions with degree no higher than 3. Based on the shape index and curvedness information, the local surface type can be determined, and the edge points are detected with the high curvature values. After clustering the edge points and merging the local surfaces with the same type, the segmentation result is obtained. The main contribution of this method is that it can recognize and extract the regions surrounded by real defined boundaries, which can be sharp edges, smooth edges, inflexion edges, etc.

To sum up, region-growing methods have less influence by noise than edge-based methods, but it is quite sensitive to threshold and the selection of seed point is also a technical problem. The hybrid methods combining the virtue of edge-based and region-based methods can overcome the two kinds of limitations.

(

2) . Extraction

The (

3) . Filtration

The filtration operation in GPS [ISO 2005] is the operation that used to distinguish between roughness, waviness, structure and form etc. A point comparatively distant to the cluster built by its k-nearest neighbors is likely to be an outlier. This observation leads to this criterion.

For each point p consider the smallest enclosing sphere S around ( ) This criterion is based on the following observation: potential outliers draw their k-nearest neighbors from a larger vicinity than points in a well-sampled environment.

In particular, a valid point sample q may be in the k-nearest neighbor of an outlier, but the outlier will most likely not be part of q's k-nearest neighbors.

( ) ( ) ( ) k uni k uni bi k bi k uni N p N p x p k N p N p (2-4) ( ) ( )
The final outlier classification is computed using weights w1,…,w3,

1 i i w
, interactively defined by the user as formula 2-5

1 2 3 ( ) ( ) ( ) ( ) pl mb bi x p w x p w x p w x p (2-5)
As all outlier criteria are based on the k-nearest neighbor graph, pl x , mb x , and bi x are computed once and cached during the computation of x. The principle of Nearest-neighbor graph method can be describe by figure 2-12. Depicted are the five nearest-neighbor relations for p and its five neighbors q 0 ,…,q 4 , since that only q 2 shares a reciprocal neighbor relationship with p.

(4) . Association

The methods of association defined in GPS can be classified as Least Squares, Minimum Zone, One Side Chebyschev, Maximum inscribed and Minimum

Circumscribed, and all of them can be illuminated by a uniform formula 2-6

1 1 1 [ ( ) ] i n norm n p i p p L n r (2-6)
Where i is the index of point on the non-idea feature, p is the index of the function, n is the number of points of the non-ideal feature, i r is the residuals between non-ideal feature and ideal feature (see figure 2345678910111213).

In discrete geometry, we evaluate the association operation instead of continuous features are discrete ones. Therefore, the three of common used methods of association in discrete geometry will be introduced in this section. There are Least Squares (LS), Weighted Least Squares (WLS) and Moving Least Squares (MLS) [Nealen 92]. The Least Squares method has be adopted in GPS, while the other two are something new.

LS i i i J f x f .
Thus the problem can be described as formula 2-7 2 min ( )

d m i i f i f x f (2-7)
Where f is taken from d m , the space of polynomials of total degree m in d spatial dimensions (see figure 2-14).

d m i i i f i x x f x f (2-8)
Similar to above, only that now the error is weighted by ( ) an algorithm to find samples on the intersection curve and a rendering method that allows the user to display crisp features curves using point primitives.

d
For classification: the goal of the classification stage is to determine which points of 1 P are inside or outside the volume enclosed by the surface 2 S and vice versa. For this purpose a classification predicate p is defined as formula 2-9 1 ( ) 0

p x V x x V (2-9)
WhereV is the volume bounded by the MLS surface S defined by the point cloud P .

Given the classification predicate , the subsets 1 Q and 2 Q can be computed as shown in table 2-1. From all closest pairs (

1 1 q Q , 2 2 q Q
) of these points a new sample q on the intersection curve is computed using a Newton type iteration. This is done as follows:

Let r be the point on the intersection line of the two tangent planes of 1 q and 2 q that is closest to both points (i.e., that minimizes the distance 1 2 r q r q ). The point r is the first approximation of q and can now be projected onto 1 S and 2 S to obtain two new starting points 1 q and 2 q for the iteration. This procedure can be repeated iteratively until the points 1 q and 2 q converge to a point q on the intersection curve (figure 2-18).

Characteristics

In [ISO 2005] characteristics are defined using some instances: ideal features also called intrinsic characteristics, or between ideal features and called situation characteristics, or between ideal and non-ideal features and also called situation characteristics.

Correspondingly, in discrete geometry characteristics maybe can be defined as:

either on ideal features called intrinsic characteristics, or between ideal features called situation characteristics, or between ideal and non-ideal features called situation characteristics, or between non-ideal feature and non-ideal feature and similarly called situation characteristic.

(

1). Intrinsic characteristics of ideal features

The intrinsic characteristics are functions of features, so they are denoted as functions of these features [ISO 2005], and it is the same as in discrete geometry.

(

2). Situation characteristics between ideal features

The definition of ideal feature in discrete geometry has been discussed in section

(3). Situation characteristics between non ideal and ideal features

(4). Situation characteristics between non-ideal and non-ideal features

In GPS, there is not exist this kind of situation characteristics, whereas, in discrete geometry it should be take into account, and these situation characteristics are also only distance. Corresponding to the location characteristic between ideal feature (see table 2-2), the location characteristic between non-ideal and non-ideal feature should be present as table 2-3 and the mathematical notation as table2-4. The most used non-ideal features in discrete geometry are denoted by two letters, see table 2-5. The calculation of each kind of location characteristics between non-ideal and non-ideal features in discrete geometry will be discussed as follow [Schneider 03].

(a) Point to point distance. As we all know, the fundamental to any distance algorithm is the distance between two points, so we will discussed the distance in 3D case firstly. Let two points are 0 1 2 ( , , ) X x x x and 0 1 2 ( , , ) Y y y y . The sketch map and formula are provided, see table 2-6.

Sketch map Formula

2 2 2 2 0 0 1 1 2 2 ( , ) ( ) ( ) ( ) X Y X Y x y x y x y
Note: the square root calculation is much more time consuming than squared one, so all the distance discussed below will be squared calculation. The center triangle labeled 0 is the domain of Q , that is ( , ) s t D . If ( , ) s t is in region 0, the P`, the point on the triangle closest to P, is on the interior of the triangle.

The three dimensional illustration is be provided in figure 2-21. The Q with quadratic function represents as paraboloid, and ( , ) (0, 0) Q s t occurs at , s t in region 0 case. v Q Q is a minimum, and can be rewrite as formula 2-13

Q V 0 Q V 0 Q V
2 0 1 0 1 0 1 0 1 (( ) ) (( ) )) v v v P P sd td P P sd td (2-13)
This is a quadratic function in s and t, that is, it is a function ( , ) f s t whose shape is a paraboloid. For the case of lines, the domain of s and t is unrestricted, and the solution corresponds to the point where f is minimized (that is, the bottom of the paraboloid).

However, if the linear components are both segment, then the domain of s and t is restricted, which can be expressed by 0 1 s and 0 1 t (see figure 2-24).

In general, the global minimum of the quadratic function may not be within the restricted domain. In such case, the minimum will be at some point along one of the boundary edges of the domain. The method to solve this problem is more like the algorithm that classifies the location of ( , )

c c
s t , and then we can determine the closest points and their distance.

Analogous to the approach of categorizing the region in which ( , ) Then the minimum can be calculated as formula 2-19

1 1 0 1 1 d u d d t d d (2-19) If 0 1 t
, then this is the actual solution, otherwise, the actual solution is 1

if 1 t or 0 if 0 t .
In the case of edge 1

t , it has 2 1 0 1 0 ( ) ( ) v u d sd u d sd .
Taking the derivative with respect to s, then the deviation can be calculated as formula 2-20

2 0 0 1 0 2 ( ) d v d u sd d ds (2-20)
Then the minimum can be calculated as formula 2-21

0 1 0 0 0 d u d d s d d (2-21) If 0 1 s
, then this is the actual solution, and otherwise, the actual solution is 1 Distance ( , , ) ( , , ) ( , ) ( )

if 1 s or 0 if 0 s .
u v t Q u v t T u v L t (2-24)
Expanding terms and multiplying, can get formula 2-25 segment and the triangle will be ( , , ) ( ) T u v t L t . Otherwise, the minimum of ( , , ) Q u v t will be on a face separating the regions.

2 2 2 2 0 0 1 1 0 1 0 1 0 1 ( , , ) ( , ) ( ) ( ) ( ) ( ) 2( ) 2( ) 2( ) 2( ( )) 2( ( )) ( ( )) ( ) ( ) Q u v t T u v L
(f) Triangle to triangle distance. The calculation between two triangles must be very complicated, because there are so many possible conditions. In order to obtain the result we can turn this problem into calculate the distance between point and triangle. That means the minimum distance among each point of one triangle to the other triangle is the actual distance between two triangles.

To sum up, the main contribution of this chapter is that we established a mapping relationship between the algorithms existed in discrete geometry domain and the concepts defined in GeoSpelling model. The corresponding relationship is summarized in table2-8. GeoSpelling and each operation needs to rely on it to carry out, the next chapter will discuss how to simulate the skin models.

Conclusion

GeoSpelling provides a coherent and complete model for ideal and non-ideal

Introduction

As gives the comparative analysis of the proposed methods, and section 3.6 is the conclusion.

Basic foundations

The The basic concepts and foundations concerned will be introduced in this chapter.

Discrete representations of the surface model

As discussed above, the skin models are created from nominal CAD models.

This means that our proposed approach considers the CAD model as the reference model (or master model) in the CAD environment. CAD models are typically generated to create a product shape satisfying functional requirements without prior knowledge of their effects on all downstream applications. A CAD system database contains details of the geometry of all features in the model as initially created. In some systems, if a subsequent modification changes the topology of an existing feature, the geometry of the modified feature is also recorded [ Kim 07].

In order to obtain the discrete surface model, a tessellation process to convert CAD models into polyhedral ones is considered here. Normally there are two main categories of this processing integrating the tessellation process into CAD modelers inconsistent topology due to data exchange between different softwares or to the differences of shape requirements between tessellated mesh and CAD models, in such case the tessellation criteria should be taken into account.

In the perspective of a full CAD and downstream applications at the level of integration and interoperability, the polyhedral model tessellated from CAD model directly is adopted in our work. Based on the shape of primitives distributed on a tessellation mesh, the tessellation can be roughly classified into two categories: regular and irregular one. A regular tessellation is a highly symmetric tessellation made up of regular polygons, which are triangles, squares or hexagons. The most common irregular tessellation is composed by Delaunay triangular mesh, in which the size of triangles is different from each other. In our work, we consider both regular and irregular tessellations.

Tessellation techniques

Polyhedral surface approximation

The built-in tessellation algorithm creates a boundary representation that covers the surface of the solid model with triangles, and this mesh data structure is a common way of describing the geometry and the topology of objects in computer graphics.

Generally the mesh data structure is the polygon mesh. A polygon mesh consists of vertices connected to form the faces that in turn form an object. It's known that a proper data structure of polyhedral model is quite important for geometry processing and the data structure of mesh has been studied for a while.

(

1). Mesh data structure

As discussed in A synthetic survey of data representation of meshes can be found in [Kettnert 99]. In our method, the Half-edge method is adopted.

As its name implies, the Half-edge Data Structure (HDS) splits each edge into two oriented half-edges having two opposite directions. The mutual relation between the two half-edges is added for convenient query. A half-edge is thus considered belonging to exactly one triangle. The half-edges of one triangle can be oriented as clockwise or counter-clockwise around the facet.

The half-edge data structure is an extension of the simple polygon mesh. Not only does it contain information of vertices and faces, it also stores information about edges in the mesh, which simplifies analysis of the mesh. An edge is defined as a vertex, a face and three connected edges known as next, prev and pair, see figure 3-1.

Using these connections it is possible to access any other edge on the mesh. (

2). Mesh file formats

The exchange of polyhedral mesh model between different CAD systems and to downstream applications is an important practical requirement for interoperability and integration. Until recently [ Zhao 10] there are many file formats used to store and exchange the mesh data in computer graphics and engineering applications The first line in the ASCII format is a description line that starts with the word "solid" in lower case, followed eventually by additional information as the file name, author, date etc. The last line should be the keyword "endsolid". The file continues with any number of triangles, and each one represented as follows figure 3-2): Thanks to their popularity and their availability on CAD systems and public software, STL and OFF file formats are both used in this work.

Normal vector estimation

The derivation of discrete analogs to differential properties of smooth surfaces has been an active area of research for many years [Petitjean 02] [ Hildebrandt 06] [ Botsch 10]. Two main groups of methods have been developed: fitting and discrete methods. Fitting is a very common approach to estimating local surface properties using a local reconstruction of the surface followed by analytic evaluation on the reconstructed smooth surface patch [ Botsch 10]. Differential geometry is used then and employs methods of differential calculus to describe local properties of smooth curves and surfaces [Carmo 76].

Since triangular meshes are piecewise linear surfaces, the classical concepts of differential geometry cannot be applied directly. The challenge is then to compute approximations of the differential properties of this underlying surface directly from the mesh data. Different approaches have been proposed in recent years [ Zhao 10].

(

1). Neighbor region

Many operations in geometry processing and computer graphics require normal vectors estimation and discrete curvatures computation. A normal vector is a local geometric property of a 3D surface, which is specific to a given point or a planar facet.

Many attempts have already been made for a reliable estimation of normal vectors from point sets.

To calculate the normal vector form a point set, the most common way is to construct a local neighborhood through meshes to obtain the local relationship among each point. In this work, the local averaging region is a one-ring neighborhood as discussed in [ Zhao 10].

Mathematically, a mesh can be described by the couple { , } M V F , where the vertex list is noted as Reliable estimation of the normal vector at a point is much dependent on the identification of its valid neighbor points. Many researchers have used a fixed number of Euclidean nearest neighbor points to estimate the normal vector at the given point [ Zhao 10]. Too many neighbor points may degrade the local characteristics of the normal vector. And too few neighbor points may be not sufficient to evaluate the real local geometry. Moreover, possibly, the number of neighbor should be different for different points in implementation. Here we focus on the approach of vertex estimation instead of the mesh structure.

{ :1 } i V V v i n ,

(2). Vertex normal estimation methods

Given a polyhedral mesh structure (see figure 3-5 (a)), to calculate the point P vertex normal, generally, the neighborhood of point P should be found out (see figure 3-5 (b)). The vertex normal of point P is a weighted average value of the normal of triangles, which compose the neighborhood of point P . In figure 3-5 (b), for the i th triangle, the normal i n can be estimated by its edges, see formula 3-1. Since the vertex normal is a weighted average value of its neighborhood, a number of researches of evaluating the weight coefficient have been proposed. We present here a survey and comparison of these algorithms in order to find out the most suitable methods for our work.

1 2 2 3 3 1 1 2 2 3 3 1 i i i i i i i i i i i i i
(a) Gouraud's method [Gouraud 71].

In this method, the vertex normal ( ) p n is deemed as the average vertex normal of all the triangles, which compose point p 's neighborhood. Mathematically, it can be described by formula 3-2 1 1 ( )

N i i N i i n n p n (3-2) (b) Thumer's method [Thumer 98].
Based on the Gouraud's method, Thumer and Wuthrich proposed a new method which takes into account the influence of the area of triangles. In Thumer's method, the area of triangle is bigger the influence to the vertex normal is greater. The weight coefficient can be calculated by formula3-3. Shen improved Thumer's method by introducing centroid distance into his method. Instead of estimating the influence of triangle's area, the centroid distance is invested. The weight coefficient can be calculated by formula3-4

1 i i N i i A A (3-3) i ( 1,... i N )
1 i i N i i d d (3-4) (d) Zhao's method [Zhao 10].
Given a polyhedral mesh surface, the normal vector at a vertex can be estimated as the weighted average of the normal vectors of the adjacent triangle facets around it.

Considering an arbitrary vertex p in a discrete mesh surface , assuming its neighbor contains N triangles, then the normal vector at p could be estimated using formula 3-5. The method used here for the weight coefficients computation considers the influence of the area of each adjacent triangle facet and the distance between the given vertex and the barycenter of each adjacent facet. Parameter i can be calculated by formula 3-6.

2 2 1 i i i N i i i A d A d (3-6)
Where, (

3). Comparison techniques

In order to test the above methods, three kinds of mesh structure of the unit sphere are discussed, as showed in figure 3

i i i i
v x y z of a sphere, and then its vertex normal i N can be calculated using formula 3-7

( 1)

i i i i i N x y z N i j k (3-7)
In our testing, given the algorithmic and theoretical normals, we estimate the angular cosine discrepancy as formula 3-

8 lg 1 discrepancy a orithmic theoretical d N N (3-8)
The value of the discrepancy at which the fraction is 0, it means that algorithmic and theoretical normals are in the same direction. The value of the discrepancy is big then the difference between the two vertex normals is distinct.

To evaluate the accuracy of each vertex normal algorithm, we performed two different ways to compare these methods based on formula 3-8: one is comparing the vertex normal of marked points called landmark and the other one is comparing the average vertex normal and its standard deviations. Combining the two evaluation methods of vertex normal estimation discussed above, we infer that Shen's method is good at regular mesh structure case while Zhao method is suitable to the irregular mesh structure case. Although Shen's method has the closet value in regular testing experiment, the difference comparing to Zhao method is small. In irregular experiment, the difference between these two methods is also small. In order to use a unique vertex normal estimation method, we adopt Zhao's method in our work. The first method approximates a given mesh by a local quadric surface, and then it applies the first and second derivatives to obtain the curvatures [Meyer 02]. This method is based on surface parameterization and calculates mean curvature and Gaussian curvature using formula 3-9 ( , ) ( ( , ), ( , ), ( , ))

Discrete curvatures

r u v x u v y u v z u v (3-9)
Where ( , ) r u v correspond to semi-geodesic coordinates [Mokhtarian 01],

Gaussian curvature and mean curvature could be derived from formula (3-9) using formula 3-10 and formula 3-11

2 2 2 2 uu vv uv v v v b b b K x y z (3-10) 2 2 2 2 2 2 ( ) 2( ) vv v v v uu v v v b x y z b H x y z (3-11)
Where, K and H represent the Gaussian curvature and mean curvature respectively.

Principal curvatures are then derived as follows (formula 3-12).

2 1 2 2 H H K H H K (3-12)
Where, 1 and 2 are the maximal and the minimal principal curvatures respectively.

The second techniques discretize the mathematical formulas that compute the curvatures of continuous surface and then extend the underlying notions to discrete domains [Srinark 08]. This method begins with the calculations of mean curvature and Gaussian curvature based on the discrete version of the Laplace-Beltrami operator.

Similar to the various discrete versions of the Laplace-Beltrami operator, many methods have been proposed for directly estimating the curvature tensor on polygonal surfaces. The method introduced by Cohen-Steiner and Morvan [Cohen-Morvan 03] has been successfully applied for discrete shape processing. In differential geometry, the shape operator or Weingarten endomorphism [Oneill 97] determines the principal curvatures and the principal directions of a surface. In the case of discrete shapes, the discrete shape operator matrix is estimated at each vertex and then the principal curvatures are derived.

The method proposed by Zhao [Zhao 10] is based on the work reported in [Cohen-Morvan] which has been improved by adding weights to the discrete shape operator matrix and modifying neighbour region.

Considering an arbitrary vertex p on a polyhedral mesh surface , the discrete shape operator matrix at p can be estimated as formula 3-13

1 ( ) ( ) ( ) ( ) T e e E

W B e length e B e e A

(3-13)

Where, B is the local region around the vertex and A is its area. In our case, B is defined based on the Voronoi cell, (figure 3-7 (a)).

e is the coefficient associated with the edge e and is defined as formula 3-14

Skin model simulation

The In our work, we focus mainly on Gaussian distribution. There are three different methods to obtain the Gaussian random distribution numbers [Rubinstein,81] [Taygeta 95] and these methods can be used also in the case of other distributions.

Random simulation techniques

The first method is the inversion method. The basic idea is based on inverse The second method uses the fundamental transformation law of probabilities.

The idea is that the transformation takes random variable from one distribution as

1D-Gaussian method

In probability theory, the Gaussian distribution is a continuous probability distribution that is often used as a first approximation to describe real-valued random variables that tend to cluster around a single mean value. The graph of the associated probability density function is "Bell"-shaped.

The principle of the 1D-Gaussian method can be described in figure 3456789. The "bell" shape reflects the scope of the 1D-Gaussian distribution acting on one point in the direction of the vertex normal. Where is the mean value, 2 is the variance, x is the Gaussian variable.

In our case, in formula 3-17, the mean value is the input points' coordinates, and the variance determines the width of the Gaussian distribution. This method uses the Gaussian variable as the deviation value in the direction of the vertex normal (see section 3.2.1) of CAD model, and then applies this calculation to each point.

The simulation result in figure 3-10 shows the 1D-Gaussian method in the case of a skin model of a plane sampled with 273 points.

Multi-Gaussian method

The multivariate Gaussian random function model is commonly used in physical modeling and geostatistics to model spatial variability. Its distribution is a generalization of the one-dimensional normal distribution to higher dimensions. A random vector is said to be multivariate normally distributed if every linear combination of its components has a univariate normal distribution. The multivariate normal distribution is often used to describe random variables which cluster around a mean value. Suppose that 1D-Gaussian is a verso method, and then the multi-Gaussian would be a recto method. While 1D-Gaussian method is based on the assumption that the corresponding points of the real workpieces could be found out from the CAD model in the vertex normal directionmulti-Gaussian method enables to simulate how the points of a CAD model would distribute after a manufacturing process. The variables generated in a multivariate Gaussian method are constrained by a covariance matrix.

Since multi-Gaussian method generates the random variables directly from the CAD model, independent from the vertex normal estimation, it would be a more reliable and more general method.

In our case, a spatial random vector is defined as

1 2 3 ( , , ) T X X X X .
The probability density function of multivariate Gaussian distribution can be expressed as in formula 3-18.

1 3 1 2 2 1 1 exp( ( ) ( )) 2 (2 ) ( ) T x x f x (3-18)
Where is the covariance matrix, is the determinant value, and is the mean vector.

The principle of this method is described in figure 3 Here is an experiment of this method, when considering a CAD plane composed of 273 points. The simulation result with different views is illustrated in figure 3-12.

Compared to the simulation result of 1D-Gaussian, the random distribution of multi-Gaussian is in three dimensions.

Gibbs method

Gibbs method defined here is used to simulate the multi-Gaussian distribution of random numbers using Markov Chain Monte Carlo (MCMC) methods. MCMC method is an example of Monte Carlo methods, which relies on repeated random sampling to compute their results. Since Monte Carlo simulation methods do not always require truly random numbers, the pseudorandom sequences are enough in most cases [Davenport 92]. Considering that MCMC methods are based on constructing a Markov chain that has the desired distribution and only depends on current state instead of the entire past data, the Gibbs method provides a reliable Gaussian distribution result.

The Gibbs sampling algorithm is used to generate a sequence of samples from the joint probability distribution of two or more random variables. The algorithm is in reference to an analogy between the sampling algorithm and statistical physics. Gibbs method requires an initial value of the parameters. At each iteration each parameter of interest is sampled a given value from the other parameters and data. Once all the parameters of interest are sampled, the nuisance parameters are sampled given the parameters of interest and the observed data. This characteristic of the Gibbs method can make the random distribution of point set of skin models approximates a Gaussian distribution.

When constructing a Markov chain for Gibbs method to obtain a target distribution, the determination of how many steps are needed to converge to the stationary distribution within an acceptable error is an important problem. Since the convergence performance is determined by the iterative times, the probability distribution of the normality assumptions of Gibbs should be considered. The experiment of normal distributions is simulated by Minitab ® software for different iterative runs. In our experiment, we test the interactive time N equal to 100, 1000 and 10000 respectively. The convergent normality distributions are illustrated in figure 3-13, and we can see that the convergent probability of the first two conditions is around 99% and in the third condition can be achieved at 99.9%. Based on [Rouchka 97] Gibbs sampling requires an initial starting value for the parameters.

In Gibbs sampling, a vector of parameters of interest is required, and also a nuisance parameter with observed data , from which a converging distribution can be obtained. Suppose 1 2 ( (0), (0),..., (0)) when i .

In our case, the stationary objective function follows a Gaussian distribution.

Based on Gibbs interactive method, sampling random variables from Gaussian random numbers enables to simulate the skin model as in figure 3-14.

Time performance

To compare the time performance of skin model simulation methods including 1D-Gaussian method, 3D-Gaussian method and Gibbs method, we experiment five different CAD models with different vertex numbers for testing. For each test model, we generate the corresponding skin models using the three different skin model generation methods described above, and the results are illustrated in table 3-3. From table 3-3 we can deduce that the 1D Gaussian method has better performances, followed by the 3D-Gaussian than the Gibbs method. The variation trends of the Gibbs method and the 3D-Gaussian method are illustrated in figure 3-15(a) and figure 3-15(b) which is the magnified trend of the 3D-Gaussian method.

(a) Time performance of the Gibbs method and the 3D-Gaussian method.

(b) Time performance of the of 3D-Gaussian method.

Figure 3-15: Time performance

Adding constraints on skin model

According to the GPS paradigms, the tolerance specifications encode the allowable variation in product geometry, and it should be reflected by the skin model.

The probabilistic interpretation of the clouds of points introduced in section 3.2doesn't take into considerations functional requirements or manufacturing considerations. Figure 3-16 highlights the tolerance types considered in our work, respectively, form specification, orientation specification and position specification.

They are denominated here as constraints. After creating the random point set to simulate the skin model, we also intent to add constraints on it to satisfy the specification requirements.

Form specification

Based on ISO [ISO 2005] standard, the flatness is the condition of a surface having all elements in one plane A flatness tolerance specifies a tolerance zone defined by two parallel planes within which the surface must lie. In discrete geometry view, the flatness tolerance zone limits the points set of the surface within a given bound (see figure3-17).

t The parallelism specification satisfies the constraints in formula 3-22.

( ) ( ) i i parallelism Max M n Min M n t (3-22)
Where n is the normal direction of the datum plane, and i M is an arbitrary point.

The process flow of parallelism tolerance is illustrated in figure 345678910111213141516171819202122. Where n is the normal direction of the datum plane, i M is an arbitrary point, and d is the distance between the point i M to datum plane A P in the direction of vector n , and a is the nominal distance value of position tolerance (true position). The process flow is then illustrated in figure 3-25.

n i M ( , ) [ , ] 2

Other constraints (1). Combining constraints

The constraints on the skin model discussed above are based on the simulation of pure random errors. In general, the realistic part not only contains the random geometrical errors (uncorrelated errors) but also the systematic geometrical errors (correlated errors). In order to ensure that the skin model satisfies both correlated and uncorrelated errors, we propose to improve the constraints discussed before when combined.

Considering that the form specification is independent on any other conditions, it can be constrained first when there are also other tolerance specifications. Since the PCA method can identify the principle axis, the bounding box of the point set is then determined, and the principal directions uncorrelate the data. Systematic geometrical errors thereby can be well described by this bounding box thanks to the position of the centroid and the principal directions orientations through a rigid transformation.

The constraints added on the point set which combine the systematic geometrical errors are the orientation and the position specification requirements. To sum up, the constraints with systematic deviation method can evaluate the constraints combined by form, orientation and position specifications.

The input of this method is a tessellated model obtained from CAD software, and based on the tolerance specification requirement the user input the constraint values, such as form specification, orientation specification, position specification, datum plane, even any combination of these specifications, and also a rotation value that the maximum value can be easily derived from the dimensions and the tolerance zone of the toleranced surface. The rotation value is used to rotate the bounding box of the point set to consider some systematic errors. Based on the input information, the initial random point set i M can be generated by the skin model simulation method, which was introduced in section 3.3. Considering the form specification is independent on datum plane and has always a smaller constraint value than orientation and position specification, we test if the point set is within the form tolerance zone first. If the point set does not satisfy the limit value, we iterate the skin model simulation procedure until it's satisfied, else we continue the PCA evaluation step. We apply then PCA method to the point set To rotate the point set i M in a certain angle following a principal axis, we adopt here rigid transformation calculation of coordinate systems. Assuming that

o p o o R o p (3-24)
Where, ( ,

o o i j denotes the translation vectors from the origin i o to

origin j o . ( , 0,1) ij
R i j denotes the rotation matrix from the coordinate system i C to the coordinate system j C . In our method, the rotation matrix ij R is the direction cosine matrix, which is specified as formula 3-25 cos( , ) cos( , ) cos( , ) cos( , ) cos( , ) cos( , ) cos( , ) cos( , ) cos( , ) When the point set i M is rotated with a certain angle, we need to translate its local coordinates to global coordinates back. The solution is adopting the inverse matrix, and the process can be explained by formula 3-26

j i j i j i ij j i j i j i j i j i j i x x x y x z R y x y y y z z x z y z z (3-
1 1 1 1 2 21 2 1 o p o o R o p (3-26)
Where, 21 ( 1) R is the inverse matrix of 21 R .

The flow chat of this method is illustrated by figure 3-27.

Vertex normal direction deviation test

To compare skin model simulation methods described above, we create several sets of skin model of the tolerance plane described in section 3.3. The characteristic we evaluate here is the deviation between random (simulated) and nominal (Tessellated CAD) points. This test is a very common technique used by inspection software to compare a set of measurement data to a reference CAD model or to some specific target points described by their coordinates on a given reference frame. .

In figure 3-30, the blue points are the nominal points, and the black points are the random points that compose the skin model. The vertex normal of nominal point is i n .

The deviation evaluated in our method is the signed distance i d , which is obtained through the projection of the vector linking the nominal point i M to the random

point i R .
The test is based on sets of skin models using three different skin model generation methods. Simulation results are illustrated in figure 3-31, the horizontal ordinate is the number of skin models and the vertical ordinate reflects the average mean value of vertices normal direction of skin models. The Gibbs method as reported in the literature shows a slow convergence capability with the increase of the samples or the number of skin models. The statistical hypothesis test on the difference of standard deviations is a robust method of making decisions using our simulation data. The Gibbs method even if it is limited as depicted in previous sections for slow absolute time processing and weak convergence has a lower spread of data around the mean. Standard deviation is the main statistical parameter to describe the uncertainty and the variability of simulated or measured data.

Monte Carlo Markov Chain methods through the Gibbs sampler used in our work show an interesting result on standard deviations related to our simulations.

However, the statistical analysis performed here in the case of vertex normal deviation is still limited in consideration of the possible local "morphing" of the shape.

Deviation analysis here considers only the position of the simulated random point without taking into consideration the local effect of the shape in its neighborhood which can be considered through the normal computation. The following section introduces a new characteristic called volume deviation that considers the small unsigned volume around the nominal point and the simulated point.

Volume deviation test

The principle of this test is to evaluate the deviation of the small positive volume, which is composed by the vertex normal of random and nominal points. In figure 3 M R is obtained from the points i M and i R . Based on the scalar triple product which can be defined also as the as the determinant of the 3 × 3 matrix having the three vectors as its rows, the obtained scalar form is also the geometric interpretation of the (signed) volume of the parallelepiped defined by the given vectors as formula 3-28

i i i i i i R M R Vol M R N N N (3-28)
The test performed here evaluates the differences among the volume of the parallelepiped on sets of skin models using the three different skin model generation methods described in previous sections. The average volume standard deviation is also considered in this test .The results are illustrated in figure 3-37. We can see that all of these three methods have a steady standard deviation value, and the Gibbs method provides again the smallest value. From figure 3-39 we can see that there are differences among the standard deviation at the 0.05 level of significance using Minitab® statistical testing on standard deviations. Minitab® uses an alternative to the usual F-test, the Levene/Brown-Forsythe test that does not require that the data are normally distributed [Lim 96]. This test performs well for both normal data and non-normal data, even when the sample sizes are small. . From the statistical analysis perspective, the Gibbs method scores well as mentioned in the previous section. It's also important to notice that this method provides lower standard deviations in the case of non-normal distributions.

The unsigned volume deviation distribution shows some similarities to the Rayleigh distribution or the one-sided distribution for form deviations [Sombstay 58].

MCMC methods are well known for their robustness even for non-normal and unknown probability density functions.

The volume deviation test considered here takes into consideration both initial CAD/nominal point and the random generated point as well as normal vectors. This new characteristic highlights also the "quality" of normal estimation for simulation. The deviations to a CAD or nominal model can be visualized on a skin model.

Improving the visualization of the skin model

Those deviations are much smaller than feature size and it remains difficult to visualize them within a multi-scale geometry by human eyes directly. Therefore, helping the user observes and analyzes the differences between the nominal model and the simulated skin model is an important task. The mesh or facet representation is well used for scientific visualization but cannot solve this problem directly. We propose here to improve the mesh visualization by adding a color scale technique to reflect the computed deviations.

Considering the two previous deviation tests, we adopt here two visualization possibilities: visualization based on vertex normal direction and visualization based on volumes.

(

1). Visualization based on vertex normal

This section proposes to use RGB color scale mapping technique to visualize the geometrical deviations on the vertex normal direction. The basic idea of this method is that the extreme of deviations of the skin model are parallelized to a continuous color strip, which varies from the red color red to the blue.

The geometrical deviations between the simulated skin model and the initial point set are computed by the deviation in the direction of the vertices normal. The vertex normal estimation method was introduced in section 3.2.4. A continuous RGB color scale is then used to reflect the deviations on a skin model.

Conclusion

Skin model construction is one of the critical issues in GeoSpelling. This chapter proposed the developed methods to shape the skin models with random deviations.

Based on the hypothesis that the random deviations follow the normal distribution, three different methods are developed to generate the skin models with discrete representations: 1-D Gaussian-based method, multi-Gaussian-based method and Gibbs-based method.

At the beginning, the nominal shape is tessellated as discrete representations Finally, a comparative analysis of these methods is discussed. The random error is considered in this chapter and the systematic error-based skin model simulation will be discussed in the next chapter

Introduction

Because of the limited accuracy of applied manufacturing machines and tools, the skills of operators, the environments, etc., No product can be manufactured ideally without any errors. The error, indicated the variance of a real measured from its theoretical value, typically composes of random error and systematic error. The previous chapter, several methods are developed to simulate the skin model by adding random error to the nominal shape. As mentioned above, the skin model only considered random error is incomplete. The systematic error should also be simulated during the skin model shaping process.

Different from random errors which are statistical fluctuations (in either direction), systematic errors are reproducible inaccuracies that are consistently in the same directions. They usually keep the same value or follow the recognizable laws which can be calculated or simulated. In skin model shaping, it is thus reasonable to adding errors followed by some known basic shape models (e.g. second order shapes)

to simulate the systematic errors. In this chapter, a set of methods are developed to simulate the systematic errors based on a group of second order shapes. In practice, the systematic errors can be simulated by adding deviations followed by a unique shape or by a combination of several shapes within the basic shapes' group.

With consideration of random and systematic errors, the shaped skin models are complete to represent the real geometrical variations. Given a nominal shape associated with specific geometrical tolerances, various skin models which satisfy the tolerance requirements can be generated to simulate the actual shape. A method based on SSM (Statistical Shape Model) is developed for skin model analysis. This is useful to evaluate the skin models and predict the trend of new skin models (actual shapes' trend prediction).

The chapter is organized as follows:

Section 4.2 reviews the literature related to variation based shape modeling methods. Section 4.3 presents the developed skin model shaping methods to simulate the systematic error. Section 4.4 gives the developed method based on SSM for skin model analysis and evaluation. Section 4.5 is the conclusion.

Shape deviations

It's well understood that shape deviations are the fundamentals of geometric Research and industry reported a number of sources of manufacturing error and deviation such as locating error, clamping error, datum feature (surface) error, workpiece elastic deformations, tool wear, vibration, misalignment and machine guidance errors as well as thermal disturbances and so on. The systematic errors are generally easier to identify, isolate and correct than random errors.

Manufacturing processes leave very specific patterns or signatures on the part. In some cases, it is possible to quantify the manufacturing errors through mathematical models. In general cases, the manufacturing errors can be captured using experimental analysis. Colosimo et al. [Colosimo 07] define the manufacturing signature as the systematic pattern which characterizes the features realized by a given process in given conditions. This systematic pattern is "masked" by additional random noise caused by the natural variability of the process. A statistical analysis is then required to obtain the manufacturing signature estimate.

Many efforts have been made to simulate the systematic deviations of shapes. All of these works can be roughly classified into three categories: analytical approaches, statistical analysis and other methods. Samper [Samper 07] proposed a new way to define for error parameters based on the eigen-shapes of natural vibrations of surfaces. The originality of this method is that the set of form parameters can be computed for any kind of shape. The principle of this method is that the geometry variation is defined by using a geometrical basis built on the model shape, which have vectorial space properties and are defined by

Systematic Deviations simulation method

As discussed before, the systematic deviations are caused by many sources such as the inherent properties of manufacturing and inspection machine, the environment condition and even the operators. Thereby the possibilities of the systematic form errors are various. Dowling [Dowling 97] argued that incorporating the systematic manufacturing errors into a modeling and assessment procedure is an important issue.

There have been already some efforts attempted on expression of form Both these two kinds of methods are using the modification of parameters to obtain the form deviations.

In our method, we proposed using second order form deviations to simulate the systematic errors, since the second order form deviations can reflect the principle curvature and the anisotropy of complex shapes better than the first order and higher order deviations [Kurokawa 05]. Kurokawa [Kurokawa 05] proved mathematically that an arbitrary second order surface can be transformed into a fundamental form of the second order by the combination rotation, translation and scaling transformation.

Based on this argument, we proposed the systematic errors defined in our method are one or a combination of some basic second order surfaces, and the details are explained below.

Plane deviation simulation

The systematic distortions of planar parts are based on the following hypothesis.

(a)

The systematic error of a planar part can be described by one or more basic geometric shapes. The principle of morphing to the basic geometric shape is that, the deviation can be assumed following the vertex normal direction. For each case, the morphing details are explained as follow.

(

1). Paraboloid

In mathematics, a paraboloid is a quadric surface and there are two kinds of paraboloid: elliptic and hyperbolic. In our work we focus on the elliptic paraboloid, which can be represented using formula 4-1

2 2 2 2 x y z a b (4-1)
Where a and b are constants that dictate the level of curvature in the x-z and y-z planes respectively.

In our method, the paraboloid surface is simulated from the discrete model of a plane. The principle of our method can be explained by figure 4-2, in which p S denotes the paraboloid point set and p I denotes the initial planar point set.

We use PCA algorithm (see section 3.4.1) to evaluate the principal axis to obtain the local coordinate system ofc. Suppose i p is a random point of p I , and i q is its corresponding point of p S . The distance between these two points in i p 's vertex normal direction is reflected using i h , which fulfils the formula 4-1. (

2). Cone

A cone is a quadratic surface. In figure 4-4 the height h and the base radius r oriented along the z -axis and with the base located at 0 z (denoted as 0 z ), the cone shape can be described by formula 4-3

2 2 2 0 2 ( ) x y z z c (4-3)
Where, ( , , )

x y z is the Cartesian coordinate value, and c is the ratio of radius to height at some distance from the peak r c h .

In our method, we simulate the cone shape form a discrete plane, which is tessellated from a CAD model of plane surface. The principle of the method can be explained by figure 4-4. (1 )

i i r h h r (4-4)
Where i r denotes the distance between the center of p I and the point i p .

During this process, the deviation of each point i p is calculated based on the height h , which is in the normal direction n . To simulate the cone shape (see figure 4-4) we construct the triangle by the peak of cone, the radius of p I , and the center of p I . The value i h is obtained from the proportional calculation of this triangle. This estimation is based on the assumption that p I and i n follow the same direction in the space. Considering p I is a normal tessellated plan model, the normal n and i n has a small difference error , which coming from the tessellated techniques. We compared these two normal values, and the value is approximately equal to 10 -6 . The simulation result is illustrated in figure 4-5. (3). Sphere

In mathematics, a sphere with center 0 0 0 ( , , )

x y z and radius r is the locus of all point ( , , )

x y z satisfying the formula 4-5

2 2 2 2 0 0 0 ( ) ( ) ( ) x x y y z z r (4-5)
In our method, we simulate the sphere point set from the tessellated plan model.

The principle of this method is explained by figure 4-6. As discussed above, p I denotes the initial planar point set and s S denotes the sphere point set. The sphere simulation method is based on the hypothesis that the shape can be reflected by the deviation of point set in the direction of each vertex normal. In figure 4

(4). Cylinder

In mathematics, a cylinder is a quadric surface, which is formed by the points at a fixed distance called radius from a given line segment, the axis of the cylinder. With the radius r , a cylinder can be illustrated as in formula 4-7 2 2 ( ) ( ) 1 x y r r (4-7)

In our method, we simulate the cylinder point set from a planar tessellated model, and the principal of this method can be explained by figure 4-8. Where a and b are the equatorial radii (along x and y axes) and c is the polar radius (along the z -axis).

In our method, we simulate the ellipsoid point set from a planar tessellated model, and the principal of this method can be explained by figure 4-10. As defined before,

(6). Rotation

Rotation defined in our method is a rigid body movement of the point set following an axis. In our method, firstly we define a rotation axis, and then adopt a rotation matrix to obtain the rotation point set. In three-dimension space, a rotation matrix has a unit real eigenvalue, and based on the Euler's rotation theorem the rotation matrix can specify the rotation of the corresponding eigenvector. Suppose the rotation follows x axis, y axis, and z axis respectively in Cartesian coordinate system, and each of rotation is named as roll, pitch and yaw, and then the rotation matrices as formula 9 to formula 11: Where, x is the angle of roll, y is the angle of pitch, z is the angle of yaw.

The principle of our method can be explained by figure 4 (

2). Convex

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object. According to this definition, there are various types of convex models, such as solid cubes. While in our method, we simulate the convex shape following the ellipsoid model.

An ellipsoid is a closed type of quadric surface, the standard axis-aligned ellipsoid in a Cartesian coordinate system is interpreted by formula 4-13:

2 2 2 2 2 2 1 x y z a b c (4-13)
Where a and b are the equatorial radii along the x axes and y axes and c is the polar radius along z axis.

In our method, we simulate the ellipsoid from a tessellated cylinder model. (

3). Concave

The concept concave means curving in or hollowed inward, as opposed to convex.

There are many kinds of concave shapes, while in our method we simulate the hyperboloid surface as the concave systematic error.

In mathematics, a hyperboloid is a quadric surface in three dimensions space, and can be described by formula 4-14:

2 2 2 2 2 2 1 x y z a b c (4-14)
Where a and b are the equatorial radii along the x axes and y axes and c is the polar radius along z axis.

In our method, we simulate the hyperboloid from a tessellated cylinder model.

4). Banana

The banana systematic error is named by the appearance of the form error of a cylinder. There is no simple analytical definition of a banana shape, while we propose using quadric surface to simulate it, such as, ellipsoid and hyperboloid etc. The banana simulation approach we implemented here is based on the hyperboloid surface, which can be described by formula 4-15:

Mean vector and covariance matrix

The computation of the mean vector and the covariance matrix is the common solution to analyze the multivariate data. The mean vector is often referred to as the centroid and the covariance matrix as the dispersion or matrix. The definition of mean vector and the covariance matrix can be explained by the following formula 4-16

1 n X X X (4-16)
Where X is used to refer to random vectors, and i X , (1, 2, ) i N is used refer to random scalars. In formula 4-16, if the items in the column vector are random variables, then the covariance ij is the difference whose ( , ) i j item is the covariance as formula 4-17 cov( , )

] i j ij i j i j X X E X X X X (4-17) [( )( )
Where X is the mean vector and

] ii i i i X X E X X (4-18) [( )
To summarize all the covariance of the vector X , the covariance matrix can be obtained as formula 4-19

1,1 1,2 1, 2,1 2,2 ,1 , n n n n = (4-19) If , 0 i j
, it means that the two variables vary together in the same direction relative to their expected values, and otherwise , 0 i j it means these two variables are have the different tends to the expected value. When , 0 i j , it means that there is no linear dependency between these two variables.

Principle of Statistical shape model method

To establish a statistical shape model, four steps are needed [ ( x y z is the coordinates of the shape model in spatial space. In practice the number n of points is fixed to a value which permits sufficient details of the shape.

1). Acquiring a training set

The requirements for the training set for our skin models are as follow.

(a) The samples show strong similarities and encapsulate enough variability informations;

(b) The size of the sample should be choosen to avoid large data for time processing and small data for the reliability of the results;

(c) The observed shape models can be provided from the different activities and phases of the product life cycle, such as engineering simulation, manufacturing and inspection, etc.

(

2). Determining the correspondence

Since a training set contains a number of samples, establishing the relationship among them is a critical problem. There are many efforts that have been done to solve this problem. According to the study of Niu [Niu 07], these solutions are roughly separated into two categories, landmark-based method and landmark-free method. A landmark as defined in [Stegmann 02] is a point of correspondence on each object that matches between and within populations. Dryden and Mardia [ Dryden 98] discriminates landmarks in to three subgroups:

(a) Anatomical landmarks: points assigned by an expert that corresponds between organisms in some biologically meaningful way.

(b) Mathematical landmarks: points located on an object according to some mathematical or geometrical property, i.e. high curvature or an extremum point.

(c) Pseudo-landmarks: constructed points on an object either on the outline or between landmarks.

In general, there are some principles that should be followed to determine the landmarks. Firstly, the points that contain the important geometrical or mechanical information should be demarked. Secondly, the number of landmarks should be proper. If the density of landmarks is too small the model can not reflect enough geometrical information, and in contrary, the calculation process will be time consuming. At last, the landmarks in a training set should have the corresponding relationship, which means that the related landmarks can present the same geometrical character of a shape.

(3). Alignment

Considering that the models in the training set are different from each other by scale, position and rotational effects, an alignment operation is necessary to make the shape prior independent of translation, rotation and. In our case, we suppose that the scale effects are non-significant and we will focus mainly on rotation and translation effects.

Since the shape model is represented by point set, registration techniques as described in chapter 2 can be employed here. First, using PCA method we estimate the principal components and the centroid position of the point set, the local coordinate system of each sample can be determined (Figure 4-22). ICP is an algorithm for searching the corresponding point pairs between two discrete shapes. Many efforts have been attempted to improve the ICP method, and we adopt here CFR (Curvature based Fine Registration) [ Zhao 10] method, which combines the Euclidean distance and the principal curvature ratio distance.

Let i p and i q are two arbitrary points in different samples of a training set, and let g d denotes the geometric distance between points i p and i q . The geometric distance is defined as formula 4-21

( , ) (1 )
g i i e c d p q d k d (4-21)
Where We construct the corresponding point pairs for all the samples, and then we can calculate the mean model for the training set and establish its statistical model. Where X is the mean; the t dimension vector x b is the shape coefficient that controls the models of variation.

The main function of statistical shape model is to determine the mean model among numerous sampling shape models and to predict new shape model belonging to the same shape family. Since X and

Application

The In table 4-3, each sample is composed of 80 points, which are deemed as the landmarks in our method. The distribution of landmarks is described as follows: To find out the mean shape, we create the point distribution model of each shape using the coordinates of the landmarks. Then we align the nine samples based on the eighty landmarks. The samples are imported in our software platform, and then the PCA method is employed to calculate the local coordinate system for each sample.

-Gauss Multi-Gauss Gibbs (a) (b) (c) (d) (e) (f) (g) (h) (i)
We transform all the samples represented in their local system to the global coordinate system, and then an initial registration of the samples is obtained

Conclusion

This chapter presents the skin model simulation methods considering the systematic errors and the skin model analysis method based on statistic shape models.

The first part of this chapter discussed the developed methods for skin model simulation considering the systematic errors. A group of second order shape models are implemented as the constraints of adding systematic errors on skin models. Six basic shapes in this group are generalized to simulate the shapes with systematic errors: Taper, spherical, cylindrical, hyperboloid, ellipsoid, banana-based shape. These six shape types cover the general shapes induced by systematic errors. The proposed methods provide the reasonable simulation results.

The complete skin models including both random errors and systematic errors can be simulated based on the developed methods in this chapter and the previous one.

A new method based on Statistic Shape Models is then developed for skin model analysis. With a set of training skin models acquired from different sources, the method first aligns them together first. The statistic shape model including mean model and covariance are computed. The statistic shape model predicts the trend of the skin models, which can be used to evaluate the real shapes.

Introduction

The aim of this chapter is to further illustrate the methods described in previous chapters by presenting a detailed case study of a cross-shaped workpiece.

A software framework has been developed as the testing platform for the developed methods of discrete geometry processing (normal estimation, random and systematic errors simulation, mean model evaluation and statistical shape model prediction) described above.

Based on the CAD model and the measurement data, the form errors of the workpiece are simulated by our software framework. Since our software framework is an open system, the mean model and statistical models are also evaluated based on the training set of shape models simulated by other simulation methods.

This chapter is organized as follow:

In section 5.2, we describe the platform and the development tools of our software. Section 5.3 presents a case study including skin model simulation and statistical shape modeling. Section 5.4 is the conclusion of this chapter.

Platform overview

Development tools

Our software system is developed using C++ language based on Microsoft Visual

Studio C++ 2005 platform. The Computational Geometry Algorithms Library (CGAL) is employed to construct the polyhydric data structure of the discrete point data. For the visualization of the shape model, Advanced Graphics Programming Techniques Using OpenGL is adopted here. The details of the development tools are briefly discussed below.

( (

1). Microsoft Visual Studio

2). Computational Geometry Algorithms Library

Computational Geometry Algorithms Library (CGAL) [Cgal 11] is an open source project used to provide efficient and reliable geometric algorithms for computer graphics, computer aided design and modeling, mesh generation, numerical methods, etc.

The CGAL also provides the data structures and algorithms on discrete geometric objects like points and meshes. These data structures include Voronoi diagrams, polygons, polyhedra, mesh generation, geometry processing, etc.

The functions of CGAL employed in our work mainly focus on the geometric algorithms and the polyhedra data structure. The 3D polyhedral surfaces are composed of vertices, edges, facets and incidence relationships on them. The representation of polyhedra surface is a halfedge data structure, which restricts the class of representable surfaces to orientable 2-manifolds with boundaries. The details of the halfedge data structure are introduced in section 3.2.3.

(3). Open Graphics Library

The Open Graphics Library called also OpenGL [OpenGL 11] developed by Silicon Graphics Inc., is a developing environment, which provides thousands of interfaces for 2D and 3D computer graphics applications, and it is widely used in CAD, virtual reality, scientific visualization, etc.

The well-specified OpenGL standard has language bindings for C, C++, Java, etc.

Considering the high visual quality and performance of OpenGL to support CAD visual display, OpenGL is adopted in our work for the graphics processing.

Main interface

Figure 5-1 shows a screen shot of the main user interface, and the most important interaction tools are annotated:

Point tool allows the user to show/hide the vertices of the discrete model.

Mesh tool allows the user to show/hide the polygon mesh of the discrete model.

Facet tool allows to user to show/hide the facet rendering of the discrete model.

1D-Gaussian tool is used to generate skin models with the random deviations of 1D-Gaussian distribution.

3D-Gaussian tool is used to generate skin models with the random deviations of multi-Gaussian distribution.

Gibbs tool is used to generate skin models with the random deviations of MCMC Gibbs sampling.

Menu specification

The menu specifications displayed in figure 5-2 describe detailed functions of our developed system.

(a) Model. The "Model" menu is used to reflect the basic two kinds of information of the input tessellated shapes. One is the mode of display such as point mode, mesh mode and facet mode, and the other one is the normal information, which includes different vertex normal estimation methods and facet normal estimation method.

(b) Random. The "Random" menu is used to simulate the skin models with random errors especially Gaussian distribution deviations. In this menu there are three options: 1D-Gaussian method, Multi-Gaussian method and Gibbs method.

(c) Systematic. The "Systematic" menu is used to simulate the skin model with the systematic deviations.

The "Curvature" option is used to estimate the surface curvature including Gaussian curvature and mean curvature.

The "Systematic Plan" option is used to simulate the systematic deviations of planar shapes, and the basic shapes that can be simulated.

The "Systematic Cylinder" option is used to simulate the systematic errors of cylindrical shapes, and the basic shapes that can be simulated.

The "Form error" option is used to simulate the skin models with both random deviations and systematic deviations.

(d) SSA. The "SSA" command is used to evaluate the information of statistical shape models, which are skin models in our case.

The "Mean model" option is used to estimate the mean model of a training set of skin models.

The "SSM" is the abbreviation of the statistical shape model, and this option is used to predict new models of the training set of skin models.

Application

Skin model simulation

The case study is based on a sheet metal part manufactured in a one-stage sheet metal forming process [Stockinger 10a]. The process of sheet metal forming is selected here because of the existing simulation tools dealing with accurate material models and taking multistage process steps into account (gravity, stamping, springback, etc.) [ Stockinger 09].

The manufacturing process is simulated using stochastic FE techniques. For the discretisation of the blank, shell elements are used. The tooling is modeled as rigid parts and a process macro is used to define the process including stamping velocity, blank holder force and friction. An initial model of the stamping process serves as a basis for the variation of process parameters. The selected variables (described in Based on the CAD model (see figure 5-4), the bottom plane can be extracted using CATIA V5 GSD utilities as illustrated in figure 5-5. In order to discretize the bottom plane, the tessellation operation is implemented using CATIA V5 software. In table 5-?, the standard deviation of the point set to the associated ellipsoid and the associated cylinder has the smallest value that equal to 0.072 mm. Considering the limited deviation from point set to the associated plane is smaller than the cylinder shape, so we simulate the systematic errors using ellipsoid shape here. To verify that the skin model obtained from the simulation of ellipsoid systematic errors, the deviation analysis is adopted (see figure 5-12). We associate the point set as a planar shape, and the analysis result is as follow. The point number is equal to 2392, and the limit values of the deviation are equal to 0.258 and -0.119 as respectively. The mean deviation is equal to -9.6e-005mm, and the standard deviation is equal to 0.0904mm. Comparing the deviation between the skin model and the measured point set (see figure 56789), the random errors are absent. The random errors are added to the skin model with ellipsoid systematic errors.

Items

The Gibbs method is adopted to simulate the random errors following the Gaussian distribution. The skin model with both systematic errors (ellipsoid) and random errors (Gaussian distribution) is illustrated as figure 5-13. Figure 5-14 is the color scale representation of the skin model, and the color changed is continuous from red to blue but with some noise. This illuminate that the deviations follow the ellipsoid shape variety, but it also with random noises. Considering that the FEA simulation models are in a uniform scale and have the same coordinate reference system, the simulated models are aligned using the registration algorithm described in chapter 4. Figure 5-18 illustrates the alignment of the samples, which are denoted using different colors. Based on the analysis results of two mean models that simulated by our method (introduced in section 5.3.1) and FEA method, the deviations compared to the measurement data are compared as According to table 5-2, our method provides a smaller standard deviation and mean deviation mean model than the one simulated by FEA method. It can be deduced that our method fit the form errors better than the FEA method in this case.

( The statistical shape models predicted above are based on the training set of samples simulated by our method (introduced in section 5.3.1) and FEA method.

2). Statistical shape model

Hence they have a combined distribution performance of these two kinds of samples.

Conclusion

This chapter presents a detailed case study of a cross-shaped sheet metal

workpiece. An open modular framework software has been developed to test and support the methods and algorithms developed in this thesis.

The detailed processing results of the studied case are presented here. The main results concern the simulation of skin model that includes both systematic and random deviations. A new systematic errors simulation method based on shape decomposition technique is presented.

Based on the measurement data, a comparison between the two kinds of simulated skin models (by our method and FEA method) is presented, and our method is proved has a better approximative simulation result experimentally.

Based on the training set of simulated models using stochastic FEA, we create a mean model and derive the main characteristics of the training set. We have described a method for building 3D statistical shape models for mechanical models considering the training set composed by the samples simulated using different method. Based on the principle components analysis of the predicted models, the large variability included in the tested models is discussed.

A coherent and complete tolerancing process is necessary in mechanical applications to manage geometrical variations along the product lifecycle.

GeoSpelling is proven to be an appropriated model for this purpose, which is standardized as ISO 17450. This thesis presents several significant contributions to achieve GeoSpelling for geometrical product specification from two aspects: discrete

Contributions:

The main contributions of the dissertation to GeoSpelling for geometrical product specification are listed as follows:

A new framework for geometrical operationalization of GeoSpelling is A software framework is developed to support the skin model simulation methods presented in this thesis. The framework is modular and user-friendly. It is easy to integrate new functions related with discrete geometry processing.

Future works:

The discrete geometry processing for improve GeoSpelling contains many other topics, which have not been addressed in this thesis. Some promising works for the future are presented as follow.

Random errors simulation. Statistical model.

To predict reliable shape models that can reflect the principal characteristics of a training set, it should be investigate an efficient scope of the model coefficients.

Figure 1 - 1 :

 11 Figure 1-1: Tolerance process .........................................................................................................10 Figure 1-2: The structure of EDT....................................................................................................15 Figure 1-3: The structure of VGraph...............................................................................................16 Figure 1-4: The structure of hybrid CSG/B-Rep method [Roy 91].................................................18 Figure 1-5: Cases of tolerancing between surfaces with MGDEs results .......................................20 Figure 1-6: Three shape structural expressions...............................................................................22 Figure 1-7: Taxonomy of categories of shape representations........................................................24 Figure 1-8: CSG representation [Shapird 01] .................................................................................25 Figure 1-9: An example of B-rep shape model ...............................................................................26 Figure 1-10: The topological data structure defined in STEP standard...........................................26 Figure 1-11: Examples of polygon mesh representation.................................................................27 Figure 1-12: An example of B-rep shape model .............................................................................28 Figure 1-13: An example of NURBS surface..................................................................................31 Figure 1-14: Implicit representation in 2D space............................................................................32 Figure 1-15: Normal and principal curvature directions of a smooth surface at point p ...............34 Figure 2-1: Specification defined in GeoSpelling...........................................................................38 Figure 2-2: Classifications of operations ........................................................................................39 Figure 2-3: Partition operation ........................................................................................................40 Figure 2-4: Filtration operation.......................................................................................................40 Figure 2-5: Extraction operation .....................................................................................................40 Figure 2-6: Collection operation .....................................................................................................41 Figure 2-7: Association operation ...................................................................................................41 Figure 2-8: Construction operation .................................................................................................41 Figure 2-9: Surface model...............................................................................................................43 Figure 2-10: The plane fit criterion .................................................................................................50 Figure 2-11: The Mini-ball criterion ...............................................................................................50 Figure 2-12: The Nearest-neighbor graph criterion ........................................................................51 Figure 2-13: Lp norm of association...............................................................................................52 Figure 2-14: Least Squares method.................................................................................................53 Figure 2-15: Moving least squares..................................................................................................53 Figure 2-16: Intersection cases .......................................................................................................54 Figure 2-17: Dividing the polygon into triangles............................................................................54 Figure 2-18: Finding the intersection curve of two MLS surfaces..................................................56 Figure 2-19: The difference of distance between ideal and non-ideal feature ................................57 Figure 2-20: triangle domain D.......................................................................................................60 Figure 2-21: when ( , ) (0, 0) Q s t

  communication and sharing requires to manage the geometrical variations along the whole product lifecycle. The geometrical variations should be considered at the beginning of tolerancing process in the design stage. Many Computer Aided Tolerancing tools [Mathieu 05] can help designer for functional tolerance specification, but limited to control the geometrical variations for the view of product lifecycle. Some authors [Ballu 05] [Salomons 96] proposed concepts to build coherent and complete tolerancing process. As a perfect example of these concepts, GeoSpelling proposed by Ballu and Mathieu [Ballu 95] has already standardized as ISO 17450. However, till now there is no reported system yet has capacity to manage geometrical variations along the product lifecycle. This chapter surveys the popular techniques for tolerancing process, especially in tolerance presentation and specification. The GeoSpelling model is introduced to manage the geometrical variations. The shape modeling techniques supported for geometrical production specification are reviewed. This chapter is organized as follows: Section 1.2 presents the popular techniques for tolerancing process, especially techniques for tolerance representation. Section 1.3 surveys the common-used shaping modeling techniques in literature and industrial applications. Section 1.4 is the conclusion of this chapter.

  Figure 1-1: Tolerance process

[

  Srinivasan 89] proposed Virtual Boundary Requirements (VBRs) and Conditional tolerances (CTs) approach. The purpose of their work is that the functional requirements can be captured in a specific form of tolerances designated as their models. The VBRs approach is proposed based on the study the problems form the perspective of two classes of functional requirements, which directly relatable to the geometry of mechanical parts [Jayaraman 89]. The first involves positioning parts with respect to one another in an assembly, and the second maintaining material bulk in critical portions of parts. The CTs approach on a set of features specifies geometric variations that are dependent on geometric parameters derived from fitting fo the actual set of features. The Maximum Material Condition (MMC) and Least Material Condition (LMC) tolerances used in practice are in fact CTs specifications. Typically, VBRs when translated into allowable variations in geometric parameters of features give rise to CTs. There are some reasons for derive alternative specifications (as nearly equivalent to the VBRs as possible) based on the concept of CTs, such as: part fabrication process planning problem, part fabrication process planning problem, part fabrication process control problem, and statistical tolerancing problem, and the details of these reasons are indicated in [Srinivasan 89].

(

  a) B-Rep based model. Johnson [Johnson 85] proposed a tolerance representation approach, which integrates dimensioning and tolerancing modelers with the geometric modelers. Based on this proposal, a dimensioning and tolerancing modeler, named Evaluated Dimensions and Tolerances (EDT) model, is applied in CAM-I system. As the EDT model uses boundary representation, the B-Rep solid modeling part needed to be created first, before the tolerancing specification templates applied to the EDT model. The tolerancing specification templates are used to check the features validity to establish the DRF and to compute the tolerancing values. The schema of EDT model consists of four types of node: a D/T (Dimension and Tolerance) node; an EL (Entity-Linking) node; a DRF (Datum Reference Frame) note; and an ED (Evaluated Data) note. An example of an EDT model for slot tolerancing is illustrated in figure 1-2.

Figure 1 - 2 :

 12 Figure 1-2: The structure of EDT

Figure 1 - 3 :

 13 Figure 1-3: The structure of VGraph

Figure 1

 1 Figure 1-4: The structure of hybrid CSG/B-Rep method [Roy 91]

(d )

 ) TTRS model TTRS model is proposed by Clement [Clement91] [Clement 93] to discuss the tolerance representation both in mathematical and theoretical point of view. Clement

Figure 1 - 5 [

 15 Figure 1-5 [Salomons 96] illustrates the reclassification of TTRS and the types of tolerance specification can be determined.

Figure 1 - 5 :

 15 Figure 1-5: Cases of tolerancing between surfaces with MGDEs results

  Figure 1-6: Three shape structural expressions

Figure 1 - 7 :

 17 Figure 1-7: Taxonomy of categories of shape representations

  intersection and difference. The construction for the solids bounded by planar and second degree surfaces have been solved completely [Shapird 01]. Figure 1-8 gives an example of CSG representation of a mechanical part.

Figure 1

 1 Figure 1-8: CSG representation [Shapird 01]

Figure 1 - 9 :

 19 Figure 1-9: An example of B-rep shape model

Figure 1 - 10 :

 110 Figure 1-10: The topological data structure defined in STEP standard

(

  their coordinates) explicitly encoded along with their values. Instead, the position of a voxel is inferred based upon its position relative to other voxels. In contrast to pixels and voxels, points and polygons are often explicitly represented by the coordinates of their vertices. Voxel-based representation is a kind of spatial-partitioning technique. With this technique, a solid is decomposed into small cubic voxels. An example of voxel-based representation is given in figure 1-12.

Figure 1 -

 1 Figure 1-12: An example of B-rep shape model

  Figure 1-13 gives an example of a NURBS surface representation.

Figure 1 -

 1 Figure 1-13: An example of NURBS surface

  outside. The point is on the surface when ( ) 0 f p . Figure1-14 illustrates these cases in 2D representation.

Figure 1 -

 1 Figure 1-14: Implicit representation in 2D space

Figure 1

 1 Figure 1-15: Normal and principal curvature directions of a smooth surface at point p

  curvature. The parameter M indicates Mean curvature which is an extrinsic measure of curvature. The parameter s indicates shape index which is a single value within the range [-1, 1] to measure the local surface types [Koenderink 92]. The parameter c is the curvedness which is a positive number to specify the amount of the surface curvatures [Koenderink 92].

  features. The methods to handle ideal features are extensively researched and are mature in the popular CAD software packages. But the methods to handle the non-ideal features (skin-model which is the kernel concept in GeoSpelling) haven't solved yet. With widely applied 3D scanners (e.g. Laser scanner), 3D point clouds acquired by 3D scanners is becoming popular in many applications, such as reverse engineering, quality control, rapid-prototyping, etc. 3D point clouds which are acquired from the real part can represent the real features. Therefore, the skin model can be constructed and simulated based on 3D point clouds. The discrete geometry processing technologies can then be used to handle the discrete skin models and the related geometrical operations. This chapter represents the characteristic concepts of Geospelling and discrete geometry. The corresponding relationships between GeoSpelling and discrete geometry are constructed and a new framework is defined for the geometrical operationalization of GeoSpelling from the view of discrete geometry.

A

  specification is a condition on a characteristic defined form geometrical features, and these geometrical features are created from the model of the real surface of the part (skin model) by different operations (figure 2-1) [Mathieu 05].

Figure 2 - 1 :

 21 Figure 2-1: Specification defined in GeoSpelling

Figure 2 - 2 :

 22 Figure 2-2: Classifications of operations

Figure 2

 2 Figure 2-3: Partition operation

Figure 2

 2 Figure 2-7: Association operation

Figure 2

 2 Figure 2-8: Construction operation

  on the GPS standard [ISO 2005], the surface model is a closed surface which can represent the interface between workpiece and its environment. The concept of skin model is the basic foundation of GeoSpelling, and all the operations are performed on the skin model. The skin model is a kind of surface model, and it is opposite to nominal model. The nominal surface model is a surface model of perfect shape defined by CAD software. Normally, the nominal surface model is deemed as an ideal feature. It used to reflect the design intend and the function requirements. A comparison between the nominal model and the skin model is illustrated in figure 2-9. The skin model also called the specification surface model is a surface model of non-perfect shape imagined by the designers to reflect the specifications and verification requirements. Considering the form errors of workpieces involved during the manufacturing and inspection process can be classified into two categories: random errors and systematic errors [Henke 99] [Desta 03], the skin model need to reflect these two kinds of errors. The definition of skin model proposed in our work is that a surface model combined both random and systematic errors on a nominal model.The skin model simulation methods will be introduced in chapter 3 and chapter 4.

  Figure 2-9: Surface model

( a )

 a Acquisition. There exists a variety of geometric measurement devices based on different technologies such as contact probing, photogrammetry, laser scanning, structured lighting and tomography. The output of such devices is often composed of 2D or 3D point sets with in some cases color attributes and normal estimation. (b) Registration. The output of shape acquisition devices is a series of point set corresponding to different acquisition viewpoints. A registration is required to align the data in a common coordinate frame. Many approaches employ rigid transforms and variants of Iterative Closest Point (ICP) techniques [Besl 92] [Rusinkiewicz 01] and new researches deal with non-rigid transforms [Li 08] for compensating calibration errors, noise, and irregular sampling.

  reproduced accurately in the reconstructed surface [Chang 07]. The research literature is very rich and various techniques have been developed [Bolle 91] [Alexa 01] [Tamal 06]. The earliest techniques used NURBS or B-splines to fit and stitch together local surface patches but showed their limits when dealing with complex physical object, large data and noise. Voronoi-based methods provide a provable reconstruction guarantee. Implicit surface fitting techniques produce high-quality surfaces that accommodate sharp features and boundaries while moving least squares surfaces are robust to noise.

  connect each point to a continue boundary and consider the area inside the boundary as the segmentation. Yang and Lee [Yang 99] introduced a partition technique for extraction edge points by estimating the local surface curvature, and the parametric quadric surface approximation method was applied. Ke and Fan [Ke 04] extracted the edge points by divided dimension grids according the density of points. Wu and Wang [Wu 07] identified edge points based on the differential geometry theory. The edge-based methods always have two stages; one is edge detection stage, and the other is linking stage. This method finds boundaries between surfaces in point data firstly, and an edge-linking process followed, in which disjoint edge points are connected to form continuous edges. Then infer the surfaces as the areas inside the boundaries. Usually, detect edge points based on the behavior of some features such as normal or curvatures e.g. [Yang 99] [Wu 07]. The main problem to the edge-based technique is the points near sharp edges are unreliable, result in a relatively high sensitivity to occasional spurious data points. The region-growing methods proceed with segmentation by detecting continuous surfaces that have homogeneity or similar geometrical properties. Ke and Chen [Ke 06] proposed a partition method based on the differential geometry and mathematical statistic theory. Jagannathan [Jagannathan 07] presented a graph-morphology-based 3D mesh segmentation algorithm to classify vertices into different categories based on their intensities of curvatures. Liu and Xion [Liu 08b] addressed the approach mainly based on the Gaussian map, the Clustering, the region Recognition and the region Rectification. Benkö and Várady [Benkö 04] studied how to improve the connections of partition regions more smoothly.The region-growing methods detect continuous surfaces firstly, and then can get the homogeneity or similar geometrical segmentation, e.g. [Ke 06] and[Jagannathan 07]. For this method, it always selects a series of seed points firstly, based on a certain threshold, the seed points growing to a related range, and then can segment the cloud points. The advantage to face-based techniques is that it work on a larger number of points to reduce the risk of sensitivity to occasional spurious data points and can identified which points belong to which surface.Hybrid methods have been developed by combining the edge-based and region-based methods together to yield an approach that can overcome the limitations involved in the above two kinds of methods. Woo[Woo 02] proposed segmentation that uses an octree-based 3D-grid splitting process that uses the iterative subdivision of cells based on the normal values of points, and the region-growing process to merge the divided cells into several groups.

  While in discrete geometry, filtration mainly concerned about outlier moving based on sample points. Outlier is the erroneous point that outside the surface and should be removed. There are some methods can achieve this object, such as plane fit criterion, mini-ball criterion and nearest-neighbor reciprocity criterion [Gross 07]. (a) Plane fit criterion. The plane fit criterion considers a plane H that minimizes the squared distances to a sample point p's neighbors, it can be described by formula 2-1 (see figure 2-10): the distance of p to H, and d the mean distance of points from ( ) k N p to H. The plane fit criterion is defined as formula 2by d relates d to possible noise and surface deviations.Figure 2-10 illustrates that the plane fit criterion compares p's distance d to a least squares plane H with the average distance of its neighbors to H, and p's k-neighbors are denoted in blue.

Figure 2 - 10 :

 210 Figure 2-10: The plane fit criterion

  figure 2-11). S can be seen as an approximation of the k-nearest neighbor cluster. Comparing p's distance d to the center of S with the sphere's diameter yields a measure for p's likelihood to be an outlier. The mini-ball criterion is defined as formula 2-3

Figure 2 -

 2 Figure 2-11: The Mini-ball criterion

Figure 2 -

 2 Figure 2-12: The Nearest-neighbor graph criterion

Figure 2

 2 Figure 2-13: Lp norm of association

Figure

  Figure 2-14: Least Squares method

  where i d are the Euclidian distances between x and the positions of data points i x . (c) Moving Least Squares method. The MLS method was proposed by Lancaster and Salkauskas [Lancaster 81] for smoothing and interpolating data. The idea is to start with a weighted least squares formulation for an arbitrary fixed point in d R , and then move this point over the entire parameter domain, where a weighted least squares fit is computed and evaluated for each point individually. It can be shown that the global function ( ) f x , obtained from a set of local functions is continuously differentiable if and only if the weighting function is continuously differentiable. We can see (figure 2-15): in each location x a polynomial is computed using the least squares method, however, weighting the influence of the data points based on their distance. The value of this polynomial at x yields the functional approximation (left); the set of locally approximated function values, together, forms the approximated curve (right).

Figure 2 -

 2 Figure 2-15: Moving least squares

  Figure 2-16: Intersection cases

  Figure 2-18: Finding the intersection curve of two MLS surfaces

  2.1, and the type of ideal features in discrete geometry can be divided into point, straight line and plane as the same in GPS. Therefore, the situation characteristics, including location and orientation characteristics, both in GPS and discrete geometry can be described as what has been defined in[ISO 2005] (table 2-2).LocationOrientation point -point distance straight line -straight line angle point -straight line distance Straight line -plane angle point -plane distance plane -plane angle straight line -straight line distance plane -plane distance

  Both in GPS and discrete geometry, these situation characteristics are only distances, and used for association operation. The difference is that, in GPS the non-ideal features is continuous, but in discrete geometry the non-ideal feature represent in discrete features such as point, segment or triangles. The contrast can be illustrated in figure 2-19.

  Figure 2-19: The difference of distance between ideal and non-ideal feature

( b )

 b Point to segment distance. Given a point Y and a line L parameterized as ( ) X t P td , the closest point on the line to Y is the projection ( ) X t of Y onto the line for some parameter value t . The distance between a point and a segment is more this case. However, the projection of Y onto the line might not lie on the line segment S. The projection could lie behind the initial point or ahead of the final point of the segment.

Figure 2 -QV

 2 Figure 2-20: triangle domain D Figure 2-21: when ( , ) (0, 0) Q s t

Figure 2 -

 2 Figure 2-22: Various of level curves Figure 2-23: When ( , ) (0, 0) Q s t

  Figure 2-24: Domain for segment Figure 2-25: Definition of visibility of domain boundary

Figure 2 -

 2 Figure 2-26 made the above concept more clearly, and the figures are schematic, that means the two linear components are not necessary be perpendicular.

Figure 2 -

 2 Figure 2-26: Cases for the four edges of the domain

Figure 2 -

 2 Figure 2-27: Distance between two segments

  V P .As the solution to this consists of three values 0 0 0 ( , , ) u v t , then the solution space can be deemed as a three spatial dimensions, which is the domain of a finite triangular prism (figure 2-30).

Figure 2 -

 2 Figure 2-28: Distance between a segment and a triangle

  features' representation and operation. The real features are usually acquired by measuring instruments and represented as discrete point data. In this chapter, a new framework based on discrete geometry is developed for tolerance representation and operationalization of GeoSpelling.GeoSpelling defines ideal and non-ideal features to represent the shapes with and without geometrical variations. And it also defines six operations to process these features: partition, extraction, filtration, association, collection and construction. The corresponding shape representation and processing techniques in discrete geometry are investigated to handle the geometrical features and operation defined in GeoSpelling.The developed framework provides new convenient and executable solutions for feature representations and operations in GeoSpelling. As a representation of real features which include both random and systematic errors, Skin model is the kernel concept of GeoSpelling. The simulation of skin model based on discrete geometry and statistic analysis is thus investigated in the next two chapters.

  discussed in previous chapter, Skin model in GeoSpelling represents the non-ideal features associated with geometrical variations. Since the skin models are the geometrical objects the defined operations (partition, extraction, filtration, association, collection and construction) to process, skin model construction is one of the critical issues for operationalization of GeoSpelling. Skin model is a simulation of real shapes. The characteristics of real shapes should be considered for skin model shaping. Typically, the geometrical variations of the real surface to the nominal one are caused by two kinds of errors: random error and systematic error. Both of the two kinds of errors should be simulated in order to construct the complete skin model. A designed shape is always specified with geometrical tolerances. The simulated skin models should be located within the specified tolerance zones which can be constraints for skin model generation methods. This chapter presents the developed methods to simulate the skin model with random errors. The methods for skin model shaping with systematic errors will be discussed in the next chapter. In our research, we follow this hypothesis: the deviations caused by random errors follows Gaussian (normal) distribution, which is proven reasonable for mechanical applications [Bhu 85]. The Based on discrete representations of skin models and their discrete geometrical characteristics, three different methods are developed to shape the skin models with random errors: 1-D Gaussian-based, multi-Gaussian-based, and Gibbs-based. A comparative analysis of the three methods is discussed. This chapter is organized as follows: Section 3.2 discusses the discretization of continuous nominal shapes and the discrete characteristics of discrete shapes. Section 3.3 presents the developed methods for shaping skin models with random errors. Section 3.4 proposed the simulating methods of the skin model when considering the tolerance constraints. Section 3.5

  and conversion using tessellation criteria [Ruppert 95]. When the initial CAD model is topologically consistent [Hamri 10], i.e. when the CAD model is created in the same software as the polyhedral model and the shape of this model matches the tessellation requirements, it is easy to set up a tessellation process from the user point of view [Hamri 10]. Such cases only occur for simple shapes handled in a so-called integrated environment. However it is no longer efficient when the CAD model has an

  Tessellation techniques are often used to manage datasets of polygons and divide them into suitable structures for rendering and numerical analysis. A tessellation of the object that contains not only the coordinates and supporting triangle indices but other data such as the surface parameters (for the points) as well as the connectivity of the triangles assists the investigator in traversing through and dissecting the CAD representation of a part [Haimes 98].The use of tessellation techniques for solid models has been studied from different kinds of point of view. The hardware support for adaptive tessellation of Bezier surfaces is proposed by [Espino 07], and the high quality triangulations from CAD models are discussed in [Haimes 98]. In most cases, the solid model is tessellated for satisfying the rendering capabilities 98in the software application environment. In our work, we adopt tessellation technique to obtain the discrete structure of the solid CAD model.

[

  Zhao 10], a boundary representation (B-Rep) of mesh considers more adjacent relationships among the neighborhood than face-based representation by which a polygon mesh is represented only as a shared list of vertices and a list of faces. Many boundary representation research efforts have been reported, such as Winged-edge [Baumgart 75], Quad-edge [Leonidas 85], Half-edge [Eastman 82], etc.

  Figure 3-1: Half-edge data structure

From

  the very basic ones, such as Stanford Triangle Format (.ply) which represent just an indexed face set or Stereo-lithography or Stand Triangulation Language (.stl) an Object File Format (.off) which represent just a triangle soup, to such advanced ones, such as Virtual Reality Modeling Language or VRML (.wrl) which enable to represent single object as well as a complete scene with complete interaction. However our applications work only with set of points and meshes, and therefore, we are only interested in the formats to read and to store the mesh information. Two file formats are considered in our work. (a) STL file format (.stl) An STL file is a triangular representation of a 3D surface geometry. The surface is tessellated logically into a set of oriented triangles (facets). Each facet is described by the unit outward normal and three points listed in counterclockwise order representing the vertices of the triangle. STL is a file format native to many CAD softwares such as CATIA V5. It is widely used for rapid prototyping and computer-aided manufacturing. STL files describe only the surface geometry of a three dimensional object without any representation of color, texture or other common CAD model attributes. The STL format specifies both ASCII and binary representations.

Figure 3

 3 Figure 3-2: STL file format and the STL model

Figure 3

 3 Figure 3-3: OFF file format and the OFF model

Figure 3

 3 Figure 3-4: The neighborhood structure of point

Figure 3 - 5

 35 Figure 3-5 Vertex normal estimation basics

  are the weight coefficients corresponding to the normal vectors of facets i f . i A ( 1,... i N ) represent the area of the i -th triangle facet. (c) Shen's method [Shen 05].

  unit normal vector of the i th triangle facet. i ( 1, ... i N ) are the weight coefficients corresponding to the normal vectors of facets i f .

  the area of the i th triangle facet. i d ( 1,... i N ) are the distances between the vertex p and the barycenter of the i th triangle facet. Parameter N is the number of all the triangle facets adjacent to the given vertex.

  -6. The first two spheres (figure 3-6(a)(b)) are constructed by regular triangle mesh, and the third one (figure 3-6(c)) is constructed by irregular triangle mesh. The comparison among different vertex normal estimation methods is to evaluate the error deviation between the theoretical and the computed value of vertex normal. Theoretically, given a random vertex ( , , )

  Figure 3-6: Mesh structure

  Considerable research activities in discrete differential geometry have been ensued in recent years and many techniques have been developed [Taubin 95] [Meyer 02] [Steiner 03]. Based on the investigation of [Meek 00], these techniques can be classified into three main categories: local surface approximation based methods, discretization of continuous differential operators and formulas and tensor based methods.

  Figure 3-7: Discrete curvature estimation parameters

  3D topography of the surface of a manufactured part looks similar to a geographical terrain [Stout 10]. Prediction and modeling of surfaces which emulate complex geographical and geological shapes have been widely developed in geostatistics and spatial statistics applications [Cressie 93].The topic of rough surface simulation is also fundamental in modeling and empirical practices of the wear and friction literature. Two categories of techniques have been investigated by the wear and friction research community. The first entails the use of statistical, stochastic, or Monte Carlo methods to distribute characteristic values over a surface (point height, curvatures, etc.) [Patir 78]. 3D surface topography modeling mainly concentrates on random surfaces of Gaussian ordinate distribution [Reizer 11] or Gaussian Processes [Xia 08]. The second category employs fractal models [Blackmore 97]. There are also hybrid approaches that mix both statistical and fractal algorithms [Zou 07]. However, Surfaces simulated by fractals are different from their physical counterpart due to their homogeneous quality [Bakolas 03].Statistical approaches are physically intuitive and represent surfaces in a manner consistent with observation and measurement as well and physical based modeling [Peridier 11]. However, they fail to consider the multi-scale nature of rough surfaces Due to the discrete nature of shapes we are considering here and the discrete differential geometry characteristics of points such as normal and curvatures, statistical approaches are well adapted to model the skin model and the non-ideal features thanks to the rich analytical and sampling techniques of random variables.

  function of the cumulated density function (figure 3-8). The variable X = F -1 (U) has the cumulated density function F and U is a uniform random variable in the interval [0,1]. For the standard normal distribution, the inverse cumulated distribution function uses the error function erf(x) (see formula 3-15). The inverse of the error function can only be approximated.

Figure

  Figure 3-8: Density function

  inputs and the outputs are in a new distribution function. Box-Muller transformation [Box 58] allows us to transform uniformly distributed random variables to a new set of random variables with a Gaussian distribution The basic foundation of the transformation is as follows (formula 3-16) algorithms start with two independent random numbers 1 x and 2 x , which are uniformly distributed in the interval [0,1]. The transformation formula (formula 3-16) creates two new independent random numbers which have a Gaussian distribution with zero mean and a standard deviation of one.The third method is rejection sampling. This method belongs to the general field of Monte Carlo techniques, including Markov chain Monte Carlo algorithms that use acceptance/rejection to achieve simulation from the target distribution [Kalos 09].

Figure 3 - 9 :

 39 Figure 3-9: Principle of 1D-Gaussian method

Figure 3 - 10 :

 310 Figure 3-10: Skin model generated by 1D-Gaussian method

  -11. The ellipsoid reflects the scope of trivariate-Gaussian distribution acting on one point. It is a random vector and can be calculated by the probability density function of the 3D-Gaussian (formula 3-18).

Figure 3- 11 :

 11 Figure 3-11: Principle of 3D-Gaussian method

  Figure 3-12: Skin model generated by 3D-Gaussian method

  Figure 3-13: Convergence test of Gibbs method

  Figure 3-14: Skin model generated by Gibbs method

Figure 3 -[

 3 Figure 3-16: Constraints considered for skin model simulation

Figure 3 -Figure 3 MFigure 3

 333 Figure 3-17: Flatness tolerance zone

Figure 3 -

 3 Figure 3-20: Parallelism tolerance zone

Figure 3

 3 Figure 3-22: process flow of parallelism specification

FigureFigure 3

 3 Figure 3-23: Position tolerance zone

Figure 3

 3 Figure 3-25: Process flow of position specification

iM

  to evaluate the principal axis, which indicates the main variation direction of the surface variation. Then we rotate the point set i M with the input angle value , and then we evaluate if the point set i M satisfy other constraints such as orientation and position specification requirements, which depend on the input information. If the point set i M can satisfy the orientation and position constrains, then we can get the final skin model, otherwise we go back to the step of initial random point set generation and follow the procedures until all the conditions are satisfied.

Figure 3

 3 Figure 3-26: Translation between two coordinate systems

Figure 3

 3 Figure 3-27: Process flow for combining constraints

Figure 3 -

 3 Figure 3-28: Cylindricity tolerance zone

  Figure 3-29: Cylindricity tolerance zone

Figure 3

 3 Figure 3-30: Principle of vertex normal direction deviation test

Figure 3 -

 3 Figure 3-31: Mean value of vertex normal direction deviation

Figure 3 -

 3 Figure 3-32: Mean standard deviation value of vertex normal direction deviation

Figure 3 -

 3 Figure 3-33: Distribution of the data of vertex normal direction deviation

Figure 3

 3 Figure 3-35: Principle of volume deviation test

Figure 3 -

 3 Figure 3-36: Mean value of volume deviation

Figure 3 -

 3 Figure 3-37: Mean standard deviation value of volume deviation

Figure 3 -

 3 Figure 3-38: Distribution of the data of volume deviation

Figure 3 -

 3 Figure 3-39: Standard deviations of volume deviation

  Many techniques have been proposed to show non-ideal geometry effects and uncertainties in data visualizations [Forslund 09] [Sanyal 09]. However, their effectiveness in conveying meaningful information is not well investigated. A large variety of techniques are currently used in visualization applications, selecting the most appropriate visualization technique for a given data set is a non-trivial task. Different approaches have been designed for different types of data such as vector fields and particle systems [McLouglin 10].

  Figure 3-40 illustrates two examples. The first one is a gear model and the second one is a, comparing the skin model represented by point set and color scale, we can see that the later is more convenient for user to identify the deviations.

  Figure 3-40: RGB visualization based on vertex normal

  Figure 3-41: RGB visualization based on volume

(

  point-based and/or mesh-based). All the developed methods use this discrete nominal shape as reference but adding random deviations by different ways. For each given reference point, 1-D Gaussian method adds the random deviation along its normal direction based on 1 dimensional Gaussian possibility distribution; Multi-Gaussian method considers the random deviations in three dimensional space; Gibbs method calculates the new position of the given point by Markov Chain Monte Carlo simulation. The nominal shapes are usually specified with geometrical tolerances to indicate the acceptable geometrical variations from the nominal shapes. The specified tolerances can acts as the constraints to fix the generated skin model within the tolerance zones. The mentioned three methods (1-D Gaussian based method, Multi-Gaussian based method and Gibbs based methods) are modified to generate appropriated skin models with the specified tolerance constraints.

  product specification and verification. The two main axioms described in previous chapters highlight the combined effects of manufacturing variability and measurement uncertainty when considering a global view and consistent modeling of the skin model.In order to enrich the skin model when considering the deviations from the nominal or CAD model, we need to assess the geometrical deviations at many different scales and from the manufacturing and the measurement perspectives. In an early work, Dowling et al. [Dowling 97] pointed-out the lack of systematic manufacturing error considerations when assessing form deviations. Caskey et al. [Caskey 90] discussed the need for a catalog of typically occurring form errors for basic features produced by various manufacturing processes. Manufacturing and measurement geometric deviations or errors can be classified into two main categories, which are systematic and random [Henke 99] [Desta 03]. The systematic components called also bias are deterministic, predictable and reproducible. They are caused by imperfect manufacturing devices or measurement procedures and by the ambiguity on the use of actual rules and standards. The random components are caused by non-constant sources of error either in time or in space. Random errors are expressed by statistical methods.

  Henke et al. [Henke 99] introduced two models to describe form errors. One is an analytical model based on Chebyshev polynomials to model the axial errors and the other is Fourier series to model angular dependencies. Based on the Fourier series, Cho and To [Cho 01] proposed a harmonic roundness model to represent form deviations using Fourier series expansion. Mesay et al. [Mesay 03] represented systematic form error using a combination of Fourier components, and proved that this method can characterize a wide variety of the deviations. Huang and Ceglarek [Huang 02] proposed a discrete-cosine-transformation (DCT) method which is based on decomposing the error field into a series of independent error modes. Fourier series is the first used decomposition method used to define periods on circular [Cho 02].

  using a discretization of the ideal surface. Based on the value of the associated natural frequency, the model shapes are sorted with the different complexity orders, and this can help to analyze the form, undulation and roughness of a surface by the level of period of a flexure behavior. Based on this idea, Samper et al. [Samper 10] developed software based on (Finite Element Analysis) FEA to determine the model shapes. Kurfess and Bands [Kurfess 95] modeled the manufacturing error using a sequence of models based on statistical hypothesis testing of the fitted residuals. Yang and Jackman [Yang 00] evaluated form error using statistical method without independently analyzing the statistical properties of the associated residuals. Yang and Menq [Yang 95] reviewed form error as a deterministic component and random component. The random error was assumed to be spatially independent with a normal distribution for uncertainty parameters representing coordinate transformation elements. The deterministic component was supposed as the orthogonal deviation between nominal surface and the artificial surface, which obtained by the measuring machine.

  deviations based on shapes decomposition concept, and these work can classified into two categories [Samper 07]: explicit and implicit parameterizations. The explicit description of geometries is based on CAD modeling [Cubeles-Valade 98], which can be modified by limited parameters. The implicit geometries are defined by a parametric model, which can be discretized with elementary geometries [Gouskov 98].

( b )

 b These basic geometric shapes belong to quadric surfaces and are classified into four families: paraboloid, cone, sphere, cylinder and ellipsoid (see figure4-1), and the morphing operation is a combination of translation and rotation of the basic shapes.(c) And each simple basic shape is a result of the deviations on the vertex normal direction of a discrete plane.

Figure 4

 4 Figure 4-1: Types of systematic error of planar shapes

Figure 4

 4 Figure 4-2: Paraboloid simulation method

Figure 4 - 3 :

 43 Figure 4-3: Paraboloid simulation result

Figure 4

 4 Figure 4-4: Cone simulation method

Figure 4 - 5 :

 45 Figure 4-5: Cone simulation result

Figure 4

 4 Figure 4-6: Sphere simulation method

Figure 4

 4 Figure 4-7: Sphere simulation result

Figure 4

 4 Figure 4-8: Cylinder simulation method

Figure 4 - 9 :

 49 Figure 4-9: Cylinder simulation result

pIFigure 4 - 10 :

 410 Figure 4-10: Ellipsoid simulation method

Figure 4

 4 Figure 4-12: Rotation simulation method

Figure 4

 4 Figure 4-14: Taper simulation method

  Figure 4-16: Ellipsoid simulation method

Figure 4 -

 4 Figure 4-17: Ellipsoid simulation result

  Figure 4-18: Hyperboloid simulation method

Figure 4

 4 Figure 4-20: Banana-shape simulation method

  Acquiring a training set of observation shapes; (b) Determining the correspondence among the observation shapes, in order to establish the relationship of the training set; (c) Aligning the training set through registration operations; (d) Analyzing the principal components and establishing the statistical shape model.

Figure 4 -

 4 Figure 4-22: Principal axis estimation by PCA method

Figure 4 -

 4 Figure 4-23 illustrates the principle of coordinate system transformation calculation.

Figure 4 -

 4 Figure 4-23: Coordinate system transformation

  Figure 4-24: Alignment based on principal poses [Zhao 10]

  x W are invariants in a training set, the various shape models are obtained and determined by x b . Under Gaussian distribution assumptions as in [Hufnagel 09] [Ma 10], the variation range of each component of 3

1D

( a )

 a 32 type pseudo-landmarks: 1, 2,…, 32. (b) 48 type mathematical landmarks: 33, 34,…,80. The 32 pseudo-landmarks are placed at the boundary of the plane. The 48 mathematical landmarks are placed inside the plane (figure 4-25).

Figure 4 -

 4 Figure 4-25: Landmarks description

  . The CFP registration algorithm [Zhang 04b] is used to refine the initial registration result, and the correspondence of each point of a sample is determined. The scatter of the training set in the global coordinate system is illustrated in figure 4-26.

Figure 4 -

 4 Figure 4-26: Scatter of the nine samples

Figure 4 -

 4 Figure 4-27: Mean model

FormFigure 5

 5 Figure 5-1: The main interface of the software

Figure 5 - 2 :

 52 Figure 5-2: Menu specifications of the software

  figure 5.3) are computed using Latin Hypercube Sampling under the assumption of the independence of the variables and normal distributions [Stockinger 10b]. Ten samples are considered in this work.

Figure 5 -

 5 Figure 5-3 is the CAD model of the cross-shaped part, and its geometric specification is described in Appendix 1. In our work, we only focus on the skin model simulation of the bottom plane with the flatness specification constraint.

Figure 5

 5 Figure5-3: The cross-shaped part[Stockinger 10a]

Figure 5 -

 5 Figure 5-6 illustrates the tessellation result composed of 2392 points and 4550 facets.

Figure 5

 5 Figure 5-4: Segmentation of CAD model Figure 5-5: Bottom plane extraction

Figure 5 -

 5 Figure 5-7 illustrates three skin models of the bottom plane with a tolerance of flatness equals to 0.3mm.

Figure 5 - 7 :

 57 Figure 5-7: Skin models of bottom plane with flatness constraint

  Figure 5-8 shows the measured point set of the bottom plane of the cross-shaped part .The analysis of this point set is illustrated in figure 5-9 and Appendix 2.

Figure 5 - 8 :

 58 Figure 5-8: Measured point set of cross shaped part

  Figure 5-9: Analysis of measured point data of cross shaped part

Figure 5 - 10 :

 510 Figure 5-10: Skin model with systematic deviations

Figure 5 -

 5 Figure 5-12: Analysis of skin model with systematic errors

Figure 5 -

 5 Figure 5-13: Skin model with both systematic and random errors

Figure 5 -

 5 Figure 5-15: Analysis of skin model with both systematic and random errors

Figure 5 -

 5 Figure 5-18: Alignment of the training set

Figure 5 -

 5 Figure 5-19: The mean model of the training set

Figure 5 -

 5 Figure 5-20: Analysis of the mean model

  Based on the PCA technique, the deviation between the mean model and each model of the training set can be calculated by the covariance matrix and then the influence of each component can be detected. According to the two mean models simulated above and the statistical shape analysis method introduced in the previous chapter, new models can be predicted (see figure 5-23).

Figure 5 -,Figure 5

 55 Figure 5-23: The predicted models

  geometry based framework for geometrical operations in GeoSpelling and skin model simulation. A set of methods based on discrete geometry processing techniques are associated to provide solutions for the six geometrical operations defined in GeoSpelling: partition, extraction, filtration, association, collection and construction. This discrete or computational geometry based methods solve the operationalization of GeoSpelling in a convenient and executable way. Skin model is one of the foundation and kernel concepts of GeoSpelling. The simulation of the skin model is based on the nominal model of the shape, on random deviations and systematic deviations. Considering the point-based data are widely used in applications, the discrete skin model representations are applied in our research. Different discrete shape modeling methods are developed for skin model. Three different methods are developed to generate the skin models by adding random deviations to the discrete nominal model: 1-D Gaussian-based method, multi-Gaussian-based method and Gibbs based method. Firstly, the nominal shape is tessellated as discrete representations (point-based and/or mesh-based) from CAD model. The normal direction at each point on nominal shape is then estimated. Finally, 1-D Gaussian method adds the random deviation along a given point's normal direction based on 1 dimensional Gaussian possibility distribution; Multi-Gaussian method considers the random deviations in three dimensional space; while Gibbs method calculates the new position of the given point by Markov Chain Monte Carlo simulation. During the skin model simulation, the specified tolerances are used as constrains to locate the simulated skin models within the specified tolerance zone. Systematic errors are reproducible inaccuracies that are consistently in the same directions. Considering systematic errors usually follow some specified functions which can be traced and simulated, a group of predefined second order shapes are implemented as the constraints to simulate the systematic deviations. The shape group contains six basic shapes which are proven as the most likely shape the systematic error can follow. A set of methods are developed to adding systematic deviations based on the predefined shape group and the testing shows the reasonable results. Based on the complete skin model which includes random deviations and systematic deviations, a new method based on Statistic Shape Models is developed for skin model analysis and trend prediction. Firstly, a set of training skin models acquired from different sources. The corresponding landmarks are then searched and all the skin models are aligned together. The statistic shape model of the set of training skin models including mean model and covariance are computed. The statistic shape model provides a prediction to the trend of the skin models, which can be used to evaluate the real shapes. A modular software framework is developed to test and support the methods and algorithms developed in this thesis. The software framework is developed based on MS VC 8.0 platform, and it is also supported by OpenGL and GCAL libraries [CGAL]. A detailed case study of a cross shaped workpiece was presented. The skin models of the studied workpiece are simulated and generated by the developed software framework. The results are compared to real measured data and the simulated results of another FEA-based method. The comparative results provide that the proposed methods can provide satisfying performance.

  defined based on discrete geometry processing techniques. The corresponding methods used in discrete geometry for geometry representation and processing are associated to the feature (including ideal and non-ideal) representation and geometrical operations in GeoSpelling. The developed framework provides new convenient and executable solutions for feature representations and operations in GeoSpelling. A survey of the common used methods for discrete normal estimation is researched. In order to generate reliable estimation results, a comparative result is analyzed to specify the suitable applications of each method. Three different methods (1-D Gaussian method, Multi Gaussian method and Gibbs method) are developed to simulate the skin models by adding the random deviations. The three methods provide three different ways to add random deviations. All the three methods use the specified tolerances as constraints to determine the location and shape of the simulated skin model. The developed methods provide new ways and solutions for skin model simulation based on the discrete shape model techniques. New methods are developed to simulate the skin model considering systematic errors. A group of parametric second order shapes are implemented to simulate the shapes of systematic deviations. The shape elements in the group can be added and/or deleted according to different applications. The developed methods are convenient to implement and the testing results are proven satisfying. Based on complete skin model that includes both random and systematic errors, a new method based on statistic shape model is developed for skin model analysis and prediction. The developed method requires a set of training skin models from different sources as input. It can compute the statistic shape model considering the mean model and covariance, which provides a trend prediction of the new skin models.

  The random errors of skin models are simulated by Gaussian distribution, and only three kinds of methods are considered in our work. It should be employing other noise simulation methods to simulate the random errors, such as Perlin noise, Poission noise, etc. Tolerance specification. The tolerance specifications only consider the flatness, parallelism and position constraints, and it should be take into account other possible specifications. The tolerance specifications only satisfy the planar and cylindrical shapes, and it should be extant to other shape models. Systematic errors simulation. The systematic errors simulation methods only adapt the planar and cylindrical shape models, and it should be satisfy other kind of shape models. The regulation of basic shapes combination to simulate complex systematic errors should be considered. Edges connection of skin models. The skin model simulation methods are based on the local surface of a geometrical model. It should be considered how to connect each pieces of skin model to an entire skin model, since there are distortions on the connected edges.

Table 1 -

 1 1: MGDE and the degrees of freedom ...............................................................................19 Table 2-1: Boolean operations ........................................................................................................55 Table 2-2: Situation characteristics between ideal features.............................................................57 Table 2-3: Location characteristic...................................................................................................58 Table 2-4: Mathematical notation ...................................................................................................58 Table 2-5: symbols ..........................................................................................................................58 Table 2-6: Point to point distance....................................................................................................58 .....................59 Table 2-8: Concepts mapping between GeoSpelling and discrete geometry ..................................68 Table 3-1: Vertex normal of one marked point................................................................................82

	Tables

Table 3 -

 3

2: Average vertex normal of point set ................................................................................83

Table 3-3: Time performance ..........................................................................................................96 Table 4-1: Types of systematic error of cylinders .........................................................................132 Table 4-2: Skin model with form errors ........................................................................................138 Table 4-3: Training set .

.................................................................................................................146 Table 5-1: Performances of each systematic error simulation.......................................................157 Table 5-2: Comparison of two kinds of mean models...................................................................165

  variations in the context of product lifecycle. The critical characteristics of GeoSpelling are reviewed for comprehensive understanding. Consider shape with and/or without geometrical variations are the basis of GeoSpelling, the available

	shape modeling techniques are analyzed for ideal/non-ideal geometrical shape
	construction.
	GeoSpelling is proposed to handle both ideal geometries (e.g. CAD model or
	geometries without geometrical variations) and non-ideal geometries (e.g. actual parts
	or geometries with geometrical variations) based on 6 basis operations: partition,
	extraction, filtration, association, collection and construction. The common CAD
	software packages are mature to handle ideal geometries, but they are lack to handle

non-ideal geometries. However, the discrete shape modeling techniques which are based on discrete geometry provides solutions for non-ideal geometry processing. The mapping relationships between GeoSpelling and discrete geometry are established and analyzed.

  operation called extraction is used to identify a finite number of points from a feature, with specific rules [ISO 2005]. In discrete geometry terms, the technique of sampling can deal with this kind of problem. It links two aspects, one is the extraction Zhang 07] classified the extraction strategy into four kinds: grid extraction, stratified extraction, special curve and point extraction, and depending on the relationship between invariant class and extraction strategy to give the determination. For extraction size, it is based both on the sine wave function and Nyquist sampling theory and the result of point size for each cut-off wavelength is 7.

	In CMM measurement, four kinds of extraction methods were investigated:
	Hammersley sequence sampling, Halton-Zaremba sequence, Aligned systematic
	sampling, and Systematic random sampling [Kim 00]. British Standard BS7172
	recommended that the sample size can vary from 5~15 points for various individual
	shapes and features [Zhang 00]. Zhang et al. [Zhang 96] introduced neural network

location and the other is the extraction size. There is flock of the contributions, for geometrical specification Zhang et al. [Zhang 07] has proposed a method, and for CMM detection Kim [Kim 00] et al. introduced the corresponding approach.

Zhang [approach to determine the sample size for inspection of holes using process method, size of hole and tolerance band as factors. Li

[Li 98

] adopted rate-distortion theory to determine the number of measuring.

Table 2 -

 2

	MLS surfaces 1 S and 2 S is not represented adequately. Therefore, a set of sample points
	that lie on the intersection curve is explicitly computed and added to 1 Q Q , to obtain 2

1: Boolean operations For intersection curves: taking the union of 1 Q and 2 Q can not produce a point cloud that accurately describes the surface 3 S , since the intersection curve of the two

Table 2 -

 2

2: Situation characteristics between ideal features

Table 2 -

 2

3: Location characteristic

Table 2-4: Mathematical notation Table 2-5: symbols

Table 2 -

 2

6: Point to point distance

  Table2-7 shows the three possibilities. The direction vector , the difference of end points for the line segment. The parameter interval is [0, 1]. The value t is just as for the line, but for the segment it is tested against the parameter interval [0, 1].

	2 Distance ( , ) s t Q s t ( , )	( , ) T s t P	2	(2-11)
		For ( , ) s t D , this formula also can be denoted as formula 2-12
	is Distance ( , ) 1 0 2 s t Q s t as ( , ) Where: 0 0 a e e , b e e , 2 2 bst ct 0 1 c e e , 2 2 ds et f 2 1 1 0 ( Formula ) B P d e d P P Sketch map ( ) ( ) f B P B P .	,	e	1 ( e	(2-12) ) B P ,
		2 In calculus terms, the goal is to minimize ( , ) 2 0 Distance ( , ) Y S Y P Y Q s t over the domain D.
	Note: P 0 closest to Y. Q s t is a continuously differentiable function, the minimum occurs either at an Since ( , )
	P 0 interior point of D where the gradient 0 0 t P 1	Q	2(	, as bt d bs ct e	) (0, 0)	(that is,
	2 Distance ( , ) Y S inside the triangle) or at a point on the boundary of D. Y	0 Y P t d (	)	2
		Note: ( ) X t closest to Y. The gradient of Q is zero only when ( ) X t 0 < t 0 <1 P 0 P 1 2 be cd s ac b and	t	2 bd ad ac b	. If ( , ) s t D ,
						Y		2 Distance ( , ) Y S	1 Y P	2
							Note: P 1 closest to Y.
		P 0	t	0 1		P 1
								2
			Table 2-7: Closest point on a segment to a given point. Where	0 t d Y P 0 (	) /	d
		(c) Point to triangle distance. Given a triangle T with vertices {V0, V1, V2},
	described by parametrical expression as formula 2-10
	0 T s t B se te 1 ( , )			(2-10)
		For ( , ) s t D	{( , ) : s t s	[0,1], [0,1], t	s t	1}	,	0 B V , 0 e V V , and 1 0
	1	2	1

e V V . The distance between a point P and the triangle T can be deemed to the minimum distance, which is computed by locating the values ( , ) s t D corresponding to the point P`, the closest point on the triangle to P. The squared distance from any point on the triangle to P is as formula 2-11 then the minimum of Q is obtained. Otherwise, the minimum value must occur on the boundary of the triangle. To find the correct boundary, consider figure 2-20.

  will be in the range [0, 1], otherwise, the closest solution point will be outside that range, and thus need to check the other visible edge. The basic idea is to first compute the closest points of the infinite lines on which the segments lie, that is c s and c t . To compute the distance between segments, then the domains of s and t are restricted. So we need to find the points that minimize the squared distance function over the restricted domain, and these points will have parameter values that correspond to points on the boundary.

	0	d v dt	2		1 2 ( d u d td 0	1	)	(2-18)
			It can easily compute the closest points on the boundary edges by employing a
	little calculus. For the case of the edge	s	0	, it has	v	2	( u td	1	1 u td , ) ( )
	where	0 u P P . The derivative of this with respect to t gives as formula 2-14 1
	0	d v dt	2		1 2 ( d u td	1	)	(2-14)
			Then the minimum can be calculated as formula 2-15
	t		1 1 d u 1 d d					(2-15)
			If 0		t	1	, then this is the actual solution, otherwise, the actual solution is 1
	if	t	1	or	t		0	.
			In the case of the edge	t	0	is exactly analogous. In this case, it
	is	v	2			(		u sd	0	) (	0 u sd . The derivative of this with respect to s as formula )
	2-16
	0	d v ds	2		2	d	0	(	u sd	0	)	(2-16)
			Then the minimum can be calculated as formula 2-17
	s	0 d u 0 0 d d				(2-17)
			If 0		s		1	, then this is the actual solution, and otherwise, the actual solution is 1
	if	s	1	or 0 if	s			0	.
												2
			In the case of edge	s	1	, it has	v	0 u d td (	1	0 u d td . Taking the 1 ) ( )
	derivative with respect to t, then the deviation can be calculated as formula 2-18

c c s t . If only one boundary edge is visible, then that closest solution point

Table 2 -

 2

		GeoSpelling	Discrete geometry
	Features	Non-ideal feature	point, segment, triangle, point set, polyline,
			mesh
		Ideal feature	geometric shapes:
			plane, cylinder, sphere, …
	Characteristics	Distance	point to segment, point to triangle, segment to segment, segment to triangle
		Angle	segment to segment, segment to plane,
			plane to plane
	Operations	Partition	segmentation
		Extraction	sampling
		Filtration	outlier removal, filtering
		Association	approximation, interpolation
		Collection	Boolean operation (Union)
		Construction	Boolean operation (Intersection)

8: Concepts mapping between GeoSpelling and discrete geometry Since the fundament of applying discrete geometry theory to GeoSpelling is established, the next part of our work focuses on implement these algorithms to GeoSpelling model. Considering skin model is the basis concept defined in

  skin model simulation procedure proposed in our work follows the geometrical product design context. The skin model created using our method inherits the nominal model generated by CAD software. The procedure of creating skin model is that after tessellating the CAD model a discrete geometry product nominal model is obtained, which construct by mesh structure. We import this tessellate nominal model to our own system to generate the skin model. In order to satisfy product life cycle sequence and fulfill the technological and manufacturing demands, there are some requirements are considered in our system. Firstly, it can import tessellate model created by CAD software. Secondly, it can generate skin model, and thirdly, it can export the skin model. At last, it can support other operations defined in GeoSpelling.

Table 3 -

 3 sphere models and Zhao's method has a good behavior in irregular mesh model, while Gouraud's and Thumer's methods can offer the closet value in regular mesh case. From this testing we can roughly infer that Shen's method offers the smallest error in most cases.

	The average vertex normal testing method takes into account the mean vertex
	normal value of all the points. It reflects the global deviation between theoretical and
	computed vertex normal value. In this testing, we evaluate both mean value and
	standard deviation, and the first item reflects the average deviation while the second
	item reflects the distribution of this deviation. The testing result is illustrated in table
	3-2. From table 3-2 we can see, in case (a) and case (b), Shen method has the closest

1: Vertex normal of one marked point

For the result we can see that Shen's method provide the closest vertex normal value in different vertex normal value comparing to the other three methods, and this reflect that Shen's method is more suitable to the regular mesh structure case. In table 3-2 we can see, in case (c) Zhao's method provides the closest mean value, and this illustrates that Zhao's method has a good performance on the irregular mesh structure case.

Table 3 -

 3

2: Average vertex normal of point set

  Random variables' simulation is based on the random number generation techniques, which is used to design and generate a sequence of numbers without any

	Since the pseudorandom sequence is dependent on the initial value of the
	algorithm, these values have a periodicity. There are some investigations on the
	periodicity of the pseudorandom simulation. According to [Luby 96] if the internal
	state of a pseudorandom number generator is n bits, its period is no longer
	than 2 n results. However, in practice the output sequence is shorter than expected
	periods for some initial values, and this is an open problem for today's pseudorandom
	number generator.
	The result of the pseudorandom number generator can follow a certain
	distribution types of random variables, such as Gaussian distribution, uniform

patterns. Based on the application field, the random simulation techniques can be classified into physical and computational methods. A physical random number generator is based on a random atomic physical phenomenon whose unpredictability can be traced to the laws of quantum mechanics [

Tsoi 07

]. The computational random simulation numbers are obtained by computational algorithms, which produce long sequences of apparently random results. Actually, the computational random numbers are pseudorandom, and they are determined by the initial value of the algorithm [Fog 01]. Although pseudorandom number is not a true random number, the result sequences are quite closer to truly random ones by using hardware random number generators. The careful mathematical analysis in [

Peterson 98

] proved that a pseudorandom generation numbers are sufficiently random to suit the intended use. distribution, Perlin distribution [Wijgerse 07], Poisson distribution [Ronald 88], etc.

Table 3 -

 3

3: Time performance

Table 4 -

 4 In geometry, a taper is an object with a gradual thinning or narrowing towards one end. In our method, the taper is simulated form a tessellated cylinder model. The principle of this method is based on the hypothesis that the taper can be obtained by offsetting each point of tessellated cylinder model in the direction of its vertex normal,

	Taper	Concave	Convex	Banana

1: Types of systematic error of cylinders (1). Taper

Table 4 -

 4 table 4-2.

	Nominal model	Systematic deviation	Random deviation	Skin model

2: Skin model with form errors 4.

4. Statistical shape modeling

	Statistical analysis of shape variation or Statistical shape modeling (SSM) is
	commonly used for variability considerations in computer graphics, image processing
	and bioinformatics domains [Cootes 01]. The basic idea of this method is to establish,
	form a training set, the pattern of "legal" variation in the shapes and spatial
	relationships of structures in a given class of shapes. Statistical analysis is used to
	give an efficient parameterization of this variability, providing a compact

representation of shapes [Rhodri 08]. The key ideas underlying statistical shape analysis were developed by Kendall [Kendall 77] Bookstein [Bookstein 78] and Cootes [Cootes 01].

Table 4 -

 4

3: Training set

Table 5 -

 5 table 5-2. 2: Comparison of two kinds of mean models

	Items	Standard	Maximum	Minimum	Mean
	Data	deviation	deviation	deviation	deviation
	Measured data	0.0807	0.271	-0.195	1.21e-006
	Our method	0.0917	0.239	-0.133	1.4e-005
	FEA method	0.103	0.193	-0.177	-0.000794

Chapter 3 Skin Model Simulation and Visualization

Chapter 4

Statistical Shape Analysis for Skin Model (4). Statistical shape model

The principle of statistical shape model method is that based on statistical analysis, we extract the common characteristics of a training set, which is composed by different geometrical shape models, and establish the statistical model for the samples.

The mean model concept is proposed in the statistical shape model domain.

Suppose we have a collection of n discrete shapes (skin model): 1 2 , ,..., n X X X , and for each skin model the 1 X is a d dimension vector, where d is equal to the number of points composed a skin model. Since the skin model is calculated in the vector space, one may compute directly the empirical mean model using the method presented in

The covariance of this collection of skin models can be calculated through formula 4-24

The covariance matrix The eigenvalues reflect the variance of the principal components. When the principal component has the bigger eigenvalue, it means that this principal component reserve much more information of the initial sample. In our method, we select the principal components having bigger eigenvalues to simulate the initial sample vector using the first ( ) t t d maximal eigenvalues that fulfill the formula 4-26

Chapter 5

A Case Study deviations is equal to 0.0016, and this reflects these two models have quite similar distributions. The simulation methods of our method are satisfied in this study case.

Statistical shape modeling (1). Mean model

The training set considered here is composed of ten cross-shaped models is not suitable here. The pseudo-landmark technique is then adopted in our method.

For convenience, we use a matrix arrangement technique instead of integers to tag the landmarks as illustrated in figure 5-17. Each landmark corresponds to a unit grid, marked here as ( , ) i j which represents also a kind of pixel coordinates. Instead of using all the points, the landmark ( , ) i j refers to the mean point p of all the points inside the corresponding grid.

The training set considered here is anther ten cross-shaped skin models, which are obtained using the method introduced in section 5.3.1. The ten samples are illustrated in figure 5-21 and Appendix 4.