T Colleu

L Morin

S Pateux

C Labit

FLOATING POLYGON SOUP

Keywords: Multiview video plus depth, virtual view synthesis, 3D morphing, polygon soup

 which is appropriate for both compression, transmission and rendering stages. The floating polygon soup conserves these advantages while also taking into account misalignments at the view synthesis stage due to modeling errors. The idea for reducing these misalignments is to morph the 3D geometry depending on the current viewpoint. Results show that artifacts in virtual views are reduced and objective quality is increased.

INTRODUCTION

The year 2010 has seen the popularity of 3D video exploding, starting with the success of 3D movie 'Avatar' in cinemas in December 2009 and with electronic companies announcements of their 3D-ready televisions arriving at home. Here, the functionality that justifies the term '3D' is stereoscopy, where there is only one more image compared with traditional 2D video. But it is sufficient to show the potential of 3D video to improve the description of a scene and the feeling of depth for the users. Active research is now focused on multi-view video in order to increase the number of images of the same scene at the same time [START_REF] Schreer | 3D Videocommunication: Algorithms, concepts and real-time systems in human centred communication[END_REF][START_REF] Magnor | Video-Based Rendering[END_REF][START_REF] Do | Multicamera imaging, coding and innovative display: techniques and systems[END_REF]. Multi-view video brings mainly two functionalities to the users. The first functionality is free viewpoint navigation: similarly to the famous "bullet time effect" in the movie 'The matrix', the viewer can change the point-of-view within a restricted area in the scene, thus having a navigation functionality. The T. Colleu performed the work while at Orange Labs. This work is supported by the RUBI3 and PERSEE project second functionality is auto-stereoscopy: the viewer enjoys stereoscopic visualization without the use of special glasses. Multi-view auto-stereoscopy brings more freedom in terms of viewing position and number of users. These two functionalities raise new applications like FTV (Free viewpoint TV) and 3DTV.

The chosen representation plays a central role in a multi-view video system. Indeed, it influences the data load to be transmitted, the compression method to be used, as well as the computational complexity during the view synthesis stage and the final video quality at the display stage.

In this paper, we present an original representation for multiview videos that we call floating polygon soup. This representation takes as input multi-view video plus depth (MVD) data. It extends the previously proposed polygon soup representation [START_REF] Colleu | A polygon soup representation for multiview coding[END_REF] which is appropriate for both compression, transmission and synthesis stages. The floating polygon soup conserves these advantages while also taking into account artifacts at the synthesis stage.

Section 2 gives a state-of-art about depth imagebased representations and related view-synthesis issues. In section 3, an overview of the previously proposed polygon soup representation is given. The floating polygon soup representation is described in section 4. Section 5 presents quality evaluation of intermediate view synthesis obtained with the proposed representation and discusses the issues raised by our representation.

STATE OF ART

Depth image-based representations. Existing representations for multi-view video often contain some geometric information about the scene in addition to color information, such as depth image-based representations. A depth map is an image that associates one depth value (i.e. the distance to the camera) to each pixel. It enables to synthesize intermediate views using a perspective projection method. A depth-based representation can be composed of a single viewpoint (a.k.a 2D+Z [START_REF] Fehn | An evolutionary and optimised approach on 3D-TV[END_REF]) or multiple viewpoints (Multiview Video plus Depth MVD [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF][START_REF] Smolic | Intermediate view interpolation based on multiview video plus depth for advanced 3D video systems[END_REF]). Moreover, in order to deal with the compromise between data load due to multiple viewpoints and image quality, the Layered Depth Video (LDV) selects a certain view as reference and extract, from the other views, only the information which is not contained in the reference view, i.e. the occluded areas [START_REF] Müller | Reliability-based generation and view synthesis in layered depth video[END_REF].

Depth maps compression. Depth maps are gray level images, so they can be compressed with an efficient video codec such as H.264. However, depth maps describe the surface of a scene and have different properties compared to an image describing the texture. Therefore, synthesizing intermediate views using compressed depth maps creates visually disturbing artifacts, especially around depth discontinuities (objects boundaries) as studied in [START_REF] Merkle | Multi-view video plus depth representation and coding[END_REF]. With this in mind, several approaches have been proposed to compress depth maps while preserving depth discontinuities [START_REF] Merkle | The effect of depth compression on multiview rendering quality[END_REF][START_REF] Maitre | Shape-adaptive wavelet encoding of depth maps[END_REF][START_REF] Yea | Multi-layered coding of depth for virtual view synthesis[END_REF].

Depth based view synthesis. Synthesizing intermediate views using depth maps is generally performed using a point-based method: each pixel is independently reconstructed in 3D and then re-projected into the desired intermediate view. As a result, many small holes appear in the intermediate view and must be filled with post-processing techniques [START_REF] Smolic | Intermediate view interpolation based on multiview video plus depth for advanced 3D video systems[END_REF]. An alternative is to transform the depth maps into a 3D surface using geometric primitives such as triangles [START_REF] Zitnick | High-quality video view interpolation using a layered representation[END_REF] or quadrilaterals [START_REF] Evers-Senne | Modelling and rendering of complex scenes with a multicamera rig[END_REF] and to disconnect these primitives at depth discontinuities so that the background and foreground are not connected. This solution eliminates the post-processing stage but requires a graphic processor.

During intermediate view synthesis, multiple images are warped or projected into the novel view. A combination strategy is needed to obtain one texture from multiple candidates [START_REF] Bornik | High-quality texture reconstruction from multiple views[END_REF]. View-dependent combination of the multi-images into the novel view provides better photo-realism and helps to reproduce non-Lambertian reflectance effects [START_REF] Debevec | Modeling and rendering architecture from photographs: a hybrid geometry-and image-based approach[END_REF][START_REF] Buehler | Unstructured lumigraph rendering[END_REF]. In addition, special processing of the occlusion boundaries is used to reduce so-called ghosting artifacts in the novel views [START_REF] Smolic | Intermediate view interpolation based on multiview video plus depth for advanced 3D video systems[END_REF][START_REF] Eisemann | Floating textures[END_REF].

Modeling errors. However, due to modeling errors, images are not warped or projected to the expected position into the novel view, creating local texture misalignments. These misalignments appear in the form of texture deformation if only one image is used, or splitting and blur if multiple images are combined.

Existing solutions correct texture misalignments through matching and warping techniques. Floating textures [START_REF] Eisemann | Floating textures[END_REF] have been proposed for correcting these misalignments during view synthesis. The idea is to compute motion flow between synthesized textures coming from multiple views (matching step) and then use the estimated flow to warp them onto each other so that to reduce texture misalignments (warping step). A similar method was proposed by Takai et al. [START_REF] Takai | Harmonised texture mapping[END_REF]. In this method, the computation of texture coordinates is reduced to only vertex positions instead of computed motion flow over the whole images. This is computed as a pre-processing step together with a mesh optimization process. Furihata et al. [START_REF] Furihata | Novel view synthesis with residual error feedback for ftv[END_REF] proposed another solution to compute texture correction in a pre-processing step. They compute intensity residual error of each view projected into another one (differencing step rather than matching). Then during view synthesis, the residual error is fed back into the virtual view and processed according to the virtual position (addition step rather than warping). The main difference with the previous methods is that texture misalignment is computed in terms of intensity error instead of motion field which is computationally less expensive but may be less efficient for correcting misalignments.

Finally, in the temporal domain, there are also methods that match and morph the geometry across time in order to reproduce objects motions. Vedula et al. [START_REF] Vedula | Image-based spatio-temporal modeling and view interpolation of dynamic events[END_REF] introduced the 3D scene flow with a volumetric representation. The 3D scene flow gives the motion of each voxel of the representation between two frames of the video. It is computed using 2D motion flow and 3D data. The aim is to reproduce the motion of the scene, but it can also be thought as a problem of texture misalignments between two images of different time instant, similarly to texture misalignments between two views.

The purpose of this paper is to correct texture misalignments due to modeling errors. The proposed method, called floating polygon soup consists in morphing 3D geometry depending on the current viewpoint. Morphing the geometry enables to keep the same texture coordinates for each 3D point, on the contrary to warping 2D textures. The representation that we used to evaluate this method is the polygon soup [START_REF] Colleu | A polygon soup representation for multiview coding[END_REF]. The next section gives an overview of this representation.

POLYGON SOUP REPRESENTATION

Overview

We propose to construct, from the input MVD data, a representation called polygon soup (figures 1 and 2).

3D polygons. First of all, the rendering primitives are 3D polygons. Polygonal primitives have several advantages: they increase compactness by adapting their size to the surface, they model the continuity of the surface, and graphics processors are optimized to render them. Moreover, all the 3D polygons are not necessarily 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 connected to each others and can overlap, forming a kind of mixture of polygons which is often called a polygon soup. Here, the disconnection feature is very important. First, it ensures that foreground and background objects are not connected, thus preserving depth discontinuities. Second, it allows to easily remove redundant or unreliable polygons, thus increasing the compactness. The overlapping feature is also a key point. Since multi-texture and multi-geometry are available from the input data, overlapping polygons (i.e. coming from different views) can be selected or merged depending on the desired viewpoint, thus ensuring view-dependent quality of virtual views. In a word, disconnection and overlapping allow to play with the compactness and image quality tradeoff by removing unnecessary polygons and overlapping necessary ones. Figure 2 shows an example of such 3D polygons that can overlap and be disconnected.

Stored in 2D.

The representation forms a 3D polygon soup at the view synthesis stage. However, for compactness and compression efficiency, the polygons are stored in 2D with depth values at each corners. These 2D polygons are extracted from the depth maps using a quadtree decomposition method. These 2D polygons are also called 'quads'. Figure 3 shows an example of 2D quads extracted from MVD data and for 3 views. The decomposition of the depth maps into quadtree allows to retrieve the (x, y) positions of the quads, thus a compression method exploiting this structure can be employed. Each leaf of the tree corresponds to a quad. Using this structure, it is easy to remove redundant polygons by pruning the corresponding leaf in the tree. Moreover, the decomposition can be adapted to the geometry of the scene such that large quads approximate flat surfaces and small quads preserve geometric details and discontinuities.

Textured by the images. The texture of the polygons is given by the original images: the block of pixels in the image corresponding to a quad is mapped onto the 3D polygon using texture mapping techniques supported by graphics hardware. Since, multiple images are available, it is possible to texture the polygons with multiple textures depending on the view-point. This results in a multi-textured appearance of the polygon that better reproduces specular effects of real-world scenes. In addition, this kind of multi-view videos can be efficiently compressed using the standardized H.264/MVC compression method. Finally, transmitting the original views ensures maximum image quality at original view-points.

Processing steps

Using such a polygon soup involves several processing steps for constructing this representation, compressing it, and synthesizing virtual views. These different steps are listed:

• Construction: Depth estimation; Quadtree decomposition; Redundancies reduction.

• Compression: QuadTree-based compression or block-based compression

• View-synthesis: Polygon warping; Texture mapping; Post-processing; Quadtree decomposition (if block-based compression)

Properties

The proposed polygon soup can be analyzed in terms of general properties:

• Construction complexity: Most of the complexity is transfered to the construction of the representation in order to achieve compactness, and to decrease view synthesis complexity.

• Compactness: Compactness is achieved by keeping the number of polygons low and reducing interview redundancies.

• Compression compatibility: A new quadtree-based compression method has been introduced in [START_REF] Colleu | A polygon soup representation for multiview coding[END_REF] for the polygon soup. However, block-based compression is also possible providing that the quadtree decomposition step is transferred at the user side of the system.

• View synthesis complexity: Virtual views are synthesized using graphics hardware and polygonal primitives. Polygons avoid the apparition of sampling artifacts compared with depth-based view synthesis, thus the view synthesis complexity is lower. Moreover, since unreliable polygons are removed during the construction of the representation, the polygon soup reduces the so-called ghosting artifacts and thus no additional process are required to avoid them. Additional process like hole filling and filtering are still required for high image quality.

• Navigation range and image quality: Original views are preserved ensuring maximum quality at original viewpoints. Navigation in between original views is done by view-synthesis using the polygon soup as the geometry of the scene. However, because of modeling errors, texture misalignments appear in the synthesized views and reduce the final image quality. Therefore, the next section presents a new method to reduce these texture misalignments.

FLOATING POLYGON SOUP

This section presents a method to reduce modeling errors that create artifacts in the synthesized images. Starting from n views and associated polygon soup, the idea is to deform each polygon depending on the current viewpoint. We call this: Floating polygon soup. The proposed method is divided into two steps: matching and morphing. The matching step consists in matching 3D geometries pairwise while using an image registration constraint. This matching step can be seen as a preprocess before the synthesis of arbitrary viewing positions. Then, the morphing step consists in interpolating the geometries between their matched correspondences according to the current viewing position. It thus realizes view-dependent geometry. View-dependent texture is also performed, as all views are projected into the current viewing position and blended to allow for smooth combination.

Figure 4 summarizes the floating geometry method for virtual view synthesis.

Synthesized view Multi-geometry 3D matching with image registration constraint

View-dependent synthesis

Virtual view

Viewing position

3D morphing

Multi-view + Fig. 4. Overview of the floating geometry method for virtual view synthesis.

We use the following notations:

• a view point V i is defined as a pair (G i , I i ), where G i defines geometry (depth map, 3D model,..) and I i is the acquired color image also used as a texture image.

• π i () and π -1 Gi () denote projection on view V i and backprojection from view V i using G i .

• I j i (resp. G j i ) denotes the image (resp. geometry) from view V i projected in view V j .

• W I1→I2 is the motion flow between I 1 and I 2 .

3D matching with image registration constraint

We consider n original views V i = (G i , I i ) i=1,n , where geometry is assumed already estimated for each acquired image, for instance as a 3D model or a depth map. The matching step consists in defining a point to point correspondence between any pair of geometries (G i , G j ) based on image registration between I i and I j .

The process is illustrated on Figure 5. View V i is first projected into view point V j using geometry G i to produce projected image I j i :

I j i = π j (π -1 Gi (I i )) (1)
As explained earlier, image I j i is not aligned with I j . We thus estimate the flow field W I j i →Ij compensating for image misalignment in V j . It is then used to warp I j i , and the resulting image is back-projected in 3D using geometry G j to obtain the floated geometry G j i . That is :

G j i = π -1 Gj (W I j i →Ij • I j i ) (2)
G j i is consistent with G j , i.e. it provides same geometry information, but each point in G j i is associated with a point in G i thanks to this definition. Moreover, the projection of V i into V j using G j i is aligned with I j , i.e. it performs same image registration as applying optical flow on I j i . Thus when synthesizing view V j , 3D vertex P i with texture p i is floated to 3D vertex P j i and then projected into V j on point p j . As P i and P j i have been matched in order to represent the same physical 3D point, texture blending using texture points p i and p j will not generate misalignments in the synthesized view V j . Fig. 5. Computation of a matching vertex. P i is projected in V j giving p j i which is matched with corresponding pixel p j . Finally, p j is back-projected to the approximate geometry resulting in the 3D point P j i .

View-dependent 3D morphing.

Once matched geometry G j i has been computed for all pairs of views in a pre-processing step, then the geometry can be floated for any virtual view during the view synthesis stage. The key point here is to ensure texture alignment by keeping the geometries consistent with each other. An intermediate geometry G v i that depends on the position of the virtual view is thus computed. To do so, let V l and V r be the two original viewpoints closest to the virtual view V v (called "left" and "right" views for simplicity). Let V i be the current view to be projected into V v . The floating geometry for each vertex in V i has already been computed for left view V l and right view V r , namely G l i and G r i . Then the computation of G v i consists in interpolating the geometry between G l i and G r i , vertex by vertex:

G v i = ω l G l i + ω r G r i ( 3
)
where ω is a weight associated to the position of the current viewpoint. It can be defined using interpolation method between two original cameras (SLERP) [START_REF] Shoemake | Animating rotation with quaternion curves[END_REF] or by angular weighting scheme [START_REF] Buehler | Unstructured lumigraph rendering[END_REF][START_REF] Debevec | Modeling and rendering architecture from photographs: a hybrid geometry-and image-based approach[END_REF]. A smooth deformation of the geometry is obtained as the virtual view moves from one original view to another. Figure 6 illustrates this view synthesis step using the same example as in the previous figure. The view being projected is V i and the left and right views around the virtual view are V l = V i and V r = V j . The 3D vertex P i is floated onto an intermediate position P v i = ω i P i + ω j P j i . Finally, P v i is projected into the virtual view, giving the pixel p v i .

Fig. 6. Virtual view synthesis with floating geometry. Vertex P i is floated to an intermediate position P v i between P i and P j i , then it is projected to the virtual view giving pixel p v i .

This process is repeated for each view and associated geometry as illustrated in figure 7 where G i and G j are floated to G v i and G v j respectively. As a result, floated geometries are consistent with each other: they only differ by a change of vertices (remeshing) and texture misalignments are reduced both when synthesizing original views and virtual views.

EXPERIMENTS

In our previous work [START_REF] Colleu | A polygon soup representation for multiview coding[END_REF], the polygon soup has been compared to MVC-H264 (intra-mode) for coding depth information, showing that rate/distorsion performances are competitive on tested data. In this section we evaluate the performances of the floating method with regard to the quality of the synthesized images. Two tests have been done on views V 1 , V 3 and V 5 of Breakdancers and Ballet sequences 1 . The first test operates on the Fig. 7. Virtual view synthesis with floating geometry. G i and G j are floated to G v i and G v j respectively. As a result, the geometries are consistent with each other, and texture misalignments are reduced. full polygon soup (i.e. before the redundancy reduction step), and the second test is performed on the reduced polygon soup. The quality of the synthesized view was evaluated with and without application of the floating polygon soup method. For objective evaluation purpose, the novel view is located on original camera viewpoint V 2 and V 4 such that an error metric is used for comparison. The Peak-Signal-To-Noise PSNR metric distortion is used here (log function of inverse MSE). Motion estimation was performed using Urvoy et al. [START_REF] Urvoy | Motion tubes for the representation of images sequences[END_REF] algorithm. This motion estimator uses variable size block matching with some regularization.

Figure 8 shows typical misalignments artifacts observed when using the full polygon soup without floating geometry. As expected, blurring and splitting artifacts appear due to texture misalignments. In (a), a blur artifact is shown: the boundary of the hand is blurred. In (c), a splitting artifact is shown: the white line is split in two instead of being one. After applying the floating method, we can observe that these artifacts are reduced. The hand appears sharper and the white line corrected.

The second experiment consists in applying the floating method on the reduced polygon soup. It can thus be performed after transmission, at the user side of the system. Figure 9 shows the evaluation results. Subfigures (a),(b) and (c) give respectively the synthesized view without floating geometry, the original view, and the synthesized view with floating geometry. Subfigures (d), (e) give the images of difference between synthesized views and the original ones. The darker a pixel, the higher the error. Artifacts due to texture misalignments can be observed in the view synthesized without floating geometry (subfigures (a) and (d)): we can see in (d) that errors are visible mainly at texture edges. Results of the floating geometry approach can be seen in (c) and (e). We can see that texture misalignments around edges have been reduced. In (c), the deformation of the face (right cheek of the character) has been corrected.

Tables 1 and2 give the PSNR values obtained for One can notice that the earing of the character in the original view is not reproduced in the synthesized views. This is a non-Lambertian reflective effect that is not visible in either of the views used for the synthesis. Therefore, floating geometry cannot compensate such an effect.

The matching step of the floating method could be computed either at the acquisition side of the system or at the user side. In the first scenario, the additional information involved by the matching should be transmitted and therefore increasing the data load. In the second scenario (i.e. at the user side), the synthesis complexity is increased instead of the data load.

CONCLUSION

This paper has presented a representation for multiview videos. It extends the polygon soup representation previously proposed by reducing texture misalignment due to modeling errors. The method is called floating polygon soup. It consists in floating the geometry depending on the current viewing position such that texture misalignments are reduced. To do so, two steps are computed: matching and morphing. As a result misalignments are reduced and objective quality is increased. The main limitation of this method comes from its dependency on the quality of motion estimation (e.g. when high misalignments are present in the image).

In the future, a method for coding the additional floating geometry information will be studied, and an acceleration of the method will be tested using graphics hardware capabilities. Moreover, the floating geometry can be extended to the temporal domain and used for temporal prediction and coding.

Fig. 1 .

 1 Fig. 1. Polygon soup. Each 3D polygon is defined by a 2D polygon (quad), and by the depth information at each corner of the quad.

Fig. 2 .

 2 Fig. 2. Example of a polygon soup, seen from an arbitrary viewpoint (without texture).

Fig. 3 .

 3 Fig. 3. Example of polygon soup stored in 2D. Top line: final set of selected quads in each view. Bottom line: associated color information.

Fig. 8 .

 8 Fig. 8. Examples of artifacts observed with the full polygon soup: Blur (a) and splitting (c). Results after applying floating polygon soup (b) and (d).

Fig. 9 .

 9 Fig. 9. Comparison of a synthesized virtual view without and with floating geometry.

Table 1 .

 1 Comparison of PSNR values without and with floating geometry using three views and reduced polygon soup.

	Breakdancers no floating	floating ge-	gain
		geometry	ometry
	virtual view	35.29 dB	36.51 dB	+1.22 dB
	V2
	virtual view	34.65 dB	36.24 dB	+1.59 dB
	V4
	Ballet	no floating	floating ge-	gain
		geometry	ometry
	virtual view	33.71 dB	35.00 dB	+1.29 dB
	V2
	virtual view	35.27 dB	36.80 dB	+1.53 dB
	V4

Table 2 .

 2 Comparison of PSNR values without and with floating geometry using three views and reduced polygon soup. virtual views V 2 and V 4 and sequences Breakdancers and Ballet. For Breakdancers, the PSNR measure has increased by 1.22 dB (from 35.29 dB to 36.51 dB) for virtual view V 2 , and by 1.59 dB (from 34.65 dB to 36.24 dB) for virtual view V 4 . Similarly, for Ballet sequence, the PSNR measure has increased by 1.29 dB (from 33.71 dB to 35.00 dB) for virtual view V 2 , and by 1.53 dB (from 35.27 dB to 36.80 dB) for virtual view V 4 .

Thanks to the Interactive Visual Media Group of MicrosoftResearch for providing the data sets


Jianhua Fan
email: jianhua.fan@gmail.com

Alan Ball

Taylor & Francis

Integrated method for tool path generation in five-axis sculptured surface machining

Keywords: CNC MACHINING, CAM, MACHINING PROCESSES Five-axis, Machining, Tool path generation, Cutter orientation, Machined strip width Five-axis, Machining, Tool path generation, Cutter orientation, Machined strip width

Five-axis machining allows continuous adjustment of cutter orientation along a tool pass. Unfortunately, the flexibility has not been fully exploited due to the separate consideration of tool path generation and cutter orientation in current machining methods. This paper presents an integrated method (IM) for tool path generation, which is tightly integrated with the orientation strategy, to minimise tool path length under the constraint of smooth cutter orientation. Distinctively, cutter orientation along a tool pass is optimised by balancing considerations of maximum material removal and smoothness of cutter movement. Further, the intervals between successive tool passes are maximised according to the optimised orientation. In the paper, the IM is combined with the quadric method, a recently developed cutter orientation strategy, for iso-parametric machining with a flat-end cutter. However, the method could be applied to other orientation strategies with different machining mechanisms and cutter types. Simulated examples illustrate that the IM is more efficient in machining than established methods.

Introduction

Five-axis machining has been increasingly used in the manufacture of sculptured surfaces. Compared to 3-axis machining, it provides two extra degrees of freedom, which allow continuous adjustment of cutter orientation along tool passes. Consequently, a significant improvement in machining efficiency and surface finish can be achieved [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF]. Unfortunately, these benefits have not been fully realised due mainly to limited geometric research on surface manufacturing [START_REF] Yoon | Locally optimal cutting positions for 5-axis sculptured surface machining[END_REF]. One key issue in tool path generation is how to optimise the two orientation angles along tool passes for maximising the machining efficiency.

Much research effort has been concentrated on optimising cutter orientation at one cutter contact (CC) point to locally maximise material removal [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. However, the local solutions are not guaranteed to vary smoothly along each tool pass. Accordingly, there can be abrupt changes in cutter movement. Such abrupt changes may generate self-intersections and twists on the surfaces swept by the cutter, which lead to poor surface finish and low machining accuracy. Also, the abrupt changes induce rapid increases of cutting force, which might even damage the machined surface, cutter and machine tool. Thus, both material removal and cutter movement need to be considered in determining cutter orientation along the tool passes and, ideally, the cutter orientation and tool path generation should be integrated. Unfortunately, they are approached as two separate tasks in current machining methods.

As a contribution to improving machining efficiency, this paper develops an integrated method (IM) for tool path generation, which is tightly integrated with an orientation strategy. In the IM, cutter orientation is optimised by balancing considerations of maximum material removal and smoothness of cutter movement. Further, each successive tool pass is positioned as far as permissible from the preceding one. Then numerical simulations, comparing the IM with existing methods, show a significant reduction in the number of tool passes.

Basic assumptions and concepts

To avoid ambiguity in the discussion throughout the paper, some basic assumptions and concepts of cutter orientation and tool path generation are introduced in this subsection.

The scope of the research is limited to a geometric study of surface machining under the following assumptions:

• Design surface S(u, v) is a sculptured surface defined on a unit square (0 ≤ u, v ≤ 1) with curvature continuity (G 2 ) [START_REF] Farin | Curves and surfaces for CAGD -A Practical Guide[END_REF]. This encompasses all (non-degenerate) cubic and higher order B-spline/NURBS surfaces, but any compound surface [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF] with lower order continuity or irregular topology has to be machined patch-by-patch. • Cutter is a flat-end cutter and its spindle speed is much higher than the feed rate.

Thus, material can be considered to be removed by the sweeping motion of a cylindrical surface, the cutter surface C. • Cutter size has been selected appropriately [START_REF] Jensen | Tool selection for five-axis curvature matched machining[END_REF].

• Potential collisions on the side of C have been avoided by restricting the cutter orientation, but possible interference on the bottom of C needs to be checked. • Step-forward distance is sufficiently small and tool passes P i , i = 1, . . . , n, along which C moves on S, are parametric curves of S. Thus, iso-parametric machining [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF] • Allowable deviation of the machined surface M from S, referred to as machining tolerance ε, is positive and consistent with that in the finishing stage [START_REF] Rao | On local gouging in five-axis sculptured surface machining using flat-end tools[END_REF].

Cutter orientation is used to specify how C is placed relative to S at their contact point, the cutter contact (CC ) point. As depicted in figure 1, the orientation is described in a local machining coordinate system (LMCS, X M -Y M -Z M ), where the Z M -axis is along the surface normal N and the X M -axis is in the cutting direction. The cutter is first rotated a lead angle α around the Y M -axis, and then a screw angle β around the Z M -axis. In general, 0 ≤ α ≤ π/2, -π/2 < β < π/2, but may be further restricted by collision avoidance. Cutter orientation can be assessed locally by the machined strip width w, which is defined as follows: Let an error surface E denote the offset of S by a distance ε. Then an area on E bounded by the intersection curves with C is a machined region G. The maximum span of G along the Y M -axis is the width w. For machining efficiency at the CC point, an optimal orientation is desired to maximise w and give no gouging.

S C X M Y M Z M P i P i-1 β α N CC point
As C moves along P i , it sweeps out a cutter swept surface W i . A sequence of W i removes material to generate the machined surface M. To ensure the machining deviation, the distance from M to S, is smaller than ε, M must lie between S and E. Define an area on E bounded by the intersection curves with W i as the machined strip I i . Then the strip I i can also be considered as an envelope of the machined region G. The strip I i , region G and width w are intuitively defined in Euclidean space. However, in iso-parametric machining, it is convenient to define them in the parametric space of S. Thus, the machining can be considered as a process of overlapping a sequence of machined strips in the parametric space as illustrated in figure 2.

To improve the machining efficiency in iso-parametric machining, the length of tool path or, equivalently, the number of tool passes needs to be reduced. Accordingly, research is directed to maximising the widths of individual strips I i and the step-over distances between successive strips I i-1 and I i , whilst ensuring there are only smooth changes in the cutter orientation and no gaps between the strips.

I i I i-1 G Figure 2.
Overlapping machined strips in parametric space of design surface

Previous work

There has been much research effort to optimise the cutter orientation at a CC point in 5-axis sculptured surface machining. The published algorithms can be classified broadly into local and global methods [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. In the local methods [START_REF] Vickers | Ball-mills versus end-mills for curved surface milling[END_REF][START_REF] Bedi | Principal curvature alignment technique for machining complex surfaces[END_REF][START_REF] Rao | On local gouging in five-axis sculptured surface machining using flat-end tools[END_REF][START_REF] Jensen | Tool selection for five-axis curvature matched machining[END_REF][START_REF] Yoon | Locally optimal cutting positions for 5-axis sculptured surface machining[END_REF], only normal curvatures of C (or W i ) and S are considered to orient C. The main disadvantage of the local methods is that there could still be rear gouging, and consequently a secondary iterative gouge-check and correction algorithm has to be implemented [START_REF] Gray | Arc-intersect method for 5-axis tool positioning[END_REF]. The global methods overcome the disadvantage by using an area of S beneath C to determine the orientation [START_REF] Warkentin | Multi-point tool positioning strategy for 5-axis machining of sculptured surface[END_REF][START_REF] Gray | Rolling ball method for 5-axis surface machining[END_REF], 2005[START_REF] Hosseinkhani | Penetration-elimination method for five-axis CNC machining of sculptured surfaces[END_REF][START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. In particular, the quadric method (QM) [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF] exploits fully the orientation angles (α, β) with respect to the machined strip width w. Further, the width evaluation is involved in the method, and its approximation error is conservative and acceptably small. Thus, it is adopted to orient the cutter along tool passes in this study.

Cutter orientation only aims to maximise the material removal at one CC point in a specified cutting direction. The distribution and ordering of CC points over the entire design surface is studied in tool path generation. In general, a tool path can be topologically classified as a raster or a spiral pattern [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF]. The spiral tool path keeps the cutter continuously removing material but is more restricted in its applicability. For machining a general sculptured surface, the raster pattern is always adopted and the tool path can be further categorised as an iso-parametric, iso-planar or iso-scallop method of construction [START_REF] Chiou | A machining potential field approach to tool path generation for multi-axis sculptured surface machining[END_REF]. The iso-scallop method has a shorter tool path than the others [START_REF] Chiou | A machining potential field approach to tool path generation for multi-axis sculptured surface machining[END_REF][START_REF] Li | Efficient five-axis machining of free-form surfaces with constant scallop height tool paths[END_REF][START_REF] Tournier | Iso-scallop tool path generation in 5-axis milling[END_REF], but may have more broken tool passes and fail to converge in the numerical computation (Rao et al. 2000, Tournier and[START_REF] Tournier | Iso-scallop tool path generation in 5-axis milling[END_REF]. Therefore, the iso-parametric and iso-planar methods are most widely and almost exclusively used in industry.

Tool path generation methods and cutter orientation strategies are currently approached as two separate tasks. In order to maximise the step-over distance, the cutter orientation at each CC point is optimised locally without considering its variation between neighbouring points [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF][START_REF] Jensen | Tool selection for five-axis curvature matched machining[END_REF][START_REF] Li | Efficient five-axis machining of free-form surfaces with constant scallop height tool paths[END_REF]. Accordingly, there could be some abrupt changes in orientation along a tool pass. [START_REF] Jun | Optimizing tool orientations for 5-axis machining by configuration-space search method[END_REF] developed a method to avoid the abrupt changes by searching alternative orientations in the machining configuration space and minimising the variation in cutter orientation. [START_REF] Wang | Automatic generation of gouge-free and angularvelocity-compliant five-axis toolpath[END_REF] further improved the method by limiting the rate of change of orientation angles in a given range. However, the second derivatives of the orientation angles have not been controlled and the impact on the step-over distance when limiting the angles has not been considered in either method.

The idea of integrated tool path generation was first presented by Rao et al. (2000). In their method, cutter orientation is selected based on its contribution to the complete tool pass. However, the width evaluation from the intersections of normal vectors with the cutter gives no consideration to the error introduced by the surface discretisation, nor the computational expense if dense vectors are adopted [START_REF] Choi | Sculptured Surface Machining -Theory and Applications[END_REF]. Further, the variation of the screw angle between two adjacent CC points is minimised but not smoothed along the tool pass.

Based on the previous work, this paper proposes an integrated method (IM) for tool path generation, which aims to minimise the number of tool passes in surface machining under the constraint of smooth cutter orientation. The rest of the paper is organised as follows: The machined strip is represented in parametric space in Section 2. Then, the screw angle along a tool pass is expressed in B-spline form and optimised by balancing considerations of the width and the smoothness of cutter movement in Section 3. Further, the next tool pass is positioned as far as permissible from the previous one in Section 4. Finally, the proposed method is illustrated with numerical examples in Section 5, followed by the research conclusions in Section 6.

Machined strip along a tool pass

To optimise the cutter orientation along a tool pass and control the overlap between two adjacent machined strips in iso-parametric machining, it is convenient to represent the strips and their widths in the parametric space of the design surface S.

Parametric representation of machined strip

As shown in figure 3, let D 1 and D 2 denote the two width points, which determine the machined strip width at a CC point. They are the intersections between the error surface E and the bottom circle of the cutter C, and can be evaluated by the quadric method (QM) in Euclidean space [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. Suppose that the surface parameters, corresponding to D 1 and D 2 , are respectively (u 1 , v 1 ) and (u 2 , v 2 ). Then, D 1 lies on the straight line passing through S(u 1 , v 1 ) in the normal direction N(u 1 , v 1 ). Thus

S(u 1 , v 1 ) + h 1 N(u 1 , v 1 ) = D 1 , (1)
where h 1 is the distance between S(u 1 , v 1 ) and D 1 . Ideally, h 1 should be equal to the machining tolerance ε. However, in the QM, D 1 is evaluated by replacing the error surface E with a translated quadric, which means h 1 is always smaller than ε. Consequently, equation (1) consists of three nonlinear component equations in three unknowns u 1 , v 1 , h 1 , and has generally to be solved by a numerical method, such as the Newton-Raphson

X M Y M Z M CC point N(u 0 , v 0 ) N(u 1 , v 1 ) N(u 2 , v 2 ) D 1 D 2 Figure 3. Parametric representation of width points
method. An initial estimate of S(u 1,0 , v 1,0 ) is evaluated from that of the previous width point, and an initial estimate of h 1,0 is set as ε.

Let u 1,q , v 1,q , h 1,q be the qth approximation of a root of (1) and ∆u, ∆v, ∆h the respective errors. Then

S(u 1,q + ∆u, v 1,q + ∆v) + (h 1,q + ∆h)N(u 1,q + ∆u, v 1,q + ∆v) = D 1 .
(2)

Expanding ( 2) in a Taylor series, taking the first order approximation and rearranging, yields

a 1,q ∆u + b 1,q ∆v + c 1,q ∆h = d 1,q , (3)
where

a 1,q = S u (u 1,q , v 1,q ) + h 1,q N u (u 1,q , v 1,q ), b 1,q = S v (u 1,q , v 1,q ) + h 1,q N v (u 1,q , v 1,q ), c 1,q = N(u 1,q , v 1,q ), d 1,q = D 1 -S(u 1,q , v 1,q ) -h 1,q N(u 1,q , v 1,q ).
By solving the linear equation (3), ∆u, ∆v and ∆h are obtained, and the next approximation is determined by

u 1,q+1 = u 1,q + ∆u, v 1,q+1 = v 1,q + ∆v, h 1,q+1 = h 1,q + ∆h. (4)
The iterative procedure for finding the root of ( 1) is terminated if

|d 1,q | < e 1 or |S(u 1,q+1 , v 1,q+1 ) -S(u 1,q , v 1,q )| < e 2 , (5)
where e 1 , e 2 > 0 are the predefined accuracies of the point evaluation. Hence, the parameters (u 1 , v 1 ) of the width point D 1 are obtained. Similarly, (u 2 , v 2 ) of D 2 can be evaluated.

As the cutter C moves along the tool pass, the machined strip is bounded by two sets of width points. Accordingly, the strip can be expressed in the parametric space of the design surface S.

Parametric representation of width

Suppose that the cutter C moves along a tool pass P i with a constant v, and the parameters of the two width points are (u 1 , v 1 ) and (u 2 , v 2 ) at a CC point. Then

w = |v 1 -v 2 |
is referred to as the parametric representation of the machined strip width at this location. The formulation takes no account of any difference in the values of u 1 and u 2 , but this can have little practical effect in parametric machining unless v 1 and v 2 are changing a lot between successive CC points on the tool pass. Further, it should be pointed out that the values of u 1 and u 2 are taken into account in Section 4.1, when ensuring successive machined strips overlap. The machining is therefore guaranteed to cover the whole surface although there could be a slight compromise of the machining efficiency.

In the quadric method (QM) for 5-axis sculptured surface machining [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF], the design surface S is approximated locally by two quadrics. An upper quadric lying above S is used to orient the cutter and a lower quadric below S is used to evaluate the machined strip width.

To maximise the width, for a given screw angle β, the lead angle α is optimised by placing the cutter C as close as possible to the upper quadric. Since the bottom plane of C intersects the upper quadric in a conic, the optimal α can be obtained based on the intersections of the bottom circle of C and the conic. there are in general four roots. Note that the circle and the conic share a common tangent direction at the CC point which accounts for two of the roots and the remaining two determine whether α should be increased to avoid gouging or decreased for cutting more material. The optimal solution for α is where the remaining two roots are equal and is referred to as two contact machining.

The machined strip width is determined by considering the distance of the surface below the bottom circle of the cutter C. It is guaranteed in two contact machining that all the distances are positive and the critical points are where the distances are equal to the machining tolerance ε. There are at most four such points, which can be found by translating the lower quadric in the normal direction by a distance ε and intersecting with the bottom circle of C.

In the most straightforward case there are four distinct intersection points, dividing the circle into four segments which are alternately within and outside machining tolerance. Then the segment containing the CC point is used to determine the machined strip width. As β varies, it is possible for the two segments machined within tolerance to merge, with the transition occurring where they just touch at a double intersection point. Consequently, the machined region can be classified broadly into three types: one single region, two connected regions or two disjoint regions.

The width function is determined numerically from the region or connected regions containing the CC point and its features, established by experimentation with thousands of quadrics and a range of machining tolerances, are as follows:

• Width w may increase or decrease significantly when two disjoint regions merge into one or one region splits into two. So it is discontinuous in this case. If there is only a single region, then w is continuous. • In the discontinuous case, there are two local maxima within the range of β, corresponding to one region. Generally, they are at the two discontinuities. • In the continuous case, there is one local maximum.

Figure 4 shows examples of discontinuous and continuous width functions, taken respectively from the inverse mouse and mouse surface machinings which were used previously to illustrate the quadric method (QM) for cutter orientation [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. Suppose that the cutter moves along a tool pass containing m + 1 CC points. At the jth CC point where j = 0, 1, 2, . . . , m, if the width is discontinuous, then the two local maxima are at β h1 (j) and β h0 (j), where β h1 (j) > β h0 (j). If it is continuous, then the local maximum is at β h (j). In the next section, the angle β will be optimised along the tool pass with consideration to the balance between the width and the smoothness of cutter movement.

Smoothing screw angle

The smoothness of the cutter movement is critical in 5-axis machining, and it is generally characterised by the rate of change of particular variables, such as the speed of the CC point [START_REF] Lo | Real-time generation and control of cutter path for 5-axis CNC machining[END_REF], the direction vector of the cutter axis (Li andJerard 1994, Jun et al. 2003), and the angles of machine rotary axes [START_REF] Affouard | Avoiding 5-axis singularities using tool path deformation[END_REF][START_REF] Munlin | Optimization of rotations of a five-axis milling machine near stationary points[END_REF]). The speed of the CC point is determined mainly by the setting of the feed rate. The vector of the cutter axis and angles of the rotary axes are dependent on the lead angle α and the screw angle β. Since the width w is a monotonic decreasing function of α [START_REF] Jun | Optimizing tool orientations for 5-axis machining by configuration-space search method[END_REF][START_REF] Fan | Geometric modelling of 5-axis sculptured surface machining[END_REF]) and a much more complex function of β as described in Section 2.2, this paper concentrates on maximising w with a smooth β along a tool pass. The method developed in the section is general, and could be applied to the smoothing of the angle α or other optimisation criteria.

The basic idea for smoothing the angle β is to fit the local maxima with a cubic B-spline, which is the lowest possible degree for second derivative continuity [START_REF] Piegl | The NURBS Book[END_REF]. To ensure there are no abrupt changes in the cutter movement, the first and second derivatives are kept within specified bounds. It should be noted that special care is needed for calculating the inverse kinematics of 5-axis milling machines, due to singularities in the coordinate vector transformation. Consequently, a small deviation is given to any tool orientation close to the singular positions to avoid abrupt changes in the machine rotary axes [START_REF] Affouard | Avoiding 5-axis singularities using tool path deformation[END_REF][START_REF] Munlin | Optimization of rotations of a five-axis milling machine near stationary points[END_REF][START_REF] Sørby | Inverse kinematics of five-axis machines near singular configurations[END_REF].

There are three cases to consider, dependent on whether the width is a discontinuous, continuous or hybrid function of the angle β as it varies along the tool pass.

Discontinuous case

Consider the case when the width w is discontinuous in terms of the angle β at each CC point along the tool pass. First, β h1 (j), j = 0, 1, 2, . . . , m are fitted by the optimal screw angle β H1 described in cubic B-spline form as

β H1 (t) = K k=0 N k,3 (t)H k , 0 ≤ t ≤ 1, (6)
where K + 1 is the number of control values {H k } with K > 2, and the {N k,3 (t)} are the cubic B-spline basis functions defined on the unclamped, uniform knot vector (Piegl and Tiller 1997)

T = { -3 K-2 , -2 K-2 , -1 K-2 , 0, 1 K-2 , 2 K-2 , . . . , K-4 K-2 , K-3 K-2 K-3 internal knots , 1, K-1 K-2 , K K-2 , K+1 K-2 }.
It should be emphasised that the screw angle is a scalar function defined by a sequence {H k } of one-dimensional scalars whereas, in most B-spline applications, spatial curves are defined by a sequence of three-dimensional vectors. The cubic B-spline basis functions are identical in both cases. The B-spline parameter t is defined to vary linearly with the accumulated chord length s. Suppose s = s j and t = t j at the jth CC point. Then t j = s j s m , j = 0, 1, 2 . . . , m.

In addition, since ds dt is constant and t m = 1, ds dt = s m , 0 ≤ t ≤ 1. Then, in fitting the screw angle along the tool pass, the objective function is set as

minimise z = m j=0 β h1 (j) - K k=0 N k,3 (t j )H k . (7)
To keep β H1 (t) on the side of β h1 (j) that corresponds to the one single region, there are constraints

β h1 (j) - K k=0 N k,3 (t j )H k ≥ 0, j = 0, 1, 2, . . . , m. (8)
To ensure smoothness of the fitting, it is necessary to control the rates of change of the screw angle along the tool pass. The first and second derivatives of β H1 with respect to

v H1 (t) = dβ H1 (t) ds = dβ H1 (t) dt dt ds = 1 s m K k=0 N k,3 (t)H k , (9)
a H1 (t) = d 2 β H1 (t) ds 2 = d 2 β H1 (t) dt 2 dt ds 2 = 1 s 2 m K k=0 N k,3 (t)H k , (10)
where N k,3 (t) and N k,3 (t) are respectively the first and second derivatives of N k,3 (t) with respect to t.

The principal method of control is to keep v H1 (t) within a specified range [-V, V ]. It follows from ( 9) that

s m |v H1 (t j )| = K k=0 N k,3 (t j )H k ≤ s m V, j = 0, 1, 2, . . . , m. (11)
The above constraints not only control v H1 (t) but also help to keep a H1 (t) in check. However, further constraints are needed to counter the possibility of relatively high values of |a H1 (t)| at the ends of the spline. One control option is to specify zero first derivatives at the ends with v H1 (0) = v H1 (1) = 0. Another option is to implement natural splines with a H1 (0) = a H1 (1) = 0. A less restrictive option, adopted here, is to bound the values of a H1 (0) and a H1 (1):

s 2 m |a H1 (t j )| = K k=0 N k,3 (t j )H k ≤ 4(K -2)s m V, j = 0, m. ( 12
)
It is proved in the Appendix A (with

D = s m V , dβ(t) dt = s m v H1 (t) and d 2 β(t) dt 2 = s 2 m a H1 (t)) that for each of the control options s 2 m max |a H1 (t)| ≤ 4(K -2)s m V. ( 13
)
Consequently, to keep a H1 (t) within a specified range [-A, A], K is assigned as the largest integer satisfying

K ≤ s m A 4V + 2. ( 14
)
Then, it follows from ( 7), ( 8), ( 11) and ( 12) that the problem of optimising the screw angle can be expressed as a constrained linear minimisation of the form:

minimise z = m j=0 β h1 (j) - K k=0 N k,3 (t j )H k , subject to K k=0 N k,3 (t j )H k ≤ β h1 (j), j = 0, 1, 2, . . . , m, K k=0 N k,3 (t j )H k ≤ s m V, j = 0, 1, 2, . . . , m, - K k=0 N k,3 (t j )H k ≤ s m V, j = 0, 1, 2, . . . , m, K k=0 N k,3 (t j )H k ≤ 4(K -2)s m V, j = 0, m, - K k=0 N k,3 (t j )H k ≤ 4(K -2)s m V, j = 0, m. (15)
The problem ( 15) can be further reformulated into the standard form of linear programming [START_REF] Dantzig | Linear Programming and Extensions[END_REF], and then solved by the simplex method, which is efficient in solving linear problems with hundreds (even thousands) of variables and constraints [START_REF] Vanderbei | Linear Programming: Foundations and Extensions[END_REF]. Hence, β H1 (t) is obtained. Similarly, replacing β h1 (j) by β h0 (j) and H k by -H k in (15) gives β H0 (t), the optimal screw angle fitting to β h0 (j), j = 0, 1, 2, . . . , m.

For example, consider the optimisation of the screw angles along the tool pass v = 0.75 in the inverse mouse surface machining. 14) that K = 11 should be adopted for the fitting. Figure 5 shows the optimal screw angles β H1 (t) and β H0 (t), and confirms that the respective first and second derivatives are within the specified ranges. Whichever is used for the machining, there is no risk of abrupt changes in the cutter movement.

To construct the machining data at each CC point along the tool pass, the screw angle β is evaluated from the B-spline approximation and the corresponding lead angle α is determined by the integrated orientation strategy of the quadric method (QM) [START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. As outlined in Section 2.2, the QM optimises α by placing the cutter C as close as possible to the upper quadric approximation of the design surface S. Inevitably, the data smoothing reduces the width of the machined strip, but the QM minimises that reduction whilst guaranteeing there is no local interference.

(c) 60 • 30 • 0 • -30 • -60 • 0 1 β h1 (j) βH1(t) β h0 (j) βH0(t) 0 1 0 1 1 • /mm -1 • /mm 0.3 • /mm 2 -0.3 • /mm 2 vH0(t) vH1(t) aH1(t)

Continuous case

Next, consider the case when the width is continuous in terms of the screw angle at each CC point along the tool pass. Two angle functions β H0 (t) and β H1 (t) are constructed in cubic B-spline form, which best fit β h (j), j = 0, 1, 2, . . . , m, with limited first and second derivatives along the tool pass such that β H0 (t j ) ≤ β h (j) ≤ β H1 (t j ), j = 0, 1, 2, . . . , m. More generally, any cubic spline of the form β Hλ (t) = (1 -λ)β H0 (t) + λβ H1 (t), 0 ≤ λ ≤ 1, has first and second derivatives within the specified bounds. Unlike the discontinuous case, the sign of (β Hλ (t) -β h (t)) is not critical. Consequently, choosing λ such that m j=0 (β Hλ (t) -β h (t)) = 0 or λ = 0.5 would give reasonable, unbiassed fits but, for total compatibility with the discontinuous case, the choice is restricted to λ = 0 or λ = 1.

Hybrid case

Finally, consider the hybrid case when the width is discontinuous in terms of the screw angle at some CC points and continuous at others. If the width is discontinuous at the jth CC point, then its local maxima are at β h1 (j) and β h0 (j), where β h1 (j) > β h0 (j). If the width is continuous, then its local maxima are considered at β h1 (j) and β h0 (j) with β h1 (j) = β h0 (j). Consequently, two angle functions β H1 (t) and β H0 (t) are constructed in B-spline form, which best fit β h1 (j) and β h0 (j), j = 0, 1, 2, . . . , m, as before.

The hybrid case essentially unifies the analysis and provides a general solution with two candidates, β H0 (t) and β H1 (t), for defining the screw angle. The choice for an individual machined pass could be determined by comparing min w H0 (t) and min w H1 (t) and adopting the one with the greater width. However, the overall surface quality is likely to be better by adopting a fixed preference for either β H0 (t) or β H1 (t) over the whole surface, since the spacing of the P i 's will be more regular and the screw angle functions along successive P i 's will be more compatible.

Machining whole surface

A method is proposed in this section to construct the machined strip I i adjacent to a previously constructed I i-1 , with an adaptation to construct the first strip I 1 . A discrete parametric definition is adopted for the profile of a machined strip and an iterative algorithm is proposed to maximise the step-over from v i-1 to v i , whilst ensuring there are no gaps between I i and I i-1 . The method is applicable to any construction of machined strips where the screw angle and lead angle functions are uniquely defined for all CC points along a tool pass, for all values of v, 0 ≤ v ≤ 1. Functions of particular interest in this paper are β = 0, β = β H0 (t) or β = β H1 (t) with optimal α; or β = 0 with constant α.

Overlap between two machined strips

The overlap between I i and I i-1 is independent of the directions in which they are machined. So, to simplify the description and computational details, it is assumed that the tool passes have increasing u-values.

Suppose that at the jth CC point along the tool pass P i , the parametric left and right width points are respectively at (a i,j , b i,j ) and (c i,j , d i,j ) as shown in figure 6. Then the machined strip I i is bounded by two sets of points (a i,j , b i,j ) and (c i,j , d i,j ), j = 0, 1, 2, . . . , m(i), where m(i) + 1 is the number of CC points along P i . The overlap distance ∆v i,j between I i and I i-1 at (c i,j , d i,j ) can be evaluated as

∆v i,j = c i,j -a i-1,r a i-1,r+1 -a i-1,r (b i-1,r+1 -b i-1,r ) + b i-1,r -d i,j , (16)
where r is determined by a i-1,r ≤ c i,j < a i-1,r+1 . If ∆v i,j ≥ 0, then I i and I i-1 overlap at (c i,j , d i,j ) by a distance equal to ∆v i,j . Otherwise, there is a gap equal to -∆v i,j . Consequently, when constructing I i , a necessary condition is that ∆v i,j ≥ 0, j = 0, 1, 2, . . . , m(i), i.e., there should be no gaps between I i and I i-1 .

Determining step-over

The primary objective in the construction of a machined strip I i is to determine the parametric constant v = v i > v i-1 for the next tool pass P i . It is assumed that b i-1 = min{b i-1,j } < 1, otherwise there would be no need to construct another tool pass. It is also assumed that the screw angle and lead angle functions are uniquely defined at all CC points along a tool pass, for all values of v, 0 ≤ v ≤ 1. If the machined strip along v = 1 overlaps I i-1 without any gaps, then v i = 1 is adopted as an acceptable solution. Otherwise, the aim is to maximise the step-over from v i-1 to v i , within a tolerance e p . Let δ(v i ) denote the minimum overlap of the machined strip along v = v i with

P i v i-1 v i I i-1 I i (a i-1,r+1 , b i-1,r+1 ) (c i,j , d i,j ) (a i-1,r , b i-1,r ) (a i,
I i-1 , 1 ≥ v i ≥ v i-1 . Then b i-1 < 1, δ(b i-1 ) > 0 and δ(1) < 0. Consequently, by successive bisection of the interval [b i-1 , 1], it is possible to find an interval [v i , v * i ] where δ(v i ) ≥ 0, δ(v * i ) < 0 and 0 < v * i -v i ≤ e p .
Of course, there are generally more computationally efficient ways of finding v i .

For example, an iterative algorithm is proposed to find v i which aims to minimise the overlap with I i-1 rather than maximise the step-over. Let min{w i-1 } denote the minimum width of I i-1 , then the v-value of P i is initialised at

v i,0 = v i-1 + min{w i-1 }. ( 17
)
At the qth iteration, suppose that the minimum overlap distance between the two strips is δv i,q = min{∆v i,j }. If 0 ≤ δv i,q ≤ e p , then the iteration is terminated. Otherwise, the v-value of P i at the (q + 1)th iteration is determined by

v i,q+1 = v i,q + δv i,q -e p /2. ( 18
)
For total computational robustness, it is advisable to incorporate within the software solution a binary search to find v i , which can be triggered whenever there is slow convergence.

The above algorithm must be adapted for the first machined strip I 1 , where there is not a previously constructed strip. In this case a dummy machined strip is constructed along v = 0. Let min{w 0 } denote the minimum width of the whole strip and b 0 denote the minimum width of that part with v ≥ 0. Then, in the iterative process to find v i , equations ( 16) and ( 17) are adapted to ∆v 1,j = -d 1,j , (16a)

v 1,0 = -b 0 + min{w 0 }. (17a)
Consequently, the first machined strip will overlap v = 0 such that the minimum overlap is within tolerance.

Inverse mouse surface machining

The proposed integrated method (IM) was implemented using Visual C++ R and OpenGL R on a personal computer with an Inter R Core TM 2 Duo 2.33GHz Processor and 2.00GB of RAM under Windows R XP Professional SP2 operating system. The implementation comprises four modules for lead angle optimisation, screw angle optimisation, width evaluation and step-over determination. The cutter is a flat-end cutter with radius R = 4 mm, machining tolerance ε = 0.01 mm, allowable overlap distance e p = 2e -4 , and accuracies of point evaluation e 1 = e 2 = 1e -5 mm. It took 6.32 minutes to generate 16 tool passes to cover the entire inverse mouse surface as shown in figure 7(a).

The tool path has been checked by Toolpath Verification in PowerMILL R 9.0, a world leading CAM software package, and there are no gouges/collisions reported. The machining was also simulated using ViewMILL in PowerMILL and figure 7(b) illustrates the shiny rendered image. It should be noted that ViewMILL employs a dynamic flute model, rather than a cylindrical surface, to define the geometry of the cutter and produces photorealistic images which correspond almost perfectly to the results of physical machinings [START_REF] Liu | Surface finish visualisation in high speed, ball nose milling applications[END_REF]. Comparing figures 7(a) and 7(b), it can be seen that they have very similar strip patterns although the ViewMILL shows up some minor surface irregularities, well within the machining tolerance, just as one would get in the physical machining.

Table 1 gives the v-values of the corresponding tool passes, and figure 8(a) illustrates the machined strips in parametric space. Suppose that the surface is physically machined with a feed rate of 250 mm/min, then the total machining time is approximately 8.26 minutes. Table 2 compares of the IM with some alternative machining strategies introduced in Section 1.2 for machining the inverse mouse surface, and figure 8 illustrates the corresponding machined strips in parametric space. In some published 5-axis machining methods [START_REF] Gray | Rolling ball method for 5-axis surface machining[END_REF], 2005[START_REF] Hosseinkhani | Penetration-elimination method for five-axis CNC machining of sculptured surfaces[END_REF], the screw angle β is kept at 0 • and the lead angle α is optimised by placing the cutter as close as possible to the design surface. The computational time for this method to generate 24 tool passes to cover the entire surface is 2.41 minutes, and the machining time is 12.40 minutes. Alternatively, if the surface is machined by the conventional 5-axis method with α = 10 • and β = 0 • (Choi and Jerard 1998), it will take 3.55 minutes to generate 50 tool passes and 25.80 minutes to physically machine the surface. The example illustrates the potential efficiency savings of the IM compared to the other strategies, with reductions in the machining times of 33% and 68% respectively. The simple practical explanation for the improvement is that the two orientation angles of the cutter are fully exploited in the IM, so that the cutter surface is optimally close to the design surface, subject only to the constraint of having a smooth cutter movement. Further, comparing the machined strips in figure 8, it can be seen that those in 8(a) are as regular as those in 8(c) and more regular than those in 8(b), which suggest the machined surface quality is as good with the IM as with the other strategies.

The one disadvantage of the IM is the extra computational time, with the bulk of that time (about 0.2 min/pass) spent on searching for the optimal screw angle. Certainly, there is a scope for improving the search algorithm but the extra cost of computation is already small compared to the valuable savings in 5-axis machining time. Indeed, in all cases, the extra computational time is outweighed by the reduction in machining time without any consideration to their relative value.

Conclusions

In this paper, the integrated method (IM) has been developed for tool path generation in 5-axis machining. Distinctive from existing methods, both the machined strip width and the smoothness of cutter movement are considered in determining cutter orientation along a tool pass. Further, the next tool pass is positioned as far as permissible from the previous one. It follows that the two cutter orientation angles are fully exploited along the tool passes and the step-over distances are maximised under the constraint of smooth cutter movements. Consequently, the IM is more efficient and the numerical simulations in Section 5 have shown that there can be a significant reduction in the number of tool passes required by the IM compared to other methods.

In the paper, the IM has been combined with the quadric method (QM) in iso-parametric machining with a flat-end cutter. However, the IM can be extended easily to machining with a fillet-end cutter, according to the geometric equivalency between the flat-end and fillet-end cutters (Yoon 2003, Fan and[START_REF] Fan | Quadric method for cutter orientation in five-axis sculptured surface machining[END_REF]. Also, it is applicable to other orientation strategies with different machining mechanisms, based on the width evaluation in physical space [START_REF] Marciniak | Geometric Modelling for Numerically Controlled Machining[END_REF]. Finally, by formulating the possible constraints from collision avoidance into a linear form, an efficient, smooth and safe tool path can be obtained.

Acknowledgements

Figure 1 .

 1 Figure 1. Cutter orientation in 5-axis machining

Figure 4 .

 4 Figure 4. Width w as a function of screw angle β in (a) inverse mouse and (b) mouse surface machinings at (0.5, 0.75)

  Taylor & Francis and I.T. Consultant s, v H1 (t) and a H1 (t), are related to the parametric derivatives of the B-spline as follows:

Figure 5 .

 5 Figure 5. Optimisation along tool pass with K = 11 showing (a) optimal screw angles (b) first and (c) second derivatives

Figure 7 .

 7 Figure 7. Inverse mouse surface machining showing (a) machined strips and (b) simulation result

Figure 8 .

 8 Figure 8. Comparison of machined strips in parametric space showing (a) Integrated method (16 passes), (b) β = 0 • with optimal α (24 passes), and (c) β = 0 • , α = 10 • (50 passes)

  The first author would like to acknowledge the financial support of the Overseas Research Students (ORS) award from Universities UK and the Research Scholarship from the School of Mechanical Engineering at the University of Birmingham. The authors thank Martin Loftus and Robert Cripps at the University of Birmingham, Jonathan Corney at the University of Strathclyde and Steve Hobbs at Delcam PLC for their valuable comments and suggestions.

Table 1 .

 1 v-values of tool passes

	No.	1	2	3	4	5	6	7	8
	v	0.0110 0.0411 0.0881 0.1417 0.2068 0.2741 0.3482 0.4293
	No.	9	10	11	12	13	14	15	16
	v	0.5104 0.5872 0.6659 0.7425 0.8206 0.8935 0.9551 0.9862

Table 2 .

 2 Comparison of alternative machining methods in inverse mouse surface machining

Taylor & Francis and I.T. Consultant

Appendix A.

Suppose that β(t), 0 ≤ t ≤ 1 is a uniform cubic B-spline comprising (K -2) segments, K > 2, where max dβ(t) dt ≤ D.

Proof :

dt 2 is a uniform linear B-spline comprising (K -2) segments, varying linearly from

must occur at one of the segment ends.

First suppose that the maximum of d 2 β(t) dt 2 occurs at t = 0. Then result follows immediately in cases (ii) and (iii). In case (i)

where

Integrating with dβ(0) dt = 0 gives

Minimum range of dβ(t) dt over 0, 1 K-2 occurs when

and dβ(t) dt ranges from 0 to 1 4(K -2)

The proof is similar at t = 1. Now suppose that the maximum of

The minimum range of dβ(t) dt over l-1 K-2 , l+1 K-2 occurs when

Since dβ(t) dt ranges at most from -D to D, it follow that max d 2 β(t) dt 2 = max

≤ 4(K -2)D.