Optimal path planning for automated dimensional inspection of free-form surfaces

Structural dimensional inspection is vital for the process monitoring, quality control, and fault diagnosis in the mass production of auto bodies. Comparing with the non-contact measurement, the high-precision five-axis measuring machine with the touch-trigger probe is a preferred choice for data collection. It can assist manufacturers in making accurate inspection quickly. As the increase of free-form surfaces and diverse surface orientations in product design, existing inspection approaches cannot capture some new critical features in the curvature of products in an efficient way. Therefore, we need to develop new path planning methods for automated dimensional inspection of free-form surfaces. This paper proposes an optimal path planning system for automated programming of measuring point inspection by incorporating probe rotations and effective collision detection. Specifically, the methodological contributions include: (i) a dynamic searching volume-based algorithm is developed to detect potential collisions in the local path between measurement points; (ii) a local path generation method is proposed with the integration of the probe trajectory and the stylus rotation. Then, the inspection time matrix is proposed to quantify the measuring time of diverse local paths; (iii) an optimization approach of the global inspection path for all critical points on the product is developed to minimize the total inspection time. A case study has been conducted on an auto body to verify the performance of the proposed method. Results show that the collision-free path for the free-form auto body could be generated automatically with off-line programming, and the proposed method produces about 40% fewer dummy points and needs 32% less movement time in the auto body inspection process.     

Ray-tracing triangular trimmed free-form surfaces

This paper presents a new approach to rendering triangular algebraic free-form surfaces. A hierarchical subdivision of the surface with associated tight bounding volumes provides for quick identification of the surface regions likely to be hit by a ray. For each leaf of the hierarchy, an approximation to the corresponding surface region is stored. The approximation is used to compute a good starting point for the iteration, which ensures rapid convergence. Trimming curves are described by a tree of trimming primitives, such as squares, circles, polygons, and free-form curves, combined with Boolean operations. For trimmed surfaces, an irregular adaptive subdivision is constructed to quickly eliminate all parts outside the trimming curve from consideration during rendering. Cost heuristics are introduced to optimize the rendering time further     

Gauss map computation for free-form surfaces

The Gauss map of a smooth doubly-curved surface characterizes the range of variation of the surface normal as an area on the unit sphere. An algorithm to approximate the Gauss map boundary to any desired accuracy is presented, in the context of a tensor-product polynomial surface patch, r(u,v) for (u,v)[0,1]×[0,1]. Boundary segments of the Gauss map correspond to variations of the normal along the patch boundary or the parabolic lines (loci of vanishing Gaussian curvature) on the surface. To compute the latter, points of vanishing Gaussian curvature are identified with the zero-set of a bivariate polynomial, expressed in the numerically-stable Bernstein basis—the subdivision and variation-diminishing properties then govern an adaptive quadtree decomposition of the (u,v) parameter domain that captures the zero-set of this polynomial to any desired accuracy. Loci on the unit sphere corresponding to the patch boundaries and parabolic lines are trimmed at their mutual or self-intersection points (if any), and the resulting segments are arranged in a graph structure with the segment end-points as nodes. By appropriate traversal of this graph, the Gauss map boundary segments may then be identified in proper order, and extraneous segments (lying in the Gauss map interior) are discarded. The symmetrization of the Gauss map (by identification of antipodal points) and its stereographic projection onto a plane are also discussed.     

Localization and comparison of two free-form surfaces

Comparison of two free-form surfaces based on discrete data points is of paramount importance for reverse engineering. It can be used to assess the accuracy of the reconstructed surfaces and to quantify the difference between two such surfaces. The entire process involves three main steps: data acquisition, 3D feature localization and quantitative comparison. This paper presents models and algorithms for 3D feature localization and quantitative comparison. Complex free-form surfaces are represented by bicubic parametric spline surfaces using discrete points. A simple yet effective pseudoinverse algorithm was developed and implemented for localization. It consists of two iterative operations, namely, constructing a pseudo transformation matrix and point matching. A computing algorithm was developed to compare two such surfaces using optimization techniques. Since this approach does not involve solving non-linear equations for the parameters of positions and orientations, it is fast and robust. The algorithm was implemented and tested with several examples. It is effective and can be used in industry for sculptured surface comparison.     

Iso-level tool path planning for free-form surfaces

The aim of tool path planning is to maximize the efficiency against some given precision criteria. In practice, scallop height should be kept constant to avoid unnecessary cutting, while the tool path should be smooth enough to maintain a high feed rate. However, iso-scallop and smoothness often conflict with each other. Existing methods smooth iso-scallop paths one-by-one, which make the final tool path far from being globally optimal. This paper proposes a new framework for tool path optimization. It views a family of iso-level curves of a scalar function defined over the surface as tool path so that desired tool path can be generated by finding the function that minimizes certain energy functional and different objectives can be considered simultaneously. We use the framework to plan globally optimal tool path with respect to iso-scallop and smoothness. The energy functionals for planning iso-scallop, smoothness, and optimal tool path are respectively derived, and the path topology is studied too. Experimental results are given to show effectiveness of the proposed methods.     

Boundary-conformed toolpath generation for trimmed free-form surfaces

In this paper, we adopt a 2D reparameterization procedure to regenerate boundary-conformed toolpaths. Three methods for the 2D reparameterization of trimmed boundaries in parametric space are examined and compared. They are the Coons method, the Laplace method, and a newly developed boundary-blending method. These three methods represent three different approaches to 2D surface parameterization, namely, the algebraic interpolation approach, the partial differential equation approach, and a geometric offsetting approach, respectively. Complete algorithms for surface reparameterization and toolpath generation are developed and implemented. The results showed that the Coons method is relatively simple yet might cause anomalies when the complexities of the boundary are high. The Laplace method is robust but takes relatively more computational time and also has the problem of uneven distribution of iso-parametrics. For the newly developed boundary-blending method, both the computational efficiency and parameterization robustness are quite good, in addition, it alleviates the uneven distribution problem appeared in the Laplace results.     

A spherical representation for recognition of free-form surfaces

Introduces a new surface representation for recognizing curved objects. The authors approach begins by representing an object by a discrete mesh of points built from range data or from a geometric model of the object. The mesh is computed from the data by deforming a standard shaped mesh, for example, an ellipsoid, until it fits the surface of the object. The authors define local regularity constraints that the mesh must satisfy. The authors then define a canonical mapping between the mesh describing the object and a standard spherical mesh. A surface curvature index that is pose-invariant is stored at every node of the mesh. The authors use this object representation for recognition by comparing the spherical model of a reference object with the model extracted from a new observed scene. The authors show how the similarity between reference model and observed data can be evaluated and they show how the pose of the reference object in the observed scene can be easily computed using this representation. The authors present results on real range images which show that this approach to modelling and recognizing 3D objects has three main advantages: (1) it is applicable to complex curved surfaces that cannot be handled by conventional techniques; (2) it reduces the recognition problem to the computation of similarity between spherical distributions; in particular, the recognition algorithm does not require any combinatorial search; and (3) even though it is based on a spherical mapping, the approach can handle occlusions and partial views     

Improvement of free-form surfaces for product styling applications

There are a number of ways of describing free-form surfaces within geometric modelling systems. For product styling and related activities, there is a need to ensure that surface quality is good and that patches join together smoothly. Additional parameters can be introduced to allow surfaces to be modified. This raises the question of whether these can be chosen automatically, and this in turn requires measures of what is a ‘fair’ surface. Measures based on surface curvature are discussed and applied to adjust surface patches presented in terms of point meshes.     

5-axis flank milling free-form surfaces considering constraints

A new tool path generation method of flank milling considering constraints is proposed for ball-end cutters in this paper. It will not only reduce the machining error range but also meet the following two constraints: (a) The ball end of the milling tool is tangential to the constraint surface; (b) There is no overcut and the minimum error is zero, which is called nonnegative-error constraint. The two constraints are very useful in some situations of engineering applications, such as flank milling impeller blades. Based on the proposed method, two types of cutter will be used to generate tool paths for the same designed surface and constraint surface. The effectiveness and accuracy of the proposed method will be finally proved with some examples.     

SURFED — an interactive editor for free-form surfaces

An editor is described for creating and modifying free-form surfaces. A modular system was developed in order to provide the researchers with a facility for communicating design ideas and new mathematical forms through an interactive graphical interface to a computer-based model. To achieve this it was necessary to invent a new graphical construct called a ‘spider’ for inputting three-dimensional parameters. This experimental system has the essential features of a large-scale implementation, with the capability of utilizing many new surface forms that have not yet been tried in actual applications.     

Semi-automatic system for defining free-form curves and surfaces

Among curves and surfaces defined by parametric polynomials, the cases dealt with here are those which only have to comply with the requirement to run through a certain number of points previously located in space. The process can be totally automatic, but the results are liable to be altered by arbitrary decisions.     

Hermite approximation for free-form deformation of curves and surfaces

Free-Form Deformation Techniques (FFD) are commonly used to generate animations, where a polygonal approximation of the final object suffices for visualization purposes. However, for some CAD/CAM applications, we need an explicit expression of the object, rather than a collection of sampled points. If both object and deformation are polynomial, their composition yields a result that is also polynomial, albeit very high degree, something undesirable in real applications. To solve this problem, we transform each curve or surface composing the object, usually expressed in the Bernstein basis, to a modified Newton form. In this representation, the two-point analogue of Taylor expansions, the composition admits a simple expression in terms of discrete convolutions, and degree reduction corresponding to Hermite approximation is trivial by dropping high-degree coefficients. Furthermore, degree-reduction can be incorporated into the composition. Finally, the deformed curve or surface is converted back to the Bernstein form. This method extends to general non-polynomial deformation, such as bending and twisting, by computing a polynomial approximant of the deformation.     

Design and manufacture of free-form surfaces by cross-sectional approach

Conventional methods for manual design and analysis are not necessarily the best methods for computer implementation, lofting techniques, or computer aided design to produce a satisfactory result for the design of a wide range of shapes and the general form of the B-spline curve with the defining polygon adequately fulfils most essential requirements. Fourth-order curves seemed to be best suited for most cases, as they provide a compromise between smoothness and ‘localness’, yet curve orders of varying degrees still have some merit in certain circumstances.The most attractive feature realized with this method is the simplicity of design and the determination of the main input elements. Surface interpolation curves are shown and the production of a mould for a plastic handle indicated.     

A vision-aided reverse engineering approach to reconstructing free-form surfaces

A vision-aided reverse engineering approach (VAREA) has been developed to reconstruct least-square free-form surface models from physical models, with a coordinate measurement machine (CMM) equipped with a touch-triggered probe and a computer vision system. The VAREA integrates computer vision, surface data digitization and surface modelling into a single process. Two main steps are applied in this innovative approach. The initial vision-driven surface triangulation process (IVSTP) generates a triangular patch by using stereo image detection and a constrained Delaunay triangulation method. The adaptive model-based digitizing process is then used to refine the surface reconstruction and to control accuracy to within user-specified tolerances. As a result, a least-squares bicubic B-spline surface model with the controlled accuracy of digitization can be obtained for further application in product design and manufacturing processes. More than 85% reduction has been achieved in the time required to construct free-form surfaces using this approach, as compared with traditional manual methods with CMM. Therefore, product design lead time can be significantly reduced.     

Rigid, affine and locally affine registration of free-form surfaces

In this paper, we propose a new framework to perform nonrigid surface registration. It is based on various extensions of an iterative algorithm recently presented by several researchers (Besl and McKay, 1992; Champleboux et al., 1992; Chen and Medioni, 1992; Menq and Lai, 1992; Zhang, 1994) to rigidly register surfaces represented by a set of 3D points, when a prior estimate of the displacement is available. Our framework consists of three stages:First, we search for the best rigid displacement to superpose the two surfaces. We show how to efficiently use curvatures to superpose principal frames at possible corresponding points in order to find a prior rough estimate of the displacement and initialize the iterative algorithm.Second, we search for the best affine transformation. We introduce differential information in points coordinates: this allows us to match locally similar points. Then, we show how principal frames and curvatures are transformed by an affine transformation. Finally, we introduce this differential information in a global criterion minimized by extended Kalman filtering in order to ensure the convergence of the algorithm.Third, we locally deform the surface. Instead of computing a global affine transformation, we attach to each point a local affine transformation varying smoothly along the surface. We call this deformation a locally affine deformation.All these stages are illustrated with experiments on various real biomedical surfaces (teeth, faces, skulls, brains and hearts), which demonstrate the validity of the approach.     

Iterative point matching for registration of free-form curves and surfaces

A heuristic method has been developed for registering two sets of 3-D curves obtained by using an edge-based stereo system, or two dense 3-D maps obtained by using a correlation-based stereo system. Geometric matching in general is a difficult unsolved problem in computer vision. Fortunately, in many practical applications, some a priori knowledge exists which considerably simplifies the problem. In visual navigation, for example, the motion between successive positions is usually approximately known. From this initial estimate, our algorithm computes observer motion with very good precision, which is required for environment modeling (e.g., building a Digital Elevation Map). Objects are represented by a set of 3-D points, which are considered as the samples of a surface. No constraint is imposed on the form of the objects. The proposed algorithm is based on iteratively matching points in one set to the closest points in the other. A statistical method based on the distance distribution is used to deal with outliers, occlusion, appearance and disappearance, which allows us to do subset-subset matching. A least-squares technique is used to estimate 3-D motion from the point correspondences, which reduces the average distance between points in the two sets. Both synthetic and real data have been used to test the algorithm, and the results show that it is efficient and robust, and yields an accurate motion estimate.     

Adaptive iso-planar tool path generation for machining of free-form surfaces

The iso-planar (Cartesian) tool path generation method has been used for several decades. However, it suffers an inherent drawback: in the region where the direction of the surface normal is close to that of the parallel intersecting planes, the intersecting plane intervals have to be reduced because of the influence of surface slopes. This causes redundant tool paths in the associated flatter regions and results in lower machining efficiency. This paper presents an algorithm that overcomes the disadvantage of the iso-planar method while keeping its advantages of robustness and simplicity. In this algorithm, the concept of isophote is applied to partition the surface into different regions. In each region the tool path side steps are adaptive to the surface features. Therefore redundant tool paths are avoided. By applying the region-by-region or global-local machining strategy, the machining efficiency is increased.     

A sketching interface for feature curve recovery of free-form surfaces

In this paper, we present a semi-automatic approach to efficiently and robustly recover the characteristic feature curves of a given free-form surface where we do not have to assume that the input is a proper manifold. The technique supports a sketch-based interface where the user just has to roughly sketch the location of a feature by drawing a stroke directly on the input mesh. The system then snaps this initial curve to the correct position based on a graph-cut optimization scheme that takes various surface properties into account. Additional position constraints can be placed and modified manually which allows for an interactive feature curve editing functionality. We demonstrate the usefulness of our technique by applying it to two practical scenarios. At first, feature curves can be used as handles for surface deformation, since they describe the main characteristics of an object. Our system allows the user to manipulate a curve while the underlying non-manifold surface adopts itself to the deformed feature. Secondly, we apply our technique to a practical problem scenario in reverse engineering. Here, we consider the problem of generating a statistical (PCA) shape model for car bodies. The crucial step is to establish proper feature correspondences between a large number of input models. Due to the significant shape variation, fully automatic techniques are doomed to failure. With our simple and effective feature curve recovery tool, we can quickly sketch a set of characteristic features on each input model which establishes the correspondence to a pre-defined template mesh and thus allows us to generate the shape model. Finally, we can use the feature curves and the shape model to implement an intuitive modeling metaphor to explore the shape space spanned by the input models.     

Adaptive reconstruction of free-form surfaces using Bernstein basis function networks

Many computer graphics and computer-aided design (CAD) applications require mathematical models to be generated from measured coordinate data. The three-dimensional surface model of a complex object can be created by fitting the data with low-order parametric surface patches, and adjusting the control parameters such that the constituent patches meet seamlessly at their common boundaries. Most neural networks that are designed for function approximation produce a solution that is not easily transferable to CAD software. An adaptive technique to reconstruct a smooth surface from Bézier patches is presented in this paper. The approach utilizes a neural network that performs a weighted summation of Bernstein polynomial basis functions. The number of basis neurons is related to the degree of the Bernstein polynomials and is equivalent to the number of control parameters. Free-form surfaces are reconstructed by simultaneously updating networks that correspond to the separate patches. A smooth transition between adjacent Bézier surface patches is achieved by imposing positional and tangential continuity constraints on the weights during the adaptation process. The final weights of the various networks correspond to the control points of the stitched Bézier surface, and can therefore be used directly in many commercial CAD packages. This method has been used to create a closed surface by adaptively fitting two adjacent patches to synthetic range data and a complex open surface by fitting four patches to experimentally measured range data.