Automatic feature recognition aids downstream processes such as engineering analysis and manufacturing planning. Not all features can be defined in advance; a declarative approach allows engineers to specify new features without having to design algorithms to find them. Naive translation of declarations leads to executable algorithms with high time complexity. Database queries are also expressed declaratively; there is a large literature on optimizing query plans for efficient execution of database queries. Our earlier work investigated applying such technology to feature recognition, using a testbed interfacing a database system (SQLite) to a CAD modeler (CADfix). Feature declarations were translated into SQL queries which are then executed. The current paper extends this approach, using the PostgreSQL database, and provides several new insights: (i) query optimization works quite differently in these two databases, (ii) with care, an approach to query translation can be devised that works well for both databases, and (iii) when finding various simple common features, linear time performance can be achieved with respect to model size, with acceptable times for real industrial models. Further results also show how (i) lazy evaluation can be used to reduce the work performed by the CAD modeler, and (ii) estimating the time taken to compute various geometric operations can further improve the query plan. Experimental results are presented to validate our main conclusions.

We introduce a novel stratified sampling technique for mesh surfaces that gives the user control over sampling density and anisotropy via a tensor field. Our approach is based on sampling space-filling curves mapped onto mesh segments via parametrizations aligned with the tensor field. After a short preprocessing step, samples can be generated in real time. Along with visual examples, we provide rigorous spectral analysis and differential domain analysis of our sampling. The sample distributions are of high quality: they fulfil the blue noise criterion, so have minimal artifacts due to regularity of sampling patterns, and they accurately represent isotropic and anisotropic densities on the plane and on mesh surfaces. They also have low discrepancy, ensuring that the surface is evenly covered.

Three-dimensional surface registration transforms multiple three-dimensional data sets into the same coordinate system so as to align overlapping components of these sets. Recent surveys have covered different aspects of either rigid or nonrigid registration, but seldom discuss them as a whole. Our study serves two purposes: 1) To give a comprehensive survey of both types of registration, focusing on three-dimensional point clouds and meshes and 2) to provide a better understanding of registration from the perspective of data fitting. Registration is closely related to data fitting in which it comprises three core interwoven components: model selection, correspondences and constraints, and optimization. Study of these components 1) provides a basis for comparison of the novelties of different techniques, 2) reveals the similarity of rigid and nonrigid registration in terms of problem representations, and 3) shows how overfitting arises in nonrigid registration and the reasons for increasing interest in intrinsic techniques. We further summarize some practical issues of registration which include initializations and evaluations, and discuss some of our own observations, insights and foreseeable research trends.

In region machining, neighbouring regions may be close together, but disconnected. Boundary curves may also have unwanted geometric artifacts caused by approximation and discretisation. We present a strategy to improve the topology and geometry of such boundary curves, allowing the generation of better tool paths, and in turn, improved tool wear and surface quality of the machined part. We make such improvements in three steps: firstly, disconnected regions are merged where appropriate, using a method based on morphological operations from image processing. Secondly, boundary segments with undesirable geometric properties are identified and replaced by simpler segments, using a vertex deletion operation. Finally, flaws at a smaller geometric scale are removed, using a curve shortening algorithm. Experimental results are given to illustrate our algorithm.

We consider the problem of computing a parting line for a mold for a complex mesh model, given a parting direction, and the related problem of removing small undercuts, either preexisting, or resulting from the parting line. Existing parting line algorithms are unsuitable for use with complex meshes: the faceted nature of such models leads to a parting line which zig-zags or wanders across the surface undesirably. Our method computes a smooth parting line which runs through a band of triangles whose normals are approximately perpendicular to the parting direction. We generate a skeleton of this triangle band to find its distinct topological cycles, and to decompose it into simple pieces. After selecting paths making a good cycle, we generate a final smooth parting line by iteratively improving the geometry of this cycle. Compliance in the physical material, and/or modifications to eliminate minor undercuts ensure that such a parting line is practically useful.

An algorithm is presented to automatically generate bas-reliefs based on adaptive histogram equalization (AHE), starting from an input height field. A mesh model may alternatively be provided, in which case a height field is first created via orthogonal or perspective projection. The height field is regularly gridded and treated as an image, enabling a modified AHE method to be used to generate a bas-relief with a user-chosen height range. We modify the original image-contrast-enhancement AHE method to use gradient weights also to enhance the shape features of the bas-relief. To effectively compress the height field, we limit the height-dependent scaling factors used to compute relative height variations in the output from height variations in the input; this prevents any height differences from having too great effect. Results of AHE over different neighborhood sizes are averaged to preserve information at different scales in the resulting bas-relief. Compared to previous approaches, the proposed algorithm is simple and yet largely preserves original shape features. Experiments show that our results are, in general, comparable to and in some cases better than the best previously published methods.

This paper discusses noise in range data measured by a Konica Minolta Vivid 910 scanner. Previous papers considering denoising 3D mesh data have often used artificial data comprising Gaussian noise, which is independently distributed at each mesh point. Measurements of an accurately machined, almost planar test surface indicate that real scanner data does not have such properties. An initial characterisation of real scanner noise for this test surface shows that the errors are not quite Gaussian, and more importantly, exhibit significant short range correlation. This analysis yields a simple model for generating noise with similar characteristics. We also examine the effect of two typical mesh denoising algorithms on the real noise present in the test data. The results show that new denoising algorithms are required to effectively remove real scanner noise.

Motivated by the need to detect design intent in approximate boundary representation models, we give an algorithm to detect incomplete symmetries of discrete points, giving the models' potential local symmetries at various automatically detected tolerances. Here, incomplete symmetry is defined as a set of incomplete cycles which are constructed by, e.g., a set of consecutive vertices of an approximately regular polygon, induced by a single isometry. All seven 3D elementary isometries are considered for symmetry detection. Incomplete cycles are first found using a tolerance-controlled point expansion approach. Subsequently, these cycles are clustered for incomplete symmetry detection. The resulting clusters have welldefined, unambiguous approximate symmetries suitable for design intent detection, as demonstrated experimentally.

This paper considers the mold design problem of computing a parting line for a complex mesh model, given a parting direction. Existing parting line algorithms are unsuitable for this case, as local variations in the orientations of the facets of such models lead to a parting line which zig-zags across the surface in an undesirable way. This paper presents a method to compute a smooth parting line which runs through a triangle band composed of triangles whose normals are approximately perpendicular to the parting direction. The skeleton of the triangle band is used to generate a structure representing distinct topological cycles, and to decompose the triangle band into singly-connected surface pieces, giving candidate paths. We choose a set of paths giving a good cycle; the final smooth parting line is then constructed by iteratively improving the quality of this cycle. Compliance in the physical material, or minor modifications to the surface itself, will ensure that such a parting line is appropriate for use.

This paper considers an approach to mesh denoising based on the concept of random walks. The proposed method consists of two stages: a face normal filtering procedure, followed by a vertex position updating procedure which integrates the denoised face normals in a least-squares sense. Face normal filtering is performed by weighted averaging of normals in a neighbourhood. The weights are based on the probability of arriving at a given neighbour after a random walk of a virtual particle starting at a given face of the mesh and moving a fixed number of steps. The probability of a particle stepping from its current face to a given neighboring face is determined by the angle between the two face normals, using a Gaussian distribution whose width is adaptively adjusted to enhance the feature-preserving property of the algorithm. The vertex position updating procedure uses the conjugate gradient algorithm for speed of convergence. Analysis and experiments show that random walks of different step lengths yield similar denoising results. In particular, iterative application of a one-step random walk in a progressive manner effectively preserves detailed features while denoising the mesh very well. We observe that this approach is faster than many other feature-preserving mesh denoising algorithms.

We present a simple and fast mesh denoising method, which can remove noise effectively, while preserving mesh features such as sharp edges and corners. The method consists of two stages. Firstly, noisy face normals are filtered iteratively by weighted averaging of neighboring face normals. Secondly, vertex positions are iteratively updated to agree with the denoised face normals. The weight function used during normal filtering is much simpler than that used in previous similar approaches, being simply a trimmed quadratic. This makes the algorithm both fast and simple to implement. Vertex position updating is based on the integration of surface normals using a least-squares error criterion. Like previous algorithms, we solve the least-squares problem by gradient descent, but whereas previous methods needed user input to determine the iteration step size, we determine it automatically. In addition, we prove the convergence of the vertex position updating approach. Analysis and experiments show the advantages of our proposed method over various earlier surface denoising methods.

Sculptural reliefs are widely used in various industries for purposes such as applying brands to packaging and decorating porcelain. In order to easily apply reliefs to CAD models, it is often desirable to reverse-engineer previously designed and manufactured reliefs. 3D scanners can generate triangle meshes from objects with reliefs; however, previous mesh segmentation work has not considered the particular problem of separation of reliefs from background. We consider here the specific case of segmenting a simple relief delimited by a single outer contour, which lies on a smooth, slowly varying background. Generally, such reliefs meet the surrounding surface in a small step, enabling us to devise a specific method for such relief segmentation.We find the boundary between the background and the relief using an adaptive snake. It starts at a simple user-drawn contour, and is driven inwards by a collapsing force until it matches the relief's boundary. Our method is insensitive to the choice of the initial contour. The snake's limiting position is controlled by a feature energy term designed to find a step. A refinement strategy is then used to drive the snake into concavities of the relief contour.We demonstrate operation of our algorithm using real scanned models with different relief contour shapes and triangle meshes with different resolutions.

Reverse engineering allows the geometric reconstruction of simple mechanical parts. However, the resulting models suffer from inaccuracies caused by errors in measurement and reconstruction so such models do not have the exact congruence, symmetries and other regularities the original designer intended. We wish to impose such regularities in a beautification process. The paper discusses the particular problem of detecting approximate congruence between parts (e.g. a pair of handles) of a reconstructed B-rep model, so that a subsequent step can enforce them exactly. A practical detection algorithm is given for models defined using planes, spheres, cylinders, cones and tori. Analysis of the algorithm and experimental results show that expected congruence are detected reasonably quickly.

Boundary representation models reconstructed from 3D range data suffer from various inaccuracies caused by noise in the data and the model building software. The quality of such models can be improved in a beautification step, which finds geometric regularities approximately present in the model and tries to impose a consistent subset of these regularities on the model. A framework for beautification and numerical methods to select and solve a consistent set of constraints deduced from a set of regularities are presented. For the initial selection of consistent regularities likely to be part of the model's ideal design priorities, and rules indicating simple inconsistencies between the regularities are employed. By adding regularities consecutively to an equation system and trying to solve it by using quasi-Newton optimization methods, inconsistencies and redundancies are detected. The results of experiments are encouraging and show potential for an expansion of the methods based on degree of freedom analysis.

Boundary representation models reconstructed from 3D range data suffer from various inaccuracies caused by noise in the data and the model building software. The quality of such models can be improved in a beautification step, which finds regular geometric patterns approximately present in the model and imposes a maximal consistent subset of constraints deduced from these patterns on the model. This paper presents analysis methods seeking geometric patterns defined by similarities. Their specific types are derived from a part survey estimating the frequencies of the patterns in simple mechanical components. The methods seek clusters of similar objects which describe properties of faces, loops, edges and vertices, try to find special values representing the clusters, and seek approximate symmetries of the model. Experiments show that the patterns detected appear to be suitable for the subsequent beautification steps.