Search

This paper presents a new method for parallelizing geodesic algorithms on triangle meshes. Using the half-edge data structure, we define the propagation dependency graph to characterize data dependency in computing geodesics. Then, we design an active strategy such that the vertices and half-edges on the wavefront take the initiative to collect their input data and then propagate windows and update geodesic information in their own memory space. As a result, all the read and write operations can be carried out simultaneously. Our method, named AWP, works for both exact (e.g., the CH algorithm) and approximate (e.g., the fast marching method) geodesic algorithms. Our implementation on various NVIDIA GPUs exhibit perfect linear speedup, i.e., doubling the computational power (i.e., FLOPS) doubles the speed. We prove that the AWP-CH algorithm runs in O (n 2 ∕ min (C , n)) time, where n and C are the numbers of faces and cores, respectively. Evaluation on GTX Titan XP shows that AWP-CH empirically runs in n p time, p ∈ [ 1. 25 , 1. 35 ] , for real-world models with n ≤ 1 0 7 and anisotropy measure τ ≤ 2. 0. Thanks to its perfect efficiency and the trend of increasing the number of processors in graphics hardware, we believe that the actual performance of AWP can be further improved in the near future. • An algorithm for parallelizing discrete geodesic algorithms with perfect efficiency. • The algorithm works for both the CH algorithm and the fast marching method. • Source code is publically available at https://github.com/openawp/awp. [ABSTRACT FROM AUTHOR]

Objects with architected internal structure often consist of a lattice of beams that are interconnected at nodes. Compared to the conventional cylindrical and conical beams, quador-beams are bounded by quadrics-of-revolution. We decompose the lattice into an assembly of hubs , wherein a hub is the union of a node (ball) with the half-beams incident upon it. In this paper, we propose (1) a hybrid representation of a quador-hub (hub with quador half-beams) consisting of exact CSG + CST + Boundary models, (2) a compact data structure and associated operators to work with the hybrid representation, and (3) algorithms to perform fundamental geometric queries on the hub. We provide the operators to query the half-beams of the hub, to inquire the trimming planes of a surface, or to traverse the faces, edges and vertices of the hub. We suggest efficient algorithms, that take advantage of the hybrid representation, for geometric queries such as point membership classification, planar slicing, surface meshing, and area/volume computation. We outline a possible approach for computing exact answers to all tests that are required for computing the exact topology of the proposed representation of the hub. Finally, we show that the simplified geometry of quador hubs leads to smaller data sizes and improved performance in a commercial modeler. • A hub defined as the union of a ball and incident quadric-of-revolution half-beams. • Lattice decomposition into an assembly of hubs. • Exact hybrid (CSG + CST + Boundary) representation of a hub. • Compact data structure and related operators to work with the hybrid representation. • Efficient algorithms to perform fundamental geometric queries on a hub. [ABSTRACT FROM AUTHOR]

Toolpath is always presented as a combination of G01 linear segments in practical computer numerical control (CNC) machining. However, the inherent tangent discontinuity at junctions will lead to uncontinuous feedrate, acceleration (i.e. the change rate of feedrate), jerk (i.e. the change rate of tangential acceleration), making it difficult to realize higher machining efficiency and better machining quality. In recent studies, the improvement of practical feedrate profile continuity is beneficial to overcome the drawbacks above, especially when smooth jerk is satisfied. In this paper, it is proved that in order to obtain smooth jerk along toolpath, G 4 continuous toolpath and jerk-smooth feedrate scheduling process are both essential. On this basis, a path-smoothing algorithm is proposed to generate G 4 continuous toolpath via a quintic B-spline curve. In addition, the transition curve is optimized by curvature variation energy (CVE) to produce better machining quality. Meanwhile, the chord error is constrained seriously and the curvature extreme, occurring at the middle of transition curves, can be calculated analytically. In motion planning stage, based on the bidirectional scanning algorithm, a look-ahead method is utilized to determine the reachable transition feedrate extreme and a jerk-smooth feedrate scheduling scheme is also developed. Finally, simulations and experiments are conducted to demonstrate the feasibility and efficiency of the proposed method compared to point-to-point (P2P) motion, constant feedrate strategy, G 2 and G 3 methods respectively. • A new path-smoothing algorithm is proposed to generate G 4 continuous toolpath. • The curvature of transition curve is proved to be monotonous, and curvature extreme occurs exactly at the middle of B-spline curve analytically. • The relationship between trajectory continuity and feedrate profile continuity is illustrated. • A scanning algorithm is performed in feedrate scheduling, and jerk-smooth feedrate is achieved. [ABSTRACT FROM AUTHOR]

Routing of wire harnesses in complex machinery is a complicated problem. In this paper, we present an approach for computing all non-homotopic paths characteristic of all the homotopy classes associated with a pair of source–destination points embedded on the surface of the product. We introduce the notion of routing graphs, which are generated from specific non-trivial loops in the first homology group associated with the surface of the product. The routing graph, which is constructed only once, encodes the homotopy of the routing environment and is, therefore, used to find all the non-homotopic paths between multiple source–destination pairs. Based on the path embedding requirements, we classify the routing process into (1) On-Surface Routing, when the paths are constrained to the surface of the product, and (2) In-Air Routing, when the paths are allowed to venture into the product ambiance space. In the former case, the routing graph is defined by both the handle and tunnel loops in the first homology group, whereas in the latter case, it is defined by only the handle loops. We propose a linking number-based strategy for computing the handle and tunnel loops for a given closed surface. The methods are extended for routing in assemblies using the so-called shell structures associated with them. The results obtained demonstrate the efficacy of the proposed approach. The results show that the computation of the routing graph is very efficient, and the homotopy classes can be generated in very little time using the proposed approach. • A topological method for 3D wire harness routing is developed. • The method generates all the homotopy classes associated with a pair of terminals. • The approach works for both – (1) On-surface and (2) In-air routing. • The method is extended for routing on assemblies. • An algorithm for computing handle & tunnel loops on closed surfaces is described. [ABSTRACT FROM AUTHOR]

With the prevalence of implicit shape processing and reconstruction, extracting a polygonal mesh of an isosurface from volume data, which plays an important role in these tasks, is receiving more and more attention. GradNormal, a recently proposed marching tetrahedra method, can effectively extract high-quality meshes from analytic functional shapes but suffers from detail loss and computational inefficiency issues. In this paper, we improve GradNormal from four aspects. First, we extend GradNormal from an analytic function to an arbitrary geometric domain equipped with the projection operation. Second, we select a seed tetrahedron and find only the tetrahedra intersecting the implicit surface, in a region-growing style, which helps save memory and accelerate calculation. Third, we invent a hierarchical tiling mechanism to enhance the recovery accuracy of the resulting mesh, unlike the uniform tiling used in GradNormal. Finally, we propose to accurately predict how the underlying surface goes through a tetrahedral element so that complicated topological structures such as thin plates and gaps can be well captured. Extensive experimental results on challenging shapes show that the improved GradNormal is able to quickly produce a feature-adapted triangle mesh that is more topologically and geometrically accurate than the state-of-the-art. [Display omitted] • Propose an improved GradNormal method to extract an accurate mesh from volume data. • Extend GradNormal to an arbitrary geometric domain equipped with projection operation. • Search the tetrahedra intersecting the implicit surface in a region-growing style. • Invent a hierarchical tiling mechanism to enhance the recovery mesh accuracy. • Accurately predict how the underlying surface passes a tetrahedral element. [ABSTRACT FROM AUTHOR]

The equiareality of NURBS surfaces highly affects their rendering and tessellation results. To improve the equiareality of NURBS surfaces, an optimization algorithm using freeform transformations is presented in this paper. The equiareality energy is first formulated and its numerical approximation is then constructed using the composite Simpson's rule. By constructing the parameterization of the initial freeform transformation using a low-stretch-mesh-parameterization method, the optimal freeform transformation is obtained by the Levenberg–Marquardt method, which is further interleaved with the freeform refinement procedure to generate a hierarchical NURBS surface with bounded equiareality deviations. Experimental results are given to show the performance of our algorithm for rendering and tessellation applications. • An optimization method is presented to improve the equiareality of NURBS surfaces using the freeform transformation. • The equiareality energy of the hierarchical NURBS surfaces is formulated. • The gradient of the discretized equiareality energy is derived in this paper. [ABSTRACT FROM AUTHOR]

Abstract: Computing the shortest path, overcoming obstacles in a plane, is a well-known geometric problem. However, widely assumed obstacles are polygonal in nature. Very few papers have focused on curved obstacles, and in particular, for curved multiply-connected domains (domains having holes). Given a set of parametric curves forming a multiply-connected domain (MCD), with one closed curve acting as an outer boundary and several non-intersecting inner curves (loops) as representing holes and two distinct points and lying on the outer boundary, this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point–curve tangents (PCTs) and bitangents (BTs) using their respective constraints. A generalized region lemma is proposed, which is then employed to remove PCTs/BTs that will not contribute to the potential path and subsequently aiding in removing a few inner loops. The algorithm is designed to explore all potential paths. Merging of paths is also proposed to avoid redundant computations. A final SIP is chosen from potential paths using the length of each path. The algorithm also has the potential to give all paths of equal lengths contributing to shortest paths (within a tolerance level). As the algorithm computes all the potential paths on the fly, there is no need to employ a visibility graph to compute the shortest path. Curves are represented using non-uniform rational B-splines (NURBS). The algorithm uses the curves as such and does not discretize into point-sets or polygons. Extensions to handle curves with discontinuities and and not on the outer boundary have also been described. Results of the implementation are provided and complexity of the algorithm is also discussed. This paper follows up the one presented for simply-connected domains (SCDs) in Bharath Ram and Ramanathan (2011) [4]. [Copyright &y& Elsevier]

Abstract: A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented by a triangle mesh , the geodesic metric on can be computed exactly using computational geometry methods. Previous work for establishing the geodesic metric on only supports using half-edge data structures; i.e., each edge in is split into two halves and each half-edge corresponds to one of two faces incident to . In this paper, we prove that the exact-geodesic structures on two half-edges of can be merged into one structure associated with . Four merits are achieved based on the properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures can directly add the geodesic distance function without changing the kernel to a half-edge data structure; (2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an on-the-fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental results show that when compared to the classic half-edge data structure, the edge-based implementation of the MMP algorithm reduces running time by 44% and storage by 29% on average. [Copyright &y& Elsevier]

Abstract: An offset algorithm is important to the contour-parallel tool path generation process. Usually, it is necessary to offset with islands. In this paper a new offset algorithm for a 2D point-sequence curve (PS-curve) with multiple islands is presented. The algorithm consists of three sub-processes, the islands bridging process, the raw offset curve generation and the global invalid loops removal. The input of the algorithm is a set of PS-curves, in which one of them is the outer profile and the others are islands. The bridging process bridges all the islands to the outer profile with the Delaunay triangulation method, forming a single linked PS-curve. With the fact that local problems are caused by intersections of adjacent bisectors, the concept of stuck circle is proposed. Based on stuck circle, local problems are fixed by updating the original profile with the proposed basic rule and append rule, so that a raw offset curve can be generated. The last process first reports all the self-intersections on the raw offset PS-curve, and then a procedure called tree analysis puts all the self-intersections into a tree. All the points between the nodes in even depth and its immediate children are collected using the collecting rule. The collected points form the valid loops, which is the output of the proposed algorithm. Each sub-process can be complete in near linear time, so the whole algorithm has a near linear time complexity. This can be proved by the examples tested in the paper. [Copyright &y& Elsevier]

Abstract: The paper presents the research activity developed by the authors in the field of computer-aided inventive problem solving: an original model and a dialogue-based software application have been developed by integrating the logic of ARIZ (Algorithm for the Inventive Problem Solving) with some OTSM-TRIZ (General Theory of Powerful Thinking) models in order to guide a user also with no TRIZ education to the analysis of inventive problems. The paper demonstrates that through a dialogue-based interaction it is possible to guide the user towards a proper formulation of the problem statement, which is an essential step of any conceptual design activity. The proposed software system, although still at a prototype stage, has been tested with students at Politecnico di Milano and at the University of Florence. The paper details the structure of the algorithm and the results of the first validation activity; then, it discusses about the possibility to integrate the proposed approach into a new generation of CAD systems. [Copyright &y& Elsevier]

Abstract: Multi-axis machine production process optimization, automation and intelligence are the key codes of today’s scientific community. Rapid decision and intelligence are becoming more important for precise and safe virtual and real production. Multi-axis CNC production is a high speed machining process that demands less human intervention and high intelligence, to deal with any uncomfortable situation regarding collisions. Current CAM softwares as well as CNC machines are able to detect collisions but are unable to avoid these collisions automatically. This paper aims to make the CAD-CAM/CNC multi-axis safe trajectory generation process optimal, intelligent and automatic, using vision based image processing by the Snakes and Ladders game analogy. Applying the Snakes and Ladders analogy on machine virtual scene (trajectory preparation) and real scene (during production) images gives promising methodology for safe and efficient trajectory generation while avoiding collisions named Snakes and Ladders Analogy for Production Trajectory (SLAPT). Our Rectangular Enveloped Safe and Efficient Trajectory (RESET) algorithm, based on the same principle of the SLAPT methodology is also discussed in this paper. Results include some applications of algorithms on virtual and real machine scene images for the safe and optimized trajectory of tools. This paper focuses on intelligence and optimization of 2D non-functional transversal trajectories of 2-axis machines for production and preparation processes as an initial effort towards the complex safe trajectory generation process (mill-turn). [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for extracting Free-Form Surface Features (FFSFs) from a surface model. The extraction algorithm is based on a modified taxonomy of FFSFs from that proposed in the literature. A new classification scheme has been proposed for FFSFs to enable their representation and extraction. The paper proposes a separating curve as a signature of FFSFs in a surface model. FFSFs are classified based on the characteristics of the separating curve (number and type) and the influence region (the region enclosed by the separating curve). A method to extract these entities is presented. The algorithm has been implemented and tested for various free-form surface features on different types of free-form surfaces (base surfaces) and is found to correctly identify and represent the features irrespective of the type of underlying surface. The representation and extraction algorithm are both based on topology and geometry. The algorithm is data-driven and does not use any pre-defined templates. The definition presented for a feature is unambiguous and application independent. The proposed classification of FFSFs can be used to develop an ontology to determine semantic equivalences for the feature to be exchanged, mapped and used across PLM applications. [Copyright &y& Elsevier]

Abstract: We provide a flexible shape control technique in this paper for the automatic resizing of apparel products. The automatic resizing function has become an essential part of the 3D garment CAD systems to generate user customized apparel products for individuals with variant body shapes. The human bodies are usually represented by piecewise linear mesh surfaces with consistent connectivity. The shape of apparel products can then be warped from the space around a human body to the space around another body by computing the new positions of points on apparel products. However, one major limitation of this kind of automatic resizing technique is that the apparel products are always distorted along the shape of the human bodies. This is a required deformation for tight clothes but not an expected result for other types of clothes. To solve this problem, we investigate a method to preserve the shape of user-defined features on the apparel products. As the apparel products are often represented by discrete surfaces with non-manifold entities, the existing mesh processing approaches that preserve the local shape cannot be applied here. A new algorithm consisting of three steps is developed in this paper. First, the apparel product is warped from the reference human body to the space around the target human body. Second, the shape of features is optimized to match their original shape before the warping. Lastly, discrete surfaces of the apparel product are deformed again under an optimization framework to match their original shapes locally while interpolating the shape of features determined in the previous step. [Copyright &y& Elsevier]

Abstract: This paper deals with a problem of finding valid solutions to systems of polynomial constraints. Although there have been several quite successful algorithms based on domain subdivision to resolve this problem, some major issues are still demanding further research. Prime obstacles in developing an efficient subdivision-based polynomial constraint solver are the exhaustive, although hierarchical, search of the zero-set in the parameter domain, which is computationally demanding, and their scalability in terms of the number of variables. In this paper, we present a hybrid parallel algorithm for solving systems of multivariate constraints by exploiting both the CPU and the GPU multicore architectures. We dedicate the CPU for the traversal of the subdivision tree and the GPU for the multivariate polynomial subdivision. By decomposing the constraint solving technique into two different components, hierarchy traversal and polynomial subdivision, each of which is more suitable to CPUs and GPUs, respectively, our solver can fully exploit the availability of hybrid, multicore architectures of CPUs and GPUs. Furthermore, our GPU-based subdivision method takes advantage of the inherent parallelism in the multivariate polynomial subdivision. We demonstrate the efficacy and scalability of the proposed parallel solver through several examples in geometric applications, including Hausdorff distance queries, contact point computations, surface–surface intersections, ray trap constructions, and bisector surface computations. In our experiments, the proposed parallel method achieves up to two orders of magnitude improvement in performance compared to the state-of-the-art subdivision-based CPU solver. [Copyright &y& Elsevier]

Abstract: Shells are three-dimensional structures. One dimension, the thickness, is much smaller than the other two dimensions. Shell structures can be widely found in many real-world objects. This paper presents a method to construct a layered hexahedral mesh for shell objects. Given a closed 2-manifold and the user-specified thickness, we construct the shell space using the distance field and then parameterize the shell space to a polycube domain. The volume parameterization induces the hexahedral tessellation in the object shell space. As a result, the constructed mesh is an all-hexahedral mesh in which most of the vertices are regular, i.e., the valence is 6 for interior vertices and 5 for boundary vertices. The mesh also has a layered structure, so that all layers have exactly the same tessellation. We prove that our parameterization is guaranteed to be bijective. As a result, the constructed hexahedral mesh is free of degeneracy, such as self-intersection, flip-over, etc. We also show that the iso-parametric line (in the thickness dimension) is orthogonal to the other two iso-parametric lines. We apply our algorithm to numerous real-world models of various geometry and topology. The promising experimental results demonstrate the efficacy of our algorithm. Although our main focus is to construct a hexahedral mesh by using volumetric polycube parameterization, the proposed framework is general that can be applied to other regular domains, such as cylinder and sphere, which is also demonstrated in the paper. [Copyright &y& Elsevier]

Abstract: This paper discusses the challenges of long-term preservation of digital geometric models and the engineering processes associated with them. For engineering, design, manufacturing, and physics-based simulation data this requires formats that are accessible potentially indefinitely into the future. One of the fundamental challenges is the development of digital geometry-centric engineering representations that are self describing and assured to be interpretable over the long lifespans required by archival applications. Additionally, future users may have needs that require other information, going beyond geometry, be also accessible to fully interpret the model. These problems are highly interdisciplinary and not exclusively algorithmic or technical. To provide context, the paper introduces a case study illustrating an overall portrait of the problem. Based on observations from this case study, we present a framework for enhancing the preservation of geometry-centric engineering knowledge. This framework is currently being used on a number of projects in engineering education. [Copyright &y& Elsevier]

Abstract: Bresenham’s Algorithm for plotting a two-dimensional line segment is elegant and efficient in its deployment of mid-point comparison and integer arithmetic. It is natural to investigate its three-dimensional extensions. In so doing, this paper uncovers the reason for little prior work. The concept of the mid-point in a unit interval generalizes to that of nearest neighbours involving a Voronoi diagram. Algorithmically, there are challenges. While a unit interval in two-dimension becomes a unit square in three-dimension, “squaring” the number of choices in Bresenham’s Algorithm is shown to have difficulties. In this paper, the three-dimensional extension is based on the main idea of Bresenham’s Algorithm of minimum distance between the line and the grid points. The structure of the Voronoi diagram is presented for grid points to which the line may be approximated. The deployment of integer arithmetic and symmetry for the three-dimensional extension of the algorithm to raise the computation efficiency are also investigated. [Copyright &y& Elsevier]

Abstract: The problem of computing the minimum enclosing sphere (MES) of a point set is a classical problem in Computational Geometry. As an LP-type problem, its expected running time on the average is linear in the number of points. In this paper, we generalize this approach to compute the minimum enclosing sphere of free-form hypersurfaces, in arbitrary dimensions. This paper makes the bridge between discrete point sets (for which indeed the results are well-known) and continuous curves and surfaces, showing that the general solution for the former can be adapted for the latter. To compute the MES of a pair of hypersurfaces, each one having a contact point (a point at which the sphere touches the hypersurface), antipodal constraints are employed. For more than a pair, equidistance constraints along with tangency constraints are applied. These constraints yield a finite set of solution points which are used to identify the minimum enclosing sphere. The algorithm uses the LP-characteristic of the problem to process the input set. Furthermore, an optimization procedure that uses the convex hull of sampled points from the hypersurfaces is also described. Finally, results from our implementation are presented. [Copyright &y& Elsevier]

Abstract: This paper focuses on interpolating vertices and normal vectors of a closed quad-dominant mesh 1 [1] A mesh is quad-dominant if it contains quad facets as its majority. The quantity of quad facets is much more than the quantity of triangular and other multi-sided facets. -continuously using regular Coons B-spline surfaces, which are popular in industrial CAD/CAM systems. We first decompose all non-quadrangular facets into quadrilaterals. The tangential and second-order derivative vectors are then estimated on each vertex of the quads. A least-square adjustment algorithm based on the homogeneous form of continuity condition is applied to achieve curvature continuity. Afterwards, the boundary curves, the first- and the second-order cross-boundary derivative curves are constructed fulfilling continuity and compatibility conditions. Coons B-spline patches are finally generated using these curves as boundary conditions. In this paper, the upper bound of the rank of continuity condition matrices is also strictly proved to be , and the method of tangent-vector estimation is improved to avoid petal-shaped patches in interpolating solids of revolution. Several examples demonstrate its feasibility. [ABSTRACT FROM AUTHOR]

Surface skinning is a surface generation method that uses a set of given cross-sectional curves, and it is widely used in free-form surface design. In the B-spline surface skinning, the given B-spline curves should be compatible, that is, the curves should have the same degree and knot sequence. While making the curves compatible, lots of control vertices are generated. Although T-spline surface skinning methods have been introduced to reduce the number of control vertices, the T-spline skinning method that was proposed by Nasri et al. (2012) can generate a wiggled surface when the given B-spline curves are not sufficiently compatible. The intermediate cross sections that were introduced for T-spline surface skinning cannot preserve the shape of the given B-spline curves if the adjacent B-spline curves do not have sufficient common knots, and it can cause wiggles on the surface. In this paper, we analyze this issue and suggest a modified method to remove the wiggles on the skinned T-spline surface. Furthermore, we propose an algorithm for shape preservation of the surface. Our approach is verified by suggesting some examples compared to the Nasri et al. (2012)’s method. [ABSTRACT FROM AUTHOR]

Given a tetrahedral mesh and objective functionals measuring the mesh quality which take into account the shape, size, and orientation of the mesh elements, our aim is to improve the mesh quality as much as possible. In this paper, we combine the moving mesh smoothing , based on the integration of an ordinary differential equation coming from a given functional, with the lazy flip technique, a reversible edge removal algorithm to modify the mesh connectivity. Moreover, we utilize radial basis function (RBF) surface reconstruction to improve tetrahedral meshes with curved boundary surfaces. Numerical tests show that the combination of these techniques into a mesh improvement framework achieves results which are comparable and even better than the previously reported ones. [ABSTRACT FROM AUTHOR]

This paper presents a fast and robust mesh generation procedure that is able to generate meshes of the earth system (ocean and continent) in matters of seconds. Our algorithm takes as input a standard shape-file i.e. geospatial vector data format for geographic information system (GIS) software. The input is initially coarsened in order to automatically remove unwanted channels that are under a desired resolution. A valid non-overlapping 1D mesh is then created on the sphere using the Euclidean coordinates system x , y , z . A modified Delaunay kernel is then proposed that enables generation of meshes on the sphere in a straightforward manner without parametrization. One of the main difficulty in dealing with geographical data is the over-sampled nature of coastline representations. We propose here an algorithm that automatically unrefines coastline data. Small features are automatically removed while always keeping a valid (non-overlapping) geometrical representation of the domain. A Delaunay refinement procedure is subsequently applied to the domain. The refinement scheme is also multi-threaded at a fine grain level, allowing to generate about a million points per second on 8 threads. Examples of meshes of the Baltic sea as well as of the global ocean are presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a scalable three dimensional parallel Delaunay image-to-mesh conversion algorithm. A nested master–worker model is used to simultaneously explore process- and thread-level parallelization. The mesh generation includes two stages: coarse and fine meshing. First, a coarse mesh is constructed in parallel by the threads of the master process. Then the coarse mesh is partitioned. Finally, the fine mesh refinement procedure is executed until all the elements in the mesh satisfy the quality and fidelity criteria. The communication and computation are separated during the fine mesh refinement procedure. The master thread of each process that initializes the MPI environment is in charge of the inter-node MPI communication for data (submesh) movement while the worker threads of each process are responsible for the local mesh refinement within the node. We conducted a set of experiments to test the performance of the algorithm on distributed memory clusters and observed that the granularity of coarse level data decomposition, which affects the coarse level concurrency, has a significant influence on the performance of the algorithm. With the proper value of granularity, the algorithm is scalable to 45 distributed memory compute nodes (900 cores). [ABSTRACT FROM AUTHOR]

In 1984, Chazelle constructed a family of non-convex polyhedra which can be parametrised by the number N of the defining line segments and the vertical shift ε between the two saddle surfaces. Such a polyhedron is known as the Chazelle polyhedron (Chazelle, 1984). It establishes a quadratic lower bound on the minimum number of convex pieces for the 3d convex decomposition problem. Chazelle polyhedra are not decomposable without using addition points, so-called Steiner points. In this paper, we study the problem of triangulating a Chazelle polyhedron with only interior Steiner points. It is motivated by a crucial step in tetrahedral mesh generation in which a set of arbitrary constraints (edges or faces) need to be entirely preserved. We first “cut off” the volume of the Chazelle polyhedron by removing the regions that can be tetrahedralised without adding Steiner points. This leads to a 3d non-convex polyhedron whose vertices belong to the two shifted saddle surfaces. We call it the reduced Chazelle polyhedron . We then give a set of ( N + 1 ) 2 interior Steiner points that ensures the existence of a tetrahedralisation of the reduced Chazelle polyhedron with 4 ( N + 1 ) input line segments. The proof uses an intuitive relation between a 3d tetrahedralisation and a sequence of 2d flips. In particular, we design an edge splitting and flipping algorithm and prove that it will result a tetrahedralisation of the reduced Chazelle polyhedron. Finally, we construct a family of polyhedra, so-called generalised Chazelle polyhedra in which the set of reduced Chazelle polyhedra is a subset of it. We prove that our placement of interior Steiner points also applies to tetrahedralise generalised Chazelle polyhedra. [ABSTRACT FROM AUTHOR]

Mesh adaptation plays a critical role in balancing computational efficiency and numerical accuracy. Three types of mesh adaptation techniques exist today, namely, mesh improvement, mesh refinement and mesh simplification, and, for each of these, several algorithms have been proposed. Current mesh adaptation algorithms yield acceptable geometric mesh quality, but provide limited control over topological quality. In this paper, we introduce a unified algorithm for all three types of mesh adaptation, specifically for quadrilateral meshes. The algorithm builds upon the Minimum Singularity Templates (MST) proposed by the authors for improving the topological quality of a quadrilateral mesh. The MST is extended here to define the concept of an α MST where a single parameter α controls mesh adaptation: α = 1 for mesh improvement, α > 1 for mesh refinement, and α < 1 for mesh simplification. The proposed algorithm generates a mesh that is adapted to user requirements of high geometric and topological qualities. Further, it is non-hierarchical and stateless, and yet it provides an arbitrary level of mesh adaptation. Finally, since cyclic chords can play an important role in quadrilateral mesh adaptation, we provide a simple constructive algorithm to insert such chords using α MST. The proposed α MST templates can also be used to improve surface quadrilateral meshes using conformal mapping of surface charts. Furthermore, rotating the templates in the direction of cross-fields allows mesh edges to align along curvature lines. The proposed 3D generalization is fast, scalable, and inexpensive while improving alignment, shape, size, and sparsely placing the singularities. Several examples (both in 2D/3D) are presented that demonstrate the robustness, efficiency, and versatility of the proposed concept and algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we revisit the point-in-polyhedron problem. After reviewing previous work, we develop further insight into the problem. We then claim that, for a given testing point and a three-dimensional polyhedron, a single determining triangle can be found which suffices to determine whether the point is inside or outside the polyhedron. This work can be considered to be an extension and implementation of Horn’s work, which inspired us to propose a theorem for obtaining determining triangles. Building upon this theorem, algorithms are then presented, implemented, and tested. The results show that although our code has the same asymptotic time efficiency as commonly used octree-based ray crossing methods, in practice it is usually several times and sometimes more than ten times faster, while other costs such as preprocessing time and memory requirements remain the same. The ideas proposed in this paper are simple and general. They thus extend naturally to multi-material models, i.e., polyhedrons subdivided into smaller regions by internal boundaries. [ABSTRACT FROM AUTHOR]

Abstract: Morphing is an interpolation technique that changes one form into another through a seamless transition, producing, in the process, an infinite number of ‘intermediate’ forms between the original and the target. This paper examines the possibility of using the morphing technique for generating a large number of hull forms rapidly based on a number of target forms, existing or newly generated. The paper discusses the technique developed for applying morphing technique to hull form definition. The algorithm first projects the vertices of the original and target 3D surfaces onto 2D planes. After ‘regularising’ the vertices on 2D, they are projected back on the 3D surfaces. The corresponding vertices of the two surfaces are then used for interpolation. It has been found that the interpolated hull forms can be generated almost instantaneously, allowing the whole algorithm to be embedded in an optimisation program. [Copyright &y& Elsevier]

Abstract: In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad dominant mesh with edges well aligned to the principal directions of the underlying surface. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. We further obtain the quad dominant mesh by dropping the not-aligned diagonal edges from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. Various results are presented in the paper; they show a good alignment to surface features and rather uniform distribution of mesh vertices. This makes them well suited, e.g., as Catmull–Clark Subdivision control meshes. [Copyright &y& Elsevier]

Abstract: This paper describes non-manifold offsetting operations that add or remove a uniform thickness from a given non-manifold topological model. The mathematical definitions and properties of the non-manifold offsetting operations are investigated first, and then an offset algorithm based on the definitions is proposed and implemented using the non-manifold Euler operators proposed in this paper. In this algorithm, the offset elements of minimal size for the vertices, edges and faces of a given non-manifold model are generated first. Then, they are united into a single body using the non-manifold Boolean operations. In order to reduce computation time and numerical errors, the intersections between the offset elements are calculated considering the origins of the topological entities during union. Finally, all topological entities that are within the offset distance are detected and removed in turn. In addition to the original offset algorithm based on mathematical definitions, some variant offset algorithms, called sheet thickening and solid shelling, are proposed and implemented for more practical and efficient solid modeling of thin-walled plastic or sheet metal parts. In virtue of the proposed non-manifold offset operation and its variations, different offsetting operations for wireframes, sheets and solids can be integrated into one and applied to a wide range of applications with a great potential usefulness. [Copyright &y& Elsevier]

Abstract: This paper presents a systematic method for the determination of optimal geometric machining parameters in multi-axis machining. Machining accuracy is considered to be determined by a set of geometric parameters: the design parameters of the cutter, the positioning of the cutter, the orientation of the cutter etc. First, we formulate the general nonlinear constrained optimization model of the machining process. The optimal machining result is expected to produce the least deviation between the designed surface and the actual surface. This objective is accomplished by minimizing the deviation between the designed surface and the actual surface during machining. The details of how to characterize and calculate the deviation is then discussed for both ruled surface milling and general free-form surface milling. The swept surface is developed based on robotic manipulation and is used to model the actual surface. A signed distance function is constructed to perform the comparison which returns the signed distance from each sampled point to the designed surface. The direct search algorithm (Nelder–Mead simplex algorithm and pattern search algorithm in this paper) is used to solve our optimization problems due to possible discontinuity of the objective function and large nonlinearity of the problem. Three numerical examples and necessary comparisons are given to demonstrate the effectiveness of our method. The first example shows the generation of the swept volume of a filled-end cutter. The second example employs the swept surface generation method to solve a parameter optimization problem. Sensitivity analysis is performed for the parameters critical to machining accuracy. The third example optimizes the cutter orientation relative to the part surface to minimize the kinematics error caused by kinematics transformation and interpolation of multi-axis machines. [Copyright &y& Elsevier]

Abstract: This paper develops a novel computational technique to define and construct manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to an arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite its earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e.,  for any genus- surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications. Our new algorithm is founded upon the concept of discrete Ricci flow and associated techniques. First, Ricci flow is employed to compute a special metric of any manifold domain (serving as a parametric domain for manifold splines), such that the metric becomes flat everywhere except at one point. Then, the metric naturally induces an affine atlas covering the entire manifold except this singular point. Finally, manifold splines are defined over this affine atlas. The Ricci flow method is theoretically sound, and practically simple and efficient. We conduct various shape experiments and our new theoretical and algorithmic results alleviate the modeling difficulty of manifold splines, and hence, promote the widespread use of manifold splines in surface and solid modeling, geometric design, and reverse engineering. [Copyright &y& Elsevier]

Abstract: Increasing attention is being paid to complete machining, i.e., machining of the whole part in a single machine tool, in the metal working industry. For this purpose, complex machine tools equipped with machining components, such as multiple spindles and turrets have been developed by leading machine tool builders. The efficiency of complex machine tools is largely dependent on how the machining components are utilized. The main thrust of this paper is twofold: (1) Proposition of a nonlinear process planning based on the STEP-NC (STEP-compliant data interface for numerical controls) paradigm whose data model is formalized as ISO 14649, and (2) Development of an optimal solution algorithm for process planning for complex machining. The developed algorithm is based on the branch-and-bound approach and heuristics derived from engineering insights. The developed process planning method and optimization algorithm were implemented and tested via the TurnSTEP system developed by our research team. Through the experiments, we are convinced that the new process planning and algorithm can be used as a fundamental means for implementing the third type of STEP-NC [Suh S. TurnSTEP: Tools to create CNC turning programs. In: White paper presented on STEP Implementers’ Forum ISO TC184/SC4 Meeting. 2004], i.e., an Intelligent and Autonomous STEP-NC system for the CAD-CAM-CNC chain supporting e-Manufacturing. [Copyright &y& Elsevier]

Abstract: In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper. [Copyright &y& Elsevier]

In this paper, we present an efficient visibility-based algorithm for determining a locally exact shortest path (LESP) from a source point to a destination point on a (triangulated) polyhedral surface. Our algorithm, of a finitely-iterative scheme, evolves an initial approximately shortest path into a LESP. During each iteration, we first compute the exact shortest path restricted on the current face sequence according to Fermat’s principle which affirms that light always follows the shortest optical path, and then optimize the face sequence where the path is not locally shortest on the polyhedral surface. Since the series of paths we obtained are monotonic decreasing in length, the algorithm gives a LESP which is shorter than the initial path, at conclusion. For comparison, we use various methods to provide an initial path. One of the methods is Dijkstra’s algorithm, and the others are the Fast Marching Method (FMM) and its improved version. Our intention for improvement is to overcome the limitation of acute triangulations in the original version. To achieve this goal, we classify all the edges into seven types according to different wavefront propagation manners, and dynamically determine the type of each edge for controlling the subsequent wavefront expansion. Furthermore, we give two approaches for backtracing the approximately shortest paths directed at the improved FMM. One exploits the known propagation manners of the edges as well as the Euler’s method. This is another contribution in this paper. [Copyright &y& Elsevier]

A protein consists of linearly combined amino acids via peptide bonds, and an amino acid consists of atoms. It is known that the geometric structure of a protein is the primary factor which determines the functions of the protein. Given the atomic complex of a protein, one of the most important geometric structures of a protein is its molecular surface since this distinguishes between the interior and exterior of the protein and plays an important role in protein folding, docking, interactions between proteins, and other functions. This paper presents an algorithm for the precise and efficient computation of the molecular surface of a protein, using a recently proposed geometric construct called the -shape based on the Voronoi diagram of atoms in a protein. Given a Voronoi diagram of atoms, based on the Euclidean distance from the atom surfaces, the proposed algorithm first computes the -shape with an appropriate sized probe. Then, the molecular surface is computed by employing a blending operation on the atomic complex of the protein. In this paper, it is also shown that for a given Voronoi diagram of atoms, the multiple molecular surfaces can be computed by using various sized probes. [Copyright &y& Elsevier]

An improved grid-based algorithm for the adaptive generation of hexahedral finite element mesh is presented in this paper. It is named as the inside-out grid-based method and involves the following four steps. The first step is the generation of an initial grid structure which envelopes the analyzed solid model completely. And the elements size and density maps are constructed based on the surface curvature and local thickness of the solid model. Secondly, the core mesh is generated through removing all the undesired elements using even and odd parity rules. The third step is to magnify the core mesh in an inside-out manner through a surface node projection process using the closest position approach. To match the mesh to the characteristic boundary of the solid model, a minimal Scaled Jacobian criterion is employed. Finally, in order to handle the degenerated elements and improve the quality of the resulting mesh, two comprehensive techniques are employed: the insertion technique and collapsing technique. The present method was applied in the mesh construction of different engineering problems. Scaled Jacobian and Skew metrics are used to evaluate the hexahedral element mesh quality. The application results show that all-hexahedral element meshes which are well-shaped and capture all the geometric features of the original solid models can be generated using the inside-out grid-based method presented in this paper. [Copyright &y& Elsevier]

This paper describes algorithms for generating shapes of side actions to minimize a customizable injection moulding cost function. Given a set of undercut facets on a polyhedral part and the main mold opening directions, our approach works in the following manner: first, we compute candidate retraction space for every undercut facet. This space represents the set of candidate translation vectors that can be used by the side action to completely disengage from the undercut facet. As the next step, we generate a discrete set of feasible, nondominated retractions. Then we group the undercut facets into undercut regions by performing state space search over such retractions. This search step is performed by minimizing the given moulding cost function. After identifying the undercut regions, we generate the shapes of individual side actions. We believe that the results presented in this paper will provide the foundations for developing fully automated software for designing side actions. [Copyright &y& Elsevier]

The Medial Axis Transform surface, (or MAT or MS) is proving to be a useful tool for several applications and geometric reasoning tasks. However, calculation of the MAT is a time-consuming task and the benefits of the mathematical-based tool are offset by the cost of the calculation. This paper presents a method for medial surface calculation which uses subdivision to simplify the problem and hence speed up the calculation, a so-called ‘divide-and-conquer’ approach. The basis for this is a modification of the dual structure of the original object. As the calculation proceeds this structure is broken up into sub-pieces each representing a simpler sub-part of the MAT. Perhaps more importantly, this method creates a correct node decomposition of the dual structure. The paper goes on to demonstrate some applications of the results for geometric tasks, specifically offsetting and model subdivision, which are normally expensive but are simpler based on the MAT calculation results. [Copyright &y& Elsevier]

In this paper, we present a BPM (Bézier patch mapping) algorithm which generates a strictly non-self-overlapping structured quadrilateral grid in a given four-sided planar region. Given four pieces of polynomial curves which enclose a simple region in the plane, the algorithm first constructs a Bézier patch which interpolates the four curves (as its four boundary curves), while the inner control points of its control grid remain unknown. In this paper, we show that, for the bijective condition to be satisfied, it is sufficient that the interior points satisfy a set of quadratic inequality equations. Exploiting this key result, we formulate the mapping algorithm as an optimization problem where the constraints are the bijective condition of the Bézier patch mapping (BPM), and the objective is to find out the best from all of the non-self-overlapping grids. Thus, commercial optimization solvers can be used to find the bijective mapping. If a solution to the optimization problems exists, then so does a solution to the mapping problem, and vice-versa. The BPM method is simple and intuitive, and some examples presented in this paper demonstrate its effectiveness. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for automatically computing the planar patterns of custom-made assistive medical braces, which are employed to restrict the motion of the joints (such as wrist and knee) that suffer from musculoskeletal disorders caused by repetitive strain injuries. An elastic brace is manufactured by warping a planar elastic fabric pattern. With a specified material, different shapes of planar patterns for producing a brace will generate different biomechanical effects on the joint. As an assistive medical device, an elastic brace is often requested to provide certain normal pressures at certain specific locations on the joint. Traditionally the planar pattern of a brace respecting the prescribed normal pressure requirement is designed through empirical tests by trial-and-error. We develop a woven fitting based method in this paper to automate this geometric design process. [Copyright &y& Elsevier]

Abstract: As STEP-NC emerges as the new CNC control method and a fundamental means for realizing e-manufacturing, old manufacturing information based on the conventional manufacturing standard will become obsolete. In practice, replacement of G-code based part programs into STEP-NC is a huge task. In this paper, methods to interpret G-code based part programs into STEP-NC code are investigated. G-code is a compact, coded set of numbers for axis movements, while STEP-NC is very comprehensive and includes information about features, operations, strategies, cutting tools, and so on. It is thus very challenging to derive such comprehensive information from the low level G-code information. In this paper, we first clarify what should be given and what may be given, and then present algorithms for deriving STEP-NC information, such as geometric features, operations, etc., from the tool movement (G-code) based on expert reasoning. The algorithms are developed for the turning application. The developed algorithms were implemented and tested on G-code part programs used in actual practice. [Copyright &y& Elsevier]

Abstract: This paper presents algorithms for identifying machined parts in a database that are similar to a given query part based on machining features. In this paper we only consider parts that are machined on 3-axis machining centers. We utilize reduced feature vectors consisting of machining feature access directions, feature types, feature volumes, feature dimensional tolerances and feature group cardinality as a basis for assessing shape similarity. We have defined a distance function between two sets of reduced feature vectors to assess the similarity between them from the machining effort point of view. To assess the similarity between the two parts, one set of reduced feature vectors is transformed in space using rigid body transformations with respect to the other set such that the distance between them is minimized. The distance between the two sets of aligned reduced feature vectors is used as a measure of similarity between the two parts. The existing machined parts are rank ordered based on the value of the distance with respect to the query part. The cost of previously machined parts that have a very small distance from the query part can be used as a basis for estimating the cost of machining the new part. [Copyright &y& Elsevier]

Abstract: Ensuring that geometric models have the required draft angle is very important for many manufacturing applications. In this paper an algorithm is presented that ensures that 2D B-splines fitted to point data will have a specified draft angle. First, sufficient conditions are derived that will be used as constraints in the least squares fitting of B-splines to the point data. A Least SQuares fitting algorithm with Draft Angle Constraints (LSQ-DAC) is developed. The algorithm is compared to two non-linear programming methods, the Augmented Lagrange Multiplier method and the Sequential Quadratic Programming method. The paper concludes with a case study showing the application in 3D. [Copyright &y& Elsevier]

Abstract: The Apollonius Tenth Problem, as defined by Apollonius of Perga circa 200 B.C., has been useful for various applications in addition to its theoretical interest. Even though particular cases have been handled previously, a general framework for the problem has never been reported. Presented in this paper is a theory to handle the Apollonius Tenth Problem by characterizing the spatial relationship among given circles and the desired Apollonius circles. Hence, the given three circles in this paper do not make any assumption regarding on the sizes of circles and the intersection/inclusion relationship among them. The observations made provide an easy-to-code algorithm to compute any desired Apollonius circle which is computationally efficient and robust. [Copyright &y& Elsevier]

Abstract: Precision z-level contour machining is important for various computer-aided manufacturing (CAM) applications such as pocket machining and high-speed machining (HSM). This paper presents a new z-level contour tool-path generation algorithm for NC machining of triangulated surface models. Traditional approaches of z-level machining rely on the creation of accurate CL (cutter location) surfaces by surface offsetting or high-density z-map generation, which is computationally expensive and memory demanding. In contrast, this paper presents a novel approach to the generation of CL data directly from the section polygon of a triangulated surface model. For each polygon vertex of the contour, the offset direction is determined by the normal to the edge, while the offset distance is not fixed but is determined from the cutter shape and the part surface. An interference-free tool-path computation algorithm using fillet endmills is developed. Since there is no need to create a complete CL surface or high-density z-map grids, this proposed method is highly efficient and more flexible, and can be directly applied to triangulated surfaces either tessellated from CAD models, or reconstructed from 3D scanned data for reverse engineering (RE) applications. [Copyright &y& Elsevier]

Abstract: Current methods for recognition and interpretation of architectural drawings are limited to either low-level analysis of paper drawings or interpretation of electronic drawings that depicts only high-level design entities. In this paper, we propose a Self-Incremental Axis-Net-based Hierarchical Recognition (SINEHIR) model for automatic recognition and interpretation of real-life complex electronic construction structural drawings. We design and implement a series of integrated algorithms for recognizing dimensions, coordinate systems and structural components. We tested our approach on more than 200 real-life drawings. The results show that the average recognition rate of structural components is about 90%, and the computation time is significantly shorter than manual estimation time. [Copyright &y& Elsevier]

Abstract: A new method for 5-axis CNC tool positioning is presented in this paper that improves upon a previous tool positioning strategy named the rolling ball method (RBM), which was developed by the present authors [Gray P, Bedi F, Ismail S. Rolling ball method for 5-axis surface machining. Comput Aided Des 2003;35(4):347–57]. The special property of the RBM is that it computes tool positions by considering the area beneath the tool that the tool will be positioned to cut instead of using surface curvatures computed at a single point on the surface. This enables the RBM to generate gouge-free tool positions without secondary iterative gouge-check and correction algorithms. However, the RBM generates conservative tilt angles in order to guarantee gouge-free tool positions. The new arc-intersect method (AIM) presented in this paper improves upon the RBM by directly positioning the tool to contact the surface and thereby eliminates the conservative nature of the RBM to give optimal tool positions. Like the RBM, the AIM is an area-based method that generates gouge-free tool positions without the use of iterative gouge-check and correction algorithms. The implementation described in this paper uses triangulated surfaces and the computer''s graphics hardware to assist in the tool position calculations. However, the method can be applied to any surface representation since it only uses surface coordinates and surface normals for computation. A section of a stamping die was machined to demonstrate the AIM and to show the improvement over the RBM and for comparison with 3-axis ballnose machining. The results showed that the AIM was 1.33 times faster than the RBM and that the AIM, with single direction parallel tool passes, was 1.62 times faster than a zig-zag pattern 3-axis ballnose tool path for the same feed rate, cusp height and tool diameter. The workpieces were measured with a CMM and the data were compared to the CAD model to show no gouging occurred and to check the cusp heights. [Copyright &y& Elsevier]

Abstract: In rapid prototyping, we can significantly reduce the building time and expensive RP material consumption by building a hollowed prototype instead of a solid model. Presented in the paper is a new method to hollow out solid objects with uniform wall thickness to speed up the part building processes in rapid prototyping systems. To achieve uniform wall thickness, it is necessary to generate internal contours by slicing the offset model of an STL model. Since computing an offset model of an STL model involves many difficulties, this paper proposes a new algorithm that computes internal contours without computing the offset model. The proposed algorithm is efficient and relatively easy to implement, because it employs well-known 2D geometric algorithms, such as planar curve offsetting and tracing innermost curves. Various examples have been tested with implementation of the algorithm, and some examples are presented for illustration. [Copyright &y& Elsevier]

This paper presents a new approach for the sampling of sculptured surfaces using continuous scanning coordinate measuring machine probe heads. This approach is based on scanning isoparametric lines on the sculptured surface. This paper addresses the issue of isoparametric line sampling. The problem is to determine the locations of the sample lines extracted from the surface CAD model. These lines are fitted to construct a substitute geometry of the surface. The accuracy of the sampling plan is characterised by the maximum deviation between the substitute geometry and the surface CAD model. Two new algorithms for sampling isoparametric lines are proposed. These are, automatic sampling, and surface curvature-based sampling. Both algorithms are constrained by the maximum number of scan lines, and the step over distance between subsequent sample lines. Automatic sampling uses the deviations between the substitute geometry, and the surface CAD model to determine the sample locations. Curvature change-based sampling uses the change in surface curvature to determine the sampling line locations. Both algorithms are compared to uniform iso-planar sampling. The algorithms, their implementation, and a case study are presented in this paper. [Copyright &y& Elsevier]

This paper describes a system and underlying algorithms to perform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank-orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used by designers and process planners to find an existing part that can be used as a stock to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products. [Copyright &y& Elsevier]