Perspective silhouette of a general swept volume

We present an efficient and robust algorithm for computing the perspective silhouette of the boundary of a general swept volume. We also construct the topology of connected components of the silhouette. At each instant t, a three-dimensional object moving along a trajectory touches the envelope surface of its swept volume along a characteristic curve K^t. The same instance of the moving object has a silhouette curve L^t on its own boundary. The intersection K^t∩L^t contributes to the silhouette of the general swept volume. We reformulate this problem as a system of two polynomial equations in three variables. The connected components of the resulting silhouette curves are constructed by detecting the instances where the two curves K^t and L^t intersect each other tangentially on the surface of the moving object. We also consider a general case where the eye position changes while moving along a predefined path. The problem is reformulated as a system of two polynomial equations in four variables, where the zero-set is a two-manifold. By analyzing the topology of the zero-set, we achieve an efficient algorithm for generating a continuous animation of perspective silhouettes of a general swept volume.     

Computing swept volumes

The swept volume problem is practical, difficult and interesting enough to have received a great deal of attention over the years, and the literature contains much discussion of methods for computing swept volumes in many situations. The method presented here permits an arbitrary polyhedral object (given in a typical boundary representation) to be swept through an arbitrary trajectory. A polyhedral approximation to the volume swept by this moving object is computed and output in a typical boundary representation. A number of examples are presented demonstrating the practicality of this method. Copyright © 2000 John Wiley & Sons, Ltd.     

Complete swept volume generation — Part II: NC simulation of self-penetration via comprehensive analysis of envelope profiles

In this paper the swept volume with self-penetration (or self-intersection) of the cutter is presented. The complete swept volume (SV), which describes the side and bottom shape of a milling cutter undergoing self-penetration, is generated by using the Gauss map method proposed in the authors’ previous paper [Lee SW, Nestler A. Complete swept volume generation—part I: swept volume of a piecewise C¹-continuous cutter at five-axis milling via Gauss map. Computer-Aided Design 2011; 43(4): 427–41]. Based on the Gauss map method, the comprehensive analysis of envelope profiles of the tool is accomplished. Through the analysis the necessary condition of the self-penetration of the cutter at five-axis movement is identified. After having classified movement types of the milling cutter in an in-depth manner, the topologically consistent boundary of SV is generated by trimming the invalid facets interior to the SV. To demonstrate the validity of the proposed method, a cutting simulation kernel for five-axis machining has been implemented and applied to cavity machining examples such as intake ports of automobile engines and so forth where the self-penetration occurs. The proposed method is proved to be robust and amenable for the practical purpose of the NC simulation.     

Polygonal extrusion

A sweeping operation called polygonal extrusion is defined to improve the modeling power of CSG-based modeling. It is assumed that a 2D cross-sectional polygon (sweeping polygon) moves in space while its containing plane is kept orthogonal to the tangent direction of the trajectory curve, a planar polygonal chain having no self-intersections. The objective of the paper is to compute the boundary of the swept volume of the sweeping polygon as a set of polygons (or triangles). The most significant challenge to accomplishing this objective is the problem of trimming the swept volume. To solve the trimming problem, 2D-curve offsetting methods are employed. Two algorithms are presented for polygonal extrusion that are based on different offsetting methods, the Voronoi diagram and PWID offset. The proposed algorithms have been implemented and tested with various examples. Published online: 28 January 2003     

Boundary of the volume swept by a free-form solid in screw motion

The swept volume of a moving solid is a powerful computational and visualization concept. It provides an excellent aid for path and accessibility planning in robotics and for simulating various manufacturing operations. It has proven difficult to evaluate the boundary of the volume swept by a solid bounded by trimmed parametric surfaces undergoing an arbitrary analytic motion. Hence, prior solutions use one or several of the following simplifications: (1) approximate the volume by the union of a finite set of solid instances sampled along the motion; (2) approximate the curved solid by a polyhedron; and (3) approximate the motion by a sequence of simpler motions. The approach proposed here is based on the third type of simplification: it uses a polyscrew (continuous, piecewise-helical) approximation of the motion. This approach leads to a simple algorithm that generates candidate faces, computes the two-cells of their arrangement, and uses a new point-in-sweep test to select the correct cells whose union forms the boundary of the swept volume.     

Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes

We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self‐intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane‐based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.     

Boundary Constrained Swept Surfaces for Modelling and Animation

Due to their simplicity and intuitiveness, swept surfaces are widely used in many surface modelling applications. In this paper, we present a versatile swept surface technique called the boundary constrained swept surfaces. The most distinct feature is its ability to satisfy boundary constraints, including the shape and tangent conditions at the boundaries of a swept surface. This permits significantly varying surfaces to be both modelled and smoothly assembled, leading to the construction of complex objects. The representation, similar to an ordinary swept surface, is analytical in nature and thus it is light in storage cost and numerically very stable to compute. We also introduce a number of useful shape manipulation tools, such as sculpting forces, to deform a surface both locally and globally. In addition to being a complementary method to the mainstream surface modelling and deformation techniques, we have found it very effective in automatically rebuilding existing complex models. Model reconstruction is arguably one of the most laborious and expensive tasks in modelling complex animated characters. We demonstrate how our technique can be used to automate this process.     

Complete swept volume generation, Part I: Swept volume of a piecewise C-continuous cutter at five-axis milling via Gauss map

In this paper, we present a methodology to generate swept volume of prevailing cutting tools undergoing multi-axis motion and it is proved to be robust and amenable for practical purposes with the help of a series of tests. The exact and complete SV, which is closed from the tool bottom to the top of the shaft, is generated by stitching up envelope profiles calculated by Gauss map.The novel approach finds the swept volume boundary for five-axis milling by extending the basic idea behind Gauss map. It takes piecewise C¹-continuous tool shape into account. At first, the tool shape is transformed from Euclidean space into Tool map (T-Map) on the unit sphere and the velocity vector of a cutter is transformed into Contact map (C-Map) using Gauss map. Then, closed intersection curve is found between T-Map and C-Map on the Gaussian sphere. At last, the inverse Gauss map is exploited to get envelope profile in Euclidean space from the closed curve in the range. To demonstrate its validity, a cutting simulation kernel for five-axis machining has been implemented and applied to mold and die machining.     

High accuracy NC milling simulation using composite adaptively sampled distance fields

We describe a new approach to shape representation called a composite adaptively sampled distance field (composite ADF) and describe its application to NC milling simulation. In a composite ADF each shape is represented by an analytic or procedural signed Euclidean distance field and the milled workpiece is given as the Boolean difference between distance fields representing the original workpiece volume and distance fields representing the volumes of the milling tool swept along the prescribed milling path. The computation of distance field of the swept volume of a milling tool is handled by an inverted trajectory approach where the problem is solved in tool coordinate frame instead of a world coordinate frame. An octree bounding volume hierarchy is used to sample the distance functions and provides spatial localization of geometric operations thereby dramatically increasing the speed of the system. The new method enables very fast simulation, especially of free-form surfaces, with accuracy better than 1 micron, and low memory requirements. We describe an implementation of 3 and 5-axis milling simulation.     

Optimality and competitiveness of exploring polygons by mobile robots

A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics.We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.     

Precise algebraic-based swept volumes for arbitrary free-form shaped tools towards multi-axis CNC machining verification

This paper presents an algebraic based approach and a computational framework for the simulation of multi-axis CNC machining of general freeform tools. The boundary of the swept volume of the tool is precisely modeled by a system of algebraic constraints, using B-spline basis functions. Subdivision-based solvers are then employed to solve these equations, resulting in a topologically guaranteed construction of the swept volume. The presented algebraic-based method readily generalizes to accept tools of arbitrary free-form shape as input, and at the same time, delivers high degree of precision.Being a common representation in CNC simulations, the computed swept volume can be reduced to a dexels’ representation. Several multi-axis test cases are exhibited using an implementation of our algorithm, demonstrating the robustness and efficacy of our approach.     

Local and global analysis of parametric solid sweeps

In this work, we propose a structured computational framework for modelling the envelope of the swept volume, that is the boundary of the volume obtained by sweeping an input solid along a trajectory of rigid motions. Our framework is adapted to the well-established industry-standard brep format to enable its implementation in modern CAD systems. This is achieved via a “local analysis”, which covers parametrizations and singularities, as well as a “global theory” which tackles face-boundaries, self-intersections and trim curves. Central to the local analysis is the “funnel” which serves as a natural parameter space for the basic surfaces constituting the sweep. The trimming problem is reduced to the problem of surface–surface intersections of these basic surfaces. Based on the complexity of these intersections, we introduce a novel classification of sweeps as decomposable and non-decomposable. Further, we construct an invariant function θ on the funnel which efficiently separates decomposable and non-decomposable sweeps. Through a geometric theorem we also show intimate connections between θ, local curvatures and the inverse trajectory used in earlier works as an approach towards trimming. In contrast to the inverse trajectory approach of testing points, θ is a computationally robust global function. It is the key to a complete structural understanding, and an efficient computation of both, the singular locus and the trim curves, which are central to a stable implementation. Several illustrative outputs of a pilot implementation are included.     

A comparison of sampling strategies for computing general sweeps

Sweeping moving objects has become one of the basic geometric operations used in engineering design, analysis and physical simulation. Despite its relevance, computing the boundary of the set swept by a non-polyhedral moving object is largely an open problem due to well-known theoretical and computational difficulties of the envelopes.We have recently introduced a generic point membership classification (PMC) test for general solid sweeping. Importantly, this PMC test provides complete geometric information about the set swept by the moving object, including the ability to compute the self-intersections of the sweep itself. In this paper, we compare two recursive strategies for sampling points of the space in which the object moves, and show that the sampling based on a fast marching cubes algorithm possesses the best combination of features in terms of performance and accuracy for the boundary evaluation of general sweeps. Furthermore, we show that the PMC test can be used as the foundation of a generic sweep boundary evaluator in conjunction with efficient space sampling strategies for solids of arbitrary complexity undergoing affine motions.     

The differential equation algorithm for general deformed swept volumes

The differential equation approach for characterizing swept volume boundaries is extended to include objects experiencing deformation.For deformed swept volume,it is found that the structure and algorithm of sweep-envelope differential equation(SEDE)are similar between the deformed and the rigid swept volumes.The efficiency of SEDE approach for deformed swept volume is proved with an example.     

数控加工仿真系统的研究与应用

介绍数控加工仿真系统的整体设计,提出格栅voxel三维实体建模方法,刀具扫描体的生成算法,实现了刀具切削工件过程的动态仿真,并对碰撞检查算法进行了初步的研究.基于以上方法,建立了蓝天数控系统的加工仿真系统,在加工前对加工程序进行验证,在加工时对刀具轨迹的执行、工件的切削过程等进行实时监控.     

Approximate General Sweep Boundary of a 2D Curved Object

This paper presents an algorithm to compute an approximation to the general sweep boundary of a 2D curved moving object which changes its shape dynamically while traversing a trajectory. In effect, we make polygonal approximations to the trajectory and to the object shape at every appropriate instance along the trajectory so that the approximated polygonal sweep boundary is within a given error bound ϵ > 0 from the exact sweep boundary. The algorithm interpolates intermediate polygonal shapes between any two consecutive instances, and constructs polygons which approximate the sweep boundary of the object. Previous algorithms on sweep boundary computation have been mainly concerned about moving objects with fixed shapes; nevertheless, they have involved a fair amount of symbolic and/or numerical computations that have limited their practical uses in graphics modeling systems as well as in many other applications which require fast sweep boundary computation. Although the algorithm presented here does not generate the exact sweep boundaries of objects, it does yield quite reasonable polygonal approximations to them, and our experimental results show that its computation is reasonably fast to be of a practical use.     

Sweeping of an object held by a robotic end-effector

A broadly applicable formulation for calculating the swept volume generated by an object held by a manipulator's end-effector is presented. While the problem of determining the workspace of a robot arm has been extensively addressed in the literature, this rarely addressed problem is of significance to path planning, collision detection, plant layout, and robot design. The totality of points touched by a geometric entity moved in space using a number of joints is defined as the swept volume. The formulation and accompanying experimental code are presented and are aimed at providing the reader with a replicable computer algorithm. Calculating the swept volume is based on The Implicit Function theorem and is shown to be any number of degrees of freedom yielding the exact representation of the swept volume. By considering the sweep equation as a vector function defined on a manifold (possibly with boundaries), it is shown that stratification of the various sub-manifolds yields varieties that can be depicted in R³. A measure of the computational complexity is presented to give the reader a sense of the robustness of this method as well as its difficulties. An experimental computer code is developed using a symbolic manipulator that performs the automated calculations necessary to calculate the varieties and to visualize the manifold.