Search

The optimal feedrate planning problem for the five-axis parametric tool path remains challenging due to the nonlinear relationships between the joint space and the Cartesian space. We present a novel and complete optimal feedrate planning method for a five-axis parametric tool path by constraining the velocity, acceleration, jerk in the joint space, and the chord error in the Cartesian space. Our method formulates the problem as an optimal control problem, and we propose an iteration control vector parametrization method to compute the optimal solution. Compared with the new development five-axis feedrate planning methods, our solution satisfies “bang-bang” optimal control, and each constraint is strictly under the limits globally. Examples and comparisons with two other methods are demonstrated to show the effectiveness of the algorithm.

The μ-basis is a developing algebraic tool to study the expressions of rational curves and surfaces. It can play a bridge role between the parametric forms and implicit forms and show some advantages in implicitization, inversion formulas and singularity computation. However, it is difficult and there are few works to compute the μ-basis from an implicit form. In this paper, we derive the explicit forms of μ-basis for implicit monoid curves and surfaces, including the conics and quadrics which are particular cases of these entities. Additionally, we also provide the explicit form of μ-basis for monoid curves and surfaces defined by any rational parametrization (not necessarily in standard proper form). Our technique is simply based on the linear coordinate transformation and standard forms of these curves and surfaces. As a practical application in numerical situation, if an exact multiple point can not be computed, we can consider the problem of computing “approximate μ-basis” as well as the error estimation., Agencia Estatal de Investigación

A rational translational surface is a typical modeling surface used in computer-aided design and the architecture industry. In this study, we determine whether a given algebraic surface implicitly defined as V is a rational translational surface or not. This problem is reduced to finding the rational parameterizations of two space curves. More important, our discussions are constructive, and thus if V is translational, we provide a parametric representation of V of the form P(t1,t2)=P1(t1)+P2(t2)., Agencia Estatal de Investigación

Tool path generation is a fundamental problem in 5-axis CNC machining, which consists of tool orientation planning and cutter-contact (CC) point planning. The planning strategy highly depends on the type of tool cutters. For ball-end cutters, the tool orientation and CC point location can be planned separately; while for flat end cutters, the two are highly dependent on each other. This paper generates a smooth tool path of workpiece surfaces for flat end mills from two stages: Computing smooth tool orientations on the surface without gouging and collisions and then designing the CC point path. By solving the tool posture optimization problem the authors achieve both the path smoothness and the machining efficiency. Experimental results are provided to show the effectiveness of the method.

For points $(a,b)$ on an algebraic curve over a field $K$ with height $\mathfrak{h}$, the asymptotic relation between $\mathfrak{h}(a)$ and $\mathfrak{h}(b)$ has been extensively studied in diophantine geometry. When $K=\overline{k(t)}$ is the field of algebraic functions in $t$ over a field $k$ of characteristic zero, Eremenko in 1998 proved the following quasi-equivalence for an absolute logarithmic height $\mathfrak{h}$ in $K$: Given $P\in K[X,Y]$ irreducible over $K$ and $\epsilon>0$, there is a constant $C$ only depending on $P$ and $\epsilon$ such that for each $(a,b)\in K^2$ with $P(a,b)=0$, $$ (1-\epsilon) \deg(P,Y) \mathfrak{h}(b)-C \leq \deg(P,X) \mathfrak{h}(a) \leq (1+\epsilon) \deg(P,Y) \mathfrak{h}(b)+C. $$ In this article, we shall give an explicit bound for the constant $C$ in terms of the total degree of $P$, the height of $P$ and $\epsilon$. This result is expected to have applications in some other areas such as symbolic computation of differential and difference equations.

In computer numerical control systems, linear segments, which are generated by computer-aided manufacturing software, are the most widely used toolpath format. Since the linear toolpath is discontinuous at the junction of two adjacent segments, the fluctuations on velocity, acceleration and jerk are inevitable. Local corner smoothing is widely used to address this problem. However, most existing methods use symmetrical splines to smooth the corners. When any one of the linear segments at the corner is short, to avoid overlap, the inserted spline will be micro, thereby increasing the curvature extreme of the spline and reducing the feedrate along it. In this article, the corners are smoothed by a 𝐶4 continuous asymmetric Pythagorean-hodograph (PH) spline. The curvature extreme of the proposed spline is investigated first, and 𝐾=2.5 is determined as the threshold to constarin the asymmetry of the spline. Then a two-step strategy is used to generate a blended toolpath composed of asymmetric PH splines and linear segments. In the first step, the PH splines at the corners are generated under the premise that the transition lengths do not exceed half of the length of the linear segments. In the second step, the splines at the corners are re-planned to reduce the curvature extremes, if the transition error does not reach the given threshold and there are extra linear trajectories on both sides of the spline trajectory. Finally, the bilinear interpolation method is applied to determine the critical points of the smoothed toolpath, and a jerk-continuous feedrate scheduling scheme is presented to interpolate the smoothed toolpath. Simulations show that, under the condition of not affecting the machining quality, the proposed method can improve the machining efficiency by 7.84% to 23.98% compared to 𝐺3 and 𝐺4 methods.

We present a novel method to segment CAD models into developable patches by detecting curve-like features on Gauss images of the corresponding patches. A region-growing approach is employed to detect planar and curved developable patches. The Gauss image of each segmented patch is constrained to be curve-like via principal component analysis and Pearson correlation analysis. Experimental results demonstrate that our approach generates nice results on CAD models with all kinds of developable surfaces.

Implicit is a package for implicitizing rational planar curves and rational tensor product surfaces, developed on Maplesoft based on the state-of-the-art implicitization techniques. The main functions ImpCurve and ImpSurface return the implicit equation of a rational planar curve or a rational tensor product surface. Other popularly used functions, such as ImpDegree, ImpMatrix and ImpRuled that are used for deciding the implicit degree and the implicit matrix of a general rational surface, and computing the implicit equation of a rational ruled surface in a more efficient way, are also proposed.

In CNC machining, the tool path following G01 codes generally introduces large computations and inherent discontinuities. A common way to avoid these shortcomings is fitting the G01 polyline with a parametric curve and then scheduling the feedrate along the fitted curve. However, curve fitting with confined error in three dimensional space is nontrivial since the Hausdorff distance between a space G01 segment and a rational parametric curve segment is difficult to formulate. In this paper, we derive the explicit expression for the Hausdorff distance between a line segment and a curve segment, and then propose a curve fitting algorithm for G01 polylines. Instead of the traditional two-stage model, we present a combined trajectory planning model with error constraints as well as dynamic constraints. Moreover, an effective and efficient algorithm is designed to solve this model. Experimental results are provided to illustrate and clarify our methods.

This paper presents symbolic algorithms to determine whether a given surface (implicitly or parametrically defined) is a rational ruled surface and find a proper parametrization of the ruled surface. However, in practical applications, one has to deal with numerical objects that are given approximately, probably because they proceed from an exact data that has been perturbed under some previous measuring process or manipulation. For these numerical objects, the authors adapt the symbolic algorithms presented by means of the use of numerical techniques. The authors develop numeric algorithms that allow to determine ruled surfaces "close" to an input (not necessarily ruled) surface, and the distance between the input and the output surface is computed., Agencia Estatal de Investigación, National Natural Science Foundation of China

We present an algorithm to implicitize rational tensor product surfaces that works correctly and efficiently even in the presence of base points by combining three complementary approaches, some classical and some novel, to implicitization. One straightforward method is to implicitize these surfaces using the Dixon A -resultant of three obvious syzygies. For surfaces that cannot be implicitized using this resultant due, for example, to the presence of base points, we try the method of moving planes and moving quadrics. We show that this method works very well on surfaces with simple base points. For general rational surfaces that cannot be implicitized by these two methods, we refine the method that employs the resultant matrix of three low bidegree moving planes by providing a simple technique to construct this resultant matrix. To avoid computing the base points explicitly, we compute the extraneous factors associated to the base points by solving a system of polynomial equations with a finite number of solutions.

Implicitizing rational surfaces is a fundamental computational task in Computer Graphics and Computer Aided Design. Ray tracing, collision detection, and solid modeling all benefit from implicitization procedures for rational surfaces. The univariate resultant of two moving lines generated by a μ-basis for a rational curve represents the implicit equation of the rational curve. But although the multivariate resultant of three moving planes corresponding to a μ-basis for a rational surface is guaranteed to contain the implicit equation of the surface as a factor, μ-bases for rational surfaces are difficult to compute. Moreover, μ-bases for a rational surface often have high degrees, so these resultants generally contain many extraneous factors. Here we develop fast algorithms to implicitize rational tensor product surfaces by computing the resultant of three moving planes corresponding to three syzygies with low degrees. These syzygies are easy to compute, and the resultants of the corresponding moving planes generally contain fewer extraneous factors than the resultants of the moving planes corresponding to μ-bases. We predict and compute all the possible extraneous factors that may appear in these resultants. Examples are provided to clarify and illuminate the theory.

Implicitizing rational surfaces is a fundamental computational task in Algorithmic Algebraic Geometry. Although the resultant of a -basis for a rational surface is guaranteed to contain the implicit equation of the surface as a factor, this resultant may also contain extraneous factors. Moreover, -bases for rational surfaces are, in general, notoriously difficult to compute. Here we develop fast algorithms to find -bases for rational tensor product surfaces whose resultants are guaranteed to be the implicit equation of the corresponding rational surface with no extraneous factors. We call these -bases strong -bases. Surfaces with strong -bases are relatively rare. We show how these strong -bases are related to the number of base points counting multiplicity of the corresponding surface parametrization. In addition, when the base points are simple, we provide tables of rational tensor product surfaces with strong -bases based on the bidegree of the rational surface and the number of base points of the parametrization. The bidegrees of the corresponding strong -bases are also listed in these tables. Present fast algorithms for finding strong -bases for rational tensor product surfaces.Show the relationship between the strong -bases and the number of certain base points counting multiplicity.Provide some tables of rational tensor product surfaces with strong -bases and the number of simple base point.

We investigate conditions under which the resultant of a $\mu$-basis for a rational tensor product surface is the implicit equation of the surface without any extraneous factors. In this case, we also derive a formula for the implicit degree of the rational surface based only on the bidegree of the rational parametrization and the bidegrees of the elements of the $\mu$-basis without any knowledge of the number or multiplicities of the base points, assuming only that all the base points are local complete intersections. We conclude that in this case the implicit degree of a rational surface of bidegree $(m,n)$ is at most $mn$, so the rational surface must have at least $mn$ base points counting multiplicity. When the resultant of a $\mu$-basis generates extraneous factors, we show how to predict and compute these extraneous factors from either the existence of bad base points or anomalies occurring in the parametrization at infinity. Examples are provided to flesh out the theory.

Given a real rational parametrization P(t) of a plane curve C, we present an algorithm to compute polynomial curves to approximate C for the whole parameter domain. In this case, the denominators often have real roots in the whole interval. We decompose the interval as the union of finitely many intervals according to the real roots of the denominators. The key technique of the paper is to approximate the given curve by their asymptotes and error analysis at each interval is also presented. The asymptotes are associated with the infinity points corresponding to the real roots of the denominators. Numeric algorithms and examples are proposed to illustrate our results., Agencia Estatal de Investigación

Simplifying rational parametrizations of surfaces is a basic problem in CAD (computer-aided design). One important way is to reduce their tracing index, called proper reparametrization. Most existing proper reparametrization work is symbolic, yet in practical environments the surfaces are usually given with perturbed coefficients hence need a numerical technique of reparametrization considering the intrinsic properness of the perturbed surfaces. We present algorithms for reparametrizing a numerically rational space curve or surface. First, we provide an efficient way to find a parametric support transformation and compute a reparametrization with proper parametric support. Second, we develop a numerical algorithm to further reduce the tracing index, where numerical techniques such as sparse interpolation and approximated GCD computations are involved. We finally provide the error bound between the given rational curve/surface and our reparametrization result., Agencia Estatal de Investigación

The μ-basis of a rational curve/surface is a new algebraic tool which plays an important role in connecting the rational parametric form and the implicit form of a rational curve/surface. However, most results for μ-bases are presented for proper rational parametrizations. In this paper we consider the μ-basis for an improper rational planar curve. Based on the known properties and new results, we design two new proper reparametrization algorithms using μ-basis. The inversion, degree of the induced rational map and implicitization formulas are also derived.

We find a µ-basis for a rational ruled surface, starting from its implicit representation. A parametrization for this ruled surface is then deduced form this µ-basis. This parametrization does not have any non-generic base points and its directrix has the lowest possible degree. A complete interchange graph is built for the algebraic equation, the µ-basis and the parametric equation of a rational ruled surface. An algorithm is presented to compute µ-basis from algebraic ruled surfaces.An alternatively simpler method is given to determine and parameterize algebraic ruled surfaces.An interchange graph is built for the different representations of a rational ruled surface.

Collision avoidance is a fundamental problem in five-axis tool path planning. A two-step frame is widely used in tool path generation, that is, to determine C-spaces and then to design collision free pathes in the C-spaces. We present a feasible C-space computation algorithm for triangular mesh models based on collision-cone computation and stereographic projection. Then we sample points in the free area at each CC point and generate a tool orientation using the graph-based method. We also introduce a difference graph to find a smoother tool orientation. Experimental results show that the accelerations and velocities of the rotation axes are much smoother than those given by Plakhotnik and Lauwers (Int J Adv Manuf Technol 74:307–318, 2014).

In this study, we describe the intersection of three conics based on the singularities of their corresponding Jacobian curve. In particular, we show that certain singular points and sub-lines of the Jacobian curve are the precise common points and common tangent lines of the conics, respectively. Based on our results, these points or the tangent line can be computed as the singularities of the Jacobian curve. These results facilitate investigations of the relationships between a net of conics and their Jacobian curve.

In CNC machining, fitting the polyline machining tool path with parametric curves can be used for smooth tool path generation and data compression. In this paper, an optimization problem is solved to find a quadratic B-spline curve whose Hausdorff distance to the given polyline tool path is within a given precision. Furthermore, adopting time parameter for the fitting curve, we combine the usual two stages of tool path generation and optimal velocity planning to derive a one-step solution for the CNC optimal interpolation problem of polyline tool paths. Compared with the traditional decoupled model of curve fitting and velocity planning, experimental results show that our method generates a smoother path with minimal machining time. The explicit Hausdorff distance of a line segment and a quadratic curve is given.G01 codes can be fitted by quadratic B-splines with confined error.We combine the tool path generating and optimal velocity planning in one step.We simulate the manufacture process with our proposed method.

Traditional support vector machines have low classification performance on unbalanced datasets and are more influenced by dataset noise, which can lead to a deviation of the classification results. To address this problem, other studies have proposed fuzzy support vector machines for unbalanced datasets. However, most of these algorithms are directed to the second-class classification problem and their fuzzy membership functions typically only consider the distance factor, failing to accurately reflect the importance of training sample points. In this paper, a fuzzy multiclass support vector machine algorithm for unbalanced data is proposed. The algorithm uses the distance from the training sample point to the center of its class and a weighted class-overlap method to design the sample fuzzy membership function. Corresponding membership values are assigned according to the importance of the sample points: the weight of the support vector points is increased and the weight of noise is decreased. The latest unbalanced adjustment factors are used to reduce the influence of the unbalanced data on the classification results. Experimental results confirm that, compared with traditional fuzzy support vector machines, the proposed algorithm can address unbalanced data and noise more effectively in multi-classification problems.

We provide a framework for representing segments of rational planar curves or patches of rational tensor product surfaces with no singularities using semi-algebraic sets. Given a rational planar curve segment or a rational tensor product surface patch with no singularities, we find the implicit equation of the corresponding unbounded curve or surface and then construct an algebraic box defined by some additional equations and inequalities associated to the implicit equation. This algebraic box is proved to include only the given curve segment or surface patch without any extraneous parts of the unbounded curve or surface. We also explain why it is difficult to construct such an algebraic box if the curve segment or surface patch includes some singular points such as self-intersections. In this case, we show how to isolate a neighborhood of these special points from the corresponding curve segment or surface patch and to represent these special points with small curve segments or surface patches. This framework allows us to dispense with expensive approximation methods such as voxels for representing surface patches., National Natural Science Foundation of China, Agencia Estatal de Investigación

This paper presents a hybrid symbolic-numeric algorithm to compute ranking functions for establishing the termination of loop programs with polynomial guards and polynomial assignments. The authors first transform the problem into a parameterized polynomial optimization problem, and obtain a numerical ranking function using polynomial sum-of-squares relaxation via semidefinite programming (SDP). A rational vector recovery algorithm is deployed to recover a rational polynomial from the numerical ranking function, and some symbolic computation techniques are used to certify that this polynomial is an exact ranking function of the loop programs. At last, the authors demonstrate on some polynomial loop programs from the literature that our algorithm successfully yields nonlinear ranking functions with rational coefficients.

Approximating complex curves with simple parametric curves is widely used in CAGD, CG, and CNC. This paper presents an algorithm to compute a certified approximation to a given parametric space curve with cubic B-spline curves. By certified, we mean that the approximation can approximate the given curve to any given precision and preserve the geometric features of the given curve such as the topology, singular points, etc. The approximated curve is divided into segments called quasi-cubic Bezier curve segments which have properties similar to a cubic rational Bezier curve. And the approximate curve is naturally constructed as the associated cubic rational Bezier curve of the control tetrahedron of a quasi-cubic curve. A novel optimization method is proposed to select proper weights in the cubic rational Bezier curve to approximate the given curve. The error of the approximation is controlled by the size of its tetrahedron, which converges to zero by subdividing the curve segments. As an application, approximate implicit equations of the approximated curves can be computed. Experiments show that the method can approximate space curves of high degrees with high precision and very few cubic Bezier curve segments.

Collision and intersection detection of surfaces is an important problem in computer graphics and robotic engineering. A key idea of our paper is to use the bracket method to derive the necessary and sufficient conditions for the collision of two ruled surfaces. Then the numerical intersection curve can be characterized. The cases for two bounded ruled surfaces are also discussed.

In this paper, a class of lattice supports in the lattice space Z m is found to be inherently improper because any rational parametrization from C m to C n defined on such a support is improper. The improper index for such a lattice support is defined to be the gcd of the normalized volumes of all the simplex sub-supports. The structure of an improper support S is analyzed and shrinking transformations are constructed to transform S to a proper one. For a generic rational parametrization RP defined on an improper support S, we prove that its improper index is the improper index of S and give a proper reparametrization algorithm for RP. Finally, properties for rational parametrizations defined on an improper support and with numerical coefficients are also considered.

Among several implicitization methods, the method based on resultant computation is a simple and direct one, but it often brings extraneous factors which are difficult to remove. This paper studies a class of rational space curves and rational surfaces by implicitization with univariate resultant computations. This method is more efficient than the other algorithms in finding implicit equations for this class of rational curves and surfaces.

Parametric and implicit forms are two common representations of geometric objects. It is important to be able to pass back and forth between the two representations, two processes called parameterization and implicitization, respectively. In this paper, we study the parametrization and implicitization of quadrics (quadratic parametric surfaces with two base points) and cubic surfaces (cubic parametric surfaces with six base points) with the help of μ-bases – a newly developed tool which connects the parametric form and the implicit form of a surface. For both cases, we show that the minimal μ-bases are all linear in the parametric variables, and based on this observation, very efficient algorithms are devised to compute the minimal μ-bases either from the parametric equation or the implicit equation. The conversion between the parametric equation and the implicit equation can be easily accomplished from the minimal μ-bases.