Starting point computation

Starting Point Computations:

Roots of Polynomials

This section deals with two main objectives:

1. Identifying all the intersection curve segments,
2. Obtaining a starting point in each of the intersection curve segments.

In order to identify all connected components of an intersection curve, a set of characteristic points on the intersection curve can be defined. Such a set may include border, turning and singular points of the intersection and provides at least one point on any connected intersection segment and identifies all singularities. For RPP/RPP surface intersections, a more convenient set of such points sufficient to discover all connected components of the intersection, includes border and collinear normal points between the two surfaces. Collinear normal points provide points inside all intersection loops and all singular points. Border points are points of the intersection at which at least one of the parametric variables takes a value equal to the border of the parametric spaces.

To compute border points, a piecewise rational polynomial curve to piecewise rational polynomial surface intersection capability is required, e.g., P(0, t) = Q(u, v), which results in a nonlinear system of equations. Collinear normal points are points on the two parametric surfaces at which the normal vectors are collinear. Obtaining the starting point essentially reduces to solving a system of nonlinear polynomial equations, which can be robustly solved by the IPP algorithm.

Presentation on Nonlinear solvers and IPP

Multiple Roots and their Multiplicities

Identifying the starting point for a tangential intersections involving RPP surfaces would require you to solve a system of nonlinear polynomial equations which has multiple roots. Identification of multiple roots, and their accurate evaluation is of primary concern to the CAD/CAGD community. Specifically the problems are:

Difficulties in handling roots with high multiplicity
- Performance deterioration
- Lack of robustness in numerical computation
- Round- off errors during floating point arithmetic

We study of the topological degree and multiple roots of univariate and bivariate polynomial systems in the context of geometric modeling. The Interval Projected Polyhedron Algorithm is modified to take into account the multiplicities for a bivariate case. The new algorithm called the Bisection Method uses the Degree of Gauss Map and the Cauchy Index to solve a bivariate polynomial system was developed and studied in this context.

Presentation on Nonlinear Polynomial Systems: Multiple Roots and their Multiplicities