Minisymposium on Numerical Methods for Intersection Problems

Tenth SIAM Conference on Geometric Design & Computing

San Antonio, Texas

November 4-8, 2007

 

Organizers

 

Dealing With Degenerate Surface Intersections in Exact Solid Modeling

John Keyser

Department of Computer Science, Texas A&M University

Effectively dealing with degenerate surface-surface intersections is one of the most challenging aspects of exact solid modeling calculations.  This talk discusses the computation of exact intersections of parametric surfaces.  The Rational Univariate Representation (RUR) of roots is discussed as a method particularly useful for detecting the degenerate situations that can arise as part of solid modeling operations.  We discuss a resultant-based method for computing the RUR, and compare this implementation with a more optimized method not suitable for degenerate conditions.  Finally, we discuss a possible approach for removing degeneracies through the use of numerical perturbation.

 

Towards robust methods for computing with semi-algebraic curves and surfaces

Bernard Mourrain

INRIA, France

Geometric processing leads to a large domain of investigation, connected to topological, differential, numeric, symbolic questions and with many applications. We are interested by shapes represented by semi-algebraic models, in particular by parameterized and implicit representations (eg. based on bspline functions) which allow compact and powerful shape representations.  Performing geometric operations on these models involves on one hand topological computation and on the other hand numerical approximation.

A key issue is to combine efficiently and in a robust way these two types of computations. Natural difficulties appear in the presence of singularities on these algebraic objects and the analysis of the geometry near these singular points is an obstacle to many numerical approaches.

In this talk, we will consider subdivision methods which deduced from information on the boundary of regions the topological structure. The robustness of the approach relies on tools to isolate real roots. Following this approach, we will describe a new method for computing the topology of planar implicit curves, which proceeds by subdivision and which only
requires the isolation of extremal points. Extension of this approach to curves and surfaces in 3D and intersection curves in 4D will be described.

Some experimentation based on the subdivision solvers of the library SYNAPS and the algebraic-geometric modeler AXEL will be shortly demonstrated.

 

Efficient Computation of the Union of Cubic A-Patches

C. Bajaj*, A. Paoluzzi and S. Portuesi

The University of Texas at Austin; University "Roma Tre", Roma, Italia

A-Patches are smooth algebraic surface patch families, defined using a fixed degree trivariate polynomial within a compact polyhedron domain (also called the patch scaffold). Simple A-patches use a tetrahedron, or a cube, or a triangular prism scaffold. An exact union or intersection boolean operator is often not closed inside the domain of fixed degree A-patches. The reason is simply that the intersection of two algebraic surfaces of degree d (say cubic) is in general, a space curve of degree d^2, (i.e. nine ). In this talk, we provide an efficient solution, using a clever combination of symbolic and geometric methods, for the subproblems below:

(i) The robust computation of the intersection of a pair of algebraic curves, and/or surfaces,

(ii) The decomposition of the explicit union of a pair of A-patches, into a small set of A-patches of the same scaffold type,

The combination of (i) and (ii) provides a union operator capable of reproducing A-patches maintaining the topology of the exact solution. These methods are currently being implemented in the context of the PLaSM Language and using the Ganith Algebraic Toolkit. The computation of the union of A-patches is a necessary step for the development of Boolean set operations on algebraic finite elements in an integrated software package.

 

Subdivision Multivariate Solver in the Barycentric Bernstein Basis

Martin Reuter

Department of Mechanical Engineering, Massachusetts Institute of Technology

This talk presents a method to solve multivariate polynomial systems over an $n$-dimensional simplicial domain using subdivision methods. The system of $N$ nonlinear polynomials in $n$ variables is represented in the barycentric Bernstein basis. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices employing either a splitting or shrinking operation. This method has the advantage to be independent of the coordinate directions.

Furthermore we find that when the  total order of polynomials is close to the maximum order of each variable, an iteration of this algorithm is asymptotically more efficient than the corresponding step in a similar
algorithm which relies on polynomial representation in the tensor product Bernstein basis. We present an algorithm implementing this method in rounded interval arithmetic, discuss various implementation issues and give an outlook on further studies.

 

A Condition Number Analysis of a Surface-Surface Intersection Algorithm

Gun Srijuntongsiri*1 and Stephen Vavasis2

1Department of Computer Science, Cornell University.  2Department of Combinatorics & Optimization, University of Waterloo

The problem of finding all intersections between two surfaces has many applications in computational geometry and computer-aided geometric design. We propose an algorithm based on Newton's method and subdivision for this problem. Our algorithm uses a test based on the Kantorovich theorem to prevent the divergence and/or slow convergence problems normally associated with using unsuitable starting points for Newton's method. The other main novelty of our algorithm is an analysis showing that its running time is bounded only in terms of the condition number of the problem instance. 

 

On the choice of polynomial basis in intersection algorithms

Gun Srijuntongsiri1 and Stephen Vavasis*2

1Department of Computer Science, Cornell University.  2Department of Combinatorics & Optimization, University of Waterloo

We consider a class of algorithms for finding roots of multivariate polynomials over cubes or other regular domains.  Such problems arise frequently in geometric modeling and computer graphics, in which case the number of unknowns is typically between 1 and 4.  The class of algorithms under consideration involves an ``exclusion test'' that is, a test able to determine that part of the domain has no zeros based on a simple computation.

A natural class of exclusion tests is based on computing a convex set containing the image of the subcube under the polynomial mapping.  For example, if the polynomial is in Bernstein-B\'{e}zier form, then the hull of the control points is such a set, and it is not hard to determine whether 0 lies in this hull.  Other polynomial bases yield other natural classes of
convex-set exclusion tests.  We propose a parameter that estimates the effectiveness of a convex-set test and compare the value of this parameter among commonly used polynomial bases.  We also present computational experiments on the choice of basis and convex-set test.