Minisymposium on Numerical Methods for Intersection Problems
Tenth SIAM Conference on Geometric Design & Computing
San Antonio, Texas
November 4-8, 2007
Organizers
Gun Srijuntongsiri, Cornell University
Stephen A. Vavasis, University of Waterloo
Dealing With Degenerate Surface Intersections in Exact Solid Modeling
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
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
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 Vavasis^{2}
^{1}Department of Computer Science, Cornell University. ^{2}Department 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 Srijuntongsiri^{1} and Stephen Vavasis*^{2}
^{1}Department of Computer Science, Cornell University. ^{2}Department 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.