CARGO PROJECT
Advanced Topological Methods for Robust Surface
Intersection Algorithms and Trimmed Surface Representations
Award # DMS-0138411 (funded by NSF and DARPA)
Rida T. Farouki
Department of Mechanical and Aeronautical Engineering,
University of California, Davis
Joel Hass
Department of Mathematics,
University of California, Davis
Thomas W. Sederberg
Department of Computer Science,
Brigham Young University
Project Summary
Though motivated by practical engineering considerations, surface
intersection problems have deep roots in diverse areas of mathematics,
including algebra, geometry, topology, analysis, and numerical methods.
The proposed project will bring the diverse expertise and renewed
commitment of an inter-disciplinary team of mathematicians, computer
scientists, and engineers to bear on this critical problem. Since
successful solutions will require radically new approaches and paradigms,
rather than incremental advances, special emphasis will be placed on
re-visiting the problem from first principles, seeking new insights
through synergistic dialog among participants with diverse areas of
expertise, and use of exploratory software implementations as research
tools. A central theme of the proposed research is the ab initio
incorporation of topological information into the formulation and
verification of intersection algorithms. Although failure to guarantee
topological consistency is the main deficiency of existing algorithms,
this remains a poorly explored domain. Our initial line of enquiry will
focus on using the homotopy or "embedding" method to track topological
changes in implicitly-defined algebraic curves, as they evolve from
"simple" initial configurations into a prescribed intersection locus.
The accuracy, efficiency, and reliability of modern computer-aided
design (CAD) systems has been severely compromised by the persistent
lack of rigorous algorithms for topologically-consistent representations
of surface intersections and trimmed surfaces. The solution to this
fundamental problem can have tremendous economic impact, in terms of
eliminating the laborious "geometry preparation and repair" task that
currently precedes the use of CAD data in analysis, manufacturing, and
inspection applications, and in resolving data-exchange incompatibilities
among different CAD systems. The ensuing productivity benefits, manifested
in accelerated design cycles and greater reliance on "virtual prototyping"
for design verification, are crucial to the maintenance of technological
leadership.
A "water-tight" intersection of the Utah teapot and a bicubic surface,
obtained by the topologically-consistent surface perturbation method.
Method for coordinated topology resolution and domain decomposition
(a preparatory step for applying the surface perturbation scheme).
Publications
J. Hass, R. T. Farouki, C. Y. Han, X. Song, and T. W. Sederberg,
Guaranteed consistency of surface intersections and
trimmed surfaces
using a coupled topology resolution and domain decomposition scheme,
preprint (2004)
R. T. Farouki, C. Y. Han, J. Hass, and T. W. Sederberg,
Topologically consistent trimmed surface approximations
based on
triangular patches, Computer Aided Geometric
Design, 21, 459-478
(2004)
X. W. Song, T. W. Sederberg, J. Zheng, R. T. Farouki, and J. Hass,
Linear perturbation methods for topologically consistent
representations
of free--form surface intersections, Computer Aided Geometric Design
21, 303--319 (2004)
Presentation at the NSF/DARPA CARGO Meeting, Santa
Rosa, May 2003