Robust interval algorithm for surface intersections

Chun Yi Hu*, Takashi Maekawa, Nicholas M. Patrikalakis, Xiuzi Ye

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


In this paper, we develop robust algorithms for computing interval polynomial curve-to-surface and surface-to-surface intersections. These include well-conditioned transversal intersections as well as ill-conditioned non-transversal intersections. Key components of our methods are the reduction of the intersection problems into solving balanced or unbalanced systems of non-linear interval polynomial equations. These systems are solved using an interval non-linear polynomial solver based on Bernstein subdivision coupled with rounded interval arithmetic, documented in a series of earlier papers. The solver provides results with numerical certainty and verifiability. Examples illustrate our techniques. We also provide a theoretical analysis of degenerate interval polynomial curve-to-surface and surface-to-surface ill-conditioned non-transversal intersections.

Original languageEnglish
Pages (from-to)617-627
Number of pages11
JournalCAD Computer Aided Design
Issue number9
Publication statusPublished - 1997 Sept
Externally publishedYes


  • CAD
  • CAGD
  • CAM
  • Robustness
  • Rounded interval arithmetic
  • Surface intersection

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Robust interval algorithm for surface intersections'. Together they form a unique fingerprint.

Cite this