Surface intersection using parallelism

Long Chyr Chang, Wolfgang W. Bein, Edward Angel

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


The support of Boolean set operations in free-form solid modeling systems requires the repeated intersection of parametric surfaces. Present approaches to this problem are sequential and must make trade-offs between accuracy, robustness and efficiency. In this paper, we investigate a parallel approach to the surface intersection problem that shows, both theoretically and empirically, that with parallelism we can achieve both speed and precision simultaneously. We first develop a theoretical foundation for a subdivision method and derive complexity bounds. We show that the basic algorithm can be improved by parallelism. We then design two tolerance-based parallel subdivision algorithms, a macro-subdivision algorithm designed for MIMD shared memory machines and a lookahead-subdivision algorithm for pipelined MIMD machines. Empirical results on the Sequent Balance 21000, the Alliant FX/8, and the Cray-2 verify that significant speed-up is achievable.

Original languageEnglish
Pages (from-to)39-69
Number of pages31
JournalComputer Aided Geometric Design
Issue number1
Publication statusPublished - 1994 Feb

All Science Journal Classification (ASJC) codes

  • Modelling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Surface intersection using parallelism'. Together they form a unique fingerprint.

Cite this