Surface intersection using parallelism

Long Chyr Chang, Wolfgang W. Bein, Edward Angel

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

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
Volume11
Issue number1
DOIs
Publication statusPublished - 1994 Feb

Fingerprint

Surface Intersection
Subdivision Algorithm
Parallelism
Parametric Surfaces
Solid Modeling
Look-ahead
Shared Memory
Subdivision
Parallel algorithms
Parallel Algorithms
Macros
Tolerance
Speedup
Intersection
Trade-offs
Verify
Robustness
Data storage equipment

All Science Journal Classification (ASJC) codes

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

Cite this

Chang, Long Chyr ; Bein, Wolfgang W. ; Angel, Edward. / Surface intersection using parallelism. In: Computer Aided Geometric Design. 1994 ; Vol. 11, No. 1. pp. 39-69.
@article{b3a594497cd749349a416174d8fd95d8,
title = "Surface intersection using parallelism",
abstract = "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.",
author = "Chang, {Long Chyr} and Bein, {Wolfgang W.} and Edward Angel",
year = "1994",
month = "2",
doi = "10.1016/0167-8396(94)90024-8",
language = "English",
volume = "11",
pages = "39--69",
journal = "Computer Aided Geometric Design",
issn = "0167-8396",
publisher = "Elsevier",
number = "1",

}

Surface intersection using parallelism. / Chang, Long Chyr; Bein, Wolfgang W.; Angel, Edward.

In: Computer Aided Geometric Design, Vol. 11, No. 1, 02.1994, p. 39-69.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Surface intersection using parallelism

AU - Chang, Long Chyr

AU - Bein, Wolfgang W.

AU - Angel, Edward

PY - 1994/2

Y1 - 1994/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028381466&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028381466&partnerID=8YFLogxK

U2 - 10.1016/0167-8396(94)90024-8

DO - 10.1016/0167-8396(94)90024-8

M3 - Article

AN - SCOPUS:0028381466

VL - 11

SP - 39

EP - 69

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

SN - 0167-8396

IS - 1

ER -