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 language | English |
|---|---|
| Pages (from-to) | 39-69 |
| Number of pages | 31 |
| Journal | Computer Aided Geometric Design |
| Volume | 11 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1994 Jan 1 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Modelling and Simulation
- Automotive Engineering
- Aerospace Engineering
- Computer Graphics and Computer-Aided Design
Cite this
}
Surface intersection using parallelism. / Chang, Long chyr; Bein, Wolfgang W.; Angel, Edward.
In: Computer Aided Geometric Design, Vol. 11, No. 1, 01.01.1994, p. 39-69.Research output: Contribution to journal › Article
TY - JOUR
T1 - Surface intersection using parallelism
AU - Chang, Long chyr
AU - Bein, Wolfgang W.
AU - Angel, Edward
PY - 1994/1/1
Y1 - 1994/1/1
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
VL - 11
SP - 39
EP - 69
JO - Computer Aided Geometric Design
JF - Computer Aided Geometric Design
SN - 0167-8396
IS - 1
ER -