Abstract
This study discusses three approximation solutions in surface modeling. In surface modeling, Boolean operations such as union, intersection and difference are used to combine simple objects into a more complex ones. One of the most important computational tasks of Boolean operations is to mathematically describe the surface intersection. For finding the surface intersection, existing algorithms are required to balance three conflicting goals, namely efficiency, accuracy, and obustness. It is known that the global subdivision method is more robust than tracing method. However, the local tracing method has better efficiency and accuracy than the subdivision method, provides it has a good initial point. In order to take the advantage of both methods, a hybrid approach involving both subdivision and tracing is proposed. The novelty of the proposed method is the tracing algorithm in 4-dimensional parametric space of the surfaces instead of 3D space. We show that the proposed approach is more suitable for computing the approximation of trimmed surfaces. In the second part of this study, a hybrid intersection algorithm on a distributed computing environment is proposed. Both "master/slave" and "peer to peer" schemes are studied. Several performance parameters for parallel computations are discussed and empirical results using the Parallel Virtual Machine system on workstations are given to demonstrate that proposed parallel implementation achieves a good speedup. A trimmed parametric surface is mainly composed of a surface together with trimming curves lying in D, the parametric space of the surface. In general, trimming curves are obtained by intersecting parametric surfaces. By investigating the interrelation between surface tessellation and trimming curve approximation, we point out some problems on trimming curve approximation in existing trimmed surface tessellation algorithms. Counter examples are presented to show that a valid approximation of trimming curves in D together with the refinement imposed by surface tessellation does not necessarily generate a valid linear approximation in 3D space. To assure the 3D derivation tolerance, we propose two novel step-length estimation methods such that a piecewise linear interpolant of the trimming curve based on proposed step lengths will result in a valid linear approximation in 3D space. The first method exploits the triangle inequality and takes the derivation tolerance in 3D space into account to compute the effective step length. Our second method is based on segmenting the trimming curve into subcurves and then approximates each subcurve according to the derivation tolerance in 3D space. Moreover, several empirical tests are given to demonstrate the correctness of our step length estimations.