臺灣博碩士論文加值系統

本研究探討在曲面塑形系統中，三種近似解法的相關衍生問題。我們常
會藉由所謂的布林運算法則，將簡單的元件組合成複雜形體，而這其中
最重要的問題之一，就是如何具體地描述曲面交集的行為。這類演算法
在效率、精度與數值穩定度上，一直受到嚴格的要求。一般而言，曲面
細切解法(subdivision)的穩定度較高，交線追縱解法(tracing)則在計
算效率與精度上占有一定優勢，於是，如何適當結合此兩種方法的混合(hybrid)演算法是值得研究的課題。在本研究的第一部份，我們將提出
一個在參數曲面之參數空間內的交線追縱演算法。藉由實驗的發現，交
線追縱法的效率的確優於曲面細切法，於是適當修正兩者的合作關係，
將會獲得較優的成果。我們所提出的交線追縱演算法，也非常適用在修
剪曲面的近似解法上。
本研究的第二部份，是將第一部份所提出的混合演算法實際驗證在分散
式平行計算的環境中，包含了『主從架構』(master/slave)與『點對點
』(peer to peer)的計算模型都在考量評估之列。細切法的目的在將問
題分割簡化成數個子問題，並藉此來發現可能的交線起點，追縱法便可
以藉此順利地完成部份曲面交線的計算工作。過程中可能影響平行計算
效率的參數，都將在這個部份做探討，並將提出合宜的工作量 (work load)估算法。我們利用PVM(Parallel Virtual Machine)計算環境，在
兩種不同的機器平台與網路頻寬當中，展現平行計算的成效。
修剪曲面 (trimmed surface)也已是塑形系統應該提供的主要功能之一
。曲面交線自然是修剪動作的必要條件，然而，由於傳統的修剪參數曲
線(trimming curve)是定義在曲面的二維參數空間上的，已知相關近似
解(tessellation)的演算法其實並不完備，實際的反例也不難發現。為
了解決這個問題，在本研究的第三部份，我們提出了兩個修剪曲線『參
數步幅』的合理估算法，藉由這樣的評估，修剪曲線在空間中的直線近
似程度(chordal derivation)才能夠保證不會超出既定的容忍值。我們
開發了一套交談式修剪曲面設計系統，來展現原有解法的缺點，及兩個
新解法的成效。

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.

1.Introduction
2.Surface/Surface Intersection Algorithm
2.1 Related works
2.2 Recursive subdivision algorithm
2.3 Tracing algorithm
2.3.1 tracing direction
2.3.2 step size
2.3.3 point refinement
2.4 Empirical results
2.5 Discussions
3. Distributed Algorithm for Surface/Surface Intersection
3.1 Related works
3.2 The master/slave computation model
3.3 The distributed computation model
3.4 Empirical results
3.5 Discussions
4. The Tessellation of Trimmed Surface
4.1 Related works
4.2 Image based approximation
4.3 Step length determination problems
4.3.1 step length determination for surface
4.3.2 step length problems for trimming curve
4.4 Step length estimation based on triangle inequality
4.4.1 triangle inequality estimation
4.4.2 refinement of trimming curve
4.5 Step length estimation by segmenting curve first
4.6 Vertex set generation
4.6.1 generation of grid points
4.6.2 cell classification
4.7 Empirical results
4.8 Discussions
5. Conclusions and Future work

1. S.S.Abi-Ezzi, and L.A.Shirman. "Tessellation of curved
surfaces under highly varying transformations".
EUROGRAPHICS''91, 1991.
2. R.E.Barnhill, G.Farin, M.Jordan, and B.R.Piper.
"Surface/surface intersection". Computer Aided Geometric Design
, Vol.4, pages 3--16, 1987.
3. R.E.Barnhill, and S.N.Kersey. "A marching method for
parametric surface/surface intersection". Computer Aided
Geometric Design, Vol.7, pages 257--280, 1990.
4. A.Beguelin et al. "A users'' guide to PVM parallel virtual
machine". Tech. Report TM-1126, Oak Ridge Nat''l Laboratory, Oak
Ridge, Tenn., 1991.
5. H.Burger and R.Schaback. "A parallel multistage method for
surface/surface intersection". Computer Aided Geometric Design,
Vol.10, pages 277--291, 1993.
6. L.C.Chang, W.W.Bein, and E.Angel. "Surface intersection
using parallelism". Computer Aided Geometric Design, Vol.11,
pages 39--69, 1994.
7. G.Farin. "Curves and Surfaces for Computer Aided Geometric
Design: a practical guide". Press, Inc., 3nd ed. edition, 1992.
8. D.Filip, R.Magedson, and R.Markot. "Surface algorithms using
bounds on derivatives". Computer Aided Geometric Design, Vol.3,
pages 295--311, 1986.
9. C.M.Hoffmann. "Geometric and Solid Modeling - An
Introduction". Morgan Kaufmann Publishers, 1989.
10. S.N.Yang, and Y.J.Yang. "Step length problem for trimming
curve approximation in tessellating trimmed surfaces".
Journal of Computational and Applied Mathematics, March 2002.