代數(shù)B-樣條曲面實時繪制與非線性方程并行求根.pdf

1、代數(shù)曲面在表示具有復雜拓撲的光滑外形方面以及相關的幾何計算、外形分析方面具有優(yōu)勢，是主流參數(shù)表示形式——非均勻有理B-樣條的有益補充，張量積代數(shù)B-樣條曲面(簡稱ABS曲面)繼承了代數(shù)曲面的優(yōu)勢，且具有交互直觀、可局部編輯等特點，在幾何造型中具有潛在的應用價值，結合當前通用圖形處理器(GPU)的快速發(fā)展，本文以ABS曲面的實時光線投射繪制為切入點，深入分析了計算機輔助幾何設計與圖形學中的一元Bernstein多項式并行求根問題，提出了基

2、于Kantorovich定理的非線性幾何約束方程組的高效并行求解算法，并在此基礎上實現(xiàn)了基于GPU的ABS曲面實時繪制。
　　 論文首先回顧了曲面表示和造型方法的分類和發(fā)展歷史，并簡要分析了各自的特點，然后著重介紹了ABS曲面的定義和相關幾何性質，提出了幾種ABS曲面造型方法，包括一般代數(shù)曲面與ABS曲面的相互轉換、基于有向距離場的ABS曲面擬合、CSG造型等。這些造型方法為后續(xù)ABS曲面的實時繪制提供了素材。
　　 如

3、何設計高效、魯棒的一元多項式方程求解算法是代數(shù)曲面實時繪制的核心問題。本文對計算機輔助幾何設計與圖形學中的一元冪基和Bernstein多項式方程的各種求根算法，從理論基礎、數(shù)值魯棒性與計算效率等方面做了詳細的介紹、分析和實驗對比，并對于各種求根算法的選用給出了建議。在此基礎上，本文提出了一種迭代的、無條件收斂的Bézier點插入算法，理論分析和實驗結果顯示，該算法在時間和空間復雜度、可編程方面具有優(yōu)勢，而且適合于在當前通用GPU上并行實

4、現(xiàn)，
　　 為了實現(xiàn)更一般的Bernstein多項式約束方程組的高效、魯棒求解，本文提出了一種基于Kantorovich定理的并行求根算法.該算法可以隔離方程組的單根，并給出良好的初值，保證Newton-Raphson迭代算法的收斂性；并對某些重根也能高效、魯棒地求解.該算法解決了已有幾何求根算法中給定初值的收斂性問題，并且適合于在GPU上并行實現(xiàn)。實驗結果表明，在求解大規(guī)模約束方程組時，該算法比基于CPU的幾何造型引擎IRIT

5、中的相關算法快兩個數(shù)量級。
　　 曲面的高質量實時繪制是交互式幾何造型的基礎。已有代數(shù)曲面的實時繪制方法主要針對低次或單片曲面，ABS曲面的次數(shù)相對較高且包含數(shù)目較多的代數(shù)曲面片，因此，實時繪制ABS曲面是一個具有挑戰(zhàn)性的問題。結合當前通用GPU的快速發(fā)展以及基于非線性Bernstein多項式方程并行求根算法的研究，本文提出了兩種基于GPU的ABS曲面實時光線跟蹤算法。
　　 第一種是基于函數(shù)復合的實時光線投射方法.首先

6、使用3DDDA和深度剝離技術，高效地計算光線與曲面片定義域的交點。然后通過函數(shù)復合，將光線與ABS曲面的求交轉化為一元方程求根問題，并使用前面提出的Bézier點插入算法高效并行求解.同時實現(xiàn)了繪制曲面的高效反走樣.實驗結果表明，該算法可以實時繪制具有數(shù)以千計面片的6-9次ABS曲面，即使透明效果的繪制也可以達到交互式的幀率。
　　 在第二種算法中，為了在GPU上充分發(fā)揮Newton-Raphson算法可以高效求根的特性，本文將

7、代數(shù)曲面的多邊形化與光線跟蹤有機結合起來，實現(xiàn)了更高效的ABS曲面實時繪制.算法首先使用保拓撲多邊形化得到ABS曲面的三角網(wǎng)格逼近，然后用其光柵化結果作為計算光線與曲面求交的Newton-Raphson迭代算法的初值。在曲面的輪廓線附近，利用極曲面判斷光線與曲面交點數(shù)目并進行根隔離，并使用試位法進行求交計算.實驗結果表明，與已有基于函數(shù)復合的實時繪制算法相比，該算法可以取得3-6倍的加速效果。
　　 最后，總結了全文并指出了進一