應用於參數曲面之光線追蹤法的效能提升策略之研究

Abstract

光線追蹤法 (ray tracing) 是電腦繪圖中最常被使用的描繪技術 (rendering technique)，它的最主要功能就是能夠產生如照片般真實的影像。然而，產生一張影像所需花費的冗長時間則是它的最大問題，當物件是由參數曲面(parametric surfaces) ─ 如貝氏曲面 (Bezier surfaces)、B-spline 曲面 ─ 所建構時，這個問題更加的嚴重。在本篇論文中，我們提出一個提升效率的描繪架構 (rendering framework) 給應用於參數曲面的光線追蹤法。 這個描繪架構的主要目的是提升以下程序的執行效率：求解光線與曲面的交點以及尋求最近點 (the closest intersection point)。在求解光線與曲面的交點方面，我們利用光跡的連貫性 (ray coherence) 來加速交點的求解。在尋求最近點方面，我們提出遮蔽物探測技術 (obstruction detection technique) 來驗證一個已經求得的交點是否是最近點。這個描繪架構的主要程序如下： 對一個受測試曲面來說，我們首先找出掃瞄線 (scan line) 上，第一條與受測試曲面有相交的射線，求出並同時記錄下這條射線與曲面的最近點。接下來，我們利用 ray coherence 的性質來求解掃瞄線上的其他射線與受測試曲面的交點。當一個交點是透過 ray coherence 求得時，我們則利用遮蔽物探測技術來驗證這個點是不是最近點。如果這個點不是最近點，我們則找出真正的最近點。此外，我們延伸遮蔽物探測技術的基礎，提出一個一般性的法則來增進第二層光線 (secondary rays) 追蹤的執行效率。以這個描繪架構與遮蔽物探測技術為基礎，我們提出三套不同的方法來增進應用於參數曲面之光線追蹤法的執行效率。 第一個方法是結合目前最常用的兩個方法 ─ 數值方法 (numerical methods) 與分割方法 (subdivision methods)，成為一個既有效率而且很穩定的曲面光線追蹤法。在這個方法中，我們先利用貝氏分割法 (Bezier Clipping) 找出每一條掃瞄線上，第一條跟受測試曲面有相交的射線，求出並同時記錄下這條射線與曲面的最近點。接下來，我們則採用牛頓法 (Newton’s method) 搭配 ray coherence 來求解掃瞄線上的其他射線與受測試曲面的交點。也就是說，我們是利用前一條射線與受測試曲面的交點，作為求解下一條射線與受測試曲面交點的起始點 (initial point)，將這個起始點代入牛頓法中。 對於每一個經由牛頓法所求得的交點，我們則利用遮蔽物探測技術來驗證這個點是否是最近點。如果這個點不是最近點，我們則使用貝氏分割法找出最近點。因為牛頓法本身的執行情況並不是很穩定，不收斂的情形隨時有可能會發生。為了克服這個問題，當牛頓法不收斂時，我們改採用貝氏分割法來求解射線與受測試曲面的交點。實驗的結果顯示，在求解第一層射線(primary rays) 的交點方面，我們所提出的方法比貝氏分割法減少約 50% 的計算時間。至於在提升第二層光線追蹤的執行效率方面，我們所提出的法則可以減少約 20% 到 50% 的計算時間。 第二與第三套方法則是分別針對數值方法 (numerical methods) 與分割方法 (subdivision methods) 提出改進它們執行效率的策略。這個策略的基礎是根據我們所提出的描繪架構與遮蔽物探測技術。由於數值方法與分割方法有它們自己的方式來求解交點，因此很難提出一個共通的機制來提升它們的執行效率。因此，我們針對數值方法與分割方法各提出一套增進它們執行效率的方法。我們從數值方法與分割方法中各挑選一個方法做為我們實際測試的對象。實驗的結果顯示，我們所提出的方法可以讓數值方法與分割方法減少 16% 到 40% 的計算時間。

Ray tracing is one of the most important rendering techniques in computer graphics because of its ability in producing photo realistic images. However, ray tracing is a time-consuming process especially for parametric surfaces, such as B-spline and B?ezier surfaces. In this thesis, we propose an enhanced rendering framework for ray tracing parametric surfaces. The key point of our proposed rendering framework is to improve the performance of the following tasks: calculating the ray-surface intersection points and locating of the closest intersection points. To locate the closest intersection points efficiently, we introduce an obstruction detection technique to verify whether an intersection point is the closest one. Besides, a similar approach is also proposed to improve the performance in tracing secondary rays. Based on this rendering framework, we will discuss several methods for improving the performance of ray tracing parametric surfaces. The first algorithm is based on the combination of two most commonly used approaches: numerical methods and subdivision methods. The property of Newton's method with ray coherence is used to find the ray-surface intersection points. To overcome the problem while using Newton's method with ray coherence, we use the obstruction detection technique to verify whether an intersection point found by Newton's method is the closest one. When Newton's method fails to converge, we use Bezier clipping as the substitution to find the intersection points. Experimental results indicate that our algorithm do improve the performance of Bezier clipping by 50% on tracing primary rays. Furthermore, the improved approach on tracing secondary rays introduces a 20% to 50% reduction in total rendering time. The second issue considered is to improve both numerical methods and subdivision methods with the enhanced rendering framework. Since both numerical and subdivision methods have their own rendering process, it is difficult to create a general improvement scheme. Individual schemes are proposed for numerical and subdivision methods to enhance their performance. Two algorithms, a subdivision method and a numerical method, are modified and implemented. Experimental results indicate that the improved algorithms can reduce total rendering time by 16% to 40%.