兩空間三角形的退化關系研究

于海燕， 余沛文， 張 帥， 何援軍

(1. 東華大學機械工程學院，上海 201620；2. 上海交通大學計算機系，上海 200240)

兩空間三角形的退化關系研究

于海燕1， 余沛文1， 張 帥1， 何援軍2

(1. 東華大學機械工程學院，上海 201620；2. 上海交通大學計算機系，上海 200240)

通過對兩空間三角形關系的分類，討論了幾何退化對幾何計算的穩健性的影響力。解決一個問題的第一步是描述這個問題，空間幾何退化的完整表述是穩健幾何計算算法的設計、改進以及測試的重要基礎和保障。首次對空間三角形對的退化進行了深入的研究、全面的梳理?；谕队敖稻S原理，抽取繁雜的空間兩三角形關系的規律，分離出完整的空間三角形對的退化樣本模型。基本策略是建立計算坐標系，通過投影降維，將空間三角形對的位置關系變成一個固定，只有一個變化的平面位置關系。以相離、接觸、相交、內含的線索改變另一三角形的位置和大小，分類出空間三角形對的位置關系，檢索出兩者的所有退化狀態。該方法可以推廣到其他三維幾何間的退化狀態分類和幾何計算算法的穩健性設計中。

幾何計算；穩健性；退化；三角形求交；投影降維

幾何計算處于幾何問題的基礎層，是曲面、復雜幾何體以及其他圖形問題處理的計算基礎，是科學與工程計算的基礎與支撐，在計算機圖形學、計算機輔助設計與制造、計算幾何以及醫學圖像處理、建筑設計、運動學與機器人等領域有著廣泛應用。計算幾何算法的穩健性，尤其是三維空間的幾何計算穩健性一直是研究的難點[1-2]。

幾何計算的穩健性問題源于理論算法對于輸入值的兩個簡單假設：Real-RAM可獲得性假設和輸入無退化假設。而在應用中，須要面對由計算機進制產生的浮點運算累計誤差和幾何本身退化等可能導致的錯誤。其中退化是幾何特有的問題，幾何計算的穩健性問題通常特指退化問題[1,3]。國際上已經建立了跨國研究機構，旨在突破這種幾何問題特有的計算穩健性瓶頸[4]。近幾十年來，在精確計算以及采用擾動法以及二維幾何計算方面取得了一些成績[3,5-6]，但對于三維幾何計算，由于其空間關系的多變繁雜，仍然沒有一個徹底解決的統一方法，令研究人員束手無策[2-3]。關于退化的分析詳見文獻[3]。解決一個問題的第一步是描述這個問題，然而，在幾何計算穩健性問題上，很多情況下，有哪些退化尚不能完全確定，這也是幾何計算相對于數計算(numerical computation)的難點所在。因此，空間幾何退化的完整表述是幾何計算算法穩健性研究的基礎和關鍵。

空間三角形求交測試是幾何計算的基本問題之一，在計算機圖形學、圖像、CAD等領域有廣泛的應用。從原始的蠻力(brute-force)方法到經典的M?ller和 Held算法，再到由 Roy、Shen、Guigue 和 Troppo提出的算法，三角形求交算法一直是研究的熱點[7-12]。經典算法大多幾何意義較為明顯，涵蓋各種幾何相對位置的處理算法。近年，隨著相關應用領域的不斷發展，很多新算法將主要工作集中在如何提高算法的速度。但從算法的描述上，這些新的算法公式繁多，幾何意義不明顯，很難從理論上檢測算法的穩健性。在算法的測試方面，偏重于算法速度的測試，在已發表的文章中很少有算法穩健性的測試與證明。通常的測試方法是用隨機產生的三角形樣本對算法進行測試，而各種幾何退化情況一般不會被檢測到，致使檢測出現遺漏。實際上，空間兩三角形的位置關系比較復雜，退化狀態較多[7]。在三角形相交測試中的一個錯誤可能會導致整個工程不可估量的損失。已經有學者公開指出這種追求速度而放棄穩健性的研究方法及其在工程應用中的問題，明確指出這種只注重速度而忽略穩健性的算法以及隨機檢測的測試方法是很危險的[13-14]。

本文對空間兩三角形的各種位置關系進行全面的梳理，提出了一種基于投影降維的直觀分類方法。應用正投影的兩面投影表述空間關系，使得空間的“形”得以用平面的投影圖窮舉出來；以圖表達形的方法，便于分類，而且表達直觀、便于交流。在保證樣本的完整性的基礎上，重點考慮退化情況。給出了完整退化樣本模型的設計方法和，最后以經典的M?ller算法為測試對象，給出了以此退化模型進行算法測試的步驟和注意事項。

1 投影降維

本文采用基于投影降維的可視化分類方法將三角形對的空間位置關系簡單直觀地描述出來。一個合適的坐標系能夠簡化幾何表述和代數運算，這樣的坐標系稱為計算坐標系。

計算坐標系通過如下方式建立：對于任意一對三角形A和B，三角形A所在平面定為坐標平面xy(即H面)，其法向作為z軸，并以三角形A的一條邊作為x軸。

圖1表示兩個三角形的計算坐標系和在此坐標系下兩個三角形對應的3個投影。其中，坐標平面xy對應投影平面H，zx對應V面，yz對應W面，AH表示三角形A在平面H的投影。

圖1 計算坐標系和三角形對的3個投影

在三維坐標系下，一個平面除了不平行、不垂直于任意3個坐標平面之一(稱為一般平面)以外還有6種位置狀態：①水平面(平行于水平面)；②正平面(平行于正平面)；③側平面(平行于側平面)；④垂直于水平面；⑤垂直于正平面；⑥垂直于側平面。

如果把三角形A固定在水平面上，在計算坐標系下，三角形A在V和W面的投影都是線段，在H面的投影是其本身；三角形B的投影可能是線段或者三角形。三角形A和B這7種空間位置關系、兩三角形所在平面的位置關系以及對應的各面投影歸納如表1所示。其中，L表示線段，△表示三角形，PA表示三角形A所在平面，PB表示三角形B所在平面。

表1 三角形A和B的投影關系

2 模型樣本設計

首先，根據兩三角形所在平面的關系進行分類，分為平行、共面和相交3類。若兩平面平行，則兩三角形必定分離。若兩平面共面，則在H面上的投影即反映兩三角形空間關系。若兩平面相交，則固定三角形A，通過改變三角形B的平面，得出兩三角形平面的各種空間位置關系，并由兩個投影對應其空間關系。這樣，投影可以分為線段與線段、線段與三角形這兩種類型。最后，通過改變三角形B的相對與三角形A的位置或大小得到投影面上典型的相對位置關系；對于兩個平面相交的，再通過兩個投影面的排列組合得到所有典型的空間位置關系。

2.1 兩三角形所在平面共面

為尋求最佳吸塵孔徑尺寸，探究吸塵孔孔徑大小對除塵效果的影響，特建立孔徑分別為1、20、25 mm的掘進機截割部模型，探究同轉速、同行進速度下孔徑大小對除塵效果的影響。具體方案見表2。

當兩三角形位于同一平面時，屬于表1的t-1，在H面的投影情況就是實際的空間位置關系。重點討論所有的幾何退化情況：點點碰撞、點線碰撞、線線碰撞以及一些容易判斷出錯的情況，如圖2所示。

圖2 平面內兩三角形典型位置關系

2.2 兩三角形所在平面相交

當兩三角形所在平面相交時，兩三角形平面的位置關系可為表1中的t-2到t-7，三角形A和B的投影關系在3個投影面有L-L，L-△和△-△ 3種，選擇兩個相對簡單的投影關系描述空間狀態。據此，將兩面投影關系進一步分為3類：①表1中的t-2、t-3、t-4、t-5，兩面投影關系為L-L/L-△；②表1中的t-6，兩面投影關系為L-△/△-△；③表1中的t-7，三角形B的平面為一般位置。

2.2.1 類型①的分類方法

以t-2為例，首先選取V/W兩投影面描述空間狀態。然后，在V面上移動三角形B得到3種位置關系，如圖3所示。在W面上移動三角形B，得到9種位置關系，如圖4所示。最后，通過兩個面的組合得到所有位置關系。例如，當在V面的位置關系如圖3(a)所示時，W面上所有的位置關系都可能出現，所以此種情況有9種；同理，圖3(b)也對應9種；圖3(c)中除了圖4(h)所示的位置關系不會出現外都會出現，所以有8種。綜上，t-2有26種位置關系。當選擇圖3(a)和圖4(b)進行組合，那么實際的空間位置關系為圖5(a)所示，顯然，兩三角形不相交。同理，圖5(b)由圖3(b)和圖4(e)組合而成，此處為線面碰撞的幾何退化情況。圖5(d)由圖3(b)和圖4(e)組合成，雖然圖3(b)和圖4(e)均相交，但是實際不相交。對于圖5(e)同樣如此。從圖5中可以看出，若兩三角形在兩投影面都不相交，則空間一定不相交；即使兩三角形在兩投影面均相交，空間也不一定相交。

對類型①的其他類型，如t-3、t-4和t-5，分類方法與t-2相同。例如，對 t-3，選取 V/W兩投影描述對應空間狀態。在W面上移動三角形B得到3種位置關系，如圖6所示。在V面上移動三角形B，得到類似于圖4的9種位置關系。此類的組合情況與 t-2完全一樣，也有 26種位置關系。

圖3 三角形B垂直于V面時V面的投影關系

圖4 三角形B垂直于V面時W面的投影關系

圖5 t-2中一些典型的位置關系

圖6 三角形B為正平面時W面的投影關系

在t-6中，由于所有面的投影關系均為L-△，所以t-6單獨歸為類型②。選取H/W兩投影面，其兩面的投影關系均與圖4一樣。將兩投影面關系進行組合，排除重復的，得到36種位置關系。

2.2.3 類型③的分類方法

在t-7中，由于三角形B處于一般位置，采用隨機三角形產生測試樣本。

根據以上的分類方法，t-1有7種位置關系，t-2，t-3，t-4和t-5均有26種，t-6有36種，則穩健性測試樣本一共有147種位置關系。其中有81對相交，66對不相交。

3 模型樣本的建立

通過以上分析，得到了147種三角形求交測試樣本，包括了表1中的前6種類型，涵蓋各種可能出現退化的情況。這種分類方法以及模型樣本可作為三角形求交算法設計的依據和參考，也可以作為測試樣本，供算法測試使用。文獻[15]將這種分類方法與算法設計相結合，提出了一種基于投影降維的三角形求交算法，詳細分析了各種退化情況，并最終給出了統一的算法。

4 模型樣本分析及應用

以下給出在算法測試上的應用方法。

幾何計算算法測試一般包括穩健性測試和速度測試。兩種測試目標不同，應分別設計不同的測試樣本。以上得到的t-1到t-6的147種位置關系包含了各種特殊位置狀態，可以作為穩健性測試樣本。對于表1中的t-7類型，即兩三角形處于一般位置狀態，可采用隨機測試方法得到若干數據，可作為速度測試的補充樣本。這樣，特殊位置關系的逐級分類表述設計，輔以大量隨機數據，整個測試樣本包括了兩三角形所在平面平行、相交及共面3種位置關系，及每種位置關系下兩投影的各種組合關系，對應得到各種空間位置關系。

測試流程上，可先作穩健性測試，測試通過后可對各種不同相交率進行速度測試。表2給出了采用上述方法對經典的 M?ller算法的測試結果，供其他算法測試對比參考。測試硬件條件為：Intel Core i3 CPU M 370；2.4 GHz；內存1.92 GB；Windows XP操作系統。穩健性測試使用147種測試樣本。速度測試，取11種相交率(0，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1.0)，分別對每種相交率取5個數據樣本集，每個樣本由5 000個三角形對組成，5個樣本重復測試1 000次，測試完成后取均值得到每種相交率的測試時間。

表2 不同相交率的平均測試時間

幾何計算算法的不穩健主要由 2種原因導致：①幾何問題本身引起的，源于幾何元素和關系的一般性假設，對于特殊狀態和關系的忽略或遺漏導致)；②源于計算機的有限計數制，對實際中的數值的截斷有累計誤差導致。累計誤差導致的錯誤也常常發生在退化情況。因此，在算法設計與測試中，還應相應地對計算精度進行處理。例如，實際測試中，曾檢測出有3對三角形關系判斷錯誤，如圖7所示。這3對三角形位置關系恰好都是處于相交與不相交的臨界狀態，運算過程中變量產生的誤差將逐漸累積，最終導致有效數字最后位數與沒有截斷誤差時不同，即判斷出錯。將坐標值都縮小100倍后(此時坐標值均小于10)，測試結果恢復正確。累計誤差一般采用精確計算方法解決，可以參考文獻[16]。

圖7 坐標值擴大后測試出錯的3對三角形

5 總結與討論

本文提出了一種直觀的空間三角形對的分類方法，重點考慮幾何退化導致的穩健性問題的測試。首先給出了計算坐標系的建立方法，然后給出了分類的依據和用兩投影描述空間關系的方法。并由此設計出了一套以圖形表達的、涵蓋各種可能影響幾何穩健性情況的直觀完整的退化模型。將復雜的空間關系轉換為平面上簡單直觀的線段與線段、線段與三角形的幾何關系，這種投影降維的幾何方法描述直觀，幾何意義明顯，便于交流。本文將空間的“形”，借助投影降維的方法與兩投影圖建立了相互對應的關系，進而由兩投影圖推演表述出各種可能的空間退化。這種對空間幾何關系的降維梳理及投影圖表述方法，可推廣到其他三維幾何計算算法的穩健性測試甚至幾何計算算法本身的設計上。為三維幾何計算穩健性算法研究提供了一種新的途徑。

[1] Schirra S. Precision and robustness in geometric computations [M]//Lecture Notes in Computing Science. Berlin：Springer Press, 1997: 255-287.

[2] Halperin D. Robust geometric computing in motion [J]. The International Journal of Robotics Research, 2002, 21(3): 219-232.

[3] Mehlhon K, Osbild R, Sagraloff M. A general approach to the analysis of controlled perturbation algorithms [J]. Computational Geometry: Theory and Application, 2011, 44(9): 507-528.

[4] The Computational Geometry A lgorithms Library. The cooperative association for internet (CGAL) [EB/OL]. [2015-05-04]. http://www.cgal.org.

[5] Sacks E, Milenkovic V, Kyung M K. Controlled linear perturbation [J]. Computer-Aided Design, 2011, 43(10): 1250-1257.

[6] Ozaki K, Ogita T, Oishi S. A robust algorithm for geometric predicate by error-free determ inant transformation [J]. Information and Computation, 2012, 216: 3-13.

[7] M?ller T. A fast triangle-triangle intersection test [J]. Journal of Graphics Tools, 1997, 2(2): 25-30.

[8] Held M. ERIT-A collection of efficient and reliable intersection tests [J]. Journal of Graphics Tools, 1998, 2(4): 25-44.

[9] Tropp O, Tal A, Shimshoni I. A fast triangle to triangle intersection test for collision detection [J]. Computer Animation and Virtual Worlds, 2006, 17(5): 527-535.

[10] Devillers O, Guigue P. Faster triangle-triangle intersection tests [R/OL]. [2015-03-05]. http://citeseerx.ist.psu.edu/ viewdoc/download?doi=10.1.1.6.1725&rep=rep1&type=pdf.

[11] Guigue P, Devillers O. Fast and robust triangle-triangle overlap test using orientation predicates [J]. Journal of Graphics Tools, 2003, 8(1): 25-32.

[12] Hao S, Heng P A, Tang Z H. A fast triangle-triangle overlap test using signed distances [J]. Journal of Graphics Tools, 2003, 8(1): 17-23.

[13] Robbins S, Whitesides S. On the reliability of triangle intersection in 3D [C]//Computational Science and Its Applications — ICCSA 2003. Berlin: Springer Press, 2003: 923-930.

[14] Ericson C. Triangle-triangle tests, plus the art of benchmarking [EB/OL]. [2015-03-01]. http://realtimecollisiondetection.net/blog/?p=29.

[15] 于海燕, 何援軍. 空間兩三角形的相交問題[J]. 圖學學報, 2013, 34(4): 54-62.

[16] Fortune S. Polyhedral modeling with exact arithmetic [C]//SMA’ 95 Proceedings of the third ACM symposium on solid modeling and applications. New York: ACM Press, 1995: 225-234.

Degeneracy Relations for Two Spatial Triangles

Yu Haiyan1, Yu Peiwen1, Zhang Shuai1, He Yuanjun2

(1. College of Mechanical Engineering, Donghua University, Shanghai 201620, China; 2. Department of Computer Science & Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

This paper discussed degeneracy and robustness issues in geometric computing by an example of two 3D triangle pairs intersecting ,especially the classification of their various relations. The first key to a problem is to describe this problem. Hence, the complete representation of degeneracies is an important foundation and support to design, improve as well as test a robust geometric computing algorithm. For the first time, this paper studies degeneracies for various triangle pairs in 3D space. Based on projecting reduction, their relationships are classified and a complete sample model is deduced to cover all kinds of degeneracies. The basic strategy is to establish a computed coordinate system. Then by projection, 3D relations are reduced to planar ones. Fixing one triangle, and changing the relative position and size of the other, various relations are classified in the clue of departed, contacted, intersected and overlapped. Consequently, all degeneracies can be got. The method proposed in this paper provides a new way to robustness 3D geometric computing algorithms not only for testing samples but also for algorithm reform ing.

geometric computing; robustness; degeneracy; triangles intersection; projection and reduction

TP 391.72

10.11996/JG.j.2095-302X.2016030349

A

2095-302X(2016)03-0349-06

2015-08-11；定稿日期：2015-11-13

于海燕(1974–)，女，黑龍江海林人，副教授，博士。主要研究方向為CAD/CG。E-mail：yuhy@dhu.edu.cn