三維裁剪演算法

❶ 三維Cohen-Surtherland裁剪演算法中直線端點編碼需要多少位

三維Cohen-Surtherland裁剪演算法中直線端點編碼需要四位。直線的端點賦予一組4位二進制碼，稱為RC(區域編碼），裁剪窗口的四條邊所在的直線可以把平面分為9個區域，對各個區域的編碼也是四位。

三維Cohen-Surtherland緒論

利用DDA和Wu演算法測增量思路，以及Wu演算法的思想利用距離進行顏色分配思想，根據計算機浮點數的內部格式，用整數補碼表示平移後的斜率（增量）小數部分（32位定點小數），將畫點位置的計算與顏色分配比例的計算合為一體。

將這兩個參數的計算在繪制循環中減少到一個判斷，和0～1個自增或自減計算。顏色分配的精度達到2的32次冪。並用32位整數以向量運算方式計算顏色分量與背景合成的顏色值，加快了顏色計算的速度。

圓求解坐標的時候利用級數展開，避免開放和實數運算，快並且誤差小。

矩形裁剪演算法可快速繪制。

❷ 計算機圖形學中有幾種直線裁剪演算法

計算機圖形學(Computer Graphics，簡稱CG)是一種使用數學演算法將二維或三維圖形轉化為計算機顯示器的柵格形式的科學。

簡單地說，計算機圖形學的主要研究內容就是研究如何在計算機中表示圖形、以及利用計算機進行圖形的計算、處理和顯示的相關原理與演算法。圖形通常由點、線、面、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。從處理技術上來看，圖形主要分為兩類，一類是基於線條信息表示的，如工程圖、等高線地圖、曲面的線框圖等，另一類是明暗圖，也就是通常所說的真實感圖形。

計算機圖形學一個主要的目的就是要利用計算機產生令人賞心悅目的真實感圖形。為此，必須建立圖形所描述的場景的幾何表示，再用某種光照模型，計算在假想的光源、紋理、材質屬性下的光照明效果。所以計算機圖形學與另一門學科計算機輔助幾何設計有著密切的關系。事實上，圖形學也把可以表示幾何場景的曲線曲面造型技術和實體造型技術作為其主要的研究內容。同時，真實感圖形計算的結果是以數字圖像的方式提供的，計算機圖形學也就和圖像處理有著密切的關系。

圖形與圖像兩個概念間的區別越來越模糊，但還是有區別的：圖像純指計算機內以點陣圖形式存在的灰度信息，而圖形含有幾何屬性，或者說更強調場景的幾何表示，是由場景的幾何模型和景物的物理屬性共同組成的。

計算機圖形學的研究內容非常廣泛，如圖形硬體、圖形標准、圖形交互技術、光柵圖形生成演算法、曲線曲面造型、實體造型、真實感圖形計算與顯示演算法、非真實感繪制，以及科學計算可視化、計算機動畫、自然景物模擬、虛擬現實等。

❸ 三維數據分析有哪些好的方法與軟體

三維數據處理軟體都包含哪些模塊

三維數據處理軟體，一般包含三個模塊：數據管理和處理，三維渲染，UI。 這與圖形學的三個經典問題是相對應的：建模，渲染和交互。與一般常見的數據處理軟體，比如圖像視頻處理，不同的是，這里的數據展示模塊需要三維渲染。與之對應的UI操作，也變成了一些三維空間的變換，比如模型的旋轉縮放等。

如何搭建一個簡單的三維數據處理軟體

那麼如何快速的搭建一個三維數據處理軟體呢？採用搭積木的方式，每個模塊都有很多現成的開發包可以選擇。比如UI模塊處，一般常見的有MFC，QT，MyGUI（Magic3D使用的UI）等。數據處理演算法方面，常見的有Geometry++，CGAL，OpenMesh，PCL等。渲染模塊，可以使用OpenGL或者Direct3D，也可以使用渲染引擎，如OGRE，OSG等。

如何選擇幾何演算法開發包

幾何演算法模塊，一般有三種選擇：自主開發，使用開源庫，使用商業庫。如何選擇呢？開發包API的生命周期，大概分為開發，維護和升級。對於一個演算法，幾乎不可能開發出放之四海皆準的API。它的絕大部分時間都在維護和升級。開發包的選擇，其實就是一個成本問題。開發階段主要是時間成本，如何快速的實現目標功能是最關鍵的問題。維護和升級階段需要盡量低的成本開銷。所謂開源庫免費，其實只是在開發階段免費，而開發階段最看重的卻是時間成本。有了源代碼就需要人去維護，沒有人維護的源代碼是沒有用處的。商業庫的主要優勢就是有專業的團隊來維護和升級這些API，並且成本會比個人做得更低。如果想清楚API的生命周期以及每個階段的成本開銷後，根據自身具體情況，就能很容易的做出選擇了。

數字幾何處理是什麼

數字幾何處理，一般是指點雲網格數據的處理。和傳統的NURBS正向建模的模型相比，數字幾何處理的對象一般是三維掃描儀採集的數據，是曲面的離散表達，也就是數字化的。它的研究內容包括數據的獲取，存儲，表示，編輯，可視化等等。

OpenGL是什麼

OpenGL是一套跨平台的圖形繪制API，它通過一系列API把三維模型渲染到2D屏幕上。OpenGL採用了流水線機制，其繪制過程也稱為渲染流水線。此外還有OpenGLES，主要用於嵌入式系統，或者移動平台；WebGL主要用於Web瀏覽器里的圖形繪制。

OpenGL流水線

OpenGL通過一系列API可以設置渲染流水線的狀態，所以OpenGL也是一個狀態機。三維模型通過一些處理，最終渲染到2D屏幕上：

• 模型離散為三角面片：所有模型都需要離散為三角面片，OpenGL只接受三角面片輸入。注意，雖然OpenGL也可以接受四邊形，NURBS等輸入，其本質最後都是三角面片的繪制。

• Vertex Shader把三維三角片轉化到屏幕坐標系下的2D三角片：這個過程包含了變換，裁剪等操作

• 2D三角片的光柵化：2D三角片被離散化，用屏幕坐標系的像素來表示，這也叫光柵化。

• Pixel Shader為光柵化後的模型像素著色。

  上面是渲染流水線的大致描述，其中還有很多細節，不同的API也有些細節上的差別。最早的OpenGL是固定的流水線，也就是只能通過API來設置一些流水線中的狀態。現代的OpenGL開放出了一些Shader，用戶可以自己為Shader寫代碼，利用Shader可以寫出各式各樣的渲染效果。

  渲染模塊使用OpenGL還是渲染引擎

  如果渲染模塊不是主要業務，建議使用渲染引擎。因為引擎內有很多現成的工具可以使用，減少開發的時間成本。

❹ 斷面建模

（一）斷面的生成

在斷面建模之前，要先導入剖面圖和鑽孔以及斷層線等信息。根據導入的剖面圖、斷層線和鑽孔信息，來生成模型的斷層。生成斷層有兩種方式，即根據剖面上的斷層剖面線和根據離散點數據生成。

1.離散點斷面建模演算法

基於不同方法獲取的離散點數據，可進行插值生成斷面模型，下面是根據離散點來構建斷面演算法的思想。

（1）求解投影坐標系。斷面採用的投影坐標系並非斷面的最小二乘面投影坐標系，而是在求得最小二乘面後，將Z方向的偏差置為0，這是一個世界坐標與XOY平面垂直的平面。根據斷面的特點，斷面在一般情況下是豎直的，這樣的投影平面不會出現插值點重疊的問題。該設計是為在查找地層離散點在斷層上的投影點時提供一個更有意義的投影坐標系。

（2）求解矩形基礎網格，並根據基礎網格計算三角網格，根據三角網格包圍盒計算一個包圍邊界。用這個包圍邊界作為第一次裁剪曲面的邊界，得到初始顯示曲面。

（3）用戶根據需求對初始顯示曲面進行編輯或者指定初始顯示曲面的裁剪曲面就可以得到顯示曲面。重復本步驟，直至滿足要求，完成最終的斷面模型。

2.基於剖面上的斷層線生成斷面模型

將剖面導入三維建模軟體系統之後，對剖面上的斷層線進行分析，選定屬於相同斷層的剖面斷層線，然後進行剖分、插值生成斷層。如圖4-11所示。

圖4-11 根據剖面上的斷層線生成斷層

3.基於離散點數據生成斷面模型

通過導入的離散點也可以生成斷層，或者在鑽孔導入三維建模軟體系統之後，通過在孔軌跡上指定斷層上的鑽點，然後通過剖分、插值生成斷層。如圖4-12所示。

圖4-12 根據離散點生成斷層

（二）斷面的編輯

斷層生成之後，根據需要可以編輯斷層邊界和使用控制點編輯斷層，改變斷層面的形狀，還可以通過修改屬性框中的內容來編輯斷層的屬性等。如圖4-13所示。

圖4-13 根據離散點生成斷層

對地質體中的信息進行修改是重要的功能之一。課題組地質體模型的數據結構中，輸入可以是點集合和折線集合，但是折線集合也被示為有序點的集合。所以，對於點的編輯和修改是所有編輯和修改的基礎。由於一般圖形平台中很難解決計算機圖形學中的一個基本問題即「坐標變換」的深度問題，所以只能依賴於生成的三角網格面，實現沿著面和垂直面兩個方向的空間點的「位置坐標」編輯，即標量編輯。採用標量編輯，解決了「坐標變換」的深度問題，實現了不依賴於三角網格面的空間點編輯。

此外，還採用了「三維空間矢量點」的編輯功能。「三維空間矢量點」是指工區種的三維點不僅含有「位置坐標」的概念，還賦予每個點一個「方向矢量」。這樣，很容易對空間點進行方向上的編輯功能，我們稱謂「三維空間矢量點編輯」。本系統中多處採用了這種編輯功能，例如斷面上控制點的編輯（圖4-13（a））、地層上控制點的編輯、光源矢量的編輯等。光源矢量的編輯效果如圖4-14所示。

圖4-14 光源矢量編輯功能

（三）定義斷面關系

在建模時，對於工區中相交的兩個斷層，需要確認它們的相交關系，即哪一個是主切面，哪一個是被切面。通過定義它們的關系，實現主斷層面剪切輔斷層面的功能。在定義主斷層面時，一般選擇相對較高且長度大於被切斷層面在其上的投影面的斷層面，這樣選擇的要求可使系統較快地構建斷面網格。

斷層主輔關系定義之後，選擇「更新斷層」功能，生成切割後的斷層。圖4-15所示為定義斷層關系之後重新生成的斷層效果。

圖4-15 定義斷層關系

（四）三角網格邊界裁剪演算法

網格邊界裁剪演算法是構建連續曲面的基礎演算法。在復合結構表示的地質面構建演算法中，沒有採用根據邊界進行三角剖分和插值的方法來構建地質面，而是設計了一種通用性更廣、集網格裁剪、網格分割的快速網格邊界計算方法。本系統中多處要應用此演算法，如主輔斷面的裁減、主輔地層的裁減、地層三角網與斷面矩形網的裁減等等。

由三角剖分生成的三角網格均勻且易於保證求交精度，而直接切分的三角形勢必出現三角形畸形的問題。由於本演算法的計算基礎是曲面的矩形網格，所以畸形的三角形對演算法沒有影響。

表4-1是分別由三角剖分和矩形網格映射生成三角網格的效果對比。

表4-1 三角網格效果對比

由表4-1可以看出，三角剖分和矩形網格映射各有優缺點，在本軟體中，我們結合這兩種方法的優點，設計出了一種全新的三角網格構建方法，具體將在下文中詳細介紹。

1.裁剪器的設計

本系統中根據地質面邊界計算的需求設計了裁剪器的結構。裁剪的核心計算部分是統一的，其他的輸入和細節處理部分由虛函數分發到不同的子類處理，具有可維護性高，擴展性好的特點。

初始構建的三角網格由矩形網格映射而成，具有矩形的邊界。同時在構建過程中採用了保留拓撲關系的映射方式，使得三角網格中相鄰三角形之間有拓撲關系，並且在以後的計算中將保留並維護這種拓撲關系。

在構建地質面過程中，地質面邊界可能由於以下情況而發生改變：

（1）用戶直接對地質面邊界進行編輯。

（2）地質面將地質面的邊界改變；地質面被地質面切割包括兩種：一種是有矩形背景網格的三角網格被三角網格切割；一種是無矩形背景網格的三角網格被有矩形背景網格的三角網格切割。對於三角網格被三角網格切割的情況，考慮到演算法的效率以盡量避免為主，演算法不對其進行研究。

（3）在地質面被切割時，還包括局部切割和全局切割的情況。

分析上述地質面切割的特點，發現上述切割有一個共同的特點，即三角網格被切割成兩個部分後，網格的形態沒有改變，只是網格的邊界發生改變。根據上述需求三角網格裁剪的演算法輸入是：

（1）三角形網格：本演算法為了提高運算的效率採用如下的三角網格結構：每個三角形中保存的是頂點的指針和臨近三角形的指針。一套三角網格保存著一個頂點集合用來記錄所有的頂點。該結構不僅能清晰記錄三角形的形狀信息和地理位置信息，還能保存同該三角形的相鄰拓撲信息，便於查找和運算。本裁剪演算法就是以此為基礎進行設計和實現的。本演算法認為三角網格邊界相對於三角網格密度足夠光滑，在三角形內部沒有拐點。

（2）剪路徑：裁剪路徑是地質面新的邊界，裁剪路徑的限制條件是輸入的裁剪路徑不自交。

根據對輸入條件的分析，裁剪三角形的流程是統一的，都是將三角形網格一分為二，只是裁剪路徑的決定條件不同。裁剪路徑可以是由多邊形決定，也可以是由曲面決定，還可以是由其他幾何元素決定，本演算法根據C++派生類的關系設計了裁剪演算法的機制——裁剪器。

構建裁剪器後，只需傳入待裁剪的三角網格和裁剪路徑，裁剪器就可以完成對三角網格的裁剪工作。不同的路徑判斷演算法需要構建不同的裁剪器，每個具體裁剪器都從裁剪器基類派生而來，裁剪器基類負責三角網格的裁剪工作。這樣有利於演算法的維護和擴展。

2.裁剪器的基本裁剪演算法

裁剪演算法可以應用於所有三角網格被矩形網格或折線裁剪的情況，並且裁剪時對三角形拓撲關系的維護及重建過程是一致的，採用有拓撲的三角網格結構能起到很好的加速作用。

根據帶拓撲關系的三角網格的特點，裁剪演算法的流程如圖4-16所示。

圖4-16 三角網格裁剪流程

具體演算法流程為：

（1）確定所有三角形的頂點與裁剪路徑的關系，有以下兩種可能的關系：①頂點在裁剪路徑內；②頂點在裁剪路徑外（即將被裁剪掉的部分）。該功能由每個具體的裁剪器來完成。

（2）根據頂點關系將三角形分類：頂點全部在裁剪路徑外或全部在裁剪路徑上的三角形為不需要裁剪的三角形，其他的為待裁剪三角形。

（3）建立一個待裁剪三角形堆棧，選出一個待裁剪三角形作為初始三角形入棧，開始裁剪：

①在初始三角形中，肯定有兩個頂點同側，如圖4-17所示的三角形中頂點c和頂點b同側；

圖4-17 初始三角形

②求解三角形與裁剪路徑的交點值，分別記為A和B，具體求交過程由每個具體的裁剪器完成，如圖4-18所示：

圖4-18 三角形交點

③建立四個新三角形頂點A，B，A'和B'，其中A=A'，B=B'。建立三個新三角形，分別為△aBA，△B'bc和△A'B'c，如圖4-19所示：

圖4-19 新三角形結構

④為上述三個新三角形建立拓撲關系，保持三角網格中拓撲的完整性，同時，將ac和ab邊所對應的三角形入棧等待處理。記錄維護拓撲所需的相應信息後，將初始三角形出棧並將其在三角網格中刪除。將棧頂的三角形作為初始三角形重復步驟Ⅲ，直至棧空。

（4）查找待裁剪網格中沒有裁剪的三角形，如果有則重復上述步驟（3）。

（5）根據三角網格頂點與裁剪路徑的位置關系將三角形網格裁剪為兩個三角網格。

（6）裁剪後的三角形網格存在法矢缺失的問題，在顯示時，需要考慮到光照和反射才能有較好的三維效果。作為待顯示的三角網格，需要補齊法矢。

3.裁剪器其他的功能

在基本演算法的基礎上，為了完成不同對象之間的裁剪，裁剪器還定義了一些其他的功能，包括：計算三角網格同裁剪器的交點、根據空間位置將三角網格頂點劃分為裁剪路徑正側和負側。裁剪器主要有以下幾種：

（1）多邊形裁剪器

主要用於裁剪多餘的三角形，標定曲面的邊界和有效范圍。多邊形裁剪器在裁剪三角網格時，將三角網格分為多邊形內部和多邊形外部兩個部分進行裁剪。在三維地質建模過程中常常需要用多邊形來標識斷面邊界，因此需要使用多邊形裁剪器。該裁剪器的功能如下：

工作1：用多邊形將三角網格頂點分為多邊形內部和多邊形外部。

工作2：用三角形邊和多邊形網格求交點。

（2）矩形網格完全裁剪器

該裁剪器是用矩形網格將待裁剪的三角網格分為兩部分，當不能將三角網格完全劃分為兩個部分時，則矩形網格延長將三角網格完全劃分為兩個部分—矩形網格正側部分和矩形網格負側部分。利用矩形網格來判斷待劃分的三角網格頂點在矩形網格正側還是負側非常高效。可以採用該裁剪器計算斷面被其他地質面裁剪後的形態。該裁剪器的功能如下：

工作1：用矩形網格將三角網格頂點分為矩形網格正側頂點和矩形網格負側頂點。

工作2：用三角形邊和矩形網格求交點。

（3）矩形網格不完全裁剪器

該裁剪器是用矩形網格破壞待裁剪三角網格的拓撲關系，將矩形網格與待裁剪三角網格相交處三角形分為兩步分，而三角網格本身並沒有被完全割斷。該裁剪器用於求解斷層分割地層的裂口。該裁剪器的功能如下：

工作1：用矩形網格將三角網格頂點分為矩形網格正側頂點和矩形網格負側頂點。

工作2：用三角形邊和矩形網格求交點。

經過多次不同裁剪器裁剪後的三角網格形態如圖4-20所示：

圖4-20 多次不同裁剪器裁剪後的三角網格

❺ 柵格化的基本實現方法

最基礎的柵格化演算法將多邊形表示的三維場景渲染到二維表面。多邊形由三角形的集合表示，三角形由三維空間中的三個頂點表示。在最簡單的實現形式中，柵格化工具將頂點數據映射到觀察者顯示器上對應的二維坐標點，然後對變換出的二維三角形進行合適的填充。 一旦三角形頂點轉換到正確的二維位置之後，這些位置可能位於觀察窗口之外，也可能位於屏幕之內。裁剪就是對三角形進行處理以適合顯示區域的過程。
最常用的技術是Sutherland-Hodgeman裁剪演算法。在這種方法中，每次測試每個圖像平面的四條邊，對於每個邊測試每個待渲染的點。如果該點位於邊界之外，就剔除該點。對於與圖像平的面邊相交的三角形邊，即邊的一個頂點位於圖像內部一個位於外部，那麼就在交叉點插入一個點並且移除外部的點。 傳統的柵格化過程的最後一步就是填充圖像平面中的二維三角形，這個過程就是掃描變換。
第一個需要考慮的問題就是是否需要繪制給定的像素。一個需要渲染的像素必須位於三角形內部、必須未被裁掉，並且必須未被其它像素遮擋。有許多演算法可以用於在三角形內進行填充，其中最流行的方法是掃描線演算法。
由於很難確定柵格化引擎是否會從前到後繪制所有像素，因此必須要有一些方法來確保離觀察者較近的像素不會被較遠的像素所覆蓋。最為常用的一種方法是深度緩存，深度緩存是一個與圖像平面對應的保存每個像素深度的二維數組。每個像素進行繪制的時候都要更新深度緩存中的深度值，每個新像素在繪制之前都要檢查深度緩存中的深度值，距離觀察者較近的像素就會繪制，而距離較遠的都被舍棄。
為了確定像素顏色，需要進行紋理或者濃淡效果計算。紋理圖是用於定義三角形顯示外觀的點陣圖。每個三角形頂點除了位置坐標之外都與紋理以及二維紋理坐標 (u,v) 發生關聯。每次渲染三角形中的像素的時候，都必須在紋理中找到對應的紋素，這是根據在屏幕上像素與頂點的距離在與紋理坐標相關聯的三角形頂點之間插值完成的。在透視投影中，插值是在根據頂點深度分開的紋理坐標上進行的，這樣做就可以避免透視縮減（perspective foreshortening）問題。
在確定像素最終顏色之前，必須根據場景中的所有光源計算像素上的光照。在場景中通常有三種類型的光源。定向光是在場景中按照一個固定方向傳輸並且強度保持不變的光。在現實生活中，由於太陽距離遙遠所以在地球上的觀察者看來是平行光線並且其衰減微乎其微，所以太陽光可以看作是定向光。點光源是從空間中明確位置向所有方向發射光線的光源。在遠距離的物體上的入射光線會有衰減。最後一種是聚光燈，如同現實生活中的聚光燈一樣，它有一個明確的空間位置、方向以及光錐的角度。另外，經常在光照計算完成之後添加一個環境光值以補償光柵化無法正確計算的全局照明效果。
有許多可以用於光柵化的濃淡演算法。所有的濃淡處理演算法都必須考慮與光源的距離以及遮蔽物體法向量與光照入射角。最快的演算法讓三角形中的所有像素使用同樣的亮度，但是這種方法無法生成平滑效果的表面。另外也可以單獨計算頂點的亮度，然後繪制內部像素的時候對頂點亮度進行插值。速度最慢也最為真實的實現方法是單獨計算每點的亮度。常用的濃淡模型有 Gouraud shading 和 Phong shading。