一種三維三角網構建填挖空間的圖割方法
2023-07-10 07:43:41 2
一種三維三角網構建填挖空間的圖割方法
【專利摘要】本發明涉及一種三維三角網構建填挖空間的圖割方法。本發明基於圖割法直接構建三維三角網，將構網問題視為優化標記問題。首先獲取原始地形散點和現實地形散點，將其合併後估計各點法向量；對合併後的散點採用逐點插入算法構建四面體對空間進行分解，我們想要得到的三角網即包含在四面體中；依據各散點法向量與四面體的相交信息和四面體中各三角面面積信息，添加s-t圖中權值；用最小割-最大流算法求解最終表面，即得到填挖空間，將空間內的各四面體體積相加即得到填挖的土石方數量。此方法無需投影到二維平面，避免了二維投影法構建三角網的不足；由四面體計算土石方量，精度更高。
【專利說明】—種三維三角網構建填挖空間的圖割方法
【技術領域】
[0001]本發明屬於三維建模領域，特別是涉及一種三維三角網構建填挖空間的圖割方法。
【背景技術】
[0002]在巖土工程中，廣泛涉及對填挖空間土石方的測量。土石方的測量、計算是工程施工中工程量預算、編制施工設計和合理安排施工現場的重要依據。現有的土石方計算方法有斷面法、方格網法和DTM法。
[0003]斷面法計算精度與斷面間距的長度有關，間距越小，精度就越高；斷面法計算土石方量時要注意橫斷面的選取，斷面的選取對精度有較大影響；但是這種方法計算量大，尤其是在範圍較大精度要求高的情況下更為明顯。
[0004]方格網法計算土石方量的精度取決於採集數據密度的大小，同時和方格網的大小有關，方格網越小，精度越高；一些地形起伏較小坡度變化平緩的場地適宜用方格網法。
[0005]DTM法能很好地適應複雜不規則地形，從而能更好地表達真實的地面特徵，採用投影法分別構建原始地形TIN和現實模型TIN ;用三稜柱法或柵格法填充開挖方邊界內的設計模型與現實模型之間的差異空間，之後計算土石方量。這種方法計算精度高，但也存在一些問題:用投影法構建TIN時，不同的投影面構建的TIN存在差異(甚至錯誤的TIN)，對精度有較大影響；投影法不能構建更為複雜的現實模型(投影面上存在重疊)；用三稜柱法計算體積時會對三角面進行分解，對精度有較大影響。
【發明內容】
[0006]本發明所要解決的技術問題在於提供一種三維三角網構建填挖空間的圖割方法。通過該方法，可以對複雜的巖土工程構建更準確的三維模型，以得到更高精度的土石方數量。
[0007]為了達到上述目的，本發明基於圖割法，將構網問題視為優化標記問題。首先獲取原始地形散點和現實地形散點，將其合併後估計各點法向量；對合併後的散點採用逐點插入算法構建四面體對空間進行分解，我們想要得到的三角網即包含在四面體中；依據各散點法向量與四面體的相交信息和四面體中各三角面面積信息，添加s_t圖中權值；用最小割-最大流算法求解最終表面，即得到填挖空間，將空間內的各四面體體積相加即得到填挖的土石方數量。
[0008]具體地，本發明方法包括如下步驟:
[0009](I)首先獲取待測填挖空間的現實地形散點，根據現實測量散點邊界裁剪並剖分原始地形三角網獲取原始地形散點；
[0010](2)將現實測量散點和原始地形散點合併後估計各個散點法向量；
[0011](3)對合併後的測量散點採用逐點插入算法構建四面體對填挖填挖空間進行分解；[0012](4)構建s-t圖,包括法向量能量項和三角形面積能量項,依據各散點法向量與四面體的相交信息和四面體中各三角面面積信息，添加s-t圖中權值；
[0013](5)用最小割-最大流算法求解最終表面，即得到填挖空間，將空間內的各四面體體積相加即得到填挖的土石方數量。
[0014]本發明構建能量函數的方法為:對填挖空間進行Delaunay四面體剖分，將Delaunay四面體的對偶圖(B卩Voronoi圖)作為s_t圖的節點和有向邊，s_t圖包括法向量能量項和三角形面積能量項。
[0015]填挖空間表面能量函數E (S) = λ normalEnormal (S) + λ areaEarea(S)；
[0016]S為填挖空間表面；
[0017]E_aJS)為法向量的能量項；
[0018]EmeJS)為三角形面積的能量項；
[0019]λ normal為法向量能量項權重；λ area為面積項能量項權重。
[0020]本發明提出利用法向量與四面體的相交信息添加s-t圖的權值。利用四面體頂點P和平移值σ確定四面體，添加其t權值；與法向量相交的三角面對應著S-t中的有向邊，添加邊權值；法向量穿過的最後一個四面體添加s權值。
[0021]本發明提出用最大流最小割算法重新標記s-t圖中的節點後，將未被s和t標記的節點標記為t，保留t節點對應的四面體即為填挖空間。本發明方法對封閉場景直接三維三角網構建，無需投影到二維平面，避免了二維投影法構建三角網的不足；直接構建出填挖空間，可以更直觀的展示出填挖的空間範圍；由四面體計算土石方量，避免了 DTM方法中三角形的分解，精度更高。
【專利附圖】
【附圖說明】
[0022]圖1為現實測量散點圖。I為測量邊界點，2為表面散點，3為地形特徵散點。
[0023]圖2為加密地形特徵散點示意圖。I為測量散點,2為加密的點,3為加密前地形特徵散點，4為加密後地形特徵散點。
[0024]圖3為依據測量邊界剪裁併加密原始散點示意圖。I為原始地形圖，2為測量邊界，3為原始地形散點。
[0025]圖4為合併現實散點和原始地形散點後，估計散點法向量示意圖。I為原始地形散點，2為現實測量散點，3為散點法向量。
[0026]圖5為基於s_t圖的二維二角網重建原理圖。I為被法向量穿過的二角面，2為Voronoi多面體，3為Delaunay四面體，4為重建的三維三角網表面，5為法向量終點，6為四面體頂點的法向量，7為四面體頂點，8為四面體頂點沿法向量反方向平移σ距離後的點。
[0027]圖6為填挖空間三維三角網重建流程圖。
[0028]圖7為構建的填挖空間示意圖。
【具體實施方式】
[0029]本發明是基於Delaunay四面體和圖割法的三維三角網構網方法，技術流程如圖6所示。利用原始地形散點和現實地形散點對空間進行Delaunay四面體分解，Delaunay四面體的對偶圖(即Voronoi圖)的頂點和有向邊對應著s_t圖中的頂點和有向邊，頂點表示Delaunay四面體，有向邊表示帶有方向的三角面。我們將填挖空間的計算問題視為能量函數最小化問題，能量函數包括法向量能量項和三角形面積能量項，依據法向量信息和三角形面積信息添加s-t圖的權值，求解過程就是找到s_t圖的最小割，全局最優化的標記四面體為s或t。
[0030]基於以上原理，參照附圖來詳細說明本發明的實施方式。
[0031]1.獲取散點數據
[0032]1.1對某區域的現實表面進行測量，獲取現實測量散點及測量邊界散點，若開挖後的邊坡存在地形特徵線，獲取地形特徵的測量散點，如圖1所示。獲取地形特徵測量散點的目的是更準確的表達三維模型，從而獲取更準確的填挖方數量。
[0033]1.2加密地形特徵測量點，使相鄰地形特徵測量點的平均距離為現實表面測量點平均距離的三分之一，目的是更準確的恢復地形的形狀，如圖2所示。
[0034]1.3剖分原始地形三角網，目的是更小的三角形能夠更加準確的接近測量邊界，將測量邊界和原始地形三角網投影到XY平面，將落入邊界內的三角網頂點取出，作為原始地形測量散點，如圖3所示。剖分算法是分割各三角形的邊，取三角形邊的中點作為分割點，並找到此邊所在的三角形tl和t2，分割點的坐標為三角形tl和t2 —共4個頂點的平均值，這樣一個三角形被分割為四個更小的三角形。
[0035]1.4將現實測量散點和原始地形測量散點合併後估計各散點法向量，如圖4所示。為此，對於點雲中的每個點P，獲取與其最相近的k個相鄰點，然後通過最小二乘為這些點計算一個局部平面P。此平面可以表述如下:
k 2
[0036]P(n [0037]其中n為平面P的法向量，d為P到坐標原點的距離。
[0038]2.構建 Delaunay 四面體
[0039]構建Delaunay四面體的目的是對空間進行分解，將原始地形測量散點和現實測量散點採取逐點插入算法構建Delaunay四面體。Delaunay四面體的對偶圖(即Voronoi圖)的頂點和有向邊對應著s-t圖的頂點和有向邊。s-t圖的頂點表示四面體，有向邊表示帶有方向的三角面。
[0040]3.添加s-t的權值
[0041]3.1依據法向量添加權值。基於表面重建的s-t圖原理展不在圖5中，黑色實心圓點P表示四面體頂點，黑色虛線L為黑色實心圓點P的法向量n，黑色空心圓點P』為四面體頂點沿法向量的反方向移動σ距離後的點。定位P』點所在的四面體Τ』，將其與s-t圖中的t端點相連並賦予其t權值，按此方法添加所有的t權值；從P點出發沿著法向量η找到被法向量穿過的三角面1\直到所穿越的四面體為無限四面體或者為t四面體，添加Ti對應的s-t圖的有向邊的權值；法向量η穿越的最後一個四面體T與s-t圖中的s相連，並賦予s權值，依次方法添加所有的邊權值和s權值。
[0042]3.2依據三角形面積添加權值。計算Delaunay四面體中各三角形的面積，將其作為權值加入到s-t圖中對應的有向邊中，同時計算Delaunay四面體各三角形面積的平均值，將其作為權值加入到所有的t權值中。
[0043]3.3合理分配λ _al和λ area的權重，至此s-t圖構建完成。[0044]4.求解填挖空間
[0045]利用最大流最小割算法重新標記s-t圖中各頂點與s和t相連的狀態，經重新標記後，未與S和t相連的頂點定義為t頂點，這樣S-t圖中各頂點被分為兩類:s頂點和t頂點。我們保留t頂點對應的Delaunay四面體，這些被保留的四面體即為填挖空間，如圖7所示。填挖土方量V就是各四面體體積之和，土方量的計算如下:
【權利要求】
1.一種三維三角網構建填挖空間的圖割方法，其特徵在於，包括如下步驟: (1)首先獲取待測填挖空間的現實地形散點，根據現實測量散點邊界裁剪並剖分原始地形三角網獲取原始地形散點； (2)將現實測量散點和原始地形散點合併後估計各個散點法向量； (3)對合併後的測量散點採用逐點插入算法構建四面體對填挖填挖空間進行分解； (4)構建s-t圖,包括法向量能量項和三角形面積能量項,依據各散點法向量與四面體的相交信息和四面體中各三角面面積信息，添加s-t圖中權值； (5)用最小割-最大流算法求解最終表面，即得到填挖空間，將空間內的各四面體體積相加即得到填挖的土石方數量。
2.如權利要求1所述的方法，其特徵在於，構建能量函數的方法為:對空間進行Delaunay四面體剖分，將Delaunay四面體的對偶圖作為s_t圖的節點和有向邊，s-t圖包括法向量能量項和三角形面積能量項；填挖空間表面能量函數E (S)=U0rmal(s)+ AareaEarea(S)，S為填挖空間表面；Enormal(S)為法向量的能量項；Earea(S)為三角形面積的能量項；λ normal為法向量能量項權重；λ area為面積項能量項權重。
3.如權利要求1和2所述的方法，其特徵在於，利用法向量與四面體的相交信息添加s-t圖的權值，利用四面體頂點P和平移值σ確定四面體，添加其t權值；與法向量相交的三角面對應著s-t中的有向邊，添加邊權值；法向量穿過的最後一個四面體添加s權值。
4.如權利要求1或2所述方法，其特徵在於，用最大流最小割算法重新標記s-t圖中的節點後，將未被s和t標記的節點標記為t，保留t節點對應的四面體即為填挖空間。
【文檔編號】G06T17/00GK103927783SQ201410154904
【公開日】2014年7月16日 申請日期:2014年4月17日 優先權日:2014年4月17日
【發明者】楊建思, 劉健辰, 郭丙軒, 李小龍 申請人:武漢大學