[發明專利]面向高效渲染的二維三角網格生成方法

有效

• 申請號: 201611073459.X
• 申請日: 2016-11-29
• 公開（公告）號: CN106652036B
• 公開（公告）日: 2020-10-20
• 發明（設計）人: 王逸群;嚴冬明;達瓦·克汗;張曉鵬
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06T17/20
• 分類號: G06T17/20
• 代理公司: 北京市恒有知識產權代理事務所(普通合伙) 11576
• 代理人: 郭文浩

本發明涉及一種面向高效渲染的二維三角網格生成方法，所述方法包括：根據給定渲染對象的邊界形狀，生成初始的二維三角網格；在二維三角網格中尋找所有的簇，其中，每個簇為包括一個鈍角三角形和與該鈍角三角形鄰近的兩個或更多三角形的整體，并且簇與簇之間不重合；在每個簇內插入Steiner點，以生成新的二維三角網格。本發明可以保證生成全銳角的二維三角網格，并且可以優化較小的角度，從而能夠保持良好的二維三角網格形狀結構以進行二維對象的高效渲染。

技術領域

本發明涉及計算機圖形處理技術領域，尤其涉及一種面向高效渲染的二維三角網格生成方法。

背景技術

在計算機圖形學領域中，三角網格是幾何離散表示中最廣泛的形式，大多數二維對象最終都要轉化為二維三角網格，從而能夠在計算機中進行高效的渲染?？梢哉f，生成二維三角網格是幾何處理應用中最重要的步驟之一。但是，好的渲染需要高質量的二維三角網格，如果能夠使用全銳角的二維三角網格，將會大大減輕計算難度。

研究者們提出了許多方法來避免二維三角網格中出現過小和過大的角。目前，高質量的二維三角網格生成方法可以分為構造法和迭代法。通常，構造法僅提供輸入的邊界，然后通過在內部或者邊界插入Steiner點來產生所需的三角網格；相反，迭代法開始于一個已有的二維三角網格，然后通過迭代地插入、刪除或移動Steiner點來提高該二維三角網格的質量(例如，使用最優Delaunay三角化的方法，即ODT方法，其通過一些平滑步驟可以產生較好形狀的三角剖分，并且可以適用于各向異性的情況。

另外，還有一些方法結合了構造法與迭代法，通過修改連接關系和頂點的位置來保證二維三角網格中的角的上限與下限。例如，使用平面直線圖作為約束，使角度范圍縮小到30°和100°之間(后文也稱作CVT方法)；保證角度在30°和120°之間的一致Delaunay 三角化方法(后文也稱作CDT方法)；再例如，基于Voronoi圖中的短邊會對網格質量產生較大影響，利用能量函數最小化三角形外心和內心的距離的方法(后文也稱作OVD方法)。然而，這些方法盡管能夠在一定程度上約束大角和小角，但是所生成的二維三角網格仍會包含鈍角。

為了生成高質量無鈍角的二維三角網格，目前，研究者們還提出了啟發式方法、調整最大泊松圓盤的空間密度的方法、分治的方法以及避免直角的方法、最小化代價函數方法(后文也稱作Vanderzee 方法)等。

然而，這些方法或者不能避免過小的角度，或者不能保證產生全銳角的三角網格。

發明內容

為解決上述現有技術中存在的問題，根據本發明的一個實施例，提供一種二維三角網格生成方法，包括：

步驟1)、根據給定的邊界形狀，生成初始的二維三角網格；其中，可使用CVT方法生成初始的二維三角網格；

步驟2)、在二維三角網格中尋找所有的簇；其中，每個簇為包括一個鈍角三角形和與該鈍角三角形鄰近的兩個或更多三角形的整體，并且簇與簇之間不重合；

步驟3)、在每個簇內插入Steiner點，以生成新的二維三角網格。

上述方法中，每個簇包括一個鈍角三角形和與該鈍角三角形鄰近的兩個三角形。

上述方法中，在步驟2)中，采用如下步驟得到包括n個三角形的簇，其中n大于等于3：

步驟a)、尋找一個鈍角三角形，作為簇的部分并且作為參照三角形；

步驟b)、尋找參照三角形的最長邊鄰接的三角形，

如果找到的三角形是無限的或者是屬于另一個簇的非鈍角三角形，則尋找參照三角形的非最長邊鄰接的三角形，如果找到的三角形不是無限的且不是屬于另一個簇的非鈍角三角形，則將該三角形作為簇的部分并且作為參照三角形，否則結束，