3

入力として、穴のある凹型メッシュを形成する三角形のセットがあります。各三角形は3つの頂点で構成されています：（vi、vj、vk）、...隣接情報は提供されません。アルゴリズムは、同じ法線を持つ三角形のセットをポリゴンに「結合」する必要があります。したがって、出力は（pi、pj、pk、...、ps）、..です。

たとえば（下の画像を参照）、三角形で構成されるメッシュがあるとします。

（v0、v1、v4）、（v1、v3、v4）、（v1、v2、v3）

（v2、v6、v4）、（v6、v5、v4）。

出力として、次のようになります。

（p0、p1、p4）

（p1、p2、p3、p4）

ここに画像の説明を入力してください

上記の問題を解決する効率的なアルゴリズムを探しています。任意の提案、ヒントまたは記事をいただければ幸いです。

4

2 に答える 2

2

頭のてっぺんから。

  • 各ポリゴンを三角形分割して、三角形のセットを取得します。
  • すべてのポリゴンのすべての三角形に、法線に基づいてグループ番号を割り当てます
  • すべての三角形について、T =（va、vb、vc）は隣接情報E =（ab、bc、ca）を作成しました。ここで、abは、エッジa、bでTに隣接する三角形へのリンク/インデックスです。
  • 2つの隣接する三角形が同じグループの一部ではないエッジを検索し、同じ関係を持つ次のエッジをたどり、最初のエッジに戻るまで繰り返して、新しい各ポリゴンの輪郭をトレースします。

また、TINハルのエッジでNULLエッジタイプと競合する必要があることに注意してください。ただし、これは簡単です。

ここで最も遅いのは、多くの優れたTIN作成アルゴリズムによってO（n log n）で実行できる隣接情報の開発です。

于 2012-06-07T10:30:16.503 に答える
1

アダプティブメッシュ粗大化アルゴリズムを見てください。これらは通常、数値流体力学（Ansys CFX、CD-Adapco Star CCM +など）/構造力学（Anasys et al。）の高度なソフトウェアで使用されます。与えられたメッシュの自動細分化と粗大化が有利な場合。

このテーマについて検討するためのいくつかの無料の論文は、あなたに強力な出発点を与えるでしょう：

  1. https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/coarsening.pdf

  2. http://tetra.mech.ubc.ca/ANSLab/publications/coarsen.pdf

  3. http://www.cs.cmu.edu/~glmiller/Publications/MiTaTe98.pdf（これはかなり数学的なものです）

アダプティブメッシュリファインメントアルゴリズムの分野で追加のGoogle検索を行うと、このテーマに関する同様の論文が明らかになります。

編集。アダプティブメッシュコーシングの基本的で確立された方法は、エッジを1つの頂点に縮小し、それによって2つの要素を削除するエッジ崩壊法です。Li X.、Shephard MS、BeallMW「メッシュ修正による3D異方性メッシュ適応」。応用力学および工学におけるコンピュータ手法、2004年。擬似コードで次のように定義される優れた粗大化アルゴリズムがあります。

for all edge in short edge list do
    for all vertex that bounds the current edge do
        if vertex is not yet tagger then
            append vertex to dynamic list
            tag vertex to be in dynamic list
        end if
    end for
end for
while vertices not tagged processed in dynamic list do
    get an unprocessed vertex Vi from the list
    get Ej , the shortest mesh edge in transformed space connected to Vi
    if the transformed length Ej is greater than Llow then
        remove Vi from the dynamic list
    else
        evaluate edge collapse operation of collapsing Ej with Vi removed
        if the edge collapse would create an edge longer than Lmax then
            evaluate relocated vertex Vi
        else if the edge collapse would lead to 
            at/inverted elements then
            evaluate the swaps(s)/collapse compound operation
        end if
        if any local mesh modication is determined then
            tag neighbouring vertices of Vi in the dynamic list as unprocessed
            apply the local mesh modication
            remove Vi from the dynamic list if it is collapse
        else
            tag Vi as processed
        end if
    end if
end while

これは私が過去に使用した印象的な修士論文から取られています。ここで見つけることができます

これがお役に立てば幸いです。

于 2012-06-07T08:52:18.213 に答える