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 相邻的三角形的链接/索引。
  • 通过搜索两个相邻三角形不属于同一组的任何边来跟踪每个新多边形的轮廓，跟随具有相同关系的下一条边，并重复直到回到第一条边。

请注意，您还必须在 TIN 船体边缘处理 NULL 边缘类型，但这很简单。

这里最慢的一点是开发邻接信息，许多好的 TIN 创建算法可以在 O(n log n) 内完成。

于 2012-06-07T10:30:16.503 回答
1

查看自适应网格粗化算法。这些通常用于计算流体动力学（Ansys CFX、CD-Adapco Star CCM+等）/结构动力学（Anasys 等人）的高级软件。给定网格的自动细化和粗化是有利的。

一些关于这个主题的免费论文将为您提供一个强有力的起点：

  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 搜索将显示有关该主题的类似论文。

编辑。自适应网格粗化的一种基本且成熟的方法是边缘折叠方法，该方法涉及将边缘减少到单个顶点，从而删除两个元素。Li X.、Shephard MS、Beall MW “通过网格修改进行 3-D 各向异性网格自适应”。Computer Methods in Applied Mechanics and Engineering, 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 回答