我已经实现了一个三角形镶嵌着色器,如 this 网站上的示例所示。
如何确定定义的
inter
和 outer
镶嵌因子输出的面总数? - 它不会以任何方式影响我的程序,我只是想知道我的多边形/面数。
可以使用简单的递归找到单个三角形的重心细分的三角形数量(内部和外部细分相等):
// Calculate number of triangles produced by barycentric subdivision (i.e. tessellation)
// Where n is the level of detail lod and outer and inner level is always equal
int calculateTriangles(int n) {
if(n < 0) return 1; // Stopping condition
if(n == 0) return 0;
return ((2*n -2) *3) + calculateTriangles(n-2); // Recurse
}
这是基于内层和外层的三角形、四边形和直线的顶点数或面数的完整答案!
我需要一个类似的答案,即给定细分以及内部和外部细节级别生成的顶点数量(其中所有 LOD 可以不同)。我解决了这个问题,并且不需要再进一步计算出面的数量。
因此,这是三角形镶嵌的两个答案。我的 LOD 语法是 IL 表示内部 LOD,OL0、OL1 和 OL2 表示三个边缘的外部 LOD。
Inner faces/triangles (based only on IL):
if IL==1 -> inner faces = 0
if IL odd -> inner faces = 3/2*(IL-1)(IL-3)+1
if IL even -> inner faces = 6*(IL/2-1)^2
Outer faces/triangles
if IL==1 -> outer faces = (OL0+OL1+OL2 == 3) ? 1 : OL0+OL1+OL2
else -> outer faces = 3*IL+OL0+Ol1+OL2-6
Total = Inner + Outer faces
我知道——这些方程看起来非常疯狂。真正有帮助的一件事是意识到any单调递增序列的总和,例如 (7+9+11+13+15+17) 可以计算为 (num_elements/2*(first_element+last_element)。这就是正方形最终来自。
如果有人关心顶点数量:
Inner vertices:
if IL==1 -> inner vertices = (OL0+OL1+OL2 == 3) ? 0 : 1
if IL odd -> inner vertices = (IL-1)^2 * 3/4
if IL even -> inner vertices = 3((IL/2)^2-IL/2) +1
Outer vertices = OL0+OL1+OL2
Total = Inner + Outer vertices (OL0+OL1+OL2)
这是四边形的顶点数和三角形面的答案。
Quad Vertices (LOD levels are IL0, IL1, OL0, OL1, OL2, OL3)
Inner vertices:
if IL0==IL1==1 but OL0+OL1+OL2+OL3>4 -> inner vertices = 1
else -> inner vertices = (IL0-1)*(IL1-1)
Outer vertices = OL0+OL1+OL2+OL3
Total = Inner + Outer vertices
Quad Faces (triangles)
Outer ring faces =
if IL0==IL1==OL0=OL1=OL2=OL3==1 -> 1 face total
if IL0==IL1==1 but OL0+OL1+OL2+OL3>4 -> calc as if IL0=IL1=2
else OL0+OL1+OL2+OL3+2*IL0+2*IL1-8
Inner faces:
if IL0<3 and IL1<3 -> 0
else 2*(IL0-2)*(IL1-2)
Total = Inner + Outer
i.e.: when IL0/IL1>2 -> OL0+OL1+OL2+OL3+2*IL0+2*IL1-8 + 2*(IL0-2)*(IL1-2)
相对而言,等值线非常简单:
Isoline (LOD levels are OL0, OL1 - OL0 is missing top edge)
num vertices = OL0*(OL1+1)
num segments = OL0*OL1
哇,这是一些很长的方程!
希望对您有帮助!
图论的小技巧:如果你的图是平面的(如网格),你可以使用平面图的欧拉公式来删除一个(或多个)自由度:
V-E+F=2
https://en.wikipedia.org/wiki/Planar_graph#Euler's_formula
然后可以从图中的顶点和边的数量轻松获得面的数量。
F = 2+E-V
我们以四边形细分为例。我们可以简单地计算内部曲面细分中的顶点、边和面的数量,即 V=NM E=N(M-1)+M*(N-1) 和 F=(N-1)*(M- 1),如果我们将四边形的外侧也算作另一个面,则满足公式。
唯一的问题在于计算内部和外部补丁之间的三角形,与内部补丁不同,它可以是不规则的。
对于外层,我们得到
Vo = OL1+OL2+OL3+OL4
个顶点和相同数量的(外)边。对于内层,我们从内面片的边界得到 Vi = 2*(IL1+IL2)-8 个顶点以及相同数量的边 Ei=Vi。这是预期的结果,因为具有任意数量节点的闭环将具有连接每对连续节点的匹配数量的边。
这使得我们在两者之间的条纹中留下边缘和三角形。
解决该问题的方法有多种,但直观的方法是认识到条纹中的每个三角形只有 1 条边位于内部或外部边界上。
考虑到这一点,我们只需计算两个边界中的边的总和,每个边界正好抵消一个三角形。网格中剩余的顶点和边与计数无关,除了注意到每条剩余边都位于跨层区域中,并且唯一匹配一个剩余顶点,因此欧拉公式成立。
将所有内容放回一起,并小心避免任何重复计算,我们获得以下条纹计数:
F0 = E0o + E0i = OL0 + IL0-1
F1 = E1o + E1i = OL1 + IL1-1
F2 = E2o + E2i = OL2 + IL0-1
F3 = E3o + E3i = OL3 + IL1-1
加起来就是:
Fo = OL0 + OL1 + OL2 + OL3 + 2*IL0 + 2*IL1 - 4
条带中的面孔,加上:
Fi = (IL0-1)*(IL1-1)
内部的四边形,或者如果我们使用三角形则加倍。
嗯,当我处理内部和外部镶嵌时,这帮助我理解了如何计算它们。非常合理且直接的解释。 :)