首页 软件应用 Mesh is Art(4)

Mesh is Art(4)

Mesh is Art(4)

前言

上文我们介绍了半边网格的底层架构,介绍了点、半边和面所携带的信息。本文我们来探讨一个半边网格的应用——网格细分(Subdivision)。网格细分是一种高效地表达几何的方法。



网格细分简述

在 Mesh is Art(1) 中我们讲解了网格数据大多数由三角形或四边形组成。网格细分技术为分割曲面提供了解决方案。这种技术的核心是关注如何通过细分算法(Subdivision)计算来用大量的较小的网格面来替代原来的曲面,从而细分并优化输入的基础网格面。并且由此产生的精密网格还可以使用相同的算法来产生更精密的网格,如此可以反复迭代。随着迭代步的增加,网格的数量也不断地翻倍,从而更加逼近于精确、光滑的初始曲面。

网格细分技术已经被广泛地应用于游戏和动画产业当中,在项目中常采用非常粗糙的基础网格来表达一个物体(大概只需要几百个多边形),因此存储时所占用的计算机资源非常少。我们知道动画和游戏中常常需要渲染模型,对于模型的渲染时,并不是所有模型都要达到几十万网格面级别再去渲染,这样不仅增加了模型场景中的负担,还浪费了许多时间。在一个场景中,通常只有距离摄像机近、需要突出表达细节的模型才会被渲染地非常清晰,其他背景、场景往往不需要那么高精度的表达。因此,网格细分技术变得十分重要,设计师只需要建立一些粗糙网格模型,当该模型需要被表达时,将其细分,不需要表达细节时,就保持不变。

Mesh is Art(4)

Figure 1:随着网格细分迭代次数增加,网格模型逐渐变得精细(从右至左)

图片来源:Pixie3D | Animation Software



Mesh is Art(4)

Figure 2:随着网格细分迭代次数增加,网格模型逐渐变得精细(从左至右)
图片来源:《Subdivision for Modeling and Animation》

在建筑设计中,许多建筑在设计阶段是由NURBS曲面这样的光滑连续曲面建模技术来设计的。然而,这些模型在几何学方面很容易操作(很容易在计算机中建模),但它们很难被精确地制造出来,由于加工尺度问题,在实际项目中不可避免地要将它们分割成小构件,从而制作出能安装在结构上的表面嵌板(如图3)。在建造中,即使最后完成时是一个单体结构,通常也需要采用离散单元来拼合的传统方法。因此,这些项目在建模时经常使用离散网格来表示曲面(如图4、5),来代替一张参数化连续的NURBS曲面(至少在工程和制造阶段上是这样)。在 Mesh is Art(2) 中,也简述了一个由细分算法主导的建筑设计实例。


Mesh is Art(4)

Figure 3:细分网格在建筑中的应用
图片来源:Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes


Mesh is Art(4)

Figure 4:用细分网格表达光滑曲面(一):从左至右依次为:初始光滑曲面、手动创建的初始网格、通过投影算法匹配到初始光滑曲面后的网格、细分之后的网格。
图片来源:Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes


Mesh is Art(4)

Figure 5:用细分网格表达光滑曲面(二):初始网格(左)和细分后的网格(右)



图片来源:Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes


网格细分除了在建造上表达曲面的优势外,还常被用于分析和优化。

在幕墙优化中,细分曲面常用来控制嵌板的尺寸以及辅助其他优化算法。比如当设计师设计了一张曲面,需要将该曲面铺上嵌板,设计师可以使用细分算法对该曲面不断地迭代细分,直至嵌板的尺寸符合可加工的尺寸,接着可进行更进一步地平板优化和规格优化,当然这两个问题先放到后面了。

在对于需要执行多目标优化的曲面来说,网格细分同样非常有用。在设计和施工的过程中,通常要对建筑曲面进行优化来提高其性能。结构优化通常要求在最大限度节省材料的前提下尽可能小地改变形状,优化的实现可以通过将结构构件仅放置在所需要的地方来尽可能减少结构构件的数量,或者通过调整结构构件以便有效地将载荷传递到支撑来减少结构构件的大小。改变建筑物的形状可以减小风和雪带来的荷载,当然也可以通过考虑热环境、通风和采光来优化建筑的场地、形状和遮阳,从而提高建筑的环境性能。

这些优化目标都需要对建筑模型采用一种特殊表式方法来分析其性能。这些分析需要大量离散的类似网格的表示方法,并且所需要的网格的密度会取决于正在执行的分析类型。例如有限元结构分析可能会要求网格的离散方式能够反映给出的支撑结构,计算风流分析可能需要更精密的分析网格,而太阳能生成计算会相对精确,可能只需要比较粗糙的网格来表示即可。连续壳体的有限元结构分析需要形状函数来在两节点间插入几何结构,而细分曲面也可用于此。

网格细分可以看作是一种圆滑的过程,细分得到的网格子顶点坐标是由周围相邻父顶点的平滑平均值产生。用这种方式,网格的坐标被圆滑,形成更接近初始的近似曲面。这一点已经被证明(Zorin et al.,2000),这种生成的近似曲面在非边界和非奇异顶点处都是C2连续的,这意味着形态表面(没有缝隙)、表面切线(没有折痕)以及切线的变化率(在视觉反射中没有变形)都没有突变(这三点分别是C0,C1和C2连续性的判断标准)。这也是细分网格看上去特别美观的原因。

圆滑过程的另一个优点是,细分不仅能可以圆滑顶点坐标,任何一组与顶点关联的数据都会被圆滑,如果一个初始的粗糙网格中每一个顶点附带着一个颜色的信息,所有连续细分的网格都能够自动匹配圆滑曲面上的颜色。可以类似地应用于更多实际的参数,例如顶点携带的贴图信息、应力值、立面渗透率或透明度值,百叶窗角度或者覆层的偏移距离。在基础网格上,这些数据可以被定义在所需要的顶点上,细分网格后,这些信息将完全以与顶点位置相同的C2连续的方式均匀地分布在整个曲面上。



细分算法原理

实现网格细分有多种方案,有基于三角形网格的,基于四边形网格,也有基于高阶多边形及混合网格的。细分算法的基本过程首先是从一张网格面开始,用某种方式在网格上添加点,并对拓扑结构进行优化。本文中着重讨论两个细分算法的原理及C#实现。

Loop细分算法

Mesh is Art(4)

原理

Loop细分算法(Loop,1992)是一种应用在三角形网格的算法,如图6所示,这是从一个球形网格中提取的一张网格面,每个三角形上的每条边都被新引入的子顶点分割成了两段,然后每一个三角形都被四个新的小三角形代替。
Mesh is Art(4)

Figure 6:Loop细分算法的实现步骤:(a)基础网格;(b)拓扑划分;(c)圆滑子顶点;(d)圆滑父顶点
图片来源:《Shell Structures for Architecture: Form Finding and Optimization》


这里有很多人可能看不懂图6中的(c)和(d)在做什么,我做进一步地解释:第一步是输入的初始球形网格中的一张网格面,第二步在初始网格中的各个边缘的中点处插入了子顶点,并互相连接。但是如果仅仅执行到这一步就结束了的话,无法起到逼近原始曲面的圆滑效果,因为三角形是平面图形,在三角形内部无论如何划分,得到的图形都依然是平面的,所以需要对各点进行挪动。第三步是将子顶点的位置挪动到一个新的位置,挪动的方向和距离取决于与它相邻的点及权重值,第四步是挪动父顶点,挪动的方向和距离同子顶点一样取决于相邻点。

由此可以看出,关键是点的权重,那么这个权重值是如何定义的呢?
处理的方法分为两部分,对于位于网格内部的顶点,如图7-a所示,公共边两端的顶点的权重值按照3/8来计算,面上其他的顶点的权重值按照1/8来计算,就这样将子顶点放在了一个加权平均的位置。这种近似方案还将父顶点移动到新的位置,如图7-b所示,在这个例子中父顶点旧的位置的权重值为5/8,周围顶点的平均位置的权重值为3/8 。
Mesh is Art(4)

Figure 7:内部顶点的权重值
图片来源:《Shell Structures for Architecture: Form Finding and Optimization》


由于公众号不支持markdown的数学公式,所以以下数学公式部分用图片来表达了。想看更清晰的版本请到我的CSDN博客:

https://blog.csdn.net/weixin_38976271/article/details/89736231

Mesh is Art(4)

Mesh is Art(4)


在细分算法里曲面的边缘通常需要被特殊处理,比如一条只通过一个面的边(面的边缘)。如图8-a所示,沿着边界创建的子顶点会被放置在边界上的边的中点。如图8-b所示,边界上的边的父顶点会被放置在以原始位置为3/4权重值和相邻两个顶点位置各占1/8权重值的位置,而不会考虑内部邻近顶点的位置。

Mesh is Art(4)

Figure 8:边界顶点的权重值


图片来源:《Shell Structures for Architecture: Form Finding and Optimization》

Mesh is Art(4)

Mesh is Art(4)


代码实现

Mesh is Art(3)中,我们讲解了半边网格的特性,即半边网格在处理邻域查找问题上尤为高效。因此在实现网格细分算法中,半边网格是最适合的网格数据结构,这也是为什么我一直在强调使用半边数据结构,类似细分一样大量使用网格邻域查找的算法还有很多。简略版的Loop细分的C#源码如下(不是很elegent):

 public Mesh Loop(Mesh m)
{
PlanktonMesh P = m.ToPlanktonMesh();
PlanktonMesh NP = new PlanktonMesh();
PlanktonMesh TP = P;

for (int v = 0; v < P.Vertices.Count; v++)
{
// Loop
int[] Neighbours = P.Vertices.GetVertexNeighbours(v);

int Valence = Neighbours.Length;
double Beta = 0.625 - (Math.Pow((3 + 2 * Math.Cos((2 * Math.PI) / Valence)), 2) * 0.015625);
double Mult = Beta / Valence;

Point3d NewPosition = P.Vertices[v].ToPoint3d() * (1 - Beta);

foreach (int Neighbour in Neighbours)
{
NewPosition += P.Vertices[Neighbour].ToPoint3d() * Mult;
}
NP.Vertices.Add(NewPosition);
}
for (int HE = 0; HE < P.Halfedges.Count; HE += 2)
{
int Pair = P.Halfedges.GetPairHalfedge(HE);
int ThisOpp = P.Halfedges[HE].PrevHalfedge;
int PairOpp = P.Halfedges[Pair].PrevHalfedge;

int HeSV = P.Halfedges[HE].StartVertex;
int PrSV = P.Halfedges[Pair].StartVertex;

// split the halfedges in the topology lookup mesh
TP.Halfedges.SplitEdge(HE);
// ensure that each face has a starting halfedge on an even vertex
if (P.Halfedges[Pair].AdjacentFace > -1)
TP.Faces[P.Halfedges[Pair].AdjacentFace].FirstHalfedge = TP.Halfedges.Count - 1;

// Loop
Point3d NewPosition = P.Vertices[HeSV].ToPoint3d() * 0.375 +
P.Vertices[PrSV].ToPoint3d() * 0.375 +
P.Vertices[P.Halfedges[ThisOpp].StartVertex].ToPoint3d() * 0.125 +
P.Vertices[P.Halfedges[PairOpp].StartVertex].ToPoint3d() * 0.125;
NP.Vertices.Add(NewPosition);
}
for (int f = 0; f < P.Faces.Count; f++)
{
// add new triangulated faces
int[] FaceVerts = TP.Faces.GetFaceVertices(f);
NP.Faces.AddFace(FaceVerts[0], FaceVerts[1], FaceVerts[5]);
NP.Faces.AddFace(FaceVerts[2], FaceVerts[3], FaceVerts[1]);
NP.Faces.AddFace(FaceVerts[4], FaceVerts[5], FaceVerts[3]);
NP.Faces.AddFace(FaceVerts[1], FaceVerts[3], FaceVerts[5]);
}
return NP.ToRhinoMesh();
}

Catmull-Clark细分算法

Mesh is Art(4)

原理

Catmull-Clark细分是一种基于四边形的网格细分算法,它所产生的网格能够达到C2连续,奇异点处为C1连续。和Loop类似,其实就是父的更新法则和子顶点的创建法则有不同。对于内部顶点,位于面中的子顶点创建法则为该面顶点的加权平均,位于边界的子顶点的创建法则是内部边两端点的3/8,过该边的两张网格面的其他顶点占1/16。父顶点的更新法则分两种,与父顶点相邻的顶点的权重为β/k(β=3/2k,k为顶点的价),与父顶点共面却不相邻的顶点的权重为γ/k(γ=1/4k),父顶点挪动前的权重为1-β-γ。边界顶点的处理和Loop算法完全相同,这里不再多做解释了。

Mesh is Art(4)

Figure 9:Catmull-Clark细分法则
图片来源:《Subdivision for Modeling and Animation》

Mesh is Art(4)

Mesh is Art(4)

Mesh is Art(4)

Mesh is Art(4)

Mesh is Art(4)

代码实现

简略版的Catmull-Clark细分的C#源码如下:

public Mesh CatmullClark(Mesh m)
{
PlanktonMesh P = m.ToPlanktonMesh();
PlanktonMesh NP = new PlanktonMesh();
PlanktonMesh TP = m.ToPlanktonMesh();

for (int v = 0; v < P.Vertices.Count; v++)
{
// Catmull-Clark
int[] InHEs = P.Vertices.GetIncomingHalfedges(v);

double Beta = 3.0 / (2 * InHEs.Length);
double Delta = 1.0 / (4 * InHEs.Length);
double BetaK = Beta / InHEs.Length;
double DeltaK = Delta / InHEs.Length;

Point3d NewPosition = P.Vertices[v].ToPoint3d() * (1 - Beta - Delta);

foreach (int InHE in InHEs)
{
NewPosition += P.Vertices[P.Halfedges[InHE].StartVertex].ToPoint3d() * BetaK;
NewPosition += P.Vertices[P.Halfedges[P.Halfedges[InHE].PrevHalfedge].StartVertex].ToPoint3d() * DeltaK;
}
NP.Vertices.Add(NewPosition);
}
for (int HE = 0; HE < P.Halfedges.Count; HE += 2)
{
int Pair = P.Halfedges.GetPairHalfedge(HE);
int ThisOpp = P.Halfedges[HE].PrevHalfedge;
int PairOpp = P.Halfedges[Pair].PrevHalfedge;

int HeSV = P.Halfedges[HE].StartVertex;
int PrSV = P.Halfedges[Pair].StartVertex;

// split the halfedges in the topology lookup mesh
TP.Halfedges.SplitEdge(HE);
// ensure that each face has a starting halfedge on an even vertex
if (P.Halfedges[Pair].AdjacentFace > -1) TP.Faces[P.Halfedges[Pair].AdjacentFace].FirstHalfedge = TP.Halfedges.Count - 1;

// Catmull-Clark
Point3d NewPosition = P.Vertices[HeSV].ToPoint3d() * 0.375 +
P.Vertices[PrSV].ToPoint3d() * 0.375 +
P.Vertices[P.Halfedges[P.Halfedges.GetPairHalfedge(P.Halfedges[HE].NextHalfedge)].StartVertex].ToPoint3d() * 0.0625 +
P.Vertices[P.Halfedges[P.Halfedges[HE].PrevHalfedge].StartVertex].ToPoint3d() * 0.0625 +
P.Vertices[P.Halfedges[P.Halfedges.GetPairHalfedge(P.Halfedges[Pair].NextHalfedge)].StartVertex].ToPoint3d() * 0.0625 +
P.Vertices[P.Halfedges[P.Halfedges[Pair].PrevHalfedge].StartVertex].ToPoint3d() * 0.0625;
NP.Vertices.Add(NewPosition);
}
for (int f = 0; f < P.Faces.Count; f++)
{
int CenterIdx = NP.Vertices.Count;
NP.Vertices.Add(P.Faces.GetFaceCenter(f).ToPoint3d());
int[] FaceVerts = TP.Faces.GetFaceVertices(f);
for (int nf = 0; nf < FaceVerts.Length; nf += 2)
{
int LastVert = nf - 1;
if (nf == 0) LastVert = FaceVerts.Length - 1;
NP.Faces.AddFace(FaceVerts[nf], FaceVerts[nf + 1], CenterIdx, FaceVerts[LastVert]);
}
}
return NP.ToRhinoMesh();
}

本文已获授权,转载自公众号“AlbertLiDesign”

Mesh is Art(4)

本文来自网络,不代表钢构人的立场,转载请注明出处。搜索工程类文章,就用钢构人网站。 https://www.ganggouren.com/2019/05/9fd407399f/
上一篇
下一篇

作者: ganggouren

为您推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

17717621528

在线咨询: QQ交谈

邮箱: 1356745727@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息
关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部