空间曲面算法

‘壹’ 曲面生成和交叉处理

一、曲面生成

空间曲面存储在一个曲面文件中，该文件的结构如表4-10所示。一个空间曲面由多个曲面片组合而成，所以生成空间曲面之前首先要生成空间曲面片。空间曲面片由两闭合曲线或两条非闭合曲线连接而成。生成实体表面的方法有很多，如遗传算法、模拟退火法和插值算法等。其中遗传算法和模拟退火法基于图论的原理来完成曲面生成任务。本系统中采用了遗传算法来生成曲面片，曲面和曲面片用非规则三角网TIN(triangle irregurlar network）来表示。

表4-10 曲面文件

续表

1.遗传算法的基本原理

遗传算法（genetic algorithm）简称GA，它是建立在自然选择和群体遗传学机理基础上的随机迭代和进化，是具有广泛适用性的搜索方法。在遗传算法中，所有的自然种类适应环境而得以生存，这一自然适应性是GA的主旋律。GA搜索结合了达尔文适者生存和随机信息交换，前者消除了各种不适应因素，后者利用了原有解中已有的认识，从而加快了搜索过程。下面说明基本方法。

对于一个给定的优化问题，设定目标函数：

F=f(x,y,z）,（x,y,z）∈Ω，F∈R

求空间点（x₀,y₀,z₀）使得（不失一般性，假设求最大值）

F=f(x₀,y₀,z₀)=maxf(x,y,z）

其中（x,y,z）为自变量，Ω是（x,y,z）的定义域，x,y,z可以是数值，也可以是符号，F为实数，是解的优劣程度或适应度的一种度量，f为解空间点（x,y,z）∈Ω到实数域F ∈ R的一种映射，那么GA的求解步骤如下：

（1）编码

用一定比特数的0,1二进制编码对自变量x,y,z进行编码形成基因码链，每一码链代表一个个体，表示优化问题的一个解，如x有16种可能取值x₀,x₁,x₂，…，x₁₅，则可用4bit的二进制编码0000-1111来表示，将x,y,z的基因码组合在一起则形成码链。

（2）产生群体

t=0，随机产生n个个体组合成一个群体P(t），该群体代表优化问题的一些可能解的集合，当然，一般来说，它们的素质都很差。GA的任务是要从这些群体出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体和个体，满足优化的要求。

（3）评价

按编码的规则，将群体P(t）中的每一个体的基因码所对应的自变量（x_i,y_i,z_i）代入（1）式，算出其函数值F_i,i=0,1,2，…，N_oF_i越大，表示该个体有较高的适应度，更适应于f所定义的生存环境，适应度Fi为群体进化时的选择提供了依据。

（4）选择（复制）

按一定概率从群体P(t）中选取M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体P(t+1）中。一般P_i与F_i成正比，就是说，适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中适者生存的思想。

（5）交叉

对于选中的用于繁殖的每一对个体，随即选择同一整数n，将双亲的基因码链在此位置相互交换。如个体X,Y在位置3经交叉产生新个体X´，Y´，它们组合了父辈个体X,Y的特征，即

X=X₁X₂X₃X₄X₅[00011]

Y=Y₁Y₂Y₃Y₄Y₅[11100]

X´＝X₁X₂X₃X₄X₅[00000]

Y´＝Y₁Y₂Y₃Y₄Y₅[11111]

交叉体现了自然界中信息交换的思想。

（6）变异

以一定概率P_m从群体P(t+1）中随机选取若干个体，对于选中的个体，随机选取某一位进行反运算，即由1->0由0->1。同自然界一样，每一位发生变异的概率是很小的，变异模拟了生物进化过程中的偶然基因突变现象。GA的搜索能力主要是由选择和交叉赋予的，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全局最优，它进一步增强了GA的能力。

（7）迭代

对于交叉和变异产生的新一代群体进行重新评价和选择，然后再进行交叉和变异操作，如此循环往复。当群体中最优个体的适应度和平均适应度值不再提高，或迭代次数达到预设次数时，迭代过程结束。

2.生成曲面片的遗传算法

曲面片生成算法描述如下：

step1：初始化点列P₁和P₂，初始化交叉概率P_c，初始化变异概率P_m，初始化迭代计数器count为0。

step2：在P₁,P₂之间随机产生N个三角划分，其中每个三角划分称为一个串，这些串构成了第一代群体。

step3：对群体中的串随机地配对并按概率P_c进行交叉，将得到的新串添加到群体中。

step4：对群体中的串按概率P_m进行变异，将得到的新串添加到群体中。

step5：用选择算子筛选保留串形成下一代群体。

step6：修改迭代计数值，令count=count+1，如果迭代次数达到预设次数，转step7，否则转step3。

step7：返回群体中的最优串，结束。

3.倒转地层建模

使用前面的曲面生成算法，可以对如图4-4所示的倒转地层面进行建模，图4-5是通过这种方法进行建模得到的结果。

图4-4 倒转地层

图4-5 倒转地层建模

二、曲面交叉处理

在矿体出现分叉的情况下，需要把一个剖面上的一条轮廓线与另一个剖面上的多条轮廓线相连接。在本系统中，用以下方式来处理这种情况：首先用剖面1上的一条轮廓线分别与剖面2上的多条轮廓线分别相连得到多个连接曲面，取其中第一个曲面作为目标曲面；然后依次取其他曲面与目标曲面进行交叉处理，每次交叉处理的结果作为下一次交叉处理的目标曲面；最后一次交叉处理所得的曲面即所求实体曲面片。从一条轮廓线出发，分别与另外两条轮廓线相连得到两个空间曲面，对这两个曲面进行交叉处理的算法描述如下：

step1：初始化表示曲面1的三角形数组TA1，初始化表示曲面2的三角形数组TA2，初始化表示曲面1边界的线段数组BLA1，使其长度为0，初始化表示曲面2边界的线段数组BLA2，使其长度为0，初始化表示曲面1和曲面2共同边界的线段数组BLA使其长度为0。

step2：从三角形数组TA1搜索曲面边界线（段），结果存入线段数组BLA1中，从三角形数组TA2搜索曲面边界线（段），结果存入线段数组BLA2中，求BLA1和BLA2的交集，结果存入BLA中，求BLA1与BLA的差集，结果存入BLA1中，求BLA2与BLA的差集，结果存入BLA2中，初始化曲线BLA所在平面的单位法向量N,N从曲线BLA指向曲线BLAl。

step3：初始化循环控制变量I为0。

step4：如果I等于TA1中的三角形的个数，即TA1中的每个三角形都被处理过，转step9，否则从TA1中取（从0开始计数的）第I个三角形T₁。

step5：初始化循环控制变量J为0。

step6：如果J等于TA1中的三角形的个数，即TA2中的每个三角形都被处理过，转step8，否则从TA2中取（从0开始计数的）第J个三角形T₂。

step7：如果三角形T₁和T₂不相交或交线在这两个三角形的边上，令J=J+1，转step6，否则把这两个三角形分别分裂成多个三角形，使得这两个三角形的交线是分裂后的某两个三角形的公共边，从TA1中删除T₁，在T₁原来的位置处插入由T₁分裂后得到的三角形，从TA2中删除T₂，在T₂原来的位置处插入由T₂分裂后得到的三角形，转step4。

step8：令I=I+1，转step4。

step9：计算三角形数组TA1和TA2中三角形的公共边，将它们存入临时线段数组LA中，LA表示曲面I和曲面2的交线。

step10：计算TA1中顶点都不在边界线BLA上或有一个顶点在边界线BLA1的三角形，这些三角形的存储在临时三角形数组TA11中，计算TA2中顶点都不在边界线BLA上或有一个顶点在边界线BLA2的三角形，这些三角形存储在临时三角形数组TA21中。

step11：设置临时三角形数组TA12和TA22，令TA12=TA1-TA11,TA22=TA2-TA21。

step12：改变公共边界线BLA中线段的方向，使其正向相对于平面法向量N为逆时针方向。

step13：从TA12和TA22中提取相交于公共边界BLA上的三角形面片对，选择这对面片中相对于公共边界线BLA正向处于外侧的三角形面片，将TA12中外侧三角形保存在临时三角形数组TA13中，将TA22中外侧三角形保存在临时三角形数组TA23中。令TA12=TA12-TA13,TA22=TA22-TA23。

step14：以交线LA为约束边界，在TA12中搜索与TA13中相邻的三角形，将这些三角形添加到TA13中，在TA22中搜索与TA23中相邻的三角形，将这些三角形添加到TA23中。

s_tep15 返回TA11+TA13+TA21+TA23，结束。

使用如上所述曲面交叉处理算法，可以对如图4-6所示的矿体分叉情况进行建模，图4-7是通过这种方法建模得到的结果。

图4-6 分叉矿体截面图

图4-7 分叉矿体建模

‘贰’ 如何计算一个点与一个立体闭合曲面

三维闭合曲面构造算法。计算一个点与一个立体闭合曲面是大学物理中涉及的题目其中需要根据三维闭合曲面构造算法，进行计算，并且需要使用到计算机进行图像的构造。

‘叁’ 同济第七版高等数学的几种曲面积分求法

你好！第二类曲面积分的算法总结如下：
1：由于是有方向性的，所以有
“偶零奇倍”性质，跟一般情况相反的
F(x)是偶函数时，若Σ关于相应的面是对称的，一个部分取
+，一个部分取
-
结果就是F(x)
-
F(-
x)
=
F(x)
-
F(x)
=
0，两个部分互相抵消了
F(x)奇函数时，同样情况，一个部分取
+，一个部分取
-
结果就是F(x)
-
F(-
x)
=
F(x)
+
F(x)
=
2F(x)，两个部分的积分都相等，可叠加
2：三合一公式
对于Σ是z
=
z(x,y)形式的
法向量n
=
±
{
-
z'x，-
z'y，1
}
则∫∫_(Σ)
Pdydz+Qdzdx+Rdxdy
=
±
∫∫_(D)
{
P(-
z'x)
+
Q(-
z'y)
+
1
}
dxdy
取上/右/前
侧时，取
+
号
取下/左/后
侧时，取
-
号
3：高斯公式
∫∫_(Σ)
Pdydz+Qdzdx+Rdxdy
=
±
∫∫∫_(Ω)
(∂P/∂x+∂Q/∂y+∂R/∂z)
dxdydz
-
∫_(Σ和)
Pdydz+Qdzdx+Rdxdy
后面(Σ和)那部分，若原本给的曲面是不能围成封闭空间的话，不能直接使用高斯公式，需要补上几个面后使得区域封闭，例如补上若干个(Σ和)曲面，就可以运用高斯公式了，还要注意最后要减少所补上那几个曲面(Σ和)相应的积分
4：挖洞
若在Σ上，被积函数上有奇点的话，也不能直接运用高斯公式
需要补上一个小空间r=ε，足以包括所有内部的奇点的，然后取半径ε趋向0
运用高斯公式时也要减去这个部分相应的积分
所以有∫∫_(Σ)
=
±
∫∫∫_(Ω)
-
∫∫_(ε)
5：替代
若被积函数f的方程是在Σ上，则可以优先把Σ的方程代入f中
例如给Σ方程：x²+y²+z²=a²
则∫∫_(Σ)
(Pdydz+Qdzdx+Rdxdy)/√(x²+y²+z²)
=
∫∫_(Σ)
(Pdydz+Qdzdx+Rdxdy)/a
=
(1/a)∫∫_(Σ)
Pdydz+Qdzdx+Rdxdy
于是这样，就可以避免了4：的情况，不用挖洞
去掉奇点后就可以继续补面使用高斯公式了
很高兴能回答您的提问，您不用添加任何财富，只要及时采纳就是对我们最好的回报
。若提问人还有任何不懂的地方可随时追问，我会尽量解答，祝您学业进步，谢谢。XD
如果问题解决后，请点击下面的“选为满意答案”

‘肆’ 空间曲线和空间曲面什么区别与联系其方程都是三元函数嘛

空间曲线与空间曲面都是三元方程，而不一定是三元函数。
区别一个是曲线一个是曲面，其空间所需的计算对象不同：空间曲线对应的有某一点处的切线和法平面；而空间曲面对应的有切平面和法线；

要说联系，自以为，就在求导以及向量算法上了。此外，算法上更不同的是，对曲线的长度计算，和对曲面的面积计算，方法不一样。

‘伍’ 第二类曲线积分三种计算方法

一、参数方程法

根据曲线参数方程计算空间第二类曲线积分是参数法计算平面曲线积分情形的推广，也是计算空间第二类曲线积分最常用的方法之一。

‘陆’ 曲面细分的原理简述

曲面细分，或者更准确的说“镶嵌化处理技术”，就是在顶点与顶点之间自动嵌入新的顶点。在自动插入大量新的顶点之后，模型的曲面会被分得非常细腻，看上去更加平滑致密。它是一种能够在图形芯片内部自动创造顶点，使模型细化，从而获得更好画面效果的技术。 曲面细分能自动创造出数百倍与原始模型的顶点，这些不是虚拟的顶点，而是实实在在的顶点，效果是等同于建模的时候直接设计出来的。
曲面细分技术是完全可编程的，它提供了多种插值顶点位置的方法来创造各种曲面：
1. N-Patch曲面，就是和当年TruForm技术一样，根据基础三角形顶点的法线决定曲面；
2. 贝塞尔曲面，根据贝塞尔曲线的公式计算顶点的位置；
3. B-Spline、NURBs、NUBs曲线（这三种曲线均为CAD领域常用曲线，在Maya中均有相应工具可以生成）
4. 通过递归算法接近Catmull-Clark极限曲面。Tessellation技术最初主要被用以“细分曲面”，随着该技术被纳入DirectX11范畴，得到大范围推广之后，插值顶点的算法也越来越多，因此用途也越来越广，产生了很多非常有创意的应用。 例如nVIDIA的一个Demo演示了利用Tessellation技术生产的“头发”，这些头发都是真实存在的，当然并不是为每一根头发建立一个模型，而是利用Tessellation技术在有限的头发模型中，镶嵌入更多的头发模型。
除了大幅提升模型细节和画质外，Tessellation最吸引程序员的地方就是：他们无需手动设计上百万个三角形的复杂模型，只需简单勾绘一个轮廓，剩下的就可以交给Tessellation技术自动镶嵌，大大提高开发效率；而且简单的模型在GPU处理时也能大幅节约显存开销，同时大幅提升渲染速度。

‘柒’ 曲面拟合方法和曲面重构方法有哪些

散点曲面重构是计算机图形学中的一个基本问题，针对这个问题提出了一种全新的基于核回归方法的散点曲面重构方法，使用二维信号处理方法中非参数滤波等成熟手段进行曲面重构。
这种方法可以生成任意阶数连续的曲面，在理论上保证了生成曲面的连续性，可以自定义网格的拓扑，在曲率大或者感兴趣的局部能够自适应调整网格点的密度，生成的结果方便LOD建模，数据的拟合精度也可以通过调整滤波参数控制，算法自适应调整滤波器的方向，使结果曲面可以更好保持尖锐特征。同时在构造过程中避免了传统的细分曲面方法中迭代、Delaunay剖分和点云数据中重采样等时间开销大的过程，提高了效率。对于采样不均、噪声较大的数据。该算法的鲁棒性很好。实验表明这种曲面建模方法能够散点重构出精度较高的连续曲面，在效率上有很大提高，在只需要估计曲面和其一阶导数时，利用Nadaraya-Watson快速算法可以使算法时间复杂度降为O（N），远低于其他曲面重构平滑方法。同时算法可以对曲面的局部点云密度、网格顶点法矢等信息做有效的估计。重构出的曲面对类似数字高程模型（DEM）的数据可以保证以上的优点。但如果散点数据不能被投影到2维平面上，曲面重构就需要包括基网格生成、重构面片缝合等过程。缝合边缘的连续性也不能在理论上得到保证

‘捌’ 曲面积分的算法高数

## 几何意义
曲面Σ上任一点都满足x^2+y^2+z^2=4，所以积分区域上的被积函数x^2+y^2+z^2=4
I = 4∫∫dS = 4*4πR^2 = 64π
其中∫∫dS的几何意义是Σ即球面x^2+y^2+z^2=4的表面积，代入表面积公式4πR^2即可

‘玖’ （高数）曲面积分的计算

直接化成二重积分计算。
∑在xoy的投影区域D是：
直线x+y=1与两个坐标轴围成的直角三角形区域。
原式=-∫∫〔D〕【xy（1-x-y）】dxdy
=-∫〔0到1〕dx∫〔0到1-x〕【xy-xxy-xyy】dy