科学计算可视化

科学计算可视化-第八讲,中国地质大学信息工程学院,严红平,体元投射法（十）,深度排序的实现：,数据结构及初始化：建立便于判断相互遮挡关系的凸多面体网格单元的数据结构，并予以初始化，生成一个以单元为结点的有向无环图；,对该有向无环图进行拓扑排序。,数据结构：,-单元数据结构：记录节点，面，单元及其邻接关系，以及入度的信息；,-面的数据结构：记录该面两侧单元的序号及该面片相对于左右两侧单元的可见值。如果该面为边界面，则其一侧的单元不存在。,体元投射法（十一）,数据结构初始化-按照网格输入顺序进行：,在给定视点后，每输入一个单元，首先将单元序号，类型及单元各面所在的平面系数初始化；,计算单元内点O的坐标，以及单元各面片相对于点O的可见值；如果某面片为该单元与相邻单元所共有的面，则计算该面片相对于这两个相邻单元的可见值，并确定遮挡关系，给被遮挡单元的入度值加1；,重复上述过程，直至多面体网格的所有单元均输入完毕。,将整个多面体网格用一个有向无环图来表示。每个单元对应于图中的一个节点，相邻单元的遮挡关系对应于图中的一条弧，每个单元的入度就是指向它的弧的数目，也就是该单元内具有负可见值的内部面的个数。,有向无环图：,体元投射法（十二）,1,2,3,4,5,6,7,8,9,体元投射法（十三）,有向无环图的拓扑排序：,从有向无环图中任选一个入度为0的节点，作为序列的第一个单元加以输出，同时从有向无环图中删除该节点，并相应地修改与被删节点有关的信息，即删去相邻节点中由被删节点射入的弧，也就是将相邻单元的入度减1。,从更新后的有向无环图中选取第二个入度为0的节点，重复上述操作。,这一过程循环进行，直至全部单元输出为止。,注：当视点发生变化时，相应的有向无环图需重新建立。,有向无环图的拓扑排序：,1,2,3,4,5,6,7,8,9,1,2,3,4,6,5,7,9,8,1,2,4,3,5,6,7,9,8,1,2,3,4,5,6,7,9,8,1,2,4,6,3,5,7,9,8,1,2,4,3,6,5,7,9,8,体元投射法（十四）,非凸多面体网格的深度排序：,何为非凸多面体网格？,如果三维空间多面体网格的外部边界是非凸的，即存在凹穴或空洞，则该多面体网格称为非凸多面体网格。,体元投射法（十五）,判断三维空间多面体网格的凹凸性：,建立多面体网格的数据结构，注明所有包含边界面的单元；,-从任意一个包含边界面的单元出发，根据单元之间的邻接关系进行搜索。如果能将全部边界面的单元都连接起来，则该多面体网格仅有外部边界，而无空洞；否则，该多面体网格存在空洞；,在没有内部空洞时，通过判断外部边界中所有两两相邻的外部面在其交线处的二面角来判断多面体网格是否为凸的。当二面角大于或等于180度时，该多面体网格为凸多面体网格；否则，为非凸网格，即存在凹穴。,判断网格的内部空洞是否为凸：在构成内部空洞的边界面中，如果所有两两相邻的边界面在其交线处的二面角均小于180度，则该空洞为凸的，否则，非凸。,体元投射法（十六）,非凸多面体网格的深度排序：,-采用适用于凸网格的深度排序与比较视点到单元中心距离相结合的方法；,-将三维空间非凸多面体网格进行代约束的三维Delaunay三角剖分，将其剖分为符合Delaunay准则的四面体网格，而且包含了原有的边界面片。然后采用适用于凸网格的深度排序法。,-采用四面体填补法将非凸多面体网格转化为凸多面体网格，即将三维空间非凸多面体网格中的凹穴或空洞用四面体填补，使其变为凸多面体。然后采用适用于凸网格的深度排序法。,相当复杂；破坏了原有的几何邻接关系。,不适用于具有特殊外部边界的网格的深度排序；,体元投射法（十七）,虚线为voronoi图；实线为delaunay三角形,voronoi图是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。个在平面上有区别的点按照最邻近原则划分平面；每个点与它的最近邻区域相关联。,delaunay三角形是由与相邻voronoi多边形共享一条边的相关点连接而成的三角形。其外界圆圆心是与三角形相关的voronoi多边形的一个顶点；voronoi三角形是delaunay图的偶图。,Voronoi图与Delaunay三角形,Delaunay准则：任一三角形的外接圆内不能包含其它任何点。,四面体填补法,输入非凸网格的单元，节点信息,分解体元为四面体，建立四面体单元之间的邻接关系,扫描纪录外部边界面的数据结构,确认要填补的四面体不与任何外部面相交,连接相应的点对，生成新的四面体，并修改其它数据结构,根据槽连线的长度及二面角大小处理新生成的凹槽，直至相邻外部面间均无凹槽,有,无,非,将该凸空洞剖分为四面体,是,输入网格的单元，节点信息,分解体元为四面体，建立四面体单元之间的邻接关系,凸网格深度排序,物质分类，颜色，及不透明度值,光强度计算及合成,帧缓存图像,转换为凸网格,非凸,凸,体元投射法（十八）,取深度序列中第一个四面体,在四面体内构造等值面,等值面排序,等值面按顺序投影到显示屏幕,投影区域内各像素的光强度计算,取下一个四面体,是,否,否,是,体元投射法（十九）,体元投射法与光线投射法相结合,一些概念：,路径距离：当平行投影时，若某个像素P发出的光线与一个面片S相交于Q点，则P到Q的长度及为该像素到面片S的路径距离；当透视投影时，若从视点V发出光线，经像素P与面片S相交于点Q，则VQ的长度为像素P到面片S的路径距离。,像素链：链的每个节点对应于一段体元的内部路径，且连接点按照路径距离的长短由小到大排列。,当一个体元的各面投影到图像平面后，与各个像素点相关的所有路径距离，都可按由小到大的顺序排列，一次成对的路径距离之间位于体元的内部。,体元投射法与光线投射法相结合,算法实现：,从不规则数据场中任取一个体元，将它的各个面投影到图像平面上。为投影域内的每个像素建立像素链；,-图像平面上的每个像素都会被该体元的偶数个面片的投影所覆盖。凸体元投影域内每个像素被两个平面片的投影所覆盖；凹体元投影域内每个像素被两个以上偶数个面片的投影所覆盖。,从不规则数据场中再取下一个体元，进行同样操作。若某一像素已有链节点，则将新旧两个链进行合并操作，并按前后顺序对每一个节点进行颜色和不透明度的累积计算。,反复执行以上操作，直至处理完所有体元。,体元投射法与光线投射法相结合,总结：,该算法将体元投射法与光线投射法相结合，通过对每个像素建立链表，将体元排序问题化解成链节点的合成或插入运算，并且不对凹体元进行特别处理。,算法优化：,采用体元绘制顺序的优化安排，利用多边形扫描填充算法快速求取路径距离以及建立长度与颜色积累和透明度积累的对应等措施，可以进一步加快该算法的运算速度。该算法优化后较一般光线投射算法快47倍。,构造三维不规则数据场中的等值面,算法基本框架：,由差分方程计算网格中每个节点处的梯度值；,采用与MarchingCubes类似的方法，找出与等值面相交的单元，并用线性插值法计算出单元的边与等值面的交点的位置及该点处的梯度；,采用双三次Hermite插值方法来构造单元内的等值面片，以保证各单元内的等值面片在顶点处的法向量是连续的；,根据每个顶点出的法向量梯度，利用双三次Hermite插值方法求出邻接边上各处的法向量，以保证各等值面片的邻接边上的法向量连续。,单元内等值面的几何表示,由单元边与等值面的交点及交点处的法线构造双三次Hermite曲面片：,位置矢量,角点处w方向切线矢量,角点处u方向切线矢量,u,v的Hermite调和函数,Hermite几何矩阵,等值面边界法向的连续性,等值面法向量双三次Hermite表示中的Hermite几何矩阵：,角点法矢量,角点处法向量沿w方向的一阶导,角点处法向量沿u方向的一阶导,II,III的求取请参见Gall89.,散乱数据的可视化（一）,散乱数据的定义：,散乱数据是在二维平面上或三维空间中无规则的、随机分布的数据。,散乱数据的分类：,-按其复杂程度：单自变量、双自变量及多自变量。,散乱数据的来源：,-物理量的测量数据；,-科学实验所得数据；,-科学计算或工程计算的结果数据；,-按数据规模：小、中、大规模散乱数据。,散乱数据的可视化：,散乱数据的可视化是对散乱数据进行插值或拟合，形成曲线或曲面并用图形或图像表示出来的技术。,散乱数据的可视化（二）,散乱数据可视化的应用领域：,-地质勘探数据的显示；,-测井数据的显示；,-油藏数据的显示；,-气象数据的显示；,-有限元计算结果中非结构化数据的显示；,散乱数据的可视化（三）,散乱数据的可视化方法：散乱数据的插值及拟合。,插值问题的定义：,插值是首先假定给定采样数据是正确的，然后确定某个函数，使其经过各采样数据点，并利用该函数确定相邻两个采样值之间的数值时采用的运算过程。设在二维平面上有n个点(xi,yi)(i=1,n)，且Zi=F(xi,yi)。此时，插值问题就是要构造一个具有C1连续的函数F(x,y)，使其在点(xi,yi)(i=1,n)的函数值为Zi，即Zi=F(xi,yi)。,拟合问题的定义：,拟合是通过对已知数据的分析，设法找出某条光滑曲线，使其最佳地接近已知数据，但不必经过所有数据点。,散乱数据的插值与拟合（一）,散乱数据的插值与拟合（二）,插值问题的特点：,-采样数据假定是正确的；,-由采样数据确定插值函数；,-插值函数需精确经过采样点；,拟合问题的特点：,-采样数据不一定是正确的；,-由采样数据确定拟合函数；,-拟合函数不必经过所有采样点；,散乱数据的插值与拟合（三）,常用的插值方法：,-分段线性插值；,-三次样条插值；,-Lagrange插值；,常用的拟合方法：,-线性最小二乘拟合；,-多项式的最小二乘曲线拟合；,-Bzier曲线,B-Spline；,注：插值通常是利用曲线拟合的方法，通过离散的输入采样点建立一个连续函数，用这个重建的函数便可以求出任意位置处的函数值。,B样条曲线和曲面,在我们工程中应用的拟合曲线，一般地说可以分为两类：一种是最终生成的曲线通过所有的给定型值点，比如抛物样条曲线和三次参数样条曲线等，这样的曲线适用于插值放样；另一种曲线是，它的最终结果并不一定通过给定的型值点，而只是比较好地接近这些点，这类曲线（或曲面）比较适合于外形设计。,因为在外形设计中(比如汽车、船舶)，初始给出的数据点往往并不精确；并且有的地方在外观上考虑是主要的,因为不是功能的要求，所以为了美观而宁可放弃个别数据点。因此不须最终生成的曲线都通过这些数据点。另一方面，考虑到在进行外形设计时应易于实时局部修改，反映直观，以便于设计者交互操作。第一类曲线在这方面就不能适应。,法国的Bezier为此提出了一种新的参数曲线表示方法，因此称为Bezier曲线。后来又经过Gordon、Forrest和Riesenfeld等人的拓广、发展，提出了样条曲线。这两种曲线都因能较好地适用于外形设计的特殊要求而获得了广泛的应用。,一、Bezier曲线Bezier曲线的形状是通过一组多边折线（特征多边形）的各顶点唯一地定义出来的。在这组顶点中：(1)只有第一个顶点和最后一个顶点在曲线上；(2)其余的顶点则用于定义曲线的导数、阶次和形状；(3)第一条边和最后一条边则表示了曲线在两端点处的切线方向。,.Bezier曲线的数学表达式Bezier曲线是由多项式混合函数推导出来的，通常n+1个顶点定义一个n次多项式。其数学表达式为：(0t1)式中：i：为各顶点的位置向量i,n(t)：为伯恩斯坦基函数,伯恩斯坦基函数的表达式为：假如规定：，！，则t=0:i=0,Bi,n(t)=1i0,Bi,n(t)=0P(0)=P0,t=1:i=n,Bi,n(t)=1in,Bi,n(t)=0P(1)=Pn所以说，“只有第一个顶点和最后一个顶点在曲线上”。即Bezier曲线只通过多边折线的起点和终点。,下面我们通过对基函数求导，来分析两端切矢的情况。得：,讨论：t=0:i=0:Bi-1,n-1(t)=0；Bi,n-1(t)=1.i=1:Bi-1,n-1(t)=1；Bi,n-1(t)=0.i=2:Bi-1,n-1(t)=0；Bi,n-1(t)=0.（均出现0的非0次幂）,t=0同理可得，当t=1时这两个式子说明：Bezier曲线在两端点处的切矢方向与特征多边形的第一条边和最后一条边相一致。,.二次和三次Bezier曲线(1)三个顶点：P0,P1,P2可定义一条二次(n=2)Bezier曲线：其相应的混合函数为：,所以，根据式：二次Bezier曲线的表达形式为：P(t)=(1-t)2P0+2t(1-t)P1+t2P2（t1),根据Bezier曲线的总体性质，可讨论二次Bezier曲线的性质：P(t)=(1-t)2P0+2t(1-t)P1+t2P2P(t)=2(t-1)P0+2(1-2t)P1+2tP2P(1/2)=1/2P1+1/2(P0+P2)P(0)=2(P1-P0)P(1)=2(P2-P1)P(1/2)=P2-P0,二次Bezier曲线是一条抛物线,(2)四个顶点P0、P1、P2、P3可定义一条三次Bezier曲线：*,二、B样条曲线.从Bezier曲线到样条曲线(1)Bezier曲线在应用中的不足：缺乏灵活性一旦确定了特征多边形的顶点数(m个)，也就决定了曲线的阶次(m-1次)，无法更改；控制性差当顶点数较多时，曲线的阶次将较高，此时，特征多边形对曲线形状的控制将明显减弱；,不易修改由曲线的混合函数可看出，其值在开区间(0,1)内均不为零。因此所定义之曲线在(0t1)的区间内的任何一点均要受到全部顶点的影响，这使得对曲线进行局部修改成为不可能。（而在外形设计中，局部修改是随时要进行的）,为了克服Bezier曲线存在的问题，Gordon等人拓展了Bezier曲线，就外形设计的需求出发，希望新的曲线要：易于进行局部修改；更逼近特征多边形；是低阶次曲线。于是，用n次样条基函数替换了伯恩斯坦基函数，构造了称之为样条曲线的新型曲线。,2.样条曲线的数学表达式样条曲线的数学表达式为：在上式中，0t1；i=0,1,2,m,所以可以看出：样条曲线是分段定义的。如果给定m+n+1个顶点Pi(i=0,1,2,m+n)，则可定义m+1段n次的参数曲线。,在以上表达式中：Fk,n(t)为n次B样条基函数，也称样条分段混合函数。其表达式为：式中：0t1k=0,1,2,n,连接全部曲线段所组成的整条曲线称为n次样条曲线。依次用线段连接点Pi+k(k=0,1,n)所组成的多边折线称为样条曲线在第i段的特征多边形。,.二次样条曲线在二次样条曲线中，n=2,k=0,1,2故其基函数形式为：,有了基函数，因此可写出二次样条曲线的分段表达式为：(i=0,1,2,m)m+1段,写成一般的矩阵形式为：式中，k为分段曲线的特征多边形的顶点：B0,B1,B2。对于第i段曲线的Bk即为：Pi,Pi+1,Pi+2连续的三个顶点。（见下图）,n=2,二次B样条曲线m+n+1个顶点，三点一段，共m+1段。,i=0P0,2(t),i=1P1,2(t),二次样条曲线的性质先对P(t)求导得：然后分别将t=0,t=0.5,t=1代入P(t)和P(t)，可得：P(0)=1/2(B0+B1),P(1)=1/2(B1+B2);P(0)=B1-B0,P(1)=B2-B1;P(1/2)=1/21/2P(0)+P(1)+B1P(1/2)=1/2(B2-B0)=P(1)-P(0),与以上这些式子所表达的性质相符的曲线是何种形状：（见下图）,是什么曲线？与Bezier曲线有何差别？,结论：分段二次B样条曲线是一条抛物线；有n个顶点定义的二次B样条曲线，其实质上是n-2段抛物线（相邻三点定义）的连接，并在接点处达到一阶连续。（见下图）,.三次样条曲线分段三次样条曲线由相邻四个顶点定义，其表达式为：P(t)=F0,3(t)B0+F1,3(t)B1+F2,3(t)B2+F3,3(t)B3(0t1)可见，由n个顶点定义的完整的三次样条曲线是由n-3段分段曲线连接而成的。很容易证明，三次样条曲线在连接处达到二阶连续。*,样条曲线是一种非常灵活的曲线，曲线的局部形状受相应顶点的控制很直观。这些顶点控制技术如果运用得好，可以使整个样条曲线在某些部位满足一些特殊的技术要求。如：可以在曲线中构造一段直线；使曲线与特征多边形相切；使曲线通过指定点；指定曲线的端点；指定曲线端点的