科学计算可视化

科学计算可视化---第八讲中国地质大学信息工程学院严红平体元投射法（十）深度排序的实现：•数据结构及初始化：建立便于判断相互遮挡关系的凸多面体网格单元的数据结构，并予以初始化，生成一个以单元为结点的有向无环图；•对该有向无环图进行拓扑排序。数据结构：-单元数据结构：记录节点，面，单元及其邻接关系，以及入度的信息；-面的数据结构：记录该面两侧单元的序号及该面片相对于左右两侧单元的可见值。如果该面为边界面，则其一侧的单元不存在。体元投射法（十一）数据结构初始化---按照网格输入顺序进行：•在给定视点后，每输入一个单元，首先将单元序号，类型及单元各面所在的平面系数初始化；•计算单元内点O的坐标，以及单元各面片相对于点O的可见值；如果某面片为该单元与相邻单元所共有的面，则计算该面片相对于这两个相邻单元的可见值，并确定遮挡关系，给被遮挡单元的入度值加1；•重复上述过程，直至多面体网格的所有单元均输入完毕。•将整个多面体网格用一个有向无环图来表示。每个单元对应于图中的一个节点，相邻单元的遮挡关系对应于图中的一条弧，每个单元的入度就是指向它的弧的数目，也就是该单元内具有负可见值的内部面的个数。有向无环图：体元投射法（十二）123456789体元投射法（十三）有向无环图的拓扑排序：•从有向无环图中任选一个入度为0的节点，作为序列的第一个单元加以输出，同时从有向无环图中删除该节点，并相应地修改与被删节点有关的信息，即删去相邻节点中由被删节点射入的弧，也就是将相邻单元的入度减1。•从更新后的有向无环图中选取第二个入度为0的节点，重复上述操作。•这一过程循环进行，直至全部单元输出为止。注：当视点发生变化时，相应的有向无环图需重新建立。有向无环图的拓扑排序：1234567891,2,3,4,6,5,7,9,81,2,4,3,5,6,7,9,81,2,3,4,5,6,7,9,81,2,4,6,3,5,7,9,81,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的路径距离。像素链：链的每个节点对应于一段体元的内部路径，且连接点按照路径距离的长短由小到大排列。当一个体元的各面投影到图像平面后，与各个像素点相关的所有路径距离，都可按由小到大的顺序排列，一次成对的路径距离之间位于体元的内部。体元投射法与光线投射法相结合算法实现：•从不规则数据场中任取一个体元，将它的各个面投影到图像平面上。为投影域内的每个像素建立像素链；-图像平面上的每个像素都会被该体元的偶数个面片的投影所覆盖。凸体元投影域内每个像素被两个平面片的投影所覆盖；凹体元投影域内每个像素被两个以上偶数个面片的投影所覆盖。•从不规则数据场中再取下一个体元，进行同样操作。若某一像素已有链节点，则将新旧两个链进行合并操作，并按前后顺序对每一个节点进行颜色和不透明度的累积计算。•反复执行以上操作，直至处理完所有体元。体元投射法与光线投射法相结合总结：该算法将体元投射法与光线投射法相结合，通过对每个像素建立链表，将体元排序问题化解成链节点的合成或插入运算，并且不对凹体元进行特别处理。算法优化：采用体元绘制顺序的优化安排，利用多边形扫描填充算法快速求取路径距离以及建立长度与颜色积累和透明度积累的对应等措施，可以进一步加快该算法的运算速度。该算法优化后较一般光线投射算法快4~7倍。构造三维不规则数据场中的等值面算法基本框架：•由差分方程计算网格中每个节点处的梯度值；•采用与MarchingCubes类似的方法，找出与等值面相交的单元，并用线性插值法计算出单元的边与等值面的交点的位置及该点处的梯度；•采用双三次Hermite插值方法来构造单元内的等值面片，以保证各单元内的等值面片在顶点处的法向量是连续的；•根据每个顶点出的法向量梯度，利用双三次Hermite插值方法求出邻接边上各处的法向量，以保证各等值面片的邻接边上的法向量连续。mnmnmimnmnminiFXXXgj1单元内等值面的几何表示由单元边与等值面的交点及交点处的法线构造双三次Hermite曲面片：ThhwBFuFwuQ,hhUMuFhhWMwF123uuuU00000111001001110111001000100IIIIIIppppppppppppBuuuu123位置矢量角点处w方向切线矢量角点处u方向切线矢量u,v的Hermite调和函数Hermite几何矩阵在单元内部与交面重合abaaabaanPPPPPPS等值面边界法向的连续性等值面法向量双三次Hermite表示中的Hermite几何矩阵：00000111001001110111001000100IIIIIIppppppppppppBuuuu的求取请参见[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插值；常用的拟合方法：-线性最小二乘拟合；-多项式的最小二乘曲线拟合；-Bézier曲线,B-Spline；注：插值通常是利用曲线拟合的方法，通过离散的输入采样点建立一个连续函数，用这个重建的函数便可以求出任意位置处的函数值。B样条曲线和曲面在我们工程中应用的拟合曲线，一般地说可以分为两类：一种是最终生成的曲线通过所有的给定型值点，比如抛物样条曲线和三次参数样条曲线等，这样的曲线适用于插值放样；另一种曲线是，它的最终结果并不一定通过给定的型值点，而只是比较好地接近这些点，这类曲线（或曲面）比较适合于外形设计。因为在外形设计中(比如汽车、船舶)，初始给出的数据点往往并不精确；并且有的地方在外观上考虑是主要的,因为不是功能的要求，所以为了美观而宁可放弃个别数据点。因此不须最终生成的曲线都通过这些数据点。另一方面，考虑到在进行外形设计时应易于实时局部修改，反映直观，以便于设计者交互操作。第一类曲线在这方面就不能适应。法国的Bezier为此提出了一种新的参数曲线表示方法，因此称为Bezier曲线。后来又经过Gordon、Forrest和Riesenfeld等人的拓广、发展，提出了Ｂ样条曲线。这两种曲线都因能较好地适用于外形设计的特殊要求而获得了广泛的应用。一、Bezier曲线Bezier曲线的形状是通过一组多边折线（特征多边形）的各顶点唯一地定义出来的。在这组顶点中：(1)只有第一个顶点和最后一个顶点在曲线上；(2)其余的顶点则用于定义曲线的导数、阶次和形状；(3)第一条边和最后一条边则表示了曲线在两端点处的切线方向。P0P0P2P1P1P2P3P3P1P0P3P2１.Bezier曲线的数学表达式Bezier曲线是由多项式混合函数推导出来的，通常n+1个顶点定义一个n次多项式。其数学表达式为：(0≤t≤1)式中：Ｐi：为各顶点的位置向量Ｂi,n(t)：为伯恩斯坦基函数niniitBPtP0,)()(伯恩