科学计算可视化科学计算可视化 - 第第八讲八讲体元投射法（十）深度排序的实现深度排序的实现深度排序的实现深度排序的实现： 数据结构及初始化：建立便于判断相互遮挡关系的凸多面体网格单元的数据结构，并予以初始化，生成一个以单元为结点的有向无环图； 对该有向无环图进行拓扑排序。数据结构数据结构数据结构数据结构：- 单元数据结构：记录节点，面，单元及其邻接关系，以及入度的信息；- 面的数据结构：记录该面两侧单元的序号及该面片相对于左右两侧单元的可见值。如果该面为边界面，则其一侧的单元不存在。体元投射法（十一）数据结构初始化数据结构初始化数据结构初始化数据结构初始化-按照网格输入顺序进行： 在给定视点后，每输入一个单元，首先将单元序号，类型及单元各面所在的平面系数初始化； 计算单元内点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 三角形voronoivoronoi图图图图是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。个在平面上有区别的点按照最邻近原则划分平面；每个点与它的最近邻区域相关联。delaunay delaunay 三角形三角形三角形三角形是由与相邻voronoi多边形共享一条边的相关点连接而成的三角形。其外界圆圆心是与三角形相关的voronoi 多边形的一个顶点； voronoi 三角形是delaunay图的偶图。Voronoi图与Delaunay三角形DelaunayDelaunay准则准则准则准则：任一三角形的外接圆内不能包含其它任何点。四面体填补法输入非凸网格的单元，节点信息分解体元为四面体，建立四面体单元之间的邻接关系判断网格有无空洞扫描纪录外部边界面的数据结构确认要填补的四面体不与任何外部面相交连接相应的点对，生成新的四面体，并修改其它数据结构根据槽连线的长度及二面角大小处理新生成的凹槽，直至相邻外部面间均无凹槽开始结束有无凸空洞非将该凸空洞剖分为四面体是输入网格的单元，节点信息分解体元为四面体，建立四面体单元之间的邻接关系判断网格的凹凸性凸网格深度排序物质分类，颜色，及不透明度值光强度计算及合成帧缓存图像开始结束转换为凸网格非凸凸体元投射法（十八）取深度序列中第一个四面体在四面体内构造等值面等值面排序等值面按顺序投影到显示屏幕投影区域内各像素的光强度计算深度序列中还有四面体吗？该四面体是填补的？取下一个四面体是否否是体元投射法（十九）体元投射法与光线投射法相结合一些概念一些概念一些概念一些概念：路径距离路径距离路径距离路径距离：当平行投影时，若某个像素P发出的光线与一个面片S相交于Q点，则P到Q的长度及为该像素到面片S的路径距离；当透视投影时，若从视点V发出光线，经像素P与面片S相交于点Q，则VQ的长度为像素P到面片S的路径距离。像素链像素链像素链像素链：链的每个节点对应于一段体元的内部路径，且连接点按照路径距离的长短由小到大排列。当一个体元的各面投影到图像平面后，与各个像素点相关的所有路径距离，都可按由小到大的顺序排列，一次成对的路径距离之间位于体元的内部。体元投射法与光线投射法相结合算法实现算法实现算法实现算法实现： 从不规则数据场中任取一个体元，将它的各个面投影到图像平面上。为投影域内的每个像素建立像素链；- 图像平面上的每个像素都会被该体元的偶数个面片的投影所覆盖。凸体元投影域内每个像素被两个平面片的投影所覆盖；凹体元投影域内每个像素被两个以上偶数个面片的投影所覆盖。 从不规则数据场中再取下一个体元，进行同样操作。若某一像素已有链节点，则将新旧两个链进行合并操作，并按前后顺序对每一个节点进行颜色和不透明度的累积计算。 反复执行以上操作，直至处理完所有体元。体元投射法与光线投射法相结合总结总结总结总结：该算法将体元投射法与光线投射法相结合，通过对每个像素建立链表，将体元排序问题化解成链节点的合成或插入运算，并且不对凹体元进行特别处理。算法优化算法优化算法优化算法优化：采用体元绘制顺序的优化安排，利用多边形扫描填充算法快速求取路径距离以及建立长度与颜色积累和透明度积累的对应等措施，可以进一步加快该算法的运算速度。该算法优化后较一般光线投射算法快47倍。构造三维不规则数据场中的等值面算法基本框架算法基本框架算法基本框架算法基本框架： 由差分方程计算网格中每个节点处的梯度值； 采用与Marching Cubes类似的方法，找出与等值面相交的单元，并用线性插值法计算出单元的边与等值面的交点的位置及该点处的梯度； 采用双三次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 B样条曲线和曲面样条曲线和曲面在我们工程中应用的拟合曲线，一般地说可以分为两类：一种是最终生成的曲线通过所有的给定型值点最终生成的曲线通过所有的给定型值点最终生成的曲线通过所有的给定型值点最终生成的曲线通过所有的给定型值点，比如抛物样条曲线和三次参数样条曲线等，这样的曲线适用于插值放样；另一种曲线是，它的最终结果并不一定通过给定的它的最终结果并不一定通过给定的它的最终结果并不一定通过给定的它的最终结果并不一定通过给定的型值点型值点型值点型值点，而只是比较好地接近这些点而只是比较好地接近这些点而只是比较好地接近这些点而只是比较好地接近这些点，这类曲线（或曲面）比较适合于外形设计。因为在外形设计中(比如汽车、船舶)，初始给出的数据点往往并不精确；并且有的地方在外观上考虑是主要的,因为不是功能的要求，所以为了美观而宁可放弃个别数据点。因此不须最终生成的曲线都通过这些数据点。另一方面，考虑到在进行外形设计时应易于实时局部修易于实时局部修易于实时局部修易于实时局部修改改改改，反映直观，以便于设计者交互操作。第一类曲线在这方面就不能适应。法国的 Bezier 为此提出了一种新的参数曲线表示方法，因此称为Bezier曲线。后来又经过 Gordon、Forrest和 Riesenfeld等人的拓广、发展， 提出了样条曲线。 这两种曲线都因能较好地适用于 外形设计的特殊要求而获得了广泛的 应用。一、一、BezierBezier曲线曲线Bezier曲线的形状是通过一组多边折线（特征多边形）的各顶点唯一地定义出来的。在这组顶点中：(1) 只有第一个顶点和最后一个顶点在曲线上；(2) 其余的顶点则用于定义曲线的导数、阶次和形状；(3) 第一条边和最后一条边则表示了曲线在两端点处的切线方向。.Bezier.Bezier曲线的数学表达式曲线的数学表达式 Bezier曲线是由多项式混合函数推导出来的，通常 n+1 个顶点定义一个 n次多项式。其数学表达式为： (0 t 1)式中：i：为各顶点的位置向量i,n(t)：为伯恩斯坦基函数伯恩斯坦基函数的表达式为：假如规定：，！，则 t=0: i=0 ,Bi,n(t)=1 i0 ,Bi,n(t)=0 P(0)=P0t=1:i=n ,Bi,n(t)=1 in ,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曲线在两端点处的切矢方向与特征多边形的第一条边和最后一条边相一致。 . .二次和三次二次和三次BezierBezier曲线曲线(1) 三个顶点：P0,P1,P2 可定义一条二次(n=2) Bezier曲线：其相应的混合函数为： 所以，根据式：二次 Bezier 曲线的表达形式为：P(t)=(1-t)2P0+2t(1-t)P1+t 2 P2（t 1)根据 Bezier 曲线的总体性质，可讨论二次 Bezier 曲线的性质： P(t)=(1-t)2P0+2t(1-t)P1+t2 P2 P(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 B样条曲线样条曲线. .从从 Bezier Bezier 曲线到样条曲线曲线到样条曲线(1) Bezier (1) Bezier 曲线在应用中的不足：曲线在应用中的不足： 缺乏灵活性一旦确定了特征多边形的顶点数(m个)，也就决定了曲线的阶次(m-1次)，无法更改； 控制性差当顶点数较多时，曲线的阶次将较高，此时，特征多边形对曲线形状的控制将明显减弱； 不易修改由曲线的混合函数可看出， 其值在开区间 ( 0 , 1 ) 内均不为零。 因此所定义之曲线在 ( 0 t 1)的 区间内的任何一点均要受到全部顶点的影响，这使得对曲线进行局部修改成为不可能。（而在外形设计中，局部修改是随时要进行的）为了克服 Bezier 曲线存在的问题，Gordon 等人拓展了 Bezier曲线，就外形设计的需求出发，希望新的曲线要： 易于进行局部修改； 更逼近特征多边形； 是低阶次曲线。于是，用 n次样条基函数替换了伯恩斯坦基函数，构造了称之为样条曲线的新型曲线。2. 2.样条曲线的数学表达式样条曲线的数学表达式样条曲线的数学表达式为： 在上式中，0 t 1；i= 0, 1, 2, , m,所以可以看出：样条曲线样条曲线 是分段定义的是分段定义的。如果给定 m+n+1 个顶点 Pi ( i=0, 1, 2, m+n)， 则可定义 m+1 段 n次的参数曲线。 在以上表达式中：F k,n ( t ) 为 n 次B样条基函数，也称样条分段混合函数。其表达式为：式中： 0 t 1 k = 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)+B1 P(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(0 t 1)可见，由 n 个顶点定义的完整的三次样条曲线是由 n-3 段分段曲线连接而成的。很容易证明，三次样条曲线在连接处达到二阶连续。 *样条曲线是一种非常灵活的曲线，曲线的局部形状受相应顶点的控制很直观。这些顶点控制技术如果运用得好，可以使整个样条曲线在某些部位满足一些特殊的技术要求。如： 可以在曲线中构造一段直线； 使曲线与特征多边形相切； 使曲线通过指定点； 指定曲线的端点； 指定曲线端点的约束条件。三、三、B B样条曲面样条曲面在数学上，可以很容易将参数曲线段拓张为参数曲面片。因为无论是前面的 Bezier 曲线还是样条曲线,它们 都是由特征多边形控制的。而曲面是 由两个方向（比如 u 和 v）的特征多 边形来决定，这两个方向的特征多边 形构成特征网格。双二次Bezier曲面和样条曲面.Bezier .Bezier 曲面曲面给定了(m+1)(n+1)个空间点列 bi,j (i=0,1,2,n; j=0,1,2,m)后， 可以定义mn次 Bezier 曲面如下式所 示： 式中：(0 u,v 1);Bi,n(u) 为 n 次Bernstein 基函数；连接点列 bi,j 中相邻两点组成特征网格。 在实际应用中，次数 m 和 n 均不宜超过 5，否则网格对于曲面的控制力将会减弱，这同 Bezier曲线的情况是相似的。其中最重要的应用是 m=n =3，即双三次 Bezier曲面。双三次 Bezier曲面的表达式为：式中：. .样条曲面样条曲面从样条曲线到样条曲面的拓展完全类似于从Bezier曲线到Bezier曲面的拓展。给定了(m+1)(n+1)个空间点列 bi,j (i=0,1,2,n; j=0,1,2,m)后，可 以定义mn次 B样条曲面片如下式所示：同样，式中的 Fi,n(u)称为n次样条基函数族，连结 bi,j组成的空间网格称为特征网格。在实际应用中，最为重要的一种曲面是双三次样条曲面片,此时m=n=3。其表达式为：式中：其余的U、V和b同Bezier曲面。表达式中的矩阵展开，其实就可以得到如类似于在曲线中的混合函数。如展开UN可得：上面介绍的 Bezier曲面与此相同。整个样条曲面是由样条曲面片连接而成的（这正如样条曲线），并且在连接处达到了连续，这一点是由三次样条基函数族 Fi,j(u) 的连续性保证的。所以，双三次样条曲面的突出特点就在于相当轻松地解决了曲面片之间的连接问题。*