《科学计算可视化》ppt课件

1、科学计算可视化科学计算可视化 - 第八讲第八讲中国地质大学信息工程学院严红平体元投射法十 数据构造及初始化：建立便于判别相互遮挡关系的凸多面体网格单元的数据构造，并予以初始化，生成一个以单元为结点的有向无环图； 对该有向无环图进展拓扑排序。- 单元数据构造：记录节点，面，单元及其邻接关系，以及入度的信息；- 面的数据构造：记录该面两侧单元的序号及该面片相对于左右两侧单元的可见值。假设该面为边境面，那么其一侧的单元不存在。体元投射法十一 在给定视点后，每输入一个单元，首先将单元序号，类型及单元各面所在的平面系数初始化； 计算单元内点O的坐标，以及单元各面片相对于点O的可见值；假设某面片为该单元与

2、相邻单元所共有的面，那么计算该面片相对于这两个相邻单元的可见值，并确定遮挡关系，给被遮挡单元的入度值加1； 反复上述过程，直至多面体网格的一切单元均输入终了。 将整个多面体网格用一个有向无环图来表示。每个单元对应于图中的一个节点，相邻单元的遮挡关系对应于图中的一条弧，每个单元的入度就是指向它的弧的数目，也就是该单元内具有负可见值的内部面的个数。体元投射法十二123456789体元投射法十三 从有向无环图中任选一个入度为0的节点，作为序列的第一个单元加以输出，同时从有向无环图中删除该节点，并相应地修正与被删节点有关的信息，即删去相邻节点中由被删节点射入的弧，也就是将相邻单元的入度减1。 从更新后

3、的有向无环图中选取第二个入度为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体元投射法十四何为非凸多面体网格？假设三维空间多面体网格的外部边境是非凸的，即存在凹穴或空洞，那么该多面体网格称为非凸多面体网格。体元投射法十五 建立多面体网格的数据构造，注明一切包含边境面的单元；- 从恣意一个包含边境面的单元出发，根据单元之间的邻接关系进展搜索。假设能将全部边境面的单元都衔接起来，那么该多面体网

4、格仅有外部边境，而无空洞；否那么，该多面体网格存在空洞； 在没有内部空洞时，经过判别外部边境中一切两两相邻的外部面在其交线处的二面角来判别多面体网格能否为凸的。当二面角大于或等于180度时，该多面体网格为凸多面体网格；否那么，为非凸网格，即存在凹穴。 判别网格的内部空洞能否为凸：在构成内部空洞的边境面中，假设一切两两相邻的边境面在其交线处的二面角均小于180度，那么该空洞为凸的，否那么，非凸。 体元投射法十六- 采用适用于凸网格的深度排序与比较视点到单元中心间隔相结合的方法；- 将三维空间非凸多面体网格进展代约束的三维Delaunay三角剖分，将其剖分为符合Delaunay准那么的四面体网格，

5、而且包含了原有的边境面片。然后采用适用于凸网格的深度排序法。- 采用四面体填补法将非凸多面体网格转化为凸多面体网格，即将三维空间非凸多面体网格中的凹穴或空洞用四面体填补，使其变为凸多面体。然后采用适用于凸网格的深度排序法。 相当复杂；破坏了原有的几何邻接关系。 不适用于具有特殊外部边境的网格的深度排序；体元投射法十七虚线为voronoi图；实线为delaunay 三角形Voronoi图与Delaunay三角形四面体填补法输入非凸网格的单元，节点信息分解体元为四面体，建立四面体单元之间的邻接关系判别网格有无空洞扫描纪录外部边境面的数据构造确认要填补的四面体不与任何外部面相交衔接相应的点对，生成新

6、的四面体，并修正其它数据构造根据槽连线的长度及二面角大小处置新生成的凹槽，直至相邻外部面间均无凹槽开场终了有无凸空洞非将该凸空洞剖分为四面体是输入网格的单元，节点信息分解体元为四面体，建立四面体单元之间的邻接关系判别网格的凹凸性凸网格深度排序物质分类，颜色，及不透明度值光强度计算及合成帧缓存图像开场终了转换为凸网格非凸凸体元投射法十八取深度序列中第一个四面体在四面体内构造等值面等值面排序等值面按顺序投影到显示屏幕投影区域内各像素的光强度计算深度序列中还有四面体吗？该四面体是填补的？取下一个四面体是否否是体元投射法十九体元投射法与光线投射法相结合当一个体元的各面投影到图像平面后，与各个像素点相关

7、的一切途径间隔，都可按由小到大的顺序陈列，一次成对的途径间隔之间位于体元的内部。体元投射法与光线投射法相结合 从不规那么数据场中任取一个体元，将它的各个面投影到图像平面上。为投影域内的每个像素建立像素链；- 图像平面上的每个像素都会被该体元的偶数个面片的投影所覆盖。凸体元投影域内每个像素被两个平面片的投影所覆盖；凹体元投影域内每个像素被两个以上偶数个面片的投影所覆盖。 从不规那么数据场中再取下一个体元，进展同样操作。假设某一像素已有链节点，那么将新旧两个链进展合并操作，并按前后顺序对每一个节点进展颜色和不透明度的累积计算。 反复执行以上操作，直至处置完一切体元。体元投射法与光线投射法相结合该算

8、法将体元投射法与光线投射法相结合，经过对每个像素建立链表，将体元排序问题化解成链节点的合成或插入运算，并且不对凹体元进展特别处置。采用体元绘制顺序的优化安排，利用多边形扫描填充算法快速求取途径间隔以及建立长度与颜色积累和透明度积累的对应等措施，可以进一步加快该算法的运算速度。该算法优化后较普通光线投射算法快47倍。构造三维不规那么数据场中的等值面 由差分方程计算网格中每个节点处的梯度值； 采用与Marching Cubes类似的方法，找出与等值面相交的单元，并用线性插值法计算出单元的边与等值面的交点的位置及该点处的梯度； 采用双三次Hermite插值方法来构造单元内的等值面片，以保证各单元内的

9、等值面片在顶点处的法向量是延续的； 根据每个顶点出的法向量梯度，利用双三次Hermite插值方法求出邻接边上各处的法向量，以保证各等值面片的邻接边上的法向量延续。mnmnmimnmnminiFXXXgj1单元内等值面的几何表示由单元边与等值面的交点及交点处的法线构造双三次Hermite曲面片： ThhwBFuFwuQ, hhUMuF hhWMwF123uuuU 00000111001001110111001000100IIIIIIppppppppppppBuuuuwwww123wwwW 位置矢量角点处w方向切线矢量角点处u方向切线矢量u,v 的Hermite调和函数Hermite几何矩阵在单元

10、内部与交面重合abaaabaanPPPPPPS等值面边境法向的延续性等值面法向量双三次Hermite表示中的Hermite几何矩阵：00000111001001110111001000100IIIIIIppppppppppppBuuuuwwww角点法矢量角点处法向量沿w方向的一阶导角点处法向量沿u方向的一阶导II, III的求取请参见Gall89.散乱数据的可视化一散乱数据是在二维平面上或三维空间中无规那么的、随机分布的数据。- 按其复杂程度：单自变量、双自变量及多自变量。- 物理量的丈量数据；- 科学实验所得数据；- 科学计算或工程计算的结果数据；- 按数据规模：小、中、大规模散乱数据。散乱

11、数据的可视化是对散乱数据进展插值或拟合，构成曲线或曲面并用图形或图像表示出来的技术。散乱数据的可视化二- 地质勘探数据的显示；- 测井数据的显示；- 油藏数据的显示；- 气候数据的显示；- 有限元计算结果中非构造化数据的显示；散乱数据的可视化三插值是首先假定给定采样数据是正确的，然后确定某个函数，使其经过各采样数据点，并利用该函数确定相邻两个采样值之间的数值时采用的运算过程。设在二维平面上有n个点(xi, yi) (i=1,n)，且 Zi=F(xi, yi)。此时，插值问题就是要构造一个具有C1延续的函数F(x, y)，使其在点(xi, yi) (i=1,n)的函数值为Zi，即Zi=F(xi,

12、 yi) 。拟合是经过对知数据的分析，设法找出某条光滑曲线，使其最正确地接近知数据，但不用经过一切数据点。散乱数据的插值与拟合一散乱数据的插值与拟合二- 采样数据假定是正确的；- 由采样数据确定插值函数；- 插值函数需准确经过采样点；- 采样数据不一定是正确的；- 由采样数据确定拟合函数；- 拟合函数不用经过一切采样点；散乱数据的插值与拟合三- 分段线性插值；- 三次样条插值；- Lagrange插值；- 线性最小二乘拟合 ；- 多项式的最小二乘曲线拟合 ；- Bzier 曲线, B-Spline ；B B样条曲线和曲面样条曲线和曲面在我们工程中运用的拟合曲线，普通地说可以分为两类：一种是最终

13、生成的曲线经过一切的给定型值点，比如抛物样条曲线和三次参数样条曲线等，这样的曲线适用于插值放样；另一种曲线是，它的最终结果并不一定经过给定的型值点，而只是比较好地接近这些点，这类曲线或曲面比较适宜于外形设计。由于在外形设计中(比如汽车、船舶)，初始给出的数据点往往并不准确；并且有的地方在外观上思索是主要的,由于不是功能的要求，所以为了美观而宁可放弃个别数据点。因此不须最终生成的曲线都经过这些数据点。另一方面，思索到在进展外形设计时应易于实时部分修正，反映直观，以便于设计者交互操作。第一类曲线在这方面就不能顺应。法国的 Bezier 为此提出了一种新的参数曲线表示方法，因此称为Bezier曲线。

14、后来又经过 Gordon、Forrest和 Riesenfeld等人的拓广、开展， 提出了样条曲线。 这两种曲线都因能较好地适用于 外形设计的特殊要求而获得了广泛的 运用。一、一、Bezier曲线曲线Bezier曲线的外形是经过一组多边折曲线的外形是经过一组多边折线特征多边形的各顶点独一地定线特征多边形的各顶点独一地定义出来的。在这组顶点中：义出来的。在这组顶点中：(1) 只需第一个顶点和最后一个顶点只需第一个顶点和最后一个顶点在曲线上；在曲线上；(2) 其他的顶点那么用于定义曲线的导其他的顶点那么用于定义曲线的导数、阶次和外形；数、阶次和外形；(3) 第一条边和最后一条边那么表示了第一条边和

15、最后一条边那么表示了曲线在两端点处的切线方向。曲线在两端点处的切线方向。P0P0P2P1P1P2P3P3P1P0P3P2.Bezier曲线的数学表达式曲线的数学表达式 Bezier曲线是由多项式混合函数推导曲线是由多项式混合函数推导出来的，通常出来的，通常 n+1 个顶点定义一个个顶点定义一个 n次多项式。其数学表达式为：次多项式。其数学表达式为： (0 t 1)式中：式中：i：为各顶点的位置向量：为各顶点的位置向量i,n(t)：为伯恩斯坦基函数：为伯恩斯坦基函数niniitBPtP0,)()(伯恩斯坦基函数的表达式为：假设规定：，！，那么 t=0: i=0 ,Bi,n(t)=1 i0 ,Bi

16、,n(t)=0 P(0)=P0000)01 (0!1!)0(PPnnPnininittinintB)1()!(!)(,t=1:i=n ,Bi,n(t)=1 in ,Bi,n(t)=0P(1)=Pn 所以说，“只需第一个顶点和最后一个 顶点在曲线上。即Bezier曲线只经过多边折线的起点和终点。nnnPPnnP0) 11 (11!) 1 (下面我们经过对基函数求导，来分析两端切矢的情况。得： )()()(1,1, 1,tBtBntBninini101,1,1)()()(nininiitBtBPntP讨论：t=0: i=0: Bi-1,n-1(t)=0； Bi,n-1(t)=1. i=1: Bi-

17、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 次幂ininiininittinintBttinintB11,111,1)1()!1(!)!1()()1()!()!1()!1()( t=0同理可得，当 t=1 时这两个式子阐明：Bezier曲线在两端点处的切矢方向与特征多边形的第一条边和最后一条边相一致。 )()0()0(01PPntPP)()1(1nnPPnP.二次和三次二次和三次Bezier曲线曲线(1) 三个顶点：三个顶点：P0,P1,P2 可定义一条可定义一条二次二次(n=2) Bezier曲线：

18、曲线：其相应的混合函数为：其相应的混合函数为： 22222,21212,120202,0)1(!0!2!2)()1(2)1(! 1! 1!2)()1()1(!2!0!2)(ttttBtttttBttttB所以，根据式：二次 Bezier 曲线的表达方式为：P(t)=(1-t)2P0+2t(1-t)P1+t 2 P2t 1)niniitBPtP0,)()(根据 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

19、)=2(P1-P0)P(1)=2(P2-P1)P(1/2)=P2-P0P0PmP2P(1/2)P(1/2)P1二次 Bezier 曲线是一条抛物线(2)四个顶点四个顶点 P0、P1、P2、P3 可可定义一条三次定义一条三次 Bezier 曲线：曲线：*3210233322120300010033036313311)1 (3)1 (3)1 ()(PPPPtttPtPttPttPttP二、二、B样条曲线样条曲线.从从 Bezier 曲线到样条曲线曲线到样条曲线(1) Bezier 曲线在运用中的缺乏：曲线在运用中的缺乏： 缺乏灵敏性一旦确定了特征多缺乏灵敏性一旦确定了特征多边形的顶点数边形的顶点数

20、(m个个)，也就决议了曲，也就决议了曲线的阶次线的阶次(m-1次次)，无法更改；，无法更改； 控制性差当顶点数较多时，曲控制性差当顶点数较多时，曲线的阶次将较高，此时，特征多边形线的阶次将较高，此时，特征多边形对曲线外形的控制将明显减弱；对曲线外形的控制将明显减弱； 不易修正由曲线的混合函数可看出， 其值在开区间 ( 0 , 1 ) 内均不为零。 因此所定义之曲线在 ( 0 t 1)的 区间内的任何一点均要遭到全部顶点的影响，这使得对曲线进展部分修改成为不能够。而在外形设计中，部分修正是随时要进展的为了抑制 Bezier 曲线存在的问题，Gordon 等人拓展了 Bezier曲线，就外形设计的

21、需求出发，希望新的曲线要： 易于进展部分修正； 更逼近特征多边形； 是低阶次曲线。于是，用 n次样条基函数交换了伯恩斯坦基函数，构造了称之为样条曲线的新型曲线。2.样条曲线的数学表达式样条曲线的数学表达式样条曲线的数学表达式为：样条曲线的数学表达式为： 在上式中，在上式中，0 t 1；i= 0, 1, 2, , m,所以可以看出：样条曲线所以可以看出：样条曲线 是分段定义的。假设给定是分段定义的。假设给定 m+n+1 个顶点个顶点 Pi ( i=0, 1, 2, m+n)， 那么可定义那么可定义 m+1 段段 n次的参数曲线。次的参数曲线。 nknkkinitFPtP0,)()(在以上表达式中

22、：F k,n ( t ) 为 n 次B样条基函数，也称样条分段混合函数。其表达式为：式中： 0 t 1 k = 0, 1, 2, , n knjnjnjnkjkntCntF01,)()1(!1)(衔接全部曲线段所组成的整条曲线称为 n 次样条曲线。依次用线段衔接点 Pi+k (k=0,1,n)所组成的多边折线称为样条曲线在第i段的特征多边形。 .二次样条曲线二次样条曲线在二次样条曲线中，在二次样条曲线中，n=2,k=0,1,2故其基函数方式为：故其基函数方式为：22,222,1222220232,021)()122(21)()1(21!2!3)1(!2!3)2(!3!321)2()1(!21)

23、(ttFtttFttttjtCtFjjj 有了基函数，因此可写出二次样条曲线的分段表达式为：( i= 0,1,2,m )m+1段22, 212, 12, 0)()()()(iiiiPtFPtFPtFtP写成普通的矩阵方式为：写成普通的矩阵方式为：式中，式中，k为分段曲线的特征多边形为分段曲线的特征多边形的顶点：的顶点：B0,B1,B2。对于第。对于第i段曲线的段曲线的Bk 即为：即为：Pi,Pi+1,Pi+2 延续的三个顶延续的三个顶点。见以下图点。见以下图2021022,011022121211)()(kkkBBBttBtFtPP3B:P0P0,P1,P2P2P1P1,P2,P3B:P4n=

24、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)2100111211)(BBBttP与以上这些式子所表达的性质相符的曲线是何种外形：见以下图B0P(0)P(1

25、)MB2P(1/2)B1P(1/2)是什么曲线？与Bezier曲线有何差别？结论：分段二次B样条曲线是一条抛物线；有n个顶点定义的二次B样条曲线，其本质上是n-2段抛物线相邻三点定义的衔接，并在接点处到达一阶延续。见以下图P3P0P2P1P4.三次样条曲线三次样条曲线分段三次样条曲线由相邻四个顶点分段三次样条曲线由相邻四个顶点定义，其表达式为：定义，其表达式为：P( t )=F0,3(t)B0+F1,3(t)B1+F2,3(t)B2+F3,3(t)B3(0 t 1)可见，由可见，由 n 个顶点定义的完好的三次个顶点定义的完好的三次样条曲线是由样条曲线是由 n-3 段分段曲线衔接段分段曲线衔接而

26、成的。很容易证明，三次样条曲而成的。很容易证明，三次样条曲线在衔接处到达二阶延续。线在衔接处到达二阶延续。 *样条曲线是一种非常灵敏的曲线，曲线的部分外形受相应顶点的控制很直观。这些顶点控制技术假设运用得好，可以使整个样条曲线在某些部位满足一些特殊的技术要求。如： 可以在曲线中构造一段直线； 使曲线与特征多边形相切； 使曲线经过指定点； 指定曲线的端点； 指定曲线端点的约束条件。三、三、B样条曲面样条曲面在数学上，可以很容易将参数曲线段在数学上，可以很容易将参数曲线段拓张为参数曲面片。由于无论是前面拓张为参数曲面片。由于无论是前面的的 Bezier 曲线还是样条曲线曲线还是样条曲线,它们它们

27、都是由特征多边形控制的。而曲面是都是由特征多边形控制的。而曲面是 由两个方向比如由两个方向比如 u 和和 v的特征多的特征多 边形来决议，这两个方向的特征多边边形来决议，这两个方向的特征多边 形构成特征网格。形构成特征网格。22P01Pv00P10uPP20P02P11P12PvP01PP0020uP10P0221P12P11P21P22双二次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)