2009任意三维物体FDTD共形网格生成算法

1、任意三21物体FDTD共形网格生成算法牛朴,侯新宇（西北工业大学电子信息学院,陕西西安710072摘要:时域有限差分法（FDTD是计算电磁学广泛使用的方法之一。作为一种数值方法，首先要对目标模型进行网格离散。它直接影响到计算的精确性与复杂性。为了避免采用Yee氏单元对复杂模型建模所产生的阶梯误差，实现了一种任意复杂形状三维物体FDTD共形网格自动生成算法。对于由AutoCAD等建模软件生成的目标模型（三角形和四边形构成，应用计算机图形学方法求出网格线与模型的交点，在三个网格面分别生成共形网格。 数值结果证实了共形网格生成方法的正确性和在提高FDTD方法计算精度方面的有效性。关键词：共形时域有限

2、差分法；网格生成；计算电磁中图分类号:TN011文献标识码：BAConformalFDTDGridGenerationAlgorithmforArbitraryThree-DimensionalGeometricObjectNIUPu,HOUXin-yu（SchoolofElectronicandInformation,NorthwesternPolytechnicalUniversity,XianShanxi710072,ChinaABSTRACT:TheFinite-DifferentTime-Domain（ FDTDmethodisapopularmethodincomputationa

3、lelectromagnetics.Asanumericalmethod,itfirstlyshouldmeshtheobjectmode,lwhichhasinfluenceontheaccuracyandcomplexityofcomputation.Thispaperpresentsanautomaticconformalgridgenerationalgorithmforarbitrarythree-dimensionalobject.TheoriginalobjectmodelcomposedoftriangleorquadrilateraliscreatedbyusingAutoC

4、ADorothercommercialsolidmodelers.Thentheintersectionbetweenthegridlinesandmodelcanbecomputedbasedoncomputer-graphicsmethod.TheconformalFDTDgridwillbegeneratedinthreegridplanesseparately.Thevalidityofthistechniqueis川ustratedbyseveralexamples.KEYWORDS:ConformalFDTD;Gridgeneration;Computationalelectrom

5、agnetics1引言时域有限差分法（FDTD是计算电磁领域中用来解决电磁传播与散射问题所广泛采用的数值方法之一1。它模拟电磁波的传播过程，具有通用性，直接性的特点。在解决电磁传播与散射问题中，首先要对复杂几何形体进行网格划分。而网格划分的程度，直接影响到计算的复杂度与计算结果的精确性。网格划分一般采用Yee氏单元。它具有在迪卡尔坐标系下容易剖分的特性，但另一方面对于曲面及不与坐标轴重合的平面结构，模型会产生阶梯近似，因此会引起计算误差，限制了FDTD方法的应用。虽然采用更精细的网格划分会减小这种误差，但同时增大了计形FDTD技术2-4导体曲面，介质曲面以及薄涂层问题等方面都取得了显著效果。本

6、文提出了一种基于三角面元数据三维物体共形网格自动生成算法。本算法主要针对的是三维闭合物体，且对平面结构同样适用。任意三维目标可由建模软件，如AutoCAD,UG等商业软件进行绘制，然后模型表示为由三角形或四边形组成的面片,一般建模软件都带有此功能。 基于面片模型及Yee氏单元,应用本方法就可以计算出共形网格信息。 它只需要求出物体表面与坐标网格线的交点以区分物体的边界,在物体内部和外部仍然是剖分为Yee氏单元，而在边界处为共形单元。下面将会详细介绍共形网格生成技术，并通过实例验证了本文共形网格生成方法的正确性。是减小这一误差的有效途径之一，虽然需要相对复杂的共形网格信息描述，但克服了Yee氏单

7、元所带来的缺点，在处理2共形FDTD方法收稿日期：2008-05-19修回日期:2008-06-15采用常规的Yee氏单元进行计算，除非采用精细的网格划分，否则由于阶梯近似，将会引入误差。而共形FDTD方法消除了这一误差，并增加了模拟曲面边界的精确性。图1是二维FDTD共形网格结构。区域I是理想导体，区域II是导体外区域，阴影部分是变形网格。对于非变形网格，电场和磁场的更新方程不变。而对于变形网格，电场的递推公式不变，磁场更新方程需要特殊处理由于处于理想导体内的电场为零，因此仅需考虑变形网格中导体外的电场贡献。例如，分量的方程为：Hn+1/2y图2是一个球体的三角面片模型。3.2算法设定FDT

8、D计算域为一个长方体空间，沿着FDTD域边界定义全局坐标系，其xy截面如图3所示。为了加速网格生成，计算域中的FDTD网格通过在每一个扫描方向上定义一个单元列来实现,而不是逐个单元的生成5。但文献5中图2球体的三角面片模型(i,j,k=Hn-1/2yt(i,j,k+!y(i,j,kz(i,j,kEnz(i,j,k-z(i-1,j,kEn,j,kz(i-10(i!z0(kx(i,j,k-1En,j,k-1-x(i,j,kEn,j,kx(iz(i0(i!z0(k(1图3FDTD计算域xy截面生成的是非共形网格，即阶梯近似且是单方向扫描，不能准确反映其它两个方向的几何信息。所以我们采用x,y,z三个

9、图1二维FDTD共形网格结构方向同时扫描，直接生成网格面，而不是立方体单元，这不仅使变形网格精确的描述了目标模型的几何信息，而且这与共形FDTD计算网格吻合。如图4所示，变形单元的FDTD计算等同于在单元的8个变形网格面上分别计算。(2因此，只需在xy,yz,xz面生成网格面。首先确定坐标网格线的交点是位于模型内部还是外部，如图3中，区分实网格线交点和虚网格线交点，采用计算机图形学中的射线交叉算法和数算法来实现。当区域I和区域II是两种不同的介质时，变形网格处可采用有效介质参数来减小误差：effx=x1+x22上述两种情况都需要共形网格信息，即物体表面与坐标网格线的交点，应用本文所提出的方法就

10、可以产生所需网格信息。3共形网格生成算法3.1目标模型描述当采用AutoCAD,UG等CAD软件建立模型后，模型几何信息的存储形式有很多种，如IGES,DXF,STEP等，为了有效的使用CAD模型文件及算法实现的考虑,假定FDTD计算域中的所有物体模型都表示为面片（三角形或四边形组成的闭合体,大部分建模软件都带有此功能。模型信息存储Ax格式如表1所小。表1模型信息存储格式面片编号1N节点编号1n10 x11n1节点编号2n2节点坐标x,y,z0y10z1图4变形网格单元3. 2.1射线交叉算法为了网格线的交点是否位于模型内部，必须确定扫描射线与模型面片的交点。射线交叉算法可以确定这些交点。首先

11、，需要确定射线是否与三角面（或四边形所在的平面相交,这可以通过（3式来确定。3n3!=n?tn?l（3其中n是测试面的单位法向矢量,t是从射线一端点到测试面任意一个定点的矢量， l是从射线一端到另一端的矢量，如图5所示。如果！的值介于0和1之间，那么射线与该平面相交。图6二维绕数算法示意图网格线法。当网格线不足够密时，这种方法产生的模型轮廓图5射线交叉算法示意图会忽略掉一部分几何信息。如图7所示，文献6中采用单方向扫描，因此y方向和z方向的模型细节不易捕捉，本文采用x,y,z三方向扫描，弥补了不足，且计算量没有明显增加。(4对于薄片结构，虚拟网格线法需要进行修改才能应用，而本文算法可以直接应用

12、(b)(b)实统为录用虚招网格域法 4 4 修为本文方法具有一定的通用性。如果射线与与该平面相交那么交点P的坐标为:Px=l1x+!?lxPy=l1y+!?lyPz=l1z+!?lz如图5所示，Px,Py,Pz,l1x,l1y,l1z分别是交点P和射线第一个端点l1的x,y,z坐标。lx,ly,lz是l的x,y,z分量。本算法只能确定射线是否与三角面所在的测试面相交，交点有两种可能，即在三角形内，如P点，三角形外，如P#点。为了区分这两种情况，需要计算交点的绕数。3.2.2绕数算法绕数算法可以应用在二维，或三维问题中。对于三维问题，它可以用来确定一个点是否在多面体内部。二维情况下，通过计算绕数

13、可以检验一个点是否在多边形内。因此，采用二维绕数计算交点是否在三角形内。图6为绕数计算示意图。图中虚线为测试点到多边形顶点的连线，每两根虚线所形成的夹角为？i，假定有n个夹角，n为多边形的顶点书，则绕数M为所有角度的和，即：M=?ni=1?ii=1,2,%,n(5图7本文算法与虚拟网格线法cos(?i=Vi?Vj4实例验证(64. 1几何模型验证本节给出几个图形实例，验证本文方法的有效性。采用OpenGL图形库，开发了共形网格显示程序。使用不同的颜色表示不同的网格面，分别使用红，I录，蓝表示xy,yz,xz面。图8为球体的三维剖分图形。为了进一步显示本技术的性能，图9给出了一个较复杂的人头像的

14、三角面片模型，图10是其剖分后的模型。4.2FDTD数值验证采用本文FDTD共形网格生成方法，给出了计算实例来图8球体共形网格ViVj其中Vi是测试点到多边形顶点的矢量。如果M=2#,则测试点在多边形内,否则在多边形外。 当测试点处于多边形的边上， 顶点上，或附近时（5式不能准确判断测试点是否在多边形内，因此需要额外的检验：当cos（?i1-2!10-4时，可以认为测试点在多边形的边上。当时ds2!10-4,认为测试点在多边形的顶点上，ds是测试点到多边形顶点的距离。通过射线交叉算法和绕数算法，把网格线的交点分为两类，一类在目标模型内，一类在目标模型外。同时射线交叉算法也得到了网格线与模型的交

15、点（通常为非网格线交点，即得到了模型的轮廓，以便产生变形网格面（图1中的阴影区域。文献6中给出了一种确定模型轮廓的方法，即虚拟验证共行网格信息是否能满足共形FDTD计算的需要，实现降低计算复杂性和提高计算精度的目的。算例是计算一个完全导体球的后向雷达散射截面积。球体半径为0.36m,其三角面片模型和共形网格模型分别如图2和图8所示。 面片模型由500三角面元和252个顶点构成。 空间离散网格为x=y=z=0.018m,时间间隔t=3!10-11S。图11是导体球的后向散射随频率的变化。从图中可以看出，频率低于0.4GHz时，FDTD和CFDTD都与Mie级数解吻合的很好；但是随着频率的升高，F

16、DTD的误差升高，而CFDTD的误差明显小于FDTD的误差，因此对于相同数量级别的网格单元，CFDTD的计算精度要优于FDTD的精度，同时验证了本文共形网格剖分方法的正确性与有效性。图10人头像共形网格图9人头像三角面模型5结论本文提出了一种任意复杂形状三维物体共形网格自动算机图形学中的射线交叉算法和绕数算法实现网格线与物体面拟网格线法相比，能够比较全面的反映出模型的细节特征，对于薄片结构可以直接应用，具有一定的通用性。参考文献：1 KSYee.NumericalsolutionofinitialboundaryvalueproblemsinvolvingMaxwellsequationsin

17、isotropicmediaJ.IEEEAntennasandPropagation,1966,14(3:302-307.2 SupriyoDey,RajMittra.ALocallyConformalFinite-DifferenceTime-DomainAlgorithmforModelingThree-dimensionalPerfectlyConductingObjectsJ.IEEEMicrowaveandGuidedWaveLetters,1997,9(7:273-275.3 SDey,RMittra.Amodifiedlocallyconformalfinite-differen

18、cetime-domainalgorithmformodelingthree-dimensionalperfectlyconductingobjectsJ.MicrowaveandOpticalTechnologyLetters,1998,17(6:349-352.4 YuWenhua,RajMittra.AConformalFiniteDifferenceTimeDomainTechniqueforModelingCurvedDielectricSurfacesJ.IEEEMicrowaveandWirelessComponentsLetters,2001,1(11:25-27.5 YSrisukh,JNehrbass,FLTeixeira,JFLee,RLee.AnApproachforAutomaticGridGenerationinThree-DimensionalFDTDSimulationsofComplexGeometriesJ.tennasPropagat,2002,4(44:75-80.6 TaoSu,YongjunLiu,We