点云重建三角网格
1.三角网格重建的研究现状
曲面重建技术在逆向工程[57]、数据可视化[58]、机器视觉[59]、虚拟现实[60]、医疗技术[61]等领域中得到了广泛的应用。网格重建作为曲面重建的重要前处理一直是研究的热点。近十几年来，国内外学者提出了许多网格重建的算法。根据重建过程中采用的具体方法可以将网格重建算法分为基于Delaunay重建法、区域扩张重建法、基于隐式曲面重建法和基于统计学重建法。
基于Delaunay重建方法，具有很强的数学基础，一般能精确地重建物体表面，但计算量比较大，对带有噪声的物体和尖锐特征的物体，采用该方法重建并不能取得比较理想的结果。Boissonnat[62]通过采用三维Delaunay三角剖分得到数据点的凸包，然后逐步剥离冗余四面体，使所有数据点可见，最终重建出物体的网格模型。在采样点足够稠密的情况下，该方法能重建出与物体拓扑一致的网格模型，但当采样点不均匀以及存在噪声数据时，不能构造出与物体拓扑等价的网格模型，同时计算复杂，内存消耗比较多。Edelsbrunner[63]提出一种α-shape方法，该方法通过删除四面体凸包中包围球或者外半径大于α的四面体、三角面片和边重建测量数据的网格模型，但α-shape不是流形结构，必须经过后续处理才能得到正确的二维流形网格[64]，同时该方法对采样不均匀的点云难以选择合适的α值重建出正确的网格模型。Amenta[65][66][67]对扫描数据进行V oronoi图分解，然后通过Delaunay三角化方法重建网格模型。该方法能精确地通过扫描数据点，但对噪声模型和具有尖锐特征的模型不能取得理想的效果。Floater[68]将数据点投影到平面，在平面采用Denaulay三角化方法，生成平面网格，并将拓扑关系映射回空间数据点，从而达到网格重建的目的，该方法简单高效，但只适用于单值曲面。属于该类的方法还有Crust方法[69]和Cocone方法[70]。
基于隐式表面重建方法，可以有效处理噪声数据，但不能有效地处理具有尖锐特征的模型，一般只用于计算机视觉和虚拟现实中。Hoppe[71]首先给出了一个刻画点集密度的方法，引入了ρ密度样本的定义，通过计算点的法矢，得到数据点局部处的切平面，用切平面线性逼近待重建网格的局部形状，从而建立距离场函数，通过提取等值曲面得到三角网格。该方法通常涉及复杂的法矢一致性调整，不能较好地重建细节特征。周儒荣[72]对Hoppe的方法进行了改进，提出以切平面中心代替数据点，改善网格质量，较好地处理了法矢传播中的孤岛问题。Curless[73]提出了以扫描图像作为加权距离场函数，通过合并多幅图像的方法进行网格重建，能处理上百万的数据。Car[74]等提出通过径向基函数进行网格重建，他们以径向基作为基函数，建立插值函数，通过求解线性方程组，达到网格重建的目的，但由于约束点比较多，方程为全局方程，需要消耗较多的内存和计算时间。Ohtake[76]、朱心雄[77]提出一种MPU ( Multilevel Partition of Unity)方法，该方法克服了一般隐式表面重建法不能还原尖锐特征的缺点。Kazhdan[78]通过泊松等式△f= div(n)建立隐式曲面，然后提取等值面，从而达到网格重建的目的。属于这类的方法还有[71][73][74][75][77][78]。水平集的方法，最早是由Osher 和Sethian[79][80]于1988 年提出的，它的基本思想是将曲线或者曲面看成是某一更高维函数的零水平集，利用函数的演化与Hamilton-Jacobi方程的相似性，将曲线或者曲面的演化过程转化为函数的演化过程. Whitaker[81]、Zhao[82]、Sethian[83]、Osher[84]、Zhao[85]等人也提出将水平集方法应用到曲面重构中，并取得了较好的结果.变形表面方法与之类似，从初始表面开始，在能量函数的驱动下可以逼近真实表面。
区域扩张法，一般都是从一个初始种子出发，不断向周边扩张直到所有数据点都被处理，其中初始种子可以是一个三角面片或者一条边。Bernardinit在α-shape理论基础上提出了BPA算法，通过使用一个给定半径或者使用不同半径的球绕着活动边转动，直到找到另外一点，生成新的三角面片。该算法需要点的法矢信息，而且不容易取到合适的半径。
Crossno[86]提出螺旋边准则，根据边界边最小内切圆准则寻找一个新的顶点并构建新三角
形，逐步覆盖整个数据集，该方法能高效地处理均匀数据点。Huang[64]将K 个临近点投影到活动边所在三角面片的平面上，剔除不可见的点，然后利用最小长度准则在剩余点中选择一点构造新的三角面片。Lin[87]提出IPD 算法，该算法定义了采样点均匀度，利用该均匀度建立活动边的影响区域，从而获得候选点集合，然后根据加权边长和最小准则选择一点构造新的三角面片。属于区域扩张法的还有[86][87]，该类方法思想简单、实现容易、效率高，可以处理复杂拓扑模型的重建，但现有的该类方法尖锐特征重建效果不是很理想。
基于统计学方法，将统计学习和机器学习的方法运用于网格重建。Kohonen[88]提出基
于自我组织学习的网格重建算法，最先将统计学方法引入网格重建中。将反向传播用于网格重建，建立四层BP 神经网格，以网格曲面或者B 样条曲面作为样例训练该神经网络，不断调整神经网络的权值，将数据点与重建曲面转化为非线性问题，通过梯度方向搜索使数据点与重建曲面的方差最小，重建出来的曲面一般精度比较高，但它存在收敛性问题。Ivrissimtzis[89]将神经网络引入网格模型重建，该方法将三角网格作为神经网络，将数据点作为信号，通过信号刺激神经网络，逐步更新网格。Diebel[90]将贝叶斯框架引入了网格重建。另外属于这个范畴的方法还有[91][92][93]。
2. 多种子点和平坦部分优先生长方法的点云到网格重建
点云中的点有四种状态：自由点，候选点，已接受点，和异常点。首先，把散乱点集的
所有点放入方便查找相邻点的哈希表，全标记为自由状态，然后在平坦(水平或者垂直)的区域构造种子三角形，种子三角形的边放入作为前沿边堆栈。然后从前沿边堆栈中弹出一个前沿边，用与BPA 相似的方法以当前前沿边的中心为球心作一个范围球，球内点就是候选点。按四个原则从候选点中选择一个作为邻近点，连接成新三角形，把相应边存入前沿边堆栈，改变邻近点的状态为已接受点。从候选点中选择邻近点的四个原则是：邻近点与当前前沿边构成的角不能太大也不能太小；新三角形与当前三角形构成的角不能太大；新三角形应该与已成的网格不相交；与当前前沿边距离小。其中的三个原则构成一个代价函数，计算每个候选点的代价函数，从中选择最小代价的作为邻近点。如果没有合适的邻近点，则前前沿边搁置，不构造新三角形。从前沿边堆栈中弹出新的当前前沿边，继续生长，直到前沿边堆栈空。网格完成时，可能会还有自由点，此时的自由点被认为是异常点。
当前前沿边的邻近点，不一定是自由点，也可能是已接受的、在前沿边上的点。我们称
已接受的、在前沿边上的点为前沿点。在构造新三角形时，根据邻近点的属性，有四种操作：
(1)加入：如果邻近点是自由的候选点，加入新三角形，推进前沿边；
m n
f
(a) (b) (c) (d) (e)
Fig.1. The flat (horizontal or vertical) portions of the object have a higher priority to be triangulated than the places with sharp curvature change. (a) an flat portions; (b) rightly growing; (c) falsely growing; (c) falsely growing; (d) multi-seeds mesh; (e) the finished mesh.
(2)填充：如果邻近点是已接受
点，并且邻近点与前沿边的两端点
的连接边已存在，那么这里有一个
孔洞，把邻近点和前沿边构造成新
三角形，从前沿边堆栈中删除邻近
点与前沿边的两端点的连接边； (3)连接：如果邻近点是已接受点，但是邻近点与前沿边的某一个
端点的连接边已存在，而与前沿边的另一个端点的连接边不存在，把邻近点和前沿边构造成新三角形，从前沿边堆栈中删除邻近点与前沿边间已存在的连接边，把新三角形的另一边加入前沿边堆栈；
(4)缝接：如果邻近点是已接受点，但是邻近点与当前前沿边的端点间没有已存在的连
接边，把邻近点和当前前沿边构造成新三角形，同时以邻近点和当前前沿边的一端点为前沿边再构造另一新三角形，把两新三角形的二个外侧边加入前沿边堆栈；
三角形都是有方向的，按逆时针方向建构，这
样表面的方向都指向外面。前沿边也始终是封闭的
有向曲线，数目始终在变化。加入操作会新填二个
前沿边，删除一个前沿边；填充操作不会新填前沿
边，但会删除三个前沿边；连接操作会删除一个前
沿边，新填一个前沿边；缝接操作会删除二个前沿
边，新填二个前沿边。如果在填充、连接或者缝接
时发现新三角形的某两条边是前沿边，并且方向不
一致，那么网格在此处发生了纠缠。
Fig.2. Mesh Growing. 1 is the seed triangle, and 2
the finished triangle, 3 a front edge, 4 the current
front edge, 5 the free points, 6 the bounding ball, 7
the close point, 8 the reference point.
(a) (b)
(c)
Fig.3. Topological Operations. (a) a mesh with the current front edge e 1; (b) the mesh growing process; (c) the temporal result mesh after 4 topological operations.
Fig.4. Triangulation.
点云到网格的重建一向有两个困难：自相交和拓朴。但是这两个问题在多种子点和平坦
部分优方法下得到了解决。但是这个方法中也存在以下几个难点：
(1)算法的第一步，寻找平坦部位的种子点，如果需要计算每个三角形的法向才能知道
哪些三角形是平坦的，计算成本高，需要更有效的方法；
(2)从当前前沿边的中心构造范围球时，球的半径如何选择才合适。球的半径太大，会
多产生异常点，甚至得到错误的拓朴连接；但是多数范围球内至少应该有超过一个的候选点。
但是无论如果，范围球的半径与点间的平均距离有关系。如果需要范围球的半径与局部自适
应，那么可以计算出局部点云的平均距离。平均距离由点云的包围盒和点的数目计算而来；
(3)新三角形应该与已成的网格不相交，相交性检测是一个费时的计算。可以在新三角
形上取一个比范围球更大的区域，检测是否有已成的网格，新三角形的三个顶点是否落在每
个网格平面的同一边；
(4)从候选点集中选取邻近点的代价函数，其实是在邻近点与当前三角形的夹角、法向
变化和邻近点与当前边距离这三者考虑何者优先。如果重建对象平坦光滑，那么法向变化应
该小，距离可以取得大一些；相反，法向变化可以取得大，距离应该取得小。各个局部的情
况与此相同。而且在种子生长阶段和最后表面缝合阶段，代价函数也应不同；因此，代价函
数中三个因素间的系数应该是与局部情况相适应的；
(5)既然是平坦部分优先生长，那么当前前沿边应该是前沿边中最平坦的部分。因此前
沿边堆栈也需要按平坦程度排序。
3. 点云到网格的重建
(a) (b) (c) (d)
Fig.5. Reconstruct the head model: (a) Points; (b) Merge local triangular mesh; (c) Mesh optimize; (d) Geometric model after normal consistent.
1.1哈希表的构造方法
一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址即key1≠key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”
作为相应记录在表中的存储位置，这种表被称为哈希表。
注：这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数) 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。现实中哈希函数是需要构造的，并且构造的好才能使用的好。
1.2点平坦度计算方法
锐角三角函数“网格秀” 山东王勇 在网格中计算锐角三角函数值的问题是各地中考题中一道靓丽的风景，现从近两年中 考题中撷取儿例解析如下，供同学们学习时参考. 一、网格中的正弦 例1网格中的每个小正方形的边长都是1, AABC 每个顶点都在网格的交点处，则 sinA= . cl 7 % D / k \ B / A 图1 分析：根据各边长可知AABC 为等腰三角形，分别作出BC, AB 边的高AD 和CE, 根据面积相等求出CE 的长，在RtAAEC 中求出ZCAE 的正弦值即可. 解：如图1,过点A,作AD 丄BC,垂足为D ；过点C,作CE±AB,垂足为E. 由勾股定理得，AC=2 ^5 , AB=2V5 , BC=2 迈,AAB=AC. VAD±BC, ACD=BD=V2 , A AD= 7（2>/5）2 ?（A /2）2 =3^2 . 由三角形的面积相等得，1BC.AD=1AB.C E>则BC . AD=AB ? CE, 6A /5 在RfAEC 中，可得sinZCAE 谎厂盘W 3 故答案填： 点评：解题的关键是准确地把ZCAB 构造在一个直角三角形中，再利用正弦的定义来 求得相应的函数值. 二、网格屮的余弦 例2如图2,已知AABC 的三个顶点均在格点上，则cosA 的值为（ ） V3 V5 2^3 2^5 A ? -- B ? -- C ? ---- D ? ---- 分析：如图2,由勾股定理的逆定理可得AADB 是直角三角形，再利用余弦的定义直 接求岀cosA 的值即可. _____ ___________________ 解：如图 2,在AADB 中，AD=V22 +22 =2^2 , AB=A /12+32 =710, BD=A /2 , ???（忑尸+（2血卍（JIU ）2, ???△ADB 是直角三角形， . AD 2^2 2A /5 ? ? cosA= ---- = —j== --------- ? AB JlO 5 故答案选：D. 点评：在网格屮找出ZA 所在的直角三角形，利用一个锐角的余弦二邻边：斜边计算. 三、网格屮的正切 例3如图3,在网格中，小正方形的边长均为1,点A, B, C 都在格点上，贝0ZABC 的正切值 ???CE= 2@ 3迥 2y/5 6^5 "T"
C B A A B A B C · O 网格与中考 一、网格与线段 1．右图是由16个边长为1的小正方形拼成的，任意连结这些小正方形的若干个顶点，可得到一些线段，试分别画出一条长度是有理数的线段和一条长度是无理数的线段． 二、网格与三角形 2、正方形网格中，小格的顶点叫做格点。小华按下列要求作图：①在正方形网格的三条不同的实线上各取一个格点，使其中任意两点不在同一条实线上；②连结三个格点，使之构成直角三角形。小华在左边的正方形网格中作出了Rt ⊿ABC 。请你按照同样的要求，在右边的两个正方形网格中各画出一个直角三角形，并使三个网格中的直角三角形互不全等。 三、网格与四边形 四、网格与圆 4.如图，方格纸上一圆经过（2 , 5）、（2 , -3）两点，且此两点为圆与方格纸横线的切点，则该圆圆心的坐标为（ ） A ．（2, -1）; B ．（2, 2）; C ．（2, 1）; D ．（3, 1） 五、网格与面积 5、在如图的方格纸中，每个小方格都是边长为1的正方形，点A 、B 是方格纸中的两个格点（即正方形的顶点），在这个5×5的方格纸中，找出格点C 使△ABC 的面积为2个平方单位，则满足条件的格点C 的个数是（ ） A 、5 B 、4 C 、3 D 、2 六、网格与图案设计 6、在下面的网格图中按要求画出图形，并回答问题： ⑴ 先画出△ABC 向下平移5格后的△A 1B 1C 1，再画出△ABC 以点O 为旋转中心，沿顺时针方向旋转90°后的△A 2B 2C 2； ⑵ 在与同学交流时，你打算如何描述⑴中所画的△A 2B 2C 2 的位置？
4号袋 3号袋 1 7、请你在下面3个网格（两相邻格点的距离均为1个单位长度）内，分别设计1个图案，要求:在⑴中所设计的图案是面积等于3的轴对称图形；在⑵中所设计的图案是面积等于23的中心对称图形；在⑶中所设计的图案既是轴对称图形又是中心对称图形，并且面积等于33．将你设计的图案用铅笔涂黑． 七、网格与函数： 8、我们都知道在中国象棋中，马走日，象走田，如图，假设一匹马经过A 、B 两点走到点C 。请问点A 、B 在不在马的起始位置所在的点与点C 所确定的直线上？请说明你的理由。 练习： 1、图3是一个经过改造的台球桌面的示意图， 图中四个角上的阴影部分分别表示四个入球 孔.如果一个球按图中所示的方向被击出（球可以经过多次反射），那么该球最后将落入的球袋是 （ ） A ．1 号袋 B ．2 号袋 C ．3 号袋 D ．4 号袋 2、如图，已知图中每个小 方格的边长为1，则点C 到AB 所在直线的距离等于 。 3、一只蚂蚁在如图所示的图案内任意爬动一段时间后停下，蚂蚁停在阴影内的概率为 。 4、如图:球台上有两个小球P 和Q ，若击打小球P 经过球台的边AB 反弹后，恰好击中小球Q ，则小球P 击出时，应瞄准AB 边上的点（ ） A ．O 1 B.O 2 C.O 3 D.O 4
1 网格中的锐角三角函数 网格是同学们从小就熟悉的图形，在网格中隐含的条件有：1.直角；2.单位长度。所以在网格中可以求一个锐角的三角函数，是近几年中考的热点，下面举例说明。 一、在网格中与勾股定理现结合求一个锐角的三角函数。 【例1】 三角形在正方形网格纸中的位如图1，则sin α的值是( ). [解析] 本题在网格中考查锐角的正弦的意义，首先要用勾股定理计算直角三角形斜边的长．一般情况下，为了减小计算量，把小正方形的边长设为1．选C ． 练习1（广州市2014）如图2，在边长为1的小正方形组成的网格中，的三个顶点均在格点上， 则 （ ）． （A ） （B ） （C ） （D ） 练习2 （2014年福州）如图3，在边长为1个单位长度的小正方形所组成的网格中，△ABC 的顶点均在格点上， 34 45 4 3 B . ； C . 3 5 ；D . A. 35 图 3 图2
2 sinB 的值是 . 3.（2011四川）如图4，在4×4的正方形网格中， tanα= . A ．1 B ．2 C ．1 2 D 4.（2011甘肃兰州）如图5，A 、B 、C 三点在正方形网格线的交点处，若将△ACB 绕着点A 逆时针旋转得到△AC’B’，则tanB’的值为 . A ．12 B ．13 C ．14 D 3. （2011江苏连云港）如图6，△ABC 的顶点都在方格纸的格点上，则sin A =_______. 在网格中求一个锐角的三角函数时，根据图中角的位置。充分利用网格中的直角和边，然后根据勾股定理求出相应的边长，最后利用三角函数公式进行计算，达到解决问题的目的。 二、在网格中与辅助线相结合求一个锐角的三角函数。 【例2】 （2014?贺州）如图7-1网格中的每个小正方形的边长都是1，△ABC 每个顶点都在网格的交点处，则sinA= ． [解析] 虽然网格中隐含直角，但是∠A 是△ABC 中 图7-1 图7-2 图4 图6 图5
最简单的情形，多边形网格不过是一个多边形列表；三角网格就是全部由三角形组成的多边形网格。多边形和三角网格在图形学和建模中广泛使用，用来模拟复杂物体的表面，如建筑、车辆、人体，当然还有茶壶等。图14.1给出一些例子： 当然，任意多边形网格都能转换成三角网格，三角网格以其简单性而吸引人，相对于一般多边形网格，许多操作对三角网格更容易。 表示网格 三角网格为一个三角形列表，所以最直接的表示方法是用三角形数组： Listing 14.1: A trivial representation of a triangle mesh struct Triangle { Vector3 p[3]; }; struct TriangleMesh { int triCount; Triangle *triList; }; 对于某些应用程序，这种表示方法已经足够。然而，术语"网格"隐含的相邻三角形的连通性却未在这种简单表示中有任何体现。实际应用中出现的三角网格，每个三角形都和其他三角形共享边。于是，三角网格需要存储三类信息： （1）顶点。每个三角形都有三个顶点，各顶点都有可能和其他三角形共享。
（2）边。连接两个顶点的边，每个三角形有三条边。 （3）面。每个三角形对应一个面，我们可以用顶点或边列表表示面。 索引三角网格 在索引三角网格中，我们维护了两个列表：顶点表与三角形表。 每个顶点包含一个3D位置，也可能有如纹理映射坐标、表面法向量、光照值等附加数据。 每个三角形由顶点列表的三个索引组成。通常，顶点列出的顺序是非常重要的，因为我们必须考虑面的"正面"和"反面"。从前面看时，我们将用顺时针方向列出顶点。另外一些信息也存在这一级中，如预先计算的表面法向量，表面属性（纹理映射）等。 程序清单14.2给出了一段高度简化的代码： Listing 14.2: Indexed triangle mesh // struct Vertex is the information we store at the vertex level struct Vertex { // 3D position of the vertex Vector3 p; // Other information could include texture mapping coordinates, // a surface normal, lighting values, etc. } // struct Triangle is the information we store at the triangle level struct Triangle { // Indices into the vertex list int vertex[3]; // Other information could include a normal, material information , etc. } // struct TriangleMesh stores an indexed triangle mesh struct TriangleMesh {
有限元网格划分 摘要:总结近十年有限元网格划分技术发展状况。首先,研究和分析有限元网格划分的基本原则；其次,对当前典型网格划分方法进行科学地分类,结合实例,系统地分析各种网格划分方法的机理、特点及其适用范围,如映射法、基于栅格法、节点连元法、拓扑分解法、几何分解法和扫描法等；再次,阐述当前网格划分的研究热点,综述六面体网格和曲面网格划分技术；最后,展望有限元网格划分的发展趋势。 关键词:有限元网格划分；映射法；节点连元法;拓扑分解法；几何分解法；扫描法；六面体网格 1 引言 有限元网格划分是进行有限元数值模拟分析至关重要的一步，它直接影响着后续数值计算分析结果的精确性。网格划分涉及单元的形状及其拓扑类型、单元类型、网格生成器的选择、网格的密度、单元的编号以及几何体素。在有限元数值求解中，单元的等效节点力、刚度矩阵、质量矩阵等均用数值积分生成，连续体单元以及壳、板、梁单元的面内均采用高斯（Gauss）积分，而壳、板、梁单元的厚度方向采用辛普生（Simpson）积分。 2 有限元网格划分的基本原则 有限元方法的基本思想是将结构离散化,即对连续体进行离散化,利用简化几何单元来近似逼近连续体,然后根据变形协调条件综合求解。所以有限元网格的划分一方面要考虑对各物体几何形状的准确描述,另一方面也要考虑变形梯度的准确描述。为正确、合理地建立有限元模型,这里介绍划分网格时应考虑的一些基本原则。 2.1 网格数量
网格数量直接影响计算精度和计算时耗,网格数量增加会提高计算精度,但同时计算时耗也会增加。当网格数量较少时增加网格，计算精度可明显提高,但计算时耗不会有明显增加;当网格数量增加到一定程度后,再继续增加网格时精度提高就很小,而计算时耗却大幅度增加。所以在确定网格数量时应权衡这两个因素综合考虑。 2.2 网格密度 为了适应应力等计算数据的分布特点,在结构不同部位需要采用大小不同的网格。在孔的附近有集中应力,因此网格需要加密;周边应力梯度相对较小,网格划分较稀。由此反映了疏密不同的网格划分原则:在计算数据变化梯度较大的部位,为了较好地反映数据变化规律,需要采用比较密集的网格;而在计算数据变化梯度较小的部位,为减小模型规模,网格则应相对稀疏。 2.3 单元阶次 单元阶次与有限元的计算精度有着密切的关联,单元一般具有线性、二次和三次等形式,其中二次和三次形式的单元称为高阶单元。高阶单元的曲线或曲面边界能够更好地逼近结构的曲线和曲面边界,且高次插值函数可更高精度地逼近复杂场函数,所以增加单元阶次可提高计算精度。但增加单元阶次的同时网格的节点数也会随之增加,在网格数量相同的情况下由高阶单元组成的模型规模相对较大,因此在使用时应权衡考虑计算精度和时耗。 2.4 单元形状 网格单元形状的好坏对计算精度有着很大的影响,单元形状太差的网格甚至会中止计算。单元形状评价一般有以下几个指标: (1)单元的边长比、面积比或体积比以正三角形、正四面体、正六面体为参考基准。 (2)扭曲度:单元面内的扭转和面外的翘曲程度。 (3)节点编号:节点编号对于求解过程中总刚矩阵的带宽和波前因数有较大的影响,从而影响计算时耗和存储容量的大小
初中数学锐角三角函数的经典测试题及解析一、选择题 1．如图，在扇形OAB中，120 AOB ∠=?，点P是弧 AB上的一个动点（不与点A、B重 合），C、D分别是弦AP，BP的中点．若33 CD=，则扇形AOB的面积为（）A．12πB．2πC．4πD．24π 【答案】A 【解析】 【分析】 如图，作OH⊥AB于H．利用三角形中位线定理求出AB的长，解直角三角形求出OB即可解决问题． 【详解】 解：如图作OH⊥AB于H． ∵C、D分别是弦AP、BP的中点． ∴CD是△APB的中位线， ∴AB＝2CD＝63 ∵OH⊥AB， ∴BH＝AH＝33 ∵OA＝OB，∠AOB＝120°， ∴∠AOH＝∠BOH＝60°， 在Rt△AOH中，sin∠AOH＝ AH AO ， ∴AO＝ 33 6 sin3 AH AOH == ∠， ∴扇形AOB的面积为： 2 1206 12 360 π π = g g ，
故选：A ． 【点睛】 本题考查扇形面积公式，三角形的中位线定理，解直角三角形等知识，解题的关键是学会添加常用辅助线，构造直角三角形解决问题，属于中考常考题型． 2．如图，在ABC ?中，4AC =，60ABC ∠=?，45C ∠=?，AD BC ⊥，垂足为D ，ABC ∠的平分线交AD 于点E ，则AE 的长为（ ） A 2 B 22 C 42 D 32 【答案】C 【解析】 【分析】 在Rt △ADC 中，利用等腰直角三角形的性质可求出AD 的长度，在Rt △ADB 中，由AD 的长度及∠ABD 的度数可求出BD 的长度，在Rt △EBD 中，由BD 的长度及∠EBD 的度数可求出DE 的长度，再利用AE=AD?DE 即可求出AE 的长度． 【详解】 ∵AD ⊥BC ∴∠ADC=∠ADB=90? 在Rt △ADC 中，AC=4，∠C=45? ∴AD=CD=22在Rt △ADB 中，AD=22ABD=60? ∴BD=33AD=263 ． ∵BE 平分∠ABC ， ∴∠EBD=30°． 在Rt △EBD 中，26，∠EBD=30° ∴DE=33BD=223 ∴AE=AD ?DE=222242 故选：C 【点睛】
网格型问题 一、选择题 1. （2011?台湾20，4分）如图为一张方格纸，纸上有一灰色三角形，其顶点均位于某两网 格线的交点上，若灰色三角形面积为421 平方公分，则此方格纸的面积为多少平方公分 （ ） A 、11 B 、12 C 、13 D 、14 考点：一元二次方程的应用。 专题：网格型。 分析：可设方格纸的边长是x ，灰色三角形的面积等于方格纸的面积减去周围三个直角三角形的面积，列出方程可求解． 解答：解：方格纸的边长是x ，21 x2﹣21?x?21x ﹣21?21x?43x ﹣21?x?41x=421 x2=12． 所以方格纸的面积是12， 故选B ． 点评：本题考查识图能力，关键看到灰色三角形的面积等于正方形方格纸的面积减去周围三个三角形的面积得解． 2. （2011湖北潜江，7，3分）如图，在6×6的方格纸中，每个小方格都是边长为1的正方形，其中A 、B 、C 为格点．作△ABC 的外接圆⊙O，则弧AC 的长等于（ ）
A ．π43 B ．π45 C ．π23 D ．π25 考点：弧长的计算；勾股定理；勾股定理的逆定理；圆周角定理。 专题：网格型。 分析：求弧AC 的长，关键是求弧所对的圆心角，弧所在圆的半径，连接OC ，由图形可知OA ⊥OC，即∠AOC＝90°，由勾股定理求OA ，利用弧长公式求解． 解答：解：连接OC ，由图形可知OA⊥OC， 即∠AOC＝90°， 由勾股定理，得OA ＝2 212+＝5， ∴弧AC 的长＝180590??π＝25π． 故选D ． 点评：本题考查了弧长公式的运用．关键是熟悉公式：扇形的弧长＝180r n ??π． 3. （2011?西宁）如图，△DEF 经过怎样的平移得到△ABC（ ） A 、把△DEF 向左平移4个单位，再向下平移2个单位 B 、把△DEF 向右平移4个 单位，再向下平移2个单位 C 、把△DEF 向右平移4个单位，再向上平移2个单位 D 、把△DEF 向左平移4个 单位，再向上平移2个单位 考点：平移的性质。 专题：常规题型。 分析：根据网格图形的特点，结合图形找出对应点的平移变换规律，然后即可选择答案． 解答：解：根据图形，△DEF 向左平移4个单位，向下平移2个单位，即可得到△ABC．
网 格 问 题 1. 已知图1和图2中的每个小正方形的边长都是1个单位. （1）将图1中的格点△ABC ，先向右平移3个单位，再向上平移2个单位，得到△A 1B 1C 1，请你在图1中画出△A 1B 1C 1. （2）在图2中画出一个与格点△DEF 相似但相似比不等于1的格点三角形. 2. 如图，方格纸中每个小方格都是边长为1的正方形，我们把以格点连线为边的多边形称为“格点多边形”．如图（一）中四边形ABCD 就是一个“格点四边形”． （1）求图（一）中四边形ABCD 的面积； （2）在图（二）方格纸中画一个格点三角形EFG ，使△EFG 的面积等于四边形ABCD 的面积且为轴对称图形． D C B A 图（一） 图（二） 3. 如图，在55 的正方形网格中，每个小正 方形的边长都为1.请在所给网格中按下列要求画 出图形． （1）从点A 出发的一条线段AB ，使它的另一 个端点落在格点（即小正方形的顶点）上， 且长度为22； （2）以（1）中的AB 为边的一个等腰三角形 ABC ，使点C 在格点上，且另两边的长 都是无理数； （3）以（1）中的AB 为边的两个凸多边形，使 它们都是中心对称图形且不全等，其顶点都 在格点上，各边长都是无理数． 图2 F E A B C 图1 （第3题图）
4. 下面的方格纸中，画出了一个“小猪”的图案，已知每个小正方形的边长为1． （1）“小猪”所占的面积为多少？ （2）在上面的方格纸中作出“小猪”关于直线DE 对称的图案（只画图，不写作法）； （3）以G 为原点，GE 所在直线为x 轴，GB 所在直线为y 轴，小正方形的边长为单位长度建立直角坐标系，可得点A 的坐标是（_______，_______）． 5. 图(1)是一个10×10格点正方形组成的网格. △ABC 是格点三角形(顶点在网格交点处), 请你完成下面两个问题: (1) 在图(1)中画出与△ABC 相似的格点△A 1B 1C 1和△A 2B 2C 2, 且△A 1B 1C 1与△ABC 的相似比是2, △A 2B 2C 2与△ABC 的相似比是2 2. (2) 在图(2)中用与△ABC 、△A 1B 1C 1、△A 2B 2C 2全等的格点三角形(每个三角形至少使用一次), 拼出一个你熟悉的图案,并为你设计的图案配一句贴切的解说词 . 【解说词】 6. 如图，有一条小船， （1） 若把小船平移，使点A 平移到点B ，请你在图中画出平移后的小船；（5分） （2） 若该小船先从点A 航行到达岸边L 的点P 处补给后，再航行到点B ，但要求航 程最短， E C D G B F A
有限元网格剖分方法概述 在采用有限元法进行结构分析时，首先必须对结构进行离散，形成有限元网格，并给出与此网格相应的各种信息，如单元信息、节点坐标、材料信息、约束信息和荷载信息等等，是一项十分复杂、艰巨的工作。如果采用人工方法离散对象和处理计算结果，势必费力、费时且极易出错，尤其当分析模型复杂时，采用人工方法甚至很难进行，这将严重影响高级有限元分析程序的推广和使用。因此，开展自动离散对象及结果的计算机可视化显示的研究是一项重要而紧迫的任务。 有限元网格生成技术发展到现在, 已经出现了大量的不同实现方法，列举如下： 映射法 映射法是一种半自动网格生成方法，根据映射函数的不同，主要可分为超限映射和等参映射。因前一种映射在几何逼近精度上比后一种高，故被广泛采用。映射法的基本思想是：在简单区域内采用某种映射函数构造简单区域的边界点和内点，并按某种规则连接结点构成网格单元。也就是根据形体边界的参数方程，利用映射函数，把参数空间内单元正方形或单元三角形(对于三维问题是单元立方体或单元四面体)的网格映射到欧氏空间，从而生成实际的网格。这种方法的主要步骤是，首先人为地把分析域分成一个个简单可映射的子域，每个子域为三角形或四边形，然后根据网格密度的需要，定义每个子域边界上的节点数，再根据这些信息，利用映射函数划分网格。 这种网格控制机理有以下几个缺点： （1）它不是完全面向几何特征的，很难完成自动化，尤其是对于3D区域。 （2）它是通过低维点来生成高维单元。例如，在2D问题中，先定义映射边界上的点数，然后形成平面单元。这对于单元的定位，尤其是对于远离映射边界的单元的定位，是十分困难的，使得对局部的控制能力下降。 （3）各映射块之间的网格密度相互影响程度很大。也就是说，改变某一映射块的网格密度，其它各映射块的网格都要做相应的调整。 其优点是：由于概念明确，方法简单，单元性能较好，对规则均一的区域，适用性很强，因此得到了较大的发展，并在一些商用软件如ANSYS等得到应用。 2 。拓扑分解法 拓扑分解法较其它方法发展较晚, 它首先是由Wordenwaber提出来的。该方法假设最后网格顶点全部由目标边界顶点组成, 那么可以用一种三角化算法将目标用尽量少的三角形完全分割覆盖。这些三角形主要是由目标的拓扑结构决定, 这样目标的复杂拓扑结构被分解成简单的三角形拓扑结构。该方法生成的网格一般相当粗糙, 必须与其它方法相结合, 通过网格加密等过程, 才能生成合适的网格。该方法后来被发展为普遍使用的目标初始三角化算法, 用来实现从实体表述到初始三角化表述的自动化转换。 单一的拓扑分解法因只依赖于几何体的拓扑结构使网格剖分不理想，有时甚至很差。 3．连接节点法 这类方法一般包括二步：区域内布点及其三角化。早期的方法通常是先在区域内布点, 然后再将它们联成三角形或四面体, 在三角化过程中, 对所生成的单元形状难于控制。随着Delaunay三角化(简称为DT ) 方法的出现, 该类方法已成为目前三大最流行的全自动网格生成方法之一。 DT法的基本原理：任意给定N个平面点Pi(i=1,2,…,N)构成的点集为S，称满足下列条件的点集Vi为Voronoi多边形。其中，Vi满足下列条件： Vi ={ X：|X- Pi|(|X- Pj|,X(R2,i(j,j=1,2,…,N }Vi为凸多边形，称{ Vi}mi=1为Dirichlet Tesselation
锐角三角函数 知识点一：锐角三角函数 1、锐角A 的正弦、余弦、正切都叫做∠A 的锐角三角函数。 2、锐角A 的对边与斜边的比叫做∠A 的正弦，记作sinA ，即斜边的对边 A A ∠= sin 。 3、锐角A 的邻边与斜边的比叫做∠A 的余弦，记作cosA ，即斜边的邻边 A A ∠=cos 。 4、锐角A 的对边与邻边的比叫做∠A 的正切，记作tanA ，即的邻边 的对边 A A A ∠∠=tan 。 sin α，cos α，tan α都是一个完整的符号，单独的 “sin”没有意义，其中α前面的“∠”一般省略不写；但当用三个大写字母表示一个角时，“∠”的符号就不能省略。 考点一：锐角三角函数的定义 1、在Rt△ABC 中，∠C=90°，cosB=5 4 ，则AC ：BC ：AB=（ ） A 、3：4：5 B 、5：3：4 C 、4：3：5 D 、3：5：4 2、已知锐角α，cosα= 3 5 ，sinα=_______，tanα=_______。 3、在△ABC 中，∠C=90°，若4a=3c ，则cosB= = ______。 4、在△ABC 中，∠C=90°，AB=15，sinA= 1 3 ，则BC 等于_______。 5、在△ABC 中，∠C=90°，若把AB 、BC 都扩大n 倍，则cosB 的值为（ ） A 、ncosB B 、1 n cosB C 、cos n B D 、不变 考点二：求某个锐角的三角函数值——关键在构造以此锐角所在的直角三角形 例1、如图，在矩形ABCD 中，E 是BC 边上的点，AE BC =，DF AE ⊥，垂足为F ，连接DE 。 （1）求证：ABE △DFA ≌△； （2）如果10AD AB =，=6，求sin EDF ∠的值。 6、如图，在△ABC 中，∠A=60°，∠B=45°，AB=8，求△ABC 面积（结果可保留根号）。 注意：正弦、余弦、正切是在一个直角三角形中引入的，实际上是两条边的比，它们是正实数，没单位，其大小只与角的大小有关，而与所在直角三
网格中的三角形 河北张家口市第十九中学 贺峰 随着新课程的实施，在近几年的中考试卷中出现了许多新颖的网格型试题，这类试题具有很强的直观性、可操作性、开放性及综合性等特点，不仅能够考查学生的数学知识，体现分类、数形结合等重要的数学思想，同时也考查和培养学生的识图、归纳、动手操作、自主探究等多种能力，有利于培养学生的探究意识和创新精神。现以近几年中考试题中出现的“网格中的三角形”为例，为同学们加以归类分析： 一、网格中的“等面积三角形” 例1 已知在正方形网格中，每个小方格都是边长为1的正方形，A 、B 两点在小方格的顶点上，位置如图1所示，点C 也在小方格的顶点上，且以A 、B 、C 为顶点的三角形面积为1，则点C 的个数为（ ） （A ）3个 （B ）4个 （C ）5个 （D ）6个 析解：此题以网格为载体来考查同学们等面积三角形的构成，体现分类讨论思想，若使点C 在小方格的顶点上，且以A 、B 、C 为顶点的三角形面积为1， 即保证△ABC 的底为2，高为1，因此须分类讨论的思想方法，即按AC ＝2时、BC ＝2时进行分类求解。答案如图2所示： 说明：此题也可通过对图形对称变换进行求解，即确定第（1）、（3）、（5）三种情况，分别以AB 所在的直线为对称轴将△ABC 翻折，使点C 落在格点上即可求解。 即可求解。 二、网格中的“等腰三角形” 例2如图3所示，A 、B 是4×5网络中的格点，网格中的每个小正方形的边长为1，请在图中清晰标出使以A 、B 、C 为顶点的三角形是等腰三角形的 所有格点C 的位置． 析解：此题以网格为载体来考查同学们等腰三角形的构成，体现分类讨论思 想，若使点C 在小方格的顶点上，且以A 、B 、C 为顶点的三角形为等腰三角形，即保证△ABC 中AB ＝AC 或AB ＝BC 或AC ＝AB ，即分别以AC 、AB 、BC 为腰时进行分类求解。答案如图4所示： 说明：此题也可通过对图形旋转变换进行求解，即以AB 为腰，分别以点A 、点B 为旋转中心，将线段AB 进行旋转，使点B 、点A 落在格点上即可求解。 三、网格中的“直角三角形” 例3如图5，正方形网格中，小格的顶点叫做格点，小华按下列要求作图： ①在正方形网格的三条不同实线上各取一个格点，使其中任意两点不在同一条实线 上；②连结三个格点，使之构成直角三角形， 小华在左边的正方形网格中作出了Rt △ABC ，请你按照同样的要求，在右边的两个 正方形网格中各画出一个直角三角形，并使三个网格中的直角三角形互不全等。 析解：此题开放性很强， 给学生广阔的思维空 图1 A 图3 图 4 A B C 图5 图6 C C C C C C （1） （2） （3） （5） （6） 图2
有限元网格划分及发展趋势 摘要:总结近十年有限元网格划分技术发展状况。首先,研究和分析有限元网格划分的基本原则；其次,对当前典型网格划分方法进行科学地分类,结合实例,系统地分析各种网格划分方法的机理、特点及其适用范围,如映射法、基于栅格法、节点连元法、拓扑分解法、几何分解法和扫描法等；再次,阐述当前网格划分的研究热点,综述六面体网格和曲面网格划分技术；最后,展望有限元网格划分的发展趋势。关键词:有限元网格划分；映射法；基于栅格法；节点连元法;拓扑分解法；几何分解法；扫描法；六面体网格 1 引言 作为有限元走向工程应用枢纽的有限元网格划分,是有限元法的一个非常重要的研究领域,经历了40多年的发展历程。有限元网格划分算法研究中的某些难点问题始终未能得到真正意义上的解决,它们的解决对工程问题具有重要的现实价值和理论意义。有限元分析的基本过程可分为三个阶段:有限元模型的建立(即前处理)、有限元解算、结果处理和评定(即后处理)。根据经验,有限元分析各阶段所用的时间为】 【1:40%-45%用于模型的前处理,50%-55%用于后处理,而分析计算只占5%左右;更有文献】 【2指出有限元建模占有限元分析一半以上的工作量,甚至高达80%。因此,有限元分析的前后处理一直都是有限元分析的瓶颈问题,严重地阻碍着有限元分析技术的应用和发展。 许多学者对有限元网格生成方法近30年的研究进行了概括和总结】 【4。近年来,【3,对某些重要分支领域的研究进展方面也做出了贡献】 有限元网格生成方法研究有两个显著特点:(1)经历了一个进化过程,一些方法的研究与应用出现停滞,而另外一些方法在不断地深入、完善和发展,成为适应性强、应用范围广泛的通用方法;(2)领域和主题在不断扩展和深入,研究重点由二维平面问题转移到三维曲面和三维实体问题,从三角形、四面体网格自动生成转移到四边形、六面体网格自动生成。 2 有限元网格划分的基本原则 有限元方法的基本思想是将结构离散化,即对连续体进行离散化,
1． 掌握锐角三角函数的概念，会熟练运用特殊三角函数值； 2． 知道锐角三角函数的取值范围以及变化规律； 3． 同角三角函数、互余角三角函数之间的关系； 4． 将实际问题转化为数学问题，建立数学模型． 模块一 三角函数基础 一、 锐角三角函数的定义 如图所示，在Rt ABC △中，a 、b 、c 分别为A ∠、B ∠、C ∠的对边． （1）正弦：Rt ABC ?中，锐角A 的对边与斜边的比叫做A ∠的正弦，记作sin A ，即sin a A c = ． （2）余弦：Rt ABC ?中，锐角A 的邻边与斜边的比叫做A ∠的余弦，记作cos A ，即cos b A c =． （3）正切：Rt ABC ?中，锐角A 的对边与邻边的比叫做A ∠的正切，记作tan A ，即tan a A b =． 注意： ① 正弦、余弦、正切都是在直角三角形中给出的，要避免应用时对任意三角形随便套用定义． ② sin A 、cos A 、tan A 分别是正弦、余弦、正切的数学表达符号，是一个整体，不能理解为sin 与A 、 cos 与A 、tan 与A 的乘积． ③ 在直角三角形中，正弦、余弦、正切分别是某个锐角的对边与斜边、邻边与斜边、对边与邻边的比值，当这个锐角确定后，这些比值都是固定值． 二、 特殊角三角函数 这些特殊角的三角函 数值一定要牢牢记住！ 三、锐角三角函数的取值范围 在Rt ABC ?中，90C ∠=?，000a b c a c b c >>><<，，，，，又sin a A c =，cos b A c =，tan a A b =，所以 0sin 10cos 1tan 0A A A <<<<>，，． 三角函数 0? 30? 45? 60? 90? sin A 12 22 32 1 cos A 1 32 22 12 0 tan A 33 1 3 - 锐角三角函数 c b a C B A
中考“网格”中的相似三角形问题 所谓网格中的形似三角形就是在正方形的网格中寻找三角形相似的问题.这类问题是近年来全国各地中考的一个热点和亮点，试题的特点主要是以用勾股定理等知识计算三角形的边长，再加上正方形的对角线形成的特殊角，要求能从正方形网格中挖掘出条件，灵活运用相似三角形的性质与判定解决问题.目的是要考查同学们的观察、猜想、探究问题的能力，为了帮助同学们掌握这一知识点，现以中考试题为例说明如下： 例1 如图1，小正方形的边长均为1，则下图中的三角形(阴影部分)与△ABC 相似的为（ ） 分析 先利用勾股定理求出△ABC 、2 ，再分别求出选择支中三角形的三边的长，然后分别求出对应边长的比. 解 由于正方形边长均为1，在△ABC 中，AC ＝2，BC ＝2，AB ＝10；图A 中三 角形三边长为1 22，而与△ABC ，2 显然 它们不相等；图B 中三角形三边长为1，2 ABC ＝ 2 ， 2 2 ，故对应边的比相等；同样的道理可以得出在图C 和图D 中的两个三角 形三边分别与△ABC 三边的比不相等.故选B . 例 2 如图2，若A 、B 、C 、D 、E 、F 、G 、H 、O 都是5×7方格纸中的格点，为使△DME ∽△ABC ，则点M 应是F 、G 、H 、O 四点中的（ ） A.F B.G C.H D.O 分析 若△DME ∽△ABC ，△ABC 又是一个等腰直角三角形，故△DME 也应是等腰直角三角形，这样观察图中F 、G 、H 、O 四点与D 、E 两点的位置关系即可求解. 解 因为△ABC 是一个等腰直角三角形，所以要使△DME ∽△ABC ，△DME 也必须是一个等腰直角三角形， 所以观察图中F 、G 、H 、O 四点与D 、E 两点的位置关系只有点H 能与D 、E 两点构成等腰直角三角形.故应选C . 图4 图2 图1 图3
科学与财富 0引言 近年来，随着计算机图形软硬件技术的提高及人们对绘制效果的要求越来越高，计算机图形学研究和应用呈现出场景对象越加复杂，对绘制真实感的要求越来越高，显示分辨率不断递增，模型趋于复杂化，数据精度要求较高等问题。基于此提出了提高绘制性能的主要途径：GPU加速技术，并行绘制技术，可见性剔除技术，网格简化技术，多分辨率绘制技术，存储访问优化技术，基于图像的绘制技术，图像和网格压缩技术，基于预计算的绘制技术等。 对于计算机硬件性能的不断提高，存储访问带宽与计算能力的差距越来越大，因此缓存访问效率成为影响应用程序运行效率的关键因素。而要改善缓存的性能有以下几种方法：①降低缓存访问失配率；②降低失配损失；③通过并行技术降低失配率或是失配损失；④减少命中缓存的时间。降低缓存访问失配率，可以从提高缓存硬件性能与编译优化等方面来解决，其原理是：通过调整指令顺序和数据的使用顺序，增强代码和数据使用的时间局部性和空间局部性特征，从而提高缓存命中率。体系结构方面，通过缓存硬件性能来提高缓存访问效率。应用程序方面，采用编译优化不需要修改或者增加硬件，可分为计算重排和数据重排。 计算重排，根据重新排列指令顺序，提高访问相同数据单元指令的局部性，通常由编译器对应用程序编译后的指令序列进行重排来完成，对于指令，重新组织程序而不影响程序的正确性。数据重排，根据指令对数据单元的访问方式求解出缓存连贯的数据排布，由应用程序直接对数据进行重排来完成，通过优化改善了数据的空间局部性和时间局部性[1]。目前网格排布优化技术是计算机图形学与可视化领域的重点研究方向之一，该技术基于数据重排，通过对网格图元的存储顺序进行重新排序，能够减少平均缓存访问失配率，提高大型三维网格模型和大规模虚拟场景的处理和绘制性能。 2网格排布优化技术 顶点缓存的访问性能通常用平均缓存失配率（ACMR）来衡量，定义为绘制每个三角形的平均缓存失配次数，即缓存的总失配次数与总访问次数之比，ACMR的取值范围为[0.5，3.0]，因为每个顶点至少失配一次，至多失配三次。需要注意的是，ACMR无法达到最小值，主要是因为顶点缓存区容量的限制。若顶点缓存区可以装下所有顶点，则以任何方式组织的三角形都可以使ACMR接近于0.5。但是缓存容量很小，很难装下所有的顶点，并且网格的形状也会导致ACMR额外的开销。 2.2.1网格排布优化方法的分类 网格排布优化技术是图排布理论的应用与引伸，根据不同的划分方式可以将网格排布优化技术分成不同的类。根据求解技术手段的不同，网格排布优化技术可分为基于优化策略、基于空间填充曲线和基于谱序列三类[1]，现代的GPU使用一个小的缓冲区来存储最近需要访问的顶点，为了最大化的利用好顶点缓存用于快速渲染的优点，对三角形进行重排序是必要的，基于优化策略即使用了这一优点。基于空间填充曲线是对二维或者三维规则网格单元的一种具有较好空间局部性的特殊线性遍历方法，是在某种程度上保留局部相关性的多维网格单元遍历。基于谱序列方法是通过特定的线性算子推导出相关的特征性、特征向量以及特征空间投影，并利用这些特征量和组合求解出问题。因为谱序列是求解图排布问题的一个有效引导策略，所以也可以应用到网格排布技术中。 根据网格描述方式的不同，可分为基于三角形、基于三角形条带、基于三角形扇[3]，或者简单分为基于条带和基于非条带两种方式，每种描述方式又可分为索引形式和三角形汤形式。三角形扇和三角形条带类似，但是不如三角形条带灵活，所以很少使用。索引形式只需少量数据，传输代价小，使之成为目前使用最为普遍的方式，但顶点随机读取也带来了ACMR的增加。因此许多研究者提出对网格图元的存储顺序进行重新排布，可以减小 ACMR，降低顶点处理的运算量，提高渲染速度。 2.2.2三角形排布优化算法的介绍 为提高网格模型的处理和绘制性能，现代图形卡使用顶点缓冲器来提高顶点缓存命中率，使模型在绘制过程中减少发送的顶点数据。有效利用顶点缓冲器，在已有的图形绘制流水线基础上，通过重新排列网格模型图元的线性序列，增加缓存中顶点的命中率。下面对国内外几种常见的相关算法做一个简要的介绍。 Hoppe(Hoppe.1999)提出了一种贪心条带算法生成三角形序列[4]，该算法是基于优化策略和三角形条带的研究，核心思想是沿着逆时针方向生成条带，进行三角形条带合并，在合并的过程中不断检测预期的ACMR。此算法针对一个预先指定的缓存大小，比如16，对算法进行优化求解，使用FI-FO策略对三角形进行重排，采用了三角形条带索引模式。Hoppe算法可以得到很低的平均缓存失配率，其运算时间复杂度高于O(m)，该算法也存在一些待解决的问题，在网格的顶点索引中很难确定三角形的拓扑方向，对可能合并入条带的三角形进行ACMR的预估会增加算法的复杂度。Bogomjakov等人（2002）提出的面向具有任意大小的FIFO缓存的通用序列构造算法（称为BoG算法）[5]，是一种最具代表性的空间填充曲线。该算法把Hilbert空间填充曲线和MLA空间填充曲线的应用推广到不规则三角网格，使用图划分软件包Metis将网格分成多个三角形簇，保证每个簇内三角形序列的ACMR最优，从而形成整个网格的ACMR最优化。该算法在相同缓存参数前提下，AMCR指比Hoppe算法增大20％左右，分割的切割边上的失配率对整体失配率有影响。 Lin等人(Lin and Thomas.2006)算法则是基于贪心优化策略的3D渲染多边形网格序列生成算法[6]，该算法适用于非条带三角形的排布优化，可以应用于渐进网格，应用启发式条件对网格顶点进行全局搜索，同样可以得到很低的平均缓存失配率，其运算时间复杂度也高于O(m)。核心思想是赋予每个顶点一个缓存访问代价度量，选择代价度量最小的顶点作为当前输出顶点，找到与该顶点邻接的所有未输出三角形，按顺时针方向访问并逐一将这些三角形的顶点压入缓存中，最后以三角形环为单位逐一输出三角形，并在整个网格中对下一个需要输出的三角形环进行全局最优性搜索。Nehab等人(Nehab et al.2006)提出了一种多功能三角形序列重排算法[7]，该算法不仅能减少顶点缓存的平均缓存失配率，而且能减少图元的重绘率（通过深度测试的片元总数与最终可见的像素总数之比），作者首先提出通过局部优化减少顶点处理时间，同时通过三角形序列重排减少像素处理时间是自相矛盾的，原因是基于视点的深度排序会毁掉顶点缓存性能，且局部优化会导致当前视点下的高度透支。基于此提出了基于优化策略的多功能三角形序列重排算法，实现两者之间的融合。 Sander等人(Sander et al.2009)对Lin等人算法进行了改进，使三角形排布适用于动态模型[8]。其核心思想是以顶点在缓存中的位置作为代价度量，选出代价度量最小的顶点作为当前顶点，即以三角形环作为计算单位，然后输出与该顶点邻接的所有未输出三角形（随机访问），与Lin等人算法 基于三维网格模型的网格排布优化技术综述 娄自婷 （云南师范大学信息学院，云南昆明650500） 摘要：网格排布优化技术通过对网格图元的存储顺序进行重新排序，能够减少平均缓存访问失配率，提高大型三维网格模型和大规模虚拟场景的处理和绘制性能。文中综述了网格排布优化技术的研究进展，分析比较了基于优化策略、基于空间填充曲线和基于谱序列的网格排布优化方法。 关键词：三维网格模型，网格排布优化；ACMR A Survey of mesh layout optimization for3D mesh models LOU Ziting (College of computer science and information technology,Yunnan Normal University,Kunming City Yunnan Province650500,China) Abstract:The mesh layout technology through storage order of the mesh primitive reorder,can reduce the average cache miss rate and improve the process-ing and rendering performance of large3D mesh models and large-scale virtual scene.This paper gives an introduction to advances in technology mesh layout optimization.We analyze and compare the mesh layout optimization method based optimization strategy,space-filling curve and spectral sequences. Keywords:3D mesh models,Mesh layout optimization;ACMR 科学论坛 536