快速绘制 篇1
地形场景重建时,为了使提高实时显示地形的效率,需要对地形数据结构进行绘制优化[1],根据数据结构的不同,优化技术可以概括为两大类[2]:基于不规则三角网的LOD技术和基于规则网格结构的树形结构技术。
基于不规则三角网LOD技术的主要思想是对于地形简单的区域[3],采用很少的不规则三角形绘制,而对于地形复杂的区域,则可以根据实际情形用更多的不规则三角形表示[4]。基于不规则三角网的LOD技术能很好地实现对三维场景数据的近似,提高视觉的连续性,然而算法计算量大,难以实时显示[5]。与TIN结构相比,规则网格结构则由于数据结构简单而得到了较为广泛的应用,常见的DEM就使用了规则网格。采用树形结构来表示地形有许多优势。首先,树结构可方便对地形进行分块细分;其次,树结构表示的地形块方便对地形表面进行纹理映射。第三,采用树结构能够减少地形表示时间,加速地形简化[6]。但是采用树结构无法达到最优的简化效果,而且需要占用大量的内存空间。本文针对两种方法的优缺点,提出了一种混合算法,在宏观上以四叉树方法简化地形数据,在细节层次上使用不规则三角网表示地形,最后通过有效的误差控制原则,解决了四叉树结构分块间的连接问题。
1四叉树结构地形数据表示
树结构是地形绘制中经常采用的数据结构,二叉树和四叉树都被用来表示地形。采用四叉树来构造多分辨率地形在地形可视化中有许多优势。图1是用四叉树表示地形的一个实例。
树中的每一个节点都覆盖地形中一矩形区域,根结点C0 覆盖整个地形区域,通过迭代细分生成更高分辨率的地形,用节点C1、C2、C3、C4表示,在四叉树生成中所有的子节点所覆盖的地形区域为父节点四分之一,其分辨率比父节点的分辨率高一倍。在四叉树中位于上层的节点涉及的采样点较少,地形绘制花费的代价少,误差大;相反用下层的节点表示地形时采样点的分辨率高,绘制地形速率下降,地形表示的误差小。视相关的简化依据视点的位置和方向合理的选择多分辨率的地形表示,视点周围的地形用高细节的层次表示,远离视点的区域用较粗糙的细节表示,提高绘制速率使用户可交互浏览地形。
顶点的四叉树剖分从网格的中心点(图2中白点)出发,递归访问其四个子顶点(图2中黑点),判断顶点是否活动,直至到达网格所需要的精度。为实现地形数据的四叉树结构,首先地形必须是一正方形区域。而且大小必须是(2n+1)×(2n+1),n为大于0的整数。同时采样间隔必须均匀。如图3是采用四叉树的概念来描述一个多分辨率地形,图中的每一个正方形为四叉树的一个节点,每个节点保存了一定区域的信息,包括中心点的高度,从整个完整的地形出发,可以递归地把地形不断的分割(Sub-divide)成相等的四个区域,分割的深度越大,则得到的分辨率越高。即分割深度每提高一层,采样密度提高一倍。图2演示了分割的过程。
2基于四叉树结构的地形分块
本文首先使用四叉树结构对原始的规则网格数据进行多分辨率分块。其四叉树分块过程为:首先选取整个地形为结点,然后判断结点是否满足某种条件,如果是则认为是叶子结点,否则将该结点四分为四个子结点,用递归的方法判断四个子结点是否满足叶子条件,直至不可再分为止。其算法过程可描述为:
Step1 根结点入栈;
Step2 若栈为空,转step 5,否则第一个结点出栈;
Step3 判断出栈结点是否满足结点误差评估函数要求,若满足,则将此结点放入集合,否则将这个结点的4个子结点入栈;
Step4 转step 2;
Step5 结束。
叶子结点的输出判断准则直接影响到四叉树划分的质量。实际仿真中,由于视点常常离地面很近,人们所见的只是局部离视点近的区域的地形,而对较远的区域不感兴趣,甚至不可见。因此,为进一步减少算法的计算量,可以使简化与视点相关,即在计算每个节点的重要性测度时,考虑和视点相关的测度[7]。综合考虑地形特征和视点依赖这两个因素的影响,定义误差的判别准则为:
其中,α和L为视点的张角和投影平面的边长,被投线段长度为l,视点与该线段中心的距离为d,λ为物体空间中的单位长度在投影平面上的像素数,k为一可变系数,S(Ci)为地形点的视点无关误差,可由下式计算:
其中,h(x,y)为地形高程函数,A(Star(p))为结点定义的平均误差平面。
3基于四叉树的TIN网格生成算法
3.1单块Delaunay三角网的生成
Delaunay三角网要求任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[8]。这样就会生成尽可能多的锐角三角形。本文中单个数据分块是四叉树结构中的一个叶子块点集,对子块的三角网生成算法采用基于拓扑结构和凸壳技术的快速TIN生成技术的构建方法,该算法利用有序点子集凸壳的特性,提高构网效率。同时本文采用类似文献[9]中的Delaunay三角网构网优化算法,并根据四叉树结构的特点,改进了优化算法对边界点的处理,解决四叉树分块之间的连接与过渡问题,具体实现步骤如下:
Step1 由于四叉树相邻块之间分辨率相差不超过1,为了便于分块之间的拼接,消除分块间的裂缝,将分块的每条边都二等分,记为分块的边界点,并将边界点作为凸壳点以逆时针的顺序放在顶点数组中。
Step2 将四叉树分块的四个叶子结点连成初始三角形,并添加到三角形数组中依次插入凸壳上的其它边界点并用局部优化函数进行局部优化。
Step3 判断三角形数组中的每个三角形,如果该三角形需要继续插入点,执行Step 4,否则转向下一个三角形,直至判断完所有三角形。
Step4 获取该分块内的DEM数据点,计算分块内数据点的误差,找出距离该三角形所在平面距离最大的点,如果大于指定的分辨率,则将该点作为待插入点,通过算法,判断该点所在的三角形,向该三角形中插入该点,并进行局部优化。
3.2Delaunay三角网的优化
Delaunay三角网构网时必须满足两个性质:空外接圆特性以及最小角最大原则。本文根据上文设计的数据结构采取以边为单位的优化方案,方法是判断以公共边的两个三角形的对角和是否大于180°,若是则满足该规则,否则进行对角线交换(可以证明仅此条件即可满足Delaunay三角形特性),生成新边进入边链表,将新生成的两个三角面插入面链表,删除原来的边和面。如图4所示。
3.3误差计算
本文采用由Blow于2000年提出的误差嵌套球算法[10]计算不规则三角网的视点无关误差。不规则三角网的视点无关误差可由公式(3)计算,其中的d(Cj)的范围由误差嵌套球确定。对于一特定物理点来说,其投影误差和实际视点无关误差成正比,而且其距视点越远,投影误差越小。因此其计算公式为:
其中,Pi为包围球中心点,e为视点。λ为投影系数,是实际物体尺寸在投影空间投影变换后的放大倍数。求出视点无关误差后,就可以和阈值相比较,大于则插入该点,小于则进一步扩大包围球范围。
这是对于一特定物理点的计算方式,对于四叉树上的一个节点,经过分析,可认为它是一个半径Ri的球,也就是计算球上最大的投影误差值。该球距视点的最小距离为‖Pi-e‖-Ri,该球最大的视点无关绝对误差为S(Ci),其投影误差计算公式为:
对于该节点继续细分的条件是:
其中,k=τ/λ,在具体的细化过程中是常量。经过(5)式的优化,算法可以达到比较理想的计算速度。
3.4不同分块之间的误差度量
为实现视点相关多分辨率地形简化,提高多分辨率地形的简化效率,本文对四叉树的分块采用不同的误差阈值,而在同一分块内部,使用单一的阈值。图3所示的四叉树分块,不同分辨率的分块使用不同的误差阈值,这必然会使不同分辨率分块之间产生裂缝。文献[9]中给出一个分块之间拼接的方法,其主要思想是人为的在分块的每条边上添加N个边界点作为凸壳点,这些边界点可以不是原始DEM中的网格点。这种方法虽然可以解决相同大小分块之间的拼接,但是对点的选取缺少灵活性,而且无法达到最优的简化。
本文提出了一种有效的误差准则来解决不同分辨率分块之间的拼接,消除裂缝。其主要思想是在不同分辨率分块拼接时,在高分辨率分块的边缘使用低分辨率分块的误差阈值计算插入点,使不同分辨率的分块在分块边缘有相同的插入点,从而在消除不同分块间的裂缝的同时能更准确地对地形进行简化,同时使不同分辨率分块之间的过渡更平滑。如图5所示,每个圆弧区域表示具有相同的误差阈值,圆弧形区域为四叉树分块的正方形区域外接圆的一部分。
3.5四叉树分块合并
由于将点集通过四叉树分割,四叉树的每个叶子节点的情况可能不同,可能存在点集、凸壳的情况,因此可能出现点集和点集合并,凸壳和凸壳合并,凸壳和点集合并,点集和凸壳合并这四种情况。这些情况的合并较为简单,都可以归结为用凸壳技术构造合理三角形来解决。四叉树的合并是用递归的方法,从根开始自底向上先进行行块合并,再进行列块合并,最后生成整块。四叉树合并算法实际是一个递归的过程,算法描述如下:
Step1 从树根开始,如果第1子块的属性是根,将当前指针入堆栈,指针指向第1子块,递归调用合并函数,直到当前块属性为叶子为止。
Step2 从当前指针开始,如果相应根下的其它子块属性是根,当前指针入堆栈,指针指向第一个属性是根的其它子块,递归调用合并函数,直到当前根下的子块属性均为叶子为止。
Step3 当当前根的4 个子块属性全为叶子时,判断子块所分属的类型,调用相应的合并类型函数,先行后列进行合并。
Step4 从堆栈栈顶中弹出指针继续该合并过程,直到堆栈为空。
4数据结构设计
内存分配是任何LOD 简化算法中必须考虑的重要问题,合理的数据结构设计可以优化内存使用和提高算法执行效率。对于基于四叉树的数据分块结构,本文着重设计了分块后的数据结构。这里的数据结构,实际上也是分块后的数据存储方式。依据前面所描述的算法过程,可知算法采用的数据结构有点、边、三角面、四叉树。点、边和三角形面是Delaunay 三角网中最常用的图元,它们的数据结构合理与否,直接影响到算法的性能。为了满足构网要求同时尽可能减小数据量,本文设计了如下的顶点和三角形结构:
(1) 点结构
(2) 边结构
(3) 三角面结构
从四叉树的数据结构定义中可以看出,不仅在块中定义了点、边、三角面链表,而且还定义了块的中心点边界以及块的误差度量值,这样定义的目的是在地形的层次细节模型中,方便地对视景体以外的地形进行裁剪和误差过渡计算,以便加快绘制速度。
5实验结果与分析
本文对算法有效性进行了验证,实验以南方某地区规则网DEM数据为基础,实验平台为P4 3.0G CPU, 内存DDR400 1GB,显卡NVIDIA GeForce 6600 128MB。软件平台为WindowsXP,Visual C++6.0和三维图形标准库OpenGL。图6显示了地形数据分块为512×512时,地形原始数据重建图与简化后的效果图,图6(a)为原始未简化时的地形重构图像,图6(b)为经本文算法简化后的实时重构图像,图6(c)为图6(b)简化结果的网格显示效果图。实验过程中视点位于地形块的中心。表1所示为利用本文算法在不同简化率下的绘制效率。在对本文算法执行效果测试中,本文还将点按平均分块和按四叉树分块两种分块方式的简化效率作了比较。表2给出了其比较结果。
通过表1可以看出,当地形不进行简化时,绘制速度非常耗时,随着简化率的提高,绘制速度也大为提高,当简化率达到96.2%时,速度提高了近46倍,图6(b)即为此种简化率下的效果。
从表2可以看出,采用不同的地形分块策略可以得到不同的速度,与平均分块算法相比,本文采用的四叉树分块由于考虑了不同层次的绘制细节,不需要详细绘制的就采用上层的分块,需要详细绘制的就采用底层的分块,从而大大提高了绘制速度。
6结论
本文对规则网格与不规则三角网相结合的混合简化算法进行了研究,提出了一种视点相关的混合结构LOD树简化算法。算法综合了基于规则网格的四叉树结构与不规则网格的TIN结构的优点,统一了大规模绘制时地算法数据结构,提高了系统的兼容性和效率,同时对基于四叉树的误差控制进行了探讨和应用,消除了分块间的裂缝,提高了视觉连续性与实时性,实验证明效果较好。
摘要：大规模地形绘制在虚拟现实等领域中有着广泛应用。针对实时场景漫游过程中对场景精度的要求,提出一种视点相关的混合结构的LOD简化算法,算法保留了四叉树结构与不规则三角网TIN(Triangulated Irregular Network)结构的优点,在宏观上以四叉树方法简化地形数据,在细节层次上使用不规则三角网表示地形,最后通过有效的误差控制原则,解决了四叉树结构分块间的连接问题。简化了算法实现,提高了算法效率,在重建速度上有了一定的提高。
关键词：混合结构,四叉树,细节层次,地形简化,虚拟现实
参考文献
[1]Peter Lindstrom,Valerio Pascueel.Visualization of Large Terrains Made Easy[C]//IEEE Visualization2001.San Diego,California,USA,2001:363-370.
[2]Hoppe H.View_dependent refinement of progressive meshes[C]//Proc.SIGGRAPH’97:189-198.
[3]李胜,刘学慧,王文成,等.层次可见性与层次细节地表模型相结合的快速绘制[J].计算机学报,2002,25(9):945-952.
[4]王海,陈国良,黄心渊.实时生成三维地形中关于DEM数据插值的探讨[J].计算机应用与软件,2008,25(2):35-56.
[5]Yuanchen Zhu.Uniform Remeshing with an Adaptive Domain:A New Scheme for View-dependent Level-of-Detail rendering of Meshes[J].IEEE Transactions on visualization and computer graphics,2005,11(3):306-316.
[6]Levenberg J.Fast View-Dependent Level-of-Detail Rendering Using Cached Geometry[C]//Proc.IEEE Visualization2002:259-266.
[7]谭兵,徐青,马东洋.用约束四叉树实现地形的实时多分辨率绘制[J].计算机辅助设计与图形学学报,2003,15(3):270-276.
[8]邓集波,洪帆.基于任务的访问控制模型[J].软件学报,2003,14(1):76-82.
[9]武玉国,等.大规模地形TIN模型的LOD算法设计与实现[J].系统仿真学报,2005,17(3):665-669.
快速绘制 篇2
1.绘制导线网的Aut oCAD命令
在绘制测量导线控制网的过程中, 需要用到的AutoCAD绘图命令主要有三个, (1) 绘制导线点 (为了增加可视性, 以圆表示导线点, 而不用点表示, 使用命令circle) ; (2) 绘制导线 (为了增加图形的整体属性, 选用多义线命令pline) ; (3) 导线点的标注 (选用command text文本命令写入) 。
在实际使用中, 可以简化使用命令别名 (即简化的命令名称) 。上述三个命令的命令别名分别是: (1) 圆:_c; (2) 多义线:_pl; (3) 文本:_text。
为便于理解、并保证在Excel中正确编辑AutoCAD命令清单, 有必要了解这3个命令在AutoCAD中的运行过程 (以下示例是3个命令在AutoCAD命令窗口中的运行过程) 。
(1) 命令:＿c CIRCLE。
指定圆的圆心或[三点 (3P) /两点 (2P) /相切、相切、半径 (T) ]:13013.183, 12155.109;指定圆的半径或[直径 (D) ]<5.0000>:5
(2) 命令:＿pl PLINE。
指定起点:12803, 12154.274, 当前线宽为0.0000;指定下一个点或[圆弧 (A) /半宽 (H) /长度 (L) /放弃 (U) /宽度 (W) ]:12803, 11852;指定下一点或[圆弧 (A) /闭合 (C) /半宽 (H) /长度 (L) /放弃 (U) /宽度 (W) ]:11901, 11852;指定下一点或[圆弧 (A) /闭合 (C) /半宽 (H) /长度 (L) /放弃 (U) /宽度 (W) ]:*取消*
(3) 命令:＿text。
当前文字样式:Standard, 当前文字高度:10.0000;指定文字的起点或[对正 (J) /样式 (S) ]:12410.163, 12622.599;指定高度<10.0000>:10;指定文字的旋转角度<0>:0, 输入文字:GPS47。
2.在Excel中编辑Aut oCAD绘图命令清单
主要分为五个步骤。
(1) 步骤1:整理测量坐标值。
在Excel工作表中, 首先建立坐标值数据表, 具体格式为:点号、纵坐标、横坐标、高程、备注, 这是常规的测量坐标值表格式。
为方便下一步绘制AutoCAD命令流, 应增加1列表示合并坐标项 (X&Y) 。在该列数据域第一个单元格中输入公式“=B1&”“&C1”, 然后按住鼠标左键拖动填充句柄至所有数据域, 得到合并坐标项, 如表1所示。
(2) 步骤2:编制导线点绘制命令清单, 如表2所示。
(3) 步骤3:编制导线绘制命令清单 (如表3所示) 。
(4) 步骤4:编制点号绘制命令清单 (如表4所示) 。
(5) 步骤5:编制红线区域绘制命令清单 (如表5所示) 。
3.在Aut oCAD中快速绘制导线网
启动AutoCAD, 将Excel中编辑好的命令清单复制、粘贴在AutoCAD的命令窗口中, 即可得到完整的测量导线控制网及建筑红线范围的精确位置。
需要说明的是, 步骤2和步骤3的方式可以批量复制、粘贴数据, 并可批量绘制点位、导线, 而步骤4中在Excel编制点号绘制命令后, 直接往AutoCAD中复制、粘贴需要逐点进行, 这显得非常不方便。
但有一个变通的办法, 就可以实现批量编辑、批量绘制。那就是将步骤4中在Excel编制好的点号绘制命令直接复制、粘贴到记事本中, 在每行命令后面记得加回车换行, 然后将在记事本中编辑好的数据一次性复制、粘贴到AutoCAD命令窗口中, 即可一次性全部绘制出所有的导线网点号了。详见表6所示。
另外, 还有一个小技巧:在记事本中编辑好数据后, 在每个点号 (如GPS45) 前, 通过键盘敲入1～2个空格, 然后再整体复制、粘贴, 将会得到更为理想的效果, 点号与点位分开了!
最后, 可根据需要再添加上简易的地貌、方向等信息。最终效果如图1所示。
4.结论
利用Excel与AutoCAD进行测量导线控制网的快速绘制这一方法是比较实用、方便的, 该方法同时也可以用于三角网、曲线测设、施工放样、点之记等的快速批量绘制。
参考文献
[1]Excel Home.Excel实战技术精粹[M].北京:人民邮电出版社, 2007.
CDR快速绘制雨伞的方法 篇3
我们先来看看制作出的效果：
下面是具体的制作方法介绍：
第一步：在CDR里面画一条直线，
CDR快速绘制雨伞的方法
，
旋转负45度，如下图
再画一个圆，全选按上下左右居中，如下图
选中两条线再选中圆，再按修剪，如下图。
快速绘制 篇4
利用Excel在AutoCAD中快速绘制点线的方法
本文介绍了利用Microsoft Excel在AutoCAD中绘制图形的简单技巧.这种方法简单易学,在实际工作中使用这种作图方法,能有效提高作业效率,节省人力物力.
作 者：苑会玲 任正毅 Yuan Huiling Ren Zhengyi 作者单位：中原油田物探公司测绘中心,河南濮阳,457001刊 名：物探装备英文刊名：EQUIPMENT FOR GEOPHYSICAL PROSPECTING年，卷(期)：200919(3)分类号：P631关键词：AutoCAD Excel 绘制点线