三维转二维（精选5篇）
三维转二维 篇1
1 引言
三维空间数据的快速获取与重建是制约3D GIS发展的瓶颈问题之一。特别是随3D GIS不断成熟及应用的深入, 许多领域 (如数字城市、房产管理) 因昂贵的三维数据获取方式而发展滞慢, 如何快速、经济的重建是实现3D GIS在各领域深入应用的关键。城市中的建筑物多为规则体, 并有对应的二维图形数据 (楼层平面图) 和高度信息, 可采用基于二维图形法的三维重建技术来获取建筑物房产单元的三维模型, 即以二维图形为底面, 按照给定高度, 自下向上“拔高”生成体模型。基于二维图形法的三维重建技术具有成本低、自动化程度高等优点。本文将研究基于二维图形法的房产单元重建, 为三维房产空间数据获取、模型构建提供快速、经济的手段。
2 二维数据预处理
以DXF格式建筑物的竣工测量图和各楼层平面结构图为基础, 生成三维数据。其中竣工测量图中的建筑物基底图 (建筑物首层) 的各拐角点坐标及其标高提供了三维数据生成所需的坐标和高程值。楼层平面结构图则提供了各楼层的结构, 依照这些楼层平面结构图可以生成每一层体的三维数据。因楼层平面结构图是示意图, 没有坐标, 需要对它们进行预处理。步骤如下:
2.1 同名控制点的选取
为了使校正后的各层平面图与基底图一致, 每一栋楼至少要选取四个同名控制点, 这四个点从基底图出发, 垂直向上延伸, 与每一个楼层平面结构图相交, 相交后产生的每一组交点即是该楼层平面结构图相对于基底图的同名控制点。
2.2 格式转换
利用ArcInfo的命令将dxf格式的楼层平面结构图转换为Coverage格式, 并剔除因格式转换而导致的数据问题, 如数据丢失、增多等, 生成规范化的楼层平面结构图。
2.3 创建控制点文件 (Coverage格式)
将四个同名控制点的坐标添加到控制点文件中。
2.4 仿射变换
利用同名控制点文件进行仿射变换。
3 体的重建
经仿射变换, 各楼层的平面图得到了校正, 校正后的每一个楼层平面结构图与基底图都具有相同的坐标系统及相关参数。以各楼层二维平面图数据来生成三维体数据过程实际上是对二维图形“拔高”的过程。“拔高”采用了文献所提出的三维拓扑重建算法。“拔高”涉及三类信息:第一类是所“拔高”层的底面信息;第二类是生成墙体所依赖的框架, 也是墙体生成的依据;第三类是所“拔高”层的顶面信息。为了获得这三类信息, 需要三张结构平面图来综合的生成所“拔高”层的三维信息:
3.1 顶图
由该层的平面结构图和上层的平面结构图叠加生成, 如果该层为最顶层, 顶图等同于该层的平面结构图, 顶图用于生成该层的顶面面片信息。
3.2 结构图
即该层的平面结构图, 结构图用于在拔高过程中生成侧面墙体。
3.3 底图
由该层的平面结构图和下层的平面结构图叠加生成。如果该层为第一层, 底图等同于该层的平面结构图, 底图用于生成该层的底面的面片信息。通过上述的步骤, 利用“拔高”算法程序, 生成一层体数据。对一栋建筑物中的每一层均采用上述方法, 可以得到整个建筑物的三维数据。最后删除重复的公共面, 这样就构建了整栋楼的三维拓扑数据。
4 实验与结论
以某小区住宅中的部分建筑物为实验数据, 进行了实验测试。利用小区的建筑物竣工测量图与《房屋建筑层高表》分别获取了三维宗地的平面结构信息和高度信息。利用SketchUp“拔高”功能生成三维模型数据。图1是多楼层三维体的“拔高”实验结果, 左图为某建筑物, 其中透明的那层为选中效果, 右图为小区多个建筑物实验结果。实验结果表明, 所使用的方法可行。
摘要：三维空间数据的快速获取与重建是制约3D GIS发展的瓶颈问题之一, 利用已有二维图形数据重建三维模型是一条经济、快捷的途径。本文以DXF的二维图形为原始数据, 将它们分为顶图、底图和结构图, 利用ArcInfo工具进行数据预处理, 利用SketchUp进行“拔高”重建三维模型数据。实验结果表明方法可行。
关键词：3DGIS,DXF数据,三维重建,SketchUp
参考文献
[1]Tao V.Data collection and 3D object reconstruction, Large-scale 3D data integration (Problems and challenges) , Bentley International User Conference, 2004.
[2]朱庆.三维地理信息系统技术综述[J].地理信息世界, 2004, 2 (3) :8-12.
[3]贺彪, 李霖, 郭仁忠, 史云飞.顾及外拓扑的异构建筑三维拓扑重建[J].武汉大学学报·信息科学版, 2011, 36 (5) :579-583.
[4]史云飞.三维地籍空间数据模型及其关键技术研究[D].武汉大学, 2009.
三维转二维 篇2
教学目标：
1、让学生体会到三维立体的魅力；
2、学生能够区别二维和三维的区别；
3、了解三维设计的过程。
教学重难点：
重点：会设计和制作三维模型，并能掌握从二维到三维的创作过程。难点：掌握从二维到三维的创作思路和方法。
教学方法：
准备多的三维图片放映，让学生们感受三维图片的影响力和魅力。教同学们制作三维剪纸。让学生们在实践中理解三维的概念和设计意义。
教学过程：
一、课前导入：
1、简单回顾上节课所学的知识点；
2、叙述前面所学习的都是二维的，不论是国画，还是剪纸等一类的民间美术，这节课带领大家进入三维立体的世界，感受更加现代化的美术特色。
二、课堂教学：
1、先放一组ppt，让同学们感受并且让同学们评述下这些作品的艺术特色。
2、教同学们制作立体的小动物剪纸，让同学们对三维物体产生浓厚的兴趣。
3、在实践当中教学生们三维的意义以及发展前景。
三、课堂总结：
1、请学生们对从二维到三维的创作思路和方法进行讨论和发言；
2、教师对本堂课所学内容进行详尽总结。
四、课后作业：
三维转二维 篇3
目前, 二维人脸识别技术已经较为成熟, 但是因为其识别率会受姿态, 光线, 人脸的表情变化等外界影响而剧降甚至无法识别。
三维人脸识别是直接提取人脸空间信息, 克服了二维人脸识别的单一方向平面投影的所产生的缺点, 提高了系统精确性和鲁棒性。
本文是基于K-L算法的PCA二维人脸识别, 对三维数据模型的人脸识别问题展开了研究。在对三维人脸模型进行人脸几何特征与纹理特征的分别提取, 进行均值化处理后, 将三维人脸模型转换到一致的状态下, 最后用Matlab实现了具有高精度有效算法的识别。
2 基于K-L变换的PCA算法的二维人脸识别
根据主元分析的原理建立的特征脸算法是目前人脸识别领域最成功的算法之一。其核心为:用一组维数少的新变量代替旧变量, 新变量要最大程度的携带旧变量的信息以便于下一步的分析。
用训练样本的数据产生矩阵, 经K-L变换后得到一组特征向量, 由主特征向量形成脸的形状称之为特征脸, 由前K个最大特征值对应的特征向量所张成的空间称为人脸子空间。任何一幅人脸图像就可以用这K个特征脸的线性组合来表示, 其加权系数即是K-L变换的展开系数。人脸识别就是将待识别人脸投影到特征空间, 根据欧氏距离确定最佳匹配。K-L变换的PCA算法的二维人脸识别的步骤如下:
(1) 求出图像特征的协方差矩阵Sx。
其中E (X) 是期望算子;N为图像空间的维数;T表示转置运算, 且SX∈IRN×N。
(2) 求出Sx的全部特征值1λ, 2λ, …, λD和对应的特征向量1u, u2, …, uD。将特征值按从大到小的顺序排列, 特征向量也按对应特征值的顺序排序。
(3) 当前d个主成分已经能够反映整个样本特征时, 就可以只取前d个主成分作为新的特征, 这时有
后面的D-d个新特征可以舍去, 从而达到降维的作用。
3 基于二维PCA的三维人脸识别算法
在K-L的二维PCA算法的基础上, 将其推广至三维, 混合纹理特征与几何特征实现三维人脸识别, 提高了人脸识别的准确度。
3.1 三维几何特征提取
获取N幅图像的几何特征坐标点。若将训练集中第i幅图像的第j个特征点的坐标记为 (xij, yij) , 则可用向量来表示训练集中第幅图像中形状的个特征点:
通过对特征点标定可得到一组向量集Si, 它由N个向量组成, 其中1≤i≤N。这样所有图像的形状最终由一个特征点向量组Si来表示, 以达到特征提取降维的效果。
本文采用最高的鼻尖及其周围10000个点作为图像的特征矩阵, 对图像进行人脸识别。
3.2 三维纹理特征提取
人脸的纹理通常是指人脸表面像素的灰度值分布信息。形状模型建立之后, 将所有的样本图像向平均形状进行纹理映射, 然后在平均形状中实现纹理的采集。这样可以消除样本图像中的人脸因位置、姿态和尺寸等差异带来的影响。对位于W (x, p) 的点进行像素灰度采集, 即得到该点的纹理信息。对平均形状中的每一个点进行相同的操作, 从而得到整幅人脸在平均形状模型中的纹理向量 (纹理图像) , t= (t1, t2, ⋅⋅⋅, tm) Tm为采集的像素个数。
3.3 建立三维人脸主动可变形模型
三维人脸主动可变形模型同时考虑人脸的几何和纹理信息, 将原始三维人脸的几何和纹理分别表示成一个几何向量和纹理向量。但是, 由于不同人脸的个性化差异, 扫描得到的三维人脸数据有很大的差别。因此, 建立三维人脸主动可变形模型.首先要对原始扫描的三维人脸数据进行规格化处理, 建立三维人脸顶点之间点对点的对齐, 以使用统一的向量形式来表示三维人脸数据。原始的三维人脸数据在经过点对点的对齐处理后, 就可以用统一的形状向量和纹理向量来表示:
其中Si, 是由第i个三维人脸顶点的三维坐标组成的几何形状向量。iT是由三维人脸几何形状向量中对应顶点的纹理R, G, B值组成的纹理向量。N是三维人脸的个数。n是构成三维人脸的顶点个数。
然后, 采用主成分分析的方法对三维人脸的形状向量和纹理向量分别进行处理, 即可建立三维人脸主动可变形模型:
其中, 向量Smodel和向量Tmodel分别表示三维人脸空间中的任意形状向量和纹理向量, 为模型的组合参数。
4 三维人脸识别Matlab实现
基于PCA算法, 我们用MATLAB编写出三维人脸识别的代码。根据数据计算其平均人脸, 根据协方差矩阵计算其特征向量, 将所有样本进行训练。读入待检测的人脸, 在对其进行几何和纹理特征矩阵分离后, 用PCA方法得到特征向量, 将此与原样本数据库中人脸进行比较, 得到较小距离的即为最佳匹配人脸。实验在CASIA的三维人脸数据库上进行。我们取其中的25个不同个体, 每个个体取20张图片。图片包含个体正面, 侧面, 具有不同的光照条件, 面部表情和姿态。
在CASIA人脸数据库中, 使用5幅训练且维数为40时, 二维PCA人脸识别的准确率为86.4%, 但是当测试图片不是标准型时或受到遮挡时, 准确率骤降到60%以下, 有时甚至无法识别成功。所以二维人脸识别在规范取样的情况下其结果才具有可信性, 但在日常生活中要取到规范样本的可行性不大。
三维PCA人脸识别在同样的情况下的准确率为89.5%, 虽然相比二维人脸识别的准确率没有较大提高, 但是三维人脸识别可以克服二维人脸识别所具有的易受外界干扰如扭转角度所带来的识别失败的缺点。
5 结论
二维人脸识别算法实现简单, 但会受到图像成像条件的影响导致识别率骤降。三维人脸包含有较二维人脸图像更多的信息, 挖掘三维人脸的有用信息, 可以在一定程度上克服二维算法中姿态和光照变化等的影响。
本文正是基于人脸识别中存在的上述问题, 提出了基于PCA的三维人脸算法, 并给出了相应的实验结果。
影响人脸识别系统性能的因素很多, 针对该套算法还有许多值得研究和改进的地方。我们在搭建的人脸识别程序的功能也需要进一步的完善和增强, 应再增加更多的样本信息, 这样就可以识别更多的待测人脸和检验算法的准确度及快速性, 同时三维人脸识别由于处理的数据量庞大, 耗时相对较长。如何优化算法, 提高运算速率, 也成为我们今后的研究学习的方向。
参考文献
[1]孔华锋, 鲁宏伟, 冯悦, 基于二维Gabor小波特征的三维人脸识别算法[J], 计算机工程, 2008年9月.
[2]王成章, 基于三维模型的人脸识别算法研究, 北京工业大学[D], 2008年5月.
[3]程自龙, 雷秀玉, 基于K-L变换 (PCA) 的特征人脸识别方法综述, 中国科技论文在线.
二维化工工艺管道图的三维重建 篇4
关键词：二维化工工艺管道图,三维重建,Object ARX
众所周知,二维化工工艺管道在绘制过程中由于自身的复杂性,存在比较大的困难。二维化工工艺管道图在施工方面确实很重要。为了让化工管道的空间结构很直接的展现在我们面前,对管道图的三维重建是很有必要的。三位重建的第一步就是要进行视图的分离,接着通过视图的匹配和最终的绘制而完成整个重建过程,在此期间,Object ARX发挥了很大的作用。
1 视图的分离与视图关系的确定
二维化工工艺管道一般是由主视图和俯视图组成,利用AutoCAD软件所绘制的二维管道图在计算机内部是作为图形存在的。对于两视图一般处于绘图坐标系下,必须把两视图转换到对应的空间投影坐标系下才能为获取并匹配二维管道的三维信息做好充分的准备。可以根据主,俯两视图长对正的投影特性,确定视图原点的位置。之后建立对应的视图坐标系,实现二维管道的视图分离。绘制在Auto CAD环境下的二维工艺管道均在同一坐标系下,通常在XOY平面内,所有的点均以(x,y,0)的格式记录。坐标变换就是将绘图坐标系下的各图元的特征点坐标转换为空间投影坐标系下的相对坐标。如图1所示就是视图分离后的坐标关系转化图。
2 视图匹配
要进行三位重建的第一步就是视图分离,但最重要的还是视图匹配,因为完全不匹配的图形,根本也无法完成三位重建。我们通过进一步对属于同一管段的两端点三维坐标的值与相应直线段进行关联处理,不至于在重构的过程中发生混乱。运用将实体赋予不同颜色用以区别匹配成功与否的方法,用这种方法可以提示用户此实体是否已匹配成功。如表1所示。
具体操作也就是将Set2中已与Setl中对应实体匹配成功的实体赋予与原选择集中其他实体不同的颜色。直到遍历完Setl中所有实体,需要检验其所有实体是否真正全部匹配成功。若匹配成功,可弹出消息框进行提示;再遍历Set2中所有实体,此时只需检验选择集内所有实体是否都已改变颜色,此种方法可以较快的遍历出Set2中存在的实体是否真正匹配,反之亦然。
3 三维管道的绘制
关于三维管道的绘制,只要前面的分离和匹配做的没有问题,再掌握一定的Object ARX就是一定没有问题的。现代社会什么都可以实现科技化和智能话,只要掌握了ARX语言,会编写相应的程序,可以将自己的三维管道的思维通过代码通过ARX编译,那就一定没有问题。其实程序本身就是串联起来的,很多时候,我们无需一句一句编写,只要稍动改变就可以了。所以说多看程序,多思考才是最主要的。
4 结论
三维转二维 篇5
关键词：三维仿真,碰撞检测,层次模型
0 引言
碰撞检测问题按运动物体所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。由于平面物体的构造都可用多边形来表示, 故其检测算法相对要简单一些;而三维物体的构造比较复杂, 所以, 其碰撞检测算法也比较困难。而由于现实的应用, 需要对真实而且复杂的现实世界实现高质量的计算机模拟。因此, 开发高效的三维空间碰撞检测技术具有重要的现实意义。
而提高碰撞检测算法的效率, 不仅仅取决于基本干涉检验算法的效率, 也与基本检测算法使用的次数有很大关系。因此, 任何对于这两方面的改进, 都能使整个碰撞检测算法的效率提高。而本文就是运用平面碰撞检测算法结合动态八叉树的三维空间碰撞检测算法, 改进了基本检测算法, 并减少其使用次数, 以此获得一种新的三维空间的快速碰撞检测算法。
1 二维碰撞检测算法结合动态八叉树算法
1.1 平面碰撞问题
近10几年来, 许多专家学者对平面碰撞问题进行了深入的研究, 并取得一些很好的结果, 提出了许多算法。而由于要研究的碰撞对象处于同一平面内, 因此, 可得到有力和巧妙的技巧, 这使得平面碰撞问题已得到很深入的研究, 并提出了很多种最优算法, 这些成熟的理论很好地解决了平面碰撞问题, 本文在这方面就不多作论述。
1.2 传统八叉树算法及其缺点
以层次模型为基础的八叉树干涉检验算法, 是一个空间非均匀网格剖分算法。它是一种表示形体的分解方法, 在复杂三维体空间表达、求解体空间中的面模型和体模型之间的位置关系等领域得到了广泛的应用。八叉树是立方单元体的一种分层表示方法, 是一种空间分割的层次数据结构, 这种表示把三维空间 (通常为正立方体空间) 递归地分成8个单元或节点。目前在八叉树结构的研究上虽然有一些成果, 但所应用的八叉树方法大多是静态表示方法。静态八叉树在碰撞检测和干涉校验等方面的效果很显著, 但其缺点也很明显:在空间方面, 主要是占用的存储空间多, 只能近似地表示形体, 不易获取形体的边界信息, 不能实时修改等;在时间及计算复杂度方面, 由于场景中三角面片数量非常庞大, 因此, 对每个三角面片进行碰撞检测, 使得计算量巨大, 而且很大部分计算的并非将要发生碰撞的关键三角面片, 使得计算的效率低下。
1.3 二维碰撞检测算法结合动态八叉树算法
1.3.1 动态八叉树的立方体表示法
动态八叉树的基本组成是基元立方体, 采用立方体的中心坐标位置和立方体的边长来描述立方体的几何信息, 如图1所示。由自定义类Cube (x, y, z, a, k) 表示基元立方体, 其中x, y, z是立方体的中心点坐标, a是立方体的边长, k是基元裂变控制按钮, 则立方体的8个顶点坐标分别为:A (x-a/2, y+a/2, z+a/2) , B (x-a/2, y+a/2, z-a/2) , C (x+a/2, y+a/2, z-a/2) , D (x+a/2, y+a/2, z+a/2) , E (x-a/2, y-a/2, z+a/2) , F (x-a/2, y-a/2, z-a/2) , G (x+a/2, y-a/2, z-a/2) , H (x+a/2, y-a/2, z+a/2) 。
有了基元立方体之后, 以它为基体, 采用自相似分解规则, 对立方体进行多级层次分解, 而实现动态八叉树碰撞检测。基元立方体产生第一次分解后, 其8个子单元的中心点坐标为:O1 (x-a/4, y+a/4, z+a/4) , O2 (x-a/4, y+a/4, z-a/4) , O3 (x+a/4, y+a/4, z-a/4) , O4 (x+a/4, y+a/4, z+a/4) , O5 (x-a/4, y-a/4, z+a/4) , O6 (x-a/4, y-a/4, z-a/4) , O7 (x+a/4, y-a/4, z-a/4) , O8 (x+a/4, y-a/4, z+a/4) 。8个子单元的边长为a/2, k是每一单元的分解控制按钮, 其初始值为false, 当该单元检测到与碰撞检测对象发生碰撞且未达到精度要求、也不是完全位于检测对象内部或外部时设为true。图2是多层次几何结构实例, 其中被填充的单元表示达到碰撞检测要求的子立方体, 该单元的k值为false, 即不再对其进行分解。
1.3.2 动态八叉树的生成方法
当基元立方体或它的子立方体检测到与检测对象发生碰撞时, 该立方体进行自相似分解。为了满足虚拟环境基本实时性要求, 采用立方体模拟检测对象。初始状态下, 基元立方体表达为Cube (x, y, z, a, k) , k=false。根据检测对象的运动范围选择参加碰撞检测的基元立方体, 与检测对象进行碰撞检测, 构造动态八叉树。动态八叉树的构造方法如下:
(1) 进行碰撞检测。选取在检测对象运动范围内的基元立方体, 根据检测对象与该立方体的碰撞情况, 如果没有发生碰撞, k值不变;如果发生碰撞, 设置k=true。
(2) 当k=false时, 该基元立方体保持静态, 结束本次循环。
(3) 当k=true时, 将其均匀分成8个子立方体。在对每个子立方体进行碰撞检测之前, 要判断它与检测对象的位置关系:完全位于对象的外部或内部, 还是其他情况。若此子立方体完全位于检测对象的外部或内部, 停止对它的检测;否则检测它是否与对象发生碰撞。检测到碰撞后, 判断它的边长是否小于精度要求, 小于精度要求, 则发出碰撞报告, 否则将其继续分解。
(4) 对每一个子立方体重复以上步骤, 直至达到精度要求为止。
1.3.3 算法基本思想
二维空间的碰撞检测算法已经很完善, 而三维空间的八叉树碰撞检测算法却存在占有存储空间巨大和运算量大的缺点, 于是, 本文提出了一种将这两种算法结合在一起的新型算法。算法基本思想是, 将三维空间中的碰撞检测对象影射到二维平面上, 然后运用成熟完善的二维平面碰撞检测算法来进行碰撞检测, 在平面上得出发生碰撞的结果后, 再进行三维空间的动态八叉树碰撞检测计算。二维平面碰撞检测算法结合动态八叉树算法的基本思想如图3所示。
(1) 将待检测对象分别影射到非平行的几个平面上, 分别生成场景的平面影射图, 并在不同的平面内部, 使用平面碰撞检测算法对检测对象进行碰撞检测, 当几个平面内任何一个平面上未检测到碰撞, 则此次循环结束, 返回重新执行 (1) 。只有当所有平面上都检测到碰撞时系统才发出碰撞报告, 并执行 (2) 。
(2) 初始化待检测对象。为了用多个基元立方体的组合来代替检测对象进行碰撞检测, 并且尽量避免出现半个立方体, 首先将检测对象最大的长宽高数值找出来并整数化, 然后取它们的最大公约数作为立方体的边长。因为基元立方体很多, 为了减少运算量, 根据检测对象的运动轨迹、范围来选取参加碰撞检测的立方体, 只检测在检测对象运动范围内的立方体, 将那些不在检测对象运动范围内的立方体排除。
(3) 立方体由八叉树动态表示。在立方体未检测到与检测对象发生碰撞之前, 被静态地表示为一个立方体, 当检测到与检测对象发生碰撞时, 它将被均分为8个子立方体, 然后检测每个子立方体是否与检测对象发生碰撞, 再将发生碰撞的子立方体8均分, 未发生碰撞的子立方体停止分解。当出现下面3种情况之一时, 停止这一子单元的递归, 不再对其继续进行分解: (1) 当该子立方体已经裂变得足够小, 即它的边长达到所要求的精度时; (2) 当该子立方体完全位于检测对象的外部时; (3) 当该子立方体完全位于检测对象的内部时。当待检测对象的外形不太复杂, 或比较有规律时, 根据子立方体8个顶点的坐标很容易判断出它与待检测对象的具体位置关系。如此循环下去直到所有递归全部停止为止。在碰撞检测过程中, 根据检测对象的运动状态及系统的精度要求来设置时间段, 在每一时间段检测一次碰撞情况, 对八叉树结构刷新一次, 使得八叉树结构总处于变化中, 从而实现动态的碰撞检测。由上述算法, 得出算法流程图, 如图4所示。
2 实验及结果分析
碰撞检测问题是确定不同的物体在空间是否占有相同区域的问题。同时碰撞检测问题不仅仅归结为一般的求交问题, 针对不同的应用对象, 碰撞检测问题涉及到检测方法的复杂性、检测算法的可靠性和效率等, 不同的检测算法具有不同的特点和面向不同的应用对象。而本文提出的二维平面碰撞检测结合动态八叉树算法, 其本身应用的对象是外表面不太复杂的对象, 而由于运用影射到平面, 用平面上的碰撞检测算法先预处理三维碰撞检测, 这就极大地减小了计算的复杂性, 而且八叉树是在平面上得出碰撞的结论之后才生成, 且范围限制在对象的运动范围之内, 这样就大大减少了基元立方体的数量, 彻底地降低了运算规模, 大大降低了空间占用率。另外, 在判断两个基元立方体是否发生碰撞上, 本算法只通过各顶点坐标间的关系来判断, 而不需要向普通八叉树算法那样大量计算三角面片的距离, 这样更是降低了算法的计算复杂性, 大大提高了算法效率。
算法针对外表不太复杂的对象, 而算法在复杂性、空间占有率及效率方面, 都优于传统八叉树算法, 而在算法可靠性即判断碰撞的准确性上略差于它, 因此, 检验本算法的可靠性成了至关重要的一点。而下面的算例中, 本算法将与传统的碰撞检测算法在可靠性方面做一番比较。这种传统的算法是一种基于体模型的碰撞检测算法, 它在默认的情况下, 在某个视角中, 用规则的几何形体来逼近或替代检测对象。由于它的可靠性受视角的影响很大, 因此, 在实验中, 本文选取了3个不同视角分别进行测试。实验中一个检测对象为立方体, 边长固定为10mm, 另一检测对象的边长由200mm减小到5mm, 而动态八叉树的精度设定为5mm, 即子立方体分解到边长为5mm时会停止分解。实验结果如表1。表中a表示立方体边长, p表示误差, 即算法认为发生碰撞时两个立方体之间的实际距离, p值后面括号内的数字为相对误差, 即p/a。表中结果表明, 二维平面碰撞检测结合动态八叉树算法的可靠性要优于这种传统的碰撞检测算法。
3 结束语
八叉树干涉检验算法, 是一种表示形体的分解方法, 在复杂三维体空间表达、求解体空间中的面模型和体模型之间的位置关系等领域得到了广泛的应用。而目前在八叉树结构的研究成果中, 所应用的八叉树方法大多是静态表示方法。静态八叉树在碰撞检测和干涉校验等方面的效果很显著, 但也存在着占用存储空间巨大、计算复杂等缺点。本文提出的结合二维平面碰撞算法与动态八叉树的新型算法, 即在真正发生碰撞前, 用相对简单的二维平面检测算法代替复杂的三维空间检测算法, 并且在最终的碰撞检测时, 摒弃传统的需要大量计算三角面片距离的八叉树干涉检验算法, 而用简单的空间坐标间的相互关系来判断是否发生碰撞。新算法在空间占用, 计算规模、复杂度以及算法效率上, 比传统八叉树法有了很大提高。但是, 由新算法本身所决定的是, 算法应用的对象是外表面不复杂的对象, 而且在碰撞的判断准确性上要差于传统八叉树法。笔者对解决这两方面缺点的预期方法是, 在新算法执行到运用动态八叉树进行碰撞检测时, 方法回归传统, 即用计算三角面片距离的方法代替用坐标判断的方法, 当然, 这样改动后的算法效果还有待进一步研究。
注: (1) 传统算法部分数据引用参考文献[7]
参考文献
[1]王志强, 洪嘉振, 杨辉.碰撞检测问题研究综述[J].Journal Of Soft-ware, 1999 (10) .
[2]Tetsuya U, Toshiaki O, Mario T.Collision detection in motion simu-lation[J].Computer&Graphics, 1983 (2) .
[3]Chin F, Wang C A.Optimal algorithms for the intersection and the minimum distance problems between planar polygons[J].IEEE Transactions on Computers, 1983 (12) .
[4]David Baraff.Interactive simulation of solid rigid bodies[J].IEEE Computer Graphics&Applications, 1995 (5) .
[5]Ahuja N, Nash C.Octree representations of moving objects.Computer Vision, Graphics and Image Processing, 1984 (2) .
[6]吴明华, 余永翔, 周济.采用空间分割技术的八叉树干涉检验算法[J].计算机学报, 1997 (9) .
[7]齐晓松, 胡青泥, 刘晶.基于多视角的动态八叉树碰撞检测算法[J].东华大学学报, 2006 (5) .