首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 156 毫秒
1.
针对凸多面体碰撞检测问题,以直线投影法为基础对分离面投影法进行改进,提出一种采用棱线投影分离的凸多面体实时精确碰撞检测算法.首先分析了凸多面体各种相对位置关系并提出了投影分离线的概念,针对凸多面体的各种分离情况证明投影分离线的存在;其次选取凸多面体相向面上的棱集构造准投影分离线,通过沿着准投影分离线方向投影可将3D凸多面体碰撞检测降维为2D凸多边形的碰撞检测问题;最后将分离投影的思想延用至为2D凸多边形的碰撞检测,再次将2D问题降维为1D问题.算法分析和实验结果表明,该算法对于凸多面体碰撞检测具有较高的响应速度和检测精度.  相似文献   

2.
该文提出一种将任意多面体剖分为四面体的算法,该算法首先依据顶点凸凹性算法判定多面体顶点的凸凹性性质,再寻找符合剖分条件的凸顶点,将该凸顶点的凸空间从原多面体中剖分出去,得到一个新的多面体,剖分出来的凸空间再分为多个四面体;再重复对新的多面体进行剖分,直到剖分完毕。该算法的平均时间复杂度为O(N+M),其中N为多面体的凸顶点数目,M为多面体的凹顶点数目。  相似文献   

3.
提出了一种基于最短距离计算的凸多面体碰撞检测算法。该算法利用凸多面体三维空间顶点坐标的凸包表示凸多面体,将两个凸多面体间碰撞检测问题归结为一个带约束条件的非线性规划问题,采用混合人工鱼群算法对该问题进行求解,寻优过程前期利用人工鱼群算法快速找到全局极值的邻域,后期切换到模式搜索法,准确找到全局极值。实验表明,无论在计算精度还是在计算速度方面,混合人工鱼群算法比惩罚函数法和遗传算法有更加明显的优势,能够满足碰撞检测的实时性和精确性的要求。  相似文献   

4.
凸多面体快速碰撞检测的投影分离算法   总被引:1,自引:0,他引:1  
为了有效地提高凸面体之间的碰撞检测效率,提出一种凸多面体快速碰撞检测的投影分离算法.该算法通过判断2个凸多面体在中心线上的正投影不相交,或者分别构造它们的准投影分离面集合,并从这2个集合中找到一个投影分离面,来判断2个凸多面体分离;否则,判断为相交.对于2个准投影分离面集合,依次交替地判断它们的每一个面是投影分离面还是相交面,以加快2个凸多面体相交检测.计算复杂度分析和数值实验表明:该算法平均检测效率高于其他检测算法.  相似文献   

5.
该文提出了约束曲面和约束最大空球凸多面体的概念,在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法,该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分,然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分,利用约束Delaunay四面体剖分算法,该文进一步设计了一种三维物体表面重建算法。  相似文献   

6.
一个快速通用的多面体隐藏线消除算法   总被引:1,自引:0,他引:1  
隐藏线消除是加快图形明暗描绘的一种重要方法,传统的隐藏线消除算法无法满足复杂多面体或场景的明暗描绘的要求,文中提出了一种快速通用的多面体隐藏线消除算法,它适用于单个凹多面体、单个凸多面体以及由多个凹多面体或凸多面体组成的场景的隐藏线消除。  相似文献   

7.
本文研究求成对线性规划问题的组合最优解的算法,巧妙地将问题的求解转化成了求西凸多面体间的距离,并给出了求两凸多面体间距离的快速算法,以该算法为核心,一系列的成对线性规划问题的组合最优解的均能在O时间内求得。  相似文献   

8.
一个直接计算多面体之间距离的快速算法   总被引:1,自引:1,他引:0  
秦志强  熊有伦 《机器人》1996,18(1):1-6,10
在机器人离线编程及仿真系统中,如何快速确定多面体之间的距离对无碰路径规划,细微运动规划和装配运动规划都有十分重要的意义,本文介绍了通用的机器人离线编程及仿真系统HOLPSS中计算多面体之间距离的一个有效算法。该方法通过直接计算凸多面体部分棱边之间的距离来确定多面体之间的距离,并利用J0函数来判别空间直线段与凸多面体是否有交。  相似文献   

9.
为了进一步提高碰撞检测的实时性,提出一种基于Minkowski和的多面体快速碰撞检测算法.该算法以Minkowski和为工具,无需精确计算两个多面体之间的最短距离,首先通过构造两个多面体的Minkowski和,将多面体碰撞检测问题转化为判断原点是否在该Minkowski和内,然后运用射线和求交计算将三维空间问题转化为二维平面问题,再通过判断原点是否在平面多边形内来检测多面体是否发生碰撞,进而提高了碰撞检测的实时性和可靠性.在Visual C#环境下,利用OpenGL图形库搭建一个路径规划仿真系统.实验结果表明,该算法平均检测效率明显高于传统算法,并且有效降低了存储空间和时间复杂度.  相似文献   

10.
判断两个凸多面体是否相交的一个快速算法   总被引:14,自引:0,他引:14  
在机器人路径规划中,碰撞检测算法占有十分重要的地位.在智能机器人仿真系统中,碰撞检测耗用的时间在整个路径规划过程所用时间中占有相当大的比例.于是,如何进一步提高碰撞检测的速度在智能机器人路径规划系统中就起到了非常关键的作用.而碰撞检测问题最终转化为判断三维空间中两个凸多面体是否相交的问题.就这一问题,给出了一种新的算法,其思想是取一个从一个凸多面体指向另一个多面体的向量,根据两个多面体中的面与这一向量的相对位置关系来寻找相交的平面.即有两个多面体的交点位于这一平面,若能找到一个相交平面则可以断定两个多面体  相似文献   

11.
Two Algorithms for Decomposing a Polyhedron into Convex Parts   总被引:1,自引:0,他引:1  
Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring-shaped faces and cavities. The time requirement in both cases is O ( DN log N ), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D + 1 convex pieces which is the minimal number of the convex components.  相似文献   

12.
基于环链的多面体剖分快速算法研究   总被引:1,自引:0,他引:1       下载免费PDF全文
利用环链提出了一种对任意多面体不添加顶点的凸剖分快速方法 ,它对多面体的剖分个数接近最少 .该方法首先从多面体的棱和对角棱所构成的所有环中 ,以最小周长选取一个最好的环 ,然后利用这个环的各个边所形成的一系列面 ,对多面体进行一次剖分 .实验证明 ,这种方法可找到对多面体不添加顶点剖分的最好剖分面 ,使剖分的次数接近最少 ,具有较好的实用价值和广泛的应用前景 .  相似文献   

13.
This paper presents a direct method to recover the geometry of the 3D polyhedron depicted in a single parallel projection. It uses two sets of information, the list of faces in the object, obtained automatically from the drawing, and a user-identified cubic corner, to compute for the coordinates of the vertices in the drawing and thus establish the 3D geometry of the whole polyhedron. The algorithm exploits the topological structure of the polyhedron, implicit in the connectivities between the faces, resulting in a complexity that is linear in the number of faces. The method is extended to objects with no cubic corners as well. The algorithm works well for recovering objects from accurate line drawings, producing accurate 3D objects. A simple extension to the algorithm allows it to handle inaccurate drawings such as sketches, and produce 3D objects that are consistent with our human perception of the drawings.  相似文献   

14.
有限元网格体绘制中的剖切算法   总被引:3,自引:0,他引:3       下载免费PDF全文
为了解决体绘制中的遮挡问题和加快复杂剖切体的剖切操作,在MS体绘制算法的基础上,研究和提出了一种体绘制中任意封闭多面体的剖切和多种变换函数,并进一步展现了数据场内部的数据分布情况,另外,由于通过二叉树对多剖切体情况下Stenceil参照值的合并,使得算法在每一切层上的绘制次数达到最少,同时还统一了剖切体前后表面Stencil操作,并减少了不必要的法线运算,从而大大加快了复杂剖切体的剖切操作。  相似文献   

15.
An algorithm is described which accepts as input the edges of a convex polyhedron, listed in any order, and which produces a consistent collection of sequences of points which describe the faces of the polyhedron as required by certain display rendering packages. The algorithm makes use of the planarity tester of Hopcroft and Tarjan and is linear, in the number of points of the polyhedron, with respect to both time and space.  相似文献   

16.
一种任意多面体剖分成四面体的改进算法   总被引:1,自引:0,他引:1  
针对原相关算法中存在的不足,提出了凸顶点的凸空间从原多面体中完整剖分出去的充要条件。引入平面切角和空间切角的概念,使剖分思想更加直观、简化。对空间多边形进行Delaunay三角剖分时,充分考虑了凸空间的结构特点,采用了透视投影的思想,使投影后的平面多面形保持了原空间多边形的拓扑结构和顶点的凹凸性,保证了三角剖分的合理性、正确性。基于空间相关性的思想,对凸顶点的邻接点生成有向空间包围盒,快速排除与凸空间不相交的面,加快了多面体剖分的速度;最后给出了改进后的剖分算法,对相关应用有着极大的实用价值。  相似文献   

17.
医学图像3维重建模型的虚拟剖切算法   总被引:8,自引:0,他引:8       下载免费PDF全文
对医学图像体数据及重构几何模型进行虚拟剖切,可以方便地看到内部的组织,便于观察和诊断,可用于医疗放射治疗规划.针对医学图像重建的表面几何模型,提出了对模型进行平面剖切、立体开窗及任意交互切割的算法.平面剖切和开窗是用剖切面或剖切体对重建模型施以剖切,在剖切面上生成边序列及顶点序列;由此边序列和顶点序列生成封闭的边界轮廓,确定各轮廓的包含关系;对封闭轮廓包围的截面区域进行Delaunay三角剖分,得到完整的剖切后的表面模型.任意交互切割过程是交互生成切割路径,确定切割边界,并沿切割边界对表面模型进行切割.实验结果证明了本文算法的有效性.采用本文算法可得到良好的虚拟剖切效果.  相似文献   

18.
A Minkowski sum is a geometric operation that is equivalent either to the vector additions of all points in two operands or to the sweeping of one operand around the profile of the other without changing the relative orientation. Applications of Minkowski sums are found in computer graphics, robotics, spatial planning, and CAD. This paper presents two algorithms for computing Minkowski sum of convex polyhedron in three space (3-polytopes). Both algorithms are improvements on current ones found in the literature. One is based on convex hulls and the other on slope diagrams. The original convex hull based Minkowski algorithm is costly, while the original slope diagram based algorithms require the operation of stereographic projection from 3D to 2D for merging the slope diagrams of the two operands. Implementation of stereographic projection is complicated which increases the computation time and reduces the accuracy of the geometric information that is needed for constructing the resultant solid. This paper reports on improvements that have been made to these two algorithms and their implementation. These improvements include using vector operations to find the interrelations between points, arcs and regions on a unit sphere for the slope diagram algorithm, and addition of a pre-sorting procedure before constructing convex hull for convex hull based Minkowski sum algorithm. With these improvements, the computation time and complexity for both algorithms have been reduced significantly, and the computational accuracy of the slope diagram algorithm has been improved. This paper also compares these two algorithms to each other and to their original counterparts. The potential for extending these algorithms to higher dimensions is briefly discussed.  相似文献   

19.
基于成功回路的凹多面体的剖分算法   总被引:1,自引:0,他引:1       下载免费PDF全文
提出了一种对任意凹多面体不添加顶点的凸剖分方法,该算法首先把凹多面体抽象为无向图,无向图的顶点为多面体的顶点,边为多面体的棱和对角棱,权值为棱或对角棱的长度,然后根据普利姆算法构造最小生成树的思想来构造一个成功回路,利用该回路对多面体进行剖分。重复执行此过程,直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分,同时可以对任意凹多面体多面体进行剖分,包括含有空洞的凹多面体。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号