全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于非线性规划理论的凸多面体最小平移距离算法

DOI: 10.11834/jig.2006010249

Keywords: 凸多面体,最小平移距离,分离平面,实现向量,非线性规划

Full-Text   Cite this paper   Add to My Lib

Abstract:

凸多面体的最小平移距离问题一直以来都成为计算机图形学的一个研究热点.目前已有的距离算法在稳定性、可实现性、精确度和实现效率这几方面或多或少都存在一定的缺陷.为此,从最小平移距离定义出发,引入广义分离平面概念,提出一种用非线性规划求解距离问题的新算法.算法先定义一对最优广义分离平面以确定凸多面体最小平移距离;然后,将最优广义分离平面对的搜索问题等效变换为非线性规划问题;最后,用非线性优化工具软件对非线性规划问题进行求解,从而确定最小平移距离.实验结果表明:该算法能提供一个准确的距离值和实现向量,其性能优于其他同类算法;迭代次数与多面体的顶点数呈线性关系.此外,该算法只需提供顶点信息即可实现,求解过程中避免了死循环,故实现简单、可靠.因此,此算法是一种快速而有效的距离算法.

References

[1]  Lin M C,Canny J F.Fast algorithm for incremental distance calculation[A].In:Proceeding of IEEE International Conference on Robotics and Automation[C],Sacramento,USA,1991:1008 ~1014.
[2]  Bergen G,Proximity queries and penetration depth computation on 3D game objects[A].In:Proceedings of Game Developers Conference[C],San Jose,USA,2001:821 ~837.
[3]  Kim Y J,Otaduy M A,Lin M C.Fast penetration depth computation for physically-based animation[A].In:Proceeding of ACM SIGGRAPH Symposium on Computer Animation[C],New York,USA:ACM Press,2002:23 ~ 32.
[4]  Kim Y J,Lin M C,Monocha D.Incremental penetration depth estimation between convex polytopes using dual-space expansion[J].IEEE Transactions on Visualization and Computer Graphics,2004,10(2):152 ~ 163.
[5]  Ong C J.A fast growth distance algorithm for incremental motions[J].IEEE Transactions on Robotics and Automation,2000,16(6):880 ~ 890.
[6]  Shih C L,Liu J Y.Computing the minimum directed distances between convex polyhedra[J].Journal of Information Science and Engineering,1999,15 (3):353 ~ 373.
[7]  Heckbert P S.Graphics Gems Ⅳ[M],Boston:Academic Press,1994.
[8]  Bennett K P,Mangasarian O L.Neural Network Training via Linear Programming[R].TR948,Wisconsin,Madison,USA:Department of Computer Science,University of Wisconsin-Madison,1990.
[9]  Cameron S A,Culley R K.Determining the minimum translation distance between two convex polyhedra[A].In:Proceeding of IEEE International Conference of Robot and Automations[C],San Francisco,CA,USA,1986:591 ~ 596.
[10]  Gilbert E G,Johnson D W,Keerthi S S.A fast procedure for computing the distance between complex objects in three-dimensional space[J].IEEE Journal of Robotics and Automation,1988,4 (2):193 ~ 203.
[11]  Kim Y J,Otaduy M A,Lin M C.Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement[R].TR02-014,North Carolina,Chapel Hill,USA:Department of Computer Science,University of North Carolina,2002.
[12]  Zhu Xiang-yang,Ding Han,Xiong You-lun.The pseudo minimum translational distance between convex polyhedral:definitions and properties[J].Science in China (Series E),2001,31 (2):128~136.[朱向阳,丁汉,熊有伦.凸多面体之间的伪最小平移距离-Ⅰ.定义及其性质[J].中国科学(E辑),2001,31(2):128~136.]
[13]  Sridharan K.Efficient computation of a measure of depth between convex objects for graphics applications[J].Computers & Graphics,2002,26(5):785 ~793.
[14]  Yuan J.A neural network measuring the intersection of m-dimensional convex polyhedra[J].Automatica,1995,31 (4):517 ~531.
[15]  LINDO API 4.0[CP/OL].Http://www.Lindo.Com/downloads/LAPI-WINDOWS-IA32-4.0.Zip,2005-05 -23.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133