R-函数表示的几何形体间最近距离计算

彭扬平; 黄正东; 谭娟; 刘云华

doi:10.13433/j.cnki.1003-8728.2016.0904

R-函数表示的几何形体间最近距离计算

doi: 10.13433/j.cnki.1003-8728.2016.0904

1.
华中科技大学机械科学与工程学院, 武汉 430074;
2.
武汉理工大学华夏学院机电工程系, 武汉 430223

基金项目:

国家自然科学基金项目（51475186，61173115，51375186）资助

详细信息

作者简介:
彭扬平(1984-),博士研究生,研究方向为CAD和机械优化设计,peckham@126.com

通讯作者:
黄正东(联系人),教授,博士生导师,zdhuang@hust.edu.cn

计量
- 文章访问数: 197
- HTML全文浏览量: 29
- PDF下载量: 7
- 被引次数: 0
出版历程
- 收稿日期: 2014-07-22
- 刊出日期: 2016-09-05

Calculating Minimum Distance between Geometric Objects Represented with R-functions

1.
School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China;
2.
Department of Mechanical and Electronic Engineering, Wunhan University of Technology, Wuhan 430223, China

摘要

摘要: 几何形体间最近距离在机器人、游戏动画及装配仿真等领域有着广泛应用。现有的研究大部分需要将形体分解离散成若干个凸多面体的集合，用于近似原模型。对于具有曲面的形体，利用这些方法通常不能找到它们间最近距离的准确解。引入了一种几何形体R-函数表示法。通过该方法并结合形体的几何信息及Constructive Solid Geometry（CSG）信息，将它用单个形如g（x）≤0的隐式不等式表示；根据形体的隐式不等式，给出形体间最近距离的非线性约束优化模型；利用已有的SQP算法，求解该优化模型而得到形体间的最近距离。为了验证本文所提出的方法，开发了形体间最近距离的求解系统R-MinDist，实例计算结果表明该方法准确有效。
- 最近距离 /
- R-函数 /
- 隐式不等式 /
- 约束优化
Abstract: The calculation of the minimum distance between geometric objects has wide applications in robotics, video games and assembly simulation. For non-convex objects with smooth curved surfaces, most of the previous studies in this area have to decompose or discretize them into sets of polyhedra as approximations of original objects. The minimum distance obtained is approximate, being not precise. To address these issues, we propose a method of geometric object representation with R-functions; with the method, a geometric object can be defined with the implicit inequality g(x)≤0 based on the object's geometrical information and its constructive solid geometry. Then, according to their implicit equality,we derive certain non-linear constrained optimization models to calculate the minimum distance between the objects. Finally, the optimization models are solved with the exiting SQP algorithm, and the minimum distance is obtained. To verify the method proposed in the paper, a system named R-MinDist is developed. The verification results show the correctness and effectiveness of the calculation results.
- minimum distance /
- R-function /
- implicit inequality /
- constrained optimization

HTML全文

参考文献(14)

[1]	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 on Robotics and Automation, 1988,4(2):193-203
[2]	朱鹏程.GJK碰撞检测算法的研究和改进[D].辽宁阜新:辽宁工程技术大学,2007 Zhu P C. Research and improvement of GJK collision detection[D]. Liaoning Fuxin: Liaoning Technical University, 2007 (in Chinese)
[3]	Chang J W, Choi Y K, Kim M S, et al. Computation of the minimum distance between two Bézier curves/surfaces[J]. Computers & Graphics, 2011,35(3):677-684
[4]	Mirtich B. V-Clip: fast and robust polyhedral collision detection[J]. ACM Transactions on Graphics, 1998,17(3):177-208
[5]	Bartoň M, Hanniel I, Elber G, et al. Precise Hausdorff distance computation between polygonal meshes[J]. Computer Aided Geometric Design, 2010,27(8):580-591
[6]	Shapiro V. Theory of R-functions and applications: a primer[R]. Technical Report TR91-1219. Ithaca, New York: Cornell University, 1991
[7]	刘金义,张红玲.R-函数理论介绍及其应用评述[J].工程图学学报,2001,22(2):114-123 Liu J Y, Zhang H L. An introduction to theory of R-functions and a survey on their applications[J]. Journal of Engineering Graphics, 2001,22(2):114-123 (in Chinese)
[8]	Shapiro V. Semi-analytic geometry with R-functions[J]. Acta Numerica, 2007,16:239-303
[9]	史晓冉.μ基的应用-空间曲线奇异点的计算及有理曲面的隐式化[D].合肥:中国科学技术大学,2012 Shi X R. Applications of μ-bases-Computing the singularities of rational space curves and implicitization of rational surfaces[D]. Hefei: University of Science and Technology of China, 2012 (in Chinese)
[10]	Dobkin D, Guibas L, Hershberger J, et al. An efficient algorithm for finding the CSG representation of a simple polygon[J]. Algorithmica, 1993,10(1):1-23
[11]	Kim Y S, Wilde D J. A convergent convex decomposition of polyhedral objects[J]. Journal of Mechanical Design, 1992,114(3):468-476
[12]	Shapiro V, Vossler D L. Separation for boundary to CSG conversion[J]. ACM Transactions on Graphics, 1993,12(1):35-55
[13]	Buchele S F, Crawford R H. Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations[J]. Computer-Aided Design, 2004,36(11):1063-1073
[14]	Rvachev V L. On the analytical description of some geometric objects[J]. Reports of Ukrainian Academy of Sciences, 1963,153(4):765-767 (in Russian)