Octree-based hierarchial distance maps for collision detection

被引:0
作者
Jung, D
Gupta, KK [1 ]
机构
[1] SIMON FRASER UNIV, SCH ENGN SCI, BURNABY, BC V5A 1S6, CANADA
[2] FANUC ROBOT, ROCHESTER, MI 48309 USA
来源
JOURNAL OF ROBOTIC SYSTEMS | 1997年 / 14卷 / 11期
关键词
D O I
10.1002/(SICI)1097-4563(199711)14:11<789::AID-ROB3>3.0.CO;2-Q
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
Discretized distance maps have been used in robotics for path planning and efficient collision detection applications in static environments. (1) However, they have been used at the finest level of resolution, thereby making them memory intensive. In this article, we propose an octree-based hierarchical representation for discretized distance maps, called Octree Distance Maps (ODM), and show its use in efficient collision detection. To the best of our knowledge, ours is the first work to consider the use of hierarchical distance maps for collision detection. ODM representation achieves an advantageous compromise between array-based distance maps and ordinary octrees. Compared to the former, ODM requires a fraction of the memory at the expense of somewhat slower collision detection. Compared to the latter, ODM requires slightly more memory but provides a significant improvement in collision detection. ODM is similar to the quadtree distance transforms used in image representation(2) but differs significantly in various aspects of distance representation and its use in collision detection since the main motivation behind ODM is efficient collision detection instead of image representation. We then present algorithms for (1) creating an ODM from an octree, and (2) for efficient collision detection based on an ODM. Extensive experiments are then presented and compared with octree-based collision detection. Our experimental results quantify the advantageous compromise achieved by ODM representation. (C) 1997 John Wiley & Sons, Inc.
引用
收藏
页码:789 / 806
页数:18
相关论文
共 50 条
[41]   Octree-based approach to real-time collision-free path planning for robot manipulator. [J].
Hamada, K ;
Hori, Y .
AMC '96-MIE - 1996 4TH INTERNATIONAL WORKSHOP ON ADVANCED MOTION CONTROL, PROCEEDINGS, VOLS 1 AND 2, 1996, :705-710
[42]   Neurosurgical simulation system with Octree-based implicit volume modeling [J].
Shimizu, Mayumi ;
Itano, Tomoya ;
Nakamura, Yasuaki .
WMSCI 2005: 9TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL 4, 2005, :421-426
[43]   Octree-Based Finite Element Method for Electromagnetic Scattering Problems [J].
Jackson, Seth A. ;
Vouvakis, Marinos N. .
2010 IEEE ANTENNAS AND PROPAGATION SOCIETY INTERNATIONAL SYMPOSIUM, 2010,
[44]   Octree-Based Mascon Model for Small Body Gravity Fields [J].
Rathinam, Arunkumar ;
Dempster, Andrew G. .
JOURNAL OF GUIDANCE CONTROL AND DYNAMICS, 2019, 42 (11) :2557-2567
[45]   Octree-based fusion for realtime 3D reconstruction [J].
Zeng, Ming ;
Zhao, Fukai ;
Zheng, Jiaxiang ;
Liu, Xinguo .
GRAPHICAL MODELS, 2013, 75 :126-136
[46]   Octree-Based Generation and Variation Analysis of Skin Model Shapes [J].
Yacob, Filmon ;
Semere, Daniel ;
Nordgren, Erik .
JOURNAL OF MANUFACTURING AND MATERIALS PROCESSING, 2018, 2 (03)
[47]   Progressive geometry encoder using octree-based space partitioning [J].
Peng, JL ;
Kuo, CCJ .
2004 IEEE INTERNATIONAL CONFERENCE ON MULTIMEDIA AND EXP (ICME), VOLS 1-3, 2004, :1-4
[48]   Octree-based obstacle representation and registration for real-time [J].
Kim, Jaewoong ;
Kim, Daesik ;
Seo, Junghyun ;
Lee, Sukhan ;
Park, Yeonchool .
ICMIT 2007: MECHATRONICS, MEMS, AND SMART MATERIALS, PTS 1 AND 2, 2008, 6794
[49]   A novel algorithm for collision detection based on octree of adaptive subdivision and encoding [J].
Bao, Yi-Dong ;
Wu, Dong-Mei .
Shanghai Jiaotong Daxue Xuebao/Journal of Shanghai Jiaotong University, 2015, 49 (08) :1114-1122
[50]   An octree-based immersogeometric approach for modeling inertial migration of particles in channels [J].
Xu, Songzhe ;
Gao, Boshun ;
Lofquist, Alec ;
Fernando, Milinda ;
Hsu, Ming-Chen ;
Sundar, Hari ;
Ganapathysubramanian, Baskar .
COMPUTERS & FLUIDS, 2021, 214 (214)