<figure><img src="image_1.png" /></figure>

HAL
open science

# A Collision Detection-Based Wandering Method for Equipment Deploy Scene in Land Reclamation Area of Mining Dump

Juncheng Ma, Daoliang Li, Yingyi Chen, Li Li, Fei Gao, Lingxian Zhang

► To cite this version:

Juncheng Ma, Daoliang Li, Yingyi Chen, Li Li, Fei Gao, et al. A Collision Detection-Based Wandering Method for Equipment Deploy Scene in Land Reclamation Area of Mining Dump. 5th Computer and Computing Technologies in Agriculture (CCTA), Oct 2011, Beijing, China. pp.455-460, 10.1007/978-3-642-27281-3_51. hal-01351846

HAL Id: hal-01351846

https://inria.hal.science/hal-01351846

Submitted on 4 Aug 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Collision Detection-Based Wandering Method for
Equipment Deploy Scene in Land Reclamation Area of
Mining Dump

Juncheng Ma¹, Daoliang Li¹, Yingyi Chen¹, Li Li¹, Fei Gao¹,², Lingxian Zhang¹*

1.College of Information and Electrical Engineering, China Agricultural University,
Beijing 100083, China

2. College of Information, ShanDong Agricultural University, Tai’an 271018, China

**Abstract:** Aiming at developing a simple and efficient collision detection method to support the wandering in equipment deploy scene in land reclamation area of mining dump. This paper presents an efficient algorithm for collision detection in the waste dump land reclamation equipment deploy scene using a bounding volume nestification which consists of an oriented bounding boxes (OBBs) enhanced with axially aligned bounding boxes (AABBs). This approach combines the compactness of OBBs and the simplicity of AAABBs. The majority of distant objects are separated using the simpler AAABB tests. The remaining objects are in close proximity, where OBBs test is needed to detect. Implementation results show that our algorithm achieves considerable speedup in most cases.

**Keywords:** Collision Detection; Bounding Volume nestification; OBBs; AAABBs

1. Introduction

With the development of virtual techniques, collision detection is widely used in areas
such as robotics, computer graphics, animation, computer games, virtual reality,
simulation and haptic rendering (Tomas Möller, 2002). The application of collision
detection technique can improve the authenticity of 3D scene and avoid the
phenomenon of go through a wall or go into the land when come into buildings and

* Corresponding author, Tel: +86-10-62737741, Fax: +86-10-62737741, Email: zlx131@163.com
slopeland. There are many collision detection algorithms with different characteristics, but they all face the same problem: how to improve the real time and accuracy of detection.

The topographic condition of the waste dump is complicated with several sloping land that emerged in stair distribution and there are many pits and ditches. During the land reclamation monitoring of the waste dump, a large number of monitoring equipment is deployed which is irregularly shaped, of small size and easy neglected. Thus, a collision detection algorithm that is both real time and accurate is badly need in the wandering of the waste dump land reclamation equipment deploy scene.

Bounding volumes algorithm has proved to be the most widely used in contemporary systems. In this method, a simple bounding volume with slight volume is occupied to bound the complicated object, then the intersect test of the objects is carried only when the bounding volumes overlap. The bounding volumes that are widely used are Spheres, axially aligned bounding boxes (AABBs), oriented bounding boxes (OBBs) and discrete orientation polytopes (k-DOP)(J.A. Corrales,2011).

<figure><img src="image_3.png" /><figcaption>Fig.1.Two-dimensional sketch map of bounding boxes</figcaption></figure>

Spheres andABBs allow the simplest overlap tests while OBBs and K-DOP fit volumes more tightly(Jung-Woo Chang et al, 2010). In this paper, we propose a bounding volumes nestification based on conventional approach that combines the simplicity of AABBs and the compactness of OBBs to produce an efficient algorithm.

## 2.Related work

Research about collision detection problems started from the 1970s, after thirty years of research, domestic and foreign scholars in the field of collision detection have done a lot of work, formatting some of mature technology. Space decomposition method
and the hierarchical bounding volumes method became the most widely used method
in collision detection for two Geometries.

In Space decomposition method, the entire virtual space is divided into a small
volume of the cell, only applying intersection test to the same cell or adjacent cells of
the geometric object. typical examples of Space decomposition is kd-tree (JLBenile,
1975), octree (H. Nobor et al, 1989), BSP tree (B. Nayl et al, 1990), tetrahedral mesh
and the regular grid and so on. Space decomposition method is usually applied to the
collision detection for more evenly distributed geometric object between the in sparse
environment. In 1976, Clark put up with bounding techniques, characterized by the
simplicity and compactness (J.M.Snyder, 1995). The basic idea is to use slightly
larger size but geometrically simple bounding box to give an approximate description
of complex geometric objects (I.J.Palmer, 1995), Axis-Aligned Bounding Boxes (A.
Smith et al, 1995), and oriented Bounding Box (Gottschalk, 1996) and so on. With
further studies, many new algorithm were proposed, such as fixed direction hull(Wei
Yingmei, 2000) object-oriented collision detection method(Wang Zhaoqi et al, 1998).

In practice, collision detection was widely used in many areas. Kuan-Chen Lai et al (2009) applied the collision detection techniques to virtual construction stimulation. He proposed VC-COLLIDE method that support real-time rendering and effectively reduced the collision detection computation. Ehsan Arbabi et al (2009) proposed two kinds of collision detection methods for medical diagnosis and surgical planning. Many scholars improved the conventional method to meet the need of all kinds of need. Jung-Woo Chang (2009) proposed triangle-triangle intersection test algorithm based on the OBB bounding box. Jung-Woo Chang (2010) proposed a OBB-sphere bounding volume hierarchy and experiment 5 potential separating axes for OBBs.

3. Collision detection algorithm method for equipment deploy scene

Based on the characteristics ofABBs and OBBs, the topographic condition of the
waste dump and the character of the equipment, this paper presents a bounding
volumes nestification of AABBs and OBBs. The basic idea is: two levels of bounding
volumes are set for the object, the outer bounding volume choose the bounding
volumes that allow the simplest overlap tests while the inner bounding volumes select
the volumes that fit the object more tightly. When the intersect test occurs, the outer
bounding volume whose intersect test is simple is used to detect preliminarily so that
the majority of distant objects are separated. The remaining objects are in close proximity where the OBBs are used to be tested. This approach combines the compactness of OBBs and the simplicity of AABBs so that the overlap calculation is less and the efficiency is improved.

When the nestification on the equipment is constructing, because of the poor compactness of AABBs and the slender shape of the equipment, the nestification of AABBs and OBBs still exist a lot of space at the. Consequently, the algorithm is divided to 3 steps to ensure the accuracy.

### (1) AABBs-AABBs overlap test

This test is very simple due to the construction of AABBs, only when the two shadows overlap that the two AABBs cast on the three coordinate axes, the two AABBs are detected intersection.

### (2) AABBs-OBBs overlap test

The AABBs can be seen as special OBBs so that the AABBs-OBBs overlap test is the same as the OBBs-OBBs: separating axis theory. If the shadows that two OBBs cast on the same axis(may not the coordinate axis), the axis is called a separating axis. If a separating axis between two OBBs exists, this two OBBs don't overlap. There are only 15 potential axes for OBBs. We take one of them to explain the test process.

<figure><img src="image_4.png" /><figcaption>Fig.2.OBB-OBB overlap test</figcaption></figure>

A, B are two OBBs, $a_i, b_i$ is half the length of the border of A, B ($i=1, 2, 3$); $A_i, B_i$ is the unit vector along the axis($i=1, 2, 3$); T is the distance of the center of A, B; L is the unit vector parallelled to the separating axis. $r_A$ is the sum of the shadows that $a_i$ cast on the direction of L, $r_B$ is the sum of the shadows that $b_i$ cast on the direction of L. We just need to compare $|T \cdot L|$ with $(r_A + r_B)$ to detect whether the two OBBs overlap.

$$r_A = \sum_{i=1}^{3} |a_i A_i \cdot L|, \quad r_B = \sum_{i=1}^{3} |b_i B_i \cdot L| \quad (1)$$
Consequently, whether the two OBBs overlap is detected by (2), L is one of the 15 separating axes.

$$|T \cdot L| > rA + rB = \sum_{i=1}^{3} |a_i A_i \cdot L| + \sum_{i=1}^{3} |b_i B_i \cdot L| \quad (2)$$

When (2) holds, the two OBBs do not overlap. Otherwise the shadows that A, B cast on the other 14 separating axes should be calculated and compared by (2) till there exists one axis that meets(2). If there is no such a separating axis, the two OBBs overlap. (Fan Xiaoping, 2011).

### (3)OBBs-OBBs overlap test

The same method in step(2) is occupied in this step. If the two OBBs overlap, the objects collide. If the two OBBs do not overlap, even though step(2) passed, the object do not collide.

## 4. Results

We have implemented our collision detection algorithm in C++ and Multigen Vega Prime API on an AMD Athlon(tm) 2.4 GHz PC with a 1.0 GB main memory.

Vega Prime is a cross-platform and extensible developing environment, which contains complete C++ API. A typical Vega prime program consist of five parts:

(1)Initialize. Invoke vp::initialize() to initialize Vega prime.

(2)Define. Create the objects that the program needed though code or ACF file.

(3)Configure. The system is configured at this stage according to the parameters set beforehand.

(4)Run loop. All the threads are occupied to render the scene.

(5)Shutdown. Free the memory and stop the threads inprocess.

MFC contains powerful application structure based on windows, and offers a large number of windows and events management function. The document/view structural framing is becoming the mainstream structural framing for developing Windows application. So we use MFC to invoke Vega Prime, which implements the virtual wandering in equipment deploy scene of Mining Dump.
<figure><img src="image_5.png" /><figcaption>Fig.3.Wandering rendering in Fuxin Haizhou dump</figcaption></figure>

During the wandering in the equipment deploy scene in land reclamation area of mining dump, viewpoint firstly contact with the ground, at the same time, collision detection occurs. When the viewpoint come into the deployed equipment, t collision detection occurs between the viewpoint and the equipment. Consequently the viewpoint can't go on wandering unless its changes its direction.

**5. Conclusions and future work**

We have presented a bounding volumes nestification of AABBs and OBBs collision
detection algorithm that uses both OBBs and AABBs bounding volumes. We have
shown how to combine the compactness of OBBs and the efficient overlap test for
AABBs. We have implemented this algorithm C++ and Multigen Vega Prime API.
Implementation results show that our nestification makes favorable speed up.

In future work, we plan to introduce a general selection model for separating axes
to further reduce the calculation amount in the OBBs-OBBs overlap test. Furthermore,
we plan to design a collision detection algorithm intelligent model. Based on different
kinds of objects, the collision detection algorithm design beforehand will be chosen.

Acknowledgement

This work was supported by Project of National Natural Science Foundation of China (40901279). The research was also financially supported by Chinese Universities Scientific Fund (Project No. 2011JS143).
Reference

1. A. Smith, Y. kitamu-ra, H. Takemura, F. Kishino. A simple and Efficient Method for Accurate Collision Detection among Deformable Polyhedral Objects in Arbitrary Motion. The IEEE Virtual Reality Annual International Symposium, 1995,2:136-145.

2. B.Naylor, J.Amanatides, W.Thibault. Merging BSP Trees Yelds Polyhedral Set (SIGGRAPH' 90 Proceedings),1990, 24(2):Operations. ACM Computer Graphics:115-124

3. Chang Jung-Woo, Kim Myung-Soo. Efficient triangle-triangle intersection test for OBB-based

4. collision detection[J]. Computers & Graphics 2009(33):235-240.

5. Ehsan Arbabi, Ronan Boulic, Daniel Thalmann. Fast collision detection methods for joint surfaces[J]. Journal of Biomechanics, 2009(42):91-99

6. Fan Xiaoping, Hou Jinrong, Liao Zhifang et al. Research on Hybrid Hierarchical Bounding Box Algorithm in Virtual Environments[J]. Journal of Chinese Computer Systems, 2011,5(5):994-997.

7. H.Noborio, S.Fukuda and S. Arimoto. Fast Interferenee Cheek Method Using Octree Representation. Advanced Robotics.1989,3(3):193-212.

8. I.J.Palmer and R.L.Grimsdale. Collision detection for animation using sphere-trees[J].Computer Graphics Forum, 1995,14(2):105~116

9. J.M.Snyder. An interactive tool for placing curved surfaces withoutinterper_etration.ACM Computer Graphics,1995,29(4):209-218.

10. J.L.Beniley. Multidimensional Binary Seareh Trees Used for Assoeiative Searehing ACM Communications.1975,18(9):509-517.

11. J.A. Corrales, F.A. Candelas, F. Torres. Safe human-robot interaction based on dynamic sphere-swept line bounding volumes Original Research Article. Robotics and Computer-Integrated Manufacturing, 2011, 27(1): 177-185.

12. Lai Kuan-Chen, Kang Shih-Chung. Collision detection strategies for virtual construction simulation[J]. Automation in Construction, 2009(18):724-736.

13. S.Gottachalk, MC.Lin, D.Manocha. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection, the Proceedings of ACM SIGGRAPH'96, 1996:171-180

14. T. Akenine-Moller, E. Hains. Real-time rendering[M]. A.K. Peters; 2002

15. Chang Jung-Woo, Wang Wenping, Kim Myung-Soo. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J]. Computer-Aided Design,2011,(42):50-57.

16. Wei Yingmei. Research on Collision Detection in Virtual Evironment[D]. National University of Defense Technology,2000.

17. Wang Zhaoqi, Zhao Qinping, Wang Chenwei. An object-oriented collision detection method and its application on distributed virtual environment. Chinese Journal of computers,1998,21(11):990-994