<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>Collision detection plays a vital role in improving the sense of immersion and realism in virtual environment. The bounding box is the most basic collision detection algorithm, The OBB intersect test tightness and can able to significantly reduce the number of bounding volume. and try to occupy less storage space. Propose a bounding box of direction cylindrical So it can be improved though surrounded objects more close, then improve the efficiency of collision detection.</p>
</abstract>

Collision detection plays a vital role in improving the sense of immersion and realism in virtual environment. The bounding box is the most basic collision detection algorithm, The OBB intersect test tightness and can able to significantly reduce the number of bounding volume. and try to occupy less storage space. Propose a bounding box of direction cylindrical So it can be improved though surrounded objects more close, then improve the efficiency of collision detection.


<div xmlns="http://www.w3.org/1999/xhtml">
<sec id="j_ijanmc-2018-033_s_001">
<label>I.</label>
<div>THE BASIC PRINCIPLE OF COLLISION DETECTION</div>
<p>Collision detection is inevitable problems about robot, animated simulation, virtual reality, The basic task is to determine the two or more objects make contact between each other whether or through Real-time and accuracy are two important requirements collision detection.</p>
<sec id="j_ijanmc-2018-033_s_001_s_001">
<label>A.</label>
<div>Detection requirements</div>
<list list-type="simple">
<list-item>
<label>
<italic>1)</italic>
</label>
<p>Test whether there is a collision</p>
</list-item>
<list-item>
<label>
<italic>2)</italic>
</label>
<p>The position of the collision detection</p>
</list-item>
<list-item>
<label>
<italic>3)</italic>
</label>
<p>Detection distance between objects</p>
</list-item>
<list-item>
<label>
<italic>4)</italic>
</label>
<p>Prediction of the collision of the next time</p>
</list-item>
</list>
</sec>
</sec>
<sec id="j_ijanmc-2018-033_s_002">
<label>II.</label>
<div>COLLISION DETECTION ALGORITHM CLASSIFICATION AND COMPARED</div>
<p>In the field of collision detection algorithm variety, there is no unified classification standards. Here are two aspects of collision detection algorithm classification: From the point of view of a time domain to points; From the point of view of the spatial domain to points.</p>
<sec id="j_ijanmc-2018-033_s_002_s_001">
<label>A.</label>
<div>Detection algorithm based on time domain</div>
<p>The detection algorithm based on the time domain from the point of view of time domain to points, collision detection algorithm can be divided into discrete collision detection algorithm and continuous collision detection algorithm of two.</p>
<p>Because the algorithm time discrete characteristics, this kind of algorithm is at least the following two questions:<list list-type="simple">
<list-item>
<label>
<italic>1)</italic>
</label>
<p>Pierce the phenomenon exists.</p>
</list-item>
<list-item>
<label>
<italic>2)</italic>
</label>
<p>Missed a collision.</p>
</list-item>
</list>
</p>
</sec>
<sec id="j_ijanmc-2018-033_s_002_s_002">
<label>B.</label>
<div>Based on space domain collision detection algorithm classification</div>
<p>Based on space domain collision detection algorithm has always been the focus of research, According to the different structure they are divided into two types: space division method and the hierarchical bounding volume method. the space division method is used for the entire sequence level division technology to realize, and the hierarchical bounding volume law is in the scene of each object of constructing the rational hierarchical bounding volume to achieve. The object bounding box test is a collision detection algorithm is widely used in a way. Common bounding volume of the bounding sphere, of AABB of OBB bounding box.</p>
<sec id="j_ijanmc-2018-033_s_002_s_002_s_001">
<label>1)</label>
<div>Based on the method of spherical bounding box of collision detection</div>
<p>Based on the method of spherical bounding box of collision detection in virtual scene, two irregular objects in motion will be the collisions between, can use the spherical bounding box method to carry on the examination, adopt corresponding measures to avoid a collision. As shown in figure <a ref-type="fig" href="#j_ijanmc-2018-033_fig_001">1</a> first to realize the dynamic pick virtual object, and then based on the actual need, for each of the virtual objects involves creating spherical bounding box. At two objects, get the distance between the two and earn two sphere of their respective radius. When testing conditions have been met, according to the spherical bounding box collision detection algorithm, judge whether the two objects has hit. If there was a collision, will conduct collision response, according to the current characteristics of the virtual object, take different response way.</p>
<figure id="j_ijanmc-2018-033_fig_001" fig-type="figure">
<h2>Figure 1.</h2>
<figCaption>
<p>Spherical bounding box</p>
</figCaption>
<img xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_fig_001.jpg" src="https://sciendo-parsed.s3.eu-central-1.amazonaws.com/6471f52c215d2f6c89db6c4d/j_ijanmc-2018-033_fig_001.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20240725T170618Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=18000&amp;X-Amz-Credential=AKIA6AP2G7AKP25APDM2%2F20240725%2Feu-central-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=a0e6d041969a3ad8f23d8cd3127fe8e456597b5cd7314836920ab744c44a84ca" class="mw-100"/>
</figure>
</sec>
<sec id="j_ijanmc-2018-033_s_002_s_002_s_002">
<label>2)</label>
<div>Based on the coordinate transformation of the bounding box</div>
<p>Axial bounding box AABB is defined as the object contains parallel to each side of the coordinate transformation of the smallest hexahedral, is the earliest application of the bounding box. AABB can be expressed as:
<disp-formula id="j_ijanmc-2018-033_eq_001">
<label>(1)</label>
<alternatives>
<graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_eq_001.png"></graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>R</mi>
<mo>=</mo>
<mo>{</mo>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>,</mo>
<mi>y</mi>
<mo>,</mo>
<mi>z</mi>
<mo stretchy="false">)</mo>
<mo>|</mo>
<msub>
<mi>a</mi>
<mi>x</mi>
</msub>
<mo>≤</mo>
<mi>x</mi>
<mo>≤</mo>
<msub>
<mi>b</mi>
<mi>x</mi>
</msub>
<mo>,</mo>
<msub>
<mi>a</mi>
<mi>y</mi>
</msub>
<mo>≤</mo>
<mi>y</mi>
<mo>≤</mo>
<msub>
<mi>b</mi>
<mi>y</mi>
</msub>
<mo>,</mo>
<msub>
<mi>a</mi>
<mi>z</mi>
</msub>
<mo>≤</mo>
<mi>z</mi>
<mo>≤</mo>
<msub>
<mi>b</mi>
<mi>z</mi>
</msub>
<mo>}</mo>
</mrow>
</math>
<tex-math>
<?CDATA \begin{eqnarray}R=\{(x,y,z)|{a}_{x}\le x\le {b}_{x},{a}_{y}\le y\le {b}_{y},{a}_{z}\le z\le {b}_{z}\}\end{eqnarray}?>
</tex-math>
</alternatives>
</disp-formula>
</p>
<p>Among them <italic>a<sub>x</sub>, b<sub>x</sub>, a<sub>y</sub>, b<sub>y</sub>, a<sub>x</sub>, b<sub>x</sub></italic> respectively is the AABB in the X, Y, Z coordinate the projection on the minimum and maximum coordinates. Calculation of the object graph respectively of RMB each element of the vertex set x, y and z coordinates of the minimum and maximum can sure, so describe a AABB only six scalar.</p>
<p>As shown in figure <a ref-type="fig" href="#j_ijanmc-2018-033_fig_002">2</a>, AABB intersection between the test is relatively simple, Abounding box in the projection of the x-axis minimum value is <italic>A<sub>xmin</sub></italic>, A maximum of <italic>A<sub>xmax</sub></italic> bounding box in the projection of the x-axis minimum value is <italic>B<sub>xmin</sub></italic>, B maximum of <italic>B<sub>xmax</sub></italic>, If <italic>A<sub>xmin</sub></italic> > <italic>B<sub>xmax</sub></italic>, A and B do not intersect, if <italic>A<sub>xmax</sub></italic> &lt; <italic>B<sub>xmin</sub></italic>, A and B do not intersect. If and only if two AABB overlap in the three axes of the projection interval, they intersect.</p>
<figure id="j_ijanmc-2018-033_fig_002" fig-type="figure">
<h2>Figure 2.</h2>
<figCaption>
<p>AABB bounding box</p>
</figCaption>
<img xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_fig_002.jpg" src="https://sciendo-parsed.s3.eu-central-1.amazonaws.com/6471f52c215d2f6c89db6c4d/j_ijanmc-2018-033_fig_002.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20240725T170618Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=18000&amp;X-Amz-Credential=AKIA6AP2G7AKP25APDM2%2F20240725%2Feu-central-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=78c194faac74b999655475dac6766911f976a45a20e047968e0130fac792c5a1" class="mw-100"/>
</figure>
<p>The AABB advantage of simple structure, easy intersection test, computationally efficient, the drawback is that the object surrounded by enough compact.</p>
</sec>
<sec id="j_ijanmc-2018-033_s_002_s_002_s_003">
<label>3)</label>
<div>Oriented bounding box (OBB) and the improvement of it</div>
<p>Oriented Bounding Box (OBB) and the improvement of its direction the Bounding Box namely OBB, is to be detected and object contains each side, it by Gottschalk put forward in 1996. OBB and AABB is the biggest difference of the direction of arbitrariness, can be the shape of the object structure characteristics of the bounding box cuboids any direction, so OBB has better tight sex. The bounding box is a very effective collision detection accelerated method, based on OBB bounding box here proposes a direction cylindrical bounding box.</p>
<p>As shown in figure <a ref-type="fig" href="#j_ijanmc-2018-033_fig_003">3</a>, direction methods of constructing the bounding box cylinder is, first choose need to tear open outfit parts in the geometric center O = (ox, oy, oz) for vertex, tear open outfit direction <inline-formula>
<alternatives>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mrow>
<mover accent="true">
<mi>v</mi>
<mo>→</mo>
</mover>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>v</mi>
<mi>x</mi>
<mo>,</mo>
<mi>v</mi>
<mi>y</mi>
<mo>,</mo>
<mi>v</mi>
<mi>z</mi>
<mo stretchy="false">)</mo>
</mrow>
</math>
<tex-math>
<?CDATA $\overrightarrow{v}=(vx,vy,vz)$?>
</tex-math>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_ieq_001.png"></inline-graphic>
</alternatives>
</inline-formula> for direction (<inline-formula>
<alternatives>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mover accent="true">
<mi>v</mi>
<mo>→</mo>
</mover>
</math>
<tex-math>
<?CDATA $\overrightarrow{v}$?>
</tex-math>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_ieq_002.png"></inline-graphic>
</alternatives>
</inline-formula> is the unit vector), tear open outfit distance d for length, tectonic straight line, the parameter equation for:
<disp-formula id="j_ijanmc-2018-033_eq_002">
<label>(2)</label>
<alternatives>
<graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_eq_002.png"></graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mrow>
<mo>{</mo> <mrow>
<mtable columnalign="left">
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>x</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>x</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>x</mi>
</msub>
</mrow>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>y</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>y</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>y</mi>
</msub>
</mrow>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>z</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>z</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>z</mi>
</msub>
</mrow>
</mtd>
</mtr>
</mtable>
</mrow> </mrow>
</mrow>
</math>
<tex-math>
<?CDATA \begin{eqnarray}\{\begin{array}{l}x={o}_{x}+t{v}_{x}\\ y={o}_{y}+t{v}_{y}\\ z={o}_{z}+t{v}_{z}\end{array}\end{eqnarray}?>
</tex-math>
</alternatives>
</disp-formula>
</p>
<figure id="j_ijanmc-2018-033_fig_003" fig-type="figure">
<h2>Figure 3.</h2>
<figCaption>
<p>Direction cylinder</p>
</figCaption>
<img xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_fig_003.jpg" src="https://sciendo-parsed.s3.eu-central-1.amazonaws.com/6471f52c215d2f6c89db6c4d/j_ijanmc-2018-033_fig_003.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20240725T170618Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=18000&amp;X-Amz-Credential=AKIA6AP2G7AKP25APDM2%2F20240725%2Feu-central-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=76a2fd4a0a011dc78e80daa64eff74632ac8dc41ff133cc9f1cfdd550140bccd" class="mw-100"/>
</figure>
<p>For the parts of the vertex P, set the line for projection, the center to the distance to O, traverse parts on all point, take the minimum and maximum tmin tmax, parameters interval [tmin, tmax]is parts of all the points on the line of projection parameters interval</p>
<p>So the reference (2. 1) may be given to the parameter equation is line for:
<disp-formula id="j_ijanmc-2018-033_eq_003">
<label>(3)</label>
<alternatives>
<graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_eq_003.png"></graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mrow>
<mo>{</mo> <mrow>
<mtable columnalign="left">
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>x</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>x</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>x</mi>
</msub>
</mrow>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>y</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>y</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>y</mi>
</msub>
</mrow>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mi>z</mi>
<mo>=</mo>
<msub>
<mi>o</mi>
<mi>z</mi>
</msub>
<mo>+</mo>
<mi>t</mi>
<msub>
<mi>v</mi>
<mi>z</mi>
</msub>
<mo stretchy="false">(</mo>
<mi>t</mi>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
<mo>≤</mo>
<mi>t</mi>
<mo>≤</mo>
<mi>d</mi>
<mo>+</mo>
<mi>t</mi>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
<mo stretchy="false">)</mo>
</mrow>
</mtd>
</mtr>
</mtable>
</mrow> </mrow>
</mrow>
</math>
<tex-math>
<?CDATA \begin{eqnarray}\{\begin{array}{l}x={o}_{x}+t{v}_{x}\\ y={o}_{y}+t{v}_{y}\\ z={o}_{z}+t{v}_{z}(tmin\le t\le d+tmax)\end{array}\end{eqnarray}?>
</tex-math>
</alternatives>
</disp-formula>
</p>
<p>Have to line said parts in disassembling movement in line in the process of the projection of range, can be used as a direction surrounded by the axis of the cylinder box. For cylindrical bounding box below the radius. For the parts of the vertex P, the P to the center O vectors, point P linear to the distance to <inline-formula>
<alternatives>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mrow>
<mi>U</mi>
<mo>=</mo>
<mrow>
<mo>‖</mo> <mrow>
<mi>O</mi>
<mi>P</mi>
<mo>×</mo>
<mover accent="true">
<mi>v</mi>
<mo>→</mo>
</mover>
</mrow> <mo>‖</mo>
</mrow>
</mrow>
</math>
<tex-math>
<?CDATA $U=\Vert OP\times \overrightarrow{v}\Vert $?>
</tex-math>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_ieq_003.png"></inline-graphic>
</alternatives>
</inline-formula> traverse the parts on the maximum value umax to the radius r of the cylindrical bounding box.</p>
<p>So far the direction surrounded by cylindrical box has been built.</p>
<p>On the current disassembling parts of the test, at first the cylinder of it to all other parts of real intersection test, find out of the collision of the parts may occur, and then use the disassembling of these parts for accurate parts intersection test.</p>
<p>This premise, given the bounding box of the collision of the cylindrical concrete algorithm as follows<list list-type="simple">
<list-item>
<label>
<italic>a)</italic>
</label>
<p>Using the method of the introduction to the current disassembling parts of cylindrical bounding box structure direction, set for axis, radius for r, parts center for O, the equation with formula (2.2) said;</p>
</list-item>
<list-item>
<label>
<italic>b)</italic>
</label>
<p>The whole equipment traverse the other parts, the first part I get the ai, (the first time I = 0, after entering the steps of the time every time I since the 1);</p>
</list-item>
<list-item>
<label>
<italic>c)</italic>
</label>
<p>Establish a empty set list Li;</p>
</list-item>
<list-item>
<label>
<italic>d)</italic>
</label>
<p>To traverse parts of all ai vertex, made the first j a point Pij (the first enters, j = 0, every time you go to the process after when j since the 1);</p>
</list-item>
<list-item>
<label>
<italic>e)</italic>
</label>
<p>For some Pij, its linear to the distance to <inline-formula>
<alternatives>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline">
<mrow>
<mi>u</mi>
<mi>j</mi>
<mo>=</mo>
<mrow>
<mo>‖</mo> <mrow>
<mi>O</mi>
<msub>
<mi>P</mi>
<mi>j</mi>
</msub>
<mo>×</mo>
<mover accent="true">
<mi>v</mi>
<mo>→</mo>
</mover>
</mrow> <mo>‖</mo>
</mrow>
</mrow>
</math>
<tex-math>
<?CDATA $uj=\Vert O{P}_{j}\times \overrightarrow{v}\Vert $?>
</tex-math>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ijanmc-2018-033_ieq_004.png"></inline-graphic>
</alternatives>
</inline-formula>, judge whether uj &lt; r, if found, then turn to step 6, or turn to step 4;</p>
</list-item>
<list-item>
<label>
<italic>f)</italic>
</label>
<p>Will point the triangle strips Pij connected to join set Li;</p>
</list-item>
<list-item>
<label>
<italic>g)</italic>
</label>
<p>To judge the ai traverse parts all vertices are over, if it is to continue step 8, or turn to step 4;</p>
</list-item>
<list-item>
<label>
<italic>h)</italic>
</label>
<p>Traverse set Li, will equipment running and each of them all triangle triangle strips are surrounded by boxes to cylindrical projection on the vertical axis, precise fellowship test.</p>
</list-item>
<list-item>
<label>
<italic>i)</italic>
</label>
<p>To judge to traverse all parts of the equipment is over, if it is to continue step 10, or turn to step 2;</p>
</list-item>
<list-item>
<label>
<italic>j)</italic>
</label>
<p>The end of the algorithm.</p>
</list-item>
</list>
</p>
<p>Different types of testing methods, the characteristics of them are not the same. Surrounded by the ball and AABB close degree as flexible Oriented Bounding Box OBB, OBB was essentially a closest to the object cuboids, only the object of a cuboids’ may, according to the first moment arbitrary rotation. OBB surrounded by the ball and AABB than closer to the object, It is consistent with the direction, construction method, but the gender is poorer, the overall OBB performance than AABB surrounded the ball, OBB bounding box to the basic idea of the method is to use simple geometry instead of complicated geometry novelties, first to object bounding box for rough detection, when the bounding box intersect surrounded by its geometry can be intersection, This can eliminate a large number of impossible at the intersection of geometry and geometric part, which can quickly find at the intersection of geometric part.</p>
</sec>
</sec>
</sec>
<sec id="j_ijanmc-2018-033_s_003">
<label>III.</label>
<div>CONCLUSION</div>
<p>Direction surrounded by box of inherited the cylindrical OBB bounding box the advantages of the intersection of the test in its close the gender is good, can be significantly reduced the number of bounding volume, when some similar to the cylinder’s geometry object happened between the collision detection, OBB is a better choice, for direction surrounded by box of more suitable for cylinder for cylindrical objects geometry.</p>
<p>Can more closely, more convenient application, so as to enhance the efficiency of collision detection. after the rotary motion, only need to base the rotation of the coordinate system also can. So for the rigid body</p>
</sec>
</div>

An Improved Algorithm of the Collision Detection Based on OBB

International Journal of Advanced Network, Monitoring and Controls

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"An Improved Algorithm of the Collision Detection Based on OBB"}

Collision detection plays a vital role in improving the sense of immersion and realism in virtual environment. The bounding box is the most basic collision...

An Improved Algorithm of the Collision Detection Based on OBB

Online veröffentlicht: 07. Mai 2018

Seitenbereich: 44 - 47

DOI: https://doi.org/10.21307/ijanmc-2018-033

Schlüsselwörter
Collision Detection, Detection Algorithms, Bounding Box of Direction Cylindrical

© 2018 Geng Chaoyang et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Figure 1.

Figure 2.

Figure 3.

An Improved Algorithm of the Collision Detection Based on OBB

Online veröffentlicht: 07. Mai 2018

Seitenbereich: 44 - 47

DOI: https://doi.org/10.21307/ijanmc-2018-033

SchlüsselwörterCollision Detection, Detection Algorithms, Bounding Box of Direction Cylindrical

© 2018 Geng Chaoyang et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Figure 1.

Figure 2.

Figure 3.

Schlüsselwörter
Collision Detection, Detection Algorithms, Bounding Box of Direction Cylindrical