An Improved Algorithm of the Collision Detection Based on OBB

Publications

Share / Export Citation / Email / Print / Text size:

International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science, Software Engineering

GET ALERTS

eISSN: 2470-8038

DESCRIPTION

22
Reader(s)
43
Visit(s)
0
Comment(s)
0
Share(s)

SEARCH WITHIN CONTENT

FIND ARTICLE

Volume / Issue / page

Related articles

VOLUME 3 , ISSUE 2 (May 2018) > List of articles

An Improved Algorithm of the Collision Detection Based on OBB

Geng Chaoyang * / Gao Fenli *

Keywords : Collision Detection, Detection Algorithms, Bounding Box of Direction Cylindrical

Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 3, Issue 2, Pages 44-47, DOI: https://doi.org/10.21307/ijanmc-2018-033

License : (CC-BY-NC-ND-4.0)

Published Online: 07-May-2018

ARTICLE

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.

Graphical ABSTRACT

I. THE BASIC PRINCIPLE OF COLLISION DETECTION

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.

A. Detection requirements

  • 1) Test whether there is a collision

  • 2) The position of the collision detection

  • 3) Detection distance between objects

  • 4) Prediction of the collision of the next time

II. COLLISION DETECTION ALGORITHM CLASSIFICATION AND COMPARED

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.

A. Detection algorithm based on time domain

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.

Because the algorithm time discrete characteristics, this kind of algorithm is at least the following two questions:

  • 1) Pierce the phenomenon exists.

  • 2) Missed a collision.

B. Based on space domain collision detection algorithm classification

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.

1) Based on the method of spherical bounding box of collision detection

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 1 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.

Figure 1.

Spherical bounding box

10.21307_ijanmc-2018-033-f001.jpg

2) Based on the coordinate transformation of the bounding box

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:

(1)
R={(x,y,z)|axxbx,ayyby,azzbz}

Among them ax, bx, ay, by, ax, bx 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.

As shown in figure 2, AABB intersection between the test is relatively simple, Abounding box in the projection of the x-axis minimum value is Axmin, A maximum of Axmax bounding box in the projection of the x-axis minimum value is Bxmin, B maximum of Bxmax, If Axmin > Bxmax, A and B do not intersect, if Axmax < Bxmin, A and B do not intersect. If and only if two AABB overlap in the three axes of the projection interval, they intersect.

Figure 2.

AABB bounding box

10.21307_ijanmc-2018-033-f002.jpg

The AABB advantage of simple structure, easy intersection test, computationally efficient, the drawback is that the object surrounded by enough compact.

3) Oriented bounding box (OBB) and the improvement of it

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.

As shown in figure 3, 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 v=(vx,vy,vz) for direction (v is the unit vector), tear open outfit distance d for length, tectonic straight line, the parameter equation for:

(2)
{x=ox+tvxy=oy+tvyz=oz+tvz

Figure 3.

Direction cylinder

10.21307_ijanmc-2018-033-f003.jpg

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

So the reference (2. 1) may be given to the parameter equation is line for:

(3)
{x=ox+tvxy=oy+tvyz=oz+tvz(tmintd+tmax)

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 U=OP×v traverse the parts on the maximum value umax to the radius r of the cylindrical bounding box.

So far the direction surrounded by cylindrical box has been built.

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.

This premise, given the bounding box of the collision of the cylindrical concrete algorithm as follows

  • a) 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;

  • b) 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);

  • c) Establish a empty set list Li;

  • d) 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);

  • e) For some Pij, its linear to the distance to uj=OPj×v, judge whether uj < r, if found, then turn to step 6, or turn to step 4;

  • f) Will point the triangle strips Pij connected to join set Li;

  • g) To judge the ai traverse parts all vertices are over, if it is to continue step 8, or turn to step 4;

  • h) 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.

  • i) To judge to traverse all parts of the equipment is over, if it is to continue step 10, or turn to step 2;

  • j) The end of the algorithm.

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.

III. CONCLUSION

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.

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

References


  1. Sankar Jayaram etal. VADE: A Virtual Assembly Design Environment[J]. IEEE Computer Graphics and Applications, 1999(6), on page 44-50.
    [CROSSREF]
  2. Ritchie J M, Dewar R G, Simmons J E L. The generation and practical use of plans for manual assembly using immersive virtual reality [J]. Proc Inst Mech Engrs Part B (S0954-4054), 1999, 23(6): 461-474.
    [CROSSREF]
  3. Deviprasad T, Kesavadas T. Virtual Prototyping of Assembly Components Using Process Modeling [J]. Journal of Manufacturing Systems (S0278-6125), 2003, 22(1): 16-27.
    [CROSSREF]
  4. Dewar, R.G., Carpenter, I.D, Ritchie, J.M. Simmons, J.E.L, Assembly planning in a virtual environment, PICMET ’97: Portland International Conference on Management and Technology, Portland, 1997.
  5. Jia Zhen Hong, Hui Yang, In collision detection problem [J], journal of software, 1999, 10(5): 545-551.
  6. Yu Qin Gao, 3 d space collision detection algorithm of research [D], Huazhong university of science and technology, master’s degree thesis, 2007.
    [PUBMED]
  7. Fan Zhao Hui, China root, Gao Shu Ming. Based on parallel fast collision detection algorithm [J]. System simulation journal, 2000, 12(5):548-552.
  8. Li Kang Shun, Li Yuan Xiang, Shang Ming Duan, etc. Genetic programming in the application of statistical modeling [J]. System simulation journal, 2005(7).
XML PDF Share

FIGURES & TABLES

Figure 1.

Spherical bounding box

Full Size   |   Slide (.pptx)

Figure 2.

AABB bounding box

Full Size   |   Slide (.pptx)

Figure 3.

Direction cylinder

Full Size   |   Slide (.pptx)

REFERENCES

  1. Sankar Jayaram etal. VADE: A Virtual Assembly Design Environment[J]. IEEE Computer Graphics and Applications, 1999(6), on page 44-50.
    [CROSSREF]
  2. Ritchie J M, Dewar R G, Simmons J E L. The generation and practical use of plans for manual assembly using immersive virtual reality [J]. Proc Inst Mech Engrs Part B (S0954-4054), 1999, 23(6): 461-474.
    [CROSSREF]
  3. Deviprasad T, Kesavadas T. Virtual Prototyping of Assembly Components Using Process Modeling [J]. Journal of Manufacturing Systems (S0278-6125), 2003, 22(1): 16-27.
    [CROSSREF]
  4. Dewar, R.G., Carpenter, I.D, Ritchie, J.M. Simmons, J.E.L, Assembly planning in a virtual environment, PICMET ’97: Portland International Conference on Management and Technology, Portland, 1997.
  5. Jia Zhen Hong, Hui Yang, In collision detection problem [J], journal of software, 1999, 10(5): 545-551.
  6. Yu Qin Gao, 3 d space collision detection algorithm of research [D], Huazhong university of science and technology, master’s degree thesis, 2007.
    [PUBMED]
  7. Fan Zhao Hui, China root, Gao Shu Ming. Based on parallel fast collision detection algorithm [J]. System simulation journal, 2000, 12(5):548-552.
  8. Li Kang Shun, Li Yuan Xiang, Shang Ming Duan, etc. Genetic programming in the application of statistical modeling [J]. System simulation journal, 2005(7).

EXTRA FILES

COMMENTS