Xi'an Technological University
Subject: Computer Science, Software Engineering
eISSN: 2470-8038
SEARCH WITHIN CONTENT
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
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.
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.
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.
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:
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.
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.
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:
Among them a_{x}, b_{x}, a_{y}, b_{y}, a_{x}, b_{x} 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 A_{xmin}, A maximum of A_{xmax} bounding box in the projection of the x-axis minimum value is B_{xmin}, B maximum of B_{xmax}, If A_{xmin} > B_{xmax}, A and B do not intersect, if A_{xmax} < B_{xmin}, A and B do not intersect. If and only if two AABB overlap in the three axes of the projection interval, they intersect.
The AABB advantage of simple structure, easy intersection test, computationally efficient, the drawback is that the object surrounded by enough compact.
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 $$\overrightarrow{v}=(vx,vy,vz)$$ for direction ($$\overrightarrow{v}$$ is the unit vector), tear open outfit distance d for length, tectonic straight line, the parameter equation for:
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:
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=\Vert OP\times \overrightarrow{v}\Vert $$ 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=\Vert O{P}_{j}\times \overrightarrow{v}\Vert $$, 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.
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