An Improved Algorithm of the Collision Detection Based on OBB

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.

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 ) | a x ≤ x ≤ b x , a y ≤ y ≤ b y , a z ≤ z ≤ b z }

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.

Figure 2.

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 v → = ( v x , v y , v z ) for direction ( v → is the unit vector), tear open outfit distance d for length, tectonic straight line, the parameter equation for: (2) { x = o x + t v x y = o y + t v y z = o z + t v z

Figure 3.

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 = o x + t v x y = o y + t v y z = o z + t v z ( t m i n ≤ t ≤ d + t m a x )

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 = ‖ O P × 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;

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.