Collision detection between running bipeds

In this project, a simulation of collision detection and response between a pair of biped (football) players was developed. Same physical attributes, such as size, mass and inertia were assumed for every biped. A collision between two bipeds was defined as a continuous intersection between their torsos with respect to time. A collision ended when the torsos were separated in space. Intersections between torso and leg and between legs were not considered as a collision in this simulation. When a collision was detected, recovery processed started. Penalty forces were calculated and then applied to the torsos at the point of collision. This would cause the bipeds to eventually move away from each other, thus terminate the intersection.

I read the papers that are listed in the Reference section. The paper written by Boone, G.N and Hodgins, J.K. [1] provided some understanding about the structures of bipedal robot, and some of their limitations. The paper written by Witkin, A., Fleischer, K. and Barr, A.[2] provided some insight into handling collision recoveries with energy constraints.

Based on Ron and Victor's suggestions, I made two major changes to the physical model for the calculation of the penalty forces.

I separated position_err and velocity_err into two terms and assigned different control parameters for each term. Please see equation (1) for details. I removed the linear projection of the velocity difference between the two bipeds along the normal direction when this projection was pointing outward. Please see equation (4) for details.

I implemented the collision detection algorithm with bounding spheres. However, being not completely satisfied with the spherical approximation of the biped's torso, I attempted to calculate the collision points of any two ellipsoids with direct math formulas. Through calculations, I found that the collision point is a solution to either a polynomial of degree 6, or an equation system consists of 3 quadratic forms of 3 variables. Instead of trying to solve these equation systems using numerical methods, I came up with an approximation algorithm using the bipeds? parallel-coordinates bounding boxes. Please see equation (20)-(22) for details. I tested this approximation algorithm by writing a Visual Basic program. When I was convinced about the correctness of the algorithm, I implemented into the simulation.

I studied Inventor Programmers' Guide, and implemented the simulation to drive a biped around with the arrow keys.

After finishing coding, I ran the simulations with different user control parameters to understand the impact of these parameters. I found some interesting result, especially about the choice of control parameters that were associated with position_err and velocity_err. Please see the Analysis section for details.

What I learned from this project:

I gained some first-hand experience working on physical-based simulation and converting them into animation and video using various utilities, such as Inventor, scsetup, dmconverter, and so on.

I understand the bipeds' behaviors and limitations better, having put them on the field and seen them run and fall under various scenarios. I think controlling bipeds' behaviors can be difficult. To achieve the best visual results, it is important to have a right model for the simulation, give user enough control parameters, and take time to try different values for control parameters. Also, collecting data for analysis seemed very important.

I know more about the Animation Lab, the people working there and the work they do. I am very happy about my experience working on the project.

What I would do if given more time? Run more simulations with bipeds at various pre-defined positions. Right now, I have found collision effect that was similar to the collisions between linemen. I would like to find control parameters that could generate more bouncing, such as a collision between a defensive back and a wide receiver. Implement an energy based collision detection and response algorithm [2] and compare with the algorithm that was used here. Understand how bipeds lost their footing during the collision process, and how that could be avoided. Actually, I would like to learn more about the biped itself. Implement simulation for bipeds of different physical attributes, such as size, mass, inertia. Extend the collision detection to include torso-leg and leg-leg collisions. I think by using parallel-coordinator bounding boxes, we could detect collision between two regular geometric shapes. Learn to use camera better, maybe doing so by studying the current scsetup program and adding enhancements. Computation framework:

Since we did not use forward collision avoidance scheme, collision occurred before they were detected. The following factors were used to calculate the penalty forces.

Level of intersection: a number l that provides some geometric measure of the intersection, such as the diameter of the intersection region, or the volume of the intersection of the region. In this simulation, both measures were tested. However, volume of intersection seemed to have provided more realistic simulations. The unit normal vector N: in an ideal collision situation in which the two bipeds barely touch each other at the collision point. From multivariable calculus, we have the following relationship between the unit normal vectors of the two bipeds at the collision point.



In case the intersection forms a region, the choice of point of collision could be tricky. First, the collision point needs to be inside the region of intersection, therefore, inside each biped's torso. Second, this point should have equal "distance" to both bipeds. The definition of the distance depends on geometric models used to represent the torsos. Please see equation (17) and (20). More importantly, equation (0) needs to hold at the collision point to ensure the pair of response forces is in the exactly opposite direction.

Response forces calculations:

The following method was used:



where aand bare user control parameters, and position_err and velocity_err are vectors that represent the level of intersection and linear velocity difference between the two bipeds.

System provided us with the values of the following variables:

the center of the first biped.

the center of the second biped.

the linear velocity of the first biped at its center.

the linear velocity of the second biped at its center.

the angular velocity of the first biped.

the angular velocity of the second biped.

then, through calculations during the collision detection, we have determined the values of the following variables:

the collision point.

the level of intersection. Here we used volume of intersection.

the inward unit normal of the first biped at the collision point.

the inward unit normal of the second biped at the collision point.

and for the first and second biped respectively, we have

 

To calculate , we first need to calculate the linear velocities of both bipeds at the collision point. They are given by:


 
 Next, let us define the following variables:



Note that .

If , biped 2 is moving further toward biped 1 along the normal direction. In this case, the level of intersection is increasing and we need to apply penalty along that direction. Otherwise, biped 2 is moving away from biped 1, applying penalty along this direction would pull biped 2 toward biped 1. (This actually happened during the early simulations and Ron and Victor helped me corrected it).

Therefore, for biped 1 and 2 respectively, we have



Finally, by substituting (2) and (5) into (1), we have



Collision detection:


First, we need to determine whether collision occurred between the two bipeds. Second, if collision occurred, we need to be calculate the variables that are needed to calculate the response forces. These variables are, the collision point , the level of collision , and the inward normal vectors  and of biped 1 and 2 respectively.

 

Bounding spheres:


The bounding sphere of a biped in the scene is defined as the sphere that is concentric with the biped, and has radius of 0.44, the same of the biped?s longest half-axis. In other words, the bounding sphere of a biped is the smallest sphere that encloses the biped.

In this case, we only need to detect any possible intersection between two spheres that has the same radii. Let R be the common radius, and let D be the half distance between the centers of the two bounding spheres. Then



Therefore,



In case of a collision, the collision point is given by



and the level of collision, in this case the volume of the intersection of two spheres, is given by



and the inward normal unit vectors are given by



Parallel-coordinates bounding boxes:

Each biped in the scene is obtained by translating and rotating a pre-defined ellipsoidal-shaped object with two of its half-axes being 0.44, and the third of its half axis being 0.21. Therefore, this object has an equation of the following:



with a =b= 0.44 and c = 0.21.

Equation (12) can be rewritten as a quadratic form,

 

or, if we define



then, obtained a more compact form



For each biped in the scene, assume its center and its quaternion are as follows:



The formula is as follows:



where



Since P is an orthogonal matrix, thus



Also, from equation (17), we have the following result,



The gradient of function (17) is



The collision detection algorithm used here involves the parallel-coordinates bounding boxes. If the two bounding boxes do not intersect, with the loss of generality, let us assume the maximum y-coordinate of the first bounding box is less than the smallest y-coordinator of the second bounding box, then there is a x-z plane that completely separates the two bounding boxes. Therefore, the two bipeds do not intersect.

When the bounding boxes intersect, however, the bipeds still may not intersect. Sampling is conducted to determine whether there are points in the region that are inside both bipeds, i.e.,



Then



Because of the semi-random choice of the way thatis calculated, there is no guarantee that  and will be opposite to each other. However, when the collision region is relatively small, is very close to the real point of collision. Since the gradient functions for both bipeds are continuous, so is their sum. Since the sum is 0 vector at the real point of collision, the sum is very close to 0 at . However, we could not assume it is 0, since small error can turn into big error when multiplying b , see equation (1), causing response forces not being in the opposite direction. To compensate the difference, the following algorithm was used:



It can be easily seen that and are opposite. Therefore we are done with our calculation.

Analysis:
Applying response forces to the collision point vs. to the centers of mass.

When applying forces only to the centers of mass, I found that bipeds tend to maintain stable relative orientation, since no torque was applied during the collision. The side effect of this was that when two bipeds collide, they could not separate. Applying forces to the collision point tend to produce more realistic results.

Detecting collision using bounding spheres vs. parallel-coordinates bounding boxes.

When bipeds collided at sides, i.e., face to face, both detection algorithm produced very similar results. This is because the curvatures at a sphere?s side and those at an ellipsoid?s side are almost the same. However, when bipeds collided up and down, bounding boxes tended to produce more realistic result. This is because the curvatures at a sphere?s top/bottom and those at an ellipsoid?s top/bottom are very different.

The impact of a and b .

Contrary to my initial thought, I found b was the more dominant term than a . This is not say a is not important for all scenarios. However, for the scenarios in our simulations, in which bipeds did not intersect until they collided, b is the key factor. When collision was initially detected, the position_err were small () because of the time lap between two consecutive frames. However, the velocity_err was relatively (). Therefore, with reasonable choice of b (10-50), we could generate enough penalty forces to keep the bipeds from further penetration. When b is small (<1), bipeds would penetrate further and could reach a level of 0.3 before a became the dominant factor and started to drive back the other biped. However, the deep intersection was very visible. When either a (500) or b was too large (100), at least one of the bipeds would crash because of the response forces or the torque.

Bipeds' conditions right before the collision. Relative orientations:

When collision happened at both bipeds' sides, both bipeds pushed each other back and forth with almost the same speed until one of them eventually turned away due to torque. However, when collision happened on top of or underneath the bipeds, the biped that was rising during the collision had more chances to lose footing. This is because the force applied from the top forced the biped to land, without giving enough time or space for it to recover. In football terms, this may put the head-low tacklers at disadvantages.

Relative velocities.

When collisions occurred at the same time as a biped is adjusting its velocity to match its new desired velocity, the biped tended to lose footing. These scenario sometimes-involved bipeds with backpedal set to true. When both bipeds were adjusting their velocities, the collision could cause both to fall.

Reference.

[1] Boone, G.N., Hodgins, J. K., 1997. Slipping and Tripping Reflexes for Bipedal Robots", Autonomous Robots 4(3), 259-271.

[2] Andrew Witkin, Kurt Fleischer, and Alan Barr. Energy constraints on parameterized models. Computer Graphics, 21(4):225-232, July 1987.