//Adds potential ball-ball collisions to the specified set
void potentialBallBallCollisions(vector<BallPair> &collisions) {
if (hasChildren) {
for(int x = 0; x < 2; x++) {
for(int y = 0; y < 2; y++) {
for(int z = 0; z < 2; z++) {
children[x][y][z]->potentialBallBallCollisions(collisions);
}
}
}
}
else {
//Add all pairs (ball1, ball2) from balls
for(set<Ball*>::iterator it = balls.begin(); it != balls.end(); it++) {
Ball *ball1 = *it;
for(set<Ball*>::iterator it2 = balls.begin(); it2 != balls.end(); it2++) {
Ball *ball2 = *it2;
//This test makes sure that we only add each pair once
if (ball1 < ball2) {
BallPair bp;
bp.ball1 = ball1;
bp.ball2 = ball2;
collisions.push_back(bp);
}
}
}
}
}
这是8叉树的核心。在这个函数中，我们计算所有可能的球-球碰撞并将他们放入collisions数组中。如果他们是孩子，我们只是问他们得到可能的球-球碰撞；否则我们就取每个球队。
在set中遍历每对球，我们使用一个特别的c++构造，遍历一个set，使用下面的代码：
for(set<Type>::iterator it = s.begin(); it != s.end(); it++) {
Type element = *it;
//Do stuff with element
//...
}
//Adds potential ball-wall collisions to the specified set
void potentialBallWallCollisions(vector<BallWallPair> &collisions) {
potentialBallWallCollisions(collisions, WALL_LEFT, 'x', 0);
potentialBallWallCollisions(collisions, WALL_RIGHT, 'x', 1);
potentialBallWallCollisions(collisions, WALL_BOTTOM, 'y', 0);
potentialBallWallCollisions(collisions, WALL_TOP, 'y', 1);
potentialBallWallCollisions(collisions, WALL_FAR, 'z', 0);
potentialBallWallCollisions(collisions, WALL_NEAR, 'z', 1);
}
在这个函数中，通过调用6个面的辅助函数计算所有可能的球-墙碰撞，没面墙计算一次。
这是8叉树的实现。
现在为了保证不作无用功，确保8叉树能提高速度。运行程序并不停的按空白键并观察场景变慢的时候是多少个球。如果你的电脑非常的快，你可能需要减少TIME_BETWEEN_UPDATES的值来减缓程序的运行。(如果你电脑比较慢，就加大这个值，不过看起来很不流畅。)
现在使用最普通的方法。在potentialBallBallCollisions和potentialBallWallCollisions里面注释掉fast版本，并恢复slow版本。在moveBalls中，注释掉octree->ballMoved(ball, oldPos)行。在handleKeypress中注释掉_octree->add(ball)行。现在再看看程序减慢的时候有多少个球。这将非常的少，我的电脑上没有8叉树是300个球有是1000球。如果在potentialBallBallCollisions最后加入cout<<potentialCollisions.size()<<'\n'；在有8叉树的情况下，当有300个球的时候，程序每次要检查大概400对球，这比大概每次50,000少的多。
所以我们使碰撞检测快多了。
练习
- 将球体改为和坐标轴平行的立方体并确保每次弹开的时候改变了角度。
- 改变8叉树使得每个叶子节点都有至少4的深度。还句话说，深度1到3的节点度有孩子。(ps: 满n叉树， 平衡树, AVL树)
- 使程序中的所有小球在x0y平面上移动。使用2维的4叉树。