//Creates children of this, and moves the balls in this to the children
void haveChildren() {
for(int x = 0; x < 2; x++) {
float minX;
float maxX;
if (x == 0) {
minX = corner1[0];
maxX = center[0];
}
else {
minX = center[0];
maxX = corner2[0];
}
for(int y = 0; y < 2; y++) {
float minY;
float maxY;
if (y == 0) {
minY = corner1[1];
maxY = center[1];
}
else {
minY = center[1];
maxY = corner2[1];
}
for(int z = 0; z < 2; z++) {
float minZ;
float maxZ;
if (z == 0) {
minZ = corner1[2];
maxZ = center[2];
}
else {
minZ = center[2];
maxZ = corner2[2];
}
children[x][y][z] = new Octree(Vec3f(minX, minY, minZ),
Vec3f(maxX, maxY, maxZ),depth + 1);
}
}
}
//Remove all balls from "balls" and add them to the new children
for(set<Ball*>::iterator it = balls.begin(); it != balls.end(); it++) {
Ball* ball = *it;
fileBall(ball, ball->pos, true);
}
balls.clear();
hasChildren = true;
}
haveChildren 函数在需要的时候将立方体分割成8块小的立方体。创建孩子调用new Octree(Vec3f(minX, minY, minZ), Vec3f(maxX, maxY, maxZ), depth+1)。
collectBalls函数找到一个节点或节点的一个孩子中包含的所有球。当我们不拆分一个立方体的时候将用到这个函数。
//Destroys the children of this, and moves all balls in its descendants
//to the "balls" set
void destroyChildren() {
//Move all balls in descendants of this to the "balls" set
collectBalls(balls);
for(int x = 0; x < 2; x++) {
for(int y = 0; y < 2; y++) {
for(int z = 0; z < 2; z++) {
delete children[x][y][z];
}
}
}
hasChildren = false;
}
不能再拆分一个立方体。
//Removes the specified ball at the indicated position
void remove(Ball* ball, Vec3f pos) {
numBalls--;
if (hasChildren && numBalls < MIN_BALLS_PER_OCTREE) {
destroyChildren();
}
if (hasChildren) {
fileBall(ball, pos, false);
}
else {
balls.erase(ball);
}
}
从一棵8叉树中删除一个球。
/* Helper fuction for potentialBallWallCollisions(vector). Adds
* potential ball-wall collisions to cs, where w is the type of wall,
* coord is the relevant coordinate of the wall ('x', 'y', or 'z'), and
* dir is 0 if the wall is in the negative direction and 1 if it is in
* the positive direction. Assumes that this is in the extreme
* direction of the coordinate, e.g. if w is WALL_TOP, the function
* assumes that this is in the far upward direction.
*/
void potentialBallWallCollisions(vector<BallWallPair> &cs,Wall w, char coord, int dir) {
if (hasChildren) {
//Recursively call potentialBallWallCollisions on the correct
//half of the children (e.g. if w is WALL_TOP, call it on
//children above centerY)
for(int dir2 = 0; dir2 < 2; dir2++) {
for(int dir3 = 0; dir3 < 2; dir3++) {
Octree *child;
switch (coord) {
case 'x':
child = children[dir][dir2][dir3];
break;
case 'y':
child = children[dir2][dir][dir3];
break;
case 'z':
child = children[dir2][dir3][dir];
break;
}
child->potentialBallWallCollisions(cs, w, coord, dir);
}
}
}
else {
//Add (ball, w) for all balls in this
for(set<Ball*>::iterator it = balls.begin(); it != balls.end(); it++) {
Ball *ball = *it;
BallWallPair bwp;
bwp.ball = ball;
bwp.wall = w;
cs.push_back(bwp);
}
}
}
这是计算球-墙碰撞的辅助函数，注释里有详细说明。
public:
//Constructs a new Octree. c1 is (minX, minY, minZ), c2 is (maxX, maxY,
//maxZ), and d is the depth, which starts at 1.
Octree(Vec3f c1, Vec3f c2, int d) {
corner1 = c1;
corner2 = c2;
center = (c1 + c2) / 2;
depth = d;
numBalls = 0;
hasChildren = false;
}
构造函数接受立方体两个角落和节点深度的参数。这很明显就能看出来。
//Destructor
~Octree() {
if (hasChildren) {
destroyChildren();
}
}
析构函数在节点删除的时候调用，并同时清除节点的孩子。
//Adds a ball to this
void add(Ball* ball) {
numBalls++;
if (!hasChildren && depth < MAX_OCTREE_DEPTH &&
numBalls > MAX_BALLS_PER_OCTREE) {
haveChildren();
}
if (hasChildren) {
fileBall(ball, ball->pos, true);
}
else {
balls.insert(ball);
}
}
向8叉树中添加一个新球。
//Removes a ball from this
void remove(Ball* ball) {
remove(ball, ball->pos);
}
删除一个球将使用其他的remove函数，球和球的位置作为参数。
//Changes the position of a ball in this from oldPos to ball->pos
void ballMoved(Ball* ball, Vec3f oldPos) {
remove(ball, oldPos);
add(ball);
}
当球从oldPos移动到ball->pos的时候调用这个函数。为了使实现更加简单，我们只是先删除这个球，然后加入一个新的。这样可以避免计算我们的球在哪一个立方体而不在那个立方体的麻烦。但是这个方法不快。