4

I'm trying to implement this data structure, a Barnes-Hut Octree, and I keep running into an endless loop, terminated by an out of memory exception.

The complete fiddle is here: http://jsfiddle.net/cWvex/ but the functions I'm looping between are these:

OctreeNode.prototype.insert = function (body) {

    console.log('insert');

    if(this.isInternal){

        this.internalInsert(body);

        return;
    }


    if(this.isExternal){

        // insert the body into the spec. quadrant, call internalUpdate
        for(var quadrant in this.internal.quadrants){
            if(this.internal.quadrants.hasOwnProperty(quadrant)){
                this.internal.quadrants[quadrant] = new OctreeNode();
            }
        }
        this.isExternal = false;
        this.isInternal = true;

        this.internalInsert(this.external);
        this.external = null;
        this.internalInsert(body);

        return;
    }


    if(this.isEmpty){

        this.external = body;
        this.isEmpty = false;
        this.isExternal = true;

        return;
    }

};

// Precondition: quadrants' nodes must be instantiated
OctreeNode.prototype.internalInsert = function(body) {

    console.log('internalInsert');

    this.internal.quadrants[this.quadrant(body)].insert(body);
    this.internalUpdate(body);

};

Anyone got an idea of what I'm missing?

4

1 回答 1

2

我认为问题与象限函数有关：

OctreeNode.prototype.quadrant = function (body) {

    console.log('quadrant');

    var pos = this.internal.pos;

    var quadrant = (body.pos.x < pos ? 'l' : 'r') + 
        (body.pos.y < pos ? 'u' : 'd') + 
        (body.pos.z < pos ? 'i' : 'o');

    return quadrant; 
};

选择的象限应该基于象限的中心，而不是质心。我认为您需要创建一个新变量来定义象限的中心。

请注意，当您添加节点时，质心（存储在 pos 中）可以改变，但象限的中心保持固定（否则当您下降到八叉树时会出错）。

目前，每个新节点的 pos 为 0,0,0，因此每个点最终都会被分配到节点的同一个象限中。因此，当您尝试将两个物体放入树中时，最终会得到无限递归：

  1. 主体 1 被插入节点 x
  2. 主体 2 被插入节点 x
  3. 节点 1 被拆分。
  4. 主体 1 插入节点 x 的象限 1
  5. 主体 2 插入节点 x 的象限 1
  6. 返回第 1 步，将 x 更改为节点 x 的象限 1 处的节点

编辑

顺便说一句，在代码中：

avgPos.x = (body.pos.x*body.mass + 
            avgPos.x * totalMass) / totalMass + body.mass

我认为你需要更多的括号才能成为

avgPos.x = (body.pos.x*body.mass + 
            avgPos.x * totalMass) / (totalMass + body.mass)

否则重心更新会出错。

于 2013-06-09T18:53:31.077 回答