rebuildBottomUp method

void rebuildBottomUp()

Build an optimal tree. Very expensive. For testing.

Implementation

void rebuildBottomUp() {
  List<int> nodes = BufferUtils.allocClearIntList(_nodeCount);
  int count = 0;

  // Build array of leaves. Free the rest.
  for (int i = 0; i < _nodeCapacity; ++i) {
    if (_nodes[i].height < 0) {
      // free node in pool
      continue;
    }

    DynamicTreeNode node = _nodes[i];
    if (node.child1 == null) {
      node.parent = null;
      nodes[count] = i;
      ++count;
    } else {
      _freeNode(node);
    }
  }

  AABB b = AABB();
  while (count > 1) {
    double minCost = double.maxFinite;
    int iMin = -1, jMin = -1;
    for (int i = 0; i < count; ++i) {
      AABB aabbi = _nodes[nodes[i]].aabb;

      for (int j = i + 1; j < count; ++j) {
        AABB aabbj = _nodes[nodes[j]].aabb;
        b.combine2(aabbi, aabbj);
        double cost = b.getPerimeter();
        if (cost < minCost) {
          iMin = i;
          jMin = j;
          minCost = cost;
        }
      }
    }

    int index1 = nodes[iMin];
    int index2 = nodes[jMin];
    DynamicTreeNode child1 = _nodes[index1];
    DynamicTreeNode child2 = _nodes[index2];

    DynamicTreeNode parent = _allocateNode();
    parent.child1 = child1;
    parent.child2 = child2;
    parent.height = 1 + Math.max<int>(child1.height, child2.height);
    parent.aabb.combine2(child1.aabb, child2.aabb);
    parent.parent = null;

    child1.parent = parent;
    child2.parent = parent;

    nodes[jMin] = nodes[count - 1];
    nodes[iMin] = parent.id;
    --count;
  }

  _root = _nodes[nodes[0]];

  validate();
}