rebuildBottomUp method
void
rebuildBottomUp()
Build an optimal tree. Very expensive. For testing.
Implementation
void rebuildBottomUp() {
final nodes = List<int>.filled(_nodeCount, 0);
var count = 0;
// Build array of leaves. Free the rest.
for (var i = 0; i < _nodeCapacity; ++i) {
if (_nodes[i].height < 0) {
// free node in pool
continue;
}
final node = _nodes[i];
if (node.child1 == null) {
node.parent = null;
nodes[count] = i;
++count;
} else {
_freeNode(node);
}
}
final b = AABB();
while (count > 1) {
var minCost = double.maxFinite;
var iMin = -1;
var jMin = -1;
for (var i = 0; i < count; ++i) {
final aabbi = _nodes[nodes[i]].aabb;
for (var j = i + 1; j < count; ++j) {
final aabbj = _nodes[nodes[j]].aabb;
b.combine2(aabbi, aabbj);
final cost = b.perimeter;
if (cost < minCost) {
iMin = i;
jMin = j;
minCost = cost;
}
}
}
final index1 = nodes[iMin];
final index2 = nodes[jMin];
final child1 = _nodes[index1];
final child2 = _nodes[index2];
final parent = _allocateNode();
parent.child1 = child1;
parent.child2 = child2;
parent.height = 1 + 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();
}