Method InsertLeaf

CollisionB2DynamicTree.go:330–448

(leaf int)

}

func (tree *B2DynamicTree) InsertLeaf(leaf int) {
	tree.M_insertionCount++

	if tree.M_root == B2_nullNode {
		tree.M_root = leaf
		tree.M_nodes[tree.M_root].Parent = B2_nullNode
		return
	}

	// Find the best sibling for this node
	leafAABB := tree.M_nodes[leaf].Aabb
	index := tree.M_root
	for tree.M_nodes[index].IsLeaf() == false {
		child1 := tree.M_nodes[index].Child1
		child2 := tree.M_nodes[index].Child2

		area := tree.M_nodes[index].Aabb.GetPerimeter()

		combinedAABB := NewB2AABB()
		combinedAABB.CombineTwoInPlace(tree.M_nodes[index].Aabb, leafAABB)
		combinedArea := combinedAABB.GetPerimeter()

		// Cost of creating a new parent for this node and the new leaf
		cost := 2.0 * combinedArea

		// Minimum cost of pushing the leaf further down the tree
		inheritanceCost := 2.0 * (combinedArea - area)

		// Cost of descending into child1
		cost1 := 0.0
		if tree.M_nodes[child1].IsLeaf() {
			aabb := NewB2AABB()
			aabb.CombineTwoInPlace(leafAABB, tree.M_nodes[child1].Aabb)
			cost1 = aabb.GetPerimeter() + inheritanceCost
		} else {
			aabb := NewB2AABB()
			aabb.CombineTwoInPlace(leafAABB, tree.M_nodes[child1].Aabb)
			oldArea := tree.M_nodes[child1].Aabb.GetPerimeter()
			newArea := aabb.GetPerimeter()
			cost1 = (newArea - oldArea) + inheritanceCost
		}

		// Cost of descending into child2
		cost2 := 0.0
		if tree.M_nodes[child2].IsLeaf() {
			aabb := NewB2AABB()
			aabb.CombineTwoInPlace(leafAABB, tree.M_nodes[child2].Aabb)
			cost2 = aabb.GetPerimeter() + inheritanceCost
		} else {
			aabb := NewB2AABB()
			aabb.CombineTwoInPlace(leafAABB, tree.M_nodes[child2].Aabb)
			oldArea := tree.M_nodes[child2].Aabb.GetPerimeter()
			newArea := aabb.GetPerimeter()
			cost2 = newArea - oldArea + inheritanceCost
		}

		// Descend according to the minimum cost.
		if cost < cost1 && cost < cost2 {