b2DynamicTree::CreateProxy performs O((nlog(n))^2) for inserting n objects

What steps will reproduce the problem?
1. Time pushing n objects into the b2DynamicTree.

What is the expected output? What do you see instead?
Expected that performance would be O(nlog(n)) to insert n objects

What version of the product are you using? On what operating system?
box2d 2.1.2

Please provide any additional information below.
Ran AMD's profiler (CodeAnalyst) and found that the hotspot was 
b2DynamicTree::ComputeHeight(), which represents 75% of all consumption!!!

Here's what happens:

User calls CreateProxy()
  CreateProxy then calls ComputeHeight() at least once which is O(nlog(n)).

Solution:
  Create a m_heuristic_height_. m_heuristic_height_ is always >= the actual hight. It is an overestimation.

On call to CreateProxy(), increment m_heuristic_height_. If 
m_heuristic_height_is greater than 64 then set m_heuristic_height_ to 
ComputeHeight() and if necessary perform re-balancing.

Result:
  4x speedup to insert 200 objects and CreateProxy() scales at more linearly for vary large values of N.

Inline patch:
Add
int32 m_insertionCount;
to b2DynamicTree (and default construct to 0).

int32 b2DynamicTree::CreateProxy(const b2AABB& aabb, void* userData)
{
    int32 proxyId = AllocateNode();

    // Fatten the aabb.
    b2Vec2 r(b2_aabbExtension, b2_aabbExtension);
    m_nodes[proxyId].aabb.lowerBound = aabb.lowerBound - r;
    m_nodes[proxyId].aabb.upperBound = aabb.upperBound + r;
    m_nodes[proxyId].userData = userData;

    InsertLeaf(proxyId);

  static const int32 kTooHigh = 64;

  m_height_hueristic++;
  if (m_height_hueristic > kTooHigh) {
    m_height_hueristic = ComputeHeight();
      int32 iterationCount = m_nodeCount >> 4;
      int32 tryCount = 0;
      // Rebalance if necessary.
    while (m_height_hueristic > kTooHigh && tryCount < 10) {
          Rebalance(iterationCount);
          m_height_hueristic = ComputeHeight();
          ++tryCount;
    }
  }

    return proxyId;
}

Original issue reported on code.google.com by zach.vor...@gmail.com on 22 May 2011 at 3:00

Attachments:

behdad / box2d

b2DynamicTree::CreateProxy performs O((nlog(n))^2) for inserting n objects #201