Quad Tree com muitos objetos em movimento

Eu tenho uma implementação Quad Tree que é muito útil para o que estou tentando fazer. Meu problema é que, quando minha janela de exibição tem muitos objetos, a atualização para a Quad Tree leva muito tempo.

É um fato conhecido que Quad Trees são lentas para objetos não estáticos. Tentei alguns métodos para acelerar as coisas, mas o fato é que preciso atualizar um grande número de objetos com muita frequência.

Existe um algoritmo melhor que eu deveria estar procurando? Existem algumas implementações derivadas de Quad Tree que você conhece e que podem ser úteis para mim?

Como você está movendo objetos Quad Tree? O método mais simples (e mais lento) é remover o objeto e reinserir. O XNA Quad Tree de código aberto que eu e um amigo criamos faz um pouco de lógica quando um objeto se move:

If the object is still inside the same quad
    if the object fits into a child quad
        Add to child
Else
    move the object to the parent(s) until it fits, and optionally going back down into children

Se você já está fazendo algo assim, pode valer a pena procurar outros métodos de índice espacial, como Spatial Hashing .

Uso limites para objetos e os insiro no quadrilátero mais profundo que os contém. (Eu nunca me senti confortável em tratar as coisas como pontos)

Para objetos em movimento rápido, que também são tipicamente pequenos, por exemplo, marcadores, calculo os limites do caminho para um número de passos de tempo ou tamanho máximo, de modo que amarrei uma bala por um retângulo maior em vez de um quadrado menor e não preciso mova-os quase com a mesma frequência.

Além disso, você pode otimizar o próprio código em movimento para mover o objeto de maneira inteligente, em vez de removê-lo e reinseri-lo.