Ordenação, sweep, poda: algoritmo de detecção de colisão (2023)

(leanrada.com)

3 pontos por GN⁺ 2024-08-15 | 1 comentários | Compartilhar no WhatsApp

Na física de jogos, a detecção de colisão repetida é explicada com uma simulação de bolas, mostrando o fluxo de otimização que vai da verificação de todos os pares ao sweep-and-prune
A abordagem simples chama intersects() para todos os pares candidatos entre n objetos, fazendo cerca de (n*(n-1))/2 verificações, então cresce rapidamente para O(n²)
O teste de interseção AABB é composto de várias desigualdades e &&; usando avaliação de curto-circuito e a transitividade das desigualdades, é possível descartar cedo candidatos sem chance de colisão
Depois de ordenar os objetos pela borda esquerda, o minimum x, no momento em que ball2.left > ball1.right o loop interno faz break, excluindo de uma vez os candidatos seguintes
Somando o custo de ordenação O(n log n) com o custo do loop proporcional ao número m de sobreposições no eixo x, o desempenho médio fica em torno de O(n log n + m), reduzindo bastante chamadas desnecessárias a intersects()

O ponto de partida da detecção de colisão em jogos

A detecção de colisão é a base de vários comportamentos na programação de videogames
- impede que personagens atravessem uns aos outros
- faz um Goomba mudar de direção ao bater em outro objeto
- no agar.io, uma célula maior come uma menor ao encostar nela
- processa a física geral do jogo
O exemplo usa uma simulação de bolas rígidas para comparar várias abordagens de detecção de colisão
O escopo vai da forma mais simples até a abordagem de sweep-and-prune, deixando de fora particionamento espacial ou refinamentos com árvores espaciais

A abordagem ingênua de verificar todos os pares

O método mais direto trata todo par de objetos como candidato
- o loop externo percorre cada bola
- o loop interno começa em i + 1 para evitar pares duplicados como A-B e B-A
- para cada par candidato, chama intersects(ball1, ball2) e, se for verdadeiro, executa bounce(ball1, ball2)
Essa verificação se repete a cada passo de tempo, então as bolas recebem o tratamento de quique no momento em que colidem
Quando há poucos objetos, isso é suficiente, mas conforme o número cresce, a quantidade de verificações rapidamente vira um gargalo de desempenho

O limite imposto por O(n²)

O algoritmo ingênuo executa em tempo O(n²) segundo a notação Big O
Para n bolas, o número de pares a verificar é aproximadamente (n*(n-1))/2, isto é, 0.5n² - 0.5n
- n = 5 resulta em 10 pares
- n = 10 resulta em 45 pares
- n = 15 resulta em 105 pares
- n = 20 resulta em 190 pares
No pior caso, quando todos os objetos se sobrepõem ao mesmo tempo, praticamente nenhum algoritmo de detecção de colisão consegue evitar um custo de processamento de colisões em O(n²)
Em comparações reais, os casos médio e melhor costumam ser mais úteis do que o pior caso
A abordagem ingênua sempre se comporta como Θ(n²) independentemente do número real de colisões, então há bastante espaço para melhorar

O trabalho repetido dentro de `intersects()`

O ponto de partida da otimização é a função intersects(), chamada para cada par candidato
Um teste de interseção AABB típico é composto por várias verificações de desigualdade comparando os limites em cada direção

function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}

Esse teste se divide em quatro condições
- object1.left < object2.right
- object1.right > object2.left
- object1.top < object2.bottom
- object1.bottom > object2.top
Por causa da avaliação de curto-circuito de &&, se qualquer condição for falsa, o teste inteiro de interseção retorna falso imediatamente
Generalizando, ao longo de vários testes, os casos em que “pelo menos uma condição é falsa”, dá para reduzir o próprio número de chamadas a intersects()
Isso segue a mesma linha de ideia do teorema do eixo separador: se as projeções não se sobrepõem em um eixo, os dois objetos não colidem

Descartando candidatos com a transitividade das desigualdades

Só de olhar para a condição object1.right > object2.left, já aparece espaço para otimização
Se três objetos A, B e C estiverem horizontalmente na ordem A-B-C, as verificações abaixo podem todas retornar falso

A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false

Se A > B é falso e B > C é falso, então, pela transitividade das desigualdades, sabemos que A > C também é falso
Portanto, mesmo sem chamar intersects(A, C), já dá para concluir que os dois objetos não colidem
Essa omissão só se aplica quando os objetos estão em uma certa ordem, mas como os rótulos dos objetos são arbitrários, basta escolher o da esquerda como A, o do meio como B e o da direita como C
O trabalho de colocar os objetos nessa ordem lógica é justamente a ordenação

Ordenando pelo valor mínimo no eixo x

Uma lista ordenada permite aplicar a transitividade das desigualdades a vários candidatos de uma vez
Um algoritmo de ordenação rápido típico roda em O(n log n), menor que O(n²)
Como os objetos ocupam um intervalo no eixo x, e não apenas um ponto, a ordenação pela posição x usa a borda esquerda, o minimum x
No código ingênuo O(n²), as mudanças necessárias são duas
- antes dos loops, usar sortByLeft(balls) para ordenar as bolas pela coordenada x da borda esquerda
- no loop interno, fazer break quando ball2.left > ball1.right

// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

A função de ordenação organiza o array pela diferença entre as bordas esquerdas

function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

Por que o `break` é seguro

Se a lista está ordenada, então para qualquer inteiro positivo c, vale a relação abaixo

balls[j + c].left >= balls[j].left

Se o candidato atual satisfaz a condição a seguir, então o par atual não se sobrepõe no eixo x

balls[j].left > ball1.right

Combinando as duas desigualdades, chegamos à relação seguinte

balls[j + c].left >= balls[j].left > ball1.right

Pela transitividade, balls[j + c].left > ball1.right também é verdadeiro, então todos os candidatos posteriores também não se sobrepõem a ball1 no eixo x
No instante em que o ball2 atual deixa de se sobrepor a ball1, o restante dos candidatos do loop interno pode ser interrompido sem verificação adicional
Essa otimização limita as chamadas reais a intersects() aos pares que se sobrepõem no eixo x

Complexidade de tempo melhorada

O custo de ordenação adiciona um termo O(n log n), assumindo uma ordenação rápida como mergesort ou quicksort
O loop duplo com parada antecipada pode ser visto, em média, como O(n + m)
- m é o número total de sobreposições no eixo x
- no melhor caso, sem sobreposições, quase não há trabalho desnecessário, ficando perto de O(n)
- no pior caso, ainda pode degradar para O(n²)
O caso médio assume que os objetos estão distribuídos de forma razoavelmente uniforme e que cada objeto colide com apenas alguns outros
Somando ordenação e loops, a complexidade total é O(n log n + m)
Há duas razões para isso melhorar em relação à abordagem ingênua
- n log n é menor que n²
- como depende em parte do número de sobreposições m, o algoritmo evita processar muito além do necessário

Custo de implementação e próximo passo

Essa abordagem baseada em ordenação é um bom equilíbrio entre poucas mudanças no código e grande ganho de desempenho em tempo de execução
Na demo comparativa, a verificação de pares baseada em ordenação reduz visivelmente o número de testes intersects() por frame em comparação com a verificação global de todos os pares
O custo da ordenação não aparece na visualização comparativa, mas parte-se da premissa de que os testes de interseção são caros o bastante para compensar isso
Abordagens mais avançadas e o código final continuam na Part 2

1 comentários

GN⁺ 2024-08-15

Comentários no Hacker News

O ponto interessante dessa abordagem é que o autor sugere usar algoritmos de ordenação “rápidos”, como merge sort/quick sort, para obter o melhor desempenho
Mas, na prática, um algoritmo de ordenação “pior”, como insertion sort, pode ser mais rápido
Os objetos em sistemas de detecção de colisão normalmente se movem só um pouco entre um frame e outro, então dá para manter a lista quase ordenada do frame anterior
Nessas listas, o insertion sort fica próximo de O(n), enquanto o quick sort pode se aproximar de O(n^2)
- O autor cobre quase exatamente esse mesmo ponto na Parte 2
  Ele explica algo como: “A etapa de ordenação é, na análise, o gargalo, mas na maior parte do tempo a ordenação não faz nada. A lista quase sempre já vem ordenada do frame anterior. Mesmo quando sai de ordem, normalmente bastam algumas trocas para ordená-la de novo. Aqui está um exemplo do insertion sort em ação”
- Em vez de ordenar a cada etapa, também dá para afrouxar um pouco a estrutura de indexação para capturar candidatos a colisão quando o objeto tiver se movido menos que epsilon
  Por exemplo, isso pode ser feito aumentando o raio da esfera em epsilon
  Enquanto a esfera não se mover epsilon, não é preciso recalcular o índice
  Para evitar picos de latência quando for preciso recalcular, dá para ordenar 10% por frame e criar um índice defasado
  Depois de 10 frames, você terá um índice ainda válido, desde que a posição de 10 frames atrás esteja a até epsilon da posição atual
- O quick sort só vira O(n^2) em listas quase ordenadas se o pivô for escolhido muito mal
  Se o pivô for aleatório, ele fica em O(n log n), e, se a lista já estiver quase ordenada, também dá para escolher o elemento do meio como pivô
  Ainda assim, mesmo com o pivô ideal, o quick sort continua sendo O(n log n) no melhor caso
  Há variações simples de merge sort que rodam em O(n log k), onde k é o número de runs crescentes/decrescentes nos dados
  O sort padrão da biblioteca do Haskell usa um algoritmo desse tipo, e imagino que o Python também
A estrutura do texto ficou muito boa
Trabalho com desenvolvimento de jogos de alguma forma desde o fim dos anos 90, e hoje a maior parte disso está abstraída pelas engines, mas esse tipo de conteúdo continua sendo essencial para entender como simulações de sistemas complexos funcionam
Obrigado ao autor por ter escrito algo tão acessível
Sobre detecção contínua de colisão, sempre achei este documento muito bom: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
A biblioteca em si também é excelente em termos de desempenho
Só que ela é tão otimizada que a integração acaba sendo um pouco complicada
Fiquei na dúvida se a frase “esse algoritmo ingênuo executa em O(n2) no critério de big-O” está correta
O loop externo i roda n - 1 vezes, e o loop interno j começa em i + 1, então parece que ele roda cada vez menos do que n - 1 vezes
Não sou da área, então queria entender se, quando n é grande, isso é tratado aproximadamente como O(n2), ou se na prática é algo menor do que aparenta
- Não é exatamente n^2
  Para o i-ésimo elemento, a comparação é feita (n - i - 1) vezes e, usando índice começando em 0, o total de comparações vira (n - 1) * n / 2
  Veja https://en.wikipedia.org/wiki/Triangular_number
  No fim, isso não faz diferença na análise assintótica
  Big-O descreve o comportamento quando n tende ao infinito, e nesse caso o termo quadrático domina
- A “otimização” de começar o loop interno em j = i + 1 serve para evitar verificar todos os pares de objetos duas vezes
  Isso também impede que um objeto seja comparado com ele mesmo
  Como todos os pares são verificados exatamente uma vez, o algoritmo é O(n^2)
- Big-O é só uma classificação de complexidade que descreve como o número de operações abstratas escala com o tamanho da entrada, isto é, com o comprimento da lista de entrada
  Em geral, se der para expressar analiticamente o número de operações como uma função do tamanho da entrada, o big-O mantém apenas o maior termo e descarta todos os coeficientes
  Ele não descreve necessariamente o desempenho real do algoritmo
  20n2^+5n e 2n^2 + 9001n são ambos O(n^2)
- Como é a soma de 1 até n, o resultado é n(n+1)/2
  Na notação big-O, todos os coeficientes e os termos que crescem mais devagar são ignorados, então isso se reduz a complexidade quadrática
- Talvez fique mais fácil de entender pensando no big-O como algo parecido com o cálculo de limites no cálculo diferencial e integral
O uso das ilustrações foi muito bom e pareceu bem dosado
Às vezes, textos com ilustrações interativas parecem mais uma desculpa para encher de demos chamativas e acabam ficando, como uma palestra TED, mais ornamentados do que substanciais
Mas neste texto as ilustrações não engoliram o conteúdo
Parte 2: https://leanrada.com/notes/sweep-and-prune-2/
Outros bons textos também valem a leitura: https://leanrada.com/
Fiz algo parecido há muito tempo, mas em vez de ordenar eu mantinha listas de índices para cada direção e deixava os próprios objetos se ordenarem
Por exemplo, havia 4 listas como objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
Quando um objeto se movia horizontalmente, ele atualizava seu próprio índice nos arrays leftEdge e rightEdge
Mesmo com movimento, normalmente bastava trocar 1 ou 2 posições de índice
- Essa abordagem parece útil para cenas majoritariamente estáticas
  À medida que aumenta a quantidade de elementos dinâmicos, reconstruir o grafo parece uma solução melhor
É a primeira vez que vejo essa abordagem, mas isso não é parecido com usar algo como uma quadtree para reduzir o número de colisores potenciais?
- Sim
  Só que, mais do que em renderização em tempo real, é mais comum ver coisas como k-d trees em renderização offline
Fiquei curioso com a parte em que ele diz que não vai tratar de “outras abordagens, como particionamento espacial ou subdivisão por árvores espaciais”
Alguém sabe se o algoritmo do texto costuma ser mais rápido que particionamento espacial/subdivisão por árvores espaciais?
Usei uma abordagem desse tipo de árvore espacial há muito tempo e, olhando de forma ingênua, parecia uma solução bem boa, mas na época era nos anos 80, antes da internet, então nunca pesquisei nem comparei com os algoritmos usados por outras pessoas
- A complexidade de manter particionamento espacial ou subdivisão por árvores, especialmente quando há um número enorme de objetos em movimento, pode ser um peso grande
  Gerenciar uma única lista de entidades, ou até uma grade de células 256x256 em que cada célula contém sua própria lista de entidades, é muito mais fácil de escrever, depurar e otimizar do que uma estrutura de partição complexa que precisa manter todas as invariantes da árvore sempre que os objetos se movem
  Na época de DOOM e Quake, o desempenho desses sistemas de base era muito mais crítico do que hoje, então fazia mais sentido que os autores de engines criassem sistemas de partição extremamente complexos
  Hoje os CPUs são muito bons em varrer arrays ordenados e, por causa de pipelining, seguir linked lists ou árvores é relativamente menos vantajoso do que antes
  O tempo de CPU tende a ser mais gasto em coisas como IA e renderização do que no gerenciamento de listas de entidades

Ordenação, sweep, poda: algoritmo de detecção de colisão (2023)

O ponto de partida da detecção de colisão em jogos

A abordagem ingênua de verificar todos os pares

O limite imposto por O(n²)

O trabalho repetido dentro de intersects()

Descartando candidatos com a transitividade das desigualdades

Ordenando pelo valor mínimo no eixo x

Por que o break é seguro

Complexidade de tempo melhorada

Custo de implementação e próximo passo

Leituras relacionadas

1 comentários

Comentários no Hacker News

O trabalho repetido dentro de `intersects()`

Por que o `break` é seguro