A Analogia de Flatland
Flatland (1884) de Edwin Abbott: habitantes de um plano bidimensional. Eles percebem comprimento e largura. Profundidade: a terceira dimensão acima deles, invisível. Eles não podem percebê-la, não podem usá-la, não podem construir com ela. A geometria do mundo deles contém uma dimensão que eles descartam estruturalmente.
MOAD-0007 funciona da mesma forma. Objetos no espaço 3D possuem posição, rotação e volume delimitador: uma estrutura geométrica rica. Uma varredura linear os trata como uma lista plana. A estrutura espacial: presente, não utilizada, descartada. Cada teste de interseção varre a lista inteira, como se os objetos não tivessem geometria nem posição.
O Exemplo do Three.js
Three.js Raycaster.intersectObjects(): dado um raio (uma posição e direção no espaço 3D), encontra todos os objetos que o raio intersecta. A implementação: itera por todos os N objetos da cena, testando cada um contra o raio. O(N) por chamada.
Um manipulador de evento de hover chama intersectObjects() uma vez por quadro a 60 quadros por segundo. Com N=100 objetos: 6.000 testes de interseção por segundo. Com N=10.000 objetos: 600.000 testes por segundo. O custo: proporcional a N, não ao número de objetos que o raio realmente intersecta.
Em N=100: invisível. O orçamento de quadro (16,7 ms a 60 fps) absorve o custo sem reclamação.
Em N=10.000: dominante. 600.000 testes de interseção por segundo saturam a thread principal. A taxa de quadros cai. A cena que funcionava em N=100 colapsa silenciosamente quando N ultrapassa o limite.
A Estrutura que o Scan Linear Descarta
Os objetos ocupam posições no espaço. Um objeto na posição (1000, 0, 0) não pode intersectar um raio apontando na direção (-1, 0, 0) a partir da posição (0, 0, 0): o objeto está na direção oposta. Um scan linear o verifica mesmo assim.
Os objetos possuem volumes delimitadores: uma esfera ou caixa que envolve todo o objeto. Um raio que não intersecta o volume delimitador de um objeto não pode intersectar o objeto. Um scan linear calcula o teste completo de interseção mesmo assim.
A geometria codifica quais objetos devem ser ignorados. O scan linear ignora a geometria. Esse é o descarte.
O que significa 'Descartar a Estrutura'
A analogia de Flatland: os habitantes de Abbott não conseguiam perceber profundidade. Um Defeito Flatland descarta estrutura geométrica que existe nos dados mas nunca entra no algoritmo.
Por que um Conjunto Hash Não Pode Corrigir MOAD-0007
MOAD-0001 correção: substitua um teste sequencial de pertinência por um conjunto hash. list.contains(x): O(N). set.has(x): O(1). A pergunta de pertinência: 'x está nesta coleção?' Nenhuma geometria espacial envolvida.
MOAD-0007 correção: substitua uma varredura espacial linear por um índice espacial (BVH, octree, k-d tree, R-tree). A pergunta espacial: 'quais objetos nesta coleção intersectam este raio/esfera/frustum?' Proximidade espacial necessária.
Um conjunto hash responde à pertinência: 'este objeto exato está presente?' O(1). Ele não consegue responder à proximidade: 'quais objetos estão próximos deste raio?' Um conjunto hash não possui noção de distância ou extensão espacial. O hashing descarta a geometria tão completamente quanto uma varredura linear.
Uma BVH responde à proximidade: 'quais objetos estão dentro desta consulta espacial?' O(log N + k). Ela organiza os objetos por posição, de modo que consultas de proximidade ignoram objetos geometricamente distantes.
| Pergunta | Estrutura Correta | Estrutura Incorreta |
|---|---|---|
| O objeto X está neste conjunto? | HashSet (O(1)) | Lista linear (O(N)) |
| Quais objetos intersectam este raio? | BVH/octree/k-d tree (O(log N)) | Varredura linear OU HashSet (O(N) ou O(N)) |
MOAD-0001 & MOAD-0007: ambas operações O(N) substituídas por algo mais rápido. Estruturas diferentes são necessárias porque as perguntas diferem.
Quando Construir, Quando Ignorar
Construir uma BVH custa O(N log N). Consultas custam O(log N + k). Ponto de equilíbrio: quando o número de consultas supera o de construções o suficiente para que a economia nas consultas supere o custo de construção.
Em N=100: a varredura linear leva microssegundos. A construção da BVH adiciona sobrecarga. Ignore a BVH.
Em N=10.000 a 60 Hz: a varredura linear consome o orçamento de quadro. Consultas na BVH custam 1/1.000 da varredura linear. Construa a BVH uma vez; consulte 60 vezes por segundo. O ponto de equilíbrio é atingido antes do primeiro quadro.
A regra: construa quando N * Q > N log N, onde Q = consultas por ciclo de reconstrução. Para cenas 3D interativas: Q = 60 por segundo, limiar de N = algumas centenas de objetos.
Diagnosticar e Corrigir uma Cena 3D
Um aplicativo de visualização 3D renderiza 5.000 objetos geométricos. Um manipulador de hover é disparado 60 vezes por segundo. A cada evento de hover, o manipulador chama scene.intersectObjects(ray, objects), que itera sobre todos os 5.000 objetos e testa cada um contra o raio. A taxa de quadros caiu de 60 fps para 8 fps.
Um colega sugere: 'Coloque todos os objetos em um Set para busca O(1).'