A Analogia de Flatland
O Flatland de Edwin Abbott (1884): 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 construí-la. A geometria do seu mundo contém uma dimensão que eles descartam estruturalmente.
MOAD-0007 funciona da mesma maneira. Os objetos no espaço tridimensional possuem posição, rotação e volume de limitação: uma rica estrutura geométrica. 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 e não tivessem posição.
O Exemplo do Three.js
Three.js Raycaster.intersectObjects(): dado um raio (uma posição e direção no espaço tridimensional), encontre todos os objetos que o raio intersecciona. A implementação: iterar através de todos os N objetos da cena, testar cada um contra o raio. O(N) por chamada.
Um manipulador de evento de passar o mouse chama intersectObjects() uma vez por frame a 60 frames 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 intersecciona.
Com N=100: invisível. Orçamento de frame (16,7ms em 60fps) absorve o custo sem reclamar.
Com N=10.000: dominante. 600.000 testes de interseção por segundo saturam o thread principal. Taxa de quadros cai. A cena que funcionava em N=100 colapsa silenciosamente enquanto N cruza o limiar.
A Estrutura que a Varredura Linear Descarta
Os objetos ocupam posições no espaço. Um objeto na posição (1000, 0, 0) não pode interseccionar um raio apontando na direção (-1, 0, 0) a partir da posição (0, 0, 0): o objeto está na direção oposta. Uma varredura linear verifica de qualquer forma.
Os objetos têm volumes limitadores: uma esfera ou caixa que encerra todo o objeto. Um raio que não intersecciona o volume limitador de um objeto não pode interseccioná-lo. Uma varredura linear calcula o teste de interseção completo de qualquer forma.
A geometria codifica quais objetos devem ser ignorados. A varredura linear ignora a geometria. Isso é o descarte.
O Que 'Descartando a Estrutura' Significa
A analogia de Flatland: os habitantes de Abbott não podiam perceber profundidade. Um Defeito de Flatland descarta a estrutura geométrica que existe nos dados, mas nunca entra no algoritmo.
Por que um Conjunto de Hash Não Pode Corrigir o MOAD-0007
Correção MOAD-0001: substitua uma análise de pertencimento sequencial por um conjunto de hash. list.contains(x): O(N). set.has(x): O(1). A pergunta de pertencimento: 'x está nesta coleção?' Nenhuma geometria espacial envolvida.
Correção MOAD-0007: 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 feixe de raios/esfera/frusto-côno?' Requer proximidade espacial.
Um conjunto de hash responde a pertencimento: 'este objeto exato está presente?' O(1). Ele não pode responder proximidade: 'quais objetos perto deste feixe de raios?' Um conjunto de hash não tem noção de distância ou extensão espacial. A hashificação descarta geometria da mesma maneira que uma varredura linear.
Um BVH responde proximidade: 'quais objetos caem dentro desta consulta espacial?' O(log N + k). Ele organiza objetos por posição, então as consultas de proximidade pulam objetos geometricamente distantes.
| Pergunta | Estrutura Correta | Estrutura Errada |
|----------|------------------|-----------------|
| O objeto X está neste conjunto? | HashSet (O(1)) | Lista linear (O(N)) |
| Quais objetos intersectam este feixe de raios? | BVH/octree/k-d tree (O(log N)) | Varredura linear OU HashSet (O(N) ou O(N)) |
MOAD-0001 & MOAD-0007: ambos operações O(N) substituídas por algo mais rápido. Estruturas diferentes são necessárias porque as perguntas são diferentes.
Quando construir, quando pular
Construir uma BVH custa O(N log N). Consultas custam O(log N + k). Equilíbrio: quando as consultas forem maior que as construções, os ganhos nas consultas superam o custo de construção.
A N = 100: varredura linear leva microssegundos. Construção da BVH adiciona sobreposição. Pule a BVH.
A N = 10,000 em 60Hz: varredura linear domina orçamento de frame. Consultas BVH custam 1/1.000 da varredura linear. Construa a BVH uma vez; consulte 60 vezes por segundo. Equilíbrio alcançado antes do primeiro frame.
A regra: construir quando N * Q > N log N, onde Q = consultas por ciclo de reconstrução. Para cenas interativas 3D: Q = 60 por segundo, limiar de N = alguns centenas de objetos.
Diagnóstico e Correção de uma Cena 3D
Uma aplicação de visualização 3D renderiza 5.000 objetos geométricos. Um manipulador de hover dispara 60 vezes por segundo. Em cada evento de hover, o manipulador chama scene.intersectObjects(ray, objects) que itera todos os 5.000 objetos e testa cada um contra o raio. A taxa de quadros caiu de 60fps para 8fps.
Um colega sugere: 'Coloque todos os objetos em um conjunto para consultas O(1).'