Resumo Técnico: Modelagem por Aproximação Geométrica para Filtragem de Raio-Triângulo Centrada no Emissor em Simulação de LiDAR Arbitrariamente Dinâmica

1. Definição do Problema

A simulação de detecção de luz e distância (LiDAR) em tempo real requer a identificação do triângulo interceptado mais próximo para cada raio emitido dentro de cenas dinâmicas contendo grandes números de objetos móveis e deformáveis. O custo computacional de uma abordagem de força bruta escala linearmente com o produto do número de raios e o total de triângulos ($\Omega \times \gamma \times \chi \times \tau$), resultando em aproximadamente $5,2 \times 10^{12}$ testes de interseção por quadro para uma cena representativa.

As soluções de estado da arte atuais dependem de Hierarquias de Volumes Envolventes (BVH) e traçado de raios acelerado por hardware (ex: OptiX, Embree). No entanto, esses métodos enfrentam três deficiências estruturais na simulação de LiDAR dinâmica:

1. Cenas Dinâmicas: As BVHs exigem uma reconstrução completa a cada quadro para cenas com movimento ou deformação significativa, um custo proporcional ao total de triângulos, independentemente de quão pouco a geometria realmente se moveu.
2. LiDARs de 360°: LiDARs giratórios emitem raios em todas as direções simultaneamente, eliminando a coerência de raios. Isso impede a amortização dos custos de teste de nós nos quais a travessia de BVH se baseia.
3. Ausência de Filtragem de Triângulos Antecipada: As APIs de BVH padrão condicionam todo o descarte (culling) a um raio ativo. Triângulos que estão fora do alcance ou com face voltada para trás, mas que compartilham um volume delimitador com a geometria contribuinte, ainda são testados por raio. Em cenas dinâmicas, volumes delimitadores frouxos degradam ainda mais o desempenho ao envolver geometria não contribuinte.

2. Metodologia: O Algoritmo de Traçado de Raios Gajmer (GRCA)

O GRCA inverte o paradigma tradicional de traçado de raios. Em vez de perguntar "o que cada raio atinge?", ele pergunta "quais raios cada triângulo pode possivelmente atingir?". Esta abordagem elimina a necessidade de estruturas de aceleração e reconstrução de cena por quadro.

2.1 Modelagem Geométrica (GACP)

O algoritmo modela emissores de LiDAR giratórios como Cones ou Planos Aproximados Geometricamente (GACP).

• Observação: Todos os raios dentro de um único canal vertical de um LiDAR giratório traçam coletivamente uma superfície cônica ao redor do eixo de rotação (ou um plano horizontal em elevação zero).
• Implementação: Em vez de alargar os raios individuais em primitivas volumétricas (como no rastreamento de feixe/beam tracing), o GRCA mantém os raios como semirretas direcionadas, mas testa a superfície GACP contra os triângulos. Isso reduz o problema de encontrar raios interceptados para um canal a um único teste de superfície GACP-Triângulo (GACP-T).

2.2 Filtragem e Classificação Centrada no Emissor

O GRCA utiliza a lei da área aparente para classificar triângulos com base em sua pegada conforme visto da origem do raio ($A_{origin} \propto A_T \cos \phi_{view} / \delta^2$).

• SAT (Triângulos de Menor Aparência): Triângulos com uma pequena área aparente em relação à resolução angular do sensor. Estes são numerosos, mas contribuem com menos acertos.
• BAT (Triângulos de Maior Aparência): Triângulos com uma grande área aparente. Estes são menos numerosos, mas dominam a saída do escaneamento e requerem tratamento preciso.

2.3 O Pipeline de Duas Passagens

O algoritmo processa a geometria em duas passagens para equilibrar velocidade e precisão:

1. Passagem Inicial (Conservadora):
   • Aplica filtros rápidos centrados na origem (face traseira, alcance, área aparente).
   • Prediz a amplitude do canal ($C_{span}$) e a amplitude do raio ($R_{span}$) para cada triângulo usando verificações aproximadas de baixo custo (busca binária em predicados booleanos GACP-T e projeções de vértices).
   • Tratamento de SAT: Triângulos classificados como SAT são processados inline com as amplitudes preditas.
   • Tratamento de BAT: Triângulos classificados como BAT são adiados para uma segunda passagem.
2. Passagem Final (Precisa):
   • Processa a lista de BAT adiada.
   • Computa interseções exatas GACP-T por canal para determinar as extremidades precisas da amplitude do raio.
   • Resolve ambiguidades de costura azimutal (arcos CW vs. CCW) usando testes de interseção de plano.
   • Executa as verificações finais de interseção raio-triângulo (Möller–Trumbore) apenas para as amplitudes preditas.

3. Principais Contribuições

• Inversão de Paradigma: Um novo algoritmo de traçado de raios que escala com a geometria da cena ($O(\tau)$) em vez do número de raios, invertendo a direção da consulta padrão.
• Modelo Centrado no Emissor: Uma aproximação de superfície GACP de forma fechada que gera índices de amplitude inteiros por triângulo $[C_{from}, C_{to}] \times [R_{from}, R_{to}]$ sem particionamento de cena.
• Pipeline de Duas Passagens: Um design impulsionado pela classificação de área aparente (SAT/BAT) que alcança rejeição $O(\tau)$ no lado da GPU sem idas e vindas (round-trips) para a CPU.
• Implementações e Benchmarks:
  • GRCAGPU (CUDA): Supera o OptiX acelerado por hardware em até 7,97×.
  • GRCACPU (AVX2/SSE4.1, single-threaded): Supera o Embree em até 14,55×.
  • Avaliado em 216 configurações únicas, seis cenas e cinco plataformas de hardware.
• Pipeline Híbrido: Uma demonstração combinando GRCA para geometria dinâmica com uma BVH estática para geometria estática, alcançando até 19,2× de aceleração sobre o Embree e 10,5× sobre o OptiX em cenas dinâmicas complexas.

4. Resultados e Desempenho

Os benchmarks foram realizados em cenas variando de ~1,8M a ~22M de triângulos, com até 30 objetos dinâmicos e 8 LiDARs simultâneos de 128×4096 raios (aprox. 4,2M raios/quadro).

• Cenas Dinâmicas: Em cenas com deformação em toda a cena (SWD), o GRCA mantém um desempenho consistente, enquanto métodos baseados em BVH (Embree/OptiX) sofrem com custos de reconstrução que escalam com o deslocamento. Por exemplo, sob SWD, o Embree degradou ~7× enquanto o GRCACPU permaneceu inalterado (<1% de variância).
• Corte de Alcance (Range Culling): Quando alcances de implantação realistas (10–100 m) são aplicados, o GRCA alcança até 9,33× de aceleração sobre o Embree e 7,02× sobre o OptiX.
• Precisão: O algoritmo mantém uma taxa de correspondência de acertos (hit-match rate) $\ge$ 98% contra o OptiX na grande maioria das configurações. As falhas (abaixo de 98%) são atribuídas principalmente a:
  1. Descartes de área aparente (triângulos menores que a resolução do sensor).
  2. Erros de inicialização de busca binária para triângulos oblíquos.
  3. Erros de arredondamento em predicados de saída antecipada.
  4. Ambiguidades na seleção de arcos CW/CCW para triângulos que cruzam costuras.
• Escalabilidade: O desempenho do GRCA é amplamente independente do número de origens de raio ($\Omega$) para o backend de CPU, enquanto o backend de GPU escala linearmente, mas permanece significativamente mais rápido que os baselines mesmo com 8 sensores.

5. Significância e Limitações

O artigo afirma que o GRCA elimina o custo dominante da simulação de LiDAR dinâmica — a construção e travessia de BVH — substituindo-o por uma abordagem de filtragem baseada em computação e orientada à geometria. É particularmente significativo para simulações de alta resolução, multi-sensores e altamente dinâmicas, onde estruturas de aceleração tradicionais falham em amortizar os custos.

Limitações reconhecidas pelos autores:

• Cenas Estáticas: O GRCA não oferece vantagem sobre a BVH para geometria puramente estática onde os custos de reconstrução são inexistentes.
• Restrições de Ruído: O algoritmo suporta ruído de distância e azimute, mas não suporta ruído vertical por raio (offsets de elevação independentes por raio dentro de um canal), pois o predicado GACP-T avalia em uma única elevação nominal por canal.
• Precisão: Embora alta, a precisão pode cair abaixo de 98% em casos específicos envolvendo cenas compactas com tesselação fina e deformação extrema, embora estas sejam atribuídas a incompatibilidades entre sensor e geometria, e não a defeitos algormítmicos.

Os autores concluem que o GRCA reduz o limite de interseção de força bruta em três a sete ordens de magnitude em cenários dinâmicos práticos, oferecendo uma solução agnóstica de fornecedor para simulação de LiDAR em tempo real.