Como posso gerar campos de distância assinados (2D) em tempo real, rapidamente?

21

Em uma pergunta anterior , sugeriu-se que os campos de distância assinados possam ser pré-computados, carregados em tempo de execução e usados ​​a partir daí.

Por razões que explicarei no final desta pergunta (para pessoas interessadas), preciso criar os campos de distância em tempo real.

Existem alguns documentos disponíveis para diferentes métodos que deveriam ser viáveis ​​em ambientes de tempo real, como métodos para transformações à distância de chanfro e transformações baseadas em aproximação de diagrama de Voronoi (conforme sugerido nesta apresentação pelo desenvolvedor Pixeljunk Shooter ), mas Eu (e, portanto, pode-se supor que muitas outras pessoas) têm muita dificuldade em realmente usá-las, uma vez que geralmente são longas, inchadas em grande parte com matemática e não muito algorítmicas em suas explicações.

Qual algoritmo você sugeriria para criar os campos de distância em tempo real (favoravelmente na GPU), especialmente considerando a qualidade resultante dos campos de distância?

Como estou procurando uma explicação / tutorial real, em vez de um link para apenas outro artigo ou slide, essa pergunta receberá uma recompensa assim que for elegível para uma :-).

Aqui está o porquê eu preciso fazer isso em tempo real:

Se você precisar precomputar esses SDFs para grandes ambientes 2D (pense em um mapa grande como Terraria), isso significa que você está aceitando uma sobrecarga bastante grande no espaço de armazenamento (e no tempo de geração do mapa) em favor da implementação de um algoritmo complicado, rápido o suficiente para gerar SDF em tempo real.

Por exemplo, um mapa relativamente pequeno com 1000 * 256 (largura * altura) com um tamanho de bloco de 10 * 10 pixels e, portanto, dimensões totais de 10000 * 2560 pixels já custaria cerca de 2 megabytes de tamanho, se você escolher um tamanho relativamente pequeno Resolução SDF de 128x128, supondo que você esteja armazenando apenas os valores de distância de 0 a 255.

Obviamente, isso pode se tornar rapidamente demais e é uma sobrecarga que eu não quero ter.

Há algo mais:

Os SDFs podem ser usados ​​para muitas coisas (como detecção de colisão), e alguns aplicativos úteis ainda não foram descobertos. Eu acho que muitas pessoas vão procurar essas coisas no futuro, e se tivermos uma resposta abrangente aqui, acho que vamos ajudar muitas pessoas.

TravisG
fonte
Pesquisei no Google "o que é um campo de distância assinado" e o primeiro hit foi uma versão da GPU: http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html É um pouco antiga, mas pode ajudar ainda mais em suas pesquisas.
Patrick Hughes
1
Talvez esteja faltando alguma coisa, mas estou um pouco confuso com a afirmação de por que você precisa fazê-lo em tempo real (não menos importante, por que está marcado com spoilers); Em primeiro lugar, onde você obtém a figura de 2 MB para um SDF de 128x128? Em segundo lugar, por que você considera 2 MB um uso de memória particularmente pesado? Concordo que não é substancial, mas parece uma pequena fração do uso geral da memória do mapa. E terceiro, como a geração do campo em tempo real salvará essa memória? Você ainda precisa armazenar exatamente os mesmos dados, sejam eles gerados dinamicamente ou pré-computados, não?
Steven Stadnicki
De maneira mais ampla, pode ser que os SDFs não sejam a técnica que você precisa. Mais informações sobre sua situação específica - contagem estática de obstáculos, contagem dinâmica de obstáculos etc. - e precisamente o efeito que você espera alcançar seria útil para tentar identificar o que provavelmente será útil para você.
Steven Stadnicki
1
Se eu gerasse o campo de distância em tempo real, criaria apenas esses 2 MB uma vez por quadro (a sobrecarga total de memória sempre seria a memória necessária para um campo de distância, pois eu preciso apenas do campo da tela). Se eu tiver um mapa maior que o meu exemplo de 1000x128 (acho que grandes mapas de Terraria vão muito além dos 10000), preciso de um desses 2mb para cada submapa de 1000x128 desse mapa. Por que eu preciso de SDFs em primeiro lugar está descrito na primeira pergunta que eu vinculei no início desta pergunta (é para a projeção de sombra 2D da GPU).
TravisG
1
@heishe você está tentando gerar 2Mb de dados uma vez por quadro? A sério?
kaoD

Respostas:

9

Catalin Zima explica como obter sombras 2D dinâmicas em seu artigo - e ele usa um campo de distância assinado (pelo que posso dizer que é apenas um nome sofisticado para um buffer de sombras neste contexto). Seu método precisa de uma GPU, e sua implementação como está não é a melhor (a sua caiu abaixo de 60Hz a cerca de 20 luzes na minha máquina, a minha tem cerca de 500 luzes); o que é esperado, já que ele favoreceu a clareza do código sobre a velocidade.

Implementação

Exatamente como implementado por ele:

  1. Renderize todos os rodízios de sombra em uma textura.
  2. Calcule a distância do centro da luz para cada pixel e atribua esse valor ao RGB dos pixels opacos.
  3. Distorça a imagem para representar como uma câmera 3D teria visto esses pixels.
  4. Agrupe a imagem em uma imagem de tamanho 2xN usando o redimensionamento incomum descrito em seu artigo (um redimensionamento simples não funcionará).
  5. A imagem 2xN agora é o seu campo de distância assinado para todos os quatro quadrantes da luz (lembre-se de que um quadrante é basicamente um único frustum de câmera a 90 graus).
  6. Renderize o mapa de luz.
  7. Desfoque o mapa de luz (com base na distância da luz) para obter sombras suaves.

Minha implementação final foi (cada etapa sendo um único sombreador):

  1. Faça (1).
  2. Faça (2) e (3) .
  3. Faça (4). Sua implementação é realmente lenta: se você pode tentar usar o GPGPU para isso. Eu não poderia usar GPGPU (XNA), então o que eu fiz foi:
    • Configure uma malha na qual as primeiras colunas N / 2 foram representadas por quadras N / 2 com a mesma posição EXATA (cobrindo a primeira coluna do buffer final), mas com coordenadas de textura diferentes (o mesmo para as segundas colunas N / 2)
    • Desative o teste de profundidade na GPU.
    • Use a função de mistura de pixels MIN.
  4. Faça (6) e (7).

É bastante engenhoso: é basicamente uma tradução direta de como as sombras são manipuladas em 3D para 2D.

Armadilhas

A principal armadilha é que alguns objetos não devem ser sombreados: no meu exemplo, eu estava escrevendo um clone do Liero (worms em tempo real) e, portanto, não queria, por exemplo, que os worms dos jogadores fossem sombreados (pelo menos aquele na tela de cada jogador). Tudo o que fiz para esses objetos 'especiais' foi redesenha-los como um último passo. A ironia era que a maioria dos objetos não era sombreada (worms, primeiro plano da paisagem), então há um problema de excesso de dados aqui.

Jonathan Dickinson
fonte
O seu ajuste no método de redimensionamento foi a única coisa a acelerar para lidar com 500 luzes acima de 60fps?
TravisG
OK, aceitarei a resposta, pois resolve o meu problema original, mas na verdade não responde pelo que dei a recompensa. Vou esperar e talvez alguém se esforce muito para explicar um dos vários métodos O (N) para a geração de campos a distância assinados.
TravisG
@heishe em relação à sua primeira pergunta: não tenho certeza. Fiz todas as otimizações de uma só vez - acho que lembro de desligá-lo e ver a taxa de quadros cair substancialmente. As 6 chamadas all-in-all por luz matam sua taxa de quadros. Como eu disse, pelo que sei, você tem quatro campos de distância assinados na etapa (5) - mas alguém que sabe mais sobre eles precisará confirmar isso.
11136 Jonathan Dickinson
Bem, é um caso muito especial de um campo de distância assinado. Em um campo de distância sinalizada normal, cada pixel contém a distância do obstáculo mais próximo. Nesse algoritmo, o campo de distância contém apenas um obstáculo, e também o obstáculo é de apenas 1 pixel na imagem inteira (a fonte de luz), razão pela qual esse campo de distância pode ser gerado em O (N).
TravisG
1
@heishe, aqui está meu shader: gist.github.com/2384073 . O DistortPS é 2 + 3.
31712 Jonathan