Qual estrutura de dados deve ser usada para representar o terreno voxel?

18

De acordo com a página da Wikipedia sobre voxels, "[...] a posição de um voxel é inferida com base em sua posição em relação a outros voxels (ou seja, sua posição na estrutura de dados que compõe uma única imagem volumétrica)".

Como se deve implementar essa estrutura de dados? Eu estava pensando em uma octree, mas me pergunto se há algo mais sobre o qual nunca ouvi falar.

pwny
fonte
11
Essa é uma pergunta um tanto difícil de ser feita, pois depende muito de quais dados seus dados voxel precisarão. Coisas como quão cheio o voxel está, como ele é, etc., dependerão bastante do que você está fazendo. Em segundo lugar, a estrutura de dados deve se prestar a acesso de alta velocidade para manipulação em tempo real dos dados e subsequente atualização dos mesmos. Como manter a estrutura da memória baixa por voxel e o acesso / manipulação rápidos de dados são os principais desafios técnicos que são intenção bastante específica ao trabalhar com motores voxel. Não é uma resposta, é um comentário.
James

Respostas:

14

Primeiro. Vamos escrever o que sabemos sobre cada voxel:

voxel = (x, y, z, color) // or some other information

Armazenamento geral

A maneira geral é simplesmente esta:

set of voxels = set of (x,y,z, color)

Observe que esse trigêmeo (x, y, z) identifica cada voxel de forma única, uma vez que o voxel é um ponto no espaço e não há como dois pontos ocuparem um lugar (acredito que estamos falando de dados estáticos de voxel).

Deve ser bom para dados simples. Mas não é de forma alguma uma estrutura de dados rápida.

A renderização é AFAIK feita pelo algoritmo scanline. O artigo de Tom's Hardware sobre voxels possui uma imagem do algoritmo scanline .

Pesquisa rápida

Se a pesquisa rápida for necessária, a estrutura de dados mais rápida para a pesquisa é o hash (também conhecido como array, mapa ...). Então você tem que fazer hash com isso. Então, ingenuamente, queremos a maneira mais rápida de obter um elemento arbitrário:

array [x][y][z] of (color)
  • Isso tem O (1) para procurar voxel pelas coordenadas x, y, z.

  • O problema é que seus requisitos de espaço são O (D ^ 3), onde D é o intervalo de cada número x, ye z (esqueça o número real, pois se fossem caracteres Chars, com intervalo de 256 valores, haveria 256 ^ 3 = 2 ^ 24 == 16 777 216 elementos na matriz).

Mas isso depende do que você quer fazer com voxels. Se a renderização é o que você deseja, provavelmente é essa matriz o que você deseja. Mas o problema de armazenamento ainda permanece ...

Se o armazenamento é o problema

Um método é usar a compactação RLE na matriz. Imagine uma fatia de voxels (conjunto de voxels, em que voxels têm um valor constante de coordenada ... como um plano em que z = 13, por exemplo). Essa fatia de voxels pareceria um desenho simples no MSPaint . O modelo Voxel, eu diria, geralmente ocupa fração de todos os lugares possíveis (espaço D ^ 3 de todos os possíveis voxels). Eu acredito que "pegar um par de trigêmeos de coordenadas e comprimir o eixo restante" faria o truque (por exemplo, pegue [x] [y] e, para cada elemento, comprima todos os voxels no eixo z em x, y .. deve haver de 0 a poucos elementos, o RLE faria bem aqui):

array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color 

Outro método para resolver o problema de armazenamento seria, em vez de matriz, usando a estrutura de dados em árvore:

tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
  • Octree, como mencionado por Nick. Deve comprimir voxels. Octree tem até uma velocidade decente de pesquisa, acho que é algum O (log N), onde N é o número de voxels.
  • A Octree deve ser capaz de armazenar dados voxel arbitrariamente decentes.

Se os voxels são um mapa de altura simplista, você pode armazenar exatamente isso. Ou você pode armazenar parâmetros para funcionar, o que gera o mapa de altura, também conhecido como procedimento.

E, claro, você pode combinar todas as abordagens possíveis. Mas não exagere, a menos que você teste se seu código funciona e meça REALMENTE mais rápido (por isso vale a pena a otimização).

TL; DR

Além de Octrees, é a compactação RLE com voxels, google "voxlap", "ken silverman" ...

Recursos

Há uma lista de recursos e discussão sobre como fazer renderizador voxel rápido, inclui papéis e código fonte .

user712092
fonte
11
"Se o armazenamento é o problema": também é possível usar a compactação VTC ( oss.sgi.com/projects/ogl-sample/registry/NV/… ) ou DXT
KindDragon
@KindDragon obrigado por esta informação. :) Essa é uma ideia muito boa.
user712092
O link do recurso está inoperante.
Ezequiel
4

Existem dois aspectos diferentes da estrutura de dados sobre os quais eles podem estar falando.

Estruturas de matriz

Ao fazer referência a um elemento de uma matriz de qualquer número de dimensões, considere que a própria matriz, depois de passar os índices (por exemplo, myArray[4][6][15]), sabe o que está nesse local. Se o que está nesse local é um voxel, esse voxel não precisa registrar adicionalmente suas próprias coordenadas x, ye z - a matriz que contém o voxel especifica sua localização mundial implicitamente com base em sua localização indexada à matriz.

A razão disso é que a aritmética do ponteiro usada para esse tipo de acesso à matriz é inerentemente rápida e, de um modo geral, fornece a base para a maioria das matrizes rápidas (geralmente chamadas de "nativas") encontradas nos idiomas. A desvantagem dessas matrizes é que elas devem ter elementos de tamanho igual em bytes, para que a referida aritmética do ponteiro seja aplicável.

Octrees

(Observo este segundo, porque é menos provável que isso se refira à wikipedia e as implementações de voxel não exigem o uso de octrees, embora quase todas as modernas usem octrees.)

O nó raiz de um octree é um cubo único e não dividido. Vamos criar um exemplo. Digamos que a raiz do seu octree, o centro do cubo, esteja no {0, 0, 0}espaço 3D. Depois que você começa a colocar objetos nesse espaço (leia: mais de um objeto), é hora de subdividir ainda mais a octree. É aqui que você se divide em 8 ( outubro ), cortando-o usando 3 planos, sendo esses planos os planos xy, xz e yz. Seu cubo original agora contém exatamente 8 cubos menores. Cada um desses subnós é posicionado como um deslocamento do cubo pai central . Ou seja, que, por exemplo, o cubo localizado no octante xyz positivo teria um deslocamento do centro do cubo pai / contendo exatamente{root.width / 4, root.height / 4, root.depth / 4}. Em vez de especificar uma posição absoluta para cada subnó, faz mais sentido lógico considerar o nó pai como a origem do espaço do seu filho. É assim que os gráficos de cena funcionam.

É simples o suficiente para ver isso em um desenho 2D, onde você desenha um quadrado e subdividi-lo em 4 regiões iguais. Se, como nosso nó raiz octree, o centro do quadrado pai fosse considerado {0, 0}, então os 4 centros dos quadrados filhos seriam

{root.width / 4, root.height / 4}, {-root.width / 4, root.height / 4}, {root.width / 4, -root.height / 4}, {-root.width / 4, -root.height / 4}

... Em relação aos pais - o mesmo princípio que em 3D.

Engenheiro
fonte
Obrigado pela sua resposta. No meu caso, algumas partes grandes do terreno seriam feitas com o mesmo tipo de voxel, e é por isso que eu estava pensando em octrees (um pedaço grande não precisaria ser subdividido). No entanto, vou dar uma chance ao array 3D, pois parece mais simples de implementar. Tenho certeza de que posso abstrair os detalhes da implementação da minha classe de terreno o suficiente para que não seja tão difícil alternar implementações, se necessário.
pwny
Seja bem-vindo. Definitivamente, eu sugeriria olhar para as octrees, na verdade elas não são difíceis de entender. Mas sim, sua abordagem faz sentido por enquanto; certamente vale a pena fazer a prototipagem inicial usando uma matriz 3D.
coordenador
Como leitura adicional, uma boa discussão sobre a implementação de octrees, incluindo várias referências úteis, pode ser encontrada no artigo Extending the STL for Games da Intel .
Martin Foot
1

Você pode usar o RLE. Mas você pode usar o SVO (Sparse Voxel Octree), o id Tech 6 usa o SVO. Um SVO é uma técnica de renderização de gráficos de computador em 3D usando uma transmissão de raios ou, às vezes, uma abordagem de rastreamento de raios em uma representação de dados octree.

A técnica varia um pouco, mas geralmente depende da geração e processamento do casco de pontos (voxels esparsos) que são visíveis ou podem ser visíveis, dada a resolução e o tamanho da tela.

Use raycasting, porque é mais rápido.

RealTimeGraph9999
fonte
0

Geralmente, você pode evitar uma estrutura de dados 3D para terrenos. Você pode usar um mapa de altura . Isso pode ser voxelizado de maneira muito barata e eficiente em tempo de execução. Geralmente vale a pena (na minha experiência) rastrear a altura mínima que você precisa renderizar em cada coluna e, às vezes, também os ângulos start-stop-top para que você possa selecionar também as colunas da face posterior.

Aqui está um que eu fiz há muito tempo: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

Se o terreno possui um pequeno número de saliências, cavernas ou outros recursos que não podem ser representados por um mapa de altura, você pode fazer furos no mapa de altura e ter uma representação alternativa, por exemplo, objetos voxel 3D verdadeiros que preenchem apenas os locais localizados onde as despesas de execução é garantido.

Representações esparsas de voxel valem a pena quando você tem grandes mundos verdadeiros de voxel. John Carmack tem falado com eles nos últimos anos ...

Vai
fonte
Também pensei em mapas de altura, mas algumas coisas me afastaram deles. O fato é que, no meu caso, o terreno não é realmente grande de forma alguma ou muito complicado (pense em um tipo de labirinto, muito cartesiano). Eu também gostaria que parte do terreno fosse destrutível ou permitisse ao usuário afetar o terreno através da construção. Isso pode resultar na criação de "túneis" no terreno que parecem mais complicados de representar com um mapa de altura.
pwny 9/09/11