Divisão Octree

7

Eu tenho um octree, com um coelho de alto poli e uma plataforma de 12 polígonos.

O negócio é esse. Você está atirando um raio no coelho. Ele obviamente se esquiva (ou você sente falta).

atirar coelho

O feixe amarelo é o seu laser da morte.

Os triângulos "candidatos" que são selecionados devido às partes da octree atingida são mostrados em roxo.

atirar coelho 2

Claramente, você tem essa distribuição que ocorre, porque o nó raiz foi atingido, você acabou testando quaisquer polys no nó raiz. E as polys que estão nas bordas da subdivisão octree terminam no nó raiz, com o algoritmo de subdivisão que estou usando.

Então, eu quero reduzir o número de polys no nó raiz.

Se eu apenas mover o coelho para o canto, coelho de canto

Com o coelho no canto, traçando a cena inteira, leva 1/3 do tempo (35s vs 95s se o coelho estiver no meio). Acredito que isso ocorre porque menos triângulos do coelho estão na raiz, e os hits apenas da raiz do octree verificam menos polígonos.

Estou pesquisando maneiras de melhorar o desempenho. Basicamente, empurre o tris o mais longe possível da árvore, para que os objetos fiquem principalmente nas folhas.

Tentei fazer isso ingenuamente e usei esse algoritmo de subdivisão que criei:

split root into 8 CANDIDATE CHILDREN
foreach TRI in root:
  foreach of the 8 CANDIDATE CHILDREN
    if the CANDIDATE CHILD partially contains TRI (at least one vertex of TRI)
      add TRI to CANDIDATE CHILD
CLEAR tris in root

Isso empurra triângulos para baixo na hierarquia em nós de folha. Mas eu tenho buracos de certos ângulos, com padrões estranhos de falta:

(esperado) cena holeless esperada

furos de um ângulo:

furos de um ângulo

mesma cena, ângulo diferente:

mesma cena, ângulo diferente

Eu acho que é porque estou limpando a raiz. (Porque quando eu não limpo a raiz, o raytracing funciona corretamente, todos os ângulos)

Eu "empurrei" os polígonos pela árvore corretamente? Alguém pode adivinhar por que tenho buracos?

Como você melhora o desempenho do seu octree?

Eu tenho que dividir os triângulos? Estou tentando evitar isso, para não ficar mais e mais triângulos / multiplicar a geometria da cena mais do que preciso.

Também estou ciente de que as árvores KD e de que devem superar os octrees, mas também exigem a divisão de polis, estou realmente procurando maneiras de melhorar meu octree aqui.

bobobobo
fonte
2
As primitivas devem sempre estar nas folhas. Considere também usar uma árvore B + com particionamento não uniforme (os cuboides dentro de um cuboide não precisam ser distribuídos igualmente) e particione o espaço de acordo com o fato de ter primitivos ou não. Também -1 para disparar raios da morte em coelhos inocentes :).
31712 Jonathan
Eu acho que sua seção 'editar' praticamente respondeu sua própria pergunta; você deve publicá-lo como resposta e aceitá-lo.
21412 Trevor Powell

Respostas:

2

Agora entendo por que tenho buracos. Estou usando um mau esquema de contenção parcial do triângulo AABB: um AABB "continha parcialmente" um triângulo se o AABB continha pelo menos um vértice do triângulo. quase vazio

Os E estão "vazios", de acordo com o mau esquema de detecção "Triângulo parcialmente no AABB".

Acho que isso significa que, se você quiser empurrar tudo para os nós das folhas, deverá dividir os triângulos.

bobobobo
fonte
4
Divida os triângulos ou empurre triângulos em todos os nós das folhas com os quais eles se cruzam; não apenas os que contêm seus vértices.
Trevor Powell