Rendering em Tempo Real

Rendering em Tempo Real

Técnicas de Aceleração

Waldemar Celes Departamento de Informática

Tecgraf/PUC-Rio

Técnicas de Aceleração

w  Objetivo n  Aliviar esforço na GPU

l  Usando CPU l  Usando a própria GPU

w  Exemplos n  Técnicas de culling

l  Descartar objetos que não contribuem para imagem final

n  Técnicas de multi-resolução (LOD) l  Representar objetos distantes

em baixa resolução

Técnicas de Culling

w Frustum culling n  Descarta objetos fora do volume de visão

w Back face culling n  Descarta faces “voltadas para trás”

w Occlusion culling n  Descarta objetos totalmente oclusos

Frustum Culling

w Hierarquia de volumes envolventes n  Para cada nó

l VE fora do frustum w  Descarta sub-nós

l VE intercepta o frustum w  Repete teste para todos os filhos

l VE dentro do frustum w  Desliga teste e desenha sub-nós

Frustum Culling

w Hierarquia de volumes envolventes n  Volumes envolventes candidatos

l Caixa alinhada (AABB) l Caixa orientada (OBB) l Esfera

n  Avaliação l  Fácil computação (pré-processamento?) l Eficiente teste de interseção l Bom ajuste à geometria representada

Frustum Culling

n  Cálculo do volume envolvente l Caixa alinhada (AABB)

w  Determinação de mínimos e máximos: O(n)

l Caixa orientada (OBB) w  Baseado na distribuição Gaussiana anisotrópica

§  Centro geométrico: C = 1/n Σ Vj §  Avalia: Wj = Vj – C e

M3x3 = Wj WjT §  Eixos ui: autovetores de M §  Semi-eixos: hi = maxj [ui . (Vj - C)] §  Reposiciona centro C

Obs: não é a OBB ótima (mínima)

Frustum Culling

l Esfera w  Ache três pares de vértices:

§  {xmin, xmax}, {ymin, ymax}, {zmin, zmax} §  Esolha o par mais distantes

w  Inicie C como centro deste par §  E raio r como semi-distância

w  Para cada vértice: §  Calcule d = dist(Vj, C) §  Se d > r:

§  C = C + (d-r)/2 |d| §  r = (d+r)/2

Obs: não é a esfera ótima (mínima)

Frustum Culling

w  Frustum x VE n  Onde fazer o teste?

l  Espaço do objeto n  Frustum

l  Definido por seis planos: ni.x + di = 0 n  Testa VE contra cada plano

l  Fora w  “Fora” de pelo menos um plano

l  Dentro w  “Dentro” de todos os planos

l  Intercepta w  Nem dentro nem fora

l  Teste conservativo w  Pode errar, mas é rápido

Intercepta planos, mas está fora do frustum

Frustum Culling

w Teste de interseção: VE x plano n  Esfera n  Caixa alinhada (AABB) n  Caixa orientada (OBB)

Frustum Culling

w Teste de interseção: esfera x plano n  Plano: [n d] n  Esfera: c, r n  Teste: n.c + d > r

Frustum Culling

w Teste de interseção: AABB x plano n  Caixa alinhada: bmin, bmax

n  Das 4 diagonais, escolhe-se a mais alinhada com a normal do plano l Testa apenas dois pontos: vmin, vmax

w Determinação de vmin, vmax n  Acessa LUT com sinal da normal

l Por exemplo: n = [-1 0.5 2] w  vmax = LUT[011] = LUT[3] = {bxmin, bymax, bzmax} w  vmin = LUT[100] = LUT[4] = {bxmax, bymin, bzmin}

Frustum Culling

w Teste de interseção: OBB x plano n  Caixa orientada: ui, hi com i = 0, 1, 2

n  Projeta semi-eixos na direção normal e obtém raio da esfera virtual equivalente

l  r = Σi hi |n.ui|

Frustum Culling

w Coerência temporal n  Guardar testemunho junto ao VE

l Se fora, guarda plano usado na classificação l Próximo teste, começa por este plano

w  Alta probabilidade de VE continuar “fora” deste plano

w Máscara na descida da hierarquia n  Se dentro, passa adiante plano

l  Filhos não precisam ser testados com este plano

Back Face Culling

w Back face culling do pipeline n  Face a face

l Efetuado no espaço da tela w  Evita imprecisão numérica

w Cone de normais n  Cria cluster de normais n  Aplicações

l Determinação de back faces w  Culling w  Iluminação

l Acelera detecção de silhuetas

Back Face Culling

w Determinação do cone de normais n  “The cone of normals techinique for

fast processing of curved patches” l  L. A. Shirman and S. S. Abi-Ezzi

w Dada uma “clusterização” do modelo, determina o cone de normais de cada sub-superfície

Back Face Culling

w Passo 1 n  Cone de normal flutuante

l  “Envolve” todas as normais w  Sem ancoragem geométrica

C-264 L.A. Shirman et al. / Cone of Normals Technique Curved Patches

Figure 2: Construction of the floating cone.

2.2. Construction of the Floating Cone Once the normal patch has been computed, the floating cone is constructed. The floating cone

contains all the normal directions of the original patch, and it is floating since it has no position, only an orientation.

For the construction of the floating cone, we assume that all the control vectors are anchored at the origin. By the convex hull property, the tips of all the normals to the original patch when anchored at the origin, are contained in the convex hull of the tips of the control vectors of the normal patch. Assume that these control vectors (or their extensions) intersect the unit sphere, also centered at the origin, at points Then the smallest enclosing sphere of all the intersection points is constructed. The floating cone, when anchored at the origin, is defined to pass through the intersection circle of the two spheres, which is shown in Fig. 2a.

Finding the smallest enclosing sphere of a given set of points in space is a computational geometry problem. There are exact and iterative algorithms for its computation [Lawson65], but they are rather slow. Instead, we use a bounding box approach, which is very fast and in practical situations it produces a fairly close approximation to the enclosing sphere.

The idea of the method is very simple. A bounding box of all the points is constructed. The center of the enclosing sphere is defined to be the center of the bounding box. The radius is then defined by the largest distance from the center to one of the points (Fig. 2b).

In practice we construct the cone without finding the enclosing sphere explicitly. We determine the cone axis to pass through the origin and the center of the enclosing sphere, C, where

Back Face Culling

w Passo 2 n  Ancora e trunca cone

l Deve envolver todos os vértices w  Acha ponto mínimo no eixo: B como apex inicial w  Projeta pontos fora do cone no plano de B w  Círculo envolvente dos pontos projetados define

seção do cone no plano, deslocando apex. C-266 L.A. Shirman et al. / Cone of Normals Technique Curved Patches

Figure 3: Construction of the anchored truncated cone.

Clearly, for any point S above the bottom plane and outside of the translated cone, a ray from S parallel to any cone side does not intersect the smallest enclosing circle. Therefore, since every projected point inside the circle was obtained by projecting parallel to one of the cone sides, then and hence the whole patch, must lie inside the translated cone.

Finally, the top plane is determined in a similar fashion to obtaining the bottom plane. Both the bottom and the top planes are used to truncate the anchored cone as shown in Fig. 3b. Therefore, by construction the anchored truncated cone contains all the points of the patch and al l the normals at these points.

2.4. Construction of Frontfacing and Backfacing Regions

After the above operations, we partition the space into a frontfacing region, a backfacing region, and a neutral region in relation to the given patch; see Fig. 4. We show the construction of these regions in a 2D slice of the cone through its axis, which then gets generalized to 3D in a straightforward fashion.

The truncated cone ABCD contains a l l the points of the patch and the normal directions at these points. The frontfacing region EFG and the backfacing region KLM are constructed by drawing perpendiculars BG and DK to side AB, and CE and AM to side CD as shown in Fig. 4. Point F is the intersection of rays BG and CE, while point L is the intersection of rays DK and AM.

For any point P and any direction n inside the truncated cone the following relationships hold:

For any point N in the frontfacing region, the angle between PN and n is less than For any point in the backfacing region, the angle between and n is greater than For any point S which lies in the neutral region (neither in the frontfacing nor in the backfacing regions), the angle between PS and n can generally range from 0 to

Back Face Culling

w Passo 3 n  Define regiões back & front facing

l Construção geométrica L.A. Shirman et al. / Cone of Normals Technique Curved Patches C-267

Figure 4: A cross-section of the cone through its axis to show the Frontfacing and backfacing regions.

As we will see in the next section, these relationships are crucial for fast patch level tests. An imperative reasoning for the first of the above relationships is as follows: for a given fixed

point P in the truncated cone, consider the set S(P) of all points N such that the angle between PN and any direction n inside the truncated cone is less than This set is a cone centered at P with the axis parallel to the truncated cone axis and with the semiangle of a, where a is the truncated cone semiangle. Since the above relationsip must hold for all points P in the truncated cone ABCD, the frontfacing region can be defined as an intersection of a l l sets S(P) as P spans ABCD, which results exactly in EFG. Similar reasoning holds for the backfacing region.

By construction, the frontfacing and backfacing regions are actually full cones with apexes at F and L respectively. These apexes lie on the axis of the truncated cone. The semiangles of both cones are equal to The distance from the bottom plane to L is equal to tan (a), where is the radius of the bottom circle as determined in the previous section. Analogously, the distance from the top plane to F is equal to tan (a), where is the radius of the top circle, T h i s radius can be expressed in terms of the radius of the bottom circle and the vertical length l of the truncated cone:

As pointed out earlier, this construction only makes sense when a is less than since when the floating cone spans more than a halfspace, then obviously there will be no value in using this technique.

Culling por Oclusão

w  Consulta de oclusão (occlusion query) n  Assistido pela GPU n  Retorna número de pixels desenhados

w  Técnica de aceleração n  Desenha objetos na ordem “front-to-back”

l  Ou desenha os principais oclusores n  Testa oclusão cada objeto n  Desenha objeto se no de pixels visíveis for considerável

w  Adequado para cenas com grandes oclusores n  Modelos de arquitetura

Hardware Occlusion Queries Made Useful, Wimmer and Bittner, GPU Gems 2, 2005

Funcionamento

w  Inicia consulta w  Desliga escrita nos buffers (color & Z) w  Desliga estados supérfluos (lighting, etc.) w  Desenha uma aproximação simples do objeto

n  E.g. caixa envolvente n  GPU computa no de pixels que seriam visíveis

w  Termina consulta w  Requisita resultado da consulta

n  Modal w  Avalia necessidade de desenhar objeto

n  Se no de pixels > threshold

Algoritmo Simplista

w Ordena objetos em “front-to-back” n  Ordenação pode ser aproximada n  Ou desenha oclusores potenciais

w Para cada objeto n  Requisita uma consulta n  Espera pela resposta da consulta n  Avalia necessidade de renderizar

l Pode usar renderização condicional da API gráfica

Problemas

w Custo da consulta n  Renderização das caixas envolventes

l Geometria, rasterização e teste em Z

w Latência da resposta n  Espera do resultado é modal

Minimizar número de consultas

w Uso de hierarquias n  Mas consultas de grandes caixas é caro

l Alto custo de rasterização n  Pode ter efeito reverso se não há oclusão

Evitar latência

w Minimizar ociosidade dos processadores n  CPU ociosa para GPU terminar consulta n  GPU ociosa pois CPU não enviou primitivas

w Resposta é modal, mas... n  Consulta não é modal n  Pode-se requisitar várias

Solução Aproximada 1

w Explorar coerência entre frames w Usar z-buffer do quadro anterior

n  Requisita as consultas n  Limpa buffer n  Renderiza objetos cujas VE são “visíveis”

w  Imagem final com erro

Solução Aproximada 2

w Explorar coerência entre frames w Processar objetos em “front-to-back”

n  Renderizar objetos, requisitando consulta l Resultado usado no quadro seguinte

w  Imagem final com erro

Explorando hierarquia e coerência

w Evitar latência n  Intercala consulta com renderização

l Requisita consulta, mas não espera resposta

n  Prever o resultado da consulta l Visível x Não-visível l Explorar coerência temporal l Usa classificação do quadro anterior

w Possíveis erros de previsão n  Antes visível, agora não visível

l Processamento de renderização desnecessário w  OK, não gera erro

l Classificação corrigida para próximo quadro n  Antes não-visível, agora visível

l Deve ser corrigido l Re-processamento do nó é necessário

w  Quando resposta estiver disponível


w  Minimizar número de consultas n  Consultas para nós internos

l  Se era visível, não requisita consulta w  Re-classifica como não-visível w  Corrigido pela propagação da classificação dos filhos aos pais

l  Se era não visível, consulta é necessária w  Depois, verifica se previsão estava correta

n  Consultas necessárias para alguns nós apenas l  Folhas antes visíveis

w  Para atualizar e propagar visibilidade aos pais l  Nós antes não visíveis

w  Muitos continuarão não-visíveis §  Filhos não processados


Algoritmo

w  Estrutura hierárquica n  Percorrida em ordem “front-to-back” n  Pilha para gerenciar nós visitados

l  Ainda por ser processados w  Gerenciamento das consultas

n  Fila de consultas pendentes n  Verifica existência de resposta

l  Após processamento de cada nó n  Verifica previsão

l  Se OK: nada a fazer l  Se errada:

w  Se era visível: atualiza classificação, propagando aos pais w  Se era não-visível: processa nó imediatamente

Pseudo-código

Stack.Push (root) while (not Stack.Empty() or not Queue.Empty()) do // process query queue while (not Queue.Empty() and ResultAvailable(Queue.Front()) or Stack.Empty()) do node = Queue.Remove( visiblePixels = GetOcclusionQueryResult(node) if (visiblePixels > VisibilityThreshold) then PullUpVisibility(node) TraverseNode(node) end end

Pseudo-código

// process hierarchy if (not Stack.Empty()) do node = Stack.Pop() if (InsideFrustum(node)) then wasVisible = (node.classification == VISIBLE) or IsLeaf(node) node.classification = NOT_VISIBLE if (not wasVisible) then IssueOcclusionQuery(node) Queue.Insert(node) end if (wasVisible) then TraverseNode(node) end end end end

Pseudo-código

function TraverseNode (root) if (IsLeaf(node)) Render(node) // may be called more than once else Stack.PushChildren(root) // in front-to-back order end end function PullUpVisibility (node) while (node.classification == NOT_VISIBLE) do node.classification = VISIBLE node = node.parent end end

Otimizações

w  Consulta com geometria renderizada n  Para nós visíveis

l  Desenha de qualquer forma w  Desacoplar consulta de renderização

n  Consulta: z-only rendering pass l  HW pode oferecer aceleração para esta passada

n  Duplica transformações n  Pode renderizar objetos ordenados por estado

w  Teste de visibilidade conservativo n  Fazer o estado visível válido por alguns quadros

w  Visibilidade aproximada n  Aumentar o threshold para considerar visível n  Pode ter efeito reverso!

Otimizações

w  Usar lista de prioridade para processar nós n  Ordenada pela distância ao observador n  Vantagens

l  Generaliza o uso de hierarquias l  Evita dependência de visitação dos nós

w  O algoritmo não garante ordem devido às consultas

15/12/2006 Projeto Final - Paulo Ivson 36

Teste de desempenho (Ivson, 2006)

w  Navegação ao longo de caminho aleatório n  Variando número de objetos visíves

w  Base de comparação n  Renderização simples, sem otimizações

w  Avaliar n  Impacto de diferentes hierarquias n  Algoritmo de descarte contra volume de visão n  Algoritmo de descarte por oclusão n  AABB, OBB Clássica e Aproximada Mínima


Teapots(500,30)

w  Pouca complexidade geométrica w  Muita oclusão w  “Cenas que já possuem bom desempenho”


Teapots(500,30)

w AABB

n  Hierarquia: Sem diferença significativa n  Descarte contra volume de visão: 5% n  Descarte por oclusão: 40%

tempo area simples vfc chcMed_Obj 1,31 570.884,5 3,134 2,982 1,892Med_Esp 1,36 548.270,2 3,165 2,984 1,917Med_Cent 1,35 564.459,2 3,168 2,980 1,890Avg_Cent 1,31 561.398,3 3,169 3,010 1,888Eq_Comp 1,30 573.621,8 3,185 2,982 1,892SAH 216,28 515.468,2 3,133 2,983 1,924

Hierarquia Visualização


Teapots(500,30)

w OBB Clássica

n  Minimizar SAH obtém o pior resultado n  Demais são similares

tempo area simples vfc chcMed_Obj 1,42 588.440,0 3,162 2,979 1,919Med_Esp 1,47 565.394,9 3,131 2,980 1,928Med_Cent 1,48 577.345,2 3,132 2,978 1,924Avg_Cent 1,44 579.327,5 3,138 2,978 1,919Eq_Comp 1,42 589.520,4 3,160 2,977 1,923SAH 260,31 517.034,2 4,855 4,633 2,867



Teapots(500,30)

w OBB Aproximada Mínima

n  Tempo elevado de construção n  Resultados semelhantes

l  Ligeiramente melhores (0,04 s) n  Não vale a pena!

tempo area simples vfc chcMed_Obj 113,54 493.661,1 3,138 2,965 1,831Med_Esp 127,56 471.301,7 3,182 2,985 1,874Med_Cent 131,51 480.400,8 3,180 2,987 1,880Avg_Cent 125,92 483.034,3 3,186 2,991 1,869Eq_Comp 126,10 494.672,8 3,179 2,988 1,870SAH - - - - -



Teapots(5000,3)

w  Elevada complexidade geométrica w  Pouca oclusão w  “Medir overhead dos testes de visibilidade”


Teapots(5000,3)

w AABB

n  Mediana espacial ligeiramente pior (0,4 s) n  Descarte contra volume de visão: 8% n  Descarte por oclusão: 12%




Teapots(5000,3)

w OBB Clássica

n  Resultados similares l Tempos ligeramente maiores (0,3 s)




Teapots(5000,3)


n  Tempo muito elevado de construção n  Resultado semelhante n  Não vale a pena!

tempo area simples vfc chcMed_Obj 3.208,92 335.796,3 27,422 25,334 24,021Med_Esp - - - - -Med_Cent - - - - -Avg_Cent - - - - -Eq_Comp - - - - -SAH - - - - -



Teapots(5000,20)

w  Elevada complexidade geométrica w  Muita oclusão w  “Melhor cenário para descarte por oclusão”


Teapots(5000,20)

w AABB

n  Mediana espacial ligeiramente pior (0,2 s) n  Descarte contra volume de visão: 6% n  Descarte por oclusão: 81% (5x fps)

tempo area simples vfc chcMed_Obj - - 27,962 26,176 5,371Med_Esp - - 27,896 26,204 5,550Med_Cent - - 27,951 26,172 5,354Avg_Cent - - 27,973 26,185 5,360Eq_Comp - - 27,951 26,178 5,382SAH - - - - -



Teapots(5000,20)

w OBB Clássica

n  Resultados similares l Tempos ligeramente maiores (0,4 s)

tempo area simples vfc chcMed_Obj - - 28,191 26,582 5,820Med_Esp - - 27,941 26,172 5,847Med_Cent - - 27,914 26,151 5,767Avg_Cent - - 28,206 26,464 5,774Eq_Comp - - 27,892 26,155 6,167SAH - - - - -



Teapots(5000,20)


n  Tempo muito elevado de construção n  Resultado semelhante n  Não vale a pena!

tempo area simples vfc chcMed_Obj - - 29,341 26,897 5,818Med_Esp - - - - -Med_Cent - - - - -Avg_Cent - - - - -Eq_Comp - - - - -SAH - - - - -


LOD: Level of Detail

w Tipos

n  LOD discreto

n  LOD contínuo

n  LOD dependente de observador

Level of Detail for 3D Graphics, Luebke et al., 2003

LOD Discreto

w  Enumeração de modelos

w  Diferentes representações de um mesmo objeto n  Feita em pré-processamento n  Independente da posição do observador n  Em geral, agrupados num nó switch

Sw

LOD Discreto

w  Desacoplamento

n  Simplificação x Rendering n  Estrutura apropriada para rendering

l  Strip of triangles

w  Efeito de “pops” acentuados n  Minimizados com transição suave de níveis n  Vários vértices migram para um único

resultante

LOD Contínuo

w  Lista conceitual de modelos

w  Estrutura de dados n  Espectro contínuo de LOD n  Lista de operadores

l  Ex. colapso de aresta & split de vértices l  Permite mudar de resolução l  Nível apropriado extraído na renderização

w  Melhor granularidade n  Transição local para evitar “pops”

w  Suporte a renderização progressiva n  Envio de operadores via rede, por exemplo

colapso

split

modelo

LOD Dependente do Observador

w  Hierarquia conceitual de modelos n  Vários níveis de resolução (anisotrópico)

w  Estrutura de dados n  Árvore de operadores

w  Melhor granularidade

w  Apropriado para modelos grandes n  Terrenos

split

modelo

GDC 2003 Course Materials

Transição entre Níveis

w Alpha blending n  Desenha as duas versões

l Problema: podemos estar migrando para a versão de menor resolução por questão de desempenho

w  Geomorph n  Vértices re-posicionados gradualmente

l  Interpolação linear l  Pode ser feita na placa gráfica (vertex program)

Características dos Algoritmos

w  Topologia n  Genus n  2D manifold

l  Pode ter fronteira

w  Características dos algoritmos n  Preserva topologia

l  Maior fidelidade

n  Não preserva topologia l  Maior agressividade na simplificação

n  Em geral, precisa de uma estrutura topológica

Escolha do Nível de Detalhe

w Estratégias n  Baseado em fidelidade

l Busca minimizar erros visuais

n  Baseado em recursos l Busca manter desempenho

Operadores de Simplificação

w Colapso de aresta

va

vb

vnew

vnew= f (va,vb)

e colapse

v split

Outros Operadores

w  Colapso de par de vértices n  Não necessariamente ligados por aresta

l  Candidatos potenciais (O2) l  Heurística: arestas + vértices próximos

w  Colapso de triângulos n  Triângulo dá lugar a um vértice

w  Colapso de células n  Subdivide modelo em células n  Todos os vértices de uma célula

colapsa num novo vértice w  Remoção de vértices

n  Remove vértice e arestas adjacentes n  Retriangula “buraco”

Construção do LOD

w  Método guloso for each possible operation op ComputeCost(op) Q->Insert(op) end while Q->NotEmpty() do op = Q->ExtractMin() ApplyOp(op) for each neighbor operation i ComputeCost(i) Q->Update(i) end end

Critério de Avaliação de Custo

w  Critério simples n  Objetivo

l  Eliminar pequenos detalhes l  Eliminar arestas entre triângulos planares

n  Custo l  Combinação entre comprimento e curvatura l  Precisa de informações de adjacência topológica

),(),(:2

1minmax*),(

uvcvucOBS

gfvuvuc normalnormal

TgTf uvu

≠"#$

%&'

"#$

%&' ⋅−

−=∈∈

Se todos os triângulos adjacentes a u tiverem normais parecidas com um dos triângulos a serem removidos, o custo é pequeno.

Métrica Quadrática

w  Erro como a soma das distâncias do vértice aos planos adjacentes

w  Vantagem n  Se u colapse com v, criando w

l  Qw = Qu + Qv

n  Não precisa de informação topológica

( ) ( )( )

( ) vQvvQvvppv

vppvvp

vp

pp

pvp

TTTT

TT

)(

2

=!"#

$%&=!"

#$%&=

=⋅⋅=⋅=

∑∑

∑∑∈planes

ve

Visualização de Terrenos

Multi-resolução de terrenos armazenados em memória

secundária

Luiz Gustavo Magalhães Waldemar Celes

Lindstrom et al. (2002)

w  Baseado em refinamento

w  Não é necessário manter informações de estado

w  Constrói uma malha nova a cada frame

w  Pré-processamento

w  Culling hierárquico & Geomorphing

w  Existe uma solução out-of-core para o algoritmo

Partição da maior aresta

w  i é pai de j

w  Cada vértice é considerado ativo segundo um critério de refinamento

w  Para cada vértice ativo: n  Garantir que o seu pai e

seus ancestrais estão também ativos Imagens Retiradas de Lindstrom et al. [3]

Partição da maior aresta

w  Manter ponteiros de filhos para pai n  Ocupa mais espaço n  Ineficiente

w  Soluçao n  garantir que o erro usado no

critério de refinamento para o pai seja sempre maior ou igual ao do filho

Imagem Retirada de Lindstrom et al. [3]

Critério de Refinamento

w  Erro no Espaço da Tela (ρi) > Tolerância ⇒ Ativa i. w  Primeiro temos que ter:

n  Erro(objeto) do Pai ≥ Erro(objeto) do Filho l  Pré-processamento

Imagem retirada dos slides de Edinalda

Critério de Refinamento 2

w Erro no espaço do objeto está “encadeado” de pai para filho, mas e o erro no espaço de tela?

w Solução – esferas envolventes

Esferas envolventes

( )!"#

+−=

,max,0

jjii

rppr

se i é folha.

p/ j descendente de i.

ii

ii

rop −−=

λδρErro Esp. Tela:

Imagem retirada dos slides de Edinalda

Acesso aos dados out-of-core

w Mapeamento de arquivo em disco para endereço de memória (mmap) n  As páginas são carregadas pelo sistema

operacional n  Facilita implementacão mas impede o uso

de um mecanismo mais sofisticado como pre-fetching, etc

Acesso aos dados out-of-core

w  Reindexação dos dados n  Acesso em disco fica seqüencial n  Minimiza eventos de “paginação”

Implementação

w Estrutura de Dados: n  Carregamento e salvamento de terrenos. n  Pré-processamento e reindexação. n  Determinação de vértice visível e ativo. n  Indexação (BinTree).

w Estratégia de Renderização: n  Estratégia Strip. n  Estratégia Triangles.

Estratégia Strip

Imagens Retiradas de Lindstrom et al. [3]

Estratégia Triangles

subMeshRefine(V, Triangle(i, j, k), level) { IF (level > 0) AND VerticeAtivo(SPLIT(i, j, k)) subMeshRefine(V, CHILD_LEFT(i, j, k) , level-1) subMeshRefine(V, CHILD_RIGHT(i, j, k), level-1) ELSE desenha Triangle(i, j, k) } MeshRefine(V, levels) { subMeshRefine(V, SOUTH_TRIANGLE, levels-1) subMeshRefine(V, EAST_TRIANGLE , levels-1) subMeshRefine(V, NORTH_TRIANGLE, levels-1) subMeshRefine(V, WEST_TRIANGLE , levels-1) }

i

jk

Split

Child Left Child Right

Comparação entre as estratégias

w  A estratégia strip de Lindstrom et al. necessita de menos vértices (triangle strip) n  Mas gera muitos triangulos de área zero (36%)

w  A estratégia triangles é mais simples e envia mais vértices para a GPU, mas sempre gera o número exato de triângulos necessários. n  Permite uma estratégia de limitação do número de

triângulos (Budget Triangle Count)

Estratégias de rendering

w Modo Imediato n  glVertex(x,y,z)

w Arrays de Elementos n  glArrayElement(i)

w Vertex Arrays n  glDrawArray

Resultados

w  Configuração de teste: n  P4 Mobile 2.8 GHz com 512 Megabytes de RAM. n  GeForce Fx Go com 64 Megas de VRAM. n  Windows XP.

w  Casos de teste: n  Terreno: 4097x4097. n  Textura: 4096x4096. n  Tolerância de erro de 1 e 2 pixels.

w  Caminho Pré-definido: n  800 quadros

Resultados (cont.) Tolerância de erro de 1 pixel

Resultados (cont.) Tolerância de erro de 1 pixel

Estratégia Média de Tempo por quadro (ms)

Triangles Immediate 26,34473659 Triangles Array Element 27,82930232 Triangles Vertex Array 28,29788861 Strip Immediate 26,09624868 Strip Array Element 26,02400417 Strip Vertex Array 27,04737972 Strip Morph 30,26849671 Strip Morph Vertex Array 32,18535482

Resultados (cont.) Tolerância de erro de 2 pixels

Resultados (cont.) Tolerância de erro de 2 pixels

Estratégia Média de Tempo por quadro (ms)

Triangles Immediate 81,27651766 Triangles Array Element 90,14626693 Triangles Vertex Array 97,92097383 Strip Immediate 88,09698185 Strip Array Element 88,89202355 Strip Vertex Array 91,79737589 Strip Morph 107,0168068 Strip Morph Vertex Array 111,2844997

Problema

w Não é escalável

Mudança de foco

w Vértices x Conjunto de vértices w Hierarquia

n  Torna escalável n  Quadtrees

l  Implementação simples

Quadtrees

w  Divisão em Tiles w  Tiles de igual

tamanho e resolução

Quadtrees


tamanho e resolução w  Cada 4 tiles compõe

um nó pai n  Reamostragem

Quadtrees


tamanho e resolução w  Cada 4 tiles compõe

um nó pai n  Reamostragem

w  Quadtree n  Erro n  Eliminação de falhas

Cálculo do Erro

w Erro no espaço do objeto, 3 casos: n  Horizontais n  Verticais n  Diagonais

w Erro zero em nó folha.

Cálculo do Erro Projetado

w Erro de nós pai >= erro de nós filhos w BBox do pai envolve BBox dos filhos w Projeção do Erro

n  Forma de Lindstrom n  BBox do nó

ii

ii

rop −−=

λδρErro Esp. Tela:

Eliminação de falhas / vértices T

w  Tile dividido em 4 triângulos: n  2 possíveis indexações

l  Não geram cracks entre si l  Podem ser reutilizadas em

todos os tiles n  Cada triângulo adapta-se

ao seu vizinho, caso este seja de resolução inferior.

w  Ainda não é suficiente…

i

jk

Split

Eliminação de falhas / vértices T

w  Deve ser garantido que vizinhos tem diferença de apenas 1 nível

w  Balanceamento da Quadtree

Gerência de Tiles em disco

w Terreno em disco n  2 arquivos:

l  Metadados (erro, bbox, offset, etc) l  Dados

w  Compactação w  Possibilidade de mais de 1 arquivo de dados

w Execução n  2 Threads

l  Rendering l  IO de Tiles / Predição

n  Executam de forma independente

Thread de rendering

w Percorrer a árvore (quadtree)

w Critérios de refinamento n  Visibilidade n  Atividade n  Balanceamento da árvore n  Presença em memória

w Desenhar nós folhas

Thread de IO

w Percorre a árvore n  Mesmo critério de erro n  Carrega nós conforme desce na árvore

w Fila de prioridade de Tiles (heap) n  Ordenado por frame em que foi inserido

w  Inserção e remoção na fila

Video

Documents

Rendering em Tempo Real