Return to search

Uma nova solução para visibility culling de cenas genéricas, baseada em replicação, heurísticas e redução de draw calls / A New Solution for Visibility Culling in Generic Scenes, based on Replication, Heuristics and Reduction of Draw Calls (Inglês)

Made available in DSpace on 2019-03-30T00:14:05Z (GMT). No. of bitstreams: 0
Previous issue date: 2017-07-10 / This work presents RHView, a new solution for the visibility culling problem, based on a replicated spatial partitioning data structure (R), heuristics (H) and reduction of draw calls.
RHView encompasses generic tridimensional scenes, which may be completely static or even composed by dynamic objects. Additionally, it includes the traditional algorithms View-Frustum Culling, Backface Culling and Occlusion Culling, which are adapted and integrated to the replicated structure, which in turn keeps copies of the geometric meshes existent in its nodes, allowing for an efficient reduction on the number of draw calls. More specifically, RHView verifies the visibility state of dynamic objects using the View-Frustum Culling and Occlusion Culling algorithms, the latter, triggered by a cost heuristics and adapted for a better management of Occlusion Queries. In general terms, the main characteristics and heuristics of RHView are: identification of dynamic occluders in execution time, visibility status calculation, use of Level of Detail (LoD) of objects (based on the distance from the camera and on their number of fragments), temporal coherence, minimal triangle per node heuristic and memory cost heuristic.
Comparative performance tests were systematically conducted in a variety of indoor and outdoor scenarios, containing from 500 thousand to 1.5 billion vertices, with different dimensions and density of triangles per measure unit. Further, RHView was compared to two state-of-the-art solutions, Nested Grid and CHC++, as well as to the traditional spatial partitioning data structures, Grid, KD-Tree and Octree. The results show that RHView achieves always superior performance, with lower processing time and lower number of draw calls (having reduced the latter by 12 times, in some of the tests conducted). In particular, RHView was up to 2.8, 30 and 48 times faster than, respectively, CHC++, Nested Grid and the traditional structures. RHView is based on a tradeoff between precision and number of draw calls, getting greater framerates per second (FPS), even when, occasionally, presented lower triangle removal rates, in comparison to the other approaches. Regarding the proposed heuristic for calculating the rendering time, it presented a mean error of ±0.05s and ±0.0005s, in the worst and best cases, respectively.

Keywords: Visibility Culling, Generic Scenes, Replicated Spatial Partitioning Data Structure, Heuristic, Draw Calls / Este trabalho apresenta RHView, uma nova solução para o problema de visibility culling, baseada em uma estrutura de particionamento espacial replicada (R), heurísticas (H) e redução de draw calls.
RHView contempla cenas tridimensionais genéricas, sejam estas completamente estáticas ou mesmo compostas por objetos dinâmicos. Adicionalmente, inclui os algoritmos tradicionais View-Frustum Culling, Backface Culling e Occlusion Culling, adaptados e integrados à estrutura replicada, a qual mantém cópias das malhas geométricas contidas em seus nós, possibilitando a redução eficiente do número de draw calls. Mais especificamente, RHView determina a visibilidade de objetos dinâmicos usando os algoritmos de View-Frustum Culling e Occlusion Culling, este último, acionado por uma heurística de custo e adaptado para melhor gerência de Occlusion Queries. Em termos gerais, as principais características e heurísticas da RHView são: identificação de oclusores dinâmicos em tempo de execução, cálculo do estado de visibilidade, uso de nível de detalhamento (LoD) dos objetos em cena (baseado na distância à câmera e no número de fragmentos dos mesmos), coerência temporal, heurística de mínimo de triângulos por nó e de custo em memória.
Testes comparativos de desempenho foram conduzidos de forma sistemática em cenários internos e externos variados, contendo de 500 mil a 1,5 bilhão de vértices, com diferentes dimensões e densidades de triângulos por unidade de medida. Mais especificamente, RHView foi comparada frente a duas soluções que refletem o estado-da-arte, Nested Grid e CHC++, bem como às estruturas tradicionais de particionamento espacial, Grid, KD-Tree e Octree. Os resultados obtidos mostram que RHView apresenta desempenho sempre superior, exibindo menor tempo de processamento e menor número de draw calls (tendo reduzido este último, em até 12 vezes, em alguns dos testes conduzidos). Em particular, RHView foi até 2,8, 30 e 48 vezes mais rápido que, respectivamente, o CHC++, o Nested Grid e as estruturas de particionamento tradicionais. RHView baseia-se em uma razão custo/benefício entre precisão e número de draw calls, obtendo maiores taxas de quadros por segundo (FPS), mesmo quando, ocasionalmente, apresentou menores taxas de remoção de triângulos, em comparação às outras abordagens. Com relação à heurística para cálculo do tempo de renderização proposta, esta apresentou um erro médio de ±0,05s e ±0,0005s, no pior e melhor casos, respectivamente.
Palavras-chave: Visibility Culling, Cenas Genéricas, Estrutura de Particionamento Espacial Replicada, Heurísticas, Draw Calls

Identiferoai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/102000
Date10 July 2017
CreatorsSerpa, Yvens Reboucas
ContributorsRodrigues, Maria Andreia Formico, Rodrigues, Maria Andreia Formico, Macedo, Daniel Valente de, Oliveira Neto, Manuel Menezes de
PublisherUniversidade de Fortaleza, Mestrado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR
Rightsinfo:eu-repo/semantics/openAccess
Relation5443571202788449035, 500, 500, -7645770940771915222

Page generated in 0.0024 seconds