Interactive Rendering on Mobile Devices Using Visibility Algorithms and Spatial Partitioning Structures

• Wendel B. Silva UNIFOR
• Maria Andréia F. Rodrigues UNIFOR

Abstract

We developed a system for interactive rendering on mobile devices using the OpenGL ES API. We implemented various combinations of visibility algorithms (view-frustum culling, occlusion culling, backface culling, and a new and simple, yet fast algorithm, called conservative backface culling). We associated these visibility algorithms with different settings of spatial data structures (non-uniform Grids, BSP-Trees, Octrees, and Portal-Octrees) and compared their performance through extensively testings using different 3D environments (in the order of thousands of triangles). The results show that interactive frame rates on mobile devices can be obtained using geometry rather than image-based rendering or point-based rendering.

References

Akenine-Möller, T., Haines, E. (2002). "Real-Time Rendering", A. K. Peters, 2nd edition.

Bittner, J., Wimmer, M., Piringer, H., Purgathofer, W. (2004). "Coherent Hierarchical Culling: Hardware Occlusion Queries Made Useful", CGF, v. XXIII, p. 615–624.

Buschmann, F., Meunier, R., Rohnert, H., Sommerlad, P., Stal, M. (1996). "Pattern-Oriented Software Architecture", v. I, John Wiley & Sons.

Cohen-Or, D., Chrysanthou, Y., Silva, C.T., Durand, F. (2002). "A Survey of Visibility for Walkthrough Applications", IEEE Transactions on Visualization and Computer Graphics, v. IX, p. 412–431.

Cohen-Or, D., Rich, E., Lerner, U., Shenkar, V. (1996). "A Real-time Photo-realistic Visual Flythrough", IEEE Trans. on Visualization and Computer Graphics, v. II, p. 255–264.

Klosowski, J.T., Silva, C.T. (2000). "The Prioritized-Layered Projection Algorithm for Visible Set Estimation", In IEEE Transactions on Visualization and Computer Graphics, p. 108–123.

Klosowski, J.T., Silva, C.T. (2001). "Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection Algorithm", IEEE Transactions on Visualization and Computer Graphics, v. VII, p. 365–379.

Rodrigues, M.A.F., Barbosa, R.G., Silva, W.B. (2006). “Desenvolvimento de Aplicações 3D para Dispositivos Móveis utilizando as APIs M3G e OpenGL ES”, RITA, v. XIII, p. 65-96.

Rodrigues, M.A.F., Rocha, R.S., Silva, W.B. (2008). “Interactive and Accurate Collision Detection in Virtual Orthodontics”, Em 14th Eurographics Symposium on Virtual Environments (EGVE), Netherlands. Eurographics Association, p. 65-72.

Rodrigues, M.A.F., Silva, W.B., Barbosa Neto, M.E., Gillies, D., Ribeiro, I.M.M.P. (2007) “An Interactive Simulation System for Training and Treatment Planning in Orthodontics”, Computers & Graphics, v. 31, p. 688-697.

Samet, H. (1990). "The Design and Analysis of Spatial Data Structures". Addison-Wesley.

Silva, W.B. (2008). “Renderização Interativa em Dispositivos Móveis utilizando Algoritmos de Visibilidade e Estruturas de Particionamento Espacial”, Dissertação de Mestrado, MIA-UNIFOR, Fortaleza-CE. Disponível em [link]

Silva, W.B. e Rodrigues, M.A.F. (2009). “A Lightweight 3D Visualization and Navigation System on Handheld Devices”, Em Anais do 24th Annual ACM Symposium on Applied Computing (ACM SAC), Track on Mobile Computing and Applications, USA: ACM Press, p.162-166.

Wang, R.Y., Pulli, K., Popović, J. (2007). "Mobile 3D Graphics with OpenGL ES and M3G", Morgan Kauffman.