AUTOMATIC PORTAL GENERATION FOR 3D AUDIO - FROM TRIANGLE SOUP TO A PORTAL SYSTEM

Piotr Turecki; Tomasz Pędzimąż; Szymon Pałka; Bartosz Ziółko

doi:10.7494/csci.2016.17.3.321

Authors

Piotr Turecki AGH University of Science and Technology, Department of Computer Science, Electronics and Telecommunications, al. Mickiewicza 30, Krakow
Tomasz Pędzimąż AGH University of Science and Technology, Department of Computer Science, Electronics and Telecommunications, al. Mickiewicza 30, Krakow
Szymon Pałka AGH University of Science and Technology, Department of Computer Science, Electronics and Telecommunications, al. Mickiewicza 30, Krakow
Bartosz Ziółko AGH University of Science and Technology, Department of Computer Science, Electronics and Telecommunications, al. Mickiewicza 30, Krakow

DOI:

https://doi.org/10.7494/csci.2016.17.3.321

Keywords:

voxelization, portals generation, geometry occlusion, watershed transform

Abstract

The purpose of this paper is to investigate an algorithm for generating an automatic portal system. This has been accomplished based on a given set of triangles. The proposed solution was designed to enhance the performance of a sound beam-tracing engine. This solution can also be used for other areas where portal systems are applicable. The provided technical solution emphasizes the beam tracing engine's requirements. Our approach is based on the work of Haumont et al. (with additional improvements), resulting in improved scene segmentation and lower computational complexity. We examined voxelization techniques and their properties, and have adjusted these to fit the requirements of a beam-tracing engine. As a result of our investigation, a new method for finding portal placement has been developed by adjusting the orientation of the found portals to fit the neighboring scene walls. In addition, we replaced Haumont et al.'s prevoxelization step, which is used for erasing geometrical details (for example, thin walls). This was done by smoothing the distance field that, in effect, eliminated incorrectly positioned portals. The results of our work remove the requirement for walls that separate rooms to have a particular thickness. We also describe a method for building a structure that accelerates real-time queries for determining the area where a given point is located. All of the presented techniques allow for the use of larger sized voxels, which increases performance and reduces memory requirements (not only during the preprocessing phase but also during real-time usage). The proposed solutions were tested using scenarios with scenes of varying complexity.

Downloads

Download data is not yet available.

References

Alliez P., Cohen-Steiner D., Tong Y., Desbrun M.: Voronoi-based Variational Reconstruction of Unoriented Point Sets. In: Proceedings of Eurographics Symposium on Geometry Processing, 2007.

Anderson B.: An Implementation of the Marching Cubes Algorithm. URL http://www.cs.carleton.edu/cs_comps/0405/shape/marching_cubes.html.

Andersson M.: Bounding Volume Hierarchy, 2012. URL http://fileadmin.cs.lth.se/cs/Education/EDAN30/lectures/S2-bvh.pdf.

Bellmann J., Michel F., Deines E., Hering-Bertram M., Mohring J., Hagen H.: Sound Tracing: Rendering Listener Specific Acoustic Room Properties. In: EG Computer Graphics Forum, vol. 27(3), pp. 943-950, 2008.

Beucher S.: The watershed transformation applied to image segmentation, 1991.

Brentzen J.A., Aans H.: Generating Signed Distance Fields From Triangle Meshes, 2002. IMM-Technical report-2002-21.

Chandak A., Lauterbach C., Taylor M.T., Ren Z., Manocha D.: AD-Frustum: Adaptive Frustum Tracing for Interactive Sound Propagation. In: IEEE Trans. Vis. Comput. Graph., vol. 14(6), pp. 1707{1722, 2008. URL http://dblp.uni-trier.de/db/journals/tvcg/tvcg14.html.

critterai.org: Study: Navigation Mesh Generation. URL http://www.critterai.org/projects/nmgen_study.

Cryengine: Cryengine. URL http://cryengine.com/.

Erleben K., Dohlmann H.: GPU Gems 3, Chapter 34. Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra, 2007. URL http://http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html.

Fisher M.: Marching Cubes. URL http://graphics.stanford.edu/~mdfisher/MarchingCubes.html.

Haumont D., Debeir O., Sillion F.: Volumetric cell-and-portal generation. In: Proceedings of EUROGRAPHICS, 2003.

Haumont D., Warzée N.: Complete Polygonal Scene Voxelization. In: Journal of Graphics Tools, 2002.

Intel Corporation: Software Occlusion Culling. URL https://software.intel.com/en-us/articles/software-occlusion-culling.

Jachimczak T., Lentz J., Hendriks M.: Unreal engine 2: Level Optimization - BSP. URL http://udn.epicgames.com/Two/LevelOptimizationBSP.html.

Jeong C.H.: Absorption and impedance boundary conditions for phased geometrical-acoustics methods. In: Journal of the Acoustical Society of America, vol. 132(4), p. 23472358, 2012.

Jones M., Baerentzen J.A., Sramek M.: 3D distance fields: A survey of techniques and applications. In: IEEE Transactions on Visualization and Computer Graphics, vol. 12, pp. 581-599, 2006.

Kamisiński T.: Correction of Acoustics in Historic Opera Theatres with the Use of Schroeder Diffuser. In: Archives of Acoustics, vol. 37, pp. 349-354, 2012.

Kamisiński T., Burkot M., Rubacha J., Brawata K.: Study of the Effect of the Orchestra Pit on the Acoustics of the Kraków Opera Hall. In: Archives of Acoustics, vol. 34, pp. 481-490, 2009.

Kowalczyk K., van Walstijn M.: Room Acoustics Simulation Using 3-D Compact Explicit FDTD Schemes. In: IEEE Transactions on Audio, Speech & Language Processing, vol. 19(1), pp. 34-46, 2011.

Kuttruff H.: Acoustics - An Introduction. 2006.

Kuttruff H.: Room Acoustics, 5th ed. Spon Press, London, 2009.

Lauterbach C., Chandak A., Manocha D.: Adaptive sampling for frustum-based sound propagation in complex and dynamic environments. In: Proceedings of the 19th International Congress on Acoustics, vol. 16, 2007.

Lauterbach C., Chandak A., Manocha D.: Interactive sound rendering in complex and dynamic scenes using frustum tracing. In: IEEE Trans. Vis. Comput. Graph., vol. 13(6), pp. 1672-1679, 2007. URL http://dblp.uni-trier.de/db/journals/tvcg/tvcg13.html.

Lorensen W.E., Cline H.E.: Marching Cubes: A High Resolution 3D Surface Construction Algorithm. In: Computer Graphics, vol. 21(3), pp. 163-169, 1987.

Mahovsky J., Wyvill B.: Memory-conserving bounding volume hierarchies with coherent raytracing. In: COMPUTER GRAPHICS FORUM, vol. 25, pp. 173-182, 2006.

Makinen O., Saransaari H.: Conservative cell and portal graph generation, 2014. URL http://www.google.com/patents/US20140043331. US Patent App. 13/569,879.

Meijster A., Roerdink J., Hesselin W.: A GENERAL ALGORITHM FOR COMPUTING DISTANCE TRANSFORMS IN LINEAR TIME. In: Mathematical Morphology and its Applications to Image and Signal Processing Computational Imaging and Vision, vol. 18, pp. 331-340, 2000.

Miga B., Ziółko B.: Real-time acoustic phenomena modelling for computer games audio engine. In: Archives of Acoustics, vol. 40(2), 2015.

Mommertz E.: Building Acoustics and Vibration Theory and Practise. World Scientific Publishing Co. Pte. Ltd., Singapore, 2009.

Mononen M.: Navigation Mesh Generation via Voxelization and Watershed Partitioning, 2009. URL http://aigamedev.com/premium/masterclass/navigation-mesh-generation/.

Neperud B., Lowther J., Shene C.K.: Visualizing and animating the winged-edge data structure, 2007.

Nils L., Jansens G., Vermeir G., van der Voorden M M.: Absorbing surfaces in ray-tracing programs for coupled spaces. In: Applied Acoustics, vol. 63(6), pp. 611-626, 2002.

O.A.B.Hassan: Untersuchung akustischer Wandeigenschaften und Modellierung der Schallrückwürfe in der binauralen Raumsimulation. Doctoral thesis RWTH Aachen University, Germany.

Ozgura E., Ozisb F., Alpkocaka A.: DAAD: A New Software for Architectural Acoustic Design. In: Proceedings of the 33rd International Congress and Exposition on Noise Control Engineering Internoise, Prague, 2004.

Raghuvanshi N., Lauterbach C., Chandak A., Manocha D., Lin M.: Real-time sound synthesis and propagation for games. In: Communications of the ACM, vol. 07(50), pp. 66-73, 2007.

Sek A., Moore B.: Frequency discrimination as a function of frequency, measured in several ways. In: Journal of the Acoustical Society of America, vol. 97(4), pp. 2479-2486, 1995.

Sekulic D.: GPU Gems, Chapter 29. Efficient Occlusion Culling, 2004. URL http://http.developer.nvidia.com/GPUGems/gpugems_ch29.html.

Shimer C.: Binary Space Partition Trees. URL http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html.

Silvennoinen A., Saransaari H., Laine S., Lehtinen J.: Occluder Simplification Using Planar Sections. In: Computer Graphics Forum, vol. 33, pp. 235-245, 2014.

Sz. Pałka, Głut B., Ziółko B.: Visibility determination in beam tracing with application to real-time sound simulation. In: Computer Science, vol. 15, pp. 197-214, 2014.

van Toll W., Cook IV A.F., Geraerts R.: A navigation mesh for dynamic environments. In: Computer Animation and Virtual Worlds, vol. 23, pp. 535-546, 2012.