Automatic portal generation for 3d audio – from triangle soup to a portal system

• Autorzy: Turecki P. , Pędzimąż T. , Pałka S. , Ziółko B.

Identyfikatory

DOI

10.7494/csci.2016.17.3.321

• Języki publikacji: EN

Abstrakty

EN

The purpose of this paper is to investigate an algorithm for generating an auto- matic portal system. This has been accomplished based on a given set of trian- gles. 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 segmenta- tion 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 exam- ple, 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 al- so 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.

Słowa kluczowe

EN

voxelization; portal generation; geometry occlusion; watershed transform

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2016
• Tom: Vol. 17 (3)
• Strony: 321--352
• Opis fizyczny: Bibliogr. 42 poz., rys., wykr., tab.

Twórcy

autor

Turecki P.

• AGH University of Science and Technology, Krakow, Poland

autor

Pędzimąż T.

• AGH University of Science and Technology, Krakow, Poland

autor

Pałka S.

• AGH University of Science and Technology, Krakow, Poland

autor

Ziółko B.

• AGH University of Science and Technology, Krakow, Poland

Bibliografia

• [1] Alliez P., Cohen-Steiner D., Tong Y., Desbrun M.: Voronoi-based Variational Reconstruction of Unoriented Point Sets. Proceedings of Eurographics Symposium on Geometry Processing , 2007.
• [2] Anderson B.: An Implementation of the Marching Cubes Algorithm. http:// www.cs.carleton.edu/cs_comps/0405/shape/marching_cubes.html .
• [3] Andersson M.: Bounding Volume Hierarchy. 2012, http://fileadmin.cs.lth. se/cs/Education/EDAN30/lectures/S2-bvh.pdf .
• [4] Bærentzen J.A., Aanęs H.: Generating Signed Distance Fields From Triangle Meshes. 2002, IMM-Technical report-2002-21.
• [5] Bellmann J., Michel F., Deines E., Hering-Bertram M., Mohring J., Hagen H.: Sound Tracing: Rendering Listener Specific Acoustic Room Properties. EG Com- puter Graphics Forum , vol. 27(3), pp. 943–950, 2008.
• [6] Beucher S.: The watershed transformation applied to image segmentation. 1991.
• [7] Chandak A., Lauterbach C., Taylor M.T., Ren Z., Manocha D.: AD-Frustum: Adaptive Frustum Tracing for Interactive Sound Propagation. IEEE Trans. Vis. Comput. Graph. , vol. 14(6), pp. 1707–1722, 2008, http://dblp.uni-trier.de/db/journals/tvcg/tvcg14.html.
• [8] critterai.org: Study: Navigation Mesh Generation. http://www.critterai.org/ projects/nmgen_study.
• [9] Cryengine: Cryengine. http://cryengine.com/.
• [10] Erleben K., Dohlmann H.: GPU Gems 3, Chapter 34. Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra. 2007, http://http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html.
• [11] Fisher M.: Marching Cubes. http://graphics.stanford.edu/~mdfisher/ MarchingCubes.html.
• [12] Hassan O.: Untersuchung akustischer Wandeigenschaften und Modellierung der Schallruckwurfe in der binauralen Raumsimulation. Doctoral thesis RWTH Aachen University, Germany.
• [13] Haumont D., Debeir O., Sillion F.: Volumetric cell-and-portal generation. Proceedings of EUROGRAPHICS, 2003.
• [14] Haumont D., Warzee N.: Complete Polygonal Scene Voxelization. Journal of Graphics Tools, 2002.
• [15] Intel Corporation: Software Occlusion Culling. https://software.intel.com/ en-us/articles/software-occlusion-culling .
• [16] Jachimczak T., Lentz J., Hendriks M.: Unreal engine 2: Level Optimization – BSP. http://udn.epicgames.com/Two/LevelOptimizationBSP.html.
• [17] Jeong C.H.: Absorption and impedance boundary conditions for phased geometrical-acoustics methods. Journal of the Acoustical Society of America, vol. 132(4), pp. 2347–2358, 2012.
• [18] Jones M., Baerentzen J.A., Sramek M.: 3D distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics, vol. 12, pp. 581–599, 2006.
• [19] Kamisiński T.: Correction of Acoustics in Historic Opera Theatres with the Use of Schroeder Diffuser. Archives of Acoustics, vol. 37, pp. 349–354, 2012.
• [20] 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. Archives of Acoustics, vol. 34, pp. 481–490, 2009.
• [21] Kowalczyk K., van Walstijn M.: Room Acoustics Simulation Using 3-D Compact Explicit FDTD Schemes. IEEE Transactions on Audio, Speech & Language Processing , vol. 19(1), pp. 34–46, 2011.
• [22] Kuttruff H.: Acoustics – An Introduction. 2006.
• [23] Kuttruff H.: Room Acoustics, 5th ed. Spon Press, London, 2009.
• [24] Lauterbach C., Chandak A., Manocha D.: Adaptive sampling for frustum-based sound propagation in complex and dynamic environments. Proceedings of the 19th International Congress on Acoustics , vol. 16, 2007.
• [25] Lauterbach C., Chandak A., Manocha D.: Interactive sound rendering in complex and dynamic scenes using frustum tracing. IEEE Trans. Vis. Comput. Graph. , vol. 13(6), pp. 1672–1679, 2007, http://dblp.uni-trier.de/db/journals/ tvcg/tvcg13.html.
• [26] Lorensen W.E., Cline H.E.: Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics, vol. 21(3), pp. 163–169, 1987.
• [27] Mahovsky J., Wyvill B.: Memory-conserving bounding volume hierarchies with coherent raytracing. COMPUTER GRAPHICS FORUM, vol. 25, pp. 173–182, 2006.
• [28] Makinen O., Saransaari H.: Conservative cell and portal graph generation. 2014, http://www.google.com/patents/US20140043331, uS Patent App. 13/569,879.
• [29] Meijster A., Roerdink J., Hesselin W.: A general algorithm for computing distance transforms in linear time. Mathematical Morphology and its Applications to Image and Signal Processing Computational Imaging and Vision , vol. 18, pp. 331–340, 2000.
• [30] Miga B., Ziółko B.: Real-time acoustic phenomena modelling for computer games audio engine. Archives of Acoustics , vol. 40(2), 2015.
• [31] Mommertz E.: Building Acoustics and Vibration Theory and Practise. World Scientific Publishing Co. Pte. Ltd., Singapore, 2009.
• [32] Mononen M.: Navigation Mesh Generation via Voxelization and Watershed Partitioning. 2009, http://aigamedev.com/premium/masterclass/ navigation-mesh-generation/.
• [33] Neperud B., Lowther J., Shene C.K.: Visualizing and animating the winged-edge data structure. 2007.
• [34] Nils L., Jansens G., Vermeir G., van der Voorden M.: Absorbing surfaces in ray- tracing programs for coupled spaces. Applied Acoustics , vol. 63(6), pp. 611–626, 2002.
• [35] Ozgura E., Ozisb F., Alpkocaka A.: DAAD: A New Software for Architectural Acoustic Design. Proceedings of the 33rd International Congress and Exposition on Noise Control Engineering Internoise, Prague , 2004.
• [36] Pałka S., Głut B., Ziółko B.: Visibility determination in beam tracing with application to real-time sound simulation. Computer Science, vol. 15, pp. 197–214, 2014.
• [37] Raghuvanshi N., Lauterbach C., Chandak A., Manocha D., Lin M.: Real-time sound synthesis and propagation for games. Communications of the ACM , vol. 07(50), pp. 66–73, 2007.
• [38] Sek A., Moore B.: Frequency discrimination as a function of frequency, measured in several ways. Journal of the Acoustical Society of America , vol. 97(4), pp. 2479– 2486, 1995.
• [39] Sekulic D.: GPU Gems, Chapter 29. Efficient Occlusion Culling. 2004, http: //http.developer.nvidia.com/GPUGems/gpugems_ch29.html.
• [40] Shimer C.: Binary Space Partition Trees. http://web.cs.wpi.edu/~matt/ courses/cs563/talks/bsp/bsp.html.
• [41] Silvennoinen A., Saransaari H., Laine S., Lehtinen J.: Occluder Simplification Using Planar Sections. Computer Graphics Forum , vol. 33, pp. 235–245, 2014.
• [42] van Toll W., Cook IV A.F., Geraerts R.: A navigation mesh for dynamic environments. Computer Animation and Virtual Worlds , vol. 23, pp. 535–546, 2012.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.