Abstract
This article discusses the optimization (simplification) of procedurally generated landscapes for real time graphics applications. The problem of locality recognition, sufficient detailing and preservation of characteristic details is being solved. The mathematical models of the proposed solution are presented. The main stages of the proposed algorithm are described: the formation of the initial high-poly landscape model based on the height map, the selection from the initial high-poly model of the control points that most accurately convey the curvature and features of the landscape. At the simplification step, for the selection of control points, it is proposed to use the Ramer - Douglas - Pecker algorithm, adapted for the three-dimensional case based on the use of majority logic. At the stage of constructing a polygonal mesh (triangulation), the Delaunay method and Hausdorff metric were applied. Objective and Subjective approaches to assessing the quality of optimization results are considered. Objective is based on measuring the measure of geometric similarity of polygonal models by calculating the Hausdorff distance. Subjective - based on the adapted Double Stimulus Impairment Scale (DSIS) quality testing method. Developed and tested a prototype of the polygonal mesh optimizer in the Unity3D environment. The results obtained are presented. The considered approaches can be used in the field of computer games, in various simulators, navigation systems, training programs, as well as in the film industry. This work is a continuation of a series of publications by the authors in the field of methods and models for constructing computer graphics tools.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Valencia-Rosado, L.O., Starostenko, O.: Methods for procedural terrain generation: a review. In: Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F., Olvera-López, J.A., Salas, J. (eds.) MCPR 2019. LNCS, vol. 11524, pp. 58–67. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21077-9_6
Rose, T.J., Bakaoukas, A.G.: Algorithms and Approaches for Procedural Terrain Generation - A Brief Review of Current Techniques (2016). https://ieeexplore.ieee.org/document/7590336
World Machine: The Premier 3D Terrain Generator. http://www.bundysoft.com/L3DT/
Large 3D Terrain Generator. http://www.bundysoft.com/L3DT
Unity Manual. https://docs.unity3d.com/Manual/index.html
Terrain Level of Detail. https://graphics.pixar.com/library/LOD2002/4-terrain.pdf
Hausdorff Distance. https://en.wikipedia.org/wiki/Hausdorff_distance
Mezhenin, A., Zhigalova, A.: Similarity analysis using Hausdorff metrics (2019). http://ceur-ws.org/Vol-2344/short5.pdf
Mezhenin, A., Polyakov, V., Prishhepa, A., Izvozchikova, V., Zykov, A.: Using virtual scenes for comparison of photogrammetry software. In: Zhengbing, H., Petoukhov, S., He, M. (eds.) Advances in Intelligent Systems, Computer Science and Digital Economics II, pp. 57–65. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-80478-7_7
Polyakov, V., Mezhenin, A.: Procedural generation of virtual space. In: Kovalev, S., Tarassov, V., Snasel, V., Sukhanov, A. (eds.) Proceedings of the Fourth International Scientific Conference “Intelligent Information Technologies for Industry” (IITI’19), pp. 623–632. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-50097-9_64
Mezhenin, A., Shevchenko, A.: Optimization of procedurally generated landscapes. In: CEUR Workshop Proceedings, vol. 2744 (2020). This link is disabled
Mezhenin, A., Izvozchikova, V., Grigoreva, A., Shardakov, V.: Point cloud registration hybrid method. In: CEUR Workshop Proceedings, vol. 2893 (2020). This link is disabled
Ramer, U.: An iterative procedure for the polygonal approximation of plane curves. Comput. Graph. Image Process. 1(3), 244–256 (1972)
Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Can. Cartographer 10(2), 112–122 (1973)
Fei, L., He, J., Ma, C., Yan, H.: Three dimensional Douglas-Peucker algorithm and the study of its application to automated generalization of DEM. Acta Geodaetica et Cartographica Sinica 35(3), 278–284 (2006)
Fei, L., He, J.: A three-dimensional Douglas-Peucker algorithm and its application to automated generalization of DEMs. Int. J. Geogr. Inf. Sci. 23(6), 703–718 (2009). https://doi.org/10.1080/13658810701703001
Guo, J., Vidal, V., Cheng, I., Basu, A., Baskurt, A., Lavoue, G.: Subjective and objective visual quality assessment of textured 3D meshes. ACM Trans. Appl. Percept. 14(2), 1–20 (2017). https://doi.org/10.1145/2996296
De Simonea, F., Goldmanna, L., Leea, J.-S., Ebrahimia, T., Baroncini, V.: Subjective Evaluation of Next-Generation Video Compression Algorithms: A Case Study (2014)
Vanhoey, K., Sauvage, B., Kraemer, P., Lavoué, G.: Visual quality assessment of 3D models: on the influence of light-material interaction. ACM Trans. Appl. Percept. 15(1), 1–18 (2018). https://doi.org/10.1145/3129505
Nehmé, Y., Farrugia, J.-P., Dupont, F., Le Callet, P., Lavoué, G.: Comparison of subjective methods, with and without explicit reference, for quality assessment of 3D graphics (2019)
Wang, S., Li, W.: The implementation of 3D scene walkthrough in air pollution visualization. Int. J. Inf. Eng. Electron. Bus. (IJIEEB) 2(1), 44–50 (2010)
Bogoya, J.M., Vargas, A., Cuate, O., Schütze, O.: 2 A (p, q)-averaged hausdorff distance for arbitrary measurable sets. Math. Comput. Appl. 23, 51 (2018). https://doi.org/10.3390/mca23030051
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Mezhenin, A., Izvozchikova, V. (2022). Algorithms Optimization for Procedural Terrain Generation in Real Time Graphics. In: Hu, Z., Gavriushin, S., Petoukhov, S., He, M. (eds) Advances in Intelligent Systems, Computer Science and Digital Economics III. CSDEIS 2021. Lecture Notes on Data Engineering and Communications Technologies, vol 121. Springer, Cham. https://doi.org/10.1007/978-3-030-97057-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-97057-4_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-97056-7
Online ISBN: 978-3-030-97057-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)