Работа посвящена решению задачи оптимизации рендера компьютерной трехмерной графики, а именно рендер-конвейера. Данная работа сводит упомянутую проблему к многомерному варианту широко известной комбинаторной оптимизационной задачи о рюкзаке. Центральным элементом такой оптимизации является емкость, которую в текущем контексте играют ограниченные аппаратные возможности пользователя, и предметы для укладывания в емкость, роль которых играют различные пиксельные шейдеры. Емкость ограничена величинами ресурсов аппаратуры, а предметы-шейдеры имеют два основных свойства: полезность, выраженную в некоторой величине вклада в качество итоговой картинки, и вес, которым является их вычислительная стоимость для каждого ресурса аппаратуры. Основной задачей в данном контексте является разработка системы, которая будет способна решать такую задачу о рюкзаке в реальном времени для определения в каждый момент времени наилучшей возможной комбинации шейдеров. Таким образом, можно будет получить наилучшее качество изображения и избежать простоя или перегрузки аппаратуры. Основное применение описанная система найдет в сфере компьютерных игр, веб-рекламы, создании фильмов и других сферах, использующих компьютерную графику. Среди ключевых проблем при разработке описанной системы можно выделить сложность в определении вклада каждого отдельного шейдера в результат ввиду субъективности такой оценки. Другой сложностью является поиск компромисса между точностью решения задачи о рюкзаке и скоростью получения результата, с учетом условия, что система должна работать в реальном времени и не замедлять работу программы, для которой выполняется оптимизация.
1. Luna F.D. Introduction to 3D Game Programming with DirectX 12. Dulles: Mercury Learning and Information; 2016. 900 p.
2. Castorina M., Sassone G. Mastering Graphics Programming with Vulkan: Develop a modern rendering engine from first principles to state-of-the-art techniques. Birmingham: Packt Publishing Ltd; 2023. 382 p.
3. Dickinson C. Unity 2017 Game Optimization: Optimize all aspects of Unity performance. Birmingham: Packt Publishing Ltd; 2017. 376 p.
4. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. Chichester: John Wiley & Sons Ltd; 1990. 308 p.
5. Peresunko P., Mamatin D., Antamoshkin O., Peresunko E., Nikitin A. Models of Experts for Shaders Estimation of Rendering Complex 3D Scenes in Real Time. In: 2021 3rd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA), 10–12 November 2021, Lipetsk, Russia. IEEE; 2021. pp. 895–897. https://doi.org/10.1109/SUMMA53307.2021.9632071
6. Cacchiani V., Iori M., Locatelli A., Martello S. Knapsack problems – An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research. 2022;143. https://doi.org/10.1016/j.cor.2021.105693
7. Andonov R., Poirriez V., Rajopadhye S. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research. 2000;123(2):394–407. https://doi.org/10.1016/S0377-2217(99)00265-9
8. Pferschy U., Scatamacchia R. Improved dynamic programming and approximation results for the knapsack problem with setups. International Transactions in Operational Research. 2017;25(2):667–682. https://doi.org/10.1111/itor.12381
9. Boyer V., Baz D.E., Elkihel M. Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound. European Journal of Industrial Engineering. 2010;4(4):434–449. https://doi.org/10.1504/EJIE.2010.035653
10. Martello S., Toth P. An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem. Operations Research. 2003;51(5):826–835. https://doi.org/10.1287/opre.51.5.826.16757
11. Boussier S., Vasquez M., Vimont Y., Hanafi S., Michelon P. A multi-level search strategy for the 0–1 Multidimensional Knapsack Problem. Discrete Applied Mathematics. 2010;158(2):97–109. https://doi.org/10.1016/j.dam.2009.08.007
12. Dantzig G.B. Discrete-Variable Extremum Problems. Operations Research. 1957;5(2):266–288. https://doi.org/10.1287/opre.5.2.266
13. Al-douri T., Hifi M., Zissimopoulos V. An iterative algorithm for the Max–Min knapsack problem with multiple scenarios. Operational Research. 2021;21(1):1355–1392. https://doi.org/10.1007/s12351-019-00463-7
14. Chan T.M. Approximation Schemes for 0-1 Knapsack. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018): Open Access Series in Informatics (OASIcs): Volume 61, 07–10 January 2018, New Orleans, LA, USA. 2018. pp. 5:1–5:12. https://doi.org/10.4230/OASIcs.SOSA.2018.5
15. Jin C. An Improved FPTAS for 0-1 Knapsack. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019): Leibniz International Proceedings in Informatics (LIPIcs): Volume 132, 09–12 July 2019, Patras, Greece. 2019. pp. 76:1–76:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.76
16. Zhou Y., Kuang Z., Wang J. A Chaotic Neural Network Combined Heuristic Strategy for Multidimensional Knapsack Problem. In: Advances in Computation and Intelligence: Third International Symposium on Intelligence Computation and Applications, ISICA 2008: Proceedings, 19–21 December 2008, Wuhan, China. Berlin, Heidelberg: Springer; 2008. pp. 715–722. https://doi.org/10.1007/978-3-540-92137-0_78
17. Afshar R.R., Zhang Y., Firat M., Kaymak U. A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning. In: 12th Asian Conference on Machine Learning, ACML 2020: Proceedings of Machine Learning Research: Volume 129, 18–20 November 2020, Bangkok, Thailand. PMLR; 2020. pp. 81–96.
18. Mingo López L.F., Gómez Blas N., Arteta Albert A. Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing. 2017;22(8):2567–2582. https://doi.org/10.1007/s00500-017-2511-0
19. Ke L., Feng Z., Ren Z.H., Wei X. An ant colony optimization approach for the multidimensional knapsack problem. Journal of Heuristics. 2010;16(1):65–83. https://doi.org/10.1007/s10732-008-9087-x
20. Jalali Varnamkhasti M., Lee L.S. A Fuzzy Genetic Algorithm Based on Binary Encoding for Solving Multidimensional Knapsack Problems. Journal of Applied Mathematics. 2012;2012. https://doi.org/10.1155/2012/703601
21. Djannaty F., Doostdar S. A Hybrid Genetic Algorithm for the Multidimensional Knapsack Problem. International Journal of Contemporary Mathematical Sciences. 2008;3(9):443–456.
22. Kulik A., Shachnai H. There is no EPTAS for two-dimensional knapsack. Information Processing Letters. 2010;110(16):707–710. https://doi.org/10.1016/j.ipl.2010.05.031
23. Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society. 1990;41(11):1069–1072. https://doi.org/10.1057/jors.1990.166
24. Kong X., Gao L., Ouyang H., Li S. Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm. Computers & Operations Research. 2015;63(C):7–22. https://doi.org/10.1016/j.cor.2015.04.018
