Работа посвящена решению задачи оптимизации рендера компьютерной трехмерной графики, а именно рендер-конвейера. Данная работа сводит упомянутую проблему к многомерному варианту широко известной комбинаторной оптимизационной задачи о рюкзаке. Центральным элементом такой оптимизации является емкость, которую в текущем контексте играют ограниченные аппаратные возможности пользователя, и предметы для укладывания в емкость, роль которых играют различные пиксельные шейдеры. Емкость ограничена величинами ресурсов аппаратуры, а предметы-шейдеры имеют два основных свойства: полезность, выраженную в некоторой величине вклада в качество итоговой картинки, и вес, которым является их вычислительная стоимость для каждого ресурса аппаратуры. Основной задачей в данном контексте является разработка системы, которая будет способна решать такую задачу о рюкзаке в реальном времени для определения в каждый момент времени наилучшей возможной комбинации шейдеров. Таким образом, можно будет получить наилучшее качество изображения и избежать простоя или перегрузки аппаратуры. Основное применение описанная система найдет в сфере компьютерных игр, веб-рекламы, создании фильмов и других сферах, использующих компьютерную графику. Среди ключевых проблем при разработке описанной системы можно выделить сложность в определении вклада каждого отдельного шейдера в результат ввиду субъективности такой оценки. Другой сложностью является поиск компромисса между точностью решения задачи о рюкзаке и скоростью получения результата, с учетом условия, что система должна работать в реальном времени и не замедлять работу программы, для которой выполняется оптимизация.
The work is devoted to solving the problem of optimizing the rendering of computer three-dimensional graphics, namely the rendering pipeline. This work reduces the mentioned problem to a multidimensional version of the well-known combinatorial optimization knapsack problem. The central element of this optimization is capacity, which in the current context is the user's limited hardware capabilities, and the items to be placed in the capacity, which are various pixel shaders. The capacity is limited by the values of the hardware resources, and the shader items have two properties - utility, expressed in some value of contribution to the quality of render, and weight, which is their computational cost. The main challenge in such a context is to develop a system that will be able to solve such a knapsack problem in real time, in order to determine at each moment the best possible combination of shaders. Thus, it will be possible to obtain the best image quality and avoid downtime or overloading of the hardware. The main application of the described system will be in the sphere of computer games, web advertising, movie making and other spheres using computer graphics. Among the key problems in the development of the described system is the difficulty in determining the contribution of each individual shader to the result, due to the it’s subjectivity. Another difficulty is finding a compromise between the accuracy of the knapsack problem solution and the speed of obtaining the result, taking into account the condition that the system must work in real time and not slow down the program for which the optimization is being performed.
The authors declare that there are no conflicts of interest present.