Неправильный Z-буфер: Алгоритм для решения задачи видимости в реальном времени.
Irregular Z-buffer
Неправильный Z-буфер: алгоритм для решения проблемы видимости в 3D графике. Гибкое размещение образцов, пространственные структуры данных, растризация.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Нерегулярный Z-буфер — это алгоритм, разработанный для решения проблемы видимости в трехмерной компьютерной графике в реальном времени. Он связан с классическим Z-буфером тем, что поддерживает значение глубины для каждого пикселя изображения и использует эти значения для определения видимых геометрических элементов сцены. Однако ключевое отличие между классическим и нерегулярным Z-буферами заключается в том, что последний допускает произвольное размещение пикселей изображения в плоскости изображения, в то время как первый требует, чтобы пиксели располагались в регулярной сетке. Эти значения глубины явно хранятся в двухмерной пространственной структуре данных. В процессе растрирования треугольники проецируются на плоскость изображения обычным образом, и структура данных опрашивается для определения, какие пиксели пересекаются с каждым проецируемым треугольником. Наконец, для каждого пересекающегося пикселя выполняется стандартное Z-сравнение и (условное) обновление буфера кадров.
The irregular Z buffer is an algorithm designed to solve the visibility problem in real time 3 d computer graphics. It is related to the classical Z buffer in that it maintains a depth value for each image sample and uses these to determine which geometric elements of a scene are visible. The key difference, however, between the classical Z buffer and the irregular Z buffer is that the latter allows arbitrary placement of image samples in the image plane, whereas the former requires samples to be arranged in a regular grid. These depth samples are explicitly stored in a two dimensional spatial data structure. During rasterization, triangles are projected onto the image plane as usual, and the data structure is queried to determine which samples overlap each projected triangle. Finally, for each overlapping sample, the standard Z compare and (conditional) frame buffer update are performed.
Реализация
Классический алгоритм растрирования проецирует каждый многоугольник на плоскость изображения и определяет, какие точки выборки из регулярно расположенного множества находятся внутри проецируемого многоугольника. Поскольку местоположение этих образцов (т.е. пикселей) задано неявно, это определение может быть выполнено путем проверки границ относительно неявной сетки точек выборки. Однако, если расположение точек выборки нерегулярно и не может быть вычислено по формуле, этот подход не работает. Нерегулярный Z-буфер решает эту проблему, явно сохраняя местоположения образцов в двухмерной пространственной структуре данных, а затем выполняя запрос к этой структуре для определения, какие образцы находятся внутри проецированного треугольника. Этот последний шаг называется "нерегулярной растризацией". Хотя конкретная используемая структура данных может варьироваться в зависимости от реализации, два изученных подхода – это kd-дерево и сетка связанных списков. Сбалансированная реализация kd-дерева имеет преимущество в том, что гарантирует доступ за O(log(N)). Основной недостаток заключается в том, что параллельное построение kd-дерева может быть затруднено, а обход требует дорогостоящих инструкций ветвления. Сетка списков имеет преимущество в том, что её можно более эффективно реализовать на GPU-оборудовании, которое в первую очередь предназначено для классического Z-буфера. С появлением CUDA программируемость современного графического оборудования была значительно улучшена. Магистерская диссертация "Быстрая растризация треугольников с использованием нерегулярного Z-буфера на CUDA" (см. Внешние ссылки) содержит полное описание программной реализации создания теневых карт на основе нерегулярного Z-буфера на CUDA. Система рендеринга полностью работает на графических процессорах и способна генерировать тени без ступенчатости при пропускной способности в десятки миллионов треугольников в секунду.
The classical rasterization algorithm projects each polygon onto the image plane, and determines which sample points from a regularly spaced set lie inside the projected polygon. Since the locations of these samples (i. e. pixels) are implicit, this determination can be made by testing the edges against the implicit grid of sample points. If, however the locations of the sample points are irregularly spaced and cannot be computed from a formula, then this approach does not work. The irregular Z buffer solves this problem by storing sample locations explicitly in a two dimensional spatial data structure, and later querying this structure to determine which samples lie within a projected triangle. This latter step is referred to as "irregular rasterization". Although the particular data structure used may vary from implementation to implementation, the two studied approaches are the kd tree, and a grid of linked lists. A balanced kd tree implementation has the advantage that it guarantees O(log(N)) access. Its chief disadvantage is that parallel construction of the kd tree may be difficult, and traversal requires expensive branch instructions. The grid of lists has the advantage that it can be implemented more effectively on GPU hardware, which is designed primarily for the classical Z buffer. With the appearance of CUDA, the programmability of current graphics hardware has been drastically improved. The Master Thesis, "Fast Triangle Rasterization using irregular Z buffer on CUDA" (see External Links), provide a complete description to an irregular Z Buffer based shadow mapping software implementation on CUDA. The rendering system is running completely on GPUs. It is capable of generating aliasing free shadows at a throughput of dozens of million triangles per second.
Приложения
Нерегулярный Z-буфер может использоваться в любом приложении, требующем вычислений видимости в произвольных точках плоскости изображения. Было показано, что он особенно хорошо подходит для создания карт теней – алгоритма, работающего в пространстве изображения, для рендеринга жестких теней. Помимо рендеринга теней, потенциальные области применения включают адаптивный антиалиазинг, дрожащую выборку и отображение окружения.
The irregular Z buffer can be used for any application which requires visibility calculations at arbitrary locations in the image plane. It has been shown to be particularly adept at shadow mapping, an image space algorithm for rendering hard shadows. In addition to shadow rendering, potential applications include adaptive anti aliasing, jittered sampling, and environment mapping.