Изменения
Нет описания правки
== Описание Введение ==
Одной из важных задач является визуализация объектов, когда точка обзора находится над плоскостью с 3D или 2D объектами. Определение местоположений объектов и их теней занимает много времени.
{{Задача
== Простейшие алгоритмы отрисовки сцены ==
=== Алгоритм z-буфера (z-buffer algorithm) ===Для удаления невидимых частей объектов существует простой, но длительный метод {{--- }} алгоритм z-буфера.
В направлении просмотра проводится ось z-координат, затем определяется, какие пиксели покрывают проекции объектов.
Алгоритм хранит информацию об уже обработанных объектах в двух буферах: буфере кадра и z-буфере.
Предположим, что мы выбрали пиксель и преобразовываем объект.
*Если z-координата объекта в этом пикселе меньше, чем z-координата, хранимая в z-буфере, тогда новый объект лежит перед видимым на данный момент. Тогда запишем цвет нового объекта в буфер кадра, а его координату {{- --}} в z-буфер.
*Если z-координата объекта в этом пикселе больше, чем z-координата, хранимая в z-буфере, то новый объект не видим, и буферы останутся без изменений.
Алгоритм z-буфера легко реализовать, и он быстро работает. Поэтому именно этот метод используют чаще всего, но у него есть свой недостаток: для хранения z-буфера требуется большое количество памяти, кроме того, требуется дополнительная проверка каждого пикселя, покрываемого объектом.
=== Алгоритм художника (painter's algorithm) ===
Алгоритм художника избегает дополнительных затрат памяти, изначально сортируя объекты по расстоянию от них до точки обзора. Тогда объекты проверяются в так называемом порядке глубины, начиная от самого дальнего. В таком случае при проверке объекта уже не нужна проверка его z-координаты, мы всегда пишем цвет в буфер кадра. Значения, хранимые в буфере ранее просто перезаписываются.
В таком случае мы должны разорвать циклы, разбив один или более объектов на части. (Картинка с примером)
Определение, какие объекты нужно разбить и где, затем сортировка их фрагментов {{- --}} дорогой процесс, так как порядок зависит от положения точки обзора, и мы должны пересчитывать все при каждом ее смещении.
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
Элегантная структура данных, которая позволяет это сделать {{- --}} '''двоичное разбиение пространства ''' (англ. ''binary dpace partition'') или '''BSP-дерево'''.
== Определение ==
Чтобы понять, что из себя представляет BSP-дерево, рассмотрим рисунок. На нем показано двоичное разбиение множества объектов на плоскости и дерево, которое этому разбиению соответствует.
BSP строится с помощью рекурсивного разбиения плоскости прямыми: сначала l1, затем разбиваем полуплоскость выше l1 прямой l2, а ниже {{- --}} прямой l3 и так далее.
Прямые разбивают на фрагменты не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента плоскости окажется не более одного фрагмента объекта.
Этот процесс можно представить с помощью двоичного дерева. Каждый лист дерева соответствует фейсу разбиения, в нем хранится фрагмент объекта, находящийся внутри этого фейса. Каждый узел дерева соответсвует разбивающей прямой, которая хранится в этом узле.
Рассмотрим гиперплоскость h: a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} = 0.
Пусть h^+ {{- --}} положительная полуплоскость, а h^- {{-- - }} отрицательная:
h^+ = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} > 0}
h^- = {(x_1, x_2 ... x_d) : a_1*x_1 + a_2*x_2 + ... + a_d*x_d + a_{d + 1} < 0}
Пусть S - множество объектов, для которого мы строим забиение в d-мерном пространстве.
Пусть v - какая-то вершина дерева, тогда обозначим S(v) множество объектов (возможно пустое), хранимых в этой вершине.
BSP-дерево T для этого множества обектов обладает следующими свойствами:
*Если |S| <= 1, то T - лист. Фрагмент объекта в S, если он существует, хранится в этом листе.
* правый ребенок v является корнем BSP дерева T^+ на множестве объектов S^+ = {h_v^+ \пересечь s : s \in S}
Размер BSP-дерева равен суммарному размеру множеств во всех узлах. То есть, размер BSP-дерева - это число фрагментов, на которые были разбиты объекты.Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустой фейс), то количество узлов пропорционально размеру дерева.Строго говоря, В общем-то размер BSP-дерева ни о чем не говорит, так как мы не знаем ничего об объеме памяти, требуемой для его хранения, так как оно ничего не говорит об объеме памяти, требуемом для храния фрагмента объекта.
Но размер BSP-дерева - неплохая мера для сравнения качества разных BSP-деревьев для данного множества объектов.
Листья BSP-дерева соответствуют фейсам, то есть мы можем каждой вершине v сопоставить полигональную область на плоскости, которая определяется как пересечение полуплоскостей h_mu^ромбик, где mu - предок v, а ромбик = {-, если v левый ребенок; +, если v правый ребенок}
Корню дерева соответсвует все пространство.
Таким образом, серая область на рисунке соответствует региону l_1^+ \пересечь l_2^+ \пересечь l_3^+.
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей.
Обычно ограничивают следующим образом:
Предположим, что мы хотим построить BSP-дерево для множества отрезков на плоскости. Очевидно, что лучшими кандидатами разбивающих прямых являются продолжения данных отрезков.
