Изменения
→BSP-деревья и алгоритм художника
== BSP-деревья и алгоритм художника ==
Предположим, что мы построили BSP-дерево <tex>T </tex> для множества объектов <tex>S </tex> в трехмерном пространстве. Как нам следует использовать его, чтобы получить порядок глубины для алгоритма художника? Пусть p_view <tex>p_{view}</tex> {{- --}} точка обзора, и она лежит над разбивающей плоскостью, хранимой в корне <tex>T</tex>. Тогда ни один из объектов, лежащих под этой плоскостью, не может затемнить (мб перекрыть?) ни один из объектов, лежащих выше нее. Таким образом, мы можем безопасно показать фрагменты объектов из поддерева <tex>T^- </tex> до показа объектов из поддерва <tex>T^+</tex>.
Порядок фрагментов объектов в поддеревьях определяется таким же способом.
painters_algorithm(<tex>T</tex>, pview<tex>p_{view}</tex>) Let ν be the root of <tex>v \leftarrow T.root</tex> if ν <tex>v</tex> is a leaf then Scan-convert the object fragments in <tex>S(νv)</tex>. else if pview <tex>p_{view} \in hh_v^+ν</tex> then painters_algorithm(T−<tex>T^-</tex>, pview<tex>p_{view}</tex>) Scan-convert the object fragments in <tex>S(νv)</tex>. painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) else if pview <tex>p_{view} \in h−νh_v^-</tex> then painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) Scan-convert the object fragments in <tex>S(νv)</tex>. painters_algorithm(T−<tex>T^-</tex>, pview<tex>p_{view}</tex>) else (/∗ pview <tex>p_{view} \in hν h_v</tex> ∗)/ painters_algorithm(<tex>T^+</tex>, pview<tex>p_{view}</tex>) painters_algorithm(T−<tex>T^-</tex>, pview<tex>p_{view}</tex>)
Заметим, что мы не рисуем полигоны из <tex>S(v)</tex>, когда p_view <tex>p_{view}</tex> лежит на разбивающей плоскости <tex>h_v</tex>, потому что полигоны являются плоскими двумерными объектами.
Эффективность данного алгоритма, как и любого другого алгоритма для BSP-деревьев, зависит от размера BSP-дерева. То есть мы должны выбирать разбивающие плоскости таким образом, чтобы фрагментация объектов была минимальной.
Перед тем, как разрабатывать стратегии разбиения, которые порождают маленькие BSP-деревья, мы должны решить, какие типы объектов допустимы.
Мы заинтересовались BSP-деревьями потому, что нам нужена была быстрая реализация удаления скрытых поверхностей для симулятора полетов. Так как скорость {{--- }} наша главная цель, мы должны упростить вид объектов нашего пейзажа: не будем использовать кривые поверхности, представив все с помощью полигонов.Предположим, что фейсы грани полигонов триангулированы, и мы хотим построить в трехмерном пространстве BSP-дерево наименьшего размера для данного множества треугольников.
== Построение BSP-дерева ==
