10 Удаление невидимых граней, ребер и вершин

Это третья операция видеоконвейера, которая преследует цель, подобную цели отсечения по видимому объему: исключить из списка обрабатываемых примитивов те, которые не будут видны. Разница теперь в том, что рассматриваются примитивы, находящиеся внутри видимого объема, и удаляются те, которые заслоняются другими непрозрачными примитивами. В итоге от каждого объекта остается только повернутая к наблюдателю «половинка скорлупки», на визуализацию которой и будут далее тратиться время и память.

План раздела

1. Общая классификация методов удаления невидимых объектов.

2. Алгоритм Робертса.

3. Алгоритм Z-буфера.

Общая классификация методов удаления невидимого

Предмет обсуждения

Модель ОДНОГО трехмерного тела всегда содержит грани объекта, расположенные СО СТОРОНЫ НАБЛЮДАТЕЛЯ (видимые) и грани за линией видимости (невидимые). Правильное отображение видимых и невидимых граней сильно повышает верное восприятие изображения, даже при скромных средствах визуализации, например, выводе «проволочного» изображения.

Пример:

«Проволочное» изображение НЕОДНОЗНАЧНО (левая картинка). Но если выводить только видимые ребра, то даже в проволочном каркасе неоднозначность устраняется.

Сложная сцена может состоять из многих объектов, при этом одни объекты могут заслонять собою другие.

ИТАК, обозначились две проблемы:

ПРОБЛЕМА 1. Как отделить в каждом отдельно взятом объекте видимые грани от невидимых? Разумно выводить только видимые грани и ребра.

ПРОБЛЕМА 2. В каком порядке выводить объекты сцены и их части, чтобы получить правильное изображение?

В данном разделе обсуждаются подходы и приемы, которые помогают преодолеть эти проблемы.

Алгоритмическая основа удаления невидимых примитивов

Этой основой являются разные методы сортировки. Для простоты сравнений каждый примитив сцены рассматривается как его выпуклая оболочка. Оболочки сортируются вдоль осей X, Y и Z. По результатам сортировки можно сравнительно легко выделить пары примитивов, которые гарантированно НЕ ЗАСЛОНЯЮТ друг друга (оболочки таких пар не перекрываются вдоль X и Y) и сосредоточиться на более детальном анализе расположения тех пар, у которых оболочки полностью или частично перекрываются.

Неустранимое противоречие

В научной литературе описано много методов, которые решают обсуждаемую здесь задачу. Но одни методы дают высокое качество, но требуют больших ресурсов и трудны алгоритмически. Другие методы, напротив, дают быстрое решение, но картинка получается некачественная. И это противоречие неустранимо, оно характерно для всех алгоритмов удаления невидимых граней и ребер:

Быстро, но с низкой детальностью картинки

С картинкой высокой четкости, но с большими затратами времени.

Классификация методов удаления невидимых примитивов

ОБЪЕКТНЫЕ МЕТОДЫ

Алгоритмы этих методов работают с объектными координатами примитивов и точек.

ЭКРАННЫЕ МЕТОДЫ

Алгоритмы этих методов работают с координатами ПИКСЕЛОВ, которые изображают на экране точки сцены.

Замечание о трудоемкости методов

В теоретическом программировании трудоемкость алгоритмов сравнивают по количеству наиболее типовых повторяющихся действий в них. Поскольку в основе методов удаления невидимого лежит сортировка, типовое действие тут – сравнение положения двух объектов. То есть можно приближенно считать, что трудоемкость метода удаления невидимых примитивов ПРИМЕРНО ПРОПОРЦИОНАЛЬНА КОЛИЧЕСТВУ ВЫПОЛНЯЕМЫХ СРАВНЕНИЙ.

Что характерно для ОБЪЕКТНЫХ МЕТОДОВ?

Положение КАЖДОГО ПРИМИТИВА сцены сравнивается по очереди с положениями ВСЕХ ОСТАЛЬНЫХ ПРИМИТИВОВ. Примитивов сцены N. Значит, количество сравнений при этом примерно равно N².

Что характерно для ЭКРАННЫХ МЕТОДОВ?

Положение КАЖДОГО ПИКСЕЛА ПЛОСКОСТИ ПРОЕКЦИЙ сравнивается с положениями КАЖДОГО ПРИМИТИВА СЦЕНЫ.

Если количество пикселов вьюпорта равно М, то количество сравнений примерно равно М*N.

ТАК ЧТО ЖЕ МЕНЬШЕ - М*N или N² ?

Понятно, что при М < N (сцена с большим количеством примитивов) произведение M*N меньше, что означает предпочтительность экранных алгоритмов. Справедливо и обратное – при небольшом количестве примитивов сцены предпочтительнее объектные алгоритмы.

Объективности ради следует заметить, что этот теоретический вывод на практике часто не реализуется по причине быстрого удешевления компьютерной памяти (см. ниже замечания по Z-буферу).