Удаление нелицевых плоскостей

Для каждого тела в сцене:

Сформировать многоугольники граней и ребра, исходя из списка вершин тела.

Вычислить уравнение плоскости для каждой полигональной грани тела.

Проверить знак уравнения плоскости:

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

Вычислить скалярное произведение уравнения плоскости и точки внутри тела.

Если это скалярное произведение < О, то изменить знак уравнения этой плоскости.

Сформировать матрицу тела.

Умножить ее слева на матрицу, обратную матрице видового преобразования, включающего перспективу.

Вычислить и запомнить габариты прямоугольной объемлющей оболочки преобразованного объема: xmin, xmax,ymin, ymax.

Определить нелицевые плоскости:

Вычислить скалярное произведение пробной точки, лежащей в бесконечности, на преобразованную матрицу тела.

Если это скалярное произведение < О, то плоскость невидима.

Удалить весь многоугольник, лежащий в этой плоскости. Это избавляет от необходимости отдельно рассматривать, невидимые линии, образуемые пересечением пар невидимых плоскостей.

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

Если задано только одно тело, то алгоритм завершается.

Сформировать приоритетный список этих тел:

Провести сортировку по z. Сортировка производится по максимальным значениям координаты z вершин преобразованных тел. Первым в упорядоченном списке и обладающим наиболь­шим приоритетом будет то тело, у которого минимальное среди максимальных значений z. В используемой правой системе координат это тело будет самым удаленным от точки наблюдения, расположенной в бесконечности на оси z.

Для каждого тела из приоритетного списка:

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

Провести проверки экранирования для прямоугольных объ­емлющих оболочек пробного объекта и пробного тела:

Если xmin (пробное тело) > xmax(пробный объект) или

xmax(пробное тело) < xmin(пробный объект) или

ymin (пробное тело) > ymax(пробный объект) или

ymax (пробное тело) < ymin(пробный объект),

то пробное тело не может экранировать ни одного ребра пробного объекта. Перейти к следующему пробному телу. В противном случае:

Провести предварительные проверки протыкания, чтобы увидеть, не протыкается ли пробное тело пробным объек­том и существует ли возможность частичного экранирова­ния первого последним.

Сравнить максимальное значение z у пробного объекта с минимальным значением z у пробного тела.

Если zmax(пробный объект) < zmin (пробное тело), то протыкание невозможно. Перейти к следующему те­лу. В противном случае:

Проверить видимое протыкание.

Если zmin(пробный объект) > zmax (пробное тело), то пробный объект может проткнуть переднюю грань пробного тела.

Установить флаг видимого протыкания для последу­ющего использования. Занести проткнутое тело в спи­сок протыканий.

Если xmax(пробное тело) > xmin(пробный объект) или

xmin (пробное тело) < xmax(пробный объект),

то пробный объект может проткнуть бок пробного тела.

Установить флаг видимого протыкания для последу­ющего использования. Завести тело в список проты­каний.

Если ymax (пробное тело) > ymin(пробный объект) или

ymin (пробное тело) < ymax(пробный объект),

то пробный объект может проткнуть верх или виз пробного тела.

Установить флаг видимого протыкания для последующего использования. Занести проткнутое тело в список протыканий.

Если список протыканий пуст, то устанавливать флаг протыкания не надо.

Провести проверки экранирования ребер:

Вычислить s и d для ребра.

Вы числить p, q, w для каждой плоскости, несущей грань пробного тела.

Проверка полной видимости. Если ребро полностью, ви­димо, то перейти к следующему ребру.

Сформировать уравнения hj = 0 и решить их, объединяя попарно и включив в систему уравнения границ t = 0 и t = 1. Если установлен флаг видимого протыкания, то в систему надо включить и уравнение границы a = 0. За­помнить точки протыкания. В противном случае грани­цу a = 0 не учитывать.

Для каждой пары (t, a), являющейся решением проверить выполнение условий 0 £ t £ 1, a ³ 0 и hj > 0 для всех других плоскостей. Если эти условия выпол­нены, то найти tmaxmin и tminmax.

Вычислить видимые участки отрезков и сохранить их для последующей проверки экранирования телами с бо­лее низкими приоритетами.

Определить видимые отрезки, связывающие точки протыка­ния:

Если флаг видимого протыкания не установлен, перейти к процедуре визуализации.

Если точек протыкания не обнаружено, перейти к процеду­ре визуализации.

Сформировать все возможные ребра, соединяющие точ­ки протыкания, для пар тел, связанных отношением протыкания.

Проверить экранирование всех соединяющих ребер обои­ми телами, связанными отношением протыкания.

Проверить экранирование оставшихся соединяющих ре­бер всеми прочими телами сцены. Запомнить видимые отрезки.

Визуализировать оставшиеся видимые отрезки ребер.

3.3. Алгоритм использующий Z-буфер

Это один из простейших алгоритмов удаления невидимых поверх­ностей. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пиксела в пространстве изображения. Z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пиксела в пространстве изображения. В процессе работы глубина или значение z каждого нового пиксела, который нужно занести в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в z-буфер. Если это сравнение пока­зывает, что новый пиксел расположен впереди пиксела, находящегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, производится корректировка z-буфера новым значени­ем z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поис­ком по x и y наибольшего значения функции z (z, y).

Главное преимущество алгоритма - его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элемен­ты сцены или картинки можно заносить в буфер кадра или в z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычис­лительное время, затрачиваемое на сортировку по глубине.