3.6.4 Удаление невидимых граней

Задача удаления невидимых линий и поверхностей является одной из наиболее сложных задач в компьютерной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий, ребер, поверхностей или объемов,которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.

Алгоритм Робертсапредставляет собой первое известное решение задачи удаления невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, ко­торые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для опре­деления того, какая его часть или части, если таковые есть, экрани­руются этими телами. Поэтому вычислительная трудоемкость ал­горитмаРобертсарастет теоретически как квадрат числа объек­тов. Это в сочетании с ростом интереса к растровым дисплеям, ра­ботающим в пространстве изображения, привело к снижению инте­реса к алгоритмуРобертса.Однако математические методы, ис­пользуемые в этом алгоритме, просты, мощны и точны. Кроме то­го, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алго­ритма, использующие приоритетную предварительную сортировку вдоль осиzи простые габаритные или минимаксные тесты, де­монстрируют почти линейную зависимость количества вычислений от числа объектов.

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

(3.41)

В матричной форме этот результат выглядит так:

(3.42)

или

(3.43)

где [P]^T = [a b c d] представляет собой плоскость.Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящейиз коэффициентов уравнений плоскостей, т.е.

(3.44)

где каждый столбец содержит коэффициенты одной плоскости.

Напомним, что любая точка пространствапредставимав одно­родных координатах вектором

(3.45)

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

Поскольку объем вычислений в алгоритмах удаления невидимых линий или поверхностей растет с увеличением числа многоугольни­ков, для описания поверхностей выгодно использовать многоуголь­ники с более чем тремя сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими. Метод, предложенный Мартином Ньюэлом,позволяет найти как точное решение для уравнений плоскостей, содержащих плоские многоугольники, так и «наилучшее» приближение длянеплоскихмногоугольников. Этот метод эквивалентен определению нормали в каждой вершине мно­гоугольника посредством векторного произведения прилежащих ре­бер и усреднения результатов. Еслиа, b, с, d -коэффициенты уравнения плоскости,то

(3.46)

где если i = п, то j = 1, иначе j = i + 1.

А величина dвычисляется с помощью произвольной точки на плоско­сти. В частности, если компоненты этой точки на плоскости (x₁,y₁,z₁), то

(3.47)

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

Если зритель находится в бесконечности на положительной по­луоси zи смотрит на начало координат, то его взгляд направлен в сторону отрицательной полуосиz. В однородных координатах век­тор такого направления равен:

(3.48)

который служит, кроме того, образом точки, лежащей в бесконеч­ности на отрицательной полуоси z. Фактическипредставляет любую точку, лежащую наплоскостиz = -,т.е.любую точку типа (х, у,-). Поэтому, если скалярное произведениена столбец, соответствующий какой-нибудь плоскости в матрице тела отрицательно, толежит по отрицательную сторону этой пло­скости. Следовательно, эти плоскости невидимы из любой точки наблюдения, лежащей в плоскостиz = ,а пробная точка наz=-экранируется самим телом. Та­кие плоскости называются нелицевыми, а соответствующие им грани - задними. Следовательно,

(3.49)

является условием того, что плоскости — нелицевые, а их грани–задние (см. рис. 3.15).

Рис. 3.15

Заметим, что для аксонометрических проекций (точка наблюденияв бесконечности) это эквивалентно поиску положительных значений в третьей строке матрицы тела.

Этот метод является простейшим алгоритмом удаления невиди­мых поверхностей для тел, представляющих собой одиночные вы­пуклые многогранники. Для выпуклых многогранников число граней при этом сокращается примерно наполовину. Метод эквивалентен вы­числению нормали к поверхности для каждого отдельного много­угольника. Отрицательность нормали к поверхности показывает, что нормаль направлена в сторону от наблюдателя и, следователь­но, данная грань не видна.