ИСМ-06-2:

назад

7. а) Алгоритмы компьютерной графики (удаление невидимых линий и граней, художника)

Удаление невидимых линий и поверхностей 

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

1) алгоритмы, работающие в пространстве объекта (для определения видимости данной грани сравнивается ее взаимное расположение со всеми остальными гранями в сцене)

        2) алгоритмы, работающие в пространстве изображения (основаны на нахождении точки ближайшей грани, которую пересекает луч зрения, проходящий через заданную точку в растре)

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

Алгоритм удаления невидимых граней.

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


Этот алгоритм легко применим к объекту, ограниченному плоскими гранями (выпуклому), поскольку вектор нормали постоянен в пределах поверхности. Однако, к вогнутому объекту алгоритм неприменим.

Алгоритм художника.

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

 

Алгоритм удаления невидимых линий

Алгоритм сортировки по глубине используется для удаления невидимых поверхностей. Алгоритм невидимых граней позволяет построить рисунок со скрытыми линиями, но имеет множество ограничений в общем случае. При применении алгоритма невидимых граней к множеству объектов удалено будет лишь около 50% невидимых линий. Нужен алгоритм, который удалял бы все невидимые линии независимо от количества объектов, их выпуклости и наличия криволинейных поверхностей.

Один из таких алгоритмов действует следующим образом. Для каждого ребра (ребром объекта называется кривая пересечения соседних поверхностей, ограничивающих внутренний объем объекта [1]) каждого объекта производится проверка, не закрыто ли оно гранями (гранями называются поверхности, ограничивающие объем объекта; площадь любой грани конечна, потомку что все грани ограничиваются ребрами [1]) каких-либо объектов. Закрытые части ребер последовательно исключаются до тех пор, пока не останется непроверенных поверхностей. Оставшиеся части ребер выводятся на экран.Реализация алгоритма включает несколько этапов.

 1. Поверхности, направленные к наблюдателю, выделяются из всех остальных при помощи алгоритма невидимых граней. Выделенные поверхности сохраняются в массив FACE-TABLE. Грани, направленные от наблюдателя, учитывать не требуется, поскольку они сами по себе скрыты, а потому не скрывают ребра других граней. Для каждой грани сохраняется максимальное и минимальное значение Zv. Криволинейные поверхности разделяются по силуэтным линиям (как в алгоритме невидимых граней), а видимые части этих поверхностей также сохраняются в массиве FACE-TABLE. Вместе с плоскими гранями.

2. Ребра граней из массива FACE-TABLE выделяются из всех прочих ребер и собираются в отдельный список. Ребра других граней, не входящих в FACE-TABLE, можно не рассматривать, поскольку они невидимы. Затем для каждого ребра из списка производится проверка, не закрывается ли это ребро гранью из FACE-TABLE.

3. Скрытие ребра гранью можно обнаружить, сравнивая диапазоны значений Zv ребра и грани. Возможны три случая (рис. 45). В случае рис. 45 (а), все значения Zv ребра меньше минимального значения Zv грани, то есть, грань находится перед ребром. В случае рис. 45 (б) значения Zv ребра больше максимального значения Zv грани, то есть грань находится за ребром. В случае рис. 45 (в) диапазоны значений Zv грани и ребра перекрываются, то есть часть ребра находится за гранью, а другая часть – перед ней. Если ребро находится перед проверяемой гранью, из массива FACE-TABLE выбирается следующая грань и ребро сравнивается уже с ней. Если ребро оказывается за гранью, или проходит ее насквозь, приходится выполнять дополнительное действие.

4. Ребро и грань проецируются на экран, после чего производится проверка перекрытия проекций. Если перекрытия нет, из этого следует, что ребро не закрывает проверяемую грань. Из массива FACE-TABLE выбирается следующая грань и проверяется согласно пункту 3. Если проекции перекрываются, ребро делится на две части по той точке, где она проходит сквозь проверяемую грань (рис. 46). Закрытая часть ребра отбрасывается, а видимые части добавляются в список. Затем пункт 3 повторяется для новых элементов списка. Исходное ребро удаляется из списка.

5. Ребра, прошедшие проверку со всеми гранями из FACE-TABLE, считаются видимыми и выводятся на экран.

  

Приминение – модули черчения

[редактировать]

назад

© ism-06-2.ru