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

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

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

Реализация алгоритма включает несколько этапов.

  1. Поверхности, направленные к наблюдателю, выделяются из всех остальных в отдельную группу при помощи алгоритма невидимых граней. Выделенные поверхности сохраняются в массив FACE-TABLE. Грани, направленные от наблюдателя, учитывать не требуется, поскольку они сами по себе скрыты, а потому не скрывают ребра других граней. Для каждой грани сохраняется максимальное и минимальное значение Zv.. Криволинейные поверхности разделяются по силуэтным линиям (как в алгоритме невидимых граней), а видимые части этих поверхностей также сохраняются в массиве FACE-TABLE вместе с плоскими гранями.
  2. Ребра граней из массива FACE-TABLE выделяются из всех прочих ребер и собираются в отдельный список. Ребра других граней, не входящих в FACE- TABLE, можно не рассматривать, поскольку они невидимы. Затем для каждого ребра из списка производится проверка, не закрывается ли это ребро гранью из FACE-TABLE.
  3. Скрытие ребра гранью можно обнаружить, сравнивая диапазоны значений Zv. ребра и грани. Возможны три случая (рис. 3.25). В случае рис. 3.25, а нее значения Zv., ребра меньше минимального значения Zv. грани, то есть грань находится перед ребром. В случае рис. 3.25, б значения Zv. ребра больше максимального значения Zv., грани, то есть грань находится за ребром. В случае рис. 3.25, в диапазоны значений Z, грани и ребра перекрываются, то есть часть ребра находится за гранью, а другая часть — перед ней. Если ребро находится перед проверяемой гранью, из массива FACE-TABLE выбирается следующая грань и ребро сравнивается уже с ней. Если ребро оказывается за гранью, или проходит ее насквозь, приходится выполнять дополнительное действие.
  4. Ребро и грань проецируются на экран, после чего производится проверка перекрытия проекций. Если перекрытия нет, из этого следует, что ребро не закрывает проверяемую грань. Из массива FACE-TABLE выбирается следующая грань и проверяется согласно пункту 3. Если проекции перекрываются, ребро делится на две части в той точке, где она проходит сквозь проверяемую грань (рис. 3.26). Закрытая часть ребра отбрасывается, а видимые части добавляются в список. Затем пункт 3 повторяется для новых элементов списка. Исходное ребро из списка удаляется.
  5. Ребра, прошедшие проверку со всеми гранями из FACE-TABLE, считаются видимыми и выводятся на экран.
 
 

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

 

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

 

 


1 Ребром объекта называется кривая пересечения соседних поверхностей, ограничивающих внутренний объем объекта.

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

Смотрите также