Удаление невидимых линий и поверхностей это одна из сложнейших задач, решаемых при визуализации графических моделей. Алгоритмы удаления невидимых линий и поверхностей служат для определения видимости линий, ребер, поверхностей или объемов с точки зрения наблюдателя расположенного в некоторой точке пространства. Наилучшего общего решения данной задачи не существует. Создано большое количество различных способов решения задачи ориентированных на специализированные приложения.
Выбор подходящего алгоритма зависит от нескольких факторов:
§ Требуемой эффективности алгоритма и качества получаемого изображения. Безусловно, получение хорошего качества требует больших вычислительных затрат, но высокое качество изображения не всегда обязательно. Так если изображение быстро изменяется, зритель не в состоянии воспринять мелкие детали нет необходимости добиваться высокой точности изображения. Таким образом, для создания анимированных и статических сцен, как правило, используются различные методы.
§ Используемой геометрической модели. Требуемая для работы алгоритмов исходная информация может отличаться и, следовательно, геометрическая модель накладывает ограничения на перечень применимых алгоритмов. В данном курсе мы в основном будем рассматривать алгоритмы, связанные с гранично-определенными моделями.
§ Необходимости создания различных визуальных эффектов – освещения, прозрачности, зеркального отражения и др. Как правило, простые, эффективные алгоритмы удаления невидимых линий и поверхностей не дают возможности реализовать зеркальное отражение объектов сцены друг от друга и др. сложные эффекты.
Рассмотрим возможные расположения поверхностей относительно наблюдателя. Для примеров выберем плоские многоугольники, учитывая, что во многих случаях ими аппроксимируются сложные поверхности. Очевидно, что плоский многоугольник имеет две стороны, и они не могут быть видны наблюдателю одновременно. Как видно на рис. 8.2 а) вектор нормали, не видимой стороны многоугольника, направлен от наблюдателя. Формирующие сцену поверхности могут полностью или частично экранировать друг друга от наблюдателя, как это показано на рис 8.2 б) и в) соответственно. В некоторых случаях поверхности могут пересекаться, при этом может происходить взаимное экранирование (отметим, что при использовании невыпуклых многоугольников взаимное экранирование может происходить и без пресечения). На рисунке 8.2 г) показан пример такого пересечения многоугольников. Наиболее удаленная от наблюдателя часть многоугольника В, экранируется четырехугольником А, который в свою очередь экранируется частью многоугольника В, лежащей ближе него к наблюдателю. Так же возможна ситуация при которой поверхности не перекрывают друг друга и полностью видны наблюдателю.
a) 
б) 
в) 
г) 
Рисунок 8.2 Различные расположения поверхностей относительно наблюдателя.
Существующие алгоритмы используют два основных подхода к решению задачи удаления невидимых линий и поверхностей. Оба подхода рассматривают объекты как совокупность плоских многоугольников (граней). В первом подходе для каждого из N пикселей экрана определяется, какие из проекций n граней попадают в данную точку, и какая из граней расположена ближе к наблюдателю. Число выполняемых проверок пропорционально n*N. Во втором подходе грани сравниваются между собой, и выясняется их положение относительно наблюдателя. Каждая из n граней сравнивается с оставшимися n-1 гранями, т.е. количество сравнений пропорционально n2. На основе первого подхода строятся алгоритмы, работающие в пространстве изображения. Они имеют дело с экранными координатами и как следствие обладают точностью вычислений до пикселя, при высокой эффективности. Второй подход используют алгоритмы, работающие в объектном пространстве, т.е. с физической системой координат, в которой заданы объекты (например, мировые координаты). Они обладают высокой точностью, возможностью масштабирования, но не высокой эффективностью. Так как, несмотря на меньшее, чем при первом подходе, количество выполняемых сравнений их сложность гораздо выше.
Рассмотрим принципы построения некоторых алгоритмов удаления невидимых линий и поверхностей.