Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

____________________________________________________________________

А.И. Дружинин алгоритмы компьютерной графики

Часть 2

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

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

НОВОСИБИРСК

2007

Рецензенты: канд. техн. наук, ст. преп. Е.Л. Веретельникова

канд. педагог. наук, доцент В.В. Вихман

Работа подготовлена на кафедре вычислительной техники для студентов II курса АВТФ (направление 230100) и студентов V курса АВТФ (специальности 230101, 230105)

Дружинин А.И.

Алгоритмы компьютерной графики: Учеб. пособие. – Новосибирск: Изд-во НГТУ, 2007. – с.

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

Пособие адресовано студентам, изучающим курс "Компьютерная и инженерная графика", а также может быть полезно разработчикам программного обеспечения.

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

©

Новосибирский государственный технический университет, 2007 г.

Введение

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

Сложность задачи можно проиллюстрировать следующим примером (рис. В.1). На рис В.1, а приведен каркасный чертеж четырехгранной пирамиды [6]. Его можно интерпретировать двояко: как вид пирамиды спереди, (рис В.1, б) или снизу (рис. В.1, в).

Рис. В.1. Необходимость удаления невидимых линий

Существует множество способов решения задачи удаления невидимых линий и поверхностей. Одни из них ориентированы на специальные приложения (то есть, улучшаются одни параметры и ухудшаются другие – такие как скорость построения, детализация прорисовки и т.д.). Другие, ориентированные на выполнение «общих» задач, пытаются оптимизировать все параметры наилучшим образом (по мнению авторов алгоритма).

Несмотря на множественность решений, все алгоритмы включают в себя сортировку. И главная сортировка – сортировка по геометрическому расстоянию от тела, поверхности, ребра, точки до точки наблюдения (наблюдателя). Обычно, это сортировка по оси Z. Основной смысл этой сортировки – чем дальше объект расположен от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к наблюдателю. После определения приоритетов по глубине (сортировка по расстоянию до точки наблюдения) остается провести сортировку по горизонтали и вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Таким образом, эффективность алгоритмов зависит от эффективности алгоритмов сортировки.

Алгоритмы удаления невидимых линий и поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Выделяется два класса алгоритмов удаления невидимых линий и поверхностей:

• алгоритмы, работающие в объектном пространстве;

• алгоритмы, работающие в пространстве изображения.

Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно изменять (увеличивать, уменьшать, «закручивать» и т.д.) без изменения точности изображения. То есть, алгоритмы, работающие в объектном пространстве, необходимы там, где необходима высокая точность.

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

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