Алгоритм - удаление - невидимая поверхность
Cтраница 1
Алгоритм удаления невидимых поверхностей состоит из нескольких основных этапов. Каждый этап реализует некоторое частичное преобразование объектов, а весь алгоритм является композицией этих преобразований. Следовательно, между областью определения алгоритма удаления невидимых поверхностей ( множество объектов) и областью значений ( множество видимых частей) может существовать последовательность промежуточных представлений. [1]
Наш выбор алгоритмов удаления невидимых поверхностей не означает, что только представленные здесь методы являются хорошими и эффективными. Другие методы могут быть такими же эффективными и не менее достойными внимания, например алгоритм разработанный Ньюэллом и его коллегами. [2]
Ниже описываются четыре алгоритма удаления невидимых поверхностей, дающие представление о большом разнообразии возможных подходов к решению данной проблемы. Число существующих алгоритмов, конечно, гораздо больше. Сазерленд и др. [134] описали 10 алгоритмов, но даже их подробный обзор не является исчерпывающим. [3]
 |
Функция стратегии для алгоритма Аппеля. [4] |
В формальное описание алгоритма удаления невидимых поверхностей, приведенное в разд. Следовательно, функция стратегии является организационной частью алгоритма. Поскольку все алгоритмы удаления невидимых поверхностей являются итеративными ( некоторые даже рекурсивными, например алгоритм Вар-нока), функция стратегии не может быть представлена в виде обычного отображения. [5]
Ниже описываются четыре алгоритма удаления невидимых поверхностей, дающие представление о большом разнообразии возможных подходов к решению данной проблемы. Число существующих алгоритмов, конечно, гораздо больше. Сазерленд и др. [134] описали 10 алгоритмов, но даже их подробный обзор не является исчерпывающим. [6]
 |
Функция стратегии для алгоритма Аппеля. [7] |
В формальное описание алгоритма удаления невидимых поверхностей, приведенное в разд. Следовательно, функция стратегии является организационной частью алгоритма. Поскольку все алгоритмы удаления невидимых поверхностей являются итеративными ( некоторые даже рекурсивными, например алгоритм Вар-нока), функция стратегии не может быть представлена в виде обычного отображения. [8]
Кульминацией этих работ может стать появление алгоритмов удаления невидимых поверхностей и затенения, достаточно быстродействующих для настоящей интерактивной полутоновой графики. [9]
На рис. 5.4 приведена приближенная классификация алгоритмов удаления невидимых поверхностей по степени сделанных в них упрощений. После того как будут обсуждены несколько представительных примеров конкретных алгоритмов, мы разработаем более подробную классификацию. [10]
На рис. 5.4 приведена приближенная классификация алгоритмов удаления невидимых поверхностей по степени сделанных в них упрощений. После того как будут обсуждены несколько представительных примеров конкретных алгоритмов, мы разработаем более подробную классификацию. [11]
Операции сортировки используются и на различных этапах работы большинства алгоритмов удаления невидимых поверхностей В методе Аппеля, например, грани сначала разбиваются на полностью невидимые и потенциально видимые. В конце концов ребра потенциально видимых граней подразделяются на отрезки с разными значениями количественной невидимости; этот процесс также может рассматриваться как сортировка отрезков. В методе приоритетов Энкарнако треугольные грани рассортировываются сначала на два класса. В один класс входят грани, полностью отделенные от других граней, в другой - все остальные. Грани, входящие во второй класс, распределяются ( сортируются) затем по множествам Tit упорядоченным по неубыванию в соответствии с приоритетом. Последний этап процедуры - определение взаимного перекрытия и видимости внутри пар ( tiTi) ( разд. Действительно, поскольку ребра 6i k ti, & e [ I: 3 ] проверяются отдельно, можно увеличить скорость работы алгоритма, переместив треугольник t /, перекрывающий е /, 1, в голову списка Ti, поскольку вероятность того, что ti перекроет также е -, 2 и eit 3 ( по крайней мере одна из крайних точек е, 2 и e - i3 лежит в треугольнике -), выше средней. [12]
Операции сортировки используются и на различных этапах работы большинства алгоритмов удаления невидимых поверхностей В методе Аппеля, например, грани сначала разбиваются на полностью невидимые и потенциально видимые. В конце концов ребра потенциально видимых граней подразделяются на отрезки с разными значениями количественной невидимости; этот процесс также может рассматриваться как сортировка отрезков. В методе приоритетов Энкарнако треугольные грани рассортировываются сначала на два класса, В один класс входят грани, полностью отделенные от других граней, в другой - все остальные. Грани, входящие во второй класс, распределяются ( сортируются) затем по множествам Ti, упорядоченным по неубыванию в соответствии с приоритетом. Последний этап процедуры - определение взаимного перекрытия и видимости внутри пар ( tiTi) ( разд. [13]
Проблема построения перспективного изображения подробно рассмотрена в гл. Как уже было сказано, почти во всех алгоритмах удаления невидимых поверхностей используется простая ортогональная проекция, практически совпадающая с операцией тождественного отображения: если ( х, у, z) - точка в объектном пространстве, a ( А У) - ее проекция на картинную плоскость, то для определения X и Y можно использовать простые соотношения X х и У у. Таким образом, координаты х и у совпадают в обоих пространствах, а координата г при отображении отбрасывается. [14]
Проблема построения перспективного изображения подробно рассмотрена в гл. Как уже было сказано, почти во всех алгоритмах удаления невидимых поверхностей используется простая ортогональная проекция, практически совпадающая с операцией тождественного отображения: если ( х, у, г ] - точка в объектном пространстве, a ( XY) - ее проекция на картинную плоскость, то для определения X и У можно использовать простые соотношения X х и У у. Таким образом, координаты х и у совпадают в обоих пространствах, а координата г при отображении отбрасывается. [15]
Страницы: 1 2