Алгоритм - удаление - невидимая поверхность
Cтраница 2
В формальное описание алгоритма удаления невидимых поверхностей, приведенное в разд. Следовательно, функция стратегии является организационной частью алгоритма. Поскольку все алгоритмы удаления невидимых поверхностей являются итеративными ( некоторые даже рекурсивными, например алгоритм Вар-нока), функция стратегии не может быть представлена в виде обычного отображения. [16]
Алгоритм удаления невидимых поверхностей состоит из нескольких основных этапов. Каждый этап реализует некоторое частичное преобразование объектов, а весь алгоритм является композицией этих преобразований. Следовательно, между областью определения алгоритма удаления невидимых поверхностей ( множество объектов) и областью значений ( множество видимых частей) может существовать последовательность промежуточных представлений. [17]
В большинстве случаев параметр, по значению которого осуществляется сортировка ( ключ сортировки), является результатом работы одного из тестов принадлежности или видимости. Как показывает статистика ( рис. 5.35), эти тесты дают основной вклад в общее время выполнения алгоритмов. Поэтому, хотя сортировка является основной операцией в большинстве алгоритмов удаления невидимых поверхностей, эффективность схемы сортировки самой по себе не оказывает существенного влияния на общее время выполнения алгоритма. Время, занимаемое сортировкой, входит во время, затрачиваемое организационной частью алгоритма, которое в свою очередь составляет лишь малую долю суммарного времени. Значительный выигрыш во времени можно получить, уменьшив количество медленных арифметических операций, требуемых для вычисления пересечений, выполнения тестов принадлежности и тестов видимости, например, путем выполнения операций предварительной сортировки, основанных на простых логических функциях и функциях отношения. [18]
В большинстве случаев параметр, по значению которого осуществляется сортировка ( ключ сортировки), является результатом работы одного из тестов принадлежности или видимости. Как показывает статистика ( рис. 5.35), эти тесты дают основной вклад в общее время выполнения алгоритмов. Поэтому, хотя сортировка является основной операцией в большинстве алгоритмов удаления невидимых поверхностей, эффективность схемы сортировки самой по себе не оказывает существенного влияния на общее время выполнения алгоритма. Время, занимаемое сортировкой, входит во время, затрачиваемое организационной частью алгоритма, кото рое в свою очередь составляет лишь малую долю суммарного времени. Значительный выигрыш во времени можно получить, уменьшив количество медленных арифметических операций, требуемых для вычисления пересечений, выполнения тестов принадлежности и тестов видимости, например, путем выполнения операций предварительной сортировки, основанных на простых логических функциях и функциях отношения. [19]
 |
Сравнение восьми алгоритмов удаления невидимых поверхностей по их разрешающей способности. [20] |
Было бы интересно сравнить эффективность существующих алгоритмов удаления невидимых поверхностей. Однако общая оценка эффективности невозможна, поскольку скорость работы алгоритма зависит не только от сложности сцены, но и от свойств изображаемых объектов. Очень трудно, а может быть и невозможно, определить общую меру сложности объектов, не говоря уже о мере их свойств. Любая мера сложности, основанная на подсчете числа тел, граней, ребер или других графических элементов в сцене, не имеет реального значения, если она не дополняется мерой, выражающей степень взаимного заслонения этих элементов. Более того, эффективность алгоритма удаления невидимых поверхностей очень сильно зависит от типа изображаемых объектов. [21]
Функция, реализующая тест глубины DT, применяется к двум перекрывающимся графическим элементам и определяет, какой из элементов заслоняет другой. Сравниваемыми элементами могут быть точка и грань или две грани. Глубиной мы называем расстояние между элементом и картинной плоскостью или между элементом и точкой наблюдения. Таким образом, глубина относится к г-координате элемента. Следовательно, тест глубины обычно заключается в сравнении z - координат двух элементов. Трудно себе представить алгоритм удаления невидимых поверхностей, в котором отсутствует тест глубины. В настоящее время известны три типа тестов глубины, которые мы обозначим как DTI, DT2, DT3 и рассмотрим ниже. [22]
Функция, реализующая тест глубины DT, применяется к двум перекрывающимся графическим элементам и определяет, какой из элементов заслоняет другой. Сравниваемыми элементами могут быть точка и грань или две грани. Глубиной мы называем расстояние между элементом и картинной плоскостью или между элементом и точкой наблюдения. Таким образом, глубина относится к г-координате элемента. Следовательно, тест глубины обычно заключается в сравнении г-координат двух элементов. Трудно себе представить алгоритм удаления невидимых поверхностей, в котором отсутствует тест глубины. В настоящее время известны три типа тестов глубины, которые мы обозначим как DTI, DT2, DT3 и рассмотрим ниже. [23]
Страницы: 1 2