12.Алгоритмы удаления невидимых линий и поверхностей. Основные понятия и определения.
Удаление невидимых линий и поверхностей - это одна из наиболее сложных задач машинной графики. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые невидимы для наблюдателя, смотрящего на объект из заданной точки пространства. Даже при отображении простейших моделей возникают сложности (рис. 7.1).
Р
ис.
7.1 Две возможных интерпретации невидимых
граней
Разработано много алгоритмов решения данной задачи. Чем быстрее работает алгоритм, тем хуже результат его работы, и, наоборот, чем более качественные результаты показывает алгоритм, чем медленнее он работает. То есть имеет место обратная зависимость: СКОРОСТЬ . 1/РЕЗУЛЬТАТ.
Все алгоритмы, решающие данную задачу, включают в себя процедуру сортировки: по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Поскольку чем больше это расстояние, тем больше у обрабатываемого объекта вероятность оказаться заслоненным.
1.По выбору удаляемых частей: удаление невидимых линий, ребер, поверхностей, объемов.
2.По порядку обработки элементов сцены: удаление в произвольном порядке и в порядке, определяемом процессом визуализации.
3.По системе координа.:
Существует два основных подхода к решению данной задачи.
первый подход заключается в непосредственном сравнении объектов друг с другом для выяснения того. какие части объектов являются видимыми. В данном случае работа ведется в пространстве объектов. Этот подход используется в алгоритмах отсечения нелицевых граней и в алгоритме Робертса.
Второй подход заключается в определении для каждого пиксела экрана ближайшего к нему объекта (вдоль направления проецирования). При этом работа ведется в пространстве экранных координат. Это такие алгоритмы как алгоритм Z-буфера, алгоритм Варнака, алгоритм построчного сканирования.
Наиболее известный ранний алгоритм - алгоритм Робертса (1963 г.). Работает с только выпуклыми телами в пространстве объектов. Каждый объект сцены представляется многогранным телом, полученным в результате пересечения плоскостей. Т.е. тело описывается списком граней, состоящих из ребер, которые в свою очередь образованы вершинами.
Вначале из описания каждого тела удаляются нелицевые плоскости, экранированные самим телом. Затем каждое из ребер сравнивается с каждым телом для определения видимости или невидимости. Т.е. объем вычислений растет как квадрат числа объектов в сцене. Наконец вычисляются новые ребра, полученные при протыкании телами друг друга.
13.Классификация алгоритмов удаления невидимых линий и поверхностей. Алгоритм плавающего горизонта.
Методы удаления невидимых частей сцены можно классифицировать:
1)По выбору удаляемых частей: удаление невидимых линий, ребер, поверхностей, объемов.
2)По порядку обработки элементов сцены: удаление в произвольном порядке и в порядке, определяемом процессом визуализации.
3)По системе координат:
алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N2),
алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M2 ×N).
Алгоритм плавающего горизонта используется для каркасного изображения, когда объект представляется в виде набора кривых или ломанных линий. АПГ чаще всего испоьзуется для удаления невидимых линий, трехмерного представления ф-ций, описывающих поверхности. Этот алгоритм обычно работает в пространстве изображений. Главная идея этого алгоритма заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянное значение координат X, Y или Z. Алгоритм: сначала упорядочивают плоскости по возрастанию расстояния до них от точки наблюдения, а затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней.