logo
Ответы по компьютерной графике

18. Показ с удалением невидимых точек. Классификация методов

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

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

Эти методы различаются по следующим основным параметрам.

  1. По способу представления объектов:

● аналитические (явные и неявные);

● параметрические;

● полигональные.

  1. По способу визуализации сцены.

При построении каркасных изображений (wireframe – рисуются только ребра) используются методы удаления невидимых линий (ребер каркасных изображений), для визуализации сплошных изображений (solid – рисуются закрашенные грани) – методы удаления невидимых поверхностей (граней сплошных изображе- ний).

  1. По пространству, в котором производится анализ видимости:

● методы, работающие непосредственно в пространстве самих объектов;

● методы, работающие в пространстве картинной плоскости, т.е. работающие с проекциями объектов.

  1. По виду получаемого результата (его точности):

● набор видимых областей или отрезков, заданный с машинной точностью (имеет непрерывный вид);

● информация о ближайшем объекте для каждого пиксела экрана (имеет дискретный вид).

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

Так как эти методы работают с непрерывными исходными данными и получающиеся результаты не зависят от растровых свойств, то их иногда называют непрерывными (continuous methods). Простейший вариант непрерывного подхода заключается в сравнении каждого объекта со всеми остальными, что дает временные затраты, пропорциональные n2, где n – количество объектов в сцене.

Однако следует иметь в виду, что непрерывные методы, как правило, достаточно сложны.

Методы второго класса (point-sampling methods) дают приближенное решение задачи удаления невидимых линий, определяя видимость только в некотором наборе точек картинной плоскости – в точках растровой решетки. Они очень сильно привязаны к растровым свойствам картинной плоскости и фактически заключаются в определении для каждого пиксела той грани, которая является ближайшей к нему вдоль направления проектирования.

Простейший вариант дискретного метода имеет временные затраты порядка Cn, где C – общее количество пикселов экрана, n – число объектов.

Всем методам второго класса традиционно свойственны ошибки дискретизации (aliasing artifacts). Однако, как правило, дискретные методы отличаются простотой реализации.

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

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

Очень распространенной структурой данных в задачах удаления невидимых линий и поверхностей являются различные типы деревьев: двоичные (BSP-trees), четверичные (Quadtrees), восьмеричные (Octtrees) и др.

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

Метод плавающего горизонта. Грани выводятся в последовательности от ближайших к самым дальним. На каждом шаге границы граней образуют две ломаные линии – верхний горизонт и нижний горизонт. Во время вывода каждой новой грани рисуется только то, что выше верхнего горизонта, и то, что ниже нижнего горизонта. Каждая новая грань поднимает верхний и опускает нижний горизонты. Этот метод часто используется для показа поверхностей, описываемых явным уравнением z = f (x, y).