18. Классификация алгоритмов удаления невидимых линий и поверхностей. Алгоритм плавающего горизонта.

Методы удаления невидимых частей сцены можно классифицировать:

4. По выбору удаляемых частей: удаление невидимых линий, ребер, поверхностей, объемов.

5. По порядку обработки элементов сцены: удаление в произвольном порядке и в порядке, определяемом процессом визуализации.

6. По системе координат:

   • алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N²),

   • алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M² ×N).

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

19. Алгоритм использующий z-буфер.

Метод основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты Z для каждого пиксела растра. Координата Z отвечает расстоянию точек пространственных объектов до плоскости проецирования. Например, она может быть экранной координатой Z в системе экранных координат (X, Y,Z), если Z перпендикуляр­на плоскости экрана.

Рассмотрим алгоритм рисования объектов согласно этому методу. Пусть, чем ближе точка в пространстве к плоскости проецирования, тем больше значе­ние Z. Тогда сначала Z-буфер заполняется минимальными значениями. По­том начинается вывод всех объектов. Причем не имеет значение порядок вы­вода объектов. Для каждого объекта выводятся все его пикселы в любом по­рядке. Во время вывода каждого пиксела по его координатам (X, Y) находится текущее значение Z в Z-буфере. Если рисуемый пиксел имеет большее значе­ние Z, чем значение в Z-буфере, то это означает, что эта точка ближе к объек­ту. В этом случае пиксел действительно рисуется, а его Z-координата запи­сывается в Z-буфер. Таким образом, после рисования всех пикселов всех объектов растровое изображение будет состоять из пикселов, которые соот ветствуют точкам объектов с самыми большими значениями координат Z, то есть видимые точки — ближе всех к нам.

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

В настоящее время метод Z-буфера используется во многих графических 3d-акселераторах, которые аппаратно реализуют этот метод. Наиболее целесо­образно, когда акселератор имеет собственную память для Z-буфера, доступ к которой осуществляется быстрее, чем к оперативной памяти компьютера. Возможности аппаратной реализации используются разработчиками и пользователями компьютерной анимации, позволяя достичь большой скорости прорисовки кадров.

Этот алгоритм используется в библиотеке OpenGL для решения задачи загораживания при работе с невыпуклыми объектами.