13. Удаление скрытых частей изображений.

Задача загораживания ЗЗ (удаление невидимых частей сцены) возникла в процессе визуализации каркасных изображений на векторных дисплеях (на растровых – проблема удаления скрытых поверхностей).

В алгоритмах загораживания обычно предполагается, что экран расположен в проекционной плоскости, z = 0, сцена находится позади него, а центр проекции (и наблюдатель) – перед экраном. При проектировании проекторы проводятся через каждую точку объекта, тогда видимыми будут те точки, которые вдоль направления проектирования располагаются ближе всего к экрану. Нет единственного универсального решения задачи. Известные методы решения ЗЗ различаются м/д собой по 4м основным характеристикам: *выбору структуры данных для представления поверхностей (поверхности м.б. представлены аналитически, уравнениями в неявной форме для визуализации квадратичных поверхностей: сфера, цилиндр, конус; полигонально – совокупностью полигонов, полиномиально – бикубическими сегментами). *способу визуализации поверхности (алг-мы ориентированы либо на получение сеточных изображений, либо на получение полутоновых или закрашенных изображений). *по использованию специфических геометр св-ств изображаемых объектов (Н-р: выпуклые многоугольники или гладкие не самопересекающиеся поверхности существенно отлич от произвольных, расположенных случайным образом в пространстве, всякая грань выпукл мн-ка либо полностью видима, либо полностью невидима. Частичного загораживания нет. Если можно найти приоритет в сцене, согласно которому проводить обработку данных то это может существенно сократить время обработки) *пространство, в котором работает алгоритм (это м. б. пространство объектов (по) и пространство изображений (пи) ал-мы, работающие в по имеют дело с системой координат объекта, в декартовом пр-ве каждый n объект сцены сравнивается с оставшимися n-1. Объем вычислений пропорционален квадрату объектов. Достоинство: качество, возможность масштабировать без потери качества. Ал-мы работающие в пи отталкиваются от приборной сист коорд экрана т.е. определяют видимость каждого пикселя картины. Объем вычисл пропорц nN, n – кол-во объектов в сцене, N- число пикселов экрана. Точность вычисл ограничена расширением экрана и при масштабировании теряется качество.)

Алгитмы переборного типа.

относятся к первым алг-мам З. В них пытались точно решить задачу о том, что д.б. удалено. Для этого использовали геометрический подход к задаче: рассмотр каждое ребро сцены и его положение сопоставлялось с каждой из граней сцены. При этом м.б. 3 случая: 1) ребро полностью видимое, располож перед гранью и м/д гранью и наблюдателем. 2) ребро находится за гранью 3) ребро пересекает грань. 3 случай приводили к первым двум деля на части. Завершался анализ либо когда были просмотрены все грани выводилась видимая часть ребра, либо когда все ребро становилось невидимым. Алгоритмы данного типа работают в пространстве объекта. Типичным представителем данного семейства явл алг Роберса. Прежде всего в нем удаляются невидимые части экранируемые самим телом, а потом те, которые загораживает другой объект. Затем каждая из видимых частей, каждого тела, сравнивается с каждым из оставшихся. Достоинство: использование простых, мощных и точных математических методов, которые используются до сих пор. Н-р: метод удаления не лицевых граней. Внешняя сторона объекта будет видима наблюдателю тогда, когда нормаль грани будет направлена к наблюдателю т.е. грань будет лицевой, если угол  м/д вектором нормали и наблюдателем лежит в пределах -90, cos≥0. Для КГ последнее условие проанализировать проще т.к. знак косинуса легко определяется по скалярному произведению. Если уравнение плоскости грани имеет вид: ax+by+cz+d=0 то требуется проверить только знак коэффициента с. Такая проверка м.б. выполнена и аппаратно и программно. Для нахождения нормали также можно воспользоваться векторным произведением любых 2х смежных векторов грани. Данный м решает ЗЗ полностью для визуализации выпуклых многогранников, но м.б. применен и для решения частных задач отображения сцены.

Разбиение картинной плоскости.

Алг задающие приближенное решение. Один из первых алг – алг Варнека. Его основные принцы исходят из того, что большая часть вычислений затрачивается на высоко информационные области, считается что в ограниченном видимом объеме пространства можно распознать конечное число возможных ситуаций, для визуализации: а) проекция видимого объема пуста. Она не содержит проекцию ни одного видимого объекта сцены. Проекция объема- окно, которое закрашивается цветом фона. б) окно охватывается полностью ближайшей к нему по глубине грани проекций. Оно закрашивается цветом этой грани. в) размеры окна = 1 пикселю. Этот пиксель закрашивается цветом ближайшей охватывающей грани. г) не распознана не одна из предыдущих ситуаций. Окно разбивается на 4 части. Алг повторяется для каждой снова. Алг быстрый позволяет распараллелить вычисления, применим к удалению ребер и граней. Возможны дефекты из-за относительно произвольной разбивки для распознавания. К данной группе можно отнести один из самых универсальных и используемых алг Загораживания – алг z-буфера, или буфера глубины. Был предложен Кеттулом. Алг прост реализации. Прекрасно сочетается с конвейерной архитектурой графической системы, быстрый. Алг отталкивается от пространства изображения, но включает цикл просмотра полигонов, а не пикселей и м.б. реализован в процессе растрирования объектов. Инф о глубине размещения каждого полигона записывается в z-буфер. Его размеры: К_а х К_в х Г, где Г – количество битов для хранения инф о глубине сцены с приемлемой для количества изображения точностью, К_а – кол-во пикселей по горизонтали, К_в – по вертикали. Инициализируется буфер максимальной глубиной (аналогия с видеопамятью). В процессе преобразования объектов каждая ячейка z-буфера содержит значение расстояния до ближайшего из обработанных полигонов, вдоль проецирующего луча, проходящего через соответствующий пиксель экрана. При растрировании полигона для каждой его точки вычисляется расстояние от центра проецирования до экрана. Оно сравнивается с соответствующим для этой точки значением в z-буфере. Когда значение сравниваемого пикселя больше хранящегося точку в буфер кадра не помещают. В противном случае данный пиксель заменяет точку экрана, а его z-глубина – соответствующую ячейку z-буфера. Объем дополнительных вычислений не велик. Единственный недостаток – большой объем памяти.

Алгоритм построчного сканирования.

Работают в пространстве изображения, обрабатывают сцену, рассекая ее параллельными плоскостями проходящими по сторонам развертки. Для каждой такой плоскости определяется совокупность отрезков – следов пересечения с ней граней объектов, т.е. задача 3D сводится к задаче 2D. Алг данного типа одни из первых были реализованы аппаратно и до недавнего времени считались наиболее эффективными. Отличие алг от алг z-буфера состоит в том, что алг построчн скан должны просматривать при обработке все полигоны претендующие на отображение в данной строке, а алг z-буфера в текущий момент времени имеет дело с одним. Подобные алгоритмы требую тщательно продуманной организации данных для полигонов, используются для создания компьютерных игр и являются универсальными.

Алгоритмы, использующие список приоритетов.

Общая идея – получить преимущество за счет некоторого приоритета, н-р: сортировки по глубине. После такой сортировки любые два объекта не будут взаимно перекрывать друг друга и их можно вывести поочередно, начиная с дальнего. Тогда более близкие объекты затрут более дальние и задача удаления решится сама собой. Для простых объектов сцены алг назыв алг маляра или художника и реализуется аппаратно. К дан группе также относят алг плавающего горизонта, который используется для визуализации сетчатых поверхностей, описываемых неявно f(x,y,z)=0. Работает в пространстве изображения, обладает простотой и высокой скоростью реализации. Использует упорядочение по расстоянию до наблюдателя. Идея в том, что трехмерную задачу сводят к двумерной путем сечения поверхности последовательностью плоскостей имеющей постоянное значение одной их координат: x, y или z .например y = f(x,z_const) или х = f(y,z_const). Получается что поверхность представляется семейством кривых. Алг хранит в памяти координаты 2-горизонтов: верхнего и нижнего т.е. хранится координата z. При отображении каждой новой точки ее координату z сравнивают с соответствующим значением верх и нижн горизонта. Выводятся только пиксели с z координатой  верхнего и  горизонта. Метод просто совмещать с растрированием отрезков. Недостаток: появление дефектов на границах поверхности, в точках быстрого изменения ф-ции и не прямоугольной области определения аргумента функции.